Подделка подписей. Анализ возможностей подделки подписей называется криптоанализ. Попытку сфальсифицировать подпись или подписанный документ криптоаналитики называют «атака»

Виды асимметричных алгоритмов ЭЦП. Как было сказано выше, чтобы применение ЭЦП имело смысл, необходимо, чтобы вычисление легитимной подписи без знания закрытого ключа было вычислительно сложным процессом.

Обеспечение этого во всех асимметричных алгоритмах цифровой подписи опирается на следующие вычислительные задачи:

§ Задачу дискретного логарифмирования (EGSA).

§ Задачу факторизации, то есть разложения числа на простые множители (RSA).

Вычисления тоже могут производиться двумя способами: на базе математического аппарата эллиптических кривых (ГОСТ Р 34.10-2001) и на базе полей Галуа (DSA). В настоящее время самые быстрые алгоритмы дискретного логарифмирования и факторизации являются субэкспоненциальными. Принадлежность самих задач к классу NP-полных не доказана.

Алгоритмы ЭЦП подразделяются на обычные цифровые подписи и на цифровые подписи с восстановлением документа. При верификации цифровых подписей с восстановлением документа тело документа восстанавливается автоматически, его не нужно прикреплять к подписи. Обычные цифровые подписи требуют присоединение документа к подписи. Ясно, что все алгоритмы, подписывающие хеш документа, относятся к обычным ЭЦП. К ЭЦП с восстановлением документа относится, в частности, RSA.

Схемы цифровой подписи могут быть одноразовыми и многоразовыми. В одноразовых схемах после проверки подлинности подписи необходимо провести замену ключей, в многоразовых схемах это делать не требуется.

Также алгоритмы ЭЦП делятся на детерминированные и вероятностные. Детерминированные ЭЦП при одинаковых входных данных вычисляют одинаковую подпись. Реализация вероятностных алгоритмов более сложна, так как требует надежный источник энтропии, но при одинаковых входных данных подписи могут быть различны, что увеличивает криптостойкость. В настоящее время многие детерминированные схемы модифицированы в вероятностные.

В некоторых случаях, таких как потоковая передача данных, алгоритмы ЭЦП могут оказаться слишком медленными. В таких случаях применяется быстрая цифровая подпись. Ускорение подписи достигается алгоритмами с меньшим количеством модульных вычислений и переходом к принципиально другим методам расчета.

Перечень алгоритмов ЭЦП. Асимметричные схемы:

§ FDH (Full Domain Hash), вероятностная схема RSA-PSS (Probabilistic Signature Scheme), схемы стандарта PKCS#1 и другие схемы, основанные на алгоритме RSA

§ Схема Эль-Гамаля.

§ Американские стандарты электронной цифровой подписи: DSA, ECDSA (DSA на основе аппарата эллиптических кривых).

§ Российские стандарты электронной цифровой подписи: ГОСТ Р 34.10-94 (в настоящее время не действует), ГОСТ Р 34.10-2001.

§ Схема Диффи-Лампорта.

§ Украинский стандарт электронной цифровой подписи ДСТУ 4145-2002.

§ Белорусский стандарт электронной цифровой подписи СТБ 1176.2-99.

§ Схема Шнорра.

§ Pointcheval-Stern signature algorithm.

§ Вероятностная схема подписи Рабина.

§ Схема BLS (Boneh-Lynn-Shacham).

§ Схема GMR (Goldwasser-Micali-Rivest).

На основе асимметричных схем созданы модификации цифровой подписи, отвечающие различным требованиям:

§ Групповая цифровая подпись

§ Неоспоримая цифровая подпись

§ «Слепая» цифровая подпись и справедливая «слепая» подпись

§ Конфиденциальная цифровая подпись

§ Цифровая подпись с доказуемостью подделки

§ Доверенная цифровая подпись

Модели атак и их возможные результаты. В своей работе Гольдвассер, Микали и Ривест описывают следующие модели атак, которые актуальны и в настоящее время:

§ Атака с использованием открытого ключа. Криптоаналитик обладает только открытым ключом.

§ Атака на основе известных сообщений. Противник обладает допустимыми подписями набора электронных документов, известных ему, но не выбираемых им.

§ Адаптивная атака на основе выбранных сообщений. Криптоаналитик может получить подписи электронных документов, которые он выбирает сам.

Также описана классификация возможных результатов атак:

§ Полный взлом цифровой подписи. Получение закрытого ключа, что означает полный взлом алгоритма.

§ Универсальная подделка цифровой подписи. Нахождение алгоритма, аналогичного алгоритму подписи, что позволяет подделывать подписи для любого электронного документа.

§ Выборочная подделка цифровой подписи. Возможность подделывать подписи для документов, выбранных криптоаналитиком.

§ Экзистенциальная подделка цифровой подписи. Возможность получения допустимой подписи для какого-то документа, не выбираемого криптоаналитиком.

Ясно, что самой «опасной» атакой является адаптивная атака на основе выбранных сообщений, и при анализе алгоритмов ЭЦП на криптостойкость нужно рассматривать именно ее (если нет каких-либо особых условий).

При безошибочной реализации современных алгоритмов ЭЦП получение закрытого ключа алгоритма является практически невозможной задачей из-за вычислительной сложности задач, на которых ЭЦП построена. Гораздо более вероятен поиск криптоаналитиком коллизий первого и второго рода. Коллизия первого рода эквивалентна экзистенциальной подделке, а коллизия второго рода — выборочной. С учетом применения хеш-функций, нахождение коллизий для алгоритма подписи эквивалентно нахождению коллизий для самих хеш-функций.

Подделка документа (коллизия первого рода). Злоумышленник может попытаться подобрать документ к данной подписи, чтобы подпись к нему подходила. Однако в подавляющем большинстве случаев такой документ может быть только один. Причина в следующем:

§ Документ представляет из себя осмысленный текст.

§ Текст документа оформлен по установленной форме.

§ Документы редко оформляют в виде Plain Text — файла, чаще всего в формате DOC или HTML.

Если у фальшивого набора байт и произойдет коллизия с хешем исходного документа, то должны выполниться 3 следующих условия:

§ Случайный набор байт должен подойти под сложно структурированный формат файла.

§ То, что текстовый редактор прочитает в случайном наборе байт, должно образовывать текст, оформленный по установленной форме.

§ Текст должен быть осмысленным, грамотным и соответствующий теме документа.

Впрочем, во многих структурированных наборах данных можно вставить произвольные данные в некоторые служебные поля, не изменив вид документа для пользователя. Именно этим пользуются злоумышленники, подделывая документы.

Вероятность подобного происшествия также ничтожно мала. Можно считать, что на практике такого случиться не может даже с ненадёжными хеш-функциями, так как документы обычно большого объёма — килобайты.

Получение двух документов с одинаковой подписью (коллизия второго рода). Куда более вероятна атака второго рода. В этом случае злоумышленник фабрикует два документа с одинаковой подписью, и в нужный момент подменяет один другим. При использовании надёжной хэш-функции такая атака должна быть также вычислительно сложной. Однако эти угрозы могут реализоваться из-за слабостей конкретных алгоритмов хэширования, подписи, или ошибок в их реализациях. В частности, таким образом можно провести атаку на SSL-сертификаты и алгоритм хеширования MD5.