1.3 Формальные модели атак и угроз

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

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

Стойкость криптографической схемы определяется относительно пары (атака, угроза). Одним из важнейших направлений теоретических исследований является поиск схем, стойких против самой слабой из известных угроз, в предположении, что противник может провести самую сильную из возможных атак. Необходимо подчеркнуть, что никакая криптографическая схема не может быть стойкой "вообще". Классическим примером здесь может служить шифр Вернама, абсолютно стойкий против пассивного подслушивания. Однако, если задача активного противника состоит просто в изменении данного фиксированного бита открытого текста на противоположный, то он легко может осуществить эту угрозу. Другой весьма известный пример -- криптосистема Рабина, доказуемо стойкая (в предположении трудности задачи факторизации целых чисел) против атаки с выбором открытого текста, но нестойкая против атаки с выбором шифртекста.

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

Опишем сначала атаки на криптосистемы с секретным ключом.

Атака с известным шифртекстом (ciphertext-only attack). Самая слабая из всех возможных атак. Предполагается, что противник знает криптосистему, т. е., алгоритмы шифрования и дешифрования, но не знает секретный ключ. Кроме этого, ему известен лишь набор перехваченных криптограмм.

Атака с известным открытым текстом (known-plaintext attack). То же, что предыдущая, но противник получает в свое распоряжение еще некоторый набор криптограмм и соответствующих им открытых текстов.

Простая атака с выбором открытого текста (chosen-plaintext attack). Предполагается, что противник имеет возможность выбрать необходимое количество открытых текстов и получить их криптограммы. При этом все открытые тексты должны быть выбраны заранее, т. е., до получения первой криптограммы. В зарубежной литературе эту атаку часто называют "полуночной" атакой (midnight attack) или coffee-break attack, что соответствует реальной ситуации, когда персонал оставил устройство шифрования в рабочем состоянии и им временно завладел противник. Хотя секретный ключ ему недоступен, противник может зашифровать подготовленные им открытые тексты, что дает ему дополнительную информацию для нападения на криптосистему.

Адаптивная атака с выбором открытого текста. То же, что предыдущая, но, выбирая очередной открытый текст, противник уже знает криптограммы всех предыдущих.

Простая атака с выбором шифртекста (chosen-ciphertext attack). Противник имеет возможность выбрать необходимое количество криптограмм и получить соответствующие им открытые тексты. При этом все криптограммы должны быть выбраны заранее, т. е., до получения первого открытого текста.

Адаптивная атака с выбором шифртекста. То же, что предыдущая, но, выбирая очередную криптограмму, противник уже знает открытые тексты, соответствующие всем предыдущим.

Атака с выбором текста (chosen-text attack). Противник имеет возможность атаковать криптосистему "с обоих концов", т. е., выбирать как криптограммы (и дешифровать их), так и открытые тексты (и шифровать их). Атака с выбором текста может быть простой, адаптивной, а также простой "с одного конца" и адаптивной с другого.

Атаки перечислены в порядке возрастания их силы, т. е., атака с выбором текста является самой сильной из всех известных атак на криптосистемы.

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

Кроме того, существуют атаки, специфические для криптосистем с открытым ключом. Например, если число возможных открытых текстов невелико, то противник, зная открытый ключ, может заранее заготовить достаточное количество криптограмм и затем, сравнивая эти "заготовки" с перехваченными криптограммами, с высокой вероятностью получать соответствующие открытые тексты. Такая атака называется атакой с проверкой текста (verifiable-text attack). Заметим, что эта атака невозможна для криптосистем вероятностного шифрования.

Типы угроз не имеют столь четкой классификации как типы атак. В литературе зачастую наблюдается следующая ситуация: дается достаточно точное определение типа атаки, относительно которой рассматривается стойкость криптосистемы, но ничего не говорится о том, что понимается под раскрытием криптосистемы, т.е., в чем состоит задача противника. Выделим все же следующие (перечисленные в порядке ослабления) типы угроз.

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

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

Частичное раскрытие. Противник в результате атаки получает частичную информацию о секретном ключе или об открытом тексте. Хотя такая угроза довольно часто обсуждается в литературе, в общем случае дальше словесных формулировок дело не идет. Причина, по-видимому, в том, что само понятие частичной информации весьма расплывчато и может быть уточнено множеством различных способов. Угроза частичного раскрытия формализована лишь для абсолютно стойких (в шенноновском смысле) криптосистем и криптосистем вероятностного шифрования.

Приведем теперь классификацию типов атак на схемы электронной подписи, предложенная Гольдвассер, Микали и Ривестом [GMRiv]. Атаки перечисляются таким образом, что каждая последующая сильнее предыдущей.

Атака с известным открытым ключом. Противник знает только открытый ключ схемы электронной подписи. Это -- самая слабая из всех возможных атак. Очевидно, что противник всегда может провести такую атаку.

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

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

Направленная атака с выбором сообщений. То же, что предыдущая, но противник, выбирая сообщения, уже знает открытый ключ.

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

Угрозами для схемы электронной подписи являются раскрытие схемы или подделка подписи. Гольдвассер, Микали и Ривест [GMRiv] уточняют понятие угрозы, определяя следующие (перечисленные в порядке ослабления) типы угроз.

Полное раскрытие, т.е., вычисление секретного ключа.

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

Селективная подделка. Подделка подписи для сообщения, выбранного противником. При этом предполагается, что это сообщение выбирается априори (до начала атаки) и что если противник проводит атаку с выбором сообщений, то сообщение, для которого требуется подделать подпись, не может входить в число выбираемых во время атаки.

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

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