Атака на основе подобранного открытого текста

Атака на основе подобранного открытого текста (англ. Chosen-plaintext attack, CPA) — один из 4 основных способов криптоаналитического вскрытия^[1]. Криптоаналитик обладает определённым числом открытых текстов и соответствующих шифротекстов, кроме того, он имеет возможность зашифровать несколько предварительно выбранных открытых текстов.

Описание

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

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

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

Использование

В истории

Атакой на основе подобранного открытого текста широко пользовались спецслужбы во время Второй Мировой Войны.

В 1942 году криптоаналитики военно-морских сил США перехватили сообщение о готовящейся атаке на загадочное «AF». В NAVY полагали, что «AF» — это острова Мидуэй, но Пентагон считал иначе. Для уточнения информации (по сути — для вскрытия шифра) Вооруженные силы США на Мидуэй сообщили о недостатке запасов пресной воды. Вскоре американские спецслужбы перехватили японский шифротекст с докладом о том, что на «AF» мало пресной воды. Это подтверждало, что «AF» — не что иное, как острова Мидуэй.

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

Британская разведка также применяла CPA при дешифровании немецкой переписки (gardening). Британцы провоцировали противника использовать определённые слова и названия в текстах сообщений. Например, если немцы в недавнем времени освободили какой-либо участок прибрежных вод от мин, британские спецслужбы могли объявить о том, что данная территория была снова заминирована. Это провоцировало поток зашифрованных сообщений от местного командования, включающих слово «мины» и название территории. А также реакцию от командования, содержащую названия направленных туда кораблей и т. д. Так британцы достаточно эффективно могли подбирать открытый текст и анализировать его шифрограммы. Так как британцы могли делать выводы на основе полученной информации и так или иначе выбирать следующий открытый текст, подлежащий шифрованию немецкими спецслужбами, данную атаку можно отчасти классифицировать как атаку на основе адаптивно подобранного открытого текста.

В современной криптографии

Атака на основе подобранного открытого текста актуальна при криптоанализе современных систем шифрования.

Симметричные криптосистемы

Рис.1. Алгоритм шифрования

Рис.2 Атака на основе подобранного открытого текста

В качестве простой иллюстрации атаки на основе подобранного открытого текста, рассмотрим пример атаки на один из алгоритмов шифрования изображений, работающий в режиме последовательного сцепления блоков шифротекста. Ключевая последовательность произвольной длины (совпадающей с количеством пикселей изображения) генерируется на основе 127-значного исходного ключа (англ. Master Key). Шифротекст формируется с использованием этой последовательности. Дешифрующий алгоритм представляет собой обращенный алгоритм шифрования. (рис. 1)^[2]. В качестве шифруемого изображения взято стандартное тестовое изображение Лена. Для осуществления атаки выбирают специальный открытый текст — изображение, состоящее из чёрных пикселей. Шифротекст, соответствующий подобранному открытому изображению, позволяет вычислить ключ, который использовался при шифровании. Зная его, можно получить исходную картинку из зашифрованной.(рис. 2)

Как видно из предыдущего примера, к атаке с использованием выбранного открытого текста чувствительны некоторые симметричные шифры (использующие один и тот же ключ для шифрования и дешифрования). Очередным подтверждением этому может служить метод дифференциального криптоанализа, предложенный Эли Бихамом и Ади Шамиром в 1990 году^[3]. (позже стало известно, что эта техника была известна IBM и NSA/CCS, но была засекречена)^[1]. В основе метода лежит исследование дифференциалов пар шифротекстов, полученных от специально подобранных сообщений. Изначально данный метод был применен для системы DES, но позже был распростран`н на другие блочные шифры (Khafre, REDOC-II, LOKI, Lucifer, Feal), а также хэш-функции (Snefru, N-Hash)

Асимметричные криптосистемы

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

Самым простым примером может служить перебор по словарю (англ. dictionary-type attack). Криптоаналитик строит таблицу из наиболее часто используемых сообщений и соответствующих шифрограмм. Для расшифровки (частичной) некоторого шифротекста достаточно найти соответствующий открытый текст в таблице.

В качестве следующей иллюстрации, рассмотрим систему (как HTTPS), использующую асимметричный алгоритм для передачи сеансового ключа. Криптоаналитик располагает открытым ключом, E, и зашифрованным с его помощью сеансовым ключом, CK = F(K, E). Не имея закрытого ключа, он не может дешифровать CK, но он может попытаться подобрать подходящее значение K. Угроза такой атаки возрастает с уменьшением длины зашифрованного сообщения (в данном случае сеансового ключа), а также при сужении множества возможных шифруемых сообщений. Кроме того, известно, что асимметричный алгоритм RSA слабо защищен от CPA, если показатель степени при дешифровании (обычно d) мал^[4].

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

Упоминания в художественной литературе

В рассказе «Пляшущие человечки» Артура Конана Дойля о сыщике Шерлоке Холмсе главный герой успешно применяет атаку на основе выбранного открытого текста для разоблачения тайны загадочных рисунков, вокруг которых закручивается сюжет. Пляшущие человечки оказались шифром простой замены.

Атака на основе адаптивно подобранного открытого текста

Атака на основе адаптивно подобранного открытого текста (англ. adaptive chosen-plaintext attack) — также способ криптоаналитического вскрытия, являющийся расширением атаки на основе подобранного открытого текста. Отличие заключается в том, что помимо возможности предварительного выбора шифруемого текста, криптоаналитик может принять решение о выборе шифруемого текста на основе уже полученных данных.

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

Задача криптоаналитика остается прежней — получить ключ или построить эквивалентную систему шифрования.

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

Примечания

1. ↑ ^{1 2} Брюс Шнайер Прикладная криптография.
2. ↑ Jun Yoon, Jeong-Woo Hong, Sang-Yoon Yoon, Dong-In Park,Myung-Jin Choi Cryptanalysis of an Enhanced Spatiotemporal Chaotic Image/Video Cryptosystem.
3. ↑ Eli Biham, Adi Shamir Differential cryptanalysis of DES-like cryptosystems // CRYPTO'90 & Journal of Cryptology. — 1991. — В. 1. — Т. 4. — С. 3-72.
4. ↑ M. Wiener Efficient DES key search.

Литература

• Дэвид Кан Взломщики кодов.