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

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

Применение.

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

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

История.

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

Так, криптоаналитики из Блетчли-Парка могли определить открытый текст сообщений в зависимости от того, когда эти сообщения были посланы. Например, ежедневный отчет о погоде посылался немецкими связистами в одно и то же время. По той причине, что военные доклады имеют определенную структуру, криптоаналитикам удавалось расшифровывать остальную информацию, пользуясь данными о погоде в той местности.^[1]

Другим ярким примером являлись перехваченные сообщения офицера африканского корпуса, который постоянно отсылал «Нечего докладывать». Другие операторы тоже часто использовали стандартные ответы или приветствия.^[1]

Так же в Блетчли-Парк был придуман следующий способ заставить немцев отсылать определенные сообщения. По просьбе криптоаналитиков Королевские военно-воздушные силы Великобритании минировали определенные участки Северного моря, этот процесс был назван «Садоводством» (англ. "gardening"^[2]). Практически сразу после этого немцами посылались зашифрованные сообщения с названиями мест, где были сброшены мины.^[1]

После того, как немецкий военнопленный при допросе рассказал, что операторы Энигмы записывали цифры прописью, криптоаналитик Алан Тьюринг, анализируя присутствие в текстах наличие слова “eins” (нем. "один"), смог извлечь много информации о возможных положениях роторов и настройках клавиатуры Энигмы.^[1]

Сравнение с другими видами атак.

Согласно Брюсу Шнайеру, предполагая, что криптоаналитик знает алгоритм шифрования, можно выделить 4 основных вида криптоанализа^[3]:

1. Атака на основе шифротекста
2. Атака на основе открытых текстов и соответствующих шифртекстов
3. Атака на основе подобранного открытого текста (возможность выбрать текст для шифрования)
4. Атака на основе адаптивно подобранного открытого текста

В случае атаки на основе открытых текстов и соответствующих шифртекстов криптоаналитик имеет доступ к некоторым парам текст — шифртекст.

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

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

Алгоритм атаки.

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

Дифференциальный криптоанализ;

1. Выбирается пара открытых текстов с подобранной разностью
2. Тексты подаются на шифрующее устройство
3. Соответствующие шифртексты так же будут иметь некоторую разность
4. Набирается статистика из пар вида открытый текст — шифртекст
5. Сопоставляются разность между открытыми текстами с разностью между шифртекстами
6. На основе собранных данных делается предположение о ключе системы

Линейный криптоанализ.

Основная задача криптоаналитика заключается в получении следующего однораундового соотношения:

$P_{i_1} \oplus P_{i_2} \oplus ... \oplus P_{i_a} \oplus C_{j_1} \oplus C_{j_2} \oplus ... \oplus C_{j_b} = K_{k_1} \oplus K_{k_2} \oplus ... \oplus K_{k_c},$

где $P_{i}$ - i-ый бит открытого текста

$C_{j}$ - j-ый бит зашифрованного текста

$K_{k}$ - k-ый бит ключа

Данное соотношение называется линейной аппроксимацией. Для открытого текста, шифртекста и ключа, выбранных произвольным образом, вероятность этого сообщения примерно составляет 1/2. Если же пользоваться специальными алгоритмами, то эту вероятность можно существенно увеличить.

Аппроксимация с заданным условием на вероятность может быть найдена довольно легко. Проблема возникает при экстраполировании метода на полнораундовое шифрование. Точное решение этой проблемы невозможно, так как при этом криптоаналитику придется проанализировать все возможные варианты открытых текстов и шифртекстов. Зато после ряда предположений появляется возможность использование леммы о набегании знаков (англ. "Piling-up lemma"). Таким образом линейная аппроксимация представляется в виде цепочки аппроксимаций, называемой линейной характеристикой. Вероятность такой характеристики находится по формуле:

$P = \frac{1}{2} + 2^{n-1}\prod_{i=1}^{n} (p_i - \frac{1}{2})$

Примеры атак.

Для систем с открытым ключом;

• Обоснование

Во многих криптоаналитических системах применяется следующий режим работы:

1. Принимается сообщение от отправителя
2. Сообщение расшифровывается и далее обрабатывается
3. Если сообщение признаются случайным набором цифр, то этот набор возвращается отправителю

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

• Атака

При данной модели работы криптоаналитической системы, работающей на основе алгоритма RSA, рассмотрим следующий пример:

Пусть криптоаналитик перехватил некоторое сообщение $C = M^{e} mod N \,$, которое он хочет расшифровать.

Тогда злоумышленник начинает действовать по следующему алгоритму:

1. Выбирается случайное число $r\in\Z^{*} \,$
2. Зная, открытый ключ $e$, вычисляется сообщение $C_{2} = C*r^{e} mod N \,$
3. Сообщение $C_{2} \,$ отправляется пользователю, который после расшифровки получает

$M_{2} = C_{2}^{d} mod N = ((M*r)^{e})^{d} mod N = M*r \,$

1. Полученное число $M_{2} \,$ может показаться пользователю совершенно случайным, поскольку умножение на число $r \,$ является перестановкой над группой $Z^{*} \,$
2. Согласно представленной выше схеме работы алгоритма, пользователь отправляет злоумышленнику число $M_{2} \,$

Таким образом, у криптоаналитика в распоряжении будут иметься числа $r \,$ и $M*r \,$, тогда, деля их по модулю $N \,$, злоумышленник сможет узнать значение $M \,$.

Атака с использованием методов дифференциального криптоанализа;

Дифференциальный криптоанализ алгоритма DES

Основная статья: Дифференциальный криптоанализ

Рассмотрим для примера шифрование по алгоритму DES.

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

Пусть $X \,$ и $X' \,$ — подобранные открытые тексты с разностью $\Delta\ X \,$.

Им будут соответствовать шифртексты $Y \,$ и $Y' \,$ с разностью — $\Delta\ Y \,$.

Так как известны перестановки с расширением в $P \,$-блок, то известны $\Delta\ A \,$ и $\Delta\ C \,$.

Значения $B \,$ и $B' \,$ остаются неизвестными, зато можем найти их разность.

Так $\Delta\ \,$ $B = B - B' = A xor K - A' xor K = \,$ $\Delta\ A \,$.

Последнее выражение верно, так как совпадающие биты $A \,$ и $A' \,$ сократятся, а различные дадут разницу, несмотря на $xor \,$.

Процесс подбора ключа основан на том, что для заданного $\Delta\ A \,$ различные $\Delta\ C \,$ будут встречаться с разной вероятностью.

Таким образом, комбинации $\Delta\ A \,$ и $\Delta\ C \,$ позволяют с некоторой вероятностью предположить значения $A xor K \,$ и $A' xor K \,$. Что, при известных $A \,$ и $A' \,$, позволит найти ключ $K \,$.

Таким образом, заданные отличия открытых текстов с достаточной большой вероятностью вызовут определенные отличия полученных шифртекстов. Эти различия называются характеристиками. Характеристики находятся при помощи таблиц, построенных следующим образом: строкам соответствуют возможные $\Delta\ X \,$, столбцам — $\Delta\ Y \,$. На пересечении данной строки и столбца записывается, сколько раз при данных $\Delta\ X \,$ на входе, на выходе получили $\Delta\ Y \,$. Так как каждая из итераций независима, то различные характеристики можно объединять, перемножая их вероятности. Зная распределение вероятности, можно с высокой степенью точности подобрать ключ.

Атака с использованием методов линейного криптоанализа.

Основная статья: Линейный криптоанализ

Применение к DES

Эксперименты Мицуру Мацуи по атакам по открытому тексту (вычисления проводились на HP9750 66МГц) дали следующие результаты^[4]:

• 8-ми раундовый DES взламывается с помощью 2²¹ известных открытых текстов. Это заняло у Мацуи 40 секунд.
• 12-ти раундовый DES взламывается с помощью 2³³ известных открытых текстов. На это потребовалось 50 часов.
• На 16-ти раундовый DES требуется 2⁴⁷ известных открытых текстов. Данная атака обычно не практична. Однако, метод работает быстрее, чем исчерпывающий поиск 56-ти битного ключа.

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

Весьма часто линейный криптоанализ используется вместе с методом «грубой силы» — после того, как определённые биты ключа найдены с помощью линейного криптоанализа, проводится исчерпывающий поиск по возможным значениям остальных бит. Для взлома DES подобным образом требуется 2⁴³ открытых текстов.

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

Примечания.

1. ↑ ^{1 2 3 4} Tony Sale "The Enigma of Bletchley Park"
2. ↑ 90 Squadron
3. ↑ Шнайер Б. Криптоанализ // Прикладная криптография. Протоколы, алгоритмы, исходные тексты на языке Си = Applied Cryptography. Protocols, Algorithms and Source Code in C. — М.: Триумф, 2002. — С. 20. — 816 с. — 3000 экз. — ISBN 5-89392-055-4
4. ↑ Mitsuru Matsui "Linear Cryptanalysis Method for DES Cipher"

См. также.

• Атака на основе шифртекста
• Атака на основе открытых текстов
• Атака на основе подобранного открытого текста
• Атака на основе подобранного шифротекста
• Атака на основе подобранного ключа
• Дифференциальный криптоанализ
• Линейный криптоанализ

Литература.

1. Венбо Мао Современная криптография: теория и практика.
2. Скляров Д.В. Искусство защиты и взлома информации.
3. А.Г. Ростовцев, Н.В. Михайлова Методы криптоанализа классических шифров.
4. Брюс Шнайер Прикладная криптография. Протоколы, алгоритмы, исходные тексты на языке Си.
5. Панасенко, С. "Современные методы вскрытия алгоритмов шифрования, часть 3". Chief Information Officer - 2006. 
6. Панасенко, С. "Современные методы вскрытия алгоритмов шифрования, часть 4". Chief Information Officer - 2006.