Атака на основе адаптивно подобранного открытого текста (Gmgtg ug kvukfy g;ghmnfuk hk;kQjguukik kmtjdmkik mytvmg)

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

Применение

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

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

История

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

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

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

Еще один пример связан с битвой за Мидуэй. Специалисты ВМС США перехватили японское зашифрованное сообщение, которое сумели частично расшифровать. Оказалось, что японцы планировали атаку на AF, где AF было частью шифртекста, которую специалисты США не смогли расшифровать. Тогда криптоаналитики приказали ВС США на острове отправить фальшивое сообщение о недостатке пресной воды. Японцы перехватили это сообщение и передали своему начальству. Так, криптоаналитики ВМС узнали о запланированной атаке^[4]

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

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

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

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

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

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

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

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

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

Сначала выбирается пара открытых текстов с подобранной разностью. Они подаются на шифрующее устройство. Им соответствуют шифртексты, так же имеющие некоторую разность. Таким образом, набирается статистика из пар вида открытый текст — шифртекст. Далее сопоставляется разность между открытыми текстами с разностью между шифртекстами и на основе собранных данных делается предположение о ключе системы^[6]

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

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

Примеры атак

Атака на алгоритм RSA

Рассмотрим шифрование по алгоритму RSA^[8].

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

Тогда он выбирает случайное число $r\in \mathbb {Z} ^{*}$ , вычисляет сообщение $C_{2}=C\cdot r^{e}\operatorname {mod} N$ и отправляет его пользователю.

После расшифровки пользователь получает:

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

Полученное число $M_{2}$ может показаться пользователю совершенно случайным, поскольку умножение на число $r$ является перестановкой над группой $Z^{*}$ . Если сообщение признаётся случайным набором цифр, то этот набор возвращается отправителю, то есть пользователь отправляет злоумышленнику число $M_{2}$ . Такой алгоритм работы применяется в силу предположения, что расшифрованный текст, имеющий структуру случайного набора чисел, не может быть использован для получения полезной информации^[8].

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

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

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

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

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

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

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

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

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

Так $\Delta B=B-B'=A\operatorname {xor} K-A'\operatorname {xor} K=\Delta A$ .

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

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

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

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

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

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

Пусть P- открытый текст, C - зашифрованный, K-ключ, F - функция шифрования, A, B, D - маски, которые максимизируют вероятность следования линейным соотношениям:

$F(X_{1})\cdot A=X_{1}\cdot D$

$F(X_{3})\cdot B=X_{3}\cdot D$

$F(X_{1})\cdot D=X_{2}\cdot (A\bigoplus B)$ , где $F(X_{i})=F(X_{i},K_{i})$ , $X_{i}$ -вход функции в i-ом раунде.

Тогда уравнение для 16-раундового DES выглядит следующим образом^[7]:

$(P^{L}\cdot A)\bigoplus (F(P^{R},K_{1}^{*})\cdot A)\bigoplus (C^{L}\cdot D)\bigoplus (F(C^{R},K_{16}^{*})\cdot D)\bigoplus (C^{R}\cdot B)=0$ $(1)$

Вероятность для этого уравнения:

$P_{L}^{15}={\frac {1}{2}}+2^{14-1}\prod _{i=2}^{15}(p_{i}-{\frac {1}{2}})$ при правильных предположениях $K_{1}^{*},K_{16}^{*}$ , где

$p_{i}=1,i\in$ {2, 6, 10, 14}

$p_{i}=42/64,i\in$ {3, 9, 11}

$p_{i}=30/64,i\in$ {4, 8, 12}

$p_{i}=12/64,i\in$ {5, 7, 13, 15}

Для других ключей это уравнение будет случайным.

Зафиксируем шесть входных битов в активном S-блоке в первом раунде. Тогда любая выходная маска этой функции является константой 0 или 1 со смещением ${\frac {1}{2}}$ . Затем рассмотрим следующее уравнение^[7]:

$(P^{L}\cdot A)\bigoplus (C^{L}\cdot D)\bigoplus (F(C^{R},K_{n}^{*})\cdot D)\bigoplus (C^{R}\cdot B)=0$

При атаке для каждого значения секретного ключа ведется счетчик, который отслеживает, сколько раз левая часть уравнения равна 0. При N $(P,C)$ -парах ключ со значением счетчика T, самым дальним от ${\frac {N}{2}}$ , принимается за правильное значение ключа^[7].

См. также

Примечания

↑ ¹ ² ³ ⁴ ⁵ Шнайер Б. Криптоанализ // Прикладная криптография. Протоколы, алгоритмы, исходные тексты на языке Си = Applied Cryptography. Protocols, Algorithms and Source Code in C. — М.: Триумф, 2002. — С. 20. — 816 с. — 3000 экз. — ISBN 5-89392-055-4.
↑ Скаляров Д. В. Искусство защиты и взлома информации. — СПб.: БХВ-Петербург, 2004. — С. 56. — 288 с. — ISBN 5-94157-331-6.
↑ Мао Венбо. Современная криптография: теория и практика / пер. с англ. Д. А. Клюшина. — М.: Издательский дом "Вильямс", 2005. — С. 307. — 768 с. — ISBN 5-8459-0847-7.
↑ ¹ ² Джонатан Кац. Введение в современную криптографию. — Бока-Ратон: СиЭрСи, 2016. — 85 с. — ISBN 978-1-4822-5414-3. Архивировано 3 октября 2022 года.
↑ ¹ ² Tony Sale «The Enigma of Bletchley Park» (неопр.). Дата обращения: 30 ноября 2011. Архивировано 5 августа 2011 года.
↑ ¹ ² ³ Heys H. M. A Tutorial on Linear and Differential Cryptanalysis (19-27) // Taylor & Francis. — 2002. — ISSN 0161-1194. Архивировано 17 мая 2017 года.
↑ ¹ ² ³ ⁴ ⁵ Knudsen L. R., Mathiassen J. E. A Chosen-Plaintext Linear Attack on DES (англ.) // International Workshop on Fast Software Encryption. — 2000. — 10 April (vol. 7). — P. 262-272. — ISSN 978-3-540-41728-6. Архивировано 2 октября 2022 года.
↑ ¹ ² ³ Y. Desmedt, A. M. Odlyzko. A chosen text attack on the RSA cryptosystem and some discrete logarithm schemes (англ.) // Lecture Notes in Computer Science. — 2000. — 1 January. — ISSN 1611-3349. Архивировано 30 сентября 2022 года.

Литература

Мао В. Современная криптография: Теория и практика / пер. Д. А. Клюшина — М.: Вильямс, 2005. — 768 с. — ISBN 978-5-8459-0847-6
Скляров Д. В. Искусство защиты и взлома информации.
Брюс Шнайер. Прикладная криптография. Протоколы, алгоритмы, исходные тексты на языке Си.
Панасенко Сергей. "Современные методы вскрытия алгоритмов шифрования, часть 3". Chief Information Officer - 2006. Архивная копия от 15 января 2010 на Wayback Machine
Панасенко Сергей. "Современные методы вскрытия алгоритмов шифрования, часть 4". Chief Information Officer - 2006. Архивная копия от 21 мая 2009 на Wayback Machine

[:0-1] ¹ ² ³ ⁴ ⁵ Шнайер Б. Криптоанализ // Прикладная криптография. Протоколы, алгоритмы, исходные тексты на языке Си = Applied Cryptography. Protocols, Algorithms and Source Code in C. — М.: Триумф, 2002. — С. 20. — 816 с. — 3000 экз. — ISBN 5-89392-055-4.

[2] Скаляров Д. В. Искусство защиты и взлома информации. — СПб.: БХВ-Петербург, 2004. — С. 56. — 288 с. — ISBN 5-94157-331-6.

[3] Мао Венбо. Современная криптография: теория и практика / пер. с англ. Д. А. Клюшина. — М.: Издательский дом "Вильямс", 2005. — С. 307. — 768 с. — ISBN 5-8459-0847-7.

[:4-4] ¹ ² Джонатан Кац. Введение в современную криптографию. — Бока-Ратон: СиЭрСи, 2016. — 85 с. — ISBN 978-1-4822-5414-3. Архивировано 3 октября 2022 года.

[autogenerated1-5] ¹ ² Tony Sale «The Enigma of Bletchley Park» (неопр.). Дата обращения: 30 ноября 2011. Архивировано 5 августа 2011 года.

[:2-6] ¹ ² ³ Heys H. M. A Tutorial on Linear and Differential Cryptanalysis (19-27) // Taylor & Francis. — 2002. — ISSN 0161-1194. Архивировано 17 мая 2017 года.

[:1-7] ¹ ² ³ ⁴ ⁵ Knudsen L. R., Mathiassen J. E. A Chosen-Plaintext Linear Attack on DES (англ.) // International Workshop on Fast Software Encryption. — 2000. — 10 April (vol. 7). — P. 262-272. — ISSN 978-3-540-41728-6. Архивировано 2 октября 2022 года.

[:3-8] ¹ ² ³ Y. Desmedt, A. M. Odlyzko. A chosen text attack on the RSA cryptosystem and some discrete logarithm schemes (англ.) // Lecture Notes in Computer Science. — 2000. — 1 January. — ISSN 1611-3349. Архивировано 30 сентября 2022 года.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]