Атака методом бумеранга (Gmgtg bymk;kb Qrbyjguig)

Атака методом бумеранга – криптографическая атака на блочный шифр, основанная на методах дифференциального криптоанализа. Алгоритм атаки был опубликован в 1999 году профессором университета Беркли Дэвидом Вагнером, который использовал его для взлома шифров COCONUT98, Khufu и CAST-256 ^[1].

Этот метод позволил провести успешные атаки на многие шифры, ранее признанные устойчивыми к "классическому" дифференциальному криптоанализу.

Существуют модификации данного метода криптоанализа: усиленная атака методом бумеранга (amplified boomerang attack) и прямоугольная атака (rectangle attack).

Общая характеристика

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

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

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

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

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

Сперва предположим, что алгоритм шифрования $E$ можно разбить на две последовательные примерно равные по трудоёмкости части $E_{0}$ и $E_{1}$ , причём $E(M)=E_{1}(E_{0}(M))$ , где $M$ – некоторый открытый текст. Например, 16-раундовый алгоритм DES с раундами сходной структуры можно разделить на две части по 8 раундов
Выберем пару открытых текстов $P$ и $P^{'}$ с разностью $\Delta =P\oplus P'$ . В результате обработки этих текстов функцией $E_{0}$ получим разность $\Delta ^{*}=E_{0}(P)\oplus E_{0}(P^{'})$
Продолжим зашифровывать открытые тексты $P$ и $P'$ функцией $E_{1}$ и получим два шифртекста $C=E_{1}(E_{0}(P))$ и $C^{'}=E_{1}(E_{0}(P^{'}))$
Используем $C$ и $C^{'}$ для получения двух других шифртекстов $D$ и $D^{'}$ , связанных с предыдущими разностью $\nabla =C\oplus D=C^{'}\oplus D'$
Далее формирование квартета продолжается в обратную сторону: к $D$ и $D^{'}$ применяются функции "полу-расшифрования" $E_{1}^{-1}$ и $E_{0}^{-1}$ для получения разности $\nabla ^{*}=E_{1}^{-1}(D)\oplus E_{0}(P)=E_{1}^{-1}(D^{'})\oplus E_{0}(P^{'})$
Дальнейшее расшифрование шифртекстов $D$ и $D^{'}$ даёт два открытых текста $Q=E_{0}^{-1}(E_{1}^{-1}(D))$ и $Q^{'}=E_{0}^{-1}(E_{1}^{-1}(D^{'}))$

Причем в своей работе^[1] Вагнер доказывает, что разность между полученными таким образом открытыми текстами $Q$ и $Q^{'}$ равна разности между исходными открытыми текстами $P$ и $P^{'}$ и равна $\Delta$ .

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

Усиленная атака методом бумеранга^[2]

Усиленная атака методом бумеранга - атака на основе открытого текста, тогда как классическая атака методом бумеранга является атакой на основе адаптивно подобранного открытого текста.

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

При атаке на основе открытых текстов можно подбирать ключ в конце шифра, и для этого не нужно увеличивать количество выбранных открытых текстов.
Можно применять усиленную атаку бумерангом не только к парам, но и к K-наборам текстов.
Можно использовать усиленную атаку, чтобы получить пару (или К) текстов для какой-то части шифра, а затем использовать другие алгоритмы для оставшихся раундов шифра. Таким образом, можно использовать усеченные дифференциалы (англ. truncated differential cryptanalysis), которые задают лишь небольшую часть блока, и не могут быть использованы со стандартной атакой методом бумеранга.

Алгоритмы шифрования, уязвимые для атак методом бумеранга

Описанные в оригинальной статье^[1]

COCONUT98 взламывается с $2^{16}$ адаптивно подобранными открытыми текстами и шифртекстами.
16-раундовый Khufu взламывается с $2^{18}$ адаптивно подобранными открытыми текстами и шифртекстами.
16-раундовый CAST-256 взламывается с $2^{49.3}$ известными текстами.

Описанные в других источниках

6-раундовый KASUMI взламывается с $2^{13}$ адаптивно подобранными открытыми текстами и шифртекстами^[3].
11-раундовый MARS взламывается с $2^{65}$ известными текстами^[2].
8-раундовый Serpent взламывается с $2^{114}$ известными текстами^[2].
5-раундовый AES взламывается с $2^{39}$ известными текстами^[4].
6-раундовый AES взламывается с $2^{71}$ известными текстами^[4].

Применение к полнораундовому AES^[5]

Для осуществления атаки на основе связанных ключей на полнораундовые шифры AES-192 и AES-256 были применены принципы атаки методом бумеранга и улучшенной атаки методом бумеранга. Данный метод опирается на обнаружение локальных коллизий в блочных шифрах и использование бумеранговых переключателей (boomerang switches).

По умолчанию, шифр разбивается на раунды, но такое деление не всегда является наилучшим для применения атаки методом бумеранга. Было предложено разделить раунды на простые операции и использовать существующий в этих операциях параллелизм. Например, некоторые байты могут быть обработаны независимо. В таком случае сначала может быть обработан один байт до преобразования алгоритмом шифрования, после чего происходит переключение на обработку другого байта после преобразования. Существуют лестничные переключатели (ladder switches), переключатели Фейстеля (Feistel switches) и переключатели s-блоков (s-box switches).

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

Применение к хеш-функциям

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

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

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

Данная атака была успешно применена к алгоритму SHA-1.

Недостатки алгоритма

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

Как и для метода дифференциального криптоанализа применение на практике атаки методом бумеранга ограничено высокими требованиями к времени обработки и объёму данных.

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

В связи с этим алгоритм в большей степени является теоретическим достижением.

Примечания

↑ ¹ ² ³ David Wagner . The Boomerang Attack . Архивировано 2015-09-23 .
↑ ¹ ² ³ John Kelsey, Tadayoshi Kohno, Bruce Schneier. Amplified Boomerang Attacks Against Reduced-Round MARS and Serpent. Архивировано 6 июня 2012 года.
↑ Eli Biham, Orr Dunkelman, Nathan Keller. A Related-Key Rectangle Attack on the Full KASUMI. Архивировано 25 декабря 2014 года.
↑ ¹ ² Alex Biryukov. The Boomerang Attack on 5 and 6-round Reduced AES. Архивировано 5 февраля 2012 года.
↑ Alex Biryukov, Dmitry Khovratovich. Related-key Cryptanalysis of the Full AES-192 and AES-256. Архивировано 24 августа 2015 года.
↑ Antoine Joux, Thomas Peyrin. Hash Functions and the (Amplified) Boomerang Attack. Архивировано 27 декабря 2014 года.

Литература

Панасенко С. П. Алгоритмы шифрования. Специальный справочник — СПб.: BHV-СПб, 2009. — 576 с. — ISBN 978-5-9775-0319-8

[Slide1-1] ¹ ² ³ David Wagner . The Boomerang Attack . Архивировано 2015-09-23 .

[Slide3-2] ¹ ² ³ John Kelsey, Tadayoshi Kohno, Bruce Schneier. Amplified Boomerang Attacks Against Reduced-Round MARS and Serpent. Архивировано 6 июня 2012 года.

[Slide2-3] Eli Biham, Orr Dunkelman, Nathan Keller. A Related-Key Rectangle Attack on the Full KASUMI. Архивировано 25 декабря 2014 года.

[Slide4-4] ¹ ² Alex Biryukov. The Boomerang Attack on 5 and 6-round Reduced AES. Архивировано 5 февраля 2012 года.

[Slide6-5] Alex Biryukov, Dmitry Khovratovich. Related-key Cryptanalysis of the Full AES-192 and AES-256. Архивировано 24 августа 2015 года.

[Slide5-6] Antoine Joux, Thomas Peyrin. Hash Functions and the (Amplified) Boomerang Attack. Архивировано 27 декабря 2014 года.

[1]

[2]

[3]

[4]

[5]

[6]