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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Применение к полнораундовому AES

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

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

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

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

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

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

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

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

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

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

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

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

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

Примечания

Литература

• — СПб. : , 2009. — 576 с. — ISBN 978-5-9775-0319-8