Атака бумерангом

Форма криптоанализа

Атака бумерангом

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

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

Были опубликованы усовершенствования атаки бумерангом: усиленная атака бумерангом и атака прямоугольником .

Из-за сходства конструкции Меркла-Дамгарда с блочным шифром эта атака может быть применима и к некоторым хэш-функциям, таким как MD5 . ^[1]

Атака

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

Атака пытается сгенерировать так называемую структуру "квартета" в точке на полпути через шифр. Для этой цели предположим, что действие шифрования E шифра можно разделить на два последовательных этапа E ₀ и E ₁ , так что E(M) = E ₁ ( E ₀ (M)), где M — некоторое текстовое сообщение. Предположим, что у нас есть два дифференциала для двух этапов; скажем,

${\displaystyle \Delta \to \Delta ^{*}}$

для E ₀ , и

${\displaystyle \nabla \to \nabla ^{*}}$для E ₁ ⁻¹ (действие по расшифровке E ₁ ).

Основная атака происходит следующим образом:

• Выберите случайный открытый текст и вычислите . ${\displaystyle P}$ ${\displaystyle P'=P\oplus \Delta }$
• Запросить шифры и получить и ${\displaystyle P}$ ${\displaystyle P'}$ ${\displaystyle C=E(P)}$ ${\displaystyle C'=E(P')}$
• Рассчитать и ${\displaystyle D=C\oplus \nabla }$ ${\displaystyle D'=C'\oplus \nabla }$
• Запросить расшифровки и получить и ${\displaystyle D}$ ${\displaystyle D'}$ ${\displaystyle Q=E^{-1}(D)}$ ${\displaystyle Q'=E^{-1}(D')}$
• Сравните и ; когда дифференциалы верны, . ${\displaystyle Q}$ ${\displaystyle Q'}$ ${\displaystyle Q\oplus Q'=\Delta }$

Применение к конкретным шифрам

Одна из атак на KASUMI , блочный шифр, используемый в 3GPP , представляет собой атаку прямоугольника связанных ключей , которая взламывает все восемь раундов шифра быстрее, чем исчерпывающий поиск (Biham et al., 2005). Для атаки требуется 2 ^54,6 выбранных открытых текстов, каждый из которых был зашифрован одним из четырех связанных ключей и имеет временную сложность, эквивалентную 2 ^76,1 шифрований KASUMI.

Ссылки

1. Жу, Антуан; Пейрен, Томас (2007). «Хэш-функции и (усиленная) атака бумерангом». В Menezes, Alfred (ред.). Advances in Cryptology - CRYPTO 2007. Lecture Notes in Computer Science. Vol. 4622. Berlin, Heidelberg: Springer. pp. 244–263. doi : 10.1007/978-3-540-74143-5_14 . ISBN 978-3-540-74143-5.

• Дэвид Вагнер (март 1999 г.). «Атака бумерангом» ( PDF / PostScript ) . 6-й международный семинар по быстрому программному шифрованию (FSE '99) . Рим : Springer-Verlag . стр. 156–170 . Получено 05.02.2007 .(Слайды в PostScript)
• Джон Келси ; Тадаёси Коно; Брюс Шнайер (апрель 2000 г.). «Усиленные атаки бумерангом против MARS с уменьшенным раундом и Serpent» (PDF/PostScript) . FSE 2000. Нью -Йорк : Springer-Verlag. стр. 75–93 . Получено 06.02.2007 .
• Eli Biham ; Orr Dunkelman ; Nathan Keller (май 2001 г.). «Атака прямоугольником – Прямоугольная змея». Advances in Cryptology, Proceedings of EUROCRYPT 2001 . Innsbruck : Springer-Verlag. стр. 340–357. Архивировано из оригинала (PDF/PostScript) 29-03-2007 . Получено 06-07-2007 .
• Eli Biham ; Orr Dunkelman ; Nathan Keller (февраль 2002 г.). «Новые результаты атак бумерангом и прямоугольником». FSE '02 . Leuven : Springer-Verlag. стр. 1–16. Архивировано из оригинала (PDF/PostScript) 2008-06-14 . Получено 2007-07-06 .
• Jongsung Kim; Dukjae Moon; Wonil Lee; Seokhie Hong; Sangjin Lee; Seokwon Jung (декабрь 2002 г.). «Усиленная атака бумерангом против SHACAL с уменьшенным количеством раундов». ASIACRYPT 2002. Квинстаун , Новая Зеландия : Springer-Verlag. стр. 243–253.
• Eli Biham ; Orr Dunkelman ; Nathan Keller (февраль 2003 г.). "Rectangle Attacks on 49-Round SHACAL-1" (PDF) . FSE '03 . Lund : Springer-Verlag . стр. 22–35. Архивировано из оригинала (PDF) 2007-09-26 . Получено 2007-07-02 .
• Алекс Бирюков (май 2004 г.). «Атака бумерангом на 5- и 6-раундовый редуцированный AES» (PDF) . Расширенный стандарт шифрования — AES, 4-я международная конференция, AES 2004 . Бонн : Springer-Verlag. стр. 11–15 . Получено 06.07.2007 .
• Jongsung Kim; Guil Kim; Seokhie Hong; Sangjin Lee; Dowon Hong (июль 2004 г.). «Атака на прямоугольник с родственным ключом — применение к SHACAL-1». 9-я Австралазийская конференция по информационной безопасности и конфиденциальности (ACISP 2004) . Сидней : Springer-Verlag. стр. 123–136.
• Seokhie Hong; Jongsung Kim; Sangjin Lee; Bart Preneel (февраль 2005 г.). «Атаки с использованием связанных ключей и прямоугольников на сокращенные версии SHACAL-1 и AES-192». FSE '05 . Париж : Springer-Verlag. С. 368–383.
• Эли Бихам ; Орр Данкельман ; Натан Келлер (май 2005 г.). «Атаки с использованием связанных ключей «бумеранг» и «прямоугольника»» (PostScript) . EUROCRYPT 2005 . Aarhus : Springer-Verlag. стр. 507–525 . Получено 16.02.2007 .^{[ постоянная мертвая ссылка ]}
• Эли Бихам ; Орр Данкельман ; Натан Келлер (декабрь 2005 г.). «Атака прямоугольника с родственным ключом на полный KASUMI» (PDF/PostScript) . ASIACRYPT 2005 . Ченнаи : Springer-Verlag. стр. 443–461 . Получено 06.07.2007 .

Внешние ссылки

• Атака бумерангом — объяснение Джона Саварда