Бумеранговая атака

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

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

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

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

Атака

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

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

\Delta \to \Delta ^{*}

для E ₀ и

\nabla \to \nabla ^{*}

для Е ₁⁻¹ (дешифровочное действие E ₁ ).

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

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

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

Одна из атак на KASUMI , блочный шифр, используемый в 3GPP , представляет собой атаку прямоугольником со связанными ключами , которая взламывает полные восемь раундов шифра быстрее, чем исчерпывающий поиск (Biham et al., 2005). Для атаки требуется 2 ^54.6 выбранные открытые тексты, каждый из которых зашифрован одним из четырех связанных ключей и имеет временную сложность, эквивалентную 2 ^76.1 Шифрование КАСУМИ.

Ссылки

^ Жу, Антуан; Пейрин, Томас (2007). «Хеш-функции и (усиленная) атака бумеранга». В Менезесе, Альфред (ред.). Достижения криптологии — КРИПТО 2007 . Конспекты лекций по информатике. Том. 4622. Берлин, Гейдельберг: Springer. стр. 244–263. дои : 10.1007/978-3-540-74143-5_14 . ISBN 978-3-540-74143-5 .

Дэвид Вагнер (март 1999 г.). «Атака бумеранга» ( PDF / PostScript ) . 6-й международный семинар по быстрому программному шифрованию (FSE '99) . Рим : Шпрингер-Верлаг . стр. 156–170 . Проверено 5 февраля 2007 г. (Слайды в PostScript)
Джон Келси ; Тадаёси Коно; Брюс Шнайер (апрель 2000 г.). «Усиленные атаки бумеранга против MARS и Serpent с уменьшенным диаметром» (PDF/PostScript) . ФСЕ 2000 . Нью-Йорк : Springer-Verlag. стр. 75–93 . Проверено 6 февраля 2007 г.
Эли Бихам ; Орр Данкельман ; Натан Келлер (май 2001 г.). «Атака прямоугольником – прямоугольная змея» . Достижения в криптологии, Труды EUROCRYPT 2001 . Инсбрук : Springer-Verlag. стр. 340–357. Архивировано из оригинала (PDF/PostScript) 29 марта 2007 г. Проверено 6 июля 2007 г.
Эли Бихам ; Орр Данкельман ; Натан Келлер (февраль 2002 г.). «Новые результаты по атакам бумеранга и прямоугольника» . ФСЕ '02 . Левен : Шпрингер-Верлаг. стр. 1–16. Архивировано из оригинала (PDF/PostScript) 14 июня 2008 г. Проверено 6 июля 2007 г.
Чонсон Ким; Дукдже Мун; Вонил Ли; Сохи Хонг; Санджин Ли; Соквон Юнг (декабрь 2002 г.). «Усиленная атака бумерангом против SHACAL с уменьшенным раундом». АЗИЯКРИПТ 2002 . Квинстаун, Новая Зеландия : Springer-Verlag. стр. 243–253.
Эли Бихам ; Орр Данкельман ; Натан Келлер (февраль 2003 г.). «Прямоугольные атаки на 49-раундовый SHACAL-1» (PDF) . ФСЕ '03 . Лунд : Спрингер-Верлаг . стр. 22–35. Архивировано из оригинала (PDF) 26 сентября 2007 г. Проверено 2 июля 2007 г.
Алексей Бирюков (май 2004 г.). «Атака бумеранга на сокращенный AES с 5 и 6 раундами» (PDF) . Расширенный стандарт шифрования — AES, 4-я Международная конференция AES 2004 . Бонн : Springer-Verlag. стр. 11–15 . Проверено 6 июля 2007 г.
Чонсон Ким; Гил Ким; Сохи Хонг; Санджин Ли; Давон Хонг (июль 2004 г.). «Атака прямоугольником со связанными ключами — приложение к SHACAL-1». 9-я Австралазийская конференция по информационной безопасности и конфиденциальности (ACISP 2004) . Сидней : Спрингер-Верлаг. стр. 123–136.
Сохи Хонг; Чонсон Ким; Санджин Ли; Барт Пренил (февраль 2005 г.). «Атаки прямоугольниками со связанными ключами на сокращенные версии SHACAL-1 и AES-192». ФСЕ '05 . Париж : Springer-Verlag. стр. 368–383.
Эли Бихам ; Орр Данкельман ; Натан Келлер (май 2005 г.). «Атаки бумерангом и прямоугольником по связанным ключам» (PostScript) . ЕВРОКРИПТ 2005 . Орхус : Springer-Verlag. стр. 507–525 . Проверено 16 февраля 2007 г. ^{[ постоянная мертвая ссылка ]}
Эли Бихам ; Орр Данкельман ; Натан Келлер (декабрь 2005 г.). «Атака прямоугольником связанных ключей на полный KASUMI» (PDF/PostScript) . АЗИЯКРИПТ 2005 . Ченнаи : Спрингер-Верлаг. стр. 443–461 . Проверено 6 июля 2007 г.

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

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

[1] Жу, Антуан; Пейрин, Томас (2007). «Хеш-функции и (усиленная) атака бумеранга». В Менезесе, Альфред (ред.). Достижения криптологии — КРИПТО 2007 . Конспекты лекций по информатике. Том. 4622. Берлин, Гейдельберг: Springer. стр. 244–263. дои : 10.1007/978-3-540-74143-5_14 . ISBN 978-3-540-74143-5 .

[ 1 ]