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

редактировать

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

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

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

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

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

Содержание

1 Атака
2 Применение к конкретным шифрам
3 Ссылки
4 Внешние ссылки

Атака

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

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

Δ → Δ ∗ {\ displaystyle \ Delta \ to \ Delta ^ {*}}

\ Delta \ to \ Delta ^ {*}

для E 0 и

∇ → ∇ ∗ {\ displaystyle \ nabla \ to \ nabla ^ {*}}

\ nabla \ to \ nabla ^ {*}

для E 1 (действие по расшифровке E 1).

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

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

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

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

Ссылки

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

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