Attacco a boomerang

In crittografia l'attacco a boomerang è un metodo o tipo di attacco per la crittanalisi dei cifrari a blocchi basato sulla crittanalisi differenziale. L'attacco è stato pubblicato nel 1999 da David Wagner, che lo ha utilizzato per violare il cifrario COCONUT98.

L'attacco a boomerang ha permesso nuove modalità di attacco a molti cifrari precedentemente indicati come resistenti alla crittanalisi differenziale.

Sono anche state pubblicate versioni migliorate dell'attacco denominate attacco a boomerang amplificato ed attacco a rettangolo.

Modalità dell'attacco

L'attacco a boomerang è basato sulla crittanalisi differenziale. Nella crittanalisi differenziale un attaccante esplora in che modo le differenze nei dati forniti in ingresso ad un cifrario (il testo in chiaro) possono incidere sulle differenze risultanti nei dati in uscita (il testo cifrato): è necessaria però un "differenziale" (cioè una differenza nei dati in ingresso che produrrà verosimilmente una differenza in quelli in uscita) ad alta probabilità che coinvolga tutto, o quasi tutto, il cifrario. L'attacco a boomerang, invece, permette l'uso di differenziali che coinvolgono solo una parte del cifrario.

L'attacco tenta di creare una particolare struttura detta "a quartetto" in un punto a metà del cifrario. Per questo scopo, definiamo che l'azione di cifratura E del cifrario possa essere divisa in 2 fasi consecutive, E₀ ed E₁, tali che E(M) = E₁(E₀(M)), dove M è un messaggio in chiaro. Supponiamo di avere 2 differenziali per le 2 fasi; possiamo allora definire:

\Delta \to \Delta ^{*}

per E₀, e

\nabla \to \nabla ^{*}

per E₁^-1 (l'azione di decifratura di E₁).

L'attacco di base procede come segue:

si sceglie un testo in chiaro casuale $P$ e si calcola $P'=P\oplus \Delta$ ;
si richiedono le cifrature di $P$ e $P'$ per ottenere $C=E(P)$ e $C'=E(P')$ ;
si calcola $D=C\oplus \nabla$ e $D'=C'\oplus \nabla$ ;
si richiedono le decifrature di $D$ e $D'$ per ottenere $Q=E^{-1}(D)$ e $Q'=E^{-1}(D')$ ;
si compara $Q$ e $Q'$ : quando i differenziali non mutano più, allora si ha $Q\oplus Q'=\Delta$ .

Applicazioni a cifrari specifici

Il miglior attacco al KASUMI, un cifrario a blocchi utilizzato nel 3GPP, è un attacco a rettangolo correlato alla chiave che può violare tutti gli 8 passaggi del cifrario più velocemente di una ricerca esaustiva (Biham ed altri, 2005). L'attacco richiede 2^54,6 testi in chiaro scelti, ognuno dei quali cifrato con una di 4 chiavi correlate, ed ha una complessità temporale equivalente a 2^76,1 cifrature del KASUMI.

Bibliografia

David Wagner: The Boomerang Attack - Fast Software Encryption (FSE) 1999 ((Schede in PostScript))
John Kelsey, Tadayoshi Kohno, Bruce Schneier: Amplified Boomerang Attacks Against Reduced-Round MARS and Serpent - FSE 2000
Eli Biham, Orr Dunkelman, Nathan Keller: Advances in Cryptology - EUROCRYPT 2001
Biham, Dunkelman, Keller: New Results on Boomerang and Rectangle Attacks - FSE 2002
Jongsung Kim, Dukjae Moon, Wonil Lee, Seokhie Hong, Sangjin Lee, Seokwon Jung: Amplified Boomerang Attack against Reduced-Round SHACAL - ASIACRYPT 2002
Biham, Dunkelman, Keller: Rectangle Attacks on 49-Round SHACAL-1 - FSE 2003
Alex Biryukov: The Boomerang Attack on 5 and 6-Round Reduced AES - AES International Conference 2004
Jongsung Kim, Guil Kim, Seokhie Hong, Sangjin Lee, Dowon Hong: The Related-Key Rectangle Attack — Application to SHACAL-1] - ACISP 2004
Seokhie Hong, Jongsung Kim, Sangjin Lee, Bart Preneel: Related-Key Rectangle Attacks on Reduced Versions of SHACAL-1 and AES-192 - FSE 2005
Biham, Dunkelman, Keller: Related-Key Boomerang and Rectangle Attacks^{[collegamento interrotto]} - EUROCRYPT 2005
Biham, Dunkelman, Keller: A Related-Key Rectangle Attack on the Full KASUMI Archiviato il 6 aprile 2008 in Internet Archive. - ASIACRYPT 2005

Voci correlate

Collegamenti esterni

Boomerang attack — esposizione di John Savard
Homepage di Nathan Keller, su ma.huji.ac.il. URL consultato il 2 luglio 2009 (archiviato dall'url originale il 4 giugno 2008).

Portale Crittografia

Portale Sicurezza informatica