Attacco a boomerang

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 - 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

• Crittanalisi
• Crittanalisi differenziale

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).