From Wikipedia, the free encyclopedia

In cryptography, the boomerang attack is a method for the cryptanalysis of block ciphers based on differential cryptanalysis. The attack was published in 1999 by David Wagner.

The boomerang attack has allowed new avenues of attack for many ciphers previously deemed safe from differential cryptanalysis.

Refinements on the boomerang attack have been published: the amplified boomerang attack, then the rectangle attack.

Contents 1 The attack 2 Application to specific ciphers 3 References 4 External links

The boomerang attack is based on differential cryptanalysis. In differential cryptanalysis, an attacker exploits how differences in the input to a cipher (the plaintext) can affect the resultant difference at the output (the ciphertext). A high-probability "differential" (that is, an input difference that will produce a likely output difference) is needed that covers all, or nearly all, of the cipher. The boomerang attack allows differentials to be used which cover only part of the cipher.

The attack attempts to generate a so-called "quartet" structure at a point halfway through the cipher. For this purpose, say that the encryption action of the cipher, E can be split into two consecutive stages, E₀ and E₁, so that E(M) = E₁(E₀(M)), where M is some plaintext message. Suppose we have two differentials for the two stages; say,

for E₀, and

for E₁^-1 (the decryption action of E₁).

The basic attack proceeds as follows:

• Choose a random plaintext P and calculate .
• Request the encryptions of P and P' to obtain C = E(P) and C' = E(P')
• Calculate and
• Request the decryptions of D and D' to obtain Q = E ^{− 1}(D) and Q' = E ^{− 1}(D')
• Compare Q and Q'; when the differentials hold, .

The best attack on KASUMI, a block cipher used in 3GPP, is a related-key rectangle attack which breaks the full eight rounds of the cipher faster than exhaustive search (Biham et al., 2005). The attack requires 2^54.6 chosen plaintexts, each of which has been encrypted under one of four related keys, and has a time complexity equivalent to 2^76.1 KASUMI encryptions.

• Eli Biham, Orr Dunkelman, and Nathan Keller, A Related-Key Rectangle Attack on the Full KASUMI, ASIACRYPT 2005, 443–461
• Eli Biham, Orr Dunkelman and Nathan Keller, Related-Key Boomerang and Rectangle Attacks, EUROCRYPT 2005, 507–525
• Eli Biham, Orr Dunkelman and Nathan Keller, Rectangle Attacks on 49-Round SHACAL-1, Fast Software Encryption - FSE 2003, 22–35
• Eli Biham, Orr Dunkelman and Nathan Keller, New Results on Boomerang and Rectangle Attacks, FSE 2002, 1–16
• Eli Biham, Orr Dunkelman and Nathan Keller, The Rectangle Attack - Rectangling the Serpent, EUROCRYPT 2001, 340–357
• Alex Biryukov, The Boomerang Attack on 5 and 6-Round Reduced AES, AES Conference 2004, 11–15
• Seokhie Hong, Jongsung Kim, Sangjin Lee and Bart Preneel, Related-Key Rectangle Attacks on Reduced Versions of SHACAL-1 and AES-192, FSE 2005, 368–383
• John Kelsey, Tadayoshi Kohno and Bruce Schneier, Amplified Boomerang Attacks Against Reduced-Round MARS and Serpent, FSE 2000, 75–93
• Jongsung Kim, Guil Kim, Seokhie Hong, Sangjin Lee, and Dowon Hong, The Related-Key Rectangle Attack - Application to SHACAL-1, ACISP 2004, 123–136
• Jongsung Kim, Dukjae Moon, Wonil Lee, Seokhie Hong, Sangjin Lee and Seokwon Jung, Amplified Boomerang Attack against Reduced-Round SHACAL, ASIACRYPT 2002, 243–253
• David Wagner, "The Boomerang Attack", Fast Software Encryption 1999, pp. 156–170 (Postscript), (Slides)

• Boomerang attack — explained by John Savard

Block ciphers v • d • e
Algorithms: 3-Way | AES | Akelarre | Anubis | ARIA | BaseKing | Blowfish | C2 | Camellia | CAST-128 | CAST-256 | CIKS-1 | CIPHERUNICORN-A | CIPHERUNICORN-E | CMEA | Cobra | COCONUT98 | Crab | CRYPTON | CS-Cipher | DEAL | DES | DES-X | DFC | E2 | FEAL | FROG | G-DES | GOST | Grand Cru | Hasty Pudding Cipher | Hierocrypt | ICE | IDEA | IDEA NXT | Iraqi | Intel Cascade Cipher | KASUMI | KHAZAD | Khufu and Khafre | KN-Cipher | Libelle | LOKI89/91 | LOKI97 | Lucifer | M6 | MacGuffin | Madryga | MAGENTA | MARS | Mercy | MESH | MISTY1 | MMB | MULTI2 | NewDES | NOEKEON | NUSH | Q | RC2 | RC5 | RC6 | REDOC | Red Pike | S-1 | SAFER | SC2000 | SEED | Serpent | SHACAL | SHARK | Skipjack | SMS4 | Square | TEA | Triple DES | Twofish | UES | Xenon | xmx | XTEA | Zodiac
Design: Feistel network | Key schedule | Product cipher | S-box | SPN Attacks: Brute force | Linear / Differential / Integral cryptanalysis | Mod n | Related-key | Slide | XSL
Standardization: AES process | CRYPTREC | NESSIE Misc: Avalanche effect | Block size | IV | Key size | Modes of operation | Piling-up lemma | Weak key
Cryptography v • d • e
History of cryptography | Cryptanalysis | Cryptography portal | Topics in cryptography
Symmetric-key algorithm | Block cipher | Stream cipher | Public-key cryptography | Cryptographic hash function | Message authentication code | Random numbers