Boomerang attack explained
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, who used it to break the COCONUT98 cipher.
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, and the rectangle attack.
Due to the similarity of a Merkle–Damgård construction with a block cipher, this attack may also be applicable to certain hash functions such as MD5.[1]
The attack
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, E, of the cipher can be split into two consecutive stages, E0 and E1, so that E(M) = E1(E0(M)), where M is some plaintext message. Suppose we have two differentials for the two stages; say,
for
E0, and
for
E1−1 (the decryption action of
E1).
The basic attack proceeds as follows:
- Choose a random plaintext
and calculate
.
- Request the encryptions of
and
to obtain
and
and
- Request the decryptions of
and
to obtain
and
and
; when the differentials hold,
.
Application to specific ciphers
One 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 254.6 chosen plaintexts, each of which has been encrypted under one of four related keys and has a time complexity equivalent to 276.1 KASUMI encryptions.
References
- . The Boomerang Attack . 6th International Workshop on Fast Software Encryption (FSE '99) . 156 - 170 . . March 1999 . . . 2007-02-05 . (Slides in PostScript)
- . Tadayoshi Kohno . . Amplified Boomerang Attacks Against Reduced-Round MARS and Serpent . FSE 2000 . 75 - 93 . Springer-Verlag . April 2000 . . PDF/PostScript . 2007-02-06 .
- . . Nathan Keller . The Rectangle Attack - Rectangling the Serpent . Advances in Cryptology, Proceedings of EUROCRYPT 2001 . 340 - 357 . Springer-Verlag . May 2001 . . PDF/PostScript . 2007-07-06 . 2007-03-29 . https://web.archive.org/web/20070329110058/http://citeseer.ist.psu.edu/biham01rectangle.html . dead .
- . . Nathan Keller . New Results on Boomerang and Rectangle Attacks . FSE '02 . 1 - 16 . Springer-Verlag . February 2002 . . PDF/PostScript . 2007-07-06 . 2008-06-14 . https://web.archive.org/web/20080614184616/http://citeseer.ist.psu.edu/504429.html . dead .
- Jongsung Kim . Dukjae Moon . Wonil Lee . Seokhie Hong . Sangjin Lee . Seokwon Jung . Amplified Boomerang Attack against Reduced-Round SHACAL . ASIACRYPT 2002 . 243 - 253 . Springer-Verlag . December 2002 . .
- . . Nathan Keller . Rectangle Attacks on 49-Round SHACAL-1 . FSE '03 . 22 - 35 . . February 2003 . . 2007-07-02 . https://web.archive.org/web/20070926201253/http://vipe.technion.ac.il/~orrd/crypt/shacal.pdf . 2007-09-26 .
- . The Boomerang Attack on 5 and 6-Round Reduced AES . Advanced Encryption Standard - AES, 4th International Conference, AES 2004 . 11 - 15 . Springer-Verlag . May 2004 . . 2007-07-06 .
- Jongsung Kim . Guil Kim . Seokhie Hong . Sangjin Lee . Dowon Hong . The Related-Key Rectangle Attack - Application to SHACAL-1 . 9th Australasian Conference on Information Security and Privacy (ACISP 2004) . 123 - 136 . Springer-Verlag . July 2004 . .
- Seokhie Hong . Jongsung Kim . Sangjin Lee . . Related-Key Rectangle Attacks on Reduced Versions of SHACAL-1 and AES-192 . FSE '05 . 368 - 383 . Springer-Verlag . February 2005 . .
- . . Nathan Keller . Related-Key Boomerang and Rectangle Attacks . EUROCRYPT 2005 . 507 - 525 . Springer-Verlag . May 2005 . . PostScript . 2007-02-16 .
- . . Nathan Keller . A Related-Key Rectangle Attack on the Full KASUMI . ASIACRYPT 2005 . 443 - 461 . Springer-Verlag . December 2005 . . PDF/PostScript . 2007-07-06 .
External links
Notes and References
- Book: Joux. Antoine. Peyrin. Thomas. Advances in Cryptology - CRYPTO 2007 . Hash Functions and the (Amplified) Boomerang Attack . 2007. Menezes. Alfred. Lecture Notes in Computer Science. 4622. en. Berlin, Heidelberg. Springer. 244–263. 10.1007/978-3-540-74143-5_14. 978-3-540-74143-5. free.