In
cryptography
Cryptography, or cryptology (from grc, , translit=kryptós "hidden, secret"; and ''graphein'', "to write", or ''-logia'', "study", respectively), is the practice and study of techniques for secure communication in the presence of adver ...
, 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
In cryptography, the Merkle–Damgård construction or Merkle–Damgård hash function is a method of building collision-resistant cryptographic hash functions from collision-resistant one-way compression functions. Goldwasser, S. and Bellare, M ...
with a block cipher, this attack may also be applicable to certain hash functions such as
MD5.
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, ''E''
0 and ''E''
1, so that ''E(M)'' = ''E''
1(''E''
0(M)), where ''M'' is some plaintext message. Suppose we have two differentials for the two stages; say,
:
for ''E''
0, and
:
for ''E''
1−1 (the decryption action of ''E''
1).
The basic attack proceeds as follows:
* Choose a random plaintext
and calculate
.
* Request the encryptions of
and
to obtain
and
* Calculate
and
* Request the decryptions of
and
to obtain
and
* Compare
and
; when the differentials hold,
.
Application to specific ciphers
One attack on
KASUMI
Kasumi may refer to:
Places
* Kasumi, Hyōgo (香住), a former town in Hyōgo Prefecture, Japan
* Kasumigaseki (霞が関 "Gate of Mist"), a district in downtown Tokyo
* Kasumi, Jajce, a village in Bosnia and Herzegovina
Other uses
* Kasumi (gi ...
, 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.
References
*
(Slides in PostScript)*
*
*
*
*
*
*
*
*
*
External links
— explained by John Savard
{{Cryptography navbox , block
Cryptographic attacks