Boomerang attack

Last updated July 07, 2023

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

\Delta \to \Delta ^{*}

for E₀, and

\nabla \to \nabla ^{*}

for E₁⁻¹ (the decryption action of E₁).

The basic attack proceeds as follows:

Choose a random plaintext $P$ and calculate $P'=P\oplus \Delta$ .
Request the encryptions of $P$ and $P'$ to obtain $C=E(P)$ and $C'=E(P')$
Calculate $D=C\oplus \nabla$ and $D'=C'\oplus \nabla$
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, $Q\oplus Q'=\Delta$ .

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

Related Research Articles

The Data Encryption Standard is a symmetric-key algorithm for the encryption of digital data. Although its short key length of 56 bits makes it too insecure for modern applications, it has been highly influential in the advancement of cryptography.

Differential cryptanalysis is a general form of cryptanalysis applicable primarily to block ciphers, but also to stream ciphers and cryptographic hash functions. In the broadest sense, it is the study of how differences in information input can affect the resultant difference at the output. In the case of a block cipher, it refers to a set of techniques for tracing differences through the network of transformation, discovering where the cipher exhibits non-random behavior, and exploiting such properties to recover the secret key.

A5/1 is a stream cipher used to provide over-the-air communication privacy in the GSM cellular telephone standard. It is one of several implementations of the A5 security protocol. It was initially kept secret, but became public knowledge through leaks and reverse engineering. A number of serious weaknesses in the cipher have been identified.

Eli Biham is an Israeli cryptographer and cryptanalyst, currently a professor at the Technion - Israel Institute of Technology Computer Science department. Starting from October 2008 and till 2013, Biham was the dean of the Technion Computer Science department, after serving for two years as chief of CS graduate school. Biham received his Ph.D. for inventing (publicly) differential cryptanalysis, while working under Adi Shamir. It had, it turned out, been invented at least twice before. A team at IBM discovered it during their work on DES, and was requested/required to keep their discovery secret by the NSA, who evidently knew about it as well.

<span class="mw-page-title-main">Serpent (cipher)</span>

Serpent is a symmetric key block cipher that was a finalist in the Advanced Encryption Standard (AES) contest, where it was ranked second to Rijndael. Serpent was designed by Ross Anderson, Eli Biham, and Lars Knudsen.

In cryptography, XTEA is a block cipher designed to correct weaknesses in TEA. The cipher's designers were David Wheeler and Roger Needham of the Cambridge Computer Laboratory, and the algorithm was presented in an unpublished technical report in 1997. It is not subject to any patents.

<span class="mw-page-title-main">FEAL</span> Block cipher

In cryptography, FEAL is a block cipher proposed as an alternative to the Data Encryption Standard (DES), and designed to be much faster in software. The Feistel based algorithm was first published in 1987 by Akihiro Shimizu and Shoji Miyaguchi from NTT. The cipher is susceptible to various forms of cryptanalysis, and has acted as a catalyst in the discovery of differential and linear cryptanalysis.

In cryptography, DES-X is a variant on the DES symmetric-key block cipher intended to increase the complexity of a brute-force attack. The technique used to increase the complexity is called key whitening.

In cryptography, Khufu and Khafre are two block ciphers designed by Ralph Merkle in 1989 while working at Xerox's Palo Alto Research Center. Along with Snefru, a cryptographic hash function, the ciphers were named after the Egyptian Pharaohs Khufu, Khafre and Sneferu.

<span class="mw-page-title-main">SHACAL</span> Block cipher

SHACAL-1 is a 160-bit block cipher based on SHA-1, and supports keys from 128-bit to 512-bit. SHACAL-2 is a 256-bit block cipher based upon the larger hash function SHA-256.

In cryptography, REDOC II and REDOC III are block ciphers designed by Michael Wood (cryptographer) for Cryptech Inc and are optimised for use in software. Both REDOC ciphers are patented.

Introduced by Martin Hellman and Susan K. Langford in 1994, the differential-linear attack is a mix of both linear cryptanalysis and differential cryptanalysis.

In cryptography, impossible differential cryptanalysis is a form of differential cryptanalysis for block ciphers. While ordinary differential cryptanalysis tracks differences that propagate through the cipher with greater than expected probability, impossible differential cryptanalysis exploits differences that are impossible at some intermediate state of the cipher algorithm.

In cryptography, integral cryptanalysis is a cryptanalytic attack that is particularly applicable to block ciphers based on substitution–permutation networks. It was originally designed by Lars Knudsen as a dedicated attack against Square, so it is commonly known as the Square attack. It was also extended to a few other ciphers related to Square: CRYPTON, Rijndael, and SHARK. Stefan Lucks generalized the attack to what he called a saturation attack and used it to attack Twofish, which is not at all similar to Square, having a radically different Feistel network structure. Forms of integral cryptanalysis have since been applied to a variety of ciphers, including Hierocrypt, IDEA, Camellia, Skipjack, MISTY1, MISTY2, SAFER++, KHAZAD, and FOX.

In cryptography, Q is a block cipher invented by Leslie McBride. It was submitted to the NESSIE project, but was not selected.

In cryptography, Ladder-DES is a block cipher designed in 1994 by Terry Ritter. It is a 4-round Feistel cipher with a block size of 128 bits, using DES as the round function. It has no actual key schedule, so the total key size is 4×56=224 bits.

In cryptography, COCONUT98 is a block cipher designed by Serge Vaudenay in 1998. It was one of the first concrete applications of Vaudenay's decorrelation theory, designed to be provably secure against differential cryptanalysis, linear cryptanalysis, and even certain types of undiscovered cryptanalytic attacks.

In cryptography, the Davies attack is a dedicated statistical cryptanalysis method for attacking the Data Encryption Standard (DES). The attack was originally created in 1987 by Donald Davies. In 1994, Eli Biham and Alex Biryukov made significant improvements to the technique. It is a known-plaintext attack based on the non-uniform distribution of the outputs of pairs of adjacent S-boxes. It works by collecting many known plaintext/ciphertext pairs and calculating the empirical distribution of certain characteristics. Bits of the key can be deduced given sufficiently many known plaintexts, leaving the remaining bits to be found through brute force. There are tradeoffs between the number of required plaintexts, the number of key bits found, and the probability of success; the attack can find 24 bits of the key with 2⁵² known plaintexts and 53% success rate.

This article summarizes publicly known attacks against block ciphers and stream ciphers. Note that there are perhaps attacks that are not publicly known, and not all entries may be up to date.

<span class="mw-page-title-main">Orr Dunkelman</span> Israeli cryptographer and cryptanalyst

Orr Dunkelman is an Israeli cryptographer and cryptanalyst, currently a professor at the University of Haifa Computer Science department. Dunkelman is a co-director of the Center for Cyber Law & Privacy at the University of Haifa and a co-founder of Privacy Israel, an Israeli NGO for promoting privacy in Israel.

References

↑ Joux, Antoine; Peyrin, Thomas (2007). "Hash Functions and the (Amplified) Boomerang Attack". In Menezes, Alfred (ed.). Advances in Cryptology - CRYPTO 2007. Lecture Notes in Computer Science. Vol. 4622. Berlin, Heidelberg: Springer. pp. 244–263. doi: 10.1007/978-3-540-74143-5_14 . ISBN 978-3-540-74143-5.

David Wagner (March 1999). "The Boomerang Attack" (PDF/PostScript). 6th International Workshop on Fast Software Encryption (FSE '99). Rome: Springer-Verlag. pp. 156–170. Retrieved 2007-02-05. (Slides in PostScript)
John Kelsey; Tadayoshi Kohno; Bruce Schneier (April 2000). "Amplified Boomerang Attacks Against Reduced-Round MARS and Serpent" (PDF/PostScript). FSE 2000. New York City: Springer-Verlag. pp. 75–93. Retrieved 2007-02-06.
Eli Biham; Orr Dunkelman; Nathan Keller (May 2001). "The Rectangle Attack – Rectangling the Serpent" (PDF/PostScript). Advances in Cryptology, Proceedings of EUROCRYPT 2001. Innsbruck: Springer-Verlag. pp. 340–357. Retrieved 2007-07-06.^{[ dead link ]}
Eli Biham; Orr Dunkelman; Nathan Keller (February 2002). "New Results on Boomerang and Rectangle Attacks" (PDF/PostScript). FSE '02. Leuven: Springer-Verlag. pp. 1–16. Retrieved 2007-07-06.^{[ dead link ]}
Jongsung Kim; Dukjae Moon; Wonil Lee; Seokhie Hong; Sangjin Lee; Seokwon Jung (December 2002). "Amplified Boomerang Attack against Reduced-Round SHACAL". ASIACRYPT 2002. Queenstown, New Zealand: Springer-Verlag. pp. 243–253.
Eli Biham; Orr Dunkelman; Nathan Keller (February 2003). "Rectangle Attacks on 49-Round SHACAL-1" (PDF). FSE '03. Lund: Springer-Verlag. pp. 22–35. Archived from the original (PDF) on 2007-09-26. Retrieved 2007-07-02.
Alex Biryukov (May 2004). "The Boomerang Attack on 5 and 6-Round Reduced AES" (PDF). Advanced Encryption Standard — AES, 4th International Conference, AES 2004. Bonn: Springer-Verlag. pp. 11–15. Retrieved 2007-07-06.
Jongsung Kim; Guil Kim; Seokhie Hong; Sangjin Lee; Dowon Hong (July 2004). "The Related-Key Rectangle Attack — Application to SHACAL-1". 9th Australasian Conference on Information Security and Privacy (ACISP 2004). Sydney: Springer-Verlag. pp. 123–136.
Seokhie Hong; Jongsung Kim; Sangjin Lee; Bart Preneel (February 2005). "Related-Key Rectangle Attacks on Reduced Versions of SHACAL-1 and AES-192". FSE '05. Paris: Springer-Verlag. pp. 368–383.
Eli Biham; Orr Dunkelman; Nathan Keller (May 2005). "Related-Key Boomerang and Rectangle Attacks" (PostScript). EUROCRYPT 2005. Aarhus: Springer-Verlag. pp. 507–525. Retrieved 2007-02-16.^{[ permanent dead link ]}
Eli Biham; Orr Dunkelman; Nathan Keller (December 2005). "A Related-Key Rectangle Attack on the Full KASUMI" (PDF/PostScript). ASIACRYPT 2005. Chennai: Springer-Verlag. pp. 443–461. Retrieved 2007-07-06.

External links

Boomerang attack — explained by John Savard

This page is based on this Wikipedia article
Text is available under the CC BY-SA 4.0 license; additional terms may apply.
Images, videos and audio are available under their respective licenses.

[1] Joux, Antoine; Peyrin, Thomas (2007). "Hash Functions and the (Amplified) Boomerang Attack". In Menezes, Alfred (ed.). Advances in Cryptology - CRYPTO 2007. Lecture Notes in Computer Science. Vol. 4622. Berlin, Heidelberg: Springer. pp. 244–263. doi: 10.1007/978-3-540-74143-5_14 . ISBN 978-3-540-74143-5.

[1]