Boomerang attack

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.

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,

${\displaystyle \mathrm{\Delta }\to {\mathrm{\Delta }}^{\ast }}$

for E₀, and

${\displaystyle \mathrm{\nabla }\to {\mathrm{\nabla }}^{\ast }}$ for E₁⁻¹ (the decryption action of E₁).

The basic attack proceeds as follows:

• Choose a random plaintext ${\displaystyle P}$ and calculate ${\displaystyle P^{\prime }=P\oplus \mathrm{\Delta }}$.
• Request the encryptions of ${\displaystyle P}$ and ${\displaystyle P^{\prime }}$ to obtain ${\displaystyle C=E(P)}$ and ${\displaystyle C^{\prime }=E(P^{\prime })}$
• Calculate ${\displaystyle D=C\oplus \mathrm{\nabla }}$ and ${\displaystyle D^{\prime }=C^{\prime }\oplus \mathrm{\nabla }}$
• Request the decryptions of ${\displaystyle D}$ and ${\displaystyle D^{\prime }}$ to obtain ${\displaystyle Q=E^{-1}(D)}$ and ${\displaystyle Q^{\prime }=E^{-1}(D^{\prime })}$
• Compare ${\displaystyle Q}$ and ${\displaystyle Q^{\prime }}$; when the differentials hold, ${\displaystyle Q\oplus Q^{\prime }=\mathrm{\Delta }}$.