Boomerang attack

Boomerang attack

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, then the rectangle attack.

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.

References

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, and 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, and 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.
Biham, Dunkelman, Keller (February 2002). "New Results on Boomerang and Rectangle Attacks" (PDF/PostScript). FSE '02. Leuven: Springer-Verlag. pp. 1–16. Retrieved 2007-07-06.
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.
Biham, Dunkelman, Keller (February 2003). "Rectangle Attacks on 49-Round SHACAL-1" (PDF). FSE '03. Lund: Springer-Verlag. pp. 22–35. 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 and 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.
Biham, Dunkelman, Keller (May 2005). "Related-Key Boomerang and Rectangle Attacks" (PostScript). EUROCRYPT 2005. Aarhus: Springer-Verlag. pp. 507–525. Retrieved 2007-02-16.
Biham, Dunkelman, 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
Nathan Keller's homepage

Block ciphers (security summary)

Common algorithms	AES Blowfish DES (Internal Mechanics, Triple DES) Serpent Twofish

Less common algorithms	Camellia CAST-128 IDEA RC2 RC5 RC6 SEED ARIA Skipjack TEA XTEA

Other algorithms	3-Way Akelarre Anubis BaseKing BassOmatic BATON BEAR and LION CAST-256 Chiasmus CIKS-1 CIPHERUNICORN-A CIPHERUNICORN-E CLEFIA CMEA Cobra COCONUT98 Crab Cryptomeria/C2 CRYPTON CS-Cipher DEAL DES-X DFC E2 FEAL FEA-M FROG G-DES GOST Grand Cru Hasty Pudding cipher Hierocrypt ICE IDEA NXT Intel Cascade Cipher Iraqi KASUMI KeeLoq KHAZAD Khufu and Khafre KN-Cipher Kuznyechik Ladder-DES Libelle LOKI (97, 89/91) Lucifer M6 M8 MacGuffin Madryga MAGENTA MARS Mercy MESH MISTY1 MMB MULTI2 MultiSwap New Data Seal NewDES Nimbus NOEKEON NUSH PRESENT Prince Q RC6 REDOC Red Pike S-1 SAFER SAVILLE SC2000 SHACAL SHARK Simon SM4 Speck Spectr-H64 Square SXAL/MBAL Threefish Treyfer UES Xenon xmx XXTEA Zodiac

Design	Feistel network Key schedule Lai-Massey scheme Product cipher S-box P-box SPN Avalanche effect Block size Key size Key whitening (Whitening transformation)

Attack (cryptanalysis)	Brute-force (EFF DES cracker) MITM (Biclique attack, 3-subset MITM attack) Linear (Piling-up lemma) Differential (Impossible Truncated Higher-order) Differential-linear Distinguishing (Known-key) Integral/Square Boomerang Mod n Related-key Slide Rotational Timing XSL Interpolation Partitioning Davies' Rebound Weak key Tau Chi-square Time/memory/data tradeoff

Standardization	AES process CRYPTREC NESSIE

Utilization	Initialization vector Mode of operation Padding

Cryptography

History of cryptography Cryptanalysis Outline of cryptography

Symmetric-key algorithm Block cipher Stream cipher Public-key cryptography Cryptographic hash function Message authentication code Random numbers Steganography

Category Portal WikiProject

This article is issued from Wikipedia - version of the 7/11/2016. The text is available under the Creative Commons Attribution/Share Alike but additional terms may apply for the media files.