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"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,:Delta oDelta^*for "E"0, and: abla o abla^* for "E"1-1 (the decryption action of "E"1).

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 abla and D' = C' oplus abla
* 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

The best 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

* cite conference
author = David Wagner
title = The Boomerang Attack
booktitle = 6th International Workshop on Fast Software Encryption (FSE '99)
pages = pp.156–170
publisher = Springer-Verlag
date = 1999-03
location = Rome
url = http://citeseer.ist.psu.edu/wagner99boomerang.html
format = PDF/PostScript
accessdate = 2007-02-05
[http://www.cs.berkeley.edu/~daw/papers/boomerang-fse99-slides.ps (Slides in PostScript)]
* cite conference
author = John Kelsey, Tadayoshi Kohno, and Bruce Schneier
title = Amplified Boomerang Attacks Against Reduced-Round MARS and Serpent
booktitle = FSE 2000
pages = pp.75–93
publisher = Springer-Verlag
date = 2000-04
location = New York City
url = http://www.schneier.com/paper-boomerang.html
format = PDF/PostScript
accessdate = 2007-02-06

* cite conference
author = Eli Biham, Orr Dunkelman, and Nathan Keller
title = The Rectangle Attack – Rectangling the Serpent
booktitle = Advances in Cryptology, Proceedings of EUROCRYPT 2001
pages = pp.340–357
publisher = Springer-Verlag
date = 2001-05
location = Innsbruck
url = http://citeseer.ist.psu.edu/biham01rectangle.html
format = PDF/PostScript
accessdate = 2007-07-06

* cite conference
author = Biham, Dunkelman, Keller
title = New Results on Boomerang and Rectangle Attacks
booktitle = FSE '02
pages = pp.1–16
publisher = Springer-Verlag
date = 2002-02
location = Leuven
url = http://citeseer.ist.psu.edu/504429.html
format = PDF/PostScript
accessdate = 2007-07-06

* cite conference
author = Jongsung Kim, Dukjae Moon, Wonil Lee, Seokhie Hong, Sangjin Lee, Seokwon Jung
title = Amplified Boomerang Attack against Reduced-Round SHACAL
booktitle = ASIACRYPT 2002
pages = pp.243–253
publisher = Springer-Verlag
date = 2002-12
location = Queenstown, New Zealand

* cite conference
author = Biham, Dunkelman, Keller
title = Rectangle Attacks on 49-Round SHACAL-1
booktitle = FSE '03
pages = pp.22–35
publisher = Springer-Verlag
date = 2003-02
location = Lund
url = http://vipe.technion.ac.il/~orrd/crypt/shacal.pdf
format = PDF
accessdate = 2007-07-02

* cite conference
author = Alex Biryukov
title = The Boomerang Attack on 5 and 6-Round Reduced AES
booktitle = Advanced Encryption Standard — AES, 4th International Conference, AES 2004
pages = pp.11–15
publisher = Springer-Verlag
date = 2004-05
location = Bonn
url = http://www.cosic.esat.kuleuven.be/publications/article-206.pdf
format = PDF
accessdate = 2007-07-06

* cite conference
author = Jongsung Kim, Guil Kim, Seokhie Hong, Sangjin Lee, Dowon Hong
title = The Related-Key Rectangle Attack — Application to SHACAL-1
booktitle = 9th Australasian Conference on Information Security and Privacy (ACISP 2004)
pages= pp.123–136
publisher = Springer-Verlag
date = 2004-07
location = Sydney

* cite conference
author = Seokhie Hong, Jongsung Kim, Sangjin Lee and Bart Preneel
title = Related-Key Rectangle Attacks on Reduced Versions of SHACAL-1 and AES-192
booktitle = FSE '05
pages = pp.368–383
publisher = Springer-Verlag
date = 2005-02
location =Paris

* cite conference
author = Biham, Dunkelman, Keller
title = Related-Key Boomerang and Rectangle Attacks
booktitle = EUROCRYPT 2005
pages = pp.507–525
publisher = Springer-Verlag
date = 2005-05
location = Aarhus
url = http://vipe.technion.ac.il/~orrd/crypt/relatedkey-rectangle.ps
format = PostScript
accessdate = 2007-02-16

* cite conference
author = Biham, Dunkelman, Keller
title = A Related-Key Rectangle Attack on the Full KASUMI
booktitle = ASIACRYPT 2005
pages = pp.443–461
publisher = Springer-Verlag
date = 2005-12
location = Chennai
url = http://www.cs.technion.ac.il/users/wwwb/cgi-bin/tr-info.cgi/2005/CS/CS-2005-14
format = PDF/PostScript
accessdate = 2007-07-06

External links

* [http://www.quadibloc.com/crypto/co4512.htm Boomerang attack] — explained by John Savard
* [http://www.ma.huji.ac.il/~nkeller Nathan Keller's homepage]


Wikimedia Foundation. 2010.

Игры ⚽ Нужно сделать НИР?

Look at other dictionaries:

  • Boomerang (comics) — Superherobox| caption=Boomerang on the cover of Spectacular Spider Man #144 (November 1988). Art by Sal Buscema. comic color=background:#ff8080 character name=Boomerang real name=Fred Myers publisher=Marvel Comics debut= Tales to Astonish #81… …   Wikipedia

  • Attaque Boomerang — L attaque boomerang est une version améliorée de la cryptanalyse différentielle, cette méthode a été inventée par David Wagner en 1999. Elle consiste à attaquer les deux moitiés d un algorithme de chiffrement par bloc et part du principe que… …   Wikipédia en Français

  • Attaque boomerang — L attaque boomerang est une version améliorée de la cryptanalyse différentielle, cette méthode a été inventée par David Wagner en 1999. Elle consiste à attaquer les deux moitiés d un algorithme de chiffrement par bloc et part du principe que… …   Wikipédia en Français

  • Captain Boomerang — Superherobox| caption=Captain Boomerang as he appears in Identity Crisis . Art by Rags Morales character name=Captain Boomerang real name=George Digger Harkness publisher=DC Comics debut= Flash #117 (December 1960) creators=John Broome Carmine… …   Wikipedia

  • Bang-A-Boomerang — «Bang A Boomerang» Сингл ABBA из альбома ABBA Сторона «Б» SOS Выпущен 21 апреля …   Википедия

  • Heli Attack 3 — Infobox VG title = Heli Attack 3 developer = squarecircleco. publisher = squarecircleco. distributor = designer = Lavpreet engine = Adobe Flash version = released = June 17, 2005 genre = Run and gun shooter modes = Single player ratings =… …   Wikipedia

  • Correlation attack — In cryptography, correlation attacks are a class of known plaintext attacks for breaking stream ciphers whose keystream is generated by combining the output of several linear feedback shift registers (called LFSRs for the rest of this article)… …   Wikipedia

  • Meet-in-the-middle attack — Not to be confused with man in the middle attack. The meet in the middle attack is a cryptographic attack which, like the birthday attack, makes use of a space time tradeoff. While the birthday attack attempts to find two values in the domain of… …   Wikipedia

  • Under Attack — «Under Attack» Сингл ABBA из альбома The Singles: The First Ten Years Сторона «Б» You Owe Me One Выпущен 3 декабря 1982 (UK) 21 февраля 1983 (остальные страны) Формат …   Википедия

  • Decap Attack — Cover art Developer(s) Vic Tokai Publisher(s) …   Wikipedia

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”