Abstract
This paper describes a new differential-style attack, which we call the boomerang attack. This attack has several interesting applications. First, we disprove the oft-repeated claim that eliminating all high-probability differentials for the whole cipher is suffcient to guarantee security against differential attacks. Second, we show how to break COCONUT98, a cipher designed using decorrelation techniques to ensure provable security against differential attacks, with an advanced differential-style attack that needs just 216 adaptively chosen texts. Also, to illustrate the power of boomerang techniques, we give new attacks on Khufu-16, FEAL-6, and 16 rounds of CAST-256.
Chapter PDF
Similar content being viewed by others
Keywords
These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.
References
C. Adams, “The CAST-256 Encryption Algorithm,” NIST AES Proposal, Jun 98.
C. Adams, personal communication, Feb 1999.
E. Biham, A. Biryukov, A. Shamir. “Cryptanalysis of Skipjack Reduced to 31 Rounds using Impossible Differentials,” EUROCRYPT’99, to appear.
E. Biham, A. Biryukov, A. Shamir. “Miss in the Middle Attacks on IDEA, Khufu, and Khafre,” this volume.
E. Biham, A. Biryukov, O. Dunkelmann, E. Richardson, A. Shamir, “Initial Observations on the Skipjack Encryption Algorithm,” SAC’98, Springer-Verlag, 1998.
E. Biham, personal communication, Mar 1999.
E. Biham, A. Shamir, Differential Cryptanalysis of the Data Encryption Standard, Springer-Verlag, 1993.
C. Burwick, D. Coppersmith, E. D’Avignon, R. Gennaro, S. Halevi, C. Jutla, S.M. Matyas, L. O’Connor, M. Peyravian, D. Safford, and N. Zunic, “MARS-A Candidate Cipher for AES,” NIST AES Proposal, Jun 98.
H. Gilbert, M. Girault, P. Hoogvorst, F. Noilhan, T. Pornin, G. Poupard, J. Stern, S. Vaudenay, “Decorrelated Fast Cipher: an AES Candidate,” NIST AES Proposal, Jun 98.
H. Gilbert and P. Chauvaud, “A chosen plaintext attack of the 16-round Khufu cryptosystem,” CRYPTO’94, LNCS 839, Springer-Verlag, 1994.
D. Georgoudis, D. Lerous, and B.S. Chaves, “The ‘Frog’ Encryption Algorithm,” NIST AES Proposal, Jun 98.
M. Hellman and S. Langford., “Differential-linear cryptanalysis,” CRYPTO’94, LNCS 839, Springer-Verlag, 1994.
J. Kelsey, B. Schneier, D. Wagner, “Related-Key Cryptanalysis of 3-WAY, Biham-DES, CAST, DES-X, NewDES, RC2, and TEA,” ICICS’97, Springer-Verlag, 1997.
L.R. Knudsen, “Truncated and Higher Order Differentials,” Fast Software Encryption, 2nd International Workshop Proceedings, Springer-Verlag, 1995.
L. Knudsen, “DEAL-A 128-bit Block Cipher,” NIST AES Proposal, Jun 98.
X. Lai, “Higher Order Derivations and Differential Cryptanalysis,” Communications and Cryptography: Two Sides of One Tapestry, Kluwer Academic Publishers, 1994, pp. 227–233.
R. C. Merkle, “Fast Software Encryption Functions”, CRYPTO’90, Springer-Verlag, 1990.
R. Needham and D. Wheeler, “TEA Extensions,” unpublished manuscript, Mar 1997.
NSA, “Skipjack and KEA algorithm specifications,” May 1998. Available from http://csrc.ncsl.nist.gov/encryption/skipjack-1.pdf.
M._J. Saarinen, “Cryptanalysis of Block Tea,” unpublished manuscript, 20 Oct 1998.
B. Schneier, J. Kelsey, D. Whiting, D. Wagner, C. Hall, N. Ferguson, “Performance Comparison of the AES Submissions,” Second AES Conference, 1999.
S. Vaudenay, “A cheap paradigm for block cipher strengthening,” LIENS tech report 97-3, 1997.
S. Vaudenay, “Provable Security for Block Ciphers by Decorrelation,” STACS’98, Springer-Verlag LNCS 1373, 1998.
S. Vaudenay, “Feistel Ciphers with L2-Decorrelation,” SAC’98, Springer-Verlag, 1998.
G. Yuval, “Reinventing the Travois: Encryption/ MAC in 30 ROM Bytes,”FSE’97, LNCS 1267, 1997.
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 1999 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Wagner, D. (1999). The Boomerang Attack. In: Knudsen, L. (eds) Fast Software Encryption. FSE 1999. Lecture Notes in Computer Science, vol 1636. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-48519-8_12
Download citation
DOI: https://doi.org/10.1007/3-540-48519-8_12
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-66226-6
Online ISBN: 978-3-540-48519-3
eBook Packages: Springer Book Archive