Abstract
Differential cryptanalysis analyzes ciphers by studying the development of differences during encryption. Linear cryptanalysis is similar but is based on studying approximate linear relations. In 1994, Langford and Hellman showed that both kinds of analysis can be combined together by a technique called differential-linear cryptanalysis, in which the differential part creates a linear approximation with probability 1. They applied their technique to 8-round DES. In this paper we present an enhancement of differential-linear cryptanalysis in which the inherited linear probability is smaller than 1. We use this extension to describe a differential-linear distinguisher for a 7-round reduced-version of DES, and to present the best known key-recovery attack on a 9-round reduced-version of DES. We use our enhanced technique to attack COCONUT98 with time complexity 233.7 encryptions and 227.7 chosen plaintexts.
The work described in this paper has been supported by the European Commission through the IST Programme under Contract IST-1999-12324.
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
Biham Eli, On Matsui’s Linear Cryptanalysis, Advances in Cryptology, proceedings of EUROCRYPT’ 94, Lecture Notes in Computer Science 950, pp. 341–355, 1994.
Eli Biham, Adi Shamir, Differential Cryptanalysis of the Data Encryption Standard, Springer-Verlag, 1993.
Eli Biham, Alex Biryukov, Adi Shamir, Miss in the Middle Attacks on IDEA and Khufu, proceedings of Fast Software Encryption 6, Lecture Notes in Computer Science 1636, pp. 124–138, 1999.
Eli Biham, Alex Biryukov, Adi Shamir, Cryptanalysis of Skipjack Reduced to 31 Rounds Using Impossible Differentials, Advances in Cryptology, proceedings of EUROCRYPT’ 99, Lecture Notes in Computer Science 1592, pp. 12–23, 1999.
Alex Biryukov, Eyal Kushilevitz, From Differential Cryptoanalysis to Ciphertext-Only Attacks, Advances in Cryptology, proceedings of CRYPTO’ 98, Lecture Notes in Computer Science 1462, pp. 72–88, 1998.
Johan Borst, Lars R. Knudsen, Vincent Rijmen, Two Attacks on Reduced Round IDEA, Advances in Cryptology, proceedings of EUROCRYPT’ 97, Lecture Notes in Computer Science 1233, pp. 1–13, 1997.
Philip Hawkes, Differential-Linear Weak Keys Classes of IDEA, Advances in Cryptology, proceedings if EUROCRYPT’ 98, Lecture Notes in Computer Science 1403, pp. 112–126, 1998.
Lars R. Knudsen, John Erik Mathiassen, A Chosen-Plaintext Linear Attack on DES, proceedings of Fast Software Encryption 7, Lecture Notes in Computer Science 1978, pp. 262–272, 2001.
Xuejia Lai, James L. Massey, Markov Ciphers and Differential Cryptanalysis, Advances in Cryptology, proceedings if EUROCRYPT’ 91, Lecture Notes in Computer Science 547, pp. 17–38, 1992.
Suzan K. Langford, Martin E. Hellman, Differential-Linear Cryptanalysis, Advances in Cryptology, proceedings of CRYPTO’ 94, Lecture Notes in Computer Science 839, pp. 17–25, 1994.
Mitsuru Matsui, Linear Cryptanalysis Method for DES Cipher, Advances in Cryptology, proceedings of EUROCRYPT’ 93, Lecture Notes in Computer Science 765, pp. 386–397, 1994.
US National Bureau of Standards, Data Encryption Standard, Federal Information Processing Standards Publications No. 46, 1977.
Jim Pitman, Probability, Springer-Verlag, 1993.
Serge Vaudenay, Provable Security for Block Ciphers by Decorrelation, proceedings of STACS’ 98, Lecture Notes in Computer Science 1373, pp. 249–275, 1998.
David Wagner, The Boomerang Attack, proceedings of Fast Software Encryption 6, Lecture Notes in Computer Science 1636, pp. 156–170, 1999.
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2002 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Biham, E., Dunkelman, O., Keller, N. (2002). Enhancing Differential-Linear Cryptanalysis. In: Zheng, Y. (eds) Advances in Cryptology — ASIACRYPT 2002. ASIACRYPT 2002. Lecture Notes in Computer Science, vol 2501. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-36178-2_16
Download citation
DOI: https://doi.org/10.1007/3-540-36178-2_16
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-00171-3
Online ISBN: 978-3-540-36178-7
eBook Packages: Springer Book Archive