Abstract
Differential cryptanalysis was introduced as an approach to analyze the security of DES-like cryptosystems. The first example of a DES-like cryptosystem was Lucifer, the direct predecessor of DES, which is still believed by many people to be much more secure than DES, since it has 128 key bits, and since no attacks against (the full variant of) Lucifer were ever reported in the cryptographic literature. In this paper we introduce a new extension of differential cryptanalysis, devised to extend the class of vulnerable cryptosystems. This new extension suggests key-dependent characteristics, called conditional characteristics, selected to enlarge the characteristics’ probabilities for keys in subsets of the key space. The application of conditional characteristics to Lucifer shows that more than half of the keys of Lucifer are insecure, and the attack requires about 236 complexity and chosen plaintexts to find these keys. The same extension can also be used to attack a new variant of DES, called RDES, which was designed to be immune against differential cryptanalysis. These new attacks flash new light on the design of DES, and show that the transition of Lucifer to DES strengthened the later cryptosystem.
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
Carlisle M. Adams, On Immunity against Biham and Shamir’s “Differential Cryptanalysis”, Information Processing Letters, Vol. 41, No. 2, pp. 77–80, 1992.
Eli Biham, Adi Shamir, Differential Cryptanalysis of the Data Encryption Standard, Springer-Verlag, 1993.
Eli Biham, Adi Shamir, Differential Cryptanalysis of DES-like Cryptosystems, Journal of Cryptology, Vol. 4, No. 1, pp. 3–72, 1991.
Eli Biham, Adi Shamir, Differential Cryptanalysis of FEAL and N-Hash, technical report CS91-17, Department of Applied Mathematics and Computer Science, The Weizmann Institute of Science, 1991. The extended abstract appears in Lecture Notes in Computer Science, Advances in Cryptology, proceedings of EUROCRYPT’91, pp. 1–16, 1991.
Eli Biham, Adi Shamir, Differential Cryptanalysis of Snefru, Khafre, REDOC-II, LOKI and Lucifer, technical report CS91-18, Department of Applied Mathematics and Computer Science, The Weizmann Institute of Science, 1991. The extended abstract appears in Lecture Notes in Computer Science, Advances in Cryptology, proceedings of CRYPTO’91, pp. 156–171, 1991.
Eli Biham, Adi Shamir, Differential Cryptanalysis of the full 16-round DES, Lecture Notes in Computer Science, Advances in Cryptology, proceedings of CRYPTO’92, to appear.
Lawrence Brown, Matthew Kwan, Josef Pieprzyk, Jennifer Seberry, Improving Resistance to Differential Cryptanalysis and the Redesign of LOKI, Lecture Notes in Computer Science, Advances in Cryptology, proceedings of ASIACRYPT’91, to appear.
Lawrence Brown, Josef Pieprzyk, Jennifer Seberry, LOKI-A Cryptographic Primitive for Authentication and Secrecy Applications, Lecture Notes in Computer Science, Advances in Cryptology, proceedings of AUSCRYPT’90, pp. 229–236, 1990.
M. H. Dawson, S. E. Tavares, An Expanded Set of S-box Design Criteria Based On Information Theory and its Relation to Differential-Like Attacks, Lecture Notes in Computer Science, Advances in Cryptology, proceedings of EUROCRYPT’91, pp. 352–367, 1991.
H. Feistel, Cryptography and Data Security, Scientific American, Vol. 228, No. 5, pp. 15–23, May 1973.
Kenji Koyama, Routo Terada, How to Strengthen DES-like Cryptosystems against Differential Cryptanalysis, IEICE Transactions on Fundumentals of Electronics, Communications and Computer Science, Vol. E76-A, No. 1, pp. 63–69, January 1993.
Xuejia Lai, James L. Massey, Sean Murphy, Markov Ciphers and Differential Cryptanalysis, Lecture Notes in Computer Science, Advances in Cryptology, proceedings of EUROCRYPT’91, pp. 17–38, 1991.
Ralph C. Merkle, A Fast Software One-Way Hash Function, Journal of Cryptology. Vol. 3, No. 1, pp. 43–58, 1990.
Ralph C. Merkle, Fast Software Encryption Functions, Lecture Notes in Computer Science, Advances in Cryptology, proceedings of CRYPTO’90, pp. 476–501, 1990.
S. Miyaguchi, K. Ohta, M. Iwata, 128-bit hash function (N-Hash), proceedings of SECURICOM’90, pp. 123–137, March 1990.
Shoji Miyaguchi, Akira Shiraishi, Akihiro Shimizu, Fast Data Encryption Algorithm FEAL-8, Review of electrical communications laboratories, Vol. 36, No. 4, pp. 433–437, 1988.
National Bureau of Standards, Data Encryption Standard, U.S. Department of Commerce, FIPS pub. 46, January 1977.
Kaisa Nyberg, Perfect nonlinear S-boxes, Lecture Notes in Computer Science, Advances in Cryptology, proceedings of EUROCRYPT’91, pp. 378–386, 1991.
Luke O’Connor, On the Distribution of Characteristics in Bijective Mappings, Lecture Notes in Computer Science, Advances in Cryptology, proceedings of EUROCRYPT’93, to appear.
Luke O’Connor, On the Distribution of Characteristics in Composite Permutations, Lecture Notes in Computer Science, Advances in Cryptology, proceedings of CRYPTO’93, to appear.
Akihiro Shimizu, Shoji Miyaguchi, Fast Data Encryption Algorithm FEAL, Lecture Notes in Computer Science, Advances in Cryptology, proceedings of EUROCRYPT’87. pp. 267–278, 1987.
Arthur Sorkin, Lucifer, a Cryptographic Algorithm, Cryptologia. Vol. 8, No. 1. pp. 22–41. January 1984.
Michael C. Wood, technical report, Cryptech Inc.. Jamestown. NY. July 1990.
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 1994 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Ben-Aroya, I., Biham, E. (1994). Differential Cryptanalysis of Lucifer. In: Stinson, D.R. (eds) Advances in Cryptology — CRYPTO’ 93. CRYPTO 1993. Lecture Notes in Computer Science, vol 773. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-48329-2_17
Download citation
DOI: https://doi.org/10.1007/3-540-48329-2_17
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-57766-9
Online ISBN: 978-3-540-48329-8
eBook Packages: Springer Book Archive