Abstract
In this paper we study the influence of key-scheduling algorithms on the strength of blockciphers. We show that the key-scheduling algorithms of many blockciphers inherit obvious relationships between keys, and use these key relations to attack the blockciphers. Two new types of attacks are described: New chosen plaintext reductions of the complexity of exhaustive search attacks (and the faster variants based on complementation properties), and new low-complexity chosen key attacks. These attacks are independent of the number of rounds of the cryptosystems and of the details of the F-function and may have very small complexities. These attacks show that the key-scheduling algorithm should be carefully designed and that its structure should not be too simple. These attacks are applicable to both variants of LOKI and to Lucifer. DES is not vulnerable to the related keys attacks since the shift pattern in the key-scheduling algorithm is not the same in all the rounds.
Article PDF
Similar content being viewed by others
References
E. Biham and A. Shamir, Differential Cryptanalysis of DES-like Cryptosystems, Journal of Cryptology, Vol. 4, No. 1, pp. 3–72, 1991.
E. Biham and A. Shamir, Differential Cryptanalysis of Snefru, Khafre, REDOCII, 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 Advances in Cryptology, Proceedings of CRYPTO '91 pp. 156–171, Lecture Notes in Computer Science, Vol. 576, Springer-Verlag, Berlin, 1992.
E. Biham and A. Shamir, Differential Cryptanalysis of the Data Encryption Standard, Springer-Verlag, New York, 1993.
L. Brown, M. Kwan, J. Pieprzyk, and J. Seberry, Improving Resistance to Differential Cryptanalysis and the Redesign of LOKI, Advances in Cryptology, Proceedings of ASIACRYPT '91, pp. 36–50, Lecture Notes in Computer Science, Vol. 739, Spinger-Verlag, Berlin, 1993.
L. Brown, J. Pieprzyk, and J. Seberry, LOKI—A Cryptographic Primitive for Authentication and Secrecy Applications, Advances in Cryptology, Proceedings of AUSCRYPT '90, pp. 229–236, Lecture Notes in Computer Science, Vol. 453, Springer-Verlag, Berlin, 1990.
L. Brown and J. Seberry, Key Scheduling in DES-Type Cryptosystems, Advances in Cryptology, Proceedings of AUSCRYPT '90 221–228, Lecture Notes in Computer Science, Vol. 453, Springer-Verlag, Berlin, 1990.
H. Feistel, Cryptography and Data Security, Scientific American, Vol. 228, No. 5, pp. 15–23, May 1973.
M. E. Hellman, R. Merkle, R. Schroppel, L. Washington, W. Diffie, S. Pohlig, and P. Schweitzer, Results of an Initial Attempt to Cryptanalyze the NBS Data Encryption Standard, Technical Report, SEL 76-042, Stanford University, September 1976.
L. R. Knudsen, Cryptanalysis of LOKI, Advances in Cryptology, Proceedings of ASIACRYPT '91, pp. 22–35, Lecture Notes in Computer Science, Vol. 739, Springer-Verlag, Berlin, 1993.
L. R. Knudsen, Cryptanalysis of LOKI91, Advances in Cryptology, Proceedings of AUSCRYPT '92, pp. 196–208, Lecture Notes in Computer Science, Vol. 718, Springer-Verlag, Berlin, 1993.
M. Kwan and J. Pieprzyk, A General Purpose Technique for Locating Key Scheduling Weakness in DES-Like Cryptosystems, Advances in Cryptology, Proceedings of ASIACRYPT '91, pp. 23–246, Lecture Notes in Computer Science, Vol. 739, Springer-Verlag, Berlin, 1993.
X. Lai, J. L. Massey, and S. Murphy, Markov Ciphers and Differential Cryptanalysis, Advances in Cryptology, Proceedings of EUROCRYPT '91, pp. 17–38, Lecture Notes in Computer Science, Vol. 547, Springer-Verlag, Berlin, 1991.
X. Lai, On the Design and Security of Block Ciphers, Ph.D. Thesis, Swiss Federal Institute of Technology, Zurich, 1992.
S. Miyaguchi, A. Shiraishi, and A. 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, FIPS Publication 46, U.S. Department of Commerce, January 1977.
A. Shimizu and S. Miyaguchi, Fast Data Encryption Algorithm FEAL, Advances in Cryptology, Proceedings of EUROCRYPT '87, pp. 267–278, Lecture Notes in Computer Science, Vol. 304, Springer-Verlag, Berlin, 1987.
A. Sorkin, Lucifer, a Cryptographic Algorithm, Cryptologia, Vol. 8, No. 1, pp. 22–41, January 1984.
Author information
Authors and Affiliations
Additional information
Communicated by Don Coppersmith
This research was supported by the fund for the promotion of research at the Technion.
Rights and permissions
About this article
Cite this article
Biham, E. New types of cryptanalytic attacks using related keys. J. Cryptology 7, 229–246 (1994). https://doi.org/10.1007/BF00203965
Received:
Revised:
Issue Date:
DOI: https://doi.org/10.1007/BF00203965