New types of cryptanalytic attacks using related keys. (English) Zbl 0812.94012

Summary: 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.


94A60 Cryptography
68P25 Data encryption (aspects in computer science)
Full Text: DOI


[1] Biham, E.; Shamir, A., Differential Cryptanalysis of DES-like Cryptosystems, Journal of Cryptology, 4, No. 1, 3-72 (1991) · Zbl 0729.68017
[2] 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. · Zbl 0825.94200
[3] Biham, E.; Shamir, A., Differential Cryptanalysis of the Data Encryption Standard (1993), New York: Springer-Verlag, New York · Zbl 0778.94005
[4] Brown, L.; Kwan, M.; Pieprzyk, J.; Seberry, J., Improving Resistance to Differential Cryptanalysis and the Redesign of LOKI, Advances in Cryptology, Proceedings of ASIACRYPT ’91, 36-50 (1993), Berlin: Spinger-Verlag, Berlin · Zbl 0806.94015
[5] Brown, L.; Pieprzyk, J.; Seberry, J., LOKI—A Cryptographic Primitive for Authentication and Secrecy Applications, Advances in Cryptology, Proceedings of AUSCRYPT ’90, 229-236 (1990), Berlin: Springer-Verlag, Berlin
[6] Brown, L.; Seberry, J., Key Scheduling in DES-Type Cryptosystems, Advances in Cryptology, Proceedings of AUSCRYPT ’90, 221-228 (1990), Berlin: Springer-Verlag, Berlin
[7] Feistel, H., Cryptography and Data Security, Scientific American, 228, No. 5, 15-23 (1973)
[8] 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.
[9] Knudsen, L. R., Cryptanalysis of LOKI, Advances in Cryptology, Proceedings of ASIACRYPT ’91, 22-35 (1993), Berlin: Springer-Verlag, Berlin · Zbl 0809.94013
[10] Knudsen, L. R., Cryptanalysis of LOKI91, Advances in Cryptology, Proceedings of AUSCRYPT ’92, 196-208 (1993), Berlin: Springer-Verlag, Berlin · Zbl 0868.94037
[11] Kwan, M.; Pieprzyk, J., A General Purpose Technique for Locating Key Scheduling Weakness in DES-Like Cryptosystems, Advances in Cryptology, Proceedings of ASIACRYPT ’91, 23-246 (1993), Berlin: Springer-Verlag, Berlin · Zbl 0825.94204
[12] Lai, X.; Massey, J. L.; Murphy, S., Markov Ciphers and Differential Cryptanalysis, Advances in Cryptology, Proceedings of EUROCRYPT ’91, 17-38 (1991), Berlin: Springer-Verlag, Berlin · Zbl 0777.94013
[13] Lai, X., On the Design and Security of Block Ciphers, Ph.D. Thesis (1992), Zurich: Swiss Federal Institute of Technology, Zurich
[14] Miyaguchi, S.; Shiraishi, A.; Shimizu, A., Fast Data Encryption Algorithm FEAL-8, Review of Electrical Communications Laboratories, 36, No. 4, 433-437 (1988)
[15] National Bureau of Standards, Data Encryption Standard, FIPS Publication 46, U.S. Department of Commerce, January 1977.
[16] Shimizu, A.; Miyaguchi, S., Fast Data Encryption Algorithm FEAL, Advances in Cryptology, Proceedings of EUROCRYPT ’87, 267-278 (1987), Berlin: Springer-Verlag, Berlin · Zbl 1464.94051
[17] Sorkin, A., Lucifer, a Cryptographic Algorithm, Cryptologia, 8, No. 1, 22-41 (1984)
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.