Abstract
In a recent paper we developed a new cryptanalytic technique based on impossible differentials, and used it to attack the Skipjack encryption algorithm reduced from 32 to 31 rounds. In this paper we describe the application of this technique to the block ciphers IDEA and Khufu. In both cases the new attacks cover more rounds than the best currently known attacks. This demonstrates the power of the new cryptanalytic technique, shows that it is applicable to a larger class of cryptosystems, and develops new technical tools for applying it in new situations.
Chapter PDF
Similar content being viewed by others
References
C. M. Adams, The CAST-256 Encryption Algorithm, AES submission, available at http://www.entrust.com/resources/pdf/cast-256.pdf.
C. M. Adams, S. E. Tavares, Designing S-boxes for Ciphers Resistant to Differential Cryptanalysis, Proceedings of the 3rd symposium on State and Progress of Research in Cryptography, pp. 181–190, 1993.
I. Ben-Aroya, E. Biham, Differential Cryptanalysis of Lucifer, Journal of Cryptology, Vol. 9, No. 1, pp. 21–34, 1996.
E. Biham, A. Biryukov, How to Strengthen DES Using Existing Hardware, Lecture Notes in Computer Science 917, Advances in Cryptology-Proceedings of ASIACRYPT’94, pp. 398–412, Springer Verlag, 1995.
E. Biham, A. Biryukov, A. Shamir, Cryptanalysis of Skipjack Reduced to 31 Rounds Using Impossible Differentials, Lecture Notes in Computer Science, Advances in Cryptology-Proceedings of EUROCRYPT’99, Springer-Verlag, 1999.
E. Biham, A. Shamir, Differential Cryptanalysis of the Data Encryption Standard, Springer-Verlag, 1993.
E. Biham, New Types of Cryptanalytic Attacks Using Related Keys, J. of Cryptology, Vol. 7, pp. 229–246, 1994.
A. Biryukov, E. Kushilevitz, From Differential Cryptanalysis to Ciphertext-Only Attacks, Lecture Notes in Computer Science 1462, Advances in Cryptology-Proceedings of CRYPTO’98, pp. 72–88, Springer-Verlag, 1998.
J. Borst, L. R. Knudsen, V. Rijmen, Two Attacks on Reduced IDEA (extended abstract), Lecture Notes in Computer Science 1223, Advances in Cryptology-Proceedings of EUROCRYPT’97, pp. 1–13, Springer-Verlag, 1997.
J. Daemen, R. Govaerts, J. Vandewalle, Cryptanalysis of 2,5 Rounds of IDEA (extended abstract), Technical Report ESAT-COSIC Technical Report 93/1, Department of Electrical Engineering, Katholieke Universiteit Leuven, March 1993.
J. Daemen, R. Govaerts, J. Vandewalle, Weak Keys of IDEA, Lecture Notes in Computer Science 773, Advances in Cryptology-Proceedings of CRYPTO’93, pp. 224–231, Springer-Verlag, 1994.
H. Gilbert, P. Chauvaud, A chosen plaintext attack of the 16-round Khufu cryptosystem, Lecture Notes in Computer Science 839, Advances in Cryptology-Proceedings of CRYPTO’94, pp. 359–368, Springer-Verlag, 1994.
P. Hawkes, L. O’Connor, On Applying Linear Cryptanalysis to IDEA, Lecture Notes in Computer Science 1163, Advances in Cryptology-Proceedings of ASIACRYPT’96, pp. 105–115, Springer-Verlag, 1996.
P. Hawkes, Differential-Linear Weak Key Classes of IDEA, Lecture Notes in Computer Science 1403, Advances in Cryptology-Proceedings of EUROCRYPT’98, pp. 112–126, Springer-Verlag, 1998.
T. Jakobsen, Cryptanalysis of Block ciphers with probabilistic Non-linear relations of Low Degree, Lecture Notes in Computer Science 1462, Advances in Cryptology-Proceedings of CRYPTO’98, pp. 212–222, Springer-Verlag 1998.
J. Kelsey, B. Schneier, D. Wagner, Key-Schedule Cryptanalysis of IDEA, G-DES, GOST, SAFER, and Triple-DES, Lecture Notes in Computer Science 1109, Advances in Cryptology-Proceedings of CRYPTO’96, pp. 237–251, Springer-Verlag, 1996.
L. R. Knudsen, DEAL-A 128-bit Block Cipher, AES submission, available at http://www.ii.uib.no/~larsr/papers/deal.ps, 1998.
X. Lai, On the Design and Security of Block Ciphers, Ph.D. thesis, Swiss Federal Institute of Technology, Zurich 1992.
X. Lai, J. L. Massey, A Proposal for a New Block Encryption Standard, Lecture Notes in Computer Science 473, Advances in Cryptology-Proceedings of EUROCRYPT’90, pp. 389–404, Springer-Verlag, 1991.
X. Lai, J. L. Massey, S. Murphy, Markov Ciphers and Differential Cryptanalysis, Lecture Notes in Computer Science 547, Advances in Cryptology-Proceedings of EUROCRYPT’91, pp. 17–38, Springer-Verlag, 1992.
M. Matsui, New Block Encryption Algorithm MISTY, Lecture Notes in Computer Science 1267, Fast Software Encryption-4th International Workshop (FSE’97), pp. 54–68, Springer-Verlag, 1997.
M. Matsui, New Structure of Block Ciphers with Provable Security Against Differential and Linear Cryptanalysis, Lecture Notes in Computer Science 1039, Fast Software Encryption-3rd InternationalWorkshop (FSE’96), pp. 205–218, Springer Verlag, 1996
W. Meier, On the Security of the IDEA Block Cipher, Lecture Notes in Computer Science 765, Advances in Cryptology-Proceedings of EUROCRYPT’93, pp. 371–385, Springer-Verlag, 1994.
R. C. Merkle, Fast Software Encryption Functions, Lecture Notes in Computer Science 537, Advances in Cryptology-Proceedings of CRYPTO’90, pp. 476–501, Springer-Verlag, 1990.
S. Miyaguchi, A. Shiraishi, A. Shimizu, Fast Data Encryption Algorithm FEAL-8, Review of Electrical Communications Laboratories, Vol. 36, No. 4, pp. 433–437, 1988.
S. Miyaguchi, FEAL-N specifications, NTT, 1989.
K. Nyberg and L. R. Knudsen, Provable Security Against a Differential Attack, Journal of Cryptology, Vol. 8, No. 1, pp. 27–37, 1995.
T. Shimoyama, S. Moriai, T. Kaneko, Improving the High Order Differential Attack and Cryptanalysis of the KN Cipher, Lecture Notes in Computer Science 1396, Proceedings of the First International Workshop on Information Security (ISW’97) (Japan), pp. 32–42, Springer-Verlag 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
Biham, E., Biryukov, A., Shamir, A. (1999). Miss in the Middle Attacks on IDEA and Khufu. 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_10
Download citation
DOI: https://doi.org/10.1007/3-540-48519-8_10
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