Abstract
Using recent results from coding theory, it is shown how to break block ciphers operating on GF(q) where the ciphertext is expressible as evaluations of an unknown univariate polynomial of low degree m over the plaintext with a typically low but non-negligible, probability Μ. The method employed is essentially Sudan's algorithm for decoding Reed-Solomon codes beyond the error-correction diameter. The known-plaintext attack needs n = 2m/Μ 2 plaintext/ciphertext pairs and the running time is polynomial in n. Furthermore, it is shown how to discover more general non-linear relations p(x, y)= 0 between plaintext x and ciphertext y that hold with small probability Μ. The second attack needs access to n = (2m/Μ)2 plaintext/ciphertext pairs where m = degp and its running time is also polynomial in n. As a demonstration, we break up to 10 rounds of a cipher constructed by Nyberg and Knudsen provably secure against differential and linear cryptanalysis.
Chapter PDF
Key words
References
Sigal Ar, Richard J. Lipton, Ronitt Rubinfeld, and Madhu Sudan. Reconstructing Algebraic Functions from Mixed Data, Proceedings of the 33rd Annual IEEE Symposium on Foundations of Computer Science, 1992, pp. 503–512. To appear SIAM Journal on Computing.
Elwyn R. Berlekamp. Factoring Polynomials over Large Finite Fields. Mathematics of Computation, pp. 713, vol. 24, no. 111, 1970.
Leonard Carlitz. The Distribution of Irreducible Polynomials in Several Indeterminates II. Canadian Journal of Mathematics 17:261–266, 1965.
Weishi Feng and Richard E. Blahut. On Decoding Reed-Solomon Codes Beyond the Packing Radii. Preprint. Coordinated Science Laboratory, University of Illinois at Urbana-Champaign, Nov., 1997.
Joachim von zur Gathen and Erich Kaltofen. Factoring multivariate polynomials over finite fields. Math. Comput, 45:251–261, 1985.
Carlo Harpes, Gerhard G. Kramer, and James L. Massey. A Generalization of Linear Cryptanalysis and the Applicability of Matsui's Piling-up Lemma. Eurocrypt '95, Lectures Notes in Computer Science, Springer, 1995.
Robin Hartshorne. Algebraic Geometry. Springer-Verlag, New York, 1977.
Tom Hoholdt. Private communication.
Thomas Jakobsen and Lars R. Knudsen. The Interpolation Attack on Block Ciphers. Fast Software Encryption IV, Lecture Notes in Computer Science, Springer, Haifa, 1997.
Xueijia Lai. Higher order derivatives and differential cryptanalysis. In Proc.“Symposium on Communication, Coding and Cryptography”, in honor of James L. Massey on the occasion of his 60'th birthday, Feb. 10–13, 1994, Monte-Verita, Ascona, Switzerland, 1994.
Xuejia Lai and James L. Massey. A Proposal for a New Block Encryption Standard, Advances in Cryptology — Eurocrypt '90 Proceedings, Springer-Verlag, Berlin, 1991, pp. 389–404.
Xuejia Lai, James L. Massey, and Sean Murphy. Markov ciphers and differential cryptanalysis. Advances in Cryptology, Proceedings Eurocrypt '91, LNCS 547, D. W. Davies, Ed., Springer-Verlag, 1991, pp. 17–38.
Florence J. MacWilliams and Neil J. A. Sloane. The Theory of Error-Correcting Codes. North-Holland, 1977.
Mitsuru Matsui. Linear cryptanalysis for DES cipher. Lecture Notes in Computer Science, 765 (1994), 386–397. (Advances in Cryptology — EUROCRYPT '93.)
Kaisa Nyberg and Lars R. Knudsen. Provable Security Against a Differential Attack. Journal of Cryptology, vol. 8, no. 1, 1995.
Ronald L. Rivest. The RC5 encryption algorithm. In Bart Preneel, editor, Fast Software Encryption: Second International Workshop, Lecture Notes in Computer Science, vol. 1008, pp. 86–96, Leuven, Belgium, Springer-Verlag, Published 1995.
Madhu Sudan. Decoding Reed Solomon Codes beyond the Error-Correction Diameter. Proc. 35th Annual Allerton Conference on Communication, Control and Computing, University of Illinois at Urbana-Champaign, 1997.
Madhu Sudan. Decoding of Reed Solomon Codes beyond the Error-Correction Bound. Journal of Complexity, 13(1):180–193, March 1997.
Madhu Sudan. Preprint. May 1998.
Author information
Authors and Affiliations
Editor information
Rights and permissions
Copyright information
© 1998 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Jakobsen, T. (1998). Cryptanalysis of block ciphers with probabilistic non-linear relations of low degree. In: Krawczyk, H. (eds) Advances in Cryptology — CRYPTO '98. CRYPTO 1998. Lecture Notes in Computer Science, vol 1462. Springer, Berlin, Heidelberg. https://doi.org/10.1007/BFb0055730
Download citation
DOI: https://doi.org/10.1007/BFb0055730
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-64892-5
Online ISBN: 978-3-540-68462-6
eBook Packages: Springer Book Archive