Skip to main content
Springer Nature Link
Log in

The Inverse S-Box, Non-linear Polynomial Relations and Cryptanalysis of Block Ciphers

  • Conference paper
Advanced Encryption Standard – AES (AES 2004)

Part of the book series: Lecture Notes in Computer Science ((LNSC,volume 3373))

Included in the following conference series:

  • 2390 Accesses

  • 31 Citations

Abstract

This paper is motivated by the design of AES. We consider a broader question of cryptanalysis of block ciphers having very good non-linearity and diffusion. Can we expect anyway, to attacks such ciphers, clearly designed to render hopeless the main classical attacks ? Recently a lot of attention have been drawn to the existence of multivariate algebraic relations for AES (and other) S-boxes. Then, if the XSL-type algebraic attacks on block ciphers [10] are shown to work well, the answer would be positive. In this paper we show that the answer is certainly positive for many other constructions of ciphers. This is not due to an algebraic attack, but to new types of generalised linear cryptanalysis, highly-nonlinear in flavour. We present several constructions of somewhat special practical block ciphers, seemingly satisfying all the design criteria of AES and using similar S-boxes, and yet being extremely weak. They can be generalised, and evolve into general attacks that can be applied – potentially- to any block cipher.

Work supported by the French Ministry of Research RNRT Project “X-CRYPT”.

This is a preview of subscription content, log in via an institution to check access.

Access this chapter

Log in via an institution

Institutional subscriptions

Preview

Unable to display preview. Download preview PDF.

Unable to display preview. Download preview PDF.

Similar content being viewed by others

Explore related subjects

Discover the latest articles, books and news in related subjects, suggested using machine learning.

References

  1. Armknecht, F., Krause, M.: Algebraic Atacks on Combiners with Memory. In: Boneh, D. (ed.) CRYPTO 2003. LNCS, vol. 2729, pp. 162–176. Springer, Heidelberg (2003)

    Chapter  Google Scholar 

  2. Aoki, K., Vaudenay, S.: On the Use of GF-Inversion as a Cryptographic Primitive. In: Matsui, M., Zuccherato, R.J. (eds.) SAC 2003. LNCS, vol. 3006, pp. 234–247. Springer, Heidelberg (2004)

    Chapter  Google Scholar 

  3. Anderson, R., Biham, E., Knudsen, L.: Serpent: A Proposal for the Advanced Encryption Standard

    Google Scholar 

  4. Canteaut, A., Videau, M.: Degree of composition of highly nonlinear functions and applications to higher order differential cryptanalysis. In: Knudsen, L.R. (ed.) EUROCRYPT 2002. LNCS, vol. 2332, p. 518. Springer, Heidelberg (2002)

    Chapter  Google Scholar 

  5. Campbell, K.W., Wiener, M.J.: Proof that DES is not a group. In: Brickell, E.F. (ed.) CRYPTO 1992. LNCS, vol. 740, pp. 512–520. Springer, Heidelberg (1993)

    Google Scholar 

  6. Courtois, N.: Feistel Schemes and Bi-Linear Cryptanalysis. In: Franklin, M. (ed.) CRYPTO 2004. LNCS, vol. 3152, pp. 15–19. Springer, Heidelberg (2004)

    Google Scholar 

  7. Courtois, N.: The security of Hidden Field Equations (HFE). In: Naccache, D. (ed.) CT-RSA 2001. LNCS, vol. 2020, pp. 266–281. Springer, Heidelberg (2001)

    Chapter  Google Scholar 

  8. Courtois, N.: Algebraic Attacks on Combiners with Memory and Several Outputs (June 23, 2003), Available on, http://eprint.iacr.org/2003/125/

  9. Courtois, N.: Fast Algebraic Attacks on Stream Ciphers with Linear Feedback. In: Boneh, D. (ed.) CRYPTO 2003. LNCS, vol. 2729, pp. 176–194. Springer, Heidelberg (2003)

    Chapter  Google Scholar 

  10. Courtois, N., Pieprzyk, J.: Cryptanalysis of Block Ciphers with Overdefined Systems of Equations. In: Zheng, Y. (ed.) ASIACRYPT 2002. LNCS, vol. 2501, pp. 267–287. Springer, Heidelberg (2002); a preprint with a different version of the attack is available at, http://eprint.iacr.org/2002/044/

    Chapter  Google Scholar 

  11. Courtois, N.: Higher Order Correlation Attacks, XL algorithm and Cryptanalysis of Toyocrypt. In: Lee, P.J., Lim, C.H. (eds.) ICISC 2002. LNCS, vol. 2587, pp. 182–199. Springer, Heidelberg (2003)

    Chapter  Google Scholar 

  12. Courtois, N., Meier, W.: Algebraic Attacks on Stream Ciphers with Linear Feedback. In: Biham, E. (ed.) EUROCRYPT 2003. LNCS, vol. 2656, pp. 345–359. Springer, Heidelberg (2003); An extended version is available at, http://www.minrank.org/toyolili.pdf

    Chapter  Google Scholar 

  13. Courtois, N., Daum, M., Felke, P.: On the Security of HFE, HFEv- and Quartz. In: Desmedt, Y.G. (ed.) PKC 2003. LNCS, vol. 2567, pp. 337–350. Springer, Heidelberg (2002); The extended version can be found at, http://eprint.iacr.org/2002/138/

    Chapter  Google Scholar 

  14. Daemen, J., Rijmen, V.: AES proposal: Rijndael, http://csrc.nist.gov/encryption/aes/rijndael/Rijndael.pdf

  15. Daemen, J., Rijmen, V.: The Design of Rijndael. AES - The Advanced Encryption Standard. Springer, Berlin (2002) ISBN 3-540-42580-2

    MATH  Google Scholar 

  16. Daemen, J., Rijmen, V., Preneel, B., Bosselaers, A., De Win, E.: The Cipher SHARK. In: Gollmann, D. (ed.) FSE 1996. LNCS, vol. 1039. Springer, Heidelberg (1996)

    Google Scholar 

  17. Ferguson, N., Schroeppel, R., Whiting, D.: A simple algebraic representation of Rijndael. In: Vaudenay, S., Youssef, A.M. (eds.) SAC 2001. LNCS, vol. 2259, p. 103. Springer, Heidelberg (2001)

    Chapter  Google Scholar 

  18. Knudsen, L.: Block Ciphers - Analysis, Design and Applications, PhD thesis, Aarhus University, Denmark (1994)

    Google Scholar 

  19. Harpes, C., Kramer, G., Massey, J.: A Generalization of Linear Cryptanalysis and the Applicability of Matsui’s Piling-up Lemma. In: Guillou, L.C., Quisquater, J.-J. (eds.) EUROCRYPT 1995. LNCS, vol. 921, pp. 24–38. Springer, Heidelberg (1995), http://www.isi.ee.ethz.ch/~harpes/GLClong.ps

    Google Scholar 

  20. Jakobsen, T., Knudsen, L.: Attacks on Block Ciphers of Low Algebraic Degree. Journal of Cryptology 14(3), 197–210 (2001)

    MATH  MathSciNet  Google Scholar 

  21. Jakobsen, T.: Higher-Order Cryptanalysis of Block Ciphers. Ph.D. thesis, Dept. of Math., Technical University of Denmark (1999)

    Google Scholar 

  22. Jakobsen, T.: Cryptanalysis of Block Ciphers with Probabilistic Non-Linear Relations of Low Degree. In: Krawczyk, H. (ed.) CRYPTO 1998. LNCS, vol. 1462, pp. 212–222. Springer, Heidelberg (1998)

    Google Scholar 

  23. Jakobsen, T., Knudsen, L.R.: The Interpolation Attack on Block Ciphers. In: Biham, E. (ed.) FSE 1997. LNCS, vol. 1267, pp. 28–40. Springer, Heidelberg (1997)

    Chapter  Google Scholar 

  24. Joux, A., Faugère, J.-C.: Algebraic Cryptanalysis of Hidden Field Equation (HFE) Cryptosystems Using Gröbner Bases. In: Boneh, D. (ed.) CRYPTO 2003. LNCS, vol. 2729, pp. 44–60. Springer, Heidelberg (2003)

    Google Scholar 

  25. Lidl, R., Niederreiter, H.: Finite Fields. In: Encyclopedia of Mathematics and its applications, vol. 20. Cambridge University Press, Cambridge

    Google Scholar 

  26. Menezes, A.J., van Oorschot, P.C., Vanstone, S.A.: Handbook of Applied Cryptography. CRC Press, Boca Raton (1996)

    Book  Google Scholar 

  27. Murphy, S., Robshaw, M.: Essential Algebraic Structure within the AES. In: Yung, M. (ed.) CRYPTO 2002. LNCS, vol. 2442, p. 1. Springer, Heidelberg (2002)

    Chapter  Google Scholar 

  28. Nyberg, K.: Differentially Uniform Mappings for Cryptography. In: Helleseth, T. (ed.) EUROCRYPT 1993. LNCS, vol. 765, pp. 55–64. Springer, Heidelberg (1994)

    Google Scholar 

  29. Patarin, J.: Hidden Fields Equations (HFE) and Isomorphisms of Polynomials (IP): two new families of Asymm. Algorithms. In: Maurer, U.M. (ed.) EUROCRYPT 1996. LNCS, vol. 1070, pp. 33–48. Springer, Heidelberg (1996)

    Google Scholar 

  30. Shamir, A., Patarin, J., Courtois, N., Klimov, A.: Efficient Algorithms for solving Overdefined Systems of Multivariate Polynomial Equations. In: Preneel, B. (ed.) EUROCRYPT 2000. LNCS, vol. 1807, pp. 392–407. Springer, Heidelberg (2000)

    Chapter  Google Scholar 

  31. Shannon, C.E.: Communication theory of secrecy systems. Bell System Technical Journal 28 (1949)

    Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Axalto Cryptographic Research & Advanced Security, 36-38 rue de la Princesse, BP 45, 78430, Louveciennes Cedex, France

    Nicolas T. Courtois

Authors
  1. Nicolas T. Courtois
    View author publications

    Search author on:PubMed Google Scholar

Editor information

Editors and Affiliations

  1. Cryptology and IT Security Research Group, Ruhr-University of Bochum Germany, P.O. Box,  

    Hans Dobbertin

  2. ESAT/COSIC, K.U. Leuven, Kasteelpark Arenberg 10, B-3001, Leuven-Heverlee, Belgium

    Vincent Rijmen

  3. Horst Görtz Institut für Sicherheit in der Informationstechnik, Ruhr-University of Bochum, Universitätsstrasse 150, 44780, Bochum, Germany

    Aleksandra Sowa

Rights and permissions

Reprints and permissions

Copyright information

© 2005 Springer-Verlag Berlin Heidelberg

About this paper

Cite this paper

Courtois, N.T. (2005). The Inverse S-Box, Non-linear Polynomial Relations and Cryptanalysis of Block Ciphers. In: Dobbertin, H., Rijmen, V., Sowa, A. (eds) Advanced Encryption Standard – AES. AES 2004. Lecture Notes in Computer Science, vol 3373. Springer, Berlin, Heidelberg. https://doi.org/10.1007/11506447_15

Download citation

Keywords

Publish with us

Policies and ethics