Abstract
The problem MQ of solving a system of multivariate quadratic equations over a finite field is relevant to the security of AES and for several public key cryptosystems. For example Sflash, the fastest known signature scheme (cf. [1]), is based on MQ equations over GF(27), and Patarin’s 500 $ HFE Challenge 2 is over GF(24). Similarly, the fastest alleged algebraic attack on AES due to Courtois, Pieprzyk, Murphy and Robshaw uses a MQ system over GF(28).
At present very little is known about practical solvability of such systems of equations over GF(2k). The XL algorithm for Eurocrypt 2000 was initially studied over GF(p), and only recently in two papers presented at CT-RSA’02 and ICISC’02 the behaviour of XL is studied for systems of equations over GF(2). In this paper we show (as expected) that XL over GF(2k), k>1 (never studied so far) does not always work very well. The reason is the existence of additional roots to the system in the extension field, which is closely related to the remark made by Moh, claiming that the XSL attack on AES cannot work. However, we explain that, the specific set of equations proposed by Murphy and Robshaw already contains a structure that removes the problem. From this, we deduce a method to modify XL so that it works much better over GF(2k). In addition we show how to break the signature scheme Sflash-v2 recently selected by the European consortium Nessie, by three different methods derived from XL. Our fastest attack is in 258. All the three attacks apply also to HFE Challenge 2, and our best attack is in 263.
Chapter PDF
Similar content being viewed by others
Keywords
References
Akkar, M.-L., Courtois, N., Goubin, L., Duteuil, R.: A Fast and Secure Implementation of Slash. In: Desmedt, Y.G. (ed.) PKC 2003. LNCS, vol. 2567, pp. 267–278. Springer, Heidelberg (2002)
Barkee, B., Can, D.C., Ecks, J., Moriarty, T., Ree, R.F.: Why You Cannot Even Hope to use Gröbner Bases in Public Key Cryptography: An Open Letter to a Scientist Who Failed and a Challenge to Those Who Have Not Yet Failed. Journal of Symbolic Computation 18, 497–501 (1994)
Coppersmith, D., Winograd, S.: Matrix multiplication via arithmetic progressions. J. Symbolic Computation 9, 251–280 (1990)
Courtois, N., Daum, M., Felke, P.: On the Security of HFE, HFEvand Quartz. In: Desmedt, Y.G. (ed.) PKC 2003. LNCS, vol. 2567, pp. 337–350. Springer, Heidelberg (2002)
Courtois, N., Goubin, L., Meier, W., Tacier, J.-D.: Solving Underdefined Systems of Multivariate Quadratic Equations. In: Naccache, D., Paillier, P. (eds.) PKC 2002. LNCS, vol. 2274, pp. 211–227. Springer, Heidelberg (2002)
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)
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) available at, http://eprint.iacr.org/2002/087/
Patarin, J., Courtois, N., Goubin, L.: C*-+ and HM - Variations around two schemes of T. Matsumoto and H. Imai. In: Ohta, K., Pei, D. (eds.) ASIACRYPT 1998. LNCS, vol. 1514, pp. 35–50. Springer, Heidelberg (1998)
Patarin, J., Goubin, L., Courtois, N.: Quartz, 128-bit long digital signatures. In: Naccache, D. (ed.) CT-RSA 2001. LNCS, vol. 2020, pp. 282–297. Springer, Heidelberg (2001), See [10] for the updated Quartz specification
Patarin, J., Goubin, L., Courtois, N.: Quartz, 128-bit long digital signatures; An updated version of Quartz specification, available at, http://www.cryptosystem.net/quartz/
Patarin, J., Goubin, L., Courtois, N.: Flash, a fast multivariate signature algorithm. In: Naccache, D. (ed.) CT-RSA 2001. LNCS, vol. 2020, pp. 298–307. Springer, Heidelberg (2001)
Courtois, N., Goubin, L., Patarin, J.: Second updated version of Sflash specification (Sflash-v2), Available at, http://www.cryptosystem.net/sflash/
Courtois, N., Goubin, L., Patarin, J.: SFLASHv3, a fast asymmetric signature scheme. New, third version of Sflash specification (Sflash-v3), proposed after this paper was written, Available on eprint.iacr.org/2003/211/
Courtois, N., Patarin, J.: About the XL Algorithm over GF(2). In: Joye, M. (ed.) CT-RSA 2003. LNCS, vol. 2612, pp. 141–157. Springer, Heidelberg (2003)
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/
Daum, M.: Das Kryptosystem HFE und quadratische Gleichungssysteme über endlichen Körpern, Diplomarbeit, Universität Dortmund (2001), Available from email daum@itsc.ruhr-uni-bochum.de
Faugère, J.-C.: A new efficient algorithm for computing Gröbner bases (F 4). Journal of Pure and Applied Algebra 139, 61–88 (1999), See www.elsevier.com/locate/jpaa
Faugère, J.-C.: A new efficient algorithm for computing Gröbner bases without reduction to zero (F5). In: Workshop on Applications of Commutative Algebra, Catania, Italy, April 3-6. ACM Press, New York (2002)
Faugère, J.-C.: Report on a successful attack of HFE Challege 1 with Gröbner bases algorithm F5/2, announcement that appeared in sci.crypt newsgroup on the internet in April 19 (2002)
Garey, M., Johnson, D.: Computers and Intractability, a guide to the theory of NP-completeness. Freeman, New York (see in particular p. 251)
Gilbert, H., Minier, M.: Cryptanalysis of SFLASH. In: Knudsen, L.R. (ed.) EUROCRYPT 2002. LNCS, vol. 2332, pp. 288–298. Springer, Heidelberg (2002)
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)
Martin-Deschamps, M.: Private communication. University of Versailles
Moh, T.T.: On The Method of XL and Its Inefficiency Against TTM. In: Invited talk at the American Mathematical Society regional meeting at the University of Notre Dame, April 8 (2000) available at, http://eprint.iacr.org/2001/047/
Moh, T.T.: On The Courtois-Pieprzyk’s Attack on Rijndael, September 18 (2002), available at, http://www.usdsi.com/aes.html
Murphy, S., Robshaw, M.: Essential Algebraic Structure within the AES. In: Yung, M. (ed.) CRYPTO 2002. LNCS, vol. 2442, p. 1. Springer, Heidelberg (2002)
NESSIE Portfolio of recommended cryptographic primitives, available at, www.cosic.esat.kuleuven.ac.be/nessie/deliverables/decision-final.pdf
NESSIE Security Report, revised final version 2.0, available at, https://www.cosic.esat.kuleuven.ac.be/nessie/deliverables/D20-v2.pdf
Patarin, J.: Cryptanalysis of the Matsumoto and Imai Public Key Scheme of Eurocrypt’88. In: Coppersmith, D. (ed.) CRYPTO 1995. LNCS, vol. 963, pp. 248–261. Springer, Heidelberg (1995)
Patarin, J.: Hidden Fields Equations (HFE) and Isomorphisms of Polynomials (IP): two new families of Asymm. In: Maurer, U.M. (ed.) EUROCRYPT 1996. LNCS, vol. 1070, pp. 33–48. Springer, Heidelberg (1996)
Shamir, A., Kipnis, A.: Cryptanalysis of the HFE Public Key Cryptosystem. In: Wiener, M. (ed.) CRYPTO 1999. LNCS, vol. 1666, p. 19. Springer, Heidelberg (1999)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2004 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Courtois, N.T. (2004). Algebraic Attacks over GF(2k), Application to HFE Challenge 2 and Sflash-v2. In: Bao, F., Deng, R., Zhou, J. (eds) Public Key Cryptography – PKC 2004. PKC 2004. Lecture Notes in Computer Science, vol 2947. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-540-24632-9_15
Download citation
DOI: https://doi.org/10.1007/978-3-540-24632-9_15
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-21018-4
Online ISBN: 978-3-540-24632-9
eBook Packages: Springer Book Archive