AES (original) (raw)

AES is NOT broken

## There is a news about some attack on Rijndael symmetric key encryption system. Prof T. Moh kindly allows us to print his short comment on this topic.

---

## On the Courtois-Pieprzyk's Attack on Rijndael

## T. Moh

Sept 18, 2002

Abstract

In the paper [1] N.T. Courtois and J. Pieprzyk propose an attack on Rijndael (AES) (for definition, the reader is referred to [2]). The attack is infeasible.

§ 1. Introduction

The method of XL [3] has been studied by us in [4] (it is listed in References of [1] as item [13]). There we give the following proposition based on Algebraic Geometry:

Proposition 2: If the solution set of (L1,...,Lm) is 0-dimensional and the solution set at infinity of (L1,..., Lm) is 0-dimensional or empty, then the XL program can be solved for D large enough.

We put down the following remark right after that:

The above Proposition 2 can not be applied if the intersection at infinite is 1- dimensional or higher. We may simply construct examples for the purpose of cryptography that the projective dimension of the ideal I* is 1 or higher (the above is routinely done for the TTM encryption systems (cf [5], [6], [7] )). In these cases, X(I*,D) will be a polynomial of degree 1 or higher in D, it is not expected to have X(I,D) < = D+1, in other words the number of variables may be always bigger than the number of equations for any D.

Let us quote the following simple example with dimension 1 at infinite from [4]:

Example: (4) Let I=(x12, x2+x12, x3+x12) in K[x1,x2,x3].

We show that: **``For the present system (i.e., Example 4), the number of variables is always greater than the number of linearly independent equations."**Hence, XL program fails for all D. (Note that in Appendix D.3 of [1], somehow the authors believe, or want the readers to believe, that we were talking only for D large enough!)

We repeatly point out that the method of XL can not work in general. For instance, in section 1 of [4], we have: `` From the theory of Hilbert-Serre, we may deduce that the XL program works for many interesting cases for D large enough. In general, the XL program will not work as established by Example 4". In section 2 of [4], we say: ``we show that the XL program can be applied only under restricted conditions, namely, the intersection at infinite is 0-dimensional or empty. The XL program is unlikely to be applicable in general as established by the above Example 4."

It is understandable that people sometimes publish imperfect articles. Thus in [4] we treat the authors of [3] (i.e., N. Courtois, A. Shamir, J. Patarin, and A. Klimov) with tender and care. In fact, one of the authors of [3] sent us an e-mail to show his appreciations. We believe that there should be no hard feelings. However, keeping using wrong statement against known evidence is harmful.

Somehow, the authors of [1] only want to quote us as saying: ``From the theory of Hilbert-Serre, we may deduce that the XL program works for many interesting cases for D large enough." Clearly they are quoting out of context.

Either they do not understand the above Proposition 2 and Example 4 or they are unable to compute the dimension of the projective part at infinite, but one thing is for sure, they use the XL program or XSL program improperly.

§ 2. Dimensions

Everybody knows that the S-box of Rijndael can be defined by x->x254. In Appendix A of [1], the authors present the S-box of Rijndael by 24 quadratic equations. This reduction of degree of a polynomial by including extra variables is an old trick of the K-theory invented by A. Grothendieck in 1960's, the so-called stable method in commutative algebra. What is the dimension of the projective variety defined by those equations at infinite? It is easy to find a lower bound. Since the degree 2 parts are bi-linear, i.e., they are sums of the terms xizj, therefore the said set contains the points with zj=0 so we have

(projective-) dimension > = 6

since there are 7 xi's. Thus clearly, both XL and XSL will fail no matter how far can one push the simulation.

The only plausible way of using XL or XSL to attack Rijndael is to find a clever way to present it in a system of lower degree equations (say, quadratic or cubic equations) such that (1) the projective part at infinite is of dimension 0 or empty and (2) the large enough D is of manageable size so that the program is computationally feasible. This is a difficult task and the authors of [1] fail at both points.

In Appendix C of [1], the authors try to simulate XSL. Fortunate for them, the dimension of the projective variety defined by those 14 equations at infinite of the ``Toy Cipher" they provide is 0. For sure, XL and XSL will work for this particular ``Toy Cipher" if we push for D large enough. How do we know it is of dimension 0? Just look at the degree 2 parts of those 14 equations. If x1 is not zero, then we must have x2=x3=y1=y2=y3=0, so that is just one projective point. If x1=0 and x2 is not zero, then we must have x3=y1=y2=y3=0, so that is just another projective point. One may continue finding other four projective points this way. Therefore we may conclude the dimension is 0.

But the simulation in Appendix C of [1] has nothing to do with the S-box of Rijndael.

§ 3. Simulation

Simulation is a powerful method in studying phenomena. However we must apply it with care. We must assemble facts and known theorems first. The simulations can only be done under control and guidances. The simulations in paper [1] are like unguided missiles. After they explode, we gain nothing. In [4], we state that: "Regretly, the ideals (L1,...,Lm) are not given explicitly in the simulations." N.Courtois is doing better this time by giving the system of equations they are simulating with. It helps us to understand their simulation is not useful. Next time we hope that they will be more respectable to the scientific facts.

Appendix (After Sept 24)

§ 4. Others' Comments

A comment of Don Coppersmith is interesting. In a message posted at http://aes.nist.gov/aes/default.htm under General Cryptographic issues, Don Coppersmith states: " I believe that the Courtois-Pieprzyk work is flawed. They overcount the number of linearly independent equations. The result is that they do not in fact have enough linear equations to solve the system, and the method does not break Rijndael." For further details, please read the original message .

D. Langs states: **"It appears AES is still safe for the time being. The fact that Don Coppersmith comes to the same conclusion is very comforting."**in an e-mail to us. He is kind to allow us to quote his words.

J.M. Chen states:"The key is the theory of Hilbert-Serre in commutative algebra." in the news group sci.crypt.

BitterOak writes:"A recent Slashdot story reported that AES might have been broken by the new XL attack of Courtois and Pieprzyk. However, it appears there aren't enough linearly independent equations for this attack to work against AES. Cryptographer T.Moh has a brief explanationhere, and Don Coppersmith posted a comment on the NIST AES discussion forum (under General Cryptonanlytic Attacks), which comes to the same conclusion. Coppersmith is one of the world's greatest cryptographers, so it seems safe to assume that AES has not been broken at this point." in Slashdot.org under "slashback" on Sept 26.

Homepage of Serpent states: ``A paper by Courtois and Pieprzyk claims an attack on Serpent (and on Rijndael), and got some publicity. We do not believe this result; see comments by Coppersmithand Moh."

Grypto-Gram Newsletter: Bruce Schneier makes the following addition to his previous Newsletter (which motivates our comment): "I can say with certainty that no one knows for certain if XSL can break Rijndael or Serpent or anything else. Actually, I can say something stronger: no one has produced an actual demonstration of XSL breaking even a simplified version of Rijndael or Serpent or anything else. This makes a lot of people skeptical." and "The XSL techniques have not been demonstrated yet. A number of respectable cryptographers, whose opinions I value highly, don't think the techniques work. Don Coppersmith has published a note on the topic. And T. Moh has a Web page about this. (To be fair, T. Moh and Nicolas Courtois have an ongoing disagreement about another crypto-related topic (i.e., TTM ). But while that certainly affects the motivations, it doesn't necessarily invalidate the math.)" on Crypto-Gram Newsletter dated Oct 15, 2002. He goes on to give the pointers to Coppersmith's and our comments. In the section of "Comments from Readers" of Grypto-Gram, Don Coppersmith states: "Your recent "Crypto-gram" leads people to believe that Courtois and Pieprzyk's XSL work breaks Rijndael." . Chronologically, the last Crypto-Gram has been published on Sept 15, our webpage has been up on Sept 18, and Don Coppersmith's famous comment has been posted on Sept 19. Does it explain the motivations?

N. Courtois and J. Patarin: In [8], they use our Proposition 2 above in their arguments. They agree that "of strictly positive dimension contained in the hyperplane at infinity" would make the process (i.e. XL method) fail. However, they restrict their revised new considerations of the XL method to the smallest field GF(2) with the well-known trick of adding the equations xi2+xi=0 to make the the component at infinity empty to satisfy the requirement of our Proposition 2 above. Note that this trick can not be used for the AES situation, since the corresponding equations would be xi256+xi=0, the degrees 256 would be too high for practical purpose.

Bibliography

[1] Courtois, N.T. and J. Pierprzy: Cryptanalysis of Block Ciphers with Overdefined Systems of Equations. Accepted by Asiacrypt 2002, Dec 2002.
[2] Daemen, and Rijmen, V.: AES proposal: Rijndael. http://carc.nist.gov/encryption/aes/rijndael/Rijndael.pdf
[3] Courtois, N. Shamir, A. Patarin, J. and Klimov, A.: Efficient Algorithms for Solving Overdefined Systems of Multivariate Polynomial Equations. Eurocrypt 2000.
[4] Moh, T.: On the Method of XL and Its Inefficiency Against TTM. http://eprint.icar.org/2001/047 or http://www.usdsi.com/XL.ps
[5] Moh, T.: A Public Key System with Signature and Master Key Functions. Communications in Algebra, 27(5), 2207-2222 (1999).
[6] Moh, T.: A Fast Public Key System With Signature And Master Key Functions. CrypTEC'99 (Proc. International Workshop on Cryptographic Techniques & E-commerce, City University of Hong Kong Press, July, 1999.
[7] Moh, T. and Chen J.M.: On the the Goubin-Courtois Attack on TTM. http://eprint.icar.org/2001/072, or http://www.usdsi.com/GC.ps
[8] Courtois, N and Patarin, J. About the XL Algorithm over GF(2), to appear in Cryptographers' Track RSA 2003, April 13-17, San Francisco.