Is AES a Secure Cipher ?

independent AES security observatory,
maintained by
Nicolas T. Courtois,
cryptologist and code-breaker (home page).

Frequently updated. Open for contribution.


  • Presentation New Frontiers in Symmetric Cryptanalysis, from the invited talk given by N. Courtois at at ECRYPT workshop Tools for Cryptanalysis in Krakow, 24-25 September, full version is available here.
  • Algebraic Cryptanalysis of Block Ciphers in Practice

    Press Releases About Algebraic Attacks on AES and Other Ciphers.

    What is AES / Rijndael

    The Advanced Encryption Standard (AES) is the current encryption standard (FIPS-197) intended to be used by U.S. Government organisations to protect sensitive (and even secret and top secret) information, see below. It is also becoming a (de facto) global standard for commercial software and hardware that use encryption or other security features.
    On October 2nd, 2000, NIST selected Rijndael as the Advanced Encryption Standard (FIPS-197) and thus destined it for massive world-wide usage. Serpent was second in the number of votes.

    The security of AES/Rijndael.

    Rijndael is an encryption algorithm that has been designed with the state of art in the cryptographic research and is still believed very secure by most of the people. It has been designed to have very strong resistance against the classical approximation attacks, such as linear cryptanalysis, differential cryptanalysis etc. However since Rijndael is very algebraic, new algebraic attacks appeared.

    Algebraic attacks on Rijndael.

    In a recent paper (Asiacrypt 2002), Nicolas Courtois and Josef Pieprzyk show that Rijndael can be written as an overdefined system of multivariate quadratic equations (MQ). For example authors show that for 128-bit Rijndael, the problem of recovering the secret key from one single plaintext can be written as a system of 8000 quadratic equations with 1600 binary unknowns. Thus the security of Rijndael requires that there are no efficient algorithms for solving such systems. In a paper published at Eurocrypt 2000 Shamir et al. describe an algorithm called XL (or/and FXL)  able to solve efficiently many such systems of equations. Attacking AES/Rijndael by such a method requires only a few known plaintexts to succeed. If this method can be made to work in practice, it is a major revolution in cryptanalysis: all classical attacks on block ciphers such as linear/differential and other approximation attacks require a number of plaintexts that is very big and grows exponentially in the number of rounds.

    In practice the algorithm XL fails (quite miserably) to break Rijndael. However the system obtained from Rijndael is not random, and has many special properties: it is overdefined, sparse and very structured. From this, in a recent paper, Nicolas Courtois and Josef Pieprzyk investigate how to improve XL and adapt it to such special systems. They propose a new class of attacks, attack, called XSL attacks. 
    There is no doubt that attacks such as XL and XSL do work in many interesting cases. Unfortunately they are heuristic, and their behaviour is not well understood. There are examples where these or similar attacks do behave in practice as it is predicted, and there are examples where they don't.
    This is how the security of AES became a hot topic.

    Does XSL break AES / Rijndael ?

    In the (widely read and commented) paper presented at Asiacrypt 2002 conference, Courtois and Pieprzyk show an attack that might break AES 256 bits, but it is not certain. There are also two different versions of the XSL attack that can be found on eprint. These XSL attacks are very general, and can be applied (at least in theory) to any block cipher. Later, Murphy and Robshaw remarked that in the particular case of AES it is more interesting to write equations over GF(256) instead of over GF(2). It is quite obvious how to do it, and it gives more or less the same possibilities in terms of sizes and types of equations that can be written for AES, with one important difference: the equations over GF(256) are more sparse. One version of the XSL attack over GF(256) seems to break AES in about 2^87 or 2^100 operations. The exact complexity of the attack is unknown and it is unclear if the attack works as it stands (today's computers are not powerful enough to handle such computations and check). Yet, nobody so far has been able to prove that it will not work (see below). Moreoever, in the field of algebraic attacks, it happens frequently that if an attack doesn't work as described, a slight modification probably does. In general, it is lik ely that in the future, the best attack on AES will be of the following form:
    1. Use the equations over
    2. Apply one of the versions of XSL.
    3. Apply a final step. The so called T' method, described in several papers, may or may not be sufficient.

    Official Status of AES

    So far so good...

    Is AES / Rijndael a good cipher ?
    Should it be used ? Does XSL attack work ?
    The growing controversy around the ciphers recommended by NIST, Nessie and the NSA.

    The American NIST, the NSA and the European consortium Nessie, do recommend AES, and clearly want you to use AES (see above). In the Nessie press release (most people will only read this and never look at technical documents) we read: "No weaknesses have been identified in any of these 17 algorithms."

    No weakness ? Really ? Should one use AES ?

    Here are some elements that will help to answer this question.

    1. First of all, as explained above, the doubt about the security of AES is real, see the article by Bruce Schneier, September 2002. Nothing changed since this article has been published (except for the alleged AES attack by Filiol that proved to be due to an incorrect progam).
    2. Next month, Schneier publishes two caustic comments on XSL. Schneier writes: A number of respectable cryptographers, whose opinions I value highly, don't think the techniques work. Two opinions are quoted, and let us examine them in details:
      • Don Coppersmith once wrote this very bitter remark on the so called T' method, a final component on XSL attacks. The problem is that, at first reading, Coppersmith just did not understand the T' method and wrote this remark that is misleading and has nothing to do with the XSL attack.
      • Moh's comments on AES: Prof. Moh is very hostile to the algebraic attacks, mixes good mathematics, bad English, has very poor understanding of cryptography (for example his proposed TTM public key cryptosystems are claimed to be very secure, but the public key is NOT given to the attacker !). Moh frequently presented the public with false or/and misleading arguments about XL and XSL that do apply to something completely different.  Then he would change his claims later, explain that he was always right, and strongly object with something else.  With time, Moh has progressively removed all his criticism of XL and XSL, (after he read more papers by Courtois, Patarin, Pieprzyk, Murphy and Robshaw - who did understand XSL attacks).  Moh remains very hostile to XSL. His latest objection (as for July 2003) is as usual midleading and does not apply. At the end of his page on AES, we read: Note that this trick can not be used for the AES situation, since the corresponding equations would be xi^256+xi=0, the degrees 256 would be too high for practical purpose. This is meant to explain that XL or XSL may, on second thoughts, work over GF(2) ... but with bigger fields it would be different... Well, first of all, there are many attacks on AES that work over GF(2), and in this case there is no problem. Then, in the Courtois-Pieprzyk-Murphy-Robshaw alleged attack in 2^100 or so, that operates indeed over GF(256). the equations of the field x^256+x=0 are in fact already included, but indirectly, because of new additional variables that exist in the Robshaw-Murphy equations. Indeed for each of the variables x, one SEPARATE VARIABLE exists for each of the following powers: x, x^2, x^4, x^8, x^16, x^32, x^64, x^128. Then instead of including the equation x = x^256, we include the following quadratic equations: (x) ^ 2 = (x^2), (x^2) ^ 2 = (x^4), up to (x^128) ^ 2 = (x). These equations do ensure that x = x^256, and will remove ALL the "unwanted" solutions of the system that are in the extension fields, or in projective space at infinity, that would otherwise prevent XSL from working.
        For additional comments on this, see:
        Nicolas Courtois: Algebraic Attacks over GF(2^k), Application to HFE Challenge 2 and Sflash-v2, in PKC 2004, LNCS Springer continued/revised in Jiun-Ming Chen, Nicolas Courtois, Bo-Yin Yang: On Asymptotic Security Estimates in XL and Gröbner Bases-Related Algebraic Cryptanalysis, to be presented at ICICS'04, 27-29 October 2004, Malaga, Spain and to appear in LNCS, Springer.
      • We see that, so far, there is no serious argument why XSL should not work whatsoever. We face here a natural phenomenon: people naively believe that XSL will not work..., but in fact they don't have a clue. Schneier is perfectly right at the beginning of his first article:
        no one knows for certain if XSL can break Rijndael. (And no one knows for certain that XSL cannot break Rijndael either). Schneier and Ferguson in their recent 2003 book "Practical Cryptography" say about AES: we don't quite trust the security...No other block cipher we know of has such a simple algebraic representation. We have no idea whether this leads to an attack or not, but not knowing is reason enough to be skeptical about the use of AES.
    3. Should AES be used ? Most people will answer yes, for now, due to the lack of a better standard. AES remains still millions of times better than many snake oil ciphers you can buy here or there. Moreover, even if AES will be broken in the coming years by a fast algebraic attack, it will probably still remain more secure than DES, and can still safely be used for applications that do not require long term security.
    4. However, though AES seems overdesigned with respect to differential or linear cryptanalysis, from the point of view of algebraic attacks, it is an extremely bad cipher. It is rather difficult to imagine a worse cipher, among ciphers that resist to other known attacks... (worse with respect to algebraic attacks). Therefore, even if it turns out that the XSL is NOT faster than the exhaustive search of a 128-bit key, NIST should sooner or later revoke AES. One should not take chances with these things. Another open call for a cryptographic standard will probably be done in the coming years (no need to hurry).
    5. Remark: Nessie, in addition to recommending AES, proposes only one other 128-bit cipher, Camellia, that shares the same weaknesses that AES. Yet, it is easy to design a fast cipher that would resist algebraic attacks (but seeing if it resists all the other known attacks too requires a lot of work).
      Though according to Vincent Rijmen, "XSL is not an attack it is a dream", many members of Nessie expressed serious reserves about the security of AES and Camellia (see this document, Section 2.2., on page 2). Steve Babbage suggested that for precautionary reasons, these ciphers should be only recommended for short-term security. Yet, in the final press release
      Nessie claims: "No weaknesses have been identified in any of these algorithms." 
      This is simply not true and such a recommendation could have serious consequences...

    The Security of Rijndael/AES and the XSL Attack on Block Ciphers.

    Survey and Strategic Thinking Papers in Algebraic Attacks on Block Ciphers.

    Papers Vaguely Related To the Idea of Algebraic Attacks on Block Ciphers.

    • Nicolas Courtois, Louis Goubin: An Algebraic Masking Method to Protect AES Against Power Attacks, eprint/2005/204/. In ICISC 2005, LNCS 3935, Springer.
    • Alex Biryukov and Christophe De Canniere: Block Ciphers and Systems of Quadratic Equations. FSE 2003, LNCS, Springer, and also presented at the Third Nessie Workshop. Available here.
    • Nicolas Courtois, Guilhem Castagnos and Louis Goubin: What do DES S-boxes Say to Each Other ? Available on This paper exhibits some weird structure in the DES S-boxes, probably nothing serious. This paper also inroduced a new type of algebraic attack on block ciphers with equations that involve a very small number of monomials that are not quadratic but of much higher degree. This was later applied by Courtois and Bard to DES (to appear in IMA Cryptography and Coding 2007), but it doesn't give very interesting attacks so far.

    The Emergence of a New Science:
    Algebraic Cryptanalysis.

    On Algebraic Immunity of Cipher Components (e.g. S-boxes).

    • Nicolas Courtois, Blandine Debraize and Eric Garrido: On Exact Algebraic [Non-]Immunity of S-boxes Based on Power Functions, eprint/2005/203/. Will be presented at ACISP 2006, 11th Australasian Conference. on. Information Security and Privacy. 3 - 5 July 2006. Melbourne. Australia.
    • Jung Hee Cheon and Dong Hoon Lee: Resistance of S-boxes against Algebraic Attacks. In FSE 2004, Springer. Can be found here.
      See also J
      ung Hee Cheon and Dong Hoon Lee: Almost Perfect Nonlinear Power Functions and Algebraic Attacks. Follow-up for their FSE 2004 paper above. Can be found here.
      Coments on this work: Nice idea, unfortunately, all main results of this paper are false and should be revised, see aforementioned eprint/2005/203/.
    • Claude Carlet: Improving the algebraic immunity of resilient and nonlinear functions and constructing bent functions. This paper shows how to contruct Boolean functions with some inbuild minimal resistance against algebraic attacks. See
    • Deepak Kumar Dalai and Kishan Chand Gupta and Subhamoy Maitra: Cryptographically Significant Boolean functions: Construction and Analysis in terms of Algebraic Immunity. To appear at FSE 2005.

    Not only block ciphers can be attacked by algebraic attacks:

    • J. H. Silverman, N. P. Smart, F. Vercauteren. An Algebraic Approach to NTRU (q = 2^n) via Witt Vectors and Overdetermined Systems of Nonlinear Equations. To appear in the proceedings of SCN'04, LNCS, Springer 2004. Here is the paper.
    • Nicolas Courtois, Willi Meier: Algebraic Attacks on Stream Ciphers with Linear Feedback. Eurocrypt 2003, LNCS 2656, pp. 345-359, Springer. The extended version. Algebraic attacks on stream ciphers are really devastating, there are tens of follow-up papers, see
    • Countless public key cryptosystems that are based on multivariate polynomials (as proposed by Matsumoto, Imai, Shamir, Moh etc.) can be broken by an algebraic attack. The three main breaktrough papers in this area are the three following:
      • Nicolas Courtois: The security of Hidden Field Equations (HFE), Cryptographers' Track Rsa Conference 2001, LNCS 2020, pp. 266-281, Springer-Verlag. Paper and slides: hfesec.pdf / hfesecsl.pdf. The first and only one known practical attack on HFE and HFE Challenge 1, at Crypto 2003 Joux and Faugère explain why this attack works and improve it slightly:
      • Jean-Charles Faugère, Antoine Joux: Algebraic Cryptanalysis of Hidden Field Equation (HFE) Cryptosystems Using Gröbner Bases, in Crypto 2003, LNCS 2729, pp. 44-60, Springer, August 2003. Cf. also the HFE page.
      • Jacques Patarin: Cryptanalysis of the Matsumoto and Imai Public Key Scheme of Eurocrypt'88, In Crypto'95, Springer-Verlag, pp. 248-261.
    • Problems such as factoring integers and solving discrete logs can be described in many ways as solving systems of overdefined mulativariate equations. (Factoring is equivalent to solving a single quadratic equation.) This area of research is still to be developed.

    Background work necessary for understanding the XSL attacks and various algebraic attacks, but not directly relevant to block ciphers:
    Relinearisation, XL algorithm, Gröbner bases, etc..

    • Gwenolé Ars PhD thesis (June 2005, Rennes University, France): he claims that AES could be broken with an algebraic attack achieving the maximum degree of only 3 and with expected total complexity of about 2^88.
    • Magali Bardet, Jean-Charles Faugère, Bruno Salvy, and Bo-Ying Yang, Asymptotic Expansion of the Degree of Regularity for Semi-Regular Systems of Equations, to be presented at the 8th Conférence des Méthodes Effectives en Géométrie Algebrique (MEGA '05, May 27- June 1, Porto Conte, Italy).
    • Bo-Yin Yang and Jiun-Ming Chen, All in the XL Family: Theory and Practice, ICISC '04, LNCS 3506, pp. 67-86.
    • A. J. M. Sedgers: A Master's Thesis on XL, Gröbner bases and algebraic attacks on block ciphers. And here is the presentation.
    • Claus Diem: The XL-algorithm and a Conjecture from Commutative Algebra, in Asiacrypt 2004, 5-9 Dec. 2004, Korea, LNCS, Springer.
    • Gwenole Ars, Jean-Charles Faugère, Makoto Sugita, Mitsuru Kawazoe and Hideki Imai: Comparison between XL and Gröbner Basis Algorithms, in Asiacrypt 2004, 5-9 Dec. 2004, Korea, LNCS, Springer.
    • At AES'4 conference in May 2004, Jean-Charles Faugère showed some experimental evidence to the effect that sparse systems of non-linear equations could maybe be solved in polynomial time by his advanced Gröbner bases algorithms. This would hold for 3 different definitions of sparsity that come from the XSL attack on AES. However no such results were ever published and no explanation was ever provided by Faugère...
    • Jiun-Ming Chen, Nicolas Courtois, Bo-Yin Yang: On Asymptotic Security Estimates in XL and Gröbner Bases-Related Algebraic Cryptanalysis, ICICS'04, LNCS 3269, pp. 401-413, Springer 2004.
    • Nicolas Courtois: Algebraic Attacks over GF(2^k), Application to HFE Challenge 2 and Sflash-v2. PKC 2004, March 1-4 2004, Singapore. This paper is concerned with different versions of XL algorithm for solving quadratic equations over GF(2k), k>1. It shows that algebraic obstacles that prevent some attacks from working can be removed at somewhat small cost. It is related to the XSL attack on AES in multiple ways and should be read by anyone interested in algebraic attacks. (However, the numerical results of this paper turned out to be too optimistic and are superceded by the ICICS paper quoted above.)
    • Bo-Yin Yang, Jiun-Ming Chen: Theoretical Analysis of XL over Small Fields, In ACISP 2004, LNCS 3108, pp. 277-288.
    • For Prof. Moh's comments on XL, XSL: be very careful and exercise your critical mind, comparing to what the other authors say. See above.
    • Nicolas Courtois, Jacques Patarin: About the XL Algorithm over GF(2), presented at Cryptographers' Track RSA 2003, April 13-17, San Francisco, LNCS 2612, pages 141-157, Springer.
    • Nicolas Courtois, Alexander Klimov, Jacques Patarin, and Adi Shamir:
      Efficient Algorithms for Solving Overdefined Systems of Multivariate Polynomial Equations
      , In Eurocrypt 2000, LNCS 1807, Springer, pp. 392-407. The extended version of the paper is available here, and here are the slides from Eurocrypt 2000.

    New Ideas and Special Properties of AES.

    A cipher as important as Rijndael should be under constant scrutiny...

    More or less serious results on AES...

    It is not because somebody says something, that it has to be true:

    Maintained by Nicolas T. Courtois
    Last updated on 24th of August 2007.