Algebraic Cryptanalysis of
Block Ciphers in Practice

Milestone
paper that considerably extends the spectrum of known cryptanalytic
attacks on block ciphers. On the practical side, it is possible to recover the
DES key for up to 6 full rounds given only one single known plaintext (there
is also a weak attack on 12 rounds). More details
here (these slides were presented at Asiacrypt 2006).
Here is the full paper. Very few cases of really efficient algebraic
attacks on block ciphers are known (cf. CTC
below).

Fast
Algebraic Attacks on Block Ciphers and Courtois Toy Cipher. For now it is
posisble to break up to 10 rounds of CTC and CTC2, which are smallscale
variants of AES. Here is the initial CTC
paper and here is the newer CTC2 paper.

Johannes Buchmann, Andrei Pychkine and RalfPhilipp Weinmann:
Block ciphers sensitive to Groebner Basis Attacks:
Yet another paper showing many constructions of insecure ciphers. On
eprint/2005/200/.

Nicolas Courtois,
The Inverse Sbox and Two Paradoxes of Whitening,
Presented at the Rump Session of Crypto 2004. Here is
the long, extended version of the slides.

Nicolas Courtois,
Feistel Schemes and BiLinear Cryptanalysis,
in Crypto 2004, LNCS 3152, pp. 2340, Springer 2004. The
extended version is available at eprint.iacr.org/2005/251/.

Nicolas Courtois,
The Inverse Sbox, Nonlinear Polynomial Relations and
Cryptanalysis of Block Ciphers, in
AES 4 Conference, Bonn May 1012 2004, LNCS 3373,
pp. pp. 170188, Springer. Available
for Springer subscribers.
Press Releases About
Algebraic Attacks on AES and Other Ciphers.

Press/internet
releases in Polish:

New methods for attacking block
ciphers, two articles in Polish, In Security  Computerworld Polish edition:

Fast Moving Fronts in Computer Science: interview with Nicolas
Courtois published on the internet on 1st of July 2005,
read it here.

On the cover of New Scientist,
07 June 2003 issue, we hear about a
"Cipher Crisis", and on pages 3639, in an article
entitled "A Game of Chance",
Dana Mackenzie, deplores the growing incertainty about how long the current
encryption standard will remain secure. A short abstract
of this article can be found
here.

"Strict codes observed at conference",
by Leah McFall, a report about Courtois and Pieprzyk attack on AES, appeared in
Otago Daily, New Zealand, during the Asiacrypt 2002 conference, Tuesday,
3December 2002, page 15.
Read it here.

Hank Wolfe speaks about the weakness of AES:
"Codebreakers may have found US computer weakness", by
Joanna Norris, in Otago Daily, New Zealand, Friday, 29November 2002.
Read it here.

"Crucial Cipher Flawed, Cryptographers Claim",
by Charles Seife,
Science Magazine, 27 September 2002, page 2193.

AES News: a
Cryptogram article by Bruce Schneier, 15 September 2002. Here are
some comments on this article.
What is AES / Rijndael
The Advanced Encryption Standard (AES) is the current encryption
standard (FIPS197)
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 (FIPS197)
and thus destined it for massive worldwide 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 128bit 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 GF(256).
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

The Rijndael
web page, and the
latest specification of Rijndael. And here is
the Serpent web page. See also update on AES,
talk by Daemen and Rijmen at ISSE 2002. And here
is a report
on AES by Elisabeth Oswald, Joan Daemen and Vincent Rijmen: in the
version of October 30th 2002 (this report does not even enumerate all existing
algebraic attacks on AES).

The American
government NIST fully endorses and recommends AES with no restrictions:
see FIPS197 (Federal
Information Processing Standard number 197).

The intial position of
National Security Agency (NSA): first,
following an article
appeared in Cryptogram, 15 October 2000, the NSA did not endorse AES:
The NSA has not stated that it will use AES to protect classified
information. The NSA has not stated that it will use AES widely. It has simply
stated that, "where appropriate," it will use AES to meet its "national
security information protection needs."(...) Finally, Bruce Schneier
writes: It is possible that they will eventually use AES for classified
information. This would be a good thing. But my guess is that many more years
of internal cryptanalysis are required first.

Later in June 2003, the NSA extended their support for AES beyond
belief. AES becomes NSAapproved for all US Government Departments and
Agencies. In See paragraph
(6) of the NSA National Policy on the Use AES to Protect National Security
Systems and National Security Information. we read:

AES 128 bits and more are approved for up to "SECRET level".

AES with 192 and 256bit keys were approved even for "TOP
SECRET level" (later it has changed, and now it has to be 256 bits,
see here).

The implementation must be reviewed and certified by the NSA.

AES is now part of
suite B of recommended cryptographic algorithms (suite A, contains
classified algorithms for National security). One should
note that, maybe ideally all "TOP SECRET" information should be protected by
stronger algorithms from the suite A, however this cannot probably be done
systematically because these algorithms are themselves top secret, and their
usage cannot by too widespread in order to prevent the specs leaking out.
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.

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).

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
CourtoisPieprzykMurphyRobshaw 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
RobshawMurphy 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 Sflashv2,
in PKC 2004, LNCS Springer continued/revised in JiunMing Chen,
Nicolas Courtois, BoYin Yang: On
Asymptotic Security Estimates in XL and Gröbner BasesRelated Algebraic
Cryptanalysis, to be presented at ICICS'04, 2729 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.

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.

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 128bit 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).

Remark: Nessie, in addition to recommending AES, proposes only one
other 128bit 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 shortterm 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.