Re: XLS Attack on AES (Rijndael)

[Christian Ruediger Bahls <christian.bahls@gmx.de>]

[2003-10-25 00:20] Michael Sierchio <kudzu@tenebras.com> wrote:
> latte1@hushmail.com wrote:
> >I read, some time ago, about a new form of attack on
> >the AES algorithm: Rijndael...
> Largely FUD (or FUDGE, if you will), and the inference drawn (AESbroken)
> is unwarranted.  Robshaw and Murphy seem to be voicing an aesthetic
> objection to the marked linearity in the diffusion layer -- even though
> they clearly state that this offers no clear advantage to conventional
> linear and differential cryptanalysis.  Also note that Robshaw worked
> on RSA's finalist candidate (RC6) for AES, though he appears never to
> have been given adequate credit.
Robshaw and Murphy[1] just described an isomorphic way to express Rijndael.
more important is the paper by Courtois and Pieprzyk[2] in which they describe
an algebraic attack on Rijndael.

expressing Rijndael over GF(2^8) [BES .. as suggested by Robshaw and Murphy]
basicly improves the properties of the equations matrix.

i don't think the question in case is whether aes is broken now,
but whether it will be broken in 10 years from now ..

i don't think last years findings are just about aesthetic objections ..

niels ferguson has been talking about aes' algebraic properties at HAL 2001 ..
[niels has been involved with designing twofish - another AES finalist ..]

bruce schneier[co-developer of twofish ..] has some doubts too,
  quoted from http://www.schneier.com/crypto-gram-0209.html:
[...] Courtois and Pieprzyk posted a paper outlining a new attack against 
Rijndael (AES) and Serpent. The authors used words like "optimistic evaluation" 
and "might be able to break" to soften their claims, but the paper described a 
better-than-brute-force attack against Serpent, and possibly one against 
Rijndael as well.
Basically, the attack works by trying to express the entire algorithm as 
multivariate quadratic polynomials, and then using an innovative technique to 
treat the terms of those polynomials as individual variables. This gives you a 
system of linear equations in a quadratically large number of variables, which 
you have to solve. There are a bunch of minimization techniques, and several 
other clever tricks you can use to make the solution easier. (This is a gross 
oversimplification of the paper; read it for more detail.)
[...]
At Crypto 2002, Murply and Robshaw published a surprising result, allowing all 
of AES to be expressed in a single field. They postulated a cipher called BES 
that treats each AES byte as an 8-byte vector. BES operates on blocks of 128 
bytes; for a special subset of the plaintexts and keys, BES is isomorphic to 
AES. This representation has several nice properties that may make it easier to 
cryptanalyze.

in cryptogram october 2002 he relativates that a bit ..
.. though there seems some disagreement about the papers refered to by schneier
   (especially a lot of Prof. Moh's claims seem to be doubted)


there has been an article in the "New Scientist"
(New Scientist vol 178 issue 2398 - 07 June 2003, page 36)[4]:
[you can browse their archive with a 7-day trial membership]

so one probably would suggest to read the papers,
 and follow the proceeding of (Any)Crypt closely ..

> The question to ask is:  How well does Rijndael meet the design goals
> established by the NIST?"  And the answer, quite simply, is: "very well."
yes if you are talking about differential crypt analysis and the likes ..
.. though from time to time there appear new attack methods
   that obsolete whole classes of algorithms

at least the findings mentioned above cast some shadows about the
usability of aes in the long-term future ..

i suggest reading [3] and working from there on
(i might be terribly wrong though .. algebra is not my major)

yours

christian bahls
  maths student
  university of rostock
  germany

footnotes:
[1] Essential Algebraic Structure Within the AES (2002)
    http://citeseer.nj.nec.com/murphy02essential.html
[2] Cryptanalysis of Block Ciphers with Overdefined Systems of Equations (2002)
    (Asiacrypt 2002, LNCS 2501, pp. 267-287, Springer. )
    http://citeseer.nj.nec.com/courtois02cryptanalysis.html
[3] Comments on the Security of the AES and the XSL Technique
    http://citeseer.nj.nec.com/548008.html
[4] 
http://archive.newscientist.com/secure/article/article.jsp?rp=1&id=mg17823985.000
    [this link might be customized and will probably not work then]
-- 
  if you have an interesting or even challenging internship to offer ..
  please do not hesitate to contact me [am finishing my diploma] ..