Re: XLS Attack on AES (Rijndael)
[2003-10-25 00:20] Michael Sierchio <kudzu@xxxxxxxxxxxx> wrote:
> latte1@xxxxxxxxxxxx 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] ..