FC: Bruce Schneier on possible weaknesses in encryption systems

[Declan McCullagh <declan () well com>]

---

Date: Sun, 15 Sep 2002 16:47:45 -0500
From: Bruce Schneier <schneier () counterpane com>
Subject: CRYPTO-GRAM, September 15, 2002


                 CRYPTO-GRAM

              September 15, 2002

              by Bruce Schneier
               Founder and CTO
      Counterpane Internet Security, Inc.
           schneier () counterpane com
         <http://www.counterpane.com>

[...]

                    AES News



AES may have been broken.  Serpent, too.  Or maybe not.  In either case, 
there's no need to panic.  Yet.  But there might be soon.  Maybe.

Some of the confusion stems from different definitions of "attack."  To a 
cryptographer, an attack is anything that breaks the algorithm faster than 
brute force, even if it is completely impractical.  To an engineer, an 
attack is something that is practical, or at least might be practical in a 
few years.  An attack that breaks AES to a cryptographer might not to an 
engineer.  The rest of the confusion stems from not being sure the attack 
actually works.

Let's start from the beginning.  A few months ago, 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.)

The attack depends much more critically on the complexity of the nonlinear 
components than on the number of rounds.  Ciphers with small S-boxes and 
simple structures are particularly vulnerable.  Serpent has small S-boxes 
and a simple structure.  AES has larger S-boxes, but a very simple 
algebraic description.  (Twofish has small S-boxes, too, but a more complex 
nonlinear structure.  No one has implemented the attack against Twofish, 
but I'm not willing to stand up and declare the cipher immune.)

These are amazing results.  Previously, the best attacks worked by breaking 
simplified variants of AES using very impractical attack models (e.g., 
requiring immense amounts of chosen plaintext).  This paper claimed to 
break the entire algorithm, and with only one or two known 
plaintexts.  Moreover, the first cipher broken was Serpent: the cipher 
universally considered to be the safest, most conservative choice.

There was some buzz about the paper in the academic community, but it 
quickly died down.  I believe the problem was that the paper was dense and 
hard to understand.  The attack technique, something called XSL, was brand 
new.  (It's based on another technique, called XL, presented at Eurocrypt 
2000.)  And the results were so startling -- an attack against Serpent! -- 
that they were just discounted.

Meanwhile, Fuller and Millan released a paper showing that AES's 8x8-bit 
S-box is really an 8x1-bit S-box.  There's really only one piece of 
nonlinearity going on in the cipher; everything else is linear.  Another 
paper came from Filiol.  He claimed to have detected some biases in the 
Boolean functions of AES, which could possibly be used to break AES.  But 
there are just too few details in the paper to make sense of this claim yet.

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.

Most interestingly, the BES representation gives the XSL method a much more 
concise representation, and therefor sparser and simpler equations that are 
easier to solve.  Moreover, there are intermediate versions of BES -- 
2-byte vectors, 4-byte vectors, etc. -- decreasing in complexity as you 
head towards BES-8.  These representations identified a bunch more 
quadratic equations that apply to AES and BES.  When you throw them into 
the XSL mix, Courtois and Pieprzyk's attack now has a 2^100 complexity, as 
opposed to the wiffly waffly 2^200-or-so complexity claimed earlier.

So, here's the current scorecard.  Courtois and Pieprzyk claim a 2^100-ish 
attack against AES.  They claim a 2^200-ish attack against Serpent.  This 
is an enormously big deal.

Assuming that it's real.

We are in the era of completely theoretical cryptanalysis.  Cipher key 
lengths have gotten so long that attacks simply can't be implemented; their 
complexity is just too great.  But implementation is critical; some attacks 
have hidden problems when you try them out, and other attacks are more 
efficient than predicted.  You can try the attack on simplified versions of 
the cipher -- fewer rounds, smaller block size -- but you can never be sure 
the attack scales as predicted.  Differential cryptanalysis was developed 
this way; the attack was demonstrated on simpler variants of DES and then 
extrapolated to the full DES.  (I don't believe that the attack has ever 
been implemented on the full DES.)  Many of the attacks we use to break 
algorithms -- linear, boomerang, slide, mod n, etc. -- are more often 
mathematical arguments than computer demonstrations.  I don't believe that 
we will learn in our lifetimes whether the 2^100 attack on AES really works 
or not.  And we need a lot more analysis and testing of the general XSL 
technique, on weaker algorithms and simplified variants of real algorithms.

So we're in a quandary.  We might have an amazing new cryptanalytic 
technique, but we don't know if there's an error in the analysis, and 
there's no way to test the technique empirically.  We have to wait until 
others go over the same work.  And to be sure, we have to wait until 
someone improves the attack to a practical point before we know if the 
algorithm was broken to begin with.

In any case, there's no cause for alarm yet.  These attacks can be no more 
implemented in the field than they can be tested in a lab.  No AES (or 
Serpent) traffic can be decrypted using these techniques.  No 
communications are at risk.  No products need to be recalled.  There's so 
much security margin in these ciphers that the attacks are irrelevant.

But there is call for worry.  If the attack really works, it can only get 
better.  My fear is that we could see optimizations of the XSL attack 
breaking AES with a 2^80-ish complexity, in which case things starts to get 
dicey about ten years from now.  That's the problem with theoretical 
cryptanalysis: we learn whether or not an attack works at the same time we 
learn whether or not we're at risk.

The work is fascinating.  During the AES process, everyone agreed that 
Rijndael was the risky choice, Serpent was the conservative choice, and 
Twofish was in the middle.  To have Serpent be the first to fall (albeit 
marginally), and to have Rijndael fall so far so quickly, is something no 
one predicted.  But it's how cryptography works.  The community develops a 
series of algorithms for which there are no known attacks, and then new 
attack tools come out of the blue and strike a few of them down.  We all 
scramble, and then the cycle repeats.

We're starting to see the new attack tools that work against some of the 
AES finalists.  It's an open question as to how long the tools will remain 
theoretical.  But many cryptographers who previously felt good about AES 
are having second thoughts.


Summary of recent AES results:
<http://www.cryptosystem.net/aes/>

Preliminary version of the Courtois and Pieprzyk paper (final to be 
presented at Asiacrypt 2002):

<http://eprint.iacr.org/2002/044/>

Fuller and Millan Paper
:
<http://eprint.iacr.org/2002/111/>

Filiol paper:

<http://eprint.iacr.org/2002/099/>

Murphy and Robshaw paper:

<http://www.isg.rhul.ac.uk/~mrobshaw/aes-crypto.pdf>

Rijndael analysis by the Twofish team from May 2000:

<http://www.counterpane.com/rijndael.html>

One effect of theoretical cryptanalysis is inconsistent standards for 
papers.  Courtois and Pieprzyk submitted their paper to Crypto 2002, as did 
Murphy and Robshaw.  For some reason, the latter was accepted and the 
former wasn't.  In any case, the Courtois and Pieprzyk paper will appear at 
Asiacrypt later this year.
[...]




-------------------------------------------------------------------------
POLITECH -- Declan McCullagh's politics and technology mailing list
You may redistribute this message freely if you include this notice.
To subscribe to Politech: http://www.politechbot.com/info/subscribe.html
This message is archived at http://www.politechbot.com/
Declan McCullagh's photographs are at http://www.mccullagh.org/
-------------------------------------------------------------------------
Like Politech? Make a donation here: http://www.politechbot.com/donate/
Recent CNET News.com articles: http://news.search.com/search?q=declan
CNET Radio 9:40 am ET weekdays: http://cnet.com/broadband/0-7227152.html
-------------------------------------------------------------------------