[pmmail-list] Message hoses v.2657
Allan McLane
pmmail-list@blueprintsoftwareworks.com
Mon, 16 Sep 2002 08:23:35 -0400
Follows is the full message with header that hoses v.2657.
While retrieving this message PMMail causes W2K to totally bog down and I can't even get the task-manager to come up to see what resources PMMail is using. I have to power-down the machine to regain control ;[.
System here is PMMail 2000 Professional (2.20.2657) For Windows 2000 (5.0.2195;3)
When I looked at this message with pine I got an error message stating something like "NEWLINE command undefined" (but I didn't save the error text exactly).
Other messages from this maillist are received just fine...
HTH
--allan
Here is the complete offending-message text:
=========clip=============
Return-Path: <owner-politech@politechbot.com>
Received: from mailgate2.sover.net (mailgate2.sover.net [209.198.87.64])
by mailhub0.sover.net (8.11.6/8.11.6) with ESMTP id g8G7hc022335;
Mon, 16 Sep 2002 03:43:38 -0400 (EDT)
Received: from cluebot.com (server1.cluebot.com [216.110.36.217])
by mailgate2.sover.net (8.11.6/8.11.6) with ESMTP id g8G7hbL21286;
Mon, 16 Sep 2002 03:43:37 -0400 (EDT)
Received: by cluebot.com (Postfix)
id 8184C104FE; Mon, 16 Sep 2002 02:52:06 -0400 (EDT)
Received: by cluebot.com (Postfix, from userid 91)
id E17E110534; Mon, 16 Sep 2002 02:51:58 -0400 (EDT)
Message-Id: <5.1.1.6.0.20020916010931.01af7158@mail.well.com>
X-Sender: declan@mail.well.com
X-Mailer: QUALCOMM Windows Eudora Version 5.1.1
Date: Mon, 16 Sep 2002 01:10:37 -0400
To: politech@politechbot.com
From: Declan McCullagh <declan@well.com>
Subject: FC: Bruce Schneier on possible weaknesses in encryption systems
Mime-Version: 1.0
Content-Type: text/plain; charset="us-ascii"; format=flowed
Sender: owner-politech@politechbot.com
Precedence: normal
Reply-To: declan@well.com
X-URL: Politech is at http://www.politechbot.com/
X-Author: Declan McCullagh is at http://www.mccullagh.org/
X-News-Site: Cluebot is at http://www.cluebot.com/
X-Spam-Status: No, hits=-100.0 required=6.0 tests=USER_IN_WHITELIST version=2.11
---
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
-------------------------------------------------------------------------
==================end clip==================
- pmmail-list - The PMMail Discussion List ---------------------------
To POST to the list, send your message to:
pmmail-list@blueprintsoftwareworks.com
To UNSUBSCRIBE, send a message to mdaemon@bmtmicro.com
with the first line of the message body being...
UNSUBSCRIBE pmmail-list@blueprintsoftwareworks.com
---------------------------------------------------------------------