DES: Thank you!

["Peter Trei" <trei@process.com>]

     Well Done!

     My congratulations go out to Rocke Verser, Mike Sanders, 
and all of the other people who developed code and/or ran
clients for the DES challenge. The crack comes roughly at the
time I predicted when I first proposed the challenge, and
at a very opportune moment to influence action in the US
Congress.

     I first proposed the challenge on Oct 1, 1996, in a posting 
to the cypherpunks mailing list: "Can we kill single DES?". Later 
that month, at the suggestion of Ron Rivest, I approached Jim 
Bidzos of RSA Data Security Inc. with the idea. From the start, 
RSA was enthusiastic, and sponsored the challenge to the tune of 
$10,000.

     I wrote some of the earliest key search routines, and
invented a technique to reduce the key schedule generation
from 80% of the total work to less than 5% - a technique which
was universally adopted by key search engine writers.

     I and others also worked on the other major part - the DES 
round. My initial version was substantially faster than any
previously existing Intel version, but later  Sven Mikkelsen of
Danemark found substantial improvements over my code.

     Sven, Rocke, and others also invented techniques to speed up
the search by reducing the number of DES rounds which needed to
be performed; I had reduced the original 16 to 14, but they got
it down to under 12.

     The upshot of this was that searching for keys became faster
than straightforward encryption or decryption with a single key.

---------------------------
What does this tell us?
What do we tell the public?
---------------------------

Single DES can be cracked for under $10,000. Any system 
in which a single DES key protects more than $10,000 in assets 
is inadequate. Thus, one $10,000 message, or even 10 bank
cards with $1000 in their accounts, becomes a tempting target 
(some banking systems use the same DES key for many cards). 

Future cracks can only get faster. Processor speeds continue
to climb, and the number of available computers increases
similarly; thus, the number of available cycles more than
doubles every year - and the cost of a cracked key halves.

This was probably the *least* efficient way to crack DES;
Wiener and others have shown that machines can be built that
will crack DES far faster and cheaper, but the method used
won because it used existing resources, with no significant
upfront development costs.

No enterprise which wishes to use or offer security should 
consider single DES from this point on. If this crack does
anything, it demonstrates that the US Government's offers
to permit the export of single DES are worthless. 

Even without formal organization, distributed computing on
the Internet can muster awesome cpu power - I estimate about
half a million MIP years were used (see below).

-------------------------------
How much cpu was actually used?
-------------------------------

The following is a very rough calculation, there are lots of 
assumptions.

1. DESChall searched 25% of the keyspace - other efforts got
about the same, so we checked roughly 2^55 keys

2. I'm assuming that most search engines used roughly the same
number of operations per key checked, regardless of processor. 
64 bit machines could do better, especially with bitslice 
algorithms.

3. The Pentium code is highly optimized, and thus is executing
roughly 2 instructions per clock cycle.

Lets do the numbers.

from the DESChall benchmark page:

Dual Pentium 200 MHz ......... 2.003M keys per second 

= 200MHz is roughly 400MIPs, due to Pentium's dual pipelines.

-> 1 Mkey/sec = 400 MIPs, or roughly 400 instructions per key.
   (this sounds about right, from my own DES Intel assembly work).

2^55 keys = 3.6*10^16 keys
* 400 = 1.44*10^19 instructions
= 1.44*10^13 million instructions.

= 457,000 MIP years used in the calculation.

Lenstra has stated that, in the factorization of RSA-130:

"we would have spent about 500 mips years (i.e., 10% of the 
computing time spent on the 129-digit QS-record) if we had 
done all the sieving on average workstations with at least 
24 megabytes of memory" 
(from http://enigma.ncsa.uiuc.edu/~dun/rsa-130.shtml)

This suggests that cracking DES used roughly 2 orders of
magnitude (ie, 100x ) more CPU than RSA-129, which I suspect
makes it a record for the largest calculation ever performed.

----------
What next?
----------

Two targets suggest themselves:

1. 56 bit RC5.
2. RSA 135


1. 56 bit RC5.

The earlier efforts on 40 and 48 bit RC5 suggest that keysearch
for RC5 is substantially slower than DES - perhaps 5-10 x slower. 
It's probable that the clients have not been fully optimized.
RSA has another $10,000 prize for this crack.

2. RSA 135 

We used about 1000x the cpu needed for the RSA 130 factorization.
I'm not sure how the best current factorization systems scale
with the modulus size (Rivest, Lenstra?) but I suspect that it's
less than linear. If this is so, then RSA 135 may be doable. RSA135
is roughly comparable to a 448 bit key. RSA also has a prize for
this factorization.

Peter Trei
trei@process.com

DISCLAIMER: The above represents my opinions only, not neccesarily
those of my employer.