Thank you! (what next?)

Peter Trei (trei@process.com)
Thu, 19 Jun 1997 11:51:11 -6


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.