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.