Thoughts on the demise of DES
Well, I'm a happy camper. Single DES is dead as a credible cipher. I feel *very* vindicated. I called for the hit, RSA bankrolled it, and the EFF pulled the trigger. DESChall and Distributed.net did severe damage, but the Deep Crack machine was the fatal blow. While the possiblity of bruting DES has been discussed at various times in and out of cpunks for years (for example, see Adam Back's message of 17 August 1995), my involvement started 22 July 1996, when I proposed a DES crack as a follow on to the previous autumn's RC4-40 attack: ------------------------------
Peter Trei trei@process.com
This got a flurry of responses, mostly positive, including some in which Matt Blaze announced his intention to build a hardware DES cracker. ----------- Later that day, I had run some more numbers:
[...] --------------- This looked much too slow, and discussion trailed off. I was still interested, and grabbed some x386 assembler by Phil Karn, and worked on optimizing it for the Pentium. It worked well. A few months later: http://infinity.nus.edu.sg/cypherpunks/dir.96.09.26-96.10.02/msg00567.html
I had managed a better than 25x speedup. My biggest innovation was a new method of producing key schedules, which when applied for key search purposes was a hundred times faster than the canonical method [Perry doubled the speed by suggesting the use of Gray codes.] Later that month, I wrote to Jim Bidzos at RSA, suggesting a DES challenge, using my prototype's speed to demonstrate feasibility. He was interested, and the Symmetric Key Challenges were born. Soon other programmers (notably Svend Mikkelsen in Dennmark) substantially improved on my speed - by better optimization, and by clever shortcuts which allowed earlier rejection of bad keys. A major innovation was use of Eli Biham's 'bitslice' algorithm, which tested large blocks of keys in parallel. The speed of his initial implementation was doubled by the work of Matthew Kwan in Australia and Andrew Meggs, et. al. at distributed.net. By the end of the latest challenge, the fastest software search engines had speeds (in clock cycles per test) well over 100x as fast as my original 10,000 cycle/key estimate. Here's one more quote from the archives:
Written well before I started to think about a DES crack, this, at least, has come true. Peter Trei ptrei@securitydynamics.com Disclaimer: This has nothing to do with my work at my employer.
participants (1)
-
Trei, Peter