RE: Brute Force DES

[Matt Thomlinson <mattt@microsoft.com>]

why not put together (a LOT of) disk space and we can build a table
(read: "a cryptanalytic time-memory tradeoff") for cracking DES? Using
the table, we could brute-search the DES keyspace in less time than it
would take to do an exhaustive search of a 38 bit keyspace, according to
the paper. 4 gigs is what, a couple of hundred nowadays?

Making DES equivalent to a 40-bit crack would take approx. 500Gig, but
publishing the table would push DES out usefulness. Certainly we could
scale back (make DES equivalent to a 45-bit crack?) if we don't have
enough disk...

mattt

>----------
>From: 	Peter Trei[SMTP:trei@process.com]
>Sent: 	Monday, July 22, 1996 9:55 AM
>To: 	frissell@panix.com; cypherpunks@toad.com; trei@process.com
>Subject: 	Re: Brute Force DES
>
>> Peter wrote:
>> >Any one up for a distributed brute force attack on single DES? My 
>> >back-of-the-envelope calculations and guesstimates put this on the
>> >hairy edge of doability (the critical factor is how many machines can
>> >be recruited - a non-trivial cash prize would help). 
>
>Duncan wrote: 
>> I volunteer my 120 MHZ Pentium.  A lot more Pentiums are out there now than
>> a year ago.  That makes it more feasible.  A lot more people with full net
>> connections.  Like most Americans, I have a flat rate net connection and a
>> flat rate local phone connection so could run a cracking session
>>permanently
>> (as long as no one tells my ISP).  We need a full test of the Winsock
>> cracking client in any case.  It wasn't working very well last time.
>> 
>> DCF
>
><back-of-envelope>
>
>In my terminology, 'hairy edge of doability" means we have a shot
>at success, but I wouldn't bet the farm on it.
>
>I thought that I might bet a couple hundred bucks, though.
>
>Sadly, after further calculation, I'm not so sure if it's doable just yet.
>
>What I'm looking at is a known plaintext attack on single ECB DES, 
>using a brute-force test to cycle through the key space. People 
>would get chunks of keyspace to test from a central server or 
>servers, and would be motivated to take part by a cash prize for
>the lucky person who finds the key.
>
>Lets do  the numbers:
>
>Single DES has the security of 56 bits of key - there are 64 bits in the
>keys, but 8 of them are parity bits which add nothing to security.
>
>2^56  = 7.205e16 keys (which is a whopping big number)
>
>Let's guess that we can recruit the equivalent of full-time on 1000
>machines.
>
>7.205e13 keys/machine.
>
>Let's guess that we have about a month before people start to lose 
>interest - so we want to be more than 1/2 done by then. Lets say
>we want to sweep the whole space in 40 days.
>
>1.8e12 keys/machine/day 
>
>~21,000,000 keys/machine/second
>
>The fastest general purpose, freely available des implementation I'm
>aware of is libdes. by Eric Young. With this, I can do a set_key in 
>15.8 us, and an ecb_encrypt in 95 us/block. That adds up to 
>about 9,000 keytests/sec (this is on a 90 MHz P5, running NT).
>
>I'm looking at ideas to speed up DES - if I'm willing to use
>honking great lookup tables, the permutation steps  can be done 
>more quickly than libdes. I'm also looking at implementing the
>algolrithm in hand-optimized P5 assembler.  (It's been years since
>I've done a major assembler project - the P5 has some truely weird
>features to be considered, but also has (some) internal 64 bit
>registers to play with).
>
>Let's guess that I can speed up a key-test up by a factor of 10. (This is
>not a slur on Eric's code - it's extremely clever, but not optimized
>for any particular processor, or for key-testing.  Note that the keytest 
>described above takes about 10,000 cycles/test.)
>
>That gets my workstation up to about 90,000 keys a second, which is
>still almost a factor of 250 too slow. 
>
>I'm going ahead with my work on a faster DES keytester, but unless
>optimizing gives an astounding win, I now think a distributed bruting 
>effort is a bit pre-mature.
>
>What will make this brute doable, if not now, then in the near future?
>
>1. Faster Processors - Moore's Law is still holding. A year ago, my
>90 MHz Pentium was one of the faster machines taking part in the
>40-bit RC4 crack. Now, it's passe.
>
>2. More processors. The number of people on the internet continues
>to grow rapidly.
>
>3. More interest - Crypto awareness has greatly increased in the
>last year, and a real cash prize (say, over $500) will generate both
>publicity and interest.
>
>These factors all multiply together. The number of cycles that could
>probably be recruited is increasing at a fast rate. A major part of the
>work will be a keyspace distribution mechanism which can handle
>the load (this was a major stumbling block last year). 
>
></back-of-envelope>
>
>Peter Trei
>trei@process.com
>
>Disclaimer: This has nothing to do with my employer.
>