Re: Brute Force DES

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

> 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.