[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

Re: Breaking 40-bit DES

Hi, everyone,


The DES numbers I posted were very preliminary,
and unfortunately there was an error in my calculation
(factor of 2 over). (I was doing ballpark estimation).

> I'm afraid it's a simple matter of arithmetic.
> 
> Let's look at Joe Touch's performance numbers.  He got DES speeds
> ranging from 20-37 Mbps.  To make the arithmetic easy, let's just say
> 32 Mbps.  At 64 bits per block, that's .5 M encryptions/second, or 2
> microseconds per encryption.  To exhaustively search a 40-bit key
> space, we need to do about 10^12 operations.  Assume that the key setup
> overhead for an exportable cipher is about 5 DES operations (and that's
> an overestimate, in my opinion), or 10^-5 seconds.  That means that a
> single processor could search the key space in 10^7 seconds.  Run
> this in parallel on 100 idle machines (or hacked machines on a LAN),
> and you're done in 10^5 seconds.  That's a bit over one day.
> 
> Note that the only real assumption in this analysis is how long it takes to
> do one key setup+encryption operation.  Even if I'm off by a factor of
> 10, it still gives you no privacy protection, though arguably it's
> safe for now for authentication, since few sessions last 11.5 days.
> 
> 
> 		--Steve Bellovin

Here are more precise measurements (no variance - just one-shot):

DESCORE:
                encry   BW      key time
        10/51   5us     12.8    58us
        20/61   4us     16      49us
        20/71   3.1us   20.6    38us

LIBDES:
        10/51   9.9us   6.4     17.3us
        20/61   8.3us   7.7     14.2us
        20/71   6.5us   9.8     14.2us

So, if you are doing encryption, I'd say 20-30 Mbps is still realistic
(include Alphas and Pentiums, etc).

As to the key time, it depends on what you use, (above).
If you want a single set key and then a single encrypt, the best
thing to use is LIBDES. 

Steve's estimate of 5x for key setup (vs. encrypt block) is
emperically very accurate, but note that the above varies widely.

Searching the key space could be done in 14.2us each, which
is right in line with his estimate of 10us (even though *my* math
was the one whose was off... :-)

Joe