Re: Comparing Cryptographic Key Sizes

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

Adam Back <aba@dcs.ex.ac.uk> writes.

> Below is a explanation of the meaning of cryptographic key sizes which
> started as an explanation I wrote for a journalist friend of mine, on
> being asked about how relatively secure a system using DES and RSA
> (SET) was as compared to netscapes export version of SSL.
 
> It could use some criticism.  If you are not that crypto aware, does
> it make sense to you?  If you are crypto aware, what do you think of
> my off the cuff estimates of hardness?
> 
> 
> 56 bit DES is probably roughly similar to 512 bit RSA in hardness to
> break.

This is way off. We used ~457,000 MIPS years to search half of the 
DES keyspace. Factoring a 512 bit modulus using the General Number
Field Sieve (GNFS) would take about 28,000 MIPS years (see Schneier
for the exact number - I don't have AC2 at hand)

Lenstra has estimated that with 500,000 MIPS years, you should be
able to factor a 600 bit modulus using GNFS, if your workstations 
had enough memory.

[...]

> About 10 years ago now Michael Wiener made a design for such a DES
> breaking machine.  He estimated it would cost $10,000,000 to build a
> machine which would break a 56 bit DES encrypted message a few hours.
> His machine was scalable, pay more money, break the key faster, pay
> less take longer.  The estimate was that could build one with enough
> DES key searching units to break it in a day for $1,000,000.  That was
> 10 years ago.  10 years is a long time in the computer industry.
> Nowadays you build the machine more cheaply as chip technology has
> progressed, and computers are much faster per $.  Estimates are around
> $100,000 to build the machine (neglecting hardware engineers
> consultancy fees).

Go back and check the numbers - if you don't the journalists will. 
(I don't have this paper to hand either :-( ) The Wiener paper is 
much more recent (93?) , and the cost much lower (I think it was 
about $1M for HW and $500K for development costs, for a 3.5 hour 
machine).

Peter Trei
trei@process.com