Re: Comparing Cryptographic Key Sizes

[Adam Back <aba@dcs.ex.ac.uk>]

Peter Trei <trei@process.com> writes:
> Adam Back <aba@dcs.ex.ac.uk> writes.
> > 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.

Ah yes.  Well I did read your post on coderpunks where you described
the results of asking Lenstra and looking for ideas for what to break
next, how hard 512 bits was etc.

So... 28,000 MIPs years you say... but that neglects memory.
Lenstra's conclusion was that even 512 bits couldn't be done, from
your post.  So by that measure it is harder (due to memory overhead)
than DES even though theoretically taking less MIPS with 64 mb
workstations.  Also he was unsure about the availability of a large
enough supercomputer to reduce the final matrix.

So any suggestetions of how to summarise the "hardness" of a problem
when it includes memory and cpu costs in as simple terms as possible.
(Bearing in mind the reader in most cases hasn't grasped the
difference between public key crypto and symmetric key, and is
comparing 1024 bit keys to 56 bit keys and probably thinks that it is
1024/56 times harder.)

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

I think I have his paper as a postscript file, will look.

But what do you think of the extrapolation to todays prices?  $100k?
(Ignoring consultancy fees).

Thanks for the criticisms, more please on readability and
understandability to neophytes!

Adam
-- 
Have *you* exported RSA today? --> http://www.dcs.ex.ac.uk/~aba/rsa/

print pack"C*",split/\D+/,`echo "16iII*o\U@{$/=$z;[(pop,pop,unpack"H*",<>
)]}\EsMsKsN0[lN*1lK[d2%Sa2/d0<X+d*lMLa^*lN%0]dsXx++lMlN/dsM0<J]dsJxp"|dc`