80-bit security? (Was: Re: SHA-1 collisions now at 2^{52}?)

[Brandon Enright]

On Wed, 6 May 2009 20:54:34 -0400
"Steven M. Bellovin" <smb at cs.columbia.edu> wrote:

> On Thu, 30 Apr 2009 17:44:53 -0700
> Jon Callas <jon at callas.org> wrote:
> 
> > The accepted wisdom
> > on 80-bit security (which includes SHA-1, 1024-bit RSA and DSA keys,
> > and other things) is that it is to be retired by the end of 2010. 
> 
> That's an interesting statement from a historical perspective -- is it
> true?  And what does that say about our ability to predict the future,
> and hence to make reasonable decisions on key length?
> 
> See, for example, the 1996 report on key lengths, by Blaze, Diffie,
> Rivest, Schneier, Shimomura, Thompson, and Wiener, available at
> http://www.schneier.com/paper-keylength.html -- was it right?
> 

On breaking DES the paper says:

"As explained above, 40-bit encryption provides inadequate
protection against even the most casual of intruders, content to
scavenge time on idle machines or to spend a few hundred dollars.
Against such opponents, using DES with a 56-bit key will provide a
substantial measure of security. At present, it would take a year
and a half for someone using $10,000 worth of FPGA technology to
search out a DES key. In ten years time an investment of this size
would allow one to a DES key in less than a week."


This is surprising accurate.  As Sandy Harris pointed out,
http://www.copacobana.org/ is selling about $10k worth of FPGA
technology to crack DES in about 6.4 days:

"With further optimization of our implementation, we could achieve a
clock frequency of 136MHz for the brute fore attack with COPACOBANA.
Now, the average search time for a single DES key is less than a week,
precisely 6.4 days. The worst case for the search has been reduced to
12.8 days now."


Now, even assuming 64 bits is within reach of modern computing power, I
still think it is naive to assume that computing power will continue to
grow to 80 or more bits any time soon.  The energy requirements for
cycling a 80 bit counter are significant.  We are likely to get to a
point where the question is not "how parallel a machine can you afford
to build?" but rather "how much heat can you afford to dissipate?".

Brandon

---------------------------------------------------------------------
The Cryptography Mailing List
Unsubscribe by sending "unsubscribe cryptography" to majordomo at metzdowd.com