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

[Paul Hoffman]

At 8:54 PM -0400 5/6/09, Steven M. Bellovin 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? 

That's an oddly-worded question.

It is true that NIST has specified that algorithms with 80 bits of effective strength should stop being used in US government systems after the end of 2010.

It is not true that the accepted wisdom is 80-bit crypto "is to be retired" by the end of 2010.

It is true that some uses of SHA-1 have 80 (now many fewer) bits of effective strength.

It is not true that SHA-1 gives 80-bit security; many uses of a hash rely on the preimage resistance, not the collision resistance.

It may be true that 1024-bit RSA and DSA gives 80 bits of effective strength, and it is true that this is the accepted wisdom. This is based on some wild hand-waving and scaling assumptions with very few data points, and particularly few in the past five years since that number became oft-repeated accepted wisdom.

>And what does that say about our ability to predict the future,
>and hence to make reasonable decisions on key length?

Bupkis. The best asymmetric attack published so far is about 700 bits. No one has produced a SHA-1 collision at 62 bits of effort (the previous estimated work). Our ability to extrapolate work effort to 80 bits is questionable indeed.

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

How could we tell? The whole point of the paper was estimating the strength needed to keep a secret *for a long time*. We are only 13 years into the 20 years that they used as a basis for the estimate of 90 bits.

>In 1993, Brickell, Denning, Kent, Maher, and Tuchman's interim report
>on Skipjack (I don't believe there was ever a final report) stated that
>Skipjack (an 80-bit cipher) was likely to be secure for 30-40 years.
>Was it right?

Asking that question six years into the 30 years (if those were the numbers they used) is begging to make approximations on insufficient data.

>The problem with SHA-1 is not its 80-bit security, but rather that it's
>not that strong.

That's one problem. Another is that because it can also be used in environments where 160ish bits of security are needed and it's still believed to be fine there, people on this list and in the press are sloppy when they speak about its use. Another is that people on this list and in the press are sloppy about security decisions that involve periods of time longer than about a year.

--Paul Hoffman, Director
--VPN Consortium

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