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

[Sandy Harris]

On Fri, May 8, 2009 at 10:28 AM, Brandon Enright <bmenrigh at ucsd.edu> wrote:

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

It was a best guess by a group of clever and well-informed people.
There's no way to tell if it was precisely right, but there's no way
to get a better estimate either, short of getting a similar group to
re-do the work today.

A back-of-the envelope approximation to today's requirements
can be had by saying Moore's Law gives twice the computer
speed every 18 months, so ciphers needs one more key bit
every 18months to keep up. They said minimum 75 bits to
keep an existing cipher in service, minimum 90 for any new
ones, as of 1996. Add 10 bits to each for a rough estimate
as of 2011.

> Now, even assuming 64 bits is within reach of modern
> computing power, ...

I'd have thought that was obvious, and had been for a
decade or so. EFF broke DES in a few days for
$200,000 ten years ago. A 64-bit cipher is only
256 times harder, easily within reach on an
intelligence agency budget.

Copacobana break DES in a week for 9,000 euro.
256 of them would break a 64-bit cipher in a
week. This is within reach for a high-stakes
industrial espionage situation, say Boeing
and Airbus competing for big orders.

-- 
Sandy Harris,
Quanzhou, Fujian, China

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