SHA-1 cracked

Jim McCoy mccoy at mad-scientist.com
Thu Feb 17 16:04:49 EST 2005


On Feb 16, 2005, at 9:15 PM, Joseph Ashwood wrote:

> ----- Original Message ----- From: "Steven M. Bellovin" 
> <smb at cs.columbia.edu>
> Subject: SHA-1 cracked
>
>> It's probably not a practical
>> threat today, since it takes 2^69 operations to do it
>
> I will argue that the threat is realizable today, and highly practical.

I would have to reply that you would be wrong.

>  It is well documented that in 1998 RSA Security's DES Challenge II 
> was broken in 72 hours by $250,000 worth of custom machine.

The DES challenge had an upper limit of 2^56, so attacking a 2^69 space 
would take you 16 years instead of 3 days (the three day break was not 
an exhaustive search either, but I will give you the benefit of the 
doubt and say that you will get as lucky as the people going after the 
DES Challenge were...)  This also assumes that a hardware attack on 
SHA1 is equivalent to an exhaustive keysearch of DES.  This is not the 
case.  SHA1 is fast in hardware, but not as fast as DES.  While you can 
speed things up for a FPGA attack using various tricks to make internal 
steps run in parallel, the numerous multiply operations in SHA1 are 
painful for a FPGA implementation, unlike the shifts and additions that 
are more common in DES.  This also assumes that the known hardware 
speed-ups for SHA1 will also apply to the attack vector recently 
revealed, which I am unable to make a guess at.

While I think that the recent results do not bode well for the future 
of the SHA line of hashes, your claims that the sky is falling (e.g. 
"you are looking at minutes if not seconds before break") are simply 
not supported by known facts.

Jim


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



More information about the cryptography mailing list