[16942] in cryptography@c2.net mail archive
Re: SHA-1 cracked
daemon@ATHENA.MIT.EDU (Jim McCoy)
Tue Feb 22 11:40:32 2005
X-Original-To: cryptography@metzdowd.com
X-Original-To: cryptography@metzdowd.com
In-Reply-To: <BAY0-SMTP038D706C93044C14B21139AC6D0@phx.gbl>
Cc: Joseph Ashwood <ashwood@msn.com>
From: Jim McCoy <mccoy@mad-scientist.com>
Date: Thu, 17 Feb 2005 13:04:49 -0800
To: cryptography@metzdowd.com
On Feb 16, 2005, at 9:15 PM, Joseph Ashwood wrote:
> ----- Original Message ----- From: "Steven M. Bellovin"
> <smb@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@metzdowd.com
