SHA-1 cracked

[Greg Rose]

At 22:33 2005-02-16 +0000, Ian G wrote:
>Steven M. Bellovin wrote:
>
>>According to Bruce Schneier's blog 
>>(http://www.schneier.com/blog/archives/2005/02/sha1_broken.html), a team 
>>has found collisions in full SHA-1.  It's probably not a practical threat 
>>today, since it takes 2^69 operations to do it and we haven't heard 
>>claims that NSA et al. have built massively parallel hash function 
>>collision finders, but it's an impressive achievement nevertheless -- 
>>especially since it comes just a week after NIST stated that there were 
>>no successful attacks on SHA-1.
>>
>
>Stefan Brands just posted on my blog (and I saw
>reference to this in other blogs, posted anon)
>saying that "it seems that Schneier forgot to
>mention that the paper has a footnote which
>says that the attack on full SHA-1 only works
>if some padding (which SHA-1 requires) is not
>done."
>
>http://www.financialcryptography.com/mt/archives/000355.html

No, that's not what it says. It says that "Note that padding rules were not 
applied to the message." This is exactly the same as the previous breaks; 
it just means that the collision appears in the chaining output... if you 
just append anything at all to the end of the texts, and pad it correctly, 
you will have valid SHA-1 hashes. Nothing different here than from the 
MD4/MD5/SHA-0 breaks.

Since I'm typing anyway, I'll also reply to Joseph Ashwood's earlier mail, 
in which he said:
>[...] SHA-1 showing big cracks, the entire SHA series is in doubt, and 
>needs to be heavily reconsidered, [...]

If you look at Phil Hawkes' paper <http://eprint.iacr.org/2004/207.pdf>, 
you will see that the SHA-2s are very different algorithms, and my own 
opinion is that the data-expansion part of the algorithm is *seriously* 
beefed up. My guess is that the NSA were already worried about this kind of 
attack (whether they'd found it or not). We don't have a good analysis of 
the data-expansion part, but I'm pretty sure that it'll defeat the Wang 
attacks.

Greg.

Greg Rose                                    INTERNET: ggr at qualcomm.com
Qualcomm Incorporated     VOICE: +1-858-651-5733   FAX: +1-858-651-5766
5775 Morehouse Drive                    http://people.qualcomm.com/ggr/
San Diego, CA 92121   232B EC8F 44C6 C853 D68F E107 E6BF CD2F 1081 A37C


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