SHA1 broken?

[David Shaw]

On Wed, Feb 16, 2005 at 11:13:23AM -0500, Atom Smasher wrote:
> On Wed, 16 Feb 2005, David Shaw wrote:
> 
> > In terms of GnuPG: it's up to you whether you want to switch hashes or 
> > not.  GnuPG supports all of the SHA-2 hashes, so they are at least 
> > available.  Be careful you don't run up against compatibility problems: 
> > PGP doesn't support 384 or 512, and only recently started supporting 
> > 256.  GnuPG before 1.2.2 (2003-05-01), doesn't have any of the new 
> > hashes.  Finally, if you have a DSA signing key (most people do) you are 
> > required to use either SHA-1 or RIPEMD/160.  RSA signing keys can use 
> > any hash.
> ====================
> 
> there's more to it than that. openPGP specifies SHA-1 (and nothing else) 
> as the hash used to generate key fingerprints, and is what key IDs are 
> derived from.
> 
> a real threat if this can be extended into a practical attack is 
> substituting a key with a *different* key having the same ID and 
> fingerprint. it would be difficult for average users (and impossible for 
> the current openPGP infrastructure) to tell bob's key from mallory's key 
> that claims to be bob's.
> 
> it can also be used (if the attack becomes practical) to forge key 
> signatures. mallory can create a bogus key and "sign" it with anyone's 
> real key. this would turn the web of trust into dust.

If you presuppose a workable attack you can conjecture any result you
like.  Let's not go off the deep end here.

Skipping completely over the point that the paper has not been
published yet so it can be checked over by the cryptographic
community, let's assume that they have indeed done what they claim to
have done: demonstrated they can find a collision in 2^69 instead of
2^80 operations.  A collision attack.  Not a preimage attack.  And
it's not workable in practice.  How many entities have the ability to
do 2^69 operations in a sane amount of time?

Without more information, it looks to me like we are now in the
position we were in with MD5 several years ago.  It's not broken in
practical terms yet.  Attacks don't get worse over time, of course, so
we need to start moving to something better.  SHA-1 was already being
phased out:
http://www.fcw.com/fcw/articles/2005/0207/web-hash-02-07-05.asp

To be sure, this is bad, but the sky isn't falling yet.

David