SHA-1 collisions now at 2^{52}?

[Eric Rescorla]

At Sat, 2 May 2009 15:00:36 -0400,
Matt Blaze wrote:
> The serious concern here seems to me not to be that this particular
> weakness is a last straw wedge that enables some practical attack
> against some particular protocol -- maybe it is and maybe it isn't.
> What worries me is that SHA-1 has been demonstrated to not have a
> property -- infeasible to find collisions -- that protocol designers
> might have relied on it for.
> 
> Security proofs become invalid when an underlying assumption is
> shown to be invalid, which is what has happened here to many
> fielded protocols that use SHA-1. Some of these protocols may well
> still be secure in practice even under degraded assumptions, but to
> find out, we'd have to analyze them again.  And that's a non-trivial
> task that as far as I know has not been done yet (perhaps I'm wrong
> and it has).  "They'll never figure out how to exploit it" is not,
> sadly, a security proof.

Without suggesting that collision-resistance isn't an important property,
I'd observe that we don't have anything like a reduction proof of
full TLS, or, AFAIK, any of the major security protocols in production
use. Really, we don't even have a good analysis of the implications
of relaxing any of the (soft) assumptions people have made about
the security of various primitives (though see [1] and [2] for some
handwaving analysis).

It's not clear this should make you feel any better when a primitive is
weakened, but then you probably shouldn't have felt that great to start
with.

-Ekr



[1] http://www.rtfm.com/dimacs.pdf 
[2] http://www.cs.columbia.edu/~smb/papers/new-hash.pdf


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