SHA-1 is teh broke

Senior year, Nate (and possibly myself… I remember being involved somehow, but I’m not sure how) did some proof-of-concept work regarding hashing algorithms and large data sets (namely Nate’s mp3 collection). He/We found that SHA-1 hiccupped several times, giving the same hash for different files. I think we left it at that.

It turns out that we were absolutely right, and that SHA-1 not only collides, it collides predictably. Thus, it’s pointless for use in digital signatures and the like. Granted, we didn’t take it this far, but it’s still nice to know that we were indeed barking up the right tree.

  1. Sometimes I wish we had taken that a bit farther. I keep hearing these reports that say that nobody’s ever demonstrated a SHA-1 (or even MD5) collision. We generated a bunch of them!

  2. I’m still very skeptical of your methodology on that one. The new attack only shows that instead of the 2^80 theoretical complexity of an attack you have 2^69. If you got collisions by just taking a mediumish data set and hashing it it would have been noticed way before this, and would be a lot more serious than what they’re talking about. Of course, the thing everyone should be worried about is that PKI hence SSL is all built on SHA-1. Anyway, the real concern is that this is a stepping off point for better attacks – at the current moment it doesn’t look like the end of the world. Of course, maybe NSA has known about this for years …

Leave a Comment

NOTE - You can use these HTML tags and attributes:
<a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <s> <strike> <strong>