« Terry Gross channels Gregg Easterbrook | Main | Cerf and Kahn win Turing award »
February 15, 2005
The news gets worse for SHA-1
Bruce Schneier is reporting that the Wang, Yin, Yu team has reduced the difficulty of finding collisons in SHA-1 to 269 operations:
- collisions in the the full SHA-1 in 2**69 hash operations, much less than the brute-force attack of 2**80 operations based on the hash length.
- collisions in SHA-0 in 2**39 operations.
- collisions in 58-round SHA-1 in 2**33 operations.
This is clearly pretty bad, but remember that in order to exploit a collision (as opposed to a second preimage) you need to generate the colliding pair in advance. So, even if we assume that you can build arbitrary collisions--which the previous work on MD5 didn't let you do---the attacker would need to expend that effort up front, before he cons you into signing one of the pair. It doesn't implicate signatures that have already been generated. See here for more details about the impact of this kind of attack.
Posted by ekr at February 15, 2005 9:34 PM | Filed under:
Comments
Well, *that* wasn't supposed to happen....
I really thought the added twist in the message schedule blocked the attacks. It sure looked like it did based on the SHA0 attacks that were published. I wish Wang & company would publish details of some of these attacks....
--John
Posted by: John Kelsey at February 16, 2005 6:33 AM
My favourite trackback on Schneier's blog was the one that said "Oh well, back to MD5..."
Posted by: william at February 16, 2005 7:20 AM