« US out of Iraq? | Main | Stingray home firewall »
August 17, 2005
Another turn of the crank on SHA-1
Steve Bellovin reports from Crypto '05 that Wang et al have made more progress on SHA-1, bringing the cost of a collision down to 263.Shamir gave her rump session talk (and first gave a humorous presentation on why she couldn't get a visa -- she admitted to attacking U.S. government systems, and used collisions). She is indeed claiming a 2^63 attack, and found a new path to use in the attack. Because of the new path, there is reason to think the attack will get even better. Shamir noted that 2^63 is within reach of a distributed Internet effort to actually find one.
Anyone want to speculate on where this will stop? My uninformed guesstimate is around 256-260 (revised downward from around 264 a month ago...).
Posted by ekr at August 17, 2005 9:39 AM | Filed under:
Comments
I was listening to the webcast, and I am pretty sure Steve got one bit wrong (we'll know for sure when the webcast is put on the IACR page). I thought Shamir talked about a hardware-attack like the DES cracker, not a distributed attack.
For the life of me, I cannot imagine why people would want to contribute their CPU cycles to helping someone find a hash collision other than for cuteness value. This isn't like the public key tests, at least from the descriptions of Wang's attacks: we will know ahead of time how much work will be expected to find a collision.
Also, I distinctly remember you saying 2^65 exactly two weeks ago while we were being interviewed for this article. :-)
Posted by: Paul Hoffman at August 17, 2005 5:03 PM
2^65 huh? Well, I could argue that 2^64 is around 2^65, but let's just say that I forgot. The key point is that I was wrong, wrong, wrong...
Posted by: EKR at August 17, 2005 5:26 PM
One benefit to doing the collision search in practice is to verify that the attack works as advertised, though there are ways to be pretty sure of that without doing the full computation. Another is to get all the details spelled out so that the attack can be carried out.
Posted by: John Kelsey at August 18, 2005 11:05 PM