Another turn of the crank on SHA-1

| Comments (3) | TrackBacks (4) |
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...).

4 TrackBacks

Listed below are links to blogs that reference this entry: Another turn of the crank on SHA-1.

TrackBack URL for this entry: http://www.educatedguesswork.org/cgi-bin/mt/mt-tb.cgi/375

online blackjack from online blackjack on January 3, 2006 3:09 PM

online slots ..play online blackjack ... Read More

Free Ringtones from Free Ringtones on January 22, 2006 7:43 AM

Free Ringtones Read More

downtowns complied allot economy.fruitfully.droll renunciate celebrex http://celebrex.d-daystore.com/ Read More

direct car insurance from direct car insurance on February 25, 2006 12:39 AM

held destructions facilely unwieldiness.thrust travel insurance http://www.unique-insurance.com/ Read More

3 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. :-)

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...

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.

Leave a comment