SHA-1 Algorithm Busted

IWETHEY v. 0.3.0 | TODO

1,095 registered users | 0 active users | 0 LpH | Statistics
Login | Create New User

Welcome to IWETHEY!

Post #195,016

by tuberculosis

Picture of tuberculosis

2/16/05 2:46:05 PM

SHA-1 Algorithm Busted

[link|http://www.schneier.com/blog/archives/2005/02/sha1_broken.html|http://www.schneier..../sha1_broken.html]

SHA-1 has been broken. Not a reduced-round version. Not a simplified version. The real thing.

The research team of Xiaoyun Wang, Yiqun Lisa Yin, and Hongbo Yu (mostly from Shandong University in China) have been quietly circulating a paper describing their results:

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 attack builds on previous attacks on SHA-0 and SHA-1, and is a major, major cryptanalytic result. It pretty much puts a bullet into SHA-1 as a hash function for digital signatures (although it doesn't affect applications such as HMAC where collisions aren't important).

"Whenever you find you are on the side of the majority, it is time to pause and reflect"   --Mark Twain

"The significant problems we face cannot be solved at the same level of thinking we were at when we created them."   --Albert Einstein

"This is still a dangerous world. It's a world of madmen and uncertainty and potential mental losses."   --George W. Bush

Post #195,020

2/16/05 3:02:12 PM

What kind of colliding?

Do they just manage to find two strings that happen to collide? (Fairly weak since neither is likely to be a message of interest.) Or do they manage to start with one string, and find another than collides with it? (Nastier, since you can intentionally substitute one message for another.) Or do they manage to start with one string, start with part of another, and complete the other out to something that collides? (Now we're talking about my being able to slip you a signed executable that does something specific.)

That they can find collisions tells me one thing. But collisions are not created equal. What is the threat?

Cheers,
Ben

I have come to believe that idealism without discipline is a quick road to disaster, while discipline without idealism is pointless. -- Aaron Ward (my brother)

SHA-1 Algorithm Busted - (tuberculosis) - (1) - Feb. 16, 2005, 02:46:05 PM EST

What kind of colliding? - (ben_tilly) - Feb. 16, 2005, 03:02:12 PM EST

Are you game enough to ICLPRD that subject line?
81 ms