New, Faster Attack against SHA-1 Revealed

VxSote writes "According to Bruce Schneier's blog, a team of Chinese cryptographers has announced new results against SHA-1 that speed up the time required to find collisions compared to their previously published attack. Schneier says that a SHA-1 collision search is now 'squarely in the realm of feasibility,' and that further improvements are expected."

Comments

Two questions...

[meditation_dude]

One is, is this really relevant when most terrorist threats these days are so low tech? Two, does anyone know what kind of funding the NSA gets these days? I remember a news report a couple years back that said they were deeply out of date with hardware and so forth.

Crypto is an evolutionary process

[Crixus]

Things like this are inevitable. Crypto is an evolving science, and this kind of thing is healthy.

    I for one am very excited about the future of crypto.

RFC4109

[fwr]

I wonder how this will effect RFC 4109 in that it depreciates MD5 in favor of SHA1. Does this mean that SHA1, at 2^63 is less secure than MD5 at a brute-force 2^64? I'm not a crypto expert or anything, just asking the question; will this effect the proposed standard for the HASH algorithm used in IPsec?

SHA-1 is still good for a lot of applications

[greenrom]

While this finding definitely shows a weakness in the SHA algorithm, it isn't a weakness that makes most applications that use SHA any more vulnerable. They found a way to generate two texts that produce the same hash using an algorithm with a time complexity of 2^63 instead of 2^80 as would be required for a brute force attack. However, being able to generate two texts that produce the same hash won't help you exploit most systems that rely on SHA. If someone finds a way to generate text that produces a SPECIFIED hash in 2^63 time, then there's reason to be concerned. However, since these findings show that SHA-1 has some weaknesses, it's probably time to start looking for a better hashing algorithm before a more serious vulnerability is found.

Re:oh God bless them, those kooky spookies

[p2sam]

not quite.

They fixed SHA up cuz they knew of a flaw, but didn't explain what the fix does.

For DES, they were ... ahem... they realize that DES was DAMNED good. And allegedly they knew of 2 theoretical attacks 20 years before the civilian academics.

But their interference in DES is to restrict DES DOWN to a 56-bit keyspace, cuz they knew that DES was TOO good. :)

Almost anyone with a million bucks can search through 56-bit key space nowadays. As far as I know, there currently does not exist a DES attack that is more efficient (cheaper) than exhaustive search. Not bad for a 20 year old algorithm, huh? That's SECURITY!!

It is commonly believe in the crypto community the weakest point of attack for DES is its small key space.

Now imagine how many more years of service we could had squeezed out of DES, if the keyspace was set to 128?

"Freeform" collision

[Gadzinka]

What no one seems to mention is that their attack finds "freeform" collisions. I mean, they go and find two plaintexts with the same hash. I wouldn't worry about it until they find 2^63 attack against given plaintext/hash.

You can read about the distinction in Birthday Paradox article on Wikipedia. In short, when the difficulty of finding collision against a given message is 2^n, the difficulty of finding any two colliding plaintexts is 2^(n/2).

So, while they may have found 2^63 attack against SHA-1, it is still a "birthday attack", and to find collision against my message signed with sha-1 the attack would still be 2^126.

Or did I miss something?

Robert