Understanding sha-1 collision weakness

Question

According to various sources, attacks looking for sha-1 collisions have been improved to 2^52 operations:

http://www.secureworks.com/research/blog/index.php/2009/6/3/sha-1-collision-attacks-now-252/

What I'd like to know is the implication of these discoveries on systems that are not under attack. Meaning if I hash random data, what are the statistical odds of a collision? Said another way, does the recent research indicate that a brute-force birthday attack has a higher chance of finding collisions that originally proposed?

Some writeups, like the one above, say that obtaining a SHA-1 collision via brute force would require 2^80 operations. Most sources say that 2^80 is a theoretical number (I assume because no hash function is really distributed perfectly even over its digest space).

So are any of the announced sha1 collision weaknesses in the fundamental hash distribution? Or are the increased odds of collision only the result of guided mathematical attacks?

I realize that in the end it is just a game of odds, and that their is an infinitesimally small change that your first and second messages will result in a collision. I also realize that even 2^52 is a really big number, but I still want to understand the implications for a system not under attack. So please don't answer with "don't worry about it".

Answer 1

The result announced in your link is an attack, a sequence of careful, algorithmically-chosen steps that generate collisions with greater probability than would a random attack. It is not a weakness in the hash function's distribution. Well, ok, it is, but not of the sort that makes a random attack likely on the order of 2^52 to succeed.

If no one is trying to generate collisions in your hash outputs, this result does not affect you.

Answer 2

Well good hash functions are resistant to 3 different types of attacks (as the article states).

The most important resistance in a practical sense is 2nd pre-image resistance. This basically means given a message M1 and Hash(M1)=H1, it is hard to find a M2 such that Hash(M2)=H1.

If someone found a way to do that efficiently, that would be bad. Further, a preimage attack is not susceptible to the birthday paradox, since message M1 is fixed for us.

This is not a pre-image or second pre-image attack, merely a collision finding attack. To answer your question, No a brute force attack does NOT have a higher chance of finding collisions. What this means is that the naive brute force method, combined with the researchers methods result in finding collisions after 2^52. A standard brute force attack still takes 2^80.

Answer 3

Keep in mind that hash function weaknesses depend also depend on the type of data you're talking about and what you're using the hash values for. The article you referred to only talks about general collisions. I.e. if I have one random string what does it take to find another random string that hashes to the same value. Getting from a collision between random data blobs to a useful collision (one where, for example, the two things that hash to the same value are both valid digital certificates seemingly signed by the same CA) is much harder. From the article: "I am unaware of a practical collision that has been found." The upshot of this is that SHA-1 is not broken for real world use - yet.

Answer 4

The key question is "Can the attacker modify both m1 and m2 messages"?. If so, the attacker needs to find m1, m2 such that hash(m1) = hash(m2). This is the birthday attack and the complexity reduces significantly --- becomes square root. If hash output is 128 bits (MD5), the complexity is 2^64, well within reach with current computing power.

The usual example given is that the seller asks his secretary to type message "I will sell it for 10 million dollars". The scheming secretary creates 2 documents one that says "I will sell it for 10 million dollars" and another that says "I will sell it for x million dollars", where x is much less than 10, modifies both messages by adding spaces, capitalizing words etc, modifies x, until hash(m1) = hash(m2). Now, the secretary shows the correct message m1 to the seller, and he signs it using his private key, resulting in hash h. The secretary switches the message and sends out (m2, h). Only the seller has access to his private key and so he cannot repudiate and say that he didn't sign the message.

For SHA1, which outputs 160 bits, the birthday attack reduces the complexity to 2^80. This should be safe for 30 years or more. New government regulations, 4G 3gpp specs are starting to require SHA256.

But if in your use-case, the attacker cannot modify both the messages (preimage or second preimage scenarios), then for SHA1 the complexity is 2^160. Should be safe for eternity unless non-brute-force attack is discovered.