8

mathematically / theoretically, what is the chance that 2 different inputs would have the same results of 2 different hash functions?

As an example, i will use 2 weaker hash algorithms, the MD5 (Collision Vulnerabilities)and SHA-1 Collision Vulnerabilities. So I have a password. I hash it with MD5 then I hash it with SHA-1. mathematically / theoretically, what is the chance that there is another input with the same SHA hash and MD5 hash as my result?

4 Answers 4

3

If I have two random strings (s1, s2) that are different (s1 != s2), you want to know the probability that md5(s1) == md5(s2) AND sha1(s1) == sha1(s2).

Well, first for two specific randomly chosen strings what is the probability that md5(s1) == md5(s2)? Answer its 1/2^128 as the first hash is some 128-bit string, and the chances that the second hash equals the second is 1 in 2^128 or about 2.9 x 10^-37 %.

Similarly, P(sha1(s1) == sha1(s2)) = 2^-160 ~ 6.8 x 10^-47 %.

Now the probability that that both conditions would be true assuming they are independent conditions (that is that the hashing functions are fundamentally independent of each other), is found by multiplying the probabilities since P(X AND Y) = P(X) P(Y) so P(md5(s1)==md5(s2) AND sha1(s1) == sha1(s2)) = 2^-288 ~ 2 x 10^-85 %.

Granted we assumed the hashing functions act independent of each other on the string -- which is a fair assumption for md5 and sha1 as hashing functions. But if instead of comparing MD5 and SHA-1, we compared MD5 and a new hashing function that's just MD5 applied to itself 100 times, we would find that whenever md5(s1) == md5(s2), that we'd also have md5^100(s1) == md5^100(s2), so the probability of both colliding is the same as the probability of having one collision.

Similarly, if we had a silly "hash" function that was just silly_hash(s) = md5(s) ++ s (where ++ means concatenate), then you could show that if s1 != s2 and md5(s1) == md5(s2) then silly_hash(s1) != silly_hash(s2) -- meaning that you could never have a double collision with md5 and silly_hash.

1
  • @Pacerier: If you take 2 specific strings and compre, there's a 1 in 2^288 ~ 497323236409786642155382248146820840100456150797347717440463976893159497012533375533056 chance of both matching. Granted if you generate roughly about 2^144 ~ 22300745198530623141535718272648361505980416 strings together, there's a good chance that both hashes will match for one.
    – dr jimbob
    Jul 16, 2011 at 18:57
9

Mathematically? 100% probability. There almost certainly exists some other input with the same MD5 and SHA hash.

Practically? 0% probability. While some other input exists, there is no known way to find it within the lifetime of the universe.

You are asking about second pre-image resistance. As far as I know, at least SHA1 (and probably MD5 as well) are believed to provide strong pre-image resistance. Hence the comment that there's no known way to find another input with the same hashes, within the lifetime of the known universe.

2
  • 5
    Actually it is not guaranteed, given a message m, that there exists another m' shuch that m and m' have the same MD5 and the same SHA-1. It would just be very surprising that there is none. What is guaranteed is that there exists many pairs (m, m') which yield the same MD5 and SHA-1 (collisions are guaranteed, second preimages are not). Jul 13, 2011 at 11:28
  • 2
    no reliable way. There's always luck.
    – AviD
    Jul 13, 2011 at 21:03
4

Collision attacks are specifically for the case where you can chose the two colliding inputs as needed. For the password scenario you describe, the password is usually determined beforehand, so it is not a collision but a pre-image attack. Since the password is probably also not known to the adversary, what you are concerned about is a "first pre-image" attack. This is the hardest attack since it gives the adversary the least degree of freedom. SHA1 and MD5 are currently secure against this kind of attack. Meaning the likelyhood of finding another input to a given hashsum output is zero for all practical purposes.

Put another way: If this attack would work, most current network protocols would be insecure. (People actually checked the current protocols to see if collision attacks are dangerous and decided we can continue to use them.)

2

Ff you have an $str1 that returns the same md5 as $str2, then they're automatically going to have the same sha1. That's because if you are doing SHA1(MD5($string)), then you just reduced the number of inputs to the SHA1 portion from an infinite space to 128bits.

4
  • 2
    I think he's talking about doing them as separate operations, not chaining the hashing functions. So, what are the odds that MD5(str1) == MD5(str2) AND SHA1(str1) == SHA1(str2)? Jul 13, 2011 at 12:38
  • "I hash it with MD5 then I hash it with SHA-1" doesn't sound like it. But if he does, then the chance is (2^-128) * (2^-160), isn't it?
    – Marcin
    Jul 13, 2011 at 12:56
  • 1
    If you hash the password with MD5 then hash it (the password) with SHA1 you're hashing them separately. But yes, I think your numbers are right. The odds of finding inputs that collide with two different hashing algorithms should be infinitesimal. Jul 13, 2011 at 13:00
  • "if i hash it with md5 then hash it with sha1" is different from "if i hash it with md5 and hash the result with sha1"
    – Pacerier
    Jul 14, 2011 at 3:34

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .