Information Security Stack Exchange is a question and answer site for information security professionals. It only takes a minute to sign up.
Sign up to join this community
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?
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.
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.
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.)
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.
