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.