What are the chances that two messages have the sa

Question

Given two different messages, A and B (maybe 20-80 characters of text, if size matters at all), what is the probability that the MD5 digest of A is the same as the MD5 digest of B and the SHA1 digest of A is the same as the SHA1 digest of B? That is:

(MD5(A) == MD5(B)) && (SHA1(A) == SHA1(B))

Assume no malicious intent, i.e., that the messages are not selected with an aim of finding a clash. I just want to know the odds of this happening naturally.

I'm thinking the chances are "astronomically low," but I'm not sure how to verify this.

More information: the size of the pool of possible messages is restricted, but large (several hundred million). Birthday paradox situations are exactly what I'm worried about.

Answer 1

an addendum to Welbog's post:

Ratios of large factorials can be computed without using arbitrary-precision arithmetic, by using Stirling's approximation:

n! ≈ sqrt(2πn) * (n/e)ⁿ

So (S!)/(S^N * (S - N)!) ≈ sqrt(2πS)/sqrt(2π(S-N))*(S/e)^S/((S-N)/e)^S-N/S^N

= sqrt(S/(S-N)) * (S/(S-N))^S-N * e^-N

= sqrt(1 + α) * (1 + α)^S-N * e^-N where α = N/(S-N) is small.

The approximation (1+a/n)^nx ≈ e^ax holds as n → ∞ (or at least becomes very large)

** so this means (1+(N/(S-N)))^S-N ≈ e^N for S-N >> N.

So I would expect that

(S!)/(S^N * (S - N)!) ≈ sqrt(1 + N/(S-N)) * e^N * e^-N = sqrt(1 + N/(S-N)) for S-N >> N....

except this is greater than 1... so one of the approximations isn't good enough. :p

(** caveat: N/S has to be small: for N=22,S=365 this is off by a factor of 2)

Answer 2

Assuming uniform spread in the range of MD5 and SHA-1 hashes for random strings (which isn't the case), and assuming we're only talking about two strings and not talking about a pool of strings (so we avoid birthday-paradox-type complexities):

An MD5 hash is 128 bits wide, and SHA-1's is 160. With the above assumptions, two strings A and B have a probability of colliding P if both hashes collide. So

P(both collide) = P(MD5 collides) * P(SHA-1 collides)

And

P(MD5 collides) = 1/(2^128)
P(SHA-1 collides) = 1/(2^160)

So

P(both) = 2^-128 * 2^-160 = 2^-288 ~= 2.01 x 10^-87

Again, if you have a pool of strings and you're trying to determine the probabilities of collisions with the pool, you're in the domain of the birthday paradox and this probability I've calculated here doesn't apply. That and hashes aren't as uniform as they should be. In reality you're going to have a much higher collision rate, but it will still be tiny.

---

EDIT

Since you are dealing with a birthday paradox situation, apply the same logic as the solution to the birthday paradox. Let's look at it from the point of view of just one hash function:

N := the number of hashes in your pool (several hundred million)
S := the size of your hash space (2^288)
Therefore,
P(There are no collisions) = (S!)/(S^N * (S - N)!)

Let's pretend we have a nice even number of hashes like 2^29 (roughly 530 million).

P = (2^288!)/(2^288^(2^29) * (2^288 - 2^29)!)

In short, I don't even want to think about calculating this number. I'm not even sure how you can go about estimating it. You'll at least need an arbitrary-precision calculator that can handle huge factorials without dying.

Note that the probabilities will follow a curve that starts at nearly 0 when N = 1 or 2, and it will reach 1 when N >= 2^288, similar in shape to the one on the Wikipedia page for the birthday paradox.

The birthday paradox reaches P = .5 when N = 23. In other words, the probability of a collision is 50% when N is 6% of S. If that scales (I'm not sure if it does), it means that there will be a 50% chance of a collision when you have 6% of 2^288 hashes. 6% of 2^288 is around 2^284. Your value of N (several hundred million) is nowhere near that. It's practically insignificant compared to your S, so I don't think you have anything to worry about. Collisions aren't very likely.

Answer 3

The chosen answer is incorrect because it uses the wrong probabilities. I spent a good portion of today researching this (you can sorta see my thought process in the comments to that answer), and believe the actual answer is the following (for birthday attack of slightly larger messages than the ones you're talking about):

2^-61 * 2^-18 = a collision in once in 2^79.

And that's if it's OK to just multiply these probabilities (I'm unsure of that).

This is doable (less than a couple months and dropping every year) by super computers today.

Note that this is based on sufficiently large pools of messages (to make the birthday paradox meaningful). This is also the scenario you said you were concerned about.

Now, a different situation is finding a collision for a pair of hashes (SHA1 and MD5) of a specific message. This takes you out of bday paradox territory and is orders of magnitude more difficult. I'm not sure if that is 2^(-61*2)*2^(-18*2) or something else. If anyone knows what that is, please post a comment to this answer (would be super appreciated!).

Now you ask:

Given two different messages, A and B (maybe 20-80 characters of text, if size matters at all)

Yes, size does matter. Click the link to the 2^-18 figure and you'll see that value is for two input blocks. In MD5, an input block is 512 bytes. 20-80 characters of text is too small for that, and the single-block value is 2^41.

Thus, for that amount of data, you get 2^-61 (I think) * 2^-41 = 2^-102.

So for that size it seems safe (link contains figure of twice current bitcoin hashrate of SHA256: 46626.93 TH/sec).

Answer 4

Generally, when one picks N elements randomly it is easier to compute the expected number of collision than the probability of a collision. Since the expected number of collisions cannot be smaller than the probability of a collision it can frequently be used as a suitable upper bound.

Assume that p is the probability that two randomly picked elements collide. If we pick N random elements then there are N*(N-1)/2 pair of elements and hence the expected number of collisions is

p * N * (N-1)/2.

E.g., if we assume that the probability for a collision for both MD5 and SHA1 is p=2^-288 then even after randomly picking 2¹⁰⁰ elements we still only expect about 2^-89 collisions.

Another example: if we pick 2³⁰ random elements and only compute the MD5. Assuming that a collision between two MD5 hashes is p=2^-128 this gives an expected number of 2^-59 for the number of collisions. Hence even the probability that the MD5 hash collides for two inputs is already very small.

Answer 5

If message size is not restricted, the chance approaches 100% asymptotically, as there's an infinite number of possible messages and a finite number of possible hashes.

(note: edit to question makes this less relevant now)