# Calculating minimum number of messages hashed a 50% probability of a collision (Birthday Paradox)

I encountered this while solving a crypto puzzle. This is the puzzle.

You have a hash which gives a 11-bit output. How many minimum messages do we have to hash to have a 50% probability of getting a collision.

Normally we see kind of problem being solved by using an approximation $$2^{n/2}$$ or $$\sqrt {2^n}$$

So for a 11-bit hash, the number of messages to hash to have 50% chance of a collision would be

$$\sqrt {2^{11}} = 45.255 \approx 46$$ messages

However, the solution for this puzzle uses

$$log_{\frac {2^{11} - 1} {2^{11}}}{(0.5)} = log_{\frac{2047}{2048}}{(0.5)} = 1419.22 \approx 1420$$ messages

So you have to hash approximately 1420 messages to get a 50% probability of having a collision.

The solution doesn't explain how they arrive at this. So which is the correct solution?

You are approximately correct; they are wrong. Their answer calculates the chance of matching a particular value i.e. hash inversion. To see this $$k$$ tries have a $$(2047/2048)^k$$ of failing to find a match so you want $$k>\log(0.5)/\log(2047/2048)$$.

For small numbers we can calculate the exact value of the birthday bound by finding the smallest $$k$$ such that $$\prod_{0\le i\le k}\frac{n-i}n=\frac {n!}{(n-k)!n^k}<0.5$$ which in this case is $$k=54$$.

• I think I misread the puzzle. They actually asked for finding a match to the particular value. Thank you. Mar 10 at 8:20