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$.

  • 2
    $\begingroup$ I think I misread the puzzle. They actually asked for finding a match to the particular value. Thank you. $\endgroup$
    – user93353
    Mar 10 at 8:20

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.