# Birthday Attack with probability of 1

According to Wikipedia,

$n(p;H)\approx \sqrt{2H\ln\frac{1}{1-p}}$

Let n(p; H) be the smallest number of values we have to choose, such that the probability for finding a collision is at least p. What if I wants my probability to be 1? In this case, $p = 1$ and $\frac{1}{1-1}$ is undefined. May I know how to find minimum number of values required to get a collision with the probability of 1 using the formula above?

• Is this question for pure curiosity or do you need it as a building block for some protocol?
– user27950
Nov 12, 2016 at 9:56

To get a collision with probability 1, you need to hash $H+1$ distinct values. You can see that because it is possible that if you hash only $H$ values, each one might happen to hash to a unique hash output; if any reasonable sized hash function, this is extremely unlikely, but it does have a nonzero probability to happen. On the other hand, if we hash $H+1$ distinct values, we know (by the pigeon hole principle (because there are only $H$ hash outputs), that two of the inputs must hash to the same output.
The expressions on Wikipedia are probabilistic approximations and in any case look at the earlier approximation $$p\approx 1-e^{-n(n-1)/(2H)}\approx 1-e^{-n^2/(2H)}$$ which shows you can achieve probability $1-\varepsilon$ for any $\varepsilon>0$ if you let $$e^{-n^2/(2H)}=\varepsilon$$ or $$n=\sqrt{2 H \ln (1/\varepsilon)}.$$
To guarantee a collision, you need $1+H$ distinct values by pigeonhole principle. It's much quicker to approach probability one than to guarantee it.