4
$\begingroup$

Pick x random "birthdays", say $10^9$. What are the chance of a collision, given $2^{160}$ possible "days"?

I'm trying to estimate the collision rate of sha1 hashes, but the calculation is too big for wolfram alpha.

$\endgroup$
  • $\begingroup$ You're being a perhaps a little too optimistic expecting that someone trying to break SHA1 would use only $10^9$ combinations. $\endgroup$ – barak manos Jul 31 '14 at 19:35
  • $\begingroup$ It's not really about breaking sha1. It's about the risk of two people having the same hash when hashing some unique input. $10^9$ is just an example of the number of people. $\endgroup$ – Filip Haglund Aug 1 '14 at 10:07
  • $\begingroup$ You could read about the generalized birthday problem and plug in whatever numbers you want. Note that your number of birthdays should be the number of inputs, not the number of people. If each of us has a thousand documents, the number of people is trillions. $\endgroup$ – Ross Millikan Mar 2 '18 at 16:56
10
$\begingroup$

Let $D$ denote the number of possible days. The probability of a collision for $x$ birthdays is $$1-\prod_{k=1}^{x-1}\left(1-\frac{k}D\right)$$ If $x^2\ll D$, this is roughly $$\frac{x^2}{2D}.$$ For $x=10^9$ and $D=2^{160}\approx10^{48}$, the condition holds and one gets approximately $$10^{-30}$$

$\endgroup$
  • $\begingroup$ Hi. How do you get to this nifty approximation? $\endgroup$ – rralf Feb 1 '15 at 16:55
  • 2
    $\begingroup$ @rralf Replacing the product by an exponential and using $1-e^{-u}\approx u$ when $u$ is small. $\endgroup$ – Did Feb 1 '15 at 18:36
  • $\begingroup$ @Did - I have the impression you're saying there's an intermediate formula, between your two formulas, that has an exponential function. I'd love to see that. $\endgroup$ – Bob Stein Jun 24 at 17:58
4
$\begingroup$

If you have $N$ possible 'dates' and $k$ people, here's one way to get a good estimate for the probability of a collision, especially if $N$ is much larger than $k$:

There are $\begin{pmatrix} k\\2 \end{pmatrix}=\frac{k^2-k}{2}$ pairs of people. The probability that any given pair of people has different birthdays is $\frac{N-1}{N}$. Thus the probability of no matches is about $\left(\frac{N-1}{N}\right)^{(k^2-k)/2}$.

For instance in the traditional birthday problem with $N=365$ and $k=23$, the above gives $P(\text{no match })\approx \left(\frac{364}{365}\right)^{253}\approx .4995$.

Caveat: We don't have exact independence of events, and if $k$ gets close to $N$, the independence approximation becomes worse.

$\endgroup$
  • $\begingroup$ "The probability that any given pair of people has different birthdays is N−1N. Thus the probability of no matches is about..." This reasoning is wrong. $\endgroup$ – Did Jul 31 '14 at 19:41
0
$\begingroup$

Well for those exact numbers you would need to use a computer program. You might wanna try asking the question to a programming stack exchange.

Mathematically we use the same probability.

For the usual birthday problem $P(n) = \prod _ {i=1}^{n-1} (1-\frac{i}{365})$. Basically for your extended birthday problem you would want to replace $n$ with $10^9$ and replace $365$ with $2^{160}$.

$\endgroup$

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.