Lets say I have a database that contains X SHA256 hashes . How do I calculate the likelihood of a me creating a hash out of random values that collides with any hash in the stored database?


Assuming you have no collision so far, and your random values are from a larger space and don't themselves collide, then the probability of a single new value being a hash collision is $\frac{X}{N_{h}}$ where $N_h$ is the maximum possible number of hashes.

For SHA256, there are $2^{256}$ possible hashes, so your answer is simply $\frac{X}{2^{256}}$

The birthday paradox arises because this probability recurs on each and every insertion into the database. The question you need to ask in order to turn this into an attack is "If I generate X random values, what is the chance that at least one pair have a collision in the hash?". This is more complicated, but is essentially 1 minus the probability that each insertion up to the $X^{th}$ one does not clash, i.e.

$$1 - \prod_{i=1}^{X-1} \frac{N_h - i}{N_h}$$

When $X << N_h$, this is approximately:

$$1 - e^{\frac{-X(X-1)}{2N_h}}$$

| improve this answer | |

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