Let's say I can check for collisions of 100,000 instances of SHA-1(x) in a second. How long would I have to run these computations to have a probability of at least 1/1000000 of finding a collision.
I'm attacking this like a normal probability problem but I think I may be getting 'lost' in the large, and very small numbers.
Essentially what I am looking to calculate is,
P(at least one collision) =.000001
And we can use the following:
P(at least one collision) = 1 - P(no collision)
So we need to compute how many instances is necessary for
P(no collision) = 0.999999
That's where I'm at thus far, and seeking your help!
It rather depends on how strong SHA-1 is. Wikipedia says it was originally thought to have strength equal to $2^{80}$ which suggests that it might be equivalent to something like a $160$-bit hash.
For a birthday attack looking for collisions, the number of values for probability $p$ of a collision is about $\sqrt{2H \log_e \dfrac{1}{1-p}}$, so if $H=2^{160}$ and $p= 10^{-6}$ this would give slightly more than $10^{21}$.
But SHA-1 is not a simple hash function, and indeed Wikipedia describes research that it is not as strong as originally thought. So in fact this is not the correct order of magnitude.