How to calculate the probability to get two random numbers equal from the same generator

Question

I have deterministic random bit generator (DRBG) to generate a random numbers in which it is 10 byte value and I want to turn this algorithm twice, what is the probability to get the two random equal and what is the maximum time to try to get this result ?

Answer 1

Well, to start with, if you run two DRBGs with the same seed, the probability of getting the same values from both of them is obviously 100%.

Assuming different seeds, the probability of getting any specific n-bit string is $1/2^n$, so getting the same 10-byte value twice in a row would happen with probability $\frac{1}{2^{10*8}} \approx 1/(1.2089*10^{24})$, assuming a perfectly random (uniformly distributed) DRBG.

If you just want to run the DRBG a number of times until any two results collide, we get into the area of the birthday paradox. I don't have the result for 80 bits (10 byte) at hand, but for 64 bits, to have a collision with the chance of 50% you would have to try $5.1 * 10^9$ invocations. For 128 bit, that grows to $2.2*10^{19}$ (results from this table). This will get lower if your DRBG is not perfectly random, but biased towards certain values.

As for the time this would take, it depends on the performance of the DRBG and your machine, but I think "quite a while" would be a good first guess. If you assume 1 ms for each invocation (including comparison), 64 bit would take around 60 days, while 128 bit would already take around $697\,615\,423$ years (for a chance of 50% for a collision). Yours would be somewhere in between.

Edit: If you want to hit a specific value, you will have the same chance of $1/2^n$ on every invocation. That's a Bernoulli process, and it's a bit of a headache.

Say you want to know what your chance is to hit one matching result in n tries, and your probability of success for each try is $p$ (that would be the $1/(1.2089*10^{24})$ from above). You would calculate $1-((1-p)^{n})$. The inner $(1-p)^n$ basically gives you the probability that you will not hit it on any of your $n$ tries (i.e. you will fail every time). You invert that by taking 1 minus that result and you get the probability of finding at least one match. You can use that to estimate how many attempts it would take.

There probably is a way to estimate the number of attempts to get to a certain probability of success, but I can't find it right now. If anyone knows, feel free to edit this answer.