Question

Probability of two vms generating the same random number

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/2n1/2n, so getting the same 10-byte value twice in a row would happen with probability 1210∗8≈1/(1.2089∗1024)1210∗8≈1/(1.2089∗1024), 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∗1095.1∗109 invocations. For 128 bit, that grows to 2.2∗10192.2∗1019 (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 697615423697615423 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/2n1/2non 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 pp (that would be the 1/(1.2089∗1024)1/(1.2089∗1024)from above). You would calculate 1−((1−p)n)1−((1−p)n). The inner (1−p)n(1−p)nbasically gives you the probability that you will not hit it on any of your nn 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.

Answer 2

Assuming different seeds, the probability of getting any specific n-bit string is 1/2n1/2n, so getting the same 10-byte value twice in a row would happen with probability 1210∗8≈1/(1.2089∗1024)1210∗8≈1/(1.2089∗1024), assuming a perfectly random (uniformly distributed) DRBG.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 697615423697615423 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/2n1/2non 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 pp (that would be the 1/(1.2089∗1024)1/(1.2089∗1024)from above). You would calculate 1−((1−p)n)1−((1−p)n). The inner (1−p)n(1−p)nbasically gives you the probability that you will not hit it on any of your nn 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.