How many bits should a token have to be unguessable (given some computational resources)?

If an attacker may try 10 billion (1E10) random numbers per second. And its attack can last 500 years (500*365*24*3600 = 1.5768E10 seconds).

Then the attacker will try 1E10*1.5768E10 = 1.5768E20 combinations.

Now suppose I have 100 billion (1E11) tokens, which are random numbers of n bits.

I want to calculate n so that the probability the attacker finds any token is around 1 in a billion (1E9).

I believe the answer is n = log2(1E11*1.5768E20/1E9) = 73.74 bits.

Questions:

1. Is this calculation correct?

2. If instead of independent random numbers the attacker can avoid repeating numbers, how much is n? I guess I should use factorials, and I guess this relates to the birthday paradox, but my mathematics seems to escape me know.

3. If simply knowing one of the tokens serves as authentication, what is the recommended n for an attacker with a few million dollars available, as of 2017?

Update:

By using the formula in https://en.wikipedia.org/wiki/Universally_unique_identifier#Collisions, with my specific numbers, in WolphramAlpha, I get: sqrt(2*(2^n)*ln(1/(1-(1/1E9))))=1.5768E20.

Wolphram solves for n: n=163.088. I guess this is the answer to my question 2. I think my calculation for question 1 is correct, but since question 2 is the more realistic scenario I am satisfied with that and will close this question.

• 73 bit random numbers are a bad idea for token. Regardless of the existence of an attacker, you will randomly produce an identical token after on average $2^{\frac{73}{2}}$ or about 137 billion tokens (so, rare but feasible). Nov 2 '17 at 22:34
• Why divide by 1e9 instead of multiplying by it? Nov 3 '17 at 6:42
• @CodesInChaos : 1E9 is the probability that the attacker finds a token. When this probability grows, it gets easier for him. So the number of bits may be smaller. Therefore we should divide by it. Nov 4 '17 at 21:26
• @ThomasM.DuBuisson 2^(73/2) is around 97 billion. How do you calculate that? And if this is so, does that mean my calculation is incorrect? In my calculation the attacker tries 100 billion tokens in 10 seconds (and I already have 100 billion tokens). Where is my calculation incorrect? Nov 4 '17 at 21:36
• @MarcG I seem to have typed $74/2$ in the calculation but the point remains the same. Notice my comment explicitly was talking about producing duplicate tokens and ignored any attacker what-so-ever - this isn't an answer but a side-comment. Should tokens always be unique? Do you want ~100 billion without high probability of duplicates? If so, 73 bits is too small. Nov 4 '17 at 21:52