1
$\begingroup$

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.

$\endgroup$
9
  • $\begingroup$ 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). $\endgroup$ Nov 2 '17 at 22:34
  • $\begingroup$ Why divide by 1e9 instead of multiplying by it? $\endgroup$ Nov 3 '17 at 6:42
  • $\begingroup$ @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. $\endgroup$
    – MarcG
    Nov 4 '17 at 21:26
  • $\begingroup$ @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? $\endgroup$
    – MarcG
    Nov 4 '17 at 21:36
  • $\begingroup$ @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. $\endgroup$ Nov 4 '17 at 21:52
2
$\begingroup$

Well whilst AES can take 256 bit keys, it still only accepts a 128 bit IV. And the width of the AES block is considered secure in 2017. So that would be a good guide.

Also, there are type 4 UUIDs that use 122 bits of uncertainty and are currently in widespread use. There's not a lot more to say other than to extract this from my reference:-

Thus, for there to be a one in a billion chance of duplication, 103 trillion version 4 UUIDs must be generated.

Increasing the size to 128 bits would require 8e14 tokens for the same 1 in a billion risk of collision. Should be okay.

$\endgroup$
3
  • $\begingroup$ Using my 73.74 bits, that formula results in sqrt(2*(2^73.74)*ln(1/(1-(1/1E9)))) = 5.6 million tokens for 1 in a billion risk. This implies my calculation is wrong. Or it is right for random numbers, but it's not if the attacker can avoid repeating numbers, which is my question number 2. And that is the more realistic scenario. $\endgroup$
    – MarcG
    Nov 4 '17 at 22:05
  • $\begingroup$ By using that formula with my numers: sqrt(2*(2^n)*ln(1/(1-(1/1E9))))=1.5768E20 ➜ n = 163 bits. $\endgroup$
    – MarcG
    Nov 4 '17 at 22:09
  • $\begingroup$ @MarcG and that number is much closer to what cryptographers often target - a 192 bit value will have negligible chance of being duplicate and is too large to brute force. $\endgroup$ Nov 4 '17 at 22:19

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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