2

I was wondering if there is a formula to calculate how long it would take to "guess" a "X-Digit" OTP, presuming you limited the number of times you can try for each code and the number of codes you can get over a period of time.

For example:

  • I have a 6-digit code
  • I can try to verify the code 3 times before it becomes invalid
  • I can generate 10 codes per hour (so 30 attempts per hour)
  • Each code is generated using a cryptographically secure random generator

To go through the 1 million possibilities, I would have to spend 33,333 hours or about 3.8 years.

I'm not an expert in statistics but since every code is random, you might never find the number even if you go through all possibilities.

So what would be the proper way to calculate this?

I tried to apply Calculating the time required to brute force a random code but I couldn't get the formula to work for some reasons

Glorfindel
  • 3,955
Nicolas Bouvrette
  • 135
  • 1
    "brute-force" is a wrong word in this case. In case of passwords there is guarantee that, if you test all possible passwords, you will find the correct one. But in case of OTP there is no guarantee that you guess the next code, no matter how long you try. In case of OTP we can talk only about probability to find. So the question should be like following: "How long would it take to guess OTP with probability 80%? (90%, 99.999%)" – mentallurg Jan 24 '23 at 22:38
  • This is the definition "brute-force" by Wikipedia: "In cryptography, a brute-force attack consists of an attacker submitting many passwords or passphrases with the hope of eventually guessing correctly." - It feels like you are splitting hairs a bit? Also, I don't know if you are the one who downvoted my question but I don't see how this will encourage people to contribute to this community – Nicolas Bouvrette Jan 24 '23 at 23:15
  • 1
    Exactly, this definition is applicable to passwords, because they are static. Whereas OTP is permanently changing. That's why in case of OTP we can only talk about probability. Misleading titles are not useful for the community. I'd suggest you to adjust it to something like "... to guess with probability ...%". Such title will be helpful. – mentallurg Jan 24 '23 at 23:21
  • I mean, for me if you brute-force a sitting or moving target, the definition I gave you applies. What differs tho is the formula, which was the question here. I just made an edit; I hope you will find this clearer now. – Nicolas Bouvrette Jan 24 '23 at 23:37
  • Your math and your premise do not appear to work out, hence the title and question being off. "Length of time" does not seem to apply, since you only get 3 tries. Therefore, the question is: how likely is it to guess a 6 digit number with only 3 tries? That's not "brute-force". Your "10 codes an hour" doesn't seem relevant since you need to re-guess (3 at a time) for each one. So, this doesn't seem to be a security question, but a really basic math question. Your link doesn't apply because the context is different (that's why it won't work out). –  Jan 24 '23 at 23:43
  • So, mentallurg is right. The actual number doesn't matter and can't get determined. You can get the percentage chance and expand the number of tries until you get to 50% and make conclusions from there. –  Jan 24 '23 at 23:45
  • Independent on math, there is one more aspect. If the application allows unlimited number of login attempts, it means a serious security problem. Any reasonably secure application allows a limited number of attempts. No matter if these are 3, 5, 10 or even 100 attempts. Important is, that after the limit is reached, the account will be locked and no further attempts are possible. That's why a scenario with unlimited attempts is far from real world and can only be interesting from the math point of view. – mentallurg Jan 25 '23 at 00:00
  • You quote from Wikipedia is not complete. See the article further: "The attacker systematically checks all possible passwords and passphrases until the correct one is found." This definition means that the number of attempts is finite and that after all possible passwords tried, the correct one will be found. Where is in case of OTP there is no correct code, and there is no guarantee that one will guess an OTP, no matter how many attempts one does. We can only speak about probability. – mentallurg Jan 25 '23 at 00:08
  • May be following example can help. Suppose person A picks up a number between 1 and 100, writes it down on a card and puts it to an envelope. Person B has to guess it. Person B has no idea how to approach it and just tries every number starting from 1. Then in the worst case after 100 attempts the person B will definitely guess the number. But if person A picks up a new number after each attempt of person B, then person B can make 100, 1 000, 1 000 000, 1 000 000 000 attempts and still there is no guarantee that person B will ever guess the number. The same logic is applicable for OPT. – mentallurg Jan 25 '23 at 00:24

1 Answers1

3

In your example, we can think about it as follows:

A six-digit code has 1,000,000 possible states, hence allows for a 1/1,000,000 chance to correctly guess it on the first try. Given that we can try thrice, the second chance is 1 / 999,999 and the third is 1 / 999,998. Although, the numbers are too close to 3/1,000,000 for it to make statistical difference.

So we can say, for one generated code, our chance is 3/1,000,000. That means, plugging into the formula 1-(1-p)^n = x, we get an n of ≈231,049 codes to generate for a 50% chance of cracking it.

In other words: If 231,049 different hackers each tried to hack a six-digit code by choosing 3 random codes, then about half of them would succeed.

Since we can do this 10 times an hour, we can conveniently just divide this by 10 to see how many hours it'd take, which is 23,105 hours, or about 2.6 years.

This is actually slightly better than your estimate.

Why does it not align with the linked calculation?

This is because you're not sufficiently exhausting the keyspace. As I said in the beginning, the second and third guess are slightly more likely to succeed than the first one, because you already know one code that isn't correct, and later two.

However, on your third wrong guess, the code becomes invalid and you are back at the beginning. For this reason, you have to use a different formula, which calculates the cumulative chance of independent events, rather than simply checking how large the keyspace is and dividing it in half.

Regarding the real world

In real life, it's likely even more difficult to be successful, because repeatedly entering wrong one-time codes could lock the account, or the service could notify the user that their account is likely compromised, which leads to them changing their password.

In short, OTP codes like this are not bullet-proof and can be guessed by sheer luck, but it's very unlikely to lead to consistent success.

Increasing Security

This scheme is already plenty secure - secure enough that PayPal uses it - but if you want to go even further, you could make the codes longer. 8 digits would turn 2.6 years to 260 years (roughly), and adding even some uppercase letters to it would make the keyspace even larger.

The downside would be a worse user experience, as "632 109" is slightly easier to type than "P88X 6A3H". It would risk users not enabling 2FA at all, all for making a theoretical attack theoretically more difficult.

  • Do you by any chance know the name for the 1-(1-p)^n = x formula? – Nicolas Bouvrette Jan 24 '23 at 04:17
  • After more research, I guess this formula has no name, but its a combination of Complementary Events and Binomial Distribution. – Nicolas Bouvrette Jan 24 '23 at 15:35
  • The number of tries to get 50% probability is correct, 231 048. But your interpretation is wrong. You say: "about half of them would succeed". This is wrong. 50% probability means, that if you repeat series of 231 048 tests many times, then in about half of these series the OTP will be guessed. – mentallurg Jan 24 '23 at 22:54
  • I'm not sure I understand your comment - isn't that what "about half of them would succeed" means? – Nicolas Bouvrette Jan 24 '23 at 23:12
  • @NicolasBouvrette: No. May be following example helps. Suppose there is a lottery with 231 048 tickets. Every week one of tickets is wins. But the winner does not get the price automatically. Instead, the price is put to one of 2 boxes and the winner has to choose one of them. Then in 50% cases the winner will guess it and will get a price, and in 50% the winner will be without price. Such game corresponds to "guessing OTP with 50% probability". Whereas the answer above means, that in such game 50% tickets get price. See the difference? – mentallurg Jan 25 '23 at 00:38
  • ... In such game, you can buy all 231 048 tickets and still not guess in what box is the price. Next week you can buy again 231 048 tickets and you can again remain without price. There is no guarantee that you guess the box. But probability 50% means, that if you repeat it many times, then the number of successful cases will be close to 50%. – mentallurg Jan 25 '23 at 00:51
  • So if I understand correctly, the answer should be edited with: If 231,049 different hackers each tried to hack a six-digit code by choosing 3 random codes, one of them would have a 50% chance to find the right code. – Nicolas Bouvrette Jan 25 '23 at 21:17