[_urga]

"As long as nobody else has that key, it's virtually impossible for anyone to figure out what the next token your authentication app will offer up."

According to the birthday paradox, TOTP can in fact be broken quite easily if the service does not rate-limit to defend against brute-force attacks on the 6-digit generated TOTP code. An attacker only needs to try 1000 different pins within a minute or two (and some services allow codes after 5 minutes) to have a 50% chance of getting through.

[URSpider94]

Please educate me if I'm wrong, but I don't believe that is correct. Let me explain:

-- There are two kinds of OTP systems: ones that regenerate the code every n seconds, and ones that regenerate the code for every attempt

-- Considering the time-based code, each attempt has an n-choose-1 (1:n) chance of being correct, so your odds of matching the code are based on how many attempts you can make before the code changes. Since the codes can be re-used with no restriction, you have to start over fresh every time the code changes. So your ultimate chance of breaking the code is n-choose-x, or 1:(n/x). Therefore, you'd have to try 500,000 codes to have a 50% chance of forcing a random collision on a 6-digit code, and the odds only go up linearly with the number of guesses.

-- For the case where the code changes every time, each guess is once again an n-choose-1 chance (1:n). Once the code is regenerated, all information from the old code is lost (there is no forward bias on the next number), so it's once again n-choose-1. So, ultimately, you get to the same answer, which is that you have a 1:(n/x) chance of guessing the code.

Now, most OTP systems will accept several passwords before and after the valid key, in case the tokens have gotten out of sync, so there may be as many as 5 keys that will work at a given time. That is just a straight divider, meaning that you have a 5x better chance at any one time of guessing the right answer.

All that said, any sane password checker should be rate-limiting attempts, and locking out a user after, say, 10 or 20 attempts.

[_urga]

"Therefore, you'd have to try 500,000 codes to have a 50% chance of forcing a random collision on a 6-digit code, and the odds only go up linearly with the number of guesses."

No, not according to the birthday paradox (https://en.wikipedia.org/wiki/Birthday_problem).

There's actually a simple formula to work out the number of attempts required for a 50% chance as shown below.

For TOTP (Time-based One-time Password Algorithm):

Assuming only the latest code per current time window is allowed (and not codes on either side), the number of brute-force attempts required for a 50% chance of collision against this code, is given by:

Math.pow(10,6/2) // base=10, digits=6

This gives roughly 1000 attempts for a system that only accepts the current code and not codes on either side.

I am sure there are plenty of systems out there that don't think to rate-limit 2FA codes.