In this post I’ll show you a neat party trick that can let you easily bypass Time-Based One Time Password (TOTP) multi-factor authentication, and often within just a few hours. If your TOTP implementation doesn’t include brute-force protection, you might be in trouble. Sample code to exploit this can be found here.

$ ./otpbrute --threads 16 http://localhost:8080/login '{"data": {"user": "test", "password": "test", "otp": "%s"}}' "successful"
2021-07-23 16:41:37,158 Starting OTP guessing, press Ctrl+C to stop...
2021-07-23 16:41:37,353 Starting 16 threads...
2021-07-23 16:41:55,479 Made 1600 guesses at ~ 88 guesses per second
2021-07-23 16:41:55,483 We think you'll be logged in after 9300 seconds (2021-07-23 19:16:55.483658), with a probability of 90%!

...

2021-07-23 18:04:47,298 Thread 14 succeeded with the code 632905:
Content-Type: application/json
Set-Cookie: Auth=49c7...yoink...; Path=/; Expires=Mon, 23 Aug 2021 06:04:47 GMT
Date: Fri, 23 Jul 2021 06:04:47 GMT
Content-Length: 42

{"status":1, "message":"Login successful"}

TOTP is a popular method for adding multi-factor authentication to websites and apps. When a user wants to log in to the application, they supply their username and password as well as a numeric code (usually six digits) generated by an app on their phone. The numeric code changes every 30 seconds so that the user can prove they’re really in possession of the shared seed and not just re-using a code they captured earlier.

You might think that if you know the username and password for someone it would be very difficult to guess their six-digit code - after all, six digits means that the chance you guess the code correctly is “one in a million”. Those are bad odds for an attacker, right? They are - but only if your TOTP implementation very carefully rate limits guesses or completely locks-out accounts.

What if your implementation doesn’t rate limit attempts and you can just make a whole lot of guesses? Then an attacker can bypass the requirement to have the device with the TOTP seed, usually within a matter of hours or days of trying.

And you know what? Software in the real world often lacks TOTP rate limiting attempts. I suspect this is because, intuitively, it doesn’t feel necessary.

It’s tempting to think that because the “correct” code changes every 30 seconds that someone trying to guess the code would also have to “start over” periodically, or than an attacker would need to issue up to a million requests in 30 seconds. In reality an attacker doesn’t have to guess the specific code that the server is thinking of - they just have to guess whatever code happens to be valid at the moment. The likelihood of any one code being correct is the same as any other.

The odds therefore remain essentially the same every time you guess, regardless of how often the code changes. If you have a small percentage chance of guessing the right code, and no punishment (such as account lockout or rate limiting), then you can attempt to win that small percentage chance as many times as you like.

Does this really work?

Yes. Just by repeatedly guessing it’s possible to bypass TOTP when no rate limiting is in place. For example, given a default MediaWiki installation this is possible in just a few hours. If you’d like to experiment with this, have a look at the otpbrute tool I’m releasing today, available here. This tool is multi-threaded, so it can generate relatively large numbers of requests. It’ll even estimate how long it thinks it will need to bypass a TOTP requirement for you, if you have scipy installed.

I’ve also left a proof-of-concept script that specifically targets MediaWiki in the same repo, though I leave it as an exercise for the reader to make this approach faster like otpbrute is.

The Maths

Estimating whether a particular TOTP implementation is vulnerable to brute force is easy in Python with SciPy’s stats module. Even though TOTP guesses don’t exactly follow a binomial distribution they’re close enough to get a useful estimate.

Using the MediaWiki example we discussed earlier, by default the MediaWiki TOTP extension allows up to 4 codes before and 4 codes after the “current” code, giving a total of 9 possible valid codes at any given time. This improves the odds of every guess from one in a million to nine in a million - almost ten times weaker.

Let’s say we’ve captured or guessed the username and password for a user of a wiki and we want to know if it’s practical to bypass the TOTP authentication step. What do we need to know to estimate this? We need to know how many guesses we can make without being noticed. Let’s say we can make 10 guesses every second - we checked, and this is realistic with MediaWiki even on a small virtual machine. With a bigger machine it’s not unreasonable to make even 30 guesses per second, or to make fewer guesses but to be more patient. Here we’ll stick with the realistic (but not especially sneaky) value of 10 guesses per second.

Take the number of guesses we can make in an hour (n=3600 * 10), and ask SciPy to calculate the probability that after an hour we haven’t succeeded at logging in even once (k=0). With a chance of 9 in a million for every guess (p=9 / 1000000), we get:

>>> from scipy.stats import binom
>>> binom.pmf(k=0, n=10 * 3600, p=9 / 1000000)
0.7232491878754308

In our first hour of guessing we have a 72% chance of complete failure, and because we have to do one of either fail or succeed, our chances of success in the first hour is therefore about 28% (100% – 72% = 28%).

But what if we kept guessing at this rate for 5 hours?

>>> 1 - binom.pmf(k=0, n=10 * 3600 * 5, p=9 / 1000000)
0.8021027436012991

After five hours we’ve got an 80% chance of success, and it’s likely we will have successfully logged in. Even at one attempt per second, we exceed an “even chance” of getting in after just a day:

>>> 1 - binom.pmf(k=0, n=3600 * 24, p=9 / 1000000)
0.5404941009170326

How to fix?

With TOTP the best way to defend against this attack is to change the numbers in the equation. Reducing the effective number of guesses an attacker can make drastically alters their chances of success.

For instance, if you lock a user’s account for 15 minutes after five incorrect code attempts, you can reduce the number of attempts per hour to just 20. At this rate an attacker would need 6 months to reach an even chance of guessing a TOTP code correctly.

If you’re running MediaWiki specifically, make sure you enable the $wgRateLimits config for “badoath”. More information is available here, specific information on $wgRateLimits is available here.

Also, when you’re implementing a rate limit for TOTP attempts, make sure it’s incrementing the count of attempts atomically. If an attacker can supply ten codes while your rate limiting counter only increments once, it won’t be nearly as effective.

An alternative solution to fixing TOTP is to implement FIDO. FIDO provides an even stronger and more flexible solution for multi-factor authentication. More information about FIDO is available from the FIDO Alliance website.

Other resources

Luke Plant has a great writeup of this same technique, and he explains the maths from a different angle. If you want to know more about how the probabilities work, be sure to check out his article.

If you’d like to experiment with different approaches to brute forcing TOTP codes Tim Goddard has a Go codebase implementing a dummy OTP authentication process that makes testing a lot quicker. Find it on his GitHub account.