There is this tiny statistics problem in IT security that almost nobody talks about, yet I have seen people get it wrong many times in the past: Calculation of the success probability of brute-force attacks against TOTP two-factor authenticators.

As a reminder: TOTP tokens are defined in RFC 6238 ("TOTP: Time-Based One-Time Password Algorithm"). They usually consist of six-digit strings that change every 30 seconds. The entire sequence of tokens is derived from a secret (and the current time) in a way that makes token prediction without the secret impossible. TOTP tokens are commonly used as a second factor, in addition to a user’s password, reducing the impact of a potential password compromise.

In various engagements I have seen TOTP validation implementations that do not rate-limit the process of entering and validating the TOTP token. Due to the limited search space (6 digits = “only” 1000000 possible tokens) this can render the second factor ineffective and allow attackers to bypass 2FA. When documenting that finding, it’s usually a good idea to provide the client with some numbers answering the question “How long does it take?”. However, over the years I have seen several colleagues calculate that number incorrectly, which highlights how easy it is to overlook some of the statistical nuances involved.

Naive Approach Link to heading

The naive (and wrong) approach is as follows: Assuming 100 guesses per second (rate R) and a search space of 1000000 possible tokens (6 digits, search space N) the attack will be successful after:

t=NR=1000000 tokens100 tokens/s=10000 s≈2 h 46 mt = \frac{N}{R} = \frac{1000000\,\text{tokens}}{100\,\text{tokens}/\text{s}} = 10000\,\text{s} \approx 2\,\text{h}\:46\,\text{m}

Unfortunately, this calculation underestimates the fact that in reality the window of opportunity (for an attacker) “jumps” every 30 seconds. That means, there is usually1 a possibility that the attacker might never guess the correct code, even after billions of guesses - if the window always “jumps” away from their next guess.

Better Calculation Link to heading

A much better approximation can be made by looking at each window individually. For each window of length T, the probability of brute-forcing (i.e. guessing without replacement) the correct code is:

P(correct guess,T)=R⋅TNP(\text{correct guess}, T) = \frac{R \cdot T}{N}

In order to calculate the probability that the correct code is found after n windows, we need to take a short detour via the probability that the correct code is not found:

P(at least one correct guess after n windows)=1−(1−P(correct guess))n=1−(1−R⋅TN)nP(\text{at least one correct guess after $n$ windows}) = 1 - \left(1 - P(\text{correct guess})\right)^n = 1 - \left(1 - \frac{R \cdot T}{N} \right) ^ n

Finally, instead of looking at n windows, let’s plug in a time t and the window time T. This yields our final2 result:

P(at least one correct guess after t)=1−(1−R⋅TN)tTP(\text{at least one correct guess after $t$}) = 1 - \left(1 - \frac{R \cdot T}{N} \right) ^ \frac{t}{T}

The following plot shows this function with the parameters R = 100/s, T=30s, N=1000000. As expected, the probability approaches 100%, but never quite reaches it.

Inversion Link to heading

Often we would like to calculate at which time a desired probability p has been reached. We start by calculating the amount of windows that must pass:

t=T⋅ln⁡(1−p)ln⁡(1−R⋅TN)t = T \cdot \frac{\ln(1 - p)}{\ln\left(1-\frac{R \cdot T}{N} \right)}

Here we can find an approximation by applying the Taylor series of ln⁡(1−x) if x=R⋅TN≪1\ln(1-x)\:\text{if}\:x = \frac{R \cdot T}{N} \ll 1 to the divisor:

f(x)=ln⁡(1−x)=−x−O(x2)f(x) = \ln(1 - x) = -x - \mathcal{O}(x^2)
t=T⋅−ln⁡(1−p)R⋅TN=−ln⁡(1−p)⋅NRt = T \cdot \frac{- \ln(1 - p)}{\frac{R \cdot T}{N}} = - \ln(1 - p) \cdot \frac{N}{R}

In practice, we can almost always use this approximation. I verified that even at R = 1000/s, the curves only differ by around 10 seconds at p = 0.5.

For the parameters shown in the plot above (R = 100/s, T=30s, N=1000000), a 50% probability is reached after 115 minutes (1h 55min), a 90% probability after 384 minutes (6h 23min).

Accepting Multiple Codes Link to heading

The probability formula can be easily extended for cases where the last m-1 TOTP codes are also accepted (total accepted: m):

P(t)=1−(1−m⋅R⋅TN)tTP(t) = 1 - \left( 1 - \frac{m \cdot R \cdot T}{N} \right) ^ \frac{t}{T}

For the inversion, this results in:

t=T⋅ln⁡(1−p)ln⁡(1−m⋅R⋅T1000000)≈−ln⁡(1−p)⋅1000000m⋅Rt = T \cdot \frac{\ln(1 - p)}{\ln\left(1-\frac{m \cdot R \cdot T}{1000000} \right)} \approx - \ln(1 - p) \cdot \frac{1000000}{m \cdot R}

One consequence is that by also accepting the last code, the brute-force time is halved.

Interactive Calculator Link to heading

For all fellow penetration testers who need to document this (or a similar) issue, I’ve vibe coded a TOTP Brute-Force Calculator!

  1. As long as the attacker does not exhaust the entire search space (1000000 guesses) within one window (30 seconds). ↩︎

  2. The exact result would be a combination of a step function with linear interpolation. The “final result” shown in this post is only an approximation. I originally wanted to include the full derivation, but this would have made the post even more boring. ↩︎