One-time passwords (OTPs) are often used as a second factor during authentication. In 2FA, usually time-based OTPs (TOTPs) are generated on a device that you own, such as RSA tokens or authenticator apps.

Sometimes OTPs are also used as an alternative to passwords or as a token for password resets. I’ll call these event-based OTPs because the OTP is generated on a specific event.

Such OTPs are usually sent to the user via email or SMS. The discussion of whether OTPs via SMS are secure is a whole different topic, I am not going to cover here.

Instead, I want to focus on an attack vector that all these implementations have in common: Brute-force attacks

Brute-force Attacks

In a brute-force attack, every possible candidate in the search space is tested. Therefore, it is only feasible if the size of the search space is limited. This applies to many OTP implementations because they are made up of 4 to 8 digits.

For example, there are 10,000 4-digit numbers (0000-9999). Now, if you have only one try, the probability of guessing correctly is $$p = \frac{1}{10000} = 0.0001$$

However, applications often allow multiple entry attempts to provide a better user experience. After a certain number of failed attempts, the OTP becomes invalid. Let’s say, you have five attempts. The probability of getting it right increases to $$p = \frac{5}{10000} = 0.0005$$

Repeated Attacks

This seems unlikely enough at first glance. However, this probability is not negligible in the long run. It’s the same principle as rolling an unbiased die: If you do it long enough, at some point you will eventually get a six. The six, or success event, in this case is the correct OTP. This type of repeated die rolling is called a Bernoulli process in probability theory.

You can calculate the probability of guessing an OTP at least once in $n$ trials as

$$P(\text{at least 1 success}) = 1 - P(\text{no success}) = 1 - (1-p)^n$$

where $p$ is the probability of a single correct guess, as above.1 The following tree diagram clarifies this:

A tree diagram of depth 2. There are two probabilities: 1/6 to get a six and 5/6 to get no six. The probability to get no six in two trials is 5/6 * 5/6 = 25/36. As such, the probability of at least one six in two trials is 1 - 25/36 = 11/36.

Probabilities to role at least one six in two tries

For example, with $p = 0.0005$ and $n = 10000$ trials, the probability is higher than $99\%$. You can play around with this graph to get a feel for how many repetitions are needed for which values of p:

A graph showing the probabilities to have at least one success in X repetitions with P 0.0005. The graph is very steep at the beginning. With 1500 repetitions, the chance is higher than 50% already. With 3000 repetitions it’s nearly 80%. From here the graph is pretty flat. It approaches 100% probability at around 12000 repetitions.

Graph showing the probabilities of at least one success

Finally, you can use the number of repetitions to determine how long your attack will take. TOTPs are usually valid for 30 seconds. This means that one repetition takes 30 seconds. 10,000 attempts take 300,000 seconds, which is around 3 days.

Let’s summarize

With five guesses per TOTP, you can guess a 4-digit number within 3 days with a probability greater than 99%. Here is a table that shows the attack time depending on the number of digits and attempts per time step.

The table shows the attack time for attempts between 1 and 10,000 and OTPs with 4 to 8 digits. The time to guess ranges from “instantly” to 438 years.

Attack time to guess an OTP

Attacking: Increase Probabilities

The higher the base probability is, the faster the success probability approaches 100%. As an attacker, you are thus interested in increasing the probability of success. Each of the following methods is a multiplier to the base probability.

Multiple Valid OTPs

Check whether multiple tokens are valid simultaneously!

This is common for TOTPs that are used as a second factor. Usually, you can use your OTP for a certain amount of time even after the time window has expired, called the grace period.

When being used as an event-based OTP, you should check whether new tokens invalidate old ones! If two codes are valid at the same time, this already doubles the base probability.

Number of Attempts

Check how many attempts you have before the token expires!

For TOTPs, this is usually 30 seconds plus the grace period. However, since we’ve already taken this into account above, it does not change the base probability again.

For event-based OTPs, find out the number of attempts allowed. This may be a fixed number or a period again. If it is a period, keep in mind that you can increase the number of guesses drastically by threading or distributed attacks, for example by using VMs in the cloud.

Multiple Targets

Attack multiple accounts at once!

Each account increases the factor by which the probability is multiplied again. Unless you’re targeting a specific account, this can have a huge impact on your overall chance of success.

Defending: Decrease Probabilities

So much for the offense. As a defender, you want to reduce the probability of success. Let me tell you how:

Increase Complexity

The first countermeasure is fairly obvious: Increase the complexity of your OTP!

This can be done by increasing the length or the underlying character set from which the OTP is built. If this is not possible due to the chosen algorithm or for usability reasons, you must use other defenses.

Must have: Limit Number of Attempts

Strictly limit the number of guesses that can be made for an account!

Lock accounts with too many failed OTP attempts, just as you would lock accounts with too many failed password attempts. I like exponentially increasing amounts of time, such as 1 minute, then 2, then 4, then 8, and so on.

Alternatively, you can introduce different limits per day, week, and month. If a correct token is provided, the limit can be reset.

Only One Valid OTP

Have only one valid OTP at a time! This is not possible for TOTPs, where the grace period usually always allows two valid OTPs. But it is especially important for event-based OTPs. Otherwise, triggering the event multiple times increases the probability immensely.

For example, consider a password-reset feature that sends 6-digit OTPs via email, but does not invalidate old OTPs. Attackers could trigger the event as many times as they wanted, resulting in an almost certain account takeover.

Alert the Account Owner

Send email alerts whenever there is an OTP failure!

Technically, this does not reduce the probability of success. However, alerting a user that an OTP has been entered incorrectly allows them to, for example, change their password if the OTP is used as a second factor.

Wrapping up

This wraps up my blog post on brute-forcing OTPs. Did you find it valuable?

  • Share it with your friends and colleagues!

  • Follow me on Mastodon for early access to my web security content!

References

  1. You can also calculate how many repetitions $N$ you need to get a certain success probability $S$, using the formula: $$N > \frac{\log(1-S)}{\log(1-p)}$$ $p$ is the base probability of guessing the OTP.

    Example: Say $S = 99\%$ and $p=0.0005$: $$N > \frac{\log(1 - 0.99)}{\log(1 - 0.0005)} \approx 9208$$ So you need more than 9208 repetitions to have a success probability of 99%. ↩︎