One-Time Passwords, or OTPs are a widely used authentication factor in many online services, big and small. When I’m not ranting about them, I actually think they’re pretty good. So, today is not another attack on OTP or multi-factor authentication, but instead, an effort to educate people about how they work and what we need to do to ensure we stay safe. There are some misconceptions out there, so let’s try to correct them.

What’s the purpose of an OTP?

We are all familiar with when OTPs are used: To login to something. They are an authentication factor, in this case something you have rather than something you know or are. Why are they something you have rather than something you know? The OTP is generated or shown to you with something in your possession, be it a token, telephone or e-mail address. You can’t remember OTPs like you can passwords, unless you can memorise keys and perform HMACs or random number generation in your head…

OTPs tend to be used as additional authentication factors, on top of traditional passwords, to introduce two-factor or multi-factor authentication (2FA or MFA). They can be used as the only factor, however. I know some websites that e-mail me a code to login without asking for a password. Are OTPs safer than passwords? In some ways, yes — you can’t leave them attached to your monitor on a sticky-note. Regardless, my opinion is that OTPs don’t negate the need for MFA if we want to have some defence in depth to an authentication process.

How does an OTP work?

While there’s all manner of ways to make an OTP, I’ll lean heavily on RFC 4226: HOTP and RFC 6238: TOTP. HOTP stands for HMAC-based One-Time Password, while TOTP is Time-based One-Time Password, although it also uses HMAC. Confused? Let’s take a look at them both.

HOTP

The original HOTP process from RFC 4226 relies on HMAC using SHA-1 hashes. A key is shared between client and server and a counter value is synchronised between both as well. When an OTP is needed, the client computes a new HMAC based on the key and current counter value. This HMAC is then truncated and then converted to a format that’s easier for the client to manually enter. The most common format is six numerical digits, shown in the diagram below:

The HMAC is dynamically truncated, meaning rather than simply slicing the front or back off the HMAC, the offset into the HMAC is calculated based on the least significant four bits of the last byte in the HMAC. So, for a 20 byte (160 bits) HMAC-SHA-1, bits 152:155 are used to determine at which byte in start taking the truncated value. A total of 31 bits are extracted from this offset.

In the conversion from bytes to a decimal value, these 31 bits are further truncated modulo the number of digits required. The specification requires six digits be supported as a minimum, but seven and eight may also be provided. With only 31 truncated bits to work with, using a larger number of digits than eight may be a problem.

The designers of HOTP went to some lengths to prove that these dynamically truncated 31 bits are very close to uniformly distributed in probability across the HMAC output with each key/counter input. The counter is defines as an 8 byte value, meaning it would take 2^64 OTPs to wrap around, making it effectively non-wrapping in practical use cases. The key length is not specified, but should be long enough to be safe against brute force versus any other brute force methods against the algorithm.

TOTP

Time-based OTP is essentially HOTP with a little bit of extra effort. Instead of a simple counter directly, we derive a counter value from the current time. We take the current Unix time (the number of seconds since midnight GMT/UTC on 1st Jan 1970), divide that into intervals (usually of thirty seconds), and use that interval count as our counter value. Everything else is the same.

Assuming the token generator and the server have clocks that are reasonably accurate and in sync, they can agree what the current OTP value should be. Some systems will even allow the previous and next one or two OTPs to be used, just in case the clocks are off a little, as giving somebody one, three or five guesses out of one million is of little consequence.

TOTP also allows the use of newer hash methods, namely SHA-256 and SHA-512 from the SHA2 standard. The rest of the algorithm remains the same.

Unix time tends to be an 8 byte value these days, meaning it will wrap in around 247 billion years. However, it is possible that systems which store the time in a smaller width may wrap around sooner. So it might be a good idea to generate new TOTP keys before 19th January 2038 and every 68 years thereafter.

Other OTP

It’s possible to generate OTPs in other ways. For example, one could generate an entirely random number and send it to somebody to use as an authentication factor, after which a new one will need to be generated the next time an OTP is needed. If the random number generation is good, it’s impossible to ever guess the OTP value. But, the OTP could be intercepted on its way to the user. This is why SMS-based OTP sucks — the strength of the OTP is irrelevant if it can be stolen through something like a SIM swapping attack.

There are also other kinds of codes that are used in a one-time sense, but don’t fit the scope of this article because there isn’t the same human element in their exchange. For example RFC 7636 uses a proof key over a code (that’s a lot more complex than just a few digits) to get an access token after an OAuth authorization has taken place.

Regardless of what OTP method we’re talking about, the exchanges of codes usually depends on the following properties:

• The server stores something unique to the client it’s trying to authenticate.
• The client is able to generate or securely receive a code that relates to what the server stores in some determinable way.
• Nobody else should be able to figure either of these things out

What needs protecting

Regardless of how an OTP is generated, three main things need to be ensured:

1. Any secret involved in generating the OTP is not leaked
2. An attacker cannot spam the system with guesses
3. Any currently or soon to be valid OTP is not leaked

In other words, if an attacker knows your secret, they can generate an OTP for themselves, or if they can make one million guesses very quickly, they’re going to find the current correct value in the end. The former requires storing keys safely, while the latter requires rate-limiting attempts so that brute-force cannot be applied to the OTP value. Let’s assume that the secret, if one exists, is strong enough that a brute-force attack on that is much harder than a brute-force attack on the OTP value itself.

The third point should be obvious, but let’s talk about that next…

What happens if somebody learns my OTP?

If somebody learns your OTP and can use it before you do, or re-use it within a time-window where it’s still valid, then they can potentially authenticate as you. This is bad.

For this to work, they probably already have other credentials of yours, such as username, e-mail, password, etc. Maybe this is all part of a sophisticated phishing attack.

Once the attacker has used the OTP to get into your account, they might update your security settings and take over the account for themselves. They might register a new token and start siphoning money out of your bank account. Again, this is bad.

This is why you don’t share OTPs with anyone. This is why you should be careful about where you enter your OTP. For example, is the page you’re on really your bank? Better check the address bar just to be sure.

What if my old OTPs get leaked?

This is where some people get confused. Old OTPs that are no longer valid don’t matter. If an attacker gets hold of them, it tells them nothing, other than perhaps when you used each OTP and what its value was. But that doesn’t help them guess any future OTP value.

Why not?

If we stick to six digit OTPs for simplicity, one intuition we might have is that by observing several OTPs, an attacker can work out the sequence and either predict some future value, or when a particular value will occur again. There’s only one million possible OTP values, right? While that’s true, the limited length of the OTP only matters for brute-force attacks, and that’s defended against already through rate-limiting.

OTP values are not cyclical. Once we see a value, we have no idea when it will appear again, unless we know both the counter value and the secret. The counter value (practically) never wraps — it just keeps getting bigger (or in the case of TOTP, time never goes backwards). The input to the OTP’s hash function is always unique, and while the output is short, the properties of that hash function should make the output unpredictable. So, only if there’s a weakness in the hashing algorithm would this potentially stop holding up.

Here’s a quote from RFC 4226 that supports this:

Assuming an adversary is able to observe numerous protocol exchanges and collect sequences of successful authentication values. This adversary, trying to build a function F to generate HOTP values based on his observations, will not have a significant advantage over a random guess.

In other words, brute-force will always be the best option, and we’ve got an answer to that already: rate limiting/throttling.

An example

The following example does not serve as formal proof of the property I’m discussing, but it should be enough to dispel the misconception about leaking old OTPs. If you are interested in more detailed information on the security properties of this particular kind of OTP, I suggest starting with RFC4226 Appendix A. The code for this example is kept on GitHub so you can try it for yourself.

$ python otpwalk.py --mode hotp --limit 5000

After 5000 iterations
----------------------------------

Secret: 2Z5OH43QM7SJGAVAB6564B7YYDRNJVA3
Number of duplicates: 10
Dupe occurrences and values: {2: {812740, 234857, 849706, 288939, 326252, 146993, 204913, 510739, 958163, 308702}}
Intervals between dupes: [1861, 770, 267, 2291, 3082, 245, 1792, 1022, 516, 3110]
Average dupe interval: 1495

Here we see the duplicates detected after 5,000 HOTP codes have been generated. That’s equivalent to over 41 hours of TOTP codes with a 30 second interval. We see that despite only being 0.5% of the way to 1,000,000 codes, we’ve seen ten values twice. These values seem to reoccur after a few hundred, or few thousand codes, 1.5K on average. If we run it again, we’ll get a new secret key and some different statistics.

$ python otpwalk.py --mode hotp --limit 5000

After 5000 iterations
----------------------------------

Secret: HHFTI23OY4VFLDJIPBG3VRTUAJNKBZRK
Number of duplicates: 11
Dupe occurrences and values: {2: {430690, 469666, 478567, 150056, 257355, 16844, 969100, 527118, 193998, 844474, 892923}}
Intervals between dupes: [316, 870, 1908, 1286, 134, 531, 1741, 2960, 2299, 3248, 3238]
Average dupe interval: 1684

If we double the iterations, we see more duplicates:

$ python otpwalk.py --mode hotp --limit 10000

After 10000 iterations
----------------------------------

Secret: M7K23GSBEJB3CLVWKUBPULFB5DVSLVO3
Number of duplicates: 39
Dupe occurrences and values: {2: {342912, 3329, 341891, 211335, 990345, 933770, 885899, 625422, 661778, 587925, 882467, 386725, 395688, 194729, 189738, 325165, 95278, 282931, 247987, 514486, 382007, 674363, 356284, 530878, 180416, 130370, 262851, 226121, 112719, 459866, 962779, 495967, 590825, 32361, 19698, 716533, 739064, 800889, 583292}}
Intervals between dupes: [57, 763, 298, 2309, 2736, 681, 1456, 1521, 1104, 3435, 2500, 4870, 4425, 3955, 2185, 1582, 725, 2778, 3922, 331, 6627, 3834, 7738, 5421, 1312, 752, 8552, 1471, 5366, 3083, 8669, 7802, 8551, 5817, 7097, 8700, 3890, 471, 8500]
Average dupe interval: 3725

The average duplicate interval is going up, because some values won’t repeat for a significant number of iterations. For very high iteration counts, I suppose this would approach 1,000,000. After around 10,000 – 20,000 HOTP codes, I tend to see a value appear for a third time.

The most important thing to take away from this example, is that while some values will be duplicated quite quickly, we have no idea which values they will be, or when. That’s all hidden behind the secret key, hash function and a counter value that’s got far more bits in it than the OTP codes have.

Feel free to clone/fork this repository and play around with it for yourself.

Conclusion

In this article I’ve explained what OTPs are and how one of the most widely used approaches — HMAC-based OTP — works, along with its derivative Time-based OTP. I’ve then addressed some of the security considerations around OTPs, including what happens if an OTP is leaked. Importantly, I’ve explained why leaking of previous OTPs (once outside of their validity window) doesn’t help an attacker in any meaningful way, assuming a good algorithm like HOTP is used.

It’s still not a good idea to leak your past OTP values. That’s getting dangerously close to leaking a current OTP value, so in terms of hygiene, I would still recommend against it. But, if it does happen, now you know why it’s not the end of the world. As always though, if you do have any doubts, you can reset passwords and keys, request new tokens and whatever else you need to do to keep your accounts secure. Just be mindful that the reset process itself can be risky, especially if it’s triggered at the behest of somebody with ill-intentions. A calm head, critical thinking and an understanding of how things work will always make a scammer’s life harder and help the rest of us sleep better at night.