I took some time to understand how One-Time passwords work.

Sometimes technology feels like magic. I'm not a big fan of magic, so in those cases I like to get a basic understanding.

One-Time Password?

The technology I'm talking about is when you log in to a website, you do not only give your username and password but also some numerical code. "789456", for example.

The code is texted to you or generated by an app (for example Google Authenticator).

Then, somehow, the website checks if the number is correct and lets you log in.

It's "One-Time" because once used, you cannot use that same number ever again. Or at least not any time soon.

Magic!

Questions

I asked myself some questions:

  • How does the website know which password to expect?
  • How can it work when the password is generated offline?
  • How is the password generated?

Summary (TL;DR)

One way for this to work is with the HOTP (HMAC-Based One-Time Password) algorithm:

  • Client and server share a "key" (large random number) and a "counter" value (number)
  • Each "key" and "counter" combination results in an unpredictable One-Time password (e.g. "789456")
    • Thanks to an "HMAC" algorithm
  • The server knows the password for the next 100 or so counter key-counter combinations
  • The client sends the password for the current counter value and then increments its local counter by 1
  • If it's one of the expected passwords, the server also updates its own counter to match the local counter
    • This ensures the same password can't be used again

A variant exists where the counter is replaced with a time value. This is called TOTP (Time-Based One-Time Password).

Please read on if you want more details.

Shared Secrets

The reason this works is because you and the website share a secret. Two actually.

You share a "key" and a "counter" value.

The key is a really long number, generated randomly by the website. It's something that must be kept secret. Only you and the website can know it.

The counter is a number that is incremented every time a password is generated. The counter is not really a secret, because it just increments sequentially and could be easily guessed.

The key doesn't change a lot, the value of the counter does.

Both you and the website know the key and the current counter value. With these two numbers it's possible to generate a password. Both you and the website can generate the same passwords because you both know the key.

You generate a password locally and send it to the website. The website then checks if the key with the current counter value would produce that password.

If you can generate the same password the website is expecting, that means you know the key and the counter value.

Offline

It can work offline if you use an app, such as Google Authenticator. This is because the "key" and "counter" value are stored on your phone.

When using SMS, the system technically doesn't work offline but you use a second communication channel: the website generates a OTP and sends you an SMS.

In the latter case, you do not know the key or counter value. Only the website knows. If you can give the expected password, all that really proves is you received the SMS from the website.

How is the password generated?

This is where it gets interesting. We need something that can generate a password using a "key" and the "counter" value.

This something is an algorithm called HOTP can do. HOTP stands for "HMAC-Based One-Time Password".

It works somewhat as follows:

  • Given a key, generate the "HMAC-SHA1" hash for the "counter" value: this results in 20 bytes (a byte is a number between 0 and 255).
  • From those 20 numbers, derive a number with a fixed number of digits (typically 6 digits). For example: "145987"

Log-in using a One-Time Password

When you generate a code to log in, the last known counter value is used in combination with the key to generate a password. The counter is incremented by 1 and saved locally.

Note that on the website, the counter is now 1 behind on your local copy.

Then you send that password to the server.

The website also knows the previous counter value, so it can also generate the password. Then it will compare the passwords.

If both match, authentication is succesful. In that case the website saves the new counter value. So both your local copy of the counter and the one on the website are again in sync.

Look-ahead Window

What happens if you generate the 10 next codes locally without sending anything to the website?

Your local counter will be 10 values higher than the one known on the website.

If you then send the 11th code, the website will not recognize it.

Because of this, the website prepares a number of passwords in advance. For example, it will generate the passwords for the current counter value and the 100.

The amount of passwords to predetermine is called the "look-ahead window".

If a code comes in, the website can check if it is one of the next 100 codes. If it is the 50th code of the 100, the website can adjust its counter value by 50 instead of 1.

It's important to update the counter, because this ensures the same code can't be valid twice. Unless it logically occurs again in the look-ahead window, but this is rare thanks to HMAC-SHA1.

If you generate too many codes without telling the website, you and it can run "out of sync". In that case, special steps need to be taken to re-align the counter values.

HMAC-SHA1

HMAC-SHA1 is an algorithm that given a key and an input can generate an unpredictable 20-byte number.

It's unpredictable because a small change in the input will generate a completely different 20-byte number.

The 20 bytes HMAC-SHA1 generates must be unpredictable, so that the derived password is very different on every counter increment.

Otherwise, it would be easy to guess the next few passwords if you have seen some previous passwords.

Derive the Password

To derive a password from the 20-byte HMAC-SHA1 the HOTP algorithm defines a "Truncate" process.

It does the following:

  • Take the first 4 bits of the 19th number (the last the number), let's call the number "n"
    • The result will be a number between 0 and 15
  • Take the n'th number of the 20-byte HMAC-SHA1 data, and the three following numbers.

These four numbers combined are the derviced password.

Additional Information

I left a few details out in the above.

Time-Based One-Time Passwords

Next to HOTP there is also "TOTP" (Time-Based One-Time Password).

In this variation, the "counter" value is replaced by the current time (in 30 second intervals).

This is used, for example, by the Google Authenticator app. Which is why that app is continuously generating new codes that expire quickly.

TOTP relies on both your phone and the website knowing the exact time. Typically, the time is kept in sync through an external "Internet Time" service.

The time difference between the website and your phone must be within an acceptable time-window. This is similar to the look-ahead window in HOTP.

Key Sharing

Sharing the Key is an important aspect. It has to be shared securely. Google Authenticator does this by letting you scan a "QR-code" which represents the key value.

Sometimes a "hardware-token" is used. Which is a physical device that can show the password. It has the key built in before it is shipped to a customer.

This is used a lot to log in to corporate networks or VPN's (Virtual Private Networks). An example is "RSA SecurID".

HMAC-SHA1

I didn't explain how this algorithm works. I do not feel it is that important here. Although it is interesting by itself.

It uses a hashing algorithm (SHA1) to "sign" data using a known "key".

Security Considerations

There are a lot of security considerations:

  • The key must remain a secret
  • SMS messages with the One-Time Password could be intercepted
  • The longer the password, the more secure it is

Car Keys

As a side-way, car-keys that let you open a car by clicking a button on the key sometimes work in a similar way.

When you click the button, a password is generated and sent to the car. The car knows the next passwords to expect and checks if its valid.

It may not be exactly HOTP or TOTP, but it's possibly something like that.

I've heard that if you press you car-key button enough times while out of range of the car you can overrun the look-ahead window, rendering your key useless. I haven't tried.

I don't know the details, so it could be some cars use other mechanisms.

Bank Authentication

Banks, in Belgium at least, all use a system where a user is provided with "challenges" they have to enter into a small calculator-like machine.

The challenge in combination with the chip-card and pin-code results in a response that is sent to the bank.

This works differently, it uses public-private key pairs as opposed to a shared-key.

Conclusion

The One-Time Passwords may seem like magical telepathy. But when you look under the hood, it can make sense.

The way it works:

  • Client and server share a "key" and a "counter" value
  • Each "key" and "counter" pair results in a hard to predict password
  • The server knows the next x number of passwords to expect for the current counter value
  • The client sends a password it just generated, and increments its local counter
  • If one of the expected passwords, the server also updates its own counter to match the local counter

A variant exists where the counter is replaced with a time value.