↓Skip to main content

Generating one-time passwords

·5 mins
Table of Contents

We all have to log into a bunch of websites and apps. For most of these, we can just use a username/email and password approach and call it a day.

Some sites, though, are bit more important and need a stronger barrier to avoid leaking or losing your data. This is why email or financial accounts often will require multi-factor authentication (MFA).

The most common way we see this MFA is through one-time passwords (OTP). When logging into online banking for example, you may also have had to enter a 6 digit series of numbers. You might get this series of numbers from an authenticator app (eg. Google Authenticator) that you register when setting up your account login.

But how are these sequences generated? Let’s take a look!

What makes a good OTP? #

In the end, the OTP is guarding something important so being robust is a top priority.

Unguessable #

You want an approach no one could figure out from existing informatio. For instance, you don’t want a “year month day” style number because someone could just try important dates in your life.

Temporary #

This is where the one-time comes from. You want a sequence that can be used maybe for a single session, so that someone doesn’t grab one code and can reuse it hours or days to breach the account.

Not reversible #

You also want to make sure bad actors can’t reverse engineer an OTP code easily based on seeing past examples.

How can we make OTPs? #

There are a few common approaches, let’s dig into two: HMAC-based one-time password (HOTP) and Time-based one-time password (TOTP).

HMAC-based one-time password (HOTP) #

HOTP is an “event-based” OTP approach. It was first introduced in RFC 4226 back in 2005.

There are three key elements:

  • event counter that always increases
  • secret key that only the user’s device and the validating service know
  • hash function

Formula #

Here’s the formula:

$$\text{HOTP}(K,C) = \text{Truncate}(\text{HMAC-SHA-1}(K,C)) \mod 10^{\text{Digit}}$$

where:

  • $K$ is the shared secret key between client and server
  • $C$ is the counter value, an 8-byte value that must be synchronized
  • $\text{Digit}$ is the desired number of digits in the HOTP value (typically 6, 7, or 8)

Procedure #

First, generate the HMAC-SHA-1 value.

$$HS = \text{HMAC-SHA-1}(K,C)$$

Where $HS$ is a 20-byte string (160 bits).

Then, we perform dynamic truncation.

The dynamic truncation extracts a 4-byte string from the HMAC result:

$$\text{Sbits} = \text{DT}(HS)$$

Let $\text{OffsetBits}$ be the low-order 4 bits of the last byte of $HS$:

$$\text{OffsetBits} = \text{HS}[19]\&~\text{0x0F}$$

Convert $\text{OffsetBits}$ to an integer value to get the offset:

$$\text{Offset} = \text{StToNum}(\text{OffsetBits})$$

where $0 \leq \text{Offset} \leq 15$

Extract a 4-byte string starting at the offset position:

$$P = HS[\text{Offset}] \ldots HS[\text{Offset}+3]$$

To avoid signed vs. unsigned integer confusion, mask the most significant bit:

$$P = P \&~\text{0x7FFFFFFF}$$

Return the resulting 31-bit string:

$$\text{Sbits} = P$$

Compute the final HOTP Value.

Convert the 31-bit string to an integer and apply the modulo operation:

$$\text{Snum} = \text{StToNum}(\text{Sbits})$$

Where $\text{StToNum}$ converts a binary string to a number, giving a value in the range $0 \ldots 2^{31}-1$.

Then compute:

$$D = \text{Snum} \mod 10^{\text{Digit}}$$

The final HOTP value $D$ is in the range $0 \ldots 10^{\text{Digit}}-1$.

Example (for Digit = 6) #

Given an HMAC result byte array with the following hexadecimal values:

$$HS = [\text{1F}, 86, 98, 69, \text{0E}, 02, \text{CA}, 16, 61, 85, 50, \text{EF}, \text{7F}, 19, \text{DA}, \text{8E}, 94, \text{5B}, 55, \text{5A}]$$

  1. Get offset bits from last byte

$$\text{OffsetBits} = \text{5A } \&~\text{0x0F} = \text{0A} = \text{d10}$$

  1. Extract 4 bytes starting at offset 10

$$P = HS[10] \ldots HS[13] = [50, \text{EF}, \text{7F}, 19]$$

  1. Interpret as a 32-bit big-endian integer and mask the most significant bit

$$P = \text{0x50EF7F19 } \&~\text{0x7FFFFFFF} = \text{0x50EF7F19}$$

  1. Convert to decimal

$$\text{Snum} = 1357872921$$

  1. Apply modulo for 6 digits

$$D = 1357872921 \mod 10^6 = 872921$$

The final 6-digit HOTP value is $872921$.

Time-based one-time password (TOTP) #

As the name might suggest, this is a time based generation. TOTP was introduced several years later than HOTP and its official RFC was adopted in 2011.

Of note, TOTP builds upon HOTP.

To support TOTP generation, we still need the following:

  • secret key that only the user’s device and the validating service know
  • hash function

The new element we need is a time based counter that both the user’s device and validating service follow in lockstep.

Formula #

TOTP is defined like so, building upon HOTP:

$$\text{TOTP} = \text{HOTP}(K, T)$$

where:

  • $K$ is the shared secret key
  • $T$ is an integer representing the number of time steps between the initial counter time $T_0$ and the current Unix time

Procedure #

Calculate the time counter value T

Calculate the number of time steps that have occurred since $T_0$: $$T = \text{floor}\left(\frac{\text{CurrentUnixTime} - T_0}{X}\right)$$

where:

  • $T_0$ is the Unix time to start counting time steps (default is 0, i.e., Unix epoch)
  • $X$ is the time step in seconds (default is 30 seconds)
  • $\text{floor}$ is the function that rounds down to the nearest integer

For example, with $T_0$ = 0 and $X$ = 30 seconds:

  • $T$ = 1 if the current Unix time is 59 seconds
  • $T$ = 2 if the current Unix time is 60 seconds

Apply the HOTP algorithm using T as the counter

The rest of the calculation follows the HOTP algorithm described earlier:

$$\text{TOTP} = \text{HOTP}(K, T) = \text{Truncate}(\text{HMAC-SHA-1}(K, T)) \mod 10^{\text{Digit}}$$

Where the truncation and modulo operations are performed exactly as in HOTP.

Some implementation notes #

  • Generally a time step of 30 seconds is recommended. Much longer means more potential for attacks, and shorter makes it hard for the actual person trying to authenticate to enter the code

  • Since TOTP relies on time, clock drift between the client device and validation server can cause validation failures. The RFC recommends two things:

    • Being a bit more forgiving of matching time steps (accepting 1 more/lesser time step than the current)
    • Provide a way to resync clocks when drift is detected