Understanding the Time-Based One-Time Password (TOTP) Algorithm Used for Multi-Factor Authentication (MFA)

Using multi-factor authentication is a commonly recommended practice for securing user accounts, and it’s available across a range of services today such as Gmail, AWS, Azure, Facebook, Twitter, etc. One of the methods for MFA is to use a third party mobile app like Google Authenticator to generate security codes that are verified by the service. How does this work exactly?

Set Up

Let’s take AWS MFA as an example.

First the user installs a third party app like Google Authenticator, typically on a mobile device that acts as the second factor. When setting up MFA in AWS, the user chooses to use a “virtual MFA device.” The virtual MFA device is the third party app.

The user can then use the third party app to either scan a QR code, or manually enter a shared secret. Either method is equivalent – the important part is getting the shared secret into the third party app. In the case of the QR code, the shared secret is encoded within the QR code to make it easier for the user to bring it into the app.

The TOTP Algorithm

Once the third party app has the shared secret, it starts generating security codes. The mechanism behind generating these codes is the Time-Based One-Time Password (TOTP) algorithm, described in RFC 6238 and RFC 4226. Here’s how it works.

First, the algorithm is initialized with a set of parameters:

  • Shared Secret: This is Base32-encoded, meaning each character represents 5 bits. The number of bytes varies from service to service. For instance, as of this writing, Gmail is using 20 byte keys and AWS is using 40 byte keys. The number of bytes beyond a certain point doesn’t significantly increase the strength of the algorithm.
  • Digits: How many digits the security code will have. The common default (used by Google Authenticator) is 6 digits.
  • Period: The interval of time over which any given security code is valid. The common default (used by Google Authenticator) is 30 seconds. After 30 seconds elapses, a new security code is generated.
  • Algorithm: The hashing algorithm used to generate security codes. The common default (used by Google Authenticator) is SHA-1.

Here’s an example of what it looks like in Python (imports excluded):

secret = base64.b32decode('W2ASCT52EGQLJ42I5THBMEK2BYJ3Q5JRKIZLSEPNN4YW3KSLWQTH2LRSPAVUFFAY')
digits = 6
period = 30
algorithm = hashlib.sha1

Then a moving counter value is calculated using the current time, represented as Unix seconds since the epoch (Jan. 1, 1970). The current time is divided by the TOTP period, and this value is rounded down (floored) to get a whole number. This whole number is converted to an 8 byte message.

t = math.floor(time.time())
# t = 1561168683, which corresponds to June 21, 2019 21:58:03 PM EST

counter = t // period
# counter = 52038956

counter_bytes = counter.to_bytes(8, byteorder='big')
# counter_bytes = 0x00000000031a0d2c

Next, a hash-based message authentication code (HMAC) is computed using the shared secret as the key, the moving counter as the message, and the hashing algorithm.

digest = hmac.new(secret, msg=counter_bytes, digestmod=algorithm).digest()
# digest = 0x370ec53937030234a743b62294252c416f4fa6e4

HMACs have two properties that are helpful in the context of TOTP:

  • They are pseudo-random functions, making it hard to predict the next output given prior outputs.
  • It’s very difficult, given an output or multiple outputs, to figure out what the shared secret is.

In the case the algorithm is SHA-1, the output digest of HMAC is 20 bytes long.

These 20 bytes are then converted into a security code. The value of the last 4 bits of the digest is treated as an offset into the digest. The offset is used to selects 4 bytes (32 bits) in the hash. The first of these bits is stripped to create a 31 bit integer. This integer is then truncated to be 6 digits base 10 using the modulo (remainder) operator. The resulting code is left-padded with zeros if it’s less than 6 digits.

offset = digest[-1] & 0x0F
# offset = 4

v_bytes = [ digest[offset] & 0x7F, digest[offset+1], digest[offset+2], digest[offset+3] ]
# v_bytes = [0x37, 0x03, 0x02, 0x34]

v = int.from_bytes(v_bytes, byteorder='big')
# v = 922944052

code = str(v % (10**digits))
code = (digits - len(code))*'0' + code
# code = 944052

Verification

To verify that a user’s security code is valid, the service receiving the code simply generates the code on its end using the same shared secret and compares it to the user’s provided code.

For verification to work, the service’s current timestamp must be in sync with the user’s current timestamp so that both sides generate the same code. In practice, because of network delays, clock drift, and the time it takes a user to enter a code, services typically also accept codes within a small window of time (30 seconds to a minute) around the actual time.

Time Code
2019-06-21 21:57:00 440073
2019-06-21 21:57:30 457776
2019-06-21 21:58:00 944052
2019-06-21 21:58:30 526587
2019-06-21 21:59:00 202643

Conclusion

Here’s a gist with the full example.

Leave a Reply

Your email address will not be published.