---
title: Understanding Time-based One-time-password
date: 2022-04-28
slug: understanding-totp
authors:
- lunik
description: Deep dive inside the TOTP protocol
related_posts:
  - manage-x509-certs
  - secure-home-entrypoint
tags:
- security
- 2fa
- totp
- two-factor
- authentication
- otp
- hmac
- hotp
---


<!--
# CHANGELOG

-->

![cover](/blog/img/posts/2022-04-28-understanding-totp/cover.png)

Now that every web service encourage you, more and more, to use [MFA][mfa-wikipedia] to secure your account, one of them is used most than others : [Time-based one-time password or TOTP][totp-wikipedia] generate a unique code of `6` or more numbers to enter just after typing your password.

The server or web app allowing to setup [TOTP][totp-wikipedia] give a [QRCode][qrcode-wikipedia] to scan (or a [Base32][rfc-4648] string) to configure in a [TOTP][totp-wikipedia] generator app like [Microsoft Authenticator][ms-authenticator-site], [Google Authenticator][google-authenticator-site], [Bitwarden][bitwarden-site] or more.

We all use it, but how does it work ? Is it secure ? Is my account secure when using third-party [TOTP][totp-wikipedia] generator ??

<!-- truncate -->

## The protocol

I will get deeps into the details of the underlying protocol allowing you to generated [TOTP][totp-wikipedia] and how the server verify it.

### Basics

The basic idea is pretty straight forward. You and the server shared a secret, a `16` character long [Base32][rfc-4648] string (sometimes stored in the [QRCode][qrcode-wikipedia]). Then you both synchronize your clocks.

Finally when you want to login, you execute a fancy magical function and ultimately you get a [TOTP][totp-wikipedia].
The server compute the [TOTP][totp-wikipedia] on his side and ask you the one you generated on your side. If both of the [TOTP][totp-wikipedia] match, the server allow you in.

### TOTP protocol

Let's dig into the [TOTP][rfc-6238] protocol. According to the [RFC 6238][rfc-6238] you need :

- A moving `counter` that must be synchronized between the two parties
- A `secret` shared between the two parties

The `counter` is calculated base on [epoch][epoch-wikipedia] time (That way everybody is synchronized) with the following formula :

```
C = (T - T0) / X
```

With :

- `C` the counter value
- `T` the current Unix time in seconds since [epoch][epoch-wikipedia]
- `T0` an arbitrary start Unix time. `0` by default
- `X` the time step in seconds or the frequency of code update. `30` by default

If we try to make a [Python][python-site] implementation, it will looks like :

```python
t0 = 0
# https://docs.python.org/3/library/time.html#time.time
current_unix_time = time.time()
time_step = 30

counter = int((current_unix_time - t0) / time_step)
```

```python
current_unix_time: 1651094239.491242


counter => 55036474
```

Now the [TOTP][rfc-6238] value can be retrieved with the following formula :

```
TOTP = HOTP(K, C, D)
```

With:

- `C` the counter value
- `K` the secret key
- `D` the number of digits in our [TOTP][rfc-6238]s
- `HOTP` the magical function that calculate the OTP

In [Python][python-site], we get :

```python
counter = 55036474
key = "ABCDEFGHYJKLMNOP"
digits = 6

totp = hotp(key, counter, digits)
```

```python
totp => 934929
```

### HOTP protocol

This second protocol is used to calculate a unique value a counter value and the secret key. From the [RFC rfc4226][rfc-4226], we learn that its based on [HMAC hash protocol][rfc-2104].

Sit tight because it will begin to be challenging and I hope that your are comfortable with binaries operations.

#### Handle inputs

First of all, we need handle the 2 of our 3 input parameters : `counter`, `key`

- `counter` needs to be converted into an `unsigned long long` and `big-endian` bytes array value.

In [Python][python-site] :

```python
import struct
# https://docs.python.org/3/library/struct.html#struct.pack
# https://docs.python.org/3/library/struct.html#byte-order-size-and-alignment
# https://docs.python.org/3/library/struct.html#format-characters
bytes_counter = struct.pack('>Q', counter)
```

```python
counter: 55036474


bytes_counter(bin) => 00000011 01000111 11001010 00111010
bytes_counter(hex) => 03 47 ca 3a
```

- `key` should be a valid [Base32][rfc-4648] string. The [RFC 4648][rfc-4648] tells us that the string length need to be a factor of `8`. So padding can be added with char `=` at the end if it's too short. For example : `AA` => `AA======`, `BBBBBBBBBB` => `BBBBBBBBBB======`, `CCCCCCCC` => `CCCCCCCC`

```python
padding = '=' * ((8 - len(key)) % 8)
valid_key = key + padding
```

```python
key: ABCDEFGHIJKLMNOP


valid_key => ABCDEFGHIJKLMNOP
```

Then we convert the updated key in bytes array value :

```python
import base64

bytes_key = base64.b32decode(key)
```

```python
valid_key: ABCDEFGHIJKLMNOP


bytes_key(bin) => 10001000 01100100 00101001 10001110 10000100 10101001 01101100 0110101 11001111
bytes_key(hex) => 44 32 14 c7 42 54 b6 35 cf
```

#### Calulate HMAC

Using the [RFC 2104][rfc-2104] we can understand how the [HMAC function][rfc-2104] work. We need to choose an hash function. [HOTP][hotp-wikipedia] or [RFC 4226][rfc-4226] use the [SHA-1][rfc-3174] cryptographic hash function.

[Python][python-site] implement [HMAC library][python-hmac-doc] :

```python
import hmac

# Calculate the HMAC-SHA1 value
# Produce a 20 bytes (or 160 bites) long string
mac = hmac.new(bytes_key, bytes_counter, "SHA1").digest()
```

```python
bytes_counter(hex): 03 47 ca 3a
bytes_key(hex): 44 32 14 c7 42 54 b6 35 cf


mac(bin) => 10110100 11010010 01111010 10110100 10111101 00110101 11111110 00100011 11101101 01011001 01111110 10111100 11110000 01111001 11000001 01001010 00000110 01101100 01010001 00101111
mac(hex) => b4 d2 7a b4 bd 35 fe 23 ed 59 7e bc f0 79 c1 4a 06 6c 51 2f
```

#### Calculate HOTP

Following the [RFC 4226][rfc-4226] section `5.3`.

##### Finding offset

We first need to find the `offset` value by getting the least significant `4` bits of the `MAC` (The `4` on the right)
using [bitwise AND operation][bitwise-and-operation-wikipedia]

In [Python][python-site] `&` can be used to make binary `AND` operation between two number. With the value `0x0F` (in hexadecimal and equivalent to `00001111` in binary) we can extract two `4` last bits. Since `offset` is an integer stored on `4` bits, the value is between `0` and `15`. In [Python][python-site] we can use `mac[-1]` to get the last byte of the bytes array converted in an integer.

```python
offset = mac[-1] & 0x0F
```

```python
mac(bin): 10110100 11010010 01111010 10110100 10111101 00110101 11111110 00100011 11101101 01011001 01111110 10111100 11110000 01111001 11000001 01001010 00000110 01101100 01010001 00101111
mac(hex): b4 d2 7a b4 bd 35 fe 23 ed 59 7e bc f0 79 c1 4a 06 6c 51 2f


offset(bin) => 1111
offset(hex) => f
offset(dec) => 15
```

##### Finding the dynamic truncation

Using the previously found `offset`, we are going to extract the `Dynamic Truncation` from the `MAC`. We need to retrieve the `4` bytes at position `offset`, `offset+1`, `offset+2` and `offset+3` in the `MAC` bytes array.

We got :

```python
dynamic_truncation = mac[offset:(offset+3)+1]
```

In [Python][python-site] the value after the `:` is not included. In order to extract `offset+3` value, we need to put `(offset+3)+1`

```python
offset(bin): 1111
offset(hex): f
offset(dec): 15

offset(dec) from 15 to 18

mac(bin): 10110100 11010010 01111010 10110100 10111101 00110101 11111110 00100011 11101101 01011001 01111110 10111100 11110000 01111001 11000001 01001010 00000110 01101100 01010001 00101111
mac(hex): b4 d2 7a b4 bd 35 fe 23 ed 59 7e bc f0 79 c1 4a 06 6c 51 2f


dynamic_truncation(bin) => 10010100 00001100 11011000 1010001
dynamic_truncation(hex) => 4a 06 6c 51
```

##### Extract the 31 bits

Finally we are going to extract the least significant `31` bits from our `Dynamic Truncation`
The solution would be to convert the result bytes array into un signed long witch is `32` bits with the most significant bit (on the left) containing the signed value (`+` or `-`).
Using the same trick as earlier, we use [bitwise AND operation][bitwise-and-operation-wikipedia] to extract them.
`0x7fffffff` (in hexadecimal and equivalent to `01111111 11111111 11111111 11111111` in binary). Resulting in a 31 bit value when ignoring leading 0.

```python
# https://docs.python.org/3/library/struct.html#struct.unpack
extract_31 = struct.unpack('>L', dynamic_truncation)[0] & 0x7fffffff
```

```python
dynamic_truncation(bin): 10010100 00001100 11011000 1010001
dynamic_truncation(hex): 4a 06 6c 51


extract_31(bin) => 10010100 00001100 11011000 1010001
extract_31(hex) => 4a 06 6c 51
extract_31(dec) => 1241934929
```

##### Truncate digits

Now that we have our final number after extracting the last `31` bits, we need to truncate the decimal value this time. Based on the configured `digits` value, we want to only keep the `X` last numbers of the decimal value of the `extract_31`.
`X` is the length of the [TOTP][rfc-6238] code we want and should be between `6` and `10`.
`6` minimum because of security requirement and `10` maximum because the max value of a `32` bit signed integer is `2147483647`, a `10` number value.

Using a length of `10` over `9` doesn't add that much security because the leading number can only take `0`, `1`, `2` value.

```python
digits_count = 6

hotp = str(extract_31)[-digits_count:]
```

```python
extract_31(dec): 1241934929

digits_count: 6


hotp => 934929
```

In the case where `extract_31` is a too low value where the number of digits is lower than `digits`, we add leading `0` at the left of the [HOTP][rfc-4226] code to make it the right length.

```python
hotp = hotp.zfill(digits_count)
```

```python
hotp: 934929

hotp => 934929
```

## Conclusion

Now you really know how [TOTP][rfc-6238] codes are generates. As we can see, it's pretty simple and you can develop your own script to generate them.

## Full code

```python
import base64
import hmac
import struct
import time

def hotp(counter, key, digits_count=6):
  bytes_counter = struct.pack('>Q', counter)

  key = key + '=' * ((8 - len(key)) % 8)
  bytes_key = base64.b32decode(key)

  mac = hmac.new(bytes_key, bytes_counter, "SHA1").digest()

  offset = mac[-1] & 0x0F
  dynamic_truncation = mac[offset:offset+4]
  extract_31 = struct.unpack('>L', dynamic_truncation)[0] & 0x7fffffff

  return str(extract_31)[-digits_count:].zfill(digits_count)


def totp(key):
  counter = int(time.time() / 30)

  return hotp(counter, key)


if __name__ == "__main__":
  key = input("Enter secret key : ").upper()

  print("TOTP code :", totp(key))

```

## References

- [TOTP: Time-Based One-Time Password Algorithm][rfc-6238]
- [HOTP: An HMAC-Based One-Time Password Algorithm][rfc-4226]
- [The Base16, Base32, and Base64 Data Encodings][rfc-4648]
- [HMAC: Keyed-Hashing for Message Authentication][rfc-2104]
- [US Secure Hash Algorithm 1 (SHA1)][rfc-3174]

- [Multi-factor authentication][mfa-wikipedia]
- [Time-based one-time password][totp-wikipedia]
- [HMAC-based one-time password][hotp-wikipedia]
- [QR code][qrcode-wikipedia]
- [SHA-1][sha-1-wikipedia]
- [Bitwise operation][bitwise-and-operation-wikipedia]
- [epoch][epoch-wikipedia]
- [Python HMAC lib][python-hmac-doc]

<!-- links -->

[rfc-6238]: https://tools.ietf.org/html/rfc6238
[rfc-4226]: https://tools.ietf.org/html/rfc4226
[rfc-4648]: https://tools.ietf.org/html/rfc4648
[rfc-2104]: https://tools.ietf.org/html/rfc2104
[rfc-3174]: https://tools.ietf.org/html/rfc3174
[mfa-wikipedia]: https://en.wikipedia.org/wiki/Multi-factor_authentication
[totp-wikipedia]: https://en.wikipedia.org/wiki/Time-based_one-time_password
[hotp-wikipedia]: https://en.wikipedia.org/wiki/HMAC-based_one-time_password
[qrcode-wikipedia]: https://en.wikipedia.org/wiki/QR_code
[sha-1-wikipedia]: https://en.wikipedia.org/wiki/SHA-1
[bitwise-and-operation-wikipedia]: https://en.wikipedia.org/wiki/Bitwise_operation#AND
[epoch-wikipedia]: https://en.wikipedia.org/wiki/Epoch_(computing)
[ms-authenticator-site]: https://www.microsoft.com/en-us/security/mobile-authenticator-app
[google-authenticator-site]: https://support.google.com/accounts/answer/1066447
[bitwarden-site]: https://bitwarden.com
[python-site]: https://www.python.org
[python-hmac-doc]: https://docs.python.org/3/library/hmac.html