Implementing Your Own Time-Based OTP Generator
Tags: python, tutorial, programming, cybersecurity
Published: 2023-02-20 03:33:04


## **Implementing Your Own Time-Based OTP Generator**


Recently I came across a coding challenge that required challengers to generate their own Time-Based One-Time Password (TOTP) following a set of pre-defined rules. It required a basic understanding of the TOTP standard defined in [RFC 6238](https://www.rfc-editor.org/rfc/rfc6238), and in turn, the underlying HOTP (HMAC-Based One-Time Password) algorithm defined in [RFC 4226](https://www.rfc-editor.org/rfc/rfc4226#section-5).

Oof, daunting. Until then, I hadn’t given OTPs much thought beyond “How does this work?”.

Turns out, everything about how it works is detailed in well written documents that are easily accessible in both availability and, to my surprise, difficulty. But more wonderfully, these documents provide insight into the design decisions of the algorithms.

For example, in [RFC 4226](https://www.rfc-editor.org/rfc/rfc4226#section-5), while foreshadowing the rise of smart phones,

> … the current approach that requires an end user to carry an expensive, single- function device that is only used to authenticate to the network is clearly not the right answer. For two-factor authentication to propagate on the Internet, it will have to be embedded in more flexible devices that can work across a wide range of applications.

the authors revealed their belief in embedding OTP in more flexible devices, and this is what led to the open-system approach of HOTP which ensures its interoperability.

Thank you, Krawczyk, et. al.

The RFC series warrants its own blog post and it is not this one, sorry to disappoint. This blog post is a tutorial for implementing your own Time-Based One-Time Password in **Python** following the algorithms described in [RFC 6238](https://www.rfc-editor.org/rfc/rfc6238) and [RFC 4226](https://www.rfc-editor.org/rfc/rfc4226#section-5).

---

## TOTP Definition

[RFC 6238](https://www.rfc-editor.org/rfc/rfc6238) states that TOTP is defined as TOTP = HOTP(K, T).

```python
    def totp(k, t):
        return hotp(k, t)
```

Welp, looks like we’ll have to take a step back and implement HOTP first.

## HOTP Defintion

[RFC 4226](https://www.rfc-editor.org/rfc/rfc4226#section-5) states:

> The HOTP algorithm is based on an increasing counter value and a static symmetric key known only to the token and the validation service. In order to create the HOTP value, we will use the HMAC- SHA-1 algorithm, as defined in [RFC 2104](https://www.rfc-editor.org/rfc/rfc2104).

Hmm, guess we’ll have to take another step back and… just kidding, we’ll dip our toes in that rabbit hole another time.

Python’s built-in hmac module will help us generate the HOTP value for now.

> As the output of the HMAC-SHA-1 calculation is 160 bits, we must truncate this value to something that can be easily entered by a user.

With that, we get the definition: HOTP(K,C) = Truncate(HMAC-SHA-1(K,C)).

```python
    def hotp(k, c):
        return truncate(hmac_sha_1(k, c))
```

Primary Parameters

* k: The Key, which is the shared secret between the client and server. The server must share this key or the method for deriving this key with the client.

* c: An 8-byte counter value. This value increments after each OTP generation. Therefore, the counter has to be synchronized between the client and server.

Client and Server

* Client: the HOTP generator

* Server: the HOTP validator

The key(k) and counter(c) are the principal verification factors for authentication. We will not get into the details of the HMAC algorithm, so to put it simply, HMAC is a method for authenticating a *message* by using a hash function (eg. SHA-1) and a *shared secret*. Given the same values for the `shared_secret`, `message`, and `hash_function`, the following is always **true**.

```
    # pseudo-code
    hmac(shared_secret, message, hash_function)
    == hmac(shared_secret, message, hash_function)
```

In HOTP, the key k is the shared secret, and the counter c is the message.

Because the counter value increments after each OTP generation, the value is guaranteed to be single-use, thus ensuring the one-time property of the password.

_For the purposes of this tutorial, we will ignore the need to increment the counter because we will only focus on the OTP generation._

We’ll get to the truncate function in a little bit. For now, understand that this is the function that would convert a long hash string into the 6-digit OTP values we most frequently see in two-factor authentication.

---

Let’s go over the steps to generate an HOTP value, taken directly from the RFC ([Section 5.3](https://www.rfc-editor.org/rfc/rfc4226#section-5.3)).

![](https://cdn-images-1.medium.com/max/2000/1*l4r263_WKsfalegH7NRJuQ.png)

Step 2 and 3 made no sense to me, but we’ll figure them out as we go over the steps one-by-one.

## Step 1: Generate an HMAC-SHA-1 value

We will use the built-in [hmac.new](https://docs.python.org/3/library/hmac.html#hmac.new) method to help us generate the HMAC-SHA-1 value.

```python
    import hmac
```

For this implementation, we will use an arbitrary string "password" and base32 encode it to use as our shared secret. Our counter value is 0.

```python
    import base64
    
    secret = base64.b32encode(b"password")
    counter = 0
    counter_bytes = counter.to_bytes(8, byteorder='big')  # 8-byte, big-edian
    hs_hmac = hmac.new(secret, counter_bytes, "sha1")


    >>> hs_hmac
    <hmac.HMAC object at 0x1093d4220>
    >>> hs_hmac.hexdigest()
    '30eb405e8b59bf997aa83f904cd03cd41e3585b3'
```

> The counter value is hashed [high-order byte first](https://www.rfc-editor.org/rfc/rfc4226#section-5.2), so we’re ordering the most significant byte at the beginning of the byte array with byteorder='big'. See [python docs](https://docs.python.org/3/library/stdtypes.html#int.to_bytes).

Step 1.2 states that HS is a 20-byte string, which we can obtain from the hmac object using the digest() [method](https://docs.python.org/3/library/hmac.html?highlight=hmac#hmac.HMAC.digest).

```python
    hs = hs_hmac.digest()


    >>> hs
    b'0\xeb@^\x8bY\xbf\x99z\xa8?\x90L\xd0<\xd4\x1e5\x85\xb3'
```

Next, we have to begin tackling the Truncate function which the RFC breaks down into two steps: Step 2 (dynamic truncation) and Step 3 (reduction modulo 10^digit).

## Step 2: Generate a 4-byte string (Dynamic Truncation)

The RFC has helpfully provided us with the function defintion for dynamic truncation:

```
    DT(String) // String = String[0]...String[19]
     Let OffsetBits be the low-order 4 bits of String[19]
     Offset = StToNum(OffsetBits) // 0 <= OffSet <= 15
     Let P = String[OffSet]...String[OffSet+3]
     Return the Last 31 bits of P
```

To avoid confusion, we will give our functions and variables the same names as above but in snake case for readability.

```python
    def DT(hs):
        offset_bits = low_order_4_bits(hs[19])
        offset = st_to_num(offset_bits)
        p = hs[offset:offset+4]
        return last_31_bits(p)
```

In summary,

 1. The DT function receives a 20-byte string.

 2. Using the first byte, we generate an offset value.

 3. Then we we extract from the 20-byte string 4 bytes starting from the offset value.

 4. Finally, we return the last 31 bits from the extracted 4 bytes.

Now, let’s go over the DT function line-by-line.

```python
    offset_bits = low_order_4_bits(hs[19])
```

To get our offset value, we need to first extract the low-order 4 bits of hs[19] . This can be achieved by [masking](https://en.wikipedia.org/wiki/Mask_(computing)).

```python
    def low_order_4_bits(val):
        return val & 0b1111
```

---

### Bytes and Bits

_If you’re already familiar with binary and bitwise operations, you may want to skip this section._

To understand the logic behind our low_order_4_bits function, let's take a deeper look at the values we are dealing with.

The value we pass into the function is hs[19]. With hs being a 20-byte string, we understand that hs[19] is the last byte in the byte string.

```python
    >>> hs
    b'0\xeb@^\x8bY\xbf\x99z\xa8?\x90L\xd0<\xd4\x1e5\x85\xb3'
    >>> hs[19]
    179
```

Hmm? It’s an integer?

Yes! Hexadecimal, binary, ascii, decimal. These are all different ways to represent the same values.

By representing the same value (179) in bytes, decimal, and binary, we get a better understanding of what we're working with.

```python
    >>> hs[19]
    179
    >>> (179).to_bytes(1, 'big')   # big or little doesn't matter here
    b'\xb3'
    >>> b'\xb3'.hex()  # bytes to hexadecimal
    'b3'
    >>> int('b3', 16)  # hexadecimal to decimal (base-16 to base-10)
    179
    >>> bin(179)       # decimal to binary
    '0b10110011'
    >>> int('10110011', 2)  # binary to decimal (base-2 to base-10)
    179
```

Now, with this understanding, let’s return to our low_order_4_bits function. The RFC instructs us to extract the last four bits of the byte (hs[19]).

As seen above, the binary for hs[19] (or 179) is 10110011. It has 8 bits. We want to get rid of the first 4 bits (1011) and return 0011. To achieve this, we need to use the bitwise AND operator (&).

For our mask, we will use the binary 00001111. You can think of the zeroes as representing the positions that we want to "turn off", and the ones as the positions we want to keep "on". (This is only true for bitwise AND.)

As you recall, the binary for 179 is 10110011.

```python
    >>> 179 & 0b00001111         # masking decimal with binary
    3
    >>> 0b10110011 & 0b00001111  # masking binary with binary
    3
    >>> 0b00001111               # binary of 00001111 is 15
    15
    >>> 179 & 15                 # masking decimal with decimal   
    3
    >>> bin(3)                   # binary of 3 is 0011 or 11
    '0b11'
```

In binary, prefix zeroes can be omitted (00001111 == 1111), so 11 in binary is the last four bits (0011) we were looking to extract.

```python
    >>> 0b0011
    3
    >>> 0b11
    3
    >>> 0b00001111
    15
    >>> 0b1111
    15
```

As you can see, we have successfully extracted the last 4 bits of 179 by masking it with 0b1111.

Given what we know about binaries and masking, these are the different ways we can write the same function:

```python
    def low_order_4_bits(val):
        return val & 0b1111
    
    def low_order_4_bits(val):
        return val & 15
    
    def low_order_4_bits(val):
        return val & 0b00001111
```

A more common way to represent the bitmask is with a hexadecimal number, which we will see again later.

```python
    def low_order_4_bits(val):
        return val & 0xf

    >>> 0xf
    15
    >>> hex(15)
    '0xf'
```

---

Whew.

Back to our dynamic truncation function.

```python
    def DT(hs):
        offset_bits = low_order_4_bits(hs[19])
        offset = st_to_num(offset_bits)
        p = hs[offset:offset+4]
        return last_31_bits(p)
```

We already saw how our return value for low_order_4_bits is automatically treated as a number, so we can remove the second line in the function. Yay!

```python
    def DT(hs):
        offset = low_order_4_bits(hs[19])
        p = hs[offset:offset+4]
        return last_31_bits(p)
```

Recall that the objective of this step (Step 2) is to generate a 4-byte string from the original 20-byte string (hs). The RFC instructs us to do this by extracting 4 consecutive bytes from an offset. Now that we have calculated our offset which is 3, we can simply slice the 20-byte string from index 3 to index 3 + 4, just like you would an array.

That was easy!

Next, we have to return the last 31 bits from our slice of bytes. A byte is 8 bits, so currently we have 32 bits (8 * 4). How do we return the last 31 bits?

Masking!

Fortunately, the RFC has graciously provides us with the value to use for our mask (0x7f) which we will be using on the first byte of this slice.

> The reason for masking the most significant bit of P is to avoid confusion about signed vs. unsigned modulo computations. Different processors perform these operations differently, and masking out the signed bit removes all ambiguity.

Not only do we have to mask the first byte with 0x7f, we will also be masking the rest of the bytes with 0xFF which in binary is 11111111. This ensures that the byte we append to the array is at most 8 bits. Isn't a byte always 8 bits? Depending on the architecture of your system, a [byte](https://en.wikipedia.org/wiki/Byte) can be larger than 8 bits.

We’ll start with an intuitive, iterative approach by initiating an empty [bytearray](https://docs.python.org/3/library/stdtypes.html#bytearray) that will be our return value. Then, we’ll mask the first byte of the slice with 0x7f and then iterating over the rest of the slice to mask the rest of the bytes with 0xFF before appending it to our bytearray.

```python
    def last_31_bits(p):
        res = bytearray()
        res.append(p[0] & 0x7F)    # 7 bits
        for b in p[1:]:
            res.append(b & 0xFF)   # 8 bits
        return res

    >>> ba = last_31_bits(p)
    >>> ba
    bytearray(b'^\x8bY\xbf')
    >>> ba.hex()
    '5e8b59bf'
    >>> int(ba.hex(), 16)
    1586190783
    >>> bin(int(ba.hex(), 16))
    '0b1011110100010110101100110111111'
    >>> len(bin(int(ba.hex(), 16)))
    33
```

33 minus the length of the prefix (“0b”) at the beginning of the binary string is 31.

We’re done with Step 2!


## Step 3: Compute an HOTP value

Let’s review the instructions for Step 3.

![](https://cdn-images-1.medium.com/max/2000/1*NRfn5uZl1RinudGGfN9fKA.png)

We already know how to convert a bytearray to an integer. Easy peasy.

```python
    s_bits = last_31_bits(p)
    s_num = int(s_bits.hex(), 16)
    
    # or
    s_num = int.from_bytes(s_bits, 'big')
    
    
    >>> s_num
    1586190783
```

Next, in order to generate a 6-digit value for our OTP, we need to calculate s_num mod 10^6.

```python
    otp = s_num % 10 ** 6
    
    
    >>> otp
    190783
```

We have our One-Time Password!

To check our work, we will use the [PyOTP library](https://github.com/pyauth/pyotp).

```sh
    pip install pyotp
```

Recall that we used a base32 encoded value to generate our HMAC-SHA-1 value in Step 1.

```python
    >>> secret
    b'OBQXG43XN5ZGI==='
    >>> base64.b32decode(secret)
    b'password'
```

Because the [PyOTP library](https://github.com/pyauth/pyotp) expects to receive a base32 encoded secret and then *decodes* the secret before hashing, if we pass our current secret directly to the pyotp.HOTP method, b'password' will be used to generate the hmac value instead of b'OBQXG43XN5ZGI===' which is what we used throughout this tutorial.

In order to get the same result, we have to base32 encode our already encoded secret one more time so the library uses the same value as we did for hashing.

```python
    import pyotp
    
    secret = base64.b32encode(b"password")
    secret = base64.b32encode(secret)  # b'J5BFCWCHGQZVQTRVLJDUSPJ5HU======'
    hotp = pyotp.HOTP(secret)
    
    
    >>> hotp.at(0)
    190783
    >>> hotp.at(0) == otp
    True
```

We did it! 🎉

Here’s our work so far:

```python
    import hmac
    import base64
    
    counter = 0
    secret = base64.b32encode(b"password")
    
    
    def low_order_4_bits(val):
        return val & 0b1111
    
    
    def last_31_bits(p):
        res = bytearray()
        res.append(p[0] & 0x7F)  # 7 bits
        for b in p[1:]:
            res.append(b & 0xFF)   # 8 bits
        return res
    
    
    def DT(hs):
        offset = low_order_4_bits(hs[19])
        p = hs[offset:offset+4]
        return last_31_bits(p)
    
    
    def hotp(k, c):
        counter_bytes = c.to_bytes(8, byteorder='big')  # 8-byte, big-edian
        hs_hmac = hmac.new(k, counter_bytes, "sha1")
        hs = hs_hmac.digest()
        s_bits = DT(hs)
        s_num = int(s_bits.hex(), 16)
        return s_num % 10 ** 6
```

---

Before we move on to TOTP, I’d like to point out [PyOTP’s logic](https://github.com/pyauth/pyotp/blob/618106c1dee7f5bf22da2c5d6739ab87070d3fc2/src/pyotp/otp.py#L28) for getting the last 31 bits in the dynamic truncation function.

```python
    offset = hmac_hash[-1] & 0xF
    code = (
      (hmac_hash[offset] & 0x7F) << 24
      | (hmac_hash[offset + 1] & 0xFF) << 16
      | (hmac_hash[offset + 2] & 0xFF) << 8
      | (hmac_hash[offset + 3] & 0xFF)
    )
```

Instead of iterating through the bytearray slice to mask and append the masked values to a new bytearray, pyotp instead utilizes the bitwise OR operator and the bitwise left shift (<<) operator.

This is actually the exact same logic shown in the [example given in the RFC](https://www.rfc-editor.org/rfc/rfc4226#section-5.4).

```java
    int offset   =  hmac_result[19] & 0xf ;
    int bin_code = (hmac_result[offset]  & 0x7f) << 24
       | (hmac_result[offset+1] & 0xff) << 16
       | (hmac_result[offset+2] & 0xff) <<  8
       | (hmac_result[offset+3] & 0xff) ;
```

So, we really could have just copied and pasted directly from the RFC and made this blog post a lot shorter. 🤷🏻‍♀️

---

Let’s talk TOTP.

## TOTP Definition

With HOTP cleared and well understood, TOTP itself is actually extremely simple since it is essentially just an extension of HOTP.

From [the RFC](https://www.rfc-editor.org/rfc/rfc6238#section-4.2),

> Basically, we define TOTP as TOTP = HOTP(K, T), where T is an integer and represents the number of time steps between the initial counter time T0 and the current Unix time.*

In HOTP, the moving factor is the number of times an OTP has been generated. After each OTP generation, the counter increases by one. On the other hand, in TOTP, the moving factor is time. After a given length of time, the number of time steps increases by one regardless of how many times the an OTP has been generated.

This allows for multiple different TOTP generators to be implemented entirely independently from each other *and* the TOTP verifier. A new TOTP generator can be implemented after the TOTP verifier has already verified several OTPs as long as the generator and verifier share the initial counter time T0 and the same time-step value X.

Let’s agree that T0 is 0 (the Unix epoch), and X is 30 seconds.

This means that if it has been 30 seconds since the Unix epoch, then T is 1. If it has been 89 seconds since the Unix epoch, then T is 2.

For the purposes of this tutorial we will ignore timezones.

```python
    import datetime
    import time
    
    t = 30
    
    
    def totp(k, t):
        s_since_epoch = time.mktime(datetime.datetime.now().timetuple())
        time_steps = int(s_since_epoch / t)
        return hotp(k, time_steps)

Done!
```

[time.mktime](https://docs.python.org/3.8/library/time.html#time.mktime) returns the number of seconds since epoch given a [struct_time](https://docs.python.org/3.8/library/time.html#time.mktime) in local time. We divide this value by the time step interval using the default floor function and convert the result to an integer. This value is our counter value for the hotp function we had defined earlier.

Let’s check our work! We’ll be using the same secret as before, so again, we have to encode the (already encoded) secret to test our answer against the library’s.

```python
    >>> totp = pyotp.TOTP(base64.b32encode(secret))
    >>> totp.now()
    '487975'
    >>> hotp(secret, int(time.mktime(datetime.datetime.now().timetuple())/30))
    487975
    >>> hotp(secret, int(time.mktime(datetime.datetime.now().timetuple())/30)) == int(totp.now())
    True
```

Aaand, with that, we have successfully implemented our own Time-Based One-Time Password!

[Here](https://gist.github.com/vimiomori/e1c32e5ac1682bc02fb56da8ab8fbdc4#file-otp-py)’s the github gist of our work.

---

## References

* [RFC 6238](https://www.rfc-editor.org/rfc/rfc6238)

* [RFC 4226](https://www.rfc-editor.org/rfc/rfc4226#section-5)

* [PyOTP](https://github.com/pyauth/pyotp)

* [Python Docs](https://docs.python.org/3/library/functions.html?highlight=int#int)

* [Real Python — Bitwise Operators in Python](https://realpython.com/python-bitwise-operators/#bitwise-or)