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, and in turn, the underlying HOTP (HMAC-Based One-Time Password) algorithm defined in RFC 4226.
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, 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 and RFC 4226.
TOTP Definition
RFC 6238 states that TOTP is defined as TOTP = HOTP(K, T).
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 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.
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)).
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).
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 method to help us generate the HMAC-SHA-1 value.
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.
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, so we’re ordering the most significant byte at the beginning of the byte array with byteorder='big'. See python docs.
Step 1.2 states that HS is a 20-byte string, which we can obtain from the hmac object using the digest() method.
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.
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,
The DT function receives a 20-byte string.
Using the first byte, we generate an offset value.
Then we we extract from the 20-byte string 4 bytes starting from the offset value.
Finally, we return the last 31 bits from the extracted 4 bytes.
Now, let’s go over the DT function line-by-line.
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.
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.
>>> 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.
>>> 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 hs19 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.
>>> 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.
>>> 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:
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.
def low_order_4_bits(val):
return val & 0xf
>>> 0xf
15
>>> hex(15)
'0xf'
Whew.
Back to our dynamic truncation function.
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!
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 can be larger than 8 bits.
We’ll start with an intuitive, iterative approach by initiating an empty 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.
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.
We already know how to convert a bytearray to an integer. Easy peasy.
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.
otp = s_num % 10 ** 6
>>> otp
190783
We have our One-Time Password!
To check our work, we will use the PyOTP library.
pip install pyotp
Recall that we used a base32 encoded value to generate our HMAC-SHA-1 value in Step 1.
>>> secret
b'OBQXG43XN5ZGI==='
>>> base64.b32decode(secret)
b'password'
Because the PyOTP library 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.
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:
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 for getting the last 31 bits in the dynamic truncation function.
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.
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,
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.
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 returns the number of seconds since epoch given a struct_time 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.
>>> 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’s the github gist of our work.
Top comments (0)