Understanding Time-based One-time-password
Now that every web service encourage you, more and more, to use MFA to secure your account, one of them is used most than others : Time-based one-time password or TOTP 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 give a QRCode to scan (or a Base32 string) to configure in a TOTP generator app like Microsoft Authenticator, Google Authenticator, Bitwarden or more.
We all use it, but how does it work ? Is it secure ? Is my account secure when using third-party TOTP generator ??
The protocol
I will get deeps into the details of the underlying protocol allowing you to generated TOTP 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 string (sometimes stored in the QRCode). Then you both synchronize your clocks.
Finally when you want to login, you execute a fancy magical function and ultimately you get a TOTP. The server compute the TOTP on his side and ask you the one you generated on your side. If both of the TOTP match, the server allow you in.
TOTP protocol
Let's dig into the TOTP protocol. According to the RFC 6238 you need :
- A moving
counterthat must be synchronized between the two parties - A
secretshared between the two parties
The counter is calculated base on epoch time (That way everybody is synchronized) with the following formula :
With :
Cthe counter valueTthe current Unix time in seconds since epochT0an arbitrary start Unix time.0by defaultXthe time step in seconds or the frequency of code update.30by default
If we try to make a Python implementation, it will looks like :
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)
Now the TOTP value can be retrieved with the following formula :
With:
Cthe counter valueKthe secret keyDthe number of digits in our TOTPsHOTPthe magical function that calculate the OTP
In Python, we get :
HOTP protocol
This second protocol is used to calculate a unique value a counter value and the secret key. From the RFC rfc4226, we learn that its based on HMAC hash protocol.
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
counterneeds to be converted into anunsigned long longandbig-endianbytes array value.
In 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)
counter: 55036474
bytes_counter(bin) => 00000011 01000111 11001010 00111010
bytes_counter(hex) => 03 47 ca 3a
keyshould be a valid Base32 string. The RFC 4648 tells us that the string length need to be a factor of8. So padding can be added with char=at the end if it's too short. For example :AA=>AA======,BBBBBBBBBB=>BBBBBBBBBB======,CCCCCCCC=>CCCCCCCC
Then we convert the updated key in bytes array value :
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 we can understand how the HMAC function work. We need to choose an hash function. HOTP or RFC 4226 use the SHA-1 cryptographic hash function.
Python implement HMAC library :
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()
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 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
In Python & 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 we can use mac[-1] to get the last byte of the bytes array converted in an integer.
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 :
In Python the value after the : is not included. In order to extract offset+3 value, we need to put (offset+3)+1
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 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.
# https://docs.python.org/3/library/struct.html#struct.unpack
extract_31 = struct.unpack('>L', dynamic_truncation)[0] & 0x7fffffff
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 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.
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 code to make it the right length.
Conclusion
Now you really know how TOTP codes are generates. As we can see, it's pretty simple and you can develop your own script to generate them.
Full code
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))