Implementation of RFC 4226 - HOPT Algorithm

HMAC based One Time Password

...in python

Two factor authentication is a technique where a user needs to prove his identity with more than just a username and a psasword to login to an online service. This was found necessary for various reasons such as people using the same password for multiple sites and one of those sites gets hacked, their password database compromised. Even if the passwords are stored as hashes and not plain texts, an attacker could run the hashes against a database of pre-computed hashes to guess the password.

With two factor authentication, a one time password (OTP) is generated each time the user logs in. This OTP is useless after one use. One way to have one time passwords is to have the user and the service agree on a long list of passwords. This would be a logistical problem. Another alternative is to use a pseudo random number generator using an Linear Feedback Shift Register (LFSR). As long as the user and the service use the same seed, they would generate the same pseudorandom number sequence. However, this is cryptograhpically weak.

This problem is solved using an HMAC based One Time Password (HOTP) generation algorithm[2]. The HOTP is based on the HMAC algorithm (see HMAC Jupyter notebook). The HMAC generates a hash, for a given secret key $K$ and message $M$ pair.

$$hmac\_hash = HMAC(K, M)$$

The HOPT uses an increasing counter in place of the message. So, the each time the user logs in, both the user and the service increament the counter to authenticate the next time. The HOTP algorithm is described in RFC-4226[1].

This notebook demonstrates the working of the RFC-4226 with intermediate steps output to the console.

In [1]:
import hashlib
import hmac
import base64
In [2]:
# Control excessive output to console
debug = True
def dbg(data):
    if (debug):
        print(data)
In [3]:
# Prepare Counter - convert integer to byte
def get_counter(counter):
    return counter.to_bytes(8, byteorder='big')
In [4]:
### Define SharedSecret, Block size, hashing algorithm, HOTP length
hash_algo = "sha1"
B = 64
counter = 1
shared_secret = b'BASE32SECRET3232'
# OTP Length
Digits = 6
# Google Authenticator Compatibility (BASE-32)
key=base64.b32decode(shared_secret)
dbg("Key Base32 Decode :")
dbg(key)
Key Base32 Decode :
b'\x08$M\xeaD\x14I=\xebz'
In [5]:
### Implement the HMAC Algorithm. For details see the rfc2104.ipynb at
# https://github.com/lordloh/OPT_algorithms/blob/master/rfc2104.ipynb

def my_hmac(key, message):
    trans_5C = bytes((x ^ 0x5C) for x in range(256))
    trans_36 = bytes((x ^ 0x36) for x in range(256))
    K_zpad=key.ljust(B,b'\0')    
    K_ipad=K_zpad.translate(trans_36)
    K_opad=K_zpad.translate(trans_5C)
    hash1 = hashlib.new(hash_algo, K_ipad+message).digest()
    hmac_hash = hashlib.new(hash_algo, K_opad + hash1).digest()
    return hmac_hash

Dynamic Truncation

The Dynamic Truncation routine takes the lowest 4 bit of the hash. This is used as the offset for the next step. Next, 4 bytes (32 bits), starting from offset : offset+4 are extracted from the same hash. The lower 31 bits of this sub-hash is finally returned.

The byte # of the HMAC hash are interpreted as -

-------------------------------------------------------------
| Byte Number                                               |
-------------------------------------------------------------
|00|01|02|03|04|05|06|07|08|09|10|11|12|13|14|15|16|17|18|19|
-------------------------------------------------------------
In [6]:
### Dynamic Truncation
def dynamic_truncate(b_hash):
    dbg ("\n***** DYNAMIC TRUNCATION *****")
    hash_len=len(b_hash)
    int_hash = int.from_bytes(b_hash, byteorder='big')
    offset = int_hash & 0xF
    dbg ("offset = Lowest 4 bits (nibble) of hash = " + hex(int_hash & 0xF)+" = "+str(offset))
    dbg ("Get hex digits (nibbles) from byte #"+str(offset)+" to byte #"+str(offset+3))
    dbg ("Byte 0 is the most significat byte (two hex digits) of the hash.")
    # Geterate a mask to get bytes from left to right of the hash
    n_shift = 8*(hash_len-offset)-32
    MASK = 0xFFFFFFFF << n_shift
    #dbg ("\nTruncate MASK : "+hex(MASK).rjust(hash_len*2,"0"))
    hex_mask = "0x"+("{:0"+str(2*hash_len)+"x}").format(MASK)
    dbg ("\nHash            : 0x"+b_hash.hex())
    dbg ("Truncate MASK   : "+hex_mask+"\n")
    # Get rid of left zeros
    P = (int_hash & MASK)>>n_shift
    dbg ("Truncated hash (hex) : "+hex(P))
    dbg ("Truncated hash (int) : "+str(P))
    # Return only the lower 31 bits
    LSB_31 = P & 0x7FFFFFFF
    dbg ("31 LSB bits of truncated hash (hex) : "+hex(LSB_31))
    dbg ("31 LSB bits of truncated hash (int) : "+str(LSB_31))
    return LSB_31
In [7]:
# function wrapper to run the HOTP algorithm multiple times for different counter value
def generate_HOTP(counter):
    C = get_counter(counter)
    
    dbg("Counter (int)     : "+str(counter)+"\nCounter (8 bytes) : "+str(C))

    hmac_hash = my_hmac(key,C)
    dbg("\nHMAC Hash (shared_secret, counter) : 0x" + hmac_hash.hex())

    # Get a truncated hash (int)
    trc_hash = dynamic_truncate(hmac_hash)
    
    # Adjust HOTP length
    HOTP = ("{:0"+str(Digits)+"}").format(trc_hash % (10**Digits))
    
    dbg("\n***** ADJUST DIGITS *****\n"+str(trc_hash)+" % 10 ^ "+str(Digits)+"\nHOPT : "+HOTP)
    return HOTP
In [8]:
# Generate HOTP for counter = 1
myHOTP1=generate_HOTP(1)
Counter (int)     : 1
Counter (8 bytes) : b'\x00\x00\x00\x00\x00\x00\x00\x01'

HMAC Hash (shared_secret, counter) : 0x7117ccfcfc54a98514d8774fb1b8fbe0624e330f

***** DYNAMIC TRUNCATION *****
offset = Lowest 4 bits (nibble) of hash = 0xf = 15
Get hex digits (nibbles) from byte #15 to byte #18
Byte 0 is the most significat byte (two hex digits) of the hash.

Hash            : 0x7117ccfcfc54a98514d8774fb1b8fbe0624e330f
Truncate MASK   : 0x000000000000000000000000000000ffffffff00

Truncated hash (hex) : 0xe0624e33
Truncated hash (int) : 3764538931
31 LSB bits of truncated hash (hex) : 0x60624e33
31 LSB bits of truncated hash (int) : 1617055283

***** ADJUST DIGITS *****
1617055283 % 10 ^ 6
HOPT : 055283
In [9]:
# Lets see the example of generating HOTP for counter = 2
myHOTP2=generate_HOTP(2)
Counter (int)     : 2
Counter (8 bytes) : b'\x00\x00\x00\x00\x00\x00\x00\x02'

HMAC Hash (shared_secret, counter) : 0x364568c345d0c5935bfd7016adfe16c51437f207

***** DYNAMIC TRUNCATION *****
offset = Lowest 4 bits (nibble) of hash = 0x7 = 7
Get hex digits (nibbles) from byte #7 to byte #10
Byte 0 is the most significat byte (two hex digits) of the hash.

Hash            : 0x364568c345d0c5935bfd7016adfe16c51437f207
Truncate MASK   : 0x00000000000000ffffffff000000000000000000

Truncated hash (hex) : 0x935bfd70
Truncated hash (int) : 2472279408
31 LSB bits of truncated hash (hex) : 0x135bfd70
31 LSB bits of truncated hash (int) : 324795760

***** ADJUST DIGITS *****
324795760 % 10 ^ 6
HOPT : 795760
In [10]:
# Similarly, lets generate HOTPs for counter = 3..10 without a lot of output messages.
debug=False
myHOTPs=[(generate_HOTP(x)) for x in range(3,10)]
myHOTPs.insert(0,myHOTP1)
myHOTPs.insert(1,myHOTP2)
In [11]:
print(myHOTPs)
['055283', '795760', '172916', '437628', '220505', '845989', '311663', '850732', '285195']

Compare with pyOTP Implementation

In [12]:
# Python
import pyotp
In [13]:
hotp_pyOTP=pyotp.HOTP(shared_secret)
In [14]:
# Generate 0..9 HOTP codes
pyHOTPs=[(hotp_pyOTP.at(x)) for x in range(1,10)]
In [15]:
print(pyHOTPs)
['055283', '795760', '172916', '437628', '220505', '845989', '311663', '850732', '285195']

Compare with Google Authenticator

Setup
Google Authenticator Setup
counter = 1 counter = 2
counter=1 counter=2
counter = 3 counter = 4
counter=3 counter=4
counter = 5 counter = 6
counter=5 counter=6

References

  1. RFC 4226
  2. Wikipedia