# Implementation of RFC 4226 - HOPT Algorithm¶

...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. 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.

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

In :
import hashlib
import hmac
import base64

In :
# Control excessive output to console
debug = True
def dbg(data):
if (debug):
print(data)

In :
# Prepare Counter - convert integer to byte
def get_counter(counter):
return counter.to_bytes(8, byteorder='big')

In :
### Define SharedSecret, Block size, hashing algorithm, HOTP length
hash_algo = "sha1"
B = 64
counter = 1
shared_secret = b'BASE32SECRET3232'
# OTP Length
Digits = 6
key=base64.b32decode(shared_secret)
dbg("Key Base32 Decode :")
dbg(key)

Key Base32 Decode :

In :
### 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))
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 :
### 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
dbg ("\nHash            : 0x"+b_hash.hex())
# Get rid of left zeros
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 :
# 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)

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 :
# 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

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

1617055283 % 10 ^ 6
HOPT : 055283

In :
# 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.

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

324795760 % 10 ^ 6
HOPT : 795760

In :
# 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 :
print(myHOTPs)

['055283', '795760', '172916', '437628', '220505', '845989', '311663', '850732', '285195']


## Compare with pyOTP Implementation¶

In :
# Python
import pyotp

In :
hotp_pyOTP=pyotp.HOTP(shared_secret)

In :
# Generate 0..9 HOTP codes
pyHOTPs=[(hotp_pyOTP.at(x)) for x in range(1,10)]

In :
print(pyHOTPs)

['055283', '795760', '172916', '437628', '220505', '845989', '311663', '850732', '285195']       