How does HOTP authentication work?

Before smartphones were popular, hardware tokens that produced an HOTP code were a popular way of performing two-factor authentications. Businesses gave their customers a small electronic device that generated a number when a button was pressed. After entering their password, customers had to enter this number to successfully authenticate themselves. 

So, how could a system know what number was generated by the token that was not connected to the internet? Well, this was made possible by the HOTP or HMAC-based One Time Password algorithm. 

The HMAC algorithm

To understand how this algorithm works, we need to first understand how HMAC works. A rudimentary explanation of HMAC could be that it hashes data to be transmitted with a cryptographic key twice to ensure data integrity and authenticity. The idea is that when the HMAC of data is sent along with the data, the recipient can repeat the HMAC algorithm using the cryptographic key that was shared with them by the sender to see if the data was received intact and that it was actually sent by the sender.  

To produce the exact hash, the same input should be used. So, the recipient has to use the same key and the same data to get the exact same hash. If the hash obtained thus is the same, then that means that the data received has not been modified during transmission. Since the cryptographic key is supposed to be a secret between the sender and the recipient, then it also means that it is indeed the sender who has sent the data. A more detailed explanation of the HMAC algorithm can be found here. 

How does HOTP use HMAC?

The HOTP algorithm uses the HMAC algorithm to generate authentication codes. To do so, HOTP hashes a cryptographic key and a counter, which is the data here, twice to produce the code. Here, the cryptographic key is shared between the system and the device. The counter is separately maintained by both the token device and the system.  This can be summarized as follows: 

H()—hashing function 

K—Shared secret key 

C—Counter  

HOTP=H(K, H(K, C)) 

When the hardware token is produced, the cryptographic key is written into the memory of the device and the system stores this key in a database against the device ID. When the token is issued to a customer, the system stores the token ID in its customer database. Thus, the system knows the secret key of the token of a particular customer. 

The counter in HOTP

The counter acts as the data here. The token increments its counter every time its button is pressed to generate a new token. The system cannot know how many times the button of the token is pressed. So, the system increments its counter only when the user enters the correct authentication code. This leads to a desynchronization between the device’s counter and the system’s counter. We shall see how this is rectified later. 

When the button on the token is pressed, the device produces the authentication code by hashing the secret key it has and its counter value. When the user enters this code into the system, the system can then hash the secret key it has with its counter value to produce its own code. 

If the codes match, then that means it is the token given to the customer that has generated the code. Since a customer is expected to keep the token securely, it is assumed that it is the customer who is trying to authenticate, and the customer is given access. 

Synchronizing counters

But, as discussed above, if the counters are not going to be in sync with one another, then the codes produced are going to be different. Let’s see how this problem is overcome. Let’s say a customer has used the token to log into the system thrice. So, the system’s counter would say three. After the last login, let’s assume the token’s button was pressed six times. Therefore, the device’s counter would say nine. 

The next time the customer tries to log in using their token, the token would increment its counter value and produce the code. Since the counter value is now nine in the token, it will be incremented to 10. The system would increment its own counter and produce the HOTP code to verify the code entered by the customer. Since the system’s counter value is now three, it increments it to 4 before generating the code. As the counter values are different, the verification will obviously fail. 

Once it fails, the system would increment its counter a specified number of times until the codes match. Hence, the system would increment its counter to 5 and once again check if the codes match. The process will be continued until either the limit is reached or the correct code is found. Once the counter is incremented to 10, then the counters would be synchronized and the codes match.  

The look-ahead window

However, if the right code is not found after incrementing the counter a certain number of times, then the authentication will be failed and the system will reset its counter to the initial value. This is called the look-ahead window parameter. The number of increments that can be made has to be limited because if the user enters the wrong code, then the system will keep on incrementing the counter forever.  

The limit has to be in such a way that it is not big enough to lead to the hogging of the system’s resources and not small enough rendering the hardware token invalid and necessitating a replacement.  

Truncation in HOTP

This is how HOTP authentication works. But there is more to it. The HMAC algorithm produces a hash. This hash would be of different lengths depending on the type of algorithm used for hashing. The SHA-1 algorithm produces a 20-byte long hash which may look like this: bfc72c78a8ee233f27b658838990d226d26f5b8a. 

This is not user-friendly and there is no way customers can be expected to enter as many letters as this to authenticate themselves. So, HOTP actually truncates this hash to produce a more user-friendly number. Let’s see how it is done.  

The hash is in the hexadecimal format. This hexadecimal number is split into byte-sized groups first. Since one hexadecimal number is equal to four bits, two hexadecimal numbers will fall into one group. The above hash can be grouped as follows: 

0	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15	16	17	18	19
bf	c7	2c	78	a8	ee	23	3f	27	b6	58	83	89	90	d2	26	d2	6f	5b	8a

Now, the last 4 bits of the last byte, or in other words the last hexadecimal number, is considered as the offset number. It is ‘a’ in this hash so the offset number is 10. The hexadecimal numbers starting from the offset index to the following three indices are extracted out. This extracted number is called the Dynamic Binary Code (DBC).  

Dynamic Binary Code

Since the offset number is 10 in this example, the algorithm extracts out numbers from the 10^th byte to the next 3 bytes. So, the DBC would be 0x58838990. Then, the first byte of this number is masked by performing a bitwise and operation with 0x7f. Since 0x7f is 01111111, this effectively masks out the first bit. We shall see why the algorithm does this a bit later. 

0x58 & 0x7f is 0x58. So, the final DBC is also 0x58838990. Now, this hexadecimal number is converted to a decimal number. Therefore, 0x58838990 becomes 1485015440. Then, the modulus of this decimal number is found by dividing it by 10 raised to the power of the number of digits that you expect the final code to have. Since, usually, the number of digits in an HOTP code is 6, the HOTP is computed by 1485015440 mod 10⁶.  

This produces 15440. A zero is added in front to make it 6 digits in length. Thus, we get a code of 015 440.  

Now, let’s see why the first digit of the DBC was masked. When performing modulo operations, different processors perform unsigned and signed modulo computations differently. To avoid this issue, the HOTP algorithm masks the first bit since it is the first bit that identities the sign of an integer.  

This is how the HOTP algorithm turns a hash into a human-friendly, six-digit code.