How does Google Authenticator work? (Part 2)

Authenticator apps like Google Authenticator use 2 authenticaion protocol centered around What you have paradigm. Those algorithms are:

  • HOTP (HMAC-based One Time Password), and
  • TOTP (Time-based One Time Password).

They obviously are different, but both are centered around the same basic idea: using a rolling hash value, that is predictable only to the server and the authenticator app. Additionally, both are using HMAC-SHA-1 for generating those hash values.

In my previous post I explained the gist of the approach used in both algorithms. Here we’ll focus on the details of implementation of HMAC. We’ll tackle TOTP in part 3.

HOTP

All that I’ve explained so far is enough to understand all the details around HOTP. We take the key and counter, calculate HMAC-SHA-1, process the resulting hash into a (typically) 6-digit long code.

The details I’ll explain here will be:

  • How does HOTP represent the counter? It’s not the ASCII string representing the number that we’ve been using in our examples so far.
  • What really is the key? We’ve been using the password: $3cr3tP4$$ throughout, but it could be any binary sequence of bytes (not necessarily printable ASCII or even UTF).
  • Result of HMAC-SHA-1 is a SHA-1 hash – 20 bytes long sequence of bytes. However, the app presents 6-digit code. How is the hash being transformed into that sequence?
  • How do server and the app exchange the secret? You probably already know that: using QR Code. This is common to both, HOTP, and TOTP and they work the same way. However, since my wife and I have already implemented TOTP authenticator app for Nitrokey Pro2 USB key, and we already have some example test data, I’ll explain this in part 3, where we’ll discuss TOTP.

The Counter

HOTP went with keeping counter as a Big-Endian integer. For example, let’s take some large counter value here: 53115673. In hex representation that is 0x32a7b19. Let’s divide it into bytes:0x03 0x2a 0x7b 0x19. The most significant byte is 03, the least significant one is 0x19. In addition to that, HOTP is using a large – 8-byte long – integer. This means that the table of bytes is padded with zeros up to 8 bytes overall.

If you don’t know what Big-endian is, well, it’s nothing more than just ordering the bytes so that the most significant byte goes into the lowest address (the 1st element in the array). So the number becomes the following array of bytes:

index: 0    1    2    3    4    5    6    7
value: 0x00 0x00 0x00 0x00 0x03 0x2a 0x7b 0x19

Thus, HOTP calls HMAC-SHA-1 with the key and the above array of bytes representing the counter.

If you’re wondering how many possible values can the counter have, well, a lot. More than you’d ever need. The range is from 0x0 all the way up to 0xFFFFFFFFFFFFFFFF. That gives us total of 18446744073709551616 HMAC results (18446744073709551616 HOTP codes).

The Key

The key is just sequence of random bytes generated by the server when you’re adding 2nd authentication factor. It may also contain zero (0x00) bytes anywhere in the middle. After the server generates the key, it shares with the app typically through a QR code.

6-digit code

Ok, so far we’ve been pondering the idea of asking user to enter for example last 3 bytes of the hash in hex format. This is not the way it works in Google Authenticator, though. We’re being asked to always enter a sequence of (usually 6) decimal digits. It’s not really that far off from our idea. Those 6 digits are derived always from that HMAC-SHA-1 hash. One way to do that would be to:

  1. Take final 4 bytes from the HMAC-SHA-1 result (e.g. from our example in part one: 5d1014482edb0afb42101d8d4b5ff9bb5340a683 that would be: 5340a683). Now, let’s treat that as a number (represented in hex: 0x5340a683). When you convert this to the decimal notation, you’ll get: 1357872921.
  2. Get last 6 digits: 872921.

And that’s our 6-digit code.

Well, almost. HOTP is adding 2 small twists to that. The 1st twist is that it’s not taking last 4 bytes. It is always taking 4 bytes, but from where exactly is actually calculated using super-simple approach. Namely, we’re looking at last 4 bits of the hash (2nd hex digit of the last byte: 0x83 in our example gives us 3). This number is always between 0 and 15 (0x00xf). And that number is the offset within the hash from where we get the 4 bytes that get converted into the code. So in our example above we’d take the following bytes:

                                   the index
                                   at which the
                                   4-bytes code
                                   sequence is
                                       🠓
index within the hash: 00 | 01 | 02 | 03 | 04 | 05 | 06 | 07 | 08 | 09 | 10 | 11 | 12 | 13 | 14 | 15 | 16 | 17 | 18 | 19
hash:                  5d | 10 | 14 | 48 | 2e | db | 0a | fb | 42 | 10 | 1d | 8d | 4b | 5f | f9 | bb | 53 | 40 | a6 | 83
                                      ^^   ^^   ^^   ^^                                                                🠑
                                                                                                                       |
Index at which the 4-byte sequence starts______________________________________________________________________________」

Thus, in our example, the number would be 0x482edb0a.

The 2nd twist is that on various architecture the most significant bit might be treated differently and yield actually different integer values. The most significant bit is typically a sign indicator (positive or negative integer). To avoid any potential confusion around that the algorithm simply omits this bit and takes only the remaining 31 bits. In our case the most significant byte is 0x48. In binary notation that’s 01001000. The most significant bit (the far left one) is already 0, so we don’t have to do anything. But if it was 1, it would be setting it to 0 when extracting the code integer.

Ok, our code integer (0x482edb0a) in decimal notation is 1211030282, so our code (last 6 digits) is 030282.

QR Code

QR Codes in both HOTP, and TOTP are just printable ASCII strings encoded in a graphical image. They contain the key and some metadata about the account to which the 2nd factor relates.

Thos QR Codes are structured almost identically in both, HOTP, and TOTP. However, since I’ve already got examples of TOTP flavour, I’ll describe how that works in details in the TOTP part.

Clunkiness of keeping the Counter in sync

The server and authenticator app are not communicating with one another. This may lead to problems with synchronization – we want each code to be valid only once (for single authentication only) and expire right after that. This means, that as soon as you get authenticated, the server will increase the counter on its end and next time around will expect the app to present the code based on the next counter tick. That, in turn, means that the app has to also bump the counter so that the next time it would be presenting the code the server would be expecting.

So now let’s say you experienced network connectivity issue right when you were in a middle of authentication process. Let’s say at that during that authentication the counter was 10. The authentication failed because of the network connectivity time-out (server never got your code), thus it hasn’t bumped the counter on its end (it’s still 10). The app, however, doesn’t know that – it isn’t receiving any feedback from the server – so it’s bumping the counter as usual (now it’s 11 on apps end). Then you retry authenticating, server will expect your app to generate the code based on counter’s value of 10, but the app generates code off of the counter 11). Authentication would simply fail. HOTP standard suggests ways to recover from this, but those aren’t perfect. What the standard suggests in particular is that the server verifies against not only the value of the counter it has saved on its end (10 in our example) but also a couple of values ahead (like maybe 11, 12, 13 – in our example looking at 11 would’ve yielded desired result).

Piece of code

Let’s use the above example to ilustrate how easy it is to calculate HOTP code. We’ll use our password as key ($3cr3tP4$$) and a counter value of 125. Now, I did say that the key doesn’t have to be printable string, but it sure can be. So let’s stick to it for clarity. Please, see the Python code below.

#! /usr/bin/env python3
import hmac

key = "$3cr3tP4$$"
key_bytes = bytearray(key, "utf-8")

counter = 125
# Let's convert it to an array of 8 bytes in Big Endian order 
counter_big_endian = counter.to_bytes(8, "big")

# The critical part of calculating the code: HMAC-SHA-1 of the
# key and the counter value in Big Endian order.
h = hmac.new(key_bytes, counter_big_endian, "sha1")
hash_value = h.digest()
print(f"Result of HMAC-SHA-1: {h.hexdigest()}")

# The above prints out 1d9e9042df2bb36c0694a3b140466ea440ac189a
# The index of the code integer is indicated by the last hex
# digit (0xa, which is 10 in decimal notation). So within the
# above HEX (remember, we start indexing at 0):
# 1d 9e 90 42 df 2b b3 6c 06 94 a3 b1 40 46 6e a4 40 ac 18 9a
#                               ^^ ^^ ^^ ^^
# Now, here the most significant bit is set!! The most significant byte
# is 0xa3. We have to zero-out that bit, so 0xa3 becomes 0x23. thus the
# whole number is: 0x23b14046. In decimal notation that is: 598818886
# so the code (last 6 digits) is 818886.

# Ok, no the code to do the above. First let's calculate the offset (here
# it's 10 as explained above).
offset = hash_value[len(hash_value) - 1] & 0x0f

# Now let's get the code integer (we zero-out the most significant bit but
# only in the 1st -- the most significant -- byte)
code =  (hash_value[offset] & 0x7f) * 0x1000000
code += (hash_value[offset + 1])    * 0x10000
code += (hash_value[offset + 2])    * 0x100
code += (hash_value[offset + 3])
print("The code integer: 0x%x" % code)
print(f"The code integer in decimal notation: {code}")

# And now we take only last 6 digits
code = code % 1000000
print(f"The final HOTP code: {code}")

And output of this script:

Result of HMAC-SHA-1: 1d9e9042df2bb36c0694a3b140466ea440ac189a
The code integer: 0x23b14046
The code integer in decimal notation: 598818886
The final HOTP code: 818886

That’s literally it. HOTP explained.

In part 3 we’ll discuss all the details around TOTP and QR Codes used by both, HOTP, and TOTP.

HOTP  MFA