I have been using google authenticator for a while and decided to have a look into how the Time-Based One-Time Password Algorithm works.
Authenticators like the google one use the TOTP algorithm which is a fairly simple open standard. TOTP is an extension of the hash-based message authentication code (HMAC). It works by combining a secret key with the time using a hash function to generate a one-time password. The time needs to be synced (usually within 30 seconds is good enough, but it depends on some algorithm variables below).
The diagram shows a rough overview of how the process works. The validator will generate and share a key and then both the generator and validator should be able to generate the same key in the future if the clocks are synced. The validator will usually generate a number of keys either side of the current time to account for any time drift between the devices.
Generation Algorithm Explained
Here are the implementation steps taken from the TOTP wiki page. Each one is explained below:
- Generate a key, K, which is an arbitrary byte string, and share it securely with the client.
When you setup two factor authentication on one of your devices it will usually display a QR code such as the one below and ask you to scan it in your authenticator.
This QR code contains a new generated secret key. The QR code is just a convenient way of copying this information into your phone.
- Agree upon an epoch, T0, and an interval, TI, which will be used to calculate the value of the counter C (defaults are the Unix epoch as T0 and 30 seconds as TI)
Lets use 30 seconds as our TI and the epoch time for Unix is a constant: 1 January 1970 00:00:00
- Agree upon a cryptographic hash method (default is SHA-1)
- Agree upon a token length, N (default is 6)
Lets just use the defaults for now
- Calculate C as the number of times TI has elapsed after T0.
To do this, we can just divide the number of seconds that have passed since epoch by the time window.
- Compute the HMAC hash H with C as the message and K as the key (the HMAC algorithm is defined in the previous section, but also most cryptographical libraries support it). K should be passed as it is, C should be passed as a raw 64-bit unsigned integer.
This is fairly simple, we hash our content (C) with the key (K) using the HMAC-SHA1 algorithm. We must format the content as expected.
- Take the least 4 significant bits of H and use it as an offset, O.
HMAC-SHA1 will generate 20 bytes. We need to get the last one, and apply a bitmask to get the 4 least significant bits.
- Take 4 bytes from H starting at O bytes MSB, discard the most significant bit and store the rest as an (unsigned) 32-bit integer, I.
As stated in the previous step, we know H is 20 bytes. We also know O will be maximum 15 as it is 4 bytes. So this will always grab us 4 bytes from H. After that, we can just discard the most significant bit and store the rest as I.
- The token is the lowest N digits of I in base 10. If the result has fewer digits than N, pad it with zeroes from the left.
Here we can just use mod 10^N if using the default 6 digit tokens.
Here is some proof of concept python code that will produce a valid TOTP token (download):
import time import hmac import struct from hashlib import sha1 import base64 # Key K = base64.b32decode('JBSWY3DPEHPK3PXP') # This will be generated as part of our first step # Get the epoch time t0 = int(time.time()) # Set our time window t1 = 30 #seconds # Our cryptographic token length N = 6 # Calculate C as the number of times TI has elapsed after T0. currentTime = int(time.time()) C = (currentTime / t1) # Compute the HMAC hash H with C as the message and K as the key (the HMAC algorithm is defined in the previous section, but also most cryptographical libraries support it). K should be passed as it is, C should be passed as a raw 64-bit unsigned integer. # Convert so that we can pass it in as a 64-bit unsigned integer C_bytes = struct.pack(">Q", C) H = hmac.new(K, C_bytes, sha1).digest() # Take the least 4 significant bits of H and use it as an offset, O. O = ord(H) & 0b00001111 # Take 4 bytes from H starting at O bytes MSB, discard the most significant bit and store the rest as an (unsigned) 32-bit integer, I. # Get the 4 bytes discarding the MSB (most significant bit). I = struct.unpack(">I", H[O:O+4]) & 0x7ffffffff # The token is the lowest N digits of I in base 10. If the result has fewer digits than N, pad it with zeroes from the left. # We can use mod to remove the 7th digit token = I % 10**N # Print our token left padded with zeros print "%06d" % token
Validation and Issues
To validate these tokens, the website will try a range of time values and the shared key K. For example the validating server can do C +/- 1 to account for 30 seconds of time drift.
The issues with this algorithm are well explained on this wiki page. One of the main issues with the code generating applications being on mobile devices is the possibility of the shared secret code being stolen or copied. Also, with the risk of losing a device, you will almost always have to generate a backup code or add a second form of identification in case of loss of the mobile device.