How virtual MFA tokens work

Almost every day I open Authy on my phone and provide a one-time MFA (multi-factor authentication) token in order to login to AWS. I also use MFA for a number of different sites including Google, GitHub, Slack, Dropbox and Twitter. If you are not using MFA to protect access to your sensitive data, you should be!

But how does this stuff work? When you snap a QR code with your phone, what is actually happening? Let's find out...

Here's a QR code generated by AWS:

(Before you try and hack me, I should point out that this code is for a temporary dummy user in a non-production AWS account!)

If we decode this QR code, we see that it is actually a URI containing a bunch of metadata and a secret:

otpauth://totp/Amazon%20Web%20Services:dummy@identity-nonprod?secret=2HZ53IOC2XPQZDT24UHSTTUNYDHQ6A5FUX7SFIZ2LEHG6IYSC33L7EOJ5YMOZUWA&issuer=Amazon%20Web%20Services

We care about two things in this URI:

1. totp - this is the hashing algorithm to use. TOTP stands for Time-based One-Time Password, and it calculates hashes based on the current timestamp and a shared secret. It's a variant of the HOTP (HMAC-based One-time Password) algorithm.
2. secret=2HZ... - this is the shared secret required by the hashing algorithm, encoded as a base-32 string

Generating a one-time token

The algorithm to generate a token looks like this, assuming the client and server agree to use the default values for all the algorithm's parameters:

timeInterval = 30 seconds
timeCounter = floor((unixtime(now)) / timeInterval)
secretKey = base32Decode("2HZ53I...")
hash = HMAC-SHA-1(secretKey, timeCounter)

The resulting hash is 20 bytes long, so we don't really want to type the whole thing in. We take a 4-byte chunk of it, treat it as an integer, take the value modulo 10⁶ and zero-pad it if necessary, to give us the 6-digit MFA token that we know and love.

Let's try it

Here's an implementation in Haskell:

generateToken :: String -> Int -> String
generateToken secretBase32 epochSeconds = token
  where
    secret = decodeBase32 secretBase32
    timeInterval = 30
    timeCounter = epochSecondsToTimeCounter timeInterval epochSeconds
    hash = hmac_sha1 secret timeCounter
    token = hashToToken hash

It takes a base32-encoded secret key, as found in our QR code, and the current UNIX time in seconds as arguments.

After decoding the secret, it uses the timestamp to calculate the "time counter", which is the number of 30-second intervals since the UNIX epoch:

epochSecondsToTimeCounter :: Int -> Int -> [Octet]
epochSecondsToTimeCounter timeInterval epochSeconds = octets
  where
    intervals = epochSeconds `div` timeInterval
    zeroPaddedHex = printf "%016x" intervals
    octets = hexToOctets zeroPaddedHex

Then it uses the secret and the time counter to calculate an HMAC-SHA1 hash, and finally it turns that hash into a 6-digit token:

hashToToken :: [Octet] -> String
hashToToken hash = paddedToken
  where
    offset = fromTwosComp [last hash .&. 15]
    truncatedHash =
      [ (hash !! offset) .&. 127
      , hash !! (offset + 1)
      , hash !! (offset + 2)
      , hash !! (offset + 3)
      ]
    integer = fromTwosComp truncatedHash
    token = integer `mod` 1000000 :: Int
    paddedToken = printf "%06d" token

It looks at the last byte of the hash and treats that value as an offset into the hash. It then takes four bytes of the hash, starting at that offset, and treats those four bytes as an integer.

Finally it takes the integer's value module 10⁶, and zero-pads it to ensure it is 6 digits long.

Here is the whole thing in action:

$ stack exec mfa-example-exe
270092

You can see that it has generated the same token as the Authy app on my phone:

The full source code for this example is available on GitHub.

Further reading

The gory details of TOTP are specified in RFC 6238.