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:
We care about two things in this URI:
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.
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 106 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 106, 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.
The gory details of TOTP are specified in RFC 6238.