Lost In Permutation

Beginner's Guide to TOTP

I’ve been a long-time fan of two-factor authentication, using Google Authenticator to represent “something I have” in addition to the password, which is “something I know.” So, of course, when GitHub added two-factor authentication, I immediately enabled it on my account.

Last night, unable to sleep, I noticed an update to Google Authenticator in the App Store. This is an app that hasn’t been updated for several years, so I was curious to see what the improvements were. I opened the app, and all of my tokens had vanished. Sure enough, Calvin reported the same issue on Hacker News. This SNAFU, in addition to my growing distrust of Google, inspired me to try and find a new, non-Google app to authenticate. I also decided to learn how it worked. Luckily, the algorithm—the Time-Based One-Time Password Algorithm (TOTP)—is very simple.

Sharing Secrets…

First, your authenticator app and the server must agree on a shared secret. The most common way this happens is that the server generates a secret and then displays a QR code to scan.

LABEL can be used to describe the key in your app, while SECRET is the 16-character base32-encoded shared secret, which is now known to both the client and the server.

…But Don’t Share With Everyone

Now, a shared secret is a pretty weak method of authentication, because the user can memorize it, effectively making it “something I know.” Also, a man-in-the-middle attack is alarmingly easy: the client will just tell you its secret!

A hash of the secret proves that we know it, without revealing what the secret is, but is still susceptible to a replay attack because the hash of the secret will never change. So an additional “moving factor” is combined with the shared secret in a hash-based message authentication code (HMAC) —specifically HMAC-SHA-1.

In HOTP, a predecessor to TOTP, the moving factor is a simple 8 byte counter. In TOTP, the moving factor is the passage of time! (That’s why it is called the time-based one-time password algorithm.) The two algorithms are otherwise identical; in fact, TOTP is defined as an extension to HOTP.

TOTP uses Unix time (roughly the number of seconds that have passed since January 1, 1970 GMT) to measure time. Since this would cause a new code to be generated each second, a time step X=30 is defined by default, meaning a new code is only generated every 30 seconds so that users have enough time to type in the code after it has been generated.

Aside: latency and clock skew

The Internet can be slow, and clocks might not match exactly, so some leniency is allowed. RFC6238 recommends looking an extra time step in either direction, which essentially opens the window from 30 seconds to 90 seconds.

Computing a one-time code

The HMAC-SHA-1 algorithm is run with the secret key and the current time step:

We could use this directly, but the user would have to type in an approximately 49-digit number every time they want to authenticate. (Plus, they would have to type this number, error-free, in 30 seconds!)

The code is shortened to 31 bits with dynamic truncation:

The offset is defined as the lower 4 bits of the last byte. The last byte of HS is hex 5a; its lower 4 bits are therefore hex a (decimal ten).

Smoosh together the 4 bytes starting at offset 10:

And truncate it further to a 31-bit number by making sure the top bit is cleared (in this case, it already is, so the number does not change):

Then convert that value to a decimal number:

And show the last 6 digits:

The user types this in. The server performs the same calculation and compares the values. If they match, the server knows that the user has possession of the authenticator device, and they can be authenticated. If not, the server knows the current session is invalid. In less than 30 seconds, the time step will increment, and the code will change.

Simple!

With a few simple building blocks, a token-based form of authentication is made using only software. With a password, the user now has two-factor authentication and will be less susceptible to many types of attacks.

UPDATE: I wrote a demo app to show how this works in practice