How do Authenticators work?

Question

When it came to choosing an authenticator app for GitHub and other sites, I ended up with the Sophos, because, why not. Apparently, I could have chosen the Google app or a different one.

That would suggest that they’re all doing basically the same job, and that the web site doesn’t particularly care which app I use. I certainly didn’t tell the site which app I’m using, so that suggests it’s pretty neutral.

How does this work? Is there a central point of authentication, or do they all follow the same algorithm, or is there a list of acceptable authenticators?

Answer 1

Most such apps follow the same algorithm, OATH TOTP (as defined in IETF RFC 6238).

It works entirely offline – the QR code that you scan contains a secret key that the 6-digit codes are derived from, in combination with the current timestamp (rounded down to the nearest half-minute). The same code can therefore be imported to multiple apps and they will completely independently generate the same code, as long as the clocks match.

(There are exceptions; e.g. RSA SecurID used to be common in the past, OATH HOTP is a rare possibility – counter-based instead of time-based – and some apps use their own algorithms for historical reasons or otherwise, but OATH TOTP the one generally accepted on the web.)

The core of the algorithm is just HMAC_SHA1(secret_key, timestamp). Most websites have an option to show the secret key in text format instead of a QR code, and then you can use oathtool or hotpie to experiment with it. (Make sure you don't leave the secret key around.)

$ oathtool --base32 --totp ABCDEFG
534266

The QR code contains otpauth://totp/USER?secret=ABC&issuer=SITE, i.e. the same secret key plus the entry label (which is for display purposes only).

$ qrencode "otpauth://totp/User?secret=ABCDEFG&issuer=Demo"

Answer 2

The core concept behind all properly secured two-factor authentication systems involves the user proving their identity using some previously agreed upon mechanism that cannot reasonably be replicated.

The particular mechanism used by most ‘authenticator’ apps is known as TOTP (Time-based One Time Password). This is a modified variant of an older mechanism known as HOTP (HMAC One Time Password). Setup for either mechanism works as follows.

1. When the user requests for a given service to enable 2FA, that service generates a secret to be used for the authentication purpose. The exact details of this generation don’t matter much here, and you can functionally think of the secret as a random number between 0 and some arbitrarily large number.
2. The service then shares this number with the user, typically via a QR code encoding a special URL using the otpauth:// scheme. The details of that are also not particularly important to the discussion, just know that it encodes the secret (and info about the site itself) in such a way that the authenticator device can read it.
3. Once the authenticator reads the secret, it stores it (hopefully) securely together with info about the account provider (and typically some small comment to remind the user which account it is if they have more than one with that provider).
4. The server then (hopefully) securely stores the secret and associates it with the user’s account. It may request one or more codes at this point to ensure that everything is working (and, in the case of HOTP, to ensure that the counter is in-sync, but more on that later).

Once that’s done, the authenticator is configured to provide codes for that account. Actually using the authenticator works as follows:

1. When asked for a code, the authenticator first consults an internal counter. For HOTP, this is a simple counter that gets incremented by one for each code generated for a given account. For TOTP, it’s a timestamp counted in seconds since the UNIX epoch.
2. After determining the counter, the authenticator retrieves the secret, combines it with the counter, and then generates a hashed message authentication code for the combination (typical implementations use SHA-1 for this, but any cryptographically secure hash algorithm can be used).
3. If TOTP is being used, the timeout on the current code is displayed, and once it expires a new one is generated.

The server does exactly the same thing to verify the code.

It’s important to note that once the authenticator is configured, there is no communication the authenticator and the server other than the user entering a code when prompted, and there is no communication at all from the server to the authenticator. This aspect is an extremely important part of why HOTP and TOTP are generally considered secure but SMS or email-based 2FA are generally not.

It is additionally important to note that both HOTP and TOTP have a few inherent limitations:

• HOTP requires the client and server to keep their counters in-sync with each other. If they get out of sync (usually by the user generating multiple codes without using them), then the codes stop working. Many servers will handle the specific case of the client getting ahead of the server automatically up to some limit, and advance the counter to whatever it would be for the code that was used, but that still requires handling, and it adds a nontrivial processing overhead on the server.
• TOTP requires that the client and server generally agree relatively well on the time, and that the user uses the code before it expires. The first issue is generally solved for any internet connected client, but the second gets tricky and usually means that the server will accept a code for some time after it expires. The time-based nature also means that you need a lockout to prevent code reuse, which functionally rate-limits successful authentication attempts (this is not really an issue for any real world use case, and in fact improves security by a tiny bit, but it is a limitation).

Some systems use an approach similar to TOTP or HOTP but with a different algorithm, usually for legacy reasons. One particularly prominent example is Valve’s ‘Steam Guard Mobile Authenticator’, which functionally uses TOTP but fully automates the setup and uses a different mechanism to derive the code from the hash algorithm output.

---

For reference, the other major secure 2FA implementation that is in widespread usage is FIDO2, which works a bit differently but still relies on the concept of the user proving their identity by doing something that only they should be able to do (instead of generating codes, FIDO2 involves digitally signing an authentication challenge using a key that was previously configured with the server, which is technically more secure than TOTP for a couple of reasons).

Answer 3

The short version is - they generate the code the same way. I believe TOTP is the 'standard' here. One of the nice things with 'modern, always online systems is you have reliable time sync - using that and a private key (which is included in the QR code they have you scan), and the same algorithm, you can generate a predictable one time key without a central point of authentication.

This also means in theory (and practice) you can export your keys to another device/TOTP client and as long as your clocks are reasonably accurate it should just work.

If memory serves, they use the OTP you provide the first time to confirm it is the 'correct' time and key but I'm not entirely sure on that.