Welcome back to the two factor authentication (2FA) series!
If you haven’t already, check out the first article in the series that explains what 2FA is and why you really should enable it on your accounts (yes, even if you have a strong, unique password).
In the previous article, I introduced time-based one-time passwords (TOTP). I covered the registration and authentication workflows, highlighted usability tradeoffs, and discussed some of the important technical aspects of TOTP. However, I avoided getting too deep and explaining the details of the TOTP algorithm itself.
This article is going to serve as a medium dive into precisely that topic. It will be much more technical than the previous article, but does leave out some important low level details. Here is a quick list of references for the tech minded among us who want to dive straight into the specifications themselves:
- Google Authenticator - Key URI Format
- HOTP: HMAC-Based One-Time Password Algorithm
- TOTP: Time-Based One-Time Password Algorithm
For everyone else interested in that middle ground explanation, read on!
Quick TOTP recap
I think it would be helpful to quickly recap the main points from the previous article about how TOTP actually works.
After Alice starts the TOTP 2FA registration process, the service provider displays a QR code and prompts her to scan it with an authentication app on her trusted device. If this is the first time that Alice has used TOTP 2FA, she will need to go to the app store to install a compatible app. Normally, the service provider will recommend one or two specific apps, but any app that implements the TOTP algorithm will generate the same exact OTP codes.
Once the app is installed, Alice will use it to scan the QR code displayed in her browser. During this step, a shared secret is saved onto her trusted device. This shared secret is foundational to how TOTP works and we’ll get more into the weeds on that in this article. Using the shared secret, the authenticator app on Alice’s trusted device generates a 6-digit code that Alice manually enters into her browser to complete the registration process.
As you can see in the diagram, there are two areas that I want to cover in more detail. First, is taking a look at what exactly gets encoded in the QR code. Second, is how the OTP is actually generated on the trusted device and verified by the service provider.
QR codes and shared secrets
In the previous article, I explained how a QR code is simply a way of encoding some data, such as plain text characters. Remember these fun examples?
In TOTP 2FA, things are a bit more serious. The QR code encodes a specifically formatted URI that includes important information that is necessary to generate valid OTP codes locally on the trusted device.
The Key URI Format wiki page in the Google Authenticator GitHub repo has full details on the format, but here is an overview.
The URI starts with a specific scheme otpauth:// and defines which algorithm (HOTP or TOTP) should be used. Don’t worry if you’re not familiar, I’ll explain each of those below. It also includes Alice’s email address/username and the name of the service provider so that the app can visually associate an account to an OTP. The URI also defines specific parameters required to generate the OTP, such as the hashing algorithm to use and the frequency at which the app should generate new OTPs. Most importantly, it includes the shared secret that gets saved onto the trusted device.
You may remember that one of the main sources of vulnerabilities with SMS 2FA was that the OTP generated by the service provider can get attacked/compromised/hijacked in a multitude of ways when it is sent through the phone networks.
TOTP 2FA is a huge step in forward in terms of security because it completely removes the phone company (and its associated vulnerabilities) from the registration and authentication flows. Instead of sending a secret over the network, the secret is visually transmitted via the QR code. Though TOTP 2FA does have its own vulnerabilities, which I talked about in the previous article, the use of the QR code does remove the possibility that someone is going to intercept the shared secret during the registration process, which provides a much smaller attack surface compared to SMS 2FA.
So, after the shared secret and related parameters are saved on the trusted device, how is that information used to actually generate the OTP?
HOTP: the precursor to TOTP
To understand the TOTP specification, we must first understand a different specification called HOTP: HMAC-Based One-Time Password Algorithm that was codified in 2005.
That acronym is a mouth-full, so let’s break it down. The “one-time password” part is straightforward: the algorithm involves creating codes/passwords that are valid for a single use.
The “HMAC” part stands for Hash-based Message Authentication Code, a specific type of the more general category of Message Authentication Codes (MAC). A MAC is something that can verify both the integrity and authenticity of a message. In other words, if you send a message to someone and include a MAC, then your recipient can use the MAC to verify that the message was not tampered with after you wrote it (integrity) and can verify that you wrote the message (authenticity).
The most important part of the HMAC acronym for our purposes is “Hash-based.” Back in the introduction article to this series on 2FA, I discussed two properties of cryptographic hash functions that are critical to understanding the basics of how passwords are securely stored in a database. As the HMAC acronym implies, cryptographic hash functions are foundational to the HOTP algorithm, so let’s recap what we learned previously and introduce a third important property:
- Property #1 - Any input to the hash function will always give you the same output hash value; it is a deterministic function.
- Property #2 - Given the output hash value, it is computationally infeasible to calculate the original input; it is a one way function.
- Property #3 - A small change to the input of the hash function should result in a drastic change to the output hash value, such that the new output cannot be correlated to the old output (not correlatable).
Remember, the overall goal is to allow Alice’s trusted device and the service provider’s server to generate the same value (the password part of an OTP) and that the value should only ever be valid a single time (the one-timedness of an OTP).
What would happen if we just hashed the shared secret?
hash (shared secret) = X
Property #2 (one way function) assures us that if an attacker got hold of the output value X, then they could not calculate the input to the hash function; in this case, the shared secret. We want the shared secret to remain secret, so this is good. However, Property #1 (deterministic function) assures us that anytime we hash the shared secret we will always get the same output value X. If we always sent the same value X over the network, then someone could just intercept X on the network and ruin our day. The hash function doesn’t provide any additional protection in this case and it is basically the same as if we just sent the shared secret itself over the network instead. Also, since the value never changes, an attacker who gets hold of the output value X can log into Alice’s account as many times as they want since the “OTP” value never changes; it is just a second static “password.”
The HOTP algorithm introduces a shared counter in order to provide that desired one-timedness property:
hash (shared secret + shared counter) = OTP
HOTP requires that Alice’s trusted device and the service provider each keep track of a local counter that starts with a value of zero (0). Each time Alice logs into the service and asks her authenticator app to generate a new OTP, the authenticator app uses the current value of the counter to generate an OTP.
Alice’s trusted device: hash (shared secret + 0) = OTP
After generating this OTP, the authenticator app increments its local counter by 1.
Because the service provider’s counter also started at zero, it can run the same exact calculation that was run on Alice’s trusted device and verify that she entered the correct OTP.
Service provider’s server: hash (shared secret + 0) = OTP
The next time that Alice logs into the service, the same process will repeat, but now the counter will have a value of 1. The login after that a value of 2, then 3, etc.
Property #1 (deterministic function) assures us that the value calculated on Alice’s trusted device will exactly match the value calculated on the service provider’s server because they both use the same input values.
Property #2 (one way function) assures us that an attacker who observes the OTP (output value) cannot use it to calculate the shared secret (input value).
Property #3 (not correlatable) assures us that each value of the shared counter will generate an OTP that is drastically different and cannot be correlated to OTPs generated in the past or future. If an attacker observes multiple OTPs in a row, then they still won’t be able to calculate the shared secret nor will they be able to calculate the value of the next valid OTP.
This is all looking great! Of course, there is a “but.”
The shared counter is only incremented when Alice actually logs into the service, which makes the next valid OTP value “long-lived.” In other words, without knowing the shared secret or the counter value, an attacker could simply start guessing the value of the next OTP. For example, “000-000”, “000-001”, “000-002”, etc. Eventually, the attacker would guess the correct value of the OTP by sheer brute force or luck.
HOTP does require service providers to implement a rate limiting mechanism to prevent attackers from brute force guessing the next OTP, but having a long-lived OTP is still not a great security property.
TOTP: short-lived one-time passwords
The TOTP: Time-Based One-Time Password Algorithm was proposed in 2011 as an extension to HOTP in order to generate short-lived OTPs. TOTP works the same exact way as HOTP, but with one critical change: it replaces the shared counter with the current time.
hash (shared secret + time) = OTP
Property #1 (deterministic function) assures us that both parties can still calculate the same OTP since they will both still use the same shared secret and same time input thanks to NTP. If you’re thinking “NTP doesn’t guarantee the exact same time on each device”, then you caught my hand waviness. Check out the spec for more detail on how TOTP uses a time- window to solve this problem.
Property #2 (one way function) assures us that an attacker who observes the OTP still cannot use it to calculate the shared secret.
Property #3 (not correlatable) assures us that, just like the previously used counter value, each new time input will generate an OTP that is drastically different and cannot be correlated to OTPs generated in the past or future.
Including the current time as input to the hash means that the valid OTP changes at a static interval (e.g. every 30 seconds) even if Alice does not log into the service. This creates a significantly smaller window of opportunity for an attacker to brute force the next OTP. Combined with a reasonable rate limiting scheme, it is insanely unlikely (yes, that is a technical term) that an attacker can reliably brute force the next OTP within 30 seconds.
However, it is important to realize that an attacker can still just get lucky! If they launch a brute force attack and happen to guess the correct 6 digit OTP within the first few tries permitted by the rate limiting scheme, then they will be able to successfully authenticate into Alice’s account. Clearly, this is not a desirable security property. The Push and U2F methods of 2FA both take a different approach that does not suffer from this problem. Stay tuned for articles later in this series explaining how those work!
Bringing things full circle, let’s take a look at the URI encoded by the QR code. Hopefully, the parameters make more sense now.
Via the QR code, the service provider is telling the authenticator app which hash algorithm it will use to generate OTPs locally on its servers. The URI also specifies how often it is going to change the time inputs and how many digits should be included in the generated OTP. This allows the authenticator app to run the exact same calculation locally on Alice’s trusted device and generate the same OTP.
I hope you enjoyed this medium dive into the TOTP specification and related background. If you are interested in a full deep dive, check out the links at the beginning of this post for the specifications themselves.
If you’ve stuck it out til the end, then you should definitely join the email list below to make sure you don’t miss the next article in this 2FA series! I highlighted some of the security drawbacks of TOTP in this article, such as the ability for someone to randomly guess an OTP. I will explain how Push and U2F both avoid that problem and are both arguably easier to use as well!