Two-factor authentication with TOTP
A (not too) technical introduction to Time-based One Time Passwords
For a long time we only used username and password to access online services, then banks and other critical institutions started rolling out an additional authentication mechanism based on devices (hardware tokens) generating time-based disposable passwords, often required when performing sensitive operations, like sending a payment or changing contact information.
After one online service after another—including some big ones—suffered a data breach in the last years, more and more services started deploying a similar extra layer of authentication, but instead of requiring you to own an additional device, they simply exploited something we carry with us all the time: our smartphone.
The most common approaches include:
- sending the password via email
- sending the password via SMS
- using a so-called software token or virtual device, a mobile application capable of generating such disposable passwords
In this article I’m going to explore the third approach, which is probably a little annoying for the user since it requires installing an application on the smartphone and setting it up for each service, but it has few advantages: your smartphone can generate the passwords without communicating with the server (which works even if there’s no signal, unlike email or SMS) and you don’t have to give away your phone number.
These are the most relevant acronyms you will encounter:
- 2FA: Two-Factor Authentication
- HMAC: Hash-based Message Authentication Code
- HOTP: HCMA-based One Time Password
- OTP: One Time Password
- TOTP: Time-based One Time Password
- U2F: Universal 2nd Factor
Before embracing 2FA, you should be aware of the involved security trade-offs, clearly explained in this article.
Prologue (for end-users)
If you want to start using 2FA, just take a look at https://twofactorauth.org or https://www.turnon2fa.com to see if the online services you use support two-factor authentication.
Your email provider should be on top of your checklist, since someone gaining access to your email account could potentially change the passwords of all your services using standard password recovery procedures.
In addition, you should regularly visit https://haveibeenpwned.com to check if your email address has been involved in some data breach. If so, change the password of your email account immediately and — if you didn’t do it already — see if you can enable 2FA.
If you want to go even further, you should take a look at the U2F authentication standard, which requires a hardware token — like a YubiKey — and it’s gaining support in the industry, including:
- Dropbox
- GitHub
- GMail
- …
So, let’s say you just discovered that your favorite service supports 2FA using a software token. If you don’t have an authenticator app already installed on your smartphone, you must pick one:
- FreeOTP (Android, iOS): my favorite choice, this open-source application is maintained by Red Hat and supports almost any possible TOTP configuration
- Google Authenticator (Android, iOS): made by and for Google, works with other services too but only supports passwords based on the recommended TOTP configuration
- Microsoft Authenticator (Android, iOS): made by and for Microsoft, it works with other services too
Starting to use this authentication factor with a new service is as easy as scanning a QR-code with your authenticator app.
Now let’s dig into the details of the TOTP algorithm.
How it works (a little math behind)
Technical information is available in RFC-4226 (HOTP) and RFC-6238 (TOTP).
TOTP is an algorithm — based on HOTP — that generates a one-time password from a shared secret key K and the current timestamp T using a hash function H.
The shared secret key K is a Base32 string — randomly generated or derived — known only to the client and the server and different and unique for each token.
The algorithm MUST use a strong shared secret. The length of the shared secret MUST be at least 128 bits. This document RECOMMENDs a shared secret length of 160 bits.
— RFC-4226
The keys SHOULD be randomly generated or derived using key derivation algorithms. […] The keys MAY be stored in a tamper-resistant device and SHOULD be protected against unauthorized access and usage.
— RFC-6238
Given a time step size of X seconds, let’s define a counter C representing the number of time steps elapsed until the current Unix timestamp T. Using X = 30 seconds we obtain the following values for C:
- C = 0 if T is between 0 and 29 seconds
- C = 1 if T is between 30 and 59 seconds
- C = 2 if T is between 60 and 89 seconds
- …
A larger time-step size means a larger validity window for an OTP to be accepted by a validation system. […] First, a larger time-step size exposes a larger window to attack. […] In general, a larger time-step window means a longer waiting time for a user to get the next valid OTP after the last successful OTP validation.
— RFC-6238
Finally, the algorithm requires a hash function H to generate a digest and truncate it to obtain a password of D digits.
The value displayed on the token MUST be easily read and entered by the user: This requires the […] value to be of reasonable length. The […] value must be at least a 6-digit value. It is also desirable that the […] value be ‘numeric only’ so that it can be easily entered on restricted devices such as phones.
— RFC-4226
The recommended settings, aiming to offer the best compromise between security and usability, are the following:
- X (time step): 30 seconds
- D (password length): 6 digits
- H (hash function): SHA-1
- |K| (length of secret key): 160 bit
As result, each password is a 6-digit number derived from a 20-bytes SHA-1 digest and valid within the 30-seconds time step in which it was generated.
TOTP(K, C) = Truncate(HMAC-SHA-1(K, C))Validation
When the validation server receives an OTP from a client, it computes the OTP on its own using the shared secret key K and its current timestamp (not the timestamp used by client) and compare the OTPs: if they are generated within the same time step they match and the validation succeeds.
If the client sends an OTP close to the end of a time step, due to network latency or performance issues, the server may start processing the request in the following time step, resulting in a validation failure.
For this scenario, the validator should allow a delay window s and compare OTPs not only in the current time step but also with the next and previous s time steps. So with s = 1 (recommended value) we verify the client OTP in the current time step and eventually in the previous and next time steps.
A larger acceptable delay window would expose a larger window for attacks. We RECOMMEND that at most one time step is allowed as the network delay.
— RFC-6238
Re-synchronization
Since client and server clocks can slowly desynchronize until not even the window delay is enough to guarantee that the validation works, an explicit re-synchronization mechanism should be available.
The client could then send multiple consecutive OTPs and the server validate the sequence within a range of time steps wider than the delay window, since for an adversary forging a valid sequence of 2–3 consecutive OTPs would be much more complicated than guessing a single OTP. Nonetheless you should set a reasonable upper bound to avoid denial-of-service attacks, with your server trying all possible time steps from here to eternity.
If a match for the OTP sequence is found, the clock’s drift can be recorded (as the number of time steps) so that the validation algorithm will take it into account when receives new OTPs.
The validation server can also track the clock’s drift upon successful validations, such reducing the need for manual re-synchronization.
Throttling or delay
[The authentication protocol] SHOULD NOT be vulnerable to brute force attacks. This implies that a throttling/lockout scheme is RECOMMENDED on the validation server side.
— RFC-4226
So far you have a working validation system, but you are still vulnerable to brute-force attacks, which under normal circumstances represent the most convenient approach for an adversary.
No matter what strategy the adversary uses, […] its success probability will not be above that of the brute force attack […] as long as the number of authentications it observes is not incredibly large.
— RFC-6238
Let’s imagine an adversary capable of trying a lot of validation attempts from multiple devices. Two suggested countermeasures are:
- setting a throttling parameter v, which represents the maximum number of validation attempts before the account is locked
- adding an increasing delay between consecutive validation attempts (e.g. if you double the delay after each attempt, brute-force attacks become quickly unfeasible)
The delay or lockout schemes MUST be across login sessions to prevent attacks based on multiple parallel guessing techniques.
— RFC-4226
Recovery
If you read the article I mentioned earlier, you probably know that one of the main trade-offs with 2FA is the risk of being locked out of your account if your device is forgotten, broken, lost, stolen, … and that having a robust recovery procedure is of the utmost importance.
How a user can quickly and safely regain access to their account in such a scenario is a critical issue, but how can you be sure a recovery request comes from the legitimate user instead of an adversary trying to circumvent your additional authentication factor?
Sadly there’s no standard procedure: Google, for example, gives you a list of backup codes while encouraging you to setup additional authentication factors (es. SMS codes, security keys, …); Amazon requires a phone number to send you a security code in case your primary device is not available (it goes without saying that you should not give them the number of the phone you installed the authenticator app on, but that’s not exactly practical). Amazon Web Services uses a different procedure altogether for its IAM users, sending a backup code via email and then making a phone call.
These procedures generally use something you know (backup codes) and/or own (email address, smartphone, security key, …) to prove your identity and verify the legitimacy of the recovery request.
Building a recovery procedure that allows the user to timely regain control of their account in such bad circumstances is not trivial and pros and cons of each possible approach must be considered. For example, if you do not want to force a user to give you their phone number, you could send a short-lived backup code to the email address associated to their account, trusting on the fact that the email account hadn’t been compromised.
Security at a glance
A detailed security analysis of the HOTP algorithm is available in the appendix A of FC-4226 while additional TOTP security considerations are available in section 5 of RFC-6238.
To summarize, the probability P of a successful attack (i.e. an adversary guessing the correct OTP) can be approximated as follows:
P = s * v / 10^Dwhere:
- s is the look-ahead synchronization window size (our delay window)
- v is the number of verification attempts
- D is the number of digits in TOTP values.
This simple formula — the ratio between the number of accepted OTPs at a certain time and all possible OTPs — gives a very understandable approximation of how the algorithm parameters affect its strength.
Obviously, generating passwords with more digits exponentially reduces the probability of a successful attack. But even without changing the password length, we could slightly reduce such probability expanding the alphabet, using for example alphabetic characters in addition to digits. If we consider the English alphabet of 26 letters, we would obtain P = s * v / 36^D .
On the other hand allowing more attempts and — for each attempt — expanding the validation window essentially increase the set of OTP values the validation server would accept. That’s why s and v should be chosen very carefully if you decide not to use the recommended values for some (very good) reason.
If you have any feedback or question, let me know in the comments.
