An OTP app is an OTP app is an…
A recent post on the Gemini blog outlined changes to two-factor authentication (2FA) on Gemini, providing additional background on the Authy service. Past comments suggest there were common misconceptions about Authy, perhaps none more prominent than the assumption that it is based on SMS. Authy is a service which includes multiple options for 2FA: SMS, voice, mobile app for generating codes and OneTouch. At the same time a common question often asked is: “Can I use Google Authenticator or other favorite 2FA application instead?” Making that scenario work turns out to be a good way to gain insight into how Authy app itself operates under the covers.
Authy has mobile applications for Android, iOS as well as two incarnations for desktops: a Chrome extension and a Chrome application. All of them can generate one-time passcodes (OTP) to serve as second-factor when logging into a website. A natural question is how these codes are generated and whether they are compatible with other popular OTP applications such as Google Authenticator or Duo Mobile.
This is not a foregone conclusion and not all OTP-generation algorithms are identical. For example the earliest design in the market was SecurID by RSA Security. These were small hardware tokens with a seven-segment LCD display for showing numerical codes. RSA not only sold these tokens but also operated the service for verifying codes entered by users. For all intents and purposes, the tokens were a blackbox: the algorithm used to generate the codes was undocumented and users could not reprogram the tokens on their own. (That did not work out all that well when RSA was breached by nation-state attackers in 2011, resulting in the downstream compromise of RSA customers relying on SecurID— including notably Lockheed Martin.)
Carrying around an extra gadget for a single purpose limits usability, all but guaranteeing that solutions such as Secure ID are confined to “enterprise” scenarios— in other words, where employees have no say in the matter because their IT department decided this is how authentication works. Ubiquity of smart-phones made it possible to replace one-off special purpose gadgets with so-called “soft tokens:” mobile apps running on smartphones that can implement similar logic without the baggage of additional hardware.
Google Authenticator was among the first of these intended for mass market consumption, as opposed to the more niche enterprise scenarios. [Full disclosure: This blogger worked on two-factor authentication at Google, including as maintainer of the Android version of Google Authenticator] Early versions were open-sourced, although the version on Play Store diverged significantly after 2010 without releasing updates to source. Still looking at the code and surrounding documentation explains how OTPs are generated. Specifically it is based on two open standards:
- TOTP: Time-based OTP as standardized in RFC 6238. Codes are generated by applying a keyed-hash function (specifically HMAC) to the current time, suitably quantized into intervals.
- HOTP: HMAC-based OTP standardized by RFC 4226. As the RFC number suggests, this predates TOTP. Codes are generated by applying a keyed hash function to an incrementing counter. That counter is incremented each time an OTP is generated. (Incidentally the internal authentication system for Google employees— as opposed to end-users/customers— leveraged this mode rather than TOTP.)
The mystery algorithm
So what is Authy using? TOTP is a reasonable guess because Authy is documented to be compatible with Google Authenticator, and can in fact import seeds using the same URL scheme represented in QR-codes. But strictly speaking that only proves that Authy includes a TOTP implementation as subset of its functionality. Recall that Authy also includes a cloud-service responsible for provisioning seeds to phones; these are the “native” accounts managed by Authy, as opposed to stand-alone accounts where the user must scan a QR code. It is entirely conceivable that OTP generation for native Authy accounts follows some other standard. The fact that native Authy accounts generate 7-digit codes lends some support to that theory, since GA can only generate 6-digit codes. (Interestingly the URL scheme for QR codes allows 6 or 8 digits, but as the documentation points out GA ignores that parameter.)
Answering this question requires looking under the hood of the Authy app itself. In principle we can pick any version. This blog post uses the Chrome application as case study, because reviewing Chrome apps does not require any special software beyond the Developer Tools built into Chrome itself. No pulling APKs from the phone, no disassembling Dalvik binaries or firing up IDA Pro necessary.
Understanding the Chrome application
First install the Authy application from the Chrome store:
Next visit chrome://extensions and make sure Developer Mode is enabled:
Now open chrome://apps in another tab and launch the Authy app:
This function computes TOTP in terms of HOTP, which may seem puzzling at first— time-based OTP based on counter-mode OTP? The intuition is both schemes share the same pattern: applying a cryptographic function to some internal state represented by a positive number. In the case of HOTP that number is an incrementing counter, increasing precisely by 1 each time an OTP is generated. In the case of TOTP the number is based on current time, effectively fast-forwarded to skip any unused values.
Looking around this function there are other hints, such as default number of digits set to 7 as expected. More puzzling is the default time-interval set to 10 seconds. TOTP uses a time interval to “quantize” time into discrete blocks. If codes were a function of a very precise timestamp measured down to the millisecond, it would be very difficult for the server to verify it without knowing exactly when it was generated with the same accuracy. It would also require both sides to have perfectly synchronized clocks. (Recall that OTPs are being entered by users, so it is not an option to include additional metadata about time.) To work get around this problem, TOTP implementations round the time down to the nearest multiple of an interval. For example if one were using 60-second intervals, the OTP code would be identical during an entire minute. Incidentally TOTP spec defines time as number of seconds since Unix epoch, so these intervals needs not start on an exact minute boundary.
The apparent discrepancy arises from the fact that Authy app displays a code for 20 seconds, suggesting it is good for that period of time. But the underlying generator is using 10 second intervals, implying that codes change after that. What is going on here? The answer is based on another trick used to make OTP implementations deal with clocks getting out of sync or delays in submitting OTP over a network. Instead of checking strictly against the current time interval, most servers will also check submitted OTP against a few preceding and following intervals. In other words, there is usually more than 1 valid OTP code at any given time, including those corresponding to times a few minutes back and a few minutes into the future. For this reason even a “stale” OTP code generated 20 seconds ago can still be accepted even when the current time (measured in 10-second intervals) has advanced one or two steps.
But we are jumping ahead— there is one more critical step required to verify that we are looking at the right function, that this is the code-path invoked by the Chrome app when generating OTPs. Easiest way to check involves setting a breakpoint in that function, by clicking on the line number:
Now we wait for the app to generate a code. Sure enough it freezes with a “paused in debugger” message:
Back to Chrome developer tools, where the debugger has paused on a breakpoint. The debugger has helpfully annotated the function parameters and will also display local variables if you hover over them:
Tracing the call a few steps further would show that “e” is the secret-seed encoded in hex, “r” is the sequence number and “o” is the number of digits. (More precisely it used to be the secret-seed; this particular Authy install has since been deleted. Each install receives a different seed, even for the same account.) Comparing “r” against the current epoch time shows that it is roughly one-tenth the value, confirming the hypothesis of 10 second intervals.
Recreating the OTP generation with another app
A TOTP generator is defined by three parameters:
- Time interval
- Number of digits
Since we have extracted all three, we have everything necessary to generate compatible codes using another TOTP implementation. Google Authenticator has defined a URL scheme starting with otp:// for encoding these parameters, which is commonly represented as 2-dimensional QR code scanned with a phone camera. So in principle one can create such a URL and import the generator into Google Authenticator or any other soft-token application that groks the same scheme. (Most 2FA applications including Duo Mobile have adopted the URL scheme introduced by GA for compatibility, to serve as drop-in replacements.) One catch is the key must be encoded using the esoteric base32 encoding instead of the more familiar hex or base64 options; this can be done with a line of Python. The final URL will take the form:
Why 8 digits? There is a practical problem with Authy using 7 digits output. The specification for the URL scheme states that valid choices are 6 or 8. (Not that it matters, since Google Authenticator does not support any option other than 6.) Luckily we do not need exactly 7 digits. Due to how HOTP/TOTP convert the HMAC output into a sequence of digits, the correct “7-digit code” can be obtained from the 8-digit one by throwing away the first digit. Armed with this trick we can create an otp:// URL containing the secret extracted from Authy and specify 8 digits. Neither Google Authenticator or Duo Mobile were able to import an account using this URL but the FreeOTP app from RedHat succeeds. Here is the final result, showing screenshots captured from both applications around the same time.
Note the extra leading digit displayed by FreeOTP. Because the generator is configured to output 8 digits, it outputs one more digit that needs to be ignored when using the code.
There is no “vulnerability” here
To revisit the original questions:
- What algorithm does Authy use for generating codes? We have verified that it is based on TOTP.
- Can a different 2FA application be used to generate codes? Sort of: it is possible to copy the secret seed from an existing Authy installation and redeploy it on a different, stand-alone OTP application such as FreeOTP. (One could also pursue other avenues to getting the seed, such as leveraging the server API used by the provisioning process.)
One point to be very clear on: there is no new vulnerability here. When using the Authy Chrome application, it is a given that an attacker with full control of the browser can extract the secret seeds. Similar attacks apply on mobile devices: seeds can be scraped from a jailbroken iPhone or rooted Android phone; it is just a matter of reverse-engineering how the application stores those secrets. Even when hardware-backed key storage is used, the seeds are vulnerable at the point of provisioning when they are delivered from the cloud or initially generated for upload to the cloud.
[Updated Apr 27th to correct a typo]