Can a Time-based One-time Password (TOTP) key be decoded from generated values?

Question

If you have access to generated Time-based One-time Password (TOTP) values, is it theoretically possible to decode the secret key?

If yes, how much time and about how many generated values are needed?

Answer 1

TOTP is explicitly designed to resist this.

TOTP is based off of HMAC-based One-time Password (HOTP), which works as follows:

• Two parties share a randomly generated key, k, generally called the "shared secret". This key must remain private.
• Both parties maintain a counter value, c, that is incremented whenever authentication is performed.
• Authentication is performed by computing HMAC(c, k) where HMAC is some HMAC function such as HMAC-SHA256. The resulting hash value is then processed to extract some number of bits, which can then be transformed into a number of decimal digits in order to produce an authentication code. This extraction and transformation is generally called "truncation" in this context.
• The party that needs to be authenticated (e.g. a user) sends the digits to the other party (e.g. a server), who computes the the same hash value and performs truncation and compares it to the digits provided. If they match then the user is authenticated.

Since both sides know the same key and (theoretically) maintain the same counter, they can always authenticate together. Usually the party doing the authentication adds in some leeway for counter desync, e.g. by computing all the possible codes from c to c + 5 an accepting any that match. This results in a security reduction but allows for some counter desynchronisation between parties.

TOTP modifies this scheme so that c is replaced with c_t, which is a time-based value. The value of c_t is calculated as c_t = (t - t₀) / t_x, where t is the current time (e.g. in Unix epoch seconds), t₀ is the time at which the token was created, and t_x is an interval time such as 30 seconds. Effectively what this results in is a c_t value that increments every 30 seconds. As long as both parties' clocks are roughly synchronised and are not skewed (they may have different clock times set, but t₀ compensates for that as it is set independently by each party) this results in both clients producing the same TOTP outputs at the same time.

Breaking this scheme by only knowing what digits were given out (even if millions of codes were known) is not feasible as it would require a full key recover attack against the HMAC hash algorithm (e.g. HMAC-SHA1 or HMAC-SHA256) which has not yet been done. For proper HOTP and TOTP implementations you are protected against key recovery and even counter recovery.

However, not all implementations use a proper HMAC function as the keyed PRF. Some HOTP implementations, such as those in radio-operated garage openers, utilise a proprietary PRF or even something like CRC32 in order to generate the hash value before truncation. These can usually be broken by recovering a few values becuase the search space is so small.

Answer 2

Anything is possible with brute force and enough time...

As described in the informational (non-standards-track) RFC 6238, the Time-based One-time Password (TOTP) algorithm, at the time of the RFC being written, commonly used SHA-1 as the base of its HMAC. The HMAC-based One-Time Password (HOTP) algorithm (RFC 4226 (informational)) that forms the foundational part of TOTP says that the shared secret should be at least 120 bits in length, and recommends 160 bits for its key.

This effectively gives us a 160 bit pseudo-random number, when combined with a message that always changes (the current timestep, usually how many 30 second periods have elapsed since Jan 1, 1970). These 160 bits come from a key with an entropy source of at least 120 bits.

On a modern consumer desktop computer, a recent benchmark was able to hash small messages, about the size of our key + time, using SHA-1 at a rate of 1,000,000 taking about 600ms. (Please take benchmarks with a grain of salt(*). I include the benchmark to get a back-of-the-napkin figure for my calculations, not to try to give a definitive answer.)

This means that every 0.6 seconds, we can add 1 million values to our rainbow table for any given time block. It will only take us 7.9*10^30 seconds (25 quintillion millenia) to build a complete rainbow table for any one 30 second time block, given 120 bit keys.

But hey, we aren't actually trying to gain access to an account in real time, right? We have all of the resources of state level actors and all the time in the universe. We can just assume that all of the pertinent rainbow tables already exist, here in our time bubble well past the heat-death of the universe.

Each one-time password is 1,000,000 decimal digits out of a 160 bit value. Each time we compare, we are removing 99.9999% of the potential keys. With 1.4*10^48 possible keys, it will only take us 8 or 9 cycles to figure out the key. Only 200 quintillion millenia to break a TOTP key? Not bad!

Of course, if they're using SHA-2, or the recommended 160 bit keys, then things will take a bit longer...

Footnote: (*) On the topic of taking things with a grain of salt, please salt your passwords. It makes them tastier.