Take the 2-minute tour ×
Information Security Stack Exchange is a question and answer site for Information security professionals. It's 100% free, no registration required.

I'm not much of a ipsec initiate, so this is a bit over my head ... but I'm always willing to learn more.

Are there any known attacks against OATH TOTP (Google Authenticator's / Authy's algorithm) if an attacker has an (unspecified) number of previous one-time passwords, as generated by the app?

Or, to put it another way: is there any reason to worry about there being a record of individual OTPs that I have used in the past? (For example, can I enter them at the command-line when invoking a tool … or should they be entered like passwords, silently and interactively, to avoid them being recorded?)

share|improve this question

2 Answers 2

up vote 9 down vote accepted

The TOTP specification points, for the security analysis, to HOTP. HOTP uses a counter, shared by both parties, and "resynchronized" every time a successful authentication occurs; TOTP replaces that counter with knowledge of the current time, which is also a shared value. As such, almost all the security analysis of HOTP applies to TOTP.


The security analysis of HOTP uses the formal tools and notations of cryptography, but boils down to the following assumption:

Let T denotes the time to perform one computation of H.  Then if A is
any adversary with running time at most t and making at most p oracle
queries,

                   Adv(A) <= (t/T)/2^k + p^2/2^n

In practice, this assumption means that H is very secure as PRF.

The important word here is PRF: it means that the "H" function (HMAC/SHA-1) behaves, in the view of the attacker (who does not know the key) like a function chosen "at random" among all possible functions. We give the attacker access to an "oracle", which is a machine which knows the key, and computes HMAC/SHA-1 over inputs chosen by the attacker; the attacker can send p such queries. The expression above means that even under these conditions, the probability that the attacker successfully predicts, after all his queries, the output for one extra input (that he did not send to the oracle), is still very low (the "advantage" is what extra success probability the attacker has over pure luck).

Right now, it seems that HMAC/SHA-1 behaves as a PRF. Nobody has found any indication to the contrary. This holds even in the face of the known structural weaknesses which seem to allow (theoretically) some computing SHA-1 collisions.

From this assumption, the security proof of HOTP (as exposed in RFC 4226) establishes the following result:

Suppose m = 10^Digit < 2^31, and let (q,r) = IntDiv(2^31,m).  Let B
be any adversary attacking HOTP using v verification oracle queries,
a <= 2^c - s authenticator oracle queries, and running time t.  Let T
denote the time to perform one computation of H.  If Assumption 1 is
true, then

     Adv(B) <= sv * (q + 1)/2^31 + (t/T)/2^k + ((sv + a)^2)/2^n

In practice, the (t/T)2^-k + ((sv + a)^2)2^-n term is much smaller
than the sv(q + 1)/2^n term, so that the above says that for all
practical purposes the success rate of an adversary attacking HOTP is
sv(q + 1)/2^n, just as for HOTP-IDEAL, meaning the HOTP algorithm is
in practice essentially as good as its idealized counterpart.

This last paragraph is what you are after: under the assumption that HMAC/SHA-1 is a PRF, it is proven that giving access to a lot of previous one-time passwords does not given any advantage to the attacker for guessing the next one, at least no more that what he would get out of an "ideal" version of HOTP in which the one-time passwords are obtained through pure unpredictable magic.


Summary: No need to worry. Resistance of HOTP (and TOTP) to the situation where many previous one-time passwords have been recorded is part of the security model of HOTP, and it has been specifically shielded against such an occurrence. The shield here relies on an assumption of security on HMAC/SHA-1, which, while not proven, is about as good as these things can get (notably because it is quite possible that the fact that a function family is a PRF might be mathematically impossible to prove; see this for more on that subject).

share|improve this answer

The tokens are computed using HMAC libraries, basically:

HOTP(K,C) = Truncate(HMAC-SHA-1(K,C))

Where K is the secret stored on your phone and on the validating server, and C is the counter (timestamp, in case of TOTP).

HMAC-SHA-1 is a one-way function, which means it should be impossible to obtain K,C regardless on any previously observed values. SHA-1 is known to have some weaknesses, but it is still reasonably well-trusted to make such attacks impractical.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.