14

Given a one-time password generator that is time-based (such as Google Authenticator), how many instances of (time, PIN) pairs would one need to significantly weaken the algorithm to a point where one would be able to narrow down possible seeds to the original function? If one were to send out PINs to clients via SMS or email (instead of using a keyfob or the actual Google Authenticator app which does not let one see past PINs), would a compromise that reveals past PINs be a significant threat to the system (note that both emails and SMS carry relatively precise time information)?

The question is related to the design of a two-factor authentication system on whether it should involve any timestamped storage of the one-time passwords generated. If this significantly weakens the security of the system, then one would argue that the design should not include any storage of past OTPs (emails, SMS or otherwise).

Per advice by folks on stackoverflow, this is re-asked here: https://stackoverflow.com/questions/9041162/reverse-engineering-one-time-passwords-for-two-factor-authentication-systems (question there will point to this one here)

Improve this question

3 Answers 3

Reset to default
12

If the OTP generation algorithm is any good (and HOTP is good):

  • the best attack when knowing one generated password, and trying to guess the next one, should be exhaustive search on the key (and exhaustive search is not doable if the key is large enough, e.g. a 128-bit key);
  • knowing many previous passwords should not give any additional advantage to the attacker.

Appendix A of RFC 4226 details the security analysis of HOTP; at its core lies the hypothesis that HMAC/SHA-1 is a key-selected random function:

To be more precise, let Maps(c,n) denote the set of all functions mapping from {0,1}^c to {0,1}^n. The idealized algorithm has key space Maps(c,n), so that a "key" for such an algorithm is a function h from {0,1}^c to {0,1}^n. We imagine this key (function) to be drawn at random.

This is the random oracle model. HMAC with a secure hash function, or even HMAC with a slightly weak hash function like SHA-1, is about the best practical approximation of a random oracle that cryptographers have in store.

To sum up the security proof of HOTP:

  • with a random oracle, you know nothing of the output for a given input until you try it on that exact input;
  • the generated passwords are (derived from) the output of HMAC/SHA-1, believed to be indistinguishable from a random oracle, over a counter value;
  • thus, nobody knows anything of a password which will be generated until the corresponding counter value is actually entered as input of HMAC/SHA-1, something which did not occur previously (for the older generated passwords) because that's a counter and it does not "wrap around".

There are details to take care of, of course, but the RFC writers are known cryptographers and the proof detailed in appendix A is sound and clear (and has been reviewed by many other cryptographers, which is the real test of security).

Improve this answer
2
  • I guess the main argument in the RFC is that the risk of HOTP algorithms for counter-based systems lies in the "wrapping-around" of the token at some point (governed by the size of the counter, c) but in time is the counter (and it never wraps around). Since the attacker can never see the entire list of generated tokens, brute force attacks would be impossible.
    – Clement P
    Jan 28, 2012 at 23:37
  • I meant "...in time-based systems, current time is the counter..." and I guess the last sentence should read "brute force attacks would be the only way to go"
    – Clement P
    Jan 28, 2012 at 23:43
5

According to the RFC:

The analysis demonstrates that these final steps introduce a negligible bias, which does not impact the security of the HOTP algorithm, in the sense that the best possible attack against the HOTP function is the brute force attack. Assuming an adversary is able to observe numerous protocol exchanges and collect sequences of successful authentication values. This adversary, trying to build a function F to generate HOTP values based on his observations, will not have a significant advantage over a random guess. The logical conclusion is simply that the best strategy will once again be to perform a brute force attack to enumerate and try all the possible values.

So according to the security analysis there's virtually no difference whether or not you store or have access to old OTP values. You basically can't use them to increase the chances of finding a right OTP value.

Improve this answer
2
  • Thanks, I might add however, that for counter-based implementations, if it ever wraps around, you do have a problem there if you have access to the list of historical tokens. However, in time-based implementations, since it naturally throttles the number of tokens generated and never wraps around, knowing past tokens does not help. In any case, it seems like a time-based HOTP implementation is the way to go (as long as you have relatively accurate clocks, which we do).
    – Clement P
    Jan 28, 2012 at 23:42
  • The counter should never wrap. The spec does mention that it is only incremented, but I haven't seen anything explicit there about wrapping. If the counter needs to wrap, you'd need to issue a new key.
    – Yoav Aner
    Jan 29, 2012 at 17:49
2

The security of the one-time-password generator obviously must not be weakened by knowing previous passwords.

The key point is that the use of symmetric cryptography with a key known only to the token and the validation service (RFC 4226) does not allow you to narrow down what you call possible seeds beneath the search space for the symmetric key / algorithm combination used for encryption - which in turn should be chosen large / secure enough to make a brute-force attack impractical.

Improve this answer

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .