Take the 2-minute tour ×
Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It's 100% free, no registration required.

My understanding of HOTP is that each password is unique and based on a counter.

$$PASSWORD = HOTP_1(K,C)$$

Where $C$ is an incremental counter.

What I wish to know, is how you keep the client and server in sync? Looking at current systems (google authenticator), there appears to be no indication if the actual 'counter' number, but you can generate successive passwords at will.

What happens if, for example, the password you have generated uses $C = 5$, but the server is expecting $C = 3$?

Also, what is the 'integrity check' for? Google cant seem to come up with a solution.

share|improve this question
add comment

1 Answer

up vote 8 down vote accepted

The HOTP standard describes the resynchronization algorithm (section 7.4). Basically, the server remembers the last value $C$ of the counter for which a correct password was presented. When a new password is to be verified, the server tries $C+1$, $C+2$... until one matches, or $C+w$ is reached for some $w$ called the "window size".

The intended scenario is the following: the client has a handheld device which outputs the successive passwords, one new password per button-press. The client may press the button a few times between two login attempts. The server "bets" that the client will not press the button more than, say, 100 times before attempting to log in again: so the server uses $w = 100$. If you let your 3-year-old nephew play with your HOTP device a whole afternoon, chances are that it will be too much desynchronized, and login will not work any longer.

The server wants to keep $w$ small, because:

  • The raw effect of $w$ is that, at any time, the server will accept $w$ possible passwords; the higher $w$ is, the higher is the risk that an attacker trying random passwords may log in.
  • The computational cost on the server in case of a wrong password is proportional to $w$.

but $w$ must not be too small, because a desynchronized device implies extra costs (more work for the help desk), which should not happen too often, even in the presence of hyperactive infants.

The RFC 4226 contains no instance whatsoever of the word "integrity" so I have no idea what your last question is about.

share|improve this answer
1  
This is a really great answer, exactly what I was looking for. Thanks. I am curious to know what people think of HOTP vs TOTP. It seem to me that TOTP is a more logical solution because it means that the above 'de-synchronisation' is less likely. –  mrwooster Sep 28 '11 at 19:40
1  
@mrwooster: TOTP requires both client and servers to know the current time. The HOTP devices I had access to were embedded in smartcards, with an internal battery but no time source. TOTP is a nice extension to HOTP but is applicable to fewer contexts. –  Thomas Pornin Sep 28 '11 at 20:01
    
Cool, thanks for clearing that up. –  mrwooster Sep 28 '11 at 20:55
add comment

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.