# How does HOTP keep in sync?

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.

-

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.

-
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
@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