# How does the small n attack work?

I'm studying the Lamport's Hash one-time password scheme.

This is the scheme:

Alice wants to authenticate herself to Bob from a workstation that knows nothing about her. Alice only knows her password. Bob knows

1. Alice types her name and her password into her Workstation
2. The Workstation sends "Alice" to Bob
3. Bob sends n to the Workstation
4. The workstation computes x = hash^(n-1) (pwd) and sends it to Bob
5. Bob hashes it once and compares it with database. If it matches, Bob considers the response valid, replaces the stored quantity with the received quantity, and replace n by n-1.

This scheme has a security weakness called small n attack.

This is the explanation given in "Network Security: Private Communications in a Public World":

Suppose an intruder, Trudy, were to impersonate Bob's network address and wait for Alice to attempt to log in. When Alice attempts to log into Bob, Trudy sends back a small value for n, say 50. When Alice responds with hash^(50) (pwd), Trudy will have enough information to impersonate Alice for some time, assuming that the actual n at Bob is greater than 50.

I don't understand this. I would need a different explanation.

• To start with, suppose Trudy sends back zero as n. ​ ​ – user991 Aug 19 '15 at 12:53
• Is such case the workstation can't compute x = hash^(0-1) (pwd) – Loris Aug 19 '15 at 12:55
• Oh, I didn't notice that the description had a -1 instead of a +1. $\:$ In that case, one should consider the effect of Trudy sending back 1 as n. $\;\;\;\;$ – user991 Aug 19 '15 at 13:05
• If n gets to 1, Alice has to choose a new password. (If a salt is used, change it, the password is the same). – Loris Aug 19 '15 at 14:55

The reason Lamport's scheme is secure against a passive attacker is that even if they see $H^{n-1}(p)$ for a given $n$, the server would require the preimage of that hash, $H^{n-2}(p)$ on the next login.
3. Bob sends $n$. Trudy intercepts it and replaces it by for example $n' = n-10$.
4. Workstation computes $h = H^{n'-1}(p) = H^{n-11}(p)$. Trudy intercepts and replaces by $H^{n-1}(p) = H^{10}(h)$.
Now Trudy can calculate the next ten hashes that Bob expects, like the next one: $H^{n-2}(p) = H^{9}(h)$. This allows several logins as Alice.