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
up vote 2 down vote accepted

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.

The active attack, in comparison, allows Trudy to find an earlier iteration than the server is expecting. That allows calculating several login hashes by iteratively hashing the captured one. It is even possible to do it transparently to the user, by replacing the hash they give by the one the server is expecting.

  1. Alice types the name and password.
  2. Workstation sends "Alice".
  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)$.
  5. Bob hashes once, sees a match.

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.

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

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