Authentication - Lamport's One-Time Password Scheme

Lecturer: Professor Fred B. Schneider

Lecture notes by Fred B. Schneider
Read the original by Leslie Lamport: Password Authentication with Insecure Communication Communications of the ACM 24, 11 (November 1981), pages 770-772.

A one-time password, by definition, can be used at most once to login to a remote computing system. The first use of the password would grant access; a second or subsequent use of the same password would not. Clearly, such a mechanism is useful when passwords are being transmitted in the clear over a network in the presence of passive wiretappers who are monitoring communications.

We assume the user has selected some secret p. This secret will be used to generate a sequence of passwords m1, m2, ..., m1000. We require that knowledge of i and mi does not help an attacker compute mk for any k where i < k holds, because this ensures the attacker cannot deduce a future (as yet unused) password from a past (already used) password.

The requirement that an attacker cannot derive a future password from a past password is satisfied if we define mi to be H1000-i(p) where H is a hash function known to all. For example, after m6 (which equals H994(p)) has been used, the attacker can compute H(m6) (which equals H995(p), the already used password m5) or H(H(m6)) (which equals H996(p), the already used password m4); but the attacker cannot compute m7, because m7 equals H993(p), and computing H993(p) from H994(p) would require the attacker to compute the inverse of H or to know p.

Notice that by defining mi to be H1000-i(p), a user need not explicitly store the entire list m1, m2, ..., m1000 of one time passwords. It suffices for the user to store p and, in a response to a challenge for mi, for the user to simply compute H1000-i(p).

It would be unwise to store p or the list m1, m2, ..., m1000 of one-time passwords on the remote computing system, since an attacker who stole that information would thereafter be able to login. A standard method for handling this problem is:

Note that learning HP (equivalently H(c)) does not give the attacker information from which password c can be derived, because hash functions are not invertible. Moreover, for the case where c is some one-time password mi, then knowledge of HP (equivalently H(mi)) does not give the attacker information from which any later password mk (for i < k ) can be derived. The proof was already given above.

The outline of a protocol should start to become clear.

Because mi-1 = H(mi) holds, the system can use previous password mi-1 as the value of HP against which the hash of mi is checked in the final step above.

After a user has successfully provided mi in response to challenge i, the next challenge would be i+1, then i+2, and so on. What should happen if the user's response to a challenge does not reach the remote computing system? To repeat that identical challenge would be unwise, because an attacker might have intercepted the user's response and that attacker would then be able to replay that response (and be granted access to the remote computing system). So we conclude that absence of a timely response to challenge i should force the next challenge to be a value j where i < j holds.

If HP = mi-1 and messages have been lost so the next response received by the remote computing system is to a challenge j where i < j holds, then comparing mj with HP is not the right thing to be checking. Since HP = mi-1 and by definition mi-1 = H1000-(i-1)(p), we should be comparing H(mi-1) with Hj-(i-1)(mj). To validate that this check is what we want, we expand H(mi-1) obtaining H1000-(i-1)(p) and we expand Hj-(i-1)(mj) obtaining Hj-(i-1)(H1000-j(p)) = H1000-(i-1)(p)).

All of the elements are now in place, and we obtain the following protocol for a user A and remote computing system S. 

System stores for each user A:
  integer n  initially 1 {the next challenge to make}
  integer f  initially 0 {mf is the last password received}
  integer HP initially H1000(p)  {=mf}

A --> S:  request login

S --> A:  challenge is: n

A --> S:  response is: mn

      S:  Check whether for response v just received
               HP = Hn-f(v)
          holds.
          If it does:  HP := v;   f := n;   n := n + 1
          If it does not or there is a timeout:  n := n + 1
A final note concerns initialization and exhaustion. To start off, each user A must invent a secret p and then securely convey H1000(p) to S. Moreover, this exercise must be repeated (with a different secret) whenever the list of 1000 one-time passwords has been exhausted.

Large n attack

Notice that an attacker who somehow learns mx where x is close to 1000 is able to compute most of the one-time passwords in the list of 1000. And there are circumstances where this could be contrived. In particular, in a system where A does not authenticate the source of the challenge (in the second message), an attacker could impersonate S and send to A a challenge value x that is close to 1000.

There are two defenses. The first, alluded to above, is for A to authenticate the source of any challenge before generating a response. A ignores challenges that do not come from S. The second would be for A to remember the last challenge to which A responded. Receipt of a challenge that is significantly larger than this last challenge should then be seen as suspicious and should be ignored---either A's previous responses have not reached S (and n >> f ) or a large n attack is in progress, and both are cause for concern.

Test Your Understanding:

  1. Is the test Hf-n(HP) = v a plausible alternative to test HP = Hn-f(v) currently being used in the protocol? Validate this check or explain why it cannot replace the test currently there.

  2. What are the consequences if A responds to a challenge i with a password mi+j where j>1 holds? Is it possible to modify the protocol given above to cope with this situation in a sensible way? If so, what modifications suffice; if not, explain why.