So here I am, googling my brain on the possibilities of impersonation attempts by a MITM attacker on Lamport's one-time password scheme.

Here's my scenario:

Say we have a client and server setup. Given a nonce $n$, and a hash function $h()$, a client computes the hash of $n$ several times (say $100$) and sends at first instance $H^{(100)}$ where $H^{(100)}=h^{(100)}(n)$. First, how does the server authenticate the identity of the client for the first client-provided value, $H^{(100)}$? Digital signatures/certificates?

For a subsequent authentication, the client sends $H^{(99)}$ and the server computes $h(H^{(100)})$ and if the computation matches the value held by the server (i.e, $H^{(100)}$), the server authenticates the client.

Now assuming there is an attacker in the middle of the communication, can't the attacker simply intercept $H^{(99)}$ from the client and send $H^{(99)}$ to the server, thus impersonating the client only for this particular session where $i$ is $99$. This would mean that the server instead authenticates the attacker instead of the client. Isn't this impersonation possible? And if so, how does Lamport's OTP protect against this.

Using digital signatures or public-key encryption for every session of authentication doesn't seem to be Lamport's idea for the use of his OTP scheme. My understanding of Lamport's OTP is that it makes use of ONLY hash functions.


2 Answers 2

  • On the short side

    The one side of the security of Lamport's One-Time Password (LOTP) is based on the fact that the server stores the last hash and for the next time, requires the previous hash and hashes it to compare to the last stored one. Therefore the attacker can't use it to impersonate the user as long as the hash function has pre-image resistance.

Lamport's idea is based on the security of Hash-Chain as follows;

  • System initialization

    1. An initial seed $s$ is chosen.
    2. The hash $H$ is applied $n$-times in cascading manner $$h_n = H^{(n)} = \underbrace{H(H(\cdots H(s) \cdots ))}_{n-times}$$ to the initial seed $s$ where $n$ can be 1000,10000, or ..
    3. The server initially stores $h_n$ ( and possibly $n$, too)
    4. The user stores $s$ and $n$
  • Login Mechanism

    • For the first login

      1. User calculates $h_{n-1}$
      2. On the login process user sends $h_{n-1}$ to the server.
      3. Server checks $H(h_{n-1}) = h_n$
      4. On a successful login server
        1. increment a counter $inc(c)$
        2. stores $h_{n-1}$
      5. On successfull login user set $n = n-1$ ( or possible another variable)
    • For the $i$-th login

      1. User calculates $h_{n-i}$
      2. On login process user sends $h_{n-i}$ to the server.
      3. Server checks $H(h_{n-i}) = h_{n-i+1}$
      4. On a successful login server
        1. increment a counter $inc(c)$
        2. stores $h_{n-1}$
      5. On successfull login user set $n = n-1$ ( or possible another variable)

This is the basics and some details are skipped for clarity; for example; for some reason, the system can be out of sync, that is the user's count may not be synced to the server. To handle this the server may keep a look ahead parameter $t$, so on the $i$-th login attempt if there is no equality $H(h_{n-i}) \neq h_{n-i+1}$, the server look ahead if there is a match from $h_{n-i+1}$ to $h_{n-i-t+1}$.

Now, what if a third person sees the LOTP token and tries to impersonate the user.

  1. For a new login they cannot use it since they need $H_{n-i-1}$. To have this they need to find a pre-image. All cryptographic hash function has maintained their pre-image securities including the collision resistance broken one MD5 and SHA-1. This doesn't mean that you should use them, prefer modern ones like SHA-256, SHA-512, SHA-3, BLAKE2, etc.

    If the system somehow enables the user to use the same LOTP token during a session the attacker may impersonate the user for this session. The attack range cannot go beyond this session due to the pre-image resistance.

    In short, the security of LTOP is based on the pre-image security of $H$

  2. Can look-ahead cause a problem? No. The server updates its stored hash values on every login. If they only stored the initial one and hashes $i$-times to check the OTP, then look-ahead is an attack point. This is one of the reasons to keep the last hash and the other is the performance.

  3. The secret $\mathbf{s}$ size, on the other hand, should have at least uniform and randomly generated 128 bits to prevent brute-force of $s$.

  • $\begingroup$ Thank you for your detailed explanation. Love the idea of the look-ahead parameter. One thing however is that my point still doesn't seem to be understood. Take for example a session where the user sends h<sub>n-1</sub>. An attacker can intercept h<sub>n-1</sub> and send it to the server. After all, the server never validates where h<sub>n-1</sub> comes from. All the server does is to check that h<sub>n-1</sub> hashes to h<sub>n</sub>. So if this happens, wouldn't it mean that the server instead authenticates the attacker instead of the user? Or could there be something I am missing. $\endgroup$
    – Joker
    Commented Feb 12, 2022 at 7:34
  • $\begingroup$ Took me a while to come up with my previous comment, I only hope you get my point. Additionally, what of when the user initially sends a n-times hash of the secret s. I am referring to the first time a user sends his n-times hash which the server begins working with. How does the server ensure the identity of the user at the first instance? Or can we assume a scenario that the server actually provides the secret s to the user in some secure way, making the user instead hash the server-provided secret. This in my opinion can be a way of the server verifying the identity of the user. $\endgroup$
    – Joker
    Commented Feb 12, 2022 at 7:45
  • $\begingroup$ 1) As I said the answer doesn't include all details. What if the server increments the hash as soon as they validate the user and forgot the previous value? The same session attack can only happen due to the designer's choice. If they want to prevent this than can request a new token. $\endgroup$
    – kelalaka
    Commented Feb 12, 2022 at 11:41
  • 1
    $\begingroup$ 2) Have you ever heard registration process? The secret should be generated by the user of must be given to the user in a secure way like the tokens of banks. Once the user and server agree on the registration the user can give their $h_s$ at this time. validation of the user should require at least two factors like the one you should know (a password) the one you should have ( phone/token) etc. LOTP is one factor. $\endgroup$
    – kelalaka
    Commented Feb 12, 2022 at 11:47
  • $\begingroup$ +1 for your feedback, thanks $\endgroup$
    – Joker
    Commented Feb 14, 2022 at 7:59

Of course, in my opinion, there is another attack, although I don't know if this attack has already been discovered or not. which allows the attacker to calculate the hashes without knowing the value based on which the hashes are calculated: in this model, the attacker can give the value 1 to the user instead of the original n value and record the hash value that the user returns and In the next steps, it is enough for the attacker to look for n-1 number of hashes from the received hash for each n value that the server returns, and in this way, the attacker can calculate the hash value in each step even without knowing the value from which the hash is calculated. to calculate


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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