Impersonation attack on Lamport's one time password

Question

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.

Answer 1

• 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$.

Answer 2

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