Alice wants to log in to a server using her password. A common way of doing this is the Secure Remote Password protocol (SRP).

First, the system needs to be set up to recognize Alice and her password. Alice has her login name $I$ and password $P$. Also, the server has chosen a large prime $p$ such that $(p-1)/2$ is also prime (this is to make the discrete logarithm problem mod $p$ hard) and a primitive root $\alpha$ mod $p$. Finally, a cryptographic hash function $H$ such as SHA256 or SHA3 is specified.

A random bitstring $s$ is chosen (this is called “salt”), and $x=H(s||I||P)$ and $v\equiv {\alpha }^x(\text{mod}p)$ are computed. The server discards $P$ and $x$, but stores $s$ and $v$ along with Alice’s identification $I$. Alice saves only $I$ and $P$.

When Alice wants to log in, she and the server perform the following steps:

1. Alice sends $I$ to the server and the server retrieves the corresponding $s$ and $v$.

2. The server sends $s$ to Alice, who computes $x=H(s||I||P)$.

3. Alice chooses a random integer $a$ mod $p-1$ and computes $A\equiv {\alpha }^a(\text{mod}p)$. She sends $A$ to the server.

4. The server chooses a random $b$ mod $p-1$, computes $B\equiv 3v+{\alpha }^b$ mod $p$, and sends $B$ to Alice.

5. Both Alice and the server compute $u=H(A||B)$.

6. Alice computes $S\equiv (B-3{\alpha }^x{)}^{a+ux}(\text{mod}p-1)$ and the server computes $S$ as $(A{v}^u{)}^b$ (these yield the same $S$; see below).

7. Alice computes $M_1=H(A||B||S)$ and sends $M_1$ to the server, which checks that this agrees with the value of $M_1$ that is computed using the server’s values of $A\text{,}B\text{,}S$.

8. The server computes $M_2=H(A||M_1||S)$ and sends $M_2$ to Alice. She checks that this agrees with the value of $M_2$ she computes with her values of $A\text{,}{M}_1\text{,}S$.

9. Both Alice and the server compute $K=H(S)$ and use this as the session key for communications.

Several comments are in order. We’ll number them corresponding to the steps in the protocol.

1. The server does not directly store $P$ or a hash of $P$. The hash of $P$ is stored in a form protected by a discrete logarithm problem. Originally, $x=H(s||P)$ was used and the salt $s$ was included to slow down brute force attacks on passwords. Eve can try various values of $P$, trying to match a value of $v$, until someone’s password is found (this is called a “dictionary attack”). If a sufficiently long bitstring $s$ is included, this attack becomes infeasible. The current version of SRP includes $I$ in the hash to get $x$, so Eve needs to attack an individual entry. Since Eve knows an individual’s salt (if she obtained access to the password file), the salt is essentially part of the identification and does not slow down the attack on the individual’s password.

2. Sending $s$ to Alice means that Alice does not need to remember $s$.

3. This is essentially the start of a protocol similar to the Diffie-Hellman key exchange.

4. Earlier versions of SRP used $B\equiv v+{\alpha }^b$. But this meant that an attacker posing as the server could choose a random $x^{\prime }$, compute $v^{\prime }\equiv {\alpha }^{x^{\prime }}$, and use $B\equiv {\alpha }^{x^{\prime }}+{\alpha }^b$, thus allowing the attacker to check whether one of $b\text{,}{x}^{\prime }$ is the hash value $x$. In effect, this could speed up the attack by a factor of 2. The 3 is included to avoid this.

5. In an earlier version of SRP, $u$ was chosen randomly by the server and sent to Alice. However, if the server sends $u$ before $A$ is received (for example, it might seem more efficient for the server to send both $s$ and $u$ in Step 2), there is a possible attack. See Exercise 16. The present method of having $u=H(A||B)$ ensures that $u$ is determined after $A$.

6. Let’s show that the two values of $S$ are equal:

   $$(B-3{\alpha }^x{)}^{a+ux}\equiv (B-3v{)}^{a+ux}\equiv ({\alpha }^b{)}^{a+ux}\equiv {\alpha }^{ab}{\alpha }^{uxb}$$

   and

   $$(A{v}^u{)}^b\equiv {\left({\alpha }^a({\alpha }^x{)}^u\right)}^b\equiv {\alpha }^{ab}{\alpha }^{uxb}\text{.}$$

   Therefore, they agree. Note the hints of the Diffie-Hellman protocol, where ${\alpha }^{ab}$ is computed in two ways.

   Since the value of $B$ changes for each login, the value of $S$ also changes, so an attacker cannot simply reuse some successful $S$.

7. Up to this point, the server has no assurance that the communications are with Alice. Anyone could have sent Alice’s $I$ and sent a random $A$. Alice and the server have computed $S$, but they don’t know that their values agree. If they do, it is very likely that the correct $x$, hence the correct $P$, is being used. Checking $M_1$ shows that the values of $S$ agree because of the collision resistance of the hash function. Of course, if the values of $S$ don’t agree, then Alice and the server will produce different session keys $K$ in the last step, so communications will fail for this reason, too. But it seems better to terminate the protocol earlier if something is wrong.

8. How does Alice know that she is communicating with the server? This step tells Alice that the server’s value of $S$ matches hers, so it is very likely that the entity she is communicating with knows the correct $x$. Of course, someone who has hacked into the password file has all the information that the server has and can therefore masquerade as the server. But otherwise Alice is confident that she is communicating with the server.

9. At the point, Alice and the server are authenticated to each other. The session key serves as the secret key for communications between Alice and the server during the current session.

Observe that $B$, $M_1$, and $M_2$ are the only numbers that are transmitted that depend on the password. The value of $B$ contains $v\equiv {\alpha }^x$, but this is masked by adding on the random number ${\alpha }^b$. The values of $M_1$ and $M_2$ contain $S$, which depends on $x$, but it is safely hidden inside a hash function. Therefore, if is very unlikely that someone who eavesdrops on communications between Alice and the server will obtain any useful information. For more on the security and design considerations, see [Wu1], [Wu2].

Another method was proposed by Lamport. The protocol, which we now introduce, is an example of what is known as a one-time password scheme since each run of the protocol uses a temporary password that can only be used once. Lamport’s one-time password protocol is a good example of a special construction using one-way (specifically, hash) functions that shows up in many different applications.

To start, we assume that Alice has a password $P_{Alice}$, that Veronica has chosen a large integer $n$, and that Alice and Veronica have agreed upon a one-way function $h$. A good choice for such an $h$ is a cryptographic hash function, such as SHA256 or SHA3, which we described in Chapter 11. Veronica calculates $h^n(P_{Alice})=h(h(\cdots (h(P_{Alice}))\cdots ))$, and stores Alice’s entry $(Alice\text{,}{h}^n(P_{Alice})\text{,}n)$ in a password file. Now, when Alice wants to authenticate herself to Veronica, she uses the revised protocol:

1. Alice $\to$ Veronica: “Hello, I am Alice.”

2. Veronica $\to$ Alice: $n$, “Password?”

3. Alice $\to$ Veronica: $r=h^{n-1}(P_{Alice})$

4. Veronica takes $r$, and checks to see whether $h(r)=h^n(P_{Alice})$. If the check passes, then Veronica updates Alice’s entry in the password as $(Alice\text{,}{h}^{n-1}(P_{Alice})\text{,}n-1)$, and Veronica grants Alice access to her services.

At first glance, this protocol might seem confusing, and to understand how it works in practice it is useful to write out the following chain of hashes, known as a hash chain:

For the first run of the protocol, in step 2, Veronica will tell Alice $n$ and ask Alice the corresponding password that will hash to $h^n(P_{Alice})$. In order for Alice to correctly respond, she must calculate $h^{n-1}(P_{Alice})$, which she can do since she has the original password. After Alice is successfully verified, Veronica will throw away $h^n(P_{Alice})$ and update the password file to contain $(Alice\text{,}{h}^{n-1}(P_{Alice})\text{,}n-1)$.

Now suppose that Eve saw $h^{n-1}(P_{Alice})$. This won’t help her because the next time the protocol is run, in step 2 Veronica will issue $n-1$ and thereby ask Alice for the corresponding password that will hash to $h^{n-1}(P_{Alice})$. Although Eve has $h^{n-1}(P_{Alice})$, she cannot determine the required response $r=h^{n-2}(P_{Alice})$.

The protocol continues to run, with Veronica updating her password file until she runs to the end of the hash chain. At that point, Alice and Veronica must renew the password file by changing the initial password $P_{Alice}$ to a new password.

This protocol that we have just examined is the basis for the S/Key protocol, which was implemented in Unix operating systems in the 1980s. Although the S/Key protocol’s use of one-time passwords achieves its purpose of protecting the password exchange from eavesdropping, it is nevertheless weak when one considers an active adversary. In particular, the fact that the counter $n$ in step 2 is sent in the clear, and the lack of authentication, is the basis for an intruder-in-the-middle attack.

In the intruder-in-the-middle attack described below, Alice intends to communicate with Veronica, but the active adversary Malice intercepts the communications between Alice and Veronica and sends her own.

1. Alice $\to$ Malice (Veronica): “Hello, I am Alice.”

2. Malice $\to$ Veronica: “Hello, I am Alice.”

3. Veronica $\to$ Malice: $n$, “Password?”

4. Malice $\to$ Alice: $n-1$, “Password?”

5. Alice $\to$ Malice: $r_1=h^{n-2}(P_{Alice})$

6. Malice $\to$ Veronica: $r_2=h^{n-1}(P_{Alice})=h(h^{n-2}(P_{Alice}))$.

7. Veronica takes $r_2$, and checks to see whether $h(r_2)=h^n(P_{Alice})$. The check will pass, and Veronica will think she is communicating with Alice, when really she is corresponding with Malice.

One of the problems with the protocol is that there is no authentication of the origin of the messages. Veronica does not know whether she is really communicating with Alice, and likewise Alice does not have a strong guarantee that she is communicating with Veronica.

The lack of origin authentication also provides the means to launch another clever attack, known as the small value attack. In this attack, Malice impersonates Veronica and asks Alice to respond to a small $n$. Then Malice intercepts Alice’s answer and uses that to calculate the rest of the hash chain. For example, if Malice sent $n=10$, she would be able to calculate $h^{10}(P_{Alice})$, $h^{11}(P_{Alice})$, $h^{12}(P_{Alice})$, and so on. The small value of $n$ allows Malice to hijack the majority of the hash chain, and thereby imitate Alice at a later time.

As a final comment, we note that the protocol we described is actually different than what was originally presented by Lamport. In Lamport’s original one-time password protocol, he required that Alice and Veronica keep track of $n$ on their own without exchanging $n$. This has the benefit of protecting the protocol from active attacks by Malice where she attempts to use $n$ to her advantage. Unfortunately, Lamport’s scheme required that Alice and Veronica stayed synchronized with each other, which in practice turns out to be difficult to ensure.