12.6 Password Protocols – Introduction to Cryptography with Coding Theory, 3rd Edition

12.6 Password Protocols

We now look at how the communications take place in a password-based authentication protocol, as is commonly used to log onto computer systems. Password-based authentication is a popular approach to authentication because it is much easier for people to remember a phrase (the password) than it is to remember a long, cryptographic response.

In a password protocol, we have a user, Alice, and a verifier, Veronica. Veronica is often called a host and might, for example, be a computer terminal or a smartphone or an email service. Alice and Veronica share knowledge of the password, which is a long-term secret that typically belongs to a much smaller space of possibilities than cryptographic keys and thus passwords have small entropy (that is, much less randomness is in a password).

Veronica keeps a list of all users and their passwords {(ID, PID)}. For many hosts this list might be small since only a few users might log into a particular machine, while in other cases the password list can be more substantial. For example, email services must maintain a very large list of users and their passwords. When Alice wants to log onto Veronica’s service, she must contact Veronica and tell her who she is and give her password. Veronica, in turn, will check to see if Alice’s password is legitimate.

A basic password protocol proceeds in several steps:

  1. Alice Veronica: “Hello, I am Alice”

  2. Veronica Alice: “Password?”

  3. Alice Veronica: PAlice

  4. Veronica: Examines password file {(ID, PID)} and verifies that the pair (Alice, PAlice) belongs to the password file. Service is granted if the password is confirmed.

This protocol is very straightforward and, as it stands, has many flaws that should stand out. Perhaps one of the most obvious problems is that there is no mutual authentication between Alice and Veronica; that is, Alice does not know that she is actually communicating with the legitimate Veronica and, vice versa, Veronica does not actually have any proof that she is talking with Alice. While the purpose of the password exchange is to authenticate Alice, in truth there is no protection from message replay attacks, and thus anyone can pretend to be either Alice or Veronica.

Another glaring problem is the lack of confidentiality in the protocol. Any eavesdropper who witnesses the communication exchange learns Alice’s password and thus can imitate Alice at a later time.

Lastly, another more subtle concern is the storage of the password file. The storage of {(ID, PID)} is a design liability as there are no guarantees that a system administrator will not read the password file and leak passwords. Similarly, there is no guarantee that Veronica’s system will not be hacked and the password file stolen.

We would like the passwords to be protected while they are stored in the password file. Needham proposed that, instead of storing {(ID, PID)}, Veronica should store {(ID, h(PID))}, where h is a one-way function that is difficult to invert, such as a cryptographic hash function. In this case, Step 4 involves Veronica checking h(PAlice) against {(ID, h(PID))}. This basic scheme is what was used in the original Unix password system, where the function h was the variant of DES that used Salt (see Chapter 7). Now, an adversary who gets the file {(ID, h(PID))} can’t use this to respond in Step 3.

Nevertheless, although the revised protocol protects the password file, it does not address the eavesdropping concern. While we could attempt to address eavesdropping using encryption, such an approach would require an additional secret to be shared between Alice and Veronica (namely an encryption key). In the following, we present two solutions that do not require additional secret information to be shared between Alice and Veronica.

12.6.1 The Secure Remote Password protocol

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 (p1)/2 is also prime (this is to make the discrete logarithm problem mod p hard) and a primitive root α 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αx(modp) 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 p1 and computes Aαa(modp). She sends A to the server.

  4. The server chooses a random b mod p1, computes B3v+αb mod p, and sends B to Alice.

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

  6. Alice computes S(B3αx)a+ux(modp1) and the server computes S as (Avu)b (these yield the same S; see below).

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

  8. The server computes M2=H(A||M1||S) and sends M2 to Alice. She checks that this agrees with the value of M2 she computes with her values of A, M1, 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 Bv+αb. But this meant that an attacker posing as the server could choose a random x, compute vαx, and use Bαx+αb, thus allowing the attacker to check whether one of b, x 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:




    Therefore, they agree. Note the hints of the Diffie-Hellman protocol, where α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 M1 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, M1, and M2 are the only numbers that are transmitted that depend on the password. The value of B contains vαx, but this is masked by adding on the random number αb. The values of M1 and M2 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].

12.6.2 Lamport’s protocol

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 PAlice, 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 hn(PAlice)=h(h((h(PAlice)))), and stores Alice’s entry (Alice, hn(PAlice), n) in a password file. Now, when Alice wants to authenticate herself to Veronica, she uses the revised protocol:

  1. Alice Veronica: “Hello, I am Alice.”

  2. Veronica Alice: n, “Password?”

  3. Alice Veronica: r=hn1(PAlice)

  4. Veronica takes r, and checks to see whether h(r)=hn(PAlice). If the check passes, then Veronica updates Alice’s entry in the password as (Alice, hn1(PAlice), n1), 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 hn(PAlice). In order for Alice to correctly respond, she must calculate hn1(PAlice), which she can do since she has the original password. After Alice is successfully verified, Veronica will throw away hn(PAlice) and update the password file to contain (Alice, hn1(PAlice), n1).

Now suppose that Eve saw hn1(PAlice). This won’t help her because the next time the protocol is run, in step 2 Veronica will issue n1 and thereby ask Alice for the corresponding password that will hash to hn1(PAlice). Although Eve has hn1(PAlice), she cannot determine the required response r=hn2(PAlice).

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 PAlice 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 Malice (Veronica): “Hello, I am Alice.”

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

  3. Veronica Malice: n, “Password?”

  4. Malice Alice: n1, “Password?”

  5. Alice Malice: r1=hn2(PAlice)

  6. Malice Veronica: r2=hn1(PAlice)=h(hn2(PAlice)).

  7. Veronica takes r2, and checks to see whether h(r2)=hn(PAlice). 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 h10(PAlice), h11(PAlice), h12(PAlice), 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.