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 . 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:
Alice Veronica: “Hello, I am Alice”
Veronica Alice: “Password?”
Veronica: Examines password file and verifies that the pair 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 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 , Veronica should store , where is a one-way function that is difficult to invert, such as a cryptographic hash function. In this case, Step 4 involves Veronica checking against . This basic scheme is what was used in the original Unix password system, where the function was the variant of DES that used Salt (see Chapter 7). Now, an adversary who gets the file 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.
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 and password . Also, the server has chosen a large prime such that is also prime (this is to make the discrete logarithm problem mod hard) and a primitive root mod . Finally, a cryptographic hash function such as SHA256 or SHA3 is specified.
A random bitstring is chosen (this is called “salt”), and and are computed. The server discards and , but stores and along with Alice’s identification . Alice saves only and .
When Alice wants to log in, she and the server perform the following steps:
Alice sends to the server and the server retrieves the corresponding and .
The server sends to Alice, who computes .
Alice chooses a random integer mod and computes . She sends to the server.
The server chooses a random mod , computes mod , and sends to Alice.
Both Alice and the server compute .
Alice computes and the server computes as (these yield the same ; see below).
Alice computes and sends to the server, which checks that this agrees with the value of that is computed using the server’s values of .
The server computes and sends to Alice. She checks that this agrees with the value of she computes with her values of .
Both Alice and the server compute 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.
The server does not directly store or a hash of . The hash of is stored in a form protected by a discrete logarithm problem. Originally, was used and the salt was included to slow down brute force attacks on passwords. Eve can try various values of , trying to match a value of , until someone’s password is found (this is called a “dictionary attack”). If a sufficiently long bitstring is included, this attack becomes infeasible. The current version of SRP includes in the hash to get , 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.
Sending to Alice means that Alice does not need to remember .
This is essentially the start of a protocol similar to the Diffie-Hellman key exchange.
Earlier versions of SRP used . But this meant that an attacker posing as the server could choose a random , compute , and use , thus allowing the attacker to check whether one of is the hash value . In effect, this could speed up the attack by a factor of 2. The 3 is included to avoid this.
In an earlier version of SRP, was chosen randomly by the server and sent to Alice. However, if the server sends before is received (for example, it might seem more efficient for the server to send both and in Step 2), there is a possible attack. See Exercise 16. The present method of having ensures that is determined after .
Let’s show that the two values of are equal:
Therefore, they agree. Note the hints of the Diffie-Hellman protocol, where is computed in two ways.
Since the value of changes for each login, the value of also changes, so an attacker cannot simply reuse some successful .
Up to this point, the server has no assurance that the communications are with Alice. Anyone could have sent Alice’s and sent a random . Alice and the server have computed , but they don’t know that their values agree. If they do, it is very likely that the correct , hence the correct , is being used. Checking shows that the values of agree because of the collision resistance of the hash function. Of course, if the values of don’t agree, then Alice and the server will produce different session keys 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.
How does Alice know that she is communicating with the server? This step tells Alice that the server’s value of matches hers, so it is very likely that the entity she is communicating with knows the correct . 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.
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 , , and are the only numbers that are transmitted that depend on the password. The value of contains , but this is masked by adding on the random number . The values of and contain , which depends on , 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 , that Veronica has chosen a large integer , and that Alice and Veronica have agreed upon a one-way function . A good choice for such an is a cryptographic hash function, such as SHA256 or SHA3, which we described in Chapter 11. Veronica calculates , and stores Alice’s entry in a password file. Now, when Alice wants to authenticate herself to Veronica, she uses the revised protocol:
Alice Veronica: “Hello, I am Alice.”
Veronica Alice: , “Password?”
Veronica takes , and checks to see whether . If the check passes, then Veronica updates Alice’s entry in the password as , 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 and ask Alice the corresponding password that will hash to . In order for Alice to correctly respond, she must calculate , which she can do since she has the original password. After Alice is successfully verified, Veronica will throw away and update the password file to contain .
Now suppose that Eve saw . This won’t help her because the next time the protocol is run, in step 2 Veronica will issue and thereby ask Alice for the corresponding password that will hash to . Although Eve has , she cannot determine the required response .
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 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 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.
Alice Malice (Veronica): “Hello, I am Alice.”
Malice Veronica: “Hello, I am Alice.”
Veronica Malice: , “Password?”
Malice Alice: , “Password?”
Malice Veronica: .
Veronica takes , and checks to see whether . 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 . Then Malice intercepts Alice’s answer and uses that to calculate the rest of the hash chain. For example, if Malice sent , she would be able to calculate , , , and so on. The small value of 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 on their own without exchanging . This has the benefit of protecting the protocol from active attacks by Malice where she attempts to use 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.