Many multiuser computer systems require someone wishing to use the computer to supply a user ID and a password. The operating system then looks up the user ID in a list, and determines if the password is correct, before allowing the user to proceed.
This simple procedure had some potential problems.
In the UNIX operating system, it was decided to put the list of user IDs and passwords in a text file that was generally available to programs on the system to read, but not to alter. This allowed programs on the system to make themselves available only to certain users. To prevent revealing everyone's password, the list didn't contain actual passwords, but instead a hash function of the password.
This was seen as such a good idea that other operating systems, which already made the password file inaccessible (as UNIX and related operating systems later did with "shadow password files") adopted it as well.
However, it still had its limitations. One could not calculate backwards from a hash to obtain a password. But one could try a list of passwords, hashing each one, until one matches the hash that is seen. This becomes easier for a computer to do when people use passwords that are easy to remember; it is called a "dictionary attack", and is the reason people are advised not to use a single word as a password, but to use special characters and unconventional capitalization in passwords. Many systems limit passwords to 8 characters in length, which increases the need to do this, and which makes it considerably harder to construct a password which is both secure and easy to remember.
One step that did not make this attack impossible, but which made it a bit less trivial, was to include "salt" in password files. In this case, the list of passwords contained hashes of the password plus a random value (which is what was called the "salt"), and the hash and the random value both appeared in the list. This meant at least that an attacker had to, based on the random value for a specific user, perform the hash of the possible passwords in his dictionary once just to attack that user's password. Without "salt", a dictionary containing precomputed hashes could be used directly against an entire password file.
Another fundamental problem was harder to solve, since it required that the user's terminal have local processing abilities: when the user types his password at a terminal, an eavesdropper could discover the password.
Today, of course, people don't buy terminals, they use their PCs as terminals. So it is possible for the link between a remote user and a computer to be encrypted.
We have seen in the preceding section that a short shared secret, such as a password, can be very powerful in combination with public-key cryptography, using methods like Encrypted Key Exchange.
A number of protocols have been proposed that address the problem of setting up a highly secure connection between a user and a computer with the help of a password, as well as addressing the question of security if an attacker can also read the password file stored on the central computer.
Kerberos illustrates how two parts of this problem can be addressed.
To prevent an eavesdropper from finding information that can be used for a later fraudulent logon, one can use a challenge-response protocol. In its simplest form, the user provides his logon ID along with a hash of his password plus a random number with which he was provided by the computer to which he seeks to log in.
Since a different random number will be provided on subsequent occasions, an eavesdropper cannot use the hash intercepted to log in later.
To verify the hash, though, the computer needs a copy of the original password. Of course, one could keep H(password) on the computer, and make H(H(password)+random number) the response to the challenge-response protocol. But then H(password) would be all the information needed to log in fraudulently.
This problem, though, was also addressed by Kerberos. While the password list needed now to be kept secure, it was kept on a central computer used to maintain security. Once a user's identity was verified, the user was given a coded credential to use to prove his identity to the computer that he - and other users - were allowed to use. That computer didn't have a copy of the password file, and so the fact that people could use it for their own computations, and possibly compromise its security, didn't put user's passwords at risk.
Now we will examine various proposals to address this problem which make use of public-key cryptography as well to gain greater security.
SRP uses techniques based on Diffie-Hellman to improve the security of logging on to a computer.
For each user, the central computer stores the following two items:
Note that a dictionary attack on the password (the Diffie-Hellman base and modulus used have to be available to all users of the system) is possible if an attacker reads these two items, although the need to perform a public-key computation for each trial does slow it down somewhat.
The protocol proceeds as follows:
PAK-R also proceeds by masking a Diffie-Hellman key exchange. The host computer retains the user's actual password, or at least the same quantity as is used in the user's computations, so if the password file is compromised, it is directly insecure, without even the need for a dictionary attack.
Again, this is not a fatal objection, since one can expect that SRP and PAK might be carried out on a security server similar to the one in Kerberos.
For PAK-R, Diffie-Hellman calculations are performed on a prime P of the form uv+1, where u is not a multiple of v. This facilitates masking the Diffie-Hellman exchange.
The steps in PAK-R are as follows:
Again, I omit further steps where this common session key is hashed, and further hashes are used to verify its joint posession.
The presentation of Augmented EKE is quite general, and I am simplifying it here, by describing only one specific case, to make it easier to understand. I believe that the special case I present here is a valid example of augmented EKE.
Let a hash of the user's password (h) be used as the private key for a Diffie-Hellman key pair, of which the public key is H=A^h.
Use H also as the conventional encryption key for EKE as described in the previous section in the normal manner. The host computer has a copy of H, so, once again, dictionary attacks are possible, but this isn't a problem if the host is a security computer and not the ultimate computational host.
Then, using the session key established by EKE, the host computer generates a nonce public/private key pair for Diffie-Hellman (y and Y=A^y), and the user's computer proves that it knows h by successfully establishing communications using the normal common session key Y^h=H^y additionally protected by the other session key.
The Kaliski-Ford protocol finally does address the question of dictionary attacks directly. It does so by distributing the information needed for such an attack over a network of computers which are peers, rather than having a hierachical system with a security server. A scheme designed for such an environment is, of course, appropriate for existing networks in many offices.
A given user has a certain set of servers with which he completes preliminary authentication. Preliminary authentication produces a credential, or "hardened password", for the user from each server as follows:
After having obtained a complete set of hardened passwords from the required set of computers, some sort of hash is taken of all these hardened passwords, and this result is used as a Diffie-Hellman private key; the corresponding public key is kept on the computer one wishes to use. So that the same set of hardened passwords can be used for logging on to more than one computer, the target computer's ID is included in the hash.
Before hearing of Kaliski-Ford, but because I noted that SRP and PAK were (in their original versions as discussed here) susceptible to dictionary attacks, instead of simply accepting that a security server could carry them out, I made the concept of a security server explicit, and came up with a fairly complicated protocol. Originally, I was going to use EKE to make the communications between the user and the security server as secure as possible; but since the computational host can retain no long-term secrets, I could not ultimately retain the increased security that would provide, so I was able, without loss, to avoid the use of this patented algorithm.
The main thing that I attempted to add was allowing the actual computational host computer, which could retain no secrets, to verify for itself that the user was authentic. This could also have been done simply by having it retain a copy of the security server's public key, to verify signed messages from it, but I went ahead and did things the hard way.
The computational host computer is the resource access to which is being controlled. Since it is a resource that users use directly, though, it cannot keep long-term secrets on its hard drives, but it is assumed that it can keep short-term secrets in its memory. Therefore, it is trusted, but not secure. The security server, on the other hand, only performs the single task of verifying users, and can't be used directly. So the information on its hard drives is secure. But because the host computer isn't secure, an attacker might be able to mount an active attack on the connection between the host computer and the security server, so while the security server itself is trusted, the host computer does not trust messages recieved from it.
My protocol went like this:
UVERIFY is almost incidental to the security of the protocol as it stands. Although normally it can only be calculated with both H(UPASS) and USALT, since the computational host has a copy of it, it is not secure. One could keep only H(UVERIFY) on the computational host, and send a copy of UVERIFY to the host in the final message to it from the user's computer. That would seem to increase security, but since the host contains no secrets, UVERIFY could be obtained if an attacker were to control the links to both the user's computer and the security server, and impersonate the computational host.
Instead, it is HR that proves the identity of the user; HR was only transmitted originally to the security server encrypted with its public key, so only the real security server could have read it. And the real security server then sends HR to the user's computer encrypted with H(UPASS) as a key; this value is kept secret by the security server, and only the user's computer, with UPASS, can decode it.
The following is an extended version of the protocol that brings a modified version of UVERIFY into the protocol more centrally, using the idea, from Augmented EKE above, that one can prove knowledge of a quantity by using it as a Diffie-Hellman private key to decrypt something sent to you by the posessor of the corresponding Diffie-Hellman public key.
Using HR2 as an encryption key, and returning HR1 to the host computer, instead of the other way around, as I mistakenly did originally in this modified protocol, prevents an attacker impersonating the host computer from mounting attacks aimed at discovering the value of UVPRV by transmitting chosen values not encrypted with UVPUB in place of EPK( HR2, UVPUB ) to the user's computer. (Actually, this isn't really a problem unless one were to use RSA encryption, instead of conventional encryption with a key derived from Diffie-Hellman key agreement, but I think it's appropriate to have a protocol that can be used in a flexible fashion.)
Can this protocol be simplified and improved?
The security server is assumed to be secure. So it could have a secret key, and the information about each user that it uses could be on the host computer, enciphered with that secret key. This would allow the security server to be smaller, and avoid the potentially dangerous operation of storing new data there.
The objective that is difficult to meet is placing on the host computer information that enables it to verify the user's identity, based on the user's password, that is immune to a dictionary attack on that password. The host computer must be protected against any deception, and yet if the host, which can keep no permanent secrets, is impersonated, the impersonator must not gain the information needed to impersonate a user.
Only the security server, if it is genuine, can decrypt HR and USALT1 and USALT2 from the host computer, and H( UPASS ) from the user. The session keys UR and HR protect the individual messages from attack, and USALT1 and USALT2 (as well as SKEY) prevents a dictionary attack on the password file; both USALT1 and USALT2 are as long as an encryption key, on the order of 128 bits in length.
USALT2, by not being provided to the user's computer, ensures that an attacker impersonating the user does not obtain the information needed for a dictionary attack. USALT1 is not strictly necessary, but avoids the security server ever having to have a copy of either H( UPASS ) or H( H( UPASS ) ), which seems desirable, even though the security server is trusted. Of course, the pair H( H( USALT1 ) + UPASS ) and E( USALT1, H( H( UPASS ) ) ) is still subject to a dictionary attack.
This is a simpler protocol, and its easy to see why it works. But it does depend on trusting the security server completely. Can that be avoided, by using some of the operations from the earlier protocols?
Now, not only does only the security server know USALT2, but only the user's computer sees USALT1. Even with an insecure link to the security server, it cannot usefully be impersonated, since all communications to it depend either on SKEY or on SPUB. The weakest link in the protocol is E( USALT1, H( H( UPASS ) ) ) in the password table, but now the other quantities it can be compared with are E( USALT2, SKEY ) and H( H( H( UPASS + USALT1 ) + USALT2 ) ). SKEY protects the one occurrence of USALT2, and USALT2 is therefore sufficient to protect the other item from being compared with H( USALT1, H( H( UPASS ) ) ) by means of a dictionary attack. Since the security server never sees USALT1, the user's identity is even more strongly confirmed. With HR1, the host computer protects itself against replay attacks.
The user needs to have a securely authenticated copy of SPUB for this and the preceding protocol to work, of course.
Why are these protocols so complicated?
Let's start from the simplest one, and move up.
The user supplies a User ID and password to the host computer.
The computer uses the User ID to look up the password in a list.
The problem with this is that a hacker might be able to read the password file without authorization, and find out people's passwords.
The user supplies a User ID and password to the host computer.
The computer uses the User ID to look up a hash of the password in a list.
A hacker can still use the password file; a list of the hashes of common passwords can even be precomputed, to make it easy to find the users with weak passwords.
The user supplies a User ID and password to the host computer.
The computer uses the User ID to look up a random value (called "salt") and a hash of the password with the salt concatenated to it in a list.
Now, the hacker can still try a list of common passwords against any user in the password file he wishes to impersonate, but because of the salt values, this must be done over again for each entry.
Thus, Protocol 1 is vulnerable to the passwords being read, and Protocols 2 and 3 are vulnerable to dictionary attacks. Also, all three protocols are vulnerable to the communications between the user and the computer being tapped.
The user supplies a User ID to the host computer.
The host computer looks up the salt value for the user with the User ID, and sends that to the user along with a random value it generates for the session.
The user enters his password; the computer generates a hash of the password concatenated with the salt, and then concatenates the result with the session random value and hashes it again. This result is sent to the host computer.
The host computer looks up the hash of the user's password plus the salt, and uses that and the random value to determine if the value sent by the user was correct.
This is a standard challenge-response protocol, which retains a salt value. Now, passwords are no longer being transmitted in the clear. But dictionary attacks are still just as possible as in Protocol 3.