[Next] [Up] [Previous] [Index]

Passwords and Protocols

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.

A Simple Example

Before going on to advanced protocols which use public-key techniques, let us revisit a protocol I sketched in the introductory section of the chapter on public-key cryptography as the way in which people might have used credit cards to buy things over the Internet if public-key cryptography hadn't been available when this activity had started in earnest.

Instead of just sketching the protocol, however, here I will make every step explicit.

A credit card company would allow its clients to shop over the Internet securely using conventional symmetric or secret-key cryptography only by setting up as follows:

The credit card number, with redundancy removed, would be 30 bits long. The fact that this isn't long enough for a secure cryptographic key complicates this protocol, despite the fact that this number is transmitted in the clear at the beginning of the protocol, for reasons that will shortly become obvious. The password will represent 94 bits of data, as each half of it, ten letters long, will represent 47 bits using the coding described in this section.

The protocol is intended to work as follows:

Now it is clear why the short length of the credit card number is a problem. Since 30 bits is too short for a secure encryption key, if the shared secret between the merchant and the user is only 30 bits long, and public-key techniques are not used, secure communications cannot be established.

In addition to the encrypted credit card number of 30 bits, 64 bits remain available in the password. Instead of those 64 bits being completely arbitrary and random, one could let only 12 of those bits be arbitrary. The other 52 bits would be divided into two halves of 26 bits, one half being the encrypted form of the other half. So, in practice, 26 bits of those 52, and the 30 bits of the credit card number, would be encrypted together using the credit card company's secret key and placed in the password. This is a 56-bit quantity, which is the size of a key in DES.

Since I am considering a case where it is intended to establish Internet credit-card use before the invention of public-key technology, I am setting the scenario in an innocent age during which 56-bit keys were considered long enough to be secure.

With the background in place, I can now present the steps of the protocol explicitly.

The 12 additional bits available are also a shared secret, although lightly encrypted. The 78 bits consisting of the 64-bit random quantity and this 12-bit value can be encrypted using the 56-bit key both sides share to produce a quantity with 56-bit security. The secret key of the credit card company would be at least 56 bits long, and could be longer (the black box could use Triple-DES), and so the only reason the 30-bit and 26-bit quantities would not be secure is their vulnerability to the codebook attack, but a codebook attack would require obtaining a large number of passwords and their corresponding credit card numbers, which would make a cryptanalytic attack on the protocol irrelevant.

One way to proceed at this point to use the 64-bit random value to make each session unique would be as follows:

After I first mentioned this protocol, I was advised that sending the credit card number in the clear at the beginning of the transaction is not considered desirable. At first, I thought this would require issuing a second identifier with credit cards, or making the password longer. But I then realized that through the use of one-way hashes, meeting this requirement actually made things easier; the length of the credit card number ceased to be a problem.

In the revised protocol, the credit card remains 11 digits long, including two check digits, containing 30 bits of information, and the password remains 20 letters long, containing 94 bits of information.

Those 94 bits, however, are now divided into a 56-bit initial key, a 26-bit key supplement, and a 12-bit free salt field.

The protocol now proceeds as follows:

Privacy-amplifying Password Protocols

Now we will examine various proposals to address this problem which make use of public-key cryptography as well to gain greater security.

SRP

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

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.

Augmented EKE

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.

Kaliski-Ford

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.

Conclusions

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:

  1. The user types his ID (UID) and password (UPASS) on the keyboard of his computer.
  2. The user's computer generates a random number (UR1).
  3. The user's computer transmits the following to the computational host computer: Thus, the message transmitted is: UID + EPK(H(UR1) + E(H(H(UR1)), H(UPASS)), SPUB). Note that this does not depend on an externally-generated random number; protection against replay attacks comes from a later step in the protocol.
  4. The computational host computer now generates a nonce public-private key pair (HPUB, HPRV) and a random number (HR). This random number will, later in the protocol, be communicated securely to the other two computers, and is used as a session key for communications between them.
  5. The host computer transmits the following to the security server: Thus, the message transmitted is: UID + EPK(H(UR1) + E(H(H(UR1)), H(UPASS)), SPUB) + EPK(HR + HPUB, SPUB)
  6. The security computer generates a random value of its own (SR). As it knows its own private key (SPRV) corresponding to SPUB, it can decode the message transmitted to it. It also has a copy of H(UPASS) for each user, and therefore it can verify that E(H(H(UR1)), H(UPASS)) and H(UR1) correspond. In addition, it has a copy of USALT, a random salt value for the user as well. This salt value, not stored on the user's computer or the computational host, is used to calculate UVERIFY, a hash of which is stored on the computational host, and thus prevents dictionary attacks on that computer's password file. Because the security computer has a copy of H(UPASS), it knows at this stage that the user is authentic, except for the possibility of a replay attack. (If the user is not valid, the protocol is halted here.) Now, the task of the protocol is to convince the computational host computer, which does not contain any secrets, of that fact, and this will be done so as to eliminate the possibility of a replay attack.
  7. Now the security computer sends a message to the host computer which gets used again later, so we refer to it as message M. Encrypted first with H(UPASS) and then with H(UR1) as the keys, it contains:
  8. The host computer retains a copy of this message for future reference.
  9. The host computer passes it on to the user's computer.
  10. The user's computer thought of the user's random value, UR1, and was given the user's password, UPASS, and so it knows the hashes of both of them, and can decrypt message M, obtaining USALT, HR, SR, and HPUB from it. It then calculates UVERIFY, a hash of H(UPASS) encrypted with USALT as the key. (That is, UVERIFY = H(E(H(UPASS),USALT)).)
  11. The user's computer transmits a message to the host computer encrypted with the host computer's public key HPUB, consisting of:
  12. The host computer has its own password file, which contains a copy of UVERIFY for the user, but not USALT or H(UPASS); thus, since it also knows HPRV and HR, it can decode the message, and verify that the hash is correct.

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.

  1. The user types his ID (UID) and password (UPASS) on the keyboard of his computer.
  2. The user's computer generates a random number (UR).
  3. The user's computer transmits the following to the computational host computer: Thus, the message transmitted is: UID + EPK(H(UR) + E(H(H(UR)), H(UPASS)), SPUB). Note that this does not depend on an externally-generated random number; protection against replay attacks comes from a later step in the protocol.
  4. The computational host computer now generates a nonce public-private key pair (HPUB, HPRV) and two random numbers (HR1, HR2). In its password table, it finds the quantity UVERIFY for the user, which will be defined later, but which is a Diffie-Hellman public key to which the corresponding private key is a quantity depending on the user's password. The first of these random numbers will, later in the protocol, be communicated securely to the other two computers, and is used as a session key for communications between them.
  5. The host computer transmits the following to the security server: Thus, the message transmitted is: UID + EPK(H(UR1) + E(H(H(UR)), H(UPASS)), SPUB) + EPK(HR1 + HPUB, SPUB) + EPK(HR2, UVPUB)
  6. The security computer generates a random value of its own (SR). As it knows its own private key (SPRV) corresponding to SPUB, it can decode the first two parts of the message transmitted to it. It also has a copy of H(UPASS) for each user, and therefore it can verify that E(H(H(UR)), H(UPASS)) and H(UR) correspond. In addition, it has a copy of USALT, a random salt value for the user as well. This salt value, not stored on the user's computer or the computational host, is used to calculate the private key corresponding to UVERIFY. Because the security computer has a copy of H(UPASS), it knows at this stage that the user is authentic, except for the possibility of a replay attack. (If the user is not valid, the protocol is halted here.) Now, the task of the protocol is to convince the computational host computer, which does not contain any secrets, of that fact, and this will be done so as to eliminate the possibility of a replay attack. Since information prepared at this stage for transmission to the user's computer will be encrypted using both H(UR) and H(UPASS), a replay attacker would not be able to read it.
  7. Now the security computer sends a message to the host computer. It consists of:
  8. The host computer passes it on to the user's computer.
  9. The user's computer thought of the user's random value, UR, and was given the user's password, UPASS, and so it knows the hashes of both of them, and can decrypt message M, obtaining USALT, HR1, SR, and HPUB from it. It then calculates UVPRV, a hash of UPASS encrypted with USALT as the key. Since it depends on UPASS and not H(UPASS), even the security server could not have calculated it. (That is, UVPRV = H(E(UPASS, USALT)).)
  10. The user's computer uses UVPRV to decrypt EPK(HR2, UVPUB), where UVPUB was the Diffie-Hellman private key corresponding to UVPRV as the private key. (Of course, since EPK is a Diffie-Hellman step, an additional public and private key pair in the other direction is involved; these keys can be nonces.)
  11. The user's computer transmits a message to the host computer encrypted with the host computer's public key HPUB, consisting of:
  12. The host computer has its own password file, which contains a copy of UVPUB for the user, but not USALT or UPASS or even H(UPASS); since it also knows HPRV and HR1, it can decode the message, and verify that the user correctly decoded HR2, which nicely authenticates the user.

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.


[Next] [Up] [Previous] [Index]

Next
Table of Contents
Home Page