When you log in to a computer and enter your password, the computer checks that your password belongs to you and then grants access. However, it would be quite dangerous to store the passwords in a file in the computer. Someone who obtains that file would then be able to open anyone’s account. Making the file available only to the computer administrator might be one solution; but what happens if the administrator makes a copy of the file shortly before changing jobs? The solution is to encrypt the passwords before storing them.

Let $f(x)$ be a one-way function. This means that it is easy to compute $f(x)$, but it is very difficult to solve $y=f(x)$ for $x$. A password $x$ can then be stored as $f(x)$, along with the user’s name. When the user logs in, and enters the password $x$, the computer calculates $f(x)$ and checks that it matches the value of $f(x)$ corresponding to that user. An intruder who obtains the password file will have only the value of $f(x)$ for each user. To log in to the account, the intruder needs to know $x$, which is hard to compute since $f(x)$ is a one-way function.

In many systems, the encrypted passwords are stored in a public file. Therefore, anyone with access to the system can obtain this file. Assume the function $f(x)$ is known. Then all the words in a dictionary, and various modifications of these words (writing them backward, for example) can be fed into $f(x)$. Comparing the results with the password file will often yield the passwords of several users.

This dictionary attack can be partially prevented by making the password file not publicly available, but there is still the problem of the departing (or fired) computer administrator. Therefore, other ways of making the information more secure are also needed.

Here is another interesting problem. It might seem desirable that $f(x)$ can be computed very quickly. However, a slightly slower $f(x)$ can slow down a dictionary attack. But slowing down $f(x)$ too much could also cause problems. If $f(x)$ is designed to run in a tenth of a second on a very fast computer, it could take an unacceptable amount of time to log in on a slower computer. There doesn’t seem to be a completely satisfactory way to resolve this.

One way to hinder a dictionary attack is with what is called salt. Each password is randomly padded with an additional 12 bits. These 12 bits are then used to modify the function $f(x)$. The result is stored in the password file, along with the user’s name and the values of the 12-bit salt. When a user enters a password $x$, the computer finds the value of the salt for this user in the file, then uses it in the computation of the modified $f(x)$, which is compared with the value stored in the file.

When salt is used and the words in the dictionary are fed into $f(x)$, they need to be padded with each of the $2^{12}=4096$ possible values of the salt. This slows down the computations considerably. Also, suppose an attacker stores the values of $f(x)$ for all the words in the dictionary. This could be done in anticipation of attacking several different password files. With salt, the storage requirements increase dramatically, since each word needs to be stored 4096 times.

The main purpose of salt is to stop attacks that aim at finding a random person’s password. In particular, it makes the set of poorly chosen passwords somewhat more secure. Since many people use weak passwords, this is desirable. Salt does not slow down an attack against an individual password (except by preventing use of over-the-counter DES chips; see below). If Eve wants to find Bob’s password and has access to the password file, she finds the value of the salt used for Bob and tries a dictionary attack, for example, using only this value of salt corresponding to Bob. If Bob’s password is not in the dictionary, this will fail, and Eve may have to resort to an exhaustive search of all possible passwords.

In many Unix password schemes, the one-way function was based on DES. The first eight characters of the password are converted to seven-bit ASCII (see Section 4.1). These 56 bits become a DES key. If the password is shorter than eight symbols, it is padded with zeros to obtain the 56 bits. The “plaintext” of all zeros is then encrypted using 25 rounds of DES with this key. The output is stored in the password file. The function

is believed to be one-way. Namely, we know the “ciphertext,” which is the output, and the “plaintext,” which is all zeros. Finding the key, which is the password, amounts to a known plaintext attack on DES, which is generally assumed to be difficult.

In order to increase security, salt is added as follows. A random 12-bit number is generated as the salt. Recall that in DES, the expansion function $E$ takes a 32-bit input $R$ (the right side of the input for the round) and expands it to 48 bits $E(R)$. If the first bit of the salt is 1, the first and 25th bits of $E(R)$ are swapped. If the second bit of the salt is 1, the second and 26th bits of $E(R)$ are swapped. This continues through the 12th bit of the salt. If it is 1, the 12th and 36th bits of $E(R)$ are swapped. When a bit of the salt is 0, it causes no swap. If the salt is all zero, then no swaps occur and we are working with the usual DES. In this way, the salt means that 4096 variations of DES are possible.

One advantage of using salt to modify DES is that someone cannot use high-speed DES chips to compute the one-way function when performing a dictionary attack. Instead, a chip would need to be designed that tries all 4096 modifications of DES caused by the salt; otherwise the attack could be performed with software, which is much slower.

Salt in any password scheme is regarded by many as a temporary measure. As storage space increases and computer speed improves, a factor of 4096 quickly fades, so eventually a new system must be developed.

For more on password protocols, see Section 12.6.