Authentication Using One-Way Functions

What Roger Needham and Mike Guy realized is that the host does not need to know the passwords; the host just has to be able to differentiate valid passwords from invalid passwords. This is easy with one-way functions [1599,526,1274,1121]. Instead of storing passwords, the host stores one-way functions of the passwords.

(1)  Alice sends the host her password.

(2)  The host performs a one-way function on the password.

(3)  The host compares the result of the one-way function to the value it previously stored.

Since the host no longer stores a table of everybody’s valid password, the threat of someone breaking into the host and stealing the password list is mitigated. The list of passwords operated on by the one-way function is useless, because the one-way function cannot be reversed to recover the passwords.

Dictionary Attacks and Salt

A file of passwords encrypted with a one-way function is still vulnerable. In his spare time, Mallory compiles a list of the 1,000,000 most common passwords. He operates on all 1,000,000 of them with the one-way function and stores the results. If each password is about 8 bytes, the resulting file will be no more than 8 megabytes; it will fit on a few floppy disks. Now, Mallory steals an encrypted password file. He compares that file with his file of encrypted possible passwords and sees what matches.

This is a dictionary attack, and it’s surprisingly successful (see Section 8.1). Salt is a way to make it more difficult. Salt is a random string that is concatenated with passwords before being operated on by the one-way function. Then, both the salt value and the result of the one-way function are stored in a database on the host. If the number of possible salt values is large enough, this practically eliminates a dictionary attack against commonly used passwords because Mallory has to generate the one-way hash for each possible salt value. This is a simple attempt at an initialization vector (see Section 9.3).

The point here is to make sure that Mallory has to do a trial encryption of each password in his dictionary every time he tries to break another person’s password, rather than just doing one massive precomputation for all possible passwords.

A lot of salt is needed. Most UNIX systems use only 12 bits of salt. Even with that, Daniel Klein developed a password-guessing program that often cracks 40 percent of the passwords on a given host system within a week [847,848] (see Section 8.1). David Feldmeier and Philip Karn compiled a list of about 732,000 common passwords concatenated with each of 4096 possible salt values. They estimate that 30 percent of passwords on any given host can be broken with this list [561].

Salt isn’t a panacea; increasing the number of salt bits won’t solve everything. Salt only protects against general dictionary attacks on a password file, not against a concerted attack on a single password. It protects people who have the same password on multiple machines, but doesn’t make poorly chosen passwords any better.

SKEY

SKEY is an authentication program that relies on a one-way function for its security. It’s easy to explain.

To set up the system, Alice enters a random number, R. The computer computes f(R), f(f(R)), f(f(f(R))), and so on, about a hundred times. Call these numbers x₁, x₂, x₃,..., x₁₀₀. The computer prints out this list of numbers, and Alice puts it in her pocket for safekeeping. The computer also stores x₁₀₁, in the clear, in a login database next to Alice’s name.

The first time Alice wants to log in, she types her name and x₁₀₀. The computer calculates f(x₁₀₀) and compares it with x₁₀₁; if they match, Alice is authenticated. Then, the computer replaces x₁₀₁ with x₁₀₀ in the database. Alice crosses x₁₀₀ off her list.

Every time Alice logs in, she enters the last uncrossed number on her list: x_i. The computer calculates f(x_i) and compares it with x_i+1 stored in its database. Eve can’t get any useful information because each number is only used once, and the function is one-way. Similarly, the database is not useful to an attacker. Of course, when Alice runs out of numbers on her list, she has to reinitialize the system.

Authentication Using Public-Key Cryptography

Even with salt, the first protocol has serious security problems. When Alice sends her password to her host, anyone who has access to her data path can read it. She might be accessing her host through a convoluted transmission path that passes through four industrial competitors, three foreign countries, and two forward-thinking universities. Eve can be at any one of those points, listening to Alice’s login sequence. If Eve has access to the processor memory of the host, she can see the password before the host hashes it.

Public-key cryptography can solve this problem. The host keeps a file of every user’s public key; all users keep their own private keys. Here is a na•ve attempt at a protocol. When logging in, the protocol proceeds as follows:

(1)  The host sends Alice a random string.

(2)  Alice encrypts the string with her private key and sends it back to the host, along with her name.

(3)  The host looks up Alice’s public key in its database and decrypts the message using that public key.

(4)  If the decrypted string matches what the host sent Alice in the first place, the host allows Alice access to the system.

No one else has access to Alice’s private key, so no one else can impersonate Alice. More important, Alice never sends her private key over the transmission line to the host. Eve, listening in on the interaction, cannot get any information that would enable her to deduce the private key and impersonate Alice.

The private key is both long and non-mnemonic, and will probably be processed automatically by the user’s hardware or communications software. This requires an intelligent terminal that Alice trusts, but neither the host nor the communications path needs to be secure.