Introduction to Computer Security - Section 11.3. Challenge-Response

Passwords have the fundamental problem that they are reusable. If an attacker sees a password, she can later replay the password. The system cannot distinguish between the attacker and the legitimate user, and allows access. An alternative is to authenticate in such a way that the transmitted password changes each time. Then, if an attacker replays a previously used password, the system will reject it.

Definition 117. Let user U desire to authenticate himself to system S. Let U and S have an agreed-on secret function f. A challenge-response authentication system is one in which S sends a random message m (the challenge) to U, and U replies with the transformation r = f(m) (the response). S validates r by computing it separately.

Challenge-response algorithms are similar to the IFF (identificationfriend or foe) techniques that military airplanes use to identify allies and enemies.

11.3.1. Pass Algorithms

Definition 118. Let there be a challenge-response authentication system in which the function f is the secret. Then f is called a pass algorithm.

Under this definition, no cryptographic keys or other secret information may be input to f. The algorithm computing f is itself the secret.

EXAMPLE: Haskett [405] suggests using this scheme in combination with a standard password scheme. After the user supplies a reusable password, a second prompt is given (Haskett points out that this could be the same as the system's standard prompt, to confuse attackers). At this point, the user must enter some string based on an algorithm. For example, if the prompt "abcdefg" were given, the appropriate response could be "bdf"; if the prompt were "ageksido," the appropriate response could be "gkio" (the algorithm is every other letter beginning with the second). Or, to use Haskett's example, the pass algorithm can alter a fixed password. In this case, at the prompt, the user would enter "wucsmfxymap" if the terminal were on a dial-in line, "acdflmq" if it were in a semisecure area, and "cfm" if it were in a secure area. Here, "cfm" is the expected password; the location dictates how many random characters surround each of the letters.

11.3.2. One-Time Passwords

The ultimate form of password aging occurs when a password is valid for exactly one use. In some sense, challenge-response mechanisms use one-time passwords. Think of the response as the password. As the challenges for successive authentications differ, the responses differ. Hence, the acceptability of each response (password) is invalidated after each use.

Definition 119. A one-time password is a password that is invalidated as soon as it is used.

A mechanism that uses one-time passwords is also a challenge-response mechanism. The challenge is the number of the authentication attempt; the response is the one-time password.

The problems in any one-time password scheme are the generation of random passwords and the synchronization of the user and the system. The former problem is solved by using a cryptographic hash function or enciphering function such as the DES, and the latter by having the system inform the user which password it expectsfor example, by having all the user's passwords numbered and the system providing the number of the one-time password it expects.

EXAMPLE: S/Key [390] implements a one-time password scheme. It uses a technique first suggested by Lamport [542] to generate the passwords. Let h be a one-way hash function (S/Key uses MD4 or MD5, depending on the version). Then the user chooses an initial seed k, and the key generator calculates

h(k) = k₁, h(k₁) = k₂, ..., h(k_n₁) = k_n

The passwords, in the order they are used, are

p₁ = k_n, p₂ = k_n₁, ..., p_n₁ = k₂, p_n = k₁

Suppose an attacker intercepts p_i. Because p_i = k_n_i₊₁, p_i₊₁ = k_n_i, and h(k_n_i) = k_n_i₊₁, the attacker would need to invert h, or launch a dictionary attack on h, in order to determine the next password. Because h is a one-way function, it cannot be inverted. Furthermore, for MD4 and MD5, dictionary attacks are not a threat provided the seeds are chosen randomly, an assumption we (and the authors of S/Key) make implicitly.

The S/Key system takes the seed the user enters and generates a list of n passwords. The implementation presents each password as a sequence of six short words (but the internal representation is an integer). The user can generate a numbered list of these sequences. S/Key initializes a database, called the skeykeys file, with the number of the next password to be supplied and the hexadecimal representation of the last password correctly supplied.

The protocol proceeds as follows.

1.
User Matt supplies his name to the server.

2.
The server replies with the number i stored in the skeykeys file.

3.
Matt supplies the corresponding password p_i.

4.
The server computes h(p_i) = h(k_n_i₊₁) = k_n_i₊₂ = p_i₁ and compares the result with the stored password. If they match, the authentication succeeds. S/Key updates the number in the skeykeys file to i 1 and stores p_i in the file. If the authentication fails, the skeykeys file is left unchanged.

When a user has used all passwords of a particular sequence of passwords, that user's entry in the skeykeys file must be reinitialized. This requires the user to reregister with the S/Key program.

One-time passwords are considerably simpler with hardware support because the passwords need not be printed on paper or some other medium.

11.3.3. Hardware-Supported Challenge-Response Procedures

Hardware support comes in two forms: a program for a general-purpose computer and special-purpose hardware support. Both perform the same functions.

The first type of hardware device, informally called a token, provides mechanisms for hashing or enciphering information. With this type of device, the system sends a challenge. The user enters it into the device. The device returns the appropriate response. Some devices require the user to enter a personal identification number or password, which is used as a cryptographic key or is combined with the challenge to produce the response.

The second type of hardware device is temporally based. Every 60 seconds, it displays a different number. The numbers range from 0 to 10ⁿ 1, inclusive. A similar device is attached to the computer. It knows what number the device for each registered user should display. To authenticate, the user provides his login name. The system requests a password. The user then enters the number shown on the hardware device, followed by a fixed (reusable) password. The system validates that the number is the one expected for the user at that time and that the reusable portion of the password is correct.

EXAMPLE: The RSA SecureID card uses a system based on time. In addition to the features described above, the password is invalidated once a login succeeds. (See Exercise 12.)

11.3.4. Challenge-Response and Dictionary Attacks

Whether or not a challenge-response technique is vulnerable to a dictionary attack of type 1 depends on the nature of the challenge and the response. In general, if the attacker knows the challenge and the response, a dictionary attack proceeds as for a reusable password system.

EXAMPLE: Suppose a user is authenticating herself using a challenge-response system. The system generates a random challenge r, and the user returns the value E_k(r) of r enciphered using the key k. Then the attacker knows both r and E_k(r) and can try different values of k until the encipherment of r matches E_k(r).

In practice, it is not necessary to know the value of r. Most challenges are composed of random data combined with public data that an attacker can determine.

EXAMPLE: In the authentication system Kerberos [872], an authentication server enciphers data consisting of a name, a timestamp, some random data, and a cryptographic key. An attacker does not see the original data sent to the server. By knowing the form and contents of part of the data sent back, the attacker can try cryptographic keys until the known parts of the enciphered data decipher correctly. From this, she can derive the cryptographic key to be used in future communications. Researchers at Purdue University combined this with a weakness in key generation to compromise Kerberos Version 4 [277].

Bellovin and Merritt [73] propose a technique, called encrypted key exchange, that defeats dictionary attacks of type 1. Basically, it ensures that random challenges are never sent in the clear. Because the challenges are random, and unknown to the attacker, the attacker cannot verify when she has correctly deciphered them. Hence, the dictionary attack is infeasible.

The protocol assumes that Alice shares a secret password with Bob.

Alice uses the shared password s to encipher a randomly selected public key p for a public key system. Alice then forwards this key, along with her name, to Bob.
Bob determines the public key using the shared password, generates a random secret key k, enciphers it with p, enciphers the result with s, and sends it to Alice.
Alice deciphers the message to get k. Now both Bob and Alice share a randomly generated secret key. At this point, the challenge-response phase of the protocol begins.

Alice generates a random challenge R_A, enciphers it using k, and sends E_k(R_A) to Bob.

Bob uses k to decipher R_A. He then generates a random challenge R_B and enciphers both with k to produce E_k(R_AR_B). He sends this to Alice.
Alice deciphers the message, validates R_A, and determines R_B. She enciphers it using k and sends the message E_k(R_B) back to Bob.
Bob deciphers the message and verifies R_B.

At this point, both Alice and Bob know that they are sharing the same random key k. To see that this system is immune to dictionary attacks of type 1, look at each exchange. Because the data sent in each exchange is randomly selected and never visible to the attacker in plaintext form, the attacker cannot know when she has correctly deciphered the message.