Challenge-response protocol

A challenge-response protocol is a technique for managing source authentication.

As a simple example, consider a user who wants to log in to a computer system. If he sends the actual password, or a hash of it, over the wire, then a wiretapper can get it. Moreover, if an attacker can obtain a list of encrypted passwords from the target system, either by reading it from an account on the system or by intercepting them on the wire, then he can conduct a dictionary attack and break into any account whose password is in the dictionary.

In a challenge-response protocol, the interaction might go like this instead:

1. the user requests a connection
2. the system generates a random challenge C, using a strong random number generator
3. the system sends C to the user
4. the user encrypts C with a block cipher, using the hash of his password as key, to generate the response R
5. the user sends R back to the system
6. the system decrypts R, using the stored hash of the user password as key
7. if the result is C, the connection is allowed

There are many variations. The example uses a block cipher, but it can also be done with public key techniques — the user encrypts with his private key in step 4 and the system verifies with the public key in step 6. A hash can also be used — step 4 is then to hash some combination of data that includes the challenge and the hashed password to get R, and step 6 is to hash the same data and compare the result to R.

In any case, the actual password is never transmitted. An eavesdropper can see C and R each time, but that does him little good. Next time a different challenge will be used and a different response required. If the cryptography used is sound, then even with a large collection of challenge/response pairs, it should be very difficult for him to discover anything about the password.

The challenge must be large enough to prevent a birthday attack. With a challenge of 2ⁿ bits, an attacker who logs the data from 2^n/2 interactions has a significant chance of seeing a repeated challenge.