Challenge-Response Authentication

From Wikipedia, the free encyclopedia

In computer security, challenge-response authentication is a family of protocols in which one party presents a question ("challenge") and another party must provide a valid answer ("response") to be authenticated.

Non-Cryptographic Techniques

Password-Based Schemes

The simplest example of a challenge-response protocol is password authentication, where the challenge is asking for the password and the valid response is the correct password.

Clearly an adversary that can eavesdrop on a password authentication can then authenticate itself in the same way. One solution is to issue multiple passwords, each of them marked with an identifier. The verifier can pick any of the identifiers, and the prover must have the correct password for that identifier. Assuming that the passwords are chosen independently, an adversary who intercepts one challenge-response message pair has no more chance of responding correctly to a different challenge than an adversary who has intercepted nothing.

For example, when other communications security methods are unavailable, the U.S. military uses the AKAC-1553 TRIAD numeral cipher to authenticate and encrypt some communications. TRIAD includes a list of three-letter challenge codes, which the verifier is supposed to choose randomly from, and random three-letter responses to them. For added security, each set of codes is only valid for a particular time period - ordinarily 24 hours.

Software in the 1980s and 1990s often used a similar method for copy protection: challenges would be questions like "What is the second word in the third paragraph on page 418 of the manual?". The security assumption was that copying the manual was more difficult than copying the software disk.

Other Non-Cryptographic Protocols

Challenge-response protocols are also used to assert things other than knowledge of a secret value. Captchas, for example, are a sort of variant on the Turing test, meant to determine whether a viewer of a Web application is a person. The challenge sent to the viewer is a distorted image of some text, and the viewer responds by typing in that text. The distortion is designed to make optical character recognition difficult, so if the captcha algorithm is secure a correct transcription of the text authenticates the Web browser as human (i.e. not an email-address-harvesting robot).

Cryptographic Techniques

Non-cryptographic authentication was generally adequate in the days before the Internet, when the user could be sure that the system asking for the password was really the system they were trying to access, and that nobody was likely to be eavesdropping on the communication channel to observe the password being entered. To address the insecure channel problem, a more sophisticated approach is necessary. Many cryptographic solutions involve two-way authentication, where both the user and the system must each convince the other that they know the shared secret (the password), without this secret ever being transmitted in the clear over the communication channel, where eavesdroppers might be lurking.

One way this is done involves using the password as the encryption key to transmit some randomly-generated information as the challenge, whereupon the other end must return as its response a similarly-encrypted value which is some predetermined function of the originally-offered information, thus proving that it was able to decrypt the challenge. For instance, in Kerberos, the challenge is an encrypted integer N, while the response is the encrypted integer N + 1, proving that the other end was able to decrypt the integer N. In other variations, a hash function operates on a password and a random challenge value to create a response value.

Such encrypted or hashed exchanges do not directly reveal the password to an eavesdropper. However, they may supply enough information to allow an eavesdropper to deduce what the password is, using a dictionary attack or brute-force attack. The use of information which is randomly generated on each exchange (and where the response is different from the challenge) guards against the possibility of a replay attack, where a malicious intermediary simply records the exchanged data and retransmits it at a later time to fool one end into thinking it has authenticated a new connection attempt from the other.

It is important to note that there is a conflict between hash-based challenge-response authentication and the hashed storage of passwords commonly used on Unix-type operating systems: the latter tries to avoid the storage of the authentication secret (the password) in any easily-decodable form on the server, but a hash-based challenge-response method requires the server to be able to easily determine what the secret is, otherwise it could not convince the client that it knows what it is. The usual consequence of this is that the secret becomes the hashed version of the password (the client performing the hashing before proceeding to do challenge-response with the result), but then it becomes every bit as essential to protect the secrecy of this hashed version as it is to protect that of the original password.