Challenge–response authentication

For the spam-filtering technique, see Challenge–response spam filtering.

For other uses, see CRAM (disambiguation).

In computer security, challenge–response authentication is an authentication process that verifies an identity by requiring correct authentication information to be provided in response to a challenge. The authentication information is usually a value that is computed in response to an unpredictable challenge value, though some authors include systems based on a simple password response.

An adversary that can eavesdrop on a simple password authentication can then authenticate itself in the same way using a replay attack. Most challenge-response authentication systems incorporate the feature that different challenges can be issued and the prover must combine their credentials with the challenge in some way in order to authenticate. An example would be to have multiple passwords, each of them marked with an identifier. The verifier can pick any of the identifiers, and the prover must respond with the correct password for that identifier. Assuming that the passwords are chosen independently, an adversary who intercepts one challenge–response pair cannot use it to authenticate unless she is lucky enough to get the same challenge.

As a practical example, when other communications security methods are unavailable, the U.S. military uses the AKAC-1553 Triad Numeral Cypher/Authentication System or the DRYAD 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 which is 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 real 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 automated optical character recognition (OCR) difficult and preventing a computer program from passing as a human.

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.

Authentication protocols usually employ a cryptographic nonce as the challenge to ensure that every challenge–response sequence is unique. This protects against a replay attack. If it is impractical to implement a true nonce, a strong cryptographically secure pseudorandom number generator and cryptographic hash function can generate challenges that are highly unlikely to occur more than once. It is important not to use time-based nonces, as these can weaken servers in different time zones and servers with inaccurate clocks.

Mutual authentication is performed using a challenge–response handshake in both directions; the server ensures that the client knows the secret, and the client also ensures that the server knows the secret, which protects against a rogue server impersonating the real server.

Challenge–response authentication can help solve the problem of exchanging session keys for encryption. Using a key derivation function, the challenge value and the secret may be combined to generate an unpredictable encryption key for the session. This is particularly effective against a man-in-the-middle attack, because the attacker will not be able to derive the session key from the challenge without knowing the secret, and therefore will not be able to decrypt the data stream.

Simple example mutual-authentication sequence

• Server sends a unique challenge value sc to the client
• Client generates unique challenge value cc
• Client computes cr = hashA(cc + sc + secret)
• Client sends cr and cc to the server
• Server calculates the expected value of cr and ensures the client responded correctly
• Server computes sr = hashB(cc + sc + secret)
• Server sends sr
• Client calculates the expected value of sr and ensures the server responded correctly

where

• sc is the server generated challenge
• cc is the client generated challenge
• cr is the client response
• sr is the server response

Password storage

To avoid storage of passwords in simple password authentication systems, it is common practice to store a hash of the password rather than storing the password itself. During authentication, the system verifies that the hash of the password entered matches the hash stored in the password database. In a true challenge response system this approach is not suitable, since an attacker who obtains the hash can use it to construct a valid reply. Instead mathematical techniques from public key cryptography are often used to store authentication data in a form that allows an identity to be verified without allowing that identity to be forged.

Examples

Examples of more sophisticated challenge–response algorithms are zero-knowledge password proof and key agreement systems (such as Secure Remote Password (SRP)), CRAM-MD5, and ssh's challenge–response system based on RSA [1].

See also

• Challenge-Handshake Authentication Protocol
• CRAM-MD5
• Cryptographic hash function
• Cryptographic nonce
• Kerberos
• Otway–Rees protocol
• Needham–Schroeder protocol
• Wide Mouth Frog protocol
• Password-authenticated key agreement
• CAPTCHA
• reCAPTCHA
• Distance-bounding protocol
• Reflection attack
• Replay attack
• Man-in-the-middle attack
• Physical unclonable function