Challenge-response authentication

The fundamental property of challenge-response authentication is that the response depends on both the secret and the challenge, so an eavesdropper who captures one exchange cannot replay it later. In symmetric-key variants, both parties share a secret, and the response is typically a cryptographic function of the challenge and the secret, such as a keyed hash. In public-key variants, the challenge is encrypted with the verifier's public key or signed with the claimant's private key, enabling authentication without shared secrets.

Common implementations include CRAM-MD5, used in email protocols, and the challenge-handshake authentication protocol (CHAP) in PPP. Modern systems often combine challenge-response with time-based one-time passwords (TOTP) to provide two-factor authentication, where the challenge is the current time and the response is derived from a shared secret.

The concept of challenge-response dates back to early computer security research in the 1970s, when Roger Needham and others explored authentication protocols. One of the first published schemes was the Needham-Schroeder protocol (1978), which used nonces (random numbers) as challenges to prevent replay attacks. Later, the Kerberos protocol, developed at MIT in the 1980s, incorporated challenge-response elements into its ticket-based authentication.

In the 1990s, the rise of the internet led to standards like CRAM-MD5 (RFC 2195) for SMTP authentication and the development of HTTP Digest Access Authentication (RFC 2617), which uses a challenge-response mechanism to secure web transactions. These protocols were designed to avoid sending passwords in cleartext, a major vulnerability of earlier systems.

Challenge-response authentication is widely used in network protocols, including PPP's CHAP, Wi-Fi's WPA2-Enterprise (EAP-PEAP), and SSH public-key authentication. It is also the basis for many CAPTCHA systems, where the challenge is a distorted image or puzzle that humans can solve but automated bots cannot. In hardware security, smart cards and security tokens often use challenge-response to authenticate to a reader without exposing the stored secret.

Financial institutions use challenge-response in chip-and-PIN cards, where the card generates a dynamic response to a transaction challenge. Additionally, challenge-response is a key component of zero-knowledge proofs, allowing a party to prove knowledge of a secret without revealing it, as used in some blockchain authentication schemes.

One overlooked application is in satellite communications, where challenge-response is used to prevent unauthorized access to military and commercial satellite links. Another is in the early days of Unix, where the s/key one-time password system used a challenge-response mechanism based on a hash chain, predating modern OTPs.

Challenge-response also appears in the FIDO2 standard, where a WebAuthn authenticator signs a challenge to prove possession of a private key. A niche edge case is the use of challenge-response in RFID systems to prevent cloning, though some implementations have been broken due to weak random number generators. Additionally, the concept is used in human interactive proofs beyond CAPTCHAs, such as in accessibility systems that use audio challenges.

Nonce

A number used only once, often random, used as a challenge to prevent replay attacks.

Replay attack

An attack where a valid data transmission is maliciously repeated or delayed.

CRAM-MD5

A challenge-response authentication mechanism using MD5 hash, defined in RFC 2195.

CHAP

Challenge-Handshake Authentication Protocol, used in PPP to authenticate users.

TOTP

Time-based One-Time Password, a type of challenge-response using time as the challenge.