Challenge-Response Authentication

Overview

Challenge-Response Authentication is one of the authentication methods used to enhance security. In this method, authentication is performed without transmitting the user’s actual password over the network. This significantly reduces the risk of password leakage through eavesdropping.

This article goes beyond a simple description of the procedure and works through:

1. Why the one-wayness of hash functions is what makes this scheme secure (a formal, logical derivation)
2. Why a fresh random challenge on every run defeats replay attacks (a proof, including an entropy-based argument)
3. How real-world standards — CHAP, HOTP, and TOTP — are concrete variants of this pattern
4. Why, conversely, this scheme in its simple form offers no resistance to an active man-in-the-middle (MITM) attack

alongside the actual output of an HMAC-SHA256 implementation in Python. Note that Single Sign-On (SSO) and Identity Federation , in the same directory, covers a different authentication topic (coordinating authentication across multiple systems) — this article focuses purely on the client-server authentication protocol itself.

Flow of Challenge-Response Authentication

1. [Client] Sending User Authentication Information: When a user enters their ID and password, the client sends only the ID to the authentication server. The password is not sent.

2. [Authentication Server] Generating and Sending the Challenge Code: The authentication server identifies the user corresponding to the received ID and generates a disposable random number (challenge code) \(c\) . This challenge code is sent to the client.

3. [Client] Generating and Sending the Response: The client combines the received challenge \(c\) with the key shared between client and server (the password or a hash of it) \(k\) , and produces a response \(r\) using a hash function:

   \[ r = H(c, k) \]

   This response \(r\) is sent to the authentication server.

4. [Authentication Server] Verifying the Response: The authentication server processes its own generated challenge \(c\) and the key \(k\) it manages using the same procedure, computing \(r' = H(c, k)\) . If \(r' = r\) , the user is determined to know the legitimate key \(k\) (i.e., the password), and authentication succeeds.

The rest of this article carefully derives why this seemingly simple formula, \(r = H(c,k)\) , achieves secure authentication, starting from the properties of hash functions.

Why It’s Secure: A Derivation from the One-Wayness of Hash Functions

Formalizing the attacker’s viewpoint

An eavesdropper on the network can observe only the ID, the challenge \(c\) , and the response \(r=H(c,k)\) . The key \(k\) (the secret corresponding to the password) itself never appears on the wire. The attacker’s goal is one of the following:

• (A) Recover the key \(k\) itself (once recovered, the attacker can correctly respond to any future challenge)
• (B) Forge a correct response \(r\) for a specific challenge \(c\) without ever learning \(k\)

The cryptographic properties required of a hash function (or a keyed hash such as HMAC) are exactly what guarantee that both of these are hard.

The property that prevents (A): one-wayness (preimage resistance)

A hash function \(H\) has one-wayness, or more precisely preimage resistance, if, given an output \(y=H(x)\) , there is no efficient algorithm (within realistic computational resources) for finding an \(x'\) such that \(H(x')=y\) .

In challenge-response authentication, the attacker holds \(c\) (known) and \(r=H(c,k)\) (observable), which is exactly a preimage-search problem over an input that contains \(k\) . If \(H\) is preimage-resistant, the attacker cannot recover \(k\) from this pair \((c, r)\) . This is the core reason this scheme can authenticate “without ever sending the password \(k\) itself over the network.”

The property that prevents (B): HMAC as a pseudorandom function (PRF)

One-wayness alone is actually not enough, because (B) is a strictly weaker (i.e., easier for the attacker) goal than (A): forging \(r\) for one specific \(c\) without recovering \(k\) . The property needed to prevent (B) is what cryptographic theory calls existential unforgeability of a MAC under a chosen-message attack (EUF-CMA).

• The attacker can impersonate the server toward the client, sending arbitrarily chosen challenges \(c_1, c_2, \dots\) and collecting the corresponding responses \(r_1=H(c_1,k), r_2=H(c_2,k),\dots\) (this can be viewed as oracle access equivalent to a chosen-plaintext attack).
• Even so, the attacker must not be able to compute, with non-negligible probability, the correct response \(r^\*=H(c^\*,k)\) for a new challenge \(c^\*\) that was never queried.

It is known that a naive \(H(c \Vert k)\) (a hash function applied to a keyed concatenation) can fail to satisfy this property against Merkle-Damgård-based hash functions, due to a weakness called the length-extension attack (https://yuhi-sa.github.io/en/posts/20260715_sha256_hmac/1/ actually carries out this attack successfully). This is why, in practice — including the numerical experiment in this article — the standard choice is HMAC (RFC 2104), whose nested construction defeats length-extension attacks:

HMAC has been shown, under standard assumptions, to behave as a pseudorandom function (PRF), and therefore satisfies the EUF-CMA property above. Consequently, no matter how many past challenge-response pairs an attacker observes, they cannot compute the correct response for a new challenge without knowing \(k\) .

Proof of Replay-Attack Resistance

Why replaying an old \((c,r)\) pair fails

Suppose the challenge \(c\) is drawn independently and uniformly at random from an \(n\) -bit space on every authentication (\(|C|=2^n\) ). Suppose an attacker who eavesdropped a past pair \((c_{old}, r_{old})\) (with \(r_{old}=\mathrm{HMAC}(k,c_{old})\) ) simply resends it in a new session. Since the new session’s challenge \(c_{new}\) is chosen independently,

so \(c_{new} \neq c_{old}\) holds with overwhelming probability (for sufficiently large \(n\) ). In that case, the value the server correctly expects is \(\mathrm{HMAC}(k, c_{new})\) , whereas the attacker’s replayed value \(r_{old}=\mathrm{HMAC}(k,c_{old})\) corresponds to a different challenge. By the EUF-CMA property discussed above (HMAC behaving as a PRF), as long as \(c_{old}\neq c_{new}\) ,

which is negligible (\(\ell\) is the bit length of the HMAC output — 256 bits for a SHA-256-based construction). In other words, a replay fails with near certainty the moment \(c_{new}\neq c_{old}\) .

Edge case: predictable or reused challenges

The proof above relies heavily on the premise that the challenge has sufficient entropy and is never reused. When that premise breaks down, replay attacks become a real, practical threat.

• Challenge space too small: with an \(n\) -bit challenge, after observing \(q\) sessions, the birthday bound tells us the probability that some challenge value repeats is roughly \(q^2/2^{n+1}\) . If \(n\) is small (say, around 16 bits), a relatively small number of observed sessions is enough to trigger a challenge collision, after which a previously recorded response becomes valid again.
• Predictable or deterministic challenges: for example, a simple incrementing counter, or a pseudorandom number generator (PRNG) seeded weakly, lets an attacker predict the next challenge in advance. Predicting the challenge alone does not let the attacker compute the correct \(r\) without \(k\) (per the EUF-CMA property above) — but if a server-side implementation bug resets a counter, or issues the same challenge twice, a previously recorded \((c,r)\) pair can simply be replayed and authentication defeated.
• No used-challenge tracking on the server: if the server does not guarantee that a given challenge value is never accepted twice, an attacker may be able to replay a legitimately observed response while the server still remembers (and would accept) the old challenge.

All of these are cases where the premise of “randomness and freshness of the challenge” breaks down. This is exactly why implementing challenge-response authentication requires using a cryptographically secure random number generator, choosing a sufficiently long challenge (generally 128 bits or more), and rejecting already-used challenges.

Comparing CHAP, HOTP, and TOTP: What Differs in the “Challenge”

Challenge-response authentication is an abstract design principle, and several real-world standards implement it as concrete variants. The differences mainly come down to what is used as the challenge.

This table shows that CHAP uses a challenge in the classic sense — “the server sends a random value” — whereas HOTP/TOTP are variants that never explicitly transmit a challenge. By using a counter or a timestamp — a value both sides can compute independently — as an “implicit challenge,” these schemes save a round trip, but this comes with trade-offs.

• HOTP: an OTP for a given counter value remains valid until the server records that counter as used and rejects it. The resynchronization logic needed when the counter drifts out of sync (advancing the counter within an allowed window to re-check) can give an attacker a small amount of extra leeway.
• TOTP: an OTP remains valid for the duration of one time step (30 seconds by default). In other words, whereas a random-challenge scheme has, in theory, almost zero window for replay, TOTP has a replay window equal to the time step (and many implementations also accept the adjacent step to tolerate clock drift, widening this window further).
• CHAP: MD5, the default algorithm in RFC 1994, is no longer recommended from a collision-resistance standpoint, but what CHAP actually relies on is mainly one-wayness (preimage resistance), and MD5’s preimage resistance itself has not been seriously broken in practice as of this writing. That said, CHAP has a structural weakness in that the server must store a plaintext-equivalent form of the secret (a hashed password alone is not enough to verify), and a raw hash function applied to a keyed concatenation, \(H(\text{ID}\Vert\text{secret}\Vert\text{challenge})\) , is harder to reason about securely than a vetted construction like HMAC. For these reasons, CHAP itself is now considered deprecated, and migration to stronger EAP-based authentication methods is the current direction.

The Limits of MITM Resistance

Challenge-response authentication is strong against eavesdropping and naive replay, but in its simple form it offers no resistance to an active man-in-the-middle (MITM) attack that actively relays and can tamper with traffic. This is an important, easily overlooked limitation.

A concrete attack scenario: the relay attack

Suppose an attacker \(M\) sits on the communication path between a legitimate client \(A\) and a legitimate server \(S\) .

1. \(A\) sends its ID to \(M\) (who, from \(A\) ’s perspective, appears to be \(S\) ).
2. \(M\) forwards this ID unmodified to the real \(S\) .
3. \(S\) generates a genuine random challenge \(c\) and sends it to \(M\) .
4. \(M\) forwards this \(c\) unmodified to \(A\) .
5. \(A\) correctly computes \(r=\mathrm{HMAC}(k,c)\) and sends it to \(M\) .
6. \(M\) forwards this \(r\) unmodified to \(S\) .
7. \(S\) verifies \(r\) and concludes authentication succeeded.

Through this sequence, \(M\) succeeds in making the authentication between \(A\) and \(S\) go through, all without ever learning \(k\) . The problem is that \(M\) remains positioned on the communication path even after authentication completes. From that position, \(M\) can continue to eavesdrop on and tamper with the (supposedly now-authenticated) traffic between \(A\) and \(S\) . Challenge-response authentication only proves “the entity that answered knew \(k\) at that moment” — it says nothing about whether the subsequent communication channel can be trusted.

Countermeasures: mutual authentication and channel binding

Addressing this limitation requires additional mechanisms:

• Mutual authentication: having the server prove itself as well as the client can prevent some categories of damage (e.g., connecting to an impersonating server). However, a pure relay attack, in which \(M\) simply forwards both directions honestly, is not addressed by mutual authentication alone — \(M\) just passes each side’s legitimate exchange straight through, letting both sides’ authentication succeed.
• Channel binding: this technique ties the authentication exchange (the challenge and response) to a value unique to the underlying communication channel (for example, a TLS session). This way, even if \(M\) can relay the challenge and response, the \(A\) -\(M\) TLS channel and the \(M\) -\(S\) TLS channel are distinct — so \(S\) can detect the mismatch between “the channel the authentication was bound to” and “the channel actually in use,” neutralizing the relay.

In short, challenge-response authentication by itself only guarantees “the plaintext password never crosses the wire” and “a simple replay fails” — it does not, by itself, cryptographically bind the authentication event to a specific communication channel or session. Defending against an active MITM requires mutual authentication, channel binding, or a design like WebAuthn/FIDO2 (discussed below), which includes the communication origin (destination domain) itself in what gets signed.

Numerical Experiment: Verifying Challenge-Response Authentication with HMAC-SHA256

Let’s put the above discussion into actual running Python code. We simulate a client and server sharing a key \(k\) , and verify four scenarios: (1) legitimate authentication, (2) a replay attack against a new challenge, (3) authentication with an incorrect key, and (4) a replay that succeeds because the challenge was reused.

import hmac
import hashlib
import secrets


def generate_challenge(nbytes: int = 16) -> bytes:
    """Generate a cryptographically secure random challenge."""
    return secrets.token_bytes(nbytes)


def client_response(key: bytes, challenge: bytes) -> bytes:
    """Client side: compute r = HMAC(k, c)."""
    return hmac.new(key, challenge, hashlib.sha256).digest()


def server_verify(key: bytes, challenge: bytes, response: bytes) -> bool:
    """Server side: recompute HMAC(k, c) and compare in constant time."""
    expected = hmac.new(key, challenge, hashlib.sha256).digest()
    return hmac.compare_digest(expected, response)


shared_key = secrets.token_bytes(32)  # 256-bit key pre-shared between client and server

# Scenario 1: legitimate authentication
c1 = generate_challenge()
r1 = client_response(shared_key, c1)
ok1 = server_verify(shared_key, c1, r1)

# Scenario 2: replay attack against a fresh, independently generated challenge
c2 = generate_challenge()
ok2_replay_fresh = server_verify(shared_key, c2, r1)

# Scenario 3: authentication with the wrong shared key
wrong_key = secrets.token_bytes(32)
r3 = client_response(wrong_key, c1)
ok3_wrong_key = server_verify(shared_key, c1, r3)

# Scenario 4: replay that succeeds because the challenge was reused
# (simulating a weak RNG / counter reset)
ok4_replay_reused_challenge = server_verify(shared_key, c1, r1)

print(f"c1 = {c1.hex()}")
print(f"r1 = {r1.hex()}")
print(f"c2 = {c2.hex()}  (differs from c1: {c1 != c2})")
print(f"Scenario 1 legitimate auth: {ok1}")
print(f"Scenario 2 replay (fresh challenge): {ok2_replay_fresh}")
print(f"Scenario 3 wrong key: {ok3_wrong_key}")
print(f"Scenario 4 replay (reused challenge): {ok4_replay_reused_challenge}")

Output:

c1 = 24de785a3ff43a32a8a9524a1b84db22
r1 = 1e482276c3da679d0d69a8fcc98be3b12bf569ecbe624aa7403c904d5113ef7e
c2 = d700d389cdc9d76c3f661a8ab964617b  (differs from c1: True)
Scenario 1 legitimate auth: True
Scenario 2 replay (fresh challenge): False
Scenario 3 wrong key: False
Scenario 4 replay (reused challenge): True

The results match the theoretical discussion exactly. (1) The legitimate client always authenticates successfully, and (2) replaying the old response \(r_1\) against a freshly generated, independent challenge \(c_2\) fails, since \(c_1 \neq c_2\) makes the HMAC outputs differ. (3) A response computed with the wrong key is naturally rejected as well. However, (4) if the same challenge \(c_1\) somehow gets reused, the previously recorded response \(r_1\) works again and authentication succeeds — reproducing in actual code the edge case discussed above: replay resistance collapses the moment challenge freshness is violated.

Also note the use of hmac.compare_digest, a constant-time comparison function, in server_verify. A naive == comparison, or any implementation that returns early on the first mismatched byte, can be vulnerable to timing attacks (inferring how close a guess is to correct from tiny differences in response time). Always using a constant-time comparison function when checking hash values or MACs is an important implementation detail.

The figure below illustrates Scenario 1 (the legitimate authentication flow) and Scenario 2 (a replay attack failing against a fresh challenge).

Recent Direction: The Evolution Toward Passkeys / WebAuthn / FIDO2

Passkeys, which increasingly come up in the context of passwordless authentication, along with the underlying WebAuthn (a Web API standardized by the W3C) and FIDO2, can be positioned as an evolution of the challenge-response scheme covered in this article.

The basic skeleton of the exchange is the same: a server (Relying Party) sends a random challenge, and a client-side authenticator (a device’s biometric sensor, a security key, etc.) responds to it. What differs substantially is how the response is constructed.

• The scheme covered in this article: the client and server share a symmetric secret key \(k\) , and the response is computed symmetrically, e.g., \(r=H(c,k)\) or \(\mathrm{HMAC}(k,c)\) . The server must be able to hold or reproduce \(k\) (in some hashed form).
• WebAuthn/FIDO2: of the public-key pair generated at registration time, the private key never leaves the client-side device. At authentication time, the client produces a digital signature over a data structure that includes the server’s challenge (plus contextual information such as the connection origin), and the server verifies it using the previously registered public key.

This difference has a structural advantage: with a symmetric-key scheme, if the server’s database is compromised, an attacker may (depending on how secrets are stored) be able to forge a valid response; with a public-key scheme, the server only ever holds a public key, and its compromise does not, by itself, allow forging a response (signature). Including origin information in what gets signed also gives this design stronger resistance than a simple symmetric challenge-response scheme against the MITM/phishing-style relay attacks discussed above.

What’s described here reflects the generally well-known basic design of passkeys and WebAuthn/FIDO2. For specification details or the current state of adoption, it’s best to consult the primary sources from the W3C and the FIDO Alliance directly.

Advantages

• Reduced Risk of Password Eavesdropping: Since the password itself never travels over the network, the risk of password leakage through eavesdropping is low.
• Resistance to Replay Attacks: Since the challenge code is a fresh, sufficiently high-entropy random value each time, replaying previously eavesdropped communications cannot break through authentication — in the probabilistic sense proven in this article.
• Understanding the limits matters just as much: on the other hand, this scheme in its simple form offers no resistance to an active man-in-the-middle attack, so the communication channel itself needs to be protected (e.g., via TLS), combined with mutual authentication and channel binding where needed.

Related Articles

• SHA-256 and HMAC: Theory and Python Implementation - Verifies, via a from-scratch implementation and RFC 4231 test vectors, the Merkle-Damgård construction, the length-extension attack, and the nested HMAC construction that this article’s HMAC-SHA256 implementation relies on.
• Single Sign-On (SSO) and Identity Federation - While challenge-response is an authentication protocol for a single system, this article covers coordinating authentication information across multiple systems.
• Email Security: Authentication and Encryption Mechanisms - Touches on the use of challenge-response-based methods, which avoid sending passwords directly, as an SMTP Auth mechanism.

References

• Challenge-Response Authentication - Wikipedia
• Simpson, W. (1996). PPP Challenge Handshake Authentication Protocol (CHAP). RFC 1994.
• M’Raihi, D., Bellare, M., Hoornaert, F., Naccache, D., & Ranen, O. (2005). HOTP: An HMAC-Based One-Time Password Algorithm. RFC 4226.
• M’Raihi, D., Machani, S., Pei, M., & Rydell, J. (2011). TOTP: Time-Based One-Time Password Algorithm. RFC 6238.
• Krawczyk, H., Bellare, M., & Canetti, R. (1997). HMAC: Keyed-Hashing for Message Authentication. RFC 2104.
• W3C. Web Authentication: An API for accessing Public Key Credentials (WebAuthn). W3C Recommendation.