Authentication protocols and challenge-response

An encrypted password can be replayed without knowing the key

Network login has no physical keyboard to prove someone is present. It needs a protocol, a sequence of steps: a single encrypted message cannot on its own prove when it was sent.

A cryptographic protocol is a sequence of well-defined steps with cryptographic protection layered in. Composing cryptographic operations into a secure protocol is genuinely hard: even where every individual operation is flawless, the sequence itself can still leave a loophole. The canonical example is a replay attack: an attacker records a legitimately encrypted message and resends it later, needing no secret at all to make the receiver accept it a second time.

Set up: Alice (A) wants to authenticate to Bob (B), and must prove possession or knowledge of something no one but A has. Assume A and B already share a secret key $k_{A,B}$.

Attempt 1: send the encrypted password. $A \to B: c = \text{Enc}_k(p)$. An attacker, call her Clare, intercepts $c$ and later sends $C \to B: c$ unchanged. Clare needs neither $p$ nor $k$; she only needs to have recorded $c$ once. Bob’s check, “does this decrypt to a valid password”, succeeds identically whether the sender is Alice or Clare replaying an old message.

Attempt 2: add a MAC. $A \to B: c, \text{MAC}_{k_{A,B}}(c)$. This is still not secure: a MAC proves the pair $(c, \text{MAC}(c))$ has not been altered, not that it is being sent for the first time. Clare simply replays $C \to B: c, \text{MAC}_{k_{A,B}}(c)$ intact, and Bob’s verification of the MAC succeeds exactly as before.

The notes call this person-in-the-middle in an authentication context. Bob cannot tell whether Alice participated now. Neither MACs nor signatures prevent replay on their own: the transmission must be bound to the current run, not merely to the key.

Optional aside

This is a different shape of person-in-the-middle from the naive public-key substitution covered on the key distribution with public keys page: there, the attacker substitutes its own key into the exchange; here, the attacker needs no key at all, only a recording. Both fail for the same root reason, an absence of freshness or origin binding, but the mechanics of the attack differ.

Four cryptographic primitives supply a protocol’s building blocks

Building a protocol that actually closes this gap starts from four primitives:

• Cryptographically secure random numbers. The essential ingredient underneath everything that follows.
• Cryptographic hash functions give MACs, by mixing in a shared secret.
• Public-key cryptography gives key exchange over an untrusted channel, confidentiality (typically via hybrid encryption), and origin authentication with integrity.
• Symmetric-key cryptography gives confidentiality for the actual data, and, via MACs, origin authentication and integrity.

A fresh nonce binds the response to the current exchange

Challenge-response with nonces is the fix. Let $\{m\}$ denote an encrypted, integrity-protected message, and recall a nonce is a random number used once:

A → B: NA
B → A: {NA, NB}
A → B: {NA, NB + 1}

Bob now has assurance that Alice has participated, and reacted specifically to message 2: she was able to read the freshly generated $N_B$ and return it incremented. A value replayed from an earlier run would carry a stale, different nonce, and would fail this check. The nonce can, in some settings, be replaced by a timestamp instead, though the lecture does not work through that variant in detail.

Exam detail

The exam expects the reasoning, not just the final protocol: state why attempt 1 fails (no freshness at all), why attempt 2 fails despite adding a MAC (the MAC protects integrity, not freshness), and precisely what property the nonce exchange adds that neither earlier attempt had (proof of active, current participation, not just knowledge of a key).

Pitfall

Do not write that adding a MAC to attempt 1 “fixes” the replay problem, or partially fixes it. It fixes a different problem entirely, tampering, and does nothing at all against a replay of an untouched, still-valid message. Keep integrity and freshness as two separate properties requiring two separate mechanisms.

Recall

• A replay attack needs no broken cryptography, only a recorded, still-valid message resent later.
• Encrypting the password alone, or encrypting it with a MAC, both fall to replay, because neither proves freshness.
• Challenge-response with nonces proves participation because only a live party can read a fresh $N_B$ and return it transformed.
• Protocols are built from four primitives: secure randomness, hash-based MACs, public-key crypto and symmetric-key crypto.