Authentication protocols and challenge-response

Why an encrypted password can still be replayed over the network, why adding a MAC does not fix it, and how a three-message nonce exchange finally proves the other party is actively present.

Explain why network authentication needs a sequence of steps (a protocol), not a single encrypted message.
Reproduce the encrypted-password and encrypted-password-plus-MAC attempts and state exactly why each falls to a replay attack.
Reproduce the challenge-response-with-nonces protocol and state what it proves that the earlier attempts do not.
List the four cryptographic primitives protocols are built from and what each contributes.

15 min read

Intuition

The previous page ended on a gap: network login has no physical keyboard to prove someone is really there. Fixing that gap turns out to need more than a stronger cipher. It needs a protocol, a sequence of steps, because a single encrypted message, no matter how well encrypted, cannot on its own prove when it was sent.

Mechanism

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.

Mechanism

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.

Threat

This is the same failure the notes call person-in-the-middle in an authentication context: Alice sends a password $p$ encrypted with $k$ , and the attacker simply records $c = \text{Enc}_k(p)$ and replays it later. Bob has no way to know whether Alice actually participated in this exchange. Neither MACs nor signatures close the gap on their own, since both can themselves be replayed unchanged. The transmission has to be bound to the current run of the communication, not merely to the key.

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.

Mechanism

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.

Mechanism

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.

Source

Week 7 Notes PDF