Key exchange, the CK (Canetti-Krawczyk) model and authenticated Diffie-Hellman

Before ThisWhere Chapter 2 Left Off

Chapter 2 built public-key encryption, signatures and the Diffie-Hellman assumptions, and closed on the key distribution problem. This is the first lecture to use that machinery. The question is how two parties who share no key can create one over a channel the adversary controls.

This LectureWhat It Adds

The lecture introduces key exchange as the bridge between symmetric and asymmetric cryptography. It opens with the four-item checklist (agreement, secrecy, authentication and key confirmation) that every later protocol is scored against. It gives Diffie-Hellman and perfect forward secrecy, breaks the plain protocol with a man-in-the-middle attack, and defines authenticated key exchange. Two failed attempts motivate the ISO 9796 (International Organization for Standardization) binding of identities. The Canetti-Krawczyk model turns the desiderata into a game with sessions, exposure and a test key. Authenticators then provide a modular compilation route, SKEME (Secure Key Exchange Mechanism) and Station-to-Station (STS) instantiate it, Sign-and-MAC (SIGMA) refines it for identity protection, and MQV (Menezes-Qu-Vanstone) and Hashed MQV (HMQV) replace transmitted signatures with implicit authentication.

Plain Diffie-Hellman is secure against a passive adversary under the Decisional Diffie-Hellman (DDH) assumption and gives perfect forward secrecy, because the ephemeral exponents are erased. The man-in-the-middle attack is the reason authentication enters every later protocol: Eve substitutes her own public values and ends the exchange with one key toward Alice and another toward Bob. The animation and lab below run the attack on exact small parameters.

The two failed Authenticated Key Exchange (AKE) attempts show that informal arguments are unreliable. CK (Canetti-Krawczyk) names sessions, lets the adversary control the network and interleave runs, defines exposure through corruption or learning queries, and tests one unexposed session against a random key. Identity misbinding is caught by combining the test query with an exposure query on the parallel session. The animation below steps through matching sessions, network control and the test key.

ISO 9796 places the peer identity inside the signature and inside the final hash. Authenticators compile protocols from an ideal authenticated-channel model to the real unauthenticated one, with signature and encryption variants. SKEME applies the encryption authenticator to Diffie-Hellman inside IKE (Internet Key Exchange), and the Station-to-Station protocol (STS) shows why possession of the DH key must still be bound to identities. SIGMA signs the DH transcript and tags identities with derived keys, with SIGMA-I and SIGMA-R choosing which identity survives an active adversary. HMQV removes transmitted signatures entirely and obtains implicit authentication by hashing the peer identity into the exponent.

1. Chapter 3 §1: The key exchange problem. Keep the bootstrapping role clear: Key Exchange (KE) creates the key that Chapter 1 schemes consume.
2. §2: Diffie-Hellman key exchange. Be able to write the protocol, the shared key and the Decisional Diffie-Hellman (DDH) argument for passive security, and state why erasure gives perfect forward secrecy.
3. §3: The man-in-the-middle attack. Reproduce the substitution with the lab numbers. The attack is the motive for every later section.
4. §4: Authenticated key exchange, and two failed attempts. Know why signing $X$ alone fails replay and why signing $X \| Y$ still permits identity misbinding.
5. §5: The ISO 9796 (International Organization for Standardization) defense. Learn the signed string $X \mid Y \mid A$ and the key hash $k = \Hash(A \mid B \mid X \mid Y \mid K)$.
6. §6: The Canetti-Krawczyk model. Be able to state matching sessions, exposure and the test-key game, and to explain the three sanity checks.
7. §7: Authenticators, SKEME (Secure Key Exchange Mechanism) and station-to-station. Know the signature authenticator guarantee and how SKEME compiles DH (Diffie-Hellman).
8. §8: Sign-and-MAC (SIGMA). Compare basic SIGMA, SIGMA-I and SIGMA-R by which identity each protects against active attackers.
9. §9: MQV (Menezes-Qu-Vanstone) and Hashed MQV (HMQV). Be able to derive the HMQV shared value and to outline the reduction chain through Exponential Challenge-Response (XCR) signatures.

• Diffie-Hellman drill with $p=29$: public values and shared key, checked by both sides.
• Man-in-the-middle with exact numbers: the two keys Eve establishes and the honest key she prevents.
• Identity misbinding on the second Authenticated Key Exchange (AKE) attempt: what verifies, what Eve learns and what Bob believes.
• Identity misbinding as a CK (Canetti-Krawczyk) break: test session plus exposure query.
• Hashed Menezes-Qu-Vanstone (HMQV) algebra: show both parties compute $g^{(x+da)(y+eb)}$.