The key distribution problem

From here on, the attacker follows the Dolev-Yao model: full control of the network. It can eavesdrop on any message, and delay, delete, modify, replay or inject messages at will, or impersonate any party. What it cannot do is beat the cryptography itself: it cannot alter an integrity-protected message without the receiver noticing, and it cannot decrypt a message encrypted under a key it does not hold. Every attack discussed this week works within those limits, not around them.

Boyd’s theorem states the problem precisely: “Assuming the absence of a secure channel, two entities cannot establish an authenticated session without the existence of an entity that can mediate between the two and which both parties trust and have a secure channel with.” Stripped of the formality: Alice and Bob cannot securely establish keys between them if they do not already have existing, established keys. The only way out is introduction by a third party that both of them already trust and already have a secure channel with. Nothing Alice and Bob do between just the two of them, no matter how clever, escapes this.

This is exactly why Diffie-Hellman is not, on its own, a full answer. DH is secure against a passive eavesdropper: the discrete logarithm problem keeps them out. Against an active Dolev-Yao attacker, the exchange needs origin authentication on top, something that proves a given public value really came from Alice or Bob. The two standard tools for that both run straight back into Boyd’s theorem:

• A MAC requires a symmetric key shared in advance.
• A digital signature requires the verifier to already hold the sender’s real public key, correctly mapped to that sender’s identity.

Both are themselves the pre-existing trusted relationship Boyd’s theorem says is required. Diffie-Hellman does not fail here; it simply cannot be the whole answer, because no unauthenticated exchange between two strangers ever can be. What DH does provide, once it is protected this way, is worth having: forward secrecy.

Forward secrecy (FS), also called perfect forward secrecy (PFS), the lecture uses the two terms interchangeably, is the property that compromising a long-term key does not compromise the confidentiality of past session keys. Concretely: even if an attacker later obtains a server’s long-term private key, they cannot use it to decrypt sessions they recorded earlier, because those sessions’ keys were never derived from the long-term key in the first place.

Ephemeral Diffie-Hellman (DHE), or its elliptic-curve form ECDHE, is how this is achieved in practice: a new, temporary DH key pair is generated for every session and discarded once the session ends. The long-term key (an RSA or signing key, say) is used only to authenticate that session’s DH values, never to derive the session key itself. Learning the long-term key later tells an attacker nothing about any exponent that was already deleted.

Given Boyd’s theorem, there are exactly two families of option for actually establishing a key:

Without a third party. Secure physical shipment of keys, in person or by courier. It works, but it does not scale: the lecture’s own examples are high-value cases such as embassy communications, or device pairing over a side channel such as scanning a QR code.

With a third party. In the symmetric case, a Key Distribution Centre (KDC) brokers session keys between parties that each already trust it. In the asymmetric case, a Public Key Infrastructure (PKI) does the equivalent job for public keys. The rest of this week builds both.