The key distribution problem

Key distribution starts with an existing trusted relationship

Every scheme covered so far quietly assumed a key was already where it needed to be. Symmetric encryption assumed both sides already held the same key. Public-key encryption assumed the sender already knew the receiver’s real public key. How does either key get there over a network an attacker fully controls? That is 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.” Alice and Bob need pre-existing keys or introduction by a third party they both already trust and have a secure channel with.

Diffie-Hellman needs authentication against an active attacker

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.

Fresh ephemeral keys protect past sessions from later compromise

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.

Exam detail

Two terms the exam expects kept straight: forward secrecy protects past sessions if a future compromise happens; it says nothing about protecting a session that is still ongoing when the compromise occurs. The construction that actually delivers it, signing fresh Diffie-Hellman values every session, is worked through in full on the authenticated key establishment page, including why a reused pair of DH exponents forfeits the property for every session that shares them.

Physical delivery or a trusted third party puts keys in place

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.

Optional aside

Strictly, some cryptographic writing treats “forward secrecy” and “perfect forward secrecy” as subtly different terms with a specific technical distinction between them. The lecture does not draw that distinction and uses them as synonyms throughout; that usage is what the exam expects.

Recall

• Every prior scheme assumed a key was already in place; key distribution is the question of how it gets there.
• Boyd’s theorem: no authenticated session without an existing secure channel to a mutually trusted third party.
• Diffie-Hellman resists a passive attacker but needs a MAC or signature, both circular under Boyd’s theorem, to resist an active one.
• Forward secrecy protects past sessions from a future long-term-key compromise; DHE/ECDHE deliver it with fresh, deleted exponents per session.
• The two paths forward are a KDC (symmetric) or a PKI (asymmetric), both trusted third parties in Boyd’s sense.