Distributing symmetric keys with public-key encryption

Why naively advertising a public key to distribute a session key falls to a person-in-the-middle attack, the nonce-based scheme that adds confidentiality and authentication, and IBM's hybrid KDC-plus-public-key alternative.

Reproduce the naive public-key person-in-the-middle attack message by message and state what D ends up holding.
Reproduce the confidentiality-and-authentication scheme and explain what each nonce and each encryption layer achieves.
Explain what the hybrid scheme adds to a plain KDC and why.

15 min read

Intuition

Public-key cryptosystems are too slow to encrypt bulk data directly, so their real job is usually to move a small secret, a symmetric session key, into place. Simply broadcasting a public key so anyone can do this looks safe: nothing about the key itself is secret. It fails the moment an active attacker sits between the two parties.

Mechanism

The notes’ naive scheme: A generates a key pair $\{PU_a, PR_a\}$ and sends B a message consisting of $PU_a$ and its identifier $ID_A$ , expecting B to use $PU_a$ to send back a secret key.

Threat

Person-in-the-middle on naive public-key distribution. An attacker D intercepts every message between A and B:

A generates $\{PU_a, PR_a\}$ and transmits $PU_a, ID_A$ , intended for B.
D intercepts the message, generates its own pair $\{PU_d, PR_d\}$ , and transmits $PU_d, ID_A$ to B, still claiming to be A.
B, believing it now holds A’s real public key, generates a secret key $K_s$ and transmits $E(PU_d, K_s)$ .
D intercepts this and recovers $K_s$ by computing $D(PR_d, E(PU_d, K_s))$ .
D transmits $E(PU_a, K_s)$ to A, using A’s real public key so A’s decryption still succeeds.

Both A and B now hold $K_s$ and believe they share it only with each other. D holds it too. Because D no longer needs to alter anything further, it can drop back to pure eavesdropping, decrypting every subsequent message with $K_s$ , while A and B remain unaware anything is wrong. This is exactly why the notes describe this scheme as useful only where the sole threat is eavesdropping: it offers no defence at all against an active attacker.

Control

Authenticate the public key exchange itself before trusting it. §3.2 does this with nonces; the certificate machinery in the rest of this week does it by having a trusted third party vouch for the binding between an identity and a public key, so a substituted key like D’s fails verification rather than being silently accepted.

Aside

This is a different manifestation of person-in-the-middle from the one already covered on the Diffie-Hellman page: there, the attacker runs two independent key exchanges; here, the attacker substitutes its own public key into a single one-directional key handoff. Both fail for the same underlying reason: neither protocol authenticates who a public value actually came from.

Mechanism

§3.2 fixes this by assuming A and B have already exchanged public keys reliably (by one of the schemes covered on the next page), then layering in nonces for freshness and mutual proof of participation.

A initiates. A encrypts $ID_A$ and a nonce $N_1$ with B’s public key: $E(PU_b, [ID_A \Vert N_1])$ .
B replies. Only B could have decrypted message 1 to read $N_1$ , so B echoes $N_1$ back alongside a new nonce $N_2$ , encrypted with A’s public key: $E(PU_a, [N_1 \Vert N_2])$ . Seeing its own $N_1$ come back assures A that the reply really is from B.
A returns $N_2$ . Encrypted with B’s public key. Only whoever decrypted message 2 could have recovered $N_2$ , so this assures B that its correspondent is A.
A sends the secret key. A selects $K_s$ and sends $M = E(PU_b, E(PR_a, K_s))$ .
B recovers it. B computes $D(PU_a, D(PR_b, M))$ , undoing the two layers in reverse.

Formula

Confidentiality and authentication of a secret key

M = E(PU_b, E(PR_a, K_s))

$K_s$: the secret key A wants to give B
$PR_a$: A's private key: encrypting with it is what only A could have produced
$PU_b$: B's public key: encrypting with it means only B can read the result

B recovers K_s with D(PU_a, D(PR_b, M)): undo B's layer first with B's own private key, then undo A's layer with A's public key.

Exam detail

The double encryption in message 4 is the exam’s favourite detail on this page: encrypting with $PR_a$ first is what gives authentication (only A holds $PR_a$ ), and encrypting the result again with $PU_b$ is what gives confidentiality (only B holds $PR_b$ to undo it). Get the order and the reasoning both stated, not just the formula.

Mechanism

Because of the inefficiency of public-key cryptosystems on large blocks, they are used here only to move $K_s$ itself; the fast symmetric cipher does the actual data encryption once $K_s$ is in place. A separate practical option, the notes’ hybrid scheme, keeps a KDC brokering session keys under shared master keys exactly as in the previous topic, but distributes the master keys themselves using public-key encryption rather than physical delivery. IBM mainframes used this approach; it pays off specifically when one KDC has to serve a widely distributed set of users.

Recall

The naive public-key distribution scheme has no way to check who a public key really belongs to, which is exactly what D exploits.
Once D has relayed $K_s$ to A, it can drop to pure eavesdropping; the scheme offers no protection against an active attacker at all.
§3.2’s fix layers two nonces (mutual freshness) and a double encryption, $E(PU_b, E(PR_a, K_s))$ , giving both confidentiality and authentication in one message.
The hybrid scheme keeps the KDC for session keys but distributes master keys with public-key encryption.

Source

Week 7 Notes PDF