Diffie–Hellman: agreeing on a secret with no secret

The first published public-key algorithm, and it encrypts nothing

Diffie–Hellman was the first public-key algorithm to appear in print, and its purpose is narrow and exact: two parties who have never met derive a shared secret over a channel an eavesdropper can read in full. It is limited to key exchange. It does not encrypt messages, it does not sign anything, and it produces no ciphertext. What it produces is a number both parties now hold and nobody else does — which is then handed to a symmetric cipher like AES to do the actual work.

Its security rests on the discrete logarithm problem. Fix a prime q and a primitive root α of q — a number whose successive powers ${\alpha }^1,{\alpha }^2,\dots ,{\alpha }^{q-1}$ run through every integer from 1 to $q-1$, each exactly once, in some permutation. Then computing $Y={\alpha }^X\mathrm{mod}q$ from X is easy (square-and-multiply, from L5.2), while recovering X from Y — the discrete logarithm — is believed to be infeasible for a large enough q. Note that "primitive root" is a real, checkable property, not decoration: an α that generates only part of the group shrinks the search space the attacker faces.

Worked example — our exchange, over q = 541

The public parameters, known to everyone including the attacker, are the prime q = 541 and α = 2.

First, confirm 2 really is a primitive root of 541. The group has order $540=2^2\cdot 3^3\cdot 5$, so it is enough to check that 2 raised to $540/2$, $540/3$ and $540/5$ is not 1: $2^{270}\mathrm{mod}541=540$, $2^{180}\mathrm{mod}541=129$, $2^{108}\mathrm{mod}541=48$. None is 1, so 2 has full order 540 and is a primitive root. Never take a generator on trust.

Alice picks a private value $X_A=97$, keeps it, and computes her public value $Y_A=2^{97}\mathrm{mod}541=410$.

Bob picks $X_B=233$ and computes $Y_B=2^{233}\mathrm{mod}541=442$.

They swap 410 and 442 in the clear.

Alice computes $K=Y_B^{X_A}\mathrm{mod}q=442^{97}\mathrm{mod}541=357$. Bob computes $K=Y_A^{X_B}\mathrm{mod}q=410^{233}\mathrm{mod}541=357$.

They agree, and the reason is one line of algebra: both are computing ${\alpha }^{X_A{X}_B}\mathrm{mod}q$, just with the exponents applied in opposite orders. The key 357 was never transmitted. An eavesdropper who logged the entire conversation holds q, α, 410 and 442, and to get 357 must take a discrete logarithm — recover 97 from 410, or 233 from 442. At 541 that is trivial by brute force; at 2048 bits it is the security of the internet.

Worked example — Darth in the middle

Now put an active attacker on the wire. Darth picks his own private value $X_D=157$ and computes $Y_D=2^{157}\mathrm{mod}541=199$.

Alice sends 410 toward Bob. Darth intercepts it and forwards 199 instead. Bob sends 442 toward Alice; Darth intercepts it and forwards 199 again. Now:

• Alice computes $199^{97}\mathrm{mod}541=96$ and believes she shares that key with Bob.
• Bob computes $199^{233}\mathrm{mod}541=132$ and believes he shares that key with Alice.
• Darth computes $410^{157}\mathrm{mod}541=96$ and $442^{157}\mathrm{mod}541=132$ — both keys.

Alice encrypts under 96. Darth decrypts it, reads it, alters it if he likes, re-encrypts under 132 and passes it to Bob, who decrypts it successfully and sees nothing wrong. Both endpoints believe they have a secure channel. Both are right that the channel is encrypted; both are wrong about who is on the other end.

The diagnosis, and the fix

The attack does not break the mathematics. The discrete logarithm was never solved; Darth never needed 97 or 233. What failed is that the protocol authenticates nothing — nothing in a bare Diffie–Hellman message says who produced the public value, so any value can be swapped for any other. This is a protocol-authentication failure, not a network-layer one, and moving the exchange to a "more secure network" fixes nothing.

The fix is to bind each public value to an identity: sign the Diffie–Hellman parameters with a long-lived key whose ownership is vouched for by a certificate. That is exactly what TLS does, and it is why a server certificate is what actually stops a man in the middle during a TLS key exchange. Note also that the static variant — both parties using long-term public values from a central directory — adds authentication but still does not stop replay, because nothing in it is fresh.