Practical 15: Key Exchange Using Diffie-Hellman

Reading part 1

With p = 23 every step can be checked by hand, and an examiner may ask you to. 5 to the power 6 is 15,625, and 15,625 divided by 23 leaves 8. 5 to the power 15 mod 23 is 19. Then 19 to the power 6 mod 23 is 2 and 8 to the power 15 mod 23 is 2, and the two agree.

And the eavesdropper broke it in six tries. With p = 23 there are only 22 possible secrets, so trying each one until g^guess mod p matches A takes no time at all. The security is entirely in the size of p.

Reading part 2

The prime is 2048 bits, and it is not invented: it is the ffdhe2048 group of RFC 7919, one of five groups the IETF published so that a server and a client can agree on a group known to be sound instead of one a server made up. The reason that matters is worth a line in the journal: a maliciously chosen p can be one for which the discrete logarithm is easy, and a client that accepts whatever group the server offers has no way to tell.

Two details of the real exchange that the small example hides.

The shared number is not used as a key. It is a 2048-bit number with structure, and a key needs to be a fixed-size string of uniform bytes. So it is put through a hash, or properly a key derivation function, and the output is the session key. The program shows the SHA-256 step.

The private exponents here come from a fixed hash, so that the run repeats. In real use they are random, from the operating system's source, as Chapter 14's rule requires. A Diffie-Hellman private exponent that can be guessed is a session that can be read.

Reading part 3, which is the point of the practical

MU's wording is "securely exchange keys between two entities over an insecure network", and the third part is what "insecure" actually costs.

Mallory does not break any mathematics. She simply answers. Alice's A never reaches Bob; Mallory keeps it and sends Bob her own M. Bob's B never reaches Alice; Mallory keeps it and sends Alice the same M.

The output shows the result exactly: Alice's shared secret is 9, and Mallory has 9. Bob's is 10, and Mallory has 10. Alice and Bob believe they share a key with each other, and their two keys are not even the same number. Every message Alice encrypts, Mallory decrypts, reads, re-encrypts under Bob's key and forwards. Neither of them sees anything wrong.

Diffie-Hellman never claimed to say who is at the other end. It says that two ends agree on a number nobody watching can compute, and "watching" is the word doing the work: an attacker who only listens learns nothing, and an attacker who can also modify the traffic defeats it completely.

The fix is authentication. Alice signs her A with the private key of Practical 14, Bob signs his B, and Mallory cannot forge either signature, so her substituted M is rejected. That is exactly what TLS does, and it is why a TLS server needs a certificate: the certificate is what lets the client check the signature on the server's Diffie-Hellman share. Practical 17 configures one.

The same exchange with OpenSSL

$ openssl genpkey -genparam -algorithm DH -pkeyopt group:ffdhe2048 -out dhp.pem
$ openssl pkeyparam -in dhp.pem -text -noout | head -2
DH Parameters: (2048 bit)
GROUP: ffdhe2048
$ openssl genpkey -paramfile dhp.pem -out alice.pem
$ openssl genpkey -paramfile dhp.pem -out bob.pem
$ openssl pkey -in alice.pem -pubout -out alice.pub
$ openssl pkey -in bob.pem -pubout -out bob.pub
$ openssl pkeyutl -derive -inkey alice.pem -peerkey bob.pub -out alice.secret
$ openssl pkeyutl -derive -inkey bob.pem -peerkey alice.pub -out bob.secret
$ wc -c < alice.secret
256
$ cmp -s alice.secret bob.secret && echo "the two sides agree" || echo "the two sides DIFFER"
the two sides agree
$ sha256sum alice.secret bob.secret | awk '{print $1}' | sort -u | wc -l
1

Two keys, two derivations, 256 bytes each and identical, and neither side ever sent the secret. That is the same exchange the Python program did, with the group named rather than written out.

The last line is there because cmp prints nothing when two files match, and a check that prints nothing is a check a reader cannot see. Counting the distinct digests of the two files gives 1, which is the same fact in a form you can write down. The digests themselves are not printed: the keys are fresh on every run, so the value would be different for every reader.

Forward secrecy, which is what this is really for

One more reason Diffie-Hellman is everywhere, and it is the one students most often miss.

Suppose a server's traffic is encrypted with a key derived from the server's long-term RSA key, and suppose an attacker has been recording that traffic for a year. If the RSA private key is later stolen, every recorded session can be decrypted, going back as far as the recordings do.

Now suppose each session used a fresh Diffie-Hellman exchange, with the exponents thrown away when the session ended. The long-term key only ever signed the exchange; it never encrypted anything. Steal it and you can impersonate the server from then on, and you still cannot read a single recorded session, because the exponents that made those keys no longer exist anywhere.

That property is forward secrecy, the ephemeral Diffie-Hellman exchange is how it is obtained, and it is why TLS 1.3 removed every key exchange that does not provide it.

Procedure

1. Choose a small prime p and a generator g and run the exchange by hand on paper first.
2. Write the program: two secret exponents, two public values, two derivations, and check the two shared numbers are equal.
3. Print exactly what an eavesdropper sees, and then break the small case by trying every exponent.
4. Repeat with a real 2048-bit group from RFC 7919 and hash the shared number into a session key.
5. Perform the man-in-the-middle attack: one attacker exponent, one substituted public value in each direction, and print all four shared numbers.
6. Record that Alice's and Bob's numbers are not equal, and that Mallory holds both.
7. Say what authentication would have prevented it.
8. Run the same exchange with openssl genpkey and openssl pkeyutl -derive, and confirm the two derived secrets are identical.

Observations

Result

The Diffie-Hellman key exchange was implemented and run three ways. With p = 23 and g = 5 both sides derived the shared secret 2 without sending it, and an eavesdropper recovered the private exponent in six attempts, which establishes that the security lies in the size of the prime. With RFC 7919's 2048-bit ffdhe2048 group both sides derived the same number and hashed it into a session key. A man-in-the-middle attack was then performed against the unauthenticated exchange: the attacker substituted her own public value in both directions and ended holding both session keys, 9 with Alice and 10 with Bob, while Alice and Bob believed they shared a key with each other and in fact held different numbers. The same exchange with OpenSSL's ffdhe2048 parameters produced 256-byte secrets that were identical on both sides.

Where marks are lost

Sending the shared secret. Nothing secret crosses the network. If your program sends it, you have not implemented Diffie-Hellman.

Using the shared number directly as a key. Hash it, or run a key derivation function over it.

A small or invented prime. Use a published group. A prime chosen by the other side can be one for which the discrete logarithm is easy.

Predictable private exponents. Use the operating system's random source.

Saying Diffie-Hellman is secure against a man in the middle. It is not, and the practical is not complete without the demonstration.

Confusing eavesdropping with modification. An attacker who only listens learns nothing; one who can alter the traffic defeats the exchange entirely.

Not explaining what fixes it. Authentication of the exchange: signatures, and in TLS, a certificate.

Reusing one exponent for every session. Then forward secrecy is lost, which is most of the reason for using this at all.

For the journal

Aim; the four steps of the exchange; why (g^a)^b equals (g^b)^a; the small-prime run with every number checked by hand; what the eavesdropper sees and what they cannot compute; the brute force on the small prime; the 2048-bit run with the group named and the session key derived by hashing; the man-in-the-middle section with all four numbers and the statement that Alice's and Bob's differ; what authentication fixes and why a TLS server needs a certificate; the OpenSSL session; forward secrecy in your own words; the observation table; the result.

Quick revision

• Agree p and g in public. Alice sends g^a mod p, Bob sends g^b mod p. Both compute g^(a*b) mod p.
• The shared secret is never sent.
• Security rests on the discrete logarithm problem: recovering a from g^a mod p.
• A small p is broken by trying every exponent. Ours fell in six tries.
• Use a published group: RFC 7919's ffdhe2048 or larger.
• Hash the shared number to get a key; do not use it raw.
• Private exponents must come from a cryptographic random source.
• Diffie-Hellman stops an eavesdropper and not a man in the middle.
• In the attack, Alice and Bob hold different keys and the attacker holds both.
• Authenticate the exchange with signatures. A TLS certificate is what makes that possible.
• Ephemeral exponents, discarded after the session, give forward secrecy.

Questions you must be able to answer

1. What crosses the network in a Diffie-Hellman exchange? The prime, the generator, and the two public values g^a mod p and g^b mod p. The secret exponents and the shared key never do.

2. Why do both sides end with the same number? Because (g^a)^b and (g^b)^a are both g^(a*b), and the modulus does not disturb that.

3. What problem must an attacker solve, and why can they not? The discrete logarithm: recovering a from g^a mod p. For a 2048-bit prime no known method is feasible. For p = 23 it took six tries.

4. Why use a published group rather than your own prime? Because a prime can be chosen so that the discrete logarithm in it is easy, and a client accepting whatever the server offers cannot tell. RFC 7919 publishes groups everyone can check.

5. Why is the shared number hashed before it is used? Because it is a large structured number, not a uniform key of the right length. A hash or a key derivation function turns it into one.

6. Describe the man-in-the-middle attack. The attacker intercepts both public values and substitutes her own in each direction. She then shares one key with each party, reads and rewrites everything, and neither party can detect it. In this run Alice held 9, Bob held 10, and the attacker held both.

7. Is that a flaw in the mathematics? No. Diffie-Hellman guarantees that two ends agree on a number no watcher can compute. It never claimed to identify who is at the other end.

8. What fixes it? Authenticating the exchange: each side signs its public value with a private key the other can verify. In TLS the server's certificate is what lets the client verify that signature.

9. What is forward secrecy, and how does Diffie-Hellman give it? That a session recorded today cannot be decrypted even if the long-term key is stolen tomorrow. Using a fresh exchange per session, and discarding the exponents afterwards, means the material that made the session key no longer exists.

10. Your two sides derive different numbers. Name the two likeliest causes. Someone is between you substituting values, which is the attack above; or one side has used the wrong peer's public value, or a different p or g. Check the parameters first, then suspect the network.