Diffie-Hellman uitgelegd: een geheim afspreken in het open
Elke HTTPS-verbinding begint met een raar probleem. Je laptop en een server die elkaar nooit eerder spraken, moeten een geheime sleutel afspreken, terwijl iedereen op het netwerk elk bericht kan lezen. Diffie-Hellman is de sleuteluitwisseling die dat oplost. Whitfield Diffie en Martin Hellman beschreven het idee in november 1976 in "New directions in cryptography", in IEEE Transactions on Information Theory. Het zit nog steeds in vrijwel elke TLS 1.3-handshake en in WireGuard.
Hieronder bouw ik het stap voor stap op. Eerst met verf, daarna met getallen die je op een bierviltje kunt narekenen, en dan met de echte getallen van 2048 bits en de kromme X25519. Onderweg meet ik hoe snel een afluisteraar het geheim met proberen terugvindt, en waarom dat bij echte sleutels niet lukt.
Het probleem: afspreken waar iedereen meeleest
Versleutelen met een gedeelde sleutel is snel; in het artikel over WireGuard haalde ChaCha20-Poly1305 honderden megabytes per seconde. Maar dan moeten beide kanten die sleutel wel al hebben. Stuur je hem gewoon over de lijn, dan heeft de afluisteraar hem ook.
Diffie-Hellman draait het om. Beide kanten sturen elkaar iets openbaars, en ieder rekent daar met een eigen geheim op verder. De uitkomst is aan beide kanten gelijk, terwijl dat resultaat zelf nooit over de lijn gaat.
Eerst met verf
De bekende uitleg gaat met verf. Alice en Bob spreken openlijk een basiskleur af, zeg geel. Ieder kiest daarnaast een geheime kleur: Alice rood, Bob blauw. Alice mengt geel met rood en stuurt dat oranje naar Bob. Bob mengt geel met blauw en stuurt groen terug.
Nu voegt Alice haar rood toe aan Bobs groen, en Bob zijn blauw aan Alices oranje. Beiden hebben dan geel plus rood plus blauw, dezelfde bruine tint. Eve, die meekijkt, heeft geel, oranje en groen gezien. Om het bruin te maken moet ze het rood uit het oranje halen, en verf ontmengen gaat niet.
De vergelijking hapert op één punt: verf ontmengen is onmogelijk, wiskundig terugrekenen is alleen onpraktisch veel werk.
Dezelfde truc met kleine getallen
In de wiskundige versie is mengen "machtsverheffen modulo een priemgetal". Modulo betekent: deel en houd de rest over, zoals een klok na 12 weer bij 1 begint. Neem het priemgetal p = 23 en het grondgetal g = 5. Die twee zijn openbaar.
- Alice kiest geheim a = 6 en stuurt A = 5⁶ mod 23. Dat is 15625 mod 23 = 8.
- Bob kiest geheim b = 15 en stuurt B = 5¹⁵ mod 23 = 19.
- Alice rekent 19⁶ mod 23 = 2.
- Bob rekent 8¹⁵ mod 23 = 2.
Het werkt omdat (gᵇ)ᵃ en (gᵃ)ᵇ allebei gᵃᵇ zijn. Eve ziet 23, 5, 8 en 19 voorbijkomen. Om het geheim te vinden, moet ze uit 8 terugrekenen welke macht van 5 dat geeft. Dat heet het discrete-logaritmeprobleem.
Ook de keuze van g doet ertoe. Ik liet Python alle machten van 5 modulo 23 uitrekenen: 5, 2, 10, 4, 20, 8, 17 en zo verder. Alle 22 mogelijke waarden kwamen precies één keer langs. Een grondgetal dat maar een paar waarden raakt, geeft Eve veel minder te proberen.
Hoe lang proberen duurt
Bij p = 23 vond mijn script a = 6 na zes pogingen. Interessanter is wat er gebeurt als p groeit. Ik nam priemgetallen van 16 tot 28 bits, liet Python een willekeurig geheim kiezen en daarna stap voor stap zoeken, op een zuinige Celeron J3455:
| Grootte van p | Stappen tot het geheim | Tijd |
|---|---|---|
| 16 bits | 8.807 | 0,004 s |
| 20 bits | 66.174 | 0,031 s |
| 24 bits | 4.279.350 | 2,1 s |
| 28 bits | 31.653.562 | 15,9 s |
Dat is ongeveer twee miljoen pogingen per seconde. Elke extra bit verdubbelt het aantal mogelijkheden, dus bij 2048 bits is botweg proberen hopeloos.
Toch is proberen de domste aanval. Er bestaan veel slimmere algoritmen voor de discrete logaritme, en daarom moet p bij klassiek Diffie-Hellman zo enorm zijn. RFC 7919, dat de groepen voor TLS vastlegt, schat de sterkte van de 2048-bits groep ffdhe2048 op 103 bits. Dat wil zeggen: ongeveer zo moeilijk als een symmetrische sleutel van 103 bits raden.
De echte getallen
Een echte Diffie-Hellman-groep is gewoon een afgesproken p en g. RFC 3526 beschrijft bijvoorbeeld groep 14, een priemgetal van 2048 bits met generator 2. Ik controleerde het getal uit de RFC: het telt 617 cijfers. Dat iedereen dezelfde p gebruikt, is geen probleem: het geheim zit in de exponent.
Voor de verdediger is het rekenwerk klein. Machtsverheffen gaat met herhaald kwadrateren, dus met een paar duizend vermenigvuldigingen in plaats van een getal met honderden cijfers aan stappen. openssl speed haalde op dezelfde Celeron 786 complete sleutelafleidingen per seconde met ffdh2048. Dat is ruim een milliseconde per keer.
Elliptische krommen: X25519
RFC 8446 laat TLS 1.3 naast zulke groepen ook elliptische krommen gebruiken, zoals x25519 en secp256r1. Daar reken je niet met machten modulo een groot priemgetal, maar met punten op een kromme. Het idee blijft hetzelfde: een openbaar beginpunt, een geheim getal, en een bewerking die makkelijk heen en lastig terug is. Volgens RFC 7748 kiest Alice bij X25519 32 willekeurige bytes als geheim en stuurt ze X25519(a, 9), waarbij 9 de coördinaat van het beginpunt is. Bob doet hetzelfde, en beiden komen uit op X25519(a, X25519(b, 9)).
Het grote voordeel is de grootte. Een X25519-sleutel is 32 bytes en hoort volgens de RFC bij ongeveer 128 bits sterkte. Een ffdh2048-sleutel is 256 bytes, want TLS 1.3 vult de waarde aan tot de lengte van p, en haalt volgens RFC 7919 maar 103 bits. Sneller is X25519 ook: openssl speed gaf 7.895 sleutelafleidingen per seconde, tien keer zoveel als bij ffdh2048.
Wie wallieweb.nl opent met de OpenSSL 3.0 op deze machine, krijgt Server Temp Key: X25519, 253 bits. Een recentere OpenSSL spreekt er de hybride groep X25519MLKEM768 mee af, zoals in het artikel over de eerste byte stond. ML-KEM is volgens NIST (FIPS 203) bedoeld om ook bestand te zijn tegen een quantumcomputer, en dezelfde norm noemt de huidige Diffie-Hellman-methoden uit SP 800-56A kwetsbaar voor een voldoende krachtige quantumcomputer.
Wat Diffie-Hellman niet oplost
Diffie-Hellman bewijst niet met wie je praat. Zit Eve niet alleen mee te kijken maar ook tussen Alice en Bob in, dan doet ze met elk van beiden een eigen uitwisseling. Alice spreekt een sleutel af met Eve, Bob ook, en Eve leest alles en geeft het door. RFC 8446 waarschuwt daar expliciet voor: een TLS-verbinding zonder controle van de sleutel van de server is kwetsbaar voor man-in-the-middle-aanvallen.
Daarom zit er in TLS 1.3 naast de key_share ook een certificaat en een handtekening (CertificateVerify) over de handshake. Hoe je browser beslist of dat certificaat te vertrouwen is, lees je in hoe je browser een certificaat vertrouwt.
Omgekeerd levert Diffie-Hellman iets wat een certificaat niet kan: forward secrecy. Bij elke verbinding worden nieuwe, tijdelijke geheimen gekozen en daarna weggegooid. RFC 8446 beschrijft het zo: raakt de langetermijnsleutel van de server later op straat, dan blijven eerdere sessiesleutels veilig, zolang die sessiesleutels zelf zijn gewist.
Zelf proberen
Het voorbeeld met kleine getallen past in een paar regels Python:
p, g = 23, 5
a, b = 6, 15
A, B = pow(g, a, p), pow(g, b, p)
print("Alice stuurt", A, "Bob stuurt", B)
print("Alice rekent", pow(B, a, p), "Bob rekent", pow(A, b, p))
Alice stuurt 8 Bob stuurt 19
Alice rekent 2 Bob rekent 2
Met de Python-bibliotheek cryptography doe je hetzelfde met X25519:
from cryptography.hazmat.primitives.asymmetric.x25519 import X25519PrivateKey
alice, bob = X25519PrivateKey.generate(), X25519PrivateKey.generate()
k1 = alice.exchange(bob.public_key())
k2 = bob.exchange(alice.public_key())
print(k1.hex(), k1 == k2)
e7d4d2a2eb3ed9a6d41b9b7bbaf6e2210ea4ca83048d6c6cd820d3b64c0bee7f True
Welke uitwisseling een site gebruikt, zie je met OpenSSL. Met -groups dwing je een andere groep af:
echo | openssl s_client -connect wallieweb.nl:443 2>/dev/null | grep "Temp Key"
echo | openssl s_client -connect wallieweb.nl:443 -groups ffdhe2048 2>/dev/null | grep "Temp Key"
Server Temp Key: X25519, 253 bits
Server Temp Key: DH, 2048 bits
De snelheid op je eigen machine meet je met openssl speed ffdh2048 ecdhx25519.
Tot slot
Ik had verwacht dat mijn eigen server de oude 2048-bits groep zou weigeren. Dat doet hij niet: met -groups ffdhe2048 kreeg ik gewoon een TLS 1.3-verbinding, met een sleutel die acht keer zo groot is en tien keer zoveel rekenwerk kost als X25519. Wat me ook bijbleef, is de tabel met het proberen. Bij 28 bits was mijn Celeron na zestien seconden al klaar, en toch is dat de enige stap die tussen een afluisteraar en de sleutel staat. Het hele bouwwerk rust op het verschil tussen twee kanten van dezelfde rekensom.