Diffie-Hellman: výměna klíčů

Máš linku, kterou někdo odposlouchává. Vidí každý bajt, který po ní pošleš, oběma směry. Nikdy předtím jsi s protistranou nemluvil, nemáte žádné společné heslo.

Domluvte se na tajném klíči.

Zní to jako trik s podmínkou, která se nedá splnit. Whitfield Diffie a Martin Hellman ji v roce 1976 splnili a je to pravděpodobně nejdůležitější jednotlivý nápad v celé praktické kryptografii. Bez něj by HTTPS nemohlo existovat v podobě, jakou znáš — každý web by s tebou musel předem sdílet heslo.

Předpokládá to stavební kameny a navazuje na veřejný a soukromý klíč.

Nejdřív intuice: míchání barev

Klasické přirovnání, které funguje překvapivě přesně:

Alice a Bob se veřejně dohodnou na společné barvě — třeba žluté. Odposlouchávající ji vidí.
Každý si potají vybere tajnou barvu. Alice červenou, Bob modrou. Nikomu je neřeknou.
Každý smíchá žlutou se svou tajnou a výsledek pošle veřejně. Alice pošle oranžovou, Bob zelenou. Odposlouchávající vidí obě.
Alice přimíchá do Bobovy zelené svou červenou. Bob přimíchá do Aliciny oranžové svou modrou. Oba dostanou stejnou hnědou — žlutá + červená + modrá.

Odposlouchávající zná žlutou, oranžovou a zelenou. Hnědou z toho nedostane, protože z namíchané barvy nejde vytáhnout, co v ní bylo. Mixování je snadné, rozmixování ne.

Tohle přirovnání zachycuje úplně všechno podstatné. Zbytek stránky jen ukazuje, co je tou barvou doopravdy.

Ta samá věc s čísly

Míchání barev je ve skutečnosti umocňování ve zbytkové aritmetice. Klíčová vlastnost, na které to celé stojí:

(g^a)^b  =  g^(a·b)  =  (g^b)^a

Nezáleží na pořadí. Když Alice umocní Bobovo číslo na svůj tajný exponent a Bob Alicino na svůj, dostanou totéž. A veřejnou část přitom nikdo nemusí umět rozložit zpátky.

Zbytek po dělení (mod p) je tam proto, aby se čísla nerozrostla do nekonečna a hlavně aby zmizela jakákoliv souvislost mezi velikostí vstupu a výstupu.

Postup

Alice a Bob se veřejně dohodnou na dvou číslech: prvočíslu p a generátoru g. Ani jedno není tajné, obojí bývá pevně dané standardem.

sequenceDiagram
    participant A as Alice
    participant E as Odposlech
    participant B as Bob
    Note over A,B: veřejně známé: p, g
    A->>A: zvolí tajné a
    B->>B: zvolí tajné b
    A->>B: A = g^a mod p
    Note over E: vidí A
    B->>A: B = g^b mod p
    Note over E: vidí B
    A->>A: s = B^a mod p
    B->>B: s = A^b mod p
    Note over A,B: obě strany mají totéž s
    Note over E: zná p, g, A, B — a nic z toho nepomůže

Spočítej si to

S malými čísly, aby to šlo na papír. p = 23, g = 5.

Alice si vybere tajné a = 6:

A = 5^6 mod 23 = 15625 mod 23 = 8

Bob si vybere tajné b = 15:

B = 5^15 mod 23 = 30517578125 mod 23 = 19

Vymění si 8 a 19. Odposlouchávající je vidí.

Alice spočítá:

s = 19^6 mod 23 = 2

Bob spočítá:

s = 8^15 mod 23 = 2

Oba mají 2, aniž by to číslo kdokoliv poslal po drátě.

Ověř si to sám:

python3 -c "p=23; g=5; a=6; b=15;
A=pow(g,a,p); B=pow(g,b,p);
print(A, B, pow(B,a,p), pow(A,b,p))"
# 8 19 2 2

V reálu je p dlouhé 2048 až 4096 bitů, a a b jsou náhodná čísla podobné velikosti a výsledek se prožene KDF, protože surové DH tajemství není rovnoměrně náhodné.

Proč to odposlech neprolomí

Útočník zná p, g, g^a mod p a g^b mod p. Chce g^(ab) mod p.

Nejpřímější cesta je z g^a mod p dopočítat a. Tomu se říká problém diskrétního logaritmu a nikdo pro něj nezná rychlý postup. U 2048bitového prvočísla by nejlepší známý algoritmus — síto v číselném tělese — potřeboval zhruba 2¹¹² operací. To není dlouhé čekání, to je mimo možnosti lidstva.

Zajímavý detail: není dokázáno, že jinak než přes diskrétní logaritmus to nejde. Předpoklad, že z g^a a g^b nikdo nedostane g^ab, se jmenuje computational Diffie-Hellman assumption a je to předpoklad, ne věta. Za padesát let se ho nepodařilo vyvrátit, což je nejsilnější důkaz, jaký máme.

Proč je to snadné dopředu a těžké zpátky

5^6 mod 23 spočítáš rychlým umocňováním na pár násobení, i když je exponent obrovský — u 2048bitového exponentu je to nízké tisíce operací.

Opačným směrem ale výsledek skáče chaoticky. Mocniny pětky modulo 23 jdou po řadě 5, 2, 10, 4, 20, 8, 17, 16, 11, 9, 22, 18, 21, 13, 19, 3, 15, 6, 7, 12, 14, 1. Žádný trend, žádná blízkost, žádné „přihořívá". Nemůžeš se k odpovědi propracovat postupně, můžeš jen zkoušet. To je celý rozdíl mezi lehkým a těžkým směrem.

Eliptické křivky: totéž, jen účinněji

Moderní protokoly nepoužívají čísla modulo prvočíslo, ale body na eliptické křivce. Princip je identický, jen se místo umocňování opakovaně sčítá bod sám se sebou:

	Klasický DH	ECDH
Veřejná dohoda	prvočíslo `p`, generátor `g`	křivka a základní bod `G`
Tajné	číslo `a`	číslo `a`
Veřejné	`g^a mod p`	bod `a·G`
Sdílené	`g^ab mod p`	bod `a·b·G`
Velikost pro 128bitovou úroveň	3072 bitů	256 bitů

Ten poslední řádek je celý důvod přechodu. Na křivkách nikdo nenašel nic lepšího než obecné metody, které trvají odmocninu z velikosti skupiny — proto stačí dvanáctkrát kratší klíče při stejné bezpečnosti. Podrobněji v asymetrické kryptografii.

X25519

Konkrétní podoba ECDH, kterou dnes v drtivé většině potkáš. Křivka Curve25519, veřejný klíč 32 bajtů, sdílené tajemství 32 bajtů, jedna operace zabere desítky mikrosekund.

Používá ji TLS 1.3, SSH, WireGuard, Signal, age, Tor.

Proč zrovna tahle:

Nemá záludné vstupy. U křivek NIST musí implementace kontrolovat, jestli přijatý bod na křivce vůbec leží — kdo to zapomene, dostane invalid curve attack a útočník mu po částech vytáhne soukromý klíč. X25519 je navržená tak, že jakýchkoliv 32 bajtů je přijatelný vstup a nic se tím nerozbije.

Sama drží konstantní čas. Používá Montgomeryho žebřík, který dělá stejnou práci bez ohledu na bity klíče. Nedá se z ní tedy měřením času nic odvodit.

Ořezává klíč automaticky. Soukromý klíč si sama upraví (nastaví a zruší konkrétní bity, tzv. clamping) tak, aby padl do bezpečné části skupiny. Programátor to nemůže pokazit.

Jediná věc, kterou implementace hlídat musí: odmítnout sdílené tajemství, které vyjde jako samé nuly. Toho lze dosáhnout posláním speciálního bodu a TLS i SSH v takovém případě spojení ukončí.

Dopředné utajení

Tohle je důvod, proč se dnes DH používá i tam, kde by šlo něco jednoduššího.

Do TLS 1.2 se běžně používal jiný postup: klient vymyslel náhodný klíč a zašifroval ho veřejným klíčem serveru z certifikátu. Fungovalo to, ale mělo zásadní vadu:

Kdo si dnes uloží zašifrovaný provoz a za pět let se dostane k soukromému klíči serveru, dešifruje zpětně všechno, co si uložil.

Klíč serveru je jeden a dlouhodobý. Uniknout může průnikem, soudním příkazem, ukradenou zálohou nebo chybou typu Heartbleed.

Diffie-Hellman to řeší tím, že si obě strany vygenerují nová a a b pro každé spojení a po jeho skončení je zahodí. Tomu se říká ephemeral — v názvech šifer to E na konci (ECDHE, DHE).

Únik dlouhodobého klíče serveru pak umožní vydávat se za server od té chvíle dál, ale nedešifruje ani jedno minulé spojení. Ta dočasná tajemství už neexistují nikde na světě.

To je dopředné utajení (forward secrecy) a TLS 1.3 ho vyžaduje povinně. Statické varianty byly z protokolu odstraněny, ne jen odrazovány.

Praktický dopad na tebe: úložiště session ticketů v nginxu dopředné utajení dokáže zrušit, když se klíče k ticketům nerotují — proto to ssl_session_tickets off.

Bez ověření je to k ničemu

Nejdůležitější odstavec na téhle stránce.

Diffie-Hellman neříká, s kým jsi se domluvil. Domluvíš se s tím, kdo ti odpoví. Když sedí uprostřed útočník, udělá DH zvlášť s tebou a zvlášť se serverem:

sequenceDiagram
    participant K as Klient
    participant M as Útočník
    participant S as Server
    K->>M: g^a
    M->>K: g^m1
    M->>S: g^m2
    S->>M: g^b
    Note over K,M: klíč 1
    Note over M,S: klíč 2
    K->>M: šifrováno klíčem 1
    M->>M: dešifruje, přečte, přešifruje
    M->>S: šifrováno klíčem 2

Obě strany mají dokonalé šifrování. Útočník vidí všechno a může to i měnit. Ani jedna strana nic nepozná, protože z pohledu matematiky proběhlo všechno správně.

Řešení je vždycky stejné: jedna strana musí svou část podepsat klíčem, který ta druhá umí ověřit nezávisle.

Protokol	Čím se to ověří
TLS	server podepíše průběh handshake klíčem z certifikátu, ten ověří CA
SSH	server podepíše výsledek výměny host keyem, ten máš v `known_hosts`
WireGuard	veřejné klíče peerů jsou napevno v konfiguraci, cizí se ignoruje
Signal	dlouhodobý identifikační klíč a bezpečnostní kód k porovnání

Tady je pak celý smysl certifikátů. Nešifrují nic. Existují výhradně proto, aby výměna klíčů měla ke komu být připoutaná.

A odtud plyne i to, proč je varování o neplatném certifikátu vážná věc a ne otravný dialog. Znamená přesně: dohoda na klíči proběhla, ale nemám čím ověřit, s kým.

Parametry a jak se to lámalo v praxi

Klasický DH nefunguje s libovolnými čísly a historie na to bohatě doplatila.

Slabé prvočíslo. Když má p−1 jen malé dělitele, dá se úloha rozložit na spoustu malých a vyřešit. Proto se používají safe primes, kde je (p−1)/2 také prvočíslo.

Logjam (2015). Servery pořád podporovaly exportní 512bitové DH z devadesátých let. Útočník je uprostřed dokázal donutit ho použít a pak parametry během minut zlomil. Součástí téhož výzkumu bylo zjištění, že 8,4 % z milionu nejnavštěvovanějších HTTPS serverů sdílelo jeden jediný 1024bitový modul — velká část práce na jeho zlomení se dá udělat jednou dopředu a pak už jednotlivá spojení padají rychle. To je práce pro státní rozpočet, ale ne pro sci-fi.

Reakce. RFC 7919 zavedlo pevně pojmenované skupiny (ffdhe2048 až ffdhe8192) a TLS 1.3 zakázalo vlastní parametry úplně. Dnes si nemůžeš vybrat špatně, protože si nemůžeš vybrat.

Praktický důsledek pro tebe: pokud v konfiguraci nginxu ještě máš ssl_dhparam, je to relikt z doby TLS 1.2. U čistého TLS 1.3 nedělá nic. Když ho tam potřebuješ kvůli starším klientům, ať má aspoň 2048 bitů a negeneruj si vlastní — pojmenovaná skupina je stejně bezpečná a nedá se pokazit.

Kde to uvidíš

TLS 1.3

Klient hádá dopředu. Do prvního paketu rovnou přiloží key_share — svou veřejnou část pro skupinu, kterou předpokládá (dnes prakticky vždy X25519). Server odpoví svou částí a tím je výměna hotová během jednoho kola.

Kdyby klient hádal špatně, server pošle HelloRetryRequest s tím, kterou skupinu chce, a stojí to jedno kolo navíc. Proto je dobré nechat výchozí nastavení.

openssl s_client -connect example.cz:443 -tls1_3 </dev/null 2>&1 | grep -iE "negotiated|cipher"
# Negotiated TLS1.3 group: X25519MLKEM768
# New, TLSv1.3, Cipher is TLS_AES_256_GCM_SHA384

Podrobný rozbor je na TLS handshake krok za krokem.

SSH

Výměna probíhá hned po pozdravu, ještě před tím, než server ví, jaký uživatel se hlásí. Výsledek se hashuje do exchange hash a server ho podepíše svým host keyem.

ssh -Q kex                       # co tvůj klient umí
ssh -vv server 2>&1 | grep -i "kex:"
# kex: algorithm: mlkem768x25519-sha256

Viz SSH do hloubky.

WireGuard

Nejzajímavější případ. WireGuard nedělá jednu výměnu, ale čtyři DH operace v jednom handshake (návrh Noise IK). Kombinuje dočasné klíče s dlouhodobými tak, že jedním postupem získá zároveň dopředné utajení i vzájemné ověření obou stran — žádné certifikáty, žádné podpisy.

Přidává k tomu vlastnost, kterou TLS nemá: neznámému odesílateli neodpoví vůbec nic. Kdo nezná tvůj veřejný klíč, nedostane od WireGuardu ani jeden bajt a z internetu ten port vypadá jako zavřený. Viz WireGuard.

Signal a šifrované chaty

Kde se druhá strana nemusí připojit ve stejnou chvíli, se používá X3DH: klíče se dopředu nahrají na server a příjemce provede svou půlku výměny až později. Na to navazuje double ratchet, který odvozuje nový klíč pro každou jednotlivou zprávu — únik jednoho klíče pak neodhalí ani zprávy předchozí, ani ty následující.

Postkvantový posun

Shorův algoritmus na dostatečně velkém kvantovém počítači řeší diskrétní logaritmus efektivně. To ukončí Diffie-Hellmana ve všech jeho podobách včetně eliptických křivek.

Takový počítač neexistuje a nikdo neví, kdy bude. Problém je ale jinde: provoz odposlechnutý dnes se dá dešifrovat později. Kdo si dnes ukládá šifrovaná data, počká si. Proto se výměna klíčů migruje jako první, ještě než je hrozba reálná.

Řešením je hybridní režim: klasický X25519 se provede zároveň s postkvantovým mechanismem a obě tajemství se sloučí do jednoho klíče. Pro prolomení musí útočník zlomit obě části.

X25519MLKEM768  =  X25519 (klasické)  +  ML-KEM-768 (postkvantové)

Tohle už není budoucnost. Chrome a Firefox to zapnuly ve výchozím nastavení během roku 2024 a OpenSSH má postkvantovou výměnu jako výchozí od verze 9.0. Když se dnes podíváš, co ti server vyjednal, dost pravděpodobně tam uvidíš právě tuhle kombinaci — aniž bys cokoliv nastavoval.

Detaily na postkvantové kryptografii.

Co si odnést

DH umožní dohodu na tajemství přes veřejný kanál. To je jeho jediný úkol.

Neověřuje protistranu. Bez podpisu z certifikátu nebo host keye je bezcenný.

Dočasné klíče dávají dopředné utajení. Proto ECDHE a proto TLS 1.3 nic jiného nedovolí.

Křivky vyhrály. X25519 se 32 bajty proti 3072bitovému klasickému DH.

Parametry si nevybíráš a je to dobře. Vlastní dhparam je dnes zbytečnost a v horším případě chyba.

Postkvantová varianta už běží. Nemusíš pro to nic dělat kromě aktualizací.

Kam dál

Veřejný a soukromý klíč — druhá polovina asymetrické kryptografie
TLS handshake krok za krokem — DH zasazený do skutečného protokolu
SSH do hloubky — totéž z druhé strany
WireGuard — čtyřnásobný DH bez certifikátů
Postkvantová kryptografie — co přijde po Diffie-Hellmanovi