Diffie-Hellman.md

# 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](Sifrovani-zaklady) a navazuje na [veřejný a soukromý klíč](Verejny-a-soukromy-klic). ## Nejdřív intuice: míchání barev Klasické přirovnání, které funguje překvapivě přesně: 1. Alice a Bob se veřejně dohodnou na společné barvě — třeba **žluté**. Odposlouchávající ji vidí.2. Každý si potají vybere **tajnou barvu**. Alice červenou, Bob modrou. Nikomu je neřeknou.3. 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ě.4. 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. ```mermaidsequenceDiagram    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: ```bashpython3 -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](Sifrovani-zaklady#kdf-jak-se-z-jednoho-tajemství-udělá-víc-klíčů), 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](Verejny-a-soukromy-klic#proč-jsou-křivky-lepší). ### 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](TLS-handshake), [SSH](SSH), [WireGuard](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](TLS-a-HTTPS#verze-a-šifry) 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: ```mermaidsequenceDiagram    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](TLS-a-HTTPS), ten ověří [CA](Certifikaty-a-Lets-Encrypt) || **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í. ```bashopenssl 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](TLS-handshake). ### 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. ```bashssh -Q kex                       # co tvůj klient umíssh -vv server 2>&1 | grep -i "kex:"# kex: algorithm: mlkem768x25519-sha256``` Viz [SSH do hloubky](SSH#výměna-klíčů). ### 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](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](Postkvantova-kryptografie). ## 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íč](Verejny-a-soukromy-klic)** — druhá polovina asymetrické kryptografie- **[TLS handshake krok za krokem](TLS-handshake)** — DH zasazený do skutečného protokolu- **[SSH do hloubky](SSH)** — totéž z druhé strany- **[WireGuard](WireGuard)** — čtyřnásobný DH bez certifikátů- **[Postkvantová kryptografie](Postkvantova-kryptografie)** — co přijde po Diffie-Hellmanovi