Věštíme, co dokáže NSA rozlousknout

Logjam se stal po dlouhé době prvním praktickým útokem na Diffie-Hellmanův algoritmus výměny klíčů. Výzkumníci začali hledat i jiné způsoby než slabé exportní parametry k prolomení Diffie-Hellmana. NSA navíc nedávno přilila do spekulací tlakem na přechod od eliptických křivek k post-kvantové kryptografii.

Logjam útok předznamenal nový cíl pro budoucí útoky na šifrované spojení: Diffie-Hellmanovu výměnu klíčů. Původní útok byl zaměřen na pozůstatky „kryptografických válek“ z 90. let. Tzv. exportní Diffie-Hellmanovy parametry (DHE_EXPORT ciphersuites) byly jednoduše tak malé (512-bit), že se pro ně dnes jednoduše spočítá diskrétní logaritmus Pollard rho nebo „baby-step giant-step“ metodou a tudíž odvodí tajné vyměněné klíče.

Malé Diffie-Hellman grupy (dále jen DH grupy) byly v novějších browserech zakázané, nepřijímají prvočísla menší než 1024-bit jako parametr DH grupy. Občas to má vtipné důsledky, kdy si i sami kryptologové, kteří toto způsobili, zanadávají, že se na některé weby nedostanou.

Stav Diffie-Hellmana v „divočině“

Nová hrozba od útočníka na státní úrovni, která byla naznačena už v původním Logjam paperu, spočívá v tom, že se běžně používají stejná prvočísla a DH grupy v SSH, TLS a VPN protokolech. To samo o sobě není až takový problém, větší problém bývá opačný – když si software začne generovat grupy a protistrana si neověřuje, že dostala prvočíslo a spokojí se třeba i s „prvočíslem“ 15. Záležitost spočívá v tom, že kdysi se v komunikačním šumu mezi kryptografy a softwarovými inženýry ztratila informace, že útočník dokáže udělat jedno obrovské předpočítání pro jedny konkrétní DH parametry – pokud není DH grupa příliš velká.

Velmi běžnou grupou je například Oakley group 2, 1024bitová DH grupa. Ve výchozím stavu ji používá např. SSH; pokud ji chcete vypnout, musíte v nastavení serveru, resp. klienta odstranit diffie-hellman-group1-sha1 z KexAlgorithms (nenechte se zmást názvem „group1“, odpovídá Oakley group 2). Doporučované je nechat jen curve25519-sha256@libssh.org, to ale nemusí být vždy praktické, protože je implementována jen v novějších SSH klientech a serverech. Bezpečná je taky 2048bitová DH grupa diffie-hellman-group14-sha1. Někdo by mohl namítat něco proti SHA-1, ale v tomto případě by museli generovat kolize pro každou výměnu klíčů.

Autoři weakdh.org uvádějí nastavení i pro další protokoly než SSH. Pro OpenVPN je možné použít vlastní vygenerovanou DH grupu pomocí optionu –dh, vygenerovat je nejprve s:

openssl dhparam -out dh2048.pem 2048

Pro *SWAN ipsec.conf se použije parametr ike=aes128-sha1-modp2048.

Analýza Diffie-Hellmana hlouběji – miskonfigurace serverů

Autoři Logjamu pokračovali v scanování používaných DH grup v nové práci. „Exportní“ DH grupy velikosti 512-bit stále používá 8,4 % HTTPS serverů z top Alexa 1M.

Asi příliš nepřekvapí, když řeknu, že některých případech parametr p DH grupy, který má být prvočíslo, byl ve skutečnosti složené číslo – přesně v 9 případech. Stalo se to už i jiným protokolům.

Pro DH grupu nestačí, že je modulem nějaké prvočíslo p, toto prvočíslo p musí mít navíc vlastnost, žep=2q+1 pro nějaké velké prvočíslo q. Taková prvočísla p se nazývají bezpečná („safe prime“). Důvodem je, že algoritmy Pollard rho a baby-step giant-step vyžadují sqrt(q) kroků na vypočtení diskrétního logaritmu v libovolné (pod)grupě řádu q. Pokud by p bylo jiného tvaru než 2q+1, tak by lámání DH mohlo být mnohem rychlejší.

Z cca 70000 prvočísel viděných jako DH parametry mělo 4800 prvočísel q složené. V tomto případě lze Pohlig-Helmmanovou metodou mnohem jednodušeji zjistit bity tajných exponentů používaných při DH výměně klíčů.

Další zvláštní miskonfigurací nebo programátorskou chybou je prohození řádu grupy s generátorem – týkalo se cca 5700 serverů. Toto je způsobeno ASN.1 reprezentací – u DH se používá (p, g) a u DSA se používá (p, q, g). Zde je vidět, proč mohla podobnost reprezentace někoho zmást. Takováto chyba ale způsobuje, že „uniká“ až polovina bitů exponentu.

To bychom měli konfigurační chyby, které útočník typu NSA může použít. Bez nich musí použít hrubé lámání DH, co do velikosti 1024-bit DH grupy to jde s předpočtem, když je zároveň jedná o jednu ze „známých“ DH grup.

Není pravda, že je 66 % VPN zranitelných

Publikovaným výsledkem scanování IPsec VPN bylo, že 66 % preferuje 1024bitovou Oakley group 2 (nazvanou modp1024 v *swan nastavení), pro kterou by šlo udělat předvýpočet a lámat data z pasivního odposlechu. Jak ale ukazuje Paul Wouters, údaj 66 % je velmi zkreslený, a to kvůli použité metodice. Jednak byl scan jen na vzorku 1 % IPv4 prostoru, ale hlavně, správně nakonfigurované VPN by se s nimi vůbec nebavily a spadly by pod „NO-PROPOSAL-CHOSEN“. Autoři takto nevědomky vyloučili všechny freeswan/openswan/libreswan servery, které měly DH grupu modp1024 zakázanou.

Anebo by se nejprve tvářily, že podporují Oakley group 2, ale dále by odmítly vytvořit IKE spojení s modp1024.

Není to až tak špatné, jak to ze začátku vypadalo, ale stejně existovalo dost serverů se slabou 768-bitovou Oakley group 1, což by se mělo opravit.

Osud standardu „Suite B“ – nový nepřítel je kvantový počítač

Lámání Diffie-Hellmannovy výměny klíčů je celkem zřetelně popsáno a není příliš sporu, že by to tak mohlo fungovat. Zajímavější konspirační teorie se může rozvíjet z práce dvou známých kryptologů N. Koblitze a J. Menezese A Riddle wrapped in an Enigma. Práce pojednává o tom, proč se NSA vyplašila a najednou přestala doporučovat kryptografii standardu NSA Suite B a naopak tlačí na přechod od něj na post-kvantovou kryptografii.

Standard Suite B byl de facto prvním veřejným standardem neobsahujícím tajné algoritmy, které byly doporučovány na šifrování dat úrovně „secret“ a „top secret“. V 90. letech tento standard již obsahoval eliptické křivky, což byla na tu dobu celkem novinka. Naproti tomu, DSA, RSA a Diffie-Hellman nikdy nebyly určeny pro stupeň „top secret“. Ze začátku nebyly v Suite B vůbec, objevily se až v roku 2010.

Otázka do pranice zní: proč NSA tlačí najednou na odchod od eliptických křivek a chce začít nějak vážně řešit kvantové počítače?

Bezpečnost eliptických křivek je založena na problému ECDLP – diskrétní logaritmus nad eliptickou křivkou. Obecně křivka řádu n vyžaduje sqrt(n) kroků na vypočtení ECDLP. Tedy například 256bitová P-256 by měla mít 128-bitovou úroveň bezpečnosti.

První pozorování na změnách Suite B je, že NSA rovnou odstranila ze standardu křivku P-256 a nejmenší doporučovaná křivka v přechodném období je 384bitová P-384. Čímž říká, že 128bitová bezpečnost P-256 již nepostačuje. Nebo jinak, že možná ví něco, co snižuje bezpečnost z 128 bitů níže.

Této hypotéze odporuje fakt, že v Snowdenových materiálech nebyl ani ťuk o nalomení ECC.

Mysteriózní fakt je, že kryptologové se zatím vůbec neshodli na tom, který že to post-kvantový algoritmus vůbec použít. Natož jaké parametry by měl mít. To je zatím u některých parametrů algoritmu jako NTRU víc věštění než věda.

Mají eliptické křivky od NSA zadní vrátka?

Po debaklu s Dual EC DRBG, kterému NSA dala zadní vrátka, je otázka existence zadních vrátek v eliptických křivkách doporučovaných od NSA často opakována. Především u křivek, které mají parametry vygenerovány „dokazatelně náhodným“ způsobem (například P-256).

Od 90. let jsou známy celé rodiny slabých eliptických křivek, např. supersingulární křivky a křivky nad tělesy s charakteristikou 2. Těmto se dá ale celkem jednoduše vyhnout. Abychom se vyhnuli ještě neznámým rodinám slabých křivek, doporučila komise ANSI X9F1 výběr parametrů „dokazatelně náhodně“. Ten proces v zásadě znamená opakované hashování určitého seedu. Co se ale ovšem nikde nedozvíme, je to, jak byl ten seed vlastně vybrán.

Původní logika byla, že vzhledem k jednosměrnosti SHA-1 by bylo výpočetně nemožné vybrat specifickou křivku a pak k ní invertovat SHA-1, aby se našel ten správný seed. Ovšem další možnost je, že NSA věděla, že existuje velká rodina křivek, které jsou slabé a prostě zkoušela různé seedy, až natrefila na takový, jehož výsledkem byla slabá křivka.

Tento argument by měl jednu důležitou implikaci, jak namítají Koblitz a Menezes. Vezmeme si P-256 jako příklad. NSA má sice obrovský výpočetní výkon, ale v 90. letech by dokázala „přesít“ tak možná 248možných seedů. Po spočtení možných rodin křivek by vycházelo, že cca 2209 z 2257 jsou slabé. Jinak řečeno, aby tento útok fungoval, vyžadoval by, aby obrovská proporce parametrů generovala slabé eliptické křivky (tvaru podobného P-256 s jinými koeficienty).

Zatím by to byla největší známá rodina slabých křivek. Naposledy byla slabá rodina křivek nalezena v roce 1997. Pokud tedy věříte, že takto velká rodina eliptických křivek existovala, jediný způsob řešení je upustit od používání ECC a utíkat pryč. Což je shodou okolností přesně to, co NSA alespoň naoko dělá. Takže možná je důvod k panice?

Další hypotézy, proč přejít od eliptických křivek k post-kvantové kryptografii

Asi nejracionálnějším vysvětlením by bylo, že NSA má nějaký průlom v budování kvantových počítačů schopných výpočtů s stovkami qubitů. To je ale dost nepravděpodobné, protože technologicky by to byl neuvěřitelný skok. Navíc Snowdenova odhalení na nic takového nepoukazují. V praxi nebyl ještě plnohodnotný Shorův algoritmus vyzkoušen, jenom jeho zjednodušená varianta, která dopředu vyžaduje znalost faktorizace.

Možná NSA vynalezla algoritmus, který dokáže vyřešit ECDLP v čase n^(1/3) místo sqrt(n), kde n je řád grupy eliptické křivky. Taký algoritmus byl sice publikován, ale zatím má jednu nepříjemnou vlastnost – potřebuje čas n^(2/3) k předvýpočtu, což ho dělá nepraktickým. Na druhé straně by to vysvětlovalo, proč je P-256 nedoporučovaná, ale P-384 už je v pořádku.

Nebo naopak nalezla způsob, jak prolomit algoritmy post-kvantové kryptografie, a chce, aby na ně lidé přešli. Zatím se ale spíš ukazuje, že NSA má dobré hackery, s matematickým pokrokem to až tak slavně nevypadá.

NSA by mohla doufat, že odrazení lidí od ECC by znamenalo přechod na RSA, které možná umí lépe napadnout. Přece jenom, průlomů v oblasti faktorizace celých čísel bylo mnohem víc než v řešení ECDLP.

Poslední vyjmenované možnosti jsou, že RSA-3072 je víc „kvantově odolné“ než P-256 a P-384, nebo se NSA chce politicky distancovat od ECC.

NSA nás nechá stejně jen hádat, co má ve skutečnosti za lubem.