Pořád dokola se vyskytují hlášky jako "sha-1 je přece nebezpečná", nebo byla "bezpečná" do roku 2010 a s úderem 1.1.2011 začala být nebezpečná, nebo "ještě dva roky by měla být bezpečná", "prostě to jde kreknout v pohodě" a podobné nesmysly. Stejně jako spekulace, co už NSA krekuje nebo nekrekuje.
Ano, od 1.1.2017 už nebudou Windows důvěřovat SHA-1 podepsaným koncovým TLS certifikátům (leaf certifikace, endpoint certificate, end-entity certifice). To jsou třeba certifikáty web serverů, které vidíte přes HTTPS. Ale je třeba zajímavé, že budou i nadále věřit certifikačním autoritám (CA, certification authority) (samo)podepsaným SHA-1 libovolné úrovně. Už z toho by mohlo být vidět, že to není žádné až tak extrémní drama.
Ano, i NIST doporučuje skončit vládám s SHA-1 do roku 2010. NIST doporučuje skončit s SHA-1 všem do roku 2014. Ani CA and browser forum doporučuje do konce roku 2015 přestat používat SHA-1 certifikáty web serverů. A je to DOBŘE. Zbavme se SHA-1.
Když jsem na toto téma měl před lety přednášku na TechEdu, kdosi mě ale obvinil z ponižování bezpečnosti. Uvědomme si, že "absolutní" bezpečnost neexistuje. Bezpečnost se dělá kvůli businessu, nedělá se kvůli pocitu nějakého bezpečáka. Čím větší "bezpečnost", tím vždycky vyšší náklady, složitější procesy, nutné pravidelné kontroly a přehodnocování a špatná kompatibilita aplikací a vybavení obecně. Já sám samozřejmě taky rád přejdu na SHA256, pokud to jde, ale nemám rád paušální hlášky.
Podívejme se pořádně, co to vlastně znamená.
Bitová kvalita SHA-1
Původně byla porovnatelná bitová bezpečnost algoritmu designována na 128, tedy brute-force útok nalezne kolizi po 2^128 iterací. Pro úplnost dodejme, že SHA-1 sice produkuje 160bitový výsledek, ale jeho bezpečnost od začátku byla plánována "jenom" jako 128bitová. Od roku 2005 je však znám "matematický" útok, který snížil porovnatelnou bitovou bezpečnost SHA-1 na 2^80 "standardních porovnatelných" iterací.
Na základě tohoto objevu bylo v roce 2007 změněno doporučení NIST special publication 800-57 (revize 2012), které (stále) hodnotí SHA-1 na 80 bitovou bezpečnost (kapitola Comparable Algorithm Strenghts) a jako takovou ji měly US vládní organizace přestat používat pro šifrování nových dat na "sensitive" úrovni do konce roku 2010. Podle tohoto standardu se řídí v podstatě i zbytek světa.
Upozorňuji, že 80-bitová bezpečnost zde v tomto případě je "porovnatelná" (comparable), tzn. ne absolutní. Porovnatelná je vzhledem k síle AES 128, což NIST považuje za 128bitovou bezpečnost. To znamený, že pokud je SHA-1 jen 80bitová bezpečnost, půjde kreknout 2^48 krát rychleji, než AES128.
Neříká to nic o tom, kolik přesně je potřeba udělat SHA-1 výpočtů, abyste kreknuli SHA-1. Jeden výpočet SHA-1 nejspíš trvá jinou dobu, než jeden výpočet například AES nebo RSA. Důvodem pro snížení náročnosti SHA-1 byl po roce 2005 tento pejpr - https://www.iacr.org/archive/crypto2005/36210017/36210017.pdf, který uvádí, že to jde už po 2^69 brute-force výpočtech SHA-1. Důvodem k "porovnatelné" 80-bitové a "skutečné" 69-bitové bezpečnosti je, že výpočet jedné SHA-1 heše trvá technicky déle, než výpočet jedné AES128 iterace.
Rád bych zmínil, že ani v tomto standardu není napsáno, že by SHA-1 byla "mrtvá" ani "nebezpečná". Je to prostě jenom 80bitová bezpečnost. Podstatné je, že standard explicitně zmiňuje, že se nemá používat na nová data. Nikde tam není napsáno, že se má okamžitě začít s masivním přešifrováváním čehokoliv staršího, záloh a podepsaných dokumentů apod. Znamená to, že data zašifrovaná před koncem roku 2010 pomocí SHA-1 budou na sensitive úrovni bezpečná až do roku 2030.
Tenhle standard počítá s výpočetními schopnostmi hardware. Pokud by vlády ještě dneska používaly SHA-1, tak by to prostě jenom nesplňovalo zaručenou dobu, po kterou by ta data měla být bezpečná do budoucnosti. Přemýšlejme nejen o zálohohách, ale také o online nachytané komunikaci (HTTPS, VPN), kterou někdo bude (sice pomalu), ale přecejenom pár let krekovat. Mnoho takových dat je zajímavých i za několik desítek let.
Jak těžké a drahé je kreknout 80bitovou bezpečnost SHA-1
SHA-1 je tedy pořád 80bitová brute-force post-signing bezpečnost v porovnání s AES128. Je to přitom 69bitová bezpečnost samo o sobě, protože krekovat AES je rychlejší na každé jednotlivé iteraci.
Pokud počítáme přímo SHA-1 hashe, tak to znamená, že pokud máme nějakou konkrétní SHA-1 hash, tak nejpozději po 2^69 brute-force iteracích nalezneme nějakou aritmetickou kolizi. Například, máme knihu a z ní SHA-1 heš. Po 2^69 iteracích nalezneme kolizní náhodnou břečku, lidem nečitelnou, která rozhodně nevypadá jako kniha. Nebo máme digitální certifikát podepsaný SHA-1. Po 2^69 nalezneme kolizní náhodnou břečku, která nejspíš nevypadá jako certifikát. Takže jedna jedinná kolize je v naprosté většině případů v podstatě na nic.
Nikomu se nepodařilo nic jiného. Dokonce i nejnovější pejpr z října 2015 hovoří pořád jenom o rychlosti brute-force.
Tak se na to podívejme.
Pro konkrétní SHA-1 heš (hash) musíte vypočítat 2^69 jiných heší k náhodným zadáním. Generování náhodného zadání nezabere moc času v porovnání s časem nutným na výpočet hash. Heše jsou schválně dělané tak, aby jejich výpočet poněkud trval. Jedná se mnohokrát zatočené kombinace XOR operací. Na výpočty takových XORů se používají výhodně grafické karty (grafické procesory GPU), protože počítačová grafika - otáčení vektorů - je také jenom XOR oprace. GPU jsou tedy vlastně jen velice rychlé XORovací procesory.
Údajně nejrychlejší krekovací program na SHA-1 heše je hashcat. Sami uvádějí, že vypočítají 3000 milionu hash za sekundu na grafickém GPU AMD HD7970. Grafická karta s tímto GPU stojí cca 9000,- Kč. Jednoduchý výpočet, jak dlouho bude na takové kartě trvat krek 2^69 heší (krekujeme přímo heše, neporovnáváme to s 80-bitovou bezpečností SHA-1 vs. AES128 viz. nahoře)? Není nutné počítat s tím, že statisticky se podaří najít kolizi už po polovině času, tedy 2^68 je zanedbatelný rozdíl.
2 ^ 69 = 590 295 810 358 705 651 712
2 ^ 69 / 3 000 000 000 sekund = 196 765 270 119
196 765 270 119 sekund = 54 657 019 hodin
54 657 019 hodin = 149 745 let
Řekněme, že bychom měli 500 takových karet (cena cca 4 500 000 CZK). I tak bychom jednu kolizi nalezli po cca 300 letech. Samozřejmě to už ale naznačuje, že použitím botnetu, nebo nějakých větších cloudů jsme možná schopni hledat ty aritmetické kolize v řádech dnů až let. Pokud na to budeme mít dostatek "prostředků" samozřejmě.
Další naznačení špatné reputace přišlo v říjnu 2015 - autoři výše zmíněného pejpru uvádí, že se jim podařilo na 64 GPU Nvidia GTX970, každá opět po cca 9000 CZK, najít za 10 dnů freestart collision. To není to stejné, jako skutečná normální post-signing kolize - pěkné vysvětlení je třeba tady. Jde prostě o ukázku, že existuje možnost pro chosen-prefix útoky, která kazí reputaci daného algoritmu. Chosen-prefix útokům se dlouhodobě bráníme vkládáním náhodných informací do podepisovaných dat (do certifikátů náhodné sériové číslo, do dokumentů prostě náhodné číslo) a jsme tudíž proti nim velmi imunní.
Takže bych to uzavřel, že SHA-1 má dneska reálnou aritmetickou post-signing kolizní bezpečnost v řádech stovek let při nákladech v řádech desítek až stovek miliónů CZK minimálně.
Poznámka: znovu k porovnatelnosti - vzhledem k tomu, že SHA-1 je 80-bitová comparable bezpečnost, tak AES128 je 2^48 krát bezpečnější.
Opakuji aritmetickou. Pokud máme už hotový (post-signing) certifikát, nebo podepsaný dokument, zaplatíte desítky až stovky milionů a za pár let dostanete aritmetickou břečku, která nevypadá ani jako ten patent, kniha, nebo certifikát. A můžete zkoušet znovu.
Všechno ostatní jsou predikce. Uvědomte si, že jde o reklamu. Když už někdo predikuje, musí to vyznít nebezpečně. Nostradamusa si taky každý pamatuje ještě dneska.
Bojíte se? Já ne. Uklízečka s keyloggerem, nebo naštvaný zaměstnanec je milionkrát nebezpečnější zvíře. Chápu, že se bojí vlády, vojáci a tajné služby, i já se v podstatě bojím. SHA-1 má poškozenou reputaci a je pro každého lepší, když prostě přejde na něco bezpečnějšího, pokud to jde. Ale tvrdit, že to je mrtvý algoritmus...
Útoky na koncové certifikáty vs. certifikační autoritu
Dobře, začíná se nám do reality přibližovat vypočetní krekování SHA-1. Co to znamená pro certifikační autority, nebo jimi vydávané koncové certifikáty? Uvědomte si na začátek rovnou rozdíl mezi kořenovou certifikační autoritou (root CA), nižší certifikační autoritou (policy nebo issuing subordinate CA) a koncovým vydaným certifikátem (leaf certificate, user certificate, endpoint certificate, end-entitity certificate).
Útok na certifikát koncový - uživatelský
Řekněme, že chceme udělat MITM útok na nějaký HTTPS web server. Například https://www.sevecek.com. Tam je certifikát podepsaný certifikační autoritou a jeho podpis je pomocí SHA-1. Certifikát už existuje. Budeme tedy hledat post-signing kolizi. K úspěšnému MITM útoku bychom potřebovali dvě věci:
- dokázat udělat MITM pro nějakou oběť
- útočník by si musel sehnat certifikát, ve kterém by pole Subject nebo SAN (Subject Alternative Name) obsahovalo www.sevecek.com a přitom by k tomuto certifikátu měl útočník v ruce svůj vlastní privátní a veřejný klíč. Jedinné, co se v certifikátu kontroluje, je Subject nebo SAN. Útočník tedy má následující dvě možnosti:
- buď bude bruteforce vymýšlet dvojici privátní a veřejný klíč takový, který dá v požadovaném koncovém certifikátu (se jménem www.sevecek.com) stejnou SHA-1 hash. A bude mít tedy kolizní certifikát s vlastními klíči. To by bylo super. Akorát to ani při 80bitové bezpečnosti prostě nejde. Uvědomte si, že generování páru privátní - veřejný klíč také něco stojí. Nejen, že počítáte náhodné certifikáty při 80-bitové bezpečnosti, ale zdržujete se významně na generování asymetrických klíčů. Poznámka: nebylo by zde snad jednodušší útočit na kvalitu RSA a jeho délky klíče než na podpis - nebylo, 112 bitů pro 2048bitový RSA je pořád o hodně více, než 80bitů pro SHA-1. A zase připomínám, že ty kolize jsou aritmetické, takže to bude jen velmi těžko po 2^80 iteracích vypadat jako certifikát!
- druhou možností je, že zkusí počkat, až někdo (podle predikce ze zmíněného pejpru) vymyslí a dokáže využít nějakou rychle vypočítatelnou freestart hash. To by potom mohl zkusit na některou (libovolnou, nemusí být stejná jako ta, která www.sevecek.com naposledy vydala) certifikační autoritu udělat chosen-prefix útok. To znamená, že by si díky freestart hash vygeneroval svoje privátní a veřejné klíče a nechal si podepsat nový certifikát s vlastním jménem - třeba www.gopas.cz. Tady by libovolná autorita podespala skutečný požadavek na něco, co ten útočník opravdu vlastní. Ale díky správně předpočítanému požadavku by měl k tomu rovnou i rychle vypočítaný kolizní certifikát se jménem www.sevecek.com. Stějně tak, jako se roku 2005 stalo s MD5. Nojo, jenže to jsou pořád jenom predikce. Chosen-prefix útok na SHA-1 zatím nikdo nedokázal. A za druhé, tomu se brání autority tím, že do certifikátů vkládají náhodná sériová čísla, takže velmi omezují možnost něco vůbec předpočítávat. Chosen-prefix útok vyžaduje dopředu vědět, co se bude podepisovat. Jestliže do podepisovaného materiálu (certifikát, dlužní úpis, daňové přiznání) vložíte při podpisu například náhodné číslo, těžko půjde něco předpočítat.
Jenže takových koncových certifikátů je moc, čím více, tím větší pravděpodobnost útoku někde. Taky je vcelku jednoduché je prostě přestat vydávat a nahradit SHA-256. Takže to všichni udělejte, a budeme v bezpečí!
Útok na certifikát kořenové certifikační autority (CA - root certification authority)
Proč budou i nadále platit SHA-1 kořenové certifikáty a certifikáty nižších (podřízených - subordinate) autorit i po roce 2017?
Dva důvody. Menší nebezpečnost a business.
Business je jasný. Zdůvěryhodnit si root CA po celém světě je velmi nákladné. Ani Verisign (Symantec) ještě nepřešel a předpokládám, že ještě dlouuuho nepřejde. Nemohou. Proč jim lidi platí za certifikáty? Protože jim věří každý OS, mobil, kalkulačka, splachovadlo s digitálním zobrazováním nálože, router, switch apod. Kdyby teď začali vydávat pod novou autoritou, všechny web shopy a internet bankingy by se zhrozily, protože by odpadla polovina uživatelů se starými neaktualizovanými trust store.
Druhý důvod bezpečnostní je zajímavější. Riziko na jedinném certifikátu certifikační autority je minimální. Co by znamenalo pro útočníka "kreknout" existující CA certifikát přes jeho SHA-1 hash? To hodně závisí na tom, co kontroluje klient, pokud vyhodnocuje platnost stromu (cesty - path validation) od koncového certifikátu směrem nahoru.
Každý spodnější certifikát odkazuje na svého vydavatele pomocí jeho jména z políčka Subject. Dále ale odkazuje nahoru i volitelným políčkem Authority Key ID (AKI). AKI pole ukazuje nahoru na rodičovo políčko Subject Key ID (SKI), což je SHA-1 heš veřejného klíče certifikátu (public key hash) - v tomto případě hash veřejného klíče vydavatele. Takže každý nižší certifikát v sobě má heš veřejného klíče vydavatele.
Na konci cesty - tedy na vrcholu stromu - se nalézá kořenový (root) CA certifikát, kterému klient musí bezmezně věřit. To znamená, že má tento certifikát celý binárně umístěný ve svém trust store (ve Windows je to Trusted Root Certification Authorities, neboli v powershellu cert:\localmachine\root).
Pokud by chtěl útočník "kreknout" přímo nějaký libovolný certifikát nějaké certifikační autority z řetězu, mohl by si zkusit generovat kolizní certifikát s jiným veřejným a privátním klíčem. Stejný jako předchozí problém post-signing kolize koncového certifikátu. A ještě to bude o trošku ztížené, pokud klientské certifikáty obsahují AKI/SKI vydavatele. Znamenalo by to tedy brute-force generovat certifikáty pro různé public-private key pair při zachování obsahu pole Subject tak, že i AKI/SKI by bylo stejné. A máme tu pořád 80bitovou bezpečnost, pokud ne silnější.
V případě root (kořenové) CA to bude ještě o to složitější, že hledáte kolizi při zachování nejen Subject a AKI/SKI, ale také thumbprint (otisk), nebo dokonce celý obsah certifikátu binárně. A tím jste skončili úplně.
Certifikáty certifikačních autorit nepodléhají problému chosen-prefix, protože veřejné autority nepodepisují CA certifikáty pro anonymní veřejné žadatele. Všeho všudy taky pro post-signing krekování máte k dispozici jen velmi málo certifikátů veřejných autorit v porovnání s počtem vydávaných koncových certifikátů a tudíž klesá pravděpodobnost, že se už někdo historicky trefil do nějaké kolize.
Proto jsou CA certifikáty podepsané SHA-1 pořád dost bezpečné nato, aby se nemuselo dramatizovat. Větší rizika jsou na koncových certifikátech, proto ta deprecation policy od roku 2017.
Na závěr dvě poznámečky
V článku o zrušení důvěryhodnosti SHA-1 koncových certifikátů se objevila nedávno zmínka o tom, že se to týká pouze root CA, které jsou na Microsoft Trusted Root Certificate Program. Tzn. snad pouze kořenových autority, které se distribuují do Windows automaticky a dynamicky z Windows Update. Takže to asi nebude ovlivňovat vaše vnitřní CA, které snad mohou vydávat i nadále cokoliv chtějí. Zdá se?
Druhak, pokud máte stávající root CA, jak je z politiky vidět a jak jsme si vysvětlili, není nutné ji přeinstalovávat, ani pokud ona sama je SHA-1 samo-podepsaná (self-signed). Jediné co musíte případně změnit, je algoritmus, kterým se podepisují koncové vydané certifikáty. To se dá udělat i jen pomocí registrů a prostě CAčku potom restartnete a všechno se už bude vydávat jako SHA-256:
HKLM\System\CurrentControlSet\Service\CertSvc\Configuration\CAxxx\CSP
CNGHashAlgorithm = REG_SZ = SHA256
A to je dneska už opravdu všechno :-)