Skupině inženýrů z USA a evropských univerzit se podařilo s pomocí 200 herních konzolí PS3 uměle vytvořit SSL certifikát autority VeriSign, který tato společnost ale nikdy nevydala.
Stejně jako relativně malý a jednoduchý otisk lidského prstu, který snadno identifikuje člověka, existuje i jeho softwarová analogie, tzv. hashovací funkce, která se nezřídka nazývá také kontrolní součet. Příkladem může být třeba kontrola integrity velkého souboru, typicky ISO obrazu optického média. Pokud budete takový soubor stahovat ze sítě, budete na konci možná chtít ověřit, jestli se rozměrný soubor stáhl celý a bez problémů. Můžete samozřejmě porovnat velikost souboru s informací na webu, z ní se ovšem nedozvíte, jestli má určitý bajt uprostřed souboru správnou hodnotu.
Hash je softwarová analogie otisku lidského prstu
Autor ISO obrazu ale mohl vytvořit pro rozměrný soubor hash, kontrolní součet, což je zpravidla řada zdánlivě nahodilých znaků. Kouzlo hashovací funkce ale spočívá v tom, že takto vygenerovaná řada bude unikátní, bude přesně odpovídat pouze tomuto jedinému souboru. Pokud tedy na staženém ISO obrazu opět provedete kontrolní součet a hash kód bude odpovídat originálu, můžete si být jisti, že oba soubory, originál na webu i vámi stažená kopie, jsou identické – stejně jako relativně jednoduchý otisk lidského prstu odpovídá bez výjimky pouze jediné mnohem složitější a komplexnější lidské bytosti.
Velké oblibě se už mnoho let těší pro svou jednoduchost hashovací funkce MD5, ačkoliv již v devadesátých letech bylo zjištěno, že má své mouchy, což bylo potvrzeno v roce 2004. Hash kód funkce MD5 totiž není až tak unikátní, jak by se mohlo na první pohled zdát. Abych byl přesný, unikátní není ani jeden hash „otisk prstu“, pravděpodobnost, že budou mít dva soubory stejný hash otisk, je ale velmi malá. Ale co když záškodník alternativní hodnotu se stejným hashem skutečně objeví?
MD5 hash ale není tak unikátní
MD5 se používá například pro uložení hesla v databázi. Pokud se tedy registrujete do nějaké webové služby, autor zpravidla nezná skutečnou hodnotu vašeho hesla, ale pouze jeho kontrolní součet, který se pak porovnává s kontrolním součtem hodnoty, kterou zadáváte při přihlašování. To je skutečně velmi užitečné, pokud by totiž takovou službu napadl hacker a získal databázi uživatelů, nedozví se skutečné heslo, které můžete používat i na mnoha dalších službách včetně kritického PayPalu. Samotný kontrolní součet mu přitom bude bez superpočítače k ničemu.
Příklady MD5 funkcí:Výrazu bobik odpovídá hash kód 4ddc3a9aaa4de72ea38333044cbecaaa
Výrazu žluťoučký koníček odpovídá hash kód 24d975ad1e05ffefd089e549b56e421c Jakýkoliv MD5 hash má konstantní délku 32 alfanumerických znaků (128 bitů), k dispozici je tedy limitní počet kombinací. |
Ale vraťme se k našemu záškodníkovi. Co když metodou „hash collision“ skutečně objeví zcela jiný text, který sice nemusí být totožný s vaším heslem, má ale s určitým algoritmem stejný hash? V takovém případě by se mohl přihlásit k mnoha službám i bez znalosti skutečného hesla.
Což takhle vytvořit dva různé SSL certifikáty se stejným hashem?
A takový „hash collision“ se na podzim povedl i jisté mezinárodní výzkumné skupině v laboratořích LACAL ve švýcarském Lausanne, která jej na konci prosince prezentovala na Chaos Computer Congress v Berlíně a která se zaměřila na kryptografii, SSL protokol a certifikační autority, které mnohdy dodnes používají zastaralý hashovací algoritmus MD5 (nutno podotknout, že o moc lépe na tom není ani novější algoritmus SHA-1 a je jen otázkou času, kdy se reverzním inženýrstvím „hash collision“ podaří i tomto případě; o tento způsob prolomení SHA-1 se dokonce pokouší i jeden gridový projekt v systému BOINC).
Tým výzkumníků z Holandska, Švýcarska a USA, kteří pracovali na hash collision MD5
Pokud se budete připojovat na nějaký server přes šifrovanou komunikaci TLS/SSL (HTTPS://), před začátkem samotné šifrované komunikace, která je nezbytná především u internetového bankovnictví, dojde k procesu „handshake“ – webový prohlížeč si doslova s webovým serverem podá ruce a ověřením certifikátu, který vydává některá z mnoha certifikačních autorit (CA) dojde k potvrzení toho, že webový server třeba na adrese https://www.zive.cz skutečně patří společnosti CPress Media.
Handshake je velmi důležitý a ještě důležitější jsou webové certifikáty, které jej identifikují a které si může každý zpravidla na dobu určitou předplatit u některé z certifikačních autorit u nás nebo v zahraničí.
Certifikáty ve velkém používají hash kód a kupodivu mnoho z nich stále i algoritmus MD5. Součástí hash kódu je pak i otisk informace, dokdy je vlastně certifikát platný a dalších údajů.
Vraťme se nyní k problému dvou různých hesel, které mají stejný hash kód. Co když bychom stejným způsobem vytvořili identický certifikát, který by měl stejný hash kód, kontrolní součet, chcete-li, obsahoval by však informace, které potřebujeme my. Takový certifikát by snadno prošel kontrolou v drtivé většině webových prohlížečů a dalších programů, mnoho z nich totiž dnes pracuje s tzv. kořenovými certifikáty.
Schéma HTTPS komunikace: (1) v prohlížeči je již po instalaci několik základních kořenových certifikátů nejznámějších vydavatelů; (2) majitel webových stránek si pronajme certifikát od vydavatele; (3) při navštívení webových stránek si prohlížeč stáhne certifikát a jeho pravost ověří kořenovým certifikátem, handshake je hotov, nyní může začít šifrovaná komunikace
Kořenové certifikáty jsou vlastně certifikáty důvěryhodných autorit (vydavatelů certifikátů) a usnadňují práci s šifrovanou komunikací. Samotný certifikát webového serveru se pouze ověří kořenovým certifikátem předinstalovaným ve vašem počítači. Ideálním případem by samozřejmě bylo, kdyby webový prohlížeč poslal certifikát získaný od webové stránky na server certifikační autority k ověření, to by ovšem drasticky zpomalovalo celou komunikaci, a pokud by takový web CA spadl, celý šifrovací systém by se kauzálně rozpadl jako velké domino. Nefungoval by e-banking, PayPal a další služby používající šifrovanou komunikaci a certifikáty.
Poměrně známým a levným certifikátem je třeba Thawte nebo RapidSSL. Oba používají hashovací algoritmus MD5 a toho druhého si vybrala naše skupina a reverzním inženýrstvím se jí podařilo postupně hash kód analyzovat. Tím pádem vytvořili nový certifikát, který byl zcela identický s jakýmkoliv jiným důvěryhodným RapidSSL certifikátem ovšem s tím rozdílem, že jej autorita RapidSSL nikdy nevydala.
Jde to, ale budete potřebovat superpočítač
VeriSign, který službu RapidSSL provozuje, později zareagoval, týmu programátorů pogratuloval a přislíbil okamžitou změnu, která snad povede k upuštění od algoritmu MD5. Nicméně jak jsem psal již na počátku, v bezpečí dnes není ani novější SHA-1, neboť se do něj již pustila další skupina reverzních inženýrů a jeho prolomení je jen otázkou času.
Vytvořit totožný hash kód pro různá data není jednoduchá operace, je to vlastně složitý analytický proces, kdy se pomocí superpočítače porovnávají stovky a tisíce různých certifikátů od jedné autority (v našem případě RapidSSL) a hledají se rozdíly, dynamika změny znaků hash kódu aj. O tom, že se skutečně nejedná o operaci pro váš osobní počítač, snad svědčí i skutečnost, že výzkumníci během celého experimentu zpracovali funkci MD5 více než 251 krát. Celý výpočet pak zabral několik desítek hodin a byl proveden na clusteru složeném z více než 200 herních konzolí PlayStation 3 s výkonnými Cell (PowerPC/SPE) procesory od IBM.
LACAL Lausanne PlayStation Lab: sen každého herního pařana
Vytvořit „hash collision“ nad zastaralým MD5 algoritmem je tedy i tak pro většinu z nás naprosto nedostupnou záležitostí, přesto je to důvod k obavám, výkon počítačů se totiž neustále zrychluje a dvě stovky paralelně zapojených PS3 dnes představují výkon superpočítače, kterého ještě před pár lety nedosáhly ani ty nejvýkonnější sálové superpočítače světa za miliony dolarů.
Pakliže bude trend paralelizace výpočetního výkonu pokračovat a jednou bude běžný počítač obsahovat mnoho procesorů s ještě větším množstvím samostatných výpočetních jader, možná budou podobné průniky na denním pořádku. Nelze než doufat, že metody kryptografie se budou ruku v ruce s vývojem výpočetního výkonu neustále zdokonalovat.
Amazon EC2: superpočítač s dvacítkou Opteronů za 19,-
Investici do výkonného podnikového mainframu nebo skutečného clusteru složeného třeba z podobných PlayStationů, si nemůže dovolit každý, přesto dnes může využít superpočítačového výkonu kdokoliv z vás a relativně levně.
Zajímavou superpočítačovou službu totiž nabízí americký Amazon. Jmenuje se EC2 (Amazon Elastic Compute Cloud) a jedná se o pronájem virtuálního serveru podobným způsobem, jak tak činí i mnozí poskytovatelé webového hostingu u nás.
EC2 je vlastně virtuální Linux (RHLE, openSUSE, Gentoo, Ubuntu aj.), OpenSolaris nebo Windows Server s databázovým (MySQL, MSSQL, Oracle) a aplikačním (Java/JBoss, Ruby on Rails) serverem na kterém můžete provozovat své aplikace. Server je virtualizovaný, což znamená, že jej spravujete jen vzdáleně přes webové nebo terminálové rozhraní a nemusíte jej instalovat. Jaké na serveru budete zpracovávat úlohy, už pak závisí pouze na vás.
Podobnou nabídku ovšem skutečně nabízí i čeští provozovatelé virtuálních serverů (třeba Pipni vServer a další), v čem se tedy Amazon liší? Výkonem a způsobem zpoplatnění. Neplatíte totiž za samotný virtuální server, ale pouze za procesorový čas. Co vám Amazon vypočítá, to zaplatíte. Nejdražší varianta High CPU Extra Large (Windows Server) si účtuje lehce přes jeden dolar za hodinu výpočtu, za který ovšem dostanete 7 GB RAM, 1 700GB úložiště a procesorový výkon srovnatelný s dvacítkou Opteronů/Xenonů s taktem 1 – 1,2 GHz.
Pokud tedy budete chtít prolamovat armádní šifry, případně vypočítávat exploze vodíkových pum, vystačíte si s devatenácti korunami na hodinu. A za hodinu se toho dá vypočítat celkem dost.
Samotná studie rekonstrukce „hash collision“ algoritmu MD5 je poměrně komplikovaná, celou zprávu včetně doprovodných grafů, animací a detailního vysvětlení ale najdete v angličtině na webových stránkách Technické univerzity v Eindhovenu.
K tématu:
