reklama

Superpočítače způsobují kryptografům problémy

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).

Klepněte pro větší obrázek
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.

Klepněte pro větší obrázek
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.

 Klepněte pro větší obrázek  Klepněte pro větší obrázek
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:

Témata článku: Internet, Bezpečnost, MD5, Lausanne, Bobik, PS3, Chaos

58 komentářů

Nejnovější komentáře

  • Honza 8. 1. 2009 7:41:34
    No, hash table se stále používá pro rychlý přístup k datům přes klíč....
  • snake 8. 1. 2009 4:43:32
    To přirovnání k otisku prstu je opravdu výborné, však ona se...
  • Joker 7. 1. 2009 16:22:51
    Pravda, ovšem to je podle mě ta hlavní oblast- řekněme "ověřování...
reklama
Určitě si přečtěte

UPC překopli páteřní kabel. V Brně i druhý den nejede internet ani kabelovka

UPC překopli páteřní kabel. V Brně i druhý den nejede internet ani kabelovka

** V Brně byl velký výpadek služeb UPC ** Důvodem je překopnutý páteřní kabel ** V některých lokalitách služby stále nefungují

5.  12.  2016 | Jakub Čížek | 100

17 expertek Microsoftu předpovědělo rok 2027. Splní se alespoň něco?

17 expertek Microsoftu předpovědělo rok 2027. Splní se alespoň něco?

** Zmizí klasické vyhledávače ** Budeme programovat buňky ** Kvantové počítače překonají šifry

6.  12.  2016 | Jakub Čížek | 34

ASUS ZenBook 3 se začal prodávat v Česku. Je ve všem lepší než MacBook, ale bude to stačit?

ASUS ZenBook 3 se začal prodávat v Česku. Je ve všem lepší než MacBook, ale bude to stačit?

** Novinka od Asusu míří přímo proti MacBooku od Applu ** Nabídne daleko více výkonu za stejné peníze

2.  12.  2016 | David Polesný | 145

11 tipů na dobrý stolní počítač: od základu po herní mašiny

11 tipů na dobrý stolní počítač: od základu po herní mašiny

** Postavte si stolní počítač! Máme pro vás 11 vzorových sestav s rozpisem komponent ** Většina tipů cílí na hráče, věnujeme se ale i základnímu PC a počítačům na střih videa ** Nadělte si nový počítač třeba pod stromeček

5.  12.  2016 | Adam Kahánek | 73


reklama