Hlavní navigace

Zůstává elektronický podpis bezpečný?

4. 5. 2005
Doba čtení: 8 minut

Sdílet

Po loňském oznámení prolomení MD5 čínským týmem Xiaoyun Wangové se již ví, jak jej provést, a to i díky českým kryptologům. Číňané následně oznámili, že jsou schopni 2048krát snížit náročnost nalézání kolizí v SHA-1 – co to znamená a jaké jsou důsledky pro praxi, především pro bezpečnost elektronických podpisů? Je možné podpis zfalšovat?

Základní teorii o hašovacích funkcích jsme se naučili chápat v minulém díle, takže dnes můžeme pokročit k zajímavější, praktické části.

Než se však začneme věnovat útoku na SHA-1, je vhodné se zmínit o předchozím útoku na MD5, což je jiná poměrně populární hašovací funkce, s délkou haše 128 bitů. Byl proveden čínským týmem Wangové, který se jím právě loni proslavil. Svou schopnost útoku na MD5 (a na další hašovací funkce) prokázal zveřejněním výsledných kolizí [PDF, 57 kB, EN]. Na IBM P690 (to by měla být databázová serverová platforma s 32 procesory) má nalezení kolize pro MD5 trvat asi hodinu. Jelikož si (alespoň někteří) kryptologové v rámci akademické spolupráce rádi navzájem dávají hádanky, Číňané podstatné podrobnosti své metody nezveřejnili. Ostatní kryptologové se následně během podzimu 2004 pokoušeli přijít ze zveřejněných dat a informací na to, jak to bylo provedeno. Předního českého kryptologa Vlastimila Klímu pohltilo téma nadmíru, takže mu věnoval nejen loňské vánoce, ale i leden a únor. Dne 5.března pak mezinárodně publikoval článek s provokativním názvem Nalézání kolizí v MD5 – hračka pro notebook [PDF, 84 kB, EN], protože sice asi nepřišel přesně na metodu Wangové, ale nalezl svou, která je celkově asi 4–6× rychlejší. Českou variantu článku si můžete přečíst zde [PDF, 173 kB, CZ]. Den poté, tj. 6. března, nechala Xiaoyun Wangová zveřejnit články Jak zlomit MD5 a jiné hašovací funkce [PDF, 185 kB, EN] (RIPEMD, HAVAL) a též Kryptonalýza hašovacích funkcí MD4 a RIPEMD [PDF, 167 kB, EN]. Tím se zase jednou potvrdilo, že nejlepším způsobem uvolnění embarga je vytvoření vlastní náhrady.

Zřejmě aby březen (měsíc Internetu) nebyl nudný, zveřejnila Wangová (nyní hostující na univerzitě v Eindhovenu) využití kolize MD5 v mírně šokujícím příkladu, kdy části, kolidující jen v celkem sedmi bitech, vložila do certifikátu veřejného klíče v místě, kde se právě nalézá veřejný klíč. Tyto dvě binární sekvence přitom byly zároveň navrženy tak, aby vyhovovaly jako klíče RSA. Výsledkem je vznik dvou certifikátů se shodnou haší a podpisem certifikační autority, ale dvěma možnostmi párů klíčů.

1616
Kolize v certifikátu veřejného klíče hašovaného funkcí MD5 (zdroj: Colliding X.509 Certificates [PDF, 96 kB, EN])

Čtenář by neměl zanevřít na certifikáty X.509 – jejich struktura není vůbec na vině, příčina spočívá výhradně v hašovací funkci MD5. Takový útok je velmi nepříjemným podlomením vlastností infrastruktury veřejného klíče (PKI) – při žádosti o certifikát se tato podpisuje soukromým klíčem, čímž certifikační autorita ověří, že žadatel má tento klíč v držení. Při uvedeném útoku by se mohl používat druhý certifikát, který certifikační autorita neověřovala, ani neověřovala držení příslušného soukromého klíče.

Praktické dopady útoků na MD5 se asi dají skutečně nalézt spíše v těch oblastech, kde lze provést záměny 1024bitových bloků binárních dat, přesto je znepokojivé, že změny stačí promítnout jen do několika málo míst. V původním loňském příkladu jsou rozdíly jen v šesti bitech zprávy, které by se promítly do pouhých tří bytů rozdílu! Wangová i Klíma umí nalézt kolize MD5 s libovolným inicializačním vektorem. Z toho plyne, že jsou schopni kolidující bloky o 128 bytech umístit kamkoliv mezi 64bytové úseky jedné zprávy (viz i obrázek), a to i na více místech.

Útok Wangové na SHA-1

Hašovací funkce SHA-1 by měla mít shodné vlastnosti jako náhodné orákulum a nejsnazší možný útok na silnou odolnost proti kolizím (obr.4 v minulém článku) by u SHA-1 tedy měl mít náročnost 280 pokusů.

Tým Wangové 13.února oznámil [PDF, 48 kB, EN], že je schopen nalézat obecné kolize v SHA-1 s náročností útoku v řádu 269 pokusů! Oznámení opět neobsahuje žádné podrobnosti, neobsahuje však ani příklady nalezených kolizí SHA-1. Obsahuje však příklady nalezených kolizí v SHA-0 (což byla předchůdkyně SHA-1) a příklady kolizí SHA-1, omezené na 58 kroků (kompresní funkce SHA-1 však obsahuje 80 kroků).

Jakékoliv snížení náročnosti útoku označuje kryptologie jako „prolomení“ funkce. Ve vědeckém a matematickém slova smyslu se jedná o úspěch prvního řádu. Pro realitu se však zdá, aspoň zatím, že SHA-1 prakticky prolomena nebyla. Opět se tedy jedná o útok ve smyslu obr. 4 v minulém článku na silnou odolnost proti kolizím.

Optimismus

Předně je třeba uvážit toto:

  • odolnost argumentu ani odolnost proti druhému argumentu útok Wangové nenarušuje – pro obě tyto vlastnosti stále platí náročnost útoku 2160 (spíše nižší – viz níže),
  • náročnost 269 je stále poměrně astronomické číslo,
  • útok předpokládá přístup útočníka ke zprávě.

Je třeba i zvážit aplikaci hašovací funkce. Hašovací funkce se např. používají jako tzv. klíčované otisky (HMAC) s parametrem symetrického klíče. Protože ten je držen v tajnosti bez přístupu útočníka, útok Wangové na HMAC pravděpodobně nemá vliv. Jinou oblastí použití SHA-1 je pseudonáhodné generování (PRNG) náhodných čísel. I zde je přístup útočníka ke vstupním datům (semeno, mezihodnoty) záměrně znemožňován a útok by neměl mít vliv. Rovněž hašování hesel by nemělo být zeslabeno, stejně jako generování klíčů z heslových frází (PRF).

Z praktických aplikací, které by útok mohl ohrozit, je tedy nejvíce asi ohrožen (elektronický) digitální podpis. V něm se totiž nepodpisuje originál zprávy, ale právě její otisk, vytvořený některou kryptografickou hašovací funkcí, v současnosti typicky právě SHA-1. Lze se ptát, jak by získal útočník možnost formulovat zprávu, když tuto vytváří typicky sám podpisující. Kryptologie zde upozorňuje, že útočníkem může být i samotný podpisující.

Cílem digitálního podpisu je dosáhnout vlastnosti nepopiratelnosti provedení podpisu podpisujícím, podpis má být posouditelný neutrální třetí stranou – arbitrem. Pokud si však podpisující předem „uvaří“ dvě alternativy zprávy, přivede tím arbitra nepochybně do rozpaků. Z proběhlé komunikace vůbec nemusí být zřejmé to, která alternativa byla „první“. Obecně ani podpisující nemusí být útočícím autorem alternativ, nýbrž přesněji jím je ta strana, která provedla formátování zprávy, což může být i spoléhající, ale i neznámá třetí osoba (včetně útoku muže uprostřed).

Na druhé straně bude arbitr vědět, že pokud jsou dvě alternativy zprávy, pak sice nebude možné určit, která z nich byla podepsána, ale viníkem je nepochybně ta ze stran, která zprávu zformátovala. Věrohodnosti tedy trochu napomůže, pokud si strany do zprávy uvedou, kdo zprávu formátoval. Obdobná zásada se ostatně uplatňuje v právu tam, kde se nachází nejasné ustanovení – má se vykládat v neprospěch toho, kdo jej jako první navrhl. Při extrémně dotaženém útoku na hašovací funkci se ovšem může přihodit, že alternativy budou obsahovat i alternativně uvedené formátující.

Pokud máte dřívější podpisy zabezpečené časovými razítky (ideálně více razítky s různými hašovacími funkcemi), pak první výše uvedená námitka rovněž znamená, že dříve provedené podpisy jsou zatím naprosto bezpečné. Falšovat je lze stále jen s náročností 2160. Otázka ale je, jak obstojí hašovací funkce samotných razítek.

Třetí námitka předpokládá nejen to, že útočník má přístup k tvorbě zprávy, ale i to, že obě zprávy budou „smysluplné“ a z hlediska útočníka obsahovat právě kýžený rozdíl. Zde spočívá zatím asi největší ochrana podepisovaných textů v jednoduchých formátech, pokud apriori nepřipouští 128bytové a delší binární úseky. Potíže ale mohou vzniknout u podpisů obecných binárních dat, jako jsou programy nebo distribuční balíky. Zde lze zneužít dokonce i již jen několika málo příkladů zveřejněných kolizí v MD5.

Zatím panuje spíše názor, že řád útoku 269 (popř. i 266) je mimo dosah i specializovaných zařízení a rozhodně mimo běžný ekonomický dosah. Např. útok Vlastimila Klímy na MD5 notebookem byl umožněn snížením výpočetní náročnosti na úroveň 233. Kromě výpočetní rychlosti hašování, únosné míry pipe‑liningu a obecné paralelizace je třeba do úvahy vzít i paměť pro uložení výsledků. Protože však neznáme přesně metodologii, je možné, že lze vystačit s úspornějším uložením, než je možné odhadovat.

Zdrojem optimismu může být i prohlášení amerického NIST [PDF, 11 kB] (tj. organizace, která je formálním autorem SHA-1), který i po oznámení útoku potvrdil, že na svém plánu přejít na třídu SHA-2 až do roku 2010 zatím nic nemění (můžete ovšem přejít dříve). Rovněž německý BSI zatím nehodlá SHA-1 rázně opustit, pouze ji již nedoporučuje pořizovat jako součást nových produktů.

Pesimismus

SHA-1 je v současnosti zřejmě nejpoužívanější hašovací funkce vůbec, používá se v mnoha systémech, protokolech a aplikacích. Její náhrada nebude rychlá ani levná.

První oznámení o oslabení bývají zpravidla následované dalšími, ještě zásadnějšími. V kuloárech se již mluví o tom, že čínský útok byl dále zefektivněn na řád 266.

Práce Antoine Jouxe z loňska ukazuje, že všechny iterativní hašovací funkce se chovají výrazně hůře než náhodné orákulum, nalezení více kolizí není o mnoho složitější než nalezení první kolize zpráv. Kvůli tomu nepomáhá ani zřetězení výsledků dvou běžných hašovacích funkcí.

Práce Johna Kelseyho a Bruce Shneiera [PDF, 166 kB, EN] podává návod, jak získat druhý argument s podstatně nižší složitostí, než je teoretická – např. pro SHA-1 vyjde 2106 namísto 2160.

Ministerstvo informatiky ČR nezareagovalo na zprávy o naprostém prolomení MD5 v loňském srpnu zatím bohužel vůbec nijak. V platnosti je stále vyhláška 366/2001 Sb, v jejíž první příloze je používání MD5 povoleno pro běžné používání uživateli (ne však certifikačními autoritami vydávajícími kvalifikované certifikáty).

Doporučení

Rámcová doporučení:

  • sledovat vývoj a zprávy kryptologů,
  • používání MD5 opustit pokud možno ihned,
  • migraci z SHA-1 na SHA-2 (ideálně SHA-512) naplánovat v časově dostupném horizontu 1–3 let,
  • mít své aplikace modulárně připravené k využití nových alternativních hašovacích funkcí; např. formáty jako CMS nebo XML Signature běžně umožňují používat alternativní kryptografické funkce.

V oblasti elektronického podpisu navíc:

BRAND24

  • používat prostředky pro bezpečné vytváření podpisu,
  • používání prostředku pro bezpečné vytváření podpisu zahrnout do certifikační politiky,
  • používat certifikované nebo alespoň důvěryhodné aplikace vytvářející podpis,
  • používat co nejjednodušší formáty podpisovaného obsahu se striktní kontrolou syntaxe, při strukturaci i s jasnou sémantikou,
  • popř. uvádět stranu provádějící formátování do obsahu zprávy,
  • při online podpisování formulářů apod. chránit kanál proti útoku muže uprostřed.

Výše uvedená doporučení asi nebudou populární (jednak protože něco stojí, jednak bezpečnost jde částečně proti uživatelnosti), většině z nich se však uživatelé v budoucnu stejně nevyhnou, pokud budou chtít skutečně zajistit právní nepopiratelnost elektronického podpisu. Pro bezpečné uložení klíčů i pro bezpečné vytváření podpisu jsou třeba objektivně, bez ohledu na momentální slabost hašovacích funkcí. Prostředek pro bezpečné vytváření podpisu pak navíc vyloučí i možnost vytvoření duplicitního certifikátu, jako je třeba na obrázku v tomto článku. Obdobně speciálně vyvíjená a udržovaná aplikace ve spojení s přesně definovanou syntaxí formátu obsahu může do značné míry vyloučit možnost „doplňování“ podpisovaného obsahu pro vznik kolize, a to i když by se zatím používala „jen“ SHA-1.

Na závěr si dovolím doporučit dva zdroje:

Důvěřujete elektronickému podpisu?

Byl pro vás článek přínosný?

Autor článku

Autor se několik let specializuje na Elektronický podpis v ČR aj. konzultace v oblasti počítačové bezpečnosti.
Upozorníme vás na články, které by vám neměly uniknout (maximálně 2x týdně).