Hlavní navigace

Totálně nebezpečné certifikáty s MD5

Vlastimil Klíma

Hašovací funkce MD5 se stala brzy po svém uvedení nejoblíbenější hašovací funkcí. Dnes je problém ji ve všech aplikacích nahradit. Marc Stevens, Arjen Lenstra a Benne de Weger vypracovali a včera oznámili metodu tzv. cílených kolizí MD5. Ukážeme si novou metodu a její použití v certifikátech.

V roce 2004 byla zveřejněna data (nikoli metoda), která znamenala kolizi MD5. Metoda byla odhalena v roce 2005. V roce 2006 byla nalezena nejúčinnější metoda hledání kolizí MD5, umožňující je generovat během sekund a pro zvolený inicializační vektor. První dva kolidující certifikáty klíčů RSA byly vyrobeny v roce 2006. Byly vydány na tutéž osobu, ale měly různé klíče. Metoda byla vylepšena, takže dnes je možné pro dvě různé osoby (libovolná jména, organizace, e-maily, sériová čísla) a dva různé klíče použít jeden podpis certifikační autority.

Jde o to, že Marc Stevens, Arjen Lenstra a Benne de Weger vypracovali a včera oznámili metodu tzv. cílených kolizí MD5. Běžná kolize je, že (k danému, ve standardu pevně definovanému inicializačnímu vektoru IV) se najdou dvě různé zprávy b1 a b2 (označení b jako binární) tak, že MD5(IV,b1) = MD5(IV,b2). Jestli si vzpomenete, v březnu tohoto roku jsem publikoval metodu tunelů, která umožňuje nalézt takové kolize v průměru za 31 sekund na notebooku, a to pro libovolně zvolené IV (zdrojové kódy a podrobnosti najdete na cryptography.hy­perlink.cz/2004/ko­lize_hash.htm).

Marc Stevens si dal za cíl najít kolizi s libovolnými různými IV1 a IV2, tj. pro tato zvolená IV1 a IV2 nalézt dvě různé zprávy b1 a b2 tak, že MD5(IV1,b1) = MD5(IV2,b2). Zdánlivě maličkost, ale není to pravda. Je za tím kus práce, neboť se musí najít jiná diferenční cesta k takovým kolizím. Za vykonanou práci je pak odměna. Kolidující zprávy mohou začínat libovolně různě (doposud mohly začínat libovolně stejně). To potom umožňuje zvolit si libovolné různé začátky m1, m2 a dopočítat k nim kolidující konce b1, b2 tak, že MD5(IV,m1,b1) = MD5(IV,m2,b2).

Skutečně, zvolíme-li libovolné různé m1 a m2 (libovolné různé začátky těl certifikátů), dostaneme se po jejich zhašování s použitím standardní hodnoty IV, tj. po zhašování (IV,m1) a (IV,m2), do různých stavů, které označíme jako IV1 a IV2. Protože nyní k IV1 a IV2 umíme najít různá b1 a b2 tak, že MD5(IV1,b1) = MD5(IV2,b2), máme MD5(IV,m1,b1) = MD5(IV,m2,b2), tj. kolizi pro standardní IV a zprávy (m1,b1) a (m2,b2).

Další dva pánové pomohli Marcovi s praktickým využitím těchto cílených kolizí k tvorbě certifikátů pro různé klíče s jedním (stejným) podpisem certifikační autority. Samozřejmě, že podpis CA je stejný, vždyť podepisuje MD5 haš od těla certifikátu, který je připraven ve formě (m1,b1) a (m2,b2). Začátky zpráv m1 a m2 jsou údaje z certifikátů, které chceme měnit, například jméno, e-mail a sériové číslo, zatímco libovolnou část ostatních údajů můžeme ponechat stejnou. Konce zpráv (b1,b2) se tvoří tak, aby zasáhly místo, kde je v certifikátu uložen veřejný klíč daného člověka (modul RSA).

Ve výsledku se dostanou dvě těla certifikátů, která mají libovolné stejné a libovolné různé položky na začátku těla certifikátu a různý veřejný klíč RSA na konci těla certifikátu a přitom stejný podpis certifikační autority. Umožňuje to připravit si dva klíče RSA pro dva různé lidi a dostat na ně jeden certifikát od certifikační autority. To je trochu nebezpečné… Podrobné informace naleznete na domácí stránce projektu.

Skutečně vytvořené certifikáty na různé klíče mají tyto vlastnosti:

  • Jsou standardní podle normy X.509.
  • Jsou kolidující, tj. jejich tělo má stejnou MD5 haš.
  • Jsou vydány na různé identity. První je na jméno (položka Common Name) Arjen K. Lenstra, druhý na jméno Marc Stevens. Odlišují se i ve jménu organizace. Tyto změny odlišují předchozí kolidující certifikáty, které zněly na stejná jména jejich držitelů.
  • Jsou platné
  • Nejsou podezřelé (kolize je skryta v modulu, tj. v nijak nepodezřelém čísle)
  • Obsahují bezpečné klíče RSA

Poznamenejme pro úplnost, že klíče zatím trochu podezřelé jsou, protože nyní tato metoda neumí kolizi u krátkých modulů, jako je například 2048 bitů, ale potřebuje dlouhý modul – konkrétně 8192 bitů. Právě při jeho tvorbě také došlo k miniaturní chybičce, kdy u jednoho modulu nenastavili správně nejvyšší bit (je to první bajt řetězce birthday bits, b2). Tím je jeden modul o tři bity kratší. Striktně řečeno to chyba je, ale některé DER dekodéry to v praxi nepoznají. Obsáhlé vysvětlení je ve zprávě na www.win.tue.nl (PDF), opravdu neznamená nic podstatného, je to opravitelná věc, a můžeme uvažovat, že certifikáty jsou platné se vším všudy.

Autorům blahopřejeme!

Další informace ke kolizím a MD5 najdete na cryptography.hy­perlink.cz.

Vlastimil Klíma, nezávislý kryptolog

Našli jste v článku chybu?
3. 11. 2006 21:36
trin (neregistrovaný)
V tom pripade bych rad vedel, proti jakemu ceskemu zakonu takovyto bod smlouvy stoji.
30. 10. 2006 20:48
K danému certifikátu neumíme efektivně najít druhý certifikát, jejichž těla mají stejný hašovací kód. K danému hašovacímu kódu neumíme efektivně najít zprávu, která na něj vede. Složitost takového postupu je dnes totiž řádově 2^128 pro MD5. Něco jiného je kolize. Tam není nic daného, tam si útočník vše volí sám. Jinými slovy, prolomit "jednocestnost" neumíme, prolomit "bezkoliznost" umíme. Ukládání hesel pomocí MD5 tedy ohroženo není. Doporučuje se ovšem solení (obrana p…