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

Vlastimil Klíma 25. 10. 2006

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?
Podnikatel.cz: Zůstat na Heurece je čiré bláznovství

Zůstat na Heurece je čiré bláznovství

120na80.cz: Cestovní nevolnost. Co pomůže?

Cestovní nevolnost. Co pomůže?

Podnikatel.cz: Babiš představil daňovou revoluci Moje daně

Babiš představil daňovou revoluci Moje daně

DigiZone.cz: ČRa hodnotí pilotní 4K vysílání

ČRa hodnotí pilotní 4K vysílání

Měšec.cz: Udali ho na nelegální software a přišla Policie

Udali ho na nelegální software a přišla Policie

DigiZone.cz: Slováci první, Češi třetí. Krásný...

Slováci první, Češi třetí. Krásný...

Vitalia.cz: 7 receptur z pohanky. Svědčí zdraví

7 receptur z pohanky. Svědčí zdraví

Vitalia.cz: Epidemie: Klíšťová encefalitida po ovčím sýru

Epidemie: Klíšťová encefalitida po ovčím sýru

120na80.cz: Léky a dietní opatření při kopřivce

Léky a dietní opatření při kopřivce

DigiZone.cz: ČTÚ květen: rušení TV vysílání narůstá

ČTÚ květen: rušení TV vysílání narůstá

DigiZone.cz: Robinsonův ostrov moderuje Novotný

Robinsonův ostrov moderuje Novotný

Vitalia.cz: Máte chutě? Nejezděte do světa, ale do Dobřichovic

Máte chutě? Nejezděte do světa, ale do Dobřichovic

DigiZone.cz: Noxon iRadio 1 W bude za pár měsíců

Noxon iRadio 1 W bude za pár měsíců

Lupa.cz: Vzali věc, která fungovala, a přidali internet

Vzali věc, která fungovala, a přidali internet

DigiZone.cz: Kanály Novy na Slovensku oficiálně?

Kanály Novy na Slovensku oficiálně?

Lupa.cz: Nej aplikace? Vodafone, Mozkovna, Záchranka

Nej aplikace? Vodafone, Mozkovna, Záchranka

DigiZone.cz: HbbTV KinoSvět: už jede na dalších TV

HbbTV KinoSvět: už jede na dalších TV

Podnikatel.cz: Chce s trdelníky ovládnout Asii. Poznejte ho

Chce s trdelníky ovládnout Asii. Poznejte ho

DigiZone.cz: Kritické poznámky k DVB-T2

Kritické poznámky k DVB-T2

Lupa.cz: Text umírá, na webu zbude jen video

Text umírá, na webu zbude jen video