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?
Lupa.cz: Elektronika tajemství zbavená. Jak s ní začít?

Elektronika tajemství zbavená. Jak s ní začít?

Podnikatel.cz: Reverse – charge dopadá na další služby

Reverse – charge dopadá na další služby

Vitalia.cz: Syfilis: To není „nemoc z lásky“

Syfilis: To není „nemoc z lásky“

Lupa.cz: Hackujete? Můžete mít problém sehnat práci

Hackujete? Můžete mít problém sehnat práci

120na80.cz: Bylinka pro dobrý sex. Jaká to je?

Bylinka pro dobrý sex. Jaká to je?

Podnikatel.cz: Česká pošta vycouvala ze služby ČP Cloud

Česká pošta vycouvala ze služby ČP Cloud

Podnikatel.cz: OSA zdraží, ale taky přidá nový poplatek

OSA zdraží, ale taky přidá nový poplatek

DigiZone.cz: Vláda schválila digitální vysílání ČRo

Vláda schválila digitální vysílání ČRo

Podnikatel.cz: Novela zákoníku práce. Řeší homeworking

Novela zákoníku práce. Řeší homeworking

Podnikatel.cz: Mění se pravidla pro rodičovskou

Mění se pravidla pro rodičovskou

Vitalia.cz: Kedlubna, neobyčejná zelenina

Kedlubna, neobyčejná zelenina

Podnikatel.cz: Sami na firemní web: Jak nastavit design?

Sami na firemní web: Jak nastavit design?

Vitalia.cz: Ženy, které milují příliš, jsou neštěstí

Ženy, které milují příliš, jsou neštěstí

Vitalia.cz: Jak pít při sportu

Jak pít při sportu

DigiZone.cz: Prima a vznik slovenského kanálu

Prima a vznik slovenského kanálu

Vitalia.cz: Budou i v Česku GM potraviny bez označení?

Budou i v Česku GM potraviny bez označení?

Lupa.cz: Kdy se Estonec přihlásí k české datové schránce?

Kdy se Estonec přihlásí k české datové schránce?

Vitalia.cz: „Nepřeskakujte“ praktické lékaře

„Nepřeskakujte“ praktické lékaře

Lupa.cz: Měřičům síly hesla se nedá věřit. Víte proč?

Měřičům síly hesla se nedá věřit. Víte proč?

Lupa.cz: Kolín dá čipy na náměstí, do kontejnerů i dětem

Kolín dá čipy na náměstí, do kontejnerů i dětem