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

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