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

Lupa.cz: Jak EET vidí ajťák aneb Drahá vražda UX

Jak EET vidí ajťák aneb Drahá vražda UX

120na80.cz: Zjistěte, zda je vaše klíště infikované

Zjistěte, zda je vaše klíště infikované

DigiZone.cz: Nová pravidla EK pro AV slu­žby

Nová pravidla EK pro AV slu­žby

Vitalia.cz: Syndrom PC vidění: stačí dvě hodiny denně

Syndrom PC vidění: stačí dvě hodiny denně

120na80.cz: Vyzrajte na návaly a pocení v přechodu

Vyzrajte na návaly a pocení v přechodu

Lupa.cz: Zaplatíme ti, když ti seženeme práci

Zaplatíme ti, když ti seženeme práci

Lupa.cz: Nová podoba Instagramu? Katastrofa

Nová podoba Instagramu? Katastrofa

120na80.cz: Jak si udržet zdravou vaginu

Jak si udržet zdravou vaginu

DigiZone.cz: ČT neskončí s nízkým rozlišením podle plánu

ČT neskončí s nízkým rozlišením podle plánu

Vitalia.cz: Před, nebo po snídani? Kdy je lepší čistit si zuby

Před, nebo po snídani? Kdy je lepší čistit si zuby

DigiZone.cz: DAB+ versus FM, ČRo a ČRa proti APSV

DAB+ versus FM, ČRo a ČRa proti APSV

Vitalia.cz: Ministerstvo: tyto příbory jsou nebezpečné

Ministerstvo: tyto příbory jsou nebezpečné

120na80.cz: 10 nej přípravků na holení

10 nej přípravků na holení

Lupa.cz: Přenos hokeje padal kvůli útoku, tvrdí O2

Přenos hokeje padal kvůli útoku, tvrdí O2

DigiZone.cz: T-Mobile je na datovou smršť připraven

T-Mobile je na datovou smršť připraven

DigiZone.cz: Konec geoblokace? Ani náhodou…

Konec geoblokace? Ani náhodou…

Vitalia.cz: 7 nemocí očí, které musíte léčit včas

7 nemocí očí, které musíte léčit včas

Vitalia.cz: SÚKL: vakcíny jsou bezpečné a s autismem nesouvisí

SÚKL: vakcíny jsou bezpečné a s autismem nesouvisí

Vitalia.cz: Sója a rakovina

Sója a rakovina

Vitalia.cz: Proč máme prasklý chléb nejraději?

Proč máme prasklý chléb nejraději?