Tunely v hašovacích funkcích: kolize MD5 do minuty

Píšu to takhle experimentálně, jinak by se to sem nevešlo. Cílem je vysvětlit, jak je možné najít kolize MD5 do minuty na notebooku. Kdyby se vám to nelíbilo, na domácí stránce projektu je sedmnáctistránkový článek v češtině, který to všechno vysvětluje podrobně a standardně (a taky je tam zdrojový kód programu).

Kolidující zprávy se skládají ze dvou 512 bitových bloků (M, N) a (HM, HN), přičemž MD5(M, N) = MD5(HM, HN). Symbol H používám místo hvězdičky – proměnné můžete tak sledovat v programu. Jsou zpracovávány po 32bitových slovech M = (x[0], …, x[15]) v 64 krocích. V prvním kroku vzniká meziproměnná Q[1], v druhém kroku Q[2] atd. až Q[64] podle následujících rovnic.

Obr. 1: Rovnice pro MD5

Proměnné Q[-3] = IV[0], Q[-2] = IV[3], Q[-1] = IV[2] a Q[0] = IV[1] jsou inicializační hodnotou, buď standardní nebo volenou.

Po 64 krocích je na poslední čtyři proměnné přičtena vstupní hodnota (IV[0..3]) – to je tzv. Davies-Meyerovo zesílení.

Obr.2: výsledek hašování po prvním bloku

Dostáváme výsledek zpracování prvního bloku (intermediate hash value) IHV[0…3]. IHV pak vstupuje do druhého bloku stejně jako IV do prvního bloku a postup se opakuje. Pokusme se udělat vlastní kolizi. Ve zprávě x[0…15] uděláme třeba jednobitovou změnu kdekoli a novou zprávu označíme hvězdičkou jako Hx[0…15]. Chceme, aby IHV a HIHV byly stejné (kolize). Zprávu x můžeme měnit až do Q[16] libovolně nebo si naopak libovolně nastavit Q[1…16]. Pak si ale schéma hraje už samo až do Q[64] a my se na to můžeme jen dívat, jestli náhodou nevyjde IHV[0…3] = HIHV[0…3]. Proměnné HQ startují také ze stejné IV, ale díky jiným Hx[0…15] vedou stejnými (jen ohvězdičkovanými) rovnicemi k úplně jiným HIHV[0…3]. Kdybychom chtěli pohybovat jen s jednou proměnnou, třeba x[0], změna se nám objeví v rovnicích celkem čtyřikrát. Predikovat dopředu, co se stane v Q[49], když v Q[1] změníme x[0] je těžké, protože mezitím tam v každé rovnici proběhnou čtyři aritmetické součty, 96 carry přenosů, rotace, která se nedá rozložit podle pravidla „rotace součtu je součet rotací“ a také nelineární funkce F a G (vůči XOR je AND nebo OR „nelineární“ – „nelze to rozložit“). V 68 rovnicích je pak těchto zábran přes jeden tisíc. Na tom stála bezpečnost MD5, i když to takhle nikde nenajdete napsané.

Nehynoucí zásluha Wangové je, že si všimla, že zmíněné nelinearity nejsou tak nelineární a za určitých podmínek může carry řídit a/nebo vzájemně rušit. Pokud někde nastavíte u proměnné Q[] nějaký bit na nulu, některé carry nevznikne, a potom můžete použít pravidlo „rotace součtu je součet rotací“. Tím vznikly tzv. postačující podmínky (což jsou právě podmínky na jednotlivé bity Q) plus diferenční cesta, tj. to, jak se budou lišit proměnné Q a jejich změněná dvojčata HQ, neboli jak se budou měnit jejich diference při postupu schématem. Postačující podmínky vidíte na obrázku (pro ušetření místa jsou tam také přidané barevné tunýlky).

Obr.3: Postačující podmínky a extra podmínky pro první blok (extra podmínky jsou zvýrazněny)

Teď uděláme tyhle tři (aritmetické) změny
Hx[ 4] = x[ 4] + 0×80000000,
Hx[11] = x[11] + 0×0000800,
Hx[14] = x[14] + 0×80000000.

Při hašování Hx vznikají budou vznikat podle výše uvedených rovnic hvězdičkované proměnné HQ a HIHV. A teď ta finta. Pokud budou splněny postačující podmínky výše (PP), budou se HQ vyvíjet podle naší tzv. diferenční cesty, velmi ukázněně takto:

Obr.4: Diferenční cesta

Jak vidíme, nedosáhli jsme na konci kolize, neboť HIHV[ 0…3] a IHV[0..] nejsou stejné. Nevadí, jsou hodně podobné. Podobným postupem s použitím druhého bloku tyhle vstupní diference srovnáme. Je to kupodivu lehčí úloha než u prvního bloku, kde začínáme ze stejných hodnot a vedeme je k různým hodnotám, než u druhého bloku, kde různé vstupy vedeme na stejné výstupy. Takže kolizní zprávy se budou vždycky skládat ze dvou bloků.

Zbývá dobře nastavit postačující podmínky a je vystaráno. (Wangová publikovala chybné postačující podmínky, což zbrzdilo mnoho týmů ve výzkumu.)

Pokud se podíváte na PP na obrázek, postačujících podmínek je jen pro Q[1…16] skoro 300. Pokud je naplníme tím, že tyto hodnoty zvolíme, je tím plně určena zpráva x[0…15] a tudíž hodnoty Q[17..64] a IHV[0..3] jsou plně určeny. Zda to pak platí, je zcela náhodná záležitost. Pokud hodnoty Q[1] až Q[16] nestanovíme zcela, budou se nám špatně počítat hodnoty Q[17..64] a IHV[0..3], které na nich nelineárně a složitě závisí.

Metoda mnohonásobné modifikace zpráv [Kli05b] [WaYu05] [YaSh05] [SNKO05] [LiLa05] spočívala v tom, že se zvolila náhodně zpráva x[] splňující Q[1…16] a její multimodifikací se krok za krokem naplňovaly podmínky na Q[17…]. Tento proces v různých pracích zprvu končil u Q[18], potom u Q[19] atd. Proč? Protože změny v Q[1…16] nebo v x[0..15] pochopitelně mění všechno od Q[17] nahoru, takže je nutné je dělat tak, aby ty změny nenarušily PP. V současné době je možné se nejdále dostat ke splnění podmínky na Q[24]. V [SNKO05] se tam už „papírově“ dostali, ale chce to ještě doladit. Nicméně tenhle výsledek byl před rokem ještě grálem (Wangová skončila u Q[18], já u Q[20]).

Dejme tomu, že máme splněno Q[24] ale co zbývajících 29 podmínek? Všichni tady končí, a zbývající podmínky se musí už jenom verifikovat, zda nejsou už náhodné. Nazval jsem tenhle bod bodem verifikace (point of verification, POV). Všichni musí získat cca 2²⁹ těchto bodů, aby jeden z nich náhodně splnil oněch 29 podmínek. A je to přece jen dost práce se metodou multimodifikací k tolika bodům POV dostat.

Proto mě napadla myšlenka tunelů. Je jednoduchá. V ideálním případě postačí získat jeden bod POV a pak ho nějak rozmnožit oněch potřebných 2²⁹ POV. Metodu jsem nazval tunelování, protože když to znázorníte graficky v rovnicích, tak to jako tunely vypadá a taky se chová – tunelem můžete projít, aniž by na povrchu (proměnné) něco zjistily.

Ukážeme si jednoduchý, ale ideální a účinný tunel Q9. Pro ty bity i, kde Q[10]i = 0 a současně Q[11]i = 1, vypadne funkce F, a hned máme tunel podle následujícího obrázku.

Obr. 5: Tunel Q9

Na všech bitech i (i = 22, 23, 24) můžeme změnit hodnotu Q[9]i, aniž by to proměnné Q[11] a Q[10] zaregistrovaly. Projeví se v rovnicích pro Q[9], Q[10] a Q[13], ale tyhle proměnné nemůžeme měnit (zatěžuje je ohromné množství PP). Místo toho změníme hodnoty zprávy v x[8], x[9] a x[12] tak, že Q[10], Q[11], Q[12] a Q[13] zůstávají nezměněny. Q[9] měníme jen na těch bitech i, na něž nejsou kladeny žádné PP. Všechny PP zůstanou tedy nezměněny, i když je zpráva x změní (to je ten tunel). Pokud se podíváte, co znamenají změny hodnot x[8], x[9] a x[12], vidíte, že ovlivní vše až za bodem verifikace. Jinými slovy, z jednoho POV získáme celkem zadarmo sedm nových POV. Ušetřili jsme krkolomnou cestu k získání každého takového bodu zvlášť.

Tunely u MD5 nejsou jednoduché, musel jsem je v diferenčním schématu Wangové přímo dolovat. Pochopitelně proto, že to diferenční schéma s žádnými tunely nepočítalo. Pokud by nestačila kolize do minuty, mohlo by se navrhnout diferenční schéma jiné, takové, že by obsahovalo pěkný tunel. Ve volbě diferenčních schémat je celkem pole neorané.

Tunely se tak týkají nejen MD5, ale i SHA-1 a SHA-2. Je pouze otázkou času, zda se podaří najít diferenční schémata s tunely. Pochopitelně jsou i jiné cesty. Tunely jen ukazují, jak slabé operace jsou v současných hašovacích funkcích použité.

Cesta z toho? Přímo mezinárodní horečné úsilí, které nepamatujeme – loni čtyři mezinárodní konference na tohle téma. Letos v létě další. Nějaká východiska už jsou, ale bezpečná hašovací funkce to ještě není. Abych nevypadal jako rozbíječ, poznamenávám, že tohle vzniklo jako vedlejší produkt v rámci mé konstruktivní snahy o návrh hašovací funkce nové generace, u níž bychom měli nesrovnatelně vyšší míru záruky a důvěry v její kvalitu a přesvědčivé důkazy.

Povšimněte si, že u současných hašovacích funkcí nemáme kromě základní filozofie, která je postavená na teorii, žádné důkazy kvality, jen víru v to, že slabě nelineární funkce zachrání to, že se jich použije hodně. A na to také ty funkce dojely a zbylé dojedou.

Poděkování

Část této práce vznikla v rámci jednoho projektu pro NBÚ, kterému tímto děkuji za podporu.

Domácí stránka projektu

cryptography.hy­perlink.cz/MD5_co­llisions.html
Na této stránce najdete zdrojový kód programu, doporučenou literaturu a další informace.