Hlavní navigace

Nalézání kolizí MD5 - hračka pro notebook

Vlastimil Klíma

Jednou z nejvýznamnějších kryptologických událostí posledních let bylo objevení kolizí pro sérii hašovacích funkcí MD4, MD5, HAVAL-128 a RIPEMD čínským týmem v srpnu 2004. Když jsem zde o tomto výsledku informoval, netušil jsem, že mě o vánocích problém natolik chytne, že mu věnuji další dva měsíce. Výsledkem je, že také umím nalézat kolize MD5 pro jakoukoli inicializační hodnotu, a možná rychleji než Číňani.

Čínský tým (Dr. Wangová a kol., [1]), jak víme, v srpnu 2004 utajili metodu nalézání kolizí a zveřejnili pouze strohá data a informace. V říjnu 2004 se australský tým (Hawkes a kol.) pokusil tuto metodu zrekonstruovat ve skvělé práci [3]. Nejdůležitější „čínský trik“ se nepodařilo objevit, ale na základě dat z [1] bylo dobře popsáno diferenční schéma, kterým uveřejněné čínské kolize vyhovují. Naplnění podmínek tohoto schématu bylo však ještě příliš náročné a výpočetně složitější, než ukazovaly výsledky z [1]. V našem výzkumu jsme také analyzovali dostupná data diferenční kryptoanalýzou. Nalezli jsme cestu, jak generovat kolize prvního bloku 1000 - 2000krát rychleji než čínský tým, což odpovídá nalezení jedné kolize prvního bloku na běžném notebooku za dvě minuty. Čínskému týmu tato fáze trvá jednu hodinu na počítači IBM P690. Naproti tomu byl čínský tým 2 - 80krát rychlejší při vyhledávání kolizí druhého bloku. Obě metody se proto mohou lišit nejen časově, ale i obsahově. Celkově je naše metoda 3 - 6krát rychlejší. Konkrétně nalezení první úplné kolize nám na notebooku (Intel Pentium 1.6 GHz) trvalo pouze osm hodin. Poznamenejme, že naše metoda pracuje pro jakoukoli zvolenou inicializační hodnotu. To je velmi zneužitelné pro falšování podpisů SW balíků nebo padělání certifikátů, jak ukazují některé současné práce ([4], [5], [6]). Ukázali jsme, že vyhledávání kolizí hašovací funkce MD5 je možné provádět na domácím počítači. To by mělo být varováním před dalším používáním této hašovací funkce. V příloze uvádíme nové příklady kolizí MD5 pro standardní a zvolenou inicializační hodnotu. Lze očekávat, že po zveřejnění čínské metody dojde k urychlení hledání kolizí druhého bloku v naší metodě, čímž by se celková časová náročnost vyhledání úplné kolize na notebooku mohla snížit až na dvě minuty.

K nalezení kolizí jsme nepoužili žádný superpočítač, pouze běžné domácí počítače. Autor prováděl své experimenty výhradně na notebooku, kde nalezl jak desetitisíce kolizí prvního bloku, tak i úplné kolize MD5 pro platnou inicializační hodnotu i pro volené inicializační hodnoty. Pro ověření funkčnosti programu jsem také požádali několik přátel o vyzkoušení na jejich domácích počítačích. Za týden experimentování na počátku března tak byly nalezeny desetitisíce kolizí prvních bloků a desítky úplných kolizí.

Další informace nalezenete na domácí stránce projektu.

Literatura

[1] Xiaoyun Wang, Dengguo Feng , Xuejia Lai, Hongbo Yu: Collisions for Hash Functions MD4, MD5, HAVAL-128 and RIPEMD, rump session, CRYPTO 2004, Cryptology ePrint Archive, Report 2004/199, first version (August 16, 2004), second version (August 17, 2004)

[2] Ronald Rivest: The MD5 Message Digest Algorithm, RFC1321, April 1992

[3] Philip Hawkes, Michael Paddon, Gregory G. Rose: Musings on the Wang et al. MD5 Collision, Cryptology ePrint Archive, Report 2004/264, 13 October 2004,

[4] Ondrej Mikle: Practical Attacks on Digital Signatures Using MD5 Message Digest, Cryptology ePrint Archive, Report 2004/356, 2nd December 2004

[5] Dan Kaminsky: MD5 To Be Considered Harmful Someday, Cryptology ePrint Archive, Report 2004/357, 6 December 2004

[6] Arjen Lenstra, Xiaoyun Wang and Benne de Weger: Colliding X.509 Certifi­cates, Cryptology ePrint Archive, Report 2005/067

[7] Vlastimil Klima: Several observations regarding Chinese collisions of MD5, 3rd International Scientific Conference Security and Protection of Information, Brno, Czech Republic, May 3 – 5, 2005, in preparation

Příloha: Příklady

Příklad: Kolize MD5 se standardní inicializační hodnotou IV

IV podle [2]:

context->state[0] = 0x67452301;
context->state[1] = 0xefcdab89;
context->state[2] = 0x98badcfe;
context->state[3] = 0x10325476;

První zpráva:

0xA6,0x64,0xEA,0xB8,0x89,0x04,0xC2,0xAC,
0x48,0x43,0x41,0x0E,0x0A,0x63,0x42,0x54,
0x16,0x60,0x6C,0x81,0x44,0x2D,0xD6,0x8D,
0x40,0x04,0x58,0x3E,0xB8,0xFB,0x7F,0x89,
0x55,0xAD,0x34,0x06,0x09,0xF4,0xB3,0x02,
0x83,0xE4,0x88,0x83,0x25,0x71,0x41,0x5A,
0x08,0x51,0x25,0xE8,0xF7,0xCD,0xC9,0x9F,
0xD9,0x1D,0xBD,0xF2,0x80,0x37,0x3C,0x5B,
0x97,0x9E,0xBD,0xB4,0x0E,0x2A,0x6E,0x17,
0xA6,0x23,0x57,0x24,0xD1,0xDF,0x41,0xB4,
0x46,0x73,0xF9,0x96,0xF1,0x62,0x4A,0xDD,
0x10,0x29,0x31,0x67,0xD0,0x09,0xB1,0x8F,
0x75,0xA7,0x7F,0x79,0x30,0xD9,0x5C,0xEB,
0x02,0xE8,0xAD,0xBA,0x7A,0xC8,0x55,0x5C,
0xED,0x74,0xCA,0xDD,0x5F,0xC9,0x93,0x6D,
0xB1,0x9B,0x4A,0xD8,0x35,0xCC,0x67,0xE3.

Druhá zpráva:

0xA6,0x64,0xEA,0xB8,0x89,0x04,0xC2,0xAC,
0x48,0x43,0x41,0x0E,0x0A,0x63,0x42,0x54,
0x16,0x60,0x6C,0x01,0x44,0x2D,0xD6,0x8D,
0x40,0x04,0x58,0x3E,0xB8,0xFB,0x7F,0x89,
0x55,0xAD,0x34,0x06,0x09,0xF4,0xB3,0x02,
0x83,0xE4,0x88,0x83,0x25,0xF1,0x41,0x5A,
0x08,0x51,0x25,0xE8,0xF7,0xCD,0xC9,0x9F,
0xD9,0x1D,0xBD,0x72,0x80,0x37,0x3C,0x5B,
0x97,0x9E,0xBD,0xB4,0x0E,0x2A,0x6E,0x17,
0xA6,0x23,0x57,0x24,0xD1,0xDF,0x41,0xB4,
0x46,0x73,0xF9,0x16,0xF1,0x62,0x4A,0xDD,
0x10,0x29,0x31,0x67,0xD0,0x09,0xB1,0x8F,
0x75,0xA7,0x7F,0x79,0x30,0xD9,0x5C,0xEB,
0x02,0xE8,0xAD,0xBA,0x7A,0x48,0x55,0x5C,
0xED,0x74,0xCA,0xDD,0x5F,0xC9,0x93,0x6D,
0xB1,0x9B,0x4A,0x58,0x35,0xCC,0x67,0xE3.

Společná haš:

0x2B,0xA3,0xBE,0x5A,0xA5,0x41,0x00,0x6B,
0x62,0x37,0x01,0x11,0x28,0x2D,0x19,0xF5.

Příklad: Kolize MD5 se zvolenou inicializační hodnotou IV

context->state[0] = 0xabaaaaaa;
context->state[1] = 0xaaacaaaa;
context->state[2] = 0xaaaadaaa;
context->state[3] = 0xaaaaaaea;

První zpráva:

0x9E,0x83,0x2A,0x4C,0x95,0x64,0x5E,0x2B,
0x2E,0x1B,0xB0,0x70,0x47,0x1E,0xBA,0x13,
0x7F,0x1A,0x53,0x43,0x22,0x34,0x25,0xC1,
0x40,0x04,0x58,0x3E,0xB8,0xFB,0x7F,0x89,
0x55,0xAD,0x34,0x06,0x09,0xF4,0xB3,0x02,
0x83,0xE4,0x88,0x83,0x25,0x71,0x41,0x5A,
0x08,0x51,0x25,0xE8,0xF7,0xCD,0xC9,0x9F,
0xD9,0x1D,0xBD,0xF2,0x80,0x37,0x3C,0x5B,
0x89,0x62,0x33,0xEC,0x5B,0x0C,0x8D,0x77,
0x19,0xDE,0x93,0xFA,0xA1,0x44,0xA8,0xCC,
0x56,0x91,0x9E,0x47,0x00,0x0C,0x00,0x4D,
0x40,0x29,0xF1,0x66,0xD1,0x09,0xB1,0x8F,
0x75,0x27,0x7F,0x79,0x30,0xD5,0x5C,0xEB,
0x42,0xE8,0xAD,0xBA,0x78,0xCC,0x55,0x5C,
0xED,0xF4,0xCA,0xDD,0x5F,0xC5,0x93,0x6D,
0xD1,0x9B,0x0A,0xD8,0x35,0xCC,0xE7,0xE3.

Druhá zpráva:

0x9E,0x83,0x2A,0x4C,0x95,0x64,0x5E,0x2B,
0x2E,0x1B,0xB0,0x70,0x47,0x1E,0xBA,0x13,
0x7F,0x1A,0x53,0xC3,0x22,0x34,0x25,0xC1,
0x40,0x04,0x58,0x3E,0xB8,0xFB,0x7F,0x89,
0x55,0xAD,0x34,0x06,0x09,0xF4,0xB3,0x02,
0x83,0xE4,0x88,0x83,0x25,0xF1,0x41,0x5A,
0x08,0x51,0x25,0xE8,0xF7,0xCD,0xC9,0x9F,
0xD9,0x1D,0xBD,0x72,0x80,0x37,0x3C,0x5B,
0x89,0x62,0x33,0xEC,0x5B,0x0C,0x8D,0x77,
0x19,0xDE,0x93,0xFA,0xA1,0x44,0xA8,0xCC,
0x56,0x91,0x9E,0xC7,0x00,0x0C,0x00,0x4D,
0x40,0x29,0xF1,0x66,0xD1,0x09,0xB1,0x8F,
0x75,0x27,0x7F,0x79,0x30,0xD5,0x5C,0xEB,
0x42,0xE8,0xAD,0xBA,0x78,0x4C,0x55,0x5C,
0xED,0xF4,0xCA,0xDD,0x5F,0xC5,0x93,0x6D,
0xD1,0x9B,0x0A,0x58,0x35,0xCC,0xE7,0xE3.

Společná haš (hodnota opravena, díky Janu Kasprzakovi):

0xef,0x2e,0xae,0x54,0xe0,0x34,0x70,0x7c,
0xa2,0x6e,0xb0,0x9b,0x45,0xc7,0xe4,0x87.
Našli jste v článku chybu?

8. 3. 2005 12:21

Yenya (neregistrovaný)

No, ja jsem si vzal md5.c z http://theory.lcs.mit.edu/~rivest/md5.c a pote co jsem mu vysvetlil, ze long int nema na mem pocitaci 32-bitu, tak uz mi to vychazi spravne (tedy stejne hashe). Ale u tech druhych dvou zprav je spolecny hash ef2eae54e034707ca26eb09b45c7e487, ne 2c8c2ca7077d24eb769727d53e15d58c. Autor ma v clanku chybu.

9180a371b0f5e9e3961e49b638349cb3, resp. 2c8c2ca7077d24eb769727d53e15d58c vyjde pro treti a ctvrtou zpravu, kdyz zapomenete nastavit ten inicialni vektor na hodno…

8. 3. 2005 12:16

myx (neregistrovaný)
Kolize je srážka - srazí se ti dvě různé zprávy tak, že obě mají stejný hash (kontrolní podpis generovaný na základě obsahu zprávy). Tím, se pak onen podpis stává bezcenným, ptž můžeš jednu zprávu (pravou) nahradit zprávou jinou (falešnou, padělanou) a podpis zůstane stejný.
Podnikatel.cz: Změny v cestovních náhradách 2017

Změny v cestovních náhradách 2017

Podnikatel.cz: K EET. Štamgast už peníze na stole nenechá

K EET. Štamgast už peníze na stole nenechá

DigiZone.cz: Recenze Westworld: zavraždit a...

Recenze Westworld: zavraždit a...

Vitalia.cz: Taky věříte na pravidlo 5 sekund?

Taky věříte na pravidlo 5 sekund?

DigiZone.cz: TV Philips a Android verze 6.0

TV Philips a Android verze 6.0

Podnikatel.cz: Udávání kvůli EET začalo

Udávání kvůli EET začalo

Vitalia.cz: Pamlsková vyhláška bude platit jen na základkách

Pamlsková vyhláška bude platit jen na základkách

Lupa.cz: Insolvenční řízení kvůli cookies? Vítejte v ČR

Insolvenční řízení kvůli cookies? Vítejte v ČR

Měšec.cz: Zdravotní a sociální pojištění 2017: Připlatíte

Zdravotní a sociální pojištění 2017: Připlatíte

Měšec.cz: Kdy vám stát dá na stěhování 50 000 Kč?

Kdy vám stát dá na stěhování 50 000 Kč?

Podnikatel.cz: Chaos u EET pokračuje. Jsou tu další návrhy

Chaos u EET pokračuje. Jsou tu další návrhy

Lupa.cz: Proč firmy málo chrání data? Chovají se logicky

Proč firmy málo chrání data? Chovají se logicky

Podnikatel.cz: Chtějte údaje k dani z nemovitostí do mailu

Chtějte údaje k dani z nemovitostí do mailu

Měšec.cz: U levneELEKTRO.cz už reklamaci nevyřídíte

U levneELEKTRO.cz už reklamaci nevyřídíte

Vitalia.cz: Proč vás každý zubař posílá na dentální hygienu

Proč vás každý zubař posílá na dentální hygienu

Vitalia.cz: Když přijdete o oko, přijdete na rok o řidičák

Když přijdete o oko, přijdete na rok o řidičák

Měšec.cz: Jak vymáhat výživné zadarmo?

Jak vymáhat výživné zadarmo?

Podnikatel.cz: Snížení DPH na 15 % se netýká všech

Snížení DPH na 15 % se netýká všech

120na80.cz: Pánové, pečujte o svoje přirození a prostatu

Pánové, pečujte o svoje přirození a prostatu

Vitalia.cz: Láska na vozíku: Přitažliví jsme pro tzv. pečovatelky

Láska na vozíku: Přitažliví jsme pro tzv. pečovatelky