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

Vlastimil Klíma 8. 3. 2005

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:

widgety

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?
DigiZone.cz: Regionální tele­vize CZ vysílá "Mapu úspěchu"

Regionální tele­vize CZ vysílá "Mapu úspěchu"

Měšec.cz: TEST: Vyzkoušeli jsme pražské taxikáře

TEST: Vyzkoušeli jsme pražské taxikáře

Podnikatel.cz: Vytvořte si web sami. Redakční systém Tumblr

Vytvořte si web sami. Redakční systém Tumblr

Lupa.cz: Adblock Plus začal prodávat reklamy

Adblock Plus začal prodávat reklamy

Podnikatel.cz: Dva měsíce na EET. Budou stačit?

Dva měsíce na EET. Budou stačit?

120na80.cz: Co je padesátkrát sladší než cukr?

Co je padesátkrát sladší než cukr?

Vitalia.cz: Test dětských svačinek: Tyhle ne!

Test dětských svačinek: Tyhle ne!

120na80.cz: Pálení žáhy: která jídla ne a co nás uzdraví?

Pálení žáhy: která jídla ne a co nás uzdraví?

Vitalia.cz: Tradiční čínská medicína a rakovina

Tradiční čínská medicína a rakovina

Lupa.cz: Jak se prodává firma za miliardu?

Jak se prodává firma za miliardu?

Vitalia.cz: Tesco nabízí desítky tun jídla zdarma

Tesco nabízí desítky tun jídla zdarma

Vitalia.cz: 5 chyb, které děláme při skladování potravin

5 chyb, které děláme při skladování potravin

Root.cz: Hořící telefon Samsung Note 7 zapálil auto

Hořící telefon Samsung Note 7 zapálil auto

DigiZone.cz: Nova opět stahuje „milionáře“

Nova opět stahuje „milionáře“

Podnikatel.cz: Rohlik.cz testoval roboty pro rozvážku

Rohlik.cz testoval roboty pro rozvážku

DigiZone.cz: Technisat připravuje trojici DAB

Technisat připravuje trojici DAB

DigiZone.cz: Parlamentní listy: kde končí PR...

Parlamentní listy: kde končí PR...

DigiZone.cz: DVB-T2 ověřeno: seznam TV zveřejněn

DVB-T2 ověřeno: seznam TV zveřejněn

120na80.cz: Galerie: Čínští policisté testují českou minerálku

Galerie: Čínští policisté testují českou minerálku

DigiZone.cz: Budoucnost TV vysílání ve Visegrádu

Budoucnost TV vysílání ve Visegrádu