Server Crypto-World upozornil na nalezení kolize

Server Crypto-World upozornil na nalezení kolize v oblíbeném hešovacím algoritmu MD5 (a několika dalších – MD4, SHA-0, pravděpodobně i SHA-1 aj.).

18.8.2004 09:58 | finn | Zajímavý článek

Komentáře

[Hynek (Pichi) Vychodil]

K čemu je dobré, že text
Ń1ÝĹćîÄi=Żů\/ĘľF~Ť@X>¸űU­4 ôłä%qAQ%č÷ÍÉŮ˝ň7<[ ŃÜA{äŘôZeUŐ5sÇđëý 0)ńfŃ ąu'y0Ő\ë"č­şyĚ\ítËÝ_ĹÓmą› Ř5̧ă
má stejné md5sum jako
Ń1ÝĹćîÄi=Żů\/ĘľF~Ť@X>¸űU­4 ôłä%ńAQ%č÷ÍÉŮ˝r7<[ ŃÜA{äŘôZeUŐ5sGđëý 0)ńfŃ ąu'y0Ő\ë"č­şyL\ítËÝ_ĹÓmą› X5̧ă

I malé dítě po absolvování mateřské školy obor cryptologie, specializace číselná tělesa ví, že každý hash o délce nb má 2^(m-n) kolizí u zpráv délky mb (pro všechna m > n). Nechápu pak slova jako bezkolizní hash a podobné ptákoviny, kterými se uvedené novinky jen hemží. A podobně jsem úžasně překvapen, že z 528 294 531 135 665 246 352 339 784 916 516 606 518 847 326 036 121 522 127 960 709 026 673 902 556 724 859 474 417 255 887 657 187 894 674 394 993 257 128 678 882 347 559 502 685 537 250 538 978 462 939 576 908 386 683 999 005 084 168 731 517 676 426 441 053 024 232 908 211 188 404 148 028 292 751 561 738 838 396 898 767 036 476 489 538 580 897 737 998 336 zpráv dlouhých 1024b, které mají stejný md5sum jako ty dvě uvedené se povedlo najít právě tuto dvojici. Xiaoyun Wang, Dengguo Feng, Xuejia Lai, Hongbo Yu také srdečně blahopřeji.

[finn]

Nikdo nezpochybňuje skutečnost, že kolize existují, zajímavé je jenom to JAK takové kolizní řetězce nalézt jinak než aplikací hrubé síly.

[Michal Marek (twofish)]

A i kolize mezi dvema nesmysly se muze hodit (viz treba http://www.cs.rice.edu/~scrosby/hash/ -- nerikam ze to je pripad MD5, ale nekde se zacit musi ;)).

[unchallenger]

Já tedy nevím.

Když chci autenticitu, podepisuji.

Když chci integritu, používám MD5 a SHA-1. Až někdo zvládne současný cílený útok na oba hashe (jinak než Moorovým zákonem), pokloním se mu až na zem.

Když chci poznávat duplicitní maily, generovat vhodná jména pro thumbnaily souborů (viz TMS), etc., použiji spokojeně MD5, a borci, co hledají kolize, mně naprosto netrápí.

[egg]

To podle OpenPGP jde, vytvořit podpis ze dvou hashů? Nepřišel jsem na to, jak bych to GPG vysvětlil, jedině podepsat zprávu dvakrát. Což by mě teda nebavilo. Ale jinak moc pěknej nápad jak pojistit integritu.

[unchallenger]

U OpenPGP? Měl jsem na mysli obyčejnou kontrolu integrity bez podepisování.

[egg]

Špatně je, že mezi těmi mnoha kolizemi jsou řetězce, které se jen málo liší. Jedna ze zásadních věcí, co se od hashovací funkce očekává, je že malá změna vstupu hodně změní výstup. Takhle by třeba (velmi hypoteticky) mohl někdo přidat do programu backdoor a dát ho na ftp se stejným md5sum.

[egg]

CryptoWorld teď píše: "Navzdory šuškandě se na konferenci Crypto 2004 nic zásadního a závažného proti SHA-1 neobjevilo." A nabízí ji jako východisko z problémů s MD5.