Obsahuje:
  • všechny e-ziny od 9/1999
  • celou databázi NEWS
  • soutěže 2000-2011
  • další články a BONUSY

Crypto - News

http://crypto-world.info

Crypto - News | Security - News

09 / 2004
Vybrali pro vás: TR - Tomáš Rosa, JP - Jaroslav Pinkava, PV - Pavel Vondruška, VK - Vlastimil Klíma

Objasnění k nepřesnostem v článku v Crypto-worldu k prolomení hašovacích funkcí

16.09.2004
Článek Hašovací funkce v roce 2004 v Crypto-worldu č.9/2004 od Jaroslava Pinkavy z PVT se zabývá hašovacími funkcemi. Samozřejmě, že hašovacími funkcemi nejvíce zamával čínský útok na Rump Session konference Crypto 2004 v srpnu t.r., od něhož se odvinuly diskuse k hašovacím funkcím a jejich bezpečnosti a budoucnosti. Právě tento výsledek je však v článku špatně interpretován, a to v klíčové myšlence kolizí MD5 (odstavec 6). Přitom chybná interpretace je opakována na čtyřech místech v odstavci 6, takže nejde o přehlédnutí. Pokusím se tedy o vysvětlení. Čínští výzkumníci přišli s metodou, jak nalézt kolize dvou různých 1024bitových zpráv, a dělají to tak, že nejprve naleznou dvě různé 512bitové půlzprávy M1, M2, což jim trvá cca hodinu, a potom k nim naleznou dvě různé 512bitové půlzprávy N1, N2 (což trvá už jen sekundy) tak, že složené zprávy (M1, N1) a (M2, N2) mají stejnou haš. Dokonce uvádí předpis, jak se první poloviny M1 a M2 těchto komponovaných zpráv mají lišit a jak se druhé poloviny N1 a N2 mají lišit. Právě jedním z překvapení útoku bylo že konstanty, o které se první a druhé poloviny liší, jsou k sobě inverzní. Hlavní myšlenkou útoku tedy bylo za prvé najít takovou zvláštní konstantu C, za druhé během první hodniny útoku nalézt zprávu M1 tak, že M1 a M2 = M1+ C vedou při hašování na určitý různý kontext (mezivýsledek hašování) ale tak, že tato diference je srovnána při hašování druhých půlek zpráv N1 a N2. První (různé) části zpráv jaksi tedy přihrají sice různé kontexty, ale druhé (různé) části zpráv to srovnají na celkový stejný výsledek, hašový kód, tedy kolizi. Aby byla vidět síla útoku, autoři to dokumentují navíc tím, že po první (hodinu trvající) fázi, kdy naleznou (M1, M2), jsou k ní schopni nalézt více dvojic (N1 a N2), (N1´, N2´), ... vedoucích ke kolizi, tj. h(M1, N1) = h(M2, N2), h(M1, N1´) = h(M2, N2´). Tedy prokazují, že původní různé kontexty dovedou dovést ke stejné haši různými cestami.

Autor článku píše, že ... Na základě výsledku čínských matematiků je možné zkonstruovat dvě zprávy, které se v první části zcela shodují, v druhé se liší a mají přitom týž hash, což konkretizuje vztahem h(M1, N1) = h(M1, N2).
Toto tvrzení jak je vidět kontrastuje s čínskou myšlenkou o nalezení diferenční konstanty C, v níž se první poloviny zpráv liší.

Dále se píše ...V příkladu jsou uvedeny zprávy se shodnou první částí, ale nejedná se o nějakou smysluplnou část, tj. asi skutečně je výsledkem nějakých výpočetních postupů. Pokud by tomu tak nebylo a bylo by z hlediska použité metody např. přímo volit obsah části zprávy, praktický dopad by mohl být více nepříjemný. To je další věc, kterou je potřeba poopravit. Pokud by tomu tak bylo.. lze nahradit Skutečně tomu tak je.. . Číňané jsou schopni tento útok provést s libovolnou inicializační hodnotou, jak ukázali i prohlásili. Mohou si tedy zvolit libovolnou smysluplnou zprávu T a poté k ní konstruovat jak jsou zvyklí M1, N1 a M2, N2 tak, že h(T, M1, N1) = h(T, M2, N2). Autor říká, že ...pak by bylo možné toho využít tak, že útočník získá dokument podepsaný druhou stranou, změní část dokumentu, podpis zůstává týž. , což právě není pravda, neboť útočník musí obě kolidující zprávy vytvářet sám. Čínský útok neumí nalézt k danému dokumentu jiný, se stejnou haší. Umí pouze najít dva různé dokumenty se stejnou haší. Je to přesně rozdíl mezi pojmy V3 a V5 článku.

Mnoho z těchto věcí bylo vyjasněno v diskusi na severu root k článku Hašovací funkce MD5 a další prolomeny!.

Pokud originální článek nemáte, můžete se zdarma k odběru e-zinu zaregistrovat na hlavní stránce crypto-worldu a poté si číslo 9/2004 stáhnout.

Zdroj: http://www.root.cz/clanek/2368
Autor: VK


Design: Webdesign