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

Security - News

http://crypto-world.info

Crypto - News | Security - News

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

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

19.03.2006
Vlastimil Klíma, Tunely v hašovacích funkcích: kolize MD5 do minuty

Abstrakt
V tomto příspěvku uvádíme novou myšlenku tunelování hašovacích funkcí. Tunely umožňují nahradit současné metody mnohonásobné modifikace zpráv a exponenciálně zkrátit čas hledání kolizí. Dále popisujeme několik konkrétních tunelů v hašovací funkci MD5. S jejich využitím zkracujeme čas hledání kolize hašovací funkce MD5 z původních osmi hodin na minutu na běžném notebooku (Intel Pentium, 1.6 GHz). Metoda je použitelná pro libovolnou inicializační hodnotu. Tunely mohou být využity k urychlení hledání kolizí i jiných hašovacích funkcí. Metoda byla experimentálně ověřena. Pro demonstraci útoku je připojen zdrojový kód programu.

A něco osobního
Touhle zprávou snad už s MD5 skončím. Stala se téměř neuvěřitelná věc. V sobotu odpoledne jsem právě končil překlad svojí tunelovací metody. Nahrazuje a urychluje mojí původní metodu mnohonásobné modifikace zpráv, kterou jsem objevil před rokem. Když tu přišel mail, že Marc Stevens udělal totéž. No není to tak úplně totéž :-), ale uznejte, že to je pěkná kolize! Asi nejzajímavější je srovnání obou metod. Stručně řečeno Marc vychází z mojí metody mnohonásobné modifikace zpráv. Tunelování víceméně začíná tam, kde možnosti metody mnohonásobné modifikace zpráv končí.

Zvláštní upozornění k programu: jsem špatný programátor, můj program je pouze ilustrativní (je hrozný). Nikoli díky programování, ale díky metodě tunelů, je dvakrát rychlejší než Marcův (mám minimálně stejné nebo lepší časy na dvakrát pomalejším stroji). Marcův je také řádově pomalejší pro jiné inicializační vektory (průměrně to trvá cca 6 minut - tady se právě projevuje rozdíl tunelů a metody mnohonásobných modifikací), ale to nic neubírá na jeho pěkném výsledku.

U MD5 jsem tunely musel pomalu ručně dolovat. Bylo tomu tak proto, že staré diferenční schéma Wangové, na kterém je to postaveno, s žádnými tunely pochopitelně nepočítalo. Trik je v tom, že pravděpodobně půjde navrhnout jiné diferenční schéma, kde budou tunely jak hrom. Návrh jiných diferenčních schémat není problém, problém je skloubení s tunelem. I když to není triviální, mohlo by to jít i u MD5, SHA-1 a SHA-2. V tom jsou tunely perspektivní kryptoanalytickou metodou.

Současně s kryptoanalýzou je vyvíjena národní i mezinárodní aktivita na získání bezpečných hašovacích funkcí. Je potřeba vyvinout zcela nový koncept hašovacích funkcí, na čemž také usilovně pracuji, a z čehož je vlastně tahle práce vedlejší výsledek.

Poznamenávám, že část práce na kolizích pro MD5 vznikla v rámci výzkumného projektu pro Národní bezpečnostní úřad, kterému tímto děkuji za podporu.

Domácí stránka projektu je zde.
Zdroj: http://cryptography.hyperlink.cz/2006/tunely.pdf
Autor: VK



Podívej se na svou síť očima hackera - starší ->>
Design: Webdesign