Hlavní navigace

Vlákno názorů k článku Praktické útoky na digitální podpisy používající hašovací funkci MD5 od polish - Jak moc je pravdepodobne prolomeni, kdyz pouziju ...

  • Článek je starý, nové názory již nelze přidávat.
  • 9. 12. 2004 13:25

    polish (neregistrovaný)

    Jak moc je pravdepodobne prolomeni, kdyz pouziju tri ruzne "prolomene" hash funkce, kde kazdy hash bude mit 256 bitu ?

  • 9. 12. 2004 14:33

    Zdeněk Štěpánek (neregistrovaný)

    Zdravim

    Pravdepodobnost je vzdy 100%, at uz pouzijes jakekoliv prolomene hashe. Tady nejde o procenta le o cas. Jakekoliv hasle sli vzdy lamat hrubou silou, ale casy sli u trivialnich funkci radove do mesicu, u bezne pouzivanych to jsou az roky. To co cinane vymysleli je zpusob jak podstatne tuto za urcitych okolnosti dobu zkratit. to je popsano v puvodnim clanku co vysel pred par mesici. Porad jd epouze o cas, informace maji hodnotu ted, ne az za 10 let az je nekdo rozlusti. U kryptogarfie je to totozne.

    Zdenek

  • 9. 12. 2004 14:42

    Clock (neregistrovaný)

    A šlo by se proti tomu bránit tak, že by člověk před rozbalenim archívu testoval, jestli neobsahuje tu danou "profláknutou" MD5 kolizní posloupnost?

    Jinak samozřejmě je to lezení do domu komínem, korektní je přestat MD5 používat a začít používat něco jiného.

  • 9. 12. 2004 21:55

    jk (neregistrovaný)

    Jo, slo by, dokonce se staci podivat na zacatek. Ale je to naprosto prastene - nekdo mi dokaze, ze typ ciselneho zamku, ktery pouzivam, neni bezpecny, a ze ho dokaze za hodinu lousknout, coz demonstruje konkretnim prikladem. Pri tom vylusti kod 5478. Ja jako opatreni prijmu pravidlo, ze nebudu pouzivat kod 5478. To je tak slabe, ze to nestoji ani za uvahu, natoz to nekam implementovat.

    V mnoha aplikacich ale urcity workaround prece jen existuje - kdyz mi dava neduveryhodna strana neco podepsat, data trochu zmenit, abych znicil pripadnou predpripravenou kolizi.

  • 9. 12. 2004 14:45

    polish (neregistrovaný)

    Asi jsem se spatne zeptal. Predstavuju si, ze prave ten cas pri pouziti tri ruznych hash funkci naroste tak hodne, ze to bude OK.

  • 9. 12. 2004 16:15

    Ondrej Mikle (neregistrovaný)

    No urcite narastie, ale velmi zavisi od typu utokov a analytickych znalosti suvislosti medzi tymi hashovacimi funkciami.

    Ako priklad spolocna kolizia u MD5 a CRC32, co sme robili: pre jeden MD5 kolidujuci par treba hodinu pocitania na ibm p690, kolizia u CRC32 sa da vypocitat na papieri, lebo je to jednoducha linearna funkcia (nie je kryptograficky bezpecna a nie je to ani jej ucel). Ale uz spolocna kolizia potrebuje 16 MD5 kolidujucich parov (16 hodin) + zanedbatelny cas na otestovanie 2^16 sprav na koliziu u CRC32.

    V pripade troch hashovych funkcii H1, H2, H3 s 256-bitovym vystupom, ktore by boli zlomene rovnakym sposobom ako MD5, by vypocet sucasnej kolizie trval dost dlho.

    Pre ilustraciu: Predpokladajme, ze najdenie paru kolidujucich sprav pre H1, H2, H3 (kazdu osobitne) trva hodinu a nie je znama ziadna pouzitelna analyticka suvislost medzi tymi hashovacimi funkciami (tj. ze zostava len brute-force narodeninovym paradoxom).

    Pre sucasnu koliziu H1 a H2 treba vypocitat 128 parov navazujucich sprav, ktore koliduju pre H1, Jouxovou fintou z toho mame 2^128 kolidujucich sprav pre H1, a tie musime otestovat pre koliziu v H2. Zlozitost 2^128 je uz dost, pridanie dalsej kolizie od H3 nam zlozitost este zvysi.

    Ak vsak bude znama nejaka suvislosti medzi jednotlivymi hashovacimi funkciami, celkova zlozitost sa moze rapidne znizit, ale o kolko, to je tazke povedat, pretoze zavisi konkretne na tom, co budeme vediet.

  • 9. 12. 2004 16:31

    Vlastimil Klíma (neregistrovaný)

    Ondra podstatu vysvětlil právě v předchozí odpovědi, jenom to sepišme:

    Uvažujme novou hašovací funkci H(x), která je složena ze tří hašovacích funkcí takto: H(x) = H1(x) || H2(x) || H3(x).

    Nejprve si vysvětlíme první Jouxovu fintu. Pracuje za předpokladu, že u dané hašovací funkce umíme najít kolizi pro libovolnou inicializační hodnotu. První dvojici kolidujících zpráv nalezneme pro IV z definice dané hašovací funkce H. Další IV definujeme jako výsledek právě proběhlého hašování (tj. hodnotu první kolize) a pro tuto hodnotu nalezneme druhý pár kolidujících zpráv. Takto pokračujeme až do k-té dvojice. Nyní můžeme vytvořit celkem 2^k zpráv, majících stejnou haš tak, že z každé z k dvojic zpráv vybereme jednu nebo druhou zprávu a ty zřetězíme (viz snímek 18 prezentace na http://cryptography.hyperlink.cz/2004/Hasovaci_funkce_a_cinsky_utok_MFFUK_2004.ppt).

    Obecně jsme tak se složitostí pouze k* 2^(n/2) získali 2^k kolizí n-bitové hašovací funkce.

    Vezmeme konstrukci H(x) = H1(x) || H2(x) || H3(x) pro tři různé hašovací funkce. Pro jednoduchost nechť mají stejnou délku haše n bitů. Pak se složitostí (n/2)* 2^(n/2) nalezneme Jouxovou metodou 2^(n/2) dvojic H1-kolidujících zpráv, v nichž bude s pstí 1/2 jedna kolize současně i pro H2. Máme tedy dvě zprávy x, pro něž je H1(x) || H2(x) stejná. Složitost je (n/2)* 2^(n/2). Takových dvojic zpráv si nyní vyrobíme n/2 za sebou opět Jouxovým postupem. Složitost je (n/2)* (n/2)* 2^(n/2). Získáme ovšem 2^(n/2) zpráv, v nichž nalezneme s pstí 1/2 jednu dvojici, která má stejnou haš H3(x). Celková složitost pro kolizi H(x) = H1(x) || H2(x) || H3(x) je tak (n/2)* (n/2)* 2^(n/2), pro n = 128 je to 4096 * 2^64. A to je právě druhá Jouxova finta.

    Pokud ovšem umíme nalézt kolizi rychleji než za za složitost 2^64, můžeme uvedený postup i výpočet upravit. Číňani umí nalézt kolizi MD5 za hodinu, MD4 za vteřiny. Takže si to můžete napočítat.

    Uvedený postup platí i pro silné hašovací funkce, třeba pro nalezení kolize MD5(x) || SHA1(x) bychom potřebovali 80 hodin pro 80 kolizí MD5 čínským postupem a poté 2^80 výpočtů SHA-1. Jinými slovy prolomená hašovací funkce do této konstrukce přispívá velmi malou složitostí (zde 80 hodin).