Názory k článku
Praktické útoky na digitální podpisy používající hašovací funkci MD5

Jinou možnost využití jedné známé kolize ukazuje Dan Kaminsky pomocí generování dvou spustitelných programů s rozdílným chováním a shodným MD5 hashem.

Whitepaper: http://www.doxpara.com/md5_someday.pdf
Proof-of-concept: http://www.doxpara.com/stripwire-1.1.tar.gz

O Danovom prispevku som sa dozvedel len vcera z jedneho mailing listu. Moj paper som submitol na eprint.iacr.org 2. decembra, on to publikoval len par dni potom (6. decembra). Dan to nazval 'near collision with MD5 collision' ;-). Aka je asi pravdepodobnost, ze sa taketo nieco moze stat...a stava sa.

Tak tedy dobre, uznavame, ze jste byl prvni a tleskame. Pokud by se snad hralo o nejakou cenu, hlasujeme v zajmu spravedlnosti pro vas. ;-)
Toliko k casovym souvislostem.

No o to nejde, mna skor zaraza to, ze vobec dvaja ludia mozu nieco vymysliet rovnaku myslienku v tom istom case (plus/minus) na uplne inych miestach. Viem ze sa to stava (v historii by sa naslo dost zmienok), ale teda poriadne ma to prekvapilo.

taky jara cimrman toho vymyslel strasne vela subezne s inymi vedcami

Tohle je zvlastni vlastnost reality, deje se to prekvapive casto :)

Ta zakladni myslenka (kolize se umisti do nejake "konstanty" a v predpripravenem programu se testuje hodnota te konstanty) snad musela napadnout kazdeho.

Ale priznavam, ze mne osobne nenapadlo, ze lze chytre vyuzit uz zname kolize s predem danou inicialni hodnotou tak, ze se testovana konstanta umisti do zvlastniho souboru.

... na Danuv prispevek je link v posledni vete :-) , ale takhle extra jsou ty linky lepsi videt. Diky. Mimochodem Dan take dal link na Ondruv clanek na svoji stranku: http://www.doxpara.com/, coz je od nej mile. Ne vzdy se setkate s takovou vstricnosti.

Omlouvám se, asi jsem to tehdy nad ranem v článku nějak přehlédl.

Nevěděl sem že MD5 je na tom až tak špatně jak to vyadá podle tohoto článku.

"Až tak špatně" - kryptografická hešovací funkce u které jsou známé kolize je na tom špatně! Stačí _jediná_ kolize, aby to určitým aplikacím mohlo způsobit problémy, už u u jedné kolize se dá zkonstruovat program, který toho využije, což právě tady ten článek popisuje.

Povšimněte si, že zatím ani není zveřejňen algoritmus hledání kolizí, ale "konkrétní příklad".

Naopak jsou aplikace, kde to vadí relativně méně - například ukládání hesel.

Vsechny hashovaci funkce maji kolize.

jen da moc prace je najit ;) - nebo to spis trva moc dlouho a brutalforce neni zrovna idealni postut.

Potesilo me, ze cesky student predvedl praktickou aplikaci zneuziti na rozdil od Cinanu, kteri jen rekli, ze MD5 je prolomen. Jeho postup ma jeste sve mouchy, ale asi je skutecne zneuzitelny, pokud by se pouzivalo nadale MD5.

No dobre, ale je treba si uvedomit rozdil v obou pracich - zatimco cinska prace je fundamentalni vysledek, druhe je dosti trivialni aplikace toho vysledku do stadia spustitelneho programu. Je to pekna ukazka, ze uz znalost nejake kolize (te, co cinane zverejnili) muze znamenat prakticke problemy. To se obecne vi, ostatne praktickou ukazku napsalo vic lidi temer najednou.

Tim nechci rict, ze to neni dobra prace, ale stavet to do protikladu k cinanum je trochu prastene. Ctenar obou clanku, ktery neni s problematikou dal obeznamen, by se mohl domnivat, ze oboji je asi tak srovnatelne dulezite.

Mate pravdu, ze prace Cinanu je fundamentalni, ale oni nesdelili konkretne, jak ke svemu vysledku dospeli, zatimco Ondrej Mikle uvedl postup, jak ke svemu vysledku (naprosto praktickemu, protoze mit na fakture 250 ci 350 dolaru je rozdil) dosel.

ja len dufam, ze ste si vsimli, ze ide o slovenskeho studenta (nie ceskeho) studujuceho v cechach.

peace :)

Slovak nebo Cech, vsichni jsme jedna rodina ;)

Kdyz chci 10000 zprav ktere maji stejne CRC, vezmu prvni a xoruju na ruzne offsety GP (generacni polynom) cimz zmenim zpravu, ale nezmenim CRC. Ten odstavec o narozeninovem paradoxu nejak nechapu. Teda, ja vim o cem je narozeninovy paradox, ale vim i jak funguje CRC a nechapu proc quli par kolizim musim generovat 2^32/2 zprav abych mel 50% sanci ze je najdu, kdyz to muzu udelat mnohem jednoduseji ne? Nebo sem to nejak nepochopil?

Problem je, ze spravu hocijako zmenit nemozeme, pretoze by sme si pokazili MD5 koliziu a my potrebujeme obe naraz (u MD5 aj u CRC32). Sprava sa musi menit 'kontrolovane'. Tj. najprv zarucit koliziu MD5, az potom CRC32 (a nepokazit pritom MD5).

Poté, co se po počátečním zmatku vyjasnilo, co je a není možné generovat za kolize, tak snad všichni udělali tento jednoduchý závěr:

MD5 nelze použít k ověřování dat, do nichž může zasáhnout nedůvěryhodná strana.

A teď budou vycházet stovky článků vymyšlející různé scénáře. Proč? Mám-li nějaký případ toho obecného tvrzení, tak s velkou pravděpodobností způsob, jak ošidit MD5, někdo najde, na to se mohu celkem spolehnout, nemusím čekat na článek, který popisuje zrovna moji situaci.

Pokud jste cetl puvodni clanek Cinanu, tak oni pouze tvrdi, umime dokazat, ze MD5 neni bezpecny, ale vubec tam neukazuji metodu jak to udelali. Pouze zverejnili dva zcela nepouzitelne datove soubory, ktere maji stejny hash. Tady Ondrej ukazal, ze v realnem case lze smysluplne padelat elektronicke dokumenty, coz je myslim na rozdil od Cinanu neco zcela jineho, a tak si zaslouzi publikovat ve forme clanku. Nezapominejme, ze spousta dosud pouzivaneho softwaru ma v sobe zakomponovan MD5 a neda se s tim v podstate delat nic jineho, nez pouzit novou verzi, ktera MD5 neobsahuje, protoze cela rada produktu neni tak modularni, aby se snadno vymenila MD5 za dosud bezpecnou funkci.

No, kdyz v nejakem programu najdu buffer-overflow, tak to je bezpecnostni chyba, at uz vyrobim exploit nebo necham nejakeho smudlu at ho sepise za me. Tady je to podobne.

I když nejsem žádným znalcem kryptografie, docela chápu, že je možné provést podobný podvod, pokud známe pouze MD5 pakovaného souboru. Pokud ovšem známe a kontrolujeme i MD5 jednotlivých nepakovaných částí, pak snad můžeme být v klidu - nebo ne? I když je jasné, že musí existovat stejná hodnota MD5 pro značné množství řetězců, nepředpodkládám, že je reálné vytvořit řetězec se stejným MD5 a přitom smysluplným a navíc požadovaným obsahem. Mýlím se?

Obecne, mylite se. Temer vzdy je prostor pro pridani nejake "nahodne informace" a zachovani "smysluplnosti".

"Náhodná informace" - není to protimluv?
Tady spíš musím vložit náhodný řetězec DO informace. To je možné tam, kde ho pak mohu vystřihnut (jako v uvedeném příkladu extraktorem), nebo ignorovat. Jinak nemá šanci projít ani jednoduchým validátorem. Existenci dvou různých programů se stejným MD5 (např.) bych opravdu chtěl vidět.

Do programu se daji vkladat komentare, ktere mohou byt zcela nahodne.

"Smlouva číslo 6968423544. Pan X dluzi panu Y 100CZK, coz pripojenym digitalnim podpisem stvrzuje." "Smlouva číslo 9521441221. Pan X dluzi panu Y 1000CZK, coz pripojenym digitalnim podpisem stvrzuje." Doslova toto se s tim, co je dosud zverejneno, neumi, ale az bude znam algoritmus, s vhodne zvolenym formatem zpravy to bude mozne.

V drtive vetsine formatu je dostatek mista, kde zmeny neposkodi smysl, v programech samozrejme taky.

Neviem ci tomu dobre rozumiem, podla mna:

Pre lubovolny n-bitovy hash existuje kolizia na n+1 bitoch. Teda aj pre SHA by bolo mozne zopakovat v clanku popisany posup, alebo nie ? Akurat sa zatial nikomu ,,nechcelo'' hladat dva taketo 161 bitove retazce.

Nerozumieš. Kolize je pro MD5 možné hledat _mnohem rychleji_.

To mi je jasne. (rozumiem tomu tak, ze maju sposob generovania dvojic (s rovnakym hash-om) ale uz nie najdenie paru k existujucemu retazcu)

Ide mi len o to, ze ci v pripade ze mam nejaku koliziu mozem pouzit postup popisany v clanku.

Presne tak. Genericky utok (funkcny na kazdu hashovaciu funkciu) je mozne spravit narodeninovym paradoxom. Ak ma hash n-bitov, tak otestovanim 2^(n/2) sprav mame pravdepodobnost 50%, ze najdeme koliziu. Ale je to vypocetne velmi narocne (pri MD5 2^64 operacii, pri SHA-1 2^80 operacii, zhruba radovo tolko je treba aj pamate na ulozene uz vypocitanych hodnot).

Hashovacia funkcia sa povazuje sa prelomenu, ak sa najde utok, ktory to dokaze pocitat rychlejsie ako genericky utok. Utokov su hlavne dva druhy:

-first order collision: je mozne najst dve spravy s rovnakym hashom (to je prave pripad MD5)
-second order preimage collision - k lubovolnej pevne danej sprave je mozne najst inu spravu s rovnakym hashom

Je jasne, ze second order preimage collision znamena uz uplne zlomenie, ale uz first order bohate staci.

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

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

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.

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.

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

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.

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).

Je nejaka stranka, kde su uverejnene zdrojaky bezpecnych resp. zatial neprekonanych hasovacich funkcii?

V poslednej dobe sa ukazalo (Kelsey, Schneier), ze vsetky sucasne hasovacie funkcie maju vadu v dizajne - iterativny dizajn.

Preimage attack pre n-bitovu hashovaciu funkciu (najdenie spravy N k danej sprave M, kde Hash(M)=Hash(N)) uz nema zlozitost 2^n (ako by sa to pozadovalo), ale k*2^(n/2+1) + 2^(n-k+1), kde vyrobime spravu N dlzky 2^k. Priklad u SHA-1: sprava 2^60 bajtov dlha, treba 2^106 operacii, namiesto povodnych 2^160. Zatial neprakticke z dovodu prilis dlhych sprav, ale poukazuje na zasadnu slabost v dizajne hashovacich funkcii.

Dalsie info:
Prednaska (slajdy) pana Klimu: http://cryptography.hyperlink.cz/2004/Hasovaci_funkce_a_cinsky_utok_MFFUK_2004.ppt
http://cryptography.hyperlink.cz/2004/Hasovaci_funkce_a_cinsky_utok_MFFUK_2004.pdf

Kelsey, Schneier: Second Preimages on n-bit Hash Functions for Much Less than 2^n Work, Eprint Cryptology Archive, http://eprint.iacr.org/2004/304/

Implementacie SHA-1, SHA-256, atd.:
RFC 3174 - US Secure Hash Algorithm 1 (SHA1), http://www.faqs.org/rfcs/rfc3174.html
Crypto++, open source kryptograficka kniznica, www.cryptopp.com

ISO image je mozne zmenit prepisanim prvych 1024 bitov takyto image sa da mountnut, napalit a citat s CD. Netrebe sprievodny spustitelny subor, resp. ten subor je schovany vnutri ISO image.

Jediny format, ktory pouziva sektor 0 (ten uplne prvy, kam to davame), je Macintosh HFS. U ISO 9660 zacina boot sektor na sektore 16 (volume descriptor), prva boot entry je na sektore 17.

KOnečně jsem sehnal logo skupiny CZert na:
http://sweb.cz/neknihy