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