Hashovací funkce SHA-1 je již od roku 2011 odmítaná NISTem, ale její slabiny byly dosud jen teoretické.
Výzkumníci z Google užívající předchozí výsledky z CWI a Microsoftu publikovali první veřejně známou kolizi. Za pomoci 110 GPU by trvalo její hledání rok, což je více než stotisíckrát rychlejší než by byl útok hrubou silou.
Obranou je nahradit zastaralý algoritmus některou novější alternativou.
Kolize má samozřejmě své stránky a logo.Tato zprávička byla zaslána čtenářem serveru Root.cz pomocí formuláře Přidat zprávičku. Děkujeme!
Melo by to castecne platit, ale prislusny kod zverejni az s odstupem.
Dali k dispozici i nejaky tool, co overi, zda dokument jevi znamky toho, ze na nej byla podobna metoda pouzita (t.j. overi, ze je "rizikovejsi" z hlediska existence kolize, aniz by tu kolizi meli v ruce).
Jak byvaji loga a stranky pro chyby nepravem vysmivana, tak tady je videt uzitecnost - FAQ toho obsahuji celkem dost, vcetne trebas otazky "a co na to git?"
Jak jsem ale psal, na odvození některých dalších kolizí není potřeba se s tím takto počítat, stačí troška algebry k Merkle–Damgård funkcím.
Konkrétněji, když ta dvě PDF porovnám přes vbindiff, divím, že kolize začíná na pozici 0xC0 (=192) a končí na pozici 0x130 (=320). Obě pozice (ne až tak překvapivě) jsou dělitelné 64, tedy nemusíme nic zarovnávat. Není tedy nic jednoduššího než na obou souborech zavolat head -c320 a… máme další kolizi: https://public.v6ak.com/shattered-trimmed/shattered-1.pdf × https://public.v6ak.com/shattered-trimmed/shattered-2.pdf .
A pokud k oběma souborům něco přiřetězím na konec (k oběma totéž), mám další a další kolize. Teď už je jen otázka, zda takto umím vytvořit užitečnou kolizi, který by splňovala pravidla nějakého formátu, a zároveň se oba soubory něčím zajímavým lišily.
Generovat další – otázka je, jaké. Generovat další je celkem triviální, stačí využít length extension attack. Otázkou ale je, jestli vám takovéto kolize k něčemu budou, protože jejich prefixy budou zmíněné dva soubory, což není moc univerzální způsob generování kolizí…
Stejně by to mělo jít i u SHA-2. S jakoukoliv funkcí náchylou na length extension attack to půjde. (Opačná implikace neplatí.)
Zajímavější mohou být tzv. multikolize, kdy vygeneruju úpravami různých míst stejného textu n kolizí na různých místech, a z toho dostanu 2^n kolizí celkem.
Obě techniky by měly fungovat pro všechny funkce založené na Merkle–Damgård, tedy minimálně MD5, SHA-1 a SHA-2 (SHA256 až SHA512). U SHA-3 to může být jinak (není to Merkle–Damgård, ale sponge construction), ale tady nechci kecat.
Ještě doplním – předpokládám zde kolize o stejné délce. Pro kolize o různé délce nic z toho platit nemusí (a dost možná ani nebude, pokud se do paddingu přidá délka, což se v SHA-1 dělá).
Prakticky vzato ale kolize o rozdílné délce (tzn. hodnoty x, y takové, že h(x) = h(y) && len(x) ≠ len(y)) je obtížnější najít a u SHA-1, kde se přidává délka do paddingu, se možná takové kolize ani nedožiju. Tedy teoreticky jsem se dopustil nepřesnosti, ale prakticky to sedí.
V principu existuje několik typů kolizí. Ta "nejjednodušší" je, že najdu dvě zprávy a řeknu "hle, tyto dvě zprávy mají stejný hash". To je o sobě dost problém, ale ještě se mi musí podařit najít dvě takové zprávy, které dávají smysl a maji patřičný účinek. Například zpráva "prodávám dům za 1 milion" a "prodávám dům za 1 korunu".
Druhý typ kolize pak je, že k jakékoliv zprávě jsem schopen dohledat jinou zprávu se stejným hashem. A samozřejme i zde platí, že ona druhá zpráva musí mít smysl a být k něčemu dobrá. Ideální je, když umím takových zpráv najít hodně (ideálně hodně hodně :-) ) a vyberu z nich tu, která se mi hodí.
Proto jsou často vhodné takové kolize, kde se začátek nějak liší a pak už se to dál shoduje.
U binárních souborů to není tak jednoznačné. Budu mít například to .pdf, ve kterém bude návrh smlouvy, kus scriptu a nějaký balast. Ten kus scriptu se koukne někam na konec balastu a když tam bude XYZ, tak text smlouvy změní na za 1 milion, když tam bude ABC, tak text smlouvy změní na 1 korunu. Ten balast bude na správné pozici obsahovat právě tu kolizi.
Takže budu mít dva skoro stejné .pdf dokumenty, které se budou lišit jen kolizním fragmentem kdesi v balastu, který .pdf čtečka ani nečte. A přesto se dokumenty zobrazí různě. Podobně je to zneužitelné prakticky u každého formátu, kam lze přidat binární smetí (balast s kolizí) a kde může být script, který na základě toho smetí pozmění výstup zobrazení. Což platí pro každý spustitelný soubor a plno dalších formátů.
Takže opravdu není nutné hledat dvě textové zprávy, které budou kolizní a přesto budou dávat smysl.
No pokud se nemylim, tak takoveho zneuziti bych se nebal, pac by jsi musel byt autorem jak prvniho pdf tak ,,upraveneho,, pdf.
V praxi mas spis nejakej pdf (ktereho nejsi autorem) a ktere potrebujes upravit tak aby byla porad steje sha. Takze dle.meho nazoru je sice hezke ze nekdo nalezl kolize ale v realnem svete to rozhodne vetsinou nepouzutelne pro padelani...
Proč by to bylo nepoužitelné? Připravím šifrovací certifikát na své jméno a nechám podepsat jako kvalifikovaný PostSignum. Nicméně mám připravený i kolizní certifikát na tvé jméno. A najednou mám certifikát, kterým můžu tvým jménem třeba posílat příkazy do katastru či si půjčovat v bance.
Autorita nepodepisuje certifikát, ale jen jeho hash. Oba dva certifikáty mají stejný hash, tedy podpis té autority se dá připojit k oběma uvedeným certifikátům a v obou případech bude sedět.
Jenže autorita nepodepisuje přesně to, co jí pošleš. Přidává minimálně sériové číslo, a to už se teď generuje tak, aby nebylo předvídatelné. Tj. certifikáty jsou bezpečné i kdyby se našla kolize SHA-2 (SHA-1 se už dávno nesmí používat).
Samozřejmě by to vyžadovalo autoritu, která to podepíše SHA-1. To už snad žádná neudělá, právě protože SHA-1 není bezpečné.
Co se týče sériového čísla: nevím přesně, jaká jsou pravidla pro jeho vkládání, ale pokud by se vám podařilo přimět autoritu, aby jej vložila do hashovaného bloku bez dat, která se snažíte změnit, tak by stačilo ten blok zkopírovat (varianta length extension attack):
certifikát rozdělený na hashované bloky: pravé CN sériové číslo Pokud mám kolizi pro první blok: podvržené CN Pak podvržené CN sériové číslo bude mít stejný hash jako pravé CN sériové číslo bez ohledu na to, jaké sériové číslo CA vygeneruje
Nebo u toho PDF, stačí, až budeš shánět půjčku, tak připravím PDF, že ti půjčím milión na deset let s úrokem 2 % p.a. Ale zároveň mám kolizní dokument, že jsem od tebe koupil tvůj dům za milión. S tím druhým zajdu na katastr. Hodně štěstí, až se to budeš snažit zneplatnit, milión jsem ti přeci na účet poslal.
Staci ti mnohem min, kdyz zmenis zapis v katastru (coz urcite neni neresitelny), a dotycnej se 3 roky neozve, tak je nemovitost tvoje.
A existujou jeste lepsi postupy, pokud predlozis u soudu splatnou smenku (a zjisti si, jak vypada smenka, pobavis se), tak se proti ni muze dotycnej ohradit tusim max do 3-5 dnu. Takze pokud je zrovna na dovoleny, tak nez staci prijet, je jeho majetek tvuj.
> Takze pokud je zrovna na dovoleny, tak nez staci prijet, je jeho majetek tvuj.
To není nezbytně pravda. Učili nás, že námitky tohoto typu jsou přípustné X dní (týdnů) od chvíle, kdy jsi se o rozhodnutí dozvěděl. Jen se to pak musí řešit zpětně (právnička nám říkala i o zneplatnění měsíc po lhůtě - prokázala, že osoba nebyla v ČR a nemohla tudíž přebírat poštu).
2MarSik:
Jenze to je ti houby platny ... ty samozrejme uspejes expost s namitkou, ze ses nemoh odvolat protoze si nevedel, ale tvuj majetek je mezi tim uz v trapu, a muzes se vesele 10 let soudit.
Jo a pro ten katastr to neplati. Soudruzi posranci to totiz presne takhle schvalili - aneb co je v katastru je pravda i kdyby to pravda nebyla, a bordel v evidenci statu si mas hlidat sam.
A voiala, buresovo novinka, pokud do 5 dnu nesdelis financaku, ze to co si jim poslal je naprosto vporadku a ze bordel v tom maji leda oni ... dostanes flastr 30k+. Takze kdyz te budu mit rad, zaridim, ze ti ta vyzva prijde v den tvyho odjezdu na 14ti denni zahranicni dovolenou. Po 10 dnech bude doruceno, prijedes v patek, zbyva ti jeden den, ale v sootu a v nedeli mas smolika, takze pondeli a to uz mas 2 dny po terminu == 30k.
Tohle už je klasický problém toho, co člověk podepisuje, když něco podepisuje.A není to zas až tak úplně technický problém a už vůbec ne problém hashovacích funkcí. Klasickým příkladem je bílé písmo na bílem pozadí.
Ten váš příklad se skriptem v PDF by se dal dotáhnout do extrému, kdy mám podepsané PDF a ono si z webu stáhne nový obsah, kterým přepíše ten původní a bude se tvářit, že je podepsaný. Ale právě proto se v PDF podepisují vlastní binární data PDF souboru a je možné si nechat zobrazit přesně tu verzi, která byla podepsaná.
Je jasné, že pro každou hashovací funkci existují kolize, protože množina vstupních dat je řádově mnohem větší než množina výstupních dat, ale nechápu, jak může být třeba taková SHA-1 nebezpečná pro X509 certifikáty. Takový certifikát má přece jasně specifikovanou strukturu s několika povinnými položkami. Je opravdu reálné, že k libovolnému certu s SHA-1 vygeneruji vlastní cert, kde bude stejný podepsaný hash?
Ne k libovolnému, ale to útočník ani nepotřebuje. V případě MD5 ten útok vypadal tak, že vybrali CA s určitými vlastnostmi (přinejmenším sekvenční sériové číslo certifikátu), vystavili certifikát pro svoji domému, a k němu spočítali jiný certifikát pro jinou doménu. Přesně si to už nepamatuju, ale tady jsou podrobnosti: https://www.win.tue.nl/hashclash/rogue-ca/
Nejsem si teď jistý, jestli je možné tento útok replikovat i na SHA-1. Jednak dnes může (ale nemusí) být problém najít vhodnou CA, jednak u MD5 použili AFAIK chosen prefix, což nevím, jestli jde u SHA-1.
Ale přinejmenším je kolize SHA-1 dost velké varování na to, abychom SHA-1 certifikáty nepoužívali. Argument „já to (zatím) neumím“ nestačí. Útoky budou leda horší.
Pokud si dobře pamatuju, tak tam to bylo tak, že pro MD5 exisotval jakýsi "resetovací" blok, tedy to co bylo před ním se anulovalo a hash neovlivnilo. T.j. oni si připravili falešný certifikát tak, že měl začátek shodný jako pravý a nechali si ten pravý vydat s tím, že do nějakého volitelného pole protlačili ten resetovací blok. A tak získali certifikát, který měl stejný podpis, ale jiný obsah....
