Spojení hashovacích funkcí

Karel

Re:Spojení hashovacích funkcí
« Odpověď #30 kdy: 02. 02. 2016, 11:33:51 »
Prosím tedy ukažte útok nebo pošlete informace které to potvrzují, pokud tvrdíte, kolize jsou.
Před deseti lety bylo možné kolize MD5 na běžném notebooku generovat v řádu minut.

Já chci vidět útok na soubor, který bude mít předem spočítaný MD5 a SHA1 hash a po útoku bude soubor změněn a OBA vypočítané hashe budou stejné.

Jsem ochoten vám k tomu zapůjčit i výrazně výkonnější HW než byly notebooky před 10 lety.

Ony se tu zaměňují dva různé útoky. To, co uvádíte vy, je snaha k existujícímu souboru vygenerovat klon s jiným obsahem ale stejným hashem. To je skutečně stále velmi obtížné.

Jenže on existuje i jiný typ útoku: vygeneruji vám dva soubory s různým obsahem, které budou mít stejný hash. A tenhle útok je díky kolizím řádově rychlejší. I tady přímo na root.cz o tom byly články s příkladem, jak to zneužít.

Rozdíl je v tom, zda má útočník pod kontrolou jen kopii, nebo i originál. Pokud má k dispozici oboje, tak vygeneruje dva prakticky stejné dokumenty, lišící se klidně jen jediným bitem. A díky kolizím dokáže ke každému přidat správný "bordel" tak, aby měly stejný hash. Nefunguje v případě "bezbordelových" formátů jako je .txt, ale funguje dobře u věcí jako je .pdf, .png apod., protože do nich je možné naložit bordel skrytý oku uživatele.


ByCzech

Re:Spojení hashovacích funkcí
« Odpověď #31 kdy: 02. 02. 2016, 11:46:48 »
Prosím tedy ukažte útok nebo pošlete informace které to potvrzují, pokud tvrdíte, kolize jsou.
Před deseti lety bylo možné kolize MD5 na běžném notebooku generovat v řádu minut.

Já chci vidět útok na soubor, který bude mít předem spočítaný MD5 a SHA1 hash a po útoku bude soubor změněn a OBA vypočítané hashe budou stejné.

Jsem ochoten vám k tomu zapůjčit i výrazně výkonnější HW než byly notebooky před 10 lety.

Ony se tu zaměňují dva různé útoky. To, co uvádíte vy, je snaha k existujícímu souboru vygenerovat klon s jiným obsahem ale stejným hashem. To je skutečně stále velmi obtížné.

Jenže on existuje i jiný typ útoku: vygeneruji vám dva soubory s různým obsahem, které budou mít stejný hash. A tenhle útok je díky kolizím řádově rychlejší. I tady přímo na root.cz o tom byly články s příkladem, jak to zneužít.

Rozdíl je v tom, zda má útočník pod kontrolou jen kopii, nebo i originál. Pokud má k dispozici oboje, tak vygeneruje dva prakticky stejné dokumenty, lišící se klidně jen jediným bitem. A díky kolizím dokáže ke každému přidat správný "bordel" tak, aby měly stejný hash. Nefunguje v případě "bezbordelových" formátů jako je .txt, ale funguje dobře u věcí jako je .pdf, .png apod., protože do nich je možné naložit bordel skrytý oku uživatele.

S tím samozřejmě souhlasím.)

Akorát upravit soubor tak, aby dával smysl a měl oba hashe ze dvou různých hashovacích algoritmů stejné není možné. A nevíme jestli to je zatím nebo to není možné, protože ty matematické funkce nemají v takovém případě průniky. Pokud má někdo jiné informace, sem s nimi (Jirsák ne, tomu to je jasné i bez relevantních informací).

Re:Spojení hashovacích funkcí
« Odpověď #32 kdy: 02. 02. 2016, 12:04:31 »
Co som tym chcel povedat bolo ako pisali niektory prave to ze, podla mna najst koliziu pre MD5 na fakture ja kludne mozne v rade minut, a mozno aj na SHA-1, ale aby ta KOLIZIA BOLA ROVNAKA pri zmene originalneho vstupu to si neviem predstavit.

A to - to si neviem predstavit :) com chcel len vediet ci mam taku zlu predstavivovst ja :) a niekto vie viac, alebo mam v podstate pravdu, len je to neekonomicke (dva hashe pocitat a spajat -> komplikovanejsie ako jeden dobry) a zbytocne dlhe?.
To si nikdo neuměl představit ani u MD5 nebo SHA-1 – protože řešení hrubou silou pořád znamená otestovat nepředstavitelný počet vstupních dokumentů, než se trefíte do takového, který bude mít stejný hash. Jenže se ukázalo, že není nutné to řešit hrubou silou, že jsou v algoritmech chyby, které umožňují „zkratky“ – umožňují generovat vstupní dokumenty tak, že je vyšší pravděpodobnost, že se trefíte do správného hashe. Samozřejmě je možné, že ty „zkratky“ pro MD5 a SHA-1 jsou navzájem nekompatibilní, že nedokážete generovat vstupní dokumenty, u kterých bude ta vyšší pravděpodobnost jako pro MD5 tak pro SHA-1. Ale také je možné, že takováhle zkratka společná pro MD5 i SHA-1 existuje. A to nikdo nebude riskovat.

No a otazka je ci je toto bezpecne. Nie som matematik a co to som kukal aj online ale ako sa hladaju prelinajuce sa kolizie dvoch hashovych funkcii mi pride velmi velmi narocne :)
Hashovací funkce musí být zaručeně bezpečné na několik let dopředu. Takže u nich neplatí, že pokud není znám žádný prakticky proveditelný útok, jsou považovány za bezpečné – naopak, už jenom pokud panuje podezření, že by mohl existovat nějaký teoretický útok, ta funkce je označena za slabou a je doporučeno přestat ji používat. Přesně to se stalo s MD5 i SHA-1 – ty byly nejprve označeny za slabé a bylo doporučeno přestat je používat, teprve po té byly představeny teoretické koncepty útoků, a na konec praktické útoky. Přičemž u MD5 jsou praktické útoky známy už dost dlouho. U SHA-1 bylo známo oslabení od roku 2005 (pořád to ale bylo málo na provedení praktických útoků), proto byl např. v ČR naplánován přechod na SHA-2 nejpozději k roku 2010, zprávy o tom, že by útok na SHA-1 mohl být prakticky proveditelný jsou až z roku 2015.
Nebo-li praktický útok proti SHA-1 je i dnes velmi náročný a těžko představitelný, přesto se SHA-1 (právem) hromadně opouští. Protože už se SHA-1 nedá věřit. A stejné je to s vaší kombinací MD5+SHA-1 – dnes je takový útok těžko představitelný a pravděpodobně je zatím neproveditelný. Jenže ty dvě výchozí funkce jsou považovány za slabé, tím pádem na nich nikdo nebude stavět něco, co by mělo odolat třeba deset patnáct let.
Nebo si to zkuste představit úplně jinak. Máte dva shnilé pilíře, ani jeden z nich už nedokáže unést most sám o sobě. Můžete je spojit do jednoho a nemáte žádnou konkrétní informaci o tom, že tohle spojení by most neuneslo. A vedle toho máte pilíř, u kterého víte, že shnilý není. Budete věnovat energii na ověření toho, zda most s tím spojením dvou shnilých pilířů opravdu nespadne, nebo ji radši budete věnovat tomu, abyste prověřil, že ten pilíř, který není shnilý, je opravdu v pořádku?

Re:Spojení hashovacích funkcí
« Odpověď #33 kdy: 02. 02. 2016, 12:12:12 »
Když dokážete generovat libovolný počet kolizí, je jasné, že mezi těmi kolizemi budou i takové, které mají stejný hash pro jinou hashovací funkci.

Cite needed. Jirsák řekl, proto to tak musí být :D. Komplex božství?
To triviálně plyne z definice hashovací funkce. Hashovací funkce má na vstupu nekonečnou množinu potenciálních vstupů, na výstupu je konečná množina všech možných hashů dané funkce, její maximální možná velikost je jedním z podstatných znaků dané hashovací funkce (např. u MD5 je to 2128, u SHA-1 2160). Je zřejmé, že při mapování z nekonečné množiny na množinu konečnou musí docházet ke kolizím, dokonce těch kolizí je nekonečné množství.
To, že při nekonečném množství vstupů dostanete na výstupu hashovací funkce kolize, je tak základní znalost, že pokud ji nevíte, nemá vůbec smysl, abyste se do nějaké diskuse o hashovacích funkcích pouštěl.

Re:Spojení hashovacích funkcí
« Odpověď #34 kdy: 02. 02. 2016, 12:20:55 »
Když dokážete generovat libovolný počet kolizí, je jasné, že mezi těmi kolizemi budou i takové, které mají stejný hash pro jinou hashovací funkci.

Cite needed. Jirsák řekl, proto to tak musí být :D. Komplex božství?
To triviálně plyne z definice hashovací funkce. Hashovací funkce má na vstupu nekonečnou množinu potenciálních vstupů, na výstupu je konečná množina všech možných hashů dané funkce, její maximální možná velikost je jedním z podstatných znaků dané hashovací funkce (např. u MD5 je to 2128, u SHA-1 2160). Je zřejmé, že při mapování z nekonečné množiny na množinu konečnou musí docházet ke kolizím, dokonce těch kolizí je nekonečné množství.
To, že při nekonečném množství vstupů dostanete na výstupu hashovací funkce kolize, je tak základní znalost, že pokud ji nevíte, nemá vůbec smysl, abyste se do nějaké diskuse o hashovacích funkcích pouštěl.

Ciste teoreticky: dusledek to neni. Muzes generovat kolize pro nejakou podmnozinu hodnot hashovaci funkce a nikde neni receno, ze ta podmnozina bude mit neprazdny prunik s mnozinou hodnot jine hashovaci funkce. (Prakticky to samozrejme pravda je, protoze hashovaci funkce maji i jine vlastnosti.)


Re:Spojení hashovacích funkcí
« Odpověď #35 kdy: 02. 02. 2016, 12:21:00 »
nevíme jestli to je zatím
Což je dostatečný důvod, proč to nepoužívat. Po roce 2005 také nikdo nevěděl, zda oslabení SHA-1 „o pár bitů“ je konečné, nebo jestli se podaří ho prolomit dál. Ale už ta znalost oslabení, které bylo nedostatečné pro praktický útok, stačilo k tomu, aby byla SHA-1 zavržena.

nebo to není možné, protože ty matematické funkce nemají v takovém případě průniky
To by byly hodně špatné hashovací funkce, kdyby pro nekonečně mnoho vstupů nedávaly náhodně rozložené výstupy, ale takové výstupy, aby se to „nepotkalo“ s tou druhou hashovací funkcí.

Re:Spojení hashovacích funkcí
« Odpověď #36 kdy: 02. 02. 2016, 12:25:38 »
> Ale také je možné, že takováhle zkratka společná pro MD5 i SHA-1 existuje.

MD5 i SHA-1 (i přes různá jména) jsou ze stejné rodiny hashovacích funkcí.

ByCzech

Re:Spojení hashovacích funkcí
« Odpověď #37 kdy: 02. 02. 2016, 12:50:06 »
nevíme jestli to je zatím
Což je dostatečný důvod, proč to nepoužívat. Po roce 2005 také nikdo nevěděl, zda oslabení SHA-1 „o pár bitů“ je konečné, nebo jestli se podaří ho prolomit dál. Ale už ta znalost oslabení, které bylo nedostatečné pro praktický útok, stačilo k tomu, aby byla SHA-1 zavržena.

nebo to není možné, protože ty matematické funkce nemají v takovém případě průniky
To by byly hodně špatné hashovací funkce, kdyby pro nekonečně mnoho vstupů nedávaly náhodně rozložené výstupy, ale takové výstupy, aby se to „nepotkalo“ s tou druhou hashovací funkcí.

Už vidím jak to nekonečno budete řešit :D... A vo tom to je. Ukažte jinak jsou to jen plky.

Re:Spojení hashovacích funkcí
« Odpověď #38 kdy: 02. 02. 2016, 13:19:08 »
Už vidím jak to nekonečno budete řešit :D... A vo tom to je. Ukažte jinak jsou to jen plky.
Klidně si dál používejte SHA-1 s odůvodněním, že na svém domácím počítači nedokážete vygenerovat kolizi, tím pádem je to  bezpečné. Odborníci na kryptografii mají na kryptografické hashovací funkce přeci jen o něco vyšší nároky, než to, co zvládne či nezvládne vaše pécéčko.

ByCzech

Re:Spojení hashovacích funkcí
« Odpověď #39 kdy: 02. 02. 2016, 14:04:20 »
Už vidím jak to nekonečno budete řešit :D... A vo tom to je. Ukažte jinak jsou to jen plky.
Klidně si dál používejte SHA-1 s odůvodněním, že na svém domácím počítači nedokážete vygenerovat kolizi, tím pádem je to  bezpečné. Odborníci na kryptografii mají na kryptografické hashovací funkce přeci jen o něco vyšší nároky, než to, co zvládne či nezvládne vaše pécéčko.

Blik! My se tu bavíme o něčem jiném, víte to?

Re:Spojení hashovacích funkcí
« Odpověď #40 kdy: 02. 02. 2016, 14:28:30 »
My se tu bavíme o něčem jiném, víte to?
Nebavíme. Váš argument „na mém počítači kolize nevygeneruji, tudíž je to bezpečná hashovací funkce“ přece musí platit úplně stejně pro SHA-1 jako pro MD5+SHA-1.

ByCzech

Re:Spojení hashovacích funkcí
« Odpověď #41 kdy: 02. 02. 2016, 14:38:05 »
My se tu bavíme o něčem jiném, víte to?
Nebavíme. Váš argument „na mém počítači kolize nevygeneruji, tudíž je to bezpečná hashovací funkce“ přece musí platit úplně stejně pro SHA-1 jako pro MD5+SHA-1.

Tohle jsem nikdy neřekl. Se lhářem a manipulátorem se tímto odmítám bavit.

Re:Spojení hashovacích funkcí
« Odpověď #42 kdy: 02. 02. 2016, 14:51:48 »
My se tu bavíme o něčem jiném, víte to?
Nebavíme. Váš argument „na mém počítači kolize nevygeneruji, tudíž je to bezpečná hashovací funkce“ přece musí platit úplně stejně pro SHA-1 jako pro MD5+SHA-1.

Tohle jsem nikdy neřekl. Se lhářem a manipulátorem se tímto odmítám bavit.
Tak co tedy chcete dokázat tím svým „Ukažte jinak jsou to jen plky“ nebo „pokud tvrdíte, že někdo takovou kolizi umí vypočítat, dodejte relevantní podklady, já proto rád zajistím potřebný HW“? Myslel jsem, že chcete předvést výpočet těch kolizí.

Gdhsjskksks

Re:Spojení hashovacích funkcí
« Odpověď #43 kdy: 02. 02. 2016, 16:11:50 »
Ondřej Surý: vy ste dal pomerne pekny koment - ze su z podobnej rodiny hashovacich funkcii a toto je nieco co ma zaujima, tieto rodiny. Ze ci je vobec mozne aby mali rovnake prieniky.

Inak teraz ma napadla mozno este debilnejsia otazka k tym hashom.

Je mi jasne ze sa da pridavat bordel (a odoberat, aj ked to je uz tahsie "asi") aby boli kolizie, preco sa o danom dokumente nepusti nejake info ktore neni hashovane, pomerne jenoznacne, a nikto tam nic moc nepomeni?

Co tak pocet bitov HEX? Tam si uz fakt neviem predstavit co by s tym kto narobil...

[input].MD5 + "[input].lenghtInHEX

A keby sme chceli byt uz uplny zialenci tak este k tomu to SHA-1 ....

A najst koliziu, pre input X, kde je znama jeho fixna dlzka MD5 a SHA-1 to by som si kukol :D

Preto ma to napadlo ze niekto pisal ze pri nekonecnom moznosti INPUTU je aj nekonecna moznost kolizii (ok to znie fakt nebezpecne) ale takto by sme input obmedzili na jeho dlzku (pridavat nemoze, uberat nemoze, mozes iba "menit")... A tam by to uz nemuselo byt take easy ani na "silnejsom HW"

A pritom taka blbost... :)

Kit

Re:Spojení hashovacích funkcí
« Odpověď #44 kdy: 02. 02. 2016, 16:45:58 »
Je mi jasne ze sa da pridavat bordel (a odoberat, aj ked to je uz tahsie "asi") aby boli kolizie, preco sa o danom dokumente nepusti nejake info ktore neni hashovane, pomerne jenoznacne, a nikto tam nic moc nepomeni?

Co tak pocet bitov HEX? Tam si uz fakt neviem predstavit co by s tym kto narobil...

[input].MD5 + "[input].lenghtInHEX

Algoritmus MD5 neznám dopodrobna, ale domnívám se, že délka vstupního stringu do něj také vstupuje.

Na kvalitě SHA-1 stojí a padá celý Git. Takže pokud někomu nestačí SHA-1, může jít do SHA-2.