Spojení hashovacích funkcí

Ovrscout

Re:Spojení hashovacích funkcí
« Odpověď #15 kdy: 01. 02. 2016, 17:02:40 »
Trochu si zateoretizuju :)
Není to dobrý nápad
Viz: http://crypto-world.info/klima/2005/cryptofest_2005.htm#_Toc98987112
Mno, v tom paragrafu se mi trochu motá kaskáda a řetězení, ale na začátku je jasně napsáno že u řetězení je složitost o něco více než součet složitosti pro jednotlivé funkce. tj. přidáním(zřetězením) druhé hashovací funkce nedochází ke snížení.

Takže, jestli to chápu správně, dva spojené hashe dávají do budoucna lepší výsledek pokud by došlo k teoretickému fatálnímu prolomení jednoho z hashů, nadruhou stranu při použití jednoho hashe který bude mít velikost výstupu jako ty dva dohromady je teoreticky mnohem těžší najít nějakou kolizi(tady spíš odhaduji, kdyžtak mne někdo opravte). Navíc pokud nebude prolomení fatální(ale spíš jenom takové to částečné zjednodušení jak se čas od času objevuje), jeden velký hash bude nejspíše stále bezpečnější než dva kratší.


Kit

Re:Spojení hashovacích funkcí
« Odpověď #16 kdy: 01. 02. 2016, 17:03:36 »
Pokud existuje riziko prolomení MD5 nebo SHA-1, tak jediným rozumným řešením je použití jiného a lepšího algoritmu.

Byla zde zmíněna sada algoritmů SHA-2. Doporučuji vydat se touto cestou.

Re:Spojení hashovacích funkcí
« Odpověď #17 kdy: 01. 02. 2016, 17:25:42 »
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.
OK. Na tom, že nedokážeme pro daný hash generovat kolize, mohou záviset hodnoty v řádech třeba desítek milionů amerických dolarů. Potenciálnímu útočníkovi se útok vyplatí tehdy, pokud jeho náklady jsou nižší než ta hodnota. Předpokládám tedy, že jste schopen zapůjčit hardware a potřebné prostředky v hodnotě alespoň jednotek milionů amerických dolarů. (Protože pokud to nedokážete s menším rozpočtem, nebude to znamenat, že by to nedokázal někdo s větším rozpočtem.)

Abych věděl, že tu jen tak neplácáte, předveďte, že máte vůbec nějaký výkon k dispozici. Chcete porovnávat MD5+SHA-1 s čistým SHA-1 – tak předveďte, že máte dostatečný výkon alespoň na výpočet kolizí SHA-1. Máte SHA-1 hash 0d495a55e421d7c352cb0dfb3b9069aa00734bc8 pro vstup Hynek Vilem Jarmila (kódovaný v ASCII), najděte jiný kolizní vstup, který má stejný SHA-1 hash.

Pokud by se vám to náhodou nepodařilo, já to s dovolením nebudu považovat za důkaz toho, že SHA-1 je bezpečná.

Ivan

Re:Spojení hashovacích funkcí
« Odpověď #18 kdy: 01. 02. 2016, 17:33:36 »
A na co ten hash potrebujes? Potrebujes bezpecny hash algoritmus anebo funkci pro hash tabulku? Existuji i jine hashvovaci algoritmy, napr FNV.


Re:Spojení hashovacích funkcí
« Odpověď #19 kdy: 01. 02. 2016, 19:10:50 »
anebo funkci pro hash tabulku
MD5+SHA-1 má 128+160 bitů, to by byla slušná tabulka. Jestli máte tolik místa na disku, nenašel by se tam malilinkatý kousíček volného prostoru pro mne? Že bych si tam zazálohoval celý internet…


nnnsas

Re:Spojení hashovacích funkcí
« Odpověď #20 kdy: 01. 02. 2016, 23:11:16 »
Zdravim,

Taka asi hlupa otazka:
Hashe maju problem v koliziach a v pripade ze nejaky hash ich ma lahko a vela tak sa da povazovat za zly, spravne?

A casom md5, sha1 atd.. Proste nie su standardami.

Ok a chapem nadsenie matematikov hladat lepsie a lepsie riesenia ale (a to viem ze kedze to tak nie je tak to asi neni riesenie, skor ma zauima vysvetlenie) co tak proste kombinacia dvoch hashov?

Md5(data)&&Sha1(data)?

Nemusel by potom utocnik hladat taky utok ktory by nasiel koliziu v dvoch na sebe nezavyslych hashovacich algorytmoch? Je vobec mozne najst takuto koliziu?

A nevyhody su ako?
- cas
- dlzka kontrolneho stringu

Je to vsetko?

Dik

Ak je kod pristupny(open source, teda aj ked nieje open source mozes pouzit) tak sa pouziva universal hashing. Dvojite hashovanie je ti nanic v praxi stoji ta to viac ako ziskas, pozrel by som sa na universal hashing. Z teorie pravdepodobnosti su algoritmy rovnako bezpecne ale v praxi sa asi ocakava ze pouzivas universal hashing(tj utocnik ma mozno vyhodu). Taktiez ak neheshujes hesla tak 128 bitov je zvacsa moc na kluc. Ak hashujes hesla tak md5 itak nepouzivas. A dvojity hash ti tam vobec nepomoze.

Teda pouziv universal hashing :)

nnnsas

Re:Spojení hashovacích funkcí
« Odpověď #21 kdy: 01. 02. 2016, 23:19:30 »
Trochu si zateoretizuju :)
Není to dobrý nápad
Viz: http://crypto-world.info/klima/2005/cryptofest_2005.htm#_Toc98987112
Mno, v tom paragrafu se mi trochu motá kaskáda a řetězení, ale na začátku je jasně napsáno že u řetězení je složitost o něco více než součet složitosti pro jednotlivé funkce. tj. přidáním(zřetězením) druhé hashovací funkce nedochází ke snížení.

Takže, jestli to chápu správně, dva spojené hashe dávají do budoucna lepší výsledek pokud by došlo k teoretickému fatálnímu prolomení jednoho z hashů, nadruhou stranu při použití jednoho hashe který bude mít velikost výstupu jako ty dva dohromady je teoreticky mnohem těžší najít nějakou kolizi(tady spíš odhaduji, kdyžtak mne někdo opravte). Navíc pokud nebude prolomení fatální(ale spíš jenom takové to částečné zjednodušení jak se čas od času objevuje), jeden velký hash bude nejspíše stále bezpečnější než dva kratší.

Problem je ked utocnik poznas funkciu. Povedzme ze prva hash funkciu ma O(N) a druha O(N) a povedzme ze to celene je O(3*N). V tomto pripade je v pohode ak mas 2N kolizii v jedhom kosiku (Tj 2N hodnost sa nahashuje na to iste miesto), a mas to rovnako rychle. Co je velmi nepravdepodne ak utocnik nepozna algoritmus co pouzicas (druha moznost je ze hashujes vela hodnot do malo kosikov ale tu ti ziadna hash funkcia nepomoze). Druha hash funkcia je nanic salting spravi to iste z pohladu utocnika(ak nepozna co pouzivas a ak pozna tak universal hashing je cesta) Tj MD5(data +'salt') je rovnako beznecne ako AND dvoch hashov a rychlejsie v kazdom pripade. 

Kolemjdoucí

Re:Spojení hashovacích funkcí
« Odpověď #22 kdy: 01. 02. 2016, 23:38:55 »
Máte SHA-1 hash 0d495a55e421d7c352cb0dfb3b9069aa00734bc8 pro vstup Hynek Vilem Jarmila (kódovaný v ASCII), najděte jiný kolizní vstup, který má stejný SHA-1 hash.

Ten SHA-1 hash máte špatně, správně je to pro daný vstup cfc59e2641c7d71f2e47040ad9352d1b98e648f1.

nnnsas

Re:Spojení hashovacích funkcí
« Odpověď #23 kdy: 01. 02. 2016, 23:44:15 »
https://www.schneier.com/blog/archives/2005/02/cryptanalysis_o.html

Najist to najdes. Otazka je ci ti to za to stoji :)

 "Over the course of the competition, some 331,252 users participated by allowing their unused processor cycles to be used for key discovery. After 1,757 days (4.81 years), a participant in Japan discovered the winning key."

nnnsas

Re:Spojení hashovacích funkcí
« Odpověď #24 kdy: 01. 02. 2016, 23:47:05 »
Ono zakonite overlap musi existovat ked hashujes nekonecne vela stringov do konecneho priestoru (160 bitov), teda je ich nekonecne vela.

ByCzech

Re:Spojení hashovacích funkcí
« Odpověď #25 kdy: 02. 02. 2016, 01:20:01 »
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.
OK. Na tom, že nedokážeme pro daný hash generovat kolize, mohou záviset hodnoty v řádech třeba desítek milionů amerických dolarů. Potenciálnímu útočníkovi se útok vyplatí tehdy, pokud jeho náklady jsou nižší než ta hodnota. Předpokládám tedy, že jste schopen zapůjčit hardware a potřebné prostředky v hodnotě alespoň jednotek milionů amerických dolarů. (Protože pokud to nedokážete s menším rozpočtem, nebude to znamenat, že by to nedokázal někdo s větším rozpočtem.)

Abych věděl, že tu jen tak neplácáte, předveďte, že máte vůbec nějaký výkon k dispozici. Chcete porovnávat MD5+SHA-1 s čistým SHA-1 – tak předveďte, že máte dostatečný výkon alespoň na výpočet kolizí SHA-1. Máte SHA-1 hash 0d495a55e421d7c352cb0dfb3b9069aa00734bc8 pro vstup Hynek Vilem Jarmila (kódovaný v ASCII), najděte jiný kolizní vstup, který má stejný SHA-1 hash.

Pokud by se vám to náhodou nepodařilo, já to s dovolením nebudu považovat za důkaz toho, že SHA-1 je bezpečná.

Vy to nechápete viďte. Jakýkoli výkon je vám momentálně úplně k ničemu, protože nenajdete možnost kolize takové, která bude pro oba algoritmy stejná. Pokud tvrdíte, že někdo takovou kolizi umí vypočítat, dodejte relevantní podklady, já proto rád zajistím potřebný HW.

Re:Spojení hashovacích funkcí
« Odpověď #26 kdy: 02. 02. 2016, 07:14:40 »
Vy to nechápete viďte. Jakýkoli výkon je vám momentálně úplně k ničemu, protože nenajdete možnost kolize takové, která bude pro oba algoritmy stejná. Pokud tvrdíte, že někdo takovou kolizi umí vypočítat, dodejte relevantní podklady, já proto rád zajistím potřebný HW.
Vaše tvrzení vychází z předpokladu, že nedokážeme v rozumném času hledat kolize pro dané hashovací funkce. Jenže lidé, kteří tomu rozumí, tenhle předpoklad pro MD5 a SHA-1 už nepovažují za splněný. 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. To, že by to běžným postupem trvalo nepoužitelně dlouho, je irelevantní – to samé platí i pro MD5 i SHA-1 samotné. Jenže pro MD5 a SHA-1 byly vymyšleny „zkratky“, jak to generování kolizí podstatně urychlit. Nikdo nezkoumal, zda takové zkratky neexistují i pro MD5+SHA-1 – takže je bláhové spoléhat na to, že neexistují.

Původní otázka zněla, proč se MD5+SHA-1 nepoužívá, na to je odpověď jednoduchá – protože tu máme SHA-2 a další moderní hashovací funkce, u kterých víme, jak jsou asi bezpečné. Vedle toho je tu návrh na použití MD5+SHA-1, o jehož bezpečnosti nevíme vůbec nic, za to víme, že ty dvě složky mají slabiny, z toho MD5 vážné, takže o spojení takových prvků si nelze myslet nic dobrého.

Tazatel se možná ptal také na to, proč se další hashovací algoritmy vytvářejí. Proč se v době, kdy MD5 a SHA-1 byly ještě považovány za dost silné udělala soutěž na SHA-2, proč pak byla otevřena soutěž na SHA-3 a hashovací algoritmy vznikají stále nové. Na to je odpověď podobná – kombinaci MD5+SHA-1 nikdo nezkoumal, ale protože ji tvoří dvě oslabené hashovací funkce, dá se očekávat, že i to společné použití bude mít slabiny. A poč by se kryptologové zabývali hledáním praktických děr u něčeho, o čem si myslí, že nejspíš děravé bude, když místo toho mohou raději prověřovat funkce, kterým dnes věří.

Gdhsjskksks

Re:Spojení hashovacích funkcí
« Odpověď #27 kdy: 02. 02. 2016, 10:34:34 »
Tu originalny autor:
(asi by som sa mal uz konecne zaregistrovat)

Kazdopadne - ano dakujem sa skvelu diskusiu, jasne nesiel som vynajst koleso a viem ze su lepsie algoritmy a su super :) mna to len zauimalo.

Co som myslel tym && bolo concatenate dvoch hashov. Nie XOR, ani hash hashu ale proste len dva hashe vedla seba.

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

Priklad:
Vstup ASCI:
oliver
MD5: acae273a5a5c88b46b36d65a25f5f435
SHA-1: c539153ba1f947bd4b6f910263b967c4a0a62357

Moj navrh:  acae273a5a5c88b46b36d65a25f5f435c539153ba1f947bd4b6f910263b967c4a0a62357
(proste som ich spojil)

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

Opat dakujem za diskusiu, mal som len strasne nutkanie sa o to podelit... :)

Gdhsjskksks

Re:Spojení hashovacích funkcí
« Odpověď #28 kdy: 02. 02. 2016, 10:39:48 »
Este raz dakujem za fakt dobre vstupy :) ok suhlasim ze sa tym nikto nezapodieval, a preco aj ano ak:
- su casti teoho napanu povazovane za prelomene
- su stale schopny hladat nove a lepsie funkcie :)

Oki chapem, a dakujem. :)

Som rad ze som aspon nelezal tak uplne mimo ze som bol hodny akurat odpluvnutia :)

ByCzech

Re:Spojení hashovacích funkcí
« Odpověď #29 kdy: 02. 02. 2016, 11:10:42 »
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í?