Jak udělat soubor s konkrétním kontrolním součtem

PCnity

  • *****
  • 685
    • Zobrazit profil
    • E-mail
Re:Jak udělat soubor s konkrétním kontrolním součtem
« Odpověď #45 kdy: 05. 01. 2012, 21:45:34 »
Ide cisto o to ze pokial mas zdrojove subory velke 2^niekolko miliard a hash sumu velku 2^128 musis mat kolizie. A stojim si za vyjadrenim ze aj ak pouzijes vela hashovacich funkcii, vzdy najdes koliziu nakolko je moznosti na strane vstupnych dat relativne nekonecno.

A ak sa mi teraz niekto bude snazit oponovat, vlastne chce tvrdit ze niekolko TiB zdrojovych dat by vedel bestratovo komprimovat na 2^128 bitov... Kedze by podla neho nedoslo ku kolizii, bolo by mozne z tych 2^128 bitov presne dostat spat vstupne data [ano, hash, ale hoci aj brute forcovanim]. Lenze tak to proste NIE JE. Pretoze mapujes mnozinu n na mnozinu m, pricom plati ze mnozina n < m, cize to nemoze byt 1:1 ale 1:X, cize to X vyjadruje pocet roznych vstupnych dat ktore vypluju tu istu kontrolu sumu.

Preto hovorim ze najdes koliziu VZDY a je uplne jedno kolo hash funkcii pouzjes, pretoze ratame s 2 premisami:

1) Vstupne data mozu byt nekonecne velke
2) Kontrolne sumy musia byt RADOVO mensie

Pokial vyhodis jednu z tych 2 podmienok, nemusia existovat kolizie. Pokial tie podmienky zachovas, MUSIA existovat kolizie.


PCnity

  • *****
  • 685
    • Zobrazit profil
    • E-mail
Re:Jak udělat soubor s konkrétním kontrolním součtem
« Odpověď #46 kdy: 05. 01. 2012, 21:49:22 »
Este k P=NP... Samotny dokaz alebo fakt ze P by sa rovnalo NP este dieru do sveta neurobi... A nie nesuhlasim ze by potom bolo hladanie kolizii lahsie. Ono to len dokaze ze existuje sposob ako to spravit lahkym. Ten sposob by vsak aj tak prov neikto musel vynajst. A nakolko sa dodnes naslo vela security expertov co dokazali ze daky algoritmus nie je dobry aj bez toho aby bolo dokazane ze P=NP alebo opak, nic by to nezmenilo.

DgBd

  • ****
  • 282
    • Zobrazit profil
    • E-mail
Re:Jak udělat soubor s konkrétním kontrolním součtem
« Odpověď #47 kdy: 05. 01. 2012, 21:53:04 »
Ide cisto o to ze pokial mas zdrojove subory velke 2^niekolko miliard a hash sumu velku 2^128 musis mat kolizie. A stojim si za vyjadrenim ze aj ak pouzijes vela hashovacich funkcii, vzdy najdes koliziu nakolko je moznosti na strane vstupnych dat relativne nekonecno.

A ak sa mi teraz niekto bude snazit oponovat, vlastne chce tvrdit ze niekolko TiB zdrojovych dat by vedel bestratovo komprimovat na 2^128 bitov... Kedze by podla neho nedoslo ku kolizii, bolo by mozne z tych 2^128 bitov presne dostat spat vstupne data [ano, hash, ale hoci aj brute forcovanim]. Lenze tak to proste NIE JE. Pretoze mapujes mnozinu n na mnozinu m, pricom plati ze mnozina n < m, cize to nemoze byt 1:1 ale 1:X, cize to X vyjadruje pocet roznych vstupnych dat ktore vypluju tu istu kontrolu sumu.

Preto hovorim ze najdes koliziu VZDY a je uplne jedno kolo hash funkcii pouzjes, pretoze ratame s 2 premisami:

1) Vstupne data mozu byt nekonecne velke
2) Kontrolne sumy musia byt RADOVO mensie

Pokial vyhodis jednu z tych 2 podmienok, nemusia existovat kolizie. Pokial tie podmienky zachovas, MUSIA existovat kolizie.

Tys už viděl nekonečný soubor?
 ;D

PCnity

  • *****
  • 685
    • Zobrazit profil
    • E-mail
Re:Jak udělat soubor s konkrétním kontrolním součtem
« Odpověď #48 kdy: 05. 01. 2012, 21:53:43 »
/dev/urandom

PCnity

  • *****
  • 685
    • Zobrazit profil
    • E-mail
Re:Jak udělat soubor s konkrétním kontrolním součtem
« Odpověď #49 kdy: 05. 01. 2012, 21:57:04 »
Ale uplne zbytocne sa chytas prave toho bodu. Nekonecne velke v zmysle, nemam obmedzenie velkosti. Cize GiB, TiB, ... a nasledne ich nasobky ;) By som bol zvedavy ako by mohol existovat sposob ako by si niekolo 100viek Yi [yobi bajtov] vdel nasumovat na < 1 MiB hoci aj 1000kami hashovacich funkcii tak aby si nenasiel ani jednu koliziu. Je to matematicky vylucene.


DgBd

  • ****
  • 282
    • Zobrazit profil
    • E-mail
Re:Jak udělat soubor s konkrétním kontrolním součtem
« Odpověď #50 kdy: 05. 01. 2012, 22:01:45 »
Ale uplne zbytocne sa chytas prave toho bodu. Nekonecne velke v zmysle, nemam obmedzenie velkosti. Cize GiB, TiB, ... a nasledne ich nasobky ;) By som bol zvedavy ako by mohol existovat sposob ako by si niekolo 100viek Yi [yobi bajtov] vdel nasumovat na < 1 MiB hoci aj 1000kami hashovacich funkcii tak aby si nenasiel ani jednu koliziu. Je to matematicky vylucene.

Ne, už to tady píšu pořád dokola. Použiju stejné množství hashovacích funkcí jako je velikost souboru. Takže pro GiB soubory použiju 10^9 hashovacích funkcí. Pro nekonečně velké soubory použiju nekonečné množství hashovacích funkcí. Už je to konečně jasné?

DgBd

  • ****
  • 282
    • Zobrazit profil
    • E-mail
Re:Jak udělat soubor s konkrétním kontrolním součtem
« Odpověď #51 kdy: 05. 01. 2012, 22:02:34 »
Ale uplne zbytocne sa chytas prave toho bodu. Nekonecne velke v zmysle, nemam obmedzenie velkosti. Cize GiB, TiB, ... a nasledne ich nasobky ;) By som bol zvedavy ako by mohol existovat sposob ako by si niekolo 100viek Yi [yobi bajtov] vdel nasumovat na < 1 MiB hoci aj 1000kami hashovacich funkcii tak aby si nenasiel ani jednu koliziu. Je to matematicky vylucene.

Ne, už to tady píšu pořád dokola. Použiju stejné množství hashovacích funkcí jako je velikost souboru. Takže pro GiB soubory použiju 10^9 hashovacích funkcí. Pro nekonečně velké soubory použiju nekonečné množství hashovacích funkcí. Už je to konečně jasné?

přičemž hashovací funkce je jednobitová.

PCnity

  • *****
  • 685
    • Zobrazit profil
    • E-mail
Re:Jak udělat soubor s konkrétním kontrolním součtem
« Odpověď #52 kdy: 05. 01. 2012, 22:03:14 »
Uvedomujes si ale ze tym to cele strati zmysel?
Pretoze suma, resp. v tomto pripade vsetky sumy dokopy budu niekolko nasobne vacsie ako samony zdrojovy subor :D
Akoze... fakt hovadina.

PCnity

  • *****
  • 685
    • Zobrazit profil
    • E-mail
Re:Jak udělat soubor s konkrétním kontrolním součtem
« Odpověď #53 kdy: 05. 01. 2012, 22:04:24 »
Jednobitova... Cize ma obor hodnot = {0, 1}
Cize vsetky sumy dokopy budu presne rovnako veleke ako zdrojovy subor... A naco ti potom su tie sumy?
nema potom vacsi zmysel porovnavat priamo zdrojovy subor bit po bite? :D

DgBd

  • ****
  • 282
    • Zobrazit profil
    • E-mail
Re:Jak udělat soubor s konkrétním kontrolním součtem
« Odpověď #54 kdy: 05. 01. 2012, 22:05:48 »
Jednobitova... Cize ma obor hodnot = {0, 1}
Cize vsetky sumy dokopy budu presne rovnako veleke ako zdrojovy subor... A naco ti potom su tie sumy?
nema potom vacsi zmysel porovnavat priamo zdrojovy subor bit po bite? :D

Jenom vyvracím tvoje tvrzení, že při libovolném množství hashovacích funkcí musí existovat kolize. Není to pravda a napsal jsem to už několikrát, že je to fakticky ekvivalentní srovnání bit po bitu.

PCnity

  • *****
  • 685
    • Zobrazit profil
    • E-mail
Re:Jak udělat soubor s konkrétním kontrolním součtem
« Odpověď #55 kdy: 05. 01. 2012, 22:08:24 »
Len v jednom mieste sme sa vobec nepochoili. Stale ratam s tym ze aj "sucet hashov" musi byt radovo mensi ako zdrojovy subor. Inak je to dost nepouzitelne. A v takom pripade kolizie budu.

DgBd

  • ****
  • 282
    • Zobrazit profil
    • E-mail
Re:Jak udělat soubor s konkrétním kontrolním součtem
« Odpověď #56 kdy: 05. 01. 2012, 22:10:54 »
Len v jednom mieste sme sa vobec nepochoili. Stale ratam s tym ze aj "sucet hashov" musi byt radovo mensi ako zdrojovy subor. Inak je to dost nepouzitelne. A v takom pripade kolizie budu.

Samozřejmě, že je to nepoužitelné. Stejně tak jako neexistuje nekonečný soubor.

Ono totiž vynechání nekonečných souborů vede k tomu, že opravdu může existovat taková kombinace hashovacích funkcí, která nemá kolizi.

JS

Re:Jak udělat soubor s konkrétním kontrolním součtem
« Odpověď #57 kdy: 05. 01. 2012, 22:52:58 »
Len v jednom mieste sme sa vobec nepochoili. Stale ratam s tym ze aj "sucet hashov" musi byt radovo mensi ako zdrojovy subor. Inak je to dost nepouzitelne. A v takom pripade kolizie budu.

Cela ta diskuse zacala tim, ze se tazatel chtel branit proti "vsem" hashovacim funkcim. Tedy lze predpokladat, ze proti nekonecne mnozine takovych funkci, nebo alespon, ze nebude dopredu vedet, jakou hashovaci funkci "obrance" zvoli (tj. chtel najit kolizi jeste pred tim, nez obrance zvolill hashovaci funkci).

Samozrejme, z pohledu nekoho, kdo vi co je hashovaci funkce, to muze byt silne naivni. Ale tazatel se ptal naivne, a proto nelze predpokladat, ze vidi, v cem je ten problem.

..|..

Re:Jak udělat soubor s konkrétním kontrolním součtem
« Odpověď #58 kdy: 05. 01. 2012, 23:08:48 »
PCnity: Pro nektery vstupy kolize nemusi existovat. Uvazujme trivialni hashovaci funci, ktera vstup 42 zahashuje na 0 a jakykoliv jiny na 1. Potom pro vstup 42 zadnou kolizi nikdy nevymyslite.

PCnity

  • *****
  • 685
    • Zobrazit profil
    • E-mail
Re:Jak udělat soubor s konkrétním kontrolním součtem
« Odpověď #59 kdy: 06. 01. 2012, 00:14:56 »
PCnity: Pro nektery vstupy kolize nemusi existovat. Uvazujme trivialni hashovaci funci, ktera vstup 42 zahashuje na 0 a jakykoliv jiny na 1. Potom pro vstup 42 zadnou kolizi nikdy nevymyslite.

Huh... Pravda. Real world scenarion je sice trochu mimo, ale chapem wo co go. Dokonca ked nad tym rozmyslam z tejto strany tak by mohla existovat aj "hashovacia funkcia" co overi uplne presne data 1:1 a ma vysledok len 0 alebo 1. Sice je to uplne pritiahnute za vlasy, ale cisto teroreticky by to slo.
Cize vysledok je asi taky ze je to dakde v strede. Univerzalne hasovacie funkcie urcene na kontrolne sumy dat budu mat kolizie nakolko to vychadza z ich natury, ale pokial by kombinovali s urcitymi specifickymi, mohlo by sa vyhnut kolizii.