Příspěvky

196

Software / Re:Jak udělat soubor s konkrétním kontrolním součtem

« kdy: 06. 01. 2012, 09:48:58 »

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

To 2) bych přeformuloval takhle: hashovací funkce dává pro libovolný vstup hash konstantní délky N bitů.

Pro vstup menší než N je totiž hash větší

# echo "x" | md5
401b30e3b8b5d629635a5c613cdb7919

Tady bych byl opatrný s definicí, protože imho MD5 není technicky definována na souborech, které jsou menší než délka výsledného hashe. MD5 patrně doplní malý soubor nulami do nejmenšího možného souboru, na kterém můžeme provádět MD5 operace (512bitový input blok).

197

Software / Re:Jak udělat soubor s konkrétním kontrolním součtem

« kdy: 06. 01. 2012, 09:44:22 »

Takže obránce si klidně může zvolit jednu jednobitovou hashovací funkci, která bude porovnávat pouze jeden jediný bit, ve kterém se dva soubory liší.

Nebo abych byl přesný, tak "nebude porovnávat jediný bit", ale ta hashovací funkce bude identita na jediném bitu, kde se ty dva případné soubory, u kterých chceme kolizi, liší.

198

Software / Re:Jak udělat soubor s konkrétním kontrolním součtem

« kdy: 06. 01. 2012, 09:42:08 »

O žádné nekonečné soubory přece nejde. Jde o to, že každá hashovací funkce má konečný obor hodnot a tedy i nějaké N takové, že mezi soubory velikosti N zaručeně existuje kolize.

Pokud zkombinuju konečné množství hashovacích funkcí, dostanu opět hashovací funkci.

Je otázka, čemu říkáš "zkombinuju konečné množství". Autor původního příspěvku chtěl jednu věc: pro libovolnou hashovací funkci chtěl kolizi. Přičemž nebylo na něm, jakou hashovací funkci si obránce zvolí. Takže obránce si klidně může zvolit jednu jednobitovou hashovací funkci, která bude porovnávat pouze jeden jediný bit, ve kterém se dva soubory liší. A tím pádem kolizi nedostaneme nikdy ani pro jednobitovou hashovací funkci. Protože pokud je na libovůli ochránce volba hashovací funkce, tak má k dispozici nekonečné množství takových funkcí.

199

Sítě / Re:DNS a presmerovanie na inú doménu II. rádu

« kdy: 06. 01. 2012, 01:49:46 »

K přístupu na web je možné použít i normální A záznam, ikdyž CNAME je flexibilnější (kdyby se náhodou rozhodli změnit IP adresu, tak tě to nijak nezasáhne).

Ono se totiž jméno v GET/POST requestu nepřekládá, takže když zadám http://neco.mojedomena.cz/, tak serveru dojde taky požadavek na stránku http://neco.mojedomena.cz/.

200

Software / Re:Jak udělat soubor s konkrétním kontrolním součtem

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

201

Software / Re:Jak udělat soubor s konkrétním kontrolním součtem

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

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.

202

Software / Re:Jak udělat soubor s konkrétním kontrolním součtem

« 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á.

203

Software / Re:Jak udělat soubor s konkrétním kontrolním součtem

« 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é?

204

Software / Re:Jak udělat soubor s konkrétním kontrolním součtem

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

205

Software / Re:Jak udělat soubor s konkrétním kontrolním součtem

« kdy: 05. 01. 2012, 21:26:35 »

Dodatok: A je uplne jedno ci pouzijes jednu alebo x hashovacich funkcii!

Ne, když použiju n jednobitových hashovacích funkcí, tak nemůže dojít ke kolizi, protože tato operace je ekvivalentní srovnání dvou souborů bit po bitu.

206

Software / Re:Jak udělat soubor s konkrétním kontrolním součtem

« kdy: 05. 01. 2012, 20:52:29 »

Je uplne jedno kolko a akych metod sa pouzije. Kym plati ze kontrolna suma je radovo mensia vstupne data, nutne musi existovat kolizia. Zaroven nemoze existovat obrana.

Chci vidět důkaz :-)

Já mám protidůkaz: mějme množinu hashovacích funkcí Hn(x), kde Hn(x)=n-tý bit vstupu x. Pak jistě platí, že Hn(x)!=Hn(y) pro všechna n z intervalu 1..len(x). Prostě ty funkce to zkontrolují bit po bitu. QED. (formální důkaz nechám na někoho jiného)

Takže váš výsledný hash je stejně dlouhý jako vstupní soubor (čímž porušujete předpoklad, že hash je menší než vstupní data). Pak je metoda opravdu neprůstřelná. Jenže, proč se tedy obtěžovat hashem, když se stejně jedná o porovnání 1:1?

Někteří lidi tady tvrdili, že při libovolné kombinaci různých hashovacích funkcí je možné najít takovou kolizi, že nebude možné ty soubory rozlišit. Já jsem na jednoduchém příkladu n jednobitových hashovacích funkcí dokázal, že to není pravda. Ano, funkčně je to porovnání bit po bitu. Ale k vyvrácení tvrzení to stačí.

207

Software / Re:Jak udělat soubor s konkrétním kontrolním součtem

« kdy: 05. 01. 2012, 17:35:40 »

Chci vidět důkaz :-)

..hash ma danou delku, rekneme 1 znak. znak muze nabyvat rekneme 5 hodnot. staci vzit 6 ruznych souboru a mas kolizi

Pro jednu funkci. Ne pro n funkcí.

208

Software / Re:Jak udělat soubor s konkrétním kontrolním součtem

« kdy: 05. 01. 2012, 17:32:16 »

Je uplne jedno kolko a akych metod sa pouzije. Kym plati ze kontrolna suma je radovo mensia vstupne data, nutne musi existovat kolizia. Zaroven nemoze existovat obrana.

Chci vidět důkaz :-)

Já mám protidůkaz: mějme množinu hashovacích funkcí Hn(x), kde Hn(x)=n-tý bit vstupu x. Pak jistě platí, že Hn(x)!=Hn(y) pro všechna n z intervalu 1..len(x). Prostě ty funkce to zkontrolují bit po bitu. QED. (formální důkaz nechám na někoho jiného)

209

Software / Re:Jak udělat soubor s konkrétním kontrolním součtem

« kdy: 05. 01. 2012, 17:15:47 »

Je uplne jedno kolko a akych metod sa pouzije. Kym plati ze kontrolna suma je radovo mensia vstupne data, nutne musi existovat kolizia. Zaroven nemoze existovat obrana.

Chci vidět důkaz :-)

210

Software / Re:Jak udělat soubor s konkrétním kontrolním součtem

« kdy: 05. 01. 2012, 17:11:58 »

Je uplne jedno kolko a akych metod sa pouzije. Kym plati ze kontrolna suma je radovo mensia vstupne data, nutne musi existovat kolizia. Zaroven nemoze existovat obrana.

Ta kolize imho nemusí existovat. Řekněme, že H1 bude mít obor funkce v lichých číslech a H2 v sudých číslech. Tam opravdu nemůže nastat situace kdy H1(x)=H2(x)

eh, zapomeňte na to, napsal jsem blbost.