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

[Mirek Prýmek]

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.

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.

Pokud zkombinuju nekonečné množství hashovacích funkcí (jako ty), tak hashovací funkci nutně NEDOSTANU, protože obor hodnot může být nekonečný. Poznámka, že funkce, která není hashovací, nemusí mít kolize, je triviální a nebylo potřeba to zdůrazňovat.

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.

Nemohla, protože hashovací funkce neporovnává dva soubory - má jenom jeden parametr.

Ledaže bysme měli předem pevně daný soubor A a tahle hashovací funkce by potom byla "je X shodné s A?"

...takže všechno se to točí jenom kolem toho, jestli nám jde o nalezení kolize k jednomu předem danému vstupu, nebo se bavíme obecně.

[Reklama]

[Mirek Prýmek]

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

[DgBd]

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

[DgBd]

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ší.

[DgBd]

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

[Reklama]

[Mirek Prýmek]

Je otázka, čemu říkáš "zkombinuju konečné množství".

No udělám nějakým způsobem funkci z nějakého KONEČNÉHO množství jiných funkcí. Jak, to je úplně jedno. Například tak, že jejich výstup zřetězím. Důležité je, že z konečného množství funkcí, které všechny mají konečný obor hodnot, nemůžu žádným způsobem (pokud se nepletu) dostat funkci s nekonečným oborem hodnot.

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

To ale právě není hashovací funkce. To je funkce identita. A hashovací není proto, že nemá konečný obor hodnot.

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

Něco takového bych očekával, ale každopádně prosté doplnění nulami to asi nebude:

Kód: [Vybrat]

# python -c 'print "\x00",' | md5
8f7cbbbe0e8f898a6fa93056b3de9c9c
# python -c 'print "\x00\x00",' | md5
a4dd23550d4586aee3b15d27b5cec433


[DgBd]

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

To ale právě není hashovací funkce. To je funkce identita. A hashovací není proto, že nemá konečný obor hodnot.

Tak to jsi nepochopil, co jsem myslel tou jednobitovou funkcí. Tato funkce je definovaná třeba takto f(x)=63. bit souboru x. Tj. identita na 63. bitu souboru. Obor hodnot této funkce je {0,1}. Z definice je to tedy hashovací funkce, protože zobrazuje libovolně velký soubor na konečný obor hodnot.

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

Něco takového bych očekával, ale každopádně prosté doplnění nulami to asi nebude:

Kód: [Vybrat]

# python -c 'print "\x00",' | md5
8f7cbbbe0e8f898a6fa93056b3de9c9c
# python -c 'print "\x00\x00",' | md5
a4dd23550d4586aee3b15d27b5cec433


To se nevylučuje, protože MD5 provádí nějaké operace s vnitřními konstantami.

[Mirek Prýmek]

Tak to jsi nepochopil, co jsem myslel tou jednobitovou funkcí. Tato funkce je definovaná třeba takto f(x)=63. bit souboru x. Tj. identita na 63. bitu souboru. Obor hodnot této funkce je {0,1}. Z definice je to tedy hashovací funkce, protože zobrazuje libovolně velký soubor na konečný obor hodnot.

Ale pochopil. Jenže když těchto funkcí (které JSOU hashovací) - jak jsi psal - zkombinuju nekonečně mnoho, abych mohl porovnávat všechny bity libovolně dlouhých souborů, tak dostanu funkci identita, která hashovací není.

To se nevylučuje, protože MD5 provádí nějaké operace s vnitřními konstantami.

No každopádně ať provádí co chce, nefunguje tak, že by vstup doplnil (zepředu) nulami.

[Karel]

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.

Tady pozor na význam slova "kolize". Taková funkce jich má naopak příliš mnoho, protože vám dokážu vygenerovat obrovské množství souborů, které budou mít stejný hash. A sice s hodnotou 1. Váš příklad není z kategorie hashovacích funkcí, ale spíše jde o generátor srovnávacích dat. Můžete udělat i složitější věci, jako generovat Mandelbrotovu množinu s nějakými parametry, čímž z pár čísel uděláte klidně TB relativně náhodných dat, se kterými pak můžete porovnat vstupní soubor. Jenže v tu chvíli ověřujete shodu souboru proti datům vygenerovaným vámi zvoleným kódem. Hash funkce ale dělají opak - pro libovolný vstupní soubor generují řádově kratší kód.