Fórum Root.cz

Hlavní témata => Software => Téma založeno: xmms 05. 01. 2012, 11:09:15

Název: Jak udělat soubor s konkrétním kontrolním součtem
Přispěvatel: xmms 05. 01. 2012, 11:09:15
Potřebuju udělat soubor, aby měl konkrétní předem daný kontrolní součet md5 nebo sha.
Mějme např. original.exe s nějakým kontrolním součtem, já ho chci předělat na jiný original.exe a ten součet musí být nakonec stejný. Jsou na to nějaké tooly?
Název: Re:Jak udělat soubor s konkrétním kontrolním součtem
Přispěvatel: smoofy 05. 01. 2012, 11:10:21
Kdyby to bylo tak jednoduche tak by kontrolni soucet nebyl zrovna idealni volba ke kontrole souboru bych rekl.
Název: Re:Jak udělat soubor s konkrétním kontrolním součtem
Přispěvatel: Program 05. 01. 2012, 11:54:30
Náhodně generujte exe soubory a počítejte hash. Během té doby budete mít dost času si nastudovat k čemu jsou vlastně tyto hashovací funkce.
Název: Re:Jak udělat soubor s konkrétním kontrolním součtem
Přispěvatel: v2kt0r 05. 01. 2012, 12:01:42
Potřebuju udělat soubor, aby měl konkrétní předem daný kontrolní součet md5 nebo sha.
Mějme např. original.exe s nějakým kontrolním součtem, já ho chci předělat na jiný original.exe a ten součet musí být nakonec stejný. Jsou na to nějaké tooly?
Aneb: presne k ZABRANENI toho, co se chystate udelat, jsou hashovaci funkce navrzeny (na hashi se ma poznat, ze nekdo se souborem manipuloval. Kdyby kazdy mohl vytvorit svuj vlastni obsah, ktery bude mit predem dany hash, pozbyly by tyto funkce smyslu). Az se vam to povede, efektivne jste hashovaci funkci prolomil.
Název: Re:Jak udělat soubor s konkrétním kontrolním součtem
Přispěvatel: pandula 05. 01. 2012, 12:10:32
Hhh a zamyslel si sa niekedy and tym co vlastne chces? :D Ved to je ako keby si sa nas opytal ze "prosim vas a ako sa to dostanem na ucet bila gatesa? je na to nejaky tool?"

hashovacie funkcie su presne od toho, keby nieco take ako pises bolo v realnom case mozne, tak by MD5 checksumy stratili vyznam ... ved od toho to je - overit ci 1 a 1 subor je ten isty :)

hhh velmi vtipny prispevok :) jo a az sa vam to podari v realnom case a nie len teoreticky (neviem ako je na tom dnes MD5) ale napriklad so SHA tak to postnite niekam na forum vedecke a nobelovka z matiky bude na ceste :)
Název: Re:Jak udělat soubor s konkrétním kontrolním součtem
Přispěvatel: stewe 05. 01. 2012, 12:10:45
no to asi nepojde :D hashovacie funkcie su zalozene prave na tom, ze zmena co i len jedneho bitu na vstupe zmeni vystup na nepoznanie (akoze hash).

idealna hash funkcia by mala mat vlastnosti ako:
a) da sa pomerne efektivne vypocitat hash nejakych dat
b) je "nemozne" generovat data s konkretnym hashom
c) je "nemozne" modifikovat data s tym, ze hash zostane rovnaky
d) je "nemozne" najst dve rozlicne sady dat s tym, ze maju rovnaky hash

ty vlastne chces najst koliziu, tzv. "strong collision resistance", to je o tom, ze ked mas spravu message1, je nemozne najst spravu message2 taku, ze hashe budu rovnake.

to je proste princip na com hashovacie funkcie stoja, inak by boli uplne bezcenne.

takze nie, neda sa to. kolizie existuju ale pravdepodobnost je skoro nula cela nic a vysledne spravy su uplne ine. ked sa najdu kolizie, povazuje sa ta funkcia viac menej za bezpredmetnu a hlada sa dalsia.
Název: Re:Jak udělat soubor s konkrétním kontrolním součtem
Přispěvatel: _diehard 05. 01. 2012, 12:20:28
http://www.mscs.dal.ca/~selinger/md5collision/
Název: Re:Jak udělat soubor s konkrétním kontrolním součtem
Přispěvatel: Karel 05. 01. 2012, 13:03:06
Pokud požadavek změníte na "jak vytvořit dva různé .exe soubory, které budou mít stejné MD5", pak na to již nástroje jsou. Pokud ale chcete podstrčit svůj vlastní .exe tak, aby měl stejný MD5 nebo SHA jako program někoho jiného, pak stále ještě máte naštěstí smůlu. Také bych pak doporučil přeformulovat otázku na "jsou dnes již nástroje na falšování podpisů?" Protože jak vám již jiní psali, ono "kontrolní součet" je technickým opisem správnějšího termínu "podpis souboru" a ono "udělat soubor s konkrétním" není nic jiného než "falšování".
Název: Re:Jak udělat soubor s konkrétním kontrolním součtem
Přispěvatel: branchman2 05. 01. 2012, 13:04:37
U MD5 je take nieco mozne, ak mas povodny subor (pisal o tom Klima aj tu na root.cz: http://www.root.cz/clanky/tunely-v-hasovacich-funkcich-kolize-md5-do-minuty/ (http://www.root.cz/clanky/tunely-v-hasovacich-funkcich-kolize-md5-do-minuty/)). Preto sa MD5 nepovazuje za kryptograficky bezpecny.

U SHA1 sa tusim nasla zatial len zranitelnost, ze je mozne predpovedat 2 bity a teda sa to da stihnut v stvrtinovom case (co je stale dost; chce to skusit radovo 2^126 retazcov)

Inak pre ostatnych posterov: ak nie je kontrolny sucet brany ako kryptograficky bezpecny, tak je uplne v pohode, ze ide spravit iny retazec, ktory ma rovnaky kontrolny sucet. Podstata kontrolneho suctu je, aby to nenastavalo nahodne.
Název: Re:Jak udělat soubor s konkrétním kontrolním součtem
Přispěvatel: xmms 05. 01. 2012, 13:21:43
No vida, tak možné to je. Jen jsem nevěděl, co mám hledat. Takže je to MD5 collision. Dokonce na to existuje program evilize.
Já myslel na něco takového, jako na konec k hotovému souboru (a nemusí to být nutně jenom exe) přidat přebytečná data a jejich generováním postupně zkoušet a hledat stejný součet.

A hlavně zařídit, aby byl stejný pro všechny možné typy kontrolních součtů současně :-)
Název: Re:Jak udělat soubor s konkrétním kontrolním součtem
Přispěvatel: Karel 05. 01. 2012, 13:54:18
To evilize ale funguje právě tím způsobem, že generuje více různých souborů se stejným MD5. Důraz je na to generuje. Pokud už jeden soubor existuje a má nějaký MD5, pak k němu stále ještě nebudete umět vygenerovat dvojníka se stejným MD5. Evilize a podobné SW totiž fungují tak, že k souborům přidají data, díky kterým "sterilizují" kontrolní součet, který pak závisí jen na tom přídavku a ne na původním souboru. Přidáním tohoto přívěsku k vícero souborům tak dostanete vícero souborů se stejným MD5, který bude záviset jen na to přívěsku. Což je k ničemu, pokud se snažíte udělat kopii souboru, který má MD5 spočítanou a zveřejněnou bez vašeho přívěsku.
Název: Re:Jak udělat soubor s konkrétním kontrolním součtem
Přispěvatel: DgBd 05. 01. 2012, 14:00:47
A hlavně zařídit, aby byl stejný pro všechny možné typy kontrolních součtů současně :-)

No, něco takového by bylo asi na nějakou Turingovu cenu nebo Fieldsovu medaili.
Název: Re:Jak udělat soubor s konkrétním kontrolním součtem
Přispěvatel: JS 05. 01. 2012, 14:19:49
A hlavně zařídit, aby byl stejný pro všechny možné typy kontrolních součtů současně :-)

No, něco takového by bylo asi na nějakou Turingovu cenu nebo Fieldsovu medaili.

Spis na poukazku do blazince. :-)
Název: Re:Jak udělat soubor s konkrétním kontrolním součtem
Přispěvatel: DgBd 05. 01. 2012, 14:26:50
A hlavně zařídit, aby byl stejný pro všechny možné typy kontrolních součtů současně :-)

No, něco takového by bylo asi na nějakou Turingovu cenu nebo Fieldsovu medaili.

Spis na poukazku do blazince. :-)

Čistě matematicky: používají se hashovací funkce, které mají nějaké rozumné rozložení kolizí, těch kolizí je pro každý otisk tedy  nekonečné množství. Pokud nejsou dvě hashovací funkce nějak "podobné", tak by měl být průnik těchto kolizí neprázdný. Ale dokazovat bych to tedy nechtěl :-)
Název: Re:Jak udělat soubor s konkrétním kontrolním součtem
Přispěvatel: sdfgsdfg 05. 01. 2012, 14:33:50
Jde to, ale budes to mit na dlouho. V kazdym hashovacim algoritmu je z principu nekonecne mnoho kolizi, takze tobe proste staci, abys pridaval nedulezity data tak dlouho, az to prijde. A ono to prijde. Nicmene treba za stovky let.
Název: Re:Jak udělat soubor s konkrétním kontrolním součtem
Přispěvatel: martin 05. 01. 2012, 14:47:02
něco o kolizích http://bit.ly/AtCknr
Název: Re:Jak udělat soubor s konkrétním kontrolním součtem
Přispěvatel: Mirek Prýmek 05. 01. 2012, 14:51:30
Čistě matematicky: používají se hashovací funkce, které mají nějaké rozumné rozložení kolizí, těch kolizí je pro každý otisk tedy  nekonečné množství. Pokud nejsou dvě hashovací funkce nějak "podobné", tak by měl být průnik těchto kolizí neprázdný. Ale dokazovat bych to tedy nechtěl :-)

Jenom tak na okraj... Kolizí sice je nekonečně mnoho:

H1(M1) =  H1(M2) = H1(M3) ...
H2(MM1) =  H2(MM2) = H2(MM3) ...

ale z toho samotnýho ještě podle mě nutně neplyne, že existují nějaké M1,M2 tak, že

H1(M1) = H1(M2) AND H2(M1) = H2(M2)

Podle mě bysme navíc museli mít nějakou znalost o tom, jak jsou ty kolize rozprostřené, protože čistě teoreticky můžou být klidně "donekonečna napřeskáčku", ne?
Název: Re:Jak udělat soubor s konkrétním kontrolním součtem
Přispěvatel: DgBd 05. 01. 2012, 15:02:22
Čistě matematicky: používají se hashovací funkce, které mají nějaké rozumné rozložení kolizí, těch kolizí je pro každý otisk tedy  nekonečné množství. Pokud nejsou dvě hashovací funkce nějak "podobné", tak by měl být průnik těchto kolizí neprázdný. Ale dokazovat bych to tedy nechtěl :-)

Jenom tak na okraj... Kolizí sice je nekonečně mnoho:

H1(M1) =  H1(M2) = H1(M3) ...
H2(MM1) =  H2(MM2) = H2(MM3) ...

ale z toho samotnýho ještě podle mě nutně neplyne, že existují nějaké M1,M2 tak, že

H1(M1) = H1(M2) AND H2(M1) = H2(M2)

Podle mě bysme navíc museli mít nějakou znalost o tom, jak jsou ty kolize rozprostřené, protože čistě teoreticky můžou být klidně "donekonečna napřeskáčku", ne?

ano, proto jsem psal "nějak podobné". Je jasné, že pro hashovací funkci H2(x)=H1(x)+1 nenastane kolize nikdy.
Název: Re:Jak udělat soubor s konkrétním kontrolním součtem
Přispěvatel: Mirek Prýmek 05. 01. 2012, 15:07:22
ano, proto jsem psal "nějak podobné". Je jasné, že pro hashovací funkci H2(x)=H1(x)+1 nenastane kolize nikdy.

Já bych řekl, že k "dvojkolizi" dojde právě tehdy, kdy si ty funkce NEJSOU podobné. Např. pokud by šlo o náhodné hodnoty, tak k tomu dojde zcela jistě :)

Ale nebudem slovíčkařit :)
Název: Re:Jak udělat soubor s konkrétním kontrolním součtem
Přispěvatel: PCnity 05. 01. 2012, 15:09:47
Pokial spravne chapem kolizie, tak nakolko z n bitov dat spravis m bitov dat, pricom m moze byt vacie, mensie alebo rovne n, je kolizii nekonecne vela.

Cize kebyze mas dany exe subor s MD5 sumou x a ty zoberies vlastny exe subor do ktoreho by si vedel niekde umiestnit velke mnozstvo dat bez toho aby sa stratila funkcionalita [podla mna sa to da, napr. self. extracting zip], skor ci neskor by si po generovani tychto dat vedel spravit exe subor s rovnakou MD5 sumou.

Pravdaze to skor-ci-neskor je velmi relative a zavisi od tvojho vypoctoveho vykonu. Pravdepodobne vsak neumerne dlho pokial nemas nejaky vzorec [ak by aj P=NP, prv by niekto ten vzorec musel najst].

O to zaujimavejsie by to vsak bolo kebyze sa snazis dosiahnut koliziu 2 hashovacish funkcii naraz. Nakolko nadalej plati vyrok ze hash kolizii je nekonecne vela, logicky z toho vyplyva ze by si zase raz skor ci neskor nasiel source data ktore by mali uplne rovnaku MD5 aj SHA sumu ako ta ktoru potreujes... Len tu sa uz asi bavime na velmi velmi teroretickej urovni.

Kazdopadne statement je: Da sa to, len to je sakra zlozite a vypoctovo narocne. Pre bezneho cloveka _dnes_ nedosiahnutelne.
Název: Re:Jak udělat soubor s konkrétním kontrolním součtem
Přispěvatel: DgBd 05. 01. 2012, 15:10:52
ano, proto jsem psal "nějak podobné". Je jasné, že pro hashovací funkci H2(x)=H1(x)+1 nenastane kolize nikdy.

Já bych řekl, že k "dvojkolizi" dojde právě tehdy, kdy si ty funkce NEJSOU podobné. Např. pokud by šlo o náhodné hodnoty, tak k tomu dojde zcela jistě :)

Ale nebudem slovíčkařit :)

Však jsem to napsal:
Citace
Pokud nejsou dvě hashovací funkce nějak "podobné", tak by měl být průnik těchto kolizí neprázdný

:-)
Název: Re:Jak udělat soubor s konkrétním kontrolním součtem
Přispěvatel: Karel 05. 01. 2012, 15:16:05
Samozřejmě, že existují kolize afektující všechny metody najednou. Pokud by existovala kombinace metod, pro kterou neexistuje "univerzální" kolize, pak je spojte a máte neprůstřelnou metodu. Už z porovnání délky původního souboru a výsledného otisku je zřejmé, že neprůstřelná metoda neexistuje a tudíž pro libovolnou množinu metod musí existovat kolize, která ovlivní všechny najednou.
Název: Re:Jak udělat soubor s konkrétním kontrolním součtem
Přispěvatel: PCnity 05. 01. 2012, 15:19:11
Samozřejmě, že existují kolize afektující všechny metody najednou. Pokud by existovala kombinace metod, pro kterou neexistuje "univerzální" kolize, pak je spojte a máte neprůstřelnou metodu. Už z porovnání délky původního souboru a výsledného otisku je zřejmé, že neprůstřelná metoda neexistuje a tudíž pro libovolnou množinu metod musí existovat kolize, která ovlivní všechny najednou.
Perfektne vyjardene. Perfektnu metodu nedosiahneme nikdy, nakolko uz podstaty pouzivania vyplyva ze by suma mala byt radovo mensia ako vstupne data. A v momente ako by neikto chcel pouizit sumu rovnu alebo vacsiu, stratilo by to uplne zmysel.
Název: Re:Jak udělat soubor s konkrétním kontrolním součtem
Přispěvatel: Mirek Prýmek 05. 01. 2012, 15:25:11
Však jsem to napsal:

Omlouvám se, to _ne_jsou jsem nějak přehlídl. Moje chyba :)
Název: Re:Jak udělat soubor s konkrétním kontrolním součtem
Přispěvatel: Mirek Prýmek 05. 01. 2012, 15:27:38
Pokud by existovala kombinace metod, pro kterou neexistuje "univerzální" kolize, pak je spojte a máte neprůstřelnou metodu.

To je pravda, to mi vůbec nedošlo. Pokud je hash kratší než data, tak k tomu dojít musí. Jak jednoduchý ten důkaz byl :)
Název: Re:Jak udělat soubor s konkrétním kontrolním součtem
Přispěvatel: DgBd 05. 01. 2012, 15:37:55
Pokud by existovala kombinace metod, pro kterou neexistuje "univerzální" kolize, pak je spojte a máte neprůstřelnou metodu.

To je pravda, to mi vůbec nedošlo. Pokud je hash kratší než data, tak k tomu dojít musí. Jak jednoduchý ten důkaz byl :)

No jo, tak jednoduché to není. On ten dotyčný hledá kolizi pro určitý vstup, ne pro libovolný vstup.
Název: Re:Jak udělat soubor s konkrétním kontrolním součtem
Přispěvatel: PCnity 05. 01. 2012, 15:40:58
Pokud by existovala kombinace metod, pro kterou neexistuje "univerzální" kolize, pak je spojte a máte neprůstřelnou metodu.

To je pravda, to mi vůbec nedošlo. Pokud je hash kratší než data, tak k tomu dojít musí. Jak jednoduchý ten důkaz byl :)

No jo, tak jednoduché to není. On ten dotyčný hledá kolizi pro určitý vstup, ne pro libovolný vstup.

No ono to je len o daco zlozitejsie, nakolko mozes zobrat funkcne execko a do neho implantovat binarny balast ako data bez toho aby si stratil funkcionalitu binarky. Cize by bolo treba do prcesu kraftovania noveho execka proste implmenetovat process v ktorom cast zostane staticka a cast sa bude menit/pridavat.
Název: Re:Jak udělat soubor s konkrétním kontrolním součtem
Přispěvatel: Policajt 05. 01. 2012, 16:44:41
Potřebuju udělat soubor, aby měl konkrétní předem daný kontrolní součet md5 nebo sha.
Mějme např. original.exe s nějakým kontrolním součtem, já ho chci předělat na jiný original.exe a ten součet musí být nakonec stejný. Jsou na to nějaké tooly?
...jen tak pro zajimavost, co je vas usecase? :)
Název: Re:Jak udělat soubor s konkrétním kontrolním součtem
Přispěvatel: JS 05. 01. 2012, 16:56:01
Samozřejmě, že existují kolize afektující všechny metody najednou. Pokud by existovala kombinace metod, pro kterou neexistuje "univerzální" kolize, pak je spojte a máte neprůstřelnou metodu. Už z porovnání délky původního souboru a výsledného otisku je zřejmé, že neprůstřelná metoda neexistuje a tudíž pro libovolnou množinu metod musí existovat kolize, která ovlivní všechny najednou.

Problem je, ze predpokladate konecnou a pevne danou mnozinu metod, proti ktere se chce branit. Ja jsem to z vyjadreni tazatele pochopil jinak, totiz ze se chce se branit i proti kontrolnim souctum, ktere muze nekdo explicitne navrhnout i na zaklade znalosti jeho algoritmu.
Název: Re:Jak udělat soubor s konkrétním kontrolním součtem
Přispěvatel: PCnity 05. 01. 2012, 17:00: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.
Název: Re:Jak udělat soubor s konkrétním kontrolním součtem
Přispěvatel: Pavouk106 05. 01. 2012, 17:04:32
Prostě a jednoduše bez matematiky a dalších podrobností

Teoreticky to jde
Prakticky to taky jde

Když se budeš hodně snažit a podaří se Ti zachovat velikost souboru a jeho hash i po změně, máš doma na polici Nobelovku. Gratuluju!
Název: Re:Jak udělat soubor s konkrétním kontrolním součtem
Přispěvatel: DgBd 05. 01. 2012, 17:08:14
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)
Název: Re:Jak udělat soubor s konkrétním kontrolním součtem
Přispěvatel: Pavouk106 05. 01. 2012, 17:08:56
Ještě dodatek:

Pokud chceš někomu podstrčit urpavenej soubor a chceš aby s nim pracoval, tak to udělej asi takhle - pošli mu to (nějak předej, ...), až (pokud) udělá hash a dá Ti vědět, že je jinej než má být (podle webu, jinýho dodavatele, ...), řekni mu, že u Tebe doma je ten hash taky jinej (a nadiktuj mu te samej, co to udělá jemu) a že Ti to dělá přesně to, co se od toho očekává (= funguje to = data jou naoko v pořádku). Lepší možnost, jak dneska obejít hash, prostě není.
Název: Re:Jak udělat soubor s konkrétním kontrolním součtem
Přispěvatel: DgBd 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.
Název: Re:Jak udělat soubor s konkrétním kontrolním součtem
Přispěvatel: DgBd 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 :-)
Název: Re:Jak udělat soubor s konkrétním kontrolním součtem
Přispěvatel: DgBd 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)
Název: Re:Jak udělat soubor s konkrétním kontrolním součtem
Přispěvatel: Policajt 05. 01. 2012, 17:33:44
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
Název: Re:Jak udělat soubor s konkrétním kontrolním součtem
Přispěvatel: DgBd 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í.
Název: Re:Jak udělat soubor s konkrétním kontrolním součtem
Přispěvatel: Karel 05. 01. 2012, 18:39:24
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í.

Takže mám funkci 1, kde hash může nabývat 5 různých hodnot. Funkci 2, kde hash může nabývat 7 různých hodnot, a funkci 3, kde hash může nabývat 11 různých hodnot. Spojením těchto 3 funkcí vzniká nejvýše 5*7*11 = 385 různých kombinací výsledků. Tak vemte 386 souborů a máte kolizi. Ono spojování N funkcí jen prodlužuje to, co by se dalo nazvat výsledným hashem. A dokud tento výsledek je menší než vstup, pak vždy existuje kolize.
Název: Re:Jak udělat soubor s konkrétním kontrolním součtem
Přispěvatel: Karel 05. 01. 2012, 18:45:53
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ázev: Re:Jak udělat soubor s konkrétním kontrolním součtem
Přispěvatel: DgBd 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čí.
Název: Re:Jak udělat soubor s konkrétním kontrolním součtem
Přispěvatel: PCnity 05. 01. 2012, 20:55:50
Este raz napisem to co nie je mozne vyvratit.
Kedze hash na to aby mal pre nas zmysel MUSI byt radovo mensi ako vstupne subory (128KiB vs. TiB, etc), musia nutne existovat kolizie. Presne ako bolo spomenute hore.

Pokial chceme kolizie 100% vylucit, mozeme predsa rovno porovnavat zdrojovy subor bit po bite!
Název: Re:Jak udělat soubor s konkrétním kontrolním součtem
Přispěvatel: PCnity 05. 01. 2012, 20:56:34
Dodatok: A je uplne jedno ci pouzijes jednu alebo x hashovacich funkcii!
Název: Re:Jak udělat soubor s konkrétním kontrolním součtem
Přispěvatel: DgBd 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.
Název: Re:Jak udělat soubor s konkrétním kontrolním součtem
Přispěvatel: JS 05. 01. 2012, 21:36:12
Dodatok: A je uplne jedno ci pouzijes jednu alebo x hashovacich funkcii!

Neni. To co jste prave udelal bylo vytknuti existencniho kvantifikatoru (existuje kolize) pred obecny (pro vsechny hashovaci funkce), a to se nema delat. :-)

Apropos, nalezani kolizi bude snadne, pokud P=NP.
Název: Re:Jak udělat soubor s konkrétním kontrolním součtem
Přispěvatel: PCnity 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.
Název: Re:Jak udělat soubor s konkrétním kontrolním součtem
Přispěvatel: PCnity 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.
Název: Re:Jak udělat soubor s konkrétním kontrolním součtem
Přispěvatel: DgBd 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
Název: Re:Jak udělat soubor s konkrétním kontrolním součtem
Přispěvatel: PCnity 05. 01. 2012, 21:53:43
/dev/urandom
Název: Re:Jak udělat soubor s konkrétním kontrolním součtem
Přispěvatel: PCnity 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.
Název: Re:Jak udělat soubor s konkrétním kontrolním součtem
Přispěvatel: DgBd 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é?
Název: Re:Jak udělat soubor s konkrétním kontrolním součtem
Přispěvatel: DgBd 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á.
Název: Re:Jak udělat soubor s konkrétním kontrolním součtem
Přispěvatel: PCnity 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.
Název: Re:Jak udělat soubor s konkrétním kontrolním součtem
Přispěvatel: PCnity 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
Název: Re:Jak udělat soubor s konkrétním kontrolním součtem
Přispěvatel: DgBd 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.
Název: Re:Jak udělat soubor s konkrétním kontrolním součtem
Přispěvatel: PCnity 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.
Název: Re:Jak udělat soubor s konkrétním kontrolním součtem
Přispěvatel: DgBd 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.
Název: Re:Jak udělat soubor s konkrétním kontrolním součtem
Přispěvatel: JS 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.
Název: Re:Jak udělat soubor s konkrétním kontrolním součtem
Přispěvatel: ..|.. 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.
Název: Re:Jak udělat soubor s konkrétním kontrolním součtem
Přispěvatel: PCnity 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.
Název: Re:Jak udělat soubor s konkrétním kontrolním součtem
Přispěvatel: Mirek Prýmek 06. 01. 2012, 08:23:34
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ě.
Název: Re:Jak udělat soubor s konkrétním kontrolním součtem
Přispěvatel: Mirek Prýmek 06. 01. 2012, 08:30:39
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

:)
Název: Re:Jak udělat soubor s konkrétním kontrolním součtem
Přispěvatel: DgBd 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í.

Název: Re:Jak udělat soubor s konkrétním kontrolním součtem
Přispěvatel: DgBd 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ší.
Název: Re:Jak udělat soubor s konkrétním kontrolním součtem
Přispěvatel: DgBd 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).
Název: Re:Jak udělat soubor s konkrétním kontrolním součtem
Přispěvatel: Mirek Prýmek 06. 01. 2012, 10:20:27
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
Název: Re:Jak udělat soubor s konkrétním kontrolním součtem
Přispěvatel: DgBd 06. 01. 2012, 10:42:46

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.

Citace
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.
Název: Re:Jak udělat soubor s konkrétním kontrolním součtem
Přispěvatel: Mirek Prýmek 06. 01. 2012, 10:47:59
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.
Název: Re:Jak udělat soubor s konkrétním kontrolním součtem
Přispěvatel: Karel 06. 01. 2012, 12:54:47
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.