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

martin

Re:Jak udělat soubor s konkrétním kontrolním součtem
« Odpověď #15 kdy: 05. 01. 2012, 14:47:02 »
něco o kolizích http://bit.ly/AtCknr


Re:Jak udělat soubor s konkrétním kontrolním součtem
« Odpověď #16 kdy: 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?

DgBd

  • ****
  • 282
    • Zobrazit profil
    • E-mail
Re:Jak udělat soubor s konkrétním kontrolním součtem
« Odpověď #17 kdy: 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.

Re:Jak udělat soubor s konkrétním kontrolním součtem
« Odpověď #18 kdy: 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 :)

PCnity

  • *****
  • 685
    • Zobrazit profil
    • E-mail
Re:Jak udělat soubor s konkrétním kontrolním součtem
« Odpověď #19 kdy: 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.


DgBd

  • ****
  • 282
    • Zobrazit profil
    • E-mail
Re:Jak udělat soubor s konkrétním kontrolním součtem
« Odpověď #20 kdy: 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ý

:-)

Karel

Re:Jak udělat soubor s konkrétním kontrolním součtem
« Odpověď #21 kdy: 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.

PCnity

  • *****
  • 685
    • Zobrazit profil
    • E-mail
Re:Jak udělat soubor s konkrétním kontrolním součtem
« Odpověď #22 kdy: 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.

Re:Jak udělat soubor s konkrétním kontrolním součtem
« Odpověď #23 kdy: 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 :)

Re:Jak udělat soubor s konkrétním kontrolním součtem
« Odpověď #24 kdy: 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 :)

DgBd

  • ****
  • 282
    • Zobrazit profil
    • E-mail
Re:Jak udělat soubor s konkrétním kontrolním součtem
« Odpověď #25 kdy: 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.

PCnity

  • *****
  • 685
    • Zobrazit profil
    • E-mail
Re:Jak udělat soubor s konkrétním kontrolním součtem
« Odpověď #26 kdy: 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.

Policajt

Re:Jak udělat soubor s konkrétním kontrolním součtem
« Odpověď #27 kdy: 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? :)

JS

Re:Jak udělat soubor s konkrétním kontrolním součtem
« Odpověď #28 kdy: 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.

PCnity

  • *****
  • 685
    • Zobrazit profil
    • E-mail
Re:Jak udělat soubor s konkrétním kontrolním součtem
« Odpověď #29 kdy: 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.