Hash-megegyezés esélye

Fejlesztés

Többtíz gigabyte napi szintű távoli szinkronizálását (kis sávszélességgel) kéne megoldanom, az adatok 1/4/16/64 MB-os szervezésűek, nincs fájlnév, dátum, egyéb azonosítóm.
Van emberi számítás szerint esély arra, hogy méret, CRC32, MD5 és SHA256 azonosság esetén a két alapul vett adathalmaz különbözzön?

  • 1820 megtekintés

( log69 | 2010. 01. 17., v – 09:24 )

sha256-nál olyan 10^77-en a kimenetek száma. Lottó ötösnél 95 alatt 5 olyan 44 millió "csak". ez lehet támpont :)

ugye még ha 1 MB-os adatrészeket is továbbítasz, az meg önmagában több kimenetet ad. tehát itt a legkisebb halmazt a hash adja, amiatt meg nem aggódnék.

( Kayapo | 2010. 01. 17., v – 10:26 )

Inkább vagy kapcsolat van!
Bár két azonos méretű file mg simán lehet különböző, de ha a méret azonos és a tartalom csak egy bitben eltér az md5, vagy sha256 különbözni fog.
Tehát, ha a két adathalmaz md5, vagy sha256 summája azonos, akkor egyértelműen kijelenthetjük, hogy a két adathalmaz azonos.

----
概略情報

Gondban is lehetnek, csak annyira kicsi az esélye az ilyen jellegű hibának, hogy véletlenül még talán elő sem fordult. Viszont szándékosan ki lehet használni a dolgot. (Persze gép is kell hozzá ;) és az ilyenek (viszonylag gyors ütközés keresés) miatt kell leváltani az MD5-öt.)

De hogy egyszerűbb legyen: Képzeld el, hogy felírod egy fájlnak az MD5 hash-ét és a pontos méretét, átmész egy másik géphez és egyértelműen helyreállítod a 80TB-os fájlt :P Jó is lenne. Imádnám! Backup-hoz kiváló lenne. Floppy-ra mentenénk a világot is.

Miert lennenek gondban? Az MD5/stb. hashek nem 100%-os biztonsaggal mondjak meg, hogy mirol keszult az a hash. Van egy hatalmas bitsorozatot, ok abbol gyartanak egy kisebb bitsorozatot, azzal a feltetellel, hogy ha az eredeti bitsorozat egy bitje valtozik, akkor a kimeneten legalabb a bitek fele valtozik. Ennyit tud az MD5, semmi tobbet. Nem garantalja (csak kicsi a valoszinusege), hogy minden kulonbozo bemenetnek kulonbozo hash-e legyen, hiszen az MD5 fuggveny nem bijektiv. Elmeletileg lehetetlen is, hiszen 32 byteon nem tarolhatsz el akarmennyi informaciot.
Ajanlom ezt az eloadast: http://www.renyi.hu/~csirmaz/nws06/nws06.pdf

azért nem jelenthetjük ki teljes biztonsággal.
Minden bit változás az inputon egy teljesen új, random hasht jelent.
ez az md5-nél 128 bites véletlenszám.
Ha két filenak ugyanannyi az md5 összege, annak az esélye, hogy a két file különböző, kb akkora, mint a lottón zsinórban egymás után 4 héten a lottóötösnek (egy szelvénnyel játszva). Azaz kicsi.

( aspirin v | 2010. 01. 17., v – 10:36 )

Előre bocsájtva, hogy különösebben nem értek a témához, az első néhány link jónak tűnik:
hash collision - Google
Talán el lehet indulni valamelyiken. :)
<-------
You can't grep on dead trees.

( Kayapo | 2010. 01. 17., v – 10:58 )

Finder, Radix!
Értem a matematikai fejtegetést, nyilvánvaló, hogy igazatok van, mindazon által kevés valószínűségét látom annak, hogy két távoli adathalmaz össze szinkronizálásakor, azon kívül ha a mester adathalmaz változatlan, ilyen azonosság álljon elő.

blr!
Írhatnál kicsit többet a feladatról.

----
概略情報

Erre írtam, hogy annyira kicsi az esélye, hogy véletlenül még talán elő sem fordult. Ez akkor jelent problémát, ha valaki szándékosan nyúl bele a fájlba. (Pl. adott egy eszköz ami csak aláírt firmware-t hajlandó boot-olni és az aláírásnál tulajdonképpen az adott MD5 hash-sel rendelkező firmware-t fogadják el akkor elég csak az általunk írt firmware-be néhány "ütköztető bitet" elrejteni és máris használhatjuk az eredeti aláírást.) Ilyen szinkronizálós dolgokra szerintem nyugodt szívvel lehet használni.

Az, hogy te kevés valószínűséget látsz, az nem jelenti azt, hogy nem fog előfordulni. Például az, hogy valaminek az előfordulási valúszínűsége 2^(-200)-on, attól még akár az első kísérletkor is előfordulhat, és utána meg sokáig nem. Ez természetes. Az, hogy valaminek kicsi a valószínűsége, attól az még nem lehetetlen. Sőt, a 0 valószínűségű esemény sem lehetetlen.

( egmont | 2010. 01. 17., v – 11:15 )

A lottós hasonlatokkal vigyázz! Igaz hogy megállapítják hogy sokkal-sokkal kisebb az ütközés esete, de azt nem veszik figyelembe, hogy sokkal-sokkal gyakrabban kísérted meg a sorsot, mint amilyen gyakran lottózol.

( Finder | 2010. 01. 17., v – 11:15 )

Egyébként ha jól értem a problémát, akkor az rsync-et neked találták ki.

( egmont | 2010. 01. 17., v – 11:25 )

Legyen N a lehetséges hash értékek száma (tehát például md5 esetén N = 2^128).
Legyen k az adatblokkok száma (több tíz gigabyte osztva kábé 1 megával, az párszor 10000, de te biztosan pontosabb becslést is tudsz készíteni. Az adatok időbeli változását is vedd figyelembe, tehát ha ez naponta vadiúj ekkora adathalmaz, akkor szorozd a napok számával!)

Az első md5 kiszámolásakor az ütközés esélye korábbiakkal 0. A másodiknál 1/N az esély hogy ütközik az előzővel. A harmadiknál 2/N (és itt elkezdünk picit csúsztatni, elhanyagoljuk azt az esetet hogy az első kettő már ütközött), és így tovább, az utolsónál (k-1)/N. Annak az esélye hogy egyáltalán volt ütközés ezek összege (ismét az előző csúsztatás befigyel), vagyis kábé k^2 / (2N). Ez a képlet N-hez képest kis k esetén (tehát a te esetedben, amikor épphogy csak azt akarod leellenőrizni hogy kell-e reálisan félni ütközéstől) tökéletesen jó közelítés.

Mindemellett ne feledd, hogy ez a valószínűséges sztori véletlen adatokra vonatkozik. Slashdot-on pár éve volt cikk arról, hogy sikerült konstruálni két fájlt azonos md5 összggel, ráadásul két érvényes postscript fájl volt egymásnak ellentmondó szerződésszöveggel. Nagyon nem mindegy tehát, hogy adataid véletlenek, vagy támadó által tökéletesen kontrollálhatóak. Utóbbi esetben érdemes utánajárni, hogy melyik algoritmus ellenállóbb, illetve a már létező hash algoritmusokat egy titkos komponenssel megbolondítani, például a checksumolt fájlok elé egy közös kis blokkot odabiggyeszteni, vagy egy másik checksum pár bitjét is hozzáfűzni.

128 bites értéknél szerintem felesleges 10 000 -el szorozgatni az esélyeket. Az hogy pl. nem hetente 1x, hanem másodpercenként állítja elő ezt az értéket, nem sokkal javítja a ~10^38 kimenetek számát imho. Ha meg az adott algoritmus köztudottam törhető, akkor már nem érdemes használni. A bitek hozzáfűzése a bemeneti adathoz meg nem növeli a kimenetek számát szerintem.

De továbbra is kérdés, hogy mi a cél. Ha sima adatmentés és ez megnyugtatja, akkor ráengedhetne a feltöltött adatokra egy shasum-ot a feltöltés végeztével, és ezt összehasonlítani az eredeti adatokéval: 


cd dir
find ! -type d -print0 | sort -z | xargs -0 sha256sum | sha256sum

vagy hasonló, lehet van egyszerűbb is

( hud | 2010. 01. 17., v – 14:21 )

Azt javaslom, hogy használj két módszert, és a programod szóljon neked, ha csak az egyik szerint különbözőek a fájlok. Igen valószínűtlen, hogy két különböző fájl esetén két algoritmussal vett lenyomatuk megegyezik, viszont ha csak az egyik módszer bukik meg, akkor van egy jó cikked belőle :)

( blr v | 2010. 01. 18., h – 00:29 )

Köszönöm az infókat. A konklúzió: kisebb a valószínűsége annak, hogy a három hash és a méret azonossága esetén különböző az eredeti adathalmaz, mint hogy egyszerre szálljon el két lemez a RAID5 tömbből.
Egyébként a napi változás nem sok, de az összes adat igen (kb. 7-800 GB), ráadásul a kedves alkalmazottak előszeretettel küldözgetnek hatalmas csatolmányokkal körleveleket, illetve játszák azt, hogy lementenek valamit magukhoz, aztán onnan átmásolják a publikus területre. Ebből következően az egész simán "tömöríthető" minimum a felére, ha elhiszem, hogy a három hash egyezősége "kimondja" két blokk egyezőségét. (Azért a blokkokra bontás, mert pl. ha valakinél 1-2 GB egy mailbox fájl, annak úgyis többnyire csak a vége változik, illetve ha egy fotóban kiretusálok egy karcolást, az sem feltétlenül érinti az egész fájlt.)

(Reméltem, hogy sejtésemet alapvetően alátámasztjátok, mert közben kb. 90%-ban elkészültem a kóddal :)