Ütközéseket találtak jópár hash függvényben

Fránya gépek. Minden jól kezdődött, amikor augusztus elején pár kriptoanalízissel foglalkozó tudós úgy döntött, hogy elmegy valahová nyaralni, mert a gépteremben sosem lesznek elég barnák, a csajok meg nem csípik a falfehér pasikat.

De hogy ne egye hiába az a 256 Itanium 2-es processzorral felszerelt desktop PC a drága áramot, adtak hát neki valami egyszerű feladatot. Nem volt más dolga, mint végigszámolni egy képletet, más-más bemenő adatokkal, egymás után 2251799813685248 alkalommal. Ezen egy kicsit elgondolkozott, majd 13 nap múlva küldött egy SM-et a tengerparton lubickoló egyik gazdájának.

Mivel a szóban forgó PC Unix szerű oprendszert futtatott, az üzenet ez volt:

"$ diff fic1.bin fic2.bin

Binary files fic1.bin and fic2.bin differ

$ openssl sha fic1.bin

SHA(fic1.bin)= c9f160777d4086fe8095fba58b7e20c228a4006b

$ openssl sha fic2.bin

SHA(fic2.bin)= c9f160777d4086fe8095fba58b7e20c228a4006b"

Szerencsére hősünknek olyan mobilja volt, amely képes egyben megjeleníteni a 160 karakternél hosszabb üzeneteket, így észrevette a nagy hírt: ütközést találtak egy kriptográf hash függvényben.A fenti sztori kitaláció, a bejelentés viszont úgy tűnik, hogy nem.

Kicsit kusza még a dolog, így egyelőre csak annyi látszik biztosnak, hogy lassan érdemes lesz elkezdeni felhagyni az MD5 (és talán az SHA) alkalmazásával és átállni valami komolyabbra. Hogy mi lesz az a komolyabb, egyelőre nem világos, mint ahogy az sem, hogy pontosan mit is találtak a kutatók és azt milyen széles körben tudják használni.

A fő szenzáció mindenesetre biztosan nem az, hogy ütközést (azaz két olyan, egymástól eltérő bemenetet, amely a függvényből ugyanolyan kimenetet hoz elő) találtak, hanem az, hogy ezt sokkal gyorsabban meg tudják tenni, mint azt eddig egyesek hitték.

Linkek a további olvasgatáshoz:

http://www.tcs.hut.fi/~mjos/md5/
http://www.mail-archive.com/cryptography@metzdowd.com/msg02554.html
http://www.freedom-to-tinker.com/archives/000664.html

Hozzászólások

De ha ez azt jelenti, h. a tripwire nem fogja felfedezni a kicserélt binárist, attól még nehéz olyan bájtsorozatot találni, ami majd azt fogja csinálni amit a rossz ember el is akar érni a módosítással.

Vagy nem ez a jelentösége a dolgonak?

ezt sokkal gyorsabban meg tudják tenni, mint azt eddig egyesek hitték

2^80 helyett 2^40 probalkozassal?

Remek :)

Nem tudom mennyire latod at a ket nagysagrendet, de _nagyon_ nem mindegy a kulonbseg. 2^40 probalkozas a mai szamitasi teljesitmenyek mellett nem nagy, sot. 2^80 nagy.

ui: bocsi hogy ezt irom, es remelem hogy mindenkinek trivialis, dev 2^80 nem ketszer, hanem sokkal tobbszor (2^40-szer) annyi mint a 2^40.

mi a pek az a ``kriptografika''? ez valami mostanaban divatos ujabb interdiszciplinaris tudomanyag? =D