[ T-Damir @ 09.09.2004. 14:23 ] @
| Ne znam šta vi mislite ali evo cijelog teksta pa da cujem komentare. Šok u kriptografskoj zajednici Hash-funkcije danas su jedan od osnovnih elemenata svakog kriptografskog sustava. Na njih se indirektno oslanjate za zaštitu vaše online kupovine, čuvanje privatnosti vaših medicinskih dokumenata ili kao mehanizam zaštite vaših e-bankarskih transakcija. Vrlo nedavno dva su istraživačka tima objavila kako su probili čak pet široko korištenih hash-funkcija! Hash-funkcije jedno su od najtežih područja u kriptografiji. Dok je kriptografska zajednica u zadnjih dvadeset godina posvetila mnogo vremena istražujući kako izraditi i probiti tzv. block cipher algoritme za enkripciju i dekripciju, može se reći kako je naše znanje o hash-funkcijama još uvijek na istom mjestu kao i osamdesetih godina. Podsjetimo se nakratko ideje iza hash-hunkcija. One (u ovom tekstu govorimo isključivo o kriptografskim hash-funkcijama, ne o nevezanoj obitelji funkcija istog imena) imaju zadaću procesirati ulazne podatke bilo koje dužine te za procesirane ulazne podatke dati jedinstveni izlaz ("otisak prsta") fiksne dužine. Taj se izlaz zove hash ili digest. Na primjer, trenutačno najviše korištena hash-funkcija MD5 za prethodnu rečenicu ovog članka daje izlaz "f8a06223e48eb9915067fdb812b3103c". Jednosmjernost izričaja Čemu nam takav hash služi? Prije nego što možemo odgovoriti na ovo pitanje, potrebno je spomenuti neka od svojstava idealne hash-funkcije. Prvo, idealna hash-funkcija je jednosmjerna, odnosno iz dane hash-vrijednosti nije nikako moguće rekonstruirati ulazne podatke koji su taj hash proizveli. Drugo, hash-funkcije uvijek proizvode izlaz fiksne dužine. Ako pogledate gore navedeni hash, on je za ulaznu rečenicu od 34 znaka proizveo hash dužine 32 znaka – no taj hash bi bio dužine 32 znaka čak i da smo umjesto kratke rečenice hash-funkciji dali da procesira, recimo, 4,5-gigabajtni DVD image. Treće važno svojstvo hash-funkcija je da i najmanja promjena u ulaznim podacima uzrokuje veliku promjenu u izlaznom hashu. Dapače, u prosjeku promjena od jednog bita u ulazu mijenja 50% bitova izlaznog hasha. Ako kombiniramo ta tri svojstva, vidimo da su hash-funkcije izuzetno korisne: one nam mogu omogućiti jednostavnu provjeru uspješnog prijenosa velike količine podataka ili općenito poslužiti kao trik iz rukava pri dizajnu kriptografskog sustava kada nije poželjno raditi s ulazom nedefinirane duljine. Posljednje bitno svojstvo idealne hash-funkcije je da je za nju nemoguće naći dva različita ulaza za koje bi ta funkcija proizvela isti izlazni hash (pronalazak takva dva ulaza naziva se collision). Ako se imalo sjećate elementarne teorije skupova, jasno vam je da je nemoguće napraviti injektivnu funkciju koja radi s dva skupa različite kardinalnosti. Odnosno, u laičkim terminima, nije moguće proizvesti funkciju kojoj ulaz može biti neograničeno dugačak, izlaz fiksne duljine, a da se nikada ne nađu dva ulaza s istim izlazom. Dapače, takvih "collisiona" u hash-funkcijama postoji beskonačno mnogo, no ono što je bitno je da ih je nemoguće pronaći – drugim riječima, da napadač koji zna originalni ulaz te hash ne može naći neki drugi ulaz koji generira taj isti hash. "R" iz RSA Da kreiranje hash-funkcija nije lako, potvrdit će vam Ron Rivest, profesor na američkom sveučilištu MIT i poznati matematičar koji se bavi teorijom brojeva (ako ste čuli za RSA algoritam, on je u toj kratici "R"). Njemački stručnjak Hans Dobbertin već davno je u potpunosti probio Rivestovu hash-funkciju MD4, nakon čega se Rivest bacio na posao i 1992. objavio novu funkciju, MD5. Iako su godinu dana kasnije dva stručnjaka objavila nalazak collisiona unutar tzv. MD5 kompresijske funkcije, jedne od internih funkcija koje MD5 koristi pri izradi hasha, nitko nije bio uspio proširiti napad na cijelu funkciju i svijet je objeručke prihvatio brzi MD5 kao de facto standard. Američka Agencija za nacionalnu sigurnost također se okušala pri izradi hash-funkcija, i to neslavno: u njihovoj funkciji nazvanoj SHA (danas SHA-0) brzo je pronađena slabost te je Agencija odmah izdala novu funkciju koja popravlja grešku. Ta je funkcija nazvana SHA-1 (kao zanimljivost valja spomenuti da, iako NSA nikad nije objavila kakvu je slabost našla u SHA-0, jedina promjena između SHA i SHA-1 bilo je dodavanje rotacije jednog bita u srži funkcije). Osim ove dvije najpopularnije funkcije, u zajednici su se pojavile još neke popularne funkcije imenima HAVAL i RIPEMD, kojima poput MD5 i SHA-1 nije bilo moguće naći greške u sigurnosti. Sve se promijenilo 16. kolovoza 2004. kada je kriptografskom zajednicom odjeknula glasina kako će na konferenciji Crypto 2004, najuglednijem skupu kripto-faca u svemiru kojim predsjeda Jim Hughes, uskoro biti objavljen nalazak "collisiona" u SHA-0, ali i onih u MD4, MD5, HAVAL-u te RIPEMD-u. U kriptografskim krugovima zavladala je polupanična euforija – nije se znalo jesu li napadi istiniti, da li su zbilja sve funkcije zahvaćene niti koje su posljedice. Nekoliko sati kasnije na Internetu je objavljen istraživački rad o collisionima u četiri od pet spomenutih funkcija. Generacija collisiona za MD5, tvrde autori, ne samo da nije teška, već do proizvodnje prvog collisiona treba samo sat vremena, a nakon toga od 15 sekundi do 5 minuta za svaki sljedeći koji dijeli početnih 512 bitova. Počelo se sumnjati da je i SHA-1 možda probijena te je brzom intervencijom organiziran prijenos uživo konferencije Crypto preko Interneta. Sve oči bile su uprte u istraživače hash-funkcija. Francusko-kineska veza Antoine Joux i njegov tim objavili su definitivan pronalazak collisiona u SHA-0, koncentrirajući se na opskurnu funkciju "if" unutar matematičke konstrukcije tog algoritma. Jouxov napad uspješno kreira collisione nakon 250 pokušaja, odnosno 20 dana na 160 Itaniuma. Kineskinja Xiaoyun Wang zatim je zapanjila publiku objavom kako su glasine točne: njen tim napravio je metodu diferencijalne kriptoanalize koja garantira pronalazak collisiona u SHA-0 u 240 pokušaja (dakle tisuću puta bolje od Jouxa). Istom metodom RIPEMD pada za dva sata, MD5 za sat vremena, HAVAL nakon 64 pokušaja te MD4 nakon samo četiri pokušaja. Pokazalo se da je barem glasina o SHA-1 bila samo glasina: tim Elia Bihama objavio je uspješan napad na 34 od 80 internih rundi SHA-1 te misle da ga mogu proširiti na 46 rundi, no to i dalje nije ni blizu probijanja cijele funkcije. Što sada? Zapravo, nitko nije siguran. Velika većina svjetskih sistema koji se oslanjaju na kriptografiju bit će zahvaćena objavljenim napadima, no zbog matematički komplicirane prirode napada očekuje se kako trenutačne posljedice ipak neće biti velike. Kriptografija je teška i očekujemo da će zajednici trebati neko vrijeme da shvati u čemu je griješila s dosadašnjim funkcijama te izbaci nove, popravljene varijante da zamijene stare. No stručnjaci se zasad slažu da na prvi pogled rješenje leži jednostavno u količini bitova kojom hash-funkcije interno manipuliraju. Prema onome što sada znamo, čini se kako će za n-bitnu hash-funkciju biti potrebno interno manipulirati s 2n bitova, odnosno kako ćemo za, recimo, siguran 128-bitni MD5 hash morati interno procesirati 256 bitova i time odraditi dvostruko više posla nego što smo prije mislili. Gospodine Rivest, rukavica je bačena - spremno očekujemo MD6. |