Izračunana uspešna kolizija nad SHA-1

Zgostitveni algoritmi (ang. hash algorithms, včasih tudi hash values, hash codes, hash sums, checksums, message digests ali fingerprints) so matematični algoritmi, ki poljubno dolg niz znakov preslikajo v število fiksne dolžine. S tem zgostitveni algoritmi izračunajo tim. prstni odtis (ang. fingerprint) oz. kontrolno vsoto (ang. hash) tega niza znakov (na primer datoteke), kar je osnova za digitalni podpis oziroma za zagotovilo, da so podatki ohranili integriteto.

Zaradi njihove funkcije je pomembno, da so zgostitveni algoritmi enosmerni (iz kontrolne vsote ni mogoče nazaj izračunati originalnih podatkov) ter zlasti, da v praksi ne sme priti do kolizije. Slednje pomeni, v praksi da ne smeta obstajati dva različna niza podatkov, ki bi vrnila isto kontrolno vsoto (to je sicer odvisno tudi od tim. bitnosti kontrolne vsote).

Dobri zgostitveni algoritmi imajo tim. efekt plazu (avalanche efekt) – če se vhodni podatki malenkost spremenijo, se bo njihova kontrolna vsota spremenila drastično.

Zgostitveni algoritmi danes tvorijo osnovo varnosti na internetu. Uporabljajo se za zaščito gesel (hramba v obliki kontrolne vsote), kot pseudonaključni generator števil, pri generiranju naključnih imen datotek, za preverjanje integritete pri prenosu datotek (npr. v P2P omrežjih), za preverjanje integritete arhivskih datotek (tim. checksum), pri implementaciji digitalnega podpisa, časovnega žigosanja, overovitvi digitalnih potrdil, za digitalno podpisovanje datotek, gonilnikov ter seveda pri digitalni forenziki.

Iz vsega tega je jasno, da morajo biti algoritmi za izračun kontrolnih vsot karseda varni.

Kolizija nad MD5 v praksi

Kot rečeno je največja grožnja varnosti algoritmom za izračun kontrolnih vsot kolizija. Eden bolj odmevnih primerov kolizije je bila kolizija v algoritmu MD5. MD5, ki so ga razvili leta 1991, se je namreč v preteklosti uporabljal pri overjanju digitalnih potrdil precej razširjen pa je bil tudi pri zagotavljanju integritete podatkov v digitalni forenziki. Več o zgostitvenih algoritmih in napadih na MD5 si je mogoče prebrati na mojih prosojnicah iz leta 2012 (Zagotavljanje integritete digitalnih dokazov).

Prvo kolizijo (pravzaprav psevdo-kolizijo) v MD5 so našli leta 1993. Matematične raziskave so šle naprej in skupina raziskovalcev je leta 2004 pokazala, da je uspešen napad na MD5 na tedanji strojni opremi mogoče izvesti v eni uri. Leta 2006 je bilo to mogoče v le eni minuti.

Kot alternativa MD5 se je nato priporočala uporaba algoritma SHA-1 oziroma njegovih kasnejših izvedenk. Raziskovalci so tudi v SHA-1 leta 2005 našli način za izračun uspešne kolizije, teoretični napadi na SHA-1 pa so se nato le še izboljševali, zato je ameriški NIST leta 2011 SHA-1 upokojil.

A v praksi se algoritem danes še vedno marsikje uporablja.

Kolizija nad SHA-1 v praksi

Temu bo zdaj potrebno narediti konec. Skupina raziskovalcev iz CWI Amsterdam in Google Research je namreč te dni objavila rezultate svoje raziskave, ki je pokazala, da je SHA-1 mogoče zlomiti tudi v praksi.

Konkretno, raziskovalci so objavili dve PDF datoteki (prva in druga) z različno vsebino, a istim SHA-1 digitalnim podpisom.

Za izračun kolizije je sicer na običajnem enoprocesorskem računalniku potrebnih 110 let, a z uporabo 110 grafičnih procesorjev (GPU) je ta čas mogoče zmanjšati na eno leto. Z uporabo dodatnih GPU procesorjev pa seveda še na manj.

Podrobnosti o napadu so objavljene na spletni strani shattered.it, rešitev pa je uporaba novejših zgostitvenih algoritmov, na primer SHA-256 ali SHA-3.

Ker se SHA-1 marsikje še vedno uporablja pri HTTPS digitalnih potrdilih, brskalnik Google Chrome od različice 56 (izdana januarja 2017) spletne strani zaščitene z digitalnimi potrdili, ki za digitalno podpisovanje uporabljajo samo SHA-1 obravnava kot ne-varne. Brskalnik Firefox bo podobno funkcionalnost uvedel v bližnji prihodnosti. Na voljo je tudi orodje sha1collisiondetection, ki skuša zaznati kolizijski napad na SHA-1 v datotekah, in s katerim je mogoče preveriti integriteto datotek.

Velik problem pa predstavlja GIT, ki za preverjanje integritete podatkov na veliko uporablja SHA-1. Zato bi napadalec lahko teoretično postavil zlonamerno različico GIT skladišča, ki bi vsebovala programsko kodo z vgrajenimi stranskimi vrati, ta zlonamerna programska koda pa bi imela enako kontrolno vsoto kot neokužena različica.

Mimogrede, digitalno potrdilo tega spletnega mesta za digitalno podpisovanje uporablja SHA-256.