Hash algoritmusok

Az Információbiztonság sorozat ezen írásában megismerkedünk a hash algoritmusok, magyarul hasító algoritmusok tulajdonságaival, alkalmazási területeivel és jelentőségükkel.

Adatépség, bevezetés

Tételezzük fel, hogy van egy tetemes adatmennyiségünk, amit megbízhatóan át kell juttatnunk egy működőképes hálózaton A pontból B pontba a lehető leggyorsabban. Mivel a hálózat működése és hibátlansága nem garantálható minden esetben, ezért nem igen kézenfekvő és hatékony módszer, ha egyben próbáljuk meg átvinni az adatot.

Ezért első lépésben célszerűbb kisebb csomagokra darabolni az adatot, amit majd a fogadó oldalon összeraknak. Így ha egy csomag sérül az átvitel során, akkor elég csak a kisebb méretű csomagot átküldeni, nem kell az egész küldést újra kezdeni.

Viszont ezen módszer esetén még mindig nem tudjuk, hogy mikor helyes és helytelen az átvitel. Bevezethetnénk pár paritás bitet az épség ellenőrzésére, és ha megfelelően alkalmazzuk őket, akkor még hibajavító is lenne a kódolásunk. A probléma a módszerrel jelen esetben az, hogy jelentősen növelné az összes csomag méretét. Hamming 8,4 esetén a hatékonyság 50%, viszont 256,8 kódolás esetén már 96,86%, ami azt jelenti, hogy ilyen kódolással 1GiB adat átvitel ~991MiB tényleges adatot hordozna. Ami nem rossz arány jelenlegi technikával, viszont a Hamming dekódoló áramkörünk bonyolultsága exponenciálisan növekszik a bitek számával és szoftverből sem lenne a leggyorsabb. Továbbá az olyan esetekben, amikor az átvitellel nincsen baj, csak feleslegesen lassítanák az átvitelt.

Ezen problémára jobb megoldás, ha egy úgynevezett hasító algoritmust alkalmazunk. A hasító algoritmusok olyan függvények, amelyek végtelen mennyiségű bemeneti adatból képeznek véges számú kimeneti bitre. Értelemszerűen ezen definícióból következik, hogy egy hash algoritmus kimenetéből nem fejthető vissza a bemenet. Tételezzük fel, hogy van egy hasító függvényünk, amely 32 bites értékeket produkál. Ebben az esetben 232 különböző bemeneti adat csomaghoz tudunk egyedi azonosítót rendelni. Ez 4 294 967 296 egyedi értéket jelent.

Természetesen probléma lehet egy ilyen algoritmus esetén a kimenetek ütközése. Ez alatt az értendő, hogy a fentebbi algoritmus definícióból következik, hogy lesz biztosan két olyan különböző bemenet, amely ugyanazt a kimeneti kódot produkálja. Ennek esélye minimalizálható a kimeneti bitek számának növelésével és az algoritmus által használt műveletek speciális megválogatásával.

Visszatérve a problémára, ha az átvitt csomagok méretét korlátozzuk 64KiB-ra, mert ekkora adatmennyiségnél garantáltan nem lesz ütközés az algoritmusunkban, akkor az előző 1GiB adat példánál maradva 16 384 db csomagunk lesz és 1023,9375 MiB tényleges adat van az átvitelben, ami 99,9939% hatékonyságot eredményez. Tehát ideális esetben fényévekkel jobb.

És akkor elhagyhatjuk az elméleti síkot, mert az említett technológiai leírás, amiről eddig volt szó, az bizony létezik, mindennap használjuk. Ezt az oldalt is a segítségével olvasod: Internet. A 64KiB csomag limit az IPv4 méret korlátja, a 32 bites algoritmus pedig a CRC-32.

A CRC-32 kifejezéssel már lehet találkoztál a ZIP archívumok esetén. Ezen fájlokban ez az algoritmus felelős azért, hogy megmondja, hogy az archívumban tárolt fájlok épek-e vagy sem, de ugyanez az algoritmus megtalálható a SATA vezérlőben is, illetve a DVD lemezek esetén használt MPEG2 kódolásban is, vagy a PNG fájlokban is.

Természetesen hasító algoritmusból annyi van, mint égen a csillag. A CRC családból van 8 (nem meglepő módon CRC-8 a neve) és 64 bites változat is. További népszerű algoritmusok még az MD5 és a SHA család tagjai, mint az SHA1, SHA256 és SHA512. Ezeket nagyobb mennyiségű adat ellenőrzésre szokták használni, de alapvetően nem csak erre jók. Erről majd egy későbbi bekezdésben lesz szó.

Hash, mint a gyors keresés módszere

Adódhat programozás során olyan eset, amikor a feladatunk az, hogy egy bemenetről megmondjuk, hogy része-e egy tárolt adatstruktúrának, adatbázisnak. Ilyen problémák megoldására találták ki a keresési algoritmusokat. Ezekből is annyi van, mint égen a csillag. Jellemzőjük azonban, hogy időt vesznek igénybe és drámaian tudják lassítani egy program működését, ha viszonylag sokat végzünk el belőlük és nem optimálisan vannak megírva.

Olyan esetekben, mikor sűrűn kell keresni, célszerű egy olyan tárolási módszert bevezetni, amely eleve megkönnyíti a keresést. Programozásban ilyen tárolási szerkezet a HashSet, amely egy olyan tömb, amiben az elemek indexét maga az elemből képzett hash adja. Így a keresés igen egyszerű, mert csupán azt kell megvizsgálni keresés esetén, hogy a képzett indexen a tömb tárol-e értelmes adatot. A módszer “hátránya”, hogy a kollekció többször nem tartalmazhatja ugyanazt az elemet.

További felhasználási lehetőség, ha fogunk egy HashSet-et és egy sima tömböt. A HashSet-el tároltatjuk az értékek indexét, míg a sima tömb tárolja a tényleges értékeket. Ebben az esetben kaptunk egy összerendelési táblázatot, vagy más néven asszociatív tömböt, vagy szótárt.

Objektumok egyenlősége

Objektumorientált programozási környezetben adódhat olyan probléma, hogy két objektumot össze kell hasonítani és meg kell mondani, hogy mikor egyenlőek. Itt a favágó módszer az lenne, hogy az objektumok memóriaterületeit bitenként összehasonlítjuk. Ez sok időt vehet igénybe és értelemszerűen nem a leghatékonyabb módszer. Éppen ezért az olyan fejlett nyelvek, mint a C# vagy Java hash értékeket használnak objektumok tartalmának összehasonlítására első körben.

Mivel a hash értékekben lehet ütközés, ezért C# és Java esetén is van módszer arra, hogy két objektumot adattagonként hasonlítson össze a keretrendszer. Viszont ez az összehasonlítás csak akkor fog futni, ha a hash értékek megegyeznek. Biztos, ami biztos alapon, ilyenkor az ütközés elkerülés végett fut le a megfelelő metódus. Azonban. ha az értékek nem egyeznek, erre sor sem kerül.

Jelszó tárolás módszere

Tételezzük fel, hogy van egy web alkalmazásunk, amely felhasználókat léptet be. Ilyen rendszerek esetén sosem célszerű nyersen tárolni csak a jelszót, mivel az adatbázist megtörhetik, megszerezhetik. Ebben az esetben viszont ha egyszerűen, titkosítás nélkül vannak tárolva a felhasználók jelszavai, akkor bizony közvetlenül hozzáférhetnek a támadók az adatokhoz. Ez pedig azért probléma, mert nagyon sok esetben egy felhasználó mindenhova ugyanazt a jelszót használja. Tehát ha az xy.hu oldal ilyen bénán tárolja az adatokat, akkor a feltörése esetén nagy valószínűséggel Gipsz Jakab felhasználónak nem csak az xy.hu jelszavát szereztük meg, hanem a Facebook jelszavát is.

Sajnos szeretném azt mondani, hogy ez nem fordulhat elő, vagy azt, hogy csak kis oldalakkal történik ilyesmi. Valóság azonban az, hogy a Sony, a Yahoo és az Adobe is követett már el hasonló banális hülyeséget jelszavak tárolásakor és lett is belőle galiba rendesen. Tanulság ebből felhasználói szinten: egy jelszót sehol se használjunk kétszer (Ennek kivitelezéséről egy másik írásban volt szó).

Programozói szempontból a probléma kivédhető, ha nem közvetlenül jelszavakat tárolunk, hanem hash értékeket. Beléptetés esetén a beírt jelszóra kiszámoljuk a hash értéket és a tárolt értéket hasonlítjuk a számolt értékhez. Ha a kettő egyezik, akkor nagy valószínűséggel jó jelszót adtak meg. Ha az algoritmusunk is elég összetett, akkor nem kell félni az ütközésektől.

Önmagában ez a módszer sem tökéletes tárolásra, mivel az adattároló egységek masszív fejlődésével lehetővé vált visszakeresési táblázatok létrehozása. Ennek lényege az, hogy ismert bemenethez tároljuk a számított hash értéket, majd az érték alapján visszakereshető az eredeti bemenet. Természetesen jelenleg még nem minden jelszó van benne ilyen táblázatokban, de a legnépszerűbb jelszavakhoz van ilyen visszakeresési táblázat, illetve a GPU-k és a CPU-k fejlődésével egyre inkább valós félelemmé válhat az, hogy előbb-utóbb minden algoritmus visszakereshető lesz egyszerűen nyers erővel.

Persze erre a problémára is van megoldás. Nem gyári hash algoritmust kell használni, hanem némiképpen módosított bemeneti értékeket kell tárolni. Ezt az eljárást nevezzük sózásnak, vagy angolosan saltingnak. Ennek kivitelezése nem triviális feladat, de elég jó leírások és tanácsok lelhetőek fel a témában, amivel a visszakeresési táblázatok ellehetetleníthetőek.

Népszerű algoritmusok

CRC

A CRC  család az egyik legrégebbi hash algoritmus. Több változata is van, bitek számában van eltérés. Legnépszerűbb változata a CRC-32, de létezik 8, 16 és 64 bites variáns is. Alapvetően adatépség ellenőrzésre használják őket, mivel jelszó tároláshoz nem elég biztonságosak. Ezen algoritmusok előnye, hogy hardverből is könnyen megvalósíthatóak, mivel csak logikai műveletek sorozatát használják, a megvalósításhoz nincs szükség hagyományos értelemben vett CPU-ra.

MD5

Az MD5 nevében az MD betűk a Message-Digest (üzenet kivonat) szavakra utalnak. Az MD algoritmusok specifikusan kétkulcsos RSA tanúsítványok épségének ellenőrzésére és jelszó titkosításra lettek tervezve. Ebből az 5. generáció 1992-ben jelent meg. 128 bites és belül 4db 32 bites blokkban dolgozik. Alapvetően a kornak megfelelő hardverhez lett tervezve, ami abban az időben az Intel 386 volt (Ez a processzor pont 4db 32 bites regiszterrel rendelkezett).

Széles körben elterjedt, viszont már 1996-ban bebizonyosodott, hogy nem hibamentes. Ez még akkoriban nem tűnt végzetes hibának, de ez inspirálta az SHA család megszületését és 2004-ben bebizonyították, hogy létezik olyan módszer, amely segítségével generálható két egymástól független bemenet, amely ugyanazt a kimeneti értéket produkálja, vagyis MD5 esetén bizonyított, hogy nem ütközés mentes. Valójában oly annyira nem, hogy 239 próbálkozással garantálhatóan találni lehet két független bemenetet, ami ugyanazt a kimenetet produkálja. Ez gyakorlatban 549 755 813 888 próbálkozást jelent. Amit egy több, mint 10 éves (2006-ban megjelent) GeForce 8800Gt nagyjából 45 perc alatt tud teljesíteni. Tehát MD5 algoritmust még sózva sem célszerű alkalmazni jelszó tárolásra.

Az ütközés valós probléma minden algoritmus esetén. Megbízhatónak akkor mondható egy N bites hasító függvény ütközések tekintetében, ha 2N/2 kombinációt ki kell legalább próbálni ahhoz, hogy ütközést produkáljunk. Mint látható az MD5 esetén ennél jóval kevesebb kell, ezért nem megbízható

SHA

Az SHA család nevében a betűk a Secure Hash Algorithm rövidítésre utaznak. Ezen algoritmusokat az NIST publikálta. Kifejezetten jelszó tárolásra lettek kifejlesztve. Az SHA név eredetileg az SHA-0 algoritmusra utal, amely 1993-ban jelent volna meg, de még a megjelenése előtt találtak benne hibákat, ezért az SHA-1, az SHA-0 javított változata jelent meg, amelyet az NSA tervezett, specifikusan digitális aláírási célokra, 160 bitet használ. Az SHA-1 sem hibátlan, ezért 2010 óta nem ajánlják jelszó tárolásra.

SHA-1 esetén a probléma, ami miatt nem ajánlott, még csak elméleti szinten ismert. Elvileg kevesebb, mint 280 próbálkozással található ütközés, de ezt még senki sem bizonyította, mivel ez 120 892 581 961 462 917 470 6176 próbálkozást jelentene, ami még a mai kor számítógépeivel kivitelezhetetlen belátható időn belül.

A család újabb tagjai az SHA-256 és SHA-512, ezek használata ajánlott. Ezen algoritmusokat szokták SHA-2 néven is emlegetni, mivel a két algoritmus belsőleg szinte azonos. Annyi különbség van csupán, hogy a 256 bites változat belsőleg 32 bites értékekkel dolgozik, míg az 512 bites változat 64 bites belső értékekkel.

2012 óta elérhető az SHA-3 algoritmus is, amely ugyanazokat a kimeneti bitszámokat támogatja, mint az SHA-2. Viszont ezt nem az NSA tervezte, és ebből adódóan jelentősen eltér a belső felépítése és működése a korábbi algoritmusoktól.

A jövő

2009 óta a hash algoritmusok még egy célra használtak: pénzügyi tranzakciók lebonyolítására. A BitCoin technológia több szempontból is zseniális (már önmagában megérne egy leírást). Ezen szoftverben ezen algoritmusok arra vannak használva, hogy a tranzakciók épségét ellenőrizzék, mivel minden BitCoin pénztárcával rendelkező gép potenciálisan részt vehet bármelyik tranzakció lebonyolításában. Érdemes megemlíteni, hogy minden csak digitálisan létező pénznem hasonló technológiát alkalmaz. Ennek két oka is van. Egyrészt az, ha jól van kivitelezve, akkor csak elméleti szinten lehet a tranzakciót meghamisítani. A másik ok pedig az, hogy a többi, hasonló technológia alapja is a BitCoin.

Természetesen a jövőben valószínű, hogy egyre több helyen alkalmazva lesznek a különböző hasító függvények. De ugyanakkor az is biztos, hogy a számítógépek sebességének növekedésével a mostanában használt algoritmusok is előbb-utóbb elavulttá válnak.

Zárásképpen a computerphile csatorna által készített videót ajánlanám még a technológia jelentőségéről.