9. fejezet - Hash függvények és a digitális aláírás

9.1. Hash függvények

9.1.1. Hash függvények fogalma

A hash függvények fogalmával az informatika más területén már találkozhattunk, adatbázisok rendszerezésére alkalmazunk. A kriptográfiában az adatok integritásának biztosítására szolgál. Ahelyett, hogy a tetszőleges hosszú és nagyméretű adatsor integritásának védelmét biztosítjuk, inkább mindössze egy fix hosszúságú, igen kisméretű bitsztringre (kb. 160 bit) koncentrálunk. A tetszőleges méretű üzenetre egy hash függvényt hajtunk végre, melynek eredményeként egy fix méretű hash értéket (üzenetkivonatot vagy lenyomatot) kapunk. A hash függvény tehát egy H:{0,1}*--›{0,1}n függvény, azaz egy tetszőleges hosszúságú bitsorozatot egy fix hosszúságú bitsorozatba képez. Amennyiben sikerül az üzenetkivonat integritását megőrizni, akkor könnyen ellenőrizhető, hogy a nagyméretű eredeti üzenetünk változott-e. Az ellenőrző fél lefuttatja a hash függvényt az eredeti üzenetre és az eredményként kapott üzenetkivonatot összehasonlítja a korábbi üzenetkivonattal. Ha a lenyomatok megegyeznek, akkor az üzenet nem módosult. A hash függvények alkalmazásával a nyilvános, nem biztonságos csatornán integritásvédelmet lehet megvalósítani.

Egy jó példa a hash függvény használatára, valamely programkód változatlanságának ellenőrzése. Tekintsünk például egy titkosító eljárást, melyet a kliens gép merevlemezén tárolunk. Első alkalommal kiszámítjuk a program kódjának lenyomatát és egy smart kártyára másoljuk, melyet állandóan magunknál tartunk. Későbbiekben minden egyes használat előtt kiszámítja a merevlemezen levő programkód hash értékét és összehasonlítja a smart kártyán levő lenyomattal. Ha megegyeznek, akkor a kód nem módosult és biztonságosan használható.

Ahhoz, hogy ez a megoldás biztonságos legyen, garantálni kell, hogy az üzenet egyetlen bitjének módosulása maga után vonja a lenyomat változását. Ami valójában azt jelenti, hogy ne lehessen megadni két olyan üzenetet, melynek lenyomata megegyezik. A hash függvények nem injektívek, hiszen tetszőleges méretű üzenetekhez egy fix méretű bitsorozatot rendelünk. Amennyiben a lenyomat hossza k, akkor 2k db különböző lenyomat lehetséges, míg az eredeti lehetséges üzenetek száma sokkal több. Ezért léteznek üzenetek, melyeknek lenyomata megegyezik. Ezek alapján célunk az, hogy nehéz (polinomiális idő alatt ne lehessen) legyen olyan üzeneteket találni, melyek hash értéke megegyezik. Az ilyen hash függvényeket ütközésmentes hash függvényeknek nevezzük. A különbség a kriptográfia, illetve általánosan az informatikában használt hash függvények között, hogy az előbbi esetben nehéz ütközéseket találni, míg az utóbbinál az ütközés előfordulása csak nem valószínű.

A kriptográfiában használt hash függvényeket az elkötelezettségi rendszereknél (commitment scheme) is alkalmazzuk. Ha valaki szeretné elkötelezni magát egy x adathoz, anélkül, hogy megmondaná az x értékét, akkor kiszámítja H(x||r) értéket, ahol H egy hash függvény és r egy véletlen bitsorozat. Később felbontja elkötelezettségét, azaz megadja az x és az r értékeket. Az ilyen esetekben fontos az, hogy H(x||r) ismeretében az x értékről ne tudjunk meg hasznos információkat, azaz a H hash függvénynek egyirányúnak kell lennie. Az egyirányúság biztosítja, hogy a lenyomatból az eredeti üzenet kiszámítása nehéz. Az egyirányú hash függvény lehetővé teszi, hogy egy entitás az üzenet lenyomatának megadásával „borítékolja” az üzenetet, azaz elrejtse, de ugyanakkor elkötelezze magát amellett.

Az elkötelezettségi rendszerek alkalmazására egy jó példa a pénzfeldobás telefonon. A játék lényege az, hogy a két résztvevő nem látja egymást, csak telefonon keresztül beszélgetnek. Az egyik fél feldob egy pénzérmét, és megkéri a másikat tippeljen, hogy fej avagy írást kapott. A másik fél megtippeli, hogy fej. A pénzt feldobó azt fogja mondani, hogy nem nyert, hiszen írás lett. Mi a garancia arra, hogy írás lett? A pénzt feldobó személy akár füllenthetett is arról, hogy mit dobott. Ez a játék szabályossá válik, ha valamely elkötelezettségi rendszert használunk. Az egyik személy feldobja az érmét és az eredményt egy véletlen értékkel együtt hash-eli. Az így kapott lenyomatot megmondja a másik félnek és kéri, hogy tippeljen. A tipp után megadja az eredményt és a véletlen értéket is, melyek alapján a tippelő fél ellenőrizheti, hogy tényleg az lett-e a pénzfeldobás eredménye. A rendszer biztonságához két dolog is szükséges: az egyirányúság, illetve, hogy nehéz legyen a lenyomathoz egy másik megfelelő ősképet találni.

9.1.2. Támadások

A hash függvényekkel szembeni támadásokat két fő kategóriába sorolhatjuk: az őskép elleni és ütközéses támadások.

1. Őskép elleni támadások

Kétféle támadást különböztetünk meg, az első és a második őskép elleni támadást.

  • Az (első) őskép elleni támadás célja, hogy a támadó az y lenyomat esetén találjon egy olyan x értéket, hogy H(x)=y. Ha egy hash függvény az első őskép elleni támadással szemben biztonságos, akkor őskép ellenálló hash függvény, a függvény egyirányúságára utal.

  • A második őskép elleni támadás célja, egy adott x érték estén olyan x’ érték megadása, hogy H(x)=H(x’), ahol x’≠x. Amennyiben egy hash függvény a második őskép elleni támadással szemben védettséget ad, akkor gyengén ütközésmentes vagy második őskép ellenálló hash függvénynek nevezzük.

2. Ütközéses támadások

Az ütközéses támadás célja, hogy a támadó meghatározzon két különböző tetszőleges üzenetet, melyek hash értéke megegyezik, azaz találjon x és x’ bitsorozatot, ahol x’≠x és H(x)=H(x’). Jelentős különbség az ütközéses és az őskép elleni támadások között, hogy az ütközéses esetben a lenyomat sem és az inputok egyike sem áll a támadó rendelkezésére. Speciálisan adott prefixű ütközéses támadás célja, hogy a támadó meghatározzon két különböző p1 és p2 bitsorozathoz, ahol p1≠p2, olyan m1 és m2 bitsorozatokat, hogy H(p1||m1)=H(p2||m2). A || szimbólum a konkatenációt jelöli. Az ütközéses támadással szemben biztonságos hash függvényeket (erősen) ütközésmentesnek nevezzük.

Különböző szituációkban a releváns támadások különbözőek. Integritásvédelem estén a támadó célja, hogy egy adott x üzenethez olyan x’ üzenetet találjon, melyek lenyomatai megegyeznek. Ez tipikusan a második őskép elleni támadás. Az elkötelezettségi rendszerek esetén, mint ahogy azt már részleteztük fontos az egyirányúság, azaz a támadó sikeres első őskép elleni támadást akar végrehajtani. Illetve, a támadó próbál azzal csalni, hogy az x üzenetet kicseréli egy x’ üzenetre még az elkötelezettség felfedése előtt, azaz ütközéses támadást végez. A fent részletezett pénzfeldobós játék esetén a támadó adott prefixű ütközéses támadást indít, hiszen célja az, hogy olyan „véletlen” m1 és m2 értékeket „találjon ki”, hogy H(„fej”||m1)=H(„írás”||m2) teljesüljön. Bizonyítható, hogy az erősen ütközésmentes függvények gyengén ütközésmentesek, és bizonyos feltételek mellett őskép ellenálló is (1). A digitális aláírásoknál erősen ütközésmentes, őskép ellenálló hash függvényeket alkalmazunk.

9.1.3. MD5

Az MD5 (Message-Digest algorithm 5) egy 128 bites hash értékkel rendelkező hash függvény. Az MD5-öt az RSA egyik alkotója Rivest fejlesztette ki 1991-ben. 2004-ben több biztonsági rést fedeztek fel az algoritmusban, mely alapján 2005 óta digitális aláírásoknál használata nem javasolt.

Hash függvények készíthetőek kompressziós függvényekből. Az CF:{0,1}n--›{0,1}m függvényt kompressziós függvénynek nevezzük, ha m<n. Látható, hogy a kompressziós függvények egy fix hosszúságú üzenethez egy rövidebb fix hosszúságú üzenetet rendel.

Az MD5 konstrukciójában is kompressziós függvényt alkalmazunk, melyet egymástól függetlenül Ralph Merkle és Ivan Damgard tervezett 1989-ben. Ennek a CF kompressziós függvénynek két inputja van, egy 128 bit hosszú Y sztring és egy 512 bit hosszú B blokk, a függvényérték pedig egy 128 bites sztring. Egy tetszőleges hosszúságú x üzenet lenyomatának generálása a következőképpen történik:

  1. A tetszőleges hosszú m üzenetet kitöltjük úgy, hogy a hossza az a legkisebb érték legyen, mely osztható 512-vel. A kitöltést egy 1-es bittel kezdjük, majd tetszőleges számú 0-t írunk. A kitöltést az eredeti m üzenet 64 biten ábrázolt hosszával zárjuk. Az így kitöltött üzenetet jelöljük M-mel.

  2. Vágjuk fel az M üzenetet 512 bit hosszú blokkokra, jelölje B1, B2, …Bn az így keletkezett blokkokat.

  3. Vegyünk egy fix 128 bit hosszú kezdeti vektort: IV, és legyen Y0=IV.

  4. Kiszámítjuk Yi=CF(Yi-1,Bi) kompressziós függvényértékeket,ahol i=1,…,n.

  5. Az eredeti m üzenet lenyomata: H(m)=Yn , azaz a keletkezett hash érték az utolsó blokkra vonatkozó kompressziós függvényérték lesz, mely 128 bit.

Meg kell, hogy jegyezzük, hogy ez a konstrukció maximálisan 264 bit hosszú üzenetekre alkalmazható, hiszen az üzenet hosszát 64 biten ábrázoljuk. Ez a gyakorlatban a szám nagysága miatt nem jelent megkötést. Bizonyítható, hogy az előbbi konstrukció esetén, ha a CF kompressziós függvény ütközésmentes, akkor a hash függvény is az.

Az MD5 CF kompressziós függvénye a Davies-Meyer kódoló algoritmusán alapszik, mely egy 128 bites és egy 512 bites sztringet 128 bites sorozatba képez. Jelölje CF0 ezt a kódoló algoritmust, Y=(A,B,C,D) a 128 bites input bitsztringet és Bi az 512 bites blokkot. Ekkor CF(Y,Bi)=CF0(Y,Bi)+(A,B,C,D), ahol az összeadást modulo 232 végezzük. Első körben az A,B,C,D értékek definiált fix konstansok.

A CF0 kódoló algoritmus főbb lépéseit ismertetjük csak, részletes leírást RFC 1321 szabvány (2) tartalmazza. Minden egyes Bi blokkot 16 db 32 bites sztringre bontunk. Az algoritmus 4 körből áll. Minden egyes körben a következő transzformáció hajtódik végre:

ROTLs(a+fi(b,c,d)+x+k)+b

A ROTLs() bitenkénti balra történő rotációt jelöl, a felső indexben levő s érték a rotáció mértékét adja meg. Az s és k fix, definiált konstansok. Az x jelöli az 512 bites Bi blokk 32 bit hosszú részét. Az a,b,c,d kezdőértékei A,B,C,D, és az algoritmus befejezése után ez négy érték együttesen fogja adni a hash értéket. Az fi (i=1,…,4) bitenkénti logikai függvény, mely a következőképpen definiáltak:

  • f1(b,c,d)=(b AND c) OR ((NOT b)AND d)

  • f2(b,c,d)= (d AND b) OR ((NOT d)AND c)

  • f3(b,c,d)=b XOR c XOR d

  • f4(b,c,d)=c XOR (b AND (NOT d))

Az MD5 ellen több gyakorlatban is alkalmazható támadást is bemutattak. Az MD5 nem mutat védettséget az ütközéses támadással szemben, illetve sikeres adott prefixű ütközéses támadást is végre lehet hajtani. 2005-ben sikeres támadást mutattak be tanúsítványokon, ugyanazon két különböző nyilvános kulcs MD5 lenyomata megegyezett. Tehát a gyakorlatban már nem javasolt alkalmazni.

9.1.4. SHA

A másik gyakorlatban elterjedt hash függvény az SHA (Secure Hash Algorithm). Az SHA az MD5 rendszeren alapszik, 1993-ban az amerikai FIPS 180 szabványban lett ismertetve. Tipikusan digitális aláírási rendszereknél alkalmazzák. Az SHA lenyomat 160 bit hosszú, a Merkle-Damgard konstrukciót használja, a kompressziós függvény 160 bites és 512 bites sztringhez 160 bitet rendel (160×512--›160). A kompressziós függvény a következőképpen adott: CF(Y,Bi)=CF0(Y,Bi)+(A,B,C,D,E).

Hasonlóan az MD5-höz az SHA is egy CF0 kódoló függvényt futtat, mely egy 160 bit hosszú Y=(A,B,C,D,E) és 512 bites Bi blokkhoz 160 bitet rendel. További részleteket a (3) dokumentumban olvashatunk.

Az amerikai szabvány az SHA és SHA-1 algoritmuson kívül tartalmazza az SHA224, SHA256, SHA384 és SHA512 algoritmusokat is, melyeket közös néven SHA-2-nek is neveznek. Ez a négy algoritmus nagyon hasonlít az SHA-hoz, csak komplexebb. Az elnevezésekben a háromjegyű számok az algoritmus által generált lenyomat hosszát jelzik. Az SHA256 egy 256 bit hosszú üzenetkivonatot eredményez. Az SHA384 és SHA512 a 32 bites részblokkok helyett 64 bitesekkel számol és az 512 bites blokkméret helyett 1024 bites üzenetblokkokat kezel.

9.1.5. Születésnapi paradoxon

A születésnapi paradoxon alapvető kérdése a következő. Tegyük fel, hogy egy szobában véletlenül választott emberek egy csoportja tartózkodik. A kérdés az, hogy mennyi a valószínűsége, hogy legalább két személynek megegyezik a születésnapja. A meglepő válasz az, hogy annak valószínűsége, hogy legalább két ember ugyanazon a napon született több mint 50%, ha a csoport létszáma 23. Emiatt a meglepő eredmény miatt hívjuk paradoxonnak, hiszen a 23 fő nagyon kis létszám az év 365 napjához képest.

A valószínűség kiszámítása a következő képlet alapján történik, ha az év 365 napját tekintjük és a véletlenül választott személyek száma n:

Ez a valószínűség jól közelíthető a

A születésnapi paradoxon a hash függvényeknél nagy jelentőséggel bír. Hiszen a paradoxon segítségével megadhatjuk annak valószínűségét, hogy mekkora egy ütközés találása. Ugyanis, ha egy n bit hosszú lenyomatot adó hash függvényt tekintünk, akkor a születésnapi paradoxon szerint 2(n/2) véletlenül választott üzenet között annak valószínűsége, hogy ütközés lesz, azaz két érték hash értéke megegyezik 50%-hoz közeli érték. Ez alapján a hash érték méretét úgy kell meghatározni, hogy 2(n/2) elég nagy legyen, hogy a gyakorlatban az ilyen jellegű támadás kivitelezhetetlen legyen. Jelenleg ez az n érték 160.

Következésképpen az MD5 által generált 128 bites sztring az elég kicsi ahhoz, hogy ilyen jellegű támadást lehessen megvalósítani. Az MD5CRK projekt keretén belül ütközést találtak a születésnapi támadás felhasználásával.

9.1.6. Üzenethitelesítés

Az üzenethitelesítő kódokra a MAC (Message Authentication Code) rövidítést is használják. Ezek a kódok egy dokumentum hitelességét garantálják egy nem biztonságos csatorna használatakor. A küldő és a fogadó fél biztonságos csatornán kicserél egy titkos kulcsot, majd a küldő fél a titkos kulccsal elkészíti üzenetének MAC kódját. Az üzenet is és a kód is továbbítódik. A fogadó fél a titkos kulcs ismeretében szintén kiszámítja a kapott üzenet MAC kódját és ellenőrzi, hogy a két MAC kód megegyezik-e.

Az üzenethitelesítő kódok, mint ahogy a neve is mutatja, az üzenet hitelességét garantálja, ami magába foglalja az üzenet adatintegritását, azaz változatlanságát és az üzenet eredetét is igazolja. Következésképpen MAC használatával ellenőrizni tudjuk, hogy a kapott üzenet megegyezik az elküldöttel, valamint az üzenetet ténylegesen az a személy vagy entitás küldte, akitől várjuk.

A következő alfejezetben a digitális aláírással foglalkozunk, mely szintén a hitelesítés eszköze. Az alapvető különbség a hitelesítő kódok és a digitális aláírások között, hogy a digitális aláírás letagadhatatlanságot is garantál, azaz bárki a nyilvános kulcs ismeretében ellenőrzést végezhet, míg a MAC esetén csak a két fél képes ellenőrzést végezni, hiszen csak ők ismerik a titkos kulcsot.

Egyik legelterjedtebb hitelesítő kód a CBC-MAC, mely az ISO/IEC 9797 szabvány. Ugyanakkor hitelesítő kódot kaphatunk hash függvényekből is a következőkben ismertetett megoldást HMAC-nek nevezik.

9.1.6.1. HMAC

A HMAC (Hash-based Message Authentication Code), az RFC 2104 Internet szabvány. A HMAC egy a kriptográfiában alkalmazott hash függvény és egy titkos kulcs kombinációja. A konstrukció lehetővé teszi az MD5 és a SHA-1 hash függvény alkalmazását is, ekkor HMAC-MD5-nek vagy HMAC-SHA-1-nek nevezzük a hitelesítő kódot.

A HMAC az üzenetet szintén blokkokra bontja, melynek mérete MD5 és SHA-1 esetén 512 bit. A blokkokra kompressziós függvényt alkalmazva a HMAC egy 128 vagy 160 bit hosszú sztringet ad attól függően, hogy milyen hash függvényt alkalmaz. Legyen m az üzenet, melynek hitelesítő kódját kívánjuk meghatározni, jelölje K a titkos kicserélt HMAC titkos kulcsot és legyen H egy választott hash függvény. A lépések a következők:

  1. Ha K hosszabb, mint a hash függvény blokkmérete, akkor legyen K a H(K) érték, így K rövidebb, mint a blokkméret.

  2. Ha K rövidebb, mint a blokkméret, akkor kitöltjük 0-val míg a mérete megegyezik a blokkmérettel.

  3. Kiszámítjuk H((K⊕opad)||H((K⊕ipad)||m)), ahol ipad és opad két fix bitsztring. Az opad (outer padding) külső kitöltést, míg az ipad (inner padding) belső kitöltést jelöl. Az ipad egy blokkméretnyi hexadecimális konstans: 0x363636…36. Az opad szintén egy blokkméretnyi hexadecimális konstans: 0x5c5c5c…5c5c.