Zgoščevalne funkcije

(cryptographic hash functions, one-way hash functions)

Zgoščevalne funkcije preslikajo poljubno dolg niz znakov v blok konstantne dolžine, ki je nekakšen prstni odtis oziroma povzetek vhodnega niza (message digest, message fingerprint). Od zgoščevalne funkcije pričakujemo, da:

• je nemogoče najti dve različni sporočili, ki bi ju preslikala v isti blok;
• isto sporočilo vedno preslika v enak blok;
• iz zgoščevalnega bloka ni mogoče restavrirati sporočila (od tu ime one-way hash function);
• vsaka sprememba v sporočilu povzroči spremembo zgoščevalnega bloka.

Pri ocenjevanju zgoščevalnih funkcij se uporabljajo izrazi:

• collision resistance
  Temu, da dvema različnima vhodnima datotekama ustreza enak povzetek, rečemo kolizija. Jasno je, da za vsako zgoščevalno funkcijo obstajajo kolizije, ker imamo neskončno mnogo možnih vhodov, ki jih preslikamo v končno mnogo izhodov. Zahtevana lastnost zgoščevalne fukcije je, da se kolizij s sedanjo tehnologijo ne da najti dovolj hitro.
• preimage resistance
  To je lastnost, da je v primernem času nemogoče najti vhod, ki se preslika v vnaprej določen izhod.
• second preimage resistance
  To je lastnost, da je v primernem času nemogoče najti drugi vhod, ki se preslika v enak izhod, kot vnaprej določen vhod.

Rezultat mora torej enolično identificirati datoteko. Zaradi te lastnosti so povzetki postali nepogrešljivi pri digitalnem podpisovanju, kjer zašifriramo samo povzetek, in pa kot indikatorji nespremenjenosti podatkov v postopkih za prenos podatkov. Ne smemo pa teh funkcij zamenjevati s kompresijskimi postopki (zip in podobnimi), kjer vedno lahko iz zgoščene datoteke dobimo nazaj prvotno datoteko.

Postopek se začne tako, da vhodno datoteko razdelimo na bloke konstantne dolžine in konec dopolnimo do polnega bloka (padding). Potem zaporedoma obdelujemo bloke:

Ena od možnosti je, da za zgoščevalno funkcijo uporabimo katerega od simetričnih algoritmov: vhodno datoteko razbijemo na bloke take dolžine, kot ustrezajo algoritmu, prvi blok zašifriramo s ključem, vsak naslednji blok seštejemo (XOR) z zašifriranim povzetkom prejšnjega bloka. Vendar se zaenkrat v glavnem uporabljajo posebej za to razviti algoritmi (MD5, SHA-1), ker so hitrejši.

Kako dolg pa naj bi bil povzetek? Ali je 128 bitov dovolj, da ne bo možno najti enakih povzetkov različnih sporočil (collision free)?
Da se izpeljati oceno (glej n.pr. Douglas R.Stinson: Cryptography Theory and Practice, pogl.7), da bo ob n-bitov dolgih povzetkih, kar da k=2ⁿ možnih različnih povzetkov, s polovično verjetnostjo prišlo do kolizije ob približno 1.17 k^1/2 = 1.17 2^n/2 zgostitvah naključnih nizov. Za 128-bitne povzetke torej velja, da bo med 2⁶⁴ povzetki naključnih nizov ena kolizija z verjetnostjo 50%. Ta dolžina je zdaj ocenjena kot premajhna, zato priporočajo uporabo vsaj 160-bitnih povzetkov, posebej še za primere, kjer bomo povzetek hranili dalj časa.

Izkoriščanje kolizij pri prekratkih povzetkih imenujejo "birthday attack". Ime ima po paradoksu rojstnega dne (birthday paradox): če kot "povzetek" za vsakega človeka izberemo obletnico njegovega rojstnega dne (k je število dni v letu, k=365), iz zgornje formule dobimo rezultat 22.3. To pomeni, da bosta od 23 naključno izbranih ljudi z verjetnostjo 50% vsaj dva imela isti rojstni dan.

Najbolj znane zgoščevalne funkcije so

- MD5 (MD je okrajšava za Message Digest)

Razvil jo je Ronald Rivest leta 1991. Opisana je v RFC 1321.
Sporočilu v binarni obliki doda toliko bitov, da je skupno število deljivo s 512 in sicer je zadnjih 64 bitov rezerviranih za zapis dolžine sporočila. Prostor med koncem sporočila in temi 64 biti pa napolni tako, da najprej doda 1, potem pa same 0. Potem zaporedoma obdeluje bloke po 512 bitov. Blok razdeli na 16 besed po 32 bitov, ki jih obdeluje v štirih 32-bitnih registrih. Postopek ima štiri različne zanke. Povzetek je tisto, kar na koncu dobimo v registrih, torej je dolg 128 bitov. Njena uporaba ni več priporočljiva.

- SHA (Secure Hash Algorithm) - zdaj verzija SHA-1,

Razvili sta jo organizaciji NIST in NSA in je objavljena kot standard FIPS PUB 180-1 (1995). Ravno tako kot MD5 obdeluje bloke po 512 bitov. Obdeluje jih v petih registrih po 32 bitov, kar da 160-bitni rezultat.
Leta 2002 je NIST objavil standard FIPS PUB 180-2, ki določa SHA-256 s 256-bitnimi povzetki, SHA-384 s 384-bitnimi povzetki in SHA-512 s 512-bitnimi povzetki.

- HAVAL

To je verzija MD5, ki so jo razvili Yuliang Zheng, Josef Pieprzyk in Jennifer Seberry. Lahko se izbere število ponovitev algoritma in dolžino rezultata (od 92 do 256 bitov).

- RIPEMD-160

so leta 1996 razvili Hans Dobbertin, Antoon Bosselaers in Bart Preneel v sklopu evropskega projekta RIPE. Obdeluje 512-bitne bloke v petih zankah, rezultat je 160-biten.

Novi teoretični dosežki, objavljeni na konferenci Crypto 2004

Niels Ferguson in Bruce Schneier v knjigi "Practical Cryptography" (Wiley Publishing, 2003, stran 95) pravita, da zgoščevalne funkcije še niso bile dovolj analizirane in da znanje na tem področju za 20 let zaostaja za znanjem o blokovnih algoritmih. To se popravlja, saj je bilo na konferenci Crypto 2004 predstavljenih več projektov na to temo:

• Eli Biham je predstavil način, kako najti kolizije pri okrnjenem algoritmu SHA-1 (pri 34 zankah namesto 80, kolikor jih ima neokrnjeni algoritem). SHA-1 je torej še vedno varen algoritem.
• Antoine Joux - kolizije za SHA-0. Ta algoritem je bil predhodnik SHA-1 in se že več let ne uporablja.
• Wang, Feng, Lai in Yu - kolizije za MD4, MD5, HAVAL-128, RIPEMD .

Gre za teoretične dosežke, ki zaenkrat najbrž niso praktično uporabni. Če iz dveh datotek, ki se razlikujeta v nekaj bitih, dobimo enak povzetek, to še ne pomeni, da lahko za dve konkretni pogodbi dobimo enak povzetek. Reakcije na konferenco so spodbudile NIST, da je objavil sporočilo o uporabi SHA-1. V njem previdevajo zamenjavo SHA-1 s SHA-256 ali SHA-512 do leta 2010.

Februarja 2005 je dodatno vznemirjenje povzročil Schneierjev dnevniški zapis, v katerem omenja, da kroži povzetek članka Xiaoyun Wang, Yiqun Lise Yin in Hongbo Yu, kjer trdijo, da so našli učinkovite postopke za iskanje kolizij za SHA-1 v 2⁶⁹ poskusih, kar je seveda bistveno manj od 2⁸⁰ poskusov. V povzetku navajajo primer kolizije za okrnjen SHA-1 (58 zank namesto 80). Članek z naslovom Finding Collisions in the Full SHA-1 je na voljo od konca junija 2005. V intervjuju Yiqun Lisa Yin pravi, da so našli dve pomanjkljivosti SHA-1 - priprava datoteke na začetku postopka bi morala biti boljša in matematični postopek v prvih 20 zankah ima nepričakovane varnostne slabosti. Odmevi na to novico so naslednji:

• 2⁶⁹ izračunov je še vedno ogromno - pri 10⁹ poskusih na sekundo znese več kot 30 let. Povprečen PC zmore 200.000 izračunov SHA-1 na sekundo.
• Junija je NIST objavil program posvetovanja o odločitvah glede SHA-1, ki bo 31.10.in 1.11.2005.
• Julija 2005 sta Steven Bellovin in Eric Rescorla objavila analizo protokolov TLS, IPSEC in S/MIME glede prehoda na novo zgoščevalno funkcijo, kjer sta razložila, kaj bi bilo treba narediti in kako hitro.

Zaenkrat torej to še ne pomeni konca e-trgovanja (2⁶³ operacij je ogromna številka), je pa jasno, da bo treba SHA-1 nadomestiti z varnejšo funkcijo prej, kot smo mislili pred nekaj leti. NIST priporoča naslednje korake:

• prehod na SHA-2 (torej na SHA-224, SHA-256, SHA-384 ali SHA-512);
  Čeprav gre za isto vrsto algoritmov kot SHA-1, so toliko močnejši, da bi morali biti nezlomljivi še eno desetletje.
• pospešiti raziskave zgoščevalnih funkcij;
  NIST organizira konference, posebej namenjene zgoščevalnim funkcijam. Druga je bila 24. in 25. avgusta 2006 (povzetek).
• priprava izbora za novo zgoščevalno funkcijo na način, kot so ga izvedli za naslednika DES.

April 1998, dopolnjeno septembra 2006