Funcţii hash

De la Capisci

Salt la: navigare, căutare

Funcţiile hash (se citeşte hæş, sau măcar heş; numite şi funcţii de dispersie sau funcţii de rezumat; din englezescul hash functions) sunt, în ultimă instanţă, nişte funcţii matematice destul de oarecare; ele sunt grupate sub umbrela funcţiilor hash mai degrabă din punct de vedere al scopului urmărit de matematicieni decât din punct de vedere al formei lor intrinseci.

Funcţia hash ideală este în mod simultan:

  • universală: poţi să introduci orice parametru de intrare;[1]
  • repetabilă: de fiecare dată când introduci variabila X vei obţine acelaşi rezultat Y;
  • unidirecţională: este uşor să calculezi valoarea funcţiei pe baza variabilei introduse în funcţie (f(x) → x), dar imposibil să afli variabila pe baza valorii funcţiei (x → f(x));
  • biunivocă: ai garanţia că variabile diferite vor produce valori diferite ale funcţiei (unicitate) – dar şi viceversa, ai garanţia că o valoare a funcţiei corespunde cu o singură variabilă posibilă;
  • concisă: produce rezultate cu o mărime predeterminată, indiferent de mărimea variabilei de intrare.[2].

Vom vedea mai jos că funcţia hash ideală este la fel de realistă ca gazul ideal, mişcarea fără frecare sau comunismul. Deocamdată însă vom presupune că există o astfel de funcţie miraculoasă.

Dar la ce folosesc de fapt funcţiile hash? Care sunt funcţiile astea? Care sunt limitările lor? Să vedem, dară.

Cuprins

Cui prodest?[3]

În primul rând trebuie să ne întrebăm care este motivul pentru care ne-ar putea interesa de fel funcţiile hash. Există două situaţii în care beneficiile utilizării funcţiilor hash sunt evidente (deşi ele sunt de fapt folosite în mult mai multe aplicaţii).

Sume de control

Imaginaţi-vă că aţi descărcat un fişier uriaş de pe Internet şi vreţi să ştiţi dacă fişierul care se află pe discul dumneavoastră este într-adevăr identic cu originalul. O variantă ar fi să descărcaţi din nou acelaşi fişier şi să comparaţi cele două variante bit cu bit. Totuşi această abordare are cel puţin două probleme majore:

  1. Simplul fapt că este nevoie să descărcaţi de două ori acelaşi fişier uriaş este o problemă în sine. Cu siguranţă se poate găsi o variantă mai simplă de a verifica dacă a apărut vreo problemă la descărcare.
  2. Motivul pentru care doriţi să verificaţi dacă aveţi varianta originală ţine de multe ori de securitate. Se întâmplă relativ frecvent ca autorul unei aplicaţii gratuite să nu aibă posibilitatea de a oferi el însuşi fişierul pentru descărcare, caz în care site-ul autorului trimite către alt site „oglindă” pentru descărcarea aplicaţiei (mirror site). Există însă posibilitatea ca pe site-ul secundar aplicaţia să fi fost infectată cu software rău intenţionat – în acest caz degeaba descărcaţi aplicaţia de două ori şi comparaţi cele două versiuni: deşi identice, ambele variante descărcate vor fi la fel de infectate. Ar fi preferabil ca autorul însuşi să vă ofere pe propriul site o modalitate de a verifica dacă fişierul pe care l-aţi descărcat este într-adevăr identic cu originalul oferit de autor.

Soluţia pentru ambele probleme exemplificate mai sus este suma de control (în engleză „checksum”). Ca să înţelegeţi esenţa ideii de sumă de control gândiţi-vă la doi contabili care calculează în mod independent veniturile şi cheltuielile aceleiaşi firme de-a lungul aceluiaşi an fiscal. Amândoi trebuie să proceseze aceleaşi încasări multiple şi aceleaşi plăţi multiple ale firmei respective. Deşi cei doi contabili fac socotelile independent unul de celălalt, dacă toate calculele celor doi sunt corecte, atunci suma tuturor încasărilor pe întregul an va fi aceeaşi pentru ambii contabili; la fel şi suma tuturor cheltuielilor. Prin urmare, dacă cei doi contabili doresc să se asigure că au socotit corect, nu este nevoie să compare fiecare încasare înregistrată şi fiecare cheltuială înregistrată între ei -- este suficient să compare totalul pe care l-a calculat fiecare pentru cheltuieli şi totalul pe care l-a calculat fiecare pentru încasări: dacă ambele sume pe care cei doi contabili le controlează se potrivesc atunci este foarte puţin probabil să fie vreo problemă în restul calculelor.

Asta e toată ideea din spatele acestui concept de sumă de control: în loc să controlăm fiecare calcul în parte, controlăm numai dacă suma coincide. Revenind la contabilii de deasupra, am propus acolo ca cei doi contabili să controleze atât suma încasărilor cât şi suma cheltuielilor -- însă le putem propune la fel de bine să calculeze fiecare în mod independent profitul (adică diferenţa dintre încasări şi cheltuieli) şi să controleze numai dacă profitul este identic. Observăm deci că suma de control este de fapt doar o idee, un concept, un algoritm -- mai devreme cei doi contabili au comparat două valori separate, acum compară una singură. Vom vedea mai jos că este foarte important în ce fel anume calculăm suma de control, însă pentru moment se dovedeşte că trebuie mai întâi ca ambii contabili să facă aceleaşi calcule -- să folosească acelaşi tip de sumă de control.

Revenim acum la exemplul iniţial, în care nu avem doi contabili ci un autor care a creat un fişier şi un utilizator care îl descarcă. O variantă simplistă a sumei de control ar putea fi paritatea. Imaginaţi-vă că luaţi la mână fiecare octet descărcat, notând pe o foaie de hârtie dacă e par sau impar (octeţii au valori între 0 şi 255, deci are sens să le notăm paritatea). Să spunem că notaţi octeţii pari cu 0 şi octeţii impari cu 1. Puteţi apoi să adunaţi toate valorile de paritate ale tuturor octeţilor din fişierul descărcat (adică în esenţă să număraţi octeţii impari, fiindcă cei pari nu ar afecta suma) şi să folosiţi rezultatul ca sumă de control. Toate bune şi frumoase, doar că o astfel de funcţie hash încalcă cel puţin două dintre dezideratele funcţiei hash ideale: nu este nici pe departe biunivocă (dacă virusul este format numai din octeţi pari suma nu se schimbă) şi nici nu este concisă (cu cât fişierul este mai mare, cu atât suma de control este mai mare).

Dintre caracteristicile funcţiei hash ideale, sumele de control au nevoie în special de repetabilitate, concizie şi unicitate.

Securizarea datelor de acces

Imaginaţi-vă că aveţi un magazin online care are clienţi înregistraţi; clienţii se autentifică folosind adresa e-mail şi o parolă, iar pe baza acestor date de identificare pot face cumpărături cu cartea de credit.[4] Dacă aţi stoca datele de acces în baza de date „în clar”[5], atunci orice persoană care are acces într-un fel sau altul la baza de date are în mod automat acces la absolut orice cont al oricărui utilizator înregistrat.[6] Pentru a evita astfel de situaţii, majoritatea programatorilor aleg să nu stocheze parolele în clar, ci ca rezultat al unei funcţii hash aplicate pe parola introdusă de utilizatori. În acest fel, chiar dacă baza de date este compromisă, este totuşi dificil să fie aflate parolele originale.

Dintre caracteristicile funcţiei hash ideale, securizarea datelor de acces are nevoie în special de repetabilitate, unidirecţionalitate şi biunivocalitate.

Idealism versus realism

Am văzut în secţiunea anterioară două exemple concrete de utilizare a funcţiilor hash: (1) sume de control: pentru că dorim să ne asigurăm că am primit mesajul corect şi (2) securitate: pentru că ne dorim să verificăm validitatea unui mesaj secret. De fapt, dacă analizăm mai atent cele două situaţii de deasupra, constatăm că sunt unul şi acelaşi lucru: dorim să ne asigurăm că niciun factor extern nu poate modifica mesajul pe care-l trimitem sau recepţionăm fără ca destinatarul să sesizeze inadvertenţa.[7]

Acum că ştim de ce ne trebuie funcţii hash, hai să vedem cam ce hram poartă funcţiile hash reale. V-a mirat cu siguranţă afirmaţia din secţiunea introductivă conform căreia funcţiile hash ideale sunt în esenţă nişte himere — gazul ideal nu poate exista deoarece se întâmplă că locuim într-o lume imperfectă, însă funcţiile locuiesc într-o lume matematică perfectă, deci care-i problema?

Criteriul prioritar

Prima problemă a funcţiei hash ideale (aşa cum am definit-o în secţiunea introductivă) este o contradicţie logică, pe care n-o putem rezolva nici în lumea ideală a matematicii. Ne dorim ca funcţia noastră să fie în mod simultan universală, biunivocă şi concisă. Or astea trei cerinţe nu se pot îndeplini în mod simultan niciodată. Problema porneşte de la cerinţa conciziei — cu alte cuvinte, să „încapă” într-un număr oarecare de cifre. De exemplu orice număr natural mai mic de un milion încape într-un spaţiu de şase cifre. Asta cerem noi funcţiei hash ideale: vrem ca rezultatul ei să încapă în N cifre. Evident, asta nu se poate dacă ne mai dorim în plus ca funcţia să fie în plus (1) biunivocă şi (2) universală. Dacă respectăm (1) atunci putem accepta cel mult numere de N cifre (deci încălcăm (2))[8]; pe de altă parte, dacă respectăm (2) atunci va exista o infinitate de date de intrare pentru care vom produce aceeaşi valoare de ieşire (deci încălcăm (1)).

Prin urmare nu se poate (nici măcar teoretic) să obţinem în mod simultan toate cerinţele originale (biunivocă, concisă şi universală). Pe de altă parte, ştim conform definiţiei că avem nevoie de concizie (dacă funcţia hash nu e concisă atunci mărimea rezultatului creşte cu valoarea de intrare[9]).

Aşadar, dintre cele trei caracteristici dezirabile (dar incompatibile), concizia este prioritatea: trebuie să căutăm un compromis în jurul conciziei, sacrificând celelalte două criterii ideale. Am rămas cu două criterii între care trebuie să decidem prioritatea: biunivocitate şi universalitatea. Dar am văzut deja în exemplele de deasupra că universalitatea nu poate fi opţională: trebuie să putem folosi funcţia hash pentru orice mesaj, parolă sau fişier, indiferent de lungimea acestora. Aşadar prioritatea criteriilor pentru o funcţie hash practică este următoarea:

  1. concizie: mărime constantă a rezultatului
  2. universalitate: trebuie să acceptăm orice valoare de intrare
  3. biunivocitate: două valori de intrare diferite trebuie, pe cât posibil, să producă rezultate diferite

Coliziuni

Prin „coliziune” se înţelege situaţia în care două valori diferite de intrare produc aceeaşi valoare de ieşire a funcţiei hash. Cu alte cuvinte, coliziunile sunt situaţiile în care se încalcă biunivocitatea sumelor de control. Am văzut mai sus că acest lucru este la fel de inevitabil ca moartea şi taxele: nu putem aştepta biunivocitate perfectă atâta timp cât valoarea de ieşire trebuie să fie concisă.

În secţiunile anterioare am căutat să identificăm criteriile ideale ale funcţiei hash ideale. S-a dovedit că nu le putem satisface pe toate simultan, iar „victima” s-a dovedit a fi biunivocitatea. Este important să acceptăm că nu ar fi putut exista niciun alt compromis mai bun. Nu are nimeni nicio vină: criteriile de mai sus au fost prioritizate din motive perfect logice, iar rezultatul final este că biunivocitatea este cea mai puţin importantă (sau, altfel spus, concizia şi universalitatea sunt mai importante).

În tot cazul, se dovedeşte că rămâne să identificăm situaţiile (măcar teoretice) în care biunivocitatea devine o problemă.

În practică

După cum probabil vă aşteptaţi, funcţiile hash nu sunt genul de funcţii cuminţi cu care aţi făcut cunoştinţă în liceu. Nici vorbă — alea din liceu sunt nişte amărâte de funcţii ale căror rezultate variază destul de previzibil în funcţie de valoarea de intrare; funcţiile hash, dimpotrivă, trebuie prin definiţie să varieze haotic atunci când schimbăm oricât de puţin valoarea de intrare -- altfel n-ar fi unidirecţionale. Din fericire, funcţiile hash au în practică de-a face doar cu valori întregi (nu uitaţi, computerele funcţionează la nivel elementar doar cu 0 şi 1). Chiar şi aşa, o funcţie hash trebuie musai să amestece valorile de intrare într-un mod care este atât haotic (pentru unidirecţionalitate) cât şi previzibil (pentru repetabilitate).

MD5

Prima funcţie hash folosită pe scară largă a fost MD5 („Message Digest versiunea 5”).[10] MD5 a fost algoritmul hash standard de facto de-a lungul unei întregi decade (aproximativ 1994-2005) pentru aplicaţiile practice indicate aici (sumă de control şi securizare a datelor de acces). Din păcate s-a dovedit că MD5 suferă de prea multe coliziuni. O funcţie hash bună distribuie în mod uniform coliziunile de-a lungul şi de-a latul domeniului de intrare, în aşa fel încât un atacator să nu poată prevedea ce valori de intrare pot produce valoarea de ieşire (cunoscută) a funcţiei hash. S-a dovedit că MD5 nu este o funcţie bună în privinţa asta: dacă-mi spui care este suma de control a fişierului tău atunci voi reuşi relativ uşor să găsesc la rândul meu o altă combinaţie de octeţi care să producă acelaşi rezultat; prin urmare voi putea să injectez un virus în fişierul pe care-l descarci şi voi face în aşa fel încât fişierul cu virus să producă aceeaşi sumă de control MD5 ca şi fişierul original.

Familia SHA

Spre deosebire de familia de funcţii hash „MD”, familia „SHA” are un nume considerabil mai ambiţios: dacă „MD” („message digest”) înseamnă aproximativ „esenţa mesajului” (ceea ce reprezintă în mod rezonabil ideea de funcţie hash), acronimul „SHA” este în mod oficial o prescurtare pentru „secure hash algorithm” („algoritm de hash securizat”). La fel ca şi funcţiile din familia MD, şi funcţiile SHA au apărut în diverse generaţii şi versiuni, fiecare cu bunele şi relele ei.

  • SHA-0 nu este folosită pe scară largă şi este considerată la fel de vulnerabilă ca şi MD5 (şi tot din cauza coliziunilor)
  • SHA-1 este folosită pe scară largă şi este considerată teoretic vulnerabilă
  • SHA-2 este folosită pe scară largă şi nu este considerată vulnerabilă în mod particular (subfamilia SHA-2 este în general cunoscută sub nume care identifică dimensiunea în biţi a valorii de ieşire: SHA-256, SHA-512 ş.a.m.d.)
  • SHA-3 nu este folosită pe scară largă şi nu este considerată vulnerabilă.

Note

  1. Conceptul de funcţie „universală” este inventat de mine; din păcate nu există un alt termen concis consacrat în limba română pentru ce vreau să spun aici, aşa că am fost nevoit să improvizez. Pentru rigurozitate, am folosit acest cuvânt pentru a reprezenta ideea unei funcţii care permite un domeniu infinit de valori de intrare.
  2. Din nou, am fost nevoit să inventez un termen pentru concizie. Pentru rigurozitate, am folosit acest cuvânt pentru a reprezenta ideea unei funcţii ale cărei rezultate aparţin unei mulţimi finite de valori posibile.
  3. Cui foloseşte? (latcui „produce”?). Variantele qui prodest, qui bono pe care le găsiţi pe Internet sunt greşite.
  4. Acesta ar fi în mod evident un design dezastruos din punct de vedere al securităţii; l-am folosit ca exemplu doar pentru a puncta importanţa securizării server-side a datelor de acces.
  5. Adică aşa cum sunt ele scrise de utilizator atunci când se autentifică: e-mail „gogu@gmail.com”, parola „parola_mea”.
  6. Există o sumedenie de scenarii în care persoane nedorite pot ajunge să aibă acces la baza de date. Cele mai evidente variante sunt situaţia în care aplicaţia este găzduită pe un server partajat şi situaţia în care un server este compromis din punct de vedere al securităţii, însă există variante la fel de simple şi în cazul serverelor bine securizate – de exemplu situaţia în care se rătăceşte suportul fizic pe care este stocată o copie de rezervă (backup).
  7. De observat că nu ne interesează să identificăm ce anume s-a modificat: ne dorim doar să aflăm dacă mesajul a fost alterat.
  8. Evident, am perpetuat aici paradigma numerelor naturale începută mai sus, în aceeaşi formă simplistă în care am început-o: presupunem că întotdeauna scriem doar numere naturale notate în baza 10. Însă deşi abordarea pare naivă, concluzia este riguros corectă: indiferent de baza de numeraţie, limitarea se aplică exact la fel.
  9. Există o sumedenie de motive concrete pentru care concizia — sau, mai riguros, constanţa mărimii funcţiei hash — este importantă, în special în contextul securităţii informaţiei, însă nu vom intra în detalii aici. Foarte pe scurt, atunci când operăm în domeniul criptografic dorim să oferim cât mai puţine informaţii unui potenţial atacator care are acces la rezultatul funcţiei hash; o funcţie hash a cărei mărime creşte cu mărimea mesajului de intrare este contraproductivă deoarece oferă informaţii atacatorului despre mărimea mesajului original, dat fiind că rezultatul unei astfel de funcţie hash ar creşte proporţional cu mesajul. Pe de altă parte, dacă ne-am propune în mod absurd să respectăm riguros condiţia de biunivocitate în detrimentul oricărei alte condiţii am sfârşi cu o funcţie hash strict teoretică al cărei rezultat ar avea întotdeauna lungime infinită, indiferent de valoarea de intrare. Aceasta ar fi o soluţie absolut perfectă, dar oarecum nepractică, dat fiind că rezultatul funcţiei nu ar putea fi înregistrat niciodată.
  10. Ca să fie spus, MD5 nu este cu nimic mai special decât MD4, de exemplu (deşi, evident, MD5 este o versiune îmbunătăţită a lui MD4). MD5 este special nu atât prin calităţile sale intrinseci (veţi vedea de altfel în corpul articolului că nu este un algoritm foarte bun), cât pentru că a fost prima funcţie hash folosită la nivel cu adevărat global.