Funcţii hash

De la Capisci

Acest articol este în lucru! Unele informaţii s-ar putea să fie incomplete, eronate, sau pur şi simplu s-ar putea să nu aibă sens. Vă rugăm să reveniţi în curând pentru versiunea finală.

Funcţiile hash (se citeşte hæş; 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:

• deterministă: de fiecare dată când introduci variabila X vei obţine acelaşi rezultat Y;
• unidirecţională: este uşor să să calculezi valoarea funcţiei pe baza variabilei introduse în funcţie, dar imposibil afli variabila pe baza valorii funcţiei;
• biunivocă (uniform distribuită): 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.

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ă.

Cui prodest?^[1]

În primul rând trebuie să ne întrebăm care este motivul pentru care ne-ar putea interesa funcţiile hash de fel. 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 situaţii):

Sume de control

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

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 mari:

• În primul rând, 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.
• În al doilea rând, 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 pentru descărcarea aplicaţiei. 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 să indice o sumă de control pe propriul site, în aşa fel încât orice discrepanţă între suma de control a originalului (oferită de autor) şi suma de control a variantei descărcate (calculată de dumneavoastră) să indice eventualele modificări nedorite.

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).

Securizarea datelor de acces

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

Imaginaţi-vă că aveţi un magazin virtual 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.^[2] Dacă aţi stoca datele de acces în baza de date în clar^[3], 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.^[4] 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.

Note

1. ↑ Cui foloseşte? (lat – cui „produce”?). Variantele qui prodest, qui bono pe care le găsiţi pe Internet sunt greşite.
2. ↑ 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.
3. ↑ Adică aşa cum sunt ele scrise de utilizator atunci când se autentifică: e-mail „gogu@gmail.com”, parola „parola_mea”.
4. ↑ 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 sau 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).