Funcțiile hash explicate

Când descărcați un program și comparați o sumă de control, vă autentificați cu o parolă, semnați un document sau adăugați un bloc în Bitcoin, o funcție hash este la lucru. Ea transformă orice cantitate de date într-o amprentă scurtă de mărime fixă, rezumatul, într-un mod care nu poate fi anulat sau falsificat. Ideea este simplă, însă cerințele pentru un hash bun sunt stricte, iar două dintre cele mai folosite, MD5 și SHA-1, nu le-au făcut față.

Două mesaje care diferă printr-o literă intră într-o funcție hash și ies ca două rezumate SHA-256 complet diferite, cu biții inversați marcați într-o grilă
Două mesaje care diferă printr-o literă intră într-o funcție hash și ies ca două rezumate SHA-256 complet diferite, cu biții inversați marcați într-o grilă

O amprentă pentru date

O funcție hash primește o intrare de orice lungime și returnează un rezumat de lungime fixă: 256 de biți pentru SHA-256, scriși ca 64 de cifre hexazecimale. Aceeași intrare dă întotdeauna același rezumat, așa că rezumatul poate ține locul datelor. Dacă două fișiere au același rezumat SHA-256, puteți avea certitudinea că sunt identice, iar dacă un bit dintr-o descărcare a fost deteriorat, rezumatul ei nu mai corespunde celui publicat de editor. Pentru că există mult mai multe intrări posibile decât rezumate, multe intrări trebuie să aibă în comun fiecare rezumat; un hash bun face pur și simplu imposibilă găsirea vreuneia dintre ele.

Trei promisiuni

Un hash criptografic face trei promisiuni. Rezistența la preimagine: dat fiind un rezumat, nu puteți găsi o intrare care să-l producă. Rezistența la a doua preimagine: dată fiind o intrare, nu puteți găsi o altă intrare cu același rezumat. Rezistența la coliziuni: nu puteți găsi nicio pereche de intrări cu același rezumat. Pentru un hash ideal cu n biți, cele mai bune atacuri se reduc la ghicit: aproximativ 2ⁿ încercări pentru o preimagine și aproximativ 2ⁿᐟ² pentru o coliziune. Un hash este numit spart atunci când cineva găsește o cale mult mai rapidă decât atât.

Efectul de avalanșă

Schimbați un bit al intrării și fiecare bit al rezumatului ar trebui să se inverseze cu o probabilitate de o jumătate, independent de ceilalți. Atunci o mică modificare a mesajului dă un rezumat care pare complet fără legătură, iar rezumatul nu trădează nimic despre partea intrării care s-a schimbat. SHA-256 obține acest lucru executând 64 de runde care rotesc, adună și combină cele opt cuvinte de 32 de biți ale sale, astfel încât în câteva runde fiecare bit de intrare a influențat fiecare cuvânt. O simplă sumă a octeților, în schimb, se modifică exact cu cât s-a modificat intrarea, așa că dezvăluie totul.

În interiorul SHA-256

SHA-256 completează mai întâi mesajul: adaugă un bit 1, zerouri și lungimea mesajului, până când totalul este un multiplu de 512 biți. Apoi prelucrează mesajul câte 512 biți o dată. Fiecare bloc este extins în 64 de cuvinte, care sunt amestecate într-o stare de opt cuvinte de 32 de biți, pornind de la valori fixe luate din rădăcinile pătrate ale primelor opt numere prime. Starea de după ultimul bloc este rezumatul. Această construcție în lanț, numită după Ralph Merkle și Ivan Damgård, este comună pentru MD5, SHA-1 și SHA-512; mai noul SHA-3, standardizat în 2015, folosește o construcție diferită, numită burete.

Ralph Merkle la Singularity Summit din 2007. Construcția în lanț folosită de SHA-256 poartă numele lui și al lui Ivan Damgård.
Ralph Merkle la Singularity Summit din 2007. Construcția în lanț folosită de SHA-256 poartă numele lui și al lui Ivan Damgård.

Atacul zilei de naștere

Într-un grup de 23 de persoane, șansa ca două să aibă aceeași zi de naștere este puțin peste o jumătate, deși anul are 365 de zile, pentru că ceea ce contează este numărul de perechi, care crește cu pătratul mărimii grupului. Coliziunile unui hash urmează aceeași regulă. Dintre 2ᵏ rezumate posibile, o coliziune este de așteptat după aproximativ √(π/2 · 2ᵏ) intrări aleatorii. Pentru 32 de biți, asta înseamnă aproximativ 82.000 de intrări, gata în câteva clipe; pentru 128 de biți înseamnă aproximativ 2⁶⁴, ceea ce este la îndemâna marilor eforturi de calcul. De aceea cei 128 de biți ai MD5 nu au fost niciodată generoși și de aceea SHA-256 dublează lungimea ca să ofere o securitate de 128 de biți.

MD5 și SHA-1: sparte

Ron Rivest a proiectat MD5 în 1991, iar NSA a proiectat SHA-1, publicat în 1995. În 2004, Xiaoyun Wang și colegii ei au arătat cum se pot crea rapid coliziuni MD5, iar în 2008 cercetătorii le-au folosit pentru a falsifica un certificat în care browserele web aveau încredere. Programul de spionaj Flame din 2012 a folosit o coliziune MD5 ca să se dea drept o actualizare Microsoft. SHA-1 a căzut în 2017, când Google și CWI Amsterdam au publicat două fișiere PDF diferite cu același rezumat SHA-1, după aproximativ 2⁶³ calcule. Ambele sunt încă bune pentru depistarea erorilor accidentale, dar nu pentru ceva ce ar putea fi ținta unui atacator.

Unde se folosesc funcțiile hash

Semnăturile digitale semnează hash-ul unui document, nu documentul însuși. Git denumește fiecare fișier și fiecare commit după hash-ul său, iar minerii Bitcoin caută antete de bloc al căror dublu hash SHA-256 începe cu un șir lung de zerouri. Site-urile nu ar trebui să stocheze niciodată parole, ci doar un hash al lor; dar pentru că oamenii aleg parole scurte, acel hash trebuie să fie lent și cu salt, cu metode precum bcrypt, scrypt sau Argon2, astfel încât ghicitul să devină costisitor. Sumele de control precum CRC-32, folosit în fișierele ZIP, imaginile PNG și Ethernet, sunt tot funcții hash, concepute să prindă zgomotul, nu atacatorii.

Explorați

Deschideți laboratorul de funcții hash ca să calculați hash-ul propriului text cu SHA-256, SHA-512, SHA-1, MD5, CRC-32 și o sumă de octeți de jucărie. Schimbați un caracter și numărați biții inversați, rulați testul de avalanșă pe o mie de modificări de un bit ca să vedeți curba în formă de clopot în jurul jumătății rezumatului și găsiți coliziuni reale pe primii 8 până la 32 de biți ai unui rezumat ca să urmăriți atacul zilei de naștere la lucru.

Întrebări frecvente

Este hashing-ul același lucru cu criptarea?

Nu. Criptarea este făcută ca să fie anulată de cine deține cheia; hashing-ul nu are cheie și nu poate fi anulat de nimeni. Criptarea păstrează un mesaj secret, în timp ce un hash oferă doar o amprentă care vă permite să verificați un mesaj pe care îl aveți deja.

Cât ar dura găsirea unei coliziuni SHA-256?

Cu atacul zilei de naștere, aproximativ 2¹²⁸ calcule de hash, un număr cu 39 de cifre. Chiar dacă toate calculatoarele de pe Pământ n-ar face nimic altceva, ar dura incomparabil mai mult decât vârsta universului. Nu se cunoaște nicio scurtătură.

De ce nu diferă niciodată două hash-uri ale aceluiași text?

O funcție hash este deterministă: nu are nimic aleatoriu și nici cheie, așa că aceiași octeți dau întotdeauna același rezumat. Micile diferențe pe care nu le vedeți, cum ar fi un spațiu la final, un alt caracter de sfârșit de rând sau o altă formă Unicode a unei litere cu diacritice, dau însă un rezumat diferit.

Ce este un salt?

O valoare aleatorie stocată lângă hash-ul unei parole și amestecată în el. Astfel, doi utilizatori cu aceeași parolă obțin hash-uri diferite, iar un atacator nu poate folosi un singur tabel precalculat de parole comune pentru toate conturile.

Ești gata să încerci?

Deschide PictorX în browser – fără instalare și fără card de credit.

Deschideți laboratorul de funcții hash