Funcții hash criptografice

În această lecție vom examina funcțiile hash criptografice, care sunt folosite pe scară largă în validarea rapidă și autentificare.

La sfârșitul lecției, vom fi acoperit:

• Ce sunt funcțiile hash criptografice
• Exemple de cod Python care demonstrează utilizarea funcțiilor hash
• O privire asupra aplicațiilor hashing-ului criptografic
• Securitatea hashing-ului criptografic
• Amenințările la adresa acestor algoritmi din partea calculatoarelor clasice și cuantice

Introducere în hashing-ul criptografic

Funcțiile hash reprezintă un construct valoros în criptografie, deoarece ajută la validarea cu confidențialitate. Astfel, funcțiile hash formează o componentă importantă a mecanismelor de autentificare și integritate a datelor, cum ar fi codurile de autentificare a mesajelor bazate pe hash (HMAC) și semnăturile digitale. Acest articol discută ideile de bază și considerațiile de securitate care stau la baza funcțiilor hash criptografice și prezintă vulnerabilitățile potențiale odată cu apariția calculului cuantic.

Rațiunea de bază și designul funcțiilor hash

Există multe situații în care autentificarea și verificarea integrității trebuie efectuate în mod eficient și fără a dezvălui informații private părții care realizează validarea.

De exemplu, la descărcarea unui software de pe un server la distanță, este nevoie de un mecanism eficient pentru a verifica că software-ul descărcat nu a fost modificat de la crearea sa de către autorul original. În mod similar, la autentificarea utilizatorilor aplicațiilor web, ar fi de dorit să se folosească un mecanism care să nu implice stocarea sau transmiterea fizică a parolelor reale, ceea ce ar putea compromite confidențialitatea acestora.

Funcțiile hash criptografice (FHC) răspund acestor nevoi în mod eficient și sigur.

În esență, o funcție hash criptografică preia o intrare (sau mesaj) de lungime arbitrară și returnează un șir de biți de lungime fixă n ca ieșire. Ieșirea unei FHC este denumită și digest. O FHC utilă trebuie să satisfacă mai multe proprietăți-cheie:

1. Uniformitate: Digesturile produse de o FHC trebuie să fie distribuite uniform și să pară aleatoare. Scopul este de a garanta că ieșirea nu dezvăluie nicio informație despre intrare.
2. Determinism: Pentru o intrare dată, o FHC trebuie să producă întotdeauna același digest, adică trebuie să fie deterministă.
3. Ireversibilitate: O FHC este o funcție unidirecțională, în sensul că, dat fiind un digest, ar trebui să fie imposibil în practică să inversezi hashing-ul și să obții intrarea.
4. Injectivitate aproximativă: Deși FHC-urile sunt funcții mai-mulți-la-unul, ele ar trebui să pară funcții unu-la-unu. Acest lucru se realizează prin combinarea unui spațiu de ieșire de dimensiuni enorme cu efectul de avalanșă, prin care modificările minuscule ale intrării conduc la digesturi complet diferite. Această caracteristică este cunoscută drept injectivitate aproximativă.

Dată fiind aceasta, este posibil să validezi o bucată de date față de instanța originală comparând un digest al datelor cu un digest al originalului.

• Dacă cele două digesturi coincid, putem fi convinși cu probabilitate ridicată că datele sunt identice cu originalul.
• Dacă digesturile diferă, putem fi siguri că datele au fost alterate sau sunt în alt mod neautentice.

Deoarece digesturile FHC în sine nu dezvăluie conținutul real al datelor sau al originalului, ele permit validarea păstrând totodată confidențialitatea.

Descriere matematică

O funcție hash $H$ poate fi definită ca:

$H : Σ^* \rightarrow \{0,1\}^n$

unde $Σ^*$ este mulțimea tuturor șirurilor posibile, pe care le putem considera șiruri binare de orice lungime.

Faptul că dimensiunea domeniului de intrare $Σ^*$ al lui $H$ este nemărginită, în timp ce cea a codomeniulul $\{0,1\}^n$ este mărginită, înseamnă că $H$ este în mod necesar o funcție mai-mulți-la-unul, care mapează infinit de multe intrări pe orice șir de n biți dat.

Proprietățile de uniformitate și determinism sunt frumos încapsulate în modelul oracolului aleator al hashing-ului criptografic.

Exemplu de hashing criptografic în Python cu SHA-256

Acest exemplu simplu demonstrează hashing-ul criptografic folosind popularul algoritm SHA-256, furnizat de biblioteca Python cryptography. Mai întâi îți arătăm cum o diferență minoră între textele în clar duce la o diferență foarte mare între rezumatele hash.

# Added by doQumentation — required packages for this notebook
!pip install -q cryptography

# Begin by importing some necessary modules
from cryptography.hazmat.backends import default_backend
from cryptography.hazmat.primitives import hashes

# Helper function that returns the number of characters different in two strings
def char_diff(str1, str2):
    return sum(str1[i] != str2[i] for i in range(len(str1)))

# Messages to be hashed
message_1 = b"Buy 10000 shares of WXYZ stock now!"
message_2 = b"Buy 10000 shares of VXYZ stock now!"

print(f"The two messages differ by { char_diff(message_1, message_2)} characters")

The two messages differ by 1 characters

Cele două mesaje diferă prin exact un caracter.

Apoi, instanțiem obiecte hash pentru a activa procesul de hashing, care implică apeluri la două metode: update și finalize.

Observăm că, datorită efectului de avalanșă din SHA-256 CHF, o diferență de un singur caracter în mesajele de intrare produce două rezumate complet diferite.

# Create new SHA-256 hash objects, one for each message
chf_1 = hashes.Hash(hashes.SHA256(), backend=default_backend())
chf_2 = hashes.Hash(hashes.SHA256(), backend=default_backend())

# Update each hash object with the bytes of the corresponding message
chf_1.update(message_1)
chf_2.update(message_2)

# Finalize the hash process and obtain the digests
digest_1 = chf_1.finalize()
digest_2 = chf_2.finalize()

# Convert the resulting hash to hexadecimal strings for convenient printing
digest_1_str = digest_1.hex()
digest_2_str = digest_2.hex()

# Print out the digests as strings
print(f"digest-1: {digest_1_str}")
print(f"digest-2: {digest_2_str}")

print(f"The two digests differ by { char_diff(digest_1_str, digest_2_str)} characters")

digest-1: 6e0e6261b7131bd80ffdb2a4d42f9d042636350e45e184b92fcbcc9646eaf1e7
digest-2: 6b0abb368c3a1730f935b68105e3f3ae7fd43d7e786d3ed3503dbb45c74ada46
The two digests differ by 57 characters

Aplicații ale hashingului criptografic

Proprietățile unice ale funcțiilor hash criptografice (CHF) le fac potrivite pentru o gamă largă de aplicații:

• Verificări de integritate a datelor: Funcțiile hash pot fi folosite pentru a crea o sumă de control pentru un set de date. Orice modificare a datelor, intenționată sau nu, va produce o sumă de control diferită, alertând sistemele sau utilizatorii cu privire la schimbare. Suma de control este, de obicei, mult mai compactă decât datele originale, ceea ce face comparațiile de checksum foarte rapide.

Figura 1. Hashingul securizat pentru verificări de integritate a datelor

• Semnături digitale: Hashurile criptografice sunt esențiale pentru funcționarea semnăturilor digitale, deoarece implică compararea mesajelor hashate criptografic pentru a stabili autenticitatea și integritatea, păstrând în același timp confidențialitatea.

Figura 2. Semnături digitale

• Blockchain și criptomonede: Criptomonedele precum Bitcoin se bazează în mare măsură pe CHF, în special pentru crearea integrității tranzacțiilor și pentru activarea mecanismelor de consens, cum ar fi dovada muncii (proof of work).

Securitatea hashingului criptografic

Securitatea unei CHF este evaluată, de obicei, în funcție de rezistența la două tipuri de atacuri: pre-imagine și coliziune.

Rezistența la pre-imagine

Rezistența la pre-imagine înseamnă că, dat fiind un digest, ar trebui să fie imposibil în practică să găsești intrarea.

Aceasta este legată de proprietatea unidirecțională a CHF.

O CHF bună este proiectată astfel încât o parte care dorește să efectueze un atac de pre-imagine să nu aibă altă opțiune decât o abordare prin forță brută, care are complexitatea temporală $2^n$.

detalii matematice

Dată o CHF $H$ și un digest $g$, ar trebui să fie imposibil din punct de vedere computațional să se găsească orice intrare $m$ din pre-imaginea lui $g$ astfel încât $H(m) = g$.

Rezistența la coliziuni

Rezistența la coliziuni înseamnă că este dificil să găsești două intrări diferite care să producă același digest.

O coliziune hash criptografică apare atunci când două intrări produc același digest. Deși coliziunile există inevitabil, dată fiind natura de tipul mulți-la-unu a CHF, o CHF bună face totuși imposibilă localizarea uneia în mod deliberat.

Rezistența la coliziuni este crucială pentru aplicații precum semnăturile digitale și certificatele, unde ar fi dezastruos dacă o parte malițioasă ar putea crea un fals care să producă același hash.

detalii matematice ale coliziunilor hash

$m_1, m_2$ pot fi găsite astfel încât $H(m_1) = H(m_2)$.

Lungimea hashului

Rezistența la coliziuni este o cerință mai dificilă decât rezistența la pre-imagine și necesită lungimi de ieșire de două ori mai mari decât cele necesare pentru rezistența la pre-imagine. Aceasta deoarece un atac prin forță brută cunoscut sub numele de atacul zilei de naștere, care poate fi folosit pentru a identifica coliziuni hash, are complexitatea temporală $2^{n/2}$.

În absența slăbiciunilor criptanalitice, securitatea unei funcții hash este influențată în principal de lungimea hashului. Cu cât hashul este mai lung, cu atât este mai sigur, deoarece devine mai dificil să se monteze atacuri prin forță brută.

Funcții hash criptografice utilizate frecvent

Următorul tabel enumeră câteva funcții hash criptografice utilizate frecvent, împreună cu lungimile hashului și domeniile principale de aplicație:

Funcție hash	Lungime ieșire (biți)	Aplicații comune
MD5	128	Verificarea integrității fișierelor, sisteme mai vechi, utilizări non-criptografice
SHA-1	160	Sisteme legacy, Git pentru controlul versiunilor
SHA-256	256	Criptomonede (Bitcoin), semnături digitale, certificate
SHA-3	Variabil (până la 512)	Diverse aplicații criptografice, succesor al SHA-2
Blake2	Variabil (până la 512)	Criptografie, înlocuind MD5/SHA-1 în unele sisteme
Blake3	Variabil (până la 256)	Criptografie, hashingul fișierelor, integritatea datelor

• MD5 și SHA-1, deși sunt încă folosite în aplicații mai puțin sensibile, sunt considerate depreciate în ceea ce privește rezistența la coliziuni și nu sunt recomandate pentru sistemele noi. SHA-256, parte a familiei SHA-2, este utilizat pe scară largă și în prezent sigur pentru majoritatea aplicațiilor.
• SHA-3 este un standard mai nou, selectat de NIST în 2015 ca și câștigător al competiției NIST pentru funcții hash. Este proiectat să fie un înlocuitor direct pentru SHA-2, dar are și unele caracteristici interne diferite și este rezistent la anumite tipuri de atacuri care ar putea fi eficiente împotriva SHA-2.
• Blake2 și Blake3 sunt funcții hash criptografice mai rapide decât MD5, SHA-1, SHA-2 și SHA-3, dar cel puțin la fel de sigure ca cel mai recent standard, SHA-3. Sunt din ce în ce mai utilizate în sistemele noi, în special acolo unde viteza este importantă.

Riscuri cuantice pentru hashing-ul criptografic tradițional

Principala amenințare cuantică la adresa hashing-ului criptografic este reprezentată de atacurile prin forță brută.

Dat fiind un anumit digest, un atacator va încerca intrări aleatorii până când găsește una care produce același digest.

Cu $n$ biți în intrare, există $2^n$ valori posibile. Prin urmare, atacatorul trebuie să încerce aproximativ $2^{n-1}$ intrări pentru a avea o șansă mai mare de 50% de succes.

Algoritmul Grover

Într-un astfel de context de căutare nestructurată, algoritmul Grover poate oferi o accelerare pătratică folosind o tehnică cunoscută sub numele de amplificare cuantică a amplitudinii, reducând complexitatea temporală a unui atac pre-imagine la $2^{n/2}$.

În termeni practici, aceasta înseamnă că un CHF de 256 de biți, considerat în prezent sigur împotriva atacurilor pre-imagine de către calculatoarele clasice, ar oferi același nivel de securitate ca un CHF de 128 de biți atunci când se confruntă cu un atacator cuantic care utilizează algoritmul Grover.

Algoritmul Grover prin el însuși nu este cunoscut a oferi accelerări cuantice suplimentare în ceea ce privește atacurile de coliziune dincolo de limita stabilită de atacul zilei de naștere, care poate fi efectuat pe calculatoare clasice. Deoarece atacul clasic al zilei de naștere necesită deja ca CHF-urile să folosească lungimi de hash de două ori mai mari decât cele necesare pentru rezistența pre-imagine, faptul că căutarea Grover înjumătățește efectiv lungimea hash-ului în raport cu atacurile pre-imagine nu reprezintă o amenințare practică.

De exemplu, în cazul SHA-256, efectuarea a aproximativ $2^{128}$ operații pentru a executa un atac pre-imagine asistat de Grover ar fi în continuare imposibilă în viitorul previzibil.

Algoritmul BHT

Un algoritm cuantic care combină aspecte ale atacului zilei de naștere cu căutarea Grover a fost propus în 1997 de Brassard, Høyer și Tapp (BHT) și oferă o scalare teoretică de $O(2^{n/3})$ pentru găsirea coliziunilor de hash. Cu toate acestea, această scalare îmbunătățită se bazează pe existența tehnologiei de memorie cu acces aleatoriu cuantic QRAM, care în prezent nu există.

Fără QRAM, scalarea realizabilă este $\tilde{O}(2^{2n/5})$ și, pentru lungimile de hash utilizate în prezent, această îmbunătățire marginală a capacității de găsire a coliziunilor față de atacul zilei de naștere nu reprezintă o amenințare critică.

Rezumat

Funcțiile hash criptografice sunt o componentă esențială pentru asigurarea integrității și confidențialității datelor în sistemele informaționale digitale și au aplicații răspândite în multe contexte.

Cerințele de securitate ale CHF-urilor sunt înțelese în principal în termeni de rezistență la atacuri pre-imagine și de coliziune. Pentru CHF-urile bine concepute, lungimea hash-ului este un bun indicator pentru nivelul de securitate.

Deși apariția calculatoarelor cuantice care execută algoritmii Grover și BHT afectează teoretic rezistența pre-imagine și la coliziune a CHF-urilor tradiționale, lungimile mari de hash deja utilizate astăzi înseamnă că algoritmii moderni de hashing criptografic, precum SHA-3, vor rămâne probabil siguri în absența descoperirii unor atacuri criptoanalitice necunoscute până în prezent.