Hash Collision

Ce este o coliziune hash?

O coliziune hash apare atunci când două intrări diferite produc exact aceeași valoare hash. Imaginează-ți două chei diferite care, cumva, deschid aceeași încuietoare digitală. E rar, dar dacă se întâmplă cu algoritmul nepotrivit, apar probleme.

Cum funcționează coliziunea hash

Gândește-te la un hash ca la o etichetă mică pentru date voluminoase. Iată o scurtă prezentare a procesului, de la intrare la „ups”.

1. Intrare: Începi cu orice mesaj, fișier sau tranzacție.
2. Hash: O funcție din familia funcțiilor hash criptografice transformă intrarea într-un șir de lungime fixă.
3. Coliziune: Deoarece numărul ieșirilor este limitat, iar intrările sunt nelimitate, două intrări diferite pot genera aceeași ieșire.
4. Atac: O amenințare serioasă apare când cineva poate crea intenționat două intrări diferite care intră în coliziune, apoi o poate înlocui pe una cu cealaltă.
5. Apărare: Algoritmii buni fac căutarea atât de costisitoare încât încercările aleatorii consumă timp și bani.

Da, cam asta e ideea.

De ce contează coliziunea hash

De ce ar trebui să-ți pese de această latură discretă a matematicii și a codului?

• Avantaj: Rezistența puternică ajută la păstrarea unicității etichetelor datelor, lăsând mai puțin loc pentru trucuri.
• Perspectivă: Coliziunile amenință integritatea unor elemente precum tehnologia blockchain, actualizările software și verificarea fișierelor.
• Relevanță: Te vei întâlni cu acest concept în wallet-uri, exchange-uri, dovezi și instrumente de audit care se bazează pe egalitatea hash-urilor.

Caracteristici cheie ale coliziunii hash

Iată ce face acest fenomen aparte și merită reținut:

• Inevitabilă: Cu ieșiri finite și intrări nelimitate, o pereche va intra în coliziune, conform principiului cutiei poștale.
• Dificilă: Pentru funcțiile hash moderne, găsirea intenționată a unei coliziuni este concepută să fie extrem de solicitantă din punct de vedere computațional.
• Semnături: Multe semnături digitale semnează un hash, așa că rezistența la coliziuni îi protejează pe semnatari de înlocuirea frauduloasă a mesajelor.

Cum se calculează o coliziune hash?

Poți estima efortul folosind principiul zilei de naștere. Pentru un hash de k biți, numărul de încercări aleatorii necesare pentru o probabilitate de aproximativ cincizeci la sută de a obține o coliziune este aproximativ rădăcina pătrată din doi la puterea k, înmulțită cu aproximativ unu virgulă unu șapte șapte.

n_fifty_percent ≈ 1.1774 * sqrt(2^k)

Exemplu: pentru k egal cu 256, numărul de încercări necesare este inimaginabil de mare, motiv pentru care obținerea unei coliziuni prin forță brută nu e un proiect de weekend.

Variante

În cercetare și în atacuri apar diferite variante:

• Coliziune: Oricare două intrări distincte au același hash.
• Coliziune de ordinul al doilea: Pornind de la o intrare, găsește alta cu același hash.
• Preimagine: Pornind de la un hash, găsește orice intrare care generează acel hash.
• Prefix: O coliziune cu prefix ales creează două mesaje cu începuturi diferite, alese intenționat, care au același hash la final.

Exemplu

Dacă un atacator ar putea crea două tranzacții diferite cu același txid, ar putea încerca o schemă de dublă cheltuire, înlocuind tranzacția cu cea geamănă după ce ai semnat.

Curiozitate

Coliziunile MD5 au fost demonstrate cu zeci de ani în urmă, iar proiectul SHAttered a produs o coliziune publică SHA one folosind două PDF-uri diferite — o demonstrație răsunătoare care a determinat industria să renunțe la acest algoritm.

În concluzie

Pe scurt, o coliziune hash este cazul rar în care două intrări diferite au aceeași amprentă digitală, iar criptografia modernă depune eforturi considerabile pentru ca acest fenomen să rămână doar o curiozitate.