Coliziune hash
În criptografie , o coliziune hash este o situație care apare atunci când două intrări diferite produc aceeași ieșire printr-o funcție hash .
Potențial, majoritatea funcțiilor hash au ca rezultat coliziuni, dar cu o funcție hash bună apar foarte rar (și sunt foarte greu de găsit). În anumite aplicații specifice, unde aveți un număr relativ mic de intrări, este posibil să construiți o funcție hash perfectă care să mapeze toate intrările diferite la ieșiri diferite. În schimb, o funcție care ia intrări de lungime arbitrară și returnează un hash de dimensiune fixă (cum ar fi MD5 ), trebuie să aibă neapărat coliziuni, deoarece numărul de ieșiri posibile este finit în fața unui număr infinit de intrări posibile.
Coliziuni în căutarea datelor
O metodă eficientă de căutare poate fi procesarea unei chei de căutare utilizând o altă funcție hash, apoi luarea valorii hash rezultate și, în final, utilizarea acesteia ca index într-o serie de date. Structura de date rezultată se numește tabel hash . Atâta timp cât diferite chei corespund unor indici diferiți (cazul ideal al unei funcții hash perfecte), timpul necesar procesului de căutare are o valoare maximă limitată (adică este independentă de dimensiunea structurii și de cheia utilizată, puterea tabelele hash). În cazul în care cheile de căutare indică indici identici, are loc o coliziune hash. Cea mai populară modalitate de a evita acest eveniment este să îl concatenăm prin crearea unei liste legate de valori pentru fiecare index al tabloului și să îl adresăm fără restricții ( adresare deschisă ), căutând alți indici din matrice din apropiere pentru a găsi spațiu liber. . Ambele, însă, devalorizează cele mai grave cazuri de complexitate a căutării pentru un timp liniar al numărului de elemente.
Criptare
O proprietate dorită a funcțiilor hash criptografice este că este imposibil de calculat să se găsească o coliziune. Valoarea funcției hash poate fi utilizată pentru a certifica că o intrare nu a fost modificată prin publicarea semnăturii hash, dacă nu este fezabil să se producă o coliziune. Fezabil , în acest context, înseamnă că fiecare metodă trebuie să fie mai rapidă decât o metodă de forță brută .
Rezistență slabă la coliziune
Rezistență slabă la coliziune pentru funcția hash , aveți dacă pentru fiecare mesaj , nu este fezabil să găsiți un alt mesaj astfel încât .
Deci, cunoscând hashul unui mesaj, nu sunt în stare, cu o putere de calcul rezonabilă, să găsesc o altă intrare care să genereze același hash pentru mine. Rețineți că proprietatea presupune că știu mesajul sursă și că acest lucru nu mă ajută să găsesc un al doilea mesaj cu un hash identic.
Rezistență puternică la coliziune
Să presupunem că nu pornim de la un mesaj dat, ci că putem alege orice pereche de mesaje care generează același hash. Dacă vom reuși, nu am încălcat slaba rezistență la coliziune. Cu toate acestea, există o altă proprietate, mai restrictivă, care împiedică acest lucru să fie fezabil.
Mai formal: nu este fezabil să găsești orice cuplu astfel încât
