Kollisionsresistens

I kryptografi är kollisionsresistens en egenskap hos kryptografiska hashfunktioner: en hashfunktion H är kollisionsresistent om det är svårt att hitta två inmatningar som ger samma utdata med en hashfunktion; det vill säga inmatningarna a och b där a ≠ b men H(a) = H(b).^[1]:136 Postfacksprincipen innebär att alla hashfunktioner med fler möjlig inmatningar (definitionsmängd) än resultat (värdemängd) nödvändigtvis kommer att ha sådana kollisioner;^[1]:136 dock ju svårare de är att hitta, desto säkrare är hashfunktionen kryptografiskt.

På grund av födelsedagsparadoxen så behöver en angripare bara beräkna 2^N/2 (eller ${\displaystyle \scriptstyle {\sqrt {2^{N}}}}$) hashoperationer, där N är mängden av alla möjliga resultat, för att troligen hitta två matchande resultat. Detta sätter en övre gräns för kollisionsresistens. Om det finns en enklare metod än att göra en totalsökning av hashoperationerna, anses hashfunktionen vara trasig.^[2]

Kryptografiska hashfunktioner är vanligtvis utformade för att vara kollisionsresistenta. Men många hashfunktioner som en gång ansågs vara kollisionsresistenta är inte det längre; till exempel har både MD5 och SHA-1 publicerade tekniker som är effektivare än totalsökning för att hitta kollisioner.^[3][4] Vissa hashfunktioner har dock ett bevis på att det är minst lika svårt att hitta kollisioner som något svårt matematiskt problem (som heltalsfaktorisering eller diskret logaritm). Dessa funktioner kallas bevisligen säkra.^[2]