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). 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; 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 $\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.

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. 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.

Definition

En familj av funktioner {h_k :{0, 1}^m(k) → {0, 1}^l(k)} genererad av någon algoritm G är en familj av kollisionsresistenta hashfunktioner, om |m(k)| > |l(k)| för vilket k som helst, dvs h_k komprimerar inmatningssträngen, och varje h_k kan beräknas inom polynomtiden givet k, men för vilken som helst probabilistisk polynomalgoritm A har vi:

Pr [k ← G(1ⁿ), (x₁, x₂) ← A(k, 1ⁿ) så att x₁ ≠ x₂ men h_k(x₁) = h_k(x₂)] < negl(n),

Där negl(·) anger någon försumbar funktion, och n är säkerhetsparametern.

Logisk grund

Kollisionsmotstånd är önskvärt av flera skäl.

• I vissa digitala signatursystem intygar en part ett dokument genom att publicera en offentlig nyckelsignatur på en hash av dokumentet. Om det är möjligt att ta fram två dokument med samma hash, kan en angripare få en part att intyga det ena, och sedan hävda att parten har intygat det andra.
• I vissa distribuerade innehållssystem jämför parterna kryptografiska hash av filer för att säkerställa att de har samma version. En angripare som kan producera två filer med samma hash kan lura användare att tro att de har samma version av en fil när de faktiskt inte har det.

Se även

• Definitionsmängdsattack