Kollisionssökning

Kollisionssökning är processen att hitta två olika indata som ger samma utdata i en hashfunktion. En kollision innebär att hashvärdet inte är unikt för varje indata, vilket äventyrar hashfunktionens kollisionresistens. Kollisionssökning är ett centralt område inom kryptanalys och bedömning av säkerheten hos kryptografiska hashfunktioner och digitala signaturer.

I en ideal hashfunktion med n-bitars utdata förväntas en kollision uppträda efter ungefär 2^(n/2) utvärderingar tack vare födelsedagsparadoxen. Att hitta en preimage kräver cirka 2^n försök. Generellt är det därför mycket billigare att söka efter kollisioner än att hitta ett specifikt förhandsvärde.

Metoder: Den generiska metoden är slumpmässig sökning. Mer avancerade attacker utnyttjar kända svagheter hos specifika hashfunktioner och kan hitta kollisionspar snabbare än 2^(n/2). Exempel är tekniker för valda-prefix-kollisioner som utnyttjats mot äldre funktioner som MD5 och SHA-1.

Användningar och risker: Kollisionssökning underminerar integritet och autenticitet i digital signeringssystem, certifikat och dataintegritet. Moderna hashfunktioner som SHA-256 och SHA-3 har längre utdata och anses motståndskraftiga mot generiska kollisionsattacker; de bör användas i nya system.

Historik och status: MD5 och SHA-1 har uppvisat kollisionsattacker och används inte längre i säkerhetskritiska sammanhang. Standarder rekommenderar övergång till starkare funktioner och kontinuerlig utvärdering av nya attacker mot hashfunktioner.