Hashkollisjoner

Hashkollisjoner oppstår når to forskjellige inngangsverdier gir samme hashverdi generert av en hash-funksjon. En hash-funksjon tar inn data av vilkårlig størrelse og returnerer en fast lengde verdi, ofte kalt en digest. Fordi antallet mulige innganger er større enn antallet mulige utdata, er kollisjoner uunngåelige i teorien, og alltid mulig i praksis.

I kryptografiske sammenhenger er kollisjonsresistens en viktig egenskap. Dette betyr at det bør være svært vanskelig å finne to forskjellige innganger som gir samme hashverdi. I praksis finnes imidlertid kollisjoner for enkelte hash-funksjoner, og derfor blir eldre eller svakere funksjoner avviklet eller erstattet med sterkere alternativer. Eksempler er kjente kollisjoner for MD5 og, senere, for SHA-1; i 2017 ble en praktisk SHA-1-kollisjons demonstrert i prosjektet SHAttered.

Kollisjoner kan oppstå av to grunner: ren tilfeldighet i et stort antall inndata, og spesifikke svakheter i funksjonens design som gjør det lettere å finne kollisjoner enn forventet. I andre sammenhenger, som datablokker i hash-tabeller, oppstår kollisjoner når to nøkler havner i samme bucket, og de løses ved kollisjonsbehandling som kjeding eller åpne adresseringsteknikker. Slike kollisjoner påvirker ytelse og pålitelighet i datastrukturer.

For å redusere risikoen i sikkerhetskritiske anvendelser brukes ofte sterke hash-funksjoner (f.eks. SHA-256 eller SHA-3), og i tillegg praksiser som salting og bruk av digitale signaturer der hashing inngår i en sikker protokoll. I andre kontekster kan flere ulike kontroller kombineres for å sikre integritet.