kollisjonsmotstanden

Kollisjonsmotstand er en egenskap ved en kryptografisk hashfunksjon som sier at det skal være svært vanskelig å finne to ulike meldinger x og y slik at H(x) = H(y). Med andre ord er det beregningsmessig unaturlig å lete etter en kollisjon. Kollisjonsmotstanden er en sentral komponent i sikker bruk av hashfunksjoner i digitale signaturer, meldingintegritet og andre kryptografiske protokoller.

Formelt sett refererer kollisjonsmotstanden til at det ikke skal være praktisk mulig å finne kollisjoner for en gitt hashfunksjon. For en n-bit utgang forventes en kollisjon å dukke opp etter omtrent 2^(n/2) forsøk på grunn av bursdagsprinsippet, noe som ofte kalles den generelle kollisjonsgraden. Dette står i kontrast til preimage-resistens (å finne et input som gir et gitt output) og second-preimage-resistens (å finne et annet input som gir samme output når et spesifikt input er gitt). I praksis betyr dette at designede hashfunksjoner er antatt kollisjonsresistente så lenge ingen effektive kollisjonsangrep er kjent.

Historisk har noen hashfunksjoner fått kollisjonsmotstanden brutt i praksis. MD5 og SHA-1 har kjente kollisjonsangrep og forventes ikke brukt i nye sikkerhetssensitive sammenhenger. Moderne standarder anbefaler derfor hashfunksjoner som SHA-256 eller SHA-3, som anses å være kollisjonsresistente under dagens kunnskap. Det er likevel en kontinuerlig vurdering av sikkerheten, siden fremtidige fremskritt kan påvirke kollisjonsmotstanden.

Praktiske anbefalinger er å velge hashfunksjoner med tilstrekkelig lengde på utgangen (minst 256 biter), følge nasjonale og internasjonale standarder og oppdatere systemer når svake funksjoner fases ut. Kollisjonsmotstand er avgjørende for sikkerheten i digitale signaturer, sertifikater og integritetsverifikasjon.