Nøkkelkollisjon

Eksempel hvor John Smith og Sandra Dee begge får 02 som nøkkelverdi hvilket forårsaker en nøkkelkollisjon

I informatikk er en nøkkelkollisjon[1][2] eller hashkollisjon (engelsk: hash collision) når to dataelementer i en nøkkeltabell deler samme nøkkelverdi. Verdiene er i dette tilfellet utledet fra en hashfunksjon som tar et input og returnerer en fast lengde biter.[3]

Selv om hashalgoritmer er laget med hensikt å være kollisjonsbestandige kan de fremdeles noen ganger redusere forskjellige data til samme nøkkel (på grunn av skuffeprinsippet). Ondsinnede brukere kan dra nytte av dette for å etterligne, få tilgang til eller endre data.[4]

På grunn av mulige negativ utnyttelse av nøkkelkollisjoner i databehandling og datasikkerhet (særlig i kryptografiske nøkkelfunksjoner) har kollisjonsunngåelse blitt et viktig tema innen datasikkerhet.

Sannsynligheter for at det skjer

[rediger | rediger kilde]

Sannsynligheten for en kollisjon avhenger av størrelsen på algoritmen, fordelingen av nøkkelverdier og om det både er matematisk kjent og beregningsmessig mulig å lage spesifikke kollisjoner.

Noen eksempler på avtrykksalgoritmer er CRC-32, MD5 OG SHA-1 (listet fra minst til størst kompleksitet, og lavest til høyest sannsynlighet for kollisjon).[5]

Se også

[rediger | rediger kilde]

Referanser

[rediger | rediger kilde]
  1. ^ «Fellesordliste for dataord på – bokmål». i18n.skolelinux.no. Arkivert fra originalen 15. mars 2023. Besøkt 3. mars 2023. 
  2. ^ «Universitetet i Bergen: Bruk av dynamiske datastrukturer - Nøkkeltabeller: HashMap 2012-07-13» (PDF). 
  3. ^ Embedded Security, http://dx.doi.org/10.1016/b978-075068215-2.50006-9, besøkt 2021-12-08 
  4. ^ Schneier, Bruce (19. august 2004). «Cryptanalysis of MD5 and SHA: Time for a New Standard». Besøkt 9. august 2024. 
  5. ^ Altheide, Cory; Carvey, Harlan (2011). Digital Forensics with Open Source Tools. Elsevier. ISBN 9781597495868. doi:10.1016/b978-1-59749-586-8.00001-7. Besøkt 8. desember 2021.