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]- ^ «Fellesordliste for dataord på – bokmål». i18n.skolelinux.no. Besøkt 3. mars 2023.
- ^ «Universitetet i Bergen: Bruk av dynamiske datastrukturer - Nøkkeltabeller: HashMap 2012-07-13» (PDF).
- ^ Embedded Security, http://dx.doi.org/10.1016/b978-075068215-2.50006-9, besøkt 2021-12-08
- ^ Schneier, Bruce (19. august 2004). «Cryptanalysis of MD5 and SHA: Time for a New Standard». Besøkt 9. august 2024.
- ^ 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.