Hva er en hashfunksjon?

En hashfunksjon tar inn data av vilkårlig lengde og gir ut en verdi med fast lengde. Inndataen kan være et passord, en fil, en hel database eller bare et enkelt tegn. Uansett blir resultatet et kort avtrykk, ofte kalt en hash eller en sjekksum. Tanken er enkel: lag et lite, håndterlig fingeravtrykk som representerer et større innhold.

Men ikke alle hashfunksjoner er like. En vanlig hashfunksjon, slik den brukes i en oppslagstabell i et dataprogram, har som mål å fordele verdier jevnt og være rask. En kryptografisk hashfunksjon har et helt annet ambisjonsnivå: den skal også motstå aktive angripere som med vilje prøver å lure den. Denne artikkelen handler om den siste typen og om hvilke egenskaper som skiller den fra en vanlig sjekksum.

Kjerneegenskapene til en kryptografisk hash

For at en hashfunksjon skal kunne brukes til sikkerhet, må den oppfylle en rekke krav. Disse egenskapene henger sammen, og det er kombinasjonen av dem som gjør funksjonen nyttig.

Deterministisk

En kryptografisk hash er deterministisk. Den samme inndataen gir alltid nøyaktig samme hash, hver gang og på enhver maskin. Uten denne egenskapen ville det ikke gå an å sammenligne avtrykk, og funksjonen ville være ubrukelig til å verifisere at noe er uendret.

Rask å beregne

Det skal være billig og raskt å regne ut hashen av en melding. Dette gjør at funksjonen kan brukes i stor skala, for eksempel til å sjekke mange filer eller behandle store datamengder. Samtidig finnes det situasjoner, som lagring av passord, der man bevisst gjør prosessen tregere ved hjelp av spesialiserte funksjoner, nettopp for å gjøre det dyrere for en angriper å gjette seg frem.

Preimage-motstand

Preimage-motstand betyr at det er praktisk umulig å finne tilbake til inndataen ut fra hashen alene. Hashen skal være en enveis gate: lett å gå gjennom forover, urealistisk å gå baklengs. Hvis du bare har avtrykket, skal du ikke kunne regne deg frem til hva den opprinnelige meldingen var. Denne egenskapen er grunnen til at hasher kan brukes til å lagre passord uten å avsløre dem.

Andre preimage-motstand

Andre preimage-motstand handler om en litt annen situasjon. Gitt en bestemt melding og dens hash, skal det være praktisk umulig å finne en annen melding som gir samme hash. Med andre ord: en angriper som har et gyldig dokument, skal ikke kunne lage et alternativt dokument med samme avtrykk. Dette er avgjørende når hashen brukes som bevis på at akkurat dette innholdet er ekte.

Kollisjonsmotstand

Kollisjonsmotstand er det sterkeste kravet. Det skal være praktisk umulig å finne to forskjellige meldinger, hvilke som helst, som gir samme hash. Her står angriperen fritt til å velge begge meldingene selv. Dette er et tøffere krav enn andre preimage-motstand, fordi angriperen har flere frihetsgrader. Det var nettopp kollisjonsmotstanden til SHA-1 som ble brutt i 2017, da to ulike filer med samme SHA-1-verdi ble laget og vist frem offentlig.

Lavineeffekt

Lavineeffekten betyr at den minste endring i inndataen gir et fullstendig annerledes resultat. Bytter du ett tegn, eller endrer en eneste bit, skal hele hashen forandre seg uten gjenkjennelig likhet med den forrige verdien. Denne egenskapen gjør det enkelt å oppdage selv ørsmå endringer, og den hindrer en angriper i å nærme seg en ønsket hash gradvis ved å gjøre små justeringer.

Hvordan en kryptografisk hash skiller seg fra en vanlig hash

En vanlig, ikke-kryptografisk hashfunksjon er laget for ytelse og fordeling, ikke for å stå imot angrep. Den brukes for eksempel til å plassere data raskt i en hashtabell, eller til en enkel sjekksum som fanger opp tilfeldige overføringsfeil. For slike formål er det helt greit at funksjonen er forutsigbar og lett å manipulere, fordi det ikke finnes noen motstander som prøver å utnytte den.

Forskjellen ligger i trusselmodellen. En kryptografisk hash må anta at noen aktivt forsøker å finne en kollisjon, reversere avtrykket eller bytte ut innhold uten å endre hashen. Derfor er den designet slik at slike angrep blir praktisk umulige. En enkel sjekksum kan typisk lures med vilje av selv en lite avansert angriper, mens en kryptografisk hash er bygget for å motstå selv en motpart med store ressurser. Når man trenger sikkerhet og ikke bare feilkontroll, er det den kryptografiske varianten som må brukes.

Hvorfor kollisjonsmotstand er det vanskeligste kravet

De tre motstandsegenskapene henger sammen, men de er ikke like krevende å bryte. Preimage-motstand og andre preimage-motstand handler begge om at angriperen er bundet til et fast mål: en gitt hash, eller en gitt melding med sin hash. Han må treffe akkurat dette målet, og det gjør oppgaven svært tung.

Kollisjonsmotstand er annerledes, fordi angriperen her står fritt til å velge begge meldingene selv. Han trenger ikke treffe en bestemt verdi på forhånd, bare finne et hvilket som helst par som tilfeldigvis møtes. Denne friheten gjør det statistisk mye lettere å finne en kollisjon enn å treffe et forhåndsbestemt avtrykk, et fenomen som er kjent fra sannsynlighetsregning under navnet bursdagsparadokset. Konsekvensen er at kollisjonsmotstand alltid er den svakeste flanken i en hashfunksjon, og det er derfor den brytes først. Nettopp dette skjedde med SHA-1: det var kollisjonsmotstanden som falt i 2017, ikke evnen til å motstå reversering.

For den som velger en hashfunksjon, betyr dette at man bør se spesielt nøye på kollisjonsmotstanden, særlig i bruksområder som digitale signaturer, der to dokumenter med samme hash er nok til å gjøre alvorlig skade.

Vanlige bruksområder

Kryptografiske hashfunksjoner dukker opp overalt der man trenger å bevise at data er uendret eller å lagre noe hemmelig på en forsvarlig måte.

  • Passordlagring med salt. Tjenester bør aldri lagre passord i klartekst. I stedet lagrer de hashen av passordet. Når du logger inn, hashes passordet du oppgir og sammenlignes med den lagrede verdien. For å hindre at like passord gir like avtrykk, og for å gjøre forhåndsberegnede angrep vanskeligere, legger man til en tilfeldig verdi som kalles salt før hashing. Til dette brukes gjerne spesialiserte, bevisst trege funksjoner.
  • Integritetssjekk. Når du laster ned en fil, kan utgiveren oppgi hashen av den ekte filen. Du kan beregne hashen av din nedlastede kopi og sammenligne. Stemmer de, er filen sannsynligvis uendret. Avviker de, har noe gått galt eller blitt endret underveis.
  • Digitale signaturer. I stedet for å signere et helt dokument, signerer man hashen av det. Det gjør signaturen rask og kompakt. Samtidig betyr det at hele sikkerheten hviler på at det er umulig å finne to dokumenter med samme hash. Derfor er kollisjonsmotstand så viktig nettopp her.
  • Blokkjeder. I en blokkjede knytter hver blokk seg til den forrige ved hjelp av en hash. Endrer noen en eldre blokk, endres hashen, og bruddet i kjeden blir synlig. Slik bygger hashfunksjoner en kjede der historikken er vanskelig å forfalske uten å bli oppdaget.

Når en hashfunksjon må byttes ut

Egenskapene over er idealer som en hashfunksjon skal oppfylle. Problemet er at en funksjon som oppfyller dem i dag, ikke nødvendigvis gjør det for alltid. Forskning kan avdekke svakheter, og raskere maskinvare kan gjøre angrep som før var urealistiske, fullt mulige. SHA-1 er det tydeligste eksempelet: den hadde god kollisjonsmotstand i teorien, helt til den ikke lenger hadde det i praksis.

Lærdommen er at valg av hashfunksjon er en beslutning som må holdes ved like. Når en funksjon viser tegn til svakhet, særlig i kollisjonsmotstanden, er det på tide å gå over til en sterkere. I dag er funksjoner i SHA-2-familien, som SHA-256, og den nyere SHA-3 anbefalte valg der man trenger en kryptografisk hash. Å forstå egenskapene som ligger til grunn, gjør det lettere å se hvorfor slike overganger er nødvendige, og hvorfor en hash er mye mer enn bare en kort sjekksum.