Dagens tekst er hentet fra kapittel 11 i Cryptography and Network Security, og handler om kryptografiske hash-funksjoner.

Hash og meldingsautentiseringskoder (MAC)

Hashfunksjoner komprimerer meldinger av vilkårlig størrelse til en fast bitlengde ved å prosessere meldinger i blokker gjennom en kompresjonsfunksjon. De kan enten være spesialbygd, eller benytte seg av et blokkchiffer med kjent nøkkel. Resultatet av en hashfunksjon vil alltid være kjent, og det skal ikke være noen hemmelig nøkkel involvert.

En meldingsautentiseringskode (MAC), på den annen side, er en autentikator av bestemt størrelse for en melding, som skal sørge for autentisering av meldingsinnholdet. En MAC bruker typisk et blokkchiffer og/eller en hashfunksjon som komponenter, og baserer seg på en hemmelig nøkkel delt mellom sender og mottaker.

Hashfunksjoner

En hashfunksjon H mates med en mengde data M av variabel lengde, og produserer en hashverdi h av fast størrelse:  h = H(M). Hovedformålet for en hashfunksjon er å kunne verifisere integritet av data. En kryptografisk hashfunksjon er en algoritme som gjøre det beregningsmessig ugjennomførbart («umulig») å finne enten a) et dataobjekt som kan generere et forhåndsoppgitt hashresultat (enveis-egenskapen), eller b) finne to dataobjekter som genererer samme hash (kollisjonsfrihet-egenskapen).

Meldingsautentiseringskoder (MAC)

En MAC-funksjon kalles også av og til for en nøklet hashfunksjon, og brukes typisk mellom to parter som deler en hemmelig nøkkel, for å autentisere informasjon som utveksles mellom de to partene. Algoritmen mates med den hemmelige nøkkelen og en melding (en datamengde av variabel størrelse), og produserer en verdi (MAC) som kobles til meldingen som skal beskyttes.  Hvis integriteten til meldingen senere må sjekkes, kan man anvende MAC-funksjonen på meldingen og sammenligne resultatet med den tilhørende MAC-verdien. En angriper som endrer på meldingen vil ikke være i stand til å lage en ny korrekt MAC uten å kjenne den hemmelige nøkkelen.

Digital Signatur

I det følgende bruker vi RSA som eksempel på digital signatur; andre digitale signaturer fungerer ikke helt på samme måten. En digital signatur fungerer i praksis på mange måter som en MAC, men her vil hashverdien krypteres med avsenderens private nøkkel. Enhver som kjenner avsenderens offentlige nøkkel kan verifisere signaturen og bekrefte integriteten til meldingen. En angriper som ønsker å endre meldingen må kjenne avsenderens private nøkkel for å kunne generere en gyldig signatur. Digitale signaturerer har også andre implikasjoner som går ut over meldingsautentisering.

Andre formål med hash-funksjoner

Hashfunksjoner brukes ofte for å generere enveis passordfiler – passordet lagres ikke i klartekst, men i stedet lagres en hash av passordet. Når brukeren taster inn passordet, vil systemet generere en hash og sammenligne med hashen som er lagret for den brukeren. Denne formen for passordbeskyttelse brukes av de fleste operativsystem.

Hasher kan også brukes i inntrengningsdeteksjon og antivirus. En velkjent metode er å beregne hash H(F) av alle statiske filer, og lagre denne sikkert. Man kan senere avgjøre om noen filer har blitt endret ved å beregne H(F) igjen og sammenligne med den lagrede verdien. En inntrenger måtte da kunne endre F uten at H(F) endres, dette skal være «umulig» med en god hashfunksjon.

En hashfunksjon kan også brukes til å lage en pseudorandom funksjon (PRF) eller en pseudorandom nummergenerator (PRNG). En vanlig anvendelse for en hash-basert PRF er for generering av symmetriske nøkler.

To enkle hash-funksjoner

Som et eksempel, la oss se på to enkle (og derfor usikre) hashfunksjoner som opererer etter følgende generelle prinsipper: Input ses på som en sekvens av n-bit blokker, og prosesseres en blokk av gangen på en iterativ måte for å produsere en n-bit hash-verdi. Den første er rett og slett en bit-for-bit exclusive-OR (XOR) av hver blokk: C_i = b_i1 xor b_i2 xor . . . xor b_im . Dette representerer en enkel paritetsfunsksjon for hver bitposisjon, og kalles en longitudinal redundans-sjekk. Denne metoden er høvelig effektiv for å detektere tilfeldige feil.

Den andre varanten får man ved å utføre en en-bits sirkulær skift på hash-verdien etter at hver blokk er prosessert. Dette medfører at inputen blir mer tilfeldig, og visker ut eventuelle regulariteter som finnes i inputen.

Krav og sikkerhet

Hvis hashverdien h = H(x), sier vi at x er preimage av h. Sagt på en annen måte er preimage den datablokken hvis hashverdi, ved bruk av hashfunksjonen H, er h. Ettersom H er en mange-til-en avbildning, vil det for en gitt hashverdi h være flere preimage.

Hvis vi har x ≠ y og H(x) = H(y), sier vi at vi har en kollisjon. Ettersom vi bruker hashfunksjoner for dataintegritet, er kollisjoner klart uønsket.

Angrep på hashfunksjoner

Det går også an å utføre uttømmende søk på hashfunksjoner; dette avhenger ikke av den spesifikke hashalgoritmen, men bare av bitlengden på den genererte hashen. Et slikt angrep går ut på å velge tileldig input og prøve hver til en kollisjon inntreffer.

Et preimage angrep går ut på å finne  y  slik at H(y) er lik en gitt hashverdi. Et andre preimage (second preimage) angrep går ut på gitt et preimage x å finne finnet et annet preimage y slik at H(x) = H(y). Dette er et spesialtilfelle av å finne en kollisjon, dvs. finne to meldinger x & y med samme hash; altså H(x) = H(y).

Styrken på en hashfunksjon mot uttømmende søk angis som 2^m/2 , dette betyr at 128 bit er utilstrekkelig, og 160 bit tvilsomt. Konklusjonen er at vi trenger bruke lenger MAC/hash.

Vi kan også utføre kryptoanalyse på hashfunksjoner, som vil være et angrep på bestemte sårbarheter i en gitt kryptografisk (hash-)algoritme. Her vil vi altså prøve å utnytte en eller annen egenskap til algoritmen for å utføre et annet angrep enn uttømmende søk.

Fødselsdagsparadokset

Hvis vi antar at alle dager i året (unntatt 29. februar) er like sannsynlige som en fødselsdag, hva er sannsynligheten for at to individer i en gruppe av n tilfeldig valgte mennesker  har samme fødselsdag? Etter «posthylle-prinsippet» vil sannsynligheten bli 100% når antallet mennesker overstiger 366, siden det bare er 366 mulige fødselsdager, inkludert 29. februar. Imidlertid viser det seg at sannsynligheten er 99,9% med bare 70 mennesker, og 50% sannsynlighet med 23 mennesker, noe som betyr at det er mer enn 50% sannsynlighet for at det finnes to barn i en vanlig skoleklasse som har samme fødselsdag. Fødselsdagsangrepet (Birthday attack) bruker denen probabilistiske modellen for å redusere kompleksiteten til å finne en kollisjon for en hashfunksjon.

Kollisjonsresistanseangrep – Fødselsdagsangrep

I et kollisjonsresistanseangrep ønsker en angriper å finne to meldinger eller datablokker som gir samme hash-resultat. Arbeidet som kreves er proporsjonalt med halvparten av bitlengden på hashen, iht. fødselsdagsparadokset beskrevet over. Yuval forslo følgende strategi for å utnytte fødselsdagsparadokset i et angrep på kollisjonsresistansen til en hashfunksjon: Kilden (A) er beredt til å signere en legitim melding x ved å legge til den korresponderende m-bit hashkoden og kryptere denne med As private RSA-nøkkel. Motstanderen genererer 2^m/2 variasjoner x’ av x, alle med essensielt samme mening, og lagrer meldingene og korresponderende hasher. Motstanderen genererer så en falsk melding y som den ønsker at A skal signere. Videre genererer motstanderen mindre variasjoner y’ av y, hvor alle essensielt har den samme meningen. For hver y’ beregner motstanderen H (y’), sjekker om den er lik en av H (x’) verdiene, og fortsetter til den finner en H (y’) som passer. Dvs., prosessen fortsetter til en y’  genereres som har en hashverdi som er lik hashverdien til en av x’ verdiene. Motstanderen sender så den gyldige varianten (f.eks. «Jeg lover å betale B 5 kroner») til A, som aner kald krig og ingen fare, og signerer meldingen. Signaturen kan deretter kobles på den falske varianten (f.eks. «Jeg lover å betale B 5 millioner kroner») og sendes til den tiltenkte mottakeren. Ettersom begge variantene har samme hashverdi, vil de generere samme signatur, og motstanderen er garantert suksess, selv om han ikke har As private nøkkel.

Hash-funksjon kryptoanalyse

Kryptoanalytiske angrep vil utnytte en eller annen strukturell egenskap til algoritmen, og vil eventuelt kunne være raskere enn bare uttømmende søk. Hashfunksjoner bruker en iterativ struktur hvor meldingen prosesseres i blokker (inkludert lengde): CV_i = f[CV_i-1, M_i], H(M)=CV_N

Angrepene fokuserer på kollisjoner i funksjonen f ved å utnytte dens egenskaper.

Hashfunksjoner basert på Cipher Block Chaining

Det har vært et antall forslag for hashfunksjoner basert på å bruke en CBC-teknikk, men uten å bruke en hemmelig nøkkel. En av de første forslagene kom fra Rabin: Del meldingen M i blokker av bestemt størrelse M₁, M₂, . . . , M_N og bruk en symmetrisk krypteringsalgoritme som f.eks. DES for å beregne hashen G som følger: H₀= initiell verdi («første nøkkel»), H_i = E(M_i, H_i-1), G = H_N. Dette ligner ganske mye på CBC-teknikken, men et er ingen hemmelig nøkkel involvert. Som med enhver hashfunksjon, er denn løsningen sårbar for et fødselsdagsangrep. Hvis krypteringsalgoritmen er DES, og bare en 64-bit hashkode genereres, vil systemet være svært sårbart.

Det kan vises at en eller annen form for fødselsdagsangrep vil lykkes mot ethvert hash-system som bruker CBC uten hemmelig nøkkel, gitt at hashkoden enten er liten nok, eller at den kan dekomponeres til uavhengige subkoder.

Et angrep som møtes på midten (Meet-in-the-middle Attack)

Møtes-på-midten-angrepet er en annen versjon av fødselsdagsangrepet som kan brukes også når motparten kun har tilgang på en melding og dens gyldige signatur, og ikke har mulighet til å få signert flere meldinger.

Som før har vi: H₀ = initial value _,  H_i = E_Mi [H_i-1] ,  G = H_N

Bytt ut M₁ … M_m-2 med vilkårlige (men ikke tilfeldige) Q₁ … Q_N-2 , og beregn H_i = E_Qi [H_i-1] for 1 ≤ i ≤ N-2. Generer 2^m/2  tilfeldige blokker og for hver X  beregn E_X [H_N-2] _. Generer 2^m/2  tilfeldige blokker, og for hver Y  beregn D_Y [G] . Fødselsdagsparadokset gir stor sannsynlighet for $X, Y slik at  E_X [H_N-2] = D_Y [G]

Meldingen Q_1, … Q_N-2, X, Y med den originale G som hash (eller kryptert med RSA som signatur) vil aksepteres som god fisk av mottakeren.

Secure Hash Algorithm (SHA)

SHA var opprinnelig utviklet av det amerikanske National Institute of Standards and Technology (NIST) og publisert som en føderal informasjonsprosesseringsstandard (FIPS 180) i 1993. Den ble revidert i 1995 som SHA-1. SHA var basert på hashfunksjonen MD4, og dens design ligner mye på MD4. SHA-1 har en 160-bit hashverdi. Tidlig på 2000-tallet var det en del forskning som stilte spørsmål rundt sikkerheten til SHA-1 og hvorvidt den var egnet til fremtidig bruk.  I 2002 laget NIST en revidert versjon av standarden som definerte trenye versjoner av SHA med hashverdi-lengder på 256, 384, og 512 bit; disse er kollektivt kjent som SHA-2, og var designet for kompatibilitet med økt sikkerhet tilbudt av AES chifferet. Strukturen og detaljene likner på SHA-1, ergo skulle analyse kunne gjøres på tilsvarende måte, men ikke minst pga. den økte hash-lengden er sikkerhetsnivåene merkbart høyere.

Brukket hash?

Hva betyr det egentlig at en algoritme er»brukket» (“broken”)? Hvis den er brukket akademisk betyr det at man har funnet angrep som systematisk er lettere eller mindre komplekse enn uttømmende søk – men avhengig av nøkkellengde eller hashlengde kan algoritmen like fullt være mer en sikker nok for fortsatt bruk. Algoritmer som er praktisk brukket vil føre til at brukere eller leverandører har grunn til å bekymre seg for om deres data fortsatt er sikre; dette vil også omfatte algortmer som har for korte nøkkellengder eller hashverdiertil å motstå uttømmende søk. Til slutt har vi algoritmer som er brukket psykologisk; dette kan være så enkelt som at noen har funnet et kollisjonspar for en hashalgoritme. Eksempel:

• Blokkchiffer DES: [Biham 91], [NIST 97] – 7 år fra brukket akademisk til praktisk
• Hash MD5: [Boer 93], [Wang.. 04] – 12 år fra brukket akademisk til praktisk(?)
• Singel-DES hash: 64-bit – praktisk brukket, men aldri akademisk brukket.

Et kollisjonspar kan føre til mange ting hvis det er smart mennesker involvert.

Kolllisjoner for MD5 som gir mening

Hvis vi har to postscript filer, M1 som er et anbefalingsbrev for Alice og M2 som er en bestilling av eteller annet til Alices fordel. Begge brevene har samme signatur fordi MD5(M1)=MD5(M2). Sjefen signerer sikkert velvillig M1 – men Alice kan så bruke M2 med en gyldig signatur.

SHA-3

SHA-1 er enda ikke «brukket»; ingen har demonstrert en praktisk teknikk som kan finne kollisjoner innen et rimelig tidsrom. Like fullt er SHA-1 regnet for å være usikker, og er i ferd med å bli faset ut til fordel for SHA-2 – men denne er basert på samme struktur og matematiske operasjoner som SHA-1, så det er fortsatt en kime til bekymring.

Ettersom det vil ta år å finne en passende erstatning for SHA-2 når den eventuelt viser seg å være sårbar, bestemte NIST  å begynne prosessen med å utvikle en ny hash-standard titdlig. De annonserte derfor allerde i 2007 en konkurranse (på tilsvarende måte som for AES) for neste generasjons SHA-3 NIST hash-funksjon. Evalueringskriteriene omfattet  sikkerhet nært teoretisk maksimum for hashstørrelser, kostnad i tid og minne, og fleksibilitet og enkelthet.

Det var også en norsk kandidat kalt Blue Midnight Wish, men den ble slått ut i andre runde. Vinneren av konkurransen, Keccak, ble annonsert av  NIST i oktober 2012. SHA-3 er en kryptografisk hashfunksjon som er ment å komplementere SHA-2 som den godkjente standarden for et bredt spekter av applikasjoner.

Svampkonstruksjonen

Den underliggende strukturen av SHA-3 er en mekanisme som designerne har kalt en svampkonstruksjon (sponge construction). Den tar en melding som input, og deler den opp i blokker av fast størrelse. Hver blokk prosesseres i rekkefølge, og resultatet i hver iterasjon mates inn i neste iterasjon, og til slutt produseres et sluttresultat. Svampfunksjonen defineres av tre parametre: f, den interne funksjonen som brukes til å prosessere hver input blokk; r, størrelsen i bit av input-blokkene, kalt bitrate; og pad, padding-algoritmen.

Svampfunksjonen har opp til to faser; først absorpsjonsfasen hvor den behandler hver inputblokk, og hvis man har behov for lengre hashverdi enn det som da finnes i tilstandsvariablen (state), går man over i kryste-fasen hvor man presser flere bit ut.