Dagen SHA-1 ble knekt i praksis
Den 23. februar 2017 kunngjorde forskningsinstituttet CWI i Amsterdam sammen med Google at de hadde funnet den første praktiske kollisjonen for hashfunksjonen SHA-1. Angrepet fikk navnet SHAttered. For første gang fantes det to forskjellige filer som ga nøyaktig samme SHA-1-verdi, laget med vilje og dokumentert offentlig. Det som lenge hadde vært en teoretisk bekymring, var nå et konkret faktum.
Resultatet var ikke bare en akademisk kuriositet. Det fungerte som et tydelig signal til hele bransjen om at SHA-1 ikke lenger kunne brukes der sikkerheten avhang av at hashen var unik. Denne artikkelen forklarer hva en kollisjon er, hva forskerne faktisk demonstrerte, hvor mye arbeid det krevde, og hvilke konsekvenser det fikk.
Hva er en kollisjon, og hvorfor er den farlig?
En kryptografisk hashfunksjon skal lage et kort, fast avtrykk av data. Et av de viktigste kravene er kollisjonsmotstand: det skal være praktisk umulig å finne to ulike meldinger som gir samme hash.
En kollisjon oppstår når to forskjellige inndata likevel ender på den samme hashverdien. I teorien finnes det alltid kollisjoner, fordi det er uendelig mange mulige meldinger, men bare et endelig antall mulige hashverdier. Poenget med en god hashfunksjon er ikke at kollisjoner er umulige å eksistere, men at de skal være umulige å finne innenfor rimelig tid og ressurser.
Når noen først klarer å finne en kollisjon, faller en grunnleggende antakelse bort. Tenk på et system som stoler på at hashen identifiserer innholdet entydig. Hvis en angriper kan lage to filer med samme hash, kan han vise frem den harmløse filen for å få en godkjenning, en signatur eller et sertifikat, og deretter bytte den ut med den skadelige filen som har akkurat samme hash. Mottakeren som bare sjekker hashen, ser ingen forskjell. Dette er kjernen i hvorfor en kollisjon undergraver tillit: avtrykket er ikke lenger et pålitelig bevis på hva innholdet faktisk er.
Hva forskerne demonstrerte
SHAttered besto av to PDF-filer. De to filene var forskjellige. De hadde ulikt synlig innhold, men de delte den samme SHA-1-verdien:
38762cf7f55934b34d179ae6a4c80cadccbb7f0a
Begge filene ga altså dette ene avtrykket når man kjørte SHA-1 over dem. Samtidig var de fullstendig forskjellige under en sterkere funksjon: kjørte du SHA-256 over de samme to filene, fikk du to ulike verdier. Det er en viktig presisering. Det var SHA-1 som ble knekt, ikke SHA-256. SHA-256 skilte tvert imot de to filene fra hverandre uten problemer, slik en trygg hashfunksjon skal.
De to dokumentene kan du laste ned og kontrollere selv:
Den fullstendige vitenskapelige beskrivelsen av angrepet er publisert i et eget dokument:
Det forskerne viste, var en såkalt kollisjon der angriperen kan styre deler av innholdet. De konstruerte to filer som begynte med en felles del, og deretter føyde til nøye beregnede forskjeller slik at SHA-1-verdiene møttes igjen i nøyaktig samme punkt. At de valgte PDF som format, var ikke tilfeldig: formatet gjør det mulig å gjemme de tekniske forskjellene slik at hver fil likevel vises som et meningsfullt dokument.
Et angrep med praktiske følger, ikke bare et tall
Forskjellen mellom en ren tallkollisjon og det SHAttered demonstrerte, er nettopp at filene var fullverdige dokumenter. Det er én ting å finne to tilfeldige bitstrenger som tilfeldigvis møtes i samme hash. Det er noe ganske annet å lage to filer som begge åpner seg som lesbare PDF-dokumenter, ser troverdige ut, og likevel deler samme avtrykk. Det er denne kontrollen over innholdet som gjør et angrep farlig i den virkelige verden, fordi den lar en angriper bygge et par der det ene dokumentet er uskyldig og det andre er noe han egentlig vil ha godkjent.
Forskerne understreket også at de to filene kunne deles et felles oppsett, og at den samme teknikken i prinsippet kunne gjenbrukes til å lage flere kolliderende par på en mer effektiv måte enn å starte helt fra bunnen hver gang. Med andre ord var ikke dette en engangshendelse knyttet til akkurat disse to PDF-ene, men en demonstrasjon av en metode.
Bakgrunnen: en svakhet som lenge var varslet
SHA-1 ble tatt i bruk på 1990-tallet og var i lang tid et standardvalg for digitale sertifikater, signaturer og integritetssjekk. Allerede flere år før 2017 hadde imidlertid kryptografer publisert teoretiske angrep som viste at SHA-1 var svakere enn den burde være. Disse arbeidene anslo at en kollisjon ville kreve langt mindre arbeid enn et idealisert, perfekt design ville krevd, og de fungerte som en advarsel om at en praktisk kollisjon bare var et spørsmål om tid og ressurser.
Mange aktører reagerte på disse advarslene ved å begynne planleggingen av en overgang til sterkere funksjoner. Likevel manglet det et endelig, konkret bevis. Så lenge ingen faktisk hadde produsert en kollisjon, var det fristende å utsette arbeidet og fortsette å bruke SHA-1 der det allerede var innarbeidet. SHAttered fjernet dette pusterommet ved å gjøre den teoretiske risikoen til et håndfast resultat hvem som helst kunne kontrollere selv.
Hvor mye arbeid krevde angrepet?
Det som gjør SHAttered imponerende, er ikke bare at en kollisjon ble funnet, men hvor mye regnekraft det krevde å presse den frem. Selve angrepet innebar i størrelsesorden 9,2 trillioner SHA-1-beregninger. Tallet er enormt, og det illustrerer hvorfor en slik kollisjon ikke hadde blitt demonstrert tidligere.
For å sette mengden arbeid i perspektiv tilsvarte innsatsen omtrent 6 500 CPU-år pluss rundt 110 GPU-år med regnetid. Med andre ord: det ville tatt en enkelt vanlig prosessor flere tusen år å gjøre dette alene. Forskerne fordelte arbeidet over store mengder maskinvare for å gjennomføre det innenfor rimelig tid.
To ting er verdt å merke seg. For det første var dette langt billigere enn et rent tilfeldig søk gjennom alle muligheter. Angrepet utnyttet kjente svakheter i SHA-1 sin indre struktur og var derfor mye mer effektivt enn å prøve seg frem blindt. For det andre er regnekraft noe som bare blir billigere over tid. Et angrep som krevde ekstreme ressurser i 2017, blir gradvis mer overkommelig. Det var en del av poenget: dersom en velfinansiert aktør kunne klare dette nå, ville stadig flere kunne klare det senere.
Konsekvensene: rask utfasing av SHA-1
SHAttered var ikke det første tegnet på at SHA-1 var på vei ut. Svakheter i algoritmen hadde vært kjent og diskutert i flere år, og mange aktører hadde allerede begynt å planlegge en overgang. Men en konkret, fungerende kollisjon endret tempoet i diskusjonen fra teoretisk uro til praktisk hastesak. Det ble vanskelig å argumentere for å beholde SHA-1 når alle kunne laste ned to filer med samme verdi.
Resultatet var at utfasingen av SHA-1 ble fremskyndet på flere viktige områder:
- TLS-sertifikater. Sertifikater som binder et domene til en offentlig nøkkel, hadde lenge brukt SHA-1 i signaturen. Etter hvert ble SHA-1-baserte sertifikater avvist, og nettlesere og sertifikatutstedere gikk over til sterkere funksjoner som SHA-256.
- Git. Versjonskontrollsystemet Git identifiserer innhold ved hjelp av SHA-1. En kollisjon var derfor en reell bekymring for prosjekter der innholdets identitet må være til å stole på. Hendelsen ga ekstra fart til arbeidet med å håndtere kollisjoner og på sikt bevege seg bort fra SHA-1 alene.
- Digital signering. Alle systemer som signerte hashen av en melding med SHA-1, var i prinsippet sårbare for at en angriper kunne bytte ut innholdet under samme signatur. Anbefalingen ble klar: ikke bruk SHA-1 til nye signaturer.
Hvordan man forsvarte seg i overgangsperioden
En fullstendig overgang bort fra SHA-1 skjer ikke over natten. Mange systemer hadde SHA-1 dypt innebygd, og data som allerede var signert eller lagret med SHA-1 forsvant ikke bare fordi en kollisjon var blitt vist. I overgangsperioden ble derfor flere tiltak tatt i bruk.
Det viktigste og mest åpenbare var å slutte å bruke SHA-1 til alt nytt: nye sertifikater, nye signaturer og nye integritetsmekanismer skulle bruke sterkere funksjoner. I tillegg ble det utviklet metoder for å oppdage nettopp den typen kolliderende filer som SHAttered besto av. Slike teknikker ser etter de karakteristiske mønstrene som oppstår når noen konstruerer en SHA-1-kollisjon, og kan flagge mistenkelige filer før de gjør skade. Dette ga systemer som ennå brukte SHA-1, en ekstra forsvarslinje mens den fullstendige utfasingen pågikk.
Lærdommen for praktikere var tydelig: når en hashfunksjon først er svekket, holder det ikke å vente på at alle skal bytte samtidig. Man må stanse ny bruk umiddelbart og samtidig beskytte det som ennå ikke er migrert.
Hva vi kan lære av SHAttered
Historien om SHA-1 er en påminnelse om at kryptografiske antakelser har en holdbarhetsdato. En algoritme som var god nok da den ble innført, kan bli utdatert etter hvert som forskningen finner svakheter og maskinvaren blir kraftigere. SHAttered viste dette på en konkret og overbevisende måte, ikke gjennom et teoretisk argument, men gjennom to filer hvem som helst kunne laste ned og kontrollere.
Lærdommen er ikke at hashfunksjoner er upålitelige, men at valg av algoritme må følge med tiden. Når en funksjon viser tegn til svakhet, er det fornuftig å bytte før noen klarer å utnytte den i praksis. For SHA-1 kom byttet for sent for noen og akkurat tidsnok for andre. I dag står SHA-256 og resten av SHA-2-familien for den jobben SHA-1 en gang gjorde, og overgangen fortsatte raskere nettopp på grunn av det som ble vist denne dagen i februar 2017.
