Dagen SHA-1 ikke længere kunne stoles på

Den 23. februar 2017 offentliggjorde forskere fra CWI Amsterdam og Google i fællesskab et resultat, som kryptografer længe havde frygtet, men ikke set demonstreret i praksis: den første rigtige SHA-1-kollision. Projektet fik navnet SHAttered, og det viste, at det var muligt at fremstille to forskellige filer med præcis det samme SHA-1-hash. Dermed faldt en af de antagelser, som store dele af internettets sikkerhed havde hvilet på i over to årtier.

For at forstå hvorfor det var så alvorligt, er vi nødt til at se på, hvad en kollision egentlig er, og hvorfor den ødelægger tilliden til en hashfunktion.

Hvad er en kollision?

En kryptografisk hashfunktion tager et input og frembringer et fingeraftryk af fast længde. SHA-1 producerer 160 bit. Eftersom der findes uendeligt mange mulige input, men kun et endeligt antal mulige hashværdier, er det matematisk uundgåeligt, at to forskellige input på et tidspunkt vil dele samme hash. Sådanne sammenfald kaldes kollisioner.

Pointen med en sikker hashfunktion er ikke, at kollisioner ikke findes, for det gør de. Pointen er, at det skal være så regnetungt at finde en kollision, at ingen i praksis kan gøre det. Når denne modstand brydes, kan en angriber konstruere to dokumenter med samme hash og dermed bytte det ene ud med det andet, uden at nogen kontrol baseret på hashet opdager forskellen.

Det er netop dér, faren ligger. Hvis et system stoler på, at to filer med samme SHA-1-hash er identiske, og en angriber kan fremstille to forskellige filer med samme hash, så kan en harmløs fil og en skadelig fil pludselig bære det samme digitale fingeraftryk.

Det er værd at skelne mellem to slags kollisionsangreb. I et generelt kollisionsangreb søger man hvilke som helst to input, der frembringer samme hash. I et identical-prefix-angreb, som SHAttered byggede på, deler de to filer den samme begyndelse og adskiller sig først i et omhyggeligt konstrueret område længere fremme. Sidstnævnte er sværere at udnytte i alle tænkelige sammenhænge, men fuldt tilstrækkeligt til at fremstille to dokumenter, der ser forskellige ud og alligevel deler hash. Det var præcis denne form for kollision, forskerne demonstrerede.

SHAttered i praksis

SHAttered demonstrerede angrebet helt konkret med to PDF-filer. De to dokumenter havde forskelligt synligt indhold, men deres SHA-1-hash var identisk. Den fælles SHA-1-værdi var:

38762cf7f55934b34d179ae6a4c80cadccbb7f0a

Begge filer er stadig tilgængelige, så man selv kan efterprøve det:

Det afgørende er, at sammenfaldet kun gælder under SHA-1. Beregner man i stedet et SHA-256-hash af de to filer, får man to helt forskellige værdier. Det viser tydeligt, at problemet ikke er filerne i sig selv, men den svaghed, der nu var fundet i SHA-1. En stærkere hashfunktion afslører øjeblikkeligt, at de to dokumenter ikke er ens.

Forskerne udgav også en teknisk artikel, der beskriver metoden i detaljer, for dem der vil grave i selve angrebet: shattered.pdf.

Hvor stort var regnearbejdet?

En central pointe i SHAttered var, at angrebet var praktisk gennemførligt, men ikke billigt. Holdet anslog, at det krævede i størrelsesordenen 9,2 trillioner SHA-1-beregninger (9,2 efterfulgt af atten nuller, på engelsk omtalt som quintillion). Omsat til regnekraft svarede indsatsen til omtrent 6.500 CPU-år plus omkring 110 GPU-år.

Det er enorme tal, og de forklarer, hvorfor angrebet ikke kunne være udført med en enkelt computer på et rimeligt tidsrum. Men de er samtidig tal, der ligger inden for rækkevidde for en stor organisation med adgang til store mængder hardware. Og det var hele pointen: et angreb, der tidligere kun var teoretisk, var nu blevet noget, en velfinansieret aktør faktisk kunne udføre. Når noget først er muligt og prisen falder med tiden, er det kun et spørgsmål om hvornår, ikke om hvorvidt, det bliver tilgængeligt for flere.

For at gøre angrebet håndterbart benyttede forskerne en teknik kaldet et identical-prefix-kollisionsangreb, hvor de to filer deler en fælles begyndelse og derefter skiller sig fra hinanden i et nøje konstrueret område. PDF-formatet er fleksibelt nok til at gemme disse forskelle, så de to dokumenter kan vise forskelligt indhold, mens de bevarer det samme SHA-1-hash.

Det er også værd at huske, hvorfor tallene kunne falde over tid. Kryptografiske angreb bliver sjældent dyrere. De bliver billigere, efterhånden som hardware bliver hurtigere, og efterhånden som forskere finder smartere genveje. Et angreb, der ved offentliggørelsen krævede ressourcer på niveau med en stor organisation, vil typisk være inden for rækkevidde af langt flere aktører nogle år senere. Derfor er det ikke nok at spørge, om et angreb er praktisk i dag. Man må også spørge, hvor hurtigt det bliver praktisk for flere, og handle i god tid, før det sker.

Hvorfor en kollision bryder tillid

Forestil dig en digital underskrift på en kontrakt. I praksis underskriver man sjældent hele dokumentet direkte. I stedet beregner man et hash af dokumentet og signerer dette hash. Det er hurtigere og fungerer fint, så længe hashfunktionen er stærk.

Men hvis hashfunktionen tillader kollisioner, opstår der et hul. En angriber kan forberede to dokumenter med samme hash: et harmløst, som offeret godkender og signerer, og et skadeligt med ganske andet indhold. Fordi de deler hash, gælder den signatur, der blev sat på det harmløse dokument, lige så vel for det skadelige. Modtageren har ingen mulighed for at se forskel ud fra hashet alene.

Det samme princip gælder for certifikater, softwarepakker og alt andet, hvor man bruger et hash som stedfortræder for det fulde indhold. Når kollisioner bliver mulige, kan fingeraftrykket ikke længere garantere, at to ting er ens, og dermed forsvinder hele grundlaget for at stole på det.

En vigtig nuance er, at SHAttered ikke brød SHA-1’s modstand mod preimage. Det forblev praktisk umuligt at tage et givet hash og regne baglæns til et input. Det, der faldt, var kollisionsmodstanden, altså evnen til at forhindre, at nogen frit konstruerer to forskellige input med samme hash. For mange anvendelser er det netop kollisionsmodstanden, der betyder noget, fordi en angriber ofte kan vælge begge dokumenter selv. Derfor var bruddet alvorligt, selv om SHA-1 ikke var fuldstændig knust på alle fronter.

Konsekvenserne: hurtigere udfasning af SHA-1

SHAttered var ikke det første tegn på, at SHA-1 var på vej ud. Teoretiske svagheder var blevet beskrevet i årevis, og store aktører havde allerede annonceret planer om at droppe algoritmen. Men en konkret, offentlig demonstration ændrede tonen fra hypotetisk bekymring til håndgribelig risiko, og det fremskyndede udfasningen mærkbart.

Effekten kunne ses flere steder:

  • TLS-certifikater: Browsere og certifikatudstedere skubbede på for at fjerne de sidste SHA-1-baserede certifikater, så krypteret webtrafik i stedet hvilede på stærkere hashfunktioner.
  • Git: Versionsstyringssystemet Git identificerer commits via SHA-1. Efter SHAttered blev der arbejdet på at indbygge beskyttelse mod kollisionsangreb og på sigt at bevæge sig mod stærkere hashing.
  • Digitale signaturer og signering: Værktøjer til kodesignering og dokumentsignering tog skridt væk fra SHA-1 for ikke at efterlade en kendt svaghed i underskriftskæden.

Den bredere lære var enkel: en hashfunktion er ikke sikker for evigt. Regnekraften vokser, og angrebsteknikkerne forfines. Derfor pensioneres kryptografiske algoritmer planlagt, helst længe før nogen offentligt demonstrerer, at de kan brydes. SHAttered blev et lærebogseksempel på, hvad der sker, når man venter for længe, og hvorfor det er klogt at skifte til en stærkere funktion som SHA-256, før presset bliver akut.

Den korte konklusion

SHAttered beviste, at SHA-1 ikke længere kunne bruges dér, hvor sikkerhed afhænger af, at kollisioner er upraktiske at finde. To forskellige PDF-filer med samme SHA-1-hash, men forskellige SHA-256-hash, gjorde svagheden umulig at bortforklare. Resultatet var ikke panik, men en velbegrundet og hurtigere overgang til moderne hashfunktioner. For alle, der bygger systemer, der hviler på tillid, er historien en påmindelse om at vælge sine kryptografiske byggesten med omtanke og at skifte dem ud, før de svigter.