När en bruten hashfunktion blev verklighet

Den 23 februari 2017 offentliggjorde forskningsinstitutet CWI i Amsterdam tillsammans med Google den första praktiska kollisionen för hashfunktionen SHA-1. Resultatet fick namnet SHAttered. För första gången kunde någon visa upp två olika filer som producerade exakt samma SHA-1-värde, inte som ett teoretiskt resonemang utan som två faktiska filer vem som helst kunde ladda ner och kontrollera.

Det här var ett ögonblick som kryptografer hade förutspått i åratal. Svagheter i SHA-1 hade diskuterats sedan mitten av 2000-talet, och flera teoretiska attacker hade pressat ner kostnaden för en kollision steg för steg. SHAttered var beviset på att kostnaden hade sjunkit tillräckligt för att en kollision skulle gå att genomföra i praktiken av en tillräckligt resursstark aktör.

Vad en kollision är

För att förstå varför detta var allvarligt behöver man förstå vad en kollision innebär. En hashfunktion tar data av godtycklig storlek och producerar ett resultat av fast längd. SHA-1 ger alltid ett resultat på 160 bitar. Eftersom indatan kan vara obegränsat stor men resultatet är begränsat, finns det matematiskt sett oändligt många olika indata som delar samma hashvärde. Det går inte att undvika.

Hela poängen med en kryptografisk hashfunktion är dock att det ska vara praktiskt ogenomförbart att faktiskt hitta två sådana indata. Så länge ingen kan hitta en kollision kan ett hashvärde fungera som ett unikt fingeravtryck. Säg att du ser hashvärdet av ett dokument, då litar du på att det enbart kan höra till just det dokumentet. En kollision bryter precis det antagandet. Plötsligt finns två olika dokument med samma fingeravtryck, och fingeravtrycket säger inte längre entydigt vilket dokument det handlar om.

De två PDF-filerna

SHAttered demonstrerades med två PDF-filer. De två filerna har olika innehåll och ser olika ut när man öppnar dem, men de delar samma SHA-1-värde:

38762cf7f55934b34d179ae6a4c80cadccbb7f0a

Vem som helst kan ladda ner dem och köra en SHA-1-beräkning på båda för att se att värdet är identiskt. Filerna finns tillgängliga som shattered-1.pdf och shattered-2.pdf.

Det avgörande är att samma två filer ger helt olika resultat när man i stället beräknar deras SHA-256-värde. Det visar tydligt att problemet ligger hos SHA-1 och inte hos filerna i sig. SHA-256, som tillhör den nyare SHA-2-familjen, skiljer obekymrat de två filerna åt. SHA-1 gör det inte. Den fullständiga forskningsrapporten som beskriver metoden finns publicerad som shattered.pdf.

Den enorma beräkningsinsatsen

En kollision i SHA-1 var aldrig gratis att ta fram. Forskarna beräknade att attacken krävde ungefär 9,2 triljoner SHA-1-beräkningar (cirka 9,2 gånger tio upphöjt till arton operationer). Det är ett tal som är svårt att greppa intuitivt.

Uttryckt i beräkningstid motsvarade insatsen ungefär 6 500 processorår av arbete i en första fas, plus omkring 110 grafikprocessorår i en andra fas. Med andra ord, om en enda dator skulle utföra hela arbetet ensam, skulle det ta tusentals år. Genom att fördela arbetet över mycket stora mängder hårdvara parallellt kunde forskarna i stället slutföra det inom rimlig tid.

Den här siffran är viktig av två skäl. Den visar att attacken var långt bortom vad en hobbyist kunde åstadkomma vid tillfället, men också att den låg väl inom räckhåll för stora organisationer, underrättelsetjänster eller välfinansierade angripare. Och historiskt går kostnaden för den här typen av attacker bara åt ett håll: nedåt. Det som krävde extrema resurser 2017 blir billigare för varje år som hårdvaran utvecklas och metoderna förfinas. En algoritm som är dyr att bryta i dag kan vara billig att bryta i morgon, vilket är själva anledningen till att man slutar använda den i god tid.

Varför en kollision bryter förtroende

Konsekvenserna sträcker sig långt bortom två PDF-filer. Många säkerhetssystem bygger på antagandet att ett hashvärde unikt identifierar sin data. När det antagandet faller kan en angripare i princip förbereda två dokument: ett ofarligt och ett skadligt, som delar samma hashvärde.

Tänk dig att ett ofarligt dokument granskas och godkänns, och att godkännandet i praktiken gäller dess hashvärde. En angripare som har en kollision kan då byta ut det godkända dokumentet mot sitt skadliga motsvarighet, eftersom det skadliga dokumentet har exakt samma hashvärde och därför ser ut att vara samma godkända dokument. Den som litar på hashvärdet luras.

Just därför hotar en kollision allt som vilar på hashvärden, från digitala signaturer och certifikat till system för versionshantering. Ett certifikat signeras genom att ett hashvärde av dess innehåll signeras med en privat nyckel. Om två olika certifikatinnehåll kan dela samma hashvärde, kan en signatur som gäller det ena innehållet missbrukas för att intyga det andra.

Följderna: SHA-1 fasas ut

SHAttered blev den konkreta knuff som påskyndade utfasningen av SHA-1 på bred front. Övergången hade redan inletts, men det praktiska beviset gjorde att de sista tveksamheterna försvann.

Inom TLS, protokollet som ligger bakom säkra webbanslutningar, hade certifikat som signerats med SHA-1 redan börjat avvisas av de stora webbläsarna. Efter SHAttered fanns det inget kvar att argumentera mot. Certifikatutfärdare hade övergått till SHA-256, och äldre SHA-1-certifikat betraktades som otillförlitliga.

Inom versionshanteringssystemet Git, som använde SHA-1 för att identifiera commits och objekt, satte demonstrationen igång ett konkret arbete med att minska beroendet av SHA-1, däribland införandet av skydd som upptäcker den typ av manipulerad data som en kollisionsattack använder. På liknande sätt övergick rutiner för signering av programvara och dokument till starkare hashfunktioner.

Lärdomen

SHAttered är ett ovanligt tydligt exempel på hur kryptografisk forskning fungerar i praktiken. En svaghet identifieras först teoretiskt, kostnaden för att utnyttja den sjunker stegvis, och till slut blir den genomförbar. Mellan den teoretiska varningen och det praktiska beviset finns ett tidsfönster, och poängen är att byta ut algoritmen medan fönstret fortfarande är öppet, inte efter att någon har utnyttjat svagheten i verkligheten.

För SHA-1 fungerade det till stor del som det skulle. Utfasningen var redan på gång när kollisionen demonstrerades, och SHAttered såg till att de sista systemen flyttade vidare. För den som bygger system i dag är lärdomen enkel: lita inte på en hashfunktion bara för att den fungerar i dag, utan följ rekommendationerna och byt till en starkare funktion i god tid. SHA-256 och resten av SHA-2-familjen är det vanliga valet i dag.