Hashfunktioner förklarade
När du laddar ner programvara och jämför en kontrollsumma, loggar in med ett lösenord, signerar ett dokument eller lägger till ett block i Bitcoin är en hashfunktion i arbete. Den gör om vilken mängd data som helst till ett kort fingeravtryck av fast storlek, hashvärdet, på ett sätt som inte går att göra ogjort eller förfalska. Idén är enkel, men kraven på en bra hashfunktion är stränga, och två av de mest använda, MD5 och SHA-1, klarade dem inte.
Ett fingeravtryck för data
En hashfunktion tar indata av valfri längd och returnerar ett hashvärde av fast längd: 256 bitar för SHA-256, skrivna som 64 hexadecimala siffror. Samma indata ger alltid samma hashvärde, så hashvärdet kan stå för datan. Om två filer har samma SHA-256-hashvärde kan du vara säker på att de är identiska, och om en bit i en nedladdning har skadats stämmer dess hashvärde inte längre med det som utgivaren angav. Eftersom det finns långt fler möjliga indata än hashvärden måste många indata dela varje hashvärde; en bra hashfunktion gör det helt enkelt omöjligt att hitta något av dem.
Tre löften
En kryptografisk hashfunktion ger tre löften. Förbildsresistens: givet ett hashvärde kan du inte hitta indata som ger det. Resistens mot andra förbild: givet en indata kan du inte hitta en annan indata med samma hashvärde. Kollisionsresistens: du kan inte hitta några två indata med samma hashvärde. För en ideal hashfunktion med n bitar är de bästa attackerna att gissa: ungefär 2ⁿ försök för en förbild och ungefär 2ⁿᐟ² för en kollision. En hashfunktion kallas knäckt när någon hittar ett sätt som är mycket snabbare än så.
Lavineffekten
Ändra en bit i indata, så ska varje bit i hashvärdet slå om med sannolikheten en halv, oberoende av de andra. Då ger en liten ändring i meddelandet ett hashvärde som ser helt orelaterat ut, och hashvärdet avslöjar ingenting om vilken del av indata som ändrades. SHA-256 åstadkommer detta genom att köra 64 rundor som roterar, adderar och kombinerar dess åtta 32-bitarsord, så att varje indatabit inom några rundor har påverkat varje ord. En enkel summa av byten ändras däremot med exakt lika mycket som indata ändrades, så den avslöjar allt.
Inuti SHA-256
SHA-256 fyller först ut meddelandet: den lägger till en 1-bit, nollor och meddelandets längd tills totalen är en multipel av 512 bitar. Sedan bearbetar den meddelandet 512 bitar i taget. Varje block sträcks ut till 64 ord, som blandas in i ett tillstånd på åtta 32-bitarsord, med start från fasta värden tagna från kvadratrötterna ur de åtta första primtalen. Tillståndet efter det sista blocket är hashvärdet. Denna kedjade konstruktion, uppkallad efter Ralph Merkle och Ivan Damgård, delas av MD5, SHA-1 och SHA-512; den nyare SHA-3, standardiserad 2015, använder en annan konstruktion som kallas svamp.
Födelsedagsattacken
I en grupp på 23 personer är sannolikheten att två fyller år samma dag strax över en halv, trots att året har 365 dagar, eftersom det som räknas är antalet par, som växer med kvadraten på gruppens storlek. Kollisioner i en hashfunktion följer samma regel. Bland 2ᵏ möjliga hashvärden väntar man sig en kollision efter ungefär √(π/2 · 2ᵏ) slumpmässiga indata. För 32 bitar är det omkring 82 000 indata, avklarat på ett ögonblick; för 128 bitar är det ungefär 2⁶⁴, vilket ligger inom räckhåll för stora beräkningsinsatser. Därför var MD5:s 128 bitar aldrig generösa, och därför fördubblar SHA-256 längden för att ge en säkerhet på 128 bitar.
MD5 och SHA-1: knäckta
Ron Rivest konstruerade MD5 1991, och NSA konstruerade SHA-1, som publicerades 1995. År 2004 visade Xiaoyun Wang och hennes kollegor hur man snabbt skapar MD5-kollisioner, och 2008 använde forskare dem för att förfalska ett certifikat som webbläsare litade på. Spionprogrammet Flame från 2012 använde en MD5-kollision för att utge sig för att vara en uppdatering från Microsoft. SHA-1 föll 2017, när Google och CWI Amsterdam publicerade två olika PDF-filer med samma SHA-1-hashvärde, efter ungefär 2⁶³ beräkningar. Båda duger fortfarande för att upptäcka oavsiktliga fel, men inte för något som en angripare kan tänkas ge sig på.
Där hashfunktioner används
Digitala signaturer signerar hashvärdet av ett dokument i stället för själva dokumentet. Git namnger varje fil och varje commit efter dess hashvärde, och Bitcoin-gruvarbetare letar efter blockhuvuden vars dubbla SHA-256-hash börjar med en lång rad nollor. Webbplatser ska aldrig lagra lösenord, bara en hash av dem; men eftersom folk väljer korta lösenord måste den hashen vara långsam och saltad, med metoder som bcrypt, scrypt eller Argon2, så att det blir dyrt att gissa. Kontrollsummor som CRC-32, som används i ZIP-filer, PNG-bilder och Ethernet, är också hashfunktioner, byggda för att fånga brus snarare än angripare.
Utforska själv
Öppna lekplatsen för hashfunktioner för att hasha din egen text med SHA-256, SHA-512, SHA-1, MD5, CRC-32 och en leksakssumma av byte. Ändra ett tecken och räkna de inverterade bitarna, kör lavintestet över tusen enbitsändringar för att se klockkurvan kring hälften av hashvärdet, och hitta riktiga kollisioner på de första 8 till 32 bitarna i ett hashvärde för att se födelsedagsattacken i arbete.
Ofta ställda frågor
Är hashning samma sak som kryptering?
Nej. Kryptering är tänkt att kunna göras ogjord av den som har nyckeln; hashning har ingen nyckel och kan inte göras ogjord av någon. Kryptering håller ett meddelande hemligt, medan en hash bara ger ett fingeravtryck som låter dig kontrollera ett meddelande du redan har.
Hur lång tid skulle det ta att hitta en SHA-256-kollision?
Med födelsedagsattacken ungefär 2¹²⁸ hashberäkningar, ett tal med 39 siffror. Även om varje dator på jorden inte gjorde något annat skulle det ta oerhört mycket längre tid än universums ålder. Ingen genväg är känd.
Varför skiljer sig två hashvärden av samma text aldrig åt?
En hashfunktion är deterministisk: den har ingen slump och ingen nyckel, så samma byte ger alltid samma hashvärde. Små skillnader som du inte kan se, som ett avslutande mellanslag, ett annat radslut eller en annan Unicode-form av en bokstav med accent, ger däremot ett annat hashvärde.
Vad är ett salt?
Ett slumpvärde som lagras bredvid en lösenordshash och blandas in i den. Två användare med samma lösenord får då olika hashar, och en angripare kan inte använda en enda förberäknad tabell över vanliga lösenord för alla konton.
Redo att prova det?
Öppna PictorX i din webbläsare - ingen installation, inget kreditkort krävs för att starta.
Öppna lekplatsen för hashfunktioner