Hashfunktioner forklaret
Når du downloader software og sammenligner en kontrolsum, logger ind med en adgangskode, signerer et dokument eller tilføjer en blok til Bitcoin, er en hashfunktion på arbejde. Den gør en hvilken som helst mængde data til et kort fingeraftryk af fast størrelse, hashværdien, på en måde, der hverken kan gøres om eller forfalskes. Idéen er enkel, men kravene til en god hash er strenge, og to af de mest brugte, MD5 og SHA-1, klarede dem ikke.
Et fingeraftryk for data
En hashfunktion tager et input af en hvilken som helst længde og returnerer en hashværdi af fast længde: 256 bits for SHA-256, skrevet som 64 hexadecimale cifre. Samme input giver altid samme hashværdi, så hashværdien kan stå for dataene. Har to filer samme SHA-256-hashværdi, kan du være sikker på, at de er identiske, og hvis én bit i en download er blevet beskadiget, passer dens hashværdi ikke længere med den, udgiveren oplyste. Fordi der er langt flere mulige input end hashværdier, må mange input dele hver hashværdi; en god hash gør det blot umuligt at finde nogen af dem.
Tre løfter
En kryptografisk hash giver tre løfter. Preimage-resistens: givet en hashværdi kan man ikke finde et input, der giver den. Second preimage-resistens: givet et input kan man ikke finde et andet input med samme hashværdi. Kollisionsresistens: man kan slet ikke finde to input med samme hashværdi. For en ideel hash med n bits er gætteri det bedste angreb: omkring 2ⁿ forsøg for et preimage og omkring 2ⁿᐟ² for en kollision. En hash kaldes brudt, når nogen finder en vej, der er meget hurtigere end det.
Lavineeffekten
Ændrer man én bit i inputtet, bør hver bit i hashværdien vende med en sandsynlighed på en halv, uafhængigt af de andre. Så giver en lille ændring i beskeden en hashværdi, der ser ud til at være helt uden sammenhæng med den første, og hashværdien afslører intet om, hvilken del af inputtet der ændrede sig. SHA-256 opnår det ved at køre 64 runder, der roterer, lægger sammen og kombinerer sine otte ord på 32 bit, så hver inputbit inden for få runder har påvirket hvert ord. En simpel sum af bytene ændrer sig derimod med præcis det beløb, inputtet ændrede sig, så den afslører alt.
Inde i SHA-256
SHA-256 fylder først beskeden op: den tilføjer en 1-bit, nuller og beskedens længde, indtil det samlede antal er et multiplum af 512 bits. Derefter behandler den beskeden 512 bits ad gangen. Hver blok strækkes til 64 ord, som blandes ind i en tilstand af otte ord på 32 bit, der starter fra faste værdier taget fra kvadratrødderne af de første otte primtal. Tilstanden efter den sidste blok er hashværdien. Denne kædede opbygning, opkaldt efter Ralph Merkle og Ivan Damgård, deles af MD5, SHA-1 og SHA-512; den nyere SHA-3, standardiseret i 2015, bruger en anden konstruktion kaldet en svamp (sponge).
Fødselsdagsangrebet
I en gruppe på 23 personer er chancen for, at to har fødselsdag samme dag, lidt over en halv, selvom året har 365 dage, fordi det afgørende er antallet af par, og det vokser med kvadratet på gruppens størrelse. Kollisioner i en hash følger samme regel. Blandt 2ᵏ mulige hashværdier kan man forvente en kollision efter omkring √(π/2 · 2ᵏ) tilfældige input. For 32 bits er det omkring 82.000 input, klaret på et øjeblik; for 128 bits er det omkring 2⁶⁴, hvilket er inden for rækkevidde af store regneprojekter. Derfor var MD5's 128 bits aldrig rundhåndede, og derfor fordobler SHA-256 længden for at give en sikkerhed på 128 bits.
MD5 og SHA-1: brudt
Ron Rivest designede MD5 i 1991, og NSA designede SHA-1, der blev udgivet i 1995. I 2004 viste Xiaoyun Wang og hendes kolleger, hvordan man hurtigt laver MD5-kollisioner, og i 2008 brugte forskere dem til at forfalske et certifikat, som webbrowsere stolede på. Spionprogrammet Flame fra 2012 brugte en MD5-kollision til at udgive sig for at være en opdatering fra Microsoft. SHA-1 faldt i 2017, da Google og CWI Amsterdam offentliggjorde to forskellige PDF-filer med samme SHA-1-hashværdi efter omkring 2⁶³ beregninger. Begge er stadig fine til at opdage tilfældige fejl, men ikke til noget, en angriber kunne have i kikkerten.
Hvor hashes bruges
Digitale signaturer signerer hashen af et dokument i stedet for selve dokumentet. Git navngiver hver fil og hvert commit efter dets hash, og Bitcoin-minere leder efter blokheadere, hvis dobbelte SHA-256-hash begynder med en lang række nuller. Websteder bør aldrig gemme adgangskoder, kun en hash af dem; men fordi folk vælger korte adgangskoder, skal den hash være langsom og saltet, med metoder som bcrypt, scrypt eller Argon2, så gætteri bliver dyrt. Kontrolsummer som CRC-32, der bruges i ZIP-filer, PNG-billeder og Ethernet, er også hashes, lavet til at fange støj frem for angribere.
Prøv det selv
Åbn Leg med hashfunktioner for at hashe din egen tekst med SHA-256, SHA-512, SHA-1, MD5, CRC-32 og en simpel sum af bytes. Skift ét tegn og tæl de vendte bits, kør lavinetesten over tusind ændringer af én bit for at se klokkekurven omkring halvdelen af hashværdien, og find ægte kollisioner på de første 8 til 32 bits af en hashværdi for at se fødselsdagsangrebet i aktion.
Ofte stillede spørgsmål
Er hashing det samme som kryptering?
Nej. Kryptering er beregnet til at blive gjort om af den, der har nøglen; hashing har ingen nøgle og kan ikke gøres om af nogen. Kryptering holder en besked hemmelig, mens en hash kun giver et fingeraftryk, som lader dig kontrollere en besked, du allerede har.
Hvor lang tid ville det tage at finde en SHA-256-kollision?
Med fødselsdagsangrebet omkring 2¹²⁸ hashberegninger, et tal med 39 cifre. Selv hvis alle computere på Jorden ikke lavede andet, ville det tage ufatteligt meget længere end universets alder. Ingen genvej er kendt.
Hvorfor er to hashes af samme tekst aldrig forskellige?
En hashfunktion er deterministisk: den har ingen tilfældighed og ingen nøgle, så de samme bytes giver altid samme hashværdi. Små forskelle, du ikke kan se, som et mellemrum til sidst, et andet linjeskift eller en anden Unicode-form af et bogstav med accent, giver til gengæld en anden hashværdi.
Hvad er et salt?
En tilfældig værdi, der gemmes ved siden af en adgangskodehash og blandes ind i den. To brugere med samme adgangskode får så forskellige hashes, og en angriber kan ikke bruge én forudberegnet tabel over almindelige adgangskoder til alle konti.
Er du klar til at prøve?
Åbn PictorX i din browser – ingen installation og intet kreditkort for at komme i gang.
Åbn Leg med hashfunktioner