Hashfuncties uitgelegd

Als je software downloadt en een controlesom vergelijkt, inlogt met een wachtwoord, een document ondertekent of een blok aan Bitcoin toevoegt, is er een hashfunctie aan het werk. Die maakt van elke hoeveelheid gegevens een korte vingerafdruk van vaste grootte, de hashwaarde, op een manier die niet terug te draaien of te vervalsen is. Het idee is eenvoudig, maar de eisen aan een goede hash zijn streng, en twee van de meest gebruikte, MD5 en SHA-1, hebben ze niet doorstaan.

Twee berichten die één letter verschillen gaan een hashfunctie in en komen eruit als twee totaal verschillende SHA-256-hashwaarden, met de omgeklapte bits gemarkeerd in een raster
Twee berichten die één letter verschillen gaan een hashfunctie in en komen eruit als twee totaal verschillende SHA-256-hashwaarden, met de omgeklapte bits gemarkeerd in een raster

Een vingerafdruk voor gegevens

Een hashfunctie neemt invoer van elke lengte en geeft een hashwaarde van vaste lengte terug: 256 bits voor SHA-256, geschreven als 64 hexadecimale cijfers. Dezelfde invoer geeft altijd dezelfde hashwaarde, dus de hashwaarde kan voor de gegevens staan. Hebben twee bestanden dezelfde SHA-256-hashwaarde, dan weet je zeker dat ze identiek zijn, en als één bit van een download beschadigd is, klopt de hashwaarde niet meer met die van de uitgever. Omdat er veel meer mogelijke invoeren zijn dan hashwaarden, moeten veel invoeren elke hashwaarde delen; een goede hash maakt het simpelweg onmogelijk om er een te vinden.

Drie beloften

Een cryptografische hash doet drie beloften. Preimage-bestendigheid: bij een gegeven hashwaarde kun je geen invoer vinden die hem oplevert. Tweede-preimage-bestendigheid: bij een gegeven invoer kun je geen andere invoer met dezelfde hashwaarde vinden. Botsingsbestendigheid: je kunt helemaal geen twee invoeren met dezelfde hashwaarde vinden. Voor een ideale hash met n bits is raden de beste aanval: ongeveer 2ⁿ pogingen voor een preimage en ongeveer 2ⁿᐟ² voor een botsing. Een hash heet gebroken als iemand een manier vindt die veel sneller is.

Het lawine-effect

Verander één bit van de invoer en elk bit van de hashwaarde moet omklappen met een kans van een half, onafhankelijk van de andere. Dan geeft een kleine wijziging in het bericht een hashwaarde die er totaal niets mee te maken lijkt te hebben, en verraadt de hashwaarde niets over welk deel van de invoer veranderd is. SHA-256 bereikt dit met 64 rondes die zijn acht woorden van 32 bits roteren, optellen en combineren, zodat binnen een paar rondes elk invoerbit elk woord heeft beïnvloed. Een eenvoudige som van de bytes verandert daarentegen met precies het bedrag waarmee de invoer veranderde, en verraadt dus alles.

Een kijkje in SHA-256

SHA-256 vult het bericht eerst aan: het voegt een 1-bit, nullen en de lengte van het bericht toe, tot het totaal een veelvoud van 512 bits is. Daarna verwerkt het het bericht per 512 bits. Elk blok wordt uitgerekt tot 64 woorden, die worden gemengd in een toestand van acht woorden van 32 bits, die begint met vaste waarden uit de vierkantswortels van de eerste acht priemgetallen. De toestand na het laatste blok is de hashwaarde. Deze geketende opbouw, genoemd naar Ralph Merkle en Ivan Damgård, delen MD5, SHA-1 en SHA-512; het nieuwere SHA-3, gestandaardiseerd in 2015, gebruikt een andere constructie, de spons (sponge).

Ralph Merkle op de Singularity Summit in 2007. De geketende opbouw die SHA-256 gebruikt, is naar hem en Ivan Damgård genoemd.
Ralph Merkle op de Singularity Summit in 2007. De geketende opbouw die SHA-256 gebruikt, is naar hem en Ivan Damgård genoemd.

De verjaardagsaanval

In een groep van 23 mensen is de kans dat twee op dezelfde dag jarig zijn iets meer dan een half, hoewel het jaar 365 dagen heeft, want wat telt is het aantal paren, en dat groeit met het kwadraat van de groepsgrootte. Botsingen in een hash volgen dezelfde regel. Bij 2ᵏ mogelijke hashwaarden is een botsing te verwachten na ongeveer √(π/2 · 2ᵏ) willekeurige invoeren. Voor 32 bits zijn dat ongeveer 82.000 invoeren, in een oogwenk gedaan; voor 128 bits is het ongeveer 2⁶⁴, wat binnen bereik ligt van grote rekenprojecten. Daarom waren de 128 bits van MD5 nooit ruim, en daarom verdubbelt SHA-256 de lengte om een beveiliging van 128 bits te bieden.

MD5 en SHA-1: gebroken

Ron Rivest ontwierp MD5 in 1991, en de NSA ontwierp SHA-1, gepubliceerd in 1995. In 2004 lieten Xiaoyun Wang en haar collega’s zien hoe je snel MD5-botsingen maakt, en in 2008 gebruikten onderzoekers die om een certificaat te vervalsen dat webbrowsers vertrouwden. De spionagesoftware Flame uit 2012 gebruikte een MD5-botsing om zich voor te doen als een update van Microsoft. SHA-1 viel in 2017, toen Google en CWI Amsterdam twee verschillende PDF-bestanden met dezelfde SHA-1-hashwaarde publiceerden, na ongeveer 2⁶³ berekeningen. Beide zijn nog prima om toevallige fouten op te sporen, maar niet voor iets waar een aanvaller het op gemunt kan hebben.

Waar hashes worden gebruikt

Digitale handtekeningen ondertekenen de hash van een document in plaats van het document zelf. Git benoemt elk bestand en elke commit naar zijn hash, en Bitcoin-miners zoeken naar blokheaders waarvan de dubbele SHA-256-hash begint met een lange reeks nullen. Websites horen nooit wachtwoorden op te slaan, alleen een hash ervan; maar omdat mensen korte wachtwoorden kiezen, moet die hash traag en gezouten zijn, met methoden als bcrypt, scrypt of Argon2, zodat raden duur wordt. Controlesommen zoals CRC-32, gebruikt in ZIP-bestanden, PNG-afbeeldingen en Ethernet, zijn ook hashes, gemaakt om ruis op te vangen in plaats van aanvallers.

Probeer het zelf

Open Hashfuncties uitproberen om je eigen tekst te hashen met SHA-256, SHA-512, SHA-1, MD5, CRC-32 en een eenvoudige som van bytes. Wijzig één teken en tel de omgeklapte bits, voer de lawinetest uit over duizend wijzigingen van één bit om de klokkromme rond de helft van de hashwaarde te zien, en vind echte botsingen op de eerste 8 tot 32 bits van een hashwaarde om de verjaardagsaanval aan het werk te zien.

Veelgestelde vragen

Is hashen hetzelfde als versleutelen?

Nee. Versleuteling is bedoeld om ongedaan gemaakt te worden door wie de sleutel heeft; hashen heeft geen sleutel en kan door niemand ongedaan gemaakt worden. Versleuteling houdt een bericht geheim, terwijl een hash alleen een vingerafdruk geeft waarmee je een bericht kunt controleren dat je al hebt.

Hoe lang zou het duren om een SHA-256-botsing te vinden?

Met de verjaardagsaanval ongeveer 2¹²⁸ hashberekeningen, een getal van 39 cijfers. Zelfs als elke computer op aarde niets anders deed, zou het onvoorstelbaar veel langer duren dan de leeftijd van het heelal. Er is geen kortere weg bekend.

Waarom verschillen twee hashes van dezelfde tekst nooit?

Een hashfunctie is deterministisch: ze heeft geen toeval en geen sleutel, dus dezelfde bytes geven altijd dezelfde hashwaarde. Kleine verschillen die je niet ziet, zoals een spatie aan het eind, een ander regeleinde of een andere Unicode-vorm van een letter met accent, geven wel een andere hashwaarde.

Wat is een salt?

Een willekeurige waarde die naast een wachtwoordhash wordt opgeslagen en erin wordt gemengd. Twee gebruikers met hetzelfde wachtwoord krijgen dan verschillende hashes, en een aanvaller kan niet één vooraf berekende tabel met veelgebruikte wachtwoorden voor alle accounts gebruiken.

Klaar om het te proberen?

Open PictorX in je browser - geen installatie, geen creditcard nodig om te starten.

Open Hashfuncties uitproberen