Hashfunctie

Een hashfunctie of hashalgoritme is in de informatica een algoritme dat invoer uit een breed domein van waarden omzet in een meestal kleiner bereik, meestal een deelverzameling van de gehele getallen. De uitvoer van een hashalgoritme wordt de hash, hashcode of digest van de invoer genoemd. Hashfuncties zijn een vorm van pseudonimiseren, dus van encryptie. Het woord hash komt uit het Engels en betekent hier hakken.

De hashfunctie heeft van de twee schilderijen van Leonardo da Vinci een hashcode gemaakt, waarvoor een veel kleiner bestand nodig is dan voor de twee schilderijen zelf. De beide schilderijen kunnen desondanks toch nog van elkaar worden onderscheiden.

Hashfuncties worden gebruikt in hashtabellen, cryptografie en gegevensverwerking. Bij een domein dat groter is dan het bereik is de functie uiteraard niet injectief, maar een goede hashfunctie is er een die in de praktijk weinig collisions veroorzaakt, dit wil zeggen dat er weinig tweetallen verschillende invoerwaarden bestaan die dezelfde uitvoer geven. Afhankelijk van de toepassing van de hashfunctie moet deze ook zo zijn dat zo'n tweetal zelfs zeer moeilijk te vinden is als men er naar zou zoeken.

Toepassingen

Hashtabellen

Zie Hashtabel voor het hoofdartikel over dit onderwerp.

Met hashtabellen kunnen associatieve arrays en verzamelingen worden geïmplementeerd. In een hashtabel wordt van de sleutelwaarde een hash in een bepaald bereik berekend, die wordt gebruikt als het volgnummer in een lijst.

Cryptografie

Een cryptografisch veilige hashfunctie heeft de eigenschappen dat het niet mogelijk is om een blok gegevens te vinden dat een gegeven hashcode oplevert, of om twee verschillende blokken gegevens te vinden die dezelfde hashcode opleveren, mits de gegevensblokken niet te klein zijn. Hierdoor heeft een hashcode de eigenschappen van een digitale vingerafdruk.

De hash lijkt willekeurig. De kans dat willekeurige oorspronkelijke gegevens een bepaalde hash opleveren is ongeveer het omgekeerde van het aantal mogelijke uitkomsten. Voorwaarde is dus dat de hashcodes niet te klein zijn, want het proberen van evenveel blokken gegevens als het aantal mogelijke hashcodes levert gemiddeld één keer de gegeven hashcode op. Ze zouden in het geval van korte hashcodes allemaal kunnen worden geprobeerd. De hash is normaal korter dan de oorspronkelijke gegevens, maar wanneer de hashcodes niet te klein zijn wordt de genoemde kans daardoor ook al zeer klein.

Een toepassing van cryptografische hashfuncties is het opslaan van wachtwoorden. Van deze wachtwoorden wordt vaak alleen een one way hash opgeslagen, dat wil zeggen dat uit de uitvoer van de hashfunctie, dus uit de hash het wachtwoord niet is af te leiden. Dat is ook niet nodig, aangezien het voldoende is te controleren of de hash van het door de gebruiker opgegeven wachtwoord overeenkomt met de opgeslagen hash. Het voordeel is dat als het bestand met hashes door een onbevoegde gelezen wordt, deze er weinig aan heeft.

scrypt is een voorbeeld van een hashalgoritme voor wachtwoorden. Hashalgoritmen zijn er in het algemeen alleen voor ontworpen om zo snel mogelijk te kunnen worden uitgevoerd, maar bij het hashen van wachtwoorden is dat onwenselijk, omdat het daardoor mogelijk wordt dat iemand die de hashcodes van de wachtwoorden in bezit heeft gekregen achterhaalt welke hashcode van welk wachtwoord is afgeleid.

De lengte en complexiteit van wachtwoorden die mensen in de praktijk gebruiken is beperkt, terwijl computers steeds sneller worden. Daardoor wordt het voor iemand die probeert hashcodes voor wachtwoorden te kraken steeds gemakkelijker om een computer allerlei mogelijkheden te laten uitproberen. Bij hashalgoritmen voor wachtwoorden kan men dit tegengaan doordat voor deze algoritmen in te stellen is hoeveel rekentijd ze moeten kosten. De algoritmen worden dan zo ingesteld dat het uitrekenen ervan bijvoorbeeld één milliseconde kost, terwijl het berekenen van een hashcode met een gewoon hashalgoritme minder dan een microseconde kan kosten. Bij het controleren van een wachtwoord is het meestal geen probleem als dit een milliseconde in plaats van een microseconde kost, terwijl iemand die wil proberen de hashcodes te kraken meer dan duizend keer zo veel rekenwerk moet doen, dus meer dan duizend keer langer bezig is.

Voorbeelden van cryptografische hashalgoritmen zijn MD5 en de SHA-familie van hashfuncties, maar MD5 wordt niet meer als veilig beschouwd. Voor SHA-1 is een theoretische aanval bekend, dus deze wordt ook afgeraden.

Dataverwerking

Aangezien de hashcode vaak veel kleiner is dan het oorspronkelijke blok gegevens is het op deze manier mogelijk om bij te houden of een bepaald document al eerder is gezien, zonder dat het hele document hoeft te worden opgeslagen. Iemand kan de hashcode van een document publiceren om er later, als het document is gepubliceerd, mee te kunnen bewijzen dat het document al eerder bestond en dat hij er toen of al over hebben beschikt of er toen al medewerking van iemand over te hebben gekregen. Dat, omdat het achteraf onmogelijk is een document te maken dat een gegeven hashcode oplevert.

Als de hash van een bestand, bijvoorbeeld een tekst of een afbeelding, bekend is kan een kopie op correctheid worden gecontroleerd door de hash daarvan te vergelijken met de bekende hash. Dit kan worden gedaan om vergissingen, storingen of vervalsingen mee te signaleren.