In mijn vrije tijd heb ik mij bezig gehouden met verschillende hashmethodes te bestuderen. Dit artikeltje is het gevolg van deze kleine 'studie'. Niet alle hashmethodes zijn besproken en ik ben misschien enkele puntjes vergeten. Let aub niet op de gebruikte html want het is in word geschreven en gewoon omgezet naar een 'webpagina'. Veel leesplezier!

Hoofdstuk 1: Hashen inleiding

Hashing (het hashen) is een van de meest complexe codeermethodes. Het wordt meestal gebruikt om wachtwoorden op te slaan. Een bekend voorbeeld hiervan is ‘hotmail’. Ze slaan niet de ‘echte’ wachtwoorden van de gebruikers op maar een gehashte versie. Stel dat ‘hotmail’ gebruik zou maken van het md5-algoritme en we hebben een account aangemaakt met de volgende gegevens:

Dan zal ‘hotmail’ dit wegschrijven in een record in de gegevensbank (vanaf nu kortweg ‘database’). Maar vooraleer ‘wachtwoord’ wordt weggeschreven zal het ‘gehasht’ worden. Als we aannemen dat ‘hotmail’ gebruik maakt van het md5 algoritme zal dit er zo uitzien.

De gehashte versie wordt weggeschreven naar de tabel en niet het originele wachtwoord ‘test’. Dit is ook de reden waarom ‘hotmail’ het originele wachtwoord nooit kan ‘teruggeven’ als je het kwijt bent. En dat je met je alternatieve email adres (dat optioneel in te vullen is) alleen een nieuw wachtwoord kan aanvragen. Zelfs ‘hotmail’ weet jouw wachtwoord niet. Hoe kunnen ze nu controleren of je, bij het inloggen, het juiste wachtwoord ingeeft: door de ingevoerde waarde ook te hashen en deze te vergelijken met de waarde die in de tabel staat.

Hashing, samen met encrypten, worden gebruikt om gevoelige data te beveiligen. Het enige verschil is dat bij hashing de originele waarde niet meer kan achterhaald worden, wat bij encrypten (door middel van een sleutel) wel kan.

Het eenvoudigste en bekendste voorbeeld van encrypten is het binaire talstelsel. Hier wordt een originele waarde (in dit geval enkel een numerieke waarde) omgezet naar een andere waarde. Als we niet weten dat we met het binaire talstelsel te doen hebben dan is het onmogelijk om de waarde te achterhalen. Nu is dit bij het binaire talstelsel eenvoudig te vinden en de sleutel is rap gevonden (namelijk de binaire waarde converteren naar de decimale waarde).

Vooraleer ik aan de complexere methodes begin bespreek ik een heel eenvoudig voorbeeldje. Het is een hashmethode omdat de oorspronkelijke boodschap onmogelijk kan worden achterhaald in haar volledige vorm. Het spijtige is wel dat de boodschap grotendeels kan worden achterhaald.

Stel we hebben een tekst ‘Dit is een tekst’ en we willen ze permuteren.

Eerst worden alle spaties uit de tekst gehaald: ‘Ditiseentekst’. We nemen als sleutelwaarde 3 hierbij lijkt het sterk op een encryptiemethode maar de spaties worden weggehaald dus ‘Dit is een tekst’ heeft dezelfde waarde als ‘Dit ise en tek st’ (wat iets anders zou kunnen betekenen).

Vervolgens verdelen we de tekst volgens de sleutelwaarde:

Dit
ise
ent
eks
tXX

De twee x’en worden toegevoegd omdat het anders geen matrix vormt (wat de bedoeling is van permutaties). Nu gaan we de tekst van boven naar beneden lezen: ‘DieetisnkXtetsX’. Het is geen veilige manier en het is mogelijk de originele boodschap te achterhalen, hoewel dat al wat moeilijker is dan bij het binaire talstelsel.

Wat is md5?

Nu we eerst een eenvoudig voorbeeld hebben gehad is het tijd voor het echte werk. Het md5-algoritme, ontworpen door Ronald Rivest in 1991, moest het eerdere md4 vervangen. Md5 staat voor ‘Message Digest Algorithm 5’. Toen in 1996 een fout werd gevonden in het md5 algoritme werd het aangeraden andere hashmethodes te gebruiken zoals de SHA-familie. Toch was dit geen ernstige fout dus werd het nog altijd gebruikt voor veiligheidstoepassingen. In 2004 echter werden ernstige fouten gevonden en eind 2005 werd de broncode van een programma getoond waarbij het mogelijk was een ‘collision’ te vinden binnen het uur met een doodgewone processor (dus geen super computer).

Een collision is een tweede of derde hash die gelijk is aan de eerste. Het kan niet anders dan dat er een hash die dezelfde waarde heeft als de hash van ‘test’. Dat komt doordat md5 de waarde omzet naar een ofwel groter ofwel kleiner formaat met altijd dezelfde lengte: 32 tekens. Dus als je een tekst invoert van duizend tekens dan zal dat omgezet worden naar 32 tekens. Dus kan het niet anders dat meerdere waardes gelijk zijn aan een hash. Dat werd heel gemakkelijk gemaakt met het eerder vernoemde programma, waardoor md5 op gebied van veiligheid gedeeltelijk heeft afgedaan.

Hoe ziet het eruit?

Een van de grote voordelen van md5 is dat als de invoer slechts 1 klein tekentje verschilt de volledige uitvoer er helemaal anders uit ziet. Zo is ‘aaaaaa’ gelijk aan ‘0b4e7a0e5fe84ad35fb5f95b9ceeac79’ en ‘aaaaab’ gelijk aan ‘9dcf6acc37500e699f572645df6e87fc’ een heel duidelijk verschil.

Md5 wordt weergegeven in hexadecimaal formaat. De md5-hash van een NULL-waarde (geen ingevoerde waarde) ziet er zo uit.

Bovenstaande eigenschap zou een eigenschap moeten zijn van hashing. Spijtig genoeg is dat bij sommige hashalgoritmes niet zo. De beoordeling van de veiligheid van een hash is dus ook hier afhankelijk van.

Wat is SHA?

Hierboven heb ik vermeld dat, omdat het md5 algoritme op gebied van veiligheid heeft afgedaan, het beter is een van de SHA algoritmes te gebruiken.

SHA staat voor Secure Hash Algorithm en zou dus (zoals de naam zegt) veiliger moeten zijn dan md5.

SHA is een verzameling van gerelateerde hash methodes ontworpen door de Amerikaanse ‘National Security Agency’ (NSA). Het eerste lid werd ontworpen in 1991 en heette toen SHA. Toen er een volgende versie kwam (genaamd SHA-1) werd de eerste versie SHA-0 getiteld. Na SHA-1 zijn er nog vier varianten ontworpen die gedeeltelijk afweken van het origineel: SHA-224, SHA-256, SHA-384 en SHA-512. Deze horen bij de groep SHA-2. Het tweede deel van hun titel (224, 256, 384 en 512) representeren het aantal bits waaruit het bestaat: 28 tekens, 32 tekens (zoals md5), 48 tekens (zoals SHA-1) en 64 tekens.

De eerste versies

Toen SHA-0 (toen nog SHA genoemd) werd gepresenteerd door de NSA werden er enkele zwakheden ontdekt door de NSA. Daardoor werd SHA-0 twee jaar later teruggetrokken en vervangen door SHA-1. Er werd geen verdere informatie gegeven over de zwakheden in SHA-0. Sindsdien zijn er al enkele zwakheden in SHA-0 en SHA-1 ontdekt.

De aanvallen op SHA-0

Sinds het terugtrekken van SHA-0 door de NSA zijn er vele aanvallen gepleegd om te proberen de reden te achterhalen. Er werd gezocht naar collisions (botsingen) en door meer dan 251 berekeningen en 80.000 processoruren op een supercomputer werd er dan eindelijk een botsing gevonden. Dat bewijst de veiligheid van SHA-0 als je ziet wat voor middelen er voor nodig zijn. Als we dan kijken naar het feit dat er verbeterde versies (SHA-1 en SHA-2) bestaan wordt de veiligheid slechts benadrukt.

Aanvallen op SHA-1

Begin 2005 werd er dan eindelijk een botsing gevonden bij SHA-1. Om dit te bereiken waren 280 berekeningen nodig. Om een berekening met een complexiteit van 269 uit te voeren zijn er honderdduizenden computers nodig. Het hangt er dus vanaf hoeveel geld en tijd de aanvaller wil besteden in het zoeken naar botsingen.

In februari 2005 werd er een botsing gevonden door een berekening met complexiteit 269. Zoals hierboven vermeld is zijn voor zo een berekening honderdduizenden computers nodig. Enkele overheidsinstanties en bedrijven hebben voor een botsing te achterhalen misschien het geld voor over (om dan slechts botsingen te vinden) maar vooralsnog wordt SHA gezien als veilig.

Daarom wordt SHA-1 en SHA-2 gebruikt door federale toepassingen in de Verenigde Staten van Amerika.
De bekende X-Box-spelcomputer maakt ook gebruik van SHA-1.

Bij cryptografie is het de bedoeling een boodschap te versleutelen zodat de boodschap later kan gereconstrueerd worden. Het reconstrueren van de boodschap gebeurt via een sleutel.

Er zijn twee situaties mogelijk - de sleutel die wordt gebruikt om de boodschap te versleutelen wordt gebruikt om deze te reconstrueren - er wordt een andere sleutel gebruikt om de boodschap te achterhalen

In het eerste geval (dezelfde sleutel) spreekt men van ‘symmetrische cryptografie’, in het tweede geval van ‘asymmetrische cryptografie’.

Een bekend voorbeeld van symmetrische cryptografie is DES (Data Encryption Standard). DES is in 1977 tot standaard verheven maar in 1995 werd er bewezen dat DES niet meer betrouwbaar is. Om te veiligheid te vergroten heeft men een werkwijze bedacht waarbij drie DES algoritmes achter elkaar worden geschakeld. Dit noemt men 3DES (uitgesproken “triple DES”).

Asymmetrische cryptografie is trager dan symmetrische cryptografie en vergt ook meer rekenkracht maar is wel betrouwbaarder. Het voordeel van Asymmetrische cryptografie ligt hem vooral in het feit dat men kan kiezen ‘wie de boodschap versleutelt’ (met sleutel A) en ‘wie de boodschap mag lezen’ (met sleutel B).

Ik zal even een duidelijk voorbeeld schetsen. Stel ik wil dat sommige mensen mij boodschappen willen sturen maar dat deze boodschap niet door iemand anders mag onderschept worden. Dan geef ik aan iedereen die maar wil de ‘publieke sleutel’. Iedereen kan dus een boodschap versleutelen. Nadat deze versleutelt is wordt aan mij getoond. Alleen ik kan de boodschap lezen want ik bezit de ‘privé sleutel’. Bij ‘symmetrische cryptografie’ kan iedereen die een sleutel bezit de boodschap zowel achterhalen als versleutelen. Bij asymmetrische cryptografie kan iedereen die de publieke sleutel bezit de boodschap versleutelen maar alleen de eigenaar van de privé sleutel kan de boodschap achterhalen.

Een bekend voorbeeld van asymmetrische cryptografie is RSA (ontworpen door Ron Rivest, Adi Shamir en Len Adleman).

Hoofdstuk 2: Het zelf ontwikkelen

In dit hoofdstuk ontwikkelen we zelf een hash methode. We baseren ons op een fictief talstelsel (speciaal ontworpen voor dit doel) met als grondtal 14. Het talstelsel bestaat uit 14 niets zeggende symbolen:

Om een voorbeeld te schetsen heb ik het getal 255 omgezet naar dit talstelsel.

Het talstelsel heet FT genoemd naar het grondtal (FourTeen).

ASCII

De eerste stap is het talstelsel kiezen. Dat is al gebeurd, daarom gaan we verder met stap 2. Dat houdt in dat we de ingevoerde waarde coderen naar een door de computer bewerkbare tegenwaarde. We maken gebruik van de ASCII-tabel. Als we bv. ‘hallo’ willen hashen gaan we dat omzetten naar 10497108108111. Nu is er al aan het principe van hashing voldaan. De boodschap kan onmogelijk in haar oorspronkelijke vorm worden teruggezet. We zouden een sleutel kunnen maken bijvoorbeeld 3233 waarbij elk getal het aantal tekens van de ASCII-waarde voorstelt. Aangezien we niet met sleutels werken moeten we ons hier geen zorgen over maken.

FT

We zetten de waarde (10497108108111) om naar de FT waarde.

Nu wordt het dus duidelijk interessant omdat deze bekomen waarde al heel wat moeilijker te achterhalen is. We zouden hier nog altijd een encryptiemethode van kunnen maken en met dezelfde sleutel 3233 werken. Een eigenschap van hashing is dat de data een niet variabele lengte heeft. We nemen als lengte 14, om maar een patroon te volgen.

Omzetten naar een string van 14 bytes

Vervolgens moeten de data dus omzetten naar een string van 14 bytes. Dat gaan we heel eenvoudig oplossen door de waarde zich te laten herhalen totdat er 14 tekens in voorkomen (of aftrekken tot het nog maar uit 14 tekens bestaat). Nu is er zeker sprake van hashing en kan de waarde niet meer omgekeerd worden. Het is wel gemakkelijk enkele mogelijkheden af te gaan en de meest logische te nemen.

Berekeningen uitvoeren

Om het nog ingewikkelder te maken de waarde te achterhalen verschuiven we de data. Hierbij baseren we ons op het idee van permutaties. We nemen als key 1.75. Dat klinkt misschien heel raar maar het past in het schema. 1.75 bytes is gelijk aan 14 bits. En met een key van 1.75 worden er al automatisch eerst bewerkingen met de originele waarde genomen. 75% van het getal hoort bij het 1e gedeelte, 25% procent bij het tweede. Dit geeft als resultaat:

Stap 1: We onthouden van elke waarde hoeveel procent bij het ene gedeelte hoort en hoeveel bij het andere.

Dan krijgen we volgende tabel:

We bereken dus de x-procent waarde van het teken.

En dan krijgen we volgende tekenreeks.

Stap 2: De permutatie uitvoeren.

De uiteindelijke hash

Met bovenstaand, zelf gevonden, algoritme hebben we het mogelijk gemaakt om de string ‘hallo’ om te zetten naar ‘//+¨,;;+=;+-/;+¨’. Een hash die onmogelijk kan worden achterhaald.

Bovenstaand voorbeeld is een zeer eenvoudig voorbeeld omdat er slechts gemakkelijke berekeningen worden uitgevoerd.

Het maken van een hashalgoritme blijft moeilijk. Toch zijn we er in geslaagd met enkele eenvoudige bewerkingen een waardige hash te genereren. Mede dankzij het ingewikkelde talstelsel dat de uitkomst zo moeilijk te achterhalen blijkt. Maar eens dat doorzien is wordt het terughalen van de originele waarde een stuk eenvoudiger. Dankzij het moeten omzetten naar een bepaalde lengte wordt dat dan weer moeilijker. Spijtig genoeg heeft dat het nadeel dat twee enorm lange zinnen met slechts op het einde 1 verschilpuntje dezelfde hash hebben. We hebben dus al snel een collision binnen de methode gevonden.