Probleem van MD5 is dat het is aangetoond dat collisions mogelijk zijn.
[...]
Met sterkere hashes heb je de kwetsbaarheid van collisions (nog) niet.
Élke hash heeft collisions; dat is inherent aan een hash functie

Hoe
makkelijk je zo'n collision kunt "forceren" is iets anders...
Voorbeeldje?
De (über-versimpelde)
RobIIIHash functie: Tel alle
ASCII-codes van de letters bij elkaar op en neem van 't totaal de
modulo 16. Dat geeft voor het wachtwoord "Secret01" de hash "7"; op basis van enkel 't getal 7 weet jij niet wat 't wachtwoord was (en zul je 't ook nooit met zekerheid weten; je kunt (in dit simpele geval) wél
makkelijk allerlei collisions brute-forcen die
ook 7 opleveren en dus "een geldig wachtwoord" zijn). Op basis van een hash kun je, bij een
fatsoenlijk algoritme als MD5, SHA1, SHA2 RipeMD160 en whatnot, niet
makkelijk zeggen wat 't originele wachtwoord was. Er zijn namelijk
2128 (of meer, afhankelijk van 't soort hash) mogelijke uitkomsten. Echter, omdat het aantal bits vast staat
moet je voor een
oneindig aantal mogelijke inputs, uiteindelijk, dus uitkomsten krijgen die je eerder hebt gezien (een zgn. collision). Hoe moeilijk je zo'n collision kunt 'forceren' bepaalt hoe sterk een hash is; elke vulnerability die je vindt die een enkel bit van de mogelijke uitkomsten afsnoept halveert 't aantal pogingen die je moet doen om zo'n collision te forceren. Voor MD5 zijn er dat
nogal wat en daarbij is een MD5 gewoon verdomd snel te berekenen en kun je met paralleliseren op GPU's e.d. daar verdomd veel van bruteforcen in een kort tijdsbestek.
Terug naar het voorbeeld: je hoeft geen genie te zijn om te zien dat "Sfcrdt01" een collision zal opleveren op de hash van "Secret01" (immers; ik heb bij de eerste e een letter opgeteld en bij de tweede e een letter teruggegaan in 't alfabet == zelfde hash. Bij een fatsoenlijk hash algoritme ligt dat vele malen complexer, maar collisions zul je
altijd hebben bij een hash; simpelweg omdat je een oneindig aantal mogelijke inputs hebt die
allemaal een x-bit (waar x vaak 1 van 128, 160, 224, 256, 384 of 512 is) uitkomst moeten opleveren en
dus collisions, daar is
geen ontkomen aan. Nu is 't voorbeeld "maar" een 4-bit hash (immers: 16 mogelijke uitkomsten, 0..15) en is het algoritme amper een hash te noemen omdat het wisselen van 2 letters of, zoals in 't voorbeeld, ergens +1 en elders -1 dezelfde hash opleveren, waar je dat bij een fatsoenlijk algoritme niet hebt, maar het gaat om 't idee.
Die 'performance' van hashes is overigens met opzet geoptimaliseerd voor 'snelheid' (of soms zelfs geoptimaliseerd zodat 't makkelijk in weinig transistors in een chip is te implementeren): de hashes zijn helemaal niet
bedoeld voor 't opslaan van wachtwoorden maar bijv. voor het verifiëren van data; als je een bestand hebt van tig GB en er wijzigt 1 bit zal een (fatsoenlijk) hash-algoritme meteen een
compleet verschillende hash opleveren maar liefst wel in zo kort mogelijke tijd. Of voor het verifiëren van echtheid van een bericht en dat er niet (al-dan-niet "onderweg") mee geknoeid is. Voor wachtwoorden zijn die algoritmes dus eigenlijk niet (zo) geschikt omdat je, met genoeg "power", die dingen
relatief makkelijk* kunt brute-forcen of zelfs simpelweg kan opzoeken in een
rainbow table. En dat is dan weer de reden van 't bestaan van zaken als
PBKDF2,
bcrypt,
scrypt. Die maken 't 'brute-forcers' gewoon vele malen moeilijker door ettelijke honderden, duizenden of meer "rounds" van een hashalgoritme los te laten op je wachtwoord (en elke round wat extra te 'husselen' met de 'tussentijdse resultaten'). Daardoor wordt 't brute-forcen van een enkele hash simpelweg 'verlengd' (in tijd die nodig is) met het aantal rounds; 100.000 rounds => 100.000 x de 'power' nodig om een hash te brute-forcen. Daarbij maken dergelijke algoritmes 't vaak lastig (liefst zelfs onmogelijk) om zaken te paralleliseren of om er zelfs dedicated hardware (
ASICs) voor te bouwen waarbij dat voor een 'gewone hash' juist vaak wel een pluspunt is (mits je 't niet gebruikt voor wachtwoorden dus).
* Afhankelijk van het algoritme, het aantal bits, aantal (al-dan-niet known) vulnerabilities etc. kan dat variëren van uren tot ver voorbij het einde van het universum en alles daartussenin met de huidige hardware en kennis; dat kan morgen of over 10 jaar een héél ander verhaal zijn (nieuwe vulnerabilities, efficiëntere/snellere hardware etc.). Bij key-stretching kun je dat probleem makkelijk 'mitigaten' door elke paar jaar (weken, dagen) gewoon het aantal rounds (flink) op te hogen en dus de rounds 'af te stemmen' op 'de huidige stand van techniek'.
[Reactie gewijzigd door RobIII op 24 juli 2024 20:35]