Vooraf, bij wachtwoordhashes die gebruikmaken van MD5 en beter, spelen collisions, voor zover ik weet, in de praktijk geen enkele rol. Hopelijk heb ik jou niet op een dwaalspoor gezet! Ik probeer e.e.a. toe te lichten, voor zover mijn kennis hierover reikt.
Door Dick99999: - De vraag is dan als dit de geldige maxima zijn, kunnen zich daarbij in de praktijk al collisions voordoen? Hierdoor zou het aantal mogelijke wachtwoorden dat voor een brute force aanval moet worden afgegaan, kleiner worden.
- Moderne hash algoritmen schijnen bij deze aantallen collision vrij te zijn.
De kans neemt af, maar collision-vrij kan niet. Immers, de defintie van een hash-functie is dat deze, ongeacht de input en haar lengte, een getal van een vast aantal bits oplevert. Aangezien er een oneindig aantal verschillende inputs mogelijk is en een beperkt aantal outputs,
moeten er collisions bestaan.
Bij oudere methode als MD5, treedt vermoedelijk een collision op na de helft van het aantal mogelijke hashes, dus na 2^27= 1E38 hashes.
Dat is zonder rekening te houden met de "Birthday Paradox". D.w.z. de kans dat in een groep mensen (bijv. een schoolklas) twee personen op dezelfde dag jarig zijn (collision); volgens
http://en.wikipedia.org/wiki/Birthday_attack is de kans 70% dat in een groep van 30 personen er twee op dezelfde dag jarig zijn. Die kans is veel groter dan dat iemand in een groep mensen toevallig op dezelfde dag jarig is als jij.
Door die Birthday Paradox zullen collisions statistisch gezien veel eerder optreden dan bij de helft van 2^128 hashes (een aanvaller heeft hier in de praktijk echter niets aan).
In
http://stackoverflow.com/questions/14973197/what-is-the-probability-of-md5-collision-if-i-pass-in-232-sets-of-string vraagt iemand hoe groot de kans is op collisions bij ruim 4 miljard met MD5 gehaste strings. In het antwoord (dat ik niet heb gecontroleerd) valt te lezen dat, hoewel de kans met 2.7E-20 nog steeds extreem klein genoemd kan worden, deze wel 9 ordes groter is dan de vragensteller vermoedde.
Daarnaast zijn wetenschappers vaak op zoek naar een methode om de collision-resistance van cryptografische hash functies te vinden. Onderin het grijze boxje rechtsbovenaan
https://en.wikipedia.org/wiki/MD5 staat dat het mogelijk is om met een gewone computer binnen 1 seconde twee inputs te genereren die dezelfde MD5 hash opleveren. Maar, voor zover ik overzie, ook hier heeft een wachtwoordaanvaller niets aan.
Ik ga nu wat theoretiseren, correct me if I'm wrong. Collisions in wachtwoordhashes vormen een risico als een aanvaller een redelijke kans heeft om in te loggen op jouw account met een
ander wachtwoord dat toevallig dezelfde hash oplevert. Aangezien die aanvaller op
jouw account probeert in te loggen geldt de Birthday Paradox niet.
Stel dat een webapplicatie wachtwoorden afkapt door slechts de eerste 128 bits van wachtwoorden
plaintext op te slaan. Dan zal een brute-force aanvaller statistisch gezien na de helft van de mogelijkheden het wachtwoord hebben geraden. Indien een
MD5 hash van een wachtwoord is opgeslagen, is de succeskans groter omdat ook andere wachtwoorden tot dezelfde hash kunnen leiden. Hoeveel groter weet ik niet, maar hoewel MD5 zwaar gebroken is op het gebied van collision resistance, verwacht ik dat dit effect verwaarloosbaar zal zijn (maar dat kan ik niet onderbouwen). Duidelijk is wel dat hoe zwakker de hash, hoe groter die kans is.
Extreem voorbeeld ter illustratie: stel als "hash" wordt de pariteit van het wachtwoord opgeslagen (odd of even). Dan heeft een aanvaller 50% kans om binnen te komen met het eerste willekeurige wachtwoord. Als hij het wachtwoordalgoritme kent komt hij bij de tweede poging gegarandeerd binnen.
Wat ik met het CRC16 voorbeeld in mijn vorige bijdrage probeerde uit te leggen is dat het bij zeer korte hashes extreem eenvoudig wordt om 100% gevulde rainbow tables te maken.
1E38 levert voor snelle hashes op prof. apparatuur een gemiddelde kraaktijd van eeuwen op. Dat strookt dan weer met mijn opmerking dat als je een sterk wachtwoord hebt, je geen zorgen hoeft te maken, ook al gebruikt een site een zwakke hash methode voor opslag van wachtwoord hashes..
Dat hangt van de definitie van "zwakke hash" af. Ik heb er geen gegevens over maar vermoed dat de meeste webapplicaties, na eerder passwords plaintext te hebben opgeslagen, direct zijn overgestapt op MD5. Aan de andere kant sluit ik niet uit dat ontwikkelaars zelf "hash functies" hebben bedacht die aanzienlijk zwakker zijn dan MD5 (zie ook hieronder).
Wel een interessant gezichtspunt als dit allemaal waar is. Ik zal mijn generatie en analyse tool SimThrow mogelijk aanpassen na wat meer leeswerk, of heb jij misschien referenties over aantallen collisions bij oudere methoden?
Het is de vraag waar je je tegen probeert te wapenen; ik neem aan de diefstal van een database met "gehashte" wachtwoorden. In bijv. password-protected Powerpoint files wordt een CRC32 hash van het wachtwoord opgeslagen (bron:
http://msdn.microsoft.com/en-us/library/ff385916%28v=office.12%29.aspx); een 100% gevulde rainbow table daarvoor genereren is niet moeilijk. In de 2e bijdrage van
http://forums.devnetwork.net/viewtopic.php?f=1&t=94511&start=15 suggereert ook iemand dat hij ook CRC32 gebruikt.
Zelf heb ik de Excel password cracker uit
http://www.theofficeexperts.com/VBASamples/Excel02.htm gebruikt toen ik een protected sheet moest bewerken en ik de auteur niet kon bereiken. Ik kwam er zo in met een vreemd ogend wachtwoord. Later kreeg ik het oorspronkelijk wachtwoord van de auteur, dat leek er van geen kanten op. Een collision dus.
In
http://www.insidepro.com/hashes.php?lang=eng zijn verschillende (ook zwakke) password hash-algoritmes te zien, ik sluit niet uit dat deze hier en daar nog worden toegepast.
In
http://en.wikipedia.org/wiki/Comparison_of_cryptographic_hash_functions#Cryptanalysis zie je de collision resistance van cryptografische hashes met een digest-size van 128 bits en groter. Gegevens van zwakkere hashes heb ik niet.
Ik ken geen methode om als gebruiker vast te stellen welke hashmethode, al dan niet met salt, een website gebruikt. Ik vrees dan ook dat je alleen maar kunt hopen dat een fatsoenlijk algoritme gebruikt wordt, maar veel belangrijker, dat de website zo beveiiligd is dat derden geen toegang hebben tot de gegevens (waaronder al dan niet gehashte en gesalte wachtwoorden).