MD5 hashing

[Verwijderd]

ik snap iets niet.

MD5 hashes worden in vele toepassingen als one-way encryptie gebruikt. Bijvoorbeeld in serv-u word een passwd in de ini gesaved als MD5, en word bij het inloggen op de server het gegeven passwd opnieuw gehashed en de hash vergeleken met de hash in de ini.
Maar hoe kan het nu dat adv de hash niet een werkend password kan worden teruggerekend?
Wiskundig gezien is het zover ik weet altijd mogelijk om welke bewerking dan ook terug te rekenen. Nu weet ik dat er bij het hashen van de data een hoop informatie verloren gaat (net zoals je met een checksum niet de oorspronkelijke data terug krijgt), maar dat hoeft toch ook niet? Het is toch niet noodzakelijk om het oorspronkelijke wachtwoord terug te krijgen, als de MD5 hash maar hetzelfde is; deze worden immers vergeleken.
Wat maakt het onmogelijk om, als je de md5 hash hebt, een stukje data te bedenken die deze hash heeft?

[GlowMouse]

Neem dit: 101011110101101001, stel je neemt de checksum en gaat daarvoor alle eentjes tellen, zijn er 11. 11 zou dan een checksum kunnen zijn. Als er één 0 of 1 verkeerd staat kun je direct zien dat hij niet klopt. Maar van 11 kun je niet meer terug naar de orignele reeks enen en nullen.

Zou leuk zijn als het wel zou kunnen. Dan zou je een complete CD-ROM over kunnen sturen dmv een MD5 hash.

[|sWORDs|]

http://www.google.nl/sear...ie-Hellman+encryption&lr=

en dan met name:

http://docsun.cites.uiuc...._9/SUNWdev/ONCDG/p65.html

[ Voor 45% gewijzigd door |sWORDs| op 18-12-2004 19:53 ]

[Daedalus]

Het maakt het niet onmogelijk. Er zijn programma's die van een gegeven MD5 hash de oorspronkelijk string terug kunnen vinden. Het probleem is echter dat er zo gigantisch veel mogelijkheden moeten worden bekeken, dat een MD5 hash niet binnen een redelijk tijd kan worden gekraakt. En dat is waar de meeste encryptie methoden op zijn gebasseerd: het zo moeilijk maken dat tegen de tijd dat de sleutel is gevonden, de data waardeloos is geworden.

Overigens krijg je uit een MD5 hash niet de oorspronkelijke data terug, maar een string die dezelfde MD5 hash opleverd. Dit heet dan een collision. Ik dacht dat pas geleden er programma was die twee strings kon vinden die zo'n collision opleverd.

[muba]

Ik heb ooit de volgende theorie bedacht (heel simpel, maar het heeft het voor mij wel geillustreerd).

Stel, je hebt de MUBA-hash ( ) 7. Dat kan uit verschillende elementen opgebouwd zijn:
6 + 1
5 + 2
4 + 3
3 + 4
2 + 5
6 + 1

Je zult, uit de MUBA-hash ( ) nooit kunnen achterhalen wat het oorspronkelijke nummer was.

[Verwijderd]

GlowMouse schreef op zaterdag 18 december 2004 @ 19:51:
Neem dit: 101011110101101001, stel je neemt de checksum en gaat daarvoor alle eentjes tellen, zijn er 11. 11 zou dan een checksum kunnen zijn. Als er één 0 of 1 verkeerd staat kun je direct zien dat hij niet klopt. Maar van 11 kun je niet meer terug naar de orignele reeks enen en nullen.

Zou leuk zijn als het wel zou kunnen. Dan zou je een complete CD-ROM over kunnen sturen dmv een MD5 hash.

ik heb toch in mijn openings post gezet dat ik dit wel begrijp. Ik wil ook helemaal niet de oorspronkelijke data terug, ik wil alleen een 'willekeurig' stukje data met dezelfde hash! Om jouw voorbeeld te nemen; stel dat een programma MD5 (nouja de variant die alles optelt dan) gebruikt om wachtwoorden te saven. en hij heeft gesaved dat de hash van het wachtwoord '11' is.
Dan zal het toch zowel 101011110101101001 als 000000011111111111 goedkeuren? Beide hebben '11' als hash! Je zal dus niet de oorspronkelijke data recoveren, maar dat hoeft ook niet, het enige wat je nodig hebt is een stukje data met dezelfde hash. En dat is toch wiskundig niet onmogelijk?

[ Voor 7% gewijzigd door Verwijderd op 18-12-2004 20:03 ]

[Bananenplant]

Dat is niet onmogelijk en heet brute force uitproberen .

Zie het zo, kun je een vijfdegraads vergelijking exact oplossen? Da's ook heel moeilijk.

[Verwijderd]

ucchan schreef op zaterdag 18 december 2004 @ 20:02:
Dat is niet onmogelijk en heet brute force uitproberen .

Zie het zo, kun je een vijfdegraads vergelijking exact oplossen? Da's ook heel moeilijk.

maar niet onmogelijk. bruteforce is geen optie, dit wil ik ook achterwege laten, ik wil alleen begrijpen hoe ze het onmogelijk maken om iets terug te rekenen.

[F_J_K]

Nee, is het niet. Bij een simpele hashing ben je dan ook inderdaad zo klaar. Bij een wat "vervelendere" hashing moet je brute force alle mogelijkheden af gaan om te zien of je teststring dezelfde hash opleverd. En dat kost tijd. En dat is wat je wilt: brute force is "alles" te kraken (al gaat het gruwelijk veel sneller als je de gehasde waarde lokaal hebt).

Maar dat staat vast toch ook wel uitgelegd op de meeste plaatsen waar de methode wordt uitgelegd?

Laten we trouwens geen kraakzooi posten, dat mag iedere scr1pt k1ddy zelf uitzoeken

Edit: ik ben traag.

Verwijderd schreef op zaterdag 18 december 2004 @ 20:04:
maar niet onmogelijk. bruteforce is geen optie, dit wil ik ook achterwege laten, ik wil alleen begrijpen hoe ze het onmogelijk maken om iets terug te rekenen.

Zoals al gezegd: niet onmogelijk. Wel traag.

Wat bedoel je met geen optie? Wil je iets kraken? Dan heb je pech: vraag het de eigenaar

[ Voor 29% gewijzigd door F_J_K op 18-12-2004 20:05 ]

[Lizard]

Op deze pagina: http://www.tcs.hut.fi/~mjos/md5/ staat een collision van md5 (met uitleg) dus nu is md5 niet meer echt secure te noemen. (Er is nog geen prg waarmee je willekeurige hashes kan colliden.) Voor de rest is alleen zoals eerder genoemd bruteforcen een optie of zelf md5 hacken...

[Victor]

Misschien wel interessant: Er is een manier om MD5 hashes in enkele minuten te "kraken" (oorspronkelijke waarde terughalen), namelijk d.m.v. rainbow tables. Dit zijn gigantische (een tabel van 3GB is geen uitzondering) tabellen met allerlei voorgegeneerde hashes waarmee de oorspronkelijke waarde terugberekend kan worden.

Zie voor meer info: LASEC en Google

[Verwijderd]

Verwijderd schreef op zaterdag 18 december 2004 @ 19:57:
[...]
Ik wil ook helemaal niet de oorspronkelijke data terug, ik wil alleen een 'willekeurig' stukje data met dezelfde hash!

Ik denk dat hij bedoelt dat een MD5-hash niet alleen uniek is voor een bepaald wachtwoord; eenzelfde hash kan inderdaad door verschillende wachtwoorden tot stand komen, al is de kans nogal klein.

[The Lord]

King_Louie schreef op zaterdag 18 december 2004 @ 20:24:
Misschien wel interessant: Er is een manier om MD5 hashes in enkele minuten te "kraken" (oorspronkelijke waarde terughalen), namelijk d.m.v. rainbow tables. Dit zijn gigantische (een tabel van 3GB is geen uitzondering) tabellen met allerlei voorgegeneerde hashes waarmee de oorspronkelijke waarde terugberekend kan worden. ...

In principe zijn rainbow tables een mogelijkheid. Echter moet je dan wel weten uit hoeveel karakters de oorspronkelijke string bestaat of een limiet stellen. Anders worden de tables al snel een aantal terabytes of zelfs nog veel groter.

Afgezien van brute force en bijbehorende versnellings technieken is het theoretisch zeker niet onmogelijk de MD5 terug te rekenen. Echter is er nog geen methode gevonden om dit te doen, maar slechts voor delen van de data uit welke de hash wordt opgebouwd.
In het algemeen geld echter dat het vinden (berekenen om te bewijzen dus) van een reverse algoritme moeilijker is dan een brute force attack. Dit betekent in de praktijk dat een hashing algoritme al als onveilig wordt gezien ruim voordat een reverse algoritme is gevonden en bewezen.
Afgezien van simpele fouten in het hashing algoritme natuurlijk, daar zijn er al meerdere van gemaakt in verschillende hash principes.

B.t.w. Een collision betekent niet meteen dat er een reverse algoritme is. Een collision is echter wel een bewijs voor de mathematische sterkte van het algoritme. De collision laat zien dat er ten minste 2 strings zijn welke dezelfde MD5 tot gevolg hebben.

[ Voor 10% gewijzigd door The Lord op 18-12-2004 20:43 ]

[Verwijderd]

The Lord schreef op zaterdag 18 december 2004 @ 20:39:
In het algemeen geld echter dat het vinden (berekenen om te bewijzen dus) van een reverse algoritme moeilijker is dan een brute force attack. Dit betekent in de praktijk dat een hashing algoritme al als onveilig wordt gezien ruim voordat een reverse algoritme is gevonden en bewezen.

en dit is dus wat ik in de openingspost al heb geprobeerd de formuleren. Hoe werkt dat dan? Over wat voor wiskunde heb je het dan? Zover ik weet bestaan er van alle wiskundige bewerkingen een soortgelijke omgekeerde bewerking, dus ik snap niet waarom het maken van een MD5 hash in een seconde gebeurd is, maar het maken van data mbv de MD5 hash (dus het omgekeerde algoritme) onmogelijk lang zou moeten duren?

[Spider.007]

Verwijderd schreef op zaterdag 18 december 2004 @ 21:02:
[...]

en dit is dus wat ik in de openingspost al heb geprobeerd de formuleren. Hoe werkt dat dan? Over wat voor wiskunde heb je het dan? Zover ik weet bestaan er van alle wiskundige bewerkingen een soortgelijke omgekeerde bewerking, dus ik snap niet waarom het maken van een MD5 hash in een seconde gebeurd is, maar het maken van data mbv de MD5 hash (dus het omgekeerde algoritme) onmogelijk lang zou moeten duren?

Voor een volledig onderbouwde uitleg kun je deze link eens bekijken: Securing the net-the fruits of incompetence

[Bananenplant]

Heeft dat terugrekenen ook geen exponentiele complexiteit net zoals bij het proberen te kraken van PGP?

[Verwijderd]

Spider.007 schreef op zaterdag 18 december 2004 @ 21:08:
[...]

Voor een volledig onderbouwde uitleg kun je deze link eens bekijken: Securing the net-the fruits of incompetence

mmm dat gaat mijn pet te boven

ucchan schreef op zaterdag 18 december 2004 @ 21:15:
Heeft dat terugrekenen ook geen exponentiele complexiteit net zoals bij het proberen te kraken van PGP?

hmz zou je dit aan de hand van een simpel voorbeeldje kunnen toelichten? Delen is toch ongeveer net zo moeilijk als vermenigvuldigen, en integreren als differentieren?

[Spider.007]

Verwijderd schreef op zaterdag 18 december 2004 @ 22:12:
[...]

mmm dat gaat mijn pet te boven

[...]

hmz zou je dit aan de hand van een simpel voorbeeldje kunnen toelichten? Delen is toch ongeveer net zo moeilijk als vermenigvuldigen, en integreren als differentieren?

Lees dan deze even door:

[rml][ md5] uitleg algoritme[/rml]
md5 hashes database

[Bananenplant]

Tijdcomplexiteit van een algoritme is een functie die weergeeft hoeveel de rekentijd toeneemt met de grootte van de invoer. Lineair en logaritmisch zijn gunstig, kwadratisch niet en exponentieel eigenlijk onbruikbaar. Dat zie je ook wel bij PGP, kleine sleutels kun je wel kraken, maar dan maak je die sleutels gewoon wat groter, want de rekentijd neemt exponentieel toe met de grootte van de sleutels.

Dat is dus het kraken van die sleutels, het gebruik van die sleutels gaat uiteraard een stuk sneller

[Spider.007]

Ik zie trouwens net dat er al een MD5 collision is gevonden:

$ diff -q file0 file1
Files file0 and file1 differ

$ md5sum file*
a4c0d35c95a63a805915367dcfe6b751 file0
a4c0d35c95a63a805915367dcfe6b751 file1

Zie ook deze PDF