Het is heel simpel.

Stel je hebt het getal 40 en je deelt dat door 2. Uitkomst = 20.
Weet je dan met ALLEEN die 20 dat het originele getal 40 was? Nee.

Nog een voorbeeld:

Stel ik heb een bestand van 10MB en ik bereken daar de MD5 hash over (128 bits)
Dan kan ik van die 128-bits tekens niet terug naar die 10MB.

Ik hoop dat dit je duidelijk maakt dat je van een hash nooit terug kunt naar de originele data.

Maar als je de uitkomst van 20 weet en je weet dat de procedure delen door 2 is, dan weet je toch nog steeds dat het oorspronkelijke getal 40 is met een terugberekening?

Erik,

Ik snap je verhaal niet precies. Je zegt 40/2 = 20. De formule weet je dan toch. Als je 20 hebt draai je de formule om: 20 x 2 = 40 dus weet je eindelijk wel wat het orginele getal was. Waarom kan dat bij een md5 dan niet.

Sorry dat was misschien een slecht voorbeeld.

Ander voorbeeld.

Stel je doet 42 MOD 4 = 2 . Kun je dan van die 2 weer terug naar die 42 (ook al weet je de 4)?

En vergeet niet mijn voorbeeld over de 10MB -> 16 bytes (128 bits) hash.

Je kunt nooit terug naar het origineel.

Google is your friend ...

De meest simpele uitleg uit een forum gejat:
http://www.frihost.com/forums/vt-63066.html

Het systeem werkt ongeveer zo, stel de volgende reeks bytes voor:

01 23 56 21 a5 b6 e3 4f 5a 3a

Een hele simpele vorm van een hash is dit:

01 + 23 + 56 + 21 + A5 + B6 + E3 + 4F + 5A + 3A = 3BC

Je kunt nu niet meer van die 3BC terug rekenen wat de originelen waren, ook al weet je exact hoe de berekening loopt.
Het probleem bij het terug rekenen is namelijk dat je voor elke variabele meerdere antwoorden hebt en je niet kunt bepalen welke de juiste is.

Een 'echte' hash is overigens wel wat complexer maar het idee blijft hetzelfde.

Misschien is dit voorbeeld makkellijker. Stel je een bestand voor dat er, op binair niveau, zo uit ziet als hieronder.
Tel nu van boven naar beneden het aantal nullen en enen, en schrijf eronder een 0 of een 1 zodanig dat het aantal nullen en enen allebei een even getal of 0 is. Dus, als er 2 enen en 1 nul staat, zet je een 0 neer zodat het 2 enen en 2 nullen wordt. Als er 3 nullen staan zet je een nul neer, zodat het 4 nullen en 0 enen wordt:

01010101
00110011
10010110
--------------
11110000

De uitkomt, 11110000, is nu een controle-string van het bestand. Als er ergens in het bestand een getal gewijzigd wordt, klopt de string niet meer (vergeet even wat er gebeurt als 2 wijzigingen elkaar opheffen, dit is slechts een voorbeeld).
Om te controleren of het bestand ongewijzigd is, kan de ontvanger van het bestand dezelfde bewerking uitvoeren, en dan het resultaat van zijn bewerking vergelijken met de uitkomst van de verzender (Het zegt dus niets over de "waarheid" van de inhoud van het bestand, maar wel over of het tijdens transport gewijzigd is). Om terug te komen op de vraag, met de uitkomst 11110000 is het oorspronkelijke bestand niet terug te halen, er is geen manier om te weten of de eerste 1 het resultaat is van "111" of "001" of "100" of "010", alle vier geven deze als uitkomst een 1.

Een ander voorbeeld: Stel je voor dat ik een soortgelijk controle-bestand wil maken van een stuk tekst. Dan kan ik bijvoorbeeld zeggen "De letter a komt 16 keer voor, de letter b 19 keer, de letter c 4 keer, de letter d 25 keer" etc. etc.
Kan je aan de hand daarvan terug redeneren wat de tekst is geweest?

De mod inderdaad één van de factoren die er voor zorgt dat je het origineel niet meer terug kunt halen.

Wat ook nog leuk is om te noemen zijn collisions. In mijn voorbeeld had ik uiteindelijk de hash 3BC verkregen.

Maar bijvoorbeeld:

FF + FF + FF + BF = 3BC

Omdat beide series data dezelfde hash opleveren noemt men dit een collision. Dit geldt ook voor bijv. password hashes. Het maakt feitelijk niet uit of het gevonden wachtwoord exact hetzelfde is als het originele wachtwoord, als beide hashes hetzelfde zijn zal de computer het als een geldig wachtwoord zien. Dit soort collisions zijn de reden dat MD5 eigenlijk niet meer geschikt is.

Hehehe.. Dit is een pariteit geen hash ;)

Hashing algoritme is niet eens zo complex als je zou denken.
Zoek maar eens md5 of sha op in wikipedia.

Zie het als basisschool staartdeling.
De methode is bekend net als het md5 algoritme.
Je kunt de restwaarde uit je staartdeling vergelijken met de uiteindelijk berekende md5 hash.
Knappe jongen als je met de restwaarde nog kan terugrekenen wat de originele invoer was.
Natuurlijk kun je net zo lang je berekening aanpassen totdat je op de restwaarde uitkomt, je bent dan aan het bruteforcen

De staartdeling vergelijking gaat natuurlijk niet volledig op, want je kunt zo een aantal verschillende berekeningen bedenken die dezelfde restwaarde opleveren (collision)

Van zowel md5 en sha zijn collisions bekend.

In md5 leveren de volgende 2 verschillende input dezelfde hash waarde 79054025255fb1a26e4bc422aef54eb4 op:

d131dd02c5e6eec4693d9a0698aff95c 2fcab58712467eab4004583eb8fb7f89
55ad340609f4b30283e488832571415a 085125e8f7cdc99fd91dbdf280373c5b
d8823e3156348f5bae6dacd436c919c6 dd53e2b487da03fd02396306d248cda0
e99f33420f577ee8ce54b67080a80d1e c69821bcb6a8839396f9652b6ff72a70

d131dd02c5e6eec4693d9a0698aff95c 2fcab50712467eab4004583eb8fb7f89
55ad340609f4b30283e4888325f1415a 085125e8f7cdc99fd91dbd7280373c5b
d8823e3156348f5bae6dacd436c919c6 dd53e23487da03fd02396306d248cda0
e99f33420f577ee8ce54b67080280d1e c69821bcb6a8839396f965ab6ff72a70

Elke collision brengt het algoritme ernstig in gevaar.
Je kunt dit dan misbruiken om bijvoorbeeld zelf een SSL certificaat te ondertekenen.
Dat kan dan gewoon zonder diginotar hacker :)

Veel cryptografische functies maken onder meer gebruik van de modulus functie.

En erg vereenvoudigde (en daarmee feitelijk incorrecte) beschrijving van een crypto hash is dan ook uistluitend de modulus functie toe te passen op de "message" om zo de "digest" uit te rekenen. Het resultaat van de modulus functie is een getal met vaste lengte, ongeacht de lengte van de message.

Allereerst: hashing != encryption
Bij md5 wordt data van gelijk welke lengte aanvaard en is de output te allen tijd een 128 bits waarde. Ff hier dieper op ingaan. Het originele datablok zal eerst aangevuld worden (beginnend met een één gevolgd door nullen) zodanig dat de lengte van het bestand 64 bytes minder is dan een veelvoud van 512 (448 (mod 512)). Deze procedure heet padding. De ontbrekende 64 bits worden aangevuld door de 64 bits representatie van het originele bericht. Het bekomen bericht wordt dan opgedeeld (chuncked) in blokken van 512 bits. Deze blokken zullen één voor één verwerkt worden adhv vier 32 bits registers (128bit). De initiële hexadecimale waarden van de registers (A, B, C en D) zijn: (0x01234567, 0x89abcdef, 0xfedcda98, 0x76543210). Hierbij wordt op een niet lineaire manier de inputdata 'bijgemixt". Na de eerste round krijgt men als resultaat een 128 bit waarde, deze uitvoer dient samen met het volgende blok van 512 bits als invoer voor de volgende round. Dit gaat net zo lang door totdat het gehele bericht is afgehandeld. Het uiteindelijke resultaat is één 128 bits message digest. Het feit dat je een variabele input hebt die niet lineair verwerkt wordt en een steeds vaste output (qua lengte) krijgt maakt md5 onomkeerbaar. Het enige zwakke punt bij md5 is dat bv. een wachtwoord éénenkele hash heeft. Eenmaal dat de link tussen die twee gelegd is, is je wachtwoord waardeloos. Nogmaals het bewijs dat mensen random all chars pwd's moeten gebruiken anders zijn ze de vogel voor de kat van Mr. Rainbow.

Dit klopt niet. Het probleem is dat verschillende wachtwoorden dezelfde hash op kunnen leveren, wat een collision is.

Kan je dat even verder toelichten aub?

Kan je dit aub even toelichten?
Share the knowledge :)

Bij het berekenen van de md5 checksum worden er 640 bits (met o.a. het wachtwoord) flink doorelkaar gehusseld.

Voor normale wachtwoorden (korter dan 48 tekens) geldt dat tot bijna het eind toe de hele berekening terug te draaien is. Maar op het eind gebeurt er iets fataals, 512 bits worden weggegooid! Op dat moment is de berekening niet meer terug te draaien. De overgebleven 128 bits vormt de checksum.

Soms zijn er wel zaken terug te draaien, dan is de checksum gekraakt. md5 is voor veel toepassingen al niet meer geschikt, maar voor password hashing is het volgens mij nog te gebruiken.

*zucht*

i rest my case.

Dit klopt niet (helemaal). Per definitie zijn er oneindig veel "collisions" bij elke hash variant. Een hash is nl een mapping van een mogelijk oneindige reeks bits naar een eindige reeks en dus zijn er per definitie oneindig veel "collisions". Waar het om gaat is of een hash "collision" resistent is. Dus, het moet praktisch onmogelijk zijn om een "collision" te vinden. MD5 heeft twee problemen. MD5 is niet meer "collision" resistent (dus je kan twee inputs vinden die dezelfde hash opleveren) en de "key space" is te klein zodat het met de huidige computers mogelijk is om een MD5 hash te "brute forcen" (rainbow tables).

Het was ook maar een relatief simpele uitleg. Maar je hebt helemaal gelijk.

Waar ik op reageerde was de opmerking dat een wachtwoord maar 1 hash heeft en dat dat het probleem van MD5 is. En dat klopt niet. Elke hashing functie (MD5, SHA-1, SHA-256, etc) levert altijd een en dezelfde hash op voor een wachtwoord. Daar is ook het hele authenticatie mechanisme op gebaseerd.

Achteraf vermoed ik dat eXpLoiT.be wellicht in de war is met een salt. Een salt wordt gebruikt om ervoor te zorgen dat als twee mensen hetzelfde wachtwoord hebben ze toch niet dezelfde hash krijgen. Tevens maakt een salt het brute-force'n moeilijker omdat je ook de salt mee moet rekenen.

Een voorbeeldje dan maar weer. En voor de muggenzifters het is een versimpeling om het duidelijk te maken ;)

Stel Pietje heeft het wachtwoord "ditismijnwachtwoord", dat wachtwoord heeft de hash-waarde 12345. In de database is dan het volgende opgeslagen:

Als Pietje z'n wachtwoord intypt rekent het systeem de hash-waarde uit en vergelijkt die met de opgeslagen hash. Als deze overeenkomen dan is het wachtwoord goed en is de authenticatie gelukt.

Maar stel nu dat "ditiseenanderwachtwoord" ook de hash-waarde 12345 oplevert. Als je dat wachtwoord intypt rekent het systeem er weer de hash waarde voor en vergelijkt deze met de opgeslagen hash. Aangezien beide hashes overeenkomen denkt het systeem dat dat wachtwoord dus correct is. Dit terwijl de feitelijke wachtwoorden eigenlijk anders zijn.

En nog even aanvullend ingaand op collision wat hier bijna nergens goed wordt uitgelegd:

Neem het letterlijk: botsing.
Een hash botst wanneer twee (of meer) verschillende bronnen (documenten, wachtwoorden) dezelfde hash opleveren.
Verschillende informatie ziet er dan als hash hetzelfde uit. Dat is gevaarlijk, want als je dat weet en je hebt zo'n botsing gemaakt of gevonden, dan kun je je als man in the middle voordoen als de hash van die andere informatie. Waar dus heel wat anders in staat. Bij MD5 is dat inmiddels vrij eenvoudig zelf te malken.
Bij SHA-1 is het goed mogelijk een botsing te vinden (niet brute force maar door er naar te zoeken) maar onwaarschijnlijk er een zelf te maken.
Van elke hash die informatie reductie gebruikt (hash korter dan de info) staat overigens wiskundig vast! dat er een of meer van deze botsingen moeten bestaan. Dat levert dan meestal onzin op.
De MD5 story levert echter info op die voor hetzelfde doel gebruikt kan worden. Bijvoorbeeld twee certificaten waarvan er dan een fals is. Daarom is al in 2008 MD5 uitgefaseerd voor dit doel.

Ik heb alsnog geen antwoord op mijn vraag gekregen.
Iedereen probeert maar duidelijk te maken dat je niet de originele waarde kan krijgen uit alleen de hash. Ik begreep dit al, zoals vermeld. Het gaat mij om de hashing mbt wachtwoorden.
Mijn vraag is waarom je niet kan terugrekenen met de hashformule (NEE, hoeft niet de originele waarde te hebben voor wachtwoord).

Nader uitgelegd:


Voorbeeld dat voorbij kwam: 42 MOD 4 = 2

- Het wachtwoord is in dit voorbeeld dus 42.
- Hash formule is [wachtwoord] MOD 4.

Met hashwaarde 2 kan je inderdaad niet 42 met zekerheid achterhalen, maar je kan wel terugrekenen, X MOD 4 = 2. Een valide waarde is bijvoorbeeld 2 (een collission).
Dus als je dan wachtwoord 2 invoert, checkt het systeem de hashwaarde, dus 2 MOD 4. Dit is 2. Dan checkt het systeem of de hashwaarde klopt, wat zo is, dus krijg je toegang tot het systeem.


Ander voorbeeld dat voorbij kwam: 01235621a5b6e34f5a3a01

De hashwaarde wordt hier verkregen door van het wachtwoord de getallen per 2 op te tellen: 01 + 23 + 56 + 21 + A5 + B6 + E3 + 4F + 5A + 3A = 3BC

Met terugrekenen kan je dus als wachtwoord FFFFFFBF invoeren, dit geeft na hashing ook 3BC. Dus krijg je met het wachtwoord FFFFFFBF ook gewoon toegang.


Toch kan je blijkbaar niet terugrekenen, alleen snap ik dit niet. Kan iemand dit nader uitleggen.

Even ingaand op dat stukje van die slat.

Die wordt toegevoegd (en is hopelijk bij elk loginsysteem verschillend) zodat elk loginsysteem een andere hash voor het wachtwoord genereerd. En twee gebruikers met hetzelfde wachtwoord op het zelfde loginsysteem krijgen dezelfde salt bij hun wachtwoord en dus dezelfde hash. Wat ook zou kunnen: iedere gebruiker een andere salt geven, maar dan moet je de salt ook ergens per gebruiker opslaan (een soort van open en bloot hulpwachtwoord).

Groeten,
Jenswa

(PS: ik lees meestal alleen hier vandaar mijn anonieme reactie)

Omdat sommige dingen wel kunnen en voor de geïnteresseerden, is er altijd nog deze site:-)
http://www.md5decrypter.co.uk/
Enjoy!

De vraag is duidelijk, maar niemand geeft een antwoord ...

Eerst even wat extra informatie :
Over collisions : Zodra de te hashen data langer is dan de hash-output, wat je zeker _dat_ er collisions moeten zijn.
Dat heet het 'pigeonhole principle' . Als je 11 duiven en 10 hokken hebt, moet er minimaal één hok zijn waar meer dan één duif zit.
Voor een hash met een lengte van n bits , kun je rekenen op een collision bij het hashen van 2^(n/2) berichten.
Voor een hash met een lengte van 128 bits, kun je gemiddeld dus een collision verwachten bij het hashen van 2^64 berichten.
Dit heet een 'birthday attack' . De reden is de 'birthday paradox' het een beetje onverwachte gegeven dat als er (maar) 23 mensen bij elkaar zijn, de kans op een een tweetal wat op dezelfde dag jarig is dan al 50% bedraagt.
(middelbare school wiskunde : 1 - (kans dat *iedereen* op een verschillende dag jarig is).
Een complete uitleg, die wat verder dan middelbare school gaat : http://en.wikipedia.org/wiki/Birthday_problem

Dat is een collision.

Als je significant sneller dan de birthday attack collisions kunt vinden, heeft de hash een probleem voor cryptografisch gebruik.

Dan heb je het begrep "pre-image (resistance)" . Dat is de vraag om, gegeven een hash-resultaat, een bericht te vinden waarvan het resultaat die hash oplevert.
Als dat "moeilijk" is, is een hash een one-way hash.

En second pre-image resistance is , gegeven een bericht en hash-output voor dat bericht, vind een ander bericht wat dezelfde hash-ouput geeft.
Dat is niet hetzelfde als een collision; Voor het vinden van een collision mag je zelf *beide* berichten kiezen , als de hash maar op hetzelfde uitkomt. Om een second pre-image attack te claimen moet je een collision vinden als één bericht al gegeven is.

Nu is je vraag waarom een first pre-image attack (een gegeven hash output, en dan een bericht vinden wat dat als resultaat heeft) moeilijk is, ook al ken je de hash functie.

"Omdat een goede cryptografische hash functie zo gebouwd is dat dat ook moeilijk cq onmogelijk is"

De hash wordt gebouwd om 'avalanche effect' te hebben, dat wil zeggen dat het veranderen van een enkel bit in de input, heel snel effect heeft op alle output bits. En 'diffusion' , dat output bits op een complexe manier afhangen van input bits.

Het komt er op neer dat je de hash dus niet 'achteruit' kunt draaien, omdat het elk bit van het resultaat op tig manieren van de input afhangt.

Gegeven dat een aantal toch vrij recente hashes uiteindelijk zwakker gebleken zijn dan hun ontwerp-doel, denk ik dat er weliswaar wel een aantal noodzakelijke eigenschappen van hash(componenten) bekend zijn, maar er ook voor de experts altijd nog verrassingen bij kunnen zitten.

Het 'Handbook of Applied Cryptography' van Menezes, van Oorschot , en van Stone is denk ik de beste algemene crypto referentie. Hoofdstuk 9 gaat over hashes.
http://www.cacr.math.uwaterloo.ca/hac/

wow je hebt een IRC bot met md5 rainbow tables gevonden.. Proficiat
probeer deze eens: 8bec2f0cd144e4c895677dbfd059557b
=)

Gut, ondanks alle posts, en herhaalde vraag, snap je nog steeds de vraag niet.

Het gaat NIET er niet om dat er geen noodzaak is om terug te rekenen.
Noch om het feit dat je vanwege informatie verlies geen zekerheid kunt krijgen wat de originele input was.

De vraag is, waarom het moeilijk is om gegeven het hash resultaat _een_ input te vinden die dat resultaat geeft.

De voorbeelden van een niet-sterke hash zoals MOD , checksum, optellen laten dat niet zien.
Want daar kun je *wel* inputs vinden die een gegegeven uitkomst als resultaat hebben.
Of dat de originele input was weet je niet. Boeit ook, vanuit een password perspectief.

Als jhgjhagdjkajkaghd en "mysecret01" dezelfde hash opleveren, kun je met allebei inloggen.

Waarom dat nu moeilijk is voor een crypto hash is een terechte vraag, en er is geen makkelijk antwoord op te geven.

Het enige wat ik verder kan toevoegen aan mijn antwoord van 2:08 voor de OP is om een beschrijving van MD5 te nemen, en (gewoon op papier) te proberen om zelfs maar 1 ronde terug te tellen, voor elke bit te kijken hoe die bit 0 dan wel 1 geworden is.

Als je die link niet alleen gegeven, maar ook gelezen had, had je ook geweten wat ik gisteren 2:08 al zei.

P1. Pre-image resistance: Given a hash value h it should be hard to find any message m such that h = H(m).
(pagina 4 van de introductie).

De OP vraagt, m.i. duidelijk genoeg, "Als je maar terugrekent met de formules krijg je toch een wachtwoord die de juiste hash oplevert? Waarom kan je niet terugrekenen, de formule is immers bekend."

En zegt er inderdaad al zelf bij dat dat niet het originele wachtwoord hoeft te zijn, maar iets wat werkt.

Dat is , in de juiste termen, de vraag naar een (First) pre-image attack . Gegeven een hash output h, het vinden van any message m zodanig dat h = H(m).
Cq de vraag waarom dat nou moeilijk is als je de hash functie kent.

Bij een collision attack mag je twee messages m en m' construeren, met als voorwaarde dat ze dezelfde hash output opleveren. De hash output staat daarbij niet vast, en de twee messages dus ook niet.
Dat is, als je vragen hebt over het terugrekenen van gegeven hashes vanuit een password file, niet zinvol.

Lees nou je antwoorden nog eens, en zeg dan waarom die een antwoord zouden zijn op de vraag van de OP.

In de intro van het afstudeerverslag wat je linkt worden de basisbegrippen (first) pre-image resistance, second pre-image resistance en collision resistance gedefinieerd.

Een collision attack is boeiend, en knap, en zeker een slechte eigenschap voor een cryptografische hash om te hebben, en ook genoeg om de hash als 'broken' te beschouwen, maar het is GEEN pre-image attack.
En een collision attack is zeker ook niet zomaar om te bouwen of uit te breiden naar een pre-image attack, of naar een second pre-image attack.
In de 18 jaar werk tussen dat van Den Boer/Bosselaers (1993),Hans Dobbertin (1996) en heden is er ook geen succesvolle pre-image attack op MD5 bekend geworden.
(dictionary attacks, rainbow tables of het brute-forcen van een klein stukje message space worden niet gezien als het falen in pre-image resistance voor MD5 of een andere serieuze cryptografische hash).

Hij heeft inderdaad de vraag aardig begrepen en velen anderen totaal niet. Het gaat inderdaad om terugrekenen van de formules met de bekende output. En het gaat NIET om de originele input, het gaat om een geldige input.
Blijkbaar is het zeer moelijk om te verklaren waarom je niet kan terugrekenen. Met normale wiskundige formules, kan je namelijk gewoon terugrekenen naar een geldige innput, ook al is er info weggegooid. Je komt dan zeer waarschijnlijk wel op een andere dan de originele input uit, maar dat is NIET relelvant, want als je de formule doorloopt kom je op dezelfde output (hash).