MD5 Decrypten, waarom kan dit niet

[synthesix]

Wat ik nou nooit begrepen heb is waarom je md5 niet kan decrypten.
Ik bedoel, er gaat een algoritme over de string heen, zodat er een andere string uit komt, waarom kan je dat algoritme dan niet gewoon andersom gebruiken om hem te decrypten.

(((10 - 5) * 3) + 1) :2 = 8
en dit is dus ook gewoon
(((8* 2) - 1) :3)+5 = 10

Hoe werkt md5 dan dat dit hiermee niet kan?

[Osiris]

Hier staat uitgelegd hoe MD5 werkt, ik zou zeggen, probeer het eens

[BasieP]

bekijk het eens zo:

een md5 hash is 32 tekens lang. ongeacht wat je er in stopt..
als je er niks in stopt komt er toch een hash uit,

en kijk nu nog eens naar je vraag..

[Wolfboy]

MD5 is geen encryptie, het is een hash en die kan je niet de-hashen oid.

Bij een md5 hash maakt het dan ook niet uit hoeveel input je hebt, als je 1 letter invoert krijg je 32 tekens maar ook met 10.000 tekens komen er 32 tekens uit.

Bij een encryptie heb je standaard net wat meer output dan dat je input hebt, totaal anders dus.

[PowerSp00n]

Een MD5 bevat gewoon niet wat je erin stopt, hoe wil je het er dan weer uit krijgen?

[LuCarD]

Heeeel simpel uitgelegd.


Nu deze
Character A + Character B = Character C
A en B zijn ingevoerde waarde en C is het resultaat
A=6, B=2,C=8

6 + 2 = 8

8 = 6+2 of 3 + 5 of 1 + 7 etc

[Osiris]

Wat ik me wél eens afvraag:

Stel je hebt een password 'foo' en maakt daar een MD5-sum van. Vervolgens pak je die RFC erbij en ga je die MD5-sum 'reverse engineren'.
Uiteindelijk kom je uit op het ge-reversed engineerde password 'bar'. Hmm, 'bar' is niet hetzelfde als 'foo'. Máár, uit zowel 'foo' als 'bar' komt dezelfde MD5-sum, dús kun je met 'bar' inloggen.

[TeXiCiTy]

Het is natuurlijk wel zo dat je met verschillende inputs dezelfde output kan krijgen. Doet DPC niet aan die ongein ?

[Bosmonster]

Osiris schreef op woensdag 04 januari 2006 @ 18:09:
Wat ik me wél eens afvraag:

Stel je hebt een password 'foo' en maakt daar een MD5-sum van. Vervolgens pak je die RFC erbij en ga je die MD5-sum 'reverse engineren'.

Doe je best met het 'reverse engineren' van een hash

[Verwijderd]

uuhm.. ?
ik gebruik wel eens Cain & abel
Password sniffer met ARP ..
Maar er zitten ook Pass crackers enzo op
nu zit er ook een MD5 hash Cracker bij ..
hoe kan dit dan ?
ik moet er een hash invoeren in HEX
iemand die er eens een kan geven zodat ik eens wat kan proberen..??

[brokenp]

De sterkte van een hash algoritme ligt daarom o.a. in het feit hoe moeilijk het is om een collision te contrueren is

Wat jij vergeet is dat een hash algoritme niet alleen simpele optellingen en vermenigvuldigingen doet, maar ook operaties die niet inverteerbaar zijn (er is dus geen tegenovergestelde operatie), te denken valt aan een machtsverheffing modulo een getal.
Probeer maar eens een oplossing te vinden van het volgende probleem
a^3 mod 12 = 5, wat is a

Deze is dus makkelijk, maar denk eens aan het algemene probleem

[ Voor 10% gewijzigd door brokenp op 04-01-2006 18:16 ]

[Bosmonster]

de enige manier om MD5 te 'kraken' is brute force (collisions), of gebruik te maken van een reverse lookup database, waar er meerdere van de vinden zijn op internet. Over het algemeen bevatten die hashes van veel voorkomende wachtwoorden.

voorbeeldje: http://gdataonline.com/

[ Voor 22% gewijzigd door Bosmonster op 04-01-2006 18:16 ]

[Orion84]

Verwijderd schreef op woensdag 04 januari 2006 @ 18:13:
uuhm.. ?
ik gebruik wel eens Cain & abel
Password sniffer met ARP ..
Maar er zitten ook Pass crackers enzo op
nu zit er ook een MD5 hash Cracker bij ..
hoe kan dit dan ?
ik moet er een hash invoeren in HEX
iemand die er eens een kan geven zodat ik eens wat kan proberen..??

Dat is prolly gewoon brute force. Dus gewoon allerlei woorden enzo hashen en kijken of je op dezelfde hash uitkomt.

[Osiris]

Bosmonster schreef op woensdag 04 januari 2006 @ 18:11:
[...]


Doe je best met het 'reverse engineren' van een hash

Nah, daar heb ik de TS voor, ik doe liever nog wat nuttigs voordat ik dood ga

[BasieP]

Orion84 schreef op woensdag 04 januari 2006 @ 18:16:
[...]

Dat is prolly gewoon brute force. Dus gewoon allerlei woorden enzo hashen en kijken of je op dezelfde hash uitkomt.

en als ze slim zijn maken ze gebruik van dictonairies, dan zijn ze een stuk sneller, maar vinden ze niet alles

[Bosmonster]

BasieP schreef op woensdag 04 januari 2006 @ 18:22:
[...]

en als ze slim zijn maken ze gebruik van dictonairies, dan zijn ze een stuk sneller, maar vinden ze niet alles

Net voor de gein eens 2 hashes geprobeerd die ik hier in een systeem heb zitten. En zowaar 1 van de twee had ie het wachtwoord bij (nog het juiste ook, niet eens een collision).

[XyritZz]

Gaat een beetje offtopic, maar toch een serieuse vraag.

Op websites/Quakenet word je altijd aangeraden om een "moeilijk" wachtwoord te nemen. Dus in plaats van "wachtwoord" dus iets als "wAcHTw00rD"

Als ik dit zo lees over dat een MD5 hash altijd 32 tekens heeft, maakt de "moeilijkheid" van je wachtwoord toch geen ........ uit? Het word er alleen voor jezelf moeilijker door om het goed te onthouden, waarom staan er dan toch zulk soort dingen op websites?

[Orion84]

XyritZz schreef op woensdag 04 januari 2006 @ 18:24:
Gaat een beetje offtopic, maar toch een serieuse vraag.

Op websites/Quakenet word je altijd aangeraden om een "moeilijk" wachtwoord te nemen. Dus in plaats van "wachtwoord" dus iets als "wAcHTw00rD"

Als ik dit zo lees over dat een MD5 hash altijd 32 tekens heeft, maakt de "moeilijkheid" van je wachtwoord toch geen ........ uit? Het word er alleen voor jezelf moeilijker door om het goed te onthouden, waarom staan er dan toch zulk soort dingen op websites?

Omdat moeilijke wachtwoorden minder makkelijk te raden zijn met behulp van brute force. Brute force methoden proberen eerst voor de hand liggende dingen en bestaande woorden, en pas als dat niet werkt willekeurige teken combo's.

[Verwijderd]

Orion84 schreef op woensdag 04 januari 2006 @ 18:16:
[...]

Dat is prolly gewoon brute force. Dus gewoon allerlei woorden enzo hashen en kijken of je op dezelfde hash uitkomt.

idd, het is brute force, plus woordenboek enzo..
en cryptanalysis via rainbowtables iemand die mij kan uitleggen wat zoiets is ?
er zit namelijk nog een programa bij dat zoiets genegeerd en daar is ie iets van 40 uur hier bezig..

[Henk007]

Een paar maanden terug was er een bericht over een groepje wiskundigen die een methode hebben gevonden om het berekenen van een collision (twee strings met een identieke md5 hash) enkele grootte-ordes gemakkelijker te maken dan pure brute force. momenteel heb ik even geen tijd om een link naar de bron te zoeken, isschien op een later tijdstip.
Conclusie van het verhaal was dat het beter was om het nieuwere SHA-256 algoritme te gebruiken voor echt kritische toepassingen.

edit:
In het MD5 wikipedia artikel wordt verwezen naar het onderzoek dat ik noemde.

[ACM]

Het gaat er om dat je niet na 5 pogingen al een collision wilt hebben

Als jij een 3-letterig password hebt, is dat worst-case na 26^3 al voor elkaar, dat zijn in de computerwereld nog vrij weinig pogingen. Bij 8 karakters, hoofd/kleine letters en cijfers is het (26+26+10)^8... net even iets meer pogingen nodig om het brute-force te kraken.

[edit]
En toen stonden er alweer meer reacties

[ Voor 8% gewijzigd door ACM op 04-01-2006 18:30 ]

[NMe]

XyritZz schreef op woensdag 04 januari 2006 @ 18:24:
Gaat een beetje offtopic, maar toch een serieuse vraag.

Op websites/Quakenet word je altijd aangeraden om een "moeilijk" wachtwoord te nemen. Dus in plaats van "wachtwoord" dus iets als "wAcHTw00rD"

Als ik dit zo lees over dat een MD5 hash altijd 32 tekens heeft, maakt de "moeilijkheid" van je wachtwoord toch geen ........ uit? Het word er alleen voor jezelf moeilijker door om het goed te onthouden, waarom staan er dan toch zulk soort dingen op websites?

Als ik iemand's wachtwoord zou willen kraken, dan zal ik eerst een relatief snelle brute force check proberen die alleen letters en cijfers herkent, en later zou ik dan, mocht het nodig zijn, een check kunnen gebruiken die ook leestekens en spaties checkt. Wanneer je hoofd- en kleine letters gebruikt, evenals spaties en leestekens, en bovendien nog eens een lang wachtwoord neemt, dan heb je een complexe brute force check nodig, die eeuwen nodig gaat hebben om je wachtwoord te achterhalen. Dat is simpelweg vervelend, en niet veel mensen zullen zo'n wachtwoord snel kunnen/willen achterhalen.

[Verwijderd]

Daarnaast is brute force ook karakter voor karakter de combinatie uitproberen, hoe meer karakters in je password des te langer het zal duren voor een bruteforce geval het te kraken

//edit: spuit 11 enzo

offtopic:
standaard heb ik een pw van 12 karakters en soms gebruik ik ook 1 die bestaat uit 16, minder belangrijke dingen waarvan mij het niet zo kan schelen als iemand daartoe acces heeft heeft heb ik een pw die bestaat uit 8 karakters

[ Voor 46% gewijzigd door Verwijderd op 04-01-2006 18:35 ]

[BasieP]

en niet dat ik paranoide ben ofzo, maar dit is mijn wachtwoord

*****************
dat zijn er dus 17
met hoofd/kleine letters, cijfers en rare tekens..

[kenneth]

Een bikkel maakt een md5 hash van zen password en gebruikt die als nieuwe password

[synthesix]

brokenp schreef op woensdag 04 januari 2006 @ 18:15:
De sterkte van een hash algoritme ligt daarom o.a. in het feit hoe moeilijk het is om een collision te contrueren is

Wat jij vergeet is dat een hash algoritme niet alleen simpele optellingen en vermenigvuldigingen doet, maar ook operaties die niet inverteerbaar zijn (er is dus geen tegenovergestelde operatie), te denken valt aan een machtsverheffing modulo een getal.
Probeer maar eens een oplossing te vinden van het volgende probleem
a^3 mod 12 = 5, wat is a

Deze is dus makkelijk, maar denk eens aan het algemene probleem

ben ik nou gek of kan dit nou gewoon zo:

Uit jouw formule haal ik dan even de volgende vars
a=a
b=3
c=12
d=5

offtopic:
Dit is ff stukje niet kloppende php code om t makkelijk te maken:P

code:

function decrypt($a, $b, $c, $d)
{
$a_waardes = array();
for($i = 1, $i > 0, $i++){
$getal1 = $i * $c + $d;
$a_waardes[] = b_de_machts_wortel($getal1);
}
}

@ontopic
Ik ben nog bezig dat rfc-ding te lezen maar ik ben nog niet overtuigd:P

[Orion84]

synthesix schreef op woensdag 04 januari 2006 @ 18:42:
[...]


ben ik nou gek of kan dit nou gewoon zo:

Uit jouw formule haal ik dan even de volgende vars
a=a
b=3
c=12
d=5

offtopic:
Dit is ff stukje niet kloppende php code om t makkelijk te maken:P

code:

function decrypt($a, $b, $c, $d)
{
$a_waardes = array();
for($i = 1, $i > 0, $i++){
$getal1 = $i * $c + $d;
$a_waardes[] = b_de_machts_wortel($getal1);
}
}

@ontopic
Ik ben nog bezig dat rfc-ding te lezen maar ik ben nog niet overtuigd:P

Ff getest en dat levert voor i<10.000 alleen een hoop kommagetallen op waar je niks aan hebt.
Hmm, had ene oeps gemaakt, blijkt dat ie bij i=409 al een intgere waarde terug geeft voor a en wel 17.

En sowieso was er gezegd dat het in het echt wel ff iets moeilijker is dan dit. Sowieso worden er grotere getallen gerbuikt waardoor de verhouding goede uitkomsten en nutteloze uitkomsten nogal in het nadeel van de hacker is

[ Voor 30% gewijzigd door Orion84 op 04-01-2006 19:12 ]

[.oisyn]

synthesix: ik zie de moduloberekening nergens terug in je code.

Maar als antwoord op je oorspronkelijke vraag: stel ik heb 3 getallen: a, b en c. En ik stel dat dat opgeteld bij elkaar 13 is. Nou mag jij zeggen welke waarden ik voor a, b en c heb gekozen. Dat kun je niet, aangezien er oneindig veel mogelijkheden zijn. Uit 13 zijn dus niet de waarden voor a, b en c te herleiden. Net als dat bij een MD5 hash het niet te herleiden is wat het oorspronkelijke bericht was.

Natuurlijk kun je met mijn voorbeeldje wel makkelijk een collision (andere input waar dezelfde hash uitkomt) te vormen door 2 willekeurige waarden te nemen voor a en b, en dan voor c te zorgen dat het bij elkaar opgeteld 13 vormt (stel a=34 en b=1, dan c = 13 - (34 + 1) = -12. Bij MD5 is dit een stuk moeilijker, maar niet onmogelijk, want zoals gezegd is er niet zo heel lang een algoritme gevonden om zo'n collision te vinden.

[ Voor 4% gewijzigd door .oisyn op 04-01-2006 18:55 ]

[Orion84]

.oisyn schreef op woensdag 04 januari 2006 @ 18:54:
synthesix: ik zie de moduloberekening nergens terug in je code.
...

Dat zit em in regel 5, de $i * $c. Je probeert gewoon voor alle veelvouden van twaalf of je een driemacht krijgt als je er 5 bij op telt.

Nadeel is dat i*12+5 niet snel een driemacht is. En dus is dit per ongeluk nog best een goed voorbeeld.
Hmm, had dus een oeps in mijn progje wat ik snel op de grafische rekenmaschine had geknutseld, i=409 geeft dus goeie output, dus das nog redelijk snel, maar zoals gezegd is dit nogal een zwak voorbeeld.

[ Voor 46% gewijzigd door Orion84 op 04-01-2006 19:14 ]

[synthesix]

Omg ik snap er echt niks van veel te ingewikkeld. Ben er maar mee gekapt:P

.oisyn schreef op woensdag 04 januari 2006 @ 18:54:
synthesix: ik zie de moduloberekening nergens terug in je code.

Modulo is toch delen door het getal dat je modulo doet(hoe zeg je dat) en dan wat er uit komt?
18 modulo 5 = 3

Daarom heb ik dus gedaan
$getal1 = $i * $c + $d;
29 = 2 * 12 + 5

Maar als antwoord op je oorspronkelijke vraag: stel ik heb 3 getallen: a, b en c. En ik stel dat dat opgeteld bij elkaar 13 is. Nou mag jij zeggen welke waarden ik voor a, b en c heb gekozen. Dat kun je niet, aangezien er oneindig veel mogelijkheden zijn. Uit 13 zijn dus niet de waarden voor a, b en c te herleiden. Net als dat bij een MD5 hash het niet te herleiden is wat het oorspronkelijke bericht was.

Natuurlijk kun je met mijn voorbeeldje wel makkelijk een collision (andere input waar dezelfde hash uitkomt) te vormen door 2 willekeurige waarden te nemen voor a en b, en dan voor c te zorgen dat het bij elkaar opgeteld 13 vormt (stel a=34 en b=1, dan c = 13 - (34 + 1) = -12. Bij MD5 is dit een stuk moeilijker, maar niet onmogelijk, want zoals gezegd is er niet zo heel lang een algoritme gevonden om zo'n collision te vinden.

Maar is dat dan echt het enige wat het probleem is, want als je er onder de 100 oplossingen uitkrijgt is het nog superweinig eigenlijk. Bovendien maakt het eigenlijk niet uit vaak of je nou een collision vind of het goede wachtwoord, maar dat even terzijde.

edit
Ik snap trouwens niet wat
448 modulo 512 (de lengte die de hash moet worden bij de eerste bewerking)
is, het getal na modulo moet toch groter zijn dan het getal ervoor, het is toch
a modulo b = rest
net als in coding
a % b

[ Voor 8% gewijzigd door synthesix op 04-01-2006 19:13 ]

[DroogKloot]

Nee, de modulo operator is wiskundig gedefinieerd voor alle gehele getallen a en b als:

a - (b * (int) (a / b))

Dus voor a < b zal de uitkomst van a % b gelijk zijn aan a.

(Wat er gebeurt als a of b < 0 kan je wel eens veel debug-werk opleveren in bepaalde talen. )

[ Voor 23% gewijzigd door DroogKloot op 04-01-2006 19:21 ]

[Nick The Heazk]

Even duidelijk maken dat ook
3 mod 5 = 3
8 mod 5 = 3
5613213540135435145303053 mod 5 = 3
regexje voor alles wat 3 zal opleveren bij mod 5: (\d*)(3|8)

mod 5 is dan nog een mooi voorbeeld. Neem eens mod (X,XXXXX . 10^300) zoals het in het echt ook is.

[StefSybo]

edit
Ik snap trouwens niet wat
448 modulo 512 (de lengte die de hash moet worden bij de eerste bewerking)
is, het getal na modulo moet toch groter zijn dan het getal ervoor, het is toch
a modulo b = rest
net als in coding
a % b

Daarmee bedoelt men lengte % 512 = 448, dus de lengte van het bericht dat je gaat hashen wordt aangevuld totdat de lengte een veelvoud van 512 + 448 bits is.

[Erkens]

Wolfboy schreef op woensdag 04 januari 2006 @ 18:06:
Bij een encryptie heb je standaard net wat meer output dan dat je input hebt, totaal anders dus.

offtopic:
ben ik het niet mee eens, rot13 is ook een vorm van encryptie, hierbij is je output even lang als je input

[Onno_Devine]

Hmm intressant, maar wat ik dan best vreemd vind hoe werken systemen dan in een website die ook md5 gebruiken voor de veiligheid?, want als je pw decrypted opgeslagen is in de database moet hij die dan ook steeds weer decrypten als jij je wachtwoord invoert?
Zoja dan moet het toch ergens mogenlijk zijn om ze te kraken?, behalve met een brute force aanval, want deze kan maar tekstjes van circa 5 letters decrypten. (naja als je er geen dagen over wilt doen, 5 letters lukt hem vrij snel..)

Of zit ik nu veelst te moeilijk te denken?, en werkt een online inlog systeem gewoon zo:
Het ingevoerde password bij de reg. daar wordt een md5 decryptie van gemaakt en opgeslagen in de database.
en steeds als je inlogt wordt van dat woord een md5 decryptie gemaakt en vergeleken met de md5 hash in de database?

[kenneth]

rot13 is onveilg. Als je het dan toch gebruikt kan je het beter twee keer encrypten.

[Erkens]

Onno_Devine schreef op woensdag 04 januari 2006 @ 23:10:
Hmm intressant, maar wat ik dan best vreemd vind hoe werken systemen dan in een website die ook md5 gebruiken voor de veiligheid?, want als je pw decrypted opgeslagen is in de database moet hij die dan ook steeds weer decrypten als jij je wachtwoord invoert?

dergelijke systemen slaan alleen (als het goed is) de hash op van het wachtwoord, bij het inloggen wordt het ingevoerde wachtwoord ook gehashed en die hash wordt vervolgens vergeleken met de hash in de database

kenneth schreef op woensdag 04 januari 2006 @ 23:10:
rot13 is onveilg. Als je het dan toch gebruikt kan je het beter twee keer encrypten.

wie zegt er dan dat rot13 _de_ methode is om te encrypten, maw lekker nuttige reply

[ Voor 20% gewijzigd door Erkens op 04-01-2006 23:14 ]

[Onno_Devine]

Erkens schreef op woensdag 04 januari 2006 @ 23:12:
[...]

dergelijke systemen slaan alleen (als het goed is) de hash op van het wachtwoord, bij het inloggen wordt het ingevoerde wachtwoord ook gehashed en die hash wordt vervolgens vergeleken met de hash in de database

Hmm en daar heb ik ooit lang overna moeten denken
Maar nuw eet ik dan wel hoe het echt zit, tja het is eigenlijk ook de simpelste oplossing he.
Anders zou Md5 eigenlijk ook niet meer veilig zijn.
Want dan was het wel zo tescripten dat je een script kon maken waarbij je een md5 hash in voerde en dat hij die dan "even" decoden.

[kenneth]

Erkens schreef op woensdag 04 januari 2006 @ 23:12:

wie zegt er dan dat rot13 _de_ methode is om te encrypten, maw lekker nuttige reply

Dude, het was een grap rot13 + rot13 = rot26 = geen encryptie

[Vinnienerd]

Hoe wordt dan voorkomen dat de hash niet wordt onderschept? Hash van ww + seed? Hoe weet het systeem dan het ww gedeelte als hij alleen de hash van het ww zelf heeft? Of wordt de hash dan weer geëncrypt?

[Erkens]

Vinnienerd schreef op woensdag 04 januari 2006 @ 23:23:
Hoe wordt dan voorkomen dat de hash niet wordt onderschept? Hash van ww + seed? Hoe weet het systeem dan het ww gedeelte als hij alleen de hash van het ww zelf heeft? Of wordt de hash dan weer geëncrypt?

Het systeem moet die seed dan geven, althans dat is het eenvoudigste. Natuurlijk kan je het dan nog steeds afvangen worden, echter met die seed en een hash van die seed samen het het wachtwoord kan je vrijwel onmogelijk "raden" wat nu dat wachtwoord is, simpelweg omdat die meegehashed is.
Wil je het allemaal nog meer secure hebben kan je ook nog gaan encrypten, bijvoorbeeld via een SSL verbinding.

kenneth schreef op woensdag 04 januari 2006 @ 23:19:
[...]

Dude, het was een grap rot13 + rot13 = rot26 = geen encryptie

Ben je alleen maar posts aan het scoren? ik geef toch niet voor niks die wiki link mee voor meer info over rot13?

[Voutloos]

Vinnienerd schreef op woensdag 04 januari 2006 @ 23:23:
Hoe wordt dan voorkomen dat de hash niet wordt onderschept? Hash van ww + seed? Hoe weet het systeem dan het ww gedeelte als hij alleen de hash van het ww zelf heeft? Of wordt de hash dan weer geëncrypt?

Veel antwoorden mogelijk: encryptie kan, seed, nonces.

Eigenlijk moet je altijd met een (desnoods vaste) seed hashen, zodat bestaande reverse lookup databases geen nut hebben. Tevens heeft de server dan ook geen hash in zijn DB staan die misbruikt kan worden op andere sites (omdat andere sites niet dezelfde seed gebruiken) en vervalt daarmee een klein stukje verantwoordelijkheid/gevoeligheid, het lekken van zo'n hash is dan alleen maar schadelijk voor je eigen site ipv alle sites waar user dezelfde pass gebruikt heeft.

[Reptile209]

Onno_Devine schreef op woensdag 04 januari 2006 @ 23:10:
Hmm intressant, maar wat ik dan best vreemd vind hoe werken systemen dan in een website die ook md5 gebruiken voor de veiligheid?, want als je pw decrypted opgeslagen is in de database moet hij die dan ook steeds weer decrypten als jij je wachtwoord invoert?
Zoja dan moet het toch ergens mogenlijk zijn om ze te kraken?, behalve met een brute force aanval, want deze kan maar tekstjes van circa 5 letters decrypten. (naja als je er geen dagen over wilt doen, 5 letters lukt hem vrij snel..)

Of zit ik nu veelst te moeilijk te denken?, en werkt een online inlog systeem gewoon zo:
Het ingevoerde password bij de reg. daar wordt een md5 decryptie van gemaakt en opgeslagen in de database.
en steeds als je inlogt wordt van dat woord een md5 decryptie gemaakt en vergeleken met de md5 hash in de database?

Meestal heb je met dat laatste gelijk, maar niet altijd . Om het inloggen wat verder te beveiligen (en het terugsturen van een afgeluisterde hash te voorkomen) wordt md5 ook vaak met een challenge-response gecombineerd. Voorbeeldje: ik wil inloggen op MSN (werkt ook met md5). Dan stuurt de servert me een code in plain text (de challenge). Daarmee moet ik bijvoorbeeld een string maken die er uitziet als "code"+"wachtwoord" en dat md5-en en terugsturen (de response).
Om die hash te kunnen checken, moet de server over mijn plain-text password beschikken. Dus slaan ze die intern op op een manier dat hij gecodeerd is, maar weer te decoderen is zodat de server het goede antwoord op de challenge kan berekenen.

Het password gaat nu gecodeerd (gehashed) over het net en de hash is slechts eenmalig te gebruiken, omdat de challenge steeds verandert (bijvoorbeeld door een tijdcode of een random getal te gebruiken). Met alleen de challenge kom je er ook nog steeds niet, omdat je dan een md5 moet gaan brute-forcen naar een string die bestaat uit een code (die je wellicht hebt kunnen afluisteren) en een onbekend password. Succes . Maar, toegegeven, helemaal onmogelijk is het niet en vanaf het moment dat je het password hebt, is het systeem natuurlijk weer zo lek als een mandje.

[Verwijderd]

Erkens schreef op woensdag 04 januari 2006 @ 23:30:

[...]

Ben je alleen maar posts aan het scoren? ik geef toch niet voor niks die wiki link mee voor meer info over rot13?

ik vond het anders wel een leuk grapje

edit:
waarom zou iemand trouwens "posts willen scoren"

[ Voor 13% gewijzigd door Verwijderd op 04-01-2006 23:44 ]

[Wolfboy]

Erkens schreef op woensdag 04 januari 2006 @ 23:00:
[...]

offtopic:
ben ik het niet mee eens, rot13 is ook een vorm van encryptie, hierbij is je output even lang als je input

Ik zei ook standaard, er zijn natuurlijk altijd uitzonderingen

Buiten dat kan ik rot13 ook niet echt een encryptie meer noemen eigenlijk
Maarja, als je kijkt naar wat het vandale er van zegt dan is dat het wel ja.

(en voor er zeurpieten komen, er zullen vast ook wel encryptiemethoden zijn die ook compressie ingebouwd hebben, zie gecodeerde rar bestanden)

[Vinnienerd]

En als je nou de seed onderschept? Dan kun je dus de gechallengede hash "rainbowen" en je pakt de collision die eindigt of begint met je seed.

[Voutloos]

Brute force kan altijd, maar dan moet je de berekeningen nog wel 'eventjes' doen. Zonder seed/nonce/one time padding/whatever kan je meteen zo'n DB raadplegen.

edit:
O wacht, bedoel je het zo:

Let wel op dat er heel veel input strings kunnen zijn welke die hash opleveren, dus je vind niet zomaar degene die begint/eindigt met die seed. Rainbow db's gaan vaak uit van karakters die veel voorkomen, om het aantal mogelijke inputstrings te beperken. Een inputstring met als substring 8273tr%@#290}{>:}||+$ (als dat de seed was) is wellicht niet van te voren in de rainbow database gezet.

[ Voor 60% gewijzigd door Voutloos op 05-01-2006 00:53 ]

[Vinnienerd]

Voutloos schreef op donderdag 05 januari 2006 @ 00:46:
Brute force kan altijd, maar dan moet je de berekeningen nog wel 'eventjes' doen. Zonder seed/nonce/one time padding/whatever kan je meteen zo'n DB raadplegen.

Met seed toch ook?

[GlowMouse]

Reptile209 schreef op woensdag 04 januari 2006 @ 23:34:
[...]
Voorbeeldje: ik wil inloggen op MSN (werkt ook met md5). Dan stuurt de servert me een code in plain text (de challenge). Daarmee moet ik bijvoorbeeld een string maken die er uitziet als "code"+"wachtwoord" en dat md5-en en terugsturen (de response).
Om die hash te kunnen checken, moet de server over mijn plain-text password beschikken. Dus slaan ze die intern op op een manier dat hij gecodeerd is, maar weer te decoderen is zodat de server het goede antwoord op de challenge kan berekenen. .

Nog beter: je wachtwoord wordt gemd5'd, code wordt achter de md5 gezet, en dat geheel wordt nog een keer gemd5'd (md5(md5(pass)+code)). Op die manier hoeft de server ook niet over het plain-text password te beschikken. Merk op dat md5(pass)+code vrij lang is, zodat het brute-forcen van wat je browser verstuurt zolang zal duren, dat het niet meer interessant is.

[Wolfboy]

Vinnienerd schreef op donderdag 05 januari 2006 @ 00:51:
[...]


Met seed toch ook?

Nee, als er een seed bij zit heb je niets aan zo'n DB aangezien die geen rekening houden bij mogelijke seeds.

[Erkens]

GlowMouse schreef op donderdag 05 januari 2006 @ 01:11:
[...]

Nog beter: je wachtwoord wordt gemd5'd, code wordt achter de md5 gezet, en dat geheel wordt nog een keer gemd5'd (md5(md5(pass)+code)). Op die manier hoeft de server ook niet over het plain-text password te beschikken. Merk op dat md5(pass)+code vrij lang is, zodat het brute-forcen van wat je browser verstuurt zolang zal duren, dat het niet meer interessant is.

Ik zou niet 2x md5'en, immers van een md5 "string" weet je hoe lang die is (32 bytes) en welke chars erin kunnen zitten: A-Z0-9 (en eventueel ook a-z)

[Voutloos]

Erkens: 16 bytes, oftewel 32 hexadecimale tekens zonder verschil tussen upper en lowercase. Je punt blijft natuurlijk wel staan.Wel kan de seed ook in de laatste hash erbij komen. Ook is een DB met alle mogelijk md5 strings als input nog steeds een gigantisch groot (cq, is het veel rekenwerk als je het one the fly doet).

En als je van tevoren een reeks seeds afspreekt (mogelijk dmv geheime functie) en die steeds maar 1x gebruikt heb je een zogenaamde 'one time padding' en mag je als aanvaller behoorlijk je best doen.

[ Voor 70% gewijzigd door Voutloos op 05-01-2006 09:23 ]

[Verwijderd]

9 Q: Is MD5 echt onomkeerbaar?
Ja, MD5 is echt niet omkeerbaar

Het is een wiskundig algorythme waarin onder andere een aantal maal wordt gedeelt en afgerond. Er wordt dus gewoon data weggegooit, en dat is absoluut niet meer om te keren. Denk an 8/4=2, maar ook 32/16=2 en zelfs 18/8=2.25 wat afgerond weer 2 is. Dus zelfs al weet je dat er door 2 werd gedeelt en de uitkomst gelijk is aan 2, dan kan kan het origineel bv nog liggen tussen 4.00000001 en 4.88888888, oftewel miljoenen/miljarden mogelijkheden.

Bron: YAPF FAQ (http://www.yapf.net/faq.php?cmd=100&itemid=190)

[Erkens]

Voutloos schreef op donderdag 05 januari 2006 @ 09:18:
Erkens: 16 bytes, oftewel 32 hexadecimale tekens zonder verschil tussen upper en lowercase.

True, maar als je bijvoorbeeld in een php webapplicatie (maar ook met diverse SQL servers en tal van andere programmeer talen) werkt dan krijg je een 32 bytes lange string terug, daarom zei ik ook "string" niet een binary "ding"
En natuurlijk kan je daar wel verschil in case hebben, ofwel het is lower, of het is uppercase (hoewel je natuurlijk altijd nog een BrEeZaH functie erop los kan gooien )

[Voutloos]

De werking van die BrEeZaH functie is makkelijk te achterhalen en helpt dus niet bij aan de entropie van de input string.

[.oisyn]

Erkens: Het gaat uiteraard niet om het aantal tekens of wat voor representatie gebruikt, maar dat een MD5 altijd 128 bits is en dat er dus maar max. 2¹²⁸ combinaties geprobeerd hoeven worden.

Hier heb je echter nog steeds niet aan omdat dat nog altijd heel veel is (3,4 * 10³⁸) en zelfs meer dan het aantal combinaties van verschillende wachtwoorden dat je kunt proberen (dat meestal bestaat uit ongeveer 8 chars van ongeveer 80 verschillende tekens per char (A-Za-z0-9 en een zooi leestekens) = 80⁸ = 1,7 * 10¹⁵

md5(md5(wachtwoord) + code) is dus over het algemeen 'veiliger' dan md5(wachtoord + code), even afgezien van de security-risk dat bij die laatste de server je wachtwoord in plain text moet weten.

[ Voor 18% gewijzigd door .oisyn op 05-01-2006 11:33 ]

[Erkens]

.oisyn schreef op donderdag 05 januari 2006 @ 11:31:
Hier heb je echter nog steeds niet aan omdat dat nog altijd heel veel is (3,4 * 10³⁸) en zelfs meer dan het aantal combinaties van verschillende wachtwoorden dat je kunt proberen (dat meestal bestaat uit ongeveer 8 chars van ongeveer 80 verschillende tekens per char (A-Za-z0-9 en een zooi leestekens) = 80⁸ = 1,7 * 10¹⁵

dat is alleen als je met bruteforce gaat proberen dat wachtwoord te achterhalen.

md5(md5(wachtwoord) + code) is dus over het algemeen 'veiliger' dan md5(wachtoord + code), even afgezien van de security-risk dat bij die laatste de server je wachtwoord in plain text moet weten.

mja, het is veiliger alleen in de zin van dat de server dat wachtwoord niet hoeft te weten in plain text, verder ook niet.

[.oisyn]

Wat ik probeerde te zeggen is dat

Erkens schreef op donderdag 05 januari 2006 @ 06:33:
[...]

Ik zou niet 2x md5'en, immers van een md5 "string" weet je hoe lang die is (32 bytes) en welke chars erin kunnen zitten: A-Z0-9 (en eventueel ook a-z)

niet klopt, het maakt gewoon niets uit of je 2x md5t of niet, aangezien het aantal wachtwoorden die je kunt vormen over het algemeen kleiner is dan het aantal verschillende md5 uitkomsten.

[ Voor 18% gewijzigd door .oisyn op 05-01-2006 12:06 ]

[Erkens]

.oisyn schreef op donderdag 05 januari 2006 @ 12:04:
Wat ik probeerde te zeggen is dat

[...]

niet klopt, het maakt gewoon niets uit of je 2x md5t of niet, aangezien het aantal wachtwoorden die je kunt vormen over het algemeen kleiner is dan het aantal verschillende md5 uitkomsten.

kan wellicht, maar ik doelde meer op bruteforce methoden, immers van die md5 string weet je hoe lang die is en welke mogelijkheden er zijn, terwijl je dat van een wachtwoord niet weet en in theorie _alle_ mogelijke mogelijkheden moet testen inclusief de mogelijkheden die je al had

[.oisyn]

maar ik doelde meer op bruteforce methoden

ik juist ook, en als je mijn voorlaatste bericht nog eens doorleest dan zie je dat ik dus aangeef dat een md5 string over het algemeen meer mogelijkheden heeft dan een wachtwoord gevormd door een mens. Een wachtwoord van 16 tekens wordt bijvoorbeeld al onwaarschijnlijk, en zelfs bij 16 tekens zijn er nog minder combinaties (omdat mensen niet voor elk teken de volledige 8 bit ascii-range gebruiken, wat het resultaat van md5 juist weer wel doet als je het binair zou representeren (waarvoor ook 16 bytes nodig zijn)).

Dus tenzij je een hoofdstuk uit LOTR als wachtwoord gebruikt zal het bruteforcen van je wachtwoord eerder resultaat opleveren dan het bruteforcen van de md5 van dat wachtwoord

[ Voor 21% gewijzigd door .oisyn op 05-01-2006 12:16 ]

[Erkens]

.oisyn schreef op donderdag 05 januari 2006 @ 12:13:
[...]
ik juist ook, en als je mijn voorlaatste bericht nog eens doorleest dan zie je dat ik dus aangeef dat een md5 string over het algemeen meer mogelijkheden heeft dan een wachtwoord gevormd door een mens. Een wachtwoord van 16 tekens wordt bijvoorbeeld al onwaarschijnlijk, en zelfs bij 16 tekens zijn er nog minder combinaties (omdat mensen niet voor elk teken de volledige 8 bit ascii-range gebruiken, wat het resultaat van md5 juist weer wel doet als je het binair zou representeren (waarvoor ook 16 bytes nodig zijn))

"over het algemeen" is gewoon vaag en niet echt een security argument
dat het zo vaak in de praktijk gaat zegt natuurlijk niks over hoe secure het daadwerkelijk is.

[.oisyn]

Je moest eens weten hoe effectief een dictionary attack in de werkelijkheid is. Leuk dat een wachtwoord in het hypothetische geval veiliger is, maar jij weet net zo goed als ik dat mensen niet zulke onmogelijke wachtwoorden kiezen, tenzij het echt veilig moet zijn. En als het echt zo veilig moet zijn kun je beter kijken naar andere manieren van hashing/encryptie dan MD5, waarvan een tijd terug al is gebleken dat het onveilig was.

[ Voor 70% gewijzigd door .oisyn op 05-01-2006 12:19 ]

[Erkens]

.oisyn schreef op donderdag 05 januari 2006 @ 12:17:
Je moest eens weten hoe effectief een dictionary attack in de werkelijkheid is.

true, een wachtwoord is gewoon geen goede/secure methode voor authenticatie...

[RagaBaSH]

Erkens schreef op donderdag 05 januari 2006 @ 12:20:
[...]

true, een wachtwoord is gewoon geen goede/secure methode voor authenticatie...

Wat is dan wel een goede/secure methode die ook nog eens gebruikersvriendelijk is?

[Erkens]

RagaBaSH schreef op donderdag 05 januari 2006 @ 13:57:
[...]

Wat is dan wel een goede/secure methode die ook nog eens gebruikersvriendelijk is?

Echt secure en gebruiksvriendelijk zijn 2 woorden die niet in 1 zin te gebruiken zijn.

[Nick The Heazk]

Vingerafdrukken en oogscans behoren tot de mogelijkheden. Deze zijn uniek voor elke mens. Ze zijn zelfs verschillend bij eeneiïge meerlingen. Of het gebruiksvriendelijk is, daar moet je zelf over oordelen.

Een vingerscan zou ik in ieder geval eenvoudig vinden. Voor zo ver ik weet zijn er al dergelijke apparaatjes in omloop.

[.oisyn]

Er is onlangs nog gebleken dat het nogal makkelijk is om dat soort apparaten te omzeilen. De techniek is ook vrij nieuw natuurlijk, dus ik zou sowieso eerst wachten tot het een beetje verder ontwikkeld is. Als we het echt over onkraakbare encryptie moeten gaan hebben dan kan quantum encryptie uiteraard niet ongenoemd blijven

[Orion84]

.oisyn schreef op donderdag 05 januari 2006 @ 16:14:
Er is onlangs nog gebleken dat het nogal makkelijk is om dat soort apparaten te omzeilen. De techniek is ook vrij nieuw natuurlijk, dus ik zou sowieso eerst wachten tot het een beetje verder ontwikkeld is. Als we het echt over onkraakbare encryptie moeten gaan hebben dan kan quantum encryptie uiteraard niet ongenoemd blijven

Mja, om dat te omzeilen moet je dan wel ff over de betreffende vinger beschikken of een kopie daarvan. En dat is niet echt helemaal triviaal voor de meeste mensen. Iig een stuk moeilijker dan een standaard dictionary attack tooltje starten.

[PanMan]

Wat ik altijd wel een mooie vergelijking vind, is de gehaktmolen bij een slager: Daar kan je een varken ingooien en er komt gehakt uit, maar andersom, er gehakt induwen om er een varken uit te halen gaat nooit lukken. Zo is dat bij hashing ook: je kan nooit uit het resultaat het origineel terughalen.
Dan nog een nummer voorbeeldje: Stel dat je algoritme alle cijfers van een getal optelt
Dan kan je, als de uitkomt 4 is, nooit weten of de input 4, 3+1, 2+2, of 1+1+1+1 is geweest. Zo werken, simpel gezegd, hashing algoritmes ook.

[alx]

Verwijderd schreef op donderdag 05 januari 2006 @ 09:29:
9 Q: Is MD5 echt onomkeerbaar?
Ja, [...]
Denk an 8/4=2, maar ook 32/16=2 en zelfs 18/8=2.25 wat afgerond weer 2 is. Dus zelfs al weet je dat er door 2 werd gedeelt en de uitkomst gelijk is aan 2, dan kan kan het origineel bv nog liggen tussen 4.00000001 en 4.88888888, oftewel miljoenen/miljarden mogelijkheden.[...]

en

PanMan schreef op donderdag 05 januari 2006 @ 17:28:
[...]
Stel dat je algoritme alle cijfers van een getal optelt
Dan kan je, als de uitkomt 4 is, nooit weten of de input 4, 3+1, 2+2, of 1+1+1+1 is geweest. Zo werken, simpel gezegd, hashing algoritmes ook.

Dat is allemaal helder, maar niet genoeg. Het gaat er niet alleen om dat je de input niet terug kan halen, maar ook dat je geen collision kunt vinden (andere input die zelfde hash oplevert). Een hash alg moet dus ook voorkomen dat je bij het omkeren iedere keer dat er meerdere mogelijkheden zijn, gewoon een mogelijkheid kiest (of eigenlijk: binnen afzienbare tijd een mogelijkheid kunt vinden die een collision oplevert).
Nr vb (1e quote): Ik kies gewoon 4.1 en ga verder met omkeren. Of 4.2 of 4.8888888.
Nr vb (2e quote): Ik kies gewoon 3+1. Of 2+2.
Boeit niet welke; als ik maar een collision krijg. Hoeft niet exact de oorspronkelijke input te zijn.

Dus mijn vraag is: Waarom vind ik tijdens een omkeerpoging (bijna) nooit een collision als ik gewoon een van de mogelijkheden kies?

[eamelink]

Bosmonster schreef op woensdag 04 januari 2006 @ 18:23:
Net voor de gein eens 2 hashes geprobeerd die ik hier in een systeem heb zitten. En zowaar 1 van de twee had ie het wachtwoord bij (nog het juiste ook, niet eens een collision).

Ik denk dat pas voor passwords vanaf een karaktertje of 30 gaat gelden dat je een aanzienlijke kans hebt dat er een kortere plaintext met dezelfde hash bestaat, dus zó toevallig is het ook niet dat je het password vond

[eamelink]

simulacrum schreef op donderdag 05 januari 2006 @ 17:56:
Dus mijn vraag is: Waarom vind ik tijdens een omkeerpoging (bijna) nooit een collision als ik gewoon een van de mogelijkheden kies?

Omdat de operaties zo gekozen worden dat de inverse operatie enórm veel tijd kost. In het geval van encryptie worden vaak twee priemgetallen genomen. Die zijn snel vermenigvuldigd. Maar het factoriseren van een groot getal in twee priemgetallen is een heidens karwei.

[JHS]

PanMan: Het is natuurlijk op zich wel mogelijk om alle moleculen zó te herschikken dat er weer een varken ontstaat, je hebt er alleen een ander apparaat voor nodig. Met hashes is het echter fundamenteel onmogelijk: alsof je het varken door de gehaktmolen duwt en een paar duizend cellen bij elkaar pakt. Dáárvan kan je natuurlijk nooit meer het originele varken maken .

[alx]

eamelink schreef op donderdag 05 januari 2006 @ 18:07:
[...]
Omdat de operaties zo gekozen worden dat de inverse operatie enórm veel tijd kost. In het geval van encryptie worden vaak twee priemgetallen genomen. Die zijn snel vermenigvuldigd. Maar het factoriseren van een groot getal in twee priemgetallen is een heidens karwei.

Daar heb je het over iets anders (denk ik). Dat is een berekening waarbij er maar 1 oplossing is, maar die is moeilijk te vinden. Dat wordt gebruikt bij pub key encr en sigs (oa RSA). Hier gaat het om operaties die niet omkeerbaar zijn, omdat er info verloren gaat. Ik kan me herinneren dat er bij md5 o.a. operaties inzitten als het max of het min nemen van twee of drie getallen. Dit is niet omkeerbaar, maar wel kun je mogelijke inputs kiezen gegeven de output; kennelijk leidt dit toch niet tot een collision. Waarom is me onduidelijk. Wellicht moet je vele inputs kiezen/gokken en kom je inconsistenties tegen.

JHS schreef op donderdag 05 januari 2006 @ 18:20:
PanMan: Het is natuurlijk op zich wel mogelijk om alle moleculen zó te herschikken dat er weer een varken ontstaat, je hebt er alleen een ander apparaat voor nodig. Met hashes is het echter fundamenteel onmogelijk: alsof je het varken door de gehaktmolen duwt en een paar duizend cellen bij elkaar pakt. Dáárvan kan je natuurlijk nooit meer het originele varken maken .

Het gaat er niet alleen om om het originele varken terug te krijgen. Ook het verkrijgen van een andere klomp gehakt die, als je die door de gehaktmolen zou halen, dezelfde berg gehakt oplevert als dat je het varken door de gehaktmolen haalt, mag niet mogelijk zijn. Die andere klomp gehakt zou dan een collision van het varken zijn. Dus md5(varken) = gehakt = md5(andere klomp gehakt)

[JHS]

simulacrum: Op zich een goeie toevoeging, alleen is het natuurlijk zo dat die paar duizend cellen, of eigenlijk liever moleculen, die je uit varken A haalt, voorschijnlijk ook wel in minstens één van alle andere mogelijke varkens zullen zitten .

[MrBucket]

simulacrum schreef op donderdag 05 januari 2006 @ 17:56:
Dus mijn vraag is: Waarom vind ik tijdens een omkeerpoging (bijna) nooit een collision als ik gewoon een van de mogelijkheden kies?

De bewerking die men loslaat op een stuk data om een hash te genereren worden ook wel trapdoor-functions genoemd (als ik me niet vergis): Om van een stuk data naar een hash te komen is heel eenvoudig, maar het omgekeerde is praktisch onmogelijk (zgn. 'unfeasible' in het engels). Vandaar de naam, je kan de functie maar in 1 richting uitvoeren, een inverse is nagenoeg niet te bepalen.

Zoals anderen al aangaven, een bepaald stuk data resulteert altijd in 1 en dezelfde hash, maar die hash terugconverteren resulteert in meerdere geldige mogelijke datablokken. Dat is ook logisch als je bedenkt dat er informatie verloren gaat tijdens het genereren van een hash (weinig bytes) uit een blok data (veel meer bytes).

En de truc zit hem er volgens mij in dat het bepalen van mogelijke blokken data die een bepaalde hash als resultaat hebben *zoveel* mogelijke resultaten geeft, dat de kans dat een bepaald blok data inderdaad de gewenste hash oplevert, voor elk mogelijk blok data ongeveer even groot is.

Ergo, als je een gegeven hash-waarde hebt waarvoor je een blok data zoekt die als invoer voor die hash heeft gediend, dan levert het terugrekenen van een hash naar een blok data zoveel mogelijke antwoorden op, dat het aantal antwoorden in dezelfde orde van grootte ligt als het totaal aantal mogelijke blokken data.

En waarom zou je nog een hele stevige berekening gebruiken als je met gokken een even grote (of liever: kleine) kans hebt om het juiste blok invoerdata te vinden? Helaas, je zult wel *ontzettend* vaak moeten gokken...

[Voutloos]

eamelink schreef op donderdag 05 januari 2006 @ 18:01:
[...]
Ik denk dat pas voor passwords vanaf een karaktertje of 30 gaat gelden dat je een aanzienlijke kans hebt dat er een kortere plaintext met dezelfde hash bestaat, dus zó toevallig is het ook niet dat je het password vond

Dat is een wilde gok, waarvan ik vermoed dat je flink te hoog zit.
Even een klein uitstapje, omdat het toch al een beetje over kansen gaat: Ik denk dat je te hoog zit en dat je verbaasd zal zijn over The Birthday Paradox. Deze stelt dat als je een groep van 23 mensen bij elkaar hebt de kans groter dan 50% is (een 'aanzienlijke kans dus') dat er een 'collision' is qua verjaardag. 23 is voor veel mensen een verrassend klein getal tov de 365 dagen in een jaar.

Illustratie Birthday Paradox (we zitten toch in /P&W ):

PHP:

 <?
function different_birthdays($n) {
  if ($n == 1) return 1.0;
  $x = different_birthdays($n-1) * (365.0-($n-1))/365.0;
  echo $n.' : '.(1-$x)."\r\n<br/>";
  return $x;
}

function different_birthdays2($n) {
  if ($n == 1) return 1.0;
  $x = different_birthdays2($n-1) * (65536.0-($n-1))/65536.0;
  echo $n.' : '.(1-$x)."\r\n<br/>";
  return $x;
}
echo "Birtday, 365 days\r\n<br/>";
different_birthdays(32);
echo "---\r\n<br/>";
echo "Birtday, 65536 outputs\r\n<br/>";
different_birthdays2(512);
?>

different_birthdays(32); zal printen wat de kans is (kans van 1 = 100%) en dat geeft oa deze regels output:

... 22 : 0.475695307663
23 : 0.507297234324
24 : 0.538344257915 ...

Dit is het exacte resultaat zoals dat bij elke uitleg van de paradox staat. Dus ik hoop dat je de werkwijze vertrouwt als ik nu de functie aanpas, voor de kans op een collision bij 2¹⁶ (=65.536) waarden. De aanroep van deze aangepaste functie geeft al de kans van 50% op een collision bij:

... 301 : 0.498418779388
302 : 0.500722489523
303 : 0.503023237328 ...

302 elementen. En getal welke 200x kleiner is dan die 65.536. Verassend klein huh?

Bovenstaande code kostte overigens slechts 1 seconde servertijd. De liefhebber mag hem aanpassen naar 2¹²⁸. Ik had er geen zin om, kost waarschijnlijk flink meer cpu tijd (geen idee of het nog in de categorie 'feasible' is) en er moet bij een getal als dit op overflows gelet gaan worden, wel denk ik dat de kans van 0.5 al ver voor het aantal mogelijkheden met 30 bytes (256^30), of desnoods 30 alfanumerieke karakters gevonden gaat worden. Note: Dit gaat wel om een willekeurige collision, maar dat geldt ook voor eamilinks post ('er bestaan een').

Voor zover het uitstapje.

Dan nog is het een behoorlijke klus om die collision daadwerkelijk te vinden. Elk element hashen is véél duurder dan de kans op een collision bij x elementen uit te rekenen.

En dat laatste is weer ontopic voor de sterkte van een encryptie/hashing algoritme. Een berekening met 1 bit meer is minder erg voor de legitieme gebruiker dan het groter worden van de exhaustive search (of desnoods hopen op die 50% kans) op 2x zoveel elementen door de aanvaller. Voor encryptie het aantal bits verdubbelen verhoogt de performance eisen in orde O, maar voor de aanvaller in een exponentiele orde.

[ Voor 38% gewijzigd door Voutloos op 05-01-2006 23:44 ]

[eamelink]

Voutloos schreef op donderdag 05 januari 2006 @ 23:34:
Dat is een wilde gok, waarvan ik vermoed dat je flink te hoog zit.

Dat is goed mogelijk

Even een klein uitstapje, omdat het toch al een beetje over kansen gaat: Ik denk dat je te hoog zit en dat je verbaasd zal zijn over The Birthday Paradox. Deze stelt dat als je een groep van 23 mensen bij elkaar hebt de kans groter dan 50% is (een 'aanzienlijke kans dus') dat er een 'collision' is qua verjaardag. 23 is voor veel mensen een verrassend klein getal tov de 365 dagen in een jaar.

Ik ken deze paradox ook. Echter, het gaat niet om het vinden van een collision waarvan beide strings klein zijn, maar om het vinden van een collision met een bepaalde string.

De birthdayparadox is vergelijkbaar met zoeken naar het kleinste collision paar, maar dat doen we niet. We zoeken naar een collision met een vooraf vastgestelde hash.

Om de birthdayparadox om te bouwen; we zoeken niet naar twee mensen die allebei op dezelfde dag jarig zijn; we zoeken naar één iemand die op míjn verjaardag jarig is (5 oktober). En je zal toch echt een groep van 183 mensen moeten hebben voordat die kans groter dan een half is

Note: Dit gaat wel om een willekeurige collision, maar dat geldt ook voor eamelinks post ('er bestaan een').

Nee, dat geldt niet voor mijn post. 'Er bestaat een' sloeg niet op een pair, maar op een andere plaintext die dezelfde hash oplevert

Voor zover het uitstapje.

Leuk uitstapje, maar weinig relevant

[ Voor 11% gewijzigd door eamelink op 06-01-2006 00:08 ]

[Voutloos]

Ok, iets te enthousiast gelezen, ik vind het gewoon leuk om het over Birthday Paradox te hebben. Het getal bij ombouwen naar 2^128 zal eerder 2^64 (wortel van outputmogelijkheden en dus voor zomaar een collision) ofzo zijn, dus dat is nog veel, maar is maar 8 bytes ipv 30 (wel is het korte vs lange string verhaal een beetje moeilijk rekenen hierbij).

[ Voor 9% gewijzigd door Voutloos op 06-01-2006 00:16 ]

[eamelink]

Voutloos schreef op vrijdag 06 januari 2006 @ 00:15:
Ok, iets te enthousiast gelezen, ik vind het gewoon leuk om het over Birthday Paradox te hebben. Het getal bij ombouwen naar 2^128 zal eerder 2^64 (wortel van outputmogelijkheden en dus voor zomaar een collision) ofzo zijn, dus dat is nog veel, maar is maar 8 bytes ipv 30 (wel is het korte vs lange string verhaal een beetje moeilijk rekenen hierbij).

En waarom neem je de wortel? Volgens mij is dat niet goed

Neem een random md5 hash (van een CD ofzo). Er zijn 2^128 mogelijke hashes. Gemiddeld moet je dus 0,5 * 2^128 plaintexts proberen voordat je een collision vindt.

Dat is dus 2^127, afgerond nog steeds 32 tekens . Dus als je password kleiner is dan 32 tekens is de kans erg klein dat er een kleinere plaintext bestaat . Die 8 klopt dus niet. Dat kon sowieso al niet, want er zijn mij geen 'natuurlijke' collisions bekend, terwijl tot een karakter of 12 zal alles wel gebruteforced zijn .

[Voutloos]

ik zeg nog speciaal tussen haakjes 'zomaar een collsion'. Die 8 gaat uit van bytes en niet van aantal alfanumerieke karakters of whatever. Verder is 50% geen garantie op het daadwerkelijk voorkomen, anders was het wel 100%.

[RickN]

eamelink schreef op donderdag 05 januari 2006 @ 18:07:
[...]


Omdat de operaties zo gekozen worden dat de inverse operatie enórm veel tijd kost. In het geval van encryptie worden vaak twee priemgetallen genomen. Die zijn snel vermenigvuldigd. Maar het factoriseren van een groot getal in twee priemgetallen is een heidens karwei.

De bloksizes waarop hashes werken zijn meestal niet zo groot dat het inverteren van operaties erg veel tijd kosten.

simulacrum schreef op donderdag 05 januari 2006 @ 17:56:
Dus mijn vraag is: Waarom vind ik tijdens een omkeerpoging (bijna) nooit een collision als ik gewoon een van de mogelijkheden kies?

Hash algoritmes worden geïnitialiseerd met een constante initialisatie vector, de IV. Je kunt wel alle operaties omkeren en telkens één van de mogelijkheden kiezen, maar als je dan aan het begin bent aangekomen en het getal dat je IV zou moeten zijn is niet gelijk aan de IV die in de standaard staat gespecificeerd heb je niks aan de message die je erbij hebt gevonden.

Voorbeeld, je hebt een hash en van daar uit ga je alle operaties van de hash functie omkeren en telkens één van de mogelijke input nemen. Op een gegeven moment ben je bij de laatste operatie aangekomen die je moet omkeren en dit is een vermenigvuldiging van de IV met de message.

Stel de waarde die je moet construeren is 25, en de IV is 7, er bestaat nu geen message die daaraan voldoet.

[alx]

En dat is een antwoord waar ik naar op zoek was. Terugrekenen levert dan idd niets op, zolang het aantal gok mogelijkheden niet in te perken is. Het gehakt en het trapdoor/priem verhaal overtuigde mij nog niet echt. Voor details zal ik wel eens in de specs of een boek kijken.

[Soultaker]

Ik denk dat je dit soort dingen pas echt kunt waarderen als je zelf daadwerkelijk een tijdje geprobeerd hebt om een inverse functie erbij te verzinnen.

[MSalters]

Voutloos schreef op donderdag 05 januari 2006 @ 23:34:
[vanaf 30 karakters password een fikse kans op een collision met fixed value]
Dat is een wilde gok, waarvan ik vermoed dat je flink te hoog zit.

Nee, hij is redelijk. Een password heeft tussen de 3 en 5 bits entropie per karakter, typisch, met uitschieters naar 6.5 (²log 96). Een password van N karakters heeft dus tussen de 3N en 6.5N bits entropie. Anders gezegd, er zijn ruwweg 2^6.5N passwords tot N karakters. Er zijn dan ruwweg 2^3.25N collisions binnen al die passwords, als 6.5N << 128. Het aantal unieke hashes is dus ongeveer 2^6.5N-2^3.25N , wat zo goed als gelijk is aan 2^6.5N. Zo goed als alle passwords zijn dus collision-free.

Met 30 karakters aan password, en een 128 bits hash zijn passwords dus zo goed als collision-free als N ongeveer 4 is, precies in de gangbaar gemeten range. 2^4*30 verschillende hashes, veel kleiner dan de 2¹²⁸ mogelijke hashes, dus naar verwachting maar 2^4*30/2 collisions, en dis een kans van 2^-4*30/2 = 2^-60 dat een gegeven password een collision heetf met een password van minder dan 30 karakters

[HarmoniousVibe]

Zou wat zijn als je een md5 kon dehashen. Heb jij toevallig $nieuwspel liggen? Ja ik stuur je wel even de MD5 toe.

[Confusion]

LB06 schreef op vrijdag 06 januari 2006 @ 21:29:
Zou wat zijn als je een md5 kon dehashen. Heb jij toevallig $nieuwspel liggen? Ja ik stuur je wel even de MD5 toe.

Je kan een md5 dehashen (edit: effectief tenminste, door te brute-forcen, niet algoritmisch). Alleen krijg je daarmee het origineel niet terug. Daar is hier ook al ellenlang over ge-emmerd

[ Voor 10% gewijzigd door Confusion op 06-01-2006 21:46 ]