Nieuwe berichten over mogelijke gebreken MD5-algoritme

Nadat we eerder deze week al berichtten over onveiligheden in het SHA-0-algoritme, blijkt nu hetzelfde probleem te bestaan met MD5. Een groep Chinese wiskundigen heeft op de Crypto 2004 conferentie onthuld dat ze een fout in het MD5 algoritme hebben gevonden waardoor het mogelijk is om een collision te berekenen. Hun ontdekking maakt het mogelijk om op een IBM P690-server in ongeveer een uur voor een gegeven hoeveelheid 'brondata' die een bepaalde MD5-hash oplevert, alternatieve data te berekenen die dezelfde hash genereert. Op een standaard pc zou dan zoiets mogelijk zijn binnen enkele uren, aldus C|Net.

Ook heeft een groep een dergelijke fout gevonden in een vereenvoudige versie van SHA-1. SHA-1 gebruikt volgens de specificaties 80 'rounds' om een hash te genereren, de vereenvoudigde (gekraakte) versie gebruikt 40 'rounds'. SHA-1 is nu dus nog veilig genoeg om te worden gebruikt als hashalgoritme voor digitale handtekeningen, maar dat zou zeer goed op termijn kunnen veranderen. SHA-1 wordt onder andere gebruikt door PGP een SSL, en een eventuele fout in dit algoritme zou relatief grote gevolgen kunnen hebben voor de betrouwbaarheid van deze twee standaarden.

De ontdekkingen die nu zijn gedaan zijn niet een logisch gevolg van de toenemende rekencapaciteit van computers. Het probleem ligt in nieuwe algoritmes die zijn ontdekt die een zwakheid van het hashalgoritme gebruikt om 'terug te rekenen'. Er werd verondersteld dat dit niet mogelijk zou zijn met (in ieder geval) SHA-1, en dat hashes die met dit algoritme worden gegenereerd alleen zijn te kraken door middel van de brute-force techniek, wat zelfs met de allersnelste computers onpraktisch lang zou duren. Nu het wellicht mogelijk is om met beschikbare computersystemen deze algoritmes te kraken is er een relatief groot probleem ontstaan.

Volgens experts is er nog geen reden om als gemiddelde computergebruiker zorgen te gaan maken, maar het is wel zo dat het MD5-algoritme niet meer als 100% betrouwbaar en onkraakbaar kan worden beschouwd. MD5 wordt onder andere gebruikt voor het versleutelen van passworden in diverse systemen. Voor dit doel is het algoritme in principe nog geschikt. Het wordt echter ook gebruikt voor het genereren van zogenaamde fingerprints van bestanden zodat de integriteit van bijvoorbeeld broncode kan worden gewaarborgd. Voor dit doel is het algoritme nu in principe niet meer geschikt. Onder andere het Apache-project en Sun Microsystems gebruiken MD5 voor dit doel. Veel andere (open-source) projecten gebruiken echter ook een variant van PGP voor dit doel die dus gebruik maakt van SHA-1.

Reacties (85)

Zijn er al "veilige" alternatieven?

RSA is veilig als je genoeg bits gebruikt. De cpu's zijn nu wel snel genoeg om passwords met RSA te versleutelen.

Dat is zeer veilig; 2048 bits RSA is zeker veilig tot ver na 2030+ en alleen nog dan kan het gekraakt worden met een hoeveelheid cpu tijd waar je u tegen zegt.

vergeef me als ik het fout heb hoor, maar MD5 en RSA zijn toch niet te vergelijken? MD5 is een hash- en RSA een public key algoritme. Dat zijn twee totaal andere toepassingen. Bij een hash moet het in principe (vrijwel) onmogelijk zijn om de brondata terug te krijgen (handig om integriteit van een bestand te garanderen of een wachtwoord onleesbaar op te slaan) en bij een public key algoritme moet dat juist WEL mogelijk zijn.

Wil je met RSA de integriteit van een bestand garanderen dan moet je toch voor elke downloader het bestand versleutelen met diens public key?

Ik heb ook het idee dat de kern misgelopen wordt.RSA is bedoeld (/geschikt) om een sleutel te maken (en wordt zelden gebruikt om data ook daadwerkelijk te coderen), niet om een hash mee te maken.

Wat ik echter niet helemaal begrijp is dat

Het wordt echter ook gebruikt voor het genereren van zogenaamde fingerprints van bestanden zodat de integriteit van bijvoorbeeld broncode kan worden gewaarborgd. Voor dit doel is het algoritme nu in principe niet meer geschikt.

Dit lijkt mij persoonlijk juist nog steeds een toepassing welke geen problemen zou moeten veroorzaken, het moet wel "heel" lek zijn (lijkt mij) wil men een bestaand bestand moedwillig kunnen "wijzigen" zodat het eenzelfde MD5 geeft.

Zeker om te kijken of er geen bitjes verkeerd zijn overgekomen bij het downloaden van een bestand moet het nog steeds uitstekend te gebruiken zijn lijkt me.

Kijk wat de platenmaatschappijen gedaan hebben toen ze erachter kwamen dat kazzaa alleen een hash berekende over de eerste X bytes .

Wanneer ze een blok data kunnen maken met eenzelfde md5 als een stuk van een iso of rar oid worden andere p2p programma's ook vatbaar voor deze sabotage methode.

Het grootste voordeel is dat het kraken twee keer zo lang gaat duren waneer je slechts 1 bit toevoegd. waneer je dus van 1024 naar 2048 gaat duurt het dus 2^1024(=een getal met meer dan 300 cijfers voor de komma ) keer zo lang.

@carvey

Misschien heb ik het wat onduidelijk geformuleerd, maar van 1024 naar 1025 bits duurt 2x zo lang. Van 1024 naar 2048 duurt dus 2x2x2x...2 = 2^1024 = dat grote getal keer zo lang ...

Dit soort algoritmes kraken zijn over het algemeen gebaseerd op bruteforce technieken. Dit komt gewoon neer op het dat (een slimme subset van) alle mogelijkheden worden geprobeert. Verdubbel je de mogelijkheden, dan verdubbelt de tijd die het duurt ook. Het maakt dus in principe niet uit hoe lang het algormitme zelf duurt (O(2) en O(3) zijn gelijk aan O(1) trouwens ).

@cavey:
Encryptie methoden zijn gebaseerd op het feit dat kraken een exponentiele berekening is (polynomiaal / intractable). Er is dus een basisgetal b en een exponent e. Het basisgetal b zegt iets over de complexiteit van het algoritme, en de exponent e geeft aan hoe lang de key is. Neem je een hele lange key dan is de uitkomst van b^e heel erg groot, waardoor het ondoenlijk is om het uit te voeren.

Ik ben geen wiskundige, maar ik heb toch het idee dat al die redenaties over "bitje toevoegen dan duurt het wel 2 tot de macht zoveel langer" aan alle kanten rammelt ...

Een bitje toevoegen aande key geeft dus b^(e+1), dus als b=2 dan is de uitkomst idd 2 keer zo groot, dus dat klopt wel.

Het specifieke getal 2 is een gok lijkt me. Je zult het algoritme moeten bestuderen om uit te vinden wat het daadwerkelijk getal is.

Je kan hooguit zeggen dat de complexiteit groter wordt, maar voor hetzelfde geld hit je de jackpot en ben je bij je eerste brute-force iteratie al klaar ...

Tja, das in veel gevallen wel waar denk ik, maar de kans dat dat gebeurd is extreem klein. De kans dat je in een dronken bui al je passwords weggeeft is veel groter.

ok

die mag je mij uitleggen...

1 bit toevoegen snap ik, dan ga je van 1024 naar 2048 mogelijkheden (maar eigenlijk gaan ze van 1024 bits naar 2048 bits... is toch even wat anders dan 1 bit toevoegen...)

anyways, dit gaat dan eesrt 2 keer zo lang duren, maar dan kom je met een berekening dat het 2^1024 keer zo lang gaat duren?! [toevoeging] Ai ai, anders lees ik eens goed ............

Ik snap het niet, de complexiteit van een algoritme wordt absoluut niet in tijdseenheden uitgedrukt.

Het was me eerder van de week ook al opgevallen, al dat gegoochel met bits, bytes, kwadraten en dat het dan wel zoveel keer langer gaat duren.

Maar eh...... weet jij of het algoritme in O(n) tijd geschijdt,? Of O(2) ? O(3) ? Of misschien wel logaritmisch/exponentieel werkt?

Je kan dan echt geen uitspraken doen van "2 keer zo lang" en daarna jezelf gewoon keihard tegen spreken met "2^1024 keer zo lang" ... [toevoeging] goed, wederom niet goed gelezen. haha...

Je kan hooguit zeggen dat de complexiteit groter wordt, maar voor hetzelfde geld hit je de jackpot en ben je bij je eerste brute-force iteratie al klaar ...

Ik ben geen wiskundige, maar ik heb toch het idee dat al die redenaties over "bitje toevoegen dan duurt het wel 2 tot de macht zoveel langer" aan alle kanten rammelt ...

[ok, [s] wordt dus niet herkend als strike.... goed, ehmz.. alles wat tussen blokken in staat moet je als niet geschreven beschouwen, maar ik laat het er toch maar bij staan...... ]

Het probleem is dat het in oa. de USA niet legaal te gebruiken is. Keys >128 bits zijn (nog) niet legaal daar. (Omdat ze moeilijker te kraken zijn door bepaalde overheidsinstanties denk ik).
Ik denk niet dat dat probleem vormt in Europa maar als je op internationaal niveau werkt kun je wel eens problemen krijgen.

Keys >128 bit niet legaal daar ?? Waar haal je deze wijsheid vandaan? In Frankrijk was het tot voor kort zo dat er geen encryptiesystemen mochten worden gebruikt die te grote keylengtes gebruikten (>= 48 bit oid), maar dat is dus al niet meer zo.
Het is wel zo geweest dat hoge encryptietechnieken niet UIT de USA geexporteerd mochten worden ... maar dat is ook al niet meer zo sinds 4 jaar ....

Ook RSA is niet per definitie veilig. Op het moment dat er weer iemand een briljant idee heeft kan RSA kraken net zo simpel worden als RSA versleutelen.

RSA blijft alleen veilig zolang het probleem van priemontbinding open blijft. Het staat echter absoluut niet vast dat er geen algoritme bestaat (significant sneller dan de huidige methoden) dat een getal in priemfactoren kan ontbinden.

Maar de potentiële "zwakte" van RSA is wel veel minder ondoorzichtig dan die van SHA-0/1 en MD5, dus vooralsnog zou ik m'n geld op RSA met veel bits zetten

Deze stelling gaat uit van het brute force idee.
De wiskundigen hebben juist een inteligente methode bedacht om het algoritme te kraken. In hoeverre deze methode nog geoptimaliseerd en verbetert kan worden en tot welke nieuwe algoritmes dit leidt is nog lang niet duidelijk.

Wel is duidelijk dat er een (fundamenteel) probleem is met hashes en aannames als tot ver na 2030+ niet meer zo zeker zijn als ze een tijdje terug leken.

RSA gebruikt natuurlijk een ander soort algoritme maar ook daar zitten zwakke punten in. Elk beveiligingsalgoritme loopt het risico op termijn door een paar (erg) slimme wiskundigen gekraakt te worden.

Volgens mij zal elk algoritme op een gegeven moment gekraakt kunnen worden. Als er maar genoeg tijd is. Echt 'veilige' alternatieven zijn er imho niet.

Versleutel-algoritmes zijn er juist op gebaseerd dat er niet genoeg tijd is om ze te kraken - mits ze correct zijn geïmplementeerd. En het is ook bewijsbaar dat het in dat geval niet mogelijk is de boel in redelijke tijd te kraken (behalve met een toekomstige quantum computer).

Zelfs met sterk toegenomen rekenkracht van (traditionele) computers schiet je nog weinig op, omdat iedere toegevoegde bit aan de sleutel de complexiteit van het ontcijferen verdubbelt (wat in de miljoenen jaren kan lopen met een redelijke sleutel). Je kunt dus vrij simpel de encryptie versterken terwijl verdubbeling van computer-rekenkracht lastiger is. Toegenomen rekenkracht komt eerder het versleutelen ten goede dan het 'kraken', zeg maar. Ofwel de krakers lopen altijd achter.

Ik vraag me trouwens af hoe lang DARPA al van deze fout afwist (het defensie onderzoekscentrum van de VS), gegeven dat PGP er 'last' van heeft, en algoritmische fouten de enige realistische manier zijn om versleutelde berichten te kraken (tenzij DARPA stiekum al een quantum computer heeft ). Als ze hiervan wisten vinden ze het vast niet leuk dat de rest van de wereld het nu ook weet.

Zoals je zelf al aangeeft met je quotes: Er is geen veilig alternatief.
Door de wet van Moore kan je met versleutelingstechnieken alleen een aantal jaar iets als veilig beschouwen. Zo zal over een jaar of 10 RSA-1024 wel niet meer veilig zijn en een aantal jaar daarna zal ook RSA-2048 eraan gaan.

Echt onkraakbaar is niet mogelijk, maar je kan wel zorgen dat het redelijk lang nog veilig is, door zoveel mogelijk bits te gebruiken, of iedere keer overstappen op andere technieken, zoals AES ofzo.

Lange keylengtes werken tegen Brute force attacks maar in principe niet tegen inteligente algoritmes.

Zie het als een deur. Als ik er een slot op zet is een dief een tijdje bezig de deur te openen. Zet ik er twee op duurt het wat langer. Geef ik hem mijn sleutels mee loopt die zo door. Wat deze wiskundigen nu ontdekt hebben is misschien de sleutelbos voor hash algoritmes.

Die komen er anders wel. Als MD5 een opvolger is van MD4, is dit dus geen revolutionaire ontdekking. Ik geloof zelf graag in onkraakbare systemen, maar als onkraakbare systemen na verloop van tijd allemaal kraakbaar blijken te zijn heb ik er vertrouwen in dat beveiligingen mee evolueren en weer voor een onbepaalde termijn voor een veilig gevoel zullen zorgen.

Volgens mij zal elk algoritme op een gegeven moment gekraakt kunnen worden. Als er maar genoeg tijd is. Echt 'veilige' alternatieven zijn er imho niet.

Heeft er iemand misschien een duidelijke uitleg hoe het precies werkt met deze algoritme? Ik zie het nu steeds vaker voorbij komen, en wil toch even weten hoe het precies werkt.

Ik kan me voorstellen dat bedrijven die gebruik maken van deze methodes zich nu wel een beetje zorgen maken.
Zijn er al wiskundigen bezig die een nieuwe methode aan het ontwikkelen zijn?

Het komt neer op een soort 1-richtings encryptie van gegevens.

Stel, jouw wachtwoord is ABCDE. Met een algoritme wordt dit omgezet in PQRTSUVW. Als funtie zou het dan heten Encrypt(ABCDE) = PQRSTUVW.

Die uitkomst is uniek, en alleen geldig met ABCDE als input. Echter, deze functie heeft geen omgekeerde. Er is dus geen functie Decrypt(PQRSTUVW) die ABCDE als uitkomst geeft.

Als jij nu je wachtwoord ingeeft ergens, wordt dat vergeleken met de ge-encrypte waarde. Die zijn gelijk, dus het wachtwoord was goed. Maar jouw originele wachtwoord is nergens opgeslagen, alleen de uitkomst van Encrypt(ABCDE).

Nu blijkt uit dit artikel dat er wel degelijk een functie Decrypt bestaat, die het mogelijk maakt om de berekening Decrypt(PQRSTUVW) = ABCDE uit te voeren.

Dat is dus een probleem

edit:

N.a.v. hieronder: jullie hebben gelijk, had het bericht iets te snel gelezen en niet helemaal doordacht wat er stond

Nu blijkt uit dit artikel dat er wel degelijk een functie Decrypt bestaat, die het mogelijk maakt om de berekening Decrypt(PQRSTUVW) = ABCDE uit te voeren.

Nee die bestaat niet, en is die is theoretisch zelfs onmogelijk, iets wat overigens niet zo heel moeilijk te bewijzen is. Uit een 128-bits hash van Windows XP SP2 ga je bijvoorbeeld echt geen .exe van 270MB krijgen door die "decrypt" functie van jou te gebruiken . Het gaat erom dat er een manier is om een FGHIJ te vinden waarvoor geldt dat md5("abcde") = md5("fghij"). Maar zelfs dat is op zich geen nieuws, want niemand heeft ooit beweerd dat dat onmogelijk is, het is zelfs gewoon inherent aan het algortime.

Een x-bit hash heeft namelijk gewoon een beperkt aantal mogelijke waardes, terwijl er wel oneindig veel data bestaat die gehashd kan worden. Hieruit volgt dat er ook oneindig veel data is die dezelfde hash oplevert. Dit is in principe niet erg, maar hoe makkelijker het is om een stuk data te vinden met dezelfde hash, hoe minder nuttig je hash is. Op een gegeven moment zullen processors sowieso krachtig genoeg worden om bruteforce een optie te maken, maar als het algoritme (dat random hoort te zijn) toch enigzins voorspelbaar blijkt te zijn, dan is er ineens een heel stuk minder processorkracht nodig om een 'match' te vinden.

Nu blijkt uit dit artikel dat er wel degelijk een functie Decrypt bestaat, die het mogelijk maakt om de berekening Decrypt(PQRSTUVW) = ABCDE uit te voeren.

(Boss)

Niet helemaal... er is nu een manier gevonden om de hash PQRSTUVW te laten berekenen op basis van ander gegevens, dus iets als Encrypt(FGRKJ)=PQRSTUVW.

Dit betekent dat ze met een gegeven MD5 als password hash zelf een bijbehorend wachtwoord kunnen genereren, die weliswaar niet hetzelfde is, maar wel werkt.

Ook is de integriteit van bestanden (die MD5-hashes gebruiken om dat te controleren) niet meer te waarborgen. Je kunt - theoretisch - virussen of andere malware verstoppen in zo'n bestand. Stel site xyz.com is een mirror voor een bepaald populair programma. Je download het programma, controleert het met de officiële hash en denkt dat alles goed is... totdat je erachter komt dat er rotzooi in zit. 't Wordt pas echt link als programma's met 'commentaar' opgevuld kunnen worden zodat de hash klopt...

Nu blijkt uit dit artikel dat er wel degelijk een functie Decrypt bestaat, die het mogelijk maakt om de berekening Decrypt(PQRSTUVW) = ABCDE uit te voeren.

Dat lijkt me niet, anders had je de beste compressie ooit: neem een 128 bit hash van een bestand van x gigabyte, en het uncompressen zou dan bestaan uit decrypten.

Per definitie onmogelijk.

In zijn geheel ook niet volledig waar. Zoals ik bij de vorige nieuwspost over SHA-1 / MD5 al (wat uitgebreider) berichtte heeft het inverse algoritme van een hashfunctie een vrije variabele n die dusdanig willekeurig gekozen kan worden dat elk mogelijke "oplossing" van de hash gevonden kan worden. Om dan een hash van 128bits naar een wel functionerend bestand van 128 miljard bits te "decoderen" moet deze n enorm hoog gekozen worden. Aangezien je deze n niet kan gokken kost dit dus ook weer tijd, zeer veel tijd aangezien de n in de orde van grootte is als de lengte van het bestand, maar het is theoretisch dus zeer zeker wel mogelijk

Bullshit, n valt onmogelijk uit de hash af te leiden. Theoretisch beslist onmogelijk, ook met "zeer veel tijd".

Het gokken van de juiste n komt overeen met het gokken van het originele bestand. Natuurlijk, je kunt alles wel gokken als je genoeg mazzel hebt, maar dat heeft niets te maken met de inverteerbaarheid van een hashing algoritme.

Dus jij schat de kansen vrij hoog in dat bij een willekeurige n een goed werkend exe bestand eruit getrokken kan worden en dat daarom onderscheid tussen het daadwerkelijke en het verkregen bestand niet bestaat? Geloof mij, ik heb het eerder gedaan bij "simpele" cryptfuncties en het is zeker wel mogelijk om middels een bepaalde heuristiek (hoe zit een exe in elkaar, hoe groot is de exe ongeveer?) de juiste data te verkrijgen. Het is een combinatie van voorspellen hoe de uitkomst zal zijn en de computer 'even' laten rekenen.

Hmm, is het dan niet mogelijk om aan de te hashen key (het password ABCDE) een extra tekst toe te voegen (de geheime key GOD)? Dan is het nog steeds onmogelijk om een fout password te genereren met dezelfde hash (zonder dat de key bekend is). Nadeel is natuurlijk wel dat er een extra key moet worden beheerd.

Er zijn velen anderen methoden zoals CRC(-32), SHA-1, SHA-2, TIGER en nog een hoop.
Zoek een goede vriend die het weet. Mijn beste buddy voor zulke dingen is Google. Al vind ik Wiki-pages soms leuker

Als ik het goed begrijp, opent dit algoritme een deur naar de mogelijkheid om vanuit een bepaalde message M een message M' berekenen die dezelfde hash heeft (een collision dus).

Dat betekent dus NIET dat je vanuit een hash een message kunt berekenen! Cq: (nog) geen consequenties voor passwords met MD5!!

Je spreekt jezelf een beetje tegen...

Je kunt met een gegeven MD5 misschien niet het originele wachtwoord achterhalen, maar er wel een genereren die werkt!

Nee, jij snapt het niet!

Je hebt eerst:
Message1 => Hash1

Met dit algoritme kan je vanuit Message1 een Message2 genereren die ook Hash1 heeft:

Message1 => Hash1
Message2 => Hash1

Dus je kan NIET vanuit Hash1 een message genereren!

Dus als je een passwordhash hebt, kan je er alsnog NIETS mee. Je kan wel als je het originele password hebt een ander password genereren met dezelfde hash.

Dit is dus vervelend in situaties waar je het originele bericht onderschept, dat aanpast naar een ander bericht met dezelfde signature (MD5 hash) en vervolgens doorstuurt.

Maar een message genereren uit een hash blijft gewoon lekker brute forcen .

In het originele artikel (PDF) staat nergens dat je vanuit een hash een message kan berekenen. Slechts vanuit een message een andere message...

Nee, dit klopt niet: wat men aangeeft is dat je een Message2 kunt genereren op basis van Hash1.
Zie dit zinnetje uit het artikel: "Het probleem ligt in nieuwe algoritmes die zijn ontdekt die een zwakheid van het hashalgoritme gebruikt om 'terug te rekenen'.".

Dat staat misschien in de Tweakers.net nieuwspost, maar dat is niet wat in het originele artikel (PDF) van die Chinezen staat...! Lees eerst dat eens - en begrijp het en test het.

stel je opent een database in een database partitie waar je eigenlijk niets te zoeken hebt ...
Je ziet allemaal geMD5-de passwords in de kolom 'password'. (Even tussen door ... het is extreem slecht om op deze manier met je paswords om te gaan als je er serieuze waarde aan hecht, maar dat is een ander onderwerp).
Je hebt nu dus de hash. Normaal kan je er niets mee, maar in het artikel staat dat je dus een collision kan berekenen vanuit de hash. Dit kan het password zijn, maar ook iets anders.
Dat password of 'het iets anders' kan je dan invullen in je password veldje en als je volledig vertrouwd op MD5 dan ben je het haasje en is het wachtwoord goedgekeurd, want de hashes zijn gelijk.

Als ik een stapje over sla, schop me dan even in de rug met een reply hierop

Hun ontdekking maakt het mogelijk om op een IBM P690-server in ongeveer een uur voor een MD5-hash 'brondata' te berekenen die dezelfde hash genereert.

Dit wil dus zeggen dat, áls je op één of andere manier de beschikking krijgt over een file met gehashte passwords (b.v. door één host te compromisen), je vervolgens originelen kunt gaan berekenen die je toegang geven op alle hosts waarop de gebruiker(s) hetzelfde password gebruikt.

Hun ontdekking maakt het mogelijk om op een IBM P690-server in ongeveer een uur voor een MD5-hash 'brondata' te berekenen die dezelfde hash genereert.

Dus ze gebruiken weldegelijk de Hash1 om Message2 te berekenen (en niet Message1 om Message 2 te berekenen, dat zou ook behoorlijk nutteloos zijn).

edit:
spuit 11

Hun ontdekking maakt het mogelijk om op een IBM P690-server in ongeveer een uur voor een MD5-hash 'brondata' te berekenen die dezelfde hash genereert.

Dan heb je toch een werkend password vanuit de MD5-hash zoals macnerd aangeeft.

Hehe, drie mensen met dezelfde quote-gedachte in 3 minuten.

En dan zeggen dat macnerd het niet snapt

Hashing van passwords werkt als volgt:
User1 registreert zich en voert een wachtwoord in.
Password1 -> Hash1, wordt opgeslagen in de database

Bij het inloggen wordt het ingevoerde wachtwoord gehashed en vergeleken met de hash in de database:
If Hash(Password1) = Password1HashInDatabase Then UserHeeftToegang.

Nu blijkt dus dat het mogelijk is om (relatief) snel een Password2 te genereren waarvan de hash hetzelfde is als van Password1.
Dan gaat dus gelden:

Hash(Password2) = Password1HashInDatabase

m.a.w. de hacker heeft toegang. Hij kan echter niet de originele wachtwoorden achterhalen, dus als mensen op meerdere plekken dezelfde wachtwoorden gebruiken, heeft de hacker niet ineens toegang daartoe. Maar hij kan zich wel toegang verschaffen tot iemands useraccount op een site, en alle toegangsrechten die daarbij horen.

Ik denk toch dat ik het wel snap

Met dit algoritme kan je vanuit Message1 een Message2 genereren die ook Hash1 heeft.

Nee, dit klopt niet: wat men aangeeft is dat je een Message2 kunt genereren op basis van Hash1.
Zie dit zinnetje uit het artikel: "Het probleem ligt in nieuwe algoritmes die zijn ontdekt die een zwakheid van het hashalgoritme gebruikt om 'terug te rekenen'.".

Dus als je een passwordhash hebt, kan je er alsnog NIETS mee.

Hier ben ik het ook niet mee eens, zie weer dat ene zinnetje uit het artikel.

Je kan wel als je het originele password hebt een ander password genereren met dezelfde hash.

Jaja. Waarom zou je als je het originele password hebt hiervan een ander password willen genereren met dezelfde hash? Je hebt dan immers al toegang!

No offense Burat, maar ik denk dat jij het niet snapt

Hun ontdekking maakt het mogelijk om op een IBM P690-server in ongeveer een uur voor een MD5-hash 'brondata' te berekenen die dezelfde hash genereert.

Ik denk het niet dus. De onderzoekers kunnen, gegeven een MD5-hash data berekenen die dezelfde hash geeft. Dat is dus nog een stap verder dan van de originele code, nieuwe code genereren.

STEL nu dat er een database gehackt wordt, op eender welke manier, waar de MD5 hashes van paswoorden worden opgeslagen, kan men nu, zonder echt het paswoord te weten, toch een geldig paswoord genereren.

Okey, het kan dus voorkomen dat Flipje88 en MijnPassword dezelfde hash opleveren als ik het goed begrijpt? En ze hebben nu software die als er een hash is van Flipje88 bijvoorbeeld MijnPassword kan vinden als zelfde hash.

Ik zie nog niet heel erg veel gevaar voor websites maar wat is de beste hash-techniek momenteel in php?

*Flipje88 en MijnPassword zijn even voorbeelden om het een naampje te geven. Ik snap dat niet 2 willekeurige wachtwoorden dezelfde hash kunnen opleveren).

Maar een message genereren uit een hash blijft gewoon lekker brute forcen

Een message genereren uit een hash is niet brute force, maar onzin. Je kunt van een file van 1MB een MD5 hash van 128 bits genereren (de fingerprint). Indien je brute force in staat zou zijn om dit terug te rekenen dan heb je een weliswaar langzaam maar super compressie algorithme. Er is niet slechts een message van 1MB bij een hash maar wel 64.000 verschillende messages.

Je kunt met een vingerafdruk een persoon identificeren, maar je kunt niet aan hand van die vingerafdruk de hele persoon reconstrueren (tenzij je misschien een handlezer bent ).

Burat:
Dus je kan NIET vanuit Hash1 een message genereren!

Dus als je een passwordhash hebt, kan je er alsnog NIETS mee. Je kan wel als je het originele password hebt een ander password genereren met dezelfde hash.

Wel dus, zie text uit topic:

Hun ontdekking maakt het mogelijk om op een IBM P690-server in ongeveer een uur voor een MD5-hash 'brondata' te berekenen die dezelfde hash genereert.

Dus bij Hash1 genereren zij een message (niet Message1, dat is onmogelijk) die Hash1 als md5 hash heeft.

Burat heeft wél gelijk hoor, het artikel op tw.net legt het wat fout aan de man.

Moest er een methode bestaan om van Hash1 naar String2 te gaan (wvg MD5(String2) = Hash1) dan zou MD5 nergens meer veilig zijn, ook al is String2 niet de originele string, het artikel maakt echter duidelijk dat er geen probleem is voor paswoorden etc.

Mensen, een hash is one-way en zal ook altijd zo blijven, ondanks deze ontdekking. En als jullie niet weten wat een collision in de cryptologie betekent, pak alsjeblieft ff een boek erbij

Een hash is one-way omdat het er vanuit gaat dat het d.m.v. wiskundige permutaties altijd een unieke hash uit basedata (message) kan genereren. Op het moment dat er uit verschillende basedata (Message M) dezelfde (nu niet meer) unieke hash gegenereert wordt, is er sprake van een collision. Dit is een potentiele zwakheid, maar dit zegt helemaal niets over het terugrekenen van een hash naar de (nu niet meer) unieke basedata.

Dit brengt wel consequenties met zich mee, aangezien je nu vatbaar wordt voor een 'man in the middle attack' ofwel 'impersonation', immers iemand kan zich nu anders voordoen als iemand anders, omdat er vanuit wordt gegaan dat de hash uniek is, wat dus nu niet meer is.

Zo, de les is nu over

Tuxie:
Mensen, een hash is one-way en zal ook altijd zo blijven, ondanks deze ontdekking. En als jullie niet weten wat een collision in de cryptologie betekent, pak alsjeblieft ff een boek erbij

Well duh.. Niemand beweert hier toch dat ze uit een hash de originele message kunnen halen?

De vraag is alleen of ze op basis van een hash EEN message kunnen genereren (dus NIET dezelfde message als het origineel, dat kan niet) dat die hash heeft.

Zoals het hier in dit bericht geschreven staat, kunnen ze dat inmiddels. Maar ik begrijp dat het verhaal een beetje verdraaid is, en dat ze alleen op basis van een message andere messages kunnen genereren die dezelfde hash hebben.

Heel erg leuk, maar nu nog een "zipje" die werkt en waar veranderde code in zit met dezelfde grootte en dezelfde md5 fingerprint.
Voordat ze dat voor elkaar krijgen is md6 (oid) er al.

Dus ik denk niet dat het erg gevaarlijk is atm, wel moet er natuurlijk op zoek worden gegaan naar een goede vervanger.

In het geval van zip bestanden is het idd. wat lastiger (maar niet onmogelijk) om dus een duplicate MD5 hash te krijgen.

Maar voor bijvoorbeeld sites waarbij de MD5 hash gebruikt wordt is het dus een stuk eenvoudiger om een passwoord te omzeilen.
Ook zijn er zat toepassingen die MD5 hashes gebruiken voor wachtwoorden. Deze kunnen dus vurnable worden als er een manier is om MD5 te omzeilen.

Het is niet omzeilen. Het is maken van een duplicate key. Dus als je iemand zijn MySQL databank kon opendoen en darn it, alle paswoorden zijn gehashed, kun je met hun algoritme binnen het uur/paar uur een paswoord vinden die een identiek MD5 key zal produceren. Het paswoord zelf kan compleet anders zijn, zolang de hashing maar dezelfde uitkomst heeft.

Op het moment dat je in die password db bent, heb je dat password eigenlijk al niet meer nodig...

Dat is niet helemaal waar. Op linux is het bijvoorbeeld mogelijk om voor de verschillende gebruikers de hashes te bekijken (/etc/passwd of ypcat passwd). Je bent dan inderdaad al in het systeem maar je kunt (als je de hashes weet) met deze kwetsbaarheid de passwords van anderen genereren. Ik zou trouwens niet weten of linux md5 hashing gebruikt voor passwords.

"linux" gebruikt geen versleuteling

De verschillende distributies wel:
RedHat is op MD5 overgegaan, SuSE en Debian bijvoorbeeld gebruiken standaard nog de crypt() methode (vandaar dat bij deze systemen standaard de passwords slechts 8 tekens lang zijn)

Omschakelen naar md5-passwords is niet moeilijk: in alle bestanden in /etc/pam.d de regels met "password required" en "pam_pwcheck" of "pam_unix2" als optie "md5" meegeven.

Voorbeeld: /etc/pam.d/passwd:
oud: password required pam_pwcheck.so nullok
nieuw: password required pam_pwcheck.se nullok md5

Dan nog een keer met "passwd" het password nieuw zetten, en je ziet in /etc/shadow een andere (langere) hash, en je shadow-bestand is om een veelvoud beter beschermd tegen password-cracker!

(bij oudere, komische systemen die NFS met password-auth gebruiken om op jouw linux-server te komen, kan je geen MD5 gebruiken, daarom hebben SuSE en Debian het nog niet standaard ingevoert)

Dat is niet helemaal waar. Op linux is het bijvoorbeeld mogelijk om voor de verschillende gebruikers de hashes te bekijken (/etc/passwd of ypcat passwd). Je bent dan inderdaad al in het systeem maar je kunt (als je de hashes weet) met deze kwetsbaarheid de passwords van anderen genereren.

Daarom gebruikt iedere niet-antieke Unix, inclusief GNU/Linux, al jaren shadow-passwords, waarbij de password-hashes in een aparte, niet voor users leesbare file staat.

Ik zou trouwens niet weten of linux md5 hashing gebruikt voor passwords.

GNU/Linux kan zowel gebruik maken van DES als van MD5 voor password-hashing.

Zip bestanden bevatten zelf ook een crc32 hash van elk bestand dat er in zit. Alhoewel deze hashing methode vrij zwak is, is het onwaarschijnlijk dat men een zipbestand zo kan aanpassen dat de CRC32 hashes kloppen, EN dat de MD5 hash gelijk blijft.
Deze CRC32 hashes zullen namelijk veranderen naar de inhoud van het bestand, en als je dus de inhoud net goed hebt, verandert die CRC32 hash, en klopt je MD5 hash nog niet.

Dit probleem zal dus denk ik eerder richten op P2P gebruik en het verifieren van de welbekende .iso bestanden.

De crc32 in een zip bestand wordt gebruikt om te controleren of de bestanden niet corrupt zijn geraakt en wordt meegeleverd in het zip bestand. De crc32 wordt helemaal niet gebruikt om te controleren of een bestand authentiek is. Als jij een bestand in een zip vervangt en je past vervolgens de checksum in het zip bestand ook aan dan kraait er geen haan naar.

Klopt, maar krijg jij dan nog de MD5 hash goed, als de crc32 hash moet kloppen bij het bestand? Die crc32 hash word ook mee ge-'MD5'-hashed hoor. Dan ben je wel iets meer dan een paar uur bezig.
Daarnaast zal waarschijnlijk ook de bestandsgrootte veranderen, dus moeten er nog een paar bits veranderd in je zipbestandje. Je kan dus niet gewoon wat bogusdata bedenken en dat in je zipje proppen, en dan klopt je MD5 hash weer.

ik begrijp niet waarom jij de crc32 bij het verhaal betrekt. data is data. die crc32 aanpassen is vanuit een checksum oogpunt niks anders dan 4 andere bytes in het bestand aanpassen.

het lijkt me sowieso onmogelijk om een collision te berekenen die enige nuttige betekenis heeft. in het geval van een wachtwoord is het idd een lek, een collision zal immers als geldig wachtwoord geaccepteerd worden. maar in het geval van integriteitscontroles lijkt het me zeer sterk dat je een collision kunt berekenen die ook nog eens een geldig zipbestand (en dan ook nog eens met kwaardaardige inhoud) oid is.

Als je 'even' wilt weten hoe zo'n algorithme werkt, dan ben je wel een middagje zoet met alle wiskundige bewerkingen die erin zitten. Maar het komt er op neer dat het een bewerking is die je maar 1 kant op kan. Na het uitvoeren van de bewerking kun je niet meer terug naar de oorspronkelijke data die je erin stopte.
Daarom is het zo ideaal voor wachtwoorden en fingerprints: er was geen enkele manier om van de hash terug te komen op een woord met dezelfde hash code. Ook nu kunnen ze nog niet het wachtwoord nog niet terug vinden, maar wel een string genereren die dezelfde hash uitkomst heeft.

Op deze site staat een RFC met nog wat uitleg over MD5:
http://userpages.umbc.edu/~mabzug1/cs/md5/md5.html

Lopen VPN routers nu ook gevaar? Die maken immers doorgaans gebruik van MD5 of SHA1-HMAC encryptie...
Of werkt dat dan weer anders?

Geen paniek. MD5 keys in netwerk packets (BGP, VPN en weet ik wat nog meer) zijn maar een beperkte tijd geldig. Het volgende packet, dus bijv. een BGP update, heeft een een andere MD5 value.

Mensen die hierboven op mij reageren: Lees ff het originele PDFje en niet de nieuwspost van Tweakers... Daar blijkt nergens uit dat je vanuit een hash een message kan genereren...

Als je een MD5 hash wil decrypten (of beter: de originele value wil kenne), dan gaat het nog veel sneller door gebruik te maken van zogenaamde rainbow tables (zeg maar voorafgecreërde md5-hash-lookup table), en dan duurt het zelfs geen uur, maar ...oeps is al klaar.

Daar gaat het hier niet om. Waar jij het over hebt is de Brute Force method. En als je een beetje slim bent gebruik je daarin nog een random salt waarde om te voorkomen dat iemand m.b.v. brute force je password kan achterhalen.

Dit is de omgekeerde wereld, namelijk twee verschillende waardes die dezelfde hash genereren. Dat is veel gevaarlijker, want dan hoef ik jouw password niet te kennen (decrypten), ik kan het gewoon met een ander overschrijven omdat die toch dezelfde hash genereert en die zal dus altijd door de check heenkomen.

Wanneer je een goeie hashfunctie denkt te hebben gevonden, kan het altijd nog fout gaan, zoals hier overduidelijk gebeurd is.

Daarom moet je ook gewoon fsum.exe gebruiken. Dat programma kan werken met meerdere hashfuncties tegelijk.

Dat één hashfunctie niet perfect is, kan ik geloven... maar de dag dat iemand uitvogelt hoe je alternatieve data genereert om zo de meerdere hashfuncties van fsum.exe voor de gek kan houden, is de dag dat de hel dichtvriest!

nu worden het wiskundigen genoemd en anders is het steeds hackers of crackers. tis maar hoe de wind waait he.

der zal ook vast wel iemand zijn die mijn handtekening kan nabootsen. en als ik een miljoen mensen laat raden naar mijn pincode zullen er geheid tussenzitten die het juist hebben.
edit-hiermee bedoel ik niet te zeggen dat deze wetenschappers ordinaire (als in: gewoon zomaar iemanden) lui zijn.

Helaas zien sommige mensen inderdaad niet in dat hackers, crackers, wiskundigen die iets ontdekken in 3 verschillende werelden leven.
Al zouden de hackers en wiskundigen nog wel redelijk in de buurt van elkaar kunnen komen.

De wiskundige berekent dat iets kan met bewijs en al hoe dat dan zou moeten. De hacker laat zien dat iets kan gebeuren en brengt het onder de aandacht. Hierna volgt de cracker, die voor zijn eigen gerief misbruikt maakt van dat wat er ook maar mogelijk is. Per definitie gaat de laatste met een schadelijk gevolg er van door.

Op zich heeft PipoDeClown best wel een punt.
In de states bijv geldt de DMCA.
Hierin staat dat het verboden is om een beveiliging te omzeilen.
Dit is duidelijk een geval van het kraken van iets wat over het algemeen als een beveiliging gezien mag worden. (beveiliging om te controleren of iets veranderd is)
Dat het hier gebruikt is om aan te tonen dat iets niet meer zo veilig is als gedacht, doet waarschijnlijk niets af aan dit gegeven.

Die Rus die hetzelfde deed voor de beveiliging van Adobe's E-book werd bij binnenkomst in de states ook opgepakt.
IMHO is dat niet zo heel erg verschillend met wat er nu is gebeurd.

* 786562 TD-er

In de states bijv geldt de DMCA.
Hierin staat dat het verboden is om een beveiliging te omzeilen.
Dit is duidelijk een geval van het kraken van iets wat over het algemeen als een beveiliging gezien mag worden. (beveiliging om te controleren of iets veranderd is)
Dat het hier gebruikt is om aan te tonen dat iets niet meer zo veilig is als gedacht, doet waarschijnlijk niets af aan dit gegeven.

Dat maakt zeker verschil: de DMCA verbiedt inderdaad het omzeilen van beveiligingen zoals jij het omschrijft, maar er zijn enkele uitzonderingen gedefinieerd. Zelfs het kraken van e-books valt onder die uitzonderingen, al is dat helaas pas ingevoerd nadat Dmitry Skylarov maanden in de Verenigde Staten gevangen heeft gezeten. Meer over die uitzonderingen is hier te lezen.

In de originele DMCA zaten ook al een aantal uitzonderingen, waaronder één uitzondering die nu van toepassing is. Ik citeer de Amerikaanse copyrightwetgeving, boek 17, hoofdstuk 12, sectie 1201, subsectie G, punt 2:

Notwithstanding the provisions of subsection (a)(1)(A), it is not a violation of that subsection for a person to circumvent a technological measure as applied to a copy, phonorecord, performance, or display of a published work in the course of an act of good faith encryption research if [...] such act is necessary to conduct such encryption research

Het aantonen van de onveiligheid van encryptie-algoritmes lijkt me hier zeker onder vallen. Wel is het zo dat je niet zomaar kunt beweren onder deze regeling te vallen: punt 3b stelt hiervoor bijvoorbeeld de volgende eis:

In determining whether a person qualifies for the exemption under paragraph (2), the factors to be considered shall include [...] whether the person is engaged in a legitimate course of study, is employed, or is appropriately trained or experienced, in the field of encryption technology

De DMCA bezorgt een hele berg narigheid, maar er is dus zeker wel nagedacht over nuttige uitzonderingen en er is zelfs een openbare mogelijkheid geweest om bij het Congres nieuwe uitzonderingen aan te dragen. Bij die gelegenheid is bijvoorbeeld het kraken van e-books gelegaliseerd voor de periode van drie jaar ofwel tot eind 2006.

Dat zou betekenen dat de States zand in hun eigen ogen gooit. Die Rus heeft eveneens aangekondigd dat het eBook systeem te kraken valt.
Echter heeft de Rus het live-on-stage even voorgedaan. i.p.v. zijn theorie weerleggen (wat hij al eerder had gedaan, echter werd er niet naar geluisterd). Die Rus heeft een gevaarlijker spelletje gespeeld door dit op deze manier te doen, omdat je live-on-stage een systeem kraakt.

Dat lijkt me toch fundamenteel iets totaal anders dan dat jij met je zakjapanner in de hand er achter komt (plus wat kladpapier) dat het MD5 algoritme een mogelijke bug/onveiligheid in zich draagt.
Er wordt geopenbaard dat het MD5 gebeuren haken en ogen heeft. Er is geen systeem met met MD5 sleutels gekraakt. Er is met een opstelling van hunzelf een zelfde hash berekent als een hash die al van te voren bekent is gemaakt en hiervan is aangetoond dat een hash naast de bedoelde oorsprong ook een andere kan hebben, dus dat je niet je wel bekende MD5 garantie meer kan dragen voor 100% unique uitkomsten.

Gooi alle intellectuelen maar de bak in voor hun bijdrage. Dan hou je alleen nog maar managers en politici over. Dat is fijn

Dat dezelfde hash meerdere malen voorkomt is niet meer dan logisch. Een MD5 hash is altijd 128 bits lang, dus 2^128 mogelijkheden.
Een reeks van 129 bits geeft al 2^129 mogelijkheden, dus moet het zo zijn dat er verschillende reeksen van 129 bits zijn die dezelfde MD5 hash hebben.
Tot nu toe werd echter gedacht dat er voor het omgekeerde (van een hash naar een waarde die die hash heeft) niet beter te doen was dan gewoon van een heleboel waardes de MD5 hash uitrekenen tot er eentje overeenkomt (brute force dus)
Echter zo'n methode is er nu gevonden, en kan bij een gegeven hash, relatief snel een bericht berekenen.

Dit algoritme wordt niet door je alledaagse hacker of cracker gekraakt hoor... Hier heb je wel degelijk een serieuze wiskundige achtergrond voor nodig.