SHA-0 niet 100% veilig, ook MD5 en SHA-1 wellicht zwak

Op Slashdot is te lezen dat op een conferentie over cryptografie is bewezen dat het hashingalgoritme SHA-0 niet veilig is. Dit is bekend gemaakt op Crypto 2004, een conferentie over cryptografie die momenteel plaatsvindt in Santa Barbara in de Verenigde Staten. Ook gaan er op diezelfde conferentie geruchten dat, door aanpassing van de methode die is gebruikt om te bewijzen dat SHA-0 onveilig is, ook te bewijzen is dat SHA-1 en MD5 mogelijk niet veilig zijn. Indien dit laatste waar is, zou dit grote gevolgen hebben voor diverse instanties en systemen die gebruik maken van hashing om de betrouwbaarheid van gegevens te waarborgen. Hashing-algoritmes worden onder andere gebruikt voor het versleutelen van passwords, e-mail en documenten. Ook worden ze vaak gebruikt voor het 'ondertekenen' van bestanden, zoals cd-rom images en gecomprimeerde archieven. SHA-1 is op dit gebied de meest gebruikte techniek.

SHA-0 is een zogenaamd hashing-algoritme wat inhoudt dat het voor een bepaalde reeks bytes (bijvoorbeeld een bericht) een tekenreeks berekent van een vaste lengte. Deze laatste tekenreeks kan worden gebruikt om te controleren of het verzonden bericht ongewijzigd is. SHA-0 blijkt nu echter niet betrouwbaar voor dit doel omdat bewezen is dat het mogelijk is met een algoritme een zogenaamde 'collision' te bepalen, wat betekent dat voor twee verschillende berichten (tekenreeksen) dezelfde hash wordt gegenereerd. Gezien het feit dat hashes een vaste lengte hebben, is het onvermijdelijk dat er twee dezelfde datasets zijn die dezelfde hash opleveren. Het is echter niet veilig als er een methode bestaat waarmee voor een bepaalde dataset eenvoudig een reeks tekens kan worden berekend die dezelfde hash hebben.

Wat nu is ontdekt is op zich nog niet heel kwalijk voor de veiligheid van systemen en gegevens. Het is echter in het verleden gebleken dat ontdekkingen zoals deze de weg vrij maakt naar de ontdekking van algoritmes waarmee geavanceerdere datamanipulatie mogelijk is die het hashing-algoritme niet opmerkt. Zodra er een algoritme beschikbaar is waarmee voor een bepaald bericht extra data kan worden berekend zodat het een gewenste hashwaarde krijgt, is het betreffende hashingalgoritme onbruikbaar. In het verleden is MD4, een eenvoudigere voorganger van MD5, ook 'gekraakt'.

Reacties (68)

[Verwijderd]

Veilig is in de digitale wereld een illusie. Relatief veilig is het enige waar je je op kunt richten bij het verzenden van e-mail, het electronisch regelen van je bankzaken en het beveiligen van je netwerk.

Ondanks dat het aantonen van zwaktes en het kraken van bestaande encryptie-systemen de enige benchmark zijn die we hebben wordt het deelnemen aan zulke benchmarks over het algemeen als zinloos bestempeld. Informatie over het nut van het blijven testen van onze digitale veiligheid is bijvoorbeeld te vinden bij RSA labs, waar dan vervolgens weer invulling aan wordt gegeven door bijvoorbeeld Distributed.net en hier misschien meer van toepassing, MD5 Crack die er dan een wedstrijdvorm van maken.

Degenen die zich wellicht wat meer willen verdiepen in de mogelijkheden die er tegenwoordig zijn om ongelofelijke hoeveelheden processorkracht op één taak te zetten, kun in ieder geval hier terecht.

[dmantione]

Ze vergeten te vertellen dat voor het bepalen van het botsingsbericht 2^51 berekeningen nodig waren.

Alhoewel 2^51 berekeningen "betaalbaar" uit te voeren is, voer je dit nog niet direct op je pctje uit.

[Verwijderd]

toch niets nieuw onder de zon ?

data.bin (5MB) kan exact dezelfde hash hebben als winamp.exe (2MB)

de kans is heeeeeeeeeeeeeeeel klein, maar MD5 heeft nooit beweerd dat de hash voor elk bestand anders is ...

ofwel klopt de tekst niet bij de titel ofwel heeft men het warm water opnieuw uitgevonden.

Het is toch EEN van DE kenmerken van hashes, dat ze voor verschillende ingaven, hetzelfde resultaat kunnen hebben .....

(na het NOG eens gelezen te hebben )
is dit gewoon een bevestiging van wat theoretisch geweten is, dat hashes gelijk kunnen zijn
alleen hebben zij het dus bewust proberen te faken .. bravo bravo
het is een spelletje, zolang de effort om zoiets te doen groter is dan wat het opbrengt, gebeurt er niets

hoe is dit op te lossen? door hash keys van 8096bit ofzo te nemen

maar dat het niet 100% veilig is, zoals in de titel, dat is niets nieuws. Het is nu gewoon eens aangetoond dat het bewust kan gefaket worden

[kris_112]

Het feit dat er (oneindig veel) berichten met dezelfde hash bestaan is niet zozeer het probleem, maar het feit dat er daadwerkelijk een collission gevonden is wel. Het idee van een hash is dat het bij een bepaalde hash-value ondoenlijk is om een ander bericht te vinden met dezelfde hash-value. Ik weet niet precies hoe dit zit bij SHA-0, maar bij MD5 bijvoorbeeld zou je na het proberen van 2^64 verschillende berichten gemiddeld wel een collission moeten vinden. Dit is echter met de huidige computers ondoenlijk. Deze kerel heeft een methode gevonden die via een of ander algoritme veel sneller dan via brute-force een collission kan vinden. Dat is meer het probleem aangezien het nu dus niet meer ondoenlijk is om een collision te vinden.

[Olaf van der Spek]

weet je de specs (slashdot site werkt hier niet)
hoeveel vlugger het is in vergelijking met bruteforce

SHA0 hashes zijn 160 bits, dus na 2^80 tests heb je waarschijnlijk een collission gevonden (birthday paradox).
De complexiteit van deze nieuwe method is 2^51, wat dus 2^29 (ongeveer 1/2 miljard) keer sneller is.

[Verwijderd]

weet je de specs (slashdot site werkt hier niet)
hoeveel vlugger het is in vergelijking met bruteforce

[Jace / TBL]

SHA0 hashes zijn 160 bits, dus na 2^80 tests heb je waarschijnlijk een collission gevonden (birthday paradox).

Uhm, 2^159 dacht ik?

[jesternl]

@ Olaf van de Spek:

De birthday paradox is het feit dat er slechts 23 mensen nodig zijn om de kans dat twee ervan op dezelfde dag jarig zijn groter dan 50% te laten zijn. Hoewel het geen echte paradox is wordt het een paradox genoemd omdat je gevoelsmatig verwacht dat er veel meer mensen voor nodig zijn.

Hoe relateerd dat aan jouw stelling dat je na 2^80 waarschijnlijk een collision hebt?

[Hakker]

ach zo moeilijk is het niet met brute force is alles te kraken zie ook het RC5 project en dergelijk het is toen ook aan het licht gekomen dat als je speciaal geschreven alogritmes gebruikt inplaats van 5 jaar iets van 2 maanden met 16 pcs nodig had om het te kraken.

Alles is te kraken maar dan ook echt ALLES. zelfs 8Kbit codes zoals eerder aangegeven. Het gaat er alleen maar om dat een code zolang ongekraakt blijft dat het rendabel is om het te gebruiken. Zelfs in de huidige vormen is SHA-0, SHA-1 en MD5 nog meer dan veilig genoeg om het uniek te maken. SHA-0 misschien de minste, maar nog genoeg daarnaast de opvolger is er al en zo zal MD5 over enkele jaren heus wel opgevolgd worden door MD6 met misschien een code bestaande uit 128bits ofzo.

Wat dat betreft vind ik het persoonlijk geen schokkend nieuws. Het is imo pas schokkend als het binnen een jaar van ingebruikname al gebeurd.

[Olaf van der Spek]

Uhm, 2^159 dacht ik?

Nope.
Ik dacht het niet.

Hoe relateerd dat aan jouw stelling dat je na 2^80 waarschijnlijk een collision hebt?

Het is toch precies hetzelfde probleem in een ander jasje?
365 -> 2^160
sqrt(365) -> 2^80

Je berekent van 2^80 inputs de hashes (kost *veel* RAM). Die hashes (/ datums) moeten uniek zijn, anders is er een collision.


Ik ben bang dat ik het ook niet verder perfect kan uitleggen.

[Jace / TBL]

Het is toch precies hetzelfde probleem in een ander jasje?
365 -> 2^160
sqrt(365) -> 2^80

Je berekent van 2^80 inputs de hashes (kost *veel* RAM). Die hashes (/ datums) moeten uniek zijn, anders is er een collision.

Ik ben bang dat ik het ook niet verder perfect kan uitleggen.

Ja ho ff, je hebt inderdaad naar verwachting 2^80 hashes nodig om 2 dezelfde tegen te komen. Maar daar gaat het hier niet om, en bovendien "kost *veel* RAM" is nog een understatement: alle harddisks die er bestaan komen nog 10^veel bits tekort om dat op te slaan.

Het gaat niet om het vinden van zomaar 2 inputs met dezelfde hash, maar om het vinden van een input met een bepaalde hash (om een password of wat dan ook te faken). Bij brute-force is het verwachte aantal pogingen wel degelijk 2^159.

[Olaf van der Spek]

Het gaat niet om het vinden van zomaar 2 inputs met dezelfde hash, maar om het vinden van een input met een bepaalde hash

kris_112 had het over het vinden van een collission, niet over het vinden van een input bij een bepaalde output.

En ook een collission is al 'vervelend'.

[Jace / TBL]

Tuurlijk niet, een collision an sich maakt toch geen bal uit? Dat ze bestaan was sowieso duidelijk, en het hebben van een concreet voorbeeld verzwakt het algoritme niet.

[peterroelen]

Olaf zegt er duidelijk bij: Birthday Paradox.
Als je dat dus op zoekt:
http://en.wikipedia.org/wiki/Birthday_paradox
dan lees je dat je inderdaad na de helft al zeer waarschijn een collision gevonden hebt.

[Jace / TBL]

2^159 is de helft

[Verwijderd]

Dus mijn torrents zijn nog veilig voor het RIAA gespuis?
Of zijn die bewerkingen binnen een dag met een supercomputer te doen?

[dmantione]

Dat is moeilijk te zeggen omdat niet bekend is wat 1 berekening precies inhoudt. Als het een paar op- en aftrekkingen is kan dat vele factoren schelen met ingewikkelde iteratieprocedures.

Mijn ervaring met programmeerwedstrijden is dat een aanvaardbare hoeveelheid berekeningen in de orde van de 1 miljard is; dat wil zeggen dat als m'n oplossing meer dan 1 miljard berekeningen nodig had het een aanwijzing was dat m'n oplossing niet deugde.

Op een programmeerwedstrijd ligt de aanvaardbare tijd die een programma erover doet in de orde van 30 a 60 seconden. Voor het kraken van een hash zet je wellicht veel meer hardware in en neem je langer de tijd.

[Verwijderd]

Ik denk niet dat dat een factor is die megenomen wordt in het vaststellen van de veiligheid.
Men is niet alleen bang voor individuele "hackers" maar ook voor criminele organisaties, of gewoon concurenten met slechte bedoelingen... die wel wat meer dan 1 PCtje tot hun beschikking hebben

[GlowMouse]

Dit was ooit te verwachten. Maar wanneer je in bijvoorbeeld een e-mail de tekst "Met vriendelijke groet" wilt vervangen door een tekst 'met kwade bedoelingen', en dat alleen kunt vervangen door "9cCé>x04Mx0#l3-Z=/", valt dat snel genoeg op. Doelgericht vervangen lijkt me een stuk moeilijker. Broncode manipuleren lijkt me om dezelfde reden ook onmogelijk, omdat een rootkit inbouwen (om maar wat te noemen) toch ergens moet 'passen'.

[TD-er]

in een aantal compressie algoritmen is ruimte om rotzooi toe te voegen die bij het uitpakken niet uitgepakt wordt. Je kunt in de table-of-content-tabel een veel grotere offset plaatsen, waardoor je een lege ruimte hebt die niet uitgepakt hoeft te worden.
Hierin kun je dus echt alles kwijt.
Het probleem is natuurlijk dat vaak niet alleen de hash bekeken wordt, maar ook de filesize, dus dan is het serieus veel moeilijker om een archive te manipuleren.

[the_stickie]

mja maar zo'n dingen zijn niet de enige manier om dit te misbruiken. Stel longhorn komt volgende week uit op 4 cd's (stel stel stel) en MS verspreidt zélf de iso's op filesharing netwerken, maar op cd 4 staat een exe bestand (met de zelfde hash als het origineel) dat normaal zorgt dat je kan inloggen (of whatever) en dat werkt niet.

Gevolg heel wat tweakers (en anderen) zullen die eerst vrijgekomen iso's willen downen,er ook in slagen (terwijl ze downen verspreide ze verder).

En iederen ie het illegaal wil downen moet eersteen versie downloaden en ze proberen te installeren voor je weet of het nu eigenlijk wel de juiste zijn. Zelfs de filesharing programma's weten het niet, zodat mensen die een goeie versie willen downen ook beginnen te downen van de verkeerde versie.. lijkt me behoorlijk

het is idd de vraag hoe gemakkelijk je dat zomaar kan aanpassen en of je echt andere code kan verstoppen (dat kan vast en zeker).

[Countess]

een werkend exe bestand vinden met de zelfde hash als het orgineel is extreem moeilijk zo niet ondoenlijk.
en dan moet het ook nog exact de zelfde groote hebben wil het niet opvallen. mission impossible eigenlijk.

[Verwijderd]

Volgens mij valt dit wel mee. Stel dat het om een security programma gaat van 100KB en ik sloop alle beveiliging en vervang het door mijn trojan van 10KB + een dummy datasegment waarmee ik de resterende ruimte opvul met random bytes. Ik zou dan in principe deze dummy bytes zo kunnen aanpassen dat ik dezelfde hash krijg. In praktijk is dit brute force bijna onmogelijk omdat ik teveel vullingen moet proberen om dezelfde hash te krijgen. Als ik echter een versnelde zoekmethode heb dan zou dit misschien wel kunnen lukken en heb ik een bestand met dezelfde hash en bestandsgrootte.

[rwwh]

Valt best mee hoor: als je een vastgestelde 160 bits hash moet maken, heb je daarvoor maar 20 bytes "vrij spel" nodig, bijvoorbeeld de laatste 20 bytes van een bestand. Dat is zelfs veel minder dan tyler en anderen hier voorstellen. In hoeverre deze nieuwe kraaktechniek werkelijk in staat is om die 20 bytes snel te "berekenen" is dan de werkelijke vraag.

Zelfs als we een "word salad" zouden willen gebruiken zoals we die in moderne SPAM nogal vaak zien, zou met een lijstje van 1024 verschillende woorden een setje van 16 woorden in willekeurige volgorde "bijna" alle mogelijke verschillende hashes moeten kunnen maken. Deze 16 woorden te kiezen lijkt me alleen nog een slag moeilijker dan 160 random bits....

[kakanox]

Maar 20 bytes nodig om een hele hash te bepalen? Leg dat eens uit, want ondanks dat ik het niet kan aantonen of uitleggen geloof ik er geen zak van.

Dan heeft het hele principe van hashes berekenen toch geen zin?

[Verwijderd]

Ja maar als je MS SP2 vervangt door een programma wat je Harddisk formateert merk je het pas nadat je harddisk geformateerd is.

[martijnvanegdom]

2^51 berekeningen..
Stel, we gebruiken de Nec Earth Simulator in Japan. Deze heeft een snelheid van 35,68Tflops (35,68 'vliegende komma' berekingen per seconden)
En elke berekning bestaat uit 1 van deze floatpoints.

Dan kunnen we in 16,326856003986048829098156452417 uur een SHA-0 ontbinden:

( 2^51 / (35,68 * 1024^3) ) / (60 * 60) = 16,326856003986048829098156452417

Als met deze snelheid codes te kraken zijn dan is het absoluut niet veilig meer.. Natuurlijk heeft een criminele organisatie niet zoveel kracht beschikbaar.. Maar parallele distributie via het internet kan zo krachtig wezen.. En spyware je encryptie laten kraken kan erg leuk zijn..

[Confusion]

Zoveel flops kan het ding lang niet effectief benutten om de sleutel te kraken. Allereerst is het de pieksnelheid, ten tweede is er overhead en ten derde zijn 2^ 51 berekeningen ongelijk aan 2^ 51 operaties.

[boner]

zijn die 2^51 berekeningen het maximale aantal, een redelijk gemiddelde of een worst case aantal?

Ik kan mij voorstellen dat zoiets nogal uitmaakt,

[TD-er]

Tflops is 1000^4

k=1000
M=k^2
G=k^3
T=k^4

[the_stickie]

het concept "veiligheid " in de digitale wereld moet altijd bijgeschaafd worden. Er komen immers altijd snelllere systemen en betere software. Sleutels met een enorme lengte die nu "onkraakbaar" zijn, zijn binnen een aantal jaar niet veiliger dan een pincode.

Om veilig bezig te blijven zullen er dus ook altijd krachtigere algoritmes moeten bedacht worden, met steeds meer voorzorgen om bepaalde soorten kraken" te voorkomen. Das inherent aan dit soort veiligheid.

[Martin Sturm]

Dit is dus niet waar. Een bezoeker van Slashdot rekent voor dat een 256-bit (goede) encryptiesleutel onkraakbaar is (bruteforce) met wat voor computer dan ook (tenzij computers in een andere tijdruimte gaan werken).

[GiLuX]

zoals een quantum computer...?

bill gates zei ooit dat iedere pc genoeg aan 256KB zou hebben....

never say never!

[AntiChris]

Het probleem met quantum-computers is dat ze weliswaar snel zijn, maar wel weer een oneindige hoeveelheid geheugen nodig hebben om je oplossing in op te slaan.

Altijd geldt de afweging tussen snelheid of opslag, dat gaat met quantum-computers niet anders worden. Die bieden enorme parallelle verwerking, maar als je geheugen erachter niet snel en groot genoeg is heb je daar dus niks aan.

[Verwijderd]

Quantum computers zijn slechts sneller bij een aantal soort problemen. Ze kunnen niet "meer" problemen oplossen dan nu al mogelijk is (een quantum computer is gewoon te simuleren op een normale computer).
De meest rekenintensieve problemen zijn ook met een quantumcomputer (als die zou bestaan) net zo ondoenlijk als met een normale computer.

[QuarkuS]

The computation was performed on TERA NOVA (a 256 Intel-Itanium2 system developped by BULL SA, installed in the CEA DAM open laboratory TERA TECH). It required approximatively 80 000 CPU hours. The complexity of the attack was about 2^51.

't Is dus nog niet overdreven onveilig Wellicht net zo onveilig als RC5-64 ?

[The Lord]

Iets minder dan 14 dagen dus op dat systeem om te kraken. Niet echt een huis tuin en keuken PC'tje, maar toch...

[Verwijderd]

14 dagen

80 000 uur is nog altijd ruim 9 jaar

edit:
80 000/24 = 3333,333.....
3333,333.... / 365 = 9,1324... => ruim 9 jaar dus

[Olaf van der Spek]

80 000 uur is nog altijd ruim 9 jaar

80000 uur / 256 CPUs / 24 uur/dag = 13,02 dagen.

[eborn]

Het gaat volgens het bericht om CPU uren. En daar de machine meerdere CPU's heeft...

[Bacchus]

Tsja, 14 dagen, en dan heb je 1 collision, die waarschijnlijk nog geen drol betekent ook.

[Verwijderd]

Volgens mij zijn alle hashes te kraken, kwestie van grote computer en veel tijd. Je kunt alleen door bijv. de key langer te maken(nieuw soort hash) de kans op kraken onrealistischer/moeilijker maken.

Zit ik op het juiste spoor?

[AntiChris]

Zoals ik hierboven (weliswaar na jou) heb gepost, als je je key n bits langer maakt worden je berekeningen 2^n keer zo lang. 1024 bits encrypties zijn onkraakbaar doordat het momenteel volledig onmogelijk is om deze te bruteforcen, terwijl het versleutelen van informatie met een 1024 bits key in een fraktie van een seconde is gebeurd.

Mocht er ooit een computer komen die zo'n key wel kan uitrekenen, dan voeg je nog eens 1024 bits toe en je hebt 2^1024 keer meer tijd nodig om het te berekenen, terwijl het versleutelen nog steeds in 2 frakties van een seconde gebeurt.

[dmantione]

Ja, alleen de hoeveelheid berekeningen loopt bij goede algortimen dusdanig op dat het geen probleem is een sleutellengte te gebruiken waarbij niet genoeg silicium op aarde aanwezig is om de computer te bouwen om die te kraken.

[MBV]

gelukkig schakelen ze daarom over op dna-achtig materiaal voor supercomputing

Niet genoeg silicium is niet ter zake doende: dat is alleen met de huidige techniek. Met neurale netwerken e.d. is veel meer mogelijk, zeker op het gebied van encryptie en decryptie.
Daarnaast gaan snelheden en dichtheden van processors zo hard omhoog (Moore's Law) dat er geen probleem is dat nooit opgelost kan worden.

Maar op de middellange termijn geef ik je gelijk

[Verwijderd]

Voor alle hashes geldt dat deze te "vervalsen" zijn. Het is natuurlijk zo dat als je een kort bericht hebt en je wilt 't "belangrijke deel" wel goed houden het niet eenvoudig misschien zelfs onmogelijk is.
Over het algemeen zal de data set groot genoeg zijn als je het hebt over een paar Mb.
Dan kun je je virus/hack/spyware gewoon in 't begin laten staan en de rest mag dan best bagger zijn.

Nog ff over de hashes en 't vervalsen. Hoe wil voorkomen dat als je een paar miljoen bits hebt die "slechts" gechecked worden door een paar honderd bits niet vervalst worden. De enige valide reden om een hash te gebruiken is om er voor te zorgen dat je ziet dat er niet "perongeluk" een paar bits zijn omgevallen.

[eborn]

Hoe wil voorkomen dat als je een paar miljoen bits hebt die "slechts" gechecked worden door een paar honderd bits niet vervalst worden.

Je kunt die hash vervolgens weer beveiligen met andere methoden, bijvoorbeeld door een set gedeelde sleutels.

[Verwijderd]

Wat ik bedoelde is dat de hash niet als beveiliging gezien kan worden. Sleutels toepassen is helemaal niet van toepassing daarvoor heb je geen hashes nodig.

[Verwijderd]

Je moet de bestanden gewoon verdelen over meerdere exemplaren en dan pas verzenden. De kans dat ze allemaal langs dezelfde weg gaan over het internet is kleiner dan de kans van kraken.......Dus de onderschepper heeft ten alle tijde slechts een deel van de informatie ter beschikking.

[solatis]

SHA-0 is een zogenaamd hashing-algoritme wat inhoud dat

Foei, inhoudt