SHA-1 gedeeltelijk gekraakt door Chinese onderzoekers

Op een weblog over security wordt gemeld dat het SHA-1-encryptiealgoritme gekraakt is door een team Chinese wetenschappers. In het rapport wordt onder andere beschreven dat er nu slechts nog 2⁶⁹ bruteforcepogingen nodig zijn in plaats van de 2⁸⁰ zoals voorheen gedacht werd. Dit betekent dat het met voldoende rekenkracht mogelijk wordt voor een bekende SHA-1-hash een collision te berekenen, data die dezelfde hashingsleutel oplevert als het oorspronkelijke bericht. Dit werd met de 2⁸⁰ mogelijkheden die tot nog toe vereist waren niet realistisch geacht. In augustus 2004 werd al gemeld dat SHA-0 onveilig bleek te zijn. Met een bepaald algoritme was men toen in staat een zogenaamde collision te berekenen.

Toen al werd er gezegd dat het met een aanpassing van dit algoritme waarschijnlijk ook mogelijk zou zijn hetzelfde te bewerkstelligen voor het SHA-1-algoritme en ook MD5, een veelgebruikt algoritme om downloads te verifiëren, zou niet veilig zijn door de mogelijkheid collisions te berekenen. SHA-1 sleutels worden voornamelijk gebruikt als digitale handtekening of om bestanden op cd's of images te verifiëren. Het is met de huidige kennis overigens nog niet mogelijk om op eenvoudige wijze een bericht te genereren met een vooraf bepaalde hash. In het verleden is echter wel gebleken dat deze ontdekking de aanleiding kan vormen tot het alsnog onveilig blijken van een algoritme.

Reacties (50)

[Verwijderd]

Wat veilig is, is afhankelijk van de geldigheidsduur van de data. Voor data die slechts een zeer beperkte geldigheidduur heeft is de SHA-1 sleutel nog steeds veilig genoeg.
Het wordt een ander verhaal als de tijd voor kraken korter wordt dan de geldigheidsduur van de data...

[_Thanatos_]

SHA-1 vind ik nog steeds zeer veilig. Als je een supercomputer nodig hebt om een sleutel te kraken, dan kun je er vanuit gaan dat de drempel om het te gaan kraken zeer hoog ligt. Als een of ander hackertje graag aan jouw data wil komen, zal ie daar een lastige kluif aan hebben, want de meesten hebben geen toegang tot een supercomputer, en al helemaal niet om die hiervoor te gebruiken.

Tuurlijk kan zoiemand een wormpje schrijven die zichzelf als distro-client gedraagt, maar dat blijft een erg hoge drempel. En dat is waar het om gaat bij beveiligingen, een zo hoog mogelijke (hoog genoege) drempel.

[Olaf van der Spek]

SHA-1 vind ik nog steeds zeer veilig. Als je een supercomputer nodig hebt om een sleutel te kraken, dan kun je er vanuit gaan dat de drempel om het te gaan kraken zeer hoog ligt.

Maar is dat over tien jaar nog steeds zo?

[Olaf van der Spek]

Over 10 jaar zal dr wel alweer een nieuwer en beter encryptie algoritme zijn

Dan moet je dus wel alles opnieuw tekenen. Een testament dat digitaal ondertekend is en 30 jaar geldig is, moet bijvoorbeeld wel 'veilig' blijven.

[florizla]

Zoals elders verduidelijkt: het gaat niet om encryptie maar om hashing, en dat is iets totaal anders.

[Radiant]

Over 10 jaar zal dr wel alweer een nieuwer en beter encryptie algoritme zijn

[Verwijderd]

SHA-256 en SHA-512

[Olaf van der Spek]

Zoals elders verduidelijkt: het gaat niet om encryptie maar om hashing, en dat is iets totaal anders.

Dus?
Beiden worden gebruikt in het digitaal ondertekenen van documenten.

[KatirZan]

een erg hoge drempel hoeft dat niet te zijn...

blaster virus wordt verspreid over elke pc met windows zonder sp2.....

dat wil zeggen dat er makkelijk een worm te schrijven valt die elke pc kan infiltreren en hier een distro van te maken.

zo moeilijk te bedenken is dat niet...
onthou wel, hackers kennen maar 1 taal, en dat is dezelfde taal waarin deze beveiligingscode is geschreven

[Tomatoman]

Even uitrekenen hoe lang je nu met brute force bezig zou moeten zijn om SHA-1 te kraken. Laten we er vanuit gaan dat je n klokcycli nodig hebt om een hash te berekenen en dat de computer op 3 GHz draait. Dat betekent dat je per seconde (3 × 10^9 ÷ n) hashes kunt controleren.

Volgens het artikel zijn er 2^69 brute-forcepogingen nodig. Dat betekent dat je (n × 6239) jaar aan het rekenen bent. Aangezien n op een pc ergens in de orde van een paar honderd klokcycli ligt, zitten we in de volgende ijstijd tegen de tijd dat je klaar bent met rekenen . Voorlopig is SHA-1 nog wel even veilig voor krakers met een pc'tje.

Wordt met wat slimmigheden het benodigde aantal brute-forcepogingen teruggebracht tot 2^50, dan kun je (uitgaande van n = 80) alle mogelijkheden binnen een tijdsbestek van een jaar uitproberen en is SHA-1 zeker niet meer veilig te noemen. Zo ver zijn we echter nog lang niet.

[Rey Nemaattori]

je snap natuurlijk wel dat een beetje supercomputer enige duizenden tot tienduizenden malen sneller rekent dat de gewone desktop pc...

[foppe-jan]

edoch, wat ziet mijn oog nu? een open deur

[the_shadow]

Dat valt zeer te bezien. Als door deze ontwikkeling steeds meer fouten in het algoritme aan het licht komen, zou het misschien binnenkort mogelijk zijn om met nog minder pogingen een collision te berekenen. Het hangt er maar net van af hoe erg er nu extra onderzoek naar gedaan gaat worden. Als er wordt gedacht "Ach ja, wij houden ons bezig met nuttigere zaken", dan zal het inderdaad niet zo'n vaart lopen, maar als meerdere onderzoekteams hier zichopeens mee bezig gaan houden, dan kan het sneller lopen dan je denk.

[Tarquin]

In het nieuwsbericht staat dat 'het mogelijk wordt een bericht dat met SHA-1 gehashed werd te 'raden' binnen een afzienbare tijd'.

Dat is gelukkig NIET zo. Je kunt nog steeds NIET een origineel bericht met terugwerkende kracht uit de hash halen.

Ook is de echte praktische toepassing, nl het opstellen van een bericht dat dezelfde hash oplevert als een bekend bericht dat jij graag wilt veranderen, NIET bereikt.

Alleen de colission, het genereren van twee verschillende berichten met dezelfde hash, is dichterbij gekomen.

Het is dus nog NIET zo dat iemand een SHA-1 ondertekend bericht naar gelieven kan aanpassen en de hash hetzelfde kan houden; ook niet met voldoende rekenkracht.

[Verwijderd]

De xbox encryptie werkt ook met een sha-1 versleuteling waarmee de .xbe bestanden zijn getekend door ms. Met een sleutel zouden willekeurige .xbe bestanden getekend kunnen worden en dus zonder exploits linux gedraaid kunnen worden op de xbox.

[Verwijderd]

Zie ook www.xbox-scene.com of:

From Bruce Schneier's weblog: 'SHA-1 has been broken. Not a reduced-round version. Not a simplified version. The real thing. The research team of Xiaoyun Wang, Yiqun Lisa Yin, and Hongbo Yu (mostly from Shandong University in China) have been quietly circulating a paper announcing their results...'" Note, though, that Schneier also writes "The paper isn't generally available yet. At this point I can't tell if the attack is real, but the paper looks good and this is a reputable research team."
[/QUOTE]

Why this article on an Xbox site? Well, Microsoft's Xbox game console relies on the security of, among others, SHA-1. It would not allow to just directly sign any XBE you want, as XBE's are signed with RSA. This RSA signature only signs the XBE header, so nothing can be changed there. But all 'sections' (part of XBE containing the program) could be changed as long as all sections keep the same size and the same SHA-1. So it might be possible to take an already MS-signed XBE and write a section that does 'what we want' (example: load/patch BIOS, install a SW exploit, ...) that's smaller then the original section and 'fill it up' so it matches the original size and SHA-1. That's where this news comes in. If this paper is real it would probably still require lots of CPU power (2**69 hash operations?) to find a 'collisions' (match), but a lot less then before (2**80 operations?) anyway.

[KoKro]

SHA-1 is een hash, geen versleutelmechanisme. Ik weet niets van een XBox, wel van code-signing.

Van zo'n .xbe bestand wordt eerste een SHA-1 hash berekend, waarna de hash wordt versleuteld met een privesleutel van Microsoft. De Xbox bevat een certificaat met daarin de publieke sleutel van Microsoft, waarmee de versleutelde hash weer kan worden teruggehaald. Tevens berekent de XBox zelf ook de SHA-1 van de ontvangen .xbe en vergelijkt de twee hashwaardes. Als die identiek zijn, dan is de code ongewijzigd.

In theorie zouden er gemiddeld 2**80 brute-force berekeningen nodig zijn om een ander bestand te vinden dat dezelfde hash heeft als de originele .xbe. Dat proces is nu 2048x eenvoiudiger geworden (maar nog steeds 2**69) De kans is echter nog wel heel klein dat de gevonden "collision" een werkende .xbe is, die de gewenste malware bevat.

Het vinden van de collision is nodig/gewenst, omdat het nog veel lastiger is om de private key van Microsoft te raden. Als je dat kan, dan zou je namelijk van een malware .xbe een correcte SHA-1 kunnen berekenen en die tekenen alsof je MS bent.

(.xbe en Microsoft kunnen door elk ander formaat c.q. instelling worden vervangen)

[sopsop]

Ze hebben het toch niet gekraakt. Zulke encryptie is per definitie te 'kraken'. Ze hebben alleen aangetoond dat het met (heel) wat minder pogingen kan.

[KoKro]

Het gaat niet om versleutelen, maar om een hash (soort van checksum) te berekenen die vrijwel uniek is voor elke verschillende vorm van invoer.

[Rac-On]

een hash is per definitie niet uniek voor een invoer. Een hash bevat veel minder informatie dan de orgiginele data.
Het idee is juist dat het enorm veel tijd kost om bij een gegeven hash A een stuk data B te vinden die matchen.

[Verwijderd]

Mhoaw... een goede hash is theoretisch gezien natuurlijk niet vrijwel uniek, maar practisch gezien is dat JUIST de definitie van een goede hash: "practisch uniek".

Als een gegeven hash code generator voor veel data telkens de zelfde hash code zou opleveren, dan zou dat erg onwerkbaar zijn. Je probeert het dus wel zo uniek mogelijk te maken (gegeven een bepaalde tijd en doel groote die je hebt).

[Rac-On]

ook niet vrijwel, niet eens een klein beetje

[Freee!!]

Inderdaad, een factor 2048 om precies te zijn.

[Durandal]

Edit: gewist; ik kan niet rekenen

[Jace / TBL]

Heel de beveiliging die werkt met dit soort algo's is erop gebaseerd dat het lang duurt (dwz veel brute force pogingen vereist) om data te genereren die een bepaalde hash oplevert.

Als je met wat slimmigheidjes het aantal pogingen drastisch kunt reduceren, is het algo effectief natuurlijk gekraakt.

[voodooless]

Zulke encryptie is per definitie te 'kraken'

Dat is niet helemaal waar. Zolang er nog niet is bewezen dat NP!=NPC moet je ervan uitgaan dat er een mogelijkheid bestaat dat het te kraken is (uitgaande van een foutloos algoritme). De vraag is wel of men dat überhaupt kan bewijzen..

Men werkt overigens wel aan het omgekeerde bewijs: NP=NPC. Als dat bewezen is kunnen we alle encryptie/hashing methoden weggooien

[Yo-han]

Deze ook al? Die chinezen zijn verdraait goed in het ontcijferen van encrypties. De SHA-0 werd ook al door een chinees ontcijferd: http://www.cryptography.com/cnews/hash.html

[Sentry23]

En SHA-0 werd al veel eerder op een (toen) vreemde manier aangepast door de NSA, de ontwerpers van het protocol, naar wat men nu SHA-1 noemt.

Voor het hele verhaal kan je altijd op wikipedia kijken:
http://en.wikipedia.org/wiki/SHA-1

[KoKro]

Natuurlijk is het belangrijk om te weten dat een hashalgorithme niet de eigenschappen heeft die ervan werden verwacht.

De toepassing van SHA-1 die ik ken liggen in de sfeer van integriteitscontrole, dus een soort checksum of gegevens niet zijn aangepast. Veelal gebeurt dit in combinatie met het versleutelen van deze hash met een asymmetrisch algoritme (digitale handtekening).

Het is nu dus 2048x eenvoudiger geworden om twee gegevensblokken (documenten/berichten) vinden die een gelijke hash opleveren. Dat betekent nog niet meteen dat het eenvoudig is om in een bepaald gegevensblok een wijziging aan te brengen zonder dat de hash wijzigt.

Er lijkt mij dus geen reden tot paniek, maar voor de echt paranoïden onder ons is er ook nog SHA-256 of sterker...

[gp500]

SHa-1 en md5 zijn familie, MD5 is allang gekraakt.
Dus dit verbaast mij niks.

[Jace / TBL]

wablief? md5 is niet gekraakt hoor.

[Radiant]

Er is een collision gevonden in MD5.. http://www.x-ways.net/md5collision.html

[Jace / TBL]

Da's iets anders. Daarmee kunnen ze niet bij een willekeurige md5 checsum een stuk data genereren wat die checksum als md5 hash heeft. Pas dan zou het "gekraakt" zijn.

[Verwijderd]

Er is voor zover ik weet nog geen praktisch geval bekend waarin twee verschillende bit-reeksen dezelfde hash opleveren.

MD5 is overigens een 128 bit hashing algoritme.

[Verwijderd]

SHA-1 en MD5 zijn in zoverre familie dat ze allebei gebaseerd zijn op bitmixing en dat ze allebei hashfuncties zijn, voor de rest weinig. Het is ongeveer stellen dat je "familie" bent van iemand uit hongkong, omdat je allebei op aarde woont en allebei mens bent.

[Jace / TBL]

Dat ze het aantal brute force stappen hebben weten te reduceren van 2^80 tot 2^69 is technisch gezien wel knap, maar ik zie niet hoe de veiligheid daardoor in het geding komt.

Als je tien miljard pogingen per seconde kunt doen (wat heel snel is) hebben ze met deze vinding de gemiddelde zoektijd van bijna 2 miljoen jaar naar ruim 935 jaar gereduceerd. Nuttig?

[curry684]

Als je tien miljard pogingen per seconde kunt doen (wat heel snel is) hebben ze met deze vinding de gemiddelde zoektijd van bijna 2 miljoen jaar naar ruim 935 jaar gereduceerd. Nuttig?

467.5 dus, gezien het feit dat een bruteforce attack per definitie uitmiddelt op de helft van de keyspace.

Iow: de hoeveelheid keyspace die je moet onderzoeken is per definitie evenredig verdeeld over de gewaagde pogingen: soms zal je na 1 poging beet hebben, en even vaak pas na 2^69. De gemiddelde processing time is dus altijd de helft van de maximale tijd.

[Jace / TBL]

467.5 dus, gezien het feit dat een bruteforce attack per definitie uitmiddelt op de helft van de keyspace.

I know, ik zei dan ook gemiddeld, niet maximaal... die 935 jaar was al gebaseerd op 2^68

[veltnet]

Het blijft in theorie natuurlijk mogelijk dat de eerste de beste brute-force poging toevallig raak is. Hoe klein die kans ook is, hij bestaat!
Daarom is in theorie elk versleutelingsalgoritme niet 100% waterdicht

[Verwijderd]

Een goed algoritme zou ervoor moeten zorgen dat elke willekeurige hash mogelijk is. Ik maak uit dit bericht op dat dit niet echt het geval is, of er moet iets anders zijn wat het aantal pogingen omlaag kan brengen.

Dit is uiteraard niet wenselijk, maar als er een vrij hoog minimaal aantal pogingen nodig is, kun je volstaan met het simpelweg vergroten van de hash waardoor de benodigde tijd weer enorm toeneemt.

Vergelijk het verschil tussen RC5-56, RC5-64 en RC5-72 maar. Dat is uiteraard iets anders, maar het principe is hetzelfde.

[SKiLLa]

Van 2^80 naar 2^69 (factor 2048) is best wel een doorbraak hoor, stel dat er nu nog een 'zwakte' gevonden wordt en dat er weer 2^11 'afgehaald' wordt, dan is het nog maar 2^58 en dat is toch echt een heel stuk zwakker (scheelt factor ~ 4.2 miljoen) !!!

Houdt dan nog rekening met de wet van Moore en ff voor het gemak de niet 100% juiste interpretatie: elke 18 maanden CPU power 2x zo hoog. En ook nog met het feit dat dergelijke hash-algo's steeds vaker hardwarematig in CPUs geimplementeerd worden, dan is het einde van SHA-1 snel (lees binnen 10 jaar) in zicht. Natuurlijk wel met de aanname dat er dus nog een 'zwakte' gevonden wordt met de orde van 2^11, maar reken maar dat bepaalde mensen nu al zenuwachtig worden ;-)