Aanval op SHA-1 eenvoudiger gemaakt

Australische cryptografie-deskundigen hebben een methode beschreven waarmee botsingen tussen SHA-1-hashes sneller gevonden kunnen worden dan voorheen. Het werk van de onderzoekers toont aan dat SHA-1 aan vervanging toe is.

Bij de beschreven methode kan na 2⁵² pogingen een botsing worden gevonden. De onderzoekers claimen tal van nieuwe differentiële paden te hebben gevonden die gebruikt kunnen worden bij een zogeheten Boomerang-aanval. De methode is aanzienlijk sneller dan de methode die drie Chinese onderzoekers in 2005 demonstreerden en die een tijdscomplexiteit van 2⁶³ had. Met de methode komt een praktisch uitvoerbare aanval steeds dichterbij.

Secure Hash Algorithmes worden gebruikt om de authenticiteit van bestanden en datastromen te waarborgen. Het algoritme berekent op basis van de bestandsdata een tekenreeks die uniek zou moeten zijn. Het gebruik van SHA bij andere of gewijzigde brondata zou dus een andere tekenreeks op moeten leveren, zodat onder andere gecontroleerd kan worden of er niet met bestanden geknoeid is. Het door de NSA ontworpen SHA-1 werd in 1995 door het Amerikaanse NIST gepubliceerd. Sinds de ontdekking van kwetsbaarheden in SHA-1 heeft het NIST vier aanvullende hash-functies gepubliceerd, de SHA-224, SHA-256, SHA-384, en SHA-512. Deze algoritmes, die samen als SHA-2 bekend staan, worden echter nog niet veel gebruikt.

Eind 2007 schreef het NIST een wedstrijd uit voor het bedenken van een opvolger van de huidige hashalgoritmes. Inzendingen konden tot oktober 2008 gedaan worden, maar het zal waarschijnlijk nog wel tot 2012 duren voor een winnaar wordt uitgeroepen. Die zou onder de naam SHA-3 als standaard moeten worden ingevoerd.

Reacties (68)

Bij alle schattingen van de tijd die het kost wordt klakkeloos uitgegaan van een CPU. Maar het is goed denkbaar dat overheden en inlichtingendiensten in staat zijn om het algoritme in dedicated hardware te realiseren. Kortom, een maatwerkchip die alleen bedoeld is om SHA-1 te kraken.
Als vuistregel wordt vaak aangehouden dat zo'n dedicated oplossing een factor 1000 sneller kan zijn dan een CPU-benadering. Dat gecombineerd met een behoorlijk aantal parallelle structuren op zo'n chip, 1000 stuks is nog niet zo'n raar getal en het gaat toch even een factor 10^6 sneller dan we in het algemeen geneigd zijn om te denken.

Overheden? "Deep Crack" was gebouwd door de EFF om te bewijzen dat DES te simpel was. Dat was een ontwerp wat in 1998 al voor $250.000 gebouwd kon worden, met off-the-shelf hardware.

Is datgene wat een hash "veiligheid" bied niet de tijd die nodig is om hem te berekenen? Dus eigenlijk is het een continue wedloop naar die functie die het langste erover doet om van zijn input een output te maken, die bij herhaling van die functie hetzelfde is.
Of is het de lage kans op collisions wat een veilige hash kenmerkt?

Is het hash-en van je hash dat ook een verstandige tussenoplossing, gezien je daarmee de factor "tijd" beinvloed die je nodig hebt om een colission te berekenen?

Je hebt gelijk, de meest veilige hash van een bepaald moment is de hash functie die het meeste tijd nodig heeft. Maar niet om van een input een output te maken, maar om van een output terug een input te maken.
Dus de tijd die nodig is om te berekenen/ proberen welke bestanden je bij elkaar moet zetten/archiveren om precies dezelfde uitkomst te hebben.
De kans op toevallige gelijkenissen is met de huidige grootte van de uitkomsten bijna verwaarloosbaar. Alhoewel... Het zit er dik in dat we die grens moeten verhogen.

Het hash-en van je hash is een uitkomst maar werkt niet als er gevonden is hoe je een bepaalde functie volledig van het einde tot begin weer laat lopen.

Voor volledige veiligheid zou je beter gebruik maken van tree-hashing. Deze hash splitst je bestand/archief op in verschillende gelijke stukken, hasht ze afzonderlijk en telt bijvoorbeeld de eerst X aantal hashes bij elkaar op, en hasht die opnieuw. De volgende X-aantal weer, etc... Daarna doet het dit nog eens met deze hashes van het "tweede niveau". Tot je uiteindelijk maar één hash-uitkomst overhoudt. Dit is de root-hash en kun je gewoon verspreiden als een simpele hash.
Op zich is dit al veilig, maar als je dan nog eens de hashes van elk stukje en elk niveau doorstuurt, kun je elk klein deeltje testen op authenticiteit en zodoende heel erg veilig zijn.
Een erg bekende tree-hash is TTH (Tiger Tree Hash). Meer over TTH en tree-hash kun je op de wiki lezen: http://en.wikipedia.org/wiki/Hash_tree

De kans op toevallige gelijkenissen is klein genoeg, astronomisch zelfs. Het probleem is hier opzettelijke gelijkenissen, waarbij de aanvaller beide inputs controleert (Collisions). Voor online bankieren bijvoorbeeld, waar de website owner de eerste hash maakt, is de uitdaging groter. De aanvaller kan nu maar 1 van de 2 inputs varieren en heeft een vastliggende doeluitkomst (Preimage Attack). In die situatie is SHA1 nu dus nog wel veilig.

Ik weet niet wat jij allemaal aan het vertellen bent, maar een hash van iets heeft altijd een vaste lengte en zou normaal een willekeurige waarde moeten zijn.
Het wordt echter berekent aan de hand van een bitpatroon (wat dus eender wat kan voorstellen), en eenzelfde bitpatroon levert altijd dezelfde waarde op.
Veranderd men echter 1 bit aan het bitpatroon, dan zou de hashwaarde een totaal andere waarde moeten zijn. Ook is het voor een goede hashfunctie onmogelijk om terug het originele bitpatroon te vinden, enkel met brute-forcing zou het mogelijk mogen zijn om een bitpatroon te vinden dat een bepaalde hashwaarde krijgt. Zelfs met moderne computer duurt dat normaal nog jaren voordat gevonden wordt (2^160 mogelijkheden).
Echter zijn er in de manier dat hashfuncties een hashwaarde produceren zwakke punten gevonden waardoor het makkelijker is om een bitpatroon te genereren dat een bepaalde hashwaarde oplevert. En omdat veel beveiligingen hierop steunen dat het niet mogelijk is, is dit een gevaarlijk probleem.

Wat heb ik als eenvoudige boerenlul met SHA-1 te maken?
De enige keer dat ik ooit een hash ben tegengekomen was toen ik een Linux-distro downloadde. Maar of dat nou nuttig was?...

Elke keer dat jij een beveiligde website bezoekt heb je er indirect mee te maken ja.

Een hash is een versimpeling van informatie naar een getal. Dat getal (vrij groot maar niet enorm) is heel makkelijk te berekenen uit de informatie, maar andersom is het heel erg moeilijk.

Hierop zijn de meeste beveiligings protocollen en authentificatie systemen binnen de IT gebaseerd. Die maken een hash code van je informatie en ondertekenen die met een bepaalde sleutel. Het kost namelijk te veel tijd/moeite/ruimte om de informatie zelf te ondertekenen (dan wordt de ondertekening namelijk groter dan de informatie die het beveiligt)

Als onderzoekers nu een manier vinden om makkelijker van de hash naar de bron-informatie (of een van de mogelijke voorbeelden van die bron-informatie want als de bron groter is dan de hash zijn er altijd meerdere mogelijkheden die tot dezelfde hash leiden) te komen, dan heb je echt een probleem, want de beveiliging maakt juist gebruik van het feit dat dit heel erg moeilijk is.

In het geval van je Linux distro: Als wat jij gedownload hebt niet meer overeenkomt met de SHA-1 hash, dan is er dus mee geknoeid (of het is gewoon simpelweg niet goed door de download gekomen).

Edit: Hmmz ik wou het simpel uitleggen, toch niet helemaal gelukt

[Reactie gewijzigd door GekkePrutser op 11 juni 2009 16:07]

Een hash is een versimpeling van informatie naar een getal. Dat getal (vrij groot maar niet enorm) is heel makkelijk te berekenen uit de informatie, maar andersom is het heel erg moeilijk.

Zeg maar gerust: onmogelijk

Ja, tenzij de hash 'gekraakt' wordt, zoals bij de MD5 (de collisions). Okee, je hebt dan misschien niet de originele tekst maar wel een random tekst die tot dezelfde hash leidt met alle gevaren van dien.

Ik neem aan dat deze nieuwe hack iets dergelijks doet maar ik heb het nog niet helemaal uitgeplozen.

[Reactie gewijzigd door GekkePrutser op 11 juni 2009 16:11]

Niets is onmogelijk zolang het te bruteforcen valt, . D'r zijn maar 2^160 SHA-1 sleutels mogelijk ( 1.4615016373309029182036848327163 x 10^48 ), en die kun je allemaal uitproberen.

MD5 is een tijdje terug gekraakt waardoor de onderzoekers een beveilingscertificaat na konden maken die een MD5 hash van een vertrouwd certificaat had, waardoor ze hun site als 'veilig' konden aanmerken. Als ze SHA-1 kraken wordt dit ook een mogelijk beveiligingslek.

Niet alles is te brute-forcen. De rekenkracht van het hele universum heeft een absolute bovengrens van ongeveer 10^80 atomen * 10^40 seconde * 1 Thz = 10^133 = 2^400 operaties. Dus elk systeem waar je meer dan 2^400 keys moet bruteforcen is absoluut veilig - er zijn niet genoeg atomen in het heelal om computers mee te bouwen.

Hoewel ik hier niets van snap klinkt dit wel ontzettend interessant, heb je misschien een linkje voor mij die het wat uitgebreider(hopelijk ook simpeler) uitlegt, of kan jij dat eventueel hier

Jij bent wel degelijk iets met SHA-1. Zeer vaak zonder het zelf te besteffen.
Als je surft naar de site van je bank, dan weet je browser dat dit een veilige site is. Dit komt omdat de site een certificaat heeft en dat dit van een van de vertrouwder bronnen komen (Global Sign, ....)
Moest nu zo een GlobalSign certificaat na te maken zijn, dan kan iemand je naar een site leiden (bv. lng.be) Als jij niet gezien hebt dat hier eigenlijk naar een andere site gelinkt wordt (er staat Lng.be), en je browserbalk kleurt bovenaan groen, dan geef je zonder al te veel te aarzelen je paswoorden in. Moest er een rode balk bovenaan je browser komen en een melding dat er iets scheelt met het certificaat, dan wordt er van jou verwacht dat je je gezond verstand gebruikt en dat je de URL eens nakijkt op fouten.

[Reactie gewijzigd door LordPan op 11 juni 2009 16:05]

SSL.......daar heb je dagelijks mee te maken, internetbankieren bijvoorbeeld.

Dan vraag ik mij af wat jij de nieuwswaarde van alle berichten hier op T.net vindt.

En uiteraard is dit erg nuttig voor een Linux-distro, het zal wat wezen als iemand het voor elkaar krijgt om een rootkit in je distro te krijgen. Dit kan de veiligheid van je systeem ernstig schaden.

Zie ook http://www.debian-administration.org/users/dkg/weblog/48 voor tips om over te stappen op sterkere PGP/GPG sleutels.

Het artikel waar je naar verwijst gaat over het overstappen naar sterkere hash functies, niet sterkere sleutels.

Als bijeffect wordt aangeraden om af te stappen van 1024 bit DSA sleutels, maar alleen omdat 1024 bit DSA default gebruik maakt van SHA-1 als signing algorithm, niet omdat een 1024 bit DSA sleutel van zichzelf kraakbaar zou zijn.

Als je bij digitaal ondertekenen gebruik maakt van een zwakke hash dan kan met een hash collision een ander documnet van dezelfde handtekening worden voorzien, ook als je geen private key hebt. Je kunt namelijk de hash van het oorspronkelijke document berekenen (dat moet je ook doen om de handtekening te controleren) en dan een document maken dat dezelfde hash heeft en daarmee dezelfde digitale handtekening.

Alle beveiligingen zijn te kraken. Het is alleen de vraag of iemand die inbreekt het de moeite waard vindt 2^52 pogingen af te wachten... Dit is toch vaak niet het geval. Men steelt zeg maar liever "de fiets in het rek met de minste sloten".

SHA1 is verder een uitstekend systeem, maar ook goede systemen moeten ooit worden vervangen.

[Reactie gewijzigd door Anoniem: 158240 op 11 juni 2009 15:57]

2^52 pogingen vind ik helemaal niet zo veel eigenlijk, dit resulteert in 4.503.599.627.370.496 pogingen, dit lijkt voor ons mensen misschien wel veel, voor een computer valt dit heus wel mee.

Ik denk dat je niet helemaal duidelijk hebt hoe groot dit getal is.

Nemen we aan dat elke poging iets van 10 ms kost (wat al behoorlijk rap is!). Dat betekent dat er in een seconden 100 pogingen gedaan kunnen worden. Per uur zijn dat 360.000 en per dag 8.640.000.

Om 2^52 bewerkingen te doen ben je dan echter nog steeds 1,4 miljoen jaar bezig...

Best een stoer getal maar met clustering en parallel computing wordt dat getalletje al een pak kleiner...

Ten eerste is 10ms al erg rap. Zou je een supercomputer met 1000 cores tot je beschikking hebben, dan zou het nog anderhalf duizend jaar duren.

10 ms is compleet, ridicuul langzaam. Dat is namelijk 10.000.000 ns. Een moderne CPU core kan een paar instructies (+/- 5) per ns verwerken, dus we hebben het hier over tientallen miljoenen instructies. Zoveel heb je er echt niet nodig.

Een GPU komt waarschijnlijk tot 2^16 pogingen per seconde, 2^41 per jaar. Nemen we even aan dat je bereid bent 4 jaar te wachten, dan moet je dus 2^52 / 2^43 = 2^9 = 512 videokaarten in parallel laten draaien. Wil je een resultaat binnen 1 jaar, dan moet je er 2048 hebben. Veel, maar voor een miljoen euro lukt het. Dan kom je in de range waar banken serieus zenuwachtig worden.

Correct, en zelfs al is je algoritme iets trager, je moet niet per se doorheen alle berekeningen lopen, dat is worst case scenario - de laatste berekening is de juiste. Enne 2048 videokaarten is niet zo enorm veel. Je koopt enkele Tesla's (al snel beschikbaar in de lokale universiteit) en voor een miljoentje heb je (als je berekeningen juist zijn) al snel enkele maanden wachttijd. Als een overheid een biljoentje wil/kan investeren voor een degelijk klasse datacenters spreken we over dagen.

tenzij je dit kan schrijven in een manier die vector computing kan gebruiken. Een goeie GPGPU heeft al snel een paar honderden rekeneenheden per stuk.

Zeker, maar we mogen er nog steeds van uitgaan dat het maanden tot jaren kan duren met een serverpark waar enkel de grote overheden over beschikken en dat inzetten voor enkele maanden is al snel een dure bedoeling. Dus de informatie moet al echt zeer waardevol zijn en er mag geen alternatief bestaan eer ze dat gaan inzetten.

Bovendien moet het ook nog zo zijn dat de informatie die ze ermee winnen dan nog wel relevant is. Als jij er een jaar over doet om uit te vogelen wat je concurrent aan het uitspoken is dan heeft die het misschien allang wel op de markt gebracht bijvoorbeeld. Zolang een beveiliging ervoor zorgt dat de data gedurende zijn "TTL" niet bekend wordt dan is de beveiliging afdoende.

10 ms is eigenlijk ook al aan de hoge kant - het berekenen van hashes kan al met honderdduizenden per seconde per core, en zal nog sneller gaan met meerdere cores, GPGPU, clusters, etc. Dan nog zal het aardig lang duren, maar toch, het geeft wel aan dat SHA-1 te kraken is.

Maar daarom gebruikt de Amerikaanse regering SHA-1 ook al niet meer - ze zagen dit al een paar jaar terug aankomen en zijn overgestapt op SHA-2, en gaan naar SHA-3 zodra dit ontwikkeld wordt.

Wat ook logisch is, gezien SHA van de NSA komt

Bedenk daarbij dat de kans 50% is dat je al in de helft van de pogingen tot een resultaat komt !!!

Let op! Op het moment dat zoiets wordt gezegd, treedt de wet van Murphy in werking.

Maar daarmee ga je dus van 2^52 naar 2^51. De orde van grootte wordt er dus niet significant kleiner van.

Ik kan je melden dat het snelste verwerkingscentrum van gegevens tussen de oren zitten.

Niet tussen alle oren, maar bij een normaal mens zekers.

Het is alleen zo verdomd moeilijk hersenen in te zetten voor dit soort zaken.

Het gaat niet zo neer om beveiliging, maar autenticiteit van bestanden (zoals certificates).

Het laat ook zien dat bij toenemede cpu kracht men een algoritme steeds sneller zal moeten vernieuwen.

Dat is niet waar. Het hangt af hoe veel extra kracht de nieuwe beveiliging vraagt tegenover de oude.
De cpu-kracht stijgt over het algemeen exponentieel.
Als we nu zouden beveiligingen vinden die stijgen per faculteit dan zullen we eerder trager moeten nieuwe beveiligingen vinden dan sneller.

Nu weet ik te weinig over SHA-1 en 2 om iets te zeggen hoe het tussen die 2 zit maar je reactie volgt alleszins niet rechtstreeks uit het artikel.

Soms hoef je niet eens nieuwe beveiligingen te vinden. Toen DES niet meer veilig genoeg was, werd triple-DES gebruikt: 3 rondes normale DES achter elkaar. De encryptie duurde 3 keer zo lang, maar het kraken werd miljarden keren moeilijker.

Is het niet logisch dat iedere hash functie collisions heeft? Een tekst van 1000 karakters kun je toch nooit samenpersen tot iets van 64 karakters, terwijl er evenveel mogelijkheden blijven bestaan?

ja, maar het is de bedoeling dat het (in de praktijk) onmogelijk is om een collision te vinden, dat men dus alle mogelijkheden moet afgaan totdat er 1 gevonden is met dezelfde waarde. De kans hierop is 1/2^160 bij SHA-1, en dat is voorlopig nog wel genoeg. Echter kan men door het algoritme dat de hashwaarde berekent te bestuderen er soms zwakheden in ontdekken zodat men gedeeltelijk kan voorspellen wat voor waarde het gaat worden en dus niet meer alle mogelijkheden moet afgaan.

Nu SHA1 blijkbaar (al geruime tijd) niet meer voldoet, hoe staat het dan met MD5..? Dat algoritme wordt ook nog altijd behoorlijk veel gebruikt bij onder andere downloads.

Is MD5 nu ook zo 'makkelijk' te hacken, te achterhalen of te brute forcen..?

Lang verhaal kort: nog makkelijker.

Er werd al lang aangeraden om geen MD5 meer te gebruiken, maar over te schakelen naar SHA-1, nu dus nog een beetje sterkere sleutels nodig.

Op de TU/e in Eindhoven is een proof-of-attack geweest, waarmee men valide root certificates kon genereren, door MD5 te kraken: http://www.win.tue.nl/hashclash/rogue-ca/

Binnen korte tijd nadat deze attack publiek gemaakt is, zijn alle SSL-certificaat verstrekkende bedrijven zo goed als direct op SHA-1 overgestapt. 2^52 is daarentegen nog een redelijke ondergrens, er moeten echter niet veel bits meer afgebeten worden...

MD5 is nog veel makkelijker te hacken (veel sneller dan brute force) en is al jaren niet meer veilig. Er zijn voorbeelden te over van originele en vervalste PDFjes (bijvoorbeeld) die precies dezelfde MD5 hashes hebben.

MD5 mag al heel lang niet meer gebruikt worden omdat het algoritme simpel weg te zwak is. Er zijn op internet tutorials te vinden hoe je met meerdere playstations zelf een md5 certificaat uitgeeft .

Een andere mannier waarop hashing word gebruikt is password hashing zodat je wachtwoorden niet plain tekst in je database hoeft op te slaan. Ook hier is md5 al redelijk hard gekraakt (rainbowtables zijn voor md5 heeel ver uitgerekend ). Dit gaat voor SHA ook nog wel gebeuren (wellicht dat het voor sha512) wel langer gaat duren.

Kortom gebruik md5 niet meer!

*is benieuwd hoelang het duurt voor der weer een optimalisatie is voor priemfactorisatie

Een MD5-hash van een bestand is ook niet bedoeld om deze te beveiligen, maar om te kunnen valideren. Als de MD5 van je gedownloade bestand niet klopt, weet je dus dat het bestand niet goed overgekomen is en dat je een nieuwe poging moet wagen. De kans dat je een bestand toevallig zo beschadigt binnenkrijgt dat de MD5 nog wel klopt is er zo goed als niet.

Bestanden 'vervalsen' met een MD5 lijkt me trouwens ook een *****karwei. Stel je eens voor dat je een ISO van 4GB wilt vervalsen met jouw 'valse' data erin en die ook nog eens uitkomt op de juiste grootte en MD5. Dat zou wel eens iets langer kunnen duren dan slechts een wachtwoord kraken...

Daarnaast is het waarschijnlijk ook niet zo lastig dat als je het bestand eenmaal kan vervalsen een valse MD5 erbij zetten ineens onmogelijk is

[Reactie gewijzigd door dcm360 op 11 juni 2009 17:08]

Voor het valideren van bestanden kan je evengoed 2 hashes gebruiken. Lijkt me heel sterk als je met 2 verschillende bestanden zowel een gelijke md5 als een gelijke sha1 hash hebt. Voor wachtwoordenopslag zou je dit ook kunnen doen, maar let dan wel op dat je de inbreker kans geeft om achter het originele wachtwoord te komen.

Dit is een veelgemaakte denkfout over cryptanalysis van hashes. Twee hashes van grote N bits zijn samen veel slechter dan 1 hash van 2N bits.

Een moderne hash roert alle bits van de input door elkaar. Als je 2 afzonderlijke hashes gebruikt, dan ben je in als het ware in 2 pannen aan het roeren. De bits van de ene hash worden niet met die van de andere hash gemengd. Alleen op het laatst worden ze gecombineerd, en wel op de meest simpele mogelijke manier: door ze achter elkaar te zetten. Een grotere hash is vergelijkbaar met het roeren in 1 grote pan ipv 2 kleine pannen. Dat mengt veel beter, in elke stap.

Des had 2**56 vergelijkingen nodig en was toen gebruteforced. in 56 uur. zelfde groote orde dus.

dus je kunt redelijk stellen dat dit vrijwel gehackt is..

Hier geeft schneider een analyse van de stelling dat chizen hem in 2**69 konden oplossen.

http://www.schneier.com/b...5/02/cryptanalysis_o.html

@boerenlul hierboven. Torrents worden geverifieerd met SHA-1. Als SHA-1 simpel een collicion kan worden geprocudeerd akn je dus torrents vervuilen met corrupte data.

DES is geen hashing algoritme!

md5 is idd niet echt de meest secure iets meer, heb zelf ooit een md5 password achterhaald omdat dit niet meer bekend was, duurde wel paar uur voordat die het had gevonden maar het resultaat was er....

Dat heeft dan helemaal niets te maken gehad met het MD5 algoritme maar alles met een slecht wachtwoord aan jouw kant. MD5 collisions kunnen niet gebruikt worden om naar de oorspronkelijke tekst terug te keren (dat zou wel bijzonder toevallig zijn), maar om eenzelfde hash te genereren met een andere tekst.

maakt toch niet uit dat hij het originele wachtwoord niet heeft? als je je valse wachtwoord (met dezelfde hash) ingeeft dan kan je ook gewoon inloggen.

Uit de post van MrHarry is het niet duidelijk of hij het oorspronkelijke wachtwoord heeft gevonden of een vals, maar op zich maakt niet uit