Onderzoekers kunnen sha-1-algoritme kraken met chosen-prefix collision-aanval

Beveiligingsonderzoekers hebben een gemakkelijk uit te voeren manier getoond om het sha-1-hash-algoritme te breken. Het is met de aanval mogelijk om identieke hashes te produceren van verschillende soorten input.

De kwetsbaarheid werd gevonden door twee beveiligingsonderzoekers van het Franse wetenschappelijk onderzoeksinstituut Inria en de Technische Universiteit van Singapore. Ze beschrijven de aanval op een website. Die krijgt de naam 'Sha-1 is a Shambles'. De onderzoekers vergelijken de zwakte in het algoritme met die van md5, dat al sinds jaren niet meer veilig is. "Alle aanvallen die praktisch mogelijk waren op md5, zijn nu ook praktisch mogelijk op sha-1", schrijven ze. De onderzoekers hebben ook een whitepaper geschreven met meer technische achtergrond.

De kwetsbaarheid kan worden uitgebuit met een zogeheten chosen-prefix collision attack. Daarbij wordt veel rekenkracht gebruikt om met brute forcing op zoek te gaan naar twee gelijke hashes van verschillende input. Bij een standaard collision-aanval moet een aanvaller net zo lang zoeken tot hij twee identieke hashes vindt, wat een paar jaar geleden al voor het eerst werd getoond. Bij een chosen-prefix-aanval kan een aanvaller juist een hash vinden van een specifieke input. Op die manier is het mogelijk een hash te vervalsen omdat er een ander bericht achter zit dan het origineel. Zo kan een aanvaller een ssl-certificaat of pgp-privésleutel nabootsen.

Chosen-prefix collision-aanvallen waren jarenlang moeilijk en duur om uit te voeren, omdat er veel meer berekeningen moeten worden uitgevoerd om een identieke hash te vinden. De onderzoekers hebben nu een manier gevonden om die kosten te drukken. Volgens hen zou het zo'n 45.000 dollar kosten om de aanval uit te voeren. Die kosten zouden over vijf jaar nog maar op tienduizend euro liggen, stellen zij. Beperkingen in de onderzoeksopzet zorgden ervoor dat het kraken van een hash langer duurde dan gedacht. De onderzoekers hebben een proof of concept laten zien waarin zij twee dezelfde hashes hebben gemaakt van verschillende pgp-sleutels.

Sha-1 wordt als hash-algoritme al jaren langzaam uitgefaseerd vanwege de beperkingen, en omdat er inmiddels veel betere alternatieven zijn. Toch gebruikt een aantal belangrijke applicaties het algoritme nog steeds. Onder andere GnuPG en OpenSSL maken er nog gebruik van. De onderzoekers hebben 'een groot aantal' ontwikkelaars op de hoogte gebracht, maar lang niet iedereen. Sommige daarvan, zoals GnuPG, gaan overwegen sha-1 nu helemaal uit te faseren. Dat is nog niet overal gebeurd.

Reacties (42)

Sha-1 wordt als hash-algoritme al jaren langzaam uitgefaseerd vanwege de beperkingen, en omdat er inmiddels veel betere alternatieven zijn. Toch gebruikt een aantal belangrijke applicaties het algoritme nog steeds. Onder andere GnuPG en OpenSSL maken er nog gebruik van.

GnuPG en OpenSSL moeten het ook blijven ondersteunen, onder andere voor de verificatie van opgeslagen hashes en decryptie van oude data. OpenSSL heeft bijvoorbeeld nog ondersteuning voor de voorgangers van MD5.

Het is nu tijd om SHA-3 (Keccak) breed te gaan implementeren. Eigenlijk was die tijd al vier jaar geleden, maar ja... De ontwikkelingen gaan helaas niet zo snel. In tegenstelling tot SHA-1 en SHA-2 maakt SHA-3 geen gebruik van de Merkle–Damgård construction. Dit neemt potentiële kwetsbaarheden in implementaties weg, onder andere in MAC's.

[Reactie gewijzigd door The Zep Man op 8 januari 2020 14:09]

Desondanks is nog wel het volgende te lezen in de OpenSSL pagina die je aanhaalt:

MD2, MD4, and MD5 are recommended only for compatibility with existing applications. In new applications, SHA-1 or RIPEMD-160 should be preferred.

Blijven ondersteunen en toestaan bij creatie nieuwe sleutels is natuurlijk wel wat anders. Het gaat hier over het uitfaseren van SHA1 bij actieve toepassingen.

SHA-3 gebruikt ook andere primitieven, waardoor aanvallen op SHA-1/2 niet van toepassing zijn. Het is wel jammer dat er gesteggel is over de implementatieparameters van SHA-3 (afweging speed/security).

Ik was even erg nieuwsgierig waarop de kosten gebaseerd waren en wat men dan gebruikt had. Voor wie geen zin heeft om door te klikken op de bron

We originally estimated that our attack would cost around 160k US$ by renting GPUs from
a cloud provider such as Amazon or Google (using spot or preemptible prices). However,
since our computations do not need much communication between the GPUs, nor fancy
inter-GPU task scheduling, we can consider renting cheaper GPUs from providers that use
gaming or mining cards in consumer-grade PCs, rather that the datacenter-grade hardware
used by big cloud providers. Services like gpuserversrental.com rent GTX 1060 or GTX
1080 GPUs for a price below 5 cents per month per CUDA core; which would give a total
cost around 75k US$ to compute a chosen-prefix collision

Grappig genoeg dus geen Amazon of Google. Dat had ik niet verwacht.

[Reactie gewijzigd door Perkouw op 8 januari 2020 10:16]

Het maakt voor het verhaal niet uit. Overheden hebben voldoende 'fuck you' geld om een dergelijke aanval uit te (laten) voeren via hofleveranciers Amazon en Google. 160k USD is niets in belastinggeld.

Waar het natuurlijk vooral om gaat is dat de kosten met dit verschil dichter in de buurt komen voor consumenten om met gemak uit te voeren. Goed, de kosten op zich zijn nog steeds behoorlijk, maar ze zijn al met meer dan 50% gereduceerd. Het wordt steeds plausibeler dat zo'n aanvallen niet alleen door overheden, maar door iedereen worden uitgevoerd.

Waar het natuurlijk vooral om gaat is dat de kosten met dit verschil dichter in de buurt komen voor consumenten om met gemak uit te voeren.

Dat is een belangrijk aspect. Toch zie ik overheden hier eerst misbruik van maken indien men hen hiervoor ruimte geeft. Overheden zijn geen bevriende partij in de wereld van cryptografie.

Daar heb je absoluut gelijk in, zij zullen meer budget hiervoor hebben dan eender willekeurige persoon. Dat de kosten steeds verder te drukken zijn vind ik daarom ook enorm positief, als het door iedereen gebruikt kan worden zonder veel moeite zal dit nog meer reden geven om minder van sha1 gebruik te maken, wat dus betekent dat partijen met meer budget dus ook geen misbruik zullen kunnen maken hiervan. Het hele argument "ja maar nog steeds duurt het kraken jaren" komt te vervallen, wat een van de weinige overgebleven redenen was voor bedrijven/personen om niet van sha1 af te stappen.

Daar heb je absoluut gelijk in, zij zullen meer budget hiervoor hebben dan eender willekeurige persoon.

Nog belangrijker is dat bij overheden winst geen primaire motivatie is, in tegenstelling tot commerciële organisaties. Een overheid kan gerust meermaals verlies draaien om iemand éénmaal schade aan te doen.

[Reactie gewijzigd door The Zep Man op 8 januari 2020 14:07]

Dat is niet zo heel gek. De grote cloudycloud-providers zijn pittig duur (ondanks dat ze proberen het goedkoop te laten lijken door de kosten in heel veel kleine stukjes te hakken), dus als je doel is om de aanvalsprijs omlaag te krijgen, zul je niet bij die partijen in gaan kopen.

Dus dat zijn ongeveer 100 x GEFORCE GTX 1060 een jaar laten draaien. Ongeveer 50 x GEFORCE GTX 1080.
Wil je in een week klaar zijn heb je dus 2500 x GEFORCE GTX 1080 nodig. Ben je zo twee miljoen euro kwijt. Goed dat er cloud providers zijn. :-)

Waar wat zou een oude coin miner FPGA doen? Die zijn stukken goedkoper.

[Reactie gewijzigd door djwice op 9 januari 2020 02:05]

Hoe lang duurt het om deze aanval uit te voeren? En is de duur van de aanval niet relevant bij applicaties als OpenSSL?

Een chosen-prefix aanval op een enkele GTX 1080 Ti kost zo'n 34 jaar volgens het paper van de onderzoekers. Als je er meer GPU's tegenaan gooit, wordt het natuurlijk makkelijker. De onderzoekers schatten een prijs van zo'n 45000 dollar aan GPU-huurkosten om een chosen-prefixaanval uit te voeren. Dit is voor een vijandige overheid natuurlijk een schijntje.

Gelukkig wordt SHA-1 weinig gebruikt. Browsers weigeren SHA-1-certificaten al een tijdje, bijvoorbeeld. Legacy-PGP-implementaties gebruiken het nog wel. OpenSSL gaat de 80-bits-sterke SHA-1 implementatie uitschakelen, maar Debian heeft dit bijvoorbeeld al veel eerder gedaan.

In de praktijk houdt dit in dat het geen enorm gevaar is, tenzij je zelf SHA-1 ergens gaat gebruiken in een beveiligingsproducten/encryptie zoals die van mail of van chats.

Gezien het feit dat er nog steeds MD5 hashes opdoken in password tables van sites doet mij denken dat de praktijk wat weerbarstiger is

Maar inderdaad, de waarschuwing is gegeven.

Op zich heb je gelijk dat MD5 helaas nog steeds op bepaalde websites gebruikt wordt als hashmethode, maar let wel dat je met deze aanval niet de richting van de hash kan omdraaien; je kunt wel iets maken dat dezelfde hash heeft, maar je ziet het gehashte wachtwoord dus niet.

Theoretisch zou SHA-1 dus nog wel gebruikt kunnen worden voor het hashen van wachtwoorden als er niet al heel lang veel betere algoritmes beschikbaar zouden zijn.

Het is inderdaad vreemd om voor het hashen van wachtwoorden algoritmes te kiezen die eigenlijk op snelheid en laag geheugengebruik geent zijn, je zou voor het hashen van wachtwoorden eerder noodzakelijk trage en geheugenvretende (binnen redelijke grenzen) hashalgoritmes moeten kiezen (Argon2 zou nu misschien een goede keuze zijn)

In dit geval 2 maanden

When renting cheap GPUs, this translates to a cost of 11k US$ for a collision,and 45k US$ for a chosen-prefix collision, within the means of academic researchers.Our actual attack required two months of computations using 900 Nvidia GTX 1060GPUs (we paid 75k US$ because GPU prices were higher, and we wasted some timepreparing the attack).

Ik heb het idee dat het vrij goed schaalt hoe meer gpu's je toevoegt, alleen dat kan ik niet zo 123 uit de paper vinden.

[Reactie gewijzigd door Rmg op 8 januari 2020 10:27]

De duur is (nu nog) lang: 2 maanden. In het geval van een sleutel hash is die duur niet van groot belang, omdat daarmee een sleutel in een certificaat kan worden vervangen.

Indien microsoft hun certificaat zou ondertekenen met SHA-1 zou je nu dus een geldig microsoft update certificaat kunnen maken met een eigen sleutel. Windows zou de update klakkeloos accepteren en installeren. Voor zo'n aanval is de tijd om een hash te krijgen niet zo heel belangrijk.

Voor openSSL zou je zo'n aanval kunnen voorbereiden in het geval van gebruik in VPN. Het is niet praktisch voor webverkeer. Tenzij je het gebruikt om een certificaat te vervalsen op je server, maar volgens mij staat geen enkele moderne browser nog SHA1 certificaten toe om deze reden.

TLS 1.3 is sowieso ook al volledig vrij van SHA1

TLS 1.3 is inderdaad volledig vrij van SHA-1 zoals je beweert, echter ik denk niet dat je begrijpt waarom..

TLS (1.3) is slechts het communicatie protocol waarmee feitelijk alleen de afspraak wordt gemaakt tussen de client en de server welke encryptie methode er toegepast zal gaan worden door beiden.

Als server en client besluiten dat de "beste" overeenkomstige encryptie methode die ze beide kennen SHA-1 is dan zal dat de methode zijn die ze beide gebruiken om de informatie mee te versleutelen. (Dat is als het goed is niet zo, maar toch, het zou theoretisch zo kunnen zijn).

In tegenstelling tot het algemeen aangenomen populaire geloof is het TLS verkeer zélf _niet_ encrypted.
Het betere, veiligere aan TLS 1.3 is het feit dat het aantal roundtrips dat in plain text gebeurt bij dit protocol slechts één roundtrip is (idealiter) terwijl bij voorgaande versies van TLS het protocol veel chattier was en meerdere roundtrips vergde om tot een encryptie afspraak te komen.

Als server en client besluiten dat de "beste" overeenkomstige encryptie methode die ze beide kennen SHA-1 is dan zal dat de methode zijn die ze beide gebruiken om de informatie mee te versleutelen. (Dat is als het goed is niet zo, maar toch, het zou theoretisch zo kunnen zijn).

NEE. TLS 1.3 heeft slechts een handvol protocollen die gebruikt mogen worden. SHA1 mag niet gebruikt worden, want dat zou een downgrade zijn van versie 1.3. Dat is het hele punt. Als de server TLS 1.3 heeft en aan komt met SHA1 geeft de browser de site gewoon een dikke middelvinger.

Bovendien is SHA een hash en wordt dus per definitie niet gebruikt voor de encryptie. De hash wordt gebruikt om vast te stellen dat de handshake onderweg niet is aangepast, juist omdat de handshake niet zelf voorzien kan worden van encryptie. Wat je verliest met TLS als de hash functie niet veilig is is de zekerheid dat je praat met wie je denkt dat je praat en niet iemand in het midden.

Wat ik niet versta is dat dit dan moet worden uitgefaseerd.
Er zijn toch redenen te vinden waarom interne logica van een applicatie SHA-1, net zoals md5, zou gebruiken. Dat je dit niet gaat gebruiken om iets veilig te maken, kan ik perfect begrijpen, maar hashing kan toch ingezet worden los van veiligheid?

Wat ik niet versta is dat dit dan moet worden uitgefaseerd.

Er wordt dan natuurlijk ook gedoeld op 't uitfaseren van SHA-1 in security context. Git gebruikt bijvoorbeeld SHA-1 als commit ID's en daarvoor is 't prima bruikbaar.

SHA-1 staat voor 'secure hashing algorithm'. Het is ontworpen voor applicaties in security. Voor veel toepassingen (zoals bijvoorbeeld een hashmap) is een simpel hash algoritme zoals Fowler-Noll-Voh genoeg. Natuurlijk betekent dat niet dat de veiligheid van elke toepassing van SHA-1 ook daadwerkelijk minder veilig is. Het is wel zo dat SHA-1 niet meer aan zijn ontwerpdoelen voldoet.

Waarom staat in de eerste alinea 'encryptiealgoritme' terwijl in de rest van het artikel wel correct of hashing wordt gesproken?

Ja dat was een dom foutje, heb het aangepast, thanks!

Ofwel op het moment dus nog onrealistisch om te gebruiken, hooguit voor hele specifieke zaken af en toe, zeker in iedergeval dus niet realtime. meer 'leuk dat het kan'..

Er is geen enkele reden om nog sha1 of md5 te gebruiken in plaats van sha2 of (beter) sha3. Maar "sha1 kan gekraakt worden" is een beetje verkeerde voorstelling van zaken.

Wat je met een chosen prefix collision kan is best wel beperkt. Zelfs het domweg opslaan van sha1 hashes van wachtwoorden zonder salt (wat om meerdere redenen heel erg not done is) eigenlijk al niet te kraken.

Maar dan haal je het zelf ook een beetje uit de context. Het is "niet meer" waardevol, omdat er al veel maatregelen genomen zijn om SHA1 te weren. Nog geen 5 jaar geleden was dit voldoende geweest om veel security certificaten op het internet te vervalsen.

Voor Windows 7 was het tot voor kort nog genoeg om een windows update te vervalsen.

Dat zijn beide toch zaken waar een goed gefinancierde aanvaller interesse in kan hebben. Anders dan bij MD5 is er door de industrie deze keer snel gereageerd en bij de eerste tekenen van een probleem is begonnen SHA1 af te bouwen

Quantum Computers zijn errug goed in dit soort doublehash berekeningen. Zodra het aantal qbits verder omhoog geschroeft kan worden vallen door deze soort aanvallen de overrijpe chosen-prefix collission attack appels en-masse uit de cryptografie boom. Een paar boompjes zullen waarschijnlijk (preventief) gekapt moeten worden. 'k verwacht geen australische bosbrand, dat dan weer niet.

Even voor de goede orde: quantum computers zijn helemaal niet zo goed in hashes. Ik bedoel niet alleen in de praktijk niet (want er bestaan nog niet eens quantum computers die hashes kunnen berekenen) maar ook theoretisch niet.

Quantum computers kunnen in een theoretisch best case scenario (wat nog ver verwijderd is van de realiteit) de search space voor een n-bit hash terugbrengen van O(2ⁿ) naar O(√2ⁿ) = O(2^½n). Dat is een flinke verbetering maar lang niet genoeg.

Voor een 256-bit hash komt dat op hetzelfde neer als een 128-bit hash bruteforcen met een conventionele computer, en dat kan bij lange na niet.

Dat is net iets anders dan een chosen prefix collision attack, maar mensen denken vaak dat cryptografische zaken zoals sha2/sha3/aes e.d. niet tegen quantum computers bestand zijn. Wat een misverstand is.

Hashes hebben natuurlijk een bepaalt aantal bits en daarmee maar een beperkt aantal mogelijkheden, hoewel met het toenemen van het aantal bits deze aantal mogelijkheden natuurlijk erg groot zijn. Het is dus logisch dat verschillende hoeveelheden data een keer dezelfde hashes opleveren. Met het toenemen van de rekenkracht en slimme aanvallen wordt dit elke keer steeds 'makkelijker' om te doen en moeten hasking algortimes dus mee evolueren en verbeteren.

SHA, Secure Hash Algorithms: https://en.wikipedia.org/wiki/Secure_Hash_Algorithms

Het is dus logisch dat verschillende hoeveelheden data een keer dezelfde hashes opleveren.

Nee, dat lijkt zo in theorie, maar is niet zo. Er zijn bijvoorbeeld veel meer (als in, heel veel meer) Sha3-512 hashes dan er elementaire deeltjes in het universum zijn. Dus ongeacht hoe ontzagwekkend veel data we produceren, de kans is afgerond 0 dat er in de praktijk een collision tussen zit.

Tenzij we een zwakte in zo'n hashing algoritme ontdekken en specifiek data kunnen genereren die tot een collision leiden. Maar per toeval of via bruteforcen hoef je er niet op te rekenen.

Voor wie een klein beetje bewijs wil, hier een PHP snippet:
https://pastebin.com/e7MZfDBi

[Reactie gewijzigd door frank_jon op 8 januari 2020 13:03]