CWI en Google onthullen collision-aanval op sha-1-algoritme
Onderzoekers van het Centrum Wiskunde & Informatica (CWI) in Amsterdam en Google hebben een succesvolle collision-aanval op het sha-1-algoritme uitgevoerd dat een belangrijke rol speelt bij internetbankieren, het signeren van documenten en allerlei andere zaken, zo heeft het CWI en Google bekendgemaakt. Het secure hash algorithm (sha) is een hashfunctie die van data een unieke hashcode maakt.
Een hashingalgoritme wordt als veilig beschouwd als het voor elke willekeurige invoer een unieke uitvoer heeft en dat die uitvoer niet is terug te draaien zodat de invoer achterhaald kan worden. Doordat de uitvoer niet is te manipuleren worden hashes gebruikt om bijvoorbeeld de geldigheid van certificaten en bestanden aan te tonen en het gehasht opslaan van wachtwoorden. Sinds 2005 zijn er echter collision-aanvallen op het sha-1-algoritme bekend waar verschillende invoer dezelfde uitvoer geeft.
Al sinds 2011 wordt daarom aangeraden sha-1 uit te faseren, maar het algoritme is nog altijd in gebruik. "Onze resultaten bewijzen dat het uitfaseren door een groot deel van de industrie veel te langzaam is geweest en het migreren naar een veiligere standaard zo snel als mogelijk moet plaatsvinden", zegt CWI-onderzoeker Marc Stevens. Het CWI en Google begonnen meer dan twee jaar geleden om het onderzoek van Stevens met de infrastructuur van Google te combineren voor het kraken van sha-1 via een collision-aanval. Door een collision-aanval is het mogelijk om digitale handtekeningen te vervalsen. Zo kan een sha-1-handtekening voor het ene bestand ook voor een andere bestand worden gebruikt.
"Het vinden van de collision vereiste 9.223.372.036.854.775.808 sha-1-berekeningen die 6500 jaar aan cpu-rekenkracht en 100 jaar aan gpu-rekenkracht in beslag namen. Toch is dit nog altijd 100.000 keer sneller dan het uitvoeren van een brute-force-aanval", zegt Google-onderzoeker Ellie Bursztein. Voor de aanval werd dezelfde infrastructuur gebruikt die ook voor verschillende kunstmatige intelligentieprojecten van Google wordt gebruikt, zoals Alpha Go en Google Photo, alsmede Google Cloud.
Stevens wijst voor de impact van de nu onthulde aanval naar het verleden, toen de voorloper van sha-1, het md5-algoritme, werd gekraakt. Een aanvaller wist op deze manier valse Windows-updates te verspreiden. Voor hun aanval slaagden Stevens en Google erin om twee verschillende pdf-bestanden van dezelfde sha-1-vingerafdruk te voorzien. Om vervalste pdf-documenten te herkennen hebben de onderzoekers een gratis tool online gezet die naar sha-1-collisions in documenten zoekt. Meer informatie over de aanval is te vinden op shattered.io.
Voor een collision is de "brute force" bovengrens de helft van de hashlengte - voor sha-1, met een hashlengte van 160 bits is dat 80 bits "werk".
De "brute force" aanval heet een "birthday attack", en dat is op basis van dezelfde statistiek voor het aantal mensen wat je nodig hebt om een 50% kans te hebben dat twee mensen in de groep op dezelfde dag jarig zijn.
Die kans heb je al bij een groep van 23 mensen - een verbazingwekkend laag aantal .
Die limiet voor grote getallen is 2^(n/2) , als n de lengte van het getal in bits is - dus 2^80 voor sha-1
Met slimme wiskunde zijn blijkbaar 17 bits aan werk (2^17 , ca 130.000 ) bespaard .
Omdat de birthday attack ook een statistische grens is, denk ik dat dit getal ook gelezen moet worden als "Orde(2^63)" en niet het exacte aantal hashes.
...als ze hebben zitten wachten op deze melding, dan zijn ze ongeveer 7 jaar te laat.
Laten we hopen dat banken en andere spannende partijen al lang(er) geleden zijn begonnen met het uitfaseren van SHA-1.
Sha-1 staat al een tijdje afgeraden. Zie ook geen meer die het publiek gebruikt.
Bedoelen jullie dat het algoritme deterministisch is of dat de kans dat 2 verschillende invoeren eenzelfde uitvoer hebben extreem klein is?
Bedoelen jullie dat het algoritme deterministisch is of dat de kans dat 2 verschillende invoeren eenzelfde uitvoer hebben extreem klein is?
Allebei. Natuurlijk is een hash deterministisch (zelfde invoer geeft zelfde hash). Zelfde hash bij verschillende invoer heet "collision" en daar gaat dit artikel over. Dus SHA1 is klaarblijkelijk niet collision-free, SHA2 (hopelijk) wel.
En daarbij, de alternatieve data waarbij een hash colission optreedt kun je als aanvaller niet zelf bepalen, dus het is niet mogelijk om zomaar even een bedrag in een contract te wijzigen zonder gigantisch veel hooi aan de speld toe te voegen en het bestand behoorlijk af te laten wijken in omvang, of door een groot deel van het bestand te wijzigen. De kans dat je specifieke programmacode kan toevoegen of aanpassen terwijl de omvang en hash gelijk blijven is wel nihil. Theoretisch is het mogelijk, maar dat geld ook voor een vliegje dat een containerschip laat zinken.
Bedoelen jullie dat het algoritme deterministisch is of dat de kans dat 2 verschillende invoeren eenzelfde uitvoer hebben extreem klein is?
Allebei. Natuurlijk is een hash deterministisch (zelfde invoer geeft zelfde hash). Zelfde hash bij verschillende invoer heet "collision" en daar gaat dit artikel over. Dus SHA1 is klaarblijkelijk niet collision-free, SHA2 (hopelijk) wel.
Nitpickje : zodra de invoer groter is dan de hashlengte is het gegarandeerd _dat_ er collisions moeten zijn.
(wiskundige term 'pigeon hole principle' - 11 duiven voor 10 hokken betekent dat er gegarandeerd minimaal 1 hok meer dan 1 duif bevat)
De eis voor security gebruik is alleen dat het vinden daarvan 'onmogelijk moeilijk' moet zijn, en er geen betere manier dan brute force (cq birthday attack voor collisions) zou moeten zijn.
Voor sha-1 is het vinden van een collision 2^17 makkelijker dan "zou moeten", en daardoor binnen bereik gekomen van een nog steeds heel stevige zoektocht.
Bedoelen jullie dat het algoritme deterministisch is of dat de kans dat 2 verschillende invoeren eenzelfde uitvoer hebben extreem klein is?
Allebei. Natuurlijk is een hash deterministisch (zelfde invoer geeft zelfde hash). Zelfde hash bij verschillende invoer heet "collision" en daar gaat dit artikel over. Dus SHA1 is klaarblijkelijk niet collision-free, SHA2 (hopelijk) wel.
De grote vraag is, kan men met de huidige rekenkracht binnen afzienbare tijd een collision vinden? Bij SHA-1 is het antwoord nu niet alleen meer theoretisch maar ook praktisch ja. Bij SHA-2 is het antwoord (voor zover publiek bekend) nog nee, daarom kan het nog gebruikt worden.
Bedoelen jullie dat het algoritme deterministisch is of dat de kans dat 2 verschillende invoeren eenzelfde uitvoer hebben extreem klein is?
Allebei. Natuurlijk is een hash deterministisch (zelfde invoer geeft zelfde hash). Zelfde hash bij verschillende invoer heet "collision" en daar gaat dit artikel over. Dus SHA1 is klaarblijkelijk niet collision-free, SHA2 (hopelijk) wel.
Iedere hash-functie heeft collisions, en ook SHA2 is niet collision-free. Dat is het concept van een hash-functie: in plaats van het originele document gebruik je de veel kortere hash. Het grote probleem bij SHA1 is dat er een algoritme bedacht is om sneller zelf een collision te kunnen genereren. Nouja, snel: 100 jaar met speciale hardware. Maar snel genoeg voorals er echt geld me te verkrijgen is.
De lengte van een SHA1 hash is 160 bits, en van SHA2 is 256 bits. Even uitgaan van de melding van Anoniem 17:15 zou de orde van grootte van het probleem rond de 2^128 liggen. Ofwel, zo lang er niet via een slim mechanisme (de CWI uitvinding) 2^17 vanaf gehaald wordt, zal het met dezelfde hardware dus 2^128 - 2^63 = 2^65 keer zo lang duren. En als ze dit met miljoen (2^20) machines tegelijk doen nog steeds 2^54 keer zo lang. Ter indicatie: dat is in de orde van 1801439850 miljard jaar...
Q
Sha-1 staat al een tijdje afgeraden. Zie ook geen meer die het publiek gebruikt.
GIT, AWS, ... allemaal SHA-1 based, het word nog massaal gebruikt!
Deze posting is gelocked. Reageren is niet meer mogelijk.
Specialiseer je in Forensisch ICT
Online informatieavond 19 november
Wil jij je specialiseren in digitaal forensisch onderzoek? Je kennis verbreden en tech-nische vaardigheden ontwikkelen? Ontdek de cursus- en opleidingsmogelijkheden van Hogeschool Leiden:
- Bachelor Informatica Forensisch ICT (deeltijd)
- Master Digital Forensics (vol- en deeltijd)
- Module Mobile Forensics
- Module Data Analytics
Interesse? Meld je aan!
Information Security Officer (2fte)
Een uitdagende rol waarbij jij, op basis van security, de vertaalslag maakt tussen business en IT en direct bijdraagt aan de veiligheid van informatie binnen de gemeente Almere. Dat is in een notendop waar jij als Information Security Officer mee bezig bent. Interesse gewekt? Door groei van de organisatie zijn we op zoek naar twee nieuwe collega’s.
Cybersecurity Trainer / Streamer
Toe aan een nieuwe nieuwe job waarmee je het verschil maakt? In de Certified Secure trainingen laat je deelnemers zien hoe actuele kwetsbaarheden structureel verholpen worden. Ook werk je actief mee aan de ontwikkeling van onze gamified security challenges. Bij het maken van challenges kom je telkens nieuwe technieken tegen, van Flutter tot GraphQL, van Elastic Search tot Kubernetes.
