Google efter 6.500 CPU-år: Nu er kollisioner med SHA-1 virkelighed

Det er ikke længere blot en teoretisk mulighed at skabe to dokumenter, der får den samme hash-værdi med SHA-1-algoritmen.

Det er nu for alvor blevet tid til at sende SHA-1 på pension som hash-algoritme til sikkerhedsformål. Det er i hvert fald konklusionen fra Googles sikkerhedsafdeling, som har fremvist det første eksempel på en kollision i SHA-1.

En kollision i en hash-algoritme betyder, at to forskellige input giver det samme output, altså eksempelvis to forskellige dokumenter, der giver den samme hashværdi.

Det er der i princippet flere hashfunktioner, der gør, men det afgørende er, dels at sandsynligheden for at det sker tilfældigt er urealistisk, og dels at det ikke er muligt fremprovokere en kollision - altså hvis man kender ét dokument og dets hash-værdi, så skal man ikke kunne regne sig frem til et andet dokument, der får samme hashværdi.

Læs også: MD5, SHA-1 eller Scrypt: Er dine brugeres kodeord (forsvarligt) krypteret?

Problemet med kollisioner er, hvis en hashværdi bruges kryptografisk til eksempelvis at bekræfte, at et dokument sendt fra Alice til Bob ikke er blevet opsnappet og ændret. Hvis Eva lytter med, så kan Eva udnytte en kollision til at lave et ændret dokument, der har samme hashværdi.

I 2013 blev en teoretisk mulighed for kollisioner i SHA-1 fremsat, og det er på baggrund af det arbejde, at Google har forsøgt at demonstrere, at det kan lade sig gøre i virkeligheden.

SHA-1 er nemlig også blevet brugt til de certifikater, som bruges til at sikre forbindelser på internettet ved hjælp af TLS-protokollen. Så kollisioner i SHA-1 kan altså underminere sikkerheden i de sikre forbindelser. Derfor er Googles egen Chrome-browser begyndt at advare mod sider, som benytter SHA-1 til at signere forbindelsen.

Det angreb, Google har demonstreret, har dog ikke været let. Først skulle Google skabe en del af et PDF-dokument, som tillod forskelligt indhold i dokumentet, men ville give samme hashværdi.

Beregningsopgaven er én af de største, Google nogensinde har foretaget. De to faser krævede henholdsvis 6.500 CPU-år, når man omregner til regnekraften i én processorkerne, og 110 GPU-år på grafikprocessorer. I alt 9.223.372.036.854.775.808 SHA-1 beregninger.

Læs også: Derfor kan gamer-pc’er knække dårligt opbevarede kodeord som pindebrænde

Det er en massiv mængde udregninger, men det er stadig 100.000 gange hurtigere, end det teoretisk ville tage, hvis man blot prøvede sig frem med et brute force-angreb.

Selvom der er et stykke vej fra Googles resultat til en realistisk trussel mod de fleste websteder, så anbefaler Google, at man skifter eksempelvis sine webstedscertifikater fra SHA-1 til en nyere algoritme så som SHA-3 eller SHA-256, hvor der endnu ikke er fundet mulighed for at finde frem til kollisioner.

Tips og korrekturforslag til denne historie sendes til tip@version2.dk
Følg forløbet
Kommentarer (8)
sortSortér kommentarer
  • Ældste først
  • Nyeste først
  • Bedste først
Michael Aggerholm

"Selvom der er et stykke vej fra Googles resultat til en realistisk trussel mod de fleste websteder, så anbefaler Google, at man skifter eksempelvis sine webstedscertifikater fra SHA-1 til en nyere algoritme så som SHA-3 eller SHA-256, hvor der endnu ikke er fundet mulighed for at finde frem til kollisioner."

Det vil altid være muligt at finde to inputs der giver samme hash, det ligger lidt i naturen for et hash. Det er kun et spørgsmål om hvor sandsynligt det er. Og selvom du kan finde en kollision så vil det input du står med formentlig ikke kunne tjene ret mange formål udover at vise at det kan lade sig gøre.

Og her mener jeg nok at der bliver pisket lidt af en stemning op, for hvem har lige 6500 CPU år til at gennemføre et forøvrigt meget teoretisk angreb på et SSL certifikat? Jeg vil mene at der nok er adskillige hundrede andre metoder man først vil afprøve, og formentlig med noget større succes.

Det Google har lavet er et form for proof of concept på hvor langt man skulle gå for at fremprovokere en kollision. Det er interessant fra en akademisk vinkel men næppe mere end det.

  • 1
  • 2
Jakob Jakobsen

Du foreslår måske at vi fortsat anvender SHA-1, som i årevis har været anset for knækket, og nu har vist kollisioner i praksis, og så venter på at nogen formår at spoofe certifikater og hugger dine dankort oplysninger?

Der er ingen grund til ikke at være på forkant, og skifte til et sikkert alternativ inden du står med et reelt sikkerhedsproblem.

  • 1
  • 0
Henning Wangerin

Der er ingen grund til ikke at være på forkant, og skifte til et sikkert alternativ inden du står med et reelt sikkerhedsproblem.

Nej, menm derfra og til at konstatere at SHA1 er død er der nu et stykke vej.

En ting er at "Du har foræret mig dit hus" og "qwertyuiasdfghjkl" giver samme hash. En helt anden ting ar at de kunne bruge de to tekster som erstatning for noget som helst. For at kollisionen bliver et rigtigt problem skal kilden til kollisionen jo stadigvæk give mening i konteksten.

Og SHA256 har da også kollisioner. Der skal bare mange flere forsøg til. Helt ligesom CRC16 hvor der trods alt vil være et potentielt hit for hvor 65000 forsøg. Google skulle gennem 9.223.372.036.854.775.808 forsøg for at finde et "tilfældigt" hit med SHA1. Hvor mange der mon skal til med SHA256 ?

/Henning

  • 0
  • 0
Jakob Jakobsen

Hvor mange der mon skal til med SHA256 ?


Lad os regne på det. Det tog ~2⁶³ SHA-1 beregninger at finde en kollision for dens 160 bit output, hvilket stemmer... nogenlunde med at sikkerheden af SHA-1 er reduceret fra 2⁸⁰ til 2⁵⁷ (https://en.wikipedia.org/wiki/SHA-1#The_SHAppening).

SHA256 derimod har ingen kendte angreb pt, og med dens 256 bit output må det være en fair antagelse at det vil kræve 2¹²⁸ eller 340282366920938463463374607431768211456 beregninger for at finde en kollision.

Så ja, der skal "bare" mange flere forsøg til.

  • 0
  • 0
Erik Andersen

Det giver min anledning til at ride en af mine kæpheste.

Man kan have alle sikkerhedsprocedurer i verden, persondatalove, osv., men det hjælper ikke, hvis IT produkterne sikkerhedsmæssigt er hullede som en si. Der er sikkert masser af systemer og certifikater derude baseret på SHA-1 og måske endda MD5.
Der findes masser af information om svagheder og trusler, men den information er ikke konsolideret i produktspecifikationer, dvs. international sikkerheds-standarder. Det er en myndighedsopgave, som langt hen af vejen ignoreres.

  • 0
  • 0
Baldur Norddahl

for hvem har lige 6500 CPU år til at gennemføre et forøvrigt meget teoretisk angreb på et SSL certifikat?

Det er kun 110 GPU år. Selv private kan tænkes at købe 100 grafikkort til tusind kr stykket. Køber du 1000 grafikkort kan du lave angrebet på en måned på en investering på 1 million kr. Med 10.000 grafikkort kan det gøres på en forlænget weekend. Bitcoin miners har allerede den slags klynger til rådighed.

Angrebet kan eksempelvis være på en digital underskrift på et skøde. Pludselig har du solgt en anden ejendom end den du regnede med. Inden du ved det, er ejendommen videresolgt og gerningsmændene stukket af med pengene.

  • 1
  • 1
Michael Cederberg

Og her mener jeg nok at der bliver pisket lidt af en stemning op, for hvem har lige 6500 CPU år til at gennemføre et forøvrigt meget teoretisk angreb på et SSL certifikat? Jeg vil mene at der nok er adskillige hundrede andre metoder man først vil afprøve, og formentlig med noget større succes.

Selvfølgeligt er det ikke noget stort problem lige nu, men man har opdaget botnet med betydeligt flere CPU'er. Og selvom ingen vil smide den slags ressourcer på at tømme din bankkonto, så kunne det fx bruges til at fake et dokument "signeret" af den franske regering om at jeg nu ejede eiffeltårnet. Så mangler jeg bare at finde penge til vedligeholdelsen :-)

Mere seriøst, så holder IT systemer længe. Der er stadigvæk systemer der krypterer vha. DES selvom man de sidste 30 år har vidst at man skulle holde op. Brug af MD5 og SHA-1 kan kun stoppe for langsomt.

  • 0
  • 0
Michael Aggerholm

Jeg synes det er forkert at tænke på det her som at "knække" SHA-1. Der er tale om en funktion med et gigantisk udfaldsrum, der dog lige præcis er indenfor rækkevidden af en organisation som Google, når det handler om at finde to inputs der giver samme hashværdi.

Jeg foreslår ikke at vi ikke kigger på bedre algoritmer, blot at der slet ikke er behov for at drive sensationsjournalistik på det. Der går stadigvæk år før SHA-1 kollisioner vil være noget man trivielt kan finde på en eftermiddag. Jeg synes det er spændende hvad Google har lavet ud fra en akademisk betragtning men heller ikke mere.

Og til ham der foreslog at kriminelle ville kunne sælge mit hus, så er det jo sådan at det "alternative input" der giver en hash kollision på mit skøde jo ikke tilnærmelsesvis vil ligne et skøde, selvom det har samme hashværdi. Kriminelle vil være nødt til at finde en kollision på et skøde med et indhold der ligner det oprindelige men med en anden pris, eller køber for eksempel. Og det vil ikke være muligt.

Desuden er det jo ikke helt så let at forfalske skøder da de jo er tinglyste.

Jeg synes der er meeeget langt fra det Google har vist til de mange mærkelige skræmmeeksempler der beskrives ovenfor. Sælge mit hus? Tømme min bankkonto?

Altså ... alt er muligt hvis man har penge nok selvfølgelig. Men det har de fleste jo ikke. Og jeg er alligevel ikke interessant nok som mål for kriminelle til at de går ud og køber 10.000 grafikkort i et bizart forsøg på at overtage mit hus. Som jeg skrev så er der masser af bedre muligheder for den slags, herunder at tage ud til mig og tvinge mig til at skrive under på skødet. Det er meget billigere.

  • 1
  • 0
Log ind eller Opret konto for at kommentere