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

"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.

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.

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

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.

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.

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.

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.

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.