Kollisionsattack

En kollisionsattack i kryptografi  är sökningen efter två olika indatablock för en kryptografisk hashfunktion som producerar samma hashvärde, det vill säga en hashkollision . Till skillnad från preimage-attacken är hashvärdet inte valt medvetet.

Ungefär[ förtydliga ] Det finns två olika typer av kollisionsattacker:

Klassisk kollisionsattack

Kollisionsattacken hittar två olika meddelanden m1 och m2 så att . I det klassiska fallet med en attack har angriparen ingen kontroll över innehållet i meddelandena, utan de är slumpmässigt valda av algoritmen. Många symmetriska kryptosystem är sårbara för brute-force-attacker , alla kryptografiska hashfunktioner är per definition sårbara för en födelsedagsattack . På grund av födelsedagsparadoxen kan den senare attackmetoden vara mycket snabbare än brute force-metoden. En hash med N bitar kan brytas 2n /2 gånger (genom att beräkna en hashfunktion). De mest effektiva attackerna är möjliga när man använder kryptoanalys på en specifik hashfunktion. När en kollisionsattack är snabbare än en "födelsedagsattack" fördöms hashfunktioner ofta som "trasiga". Skapandet av SHA-3-hashfunktionen (tävling) drevs till stor del av behovet att ersätta de gamla MD5 [1] - och SHA-1- funktionerna . Kollisionsattacker mot MD5-algoritmen har förbättrats så mycket att de på en vanlig dator bara tar några sekunders tid. [2] Hash-kollisioner som genereras på detta sätt är i allmänhet av konstant längd och till stor del ostrukturerade, så de kan inte direkt appliceras för att attackera vanliga dokumentformat eller protokoll. Lösningar är dock möjliga genom att missbruka de dynamiska konstruktionerna som finns i många format. Det kommer alltså att skapas två dokument som är identiska med varandra så att de har samma hashvärde. Om ett dokument är undertecknat av en betrodd person, kan hans underskrift kopieras till en annan fil. Ett sådant skadligt dokument skulle innehålla två olika meddelanden i samma dokument, men ändå kunna visa något av dem genom små ändringar i filen:

Kollisionsattack med ett givet prefix

Resultatet av förbättringen av kollisionsattacken var kollisionsattacken med ett givet prefix, designat för Merkle-Damgard-strukturen . I det här fallet kan en angripare välja 2 slumpmässiga olika dokument och sedan fylla på dem med 2 olika beräknade värden så att de 2 dokumenten slutar med samma hashvärde. Denna attack är allvarligare än den klassiska versionen.

Matematiskt sett finns det 2 olika prefix p1, p2 , deras 2 komplement m1 och m2 beräknas så att hash( p1 ∥ m1) = hash(p2 ∥ m2) (där ∥ är sammanlänkningsoperationen ).

Under 2007 skapades en MD5-hashkollisionsattack med prefix, som krävde cirka 250 MD5- funktionsberäkningar. I anteckningen presenterades två X.509-certifikat för olika domännamn som har samma hashfunktion. Detta innebär att certifikatet för en betrodd domän kan användas av en annan okänd domän. [5]

En riktig kollisionsattack publicerades i december 2008 när en grupp säkerhetsforskare publicerade ett falskt X.509- signeringscertifikat som kan användas för att anonymt auktorisera ett certifikat genom att använda en kollisionsattack med ett givet MD5-hashprefix. Detta innebar att en angripare kunde förfalska vilken TLS -säkrad webbplats som helst som en mellanhand och därigenom bryta mot certifikatvalideringen inbyggd i varje webbläsare för att säkra e-handeln . Ett falskt certifikat kan inte återkallas av betrodda parter, det kan också ha en godtycklig tid att förfalla. Trots svagheterna i MD5 som hittades 2004, [1] i december 2008 blev det klart att många människor fortfarande använder certifikat med denna hashfunktion, [6] och åtminstone Microsoft använde den fortfarande i maj 2012.

I Flame använde skadlig programvara framgångsrikt en ny variant av den prefixerade kollisionsattacken för att förfalska kodsigneringskomponenter med hjälp av Microsofts rotcertifikat, som fortfarande använde den komprometterade MD5-algoritmen. [7] [8]

Angreppsschema

Många applikationer med kryptografiska hashfunktioner kräver inte kollisionsskydd kollisionsattacker kan inte kringgå deras skydd Till exempel är HMAC inte föremål för denna typ av attack. [9] För en framgångsrik attack måste angriparen ha kontroll över inmatningen.

Elektroniska signaturer

Eftersom elektroniska signaturalgoritmer inte effektivt kan signera stora mängder data använder många tillägg datakomprimeringsfunktioner för att signera dem i en fast storlek. Elektroniska signatursystem är ofta utsatta för kollisioner trots att de använder en slumpmässig hashteknik. [tio]

Vanligtvis går attacken så här:

  1. Eve skapar 2 olika dokument A och B med samma hashvärden. Eve försöker lura Bob genom att låta hennes dokument vara Alices.
  2. Eve skickar dokument A till Alice , som litar på innehållet i dokumentet, undertecknar dess hash och skickar signaturen till Eve.
  3. Eve bifogar underskriften av dokument A till dokument B.
  4. Eve skickar sedan signaturen och dokumentet B till Bob och hävdar att Alice undertecknat dokumentet. Eftersom den elektroniska signaturen endast kontrollerar hashvärdet för dokument B, känner Bob inte till ersättningen.

2008 attackerade forskare prefixet MD5 med hjälp av skriptet ovan för att skapa ett falskt certifikat. De skapade två versioner av TLS -certifikatet för den offentliga nyckeln, varav en autentiserades för RapidSSL-auktorisering. En annan version, som har samma MD5-hashvärde, innehöll flaggor som signalerade till webbläsaren förtroendet och rätten att utfärda förtroende för andra certifikat [11] .

Anteckningar

  1. ↑ 1 2 Xiaoyun Wang, Dengguo Feng, Xuejia Lai, Hongbo Yu: Kollisioner för hashfunktioner MD4, MD5, HAVAL-128 och RIPEMD Arkiverad 23 augusti 2011. , Cryptology ePrint Archive Report 2004/199, 16 aug 2004, revided 17 aug 2004. Retrieved July 27, 2008.
  2. ↑ MJ Stevens. Om kollisioner för MD5  (neopr.) . - 2007. - Juni.
  3. ↑ Magnus Daum, Stefan Lucks. Hash Collisions (The Poisoned Message Attack) . Eurocrypt 2005 rump session . Arkiverad från originalet den 27 mars 2010.
  4. ↑ 1 2 3 Max Gebhardt, Georg Illies, Werner Schindler. En anteckning om det praktiska värdet av enstaka hashkollisioner för speciella filformat  (engelska)  : journal.
  5. ↑ Marc Stevens, Arjen Lenstra, Benne de Weger. Valt prefix Collisions for MD5 och Colliding X.509 Certificates for Different Identities  (engelska)  : journal. - 2007. - 30 november.
  6. ↑ Alexander Sotirov. Skapa ett falskt CA-certifikat (otillgänglig länk) (30 december 2008). Datum för åtkomst: 15 december 2015. Arkiverad från originalet den 18 april 2012. 
  7. ↑ Microsoft släpper säkerhetsrådgivning 2718704 . Microsoft (3 juni 2012). Hämtad 4 juni 2012. Arkiverad från originalet 7 juni 2012.
  8. ↑ Marc Stevens. CWI Cryptanalist upptäcker ny kryptografisk attackvariant i Flame Spy Malware . Centrum Wiskunde & Informatica (7 juni 2012). Hämtad 9 juni 2012. Arkiverad från originalet 28 februari 2017.
  9. ↑ Frågor och svar på hashkollision . Cryptography Research Inc (15 februari 2005). "På grund av hur hash-funktioner används i HMAC-konstruktionen, gäller inte teknikerna som används i dessa senaste attacker." Arkiverad från originalet den 17 juli 2008.
  10. ↑ Shai Halevi och Hugo Krawczyk, Randomized Hashing och digitala signaturer arkiverade 20 juni 2009 på Wayback Machine
  11. ↑ Alexander Sotirov, Marc Stevens, Jacob Appelbaum, Arjen Lenstra, David Molnar, Dag Arne Osvik, Benne de Weger (30 december 2008). MD5 anses vara skadligt idag . Chaos Communication Congress 2008. Arkiverad från originalet 2017-03-25 . Hämtad 2015-12-15 . Utfasad parameter används |deadlink=( hjälp )

Länkar