Kollisionsattack

I kryptografi försöker en kollisionsattack på en kryptografisk hash hitta två ingångar som producerar samma hashvärde, dvs en hashkollision . Detta till skillnad från en preimage-attack där ett specifikt mål-hashvärde anges.

Det finns ungefär två typer av kollisionsattacker:

Klassisk kollisionsattack
Hitta två olika meddelanden m 1 och m 2 så att hash ( m 1 ) = hash ( m 2 ).

Mer allmänt:

Kollisionsattack med valt prefix
Givet två olika prefix p 1 och p 2 , hitta två appendage m 1 och m 2 så att hash ( p 1 ∥ m 1 ) = hash ( p 2 ∥ m 2 ), där ∥ betecknar sammanlänkningsoperationen .

Klassisk kollisionsattack

Matematiskt uttryckt hittar en kollisionsattack två olika meddelanden m1 och m2 , så att hash(m1) = hash(m2) . I en klassisk kollisionsattack har angriparen ingen kontroll över innehållet i något av meddelandena, utan de väljs godtyckligt av algoritmen.

Ungefär som symmetriska nyckelchiffer är sårbara för brute force-attacker , är varje kryptografisk hashfunktion i sig sårbar för kollisioner med en födelsedagsattack . På grund av födelsedagsproblemet är dessa attacker mycket snabbare än en brute force skulle vara. En hash på n bitar kan brytas i 2 n /2 tidssteg (utvärderingar av hashfunktionen).

Mer effektiva attacker är möjliga genom att använda kryptoanalys till specifika hashfunktioner. När en kollisionsattack upptäcks och visar sig vara snabbare än en födelsedagsattack, fördöms en hashfunktion ofta som "trasig". NIST -hashfunktionskonkurrensen inducerades till stor del av publicerade kollisionsattacker mot två mycket vanliga hashfunktioner, MD5 och SHA-1 . Kollisionsattackerna mot MD5 har förbättrats så mycket att det från och med 2007 tar bara några sekunder på en vanlig dator. Hash-kollisioner som skapas på detta sätt är vanligtvis konstanta och till stor del ostrukturerade, så de kan inte direkt användas för att attackera utbredda dokumentformat eller protokoll.

Lösningar är dock möjliga genom att missbruka dynamiska konstruktioner som finns i många format. På så sätt skulle två dokument skapas som är så lika som möjligt för att få samma hashvärde. Ett dokument skulle visas för en myndighet för att undertecknas, och sedan kunde signaturen kopieras till den andra filen. Ett sådant skadligt dokument skulle innehålla två olika meddelanden i samma dokument, men villkorligt visa det ena eller det andra genom subtila ändringar i filen:

  • Vissa dokumentformat som PostScript eller makron i Microsoft Word har villkorliga konstruktioner. (if-then-else) som tillåter att testa om en plats i filen har ett eller annat värde för att kontrollera vad som visas.
  • TIFF- filer kan innehålla beskurna bilder, med en annan del av en bild som visas utan att det påverkar hashvärdet.
  • PDF- filer är sårbara för kollisionsattacker genom att använda färgvärden (såsom att texten i ett meddelande visas med en vit färg som smälter in i bakgrunden, och texten i det andra meddelandet visas med en mörk färg) som sedan kan ändras för att ändras det undertecknade dokumentets innehåll.

Kollisionsattack med valt prefix

En förlängning av kollisionsattacken är den valda-prefixet kollisionsattack, som är specifik för Merkle–Damgårds hashfunktioner . I det här fallet kan angriparen välja två godtyckligt olika dokument, och sedan lägga till olika beräknade värden som resulterar i att hela dokumenten har ett lika stort hashvärde. Denna attack är mycket kraftfullare än en klassisk kollisionsattack.

Matematiskt uttryckt, givet två olika prefix p 1 , p 2 , hittar attacken två bihang m 1 och m 2 så att hash ( p 1 ∥ m 1 ) = hash ( p 2 ∥ m 2 ) (där ∥ är sammanlänkningsoperationen ) .

2007 hittades en kollisionsattack med valt prefix mot MD5, vilket krävde ungefär 2 50 utvärderingar av MD5-funktionen. Tidningen visar också två X.509 -certifikat för olika domännamn, med kolliderande hashvärden. Detta innebär att en certifikatutfärdare kan bli ombedd att signera ett certifikat för en domän, och sedan kan det certifikatet (speciellt dess signatur) användas för att skapa ett nytt oseriöst certifikat för att imitera en annan domän.

En kollisionsattack i verkligheten publicerades i december 2008 när en grupp säkerhetsforskare publicerade ett förfalskat X.509 -signeringscertifikat som kunde användas för att utge sig för att vara en certifikatutfärdare och utnyttjade en prefixkollisionsattack mot MD5-hashfunktionen. Detta innebar att en angripare kunde utge sig för att vara vilken SSL -säkrad webbplats som helst som en man-in-the-midten, och därigenom undergräva certifikatvalideringen inbyggd i varje webbläsare för att skydda elektronisk handel . Det falska certifikatet kanske inte kan återkallas av verkliga myndigheter och kan också ha en godtycklig förfalskad utgångstid. Även om MD5 var känt för att vara mycket svagt 2004, var certifikatmyndigheter fortfarande villiga att signera MD5-verifierade certifikat i december 2008, och åtminstone ett Microsoft-kodsigneringscertifikat använde fortfarande MD5 i maj 2012.

Flame använde framgångsrikt en ny variant av en kollisionsattack med valt prefix för att förfalska kodsignering av dess komponenter med ett Microsoft-rotcertifikat som fortfarande använde den komprometterade MD5-algoritmen.

Under 2019 hittade forskare en kollisionsattack med valt prefix mot SHA-1 med datorkomplexitet mellan 2 66,9 och 2 69,4 och kostade mindre än 100 000 US-dollar. År 2020 minskade forskare komplexiteten i kollisionsattack med valt prefix mot SHA-1 till 2 63,4 .

Attackscenarier

Många tillämpningar av kryptografiska hashfunktioner förlitar sig inte på kollisionsmotstånd , så kollisionsattacker påverkar inte deras säkerhet. Till exempel HMAC inte sårbara. För att attacken ska vara användbar måste angriparen ha kontroll över inmatningen till hashfunktionen.

Digitala signaturer

Eftersom digitala signaturalgoritmer inte kan signera en stor mängd data effektivt använder de flesta implementeringar en hash-funktion för att minska (komprimera) mängden data som behöver signeras till en konstant storlek. Digitala signatursystem blir ofta sårbara för hashkollisioner så snart den underliggande hashfunktionen praktiskt taget bryts; tekniker som randomiserad (saltad) hashing kommer att köpa extra tid genom att kräva den hårdare preimage-attacken .

Det vanliga attackscenariot ser ut så här:

  1. Mallory skapar två olika dokument A och B som har ett identiskt hashvärde, dvs en kollision. Mallory försöker lura Bob att acceptera dokument B, skenbart från Alice.
  2. Mallory skickar dokument A till Alice , som går med på vad dokumentet säger, signerar dess hash och skickar signaturen till Mallory.
  3. Mallory bifogar signaturen från dokument A till dokument B.
  4. Mallory skickar sedan signaturen och dokumentet B till Bob och hävdar att Alice signerat B. Eftersom den digitala signaturen matchar dokument B:s hash, kan Bobs programvara inte upptäcka ersättningen.

Under 2008 använde forskare en kollisionsattack med valt prefix mot MD5 med detta scenario för att producera ett falskt certifikat från certifikatutfärdare . De skapade två versioner av ett TLS -certifikat med offentlig nyckel , varav en verkade legitim och skickades in för signering av RapidSSL-certifikatmyndigheten. Den andra versionen, som hade samma MD5-hash, innehöll flaggor som signalerar webbläsare att acceptera den som en legitim auktoritet för att utfärda godtyckliga andra certifikat.

Hashöversvämning

Hash flooding (även känd som HashDoS ) är en överbelastningsattack som använder hashkollisioner för att utnyttja den värsta (linjära sond) körtiden för hashtabelluppslagningar . Den beskrevs ursprungligen 2003. För att utföra en sådan attack skickar angriparen servern flera bitar av data som hash till samma värde och försöker sedan få servern att utföra långsamma sökningar. Eftersom huvudfokus för hashfunktioner som användes i hashtabeller var hastighet istället för säkerhet, påverkades de flesta större programmeringsspråk, med nya sårbarheter i denna klass som fortfarande dyker upp ett decennium efter den ursprungliga presentationen.

För att förhindra hashöversvämning utan att göra hashfunktionen alltför komplex, introduceras nyare nyckelhashfunktioner , med säkerhetsmålet att kollisioner är svåra att hitta så länge nyckeln är okänd. De kan vara långsammare än tidigare hash, men är fortfarande mycket lättare att beräkna än kryptografiska hash. Från och med 2021 Daniel J. Bernsteins SipHash ( 2012) den mest använda hashfunktionen i den här klassen. (Icke-nycklade "enkla" hashar förblir säkra att använda så länge som programmets hashtabell inte kan styras från utsidan.)

Det är möjligt att utföra en analog attack för att fylla upp Bloom-filter med hjälp av en (delvis) förbildsattack.

externa länkar

Hämtad från " https://en.wikipedia.org/w/index.php?title=Collision_attack&oldid=1138239916 "