Kollisionsangreb

Et kollisionsangreb i kryptografi  er søgningen efter to forskellige inputblokke af en kryptografisk hashfunktion, der producerer den samme hashværdi, det vil sige en hashkollision . I modsætning til preimage-angrebet er hashværdien ikke valgt bevidst.

Rundt regnet[ klargør ] Der er to forskellige typer kollisionsangreb:

Klassisk kollisionsangreb

Kollisionsangrebet finder to forskellige meddelelser m1 og m2 sådan, at . I det klassiske tilfælde af et angreb har angriberen ingen kontrol over indholdet af beskederne, men de er tilfældigt udvalgt af algoritmen. Mange symmetriske kryptosystemer er sårbare over for brute-force-angreb , enhver kryptografisk hash-funktion er per definition sårbar over for et fødselsdagsangreb . På grund af fødselsdagsparadokset kan sidstnævnte angrebsmetode være meget hurtigere end brute force-metoden. En hash på N bit kan brydes 2n /2 gange (ved at beregne en hashfunktion). De mest effektive angreb er mulige, når du bruger kryptoanalyse på en specifik hash-funktion. Når et kollisionsangreb er hurtigere end et "fødselsdags"-angreb, bliver hash-funktioner ofte fordømt som "brudt". Oprettelsen af ​​SHA-3 hash-funktionen (konkurrence) var i høj grad drevet af behovet for at erstatte de gamle MD5 [1] og SHA-1 funktioner . Kollisionsangreb mod MD5-algoritmen er forbedret så meget, at de på en normal computer kun tager et par sekunders tid. [2] Hash-kollisioner genereret på denne måde er generelt af konstant længde og stort set ustrukturerede, så de kan ikke direkte anvendes til at angribe almindelige dokumentformater eller protokoller. Dog er løsninger mulige ved at misbruge de dynamiske konstruktioner, der findes i mange formater. Der vil således blive oprettet to dokumenter, der er identiske med hinanden, så de har samme hashværdi. Hvis et dokument er underskrevet af en betroet person, kan hans underskrift kopieres til en anden fil. Et sådant ondsindet dokument ville indeholde to forskellige meddelelser i det samme dokument, men stadig være i stand til at vise en af ​​dem gennem små ændringer i filen:

Kollisionsangreb med et givet præfiks

Resultatet af forbedringen af ​​kollisionsangrebet var kollisionsangrebet med et givet præfiks, designet til Merkle-Damgard strukturen . I dette tilfælde kan en angriber vælge 2 tilfældige forskellige dokumenter og derefter fylde dem med 2 forskellige beregnede værdier, så de 2 dokumenter ender med den samme hashværdi. Dette angreb er mere alvorligt end dets klassiske version.

Matematisk set er der 2 forskellige præfikser p1, p2 , deres 2 komplementer m1 og m2 er beregnet sådan, at hash(p1 ∥ m1) = hash(p2 ∥ m2) (hvor ∥ er sammenkædningsoperationen ) .

I 2007 blev der oprettet et præfikset MD5 hashkollisionsangreb, som krævede cirka 250 MD5 funktionsberegninger. Notatet præsenterede to X.509-certifikater for forskellige domænenavne, der har de samme hash-funktioner. Det betyder, at certifikatet for et betroet domæne kan bruges af et andet ukendt domæne. [5]

Et rigtigt kollisionsangreb blev offentliggjort i december 2008, da en gruppe sikkerhedsforskere offentliggjorde et falsk X.509 -signeringscertifikat, der kan bruges til anonymt at autorisere et certifikat ved at bruge et kollisionsangreb med et givet MD5-hash-præfiks. Dette betød, at en angriber kunne forfalske ethvert TLS -sikret websted som en mellemmand og derved overtræde certifikatvalideringen indbygget i hver webbrowser for at sikre e-handel . Et falsk certifikat kan ikke tilbagekaldes af betroede parter, det kan også have en vilkårlig tid til at udløbe. På trods af svaghederne ved MD5 fundet i 2004, [1] i december 2008 blev det klart, at mange mennesker stadig bruger certifikater med denne hash-funktion, [6] og i det mindste brugte Microsoft det stadig i maj 2012.

I Flame brugte malware med succes en ny variant af det præfikserede kollisionsangreb til at forfalske kodesigneringskomponenter ved hjælp af Microsoft-rodcertifikater, som stadig brugte den kompromitterede MD5-algoritme. [7] [8]

Angrebsskema

Mange applikationer med kryptografiske hash-funktioner kræver ikke kollisionsbeskyttelse kollisionsangreb kan ikke omgå deres beskyttelse For eksempel er HMAC'er ikke udsat for denne form for angreb. [9] For et vellykket angreb skal angriberen have kontrol over inputtet.

Elektroniske signaturer

Da elektroniske signaturalgoritmer ikke effektivt kan signere store mængder data, bruger mange tilføjelser datakomprimeringsfunktioner til at signere dem i en fast størrelse. Elektroniske signaturordninger er ofte tilbøjelige til kollisioner på trods af, at de bruger en tilfældig hash-teknik. [ti]

Normalt går angrebet sådan her:

  1. Eve opretter 2 forskellige dokumenter A og B med de samme hash-værdier. Eve søger at bedrage Bob ved at afgive sit dokument som Alices.
  2. Eve sender dokument A til Alice , som har tillid til indholdet af dokumentet, underskriver dets hash og sender signaturen til Eve.
  3. Eve vedhæfter underskriften af ​​dokument A til dokument B.
  4. Eve sender derefter signaturen og dokumentet B til Bob og hævder, at Alice har underskrevet dokumentet. Da den elektroniske signatur kun kontrollerer hashværdien af ​​dokument B, kender Bob ikke til erstatningen.

I 2008 angreb forskere præfikset MD5 ved at bruge scriptet ovenfor for at oprette et falsk certifikat. De oprettede 2 versioner af TLS offentlige nøglecertifikat, hvoraf den ene blev godkendt til RapidSSL-autorisation. En anden version, som har den samme MD5-hash-værdi, indeholdt flag, der signalerede til browseren tilliden og retten til at udstede tillid til andre certifikater [11] .

Noter

  1. ↑ 1 2 Xiaoyun Wang, Dengguo Feng, Xuejia Lai, Hongbo Yu: Collisions for Hash Functions MD4, MD5, HAVAL-128 og RIPEMD Arkiveret 23. august 2011. , Cryptology ePrint Archive Report 2004/199, 16 Aug 2004, revided 17 Aug 2004. Hentet 27. juli 2008.
  2. ↑ MJ Stevens. Om kollisioner for MD5  (neopr.) . - 2007. - Juni.
  3. ↑ Magnus Daum, Stefan Lucs. Hash Collisions (The Poisoned Message Attack) . Eurocrypt 2005 rump session . Arkiveret fra originalen den 27. marts 2010.
  4. ↑ 1 2 3 Max Gebhardt, Georg Illies, Werner Schindler. En note om den praktiske værdi af enkelthash-kollisioner for specielle filformater  (engelsk)  : tidsskrift.
  5. ↑ Marc Stevens, Arjen Lenstra, Benne de Weger. Valgt præfiks Collisions for MD5 og Colliding X.509 Certificates for Different Identities  (engelsk)  : journal. - 2007. - 30. november.
  6. ↑ Alexander Sotirov. Oprettelse af et falsk CA-certifikat (utilgængeligt link) (30. december 2008). Dato for adgang: 15. december 2015. Arkiveret fra originalen 18. april 2012. 
  7. ↑ Microsoft frigiver Security Advisory 2718704 . Microsoft (3. juni 2012). Hentet 4. juni 2012. Arkiveret fra originalen 7. juni 2012.
  8. ↑ Marc Stevens. CWI Cryptanalist opdager ny kryptografisk angrebsvariant i Flame Spy Malware . Centrum Wiskunde & Informatica (7. juni 2012). Hentet 9. juni 2012. Arkiveret fra originalen 28. februar 2017.
  9. ↑ Hash Collision Q&A . Cryptography Research Inc (15. februar 2005). "På grund af den måde, hash-funktioner bruges i HMAC-konstruktionen, gælder de teknikker, der er brugt i disse seneste angreb ikke." Arkiveret fra originalen den 17. juli 2008.
  10. ↑ Shai Halevi og Hugo Krawczyk, Randomized Hashing og Digital Signatures Arkiveret 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 for at være skadelig i dag . Chaos Communication Congress 2008. Arkiveret fra originalen 2017-03-25 . Hentet 2015-12-15 . Forældet parameter brugt |deadlink=( hjælp )

Links