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:
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:
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]
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.
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:
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] .