Kolissionangriff
Kollisionsangriff auf einen kryptografischen Hash versucht, zwei Eingaben zu finden, die denselben Hash-Wert erzeugen, d. H. Eine Hash-Kollision. Dies steht im Gegensatz zu einem Ursprungsangriff, bei dem ein bestimmter Ziel-Hash-Wert angegeben wird.
Es gibt ungefähr zwei Arten von Kollisionsangriffen
- Kollisionsangriff: Finde zwei verschiedene Nachrichten m1 und m2, so dass Hash (m1) = Hash (m2) ist.
Allgemeiner
- Kollisionsangriff bei ausgewähltem Präfix: Geben Sie zwei verschiedene Präfixe p1 und p2 an und suchen Sie zwei Anhänge m1 und m2, so dass hash (p1 ∥ m1) = hash (p2 ∥ m2), wobei ∥ die Verkettungsoperation bezeichnet.
Inhaltsverzeichnis
Klassischer Kollisionsangriff
Mathematisch ausgedrückt findet ein Kollisionsangriff zwei verschiedene Nachrichten m1 und m2, so dass Hash (m1) = Hash (m2). Bei einem klassischen Kollisionsangriff hat der Angreifer keine Kontrolle über den Inhalt der beiden Nachrichten, aber sie werden willkürlich vom Algorithmus ausgewählt.
Ähnlich wie Chiffrierschlüssel mit symmetrischen Schlüsseln anfällig für Brute-Force-Angriffe sind, ist jede kryptografische Hash-Funktion inhärent anfällig für Kollisionen mit einem Geburtstagsangriff. Aufgrund des Geburtstagsproblems sind diese Angriffe viel schneller als eine rohe Gewalt. Ein Hash von n Bits kann in 2n/2-Zeiten unterbrochen werden (Auswertungen der Hash-Funktion).
Effizientere Angriffe sind möglich, indem die Kryptoanalyse auf bestimmte Hash-Funktionen angewendet wird. Wenn ein Kollisionsangriff entdeckt wird und schneller als ein Geburtstagsangriff ist, wird eine Hash-Funktion oft als „kaputt“ bezeichnet. Die NIST-Hashfunktions-Konkurrenz wurde weitgehend durch veröffentlichte Kollisionsangriffe gegen zwei sehr häufig verwendete Hash-Funktionen, MD5 und SHA-1, ausgelöst. Die Kollisionsangriffe auf MD5 haben sich so stark verbessert, dass sie ab 2007 auf einem normalen Computer nur noch wenige Sekunden dauern. Hash-Kollisionen, die auf diese Weise erzeugt werden, haben normalerweise eine konstante Länge und sind weitgehend unstrukturiert, so dass sie nicht direkt zum Angriff auf weit verbreitete Dokumentformate oder Protokolle verwendet werden können.
Problemumgehungen sind jedoch möglich, indem dynamische Konstrukte in vielen Formaten missbraucht werden. Auf diese Weise würden zwei Dokumente erzeugt, die so ähnlich wie möglich sind, um den gleichen Hash-Wert zu haben. Ein Dokument wird einer zu unterzeichnenden Autorität angezeigt, und dann kann die Signatur in die andere Datei kopiert werden. Ein solches bösartiges Dokument würde zwei verschiedene Nachrichten im selben Dokument enthalten, aber das eine oder das andere durch geringfügige Änderungen an der Datei anzeigen:
- Einige Dokumentformate wie PostScript oder Makros in Microsoft Word haben bedingte Konstrukte. (Wenn-dann-sonst), die es erlauben zu testen, ob ein Ort in der Datei den einen oder anderen Wert hat, um zu kontrollieren, was angezeigt wird.
- TIFF-Dateien können beschnittene Bilder enthalten, wobei ein anderer Teil eines Bildes angezeigt wird, ohne den Hash-Wert zu beeinflussen.
Ein echter Kollisionsangriff wurde im Dezember 2008 veröffentlicht, als eine Gruppe von Sicherheitsforschern ein gefälschtes X.509-Signaturzertifikat veröffentlichte, das dazu verwendet werden konnte, eine Zertifikatsautorität zu imitieren und einen Prefix-Kollisionsangriff auf die MD5-Hashfunktion zu nutzen. Dies bedeutet, dass ein Angreifer jede SSL-gesicherte Website als Man-in-the-Middle ausnutzen könnte, wodurch die in jedem Webbrowser eingebaute Zertifikatsprüfung untergraben wird, um den elektronischen Geschäftsverkehr zu schützen. Das Rogue-Zertifikat kann von echten Behörden möglicherweise nicht widerrufen werden und könnte auch eine willkürlich gefälschte Ablaufzeit haben. Obwohl MD5 2004 als sehr schwach bekannt war und mindestens ein Microsoft-Code-Signing-Zertifikat MD5 im Mai 2012 verwendete.
Die Flame-Malware hat erfolgreich eine neue Variante eines Kollisionsangriffs mit ausgewählten Präfixen verwendet, um die Code-Signierung ihrer Komponenten durch ein Microsoft-Stammzertifikat, das immer noch den kompromittierten MD5-Algorithmus verwendet, zu fälschen.
Angriffsszenarien
Viele Anwendungen von kryptographischen Hash-Funktionen beruhen nicht auf Kollisionsresistenz, so dass Kollisionsangriffe ihre Sicherheit nicht beeinträchtigen. Zum Beispiel sind HMACs nicht anfällig. Damit der Angriff nützlich ist, muss der Angreifer die Eingabe für die Hash-Funktion steuern.
Digitale Signaturen
Da digitale Signaturalgorithmen eine große Menge an Daten nicht effizient signieren können, verwenden die meisten Implementierungen eine Hash-Funktion, um die Menge der zu signierenden Daten auf eine konstante Größe zu reduzieren („komprimieren“). Digitale Signaturschemata sind oft anfällig für Hash-Kollisionen, sofern sie keine Techniken wie randomisiertes Hashing verwenden.
Das übliche Angriffsszenario sieht so aus:
- Mallory erzeugt zwei verschiedene Dokumente A und B, die einen identischen Hash-Wert haben, d.h. eine Kollision. Mallory versucht, Bob dazu zu bringen, Dokument B anzunehmen, angeblich von Alice.
- Mallory schickt Dokument A an Alice, die zustimmt, was das Dokument sagt, unterschreibt seinen Hash und sendet die Signatur an Mallory.
- Mallory fügt die Signatur aus Dokument A in Dokument B ein.
- Mallory sendet dann die Signatur und das Dokument B an Bob und behauptet, dass Alice B signiert hat. Da die digitale Signatur dem Hash von Dokument B entspricht, kann Bobs Software die Ersetzung nicht erkennen.
Im Jahr 2008 verwendeten die Forscher einen Kollisionsangriff mit ausgewählten Präfixen gegen MD5, der dieses Szenario verwendet, um ein unberechtigtes Zertifizierungsstellenzertifikat zu erstellen. Sie erstellten zwei Versionen eines öffentlichen TLS-Schlüsselzertifikats, von denen eines legitim erschien und von der RapidSSL-Zertifizierungsstelle zur Signatur gesendet wurde. Die zweite Version, die den gleichen MD5-Hash hatte, enthielt Flags, die den Webbrowsern signalisierten, sie als legitime Autorität für die Ausgabe beliebiger anderer Zertifikate zu akzeptieren.