Hash-Kollisionen und deren Ausnutzung

Von Ange Albertini und Marc Stevens.

FAQ (TL;DR)

F: Ist es möglich, eine Datei einen beliebigen MD2/MD4/MD5/MD6/SHA1/SHA2/SHA3-Hash oder denselben Hash wie eine andere Datei erhalten zu lassen?
A: Nein.

F: Kann man 2 verschiedene Dateien mit demselben Hash erstellen?
A: Mit MD5 in wenigen Sekunden auf einem Standardcomputer. Mit SHA1 ist es möglich, aber für Endbenutzer nicht praktikabel (Komplexität: 2^61.2 Preis: 11.000 $).

F: Kann man 2 verschiedene Dateien durch Anhängen von Daten denselben Hash erhalten lassen?
A: Mit MD5 in wenigen Stunden auf einem Standardcomputer. Mit SHA1 ist es möglich, aber für Endbenutzer nicht praktikabel (Komplexität: 2^63.4 Preis: 45.000 $)

F: Bleiben die 2 Dateien gültig?
A: Im Allgemeinen ja, da die meisten Dateiformate angehängte Daten tolerieren. Andererseits werden die Dateisignaturen wahrscheinlich ungültig sein.

F: Kann man 2 verschiedene Dateien mit beliebigem Inhalt und demselben Hash erstellen?
A: Ja, das kann sofort geschehen, indem man sich auf spezielle Dateistrukturen stützt:

1. einen speziellen Format-Header (oder ein Header-Paar) mit Tricks, der als Umschalter zwischen 2 Inhalten fungiert (manche Formate erlauben solche Tricks nicht).
   
2. vorberechnete Kollisionen, die auf den jeweiligen Header(s) basieren.
   
3. zwei Inhalte bestimmter Formate, die beide nach der Kollision vorhanden sind (nach der Berechnung hinzugefügt).

F: Für welche Formate kann ich sofort ein Paar MD5-kollidierender Dateien erhalten?
A: JPG, PNG, GIF, GZIP, Portable Executable, MP4, JPEG2000, PDF, DOCX/PPTX/XSLX, EPUB, 3MF, XPS. Führen Sie einfach das jeweilige Skript aus.

F: Wie sieht es mit SHA1 aus?
A: Für SHA1 wurde JPG in einer PDF berechnet und implementiert.

F: Wie sieht es mit Formaten aus, die bereits für MD5 unterstützt werden (JPG, PNG...), aber stattdessen für SHA1?
A: Sie werden höchstwahrscheinlich auch mit SHA1 unterstützt, aber ihre Kollisionen wurden noch nicht berechnet.

F: Sind Berechnungen für ähnliche (aber unterschiedliche) Inhalte schneller?
A: Nein. Jede noch so kleine Abweichung erfordert eine vollständige Berechnung.

F: Welche Formate haben diese Abkürzung nicht?
A: ELF, Mach-O, Java Class, TAR, ZIP (unter anderem...)

F: Sind klassische Kollisionen (in wenigen Stunden) bei diesen Formaten weiterhin möglich?
A: Ja, solange beliebig viele angehängte Daten toleriert werden (d. h. wahrscheinlich nicht ZIP oder Class).

F: Stellen Sie Beispiele für Kollisionen bereit?
A: Ja.

Inhaltsverzeichnis

• Einleitung
• Status
• Angriffe
  • Identisches Präfix
    • FastColl (MD5)
    • UniColl (MD5)
    • Shattered (SHA1)
  • Chosen-Prefix-Kollisionen
    • HashClash (MD5)
    • Shambles (SHA1)
  • Zusammenfassung der Angriffe
• Ausnutzung
  • Standardstrategie
    • JPG
      • benutzerdefinierte Scans
    • PNG
      • Inkompatibilität
    • GIF
    • GZIP
    • LZ4 / Zstandard
    • Portable Executable
    • MP4 und andere
      • JPEG2000
    • PDF
      • JPG in PDF
    • ZIP
      • ZIP-basierte Formate
    • Andere
  • Ungewöhnliche Strategien
    • MultiColls: Kette mehrerer Kollisionen
      • Hashquines
    • Gültigkeit
    • PolyColls: Kollisionen verschiedener Dateitypen
      • PE - JPG
      • PDF - PE
      • PDF - PNG
    • PileUps (Mehrfachkollision)
      • PE - PNG - MP4 - PDF
  • Anwendungsfälle
    • Kollidiere sie alle!
    • Belastende Dateien
  • Fehlschläge
    • ELF
    • Mach-O
    • Java Class
    • TAR
  • Zusammenfassung der Ausnutzungen
  • Testdateien
• Erkennung
  • Sichere Hashes
• Referenzen
• Danksagungen
• Fazit

Einleitung

Das Ziel ist es, bestehende Angriffe umfassend zu untersuchen - und dabei zu zeigen, wie schwach MD5 ist (sofortige Kollisionen für beliebige JPG, PNG, PDF, MP4, PE...) - und außerdem gängige Dateiformate im Detail zu untersuchen, um zu bestimmen, wie sie mit gegenwärtigen oder zukünftigen Angriffen ausgenutzt werden können.

Tatsächlich kann derselbe Dateiformat-Trick bei mehreren Hashes angewendet werden (dieselben JPG-Tricks wurden für MD5, malicious SHA-1 und SHA1), solange die Kollisionen denselben Byte-Mustern folgen.

Dieses Dokument behandelt keine neuen Angriffe (der jüngste wurde 2012 dokumentiert), sondern neue Formen der Ausnutzung bestehender Angriffe.

Status

Aktueller Stand bekannter Angriffe:

• Eine Datei dazu bringen, den Hash einer anderen Datei oder einen vorgegebenen Hash zu erhalten: unmöglich

  • Das ist selbst mit MD2 oder MD4 nicht praktikabel.
  • funktioniert für einfachere Hashes(*)

• Zwei verschiedene Dateien mit demselben MD5 erhalten: sofort

  • Beispiele: 1 ⟷ 2

• Zwei beliebige Dateien denselben MD5 erhalten lassen: einige Stunden (72 Stunden.core)

  • Beispiele: 1 ⟷ 2

• Zwei beliebige Dateien bestimmter Dateiformate (PNG, JPG, PE...) denselben MD5 erhalten lassen: sofort

  • siehe unten

• Zwei verschiedene Dateien mit demselben SHA1 erhalten: 6500 Jahre.core

  • Zwei verschiedene PDFs mit demselben SHA-1 erhalten, um ein anderes Bild zu zeigen: sofort (die Präfixe sind bereits berechnet)

(*) Beispiel mit crypt - danke Sven!```

import crypt crypt.crypt("5dUD&66", "br") 'brokenOz4KxMc' crypt.crypt("O!>',%$", "br") 'brokenOz4KxMc'

# Angriffe