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:

einen speziellen Format-Header (oder ein Header-Paar) mit Tricks, der als Umschalter zwischen 2 Inhalten fungiert (manche Formate erlauben solche Tricks nicht).
vorberechnete Kollisionen, die auf den jeweiligen Header(s) basieren.
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.

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

MD5 und SHA1 arbeiten mit Blöcken von 64 Bytes.

Wenn zwei Inhalte A und B denselben Hash haben, dann bleibt der Hash gleich, wenn man beiden denselben Inhalt C anhängt.``` text
hash(A) = hash(B) -> hash(A + C) = hash(B + C)

Kollisionen funktionieren, indem an einer Blockgrenze eine Anzahl berechneter Kollisionsblöcke eingefügt wird, die davon abhängt, was zuvor in der Datei stand. Diese Kollisionsblöcke sehen sehr zufällig aus, mit einigen geringfügigen Unterschieden (die einem spezifischen Muster für jeden Angriff folgen), und sie führen winzige Unterschiede ein, während sie schließlich nach diesen Blöcken denselben Hashwert ergeben.

Diese Unterschiede werden missbraucht, um gültige Dateien mit spezifischen Eigenschaften zu erzeugen.

Dateiformate funktionieren ebenfalls von oben nach unten, und die meisten arbeiten mit Chunks auf Byte-Ebene.

Einige 'Kommentar'-Chunks können eingefügt werden, um Datei-Chunks an Blockgrenzen auszurichten, um spezifische Strukturen an die Unterschiede der Kollisionsblöcke anzugleichen, um die restliche Zufälligkeit der Kollisionsblöcke vor den Datei-Parsern zu verbergen, und um ansonsten gültigen Inhalt vor dem Parser zu verbergen (damit er einen anderen Inhalt sieht).

Diese 'Kommentar'-Chunks sind oft keine offiziell echten Kommentare: Sie werden lediglich als Datencontainer verwendet, die vom Parser ignoriert werden (zum Beispiel sind PNG-Chunks mit einer ID, die mit einem Kleinbuchstaben beginnt, ancillary, nicht kritisch).

Meistens wird ein Unterschied in den Kollisionsblöcken genutzt, um die Länge eines Kommentar-Chunks zu verändern, der typischerweise direkt vor den Daten dieses Chunks deklariert wird: in der Lücke zwischen der kleineren und der längeren Version dieses Chunks wird ein weiterer Kommentar-Chunk deklariert, um über den Inhalt A einer Datei zu springen. Nach diesem Dateiinhalt A wird einfach ein weiterer Dateiinhalt B angehängt.

Da Dateiformate normalerweise einen Terminator definieren, der die Parser danach stoppen lässt, beendet A das Parsen, sodass der angehängte Inhalt B ignoriert wird.

Normalerweise sind also mindestens zwei Kommentare nötig – oft drei:

Ausrichtung
Kollisionsblöcke verbergen
einen Dateiinhalt verbergen (für wiederverwendbare Kollisionen)

Diese gemeinsamen Eigenschaften von Dateiformaten machen dies möglich – sie werden normalerweise nicht als Schwachstellen angesehen, aber sie können erkannt oder normalisiert werden:

Dummy-Chunks – als Kommentare verwendet
mehr als ein Kommentar
riesige Kommentare (Längen: 64b für MP4, 32b für PNG -> triviale Kollisionen. 16b für JPG, 8b für GIF -> keine generische Kollision für GIF, eingeschränkt für JPG)
beliebige Daten in einem Kommentar speichern (ASCII oder UTF8 könnte erzwungen werden)
beliebige Daten nach dem Terminator speichern (normalerweise nur für bösartige Zwecke verwendet) - kann vermieden werden, indem zwei Kommentare verwendet werden, die an denselben Offsets enden.
keine Integritätsprüfung. CRC32 in PNG wird normalerweise ignoriert. Allerdings können sie alle korrekt sein, da die Kollisionsblöcke Chunks unterschiedlicher Länge deklarieren - selbst wenn die Daten des Chunks unterschiedlich beginnen, sind die Chunk-Längen unterschiedlich.
flache Struktur: ASN.1 definiert eine Elternstruktur mit der Länge aller eingeschlossenen Unterstrukturen, was diese Konstrukte verhindert: Man müsste eine Länge missbrauchen, aber auch die Länge des Elternteils.
einen Kommentar vor den Header setzen – dies ermöglicht generische wiederverwendbare Kollisionen.

Identisches Präfix

Definiere ein beliebiges Präfix – dessen Inhalt und Länge spielen keine Rolle.
Das Präfix wird auf den nächsten 64-Byte-Block aufgefüllt.
Kollisionsblock/-blöcke werden abhängig vom Präfix berechnet und angehängt. Beide Seiten sind sehr zufällig. Die Unterschiede sind durch den Angriff vorbestimmt.
Nach diesem[diesen] Block[blöcken] ist der Hashwert trotz der Dateiunterschiede derselbe.
Ein beliebiges identisches Suffix kann hinzugefügt werden.

Präfix	=	Präfix
Kollision A	≠	Kollision B
Suffix	=	Suffix

Beide Dateien sind nahezu identisch (ihre Inhalte unterscheiden sich nur in einigen Bits)

Ausnutzung:

Bündele zwei Inhalte, dann entweder:

Daten-Exploit: Code ausführen, der die Unterschiede prüft und das eine oder das andere anzeigt (normalerweise trivial, da die Unterschiede im Voraus bekannt sind).
Struktur-Exploit: Dateistruktur ausnutzen (typischerweise die Länge eines Kommentars), um einen Inhalt zu verbergen oder den anderen zu zeigen (abhängig vom Dateiformat und seinen Parsern).

Zwei Dateien mit dieser Struktur:

zeigen entweder A oder B.

FastColl (MD5)

Endgültige Version im Jahr 2009.

Zeit: wenige Sekunden Rechenzeit
Platz: zwei Blöcke

Unterschiede: keine Kontrolle davor, keine Kontrolle danach. FastColl-Unterschiedsmaske:

.. .. .. .. .. .. .. .. .. .. .. .. .. .. .. ..
.. .. .. X. .. .. .. .. .. .. .. .. .. .. .. ..
.. .. .. .. .. .. .. .. .. .. .. .. .. X. .X ..
.. .. .. .. .. .. .. .. .. .. .. X. .. .. .. ..

Ausnutzung: schwierig

Die Unterschiede liegen nicht in der Nähe des Anfangs/Endes der Blöcke, daher ist es sehr schwer, sie auszunutzen, da man kein nahegelegenes Byte kontrolliert. Eine mögliche Lösung ist, die umgebenden Bytes per Brute-Force zu durchsuchen – vgl. PoCGTFO 14:10.

Beispiele:

Mit einem leeren Präfix:``` MD5: fe6c446ee3a831ee010f33ac9c1b602c SHA256: c5dd2ef7c74cd2e80a0fd16f1dd6955c626b59def888be734219d48da6b9dbdd

00: 37 75 C1 F1-C4 A7 5A E7-9C E0 DE 7A-5B 10 80 26 7u┴±─ºZτ£α▐z[►Ç& 10: 02 AB D9 39-C9 6C 5F 02-12 C2 7F DA-CD 0D A3 B0 ☻½┘9╔l_☻↕┬⌂┌═♪ú░ 20: 8C ED FA F3-E1 A3 FD B4-EF 09 E7 FB-B1 C3 99 1D îφ·≤ßú²┤∩○τ√▒├Ö↔ 30: CD 91 C8 45-E6 6E FD 3D-C7 BB 61 52-3E F4 E0 38 ═æ╚Eµn²=╟╗aR>⌠α8
40: 49 11 85 69-EB CC 17 9C-93 4F 40 EB-33 02 AD 20 I◄àiδ╠↨£ôO@δ3☻¡ 50: A4 09 2D FB-15 FA 20 1D-D1 DB 17 CD-DD 29 59 1E ñ○-√§· ↔╤█↨═▌)Y▲ ................ 60: 39 89 9E F6-79 46 9F E6-8B 85 C5 EF-DE 42 4F 46 9ë₧÷yFƒµïà┼∩▐BOF ...X............ 70: C2 78 75 9D-8B 65 F4 50-EA 21 C5 59-18 62 FF 7B ┬xu¥ïe⌠PΩ!┼Y↑b { .............XX. ...........X.... ................ 00: 37 75 C1 F1-C4 A7 5A E7-9C E0 DE 7A-5B 10 80 26 7u┴±─ºZτ£α▐z[►Ç& ...X............ 10: 02 AB D9 B9-C9 6C 5F 02-12 C2 7F DA-CD 0D A3 B0 ☻½┘╣╔l_☻↕┬⌂┌═♪ú░ .............XX. 20: 8C ED FA F3-E1 A3 FD B4-EF 09 E7 FB-B1 43 9A 1D îφ·≤ßú²┤∩○τ√▒CÜ↔ ...........X.... 30: CD 91 C8 45-E6 6E FD 3D-C7 BB 61 D2-3E F4 E0 38 ═æ╚Eµn²=╟╗a╥>⌠α8 40: 49 11 85 69-EB CC 17 9C-93 4F 40 EB-33 02 AD 20 I◄àiδ╠↨£ôO@δ3☻¡ / 50: A4 09 2D 7B-15 FA 20 1D-D1 DB 17 CD-DD 29 59 1E ñ○-{§· ↔╤█↨═▌)Y▲ 60: 39 89 9E F6-79 46 9F E6-8B 85 C5 EF-DE C2 4E 46 9ë₧÷yFƒµïà┼∩▐┬NF 70: C2 78 75 9D-8B 65 F4 50-EA 21 C5 D9-18 62 FF 7B ┬xu¥ïe⌠PΩ!┼┘↑b {

MD5: fe6c446ee3a831ee010f33ac9c1b602c SHA256: e27cf3073c704d0665da42d597d4d20131013204eecb6372a5bd60aeddd5d670

Other examples, with an identical prefix: [1](https://github.com/corkami/collisions/blob/HEAD/examples/fastcoll1.bin) ⟷ [2](https://github.com/corkami/collisions/blob/HEAD/examples/fastcoll2.bin)

**Variant**: es gibt eine [Single-Block-MD5-Kollision](https://marc-stevens.nl/research/md5-1block-collision/), die jedoch fünf Wochen Rechenzeit benötigt.

Hier ist eine [Aufzeichnung](https://github.com/corkami/collisions/blob/HEAD/examples/fastcoll.svg) einer FastColl-Berechnung ohne Präfix
und [eine weitere](https://github.com/corkami/collisions/blob/HEAD/examples/fastcoll-prefix.svg) mit Präfix.


### [UniColl](https://github.com/corkami/collisions/blob/HEAD/unicoll.md) (MD5)

Dokumentiert in [2012](https://www.cwi.nl/system/files/PhD-Thesis-Marc-Stevens-Attacks-on-Hash-Functions-and-Applications.pdf#page=199), implementiert in [2017](https://github.com/cr-marcstevens/hashclash/blob/95c2619a8078990056beb7aaa59104021714ee3c/scripts/poc_no.sh)

[UniColl](https://github.com/cr-marcstevens/hashclash#create-you-own-identical-prefix-collision) ermöglicht es Ihnen, ein paar Bytes in den Kollisionsblöcken zu kontrollieren, vor und nach der ersten Differenz, was es zu einer Identical-Prefix-Kollision mit einigen kontrollierbaren Differenzen macht, fast wie eine Chosen-Prefix-Kollision.
Das ist sehr praktisch, und noch besser: Die Differenz kann sehr vorhersehbar sein:
im Fall von `m2+= 2^8` (auch bekannt als `N=1` / `m2 9` im HashClash [poc_no.sh](https://github.com/cr-marcstevens/hashclash/blob/master/scripts/poc_no.sh#L30) Skript)
ist die Differenz +1 beim 9. Byte, was sie sehr ausnutzbar macht,
da man sich die Kollision sogar im Kopf vorstellen kann:
das 9. Zeichen dieses Satzes wird durch das nächste ersetzt: `0` ersetzt durch `1`, `a` ersetzt durch `b`..

- Zeit: ein paar Minuten (abhängig von der Anzahl der Bytes, die Sie kontrollieren möchten)
- Platzbedarf: zwei Blöcke
- Unterschiede:   ```
   .. .. .. .. DD .. .. .. ..
   .. .. .. .. +1 .. .. .. ..

Exploitation: sehr einfach - kontrollierte Bytes vor und nach der Differenz, und die Differenz ist vorhersagbar. Die einzigen Einschränkungen sind die Ausrichtung und dass du 'nur' 10 Bytes nach der Differenz kontrollierst.

Beispiele mit N=1 und 20 Bytes festgelegtem Text in den Kollisionsblöcken:``` 00: 55 6E 69 43-6F 6C 6C 20-31 20 70 72-65 66 69 78 UniColl 1 prefix 10: 20 32 30 62-F5 48 34 B9-3B 1C 01 9F-C8 6B E6 44 20b⌡H4╣;∟☺ƒ╚kµD 20: FE F6 31 3A-63 DB 99 3E-77 4D C7 5A-6E B0 A6 88 ■÷1:c█Ö>wM╟Zn░ªê 30: 04 05 FB 39-33 21 64 BF-0D A4 FE E2-A6 9D 83 36 ♦♣√93!d┐♪ñ■Γª¥â6
40: 4B 14 D7 F2-47 53 84 BA-12 2D 4F BB-83 78 6C 70 K¶╫≥GSä║↕-O╗âxlp 50: C6 EB 21 F2-F6 59 9A 85-14 73 04 DD-57 5F 40 3C ╞δ!≥÷YÜà¶s♦▌W_@< .........X...... 60: E1 3F B0 DB-E8 B4 AA B0-D5 56 22 AF-B9 04 26 FC ß?░█Φ┤¬░╒V"»╣♦&ⁿ ................ 70: 9F D2 0C 00-86 C8 ED DE-85 7F 03 7B-05 28 D7 0F ƒ╥♀ å╚φ▐à⌂♥{♣(╫☼ ................ ................ .........X...... 00: 55 6E 69 43-6F 6C 6C 20-31 21 70 72-65 66 69 78 UniColl 1!prefix ................ 10: 20 32 30 62-F5 48 34 B9-3B 1C 01 9F-C8 6B E6 44 20b⌡H4╣;∟☺ƒ╚kµD ................ 20: FE F6 31 3A-63 DB 99 3E-77 4D C7 5A-6E B0 A6 88 ■÷1:c█Ö>wM╟Zn░ªê ................ 30: 04 05 FB 39-33 21 64 BF-0D A4 FE E2-A6 9D 83 36 ♦♣√93!d┐♪ñ■Γª¥â6 40: 4B 14 D7 F2-47 53 84 BA-12 2C 4F BB-83 78 6C 70 K¶╫≥GSä║↕,O╗âxlp / 50: C6 EB 21 F2-F6 59 9A 85-14 73 04 DD-57 5F 40 3C ╞δ!≥÷YÜà¶s♦▌W_@< 60: E1 3F B0 DB-E8 B4 AA B0-D5 56 22 AF-B9 04 26 FC ß?░█Φ┤¬░╒V"»╣♦&ⁿ 70: 9F D2 0C 00-86 C8 ED DE-85 7F 03 7B-05 28 D7 0F ƒ╥♀ å╚φ▐à⌂♥{♣(╫☼

UniColl hat weniger Kontrolle als eine echte chosen-prefix-Kollision, ist aber viel schneller, insbesondere da es nur zwei Blöcke benötigt.

Hier ist eine [Aufnahme](https://github.com/corkami/collisions/blob/HEAD/examples/unicoll.svg) einer UniColl-Berechnung.


### [Shattered](http://shattered.io) (SHA1)

Dokumentiert in [2013](https://marc-stevens.nl/research/papers/EC13-S.pdf), berechnet in [2017](http://shattered.io).

- Zeit: 6500 Jahre.CPU und 110 Jahre.GPU
- Platz: zwei Blöcke
- Unterschiede:  ```
  .. .. .. DD ?? ?? ?? ??
  or
  ?? ?? ?? DD .. .. .. ..

Ausnutzung: mittel. Die Unterschiede liegen genau am Anfang und am Ende der Kollisionsblöcke. Es gibt also keine Kontrolle vor und nach einer Länge im Präfix/im Suffix: PNG speichert seine Länge vor dem Chunk-Typ, daher funktioniert es nicht. Es funktioniert jedoch mit JP2-Dateien, wenn sie das JFIF-Format verwenden (dasselbe wie JPG), und wahrscheinlich mit MP4 und anderen Atom/Box-Formaten, wenn du lange Längen auf 64 Bits verwendest (in diesem Fall werden sie nach dem Atom-Typ platziert).

Der Unterschied zwischen den Kollisionsblöcken jeder Seite ist diese Xor-Maske:``` 0C 00 00 02 C0 00 00 10 B4 00 00 1C 3C 00 00 04 BC 00 00 1A 20 00 00 10 24 00 00 1C EC 00 00 14 0C 00 00 02 C0 00 00 10 B4 00 00 1C 2C 00 00 04 BC 00 00 18 B0 00 00 10 00 00 00 0C B8 00 00 10



Beispiele: [PoC||GTFO 0x18](https://github.com/angea/pocorgtfo#0x18) verwendet die berechneten SHA1-Präfixe,
nutzt das Bild direkt aus dem PDFLaTeX-Quelltext wieder (siehe [Artikel 18:10](https://archive.org/stream/pocorgtfo18#page/n62/mode/1up)),
und prüft den Wert der Präfixe auch über JavaScript in der HTML-Seite (die Datei ist ein Polyglot, ZIP HTML und PDF).

## Chosen-Prefix-Kollisionen

Sie ermöglichen es, beliebige Inhalte kollidieren zu lassen.

| 𝓐            | ≠ | 𝔅             |
| :----:        |:-:| :----:        |
| Kollision *A* | ≠ | Kollision *B* |

1. Nimm zwei beliebige Präfixe
2. Fülle das kürzeste auf, bis es so lang ist wie das längste. Beide werden bis zum nächsten Block aufgefüllt - minus 12 Bytes
  - Diese 12 Bytes zufälliger Daten werden auf beiden Seiten hinzugefügt, um die Geburtstagssuche zu randomisieren.
3. X Near-Collision-Blöcke werden berechnet und angehängt.

   Je weniger Blöcke, desto länger die Berechnung.

   Bsp.: [400 kHours für einen Block](https://www.win.tue.nl/hashclash/SingleBlock/). 72 Stunden.Kerne für neun Blöcke mit [HashClash](https://github.com/cr-marcstevens/hashclash).



Chosen-Prefix-Kollisionen sind allmächtig, aber sie können selbst für ein Dateipaar lange dauern.

### [HashClash](https://github.com/cr-marcstevens/hashclash) (MD5)

Endgültige Version im Jahr [2009](https://www.win.tue.nl/hashclash/ChosenPrefixCollisions/).

Beispiele: Kollidieren wir `yes` und `no`. Es dauerte drei Stunden auf 24 Kernen.```
'yes' prefix:
000:  79 65 73 0A-3D 62 84 11-01 75 D3 4D-EB 80 93 DE  yes◙=bä◄☺u╙MδÇô▐   - Prefix, padding
010:  31 C1 D9 30-45 FB BE 1E-71 F0 0A 63-75 A8 30 AA  1┴┘0E√╛▲q≡◙cu¿0¬
020:  98 17 CA E3-A2 6B 8E 3D-44 A9 8F F2-0E 67 96 48  ÿ↨╩πókÄ=D⌐Å≥♫gûH
030:  97 25 A6 FB-00 00 00 00-49 08 09 33-F0 62 C4 E8  ù%ª√    I◘○3≡b─Φ

040:  D5 F1 54 CD-CA A1 42 90-7F 9D 3D 9A-67 C4 1B 0F  ╒±T═╩íBÉ⌂¥=Üg─←☼  - Collision blocks start
050:  04 9F 19 E8-92 C3 AA 19-43 31 1A DB-DA 96 01 54  ♦ƒ↓ΦÆ├¬↓C1→█┌û☺T
060:  85 B5 9A 88-D8 A5 0E FB-CD 66 9A DA-4F 20 8A AA  à╡Üê╪Ñ♫√═fÜ┌O è¬
070:  BA E3 9C F0-78 31 8F D1-14 5F 3E B9-0F 9F 3E 19  ║π£≡x1Å╤¶_>╣☼ƒ>↓

080:  09 9C BB A9-45 89 BA A8-03 E6 C0 31-A0 54 D6 26  ○£╗⌐Eë║¿♥µ└1áT╓&
090:  3F 80 4C 06-0F C7 D9 19-09 D3 DA 14-FD CB 39 84  ?ÇL♠☼╟┘↓○╙┌¶²╦9ä
0A0:  1F 0D 77 5F-55 AA 7A 07-4C 24 8B 13-0A 54 A2 BC  ▼♪w_U¬z•L$ï‼◙Tó╝
0B0:  C5 12 7D 4F-E0 5E F2 23-C5 07 61 E4-80 91 B2 13  ┼↕}Oα^≥#┼•aΣÇæ▓‼

0C0:  E7 79 07 2A-CF 1B 66 39-8C F0 8E 7E-75 25 22 1D  τy•*╧←f9î≡Ä~u%"↔
0D0:  A7 3B 49 4A-32 A4 3A 07-61 26 64 EA-6B 83 A2 8D  º;IJ2ñ:•a&dΩkâóì
0E0:  BE A3 FF BE-4E 71 AE 18-E2 D0 86 4F-20 00 30 26  ╛ú ╛Nq«↑Γ╨åO  0&
0F0:  0A 71 DE 1F-40 B4 F4 8F-9C 50 5C 78-DD CD 72 89  ◙q▐▼@┤⌠Å£P\x▌═rë

100:  BA D1 BF F9-96 80 E3 06-96 F3 B9 7C-77 2D EB 25  ║╤┐∙ûÇπ♠û≤╣|w-δ%
110:  1E 56 70 D7-14 1F 55 4D-EC 11 58 59-92 45 E1 33  ▲Vp╫¶▼UM∞◄XYÆEß3
120:  3E 0E A1 6E-FF D9 90 AD-F6 A0 AD 0E-C6 D6 88 12  >♫ín ┘É¡÷á¡♫╞╓ê↕
130:  B8 74 F2 9E-DD 53 F7 88-19 73 85 39-AA 9B E0 8D  ╕t≥₧▌S≈ê↓sà9¬¢αì
                                                                          \
140:  82 BF 9C 5E-58 42 1E 3B-94 CF 5B 54-73 5F A8 4A  é┐£^XB▲;ö╧[Ts_¿J
150:  FD 5B 64 CF-59 D1 96 74-14 B3 0C AF-11 1C F9 47  ²[d╧Y╤ût¶│♀»◄∟∙G      ................
160:  C5 7A 2C F7-D5 24 F5 EB-BE 54 3E 12-B0 24 67 3F  ┼z,≈╒$⌡δ╛T>↕░$g?      ................
170:  01 DD 95 76-8D 0D 58 FB-50 23 70 3A-BD ED BE AC  ☺▌òvì♪X√P#p:╜φ╛¼      ...............X
                                                                             ................
180:  B8 32 DB AE-E8 DC 3A 83-7A C8 D5 0F-08 90 1D 99  ╕2█«Φ▄:âz╚╒☼◘É↔Ö
190:  2D 7D 17 34-4E A8 21 98-61 1A 65 DA-FC 9B A4 BA  -}↨4N¿!ÿa→e┌ⁿ¢ñ║      ................
1A0:  E1 42 2B 86-0C 94 2A F6-D6 A4 81 B5-2B 0B E9 37  ßB+å♀ö*÷╓ñü╡+♂Θ7      ................
1B0:  44 D2 E4 23-14 7C 16 B8-84 90 8B E0-A1 A7 BD 27  D╥Σ#¶|▬╕äÉïαíº╜'      ..............X.
                                                                             ................
1C0:  C7 7E E6 17-1A 93 C5 EE-59 70 91 26-4E 9D C7 7C  ╟~µ↨→ô┼εYpæ&N¥╟|
1D0:  1D 3D AB F1-B4 F4 F1 D9-86 48 75 77-6E FE 98 84  ↔=½±┤⌠±┘åHuwn■ÿä      ................
1E0:  EF 3C 1C C7-16 5A 1F 83-60 EC 5C FE-CA 17 0C 74  ∩<∟╟▬Z▼â`∞\■╩↨♀t      ................
1F0:  EB 8E 9D F6-90 A3 CD 08-65 D5 5A 4C-2E C6 BE 54  δÄ¥÷Éú═◘e╒ZL.╞╛T      ...............X
                                                                             ................

'no' prefix:                                                                 ................
000:  6E 6F 0A E5-5F D0 83 01-9B 4D 55 06-61 AB 88 11  no◙σ_╨â☺¢MU♠a½ê◄      ................
010:  8A FA 4D 34-B3 75 59 46-56 97 EF 6C-4A 07 90 CC  è·M4│uYFVù∩lJ•É╠      ............X...
020:  FE 19 D7 CF-6F 92 03 9C-91 AA A5 DA-56 92 C1 04  ■↓╫╧oÆ♥£æ¬Ñ┌VÆ┴♦      ................
030:  E6 4C 08 A3-00 00 00 00-8D B6 4E 47-FF AF 7A 3C  µL◘ú    ì╢NG »z<
                                                                             ................
040:  D5 F1 54 CD-CA A1 42 90-7F 9D 3D 9A-67 C4 1B 0F  ╒±T═╩íBÉ⌂¥=Üg─←☼      ................
050:  04 9F 19 E8-92 C3 AA 19-43 31 1A DB-DA 96 01 54  ♦ƒ↓ΦÆ├¬↓C1→█┌û☺T      ............X...
060:  85 B5 9A 88-D8 A5 0E FB-CD 66 9A DA-4F 20 8A A9  à╡Üê╪Ñ♫√═fÜ┌O è⌐      ................
070:  BA E3 9C F0-78 31 8F D1-14 5F 3E B9-0F 9F 3E 19  ║π£≡x1Å╤¶_>╣☼ƒ>↓
                                                                             ................
080:  09 9C BB A9-45 89 BA A8-03 E6 C0 31-A0 54 D6 26  ○£╗⌐Eë║¿♥µ└1áT╓&      ................
090:  3F 80 4C 06-0F C7 D9 19-09 D3 DA 14-FD CB 39 84  ?ÇL♠☼╟┘↓○╙┌¶²╦9ä      .............X..
0A0:  1F 0D 77 5F-55 AA 7A 07-4C 24 8B 13-0A 54 B2 BC  ▼♪w_U¬z•L$ï‼◙T▓╝      ................
0B0:  C5 12 7D 4F-E0 5E F2 23-C5 07 61 E4-80 91 B2 13  ┼↕}Oα^≥#┼•aΣÇæ▓‼
                                                                             ................
0C0:  E7 79 07 2A-CF 1B 66 39-8C F0 8E 7E-75 25 22 1D  τy•*╧←f9î≡Ä~u%"↔      ................
0D0:  A7 3B 49 4A-32 A4 3A 07-61 26 64 EA-6B 83 A2 8D  º;IJ2ñ:•a&dΩkâóì      ...............X
0E0:  BE A3 FF BE-4E 71 AE 18-E2 D0 86 4F-20 00 30 22  ╛ú ╛Nq«↑Γ╨åO  0"      ................
0F0:  0A 71 DE 1F-40 B4 F4 8F-9C 50 5C 78-DD CD 72 89  ◙q▐▼@┤⌠Å£P\x▌═rë
                                                                           /
100:  BA D1 BF F9-96 80 E3 06-96 F3 B9 7C-77 2D EB 25  ║╤┐∙ûÇπ♠û≤╣|w-δ%
110:  1E 56 70 D7-14 1F 55 4D-EC 11 58 59-92 45 E1 33  ▲Vp╫¶▼UM∞◄XYÆEß3
120:  3E 0E A1 6E-FF D9 90 AD-F6 A0 AD 0E-CA D6 88 12  >♫ín ┘É¡÷á¡♫╩╓ê↕
130:  B8 74 F2 9E-DD 53 F7 88-19 73 85 39-AA 9B E0 8D  ╕t≥₧▌S≈ê↓sà9¬¢αì

140:  82 BF 9C 5E-58 42 1E 3B-94 CF 5B 54-73 5F A8 4A  é┐£^XB▲;ö╧[Ts_¿J
150:  FD 5B 64 CF-59 D1 96 74-14 B3 0C AF-11 1C F9 47  ²[d╧Y╤ût¶│♀»◄∟∙G
160:  C5 7A 2C F7-D5 24 F5 EB-BE 54 3E 12-70 24 67 3F  ┼z,≈╒$⌡δ╛T>↕p$g?
170:  01 DD 95 76-8D 0D 58 FB-50 23 70 3A-BD ED BE AC  ☺▌òvì♪X√P#p:╜φ╛¼

180:  B8 32 DB AE-E8 DC 3A 83-7A C8 D5 0F-08 90 1D 99  ╕2█«Φ▄:âz╚╒☼◘É↔Ö
190:  2D 7D 17 34-4E A8 21 98-61 1A 65 DA-FC 9B A4 BA  -}↨4N¿!ÿa→e┌ⁿ¢ñ║
1A0:  E1 42 2B 86-0C 94 2A F6-D6 A4 81 B5-2B 2B E9 37  ßB+å♀ö*÷╓ñü╡++Θ7
1B0:  44 D2 E4 23-14 7C 16 B8-84 90 8B E0-A1 A7 BD 27  D╥Σ#¶|▬╕äÉïαíº╜'

1C0:  C7 7E E6 17-1A 93 C5 EE-59 70 91 26-4E 9D C7 7C  ╟~µ↨→ô┼εYpæ&N¥╟|
1D0:  1D 3D AB F1-B4 F4 F1 D9-86 48 75 77-6E FE 98 84  ↔=½±┤⌠±┘åHuwn■ÿä
1E0:  EF 3C 1C C7-16 5A 1F 83-60 EC 5C FE-CA 17 0C 54  ∩<∟╟▬Z▼â`∞\■╩↨♀T
1F0:  EB 8E 9D F6-90 A3 CD 08-65 D5 5A 4C-2E C6 BE 54  δÄ¥÷Éú═◘e╒ZL.╞╛T

Hier ist ein Log des gesamten Vorgangs.

Shambles (SHA-1)

Shambles ist eine sehr teure Chosen-Prefix-Kollision, die 9 Blöcke verwendet.

Jeder Block verwendet dasselbe XOR-Muster wie Shattered:``` 0C 00 00 02 C0 00 00 10 B4 00 00 1C 3C 00 00 04 BC 00 00 1A 20 00 00 10 24 00 00 1C EC 00 00 14 0C 00 00 02 C0 00 00 10 B4 00 00 1C 2C 00 00 04 BC 00 00 18 B0 00 00 10 00 00 00 0C B8 00 00 10

Aber auch wenn Shattered viel einfacher auszunutzen ist als FastColl,
sind die Einschränkungen der Unterschiede in den Kollisionsblöcken irrelevant,
da Shambles eine Chosen-Prefix-Kollision ist.


## Angriffsübersicht

Hash | Name      | Datum | Dauer     | Präfix-Typ | Kontrolle nahe Diff
---- | --------- | ---- | -------- | ----------- | -----------------
MD5  | FastColl  | 2009 | 2s       | Identisch   | keine
     | UniColl   | 2012 | 7-40min  | Identisch   | 4-10 Bytes
     | HashClash | 2009 | 72h      | Chosen      | n/a
     |           |      |          |             |
SHA1 | Shattered | 2013 | 6500 Jahre | Identisch | Präfix & Suffix
     | Shambles  | 2020 | ?        | Chosen      | n/a


# Ausnutzung

Identische Präfix-Kollisionen werden normalerweise als (sehr) begrenzt angesehen, aber Chosen-Prefix ist zeitaufwendig.

Ein anderer Ansatz besteht darin, wiederverwendbare Präfixe zu erstellen – entweder mit einem Identical-Prefix-Angriff wie UniColl – oder mit Chosen-Prefix, um einige Einschränkungen zu überwinden –, aber dieses Präfixpaar in Kombination mit zwei Payloads wie bei einem klassischen Identical-Prefix-Angriff wiederzuverwenden.

Sobald das Präfixpaar berechnet wurde, ist es möglich, zwei Inhalte sofort kollidieren zu lassen:
Es ist nur eine Frage der Anpassung der Dateidaten (gemäß den jeweiligen Dateiformaten), sodass sie den Dateiformatspezifikationen und den zuvor berechneten Präfixanforderungen entsprechen.


## Standardstrategie

Klassische Kollisionen zweier gültiger Dateien desselben Dateityps.


### JPG



Theoretische Einschränkungen und Workarounds:
- das *Application*-Segment sollte sich in der Theorie direkt nach dem *Start of Image*-Marker befinden.
  In der Praxis ist das nicht notwendig, daher kann unsere Kollision generisch sein: Die einzige Einschränkung ist die Größe des kleinsten Bildes.
- die Länge eines Kommentars wird in zwei Bytes gespeichert, daher ist die speicherbare Menge auf 65536 Bytes begrenzt (etwa die Größe eines 400x400-Fotos)
- Anstatt über eine vollständige JPG-Datei zu springen, kann man die Datei in ihre Segmente aufteilen und Sprung-Trampoline zwischen den Segmenten einfügen

  

  *Kommentare über den jeweiligen Bildsegmenten*

  

  *Wie Kommentar-Trampoline funktionieren*

- Während der größte Teil einer JPG-Struktur aus Segmenten besteht, die alle auf 65536 Bytes begrenzt sind,
werden die eigentlichen komprimierten Daten im *Entropy Coded Segment* gespeichert, das diese Begrenzungen nicht einhält:
Seine Größe ist im Voraus unbekannt und wächst über diese Grenze hinaus.
Sie wächst mit der Größe des Bildes und macht in einem Baseline-Bild (nicht progressiv) den Großteil der Dateigröße aus.
Um das gesamte Bild in 64kb-Blöcke zu bekommen, besteht der einfache Weg darin, das Bild zunächst als progressiv zu speichern (was jede Software kann und den ECS normalerweise in bis zu sechs Scans aufteilt). Der fortgeschrittenere Weg ist die Verwendung von *JPEGTran* mit dem 'Wizard'-Kommandozeilenparameter `--scans` und die Definition eigener Scans.

Es gibt keine weiteren Einschränkungen außer den Scan-Segmenten,
daher ist eine MD5-Kollision zweier beliebiger JPGs *sofort* möglich und benötigt keine Chosen-Prefix-Kollision, sondern nur UniColl.

Mit dem [Skript](https://github.com/corkami/collisions/blob/HEAD/scripts/jpg.py):```
21:07:35.65>jpg.py Ange.jpg Marc.jpg

21:07:35.75>

Examples:

⟷

benutzerdefinierte Scans

2 MD5-kollidierende JPGs

Hier ist ein Beispiel einer JPEGTran-Scan-Definition, um ein 1944x2508-RGB-Bild in ein 100% JPG mit 20 Scans zu verwandeln, die alle in 64kb passen.``` // : -, , ;

// 0=luma 0: 0-0, 0, 0; 0: 1-1, 0, 0; 0: 2-6, 0, 0; 0: 7-10, 0, 0; 0: 11-13, 0, 0; 0: 14-20, 0, 0; 0: 21-26, 0, 0; 0: 27-32, 0, 0; 0: 33-40, 0, 0; 0: 41-48, 0, 0; 0: 49-54, 0, 0; 0: 55-63, 0, 0;

// 1=blueness 1: 0-0, 0, 0; 1: 1-16, 0, 0; 1: 17-32, 0, 0; 1: 33-63, 0, 0;

// 2=redness 2: 0-0, 0, 0; 2: 1-16, 0, 0; 2: 17-32, 0, 0; 2: 33-63, 0, 0;

Ergebnis:



*ein 1944x2508 RGB-Bild als 100 % JPG mit 20 Scans*


### PNG



Theoretische Einschränkungen und Workarounds:
- PNG verwendet CRC32 am Ende seiner Chunks, aber in der Praxis werden sie ignoriert. Sie können korrekt sein, aber es ist nicht erforderlich.
- die Bild-Metadaten (Abmessungen, Farbraum ...) sind im `IHDR`-Chunk gespeichert,
  der in der Theorie direkt nach der Signatur stehen sollte (d. h. vor einem möglichen Kommentar),
  was bedeuten würde, dass wir nur Kollisionen von Bildern mit denselben Metadaten vorberechnen können.
  Allerdings kann dieser Chunk tatsächlich nach einem Kommentarblock stehen (bei der überwiegenden Mehrheit der Leser, außer den Apple-Readern), sodass wir die Kollisionsdaten vor dem Header platzieren können,
  was es ermöglicht, jedes PNG-Paar mit einer einzigen Vorberechnung kollidieren zu lassen.

Da ein PNG-Chunk eine Länge von vier Bytes hat, muss die Struktur keiner der Dateien geändert werden: Wir können in einem Zug über ein ganzes Bild springen.

Wir können so viele verworfene Chunks einfügen, wie wir möchten, also können wir einen für die Ausrichtung hinzufügen, dann einen, dessen Länge durch eine UniColl verändert wird. Die Länge wird dann `00` `75` und `01` `75` sein.

Eine MD5-Kollision zweier beliebiger PNG-Bilder ist also *sofort*, ohne Voraussetzungen (keine Berechnung, nur einige geringfügige Dateiänderungen), und benötigt keine Chosen-Prefix-Kollision, sondern nur UniColl.

Mit dem [Skript](https://github.com/corkami/collisions/blob/HEAD/scripts/png.py):```
19:27:04.79>png.py nintendo.png sega.png

19:27:04.87>

Examples:

⟷

2 MD5-kollidierende PNGs mit unterschiedlichen Eigenschaften

Hier ist eine Aufzeichnung des gesamten Vorgangs.

eine Aufzeichnung einer universellen (missbräuchlichen) PNG-Kollision

Inkompatibilität

Die meisten Leser akzeptieren fehlerfrei PNG-Dateien, die mit einem Chunk beginnen, der nicht IHDR ist.

Einige (wie Safari und Preview – noch andere?) tolerieren das jedoch nicht. In diesem Fall müssen der Bild-Header und seine Eigenschaften (Abmessungen, Farbraum) zuerst kommen, vor allen Kollisionsblöcken.

In diesem Fall müssen beide kollidierenden Dateien dieselben Eigenschaften haben. Auch hier reicht UniColl aus, und natürlich kann das berechnete Präfixpaar für jedes andere Dateipaar mit denselben Eigenschaften wiederverwendet werden.

Hier ist ein Skript, um ein beliebiges Paar solcher Dateien kollidieren zu lassen; es startet UniColl, falls das Präfixpaar berechnet werden muss.

Beispiele:

⟷

2 Paare MD5-kollidierender PNGs mit identischen Eigenschaften für maximale Kompatibilität

Hier ist eine Aufzeichnung des gesamten Vorgangs, wenn UniColl aufgerufen wird,

eine Aufzeichnung einer PNG-UniColl-Kollision

und eine weitere, wenn das Präfix bereits berechnet wurde.

eine Aufzeichnung einer vorberechneten PNG-Kollision

GIF

GIF ist knifflig:

Es speichert seine Metadaten im Header, bevor ein Kommentar möglich ist, daher kann es kein generisches Präfix für alle GIF-Dateien geben.
Wenn die Datei eine globale Palette hat, wird sie ebenfalls gespeichert, bevor ein Kommentar möglich ist.
Seine Kommentar-Chunks sind in der Länge auf ein einzelnes Byte begrenzt, also maximal 256 Bytes!

Die Kommentar-Chunks folgen jedoch einer eigenartigen Struktur: Es ist eine Kette aus <length:1> <data:length>, bis eine Nulllänge definiert ist. Dadurch wird jedes Nicht-Null-Byte zu einem gültigen ‚Sprung nach vorn'. Das macht es geeignet für die Verwendung mit FastColl, wie in PoC||GTFO 14:11 gezeigt.

Zumindest können wir, auch wenn wir kein generisches Präfix haben, jedes Paar von GIFs mit denselben Metadaten (Abmessungen, Palette) kollidieren lassen, und wir brauchen nur eine Sekunde FastColl, um das Präfix zu berechnen.

Das Problem ist nun, dass wir nicht über ein ganzes Bild wie bei PNG oder über eine große Struktur wie bei JPG springen können.

Eine mögliche Abhilfe besteht darin, die komprimierten Daten zu bearbeiten oder das Bild in winzige Bereiche zu zerlegen, wie im Fall der GIF-Hashquine, aber das ist nicht optimal.

Eine andere Idee, die generisch funktioniert, ist, dass die Bilddaten ebenfalls mit dieser length data-Sequenzstruktur gespeichert werden: Wenn wir also zwei GIFs ohne Animation nehmen, müssen wir nur:

die Palette normalisieren
die Dauer des ersten Frames auf das Maximum setzen
einen Kommentar erzeugen, der zum Anfang der Daten des ersten Frames springt, sodass der Kommentar wie ein Kommentar über die Bilddaten rutscht, und auf dieselbe Weise endet: bis eine Nulllänge erreicht wird. Dann trifft der Parser auf den nächsten Frame und zeigt ihn an.

Mit einem geringen Aufwand (nur ein paar hundert Bytes Overhead) können wir über jedes GIF-Bild rutschen und die 256-Byte-Begrenzung umgehen. Diese Idee stammt von Marc, und sie ist brillant!

Letztendlich sind die derzeitigen GIF-Einschränkungen für sofortige MD5-Kollisionen:

keine Animation
Die Bilder müssen auf dieselbe Palette normalisiert werden – siehe gifsicle --use-colormap web
Die Bilder müssen dieselben Abmessungen haben
Nach 11 Minuten zeigen beide Dateien dasselbe Bild

Eine einfache Abkürzung, um Stand-GIF-Bilder zu normalisieren, besteht darin, sie zu Animationsframes desselben Bildes zu machen, dann können wir ein Skript verwenden, um FastColl-Blöcke wiederzuverwenden oder zu berechnen und so ein Dateipaar zu erzeugen, das jedes der beiden Bilder zeigt.

Beispiele:

⟷

2 MD5-kollidierende GIFs – Bilder von KidMoGraph

Hier ist eine Aufzeichnung des gesamten Vorgangs.

eine Aufzeichnung einer GIF-FastColl-Kollision

GZIP

GZIP-Spezifikation v4.3: RFC 1952 (1996).

Eine Gzip-Datei besteht aus einem oder mehreren verketteten ‚Members' (Gzip-Streams). Sie werden alle dekomprimiert und ihre unkomprimierten Inhalte aneinandergehängt – selbst wenn der unkomprimierte Inhalt des Members leer ist.
Diese Members können durch Nullen getrennt werden. Nullen werden einfach übersprungen, außer am Dateianfang. Jedes Nicht-Null-Byte wird auf die Signatur 1F 8B geprüft. Wenn es nicht zur Signatur passt, stoppt das Parsen, was genutzt werden kann, um das Parsen zwischen zwei Payloads zwangsweise zu stoppen, aber es werden Warnungen ausgelöst, die Probleme verursachen könnten. Eine andere Strategie besteht darin, am Ende der Datei einen zusätzlichen leeren Member hinzuzufügen und das Parsen beider Payloads dort enden zu lassen – an dem Member oder an seinem Body.
Der optionale filename und der file comment sind nullterminiert, während das Extra field über eine 16-Bit-Größenangabe definiert ist und daher missbraucht werden kann. Es besteht aus einem oder mehreren Teilfeldern (Subfields) mit einer ID und einer eigenen Teillänge, aber Teilfelder werden nicht erzwungen – nur sehr wenige sind offiziell definiert.

Daher ist ein leerer Gzip-Member mit einem Extra-Feld ein perfekter Parasitenwirt.

Wenn die oberste Datei zu groß ist, um in ein Extra-Feld zu passen, kann ihr unkomprimierter Stream in kleinere Dateien aufgeteilt werden, bis sie alle in Extra-Felder passen.

Nach dem Header eines Members folgen sein komprimierter Body, seine CRC32 und seine unkomprimierte Größe (nicht erzwungen). Daher bilden ein leerer Daten-Body mit seiner Null-CRC32 und -Größe einen generischen Postwrap, der sogar von verschiedenen Member-Headern gemeinsam genutzt werden kann.

Verschiedene Implementierungen verlassen sich auf die unkomprimierte Größe des letzten Members anstatt auf die Summe aller Members. Unsere kollidierten Dateien zeigen also, dass sie die Größe null haben, weil diese Dateien mit einem leeren Member als Trampolin enden.

Hier ist ein Skript, um sofortige MD5-Kollisionen zweier GZip-Dateien zu erzeugen. Es verbringt die meiste Zeit damit, Daten zu dekomprimieren und erneut zu komprimieren, wenn die Eingabedateien groß sind – die Kollisionspräfixe sind vorberechnet. Das Aufteilen von Members ohne Dekomprimieren ist nicht möglich, da die unkomprimierte CRC32 berechnet werden muss.

Eine .tar.gz ist nur das gzip-Archiv eines tar-Archivs. Es funktioniert problemlos mit gegzipptem tar, anders als tar selbst.

Beispiele: collision1.tar.gz (Pacome) ⟷ collision2.tar.gz (Reg)

LZ4 / Zstandard

LZ4 und Zstandard sind zwei verschiedene Kompressionsformate mit einer ähnlichen Gesamtstruktur: Sie bestehen aus Frames, die jeweils mit einer spezifischen Magic beginnen: 0xFD2FB528 für Zstandard-Frames, 0x184D2204 für Lz4-Frames.

Sie teilen sich auch dieselben ‚überspringbaren' TLV-Frames, die mit 4 Bytes Magics im Bereich 0x184D2A50 – 0x184D2A5F beginnen, dann der Length der Nutzdaten (4 Bytes, Little-Endian), dann den User Data selbst. Diese Frames sind vollständig optional, beliebig lang und wiederholbar. Die Dateien können mit diesen Frames beginnen. Diese Frames können also verkettet werden, um ein perfektes generisches Kollisionspräfix über zwei Formate hinweg zu erzeugen.

Hier ist ein Skript, um sofortige MD5-Kollisionen zweier Zstd/Lz4-Dateien zu erzeugen. Wie bei Gzip sind von außen zwei verschiedene Archive sichtbar, unabhängig vom Inhalt: zum Beispiel ein .cpio.zst.

Beispiele:

Portable Executable

Das Portable Executable hat eine eigentümliche Struktur:

Der alte DOS-Header ist fast nutzlos und zeigt auf die nächste Struktur, den PE-Header. Der DOS-Header hat keine andere Rolle. DOS-Header können zwischen ausführbaren Dateien ausgetauscht werden.
Der DOS-Header muss an Offset 0 liegen und hat eine feste Länge eines vollständigen Blocks, und der Zeiger befindet sich am Ende der Struktur, außerhalb der Reichweite von UniColl: Daher ist nur eine Chosen-Prefix-Kollision nützlich, um PE-Dateien auf diese Weise kollidieren zu lassen.
Der PE-Header und was darauf folgt, definiert die gesamte Datei.

Die Strategie ist also:

Der PE-Header kann nach unten verschoben werden, um Platz für Kollisionsblöcke nach dem DOS-Header zu schaffen.
Der DOS-Header kann (über Chosen-Prefix-Kollisionen) ausgenutzt werden, um auf zwei verschiedene Offsets zu zeigen, an die zwei verschiedene PE-Header verschoben werden.
Die Sektionen können direkt hintereinander platziert werden, nach der DOS/Collisions/Header1/Header2-Struktur. Man muss nur ein Delta auf die Offsets der beiden Sektionstabellen anwenden.

Das bedeutet, dass es möglich ist, jedes Paar von PE-Executables sofort kollidieren zu lassen. Selbst wenn sie unterschiedliche Subsysteme oder Architekturen verwenden.

Während Kollisionen von Executables über jeden Lader normalerweise trivial sind, ist diese Art der Ausnutzung hier transparent: Der Code ist identisch und wird an derselben Adresse geladen.

Beispiele: tweakPNG.exe (GUI) ⟷ fastcoll.exe (CLI)

Hier ist ein Skript, um sofortige MD5-Kollisionen von Windows-Executables zu erzeugen.

MP4 und andere

Der Container dieses Formats ist eine Folge von Length Type Value-Chunks, die Atoms genannt werden. Die Länge ist ein 32-Bit-Big-Endian-Wert und umfasst sich selbst, den Typ und den Wert, daher beträgt die normale Mindestlänge 8 (der Typ ist ein String aus 4 ASCII-Zeichen).

Wenn die Länge null ist, nimmt das Atom den Rest der Datei ein – wie zum Beispiel jp2c-Atoms in JP2-Dateien. Wenn sie 1 ist, folgt auf den Typ eine 64-Bit-Länge, wodurch das Atom zu Type Length Value wird und mit anderen Kollisionen wie Shattered kompatibel ist.

Manche Atoms enthalten andere Atoms: In diesen Fällen werden sie Boxes genannt. Deshalb wird diese ansonsten unbenannte Struktur „atom/box" genannt.

Dieses in MP4 verwendete „atom/box"-Format ist eigentlich eine Ableitung von Apple Quicktime, und wird von vielen anderen Formaten verwendet (JP2, HEIF, F4V).

Der erste Atom-Typ ist normalerweise ftyp, was die Unterscheidung des tatsächlichen Dateiformats ermöglicht.

Das Format ist recht permissiv: Verkette einfach free-Atoms, missbrauche die Länge eines davon mit UniColl und springe dann über die erste Payload.

Bei MP4-Dateien muss nur noch die stco-Tabelle (Sample Table – Chunk Offsets) oder die co64-Tabelle (das 64-Bit-Pendant) angepasst werden, da es absolute(!) Offsets sind, die auf die mdat-Filmdaten zeigen – und sie werden tatsächlich erzwungen!

Daraus ergibt sich ein Skript, das jedes beliebige Video sofort kollidieren lässt – und wie erwähnt, funktioniert es möglicherweise auch mit anderen Formaten als MP4.

Nirvana - Smells like Teen Spirit / Weird Al Yankovik - Smells like Nirvana

Beispiele (Videos von KidMoGraph):

32-Bit-Längen (Standard) collision1.mp4 ⟷ collision2.mp4

⟷
64-Bit-Längen collisionl1.mp4 ⟷ collisionl2.mp4

⟷

Beachte, dass einige Viewer (OS X, Safari, FireFox) keine Datei zulassen, die mit einem Atom beginnt, das nicht ftyp ist. In diesem Fall muss das Präfix dies abdecken, und es ist nicht so generisch, aber ansonsten ist es dieselbe Strategie – nur auf einen einzigen Dateityp beschränkt.

JPEG2000

JPEG2000-Dateien beginnen normalerweise mit der Atom/Box-Struktur wie MP4, dann reicht das letzte Atom jp2c typischerweise bis zum Ende der Datei (Nulllänge), danach folgt ab diesem Punkt die JFIF-Struktur wie bei JPEG (beginnend mit FF 4F als Segmentmarker).

Die reine JFIF-Form wird ebenfalls toleriert, in diesem Fall ist die Kollision wie bei JPEG: Shattered-kompatibel, aber mit Kommentaren, die auf 64 KB begrenzt sind.

Wenn du JPEG2000-Dateien dagegen mit der Atom/Box-Struktur bearbeitest, hast du diese Einschränkung nicht.

Wie bereits erwähnt, wenn du versuchst, diese Struktur kollidieren zu lassen und es weitere Einschränkungen gibt – zum Beispiel, dass ein Beginn mit einem free-Atom von manchen Formaten nicht toleriert wird – dann kannst du andere UniColl-Präfixpaare berechnen, die für dieses Format spezifisch sind: JPEG2000 scheint zu erzwingen, dass zuerst ein 'jP '-Atom vor dem üblichen ftyp kommt, aber abgesehen davon ist das die einzige Einschränkung: Es muss nichts verschoben werden.

Das resultierende Skript ist also sogar einfacher!

Oded Goldreich / Neal Koblitz

Beispiele: collision1.jp2 ⟷ collision2.jp2

PDF

über Shattered

Die Shattered-Ausnutzung war kein PDF-Trick, sondern ein JPG-Trick in einer PDF. Sie ermöglichte nur, dass eine PDF ein JPG-komprimiertes Objekt enthalten konnte, das zwei verschiedene Inhalte haben konnte. Beide PDFs mussten ansonsten völlig identisch sein.

Beachte, dass die Dokumente völlig normal sein können und das kollidierende JPG einfach ausschneiden und an verschiedenen Stellen anzeigen können, beispielsweise in mehrseitigen Dokumenten.

Beispiele: das Shattered-Papier, verändert ⟷ das Shattered-Papier, Original

das Shattered-Papier mit einem kollidierenden JPG an zwei Stellen

PDF-Kollisionen mit MD5

Mit MD5 (und anderen Kollisionsmustern) können wir PDF-Kollisionen auf Dokumentebene durchführen, ohne jegliche Einschränkungen an einer der beiden Dateien!

PDF hat eine ganz andere Struktur als andere Dateiformate. Es verwendet Objektnummern und Referenzen, um einen Baum zu definieren. Das gesamte Dokument hängt vom Root-Element ab.

Diese (gültige) PDF``` text %PDF-1. 1 0 obj<</Pages 2 0 R>>endobj 2 0 obj<</Kids[3 0 R]/Count 1>>endobj 3 0 obj<</Parent 2 0 R>>endobj trailer <</Root 1 0 R>>

ist äquivalent zu:``` text
%PDF-1.
11 0 obj<</Pages 12 0 R>>endobj
12 0 obj<</Kids[13 0 R]/Count 1>>endobj
13 0 obj<</Parent 12 0 R>>endobj
trailer <</Root 11 0 R>>

Tricks:

Das Speichern ungenutzter Objekte in einer PDF ist zulässig.
Das Überspringen beliebiger Objektnummern ist ebenfalls in Ordnung. Es gibt sogar einen offiziellen Weg, Nummern in der XREF-Tabelle zu überspringen.

Das Speichern zweier Dokumentbäume in derselben Datei ist also in Ordnung. Wir müssen lediglich dafür sorgen, dass das Root-Objekt auf eines der beiden Root-Objekte der Dokumente verweist.

Wir müssen also zwei Dokumente nehmen, Objekte und Referenzen so umnummerieren, dass es keine Überlappung gibt, eine Kollision erzeugen, sodass die als Root-Objekt referenzierte Elementnummer geändert werden kann, während der Hashwert gleich bleibt, was perfekt zu UniColl mit N=1 passt, und die XREF-Tabelle entsprechend anpassen.

Auf diese Weise können wir sicher jedes beliebige Paar von PDFs kollidieren lassen, unabhängig von Seitenzahlen, Abmessungen, Bildern ...

Kommentare

PDF kann fremde Daten auf zwei Arten speichern:

als Zeilenkommentar, bei dem die einzigen verbotenen Zeichen Zeilenumbrüche (\r und \n) sind. Das kann innerhalb eines Dictionary-Objekts verwendet werden, um beispielsweise eine Objektreferenz zu ändern, über UniColl. Das ist also ein gültiges PDF-Objekt, selbst wenn es binäre Kollisionsblöcke enthält – wiederhole einfach, bis du keine Zeilenumbruchzeichen mehr hast: ``` 1 0 obj << /Type /Catalog /MD5_is /REALLY_dead_now__ /Pages 2 0 R %¥┬•σe╕█╙X₧_~π▌╒εX∟■φe♦%τ8╞■[...]p╛╬ûFZ»‼v◘Åp↑╝%▓% ▼σφj╔◄dZ▀c²aU≤╨╩[├└─yNΓ5╔+▀╪yδ☻ß⌐░¼à(☺z₧

endobj
als Stream-Objekt, in diesem Fall sind beliebige Daten möglich, aber da wir uns innerhalb eines Objekts befinden, können wir nicht die gesamte PDF-Struktur verändern, daher ist eine Kollision mit gewähltem Präfix erforderlich, um die Struktur außerhalb des enthaltenden Stream-Objekts zu modifizieren.

kollidierender Text

Der erste Fall ermöglicht es, die Schönheit von UniColl hervorzuheben, einer Kollision, bei der die Unterschiede vorhersehbar sind, sodass man Poesie über kollidierende Daten schreiben kann - dank Jurph!

Anstatt die Struktur des Dokuments zu verändern und Parser zu täuschen, verwenden wir einfach Kollisionsblöcke direkt, um direkt Text mit alternativer Lesart zu erzeugen!``` V V Now he hash MD5, Now he hath MD5, No enemy cares! No enemy dares! Only he gave Only he have the shards. the shares. Can’t be owned & Can’t be pwned & his true gold, his true hold, like One Frail, like One Grail, sound as fold. sound as gold. ^ ^

Beispiele: [poeMD5 A](https://github.com/corkami/collisions/blob/HEAD/examples/poeMD5_A.pdf) ⟷ [poeMD5 B](https://github.com/corkami/collisions/blob/HEAD/examples/poeMD5_B.pdf)



*Eine wahre kryptografische künstlerische Schöpfung :)*

(Hinweis: Ich habe es mit der Adobe-Kompatibilität vermasselt, aber das ist mein Fehler, nicht der von UniColl)


**kollidierende Dokumentstruktur**

Egal, ob Sie UniColl als Inline-Kommentar oder als gewähltes Präfix in einem Dummy-Stream-Objekt verwenden, die Strategie ist ähnlich:
Objekte werden neu angeordnet, dann wird das Root-Objekt auf andere Objekte zeigen lassen. Anders als bei Shattered bedeutet das eine sofortige Kollision eines beliebigen PDF-Paares auf Dokumentebene.

Ein nützlicher Trick ist, dass die Ausgabe von [`mutool clean`](https://mupdf.com/docs/manual-mutool-clean.html) zuverlässig vorhersagbar ist,
daher kann es verwendet werden, um PDFs als Eingabe zu normalisieren und das zusammengeführte PDF zu reparieren, während die wichtigen Teile der Datei unverändert bleiben.
MuTool verwirft falsche Schlüssel/Werte nicht - außer man bittet es darum - und behält sie in derselben Reihenfolge bei.
Daher eignen sich gefälschte Wörterbucheinträge wie `/MD5_is /REALLY_dead_now__` perfekt, um Dinge vorhersagbar auszurichten, ohne eine andere Art von Kommentaren zu benötigen.
Allerdings behält es keine Kommentare in Wörterbüchern (also kein Inline-Kommentar-Trick)

Eine einfache Möglichkeit, die Objektumsortierung ohne Aufwand durchzuführen, besteht darin, beide PDF-Dateien
per `mutool merge` zusammenzuführen und dann das `/Pages`-Objekt in zwei Teile aufzuteilen.

Um Platz für dieses Objekt zu schaffen, fügt man einfach vor den beiden Dokumenten ein Dummy-PDF ein.

Optional kann eine gefälschte Referenz auf das verwaiste Array erstellt werden,
um zu verhindern, dass die Garbage Collection den zweiten Seitensatz löscht.


**Beispiel**:
Mit diesem [Skript](https://github.com/corkami/collisions/blob/HEAD/scripts/pdf.py)
dauert es [weniger als eine Sekunde](https://github.com/corkami/collisions/blob/HEAD/examples/pdf.log), die beiden öffentlichen PDF-Dokumente wie Spectre und Meltdown zur Kollision zu bringen:

Beispiele: [spectre.pdf](https://github.com/corkami/collisions/blob/HEAD/examples/collision1.pdf) ⟷ [meltdown.pdf](https://github.com/corkami/collisions/blob/HEAD/examples/collision2.pdf)



Mögliche Erweiterung: UniColl-Blöcke verketten, um auch Paare der verschiedenen [nicht kritischen Objekte](https://www.adobe.com/content/dam/acom/en/devnet/pdf/pdfs/PDF32000_2008.pdf#page=81) zu behalten,
die im Root-Objekt referenziert werden können - wie `Outlines`, `Names`, `AcroForm` und Additional Actions (`AA`) - in den ursprünglichen Quelldateien.

**in PDFLaTeX**

Die bisherigen Techniken funktionieren mit nur einem Paar PDF-Dateien,
aber es ist auch möglich, dies direkt aus TeX-Quellen zu tun,
über [spezifische PDFTeX-Operatoren](http://texdoc.net/texmf-dist/doc/pdftex/manual/pdftex-a.pdf).

Sie können Objekte direkt definieren - einschließlich Dummy-Schlüssel und -Werten für Ausrichtungen - und leere Objekte definieren, um einige Objekt-Slots zu reservieren, indem Sie dies ganz am Anfang Ihrer TeX-Quellen einfügen:``` latex
% set PDF version low to prevent stream XREF
\pdfminorversion=3

\begingroup

  % disable compression to keep alignments
  \pdfcompresslevel=0\relax

  \immediate
  \pdfobj{<<
    /Type /Catalog

    % cool alignment padding
    /MD5_is /REALLY_dead_now__

    % the first reference number should be on offset 0x49,
    % so the '2' object number will be changed to '3' by UniColl
    /Pages 2 0 R

    % now padding so that the collision blocks (ends at 0xC0) are covered
    /0123456789ABCDEF0123456789ABCDEF0123456789ABCDEF
    % with an extra character to be replaced by a return char
    /0123456789ABCDEF0123456789ABCDEF0123456789ABCDEF0123456789ABCDEF0
  >>}

  % the original catalog of the shifted doc
  \immediate\pdfobj{<</Type/Pages/Count 1/Kids[8 0 R]>>}

  % the original catalog of the host doc
  \immediate\pdfobj{<</Type/Pages/Count 1/Kids[33 0 R]>>}

  % now we need to reserve PDF Objects so that there is no overlap
  \newcount\objcount

  % the host size (+3 for spare object slots) - 1
  % putting a higher margin will just work, and XREF can have huge gaps
  \objcount=25
  \loop
    \message{\the\objcount}
    \advance \objcount -1

  \immediate\pdfobj{<<>>} % just an empty object

  \ifnum \objcount>0
  \repeat

\endgroup

Vergiss nicht, die PDFLaTeX-Ausgabe zu normalisieren – zum Beispiel mit mutool –, falls nötig: Mit PDFLaTeX ist es schwer, über Distributionen hinweg reproduzierbare Builds zu erhalten – du möchtest vielleicht sogar die Ausführungszeit einbinden, um bei Bedarf den exakten Hash zu erhalten.

JPG in PDF

Man könnte erwarten, dass JPG nur Bilder sind, aber in einem PDF und in einigen PDF-Readern (keine Browser, wie Evince und Adobe Reader), kann es als Seiteninhalt verwendet werden, genau wie jedes andere eingebettete Objekt, das in einem JPEG-Bild eingebettet ist.

Um die JPEG-Daten verlustfrei zu speichern, speichere sie als 100 % Graustufen, und verwende dann entweder ein Bild mit einer einzelnen Zeile/Spalte, oder wiederhole die Datenzeile 8-mal (da JPEG-Blöcke 8x8 sind), dann werden deine Daten verlustfrei gespeichert und von den PDF-Seiten referenziert.

Beispiele für zwei SHA-1-kollidierende PDFs über JPEG-Seitendaten (ein Graustufenbild, das Farben rendert) als Vektor-Seiteninhalt:

If ⟷ Shattered - the movie

2 SHA-1-kollidierende PDFs mit als JPG gespeicherten Bilddaten

Es ist möglich, das kollidierende JPG zweimal zu referenzieren: verlustfrei als Seiteninhalt, der sich selbst zusätzlich als verlustbehaftetes, anzuzeigendes Bild referenziert. Auch hier ist das anzuzeigende Bild in Graustufen gehalten, aber der Seiteninhalt kann über PDF-Operatoren einige Farben rendern.

Der obere Teil des Bildes zeigt den Seiteninhalt, der 8-mal wiederholt wird.

Beispiele für zwei SHA-1-kollidierende PDFs, bei denen JPEG als Seitendaten und als anzuzeigendes Bild verwendet wird:

Skulls & Crossbones ⟷ Golden Axe

2 SHA-1-kollidierende PDFs mit JPG, das als Bild und Seiteninhalt verwendet wird

ZIP

TL;DR Es gibt keine generische wiederverwendbare Kollision für ZIP, aber für ZIP-basierte Formate schon. Es sollte möglich sein, zwei Dateien in 2h.core kollidieren zu lassen (36-mal schneller als chosen-prefix).

ZIP-Archive sind ein Sandwich aus 3 Schichten (mindestens). Zuerst kommt der Inhalt der Dateien (eine Folge von Local File Header-Strukturen, eine pro archivierter Datei oder Verzeichnis), dann ein Index (wiederum eine Folge von Central Directory), dann eine einzelne Struktur, die auf diesen Index zeigt (End Of Central Directory).

Die Reihenfolge dieser Schichten kann nicht verschoben werden. Manche Parser benötigen nur die Struktur des Dateiinhalts, aber das ist keine korrekte Art zu parsen und kann missbraucht werden.

Wegen dieser erforderlichen Reihenfolge gibt es kein generisches Präfix, das für eine beliebige Kollision helfen könnte.

Nicht generischer Ansatz

Ein anderer Ansatz könnte sein, einfach beide Archive mit ihren zusammengeführten Schichten zu mergen und UniColl zu verwenden – aber mit N=2, was eine Differenz am 4. Byte einführt –, um die magische Signatur des End of Central Directory zu zerstören.

Das bedeutet, man könnte zwei beliebige ZIP-Archive mit einem einzigen UniColl und einem festgelegten Präfix von 24 Bytes kollidieren lassen.

Ein typisches End of Central Directory, das 22 Bytes lang ist, wenn der Kommentar leer ist:``` 00: 504b 0506 0000 0000 0000 0000 0000 0000 PK.............. 10: 0000 0000 0000 ......

Wenn wir dies als Präfix (das Präfix auf 16 Bits auffüllen) für UniColl und `N=2` verwenden, liegt der Unterschied im 4. Byte, wodurch der Magic-Wert `.P .K 05 06` zerstört wird, indem er vorhersehbar zu `.P .K 05 86` geändert wird.```
00: 504b 0506 0000 0000 0000 0000 0000 0000  PK..............
10: 0000 0000 0000 2121 eb66 cf9d db01 83bb  ......!!.f......
20: 2888 4c41 e345 7d07 1634 5d4a 3b61 89a0  (.LA.E}..4]J;a..
30: 0029 94af 4168 2517 0bbc b841 cbf2 9587  .)..Ah%....A....
40: e438 0043 6390 279d 7c9e a01e e476 4c36  .8.Cc.'.|....vL6
50: 527f b1f4 653e d866 f98d 7278 5324 0bd5  R...e>.f..rxS$..
60: b31d ef6d d5d6 1163 5a2e a8a5 21bf eab4  ...m...cZ...!...
70: c59c 028e a913 f6b7 0036 c93f 5092 a628  .........6.?P..(

I'm ready to translate the content, but the input appears to be empty—no Markdown text was included after "INPUT:". Please provide the chunk content you'd like translated from English to German.``` 00: 504b 0586 0000 0000 0000 0000 0000 0000 PK.............. 10: 0000 0000 0000 2121 eb66 cf1d db01 83bb ......!!.f...... 20: 2888 4c41 e345 7d07 1634 5d4a 3b61 89a0 (.LA.E}..4]J;a.. 30: 0029 94af 4168 251f 0bbc b841 cbf2 9587 .)..Ah%....A.... 40: e438 00c3 6390 279d 7c9e a01e e476 4c36 .8..c.'.|....vL6 50: 527f b1f4 653e d866 f98d 72f8 5324 0bd5 R...e>.f..r.S$.. 60: b31d ef6d d5d6 1163 5a2e a8a5 21bf eab4 ...m...cZ...!... 70: c59c 028e a913 f6af 0036 c93f 5092 a628 .........6.?P..(

Das ist überhaupt nicht generisch, aber viel schneller als chosen-prefix collision:```
real 12m23.993s
user 112m24.072s
sys 2m0.194s

Ein Problem ist, dass einige Parser ZIP-Dateien immer noch kopfüber parsen, auch wenn sie von unten nach oben geparst werden sollten: eine Möglichkeit, sicherzustellen, dass beide Dateien korrekt geparst werden, besteht darin, zwei UniColl-Blöcke zu verketten, um jedes End of Central Directory zu aktivieren/deaktivieren.

Um zu verhindern, dass ZIP-Parser sich über ungenutzten Speicherplatz beschweren, kann man Extra Fields, Dateikommentare im Central Directory und Archivkommentare im End of Central Directory missbrauchen.

diagram of ZIP collision

Beispiel: hier ist ein Assembly-Quellcode, der die Struktur einer Dual-ZIP beschreibt, die zwei verschiedene Archivdateien enthalten kann.

Nach zwei Unicoll-Berechnungen erhält man die beiden kollidierenden Dateien: collision1.zip ⟷ collision2.zip

Zip-basierte Formate

Auch wenn das ZIP-Format selbst nicht generisch wie Gzip ausgenutzt werden kann, können einige Formate, die auf ZIP basieren, generisch in ZIP-Archiven mit einer vordefinierten Struktur ausgenutzt werden. Es müssen einige Vorkehrungen getroffen werden, um die ZIP-Kollision generisch zu machen.

Einige Formate sind mehrere Dateien, die in einem ZIP-Archiv gespeichert sind, und verlassen sich auf eine Root-Datei mit einem festen Dateinamen, die auf andere Dateien im Archiv verweist. Viele von ihnen verwenden XML oder Text für die Root-Datei und speichern andere Dateien unverändert.

Idee : 2 Dateisätze im selben Archiv koexistieren lassen und auf einen der beiden Dateisätze verweisen. Eine generische Root-Datei kann zuerst am Anfang der Datei gespeichert werden, aber die Kollisionsblöcke werden außerhalb des Dateiinhalts im Archiv gespeichert (da Kollisionen eine sehr hohe Entropie haben, ist es unmöglich, XML- oder reine ASCII-Dateien mit Kollisionen auszunutzen).

Schritte:

Lege 2 Dateisätze aus 2 Ursprüngen im selben Archiv ab - d.h. in verschiedenen Unterverzeichnissen.
Ändere die Root-Datei so, dass sie abwechselnd auf jeden Dateisatz verweist.
Da der Zeitstempel, die Länge und die CRC der Root-Datei sowohl im Local File Header - vor dem Inhalt der Datei - als auch im Central Directory - nach dem Dateiinhalt - gespeichert werden, sollten sich diese Werte zwischen den beiden Versionen der Dateien nicht ändern.
- Wenn die Länge variiert, variieren anschließend alle Zeiger, sodass ein identischer Suffix nicht möglich wäre.
- Wenn die CRC32 im Central Directory falsch ist, könnte diese Kopie des Werts vom Parser ignoriert werden, aber das Fälschen einer CRC32 auf einen konstanten Wert hilft, das Problem vollständig zu vermeiden. Das Fälschen der CRC durch Anhängen von 4 zufälligen Bytes wird wahrscheinlich nicht ausreichen, da diese Root-Dateien typischerweise in XML oder Text mit strenger Syntax vorliegen und dadurch ungültig würden. CrcHack hilft sehr beim Fälschen von CRCs mit beliebigen Bits und ohne Brute-Force und stellt sicher, dass die Ausgabedatei ASCII ist und dass die modifizierten Bits weiterhin in einem Kommentar liegen.
Die Verwendung des extra field einer zusätzlichen Dummy-Datei -- selbst leer -- im Archiv nach der Root-Datei ist eine elegante Möglichkeit, Hashclash-Kollisionsblöcke zu speichern: Auf diese Weise behält das ZIP-Archiv eine Standardstruktur und kann danach sogar mit Standardwerkzeugen leicht manipuliert werden.

Extra Fields haben keine CRC32, und ihre 16-Bit-Länge wird vorab in den Headern deklariert. Sie haben ihr eigenes internes Format ID:2 Size:2 Data, das aber normalerweise ignoriert wird, und sie befinden sich sowohl im Local File Header als auch im Central Directory, können aber im Central Directory fehlen, um den Suffix nach den Kollisionsblöcken identisch zu halten.

Das Vorhandensein der zusätzlichen Datei, die die Kollisionsblöcke in ihrem extra field abdeckt, muss möglicherweise in der Formatstruktur deklariert werden, z. B. in der Datei [Content_Types].xml in einem OOXML-Dokument. Andere XML-Dateien im Suffix müssen möglicherweise geändert werden, da einige Formate die Verwendung absoluter Pfade erfordern.

Hier ist die Gesamtstruktur des generischen Exploits für ein bestimmtes ZIP-basiertes Format:``` [Root file] (with constant CRC32)

[Dummy file] (with collision blocks in the extra field)

[...] <- rest of the archive, with 2 documents merged

Also, indem man den Inhalt der Root-Datei vordefiniert und ASCII-CRC32s fälscht, kann man eine generische, wiederverwendbare Hashclash-Kollision für ein bestimmtes ZIP-basiertes Format berechnen.


### Anforderungsübersicht

- zwei oder mehr Präfixe
- eine oder mehrere Dateitypen (Polyglots funktionieren ohne Probleme)
- eine XML-Root-Datei mit festem Dateinamen, fester Dateilänge und CRC: Diese Informationen sind zweimal vorhanden, vor und nach den Kollisionsblöcken
 - Inhalte sind beliebiges XML
 - Padding ist möglich, sogar über einen XML-Kommentar, um dieselbe Länge zu erreichen.
 - Die CRC kann (über CrcHack) für jeden Inhalt gesetzt werden.
- beide Dateisätze koexistieren im Suffix, wahrscheinlich in verschiedenen Verzeichnissen. Manche Werkzeuge kodieren den Pfad fest, was die Kompatibilität einschränken kann.
- eine *Content-type*-XML-Datei muss möglicherweise zusammengeführt werden, um alle Dateien abzudecken, unterstützte und nicht unterstützte (Kollisionsblöcke und alternatives Dokument).


### Beispiele

#### CRC32

Ein minimaler XML-Kommentar (nur ASCII) mit einer gefälschten CRC32 (sofortige Berechnung) mit CrcHack.``` bash
echo "<!--ABCDEF-->" | crchack -b 4.0:+.8*6:1 -b 4.1:+.8*6:1 -b 4.2:+.8*6:1 -b 4.3:+.8*6:1 -b 4.4:+.8*6:1 -b 4.5:+.8*5:1 - 0xdeadf00d
<!--X{]EZF-->

Ein weiteres Beispiel, bei dem Sie die CRC anhand der Groß-/Kleinschreibung einer alphabetischen Nachricht anpassen.```bash echo "" | crchack.exe -b 4:+.8*32:.8 - 0xcafebabe

#### Kollisionen

[zInsider](https://github.com/corkami/collisions/blob/HEAD/scripts/zinsider.py) ist ein Skript, um sofort MD5-Kollisionen von Paaren beliebiger Dokumente mit diesen ZIP+XML-Formaten zu erzeugen:
- Office Open XML: docx / pptx / xlsx
- Open Container Format: epub
- Open Packaging Conventions:
  - 3D-Fertigungsformat: 3mf
  - XML Paper Specification: xps / oxps

Um eigene Kollisions-Präfixe zu erzeugen, [hier ist ein Skript](https://github.com/corkami/collisions/blob/HEAD/scripts/makezip.py), um ein Wurzel-ZIP-Paar zu generieren.
Nach der Berechnung von Kollisionen verwende [dieses andere Skript](https://github.com/corkami/collisions/blob/HEAD/scripts/extendzip.py), um dieses Wurzelpaar mit einem gemeinsamen Suffix zu kombinieren.

Einige Kollisions-PoCs:
- Office Open XML: Excel ([1](https://github.com/corkami/collisions/blob/HEAD/examples/free/md5-1.xls) - [2](https://github.com/corkami/collisions/blob/HEAD/examples/free/md5-2.xls)), Powerpoint ([1](https://github.com/corkami/collisions/blob/HEAD/examples/free/md5-1.pptx) - [2](https://github.com/corkami/collisions/blob/HEAD/examples/free/md5-2.pptx)), Word ([1](https://github.com/corkami/collisions/blob/HEAD/examples/free/md5-1.docx) - [2](https://github.com/corkami/collisions/blob/HEAD/examples/free/md5-2.docx)).
- Open Container Format: Epub ([1](https://github.com/corkami/collisions/blob/HEAD/examples/collision-1.epub) - [2](https://github.com/corkami/collisions/blob/HEAD/examples/collision-2.epub)).
- Open Packaging Conventions: 3MF ([1](https://github.com/corkami/collisions/blob/HEAD/examples/collision-1.3mf) - [2](https://github.com/corkami/collisions/blob/HEAD/examples/collision-2.3mf)), XPS ([1](https://github.com/corkami/collisions/blob/HEAD/examples/collision-1.xps) - [2](https://github.com/corkami/collisions/blob/HEAD/examples/collision-2.xps)).


Einige Formate mit mehreren Dateien auf Zip-Basis können nicht generisch ausgenutzt werden:
- Quake PK3: ein Zip von Dateien ohne spezifisches Wurzelverzeichnis.
- Open Document Format: Die Datei `META-INF/manifest.xml` muss jede andere Datei erwähnen, daher kann es nicht generisch sein.
- APK, JAR, XPI: Die Datei `META-INF/MANIFEST.mf` muss ebenfalls jede andere Datei mit ihren Hashes erwähnen.


Dank an [Philippe Lagadec](https://twitter.com/decalage2) für seine Hilfe bei Office-Dateiformaten!


### Sonstiges

- Wasm, über einen benutzerdefinierten Abschnitt: [Skript](https://github.com/corkami/collisions/blob/HEAD/scripts/wasm.py), Beispiele: [md5-1.wasm](https://github.com/corkami/collisions/blob/HEAD/examples/free/md5-1.wasm) ⟷ [md5-2.wasm](https://github.com/corkami/collisions/blob/HEAD/examples/free/md5-2.wasm)


## Ungewöhnliche Strategien

Bei Kollisionen geht es normalerweise um zwei gültige Dateien desselben Typs.


### MultiColls: Kette mehrerer Kollisionen

Nichts hindert daran, mehrere Kollisionsblöcke zu verketten,
und mehr als zwei Inhalte mit demselben Hashwert zu haben.
Ein Beispiel dafür sind *Hashquines* – die ihren eigenen MD5-Wert zeigen.
Die Datei [PoCGTFO 14](https://github.com/angea/pocorgtfo#0x14) enthält 609 FastColl-Kollisionen,
um dies über zwei Dateitypen in derselben Datei zu erreichen.


#### Hashquines

Hashquines sind Dateien, die ihren eigenen Hashwert anzeigen. Sie werden [hier](https://github.com/corkami/collisions/blob/HEAD/hashquines/) behandelt.


### Gültigkeit

Eine andere Strategie wäre, den Dateityp zu zerstören, um das Scannen als beschädigte Datei zu umgehen.
Es reicht, einfach die Magic-Signatur zu überschreiben.
Das Anhängen beider Dateien (gültig oder ungültig) mit einem Format,
das nicht bei Offset 0 beginnen muss (Archiv, wie ZIP/RAR/...), würde einen anderen Dateityp offenbaren.

Dies ermöglicht Polyglott-Kollisionen ohne Verwendung einer Chosen-Prefix-Kollision:
1. Verwende UniColl, um eine Magic-Signatur zu aktivieren oder zu deaktivieren, zum Beispiel eines PNG:
2. Hänge ein ZIP-Archiv an

Obwohl technisch gesehen beide Dateien ein gültiges ZIP sind, sehen die meisten Parser den ersten gefundenen Dateityp, da sie bei Offset 0 zu scannen beginnen, und sehen so einen anderen Dateityp.

Beispiele:

 ⟷ [ungültig](https://github.com/corkami/collisions/blob/HEAD/examples/png-invalid.png)



### PolyColls: Kollisionen verschiedener Dateitypen

Es ist auch möglich, beide Seiten einer Kollision mit unterschiedlichen Typen zu haben, um den Verdacht zu verringern:

Angriffsszenario:
1. sende `holiday.jpg`
2. bringe sie auf die Whitelist
3. sende `evil.exe`, die denselben MD5 besitzt.

In diesen Fällen ist eine Chosen-Prefix-Kollision erforderlich,
wenn beide Dateiformate bei Offset 0 beginnen müssen.

Einige Beispiele für Polycoll-Layouts:

![pdf-jpg-Polyglott-Kollision](https://assets.kitploit.com/production/public/readmes/47471/3dcd55e877a4ce9c933bf1478d0a71ede85e129b9e746414d754ffabceabe463.png)

*PDF/JPG-Polycoll*


![pe-png-Polyglott-Kollision](https://assets.kitploit.com/production/public/readmes/47471/63df55a15e7ca33153f352f13ba273604df6b1ae3e1e8838b601fea39de801e0.png)

*PE/PNG-Polycoll*


#### PE - JPG

Da ein PE-Header normalerweise kleiner als 0x500 Bytes ist, passt er perfekt in einen JPG-Kommentar:
1. Beginne mit DOS/JPG-Headern
2. Der JPEG-Kommentar springt über den PE-Header
3. Füge das vollständige JPG-Bild ein
4. Füge die gesamten PE-Spezifikationen ein

Auch hier ist die Kollision [sofort](https://github.com/corkami/collisions/blob/HEAD/scripts/jpgpe.py)

Beispiele: [fastcoll.exe](https://github.com/corkami/collisions/blob/HEAD/examples/jpg-pe.exe) ⟷ [Marc.jpg](https://github.com/corkami/collisions/blob/HEAD/examples/jpg-pe.jpg)


#### PDF - PE

Das Zusammenführen eines PDFs mit einer Dummy-Datei mit `mutool` ist ein guter generischer Weg, um Objekte neu anzuordnen,
und dann die ersten beiden Objekte verwerfbar zu machen (Dummy-Seite und Inhalt),
was perfekt für ein Hosting-`stream`-Objekt unbekannter Länge als `1 0` geeignet ist,
und dessen Länge weiter hinten (nach den Kollisionsblöcken) im zweiten Objekt referenziert wird.

Das einzige Problem ist, dass `mutool` die Länge immer inline einfügt – und die Längenreferenz entfernt,
daher muss sie anstelle des Werts wieder in das PDF eingefügt werden,
aber die meisten Referenzen `2 0 R` werden kleiner sein als hartkodierte Längen.
Zum Glück kann dies behoben werden, ohne irgendeinen Objekt-Offset zu verändern,
sodass kein Patchen des XREF nötig ist.

Hier ist ein [Skript](https://github.com/corkami/collisions/blob/HEAD/scripts/pdfpe.py), um zum Beispiel einen PDF-Viewer ([Sumatra](https://www.sumatrapdfreader.org/free-pdf-reader.html) ist leichtgewichtig und eigenständig) und ein PDF-Dokument sofort kollidieren zu lassen:

Beispiele: [Poster.pdf](https://github.com/corkami/collisions/blob/HEAD/examples/pepdf.pdf) ⟷ [Sumatra.exe](https://github.com/corkami/collisions/blob/HEAD/examples/pepdf.exe)

![ein PDF-Viewer, der ein PDF (das selbst ein PDF zeigt) mit demselben MD5 anzeigt](https://assets.kitploit.com/production/public/readmes/47471/4356d710fc4b60297ee05999be64f596198e9d4a02c826666818eb8ae117310f.png)

*Ein PDF-Viewer, der ein PDF (das selbst ein PDF zeigt) mit demselben MD5 anzeigt*


#### PDF - PNG

Ähnlich ist es möglich, zum Beispiel beliebige PDF- und PNG-Dateien ohne Einschränkungen auf beiden Seiten kollidieren zu lassen. Das ist sofortig, wiederverwendbar und generisch.

Beispiele: [Hello.pdf](https://github.com/corkami/collisions/blob/HEAD/examples/png-pdf.pdf) ⟷ [1x1.png](https://github.com/corkami/collisions/blob/HEAD/examples/png-pdf.png)


### PileUps (Multi-Kollision)

Kryptografische Kollisionen sind nicht auf zwei Dateien beschränkt!

Wie im Experiment [Nostradamus](https://www.win.tue.nl/hashclash/Nostradamus/) von 2008 demonstriert wurde,
ermöglicht das Verketten von Kollisionen, mehr als zwei Dateien kollidieren zu lassen.

Die ersten Kollisionen können identisch oder Chosen-Prefix sein, die nächsten müssen Chosen-Prefix sein.

Du kannst sie Multi-Kollisionen nennen, ich bevorzuge *Pileups* – es ist kürzer :)


#### PE - PNG - MP4 - PDF

Durch die Kombination allen zuvor erworbenen Wissens,
verwendete ich 3 Chosen-Prefix-Kollisionen, um 4 verschiedene Präfixe für verschiedene Dateitypen zu erzeugen:
Dokument (PDF), Video (MP4), ausführbare Datei (PE) und Bild (PNG).

![Diagramm eines PE/PNG/MP4/PDF-Pileups](https://assets.kitploit.com/production/public/readmes/47471/f7c45f284bad51f431a2993cf4797f679c85671c028cf1862f1c07604740360a.png)

*Diagramm eines PE/PNG/MP4/PDF-Pileups*

Dieses Skript ist generisch und sofortig:

![Diagramm eines PE/PNG/MP4/PDF-Pileups](https://assets.kitploit.com/production/public/readmes/47471/3ec7caeb459eab294c6b9876a8a82e136502c3d11c599804fd7925fc2d819276.png)

Beispiele: [commodore.pdf](https://github.com/corkami/collisions/blob/HEAD/examples/pileup.pdf) ⟷ [diagram.png](https://github.com/corkami/collisions/blob/HEAD/examples/pileup.png) ⟷ [kidmo.mp4](https://github.com/corkami/collisions/blob/HEAD/examples/pileup.mp4) ⟷ [sumatra18.exe](https://github.com/corkami/collisions/blob/HEAD/examples/pileup.exe)


Da du möglicherweise nur eine einzelne Datei verteilen kannst
und es unmöglich ist, die anderen Präfixwerte daraus zu erraten,
ist eine Lösung, alle Präfixe der Kollision in JavaScript-Code einzubetten
und diesen in deine PoCs einzufügen,
um deine Dateien in [HTML-Polyglotte](https://github.com/corkami/collisions/blob/HEAD/examples/polyglot.html) zu verwandeln und die zugehörigen kollidierenden Dateien einfach zu teilen.



Die [Ausgabe 19](https://github.com/angea/pocorgtfo#0x19) von ‚PoC or GTFO‘ ist ein solcher Pileup **und** Polyglott,
die ein 80-seitiges, mit PDFLaTeX erzeugtes Dokument, einen PDF-Viewer für Windows,
ein PNG-Diagramm und ein kurzes ‚Collision‘-MP4-Video von [KidMoGraph](https://www.kidmograph.com/) kombiniert,
mit einem HTML-Payload, um die anderen Dateien aus der PDF-Veröffentlichung zu erzeugen
(und auch ein ZIP-Archiv):



Dank an Rafał Hirsz für seine ständige Hilfe bei JavaScript.


## Anwendungsfälle

Verzichte besser ganz auf MD5, denn Datei-Inspektion ist einfach zu zeitaufwendig und zu riskant!


### Kollidiere sie alle!

Eine weitere Verwendung von sofortigen, wiederverwendbaren und generischen Kollisionen wäre, jede beliebige Datei eines bestimmten Typs – sagen wir PNG – hinter Dummy-Dateien (oder jedes Mal derselben Datei) zu verstecken – was eigentlich nur durch Anhängen an dasselbe Präfix nach Entfernen der Signatur geschieht – das könnte man sogar auf Bibliotheksebene tun!

Aus strenger Parsing-Sicht
zeigen alle deine Dateien denselben Inhalt,
und die bösartigen Bilder würden als Datei mit demselben MD5 wie zuvor gesammelt offenbart.

Nehmen wir zwei Dateien:

 ⟷


und lassen sie mit demselben PNG kollidieren.

Sie zeigen nun dasselbe Dummy-Bild und sind auf Dateiebene bis zum 2. Bild absolut identisch!

 ⟷


Ihre bösartige Nutzlast ist jeweils hinter einer Datei mit demselben MD5 versteckt.


### Belastende Dateien

Ein weiterer Anwendungsfall für Kollisionen ist es, etwas Belastendes in etwas Unschuldigem zu verstecken,
aber Wünschenswertem: Wenn das Einzige, was zum Sammeln von Beweisen dient, der Vergleich schwacher Hashes ist,
dann kannst du nicht leugnen, dass du die andere Datei nicht hast (die belastenden Inhalt zeigt, aber unschuldigen Inhalt verbirgt).

Software konzentriert sich typischerweise auf (schnelles) Parsen, nicht auf detaillierte Dateianalyse.



*Ein Bild, das verschiedene Vorschauen unter verschiedenen Tabs von EnCase Forensic zeigt*


## Fehlschläge

Nicht alle Formate können generische, wiederverwendbare Präfixe haben:
wenn keine Art von Datencontainer zwischen die Magic-Signatur
und die Standard-Header eingefügt werden kann, die kritisch und für jede Datei spezifisch sind,
dann sind generische Kollisionen nicht möglich.

Natürlich könnte man die alten Dateien immer noch in eine neue umwandeln,
und sogar Code verwenden, um zu zwei verschiedenen Payloads zu verzweigen,
aber das ist eher das Portieren von Payloads als das Kollidieren von Dateistrukturen.


### ELF



Der ELF-Header ist bei Offset 0 erforderlich und enthält kritische Informationen wie 32b/64b,
Endianness und ABI direkt von Anfang an,
daher ist es unmöglich, ein universelles Präfix und dann Kollisionsblöcke zu haben,
bevor kritische Parameter kommen, die für die Originaldatei spezifisch sind.


### Mach-O



Mach-O startet nicht einmal mit derselben Magic für 32b (`feedface`) und 64b (`feedfacf`).
Kurz danach folgen Anzahl und Größe der Befehle (wie Segmentdefinition, Symtab, Version, ...).

Wie bei ELF sind wiederverwendbare Kollisionen nicht möglich.


### Java Class



Direkt nach der Magic am Anfang befinden sich die Versionen (die problematisch sein können),
aber auch die Anzahl der Constant-Pool-Einträge, die für jede Datei sehr spezifisch ist,
also keine universellen Kollisionen für alle Dateien.

Viele Dateien haben jedoch weiterhin eine gemeinsame Version, und wir können den kürzesten Constant Pool auf die längste Anzahl auffüllen.
Füge zuerst ein *UTF8-Literal* ein, um Informationen auszurichten,
deklariere dann ein weiteres, dessen Länge durch eine UniColl missbraucht wird (die Länge wird auf 16 Bytes als Big-Endian gespeichert).

Dies erfordert jedoch eine Code-Manipulation, da alle Pool-Indizes verschoben werden.

Sofortige, wiederverwendbare MD5-Kollisionen von Java-Class-Dateien sollten möglich sein, erfordern aber Code-Analyse und -Modifikation.


### TAR

**TL;DR** Keine wiederverwendbare Kollision für TAR-Dateien, keine andere Strategie als Chosen-Prefix.



Tape-Archive sind eine Folge von aneinandergereihten Headern und Dateiinhalten, die alle auf 512 Bytes ausgerichtet sind.

Es gibt keine zentrale Struktur für die gesamte Datei. Also gibt es keinen globalen Header oder Kommentar irgendeiner Art, den man missbrauchen könnte.

Ein Trick wäre, eine Dummy-Datei variabler Länge zu starten, aber die Länge befindet sich immer am selben Offset, was nicht mit UniColl kompatibel ist. Das bedeutet, dass hier nur Chosen-Prefix-Kollisionen nützlich sind.


## Übersicht der Ausnutzungen

Format        | Generisch? | FastColl | UniColl | Shattered | HashClash / Shambles
--------      | -------- | :------: | :-----: | --------- | :-------:
PDF           | J        |          | x       |           | x
JPG           | J (1)    |          | x       | x (2)     | x
GZ            | J        |          | x       |           | x
PNG           | J/N (3)  |          | x       |           | x
MP4           | J (4)    |          | x       | x (5)     | x
PE            | J        |          |         |           | x
ZIP-basiert (6) | J      |          |         |           | x
              |          |          |         |           |
GIF           | N        | x        |         |           | x
ZIP           | N        |          | x (7)   |           | x
              |          |          |         |           |
ELF           | N        |          |         |           | x
TAR           | N        |          |         |           | x
Mach-O        | N        |          |         |           | x
Class         | N        |          |         |           | x

1. JPG hat einige Einschränkungen bei den Daten, die durch Manipulation der Scan-Kodierung bis zu einem gewissen Grad verbessert werden können.
2. PDF mit JPG ist die [ursprüngliche Implementierung](http://shattered.io) des Shattered-Angriffs, aber es ist nur ein reiner JPG-Trick in einem PDF-Dokument.
3. PNG: Safari/Preview verlangen, dass PNG ihren `IHDR`-Chunk im ersten Slot haben, vor jedem Kollisionsblock. Das verhindert ein generisches Präfix; in diesem Fall ist die Kollision auf bestimmte Abmessungen, Farbraum, BPP und Interlacing beschränkt.
4. Atom/Box-Formate wie MP4 funktionieren möglicherweise mit demselben Präfix für verschiedene Unterformate. Einige Unterformate wie JPEG2000 oder HEIF erfordern zusätzliches Grooming, aber die Exploit-Strategie ist dieselbe – nur ist die Kollision nicht zwischen Unterformaten möglich, sondern nur mit einem Präfixpaar für ein bestimmtes Unterformat.
5. Atom/Box ist Shattered-kompatibel bei Verwendung von 64-Bit-Längen.
6. Einige Zip-basierte Formate können generisch ausgenutzt werden.
7. Für bessere Kompatibilität benötigt ZIP zwei UniColl für ein vollständiges Archiv, und diese Kollisionen hängen vom Inhalt beider Dateien ab.


## Testdateien

[Hier](https://github.com/corkami/collisions/blob/HEAD/examples/free/README.md) sind freie (urheberrechtsfreie, PII-freie) kollidierende Testpaare.


# Erkennung

Es gibt verschiedene Möglichkeiten, Hash-Kollisionen in Dateien zu erkennen.

1. Zwei Dateien: Wenn du zwei oder mehr Dateien mit unterschiedlichem Inhalt und demselben Hash hast, vergleiche sie einfach!

Wenn du jedoch nur eine einzelne Datei hast, kann es schwierig sein zu erkennen, ob die Datei eine Hash-Kollision enthält.

2. Dateistruktur: Analysiere die Datei an Blockgrenzen. Wenn du Blöcke mit hoher Entropie und vielleicht identische Präfixe/Suffixe bemerkst, kannst du möglicherweise erkennen, welche Kollision verwendet wird, aber das ist sehr fehleranfällig. Bei einer Chosen-Prefix-Kollision ist es möglicherweise unmöglich, sie zu erkennen, da sich beide Dateien außer in den meisten Kollisionsblöcken größtenteils unterscheiden können.

3. Hash-Berechnung: Verwende eine Implementierung (in [C](https://github.com/cr-marcstevens/hashclash/tree/collisiondetection/src/collisiondetection) oder [Go](https://github.com/therealmik/detectcoll)) von Marc Stevens’ DetectColl (siehe sein [Counter-Cryptanalysis](https://marc-stevens.nl/research/papers/C13-S.pdf)-Papier). Es erfordert nur eine Datei, aber die Kollision muss in einem funktionsfähigen Zustand vorliegen (das genaue Präfix und die zugehörigen Kollisionsblöcke), und es ist langsam.

DetectColl liefert technische Informationen über die Kollision selbst und zeigt `*coll*` neben dem kollidierten Hash an.

## Beispiel

Mit dem Flame-Malware-Zertifikat:```
$ detectcoll flame.der
Found collision in block 11:
   dm: dm4=80000000 dm11=ffff8000 dm14=80000000
   ihv1=1ba33aac3a7f9ed70aec349b40390e85
   ihv2=9ba33aac3c7f60ee8cebf69bc2391085
*coll* c38a66643af816f8438b375b5f42ccbb flame.der
ba2499ba3dda9ef818f854b75a2bd1cd9f2b7bed flame.der

Sichere Hashes

Da Detectcoll Blöcke identifizieren kann, die für eine Hash-Kollision verwendet werden, kann es die Kollision durch sichere Hashes entschärfen: Wenn ein Kollisionsblock erkannt wird, verarbeitet es diesen erneut, um die Kollisionseigenschaft zu brechen. So kann DetectColl unterschiedliche Inhalte trotz der Kollisionen in der Datei über dieselbe Hash-Funktion unterscheiden.

Kurz gesagt:

Bei Dateien ohne Kollision entspricht ein sicherer Hash-Wert dem Standard-Hash-Wert.
Bei Dateien mit Kollision weicht der sichere Hash ab, unterscheidet sich aber auch bei unterschiedlichen Dateiinhalten trotz der Kollisionen.

Beispiel mit Wangs ursprünglicher Kollision von 2005:``` $ md5sum wang* 79054025255fb1a26e4bc422aef54eb4 *wang1.bin 79054025255fb1a26e4bc422aef54eb4 *wang2.bin

Sicheres MD5 bei diesen Dateien:```
$ detectcoll wang1.bin | grep coll
*coll* ff531291d102a41aa131e0e09f64ca60 wang1.bin

Der Eingabetext für dieses Chunk ist leer – es wurde kein Inhalt zum Übersetzen bereitgestellt.``` $ detectcoll wang2.bin | grep coll coll 6a8e7124724d5c819401afc202a4fbd0 wang2.bin

## Signaturen

Der Einfachheit halber können Sie die Detectcoll-Ausgabe mit diesem [Skript](https://github.com/corkami/collisions/blob/HEAD/scripts/logparse.py) parsen und sie leichter mit [bekannten Signaturen](https://github.com/corkami/collisions/blob/7f7876c431614f33f765bfc1cb62506b476a2eb0/scripts/logparse.py#L15-L24) abgleichen:``` shell
$ detectcoll_unsafe * | ./logparse.py
apop-1.bin
block: 2, collision: APop
cpc1.bin
block: 9, collision: HashClashCPC
fastcoll1.bin
block: 2, collision: FastColl
single-cpc1.bin
block: 1, collision: SingleCPC
single-ipc1.bin
block: 0, collision: SingleIPC
wang1.bin
block: 1, collision: FastColl
pileup.exe
block: 10, collision: HashClashCPC
block: 20, collision: HashClashCPC
04-unicoll-1.bin
block: 1, collision: Unicoll1
05-uc-n2-1.bin
block: 1, collision: Unicoll2
05-uc-n3-1.bin
block: 1, collision: Unicoll3
05-uc-n3-2.bin
block: 1, collision: Unicoll3
12-shattered1.bin
block: 3, collision: SHAttered/Shambles
block: 4, collision: SHAttered/Shambles
13-shambles1.bin
block: 9, collision: SHAttered/Shambles
13-shambles2.bin
block: 9, collision: SHAttered/Shambles
ca-rogue.der
block: 10, collision: HashClashCPC
flame.der
block: 11, collision: Flame

Mehrfachkollisionen

Ein kleiner Nachteil sicherer Hashes ist, dass sie die Erkennung mehrerer Kollisionen in derselben Datei verhindern, aber DetectColl kann Kollisionen mit 'standard'-Hashes weiterhin erkennen.

Beispiele mit PoCorGTFO 0x14 (ein NES+PDF-Hashquine mit einem alternativen Titelbild).

Sichere Hashes können nur eine Kollision finden:``` $ detectcoll_safe pocorgtfo14.pdf Found collision in block 135: dm: dm4=80000000 dm11=ffff8000 dm14=80000000 ihv1=73b615bd01d5e48032d3d1a549d0f956 ihv2=f3b615bd83d5e480b4d3d1a5cbd0f956 coll c4b085f9fa4b38669fa79d4c410538e9 pocorgtfo14.pdf eb5d0fb7607c1262236a5a7f591bb510ee9afbbc pocorgtfo14.pdf

Unsafe hashes findet alle davon:```
$ detectcoll_unsafe pocorgtfo14.pdf | grep Found | wc -l
609

Wenn du dir die letzten paar Kollisionen ansiehst:``` $ detectcoll_unsafe pocorgtfo14.pdf | tail | grep Found Found collision in block 34169: Found collision in block 34250: Found collision in block 34324: Found collision in block 34389: Found collision in block 34456: Found collision in block 34523: Found collision in block 34585: Found collision in block 34738:

Du kannst feststellen, dass die letzte nicht so nah an den vorherigen liegt:
das liegt daran, dass die vorherigen zur selben Bilddatei für die Hashquines gehören,
während die letzte für das alternative Cover ist.


# Referenzen

Paper (über die Ausnutzung von Dateiformaten):

- 2004
  - [MD5 To Be Considered Harmful Someday](https://eprint.iacr.org/2004/357.pdf) - Dan Kaminsky
  - [Practical Attacks on Digital Signatures Using MD5 Message Digest](https://eprint.iacr.org/2004/356.pdf) - Ondredj Mikle 
- 2005:
  - [A Note on Practical Value of Single Hash Collisions for Special File Formats](https://github.com/corkami/collisions/blob/HEAD/papers/Illies_NIST_05.pdf) - Max Gebhardt, Georg Illies, Werner Schindler
- 2014:
  - [Malicious Hashing: Eve’s Variant of SHA-1](https://malicioussha1.github.io/) - Ange Albertini, Jean-Philippe Aumasson, Maria Eichlseder, Florian Mendel, Martin Schläffer
- 2017:
  - [The first collision for full SHA-1](http://shattered.io) - Marc Stevens, Elie Bursztein, Pierre Karpman, Ange Albertini, Yarik Markov
  - [Postscript that shows its own MD5](https://archive.org/stream/pocorgtfo14#page/n45/mode/1up) von Gregor "Greg" Kopf
  - [A PDF That Shows Its Own MD5](https://archive.org/stream/pocorgtfo14#page/n49/mode/1up) von Mako
  - [This GIF shows its own MD5!](https://archive.org/stream/pocorgtfo14#page/n52/mode/1up) von Kristoffer "spq" Janke
  - [This PDF is an NES ROM that prints its own MD5 hash!](https://archive.org/stream/pocorgtfo14#page/n55/mode/1up) von Evan Sultanik, Evan Teran
- 2018:
  - [Easy SHA-1 Colliding PDFs with PDFLaTeX.](https://archive.org/stream/pocorgtfo18#page/n62/mode/1up) von Ange Albertini
- 2020:
  - [SHA-1 is a Shambles](https://eprint.iacr.org/2020/014.pdf) von Gaëtan Leurent, Thomas Peyrin

Präsentationen:
- 2017 Exploiting Hash Collisions bei Black Alps:
  - [Folien](https://speakerdeck.com/ange/exploiting-hash-collisions)
  
    [](https://speakerdeck.com/ange/exploiting-hash-collisions)
  
  - [Video](https://www.youtube.com/watch?v=Y-oJWEYKVLA)
  
    [![Exploiting hash collisions YouTube-Video](https://assets.kitploit.com/production/public/readmes/47471/c995bb115228391b655125ee5806530149829d3a62b8754485071f5db9512e67.jpg)](https://www.youtube.com/watch?v=Y-oJWEYKVLA)

- 2019 KILL MD5 bei Pass the Salt:
  - [Folien](https://speakerdeck.com/ange/kill-md5)

    [](https://speakerdeck.com/ange/kill-md5)
  - [Video](https://passthesalt.ubicast.tv/videos/kill-md5-demystifying-hash-collisions/)

    [![Kill MD5-Video](https://assets.kitploit.com/production/public/readmes/47471/4d7d0e2935f37e9ae363ad7bebe2abb3697978e7b3c1aa57851c54727b7ac49f.jpg)](https://passthesalt.ubicast.tv/videos/kill-md5-demystifying-hash-collisions/)


Workshop (CollTris):
  - [Folien](https://speakerdeck.com/ange/colltris)

    [](https://speakerdeck.com/ange/colltris)

  - [Video](https://www.youtube.com/watch?v=BcwrMnGVyBI)

    [](https://www.youtube.com/watch?v=BcwrMnGVyBI)

  - [Materialien](https://github.com/corkami/collisions/blob/HEAD/workshop/README.md)

  - Sitzungen
    - 2019/07/02 150p, Pass The Salt
    - 2019/07/24 199p, Google
    - 2019/08/19 208p, Google
    - 2019/10/23 222p, Hack.lu
    - 2019/11/07 225p, Black Alps
    - 2019/12/03 229p, Google


CTF-Aufgaben:
- [Prudentialv2](https://ctftime.org/task/3453), vom *Boston Key Party CTF 2017*.
- [HREFIN](https://ctftime.org/task/6965), vom *Google CTF 2018*.
- [Looking glass](https://ctftime.org/task/9271) vom *Dragon Sector Teaser CTF 2019*.

<!-- - [Not my digest](https://ctftime.org/task/4784) vom *Hack.lu CTF 2017*: nicht mit Kollisionen verwandt, aber von Marc selbst gelöst :p -->
Eine häufige Herausforderung bei solchen CTF-Aufgaben besteht darin, keinen allzu großen Vor- oder Nachteil zu schaffen, der auf der Rechenleistung basiert, über die die einzelnen Spieler verfügen.


# Danksagungen

All dies wurde dank [Marc Stevens](https://marc-stevens.nl/research/) möglich,
nicht nur wegen seiner kryptografischen Beiträge, sondern auch wegen seiner ständigen Hilfe und Anregungen!

Dank auch an Philippe Teuwen für sein umfangreiches Feedback zu Dateiformaten im Allgemeinen.


# Fazit

**Schluss mit MD5!**

Verwende MD5 nicht, sofern du nicht aktiv auf Fehlbildungen oder Kollisionsblöcke in Dateien prüfst!

Es ist kein kryptografischer Hash, sondern eine Spielzeugfunktion!

<!-- pandoc -s -f gfm -t html README.md -o README.html -->

collisions

Beliebteste

Hash-Kollisionen und deren Ausnutzung

FAQ (TL;DR)

Inhaltsverzeichnis

Einleitung

Status

Identisches Präfix

FastColl (MD5)

Shambles (SHA-1)

benutzerdefinierte Scans

Inkompatibilität

GIF

GZIP

LZ4 / Zstandard

Portable Executable

MP4 und andere

JPEG2000

PDF

JPG in PDF

ZIP

Zip-basierte Formate

Sichere Hashes

Mehrfachkollisionen