decalage2/collisionsHash collisions and their exploitations
TL;DR eine MD5-Kollision dieser beiden Bilder zu erzeugen ist jetzt(*) trivial und sofort möglich.
⟷
<a href=http://gunshowcomic.com/648>
Spiel nicht mit dem Feuer, verlass dich nicht auf MD5.
(*) Es ist seit vielen Jahren möglich, beliebige Dateipaare kollidieren zu lassen, aber es dauert jedes Mal mehrere Stunden, ohne Abkürzung.
Diese Seite bietet dateiformatspezifische Tricks und vorberechnete Kollisions-Präfixe, um Kollisionen sofort zu ermöglichen.
git clone. Skript ausführen. Fertig.
Von Ange Albertini und Marc Stevens.
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 auch gängige Dateiformate im Detail zu untersuchen, um festzustellen, wie sie mit gegenwärtigen oder zukünftigen Angriffen ausgenutzt werden können.
Tatsächlich kann derselbe Dateiformat-Trick bei mehreren Hashes verwendet werden (dieselben JPG-Tricks wurden für MD5, malicious SHA-1 und SHA1), solange die Kollisionen denselben Byte-Mustern folgen.
Dieses Dokument handelt nicht von neuen Angriffen (der neueste wurde 2012 dokumentiert), sondern von neuen Formen der Ausnutzung bestehender Angriffe.
Aktueller Status - Stand Dezember 2018 - der bekannten Angriffe:
eine Datei zu erhalten, die den Hash einer anderen Datei oder einen vorgegebenen Hash ergibt: unmöglich
zwei verschiedene Dateien mit demselben MD5 zu erhalten: sofort
zwei beliebige Dateien auf denselben MD5 zu bringen: einige Stunden (72 hours.core)
zwei beliebige Dateien bestimmter Dateiformate (PNG, JPG, PE...) auf denselben MD5 zu bringen: sofort
zwei verschiedene Dateien mit demselben SHA1 zu erhalten: 6500 years.core
(*) 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 & B denselben Hash haben, dann bleibt der Hash gleich, wenn man denselben Inhalt C an beide 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 von dem abhängt, was zuvor in der Datei stand. Diese Kollisionsblöcke sehen sehr zufällig aus, mit einigen geringfügigen Unterschieden (die einem bestimmten Muster für jeden Angriff folgen), und sie führen winzige Unterschiede ein, während sie nach diesen Blöcken schließlich denselben Hash-Wert ergeben.
Diese Unterschiede werden ausgenutzt, um gültige Dateien mit bestimmten Eigenschaften zu erzeugen.
Dateiformate arbeiten ebenfalls von oben nach unten, und die meisten arbeiten mit Byte-Chunks.
Einige 'Comment'-Chunks können eingefügt werden, um Datei-Chunks an Blockgrenzen auszurichten, um bestimmte Strukturen an die Unterschiede der Kollisionsblöcke anzupassen, um den Rest der 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 'Comment'-Chunks sind oft keine offiziellen echten Kommentare: Sie werden nur als Datencontainer verwendet, die vom Parser ignoriert werden (z. B. sind PNG-Chunks mit einer ID, die mit einem Kleinbuchstaben beginnt, ergänzend (ancillary), nicht kritisch).
Meistens wird ein Unterschied in den Kollisionsblöcken verwendet, um die Länge eines Comment-Chunks zu ändern, der typischerweise direkt vor den Daten dieses Chunks deklariert wird: In der Lücke zwischen der kürzeren und der längeren Version dieses Chunks wird ein weiterer Comment-Chunk deklariert, um über den Inhalt A einer Datei hinwegzuspringen. Nach diesem Dateiinhalt A wird einfach ein weiterer Dateiinhalt B angehängt.
Da Dateiformate normalerweise einen Terminator definieren, der die Parser danach stoppt, beendet A das Parsen, wodurch der angehängte Inhalt B ignoriert wird.
Normalerweise sind also mindestens zwei Kommentare erforderlich – oft drei:
Diese gemeinsamen Eigenschaften von Dateiformaten machen dies möglich – sie werden normalerweise nicht als Schwächen angesehen, können aber erkannt oder normalisiert werden:
| Präfix | = | Präfix |
|---|---|---|
| Kollision A | ≠ | Kollision B |
| Suffix | = | Suffix |
Beide Dateien sind fast identisch (ihr Inhalt hat nur wenige Bits Unterschiede)
Ausnutzung:
Bündle zwei Inhalte und dann entweder:
Zwei Dateien mit dieser Struktur:
zeigen entweder A oder B.
Finale Version im Jahr 2009.
.. .. .. .. .. .. .. .. .. .. .. .. .. .. .. ..
.. .. .. X. .. .. .. .. .. .. .. .. .. .. .. ..
.. .. .. .. .. .. .. .. .. .. .. .. .. X. .X ..
.. .. .. .. .. .. .. .. .. .. .. X. .. .. .. ..
Die Unterschiede befinden sich nicht nahe dem Anfang/Ende der Blöcke, daher ist es sehr schwer auszunutzen, da man kein nahegelegenes Byte kontrolliert. Eine mögliche Lösung besteht darin, die umgebenden Bytes zu brute-forcen – 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
Weitere Beispiele mit identischem Präfix: [1](https://github.com/decalage2/collisions/blob/HEAD/examples/fastcoll1.bin) ⟷ [2](https://github.com/decalage2/collisions/blob/HEAD/examples/fastcoll2.bin)
**Variante**: Es gibt eine [Ein-Block-MD5-Kollision](https://marc-stevens.nl/research/md5-1block-collision/), aber sie benötigt fünf Wochen Rechenzeit.
Hier ist eine [Aufzeichnung](https://github.com/decalage2/collisions/blob/HEAD/examples/fastcoll.svg) einer FastColl-Berechnung ohne Präfix
und [eine weitere](https://github.com/decalage2/collisions/blob/HEAD/examples/fastcoll-prefix.svg) mit Präfix.
### [UniColl](https://github.com/decalage2/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, einige Bytes in den Kollisionsblöcken zu kontrollieren,
vor und nach der ersten Differenz, was es zu einer Kollision mit identischem Präfix mit einigen kontrollierbaren Differenzen macht, fast wie eine Kollision mit gewähltem Präfix.
Das ist sehr praktisch, und noch besser: Die Differenz kann sehr vorhersehbar sein:
im Fall von `m2+= 2^8` (a.k.a. `N=1` / `m2 9` im HashClash-Skript [poc_no.sh](https://github.com/cr-marcstevens/hashclash/blob/master/scripts/poc_no.sh#L30)),
beträgt die Differenz +1 am 9. Byte, was es 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` wird durch `1` ersetzt, `a` durch `b`..
- Zeit: ein paar Minuten (abhängig davon, wie viele Bytes man kontrollieren möchte)
- Platz: zwei Blöcke
- Unterschiede: ```
.. .. .. .. DD .. .. .. ..
.. .. .. .. +1 .. .. .. ..
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 [Aufzeichnung](https://github.com/decalage2/collisions/blob/HEAD/examples/unicoll.svg) einer UniColl-Berechnung.
### [Shattered](http://shattered.io) (SHA1)
Dokumentiert im Jahr [2013](https://marc-stevens.nl/research/papers/EC13-S.pdf), berechnet im Jahr [2017](http://shattered.io).
- Zeit: 6500 CPU-Jahre und 110 GPU-Jahre
- Speicher: zwei Blöcke
- Unterschiede: ```
.. .. .. DD ?? ?? ?? ??
or
?? ?? ?? DD .. .. .. ..
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,
wiederverwendet das Bild direkt aus dem PDFLaTeX-Quelltext (siehe [Artikel 18:10](https://archive.org/stream/pocorgtfo18#page/n62/mode/1up)),
prüft aber auch den Wert der Präfixe über JavaScript in der HTML-Seite (die Datei ist ein Polyglott, ZIP HTML und PDF).
## Chosen-Prefix-Kollisionen
Sie ermöglichen es, beliebigen Inhalt 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 dauert die Berechnung.
Beispiel: [400 kHours für einen Block](https://www.win.tue.nl/hashclash/SingleBlock/). 72 hours.cores für neun Blöcke mit [HashClash](https://github.com/cr-marcstevens/hashclash).
Chosen-Prefix-Kollisionen sind allmächtig, aber sie können für ein einzelnes Dateipaar lange dauern.
### [HashClash](https://github.com/cr-marcstevens/hashclash) (MD5)
Finale Version in [2009](https://www.win.tue.nl/hashclash/ChosenPrefixCollisions/).
Beispiele: Lasst uns `yes` und `no` kollidieren. 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 ist eine sehr aufwendige Chosen-Prefix-Kollision, die 9 Blöcke verwendet.
Jeder Block hat 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
## Angriffszusammenfassung
Hash | Name | Datum | Dauer | Präfixtyp | Kontrolle nahe Diff
---- | --------- | ---- | -------- | ----------- | -----------------
MD5 | FastColl | 2009 | 2s | Identisch | keine
| UniColl | 2012 | 7-40min | Identisch | 4-10 Bytes
| HashClash | 2009 | 72h | Gewählt | n/a
| | | | |
SHA1 | Shattered | 2013 | 6500 Jahre | Identisch | Präfix & Suffix
| Shambles | 2020 | ? | Gewählt | n/a
# Ausnutzungen
Kollisionen mit identischem Präfix gelten normalerweise als (sehr) begrenzt, aber chosen-prefix ist zeitaufwändig.
Ein anderer Ansatz besteht darin, wiederverwendbare Präfixe zu erstellen – entweder über einen identical-prefix-Angriff wie UniColl – oder über chosen-prefix, um einige Einschränkungen zu überwinden – und dieses Präfixpaar dann in Kombination mit zwei Payloads wie bei einem klassischen identical-prefix-Angriff wiederzuverwenden.
Sobald das Präfixpaar berechnet wurde, wird die Kollision zweier Inhalte sofort möglich:
Es ist nur eine Frage der Anpassung der Dateidaten (gemäß den spezifischen Dateiformaten), sodass sie den Spezifikationen der Dateiformate und den vorab berechneten Präfixanforderungen entsprechen.
## Standardstrategie
Klassische Kollisionen von zwei gültigen Dateien mit demselben Dateityp.
### JPG
Theoretische Einschränkungen und Umgehungsmöglichkeiten:
- das *Application*-Segment sollte theoretisch direkt nach dem *Start of Image*-Marker stehen.
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 auf zwei Bytes gespeichert, daher ist die Menge, die er speichern kann, auf 65536 Bytes begrenzt (ungefähr die Größe eines 400x400-Fotos)
- anstatt über eine vollständige JPG-Datei zu springen, kann man die Datei in ihre Segmente aufteilen und zwischen den Segmenten Sprung-Trampoline einfügen
*Kommentare über jedem Bildsegment*
*wie Kommentar-Trampoline funktionieren*
- während der Großteil einer JPG-Struktur aus Segmenten besteht, die alle auf 65536 Bytes in der Größe begrenzt sind,
werden die eigentlichen komprimierten Daten im *Entropy Coded Segment* gespeichert, das sich nicht an seine Begrenzungen hä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 damit den Großteil der Dateigröße in einem Baseline-Bild (nicht progressiv) aus.
Um das gesamte Bild in 64-kb-Blöcke zu bekommen, besteht der einfache Weg darin, das Bild zunächst als progressiv zu speichern (was jede Software kann und das ECS typischerweise in bis zu sechs Scans aufteilt). Der fortgeschrittenere Weg ist die Verwendung von *JPEGTran* mit seinem 'Wizard'-Kommandozeilenparameter `--scans` und das Definieren eigener Scans.
Es gibt keine weiteren Einschränkungen außer den Scan-Segmenten,
daher ist eine MD5-Kollision von zwei beliebigen JPGs *sofortig* und benötigt keine chosen-prefix-Kollision, sondern nur UniColl.
Mit dem [Skript](https://github.com/decalage2/collisions/blob/HEAD/scripts/jpg.py):```
21:07:35.65>jpg.py Ange.jpg Marc.jpg
21:07:35.75>
Beispiele:
⟷
2 MD5-kollidierende JPGs
Hier ist ein Beispiel für eine JPEGTran-Scan-Definition, um ein 1944x2508 RGB-Bild in ein 100% JPG mit 20 Scans zu verwandeln, die alle in 64 KB 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, sind aber nicht erforderlich.
- die Bild-Metadaten (Abmessungen, Farbraum ...) werden im `IHDR`-Chunk gespeichert,
der sich theoretisch direkt nach der Signatur (d.h. vor jedem möglichen Kommentar) befinden sollte,
was bedeuten würde, dass wir Kollisionen nur für Bilder mit denselben Metadaten vorberechnen können.
Allerdings kann dieser Chunk tatsächlich nach einem Kommentarblock (in der großen Mehrheit der Reader, außer Apple-Readern) stehen, sodass wir die Kollisionsdaten vor dem Header platzieren können,
was es ermöglicht, jedes beliebige Paar von PNGs mit einer einzigen Vorberechnung kollidieren zu lassen.
Da ein PNG-Chunk eine Länge von vier Bytes hat, ist es nicht nötig, die Struktur einer der Dateien zu ändern: wir können in einem Schritt über ein ganzes Bild springen.
Wir können beliebig viele verworfene Chunks einfügen, sodass wir einen für die Ausrichtung hinzufügen können und dann einen, dessen Länge durch einen UniColl verändert wird, sodass die Länge `00` `75` und `01` `75` beträgt.
Eine MD5-Kollision zweier beliebiger PNG-Bilder ist also *sofort* möglich, ohne Voraussetzungen (keine Berechnung, nur einige kleine Dateiänderungen) und benötigt keine Chosen-Prefix-Kollision, sondern nur UniColl.
Mit dem [Skript](https://github.com/decalage2/collisions/blob/HEAD/scripts/png.py):```
19:27:04.79>png.py nintendo.png sega.png
19:27:04.87>
Beispiele:
⟷
2 MD5-kollidierende PNGs mit unterschiedlichen Eigenschaften
Hier ist eine Aufzeichnung des gesamten Vorgangs.
Die meisten Leser akzeptieren einwandfrei PNG-Dateien, die mit einem Chunk beginnen, der nicht IHDR ist.
Einige (wie Safari und Preview – gibt es andere?) tolerieren das jedoch nicht. In diesem Fall müssen der Bildheader 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 das berechnete Präfixpaar kann natürlich für jedes andere Dateipaar mit denselben Eigenschaften wiederverwendet werden.
Hier ist ein Skript, um ein beliebiges Paar solcher Dateien zur Kollision zu bringen; es startet bei Bedarf UniColl, um das Präfixpaar zu berechnen.
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,
und eine weitere, wenn das Präfix bereits berechnet wurde.
GIF ist knifflig:
Allerdings folgen die Kommentar-Chunks einer eigentümlichen Struktur: Es ist eine Kette von <length:1> <data:length>, bis eine Nulllänge definiert wird.
Dadurch wird jedes Nicht-Null-Byte zu einem gültigen 'Sprung nach vorn'. Das macht es für die Verwendung mit FastColl geeignet,
wie in PoC||GTFO 14:11 gezeigt.
Zumindest können wir also, selbst wenn wir kein generisches Präfix haben, jedes Paar von GIFs mit denselben Metadaten (Abmessungen, Palette) zur Kollision bringen, und wir brauchen nur eine Sekunde FastColl, um das Präfix zu berechnen.
Nun besteht das Problem darin, dass wir nicht über ein ganzes Bild wie bei PNG oder über eine große Struktur wie bei JPG springen können.
Ein möglicher Workaround besteht darin, die komprimierten Daten zu bearbeiten oder das Bild in winzige Bereiche aufzuteilen, 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:
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 aktuellen GIF-Einschränkungen für sofortige MD5-Kollisionen:
gifsicle --use-colormap webEine einfache Abkürzung, um unbewegte 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 ein Dateipaar zu erzeugen, das jeweils eines von ihnen anzeigt.
Beispiele:
⟷
2 MD5-kollidierende GIFs - Bilder von KidMoGraph
Hier ist eine Aufzeichnung des gesamten Vorgangs.
GZIP-Spezifikationen v4.3: RFC 1952 (1996).
1F 8B geprüft. Wenn es nicht mit der Signatur übereinstimmt, stoppt das Parsing. Das kann genutzt werden, um das Parsing zwischen zwei Payloads zwangsweise zu stoppen, erzeugt aber einige Warnungen, die Probleme verursachen könnten. Eine andere Strategie besteht darin, am Ende der Datei einen zusätzlichen leeren Member hinzuzufügen und das Parsing beider Payloads dort enden zu lassen - auf dem Member oder auf seinem Körper.filename und der file comment sind null-terminiert, während das Extra field eine 16-Bit-definierte Größe hat und daher missbraucht werden kann. Es besteht aus einem oder mehreren Unterfeldern mit einer ID und einer eigenen Unterlänge, aber Unterfelder werden nicht erzwungen - nur sehr wenige sind offiziell definiert.Daher ist ein leerer gzip-Member mit einem Extra-Feld ein perfekter parasitärer Wirt.
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 kommen sein komprimierter Körper, sein CRC32 und seine unkomprimierte Größe (nicht erzwungen). Daher bildet ein leerer Datenkörper mit seinem Null-CRC32 und seiner 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 anstelle der Summe aller Members. Daher zeigen unsere kollidierten Dateien, dass sie null-groß sind, 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 Dekomprimierung ist nicht möglich, da der unkomprimierte CRC32 berechnet werden muss.
Eine .tar.gz-Datei ist einfach das gzip-Archiv eines tar-Archivs. Es funktioniert problemlos mit gzipptem tar, anders als tar selbst.
Beispiele: collision1.tar.gz (Pacome) ⟷ collision2.tar.gz (Reg)
Das Portable Executable hat eine eigentümliche Struktur:
Die Strategie ist also:
DOS/Collisions/Header1/Header2-Struktur nebeneinander platziert werden. Man muss nur ein Delta auf die Offsets der beiden Sektionstabellen anwenden.Das bedeutet, dass es möglich ist, jedes beliebige Paar von PE-Executables sofort zur Kollision zu bringen. Selbst wenn sie unterschiedliche Subsysteme oder Architekturen verwenden.
Während Executable-Kollisionen über einen beliebigen Loader 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.
Der Container dieses Formats ist eine Sequenz 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 minimale normale Länge 8
(der Typ ist ein 4-ASCII-Zeichen-String).
Wenn die Länge null ist, nimmt das Atom den Rest der Datei ein - wie 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 diesem Fall werden sie Boxes genannt. Deshalb wird diese ansonsten unbenannte Struktur "atom/box" genannt.
Dieses "atom/box"-Format, das in MP4 verwendet wird, ist eigentlich eine Ableitung von Apple Quicktime und wird von vielen anderen Formaten verwendet (JP2, HEIF, F4V).
Der erste Atom-Typ ist normalerweise ftyp, wodurch das tatsächliche Dateiformat unterschieden werden kann.
Das Format ist recht permissiv:
Man muss nur free-Atoms verketten, die Länge eines Atoms mit UniColl missbrauchen und dann über die erste Payload springen.
Bei MP4-Dateien muss man nur die stco-Tabellen (Sample Table - Chunk Offsets) oder co64 (das 64-Bit-Äquivalent) anpassen, da es sich um absolute(!) Offsets handelt, die auf die mdat-Filmdaten zeigen - und sie werden tatsächlich erzwungen!
Das ergibt ein Skript, das sofort ein beliebiges Video zur Kollision bringt - und wie erwähnt könnte es auch mit anderen Formaten als MP4 funktionieren.
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 das abdecken, und es ist nicht so generisch, aber ansonsten ist es dieselbe Strategie - nur auf einen einzelnen Dateityp beschränkt.
JPEG2000-Dateien beginnen normalerweise mit der Atom/Box-Struktur wie bei MP4,
dann reicht das letzte Atom jp2c typischerweise bis zum Ende der Datei (Nulllänge),
und ab diesem Punkt folgt es der JFIF-Struktur, wie bei JPEG (beginnend mit FF 4F als Segment-Marker).
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 man JPEG2000-Dateien hingegen mit der Atom/Box-Struktur manipuliert, hat man diese Einschränkung nicht.
Wie bereits erwähnt, wenn man versucht, diese Struktur zur Kollision zu bringen und
weitere Einschränkungen bestehen - zum Beispiel, dass ein beginnendes free-Atom von manchen Formaten nicht toleriert wird -
dann kann man weitere UniColl-Präfixpaare berechnen, die für dieses Format spezifisch sind:
JPEG2000 scheint ein 'jP '-Atom zu erzwingen, bevor das übliche ftyp kommt,
aber das ist die einzige Einschränkung: Es muss nichts verschoben werden.
Das resultierende Skript ist also sogar einfacher!
Beispiele: collision1.jp2 ⟷ collision2.jp2
Über Shattered
Die Shattered-Ausnutzung war kein PDF-Trick, sondern ein JPG-Trick in einem PDF.
Sie ermöglichte lediglich, dass ein PDF ein JPG-komprimiertes Objekt enthält, 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 Kollisions-JPG einfach beschnitten und an verschiedenen Stellen angezeigt werden kann, z. B. in mehrseitigen Dokumenten.
Beispiele: das Shattered-Papier, modifiziert ⟷ das Shattered-Papier, Original
das Shattered-Papier, das ein kollidierendes JPG an zwei Stellen verwendet
PDF-Kollisionen mit MD5
Mit MD5 (und anderen Kollisionsmustern) können wir PDF-Kollisionen auf Dokumentebene durchführen, ohne Einschränkungen für eine 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.
Dieses (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:
XREF-Tabelle zu überspringen.Das Speichern zweier Dokumentbäume in derselben Datei ist also in Ordnung. Wir müssen nur dafür sorgen, dass das Root-Objekt auf das eine oder andere Root-Objekt der beiden Dokumente verweist.
Wir müssen also nur zwei Dokumente nehmen,
Objekte und Referenzen so umnummerieren, dass es keine Überlappungen gibt,
eine Kollision erzeugen, sodass die als Root-Objekt referenzierte Elementnummer bei gleichem Hash-Wert geändert werden kann,
was perfekt zu UniColl mit N=1 passt, und die XREF-Tabelle entsprechend anpassen.
Auf diese Weise können wir jedes beliebige PDF-Paar sicher kollidieren lassen, unabhängig von Seitenzahlen, Abmessungen, Bildern ...
Kommentare
PDF kann fremde Daten auf zwei Arten speichern:
\r und \n) sind.
Dies kann innerhalb eines Dictionary-Objekts verwendet werden, um beispielsweise eine Objektreferenz über UniColl zu modifizieren.
Daher ist dies ein gültiges PDF-Objekt, selbst wenn es binäre Kollisionsblöcke enthält - wiederhole einfach, bis keine Zeilenumbruchzeichen mehr vorhanden sind: ```
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
kollidierender Text
Der erste Fall ermöglicht es, die Schönheit von UniColl hervorzuheben, eine 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 zu erzeugen, mit alternativer Lesart!``` 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/decalage2/collisions/blob/HEAD/examples/poeMD5_A.pdf) ⟷ [poeMD5 B](https://github.com/decalage2/collisions/blob/HEAD/examples/poeMD5_B.pdf)
*Eine echte 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 du UniColl als Inline-Kommentar oder als Chosen-Prefix in einem Dummy-Stream-Objekt verwendest, die Strategie ist ähnlich:
Objektnummern umsortieren und dann das Root-Objekt auf verschiedene 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,
so dass sie verwendet werden kann, 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 keine unechten Schlüssel/Werte - außer man verlangt es - und behält sie in derselben Reihenfolge.
Daher sind 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 werden Kommentare in Wörterbüchern nicht beibehalten (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 zu teilen.
Um Platz für dieses Objekt zu schaffen, füge einfach vor den beiden Dokumenten ein Dummy-PDF ein.
Optional kann eine unechte 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/decalage2/collisions/blob/HEAD/scripts/pdf.py) dauert es [weniger als eine Sekunde](https://github.com/decalage2/collisions/blob/HEAD/examples/pdf.log), um die beiden öffentlichen PDF-Publikationen wie Spectre und Meltdown kollidieren zu lassen:
Beispiele: [spectre.pdf](https://github.com/decalage2/collisions/blob/HEAD/examples/collision1.pdf) ⟷ [meltdown.pdf](https://github.com/decalage2/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 von PDF-Dateien,
aber es ist auch möglich, es direkt aus TeX-Quellen zu tun
über [spezifische PDFTeX-Operatoren](http://texdoc.net/texmf-dist/doc/pdftex/manual/pdftex-a.pdf).
Du kannst Objekte direkt definieren - einschließlich Dummy-Schlüsseln und -Werten für Ausrichtungen - und leere Objekte definieren, um einige Objekt-Slots zu reservieren, indem du dies ganz am Anfang deiner TeX-Quellen einfügst:``` 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 - mit mutool zum Beispiel - falls nötig:
Mit PDFLaTeX sind reproduzierbare Builds über Distributionen hinweg schwer zu erreichen - du möchtest vielleicht sogar die Ausführungszeit einhaken, um bei Bedarf den exakten Hash zu erhalten.
Du würdest erwarten, dass JPG nur Bilder sind, aber in einem PDF und einigen PDF-Readern (keine Browser, wie Evince und Adobe Reader), kann es wie jedes andere eingebettete Objekt als Seiteninhalt verwendet werden, eingebettet in ein JPEG-Bild.
Um die JPEG-Daten verlustfrei zu speichern, speichere sie als Graustufen mit 100%, dann verwende entweder ein Bild mit einer einzelnen Zeile/Spalte, oder wiederhole die Datenzeile 8 Mal (da JPEG-Blöcke 8x8 sind), und deine Daten werden 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:
2 SHA-1-kollidierende PDFs mit als JPG gespeicherten Bilddaten
Es ist möglich, das kollidierende JPG zweimal zu referenzieren: als Seiteninhalt, verlustfrei, der sich selbst auch als verlustbehaftetes Bild zur Anzeige referenziert. Auch hier ist das anzuzeigende Bild graustufig, aber der Seiteninhalt kann über PDF-Operatoren einige Farben rendern.
Der obere Teil des Bildes zeigt den Seiteninhalt, 8 Mal wiederholt.
Beispiele für zwei SHA-1-kollidierende PDFs über JPEG, das als Seitendaten und als anzuzeigendes Bild verwendet wird:
Skulls & Crossbones ⟷ Golden Axe
2 SHA-1-kollidierende PDFs mit JPG als Bild und Seiteninhalt
TL;DR Es gibt keinen generischen wiederverwendbaren Kollisionsansatz für ZIP, aber für ZIP-basierte Formate. 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 Sequenz von Local File Header-Strukturen, eine pro archivierter Datei oder Verzeichnis),
dann ein Index (wiederum eine Sequenz von Central Directory),
dann eine einzelne Struktur, die auf diesen Index verweist (End Of Central Directory).
Die Reihenfolge dieser Schichten kann nicht verändert werden. Manche Parser benötigen nur die Struktur des Dateiinhalts, aber das ist keine korrekte Art zu parsen und kann ausgenutzt 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 ZIPs mit einem einzigen UniColl und 24 Bytes an festgelegtem Präfix kollidieren lassen.
Ein typisches End of Central Directory, das 22 Bytes groß 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 verwenden (das Präfix auf 16 Bits auffüllen) für UniColl und `N=2`, liegt der Unterschied im 4. Byte, wodurch die Magie `.P .K 05 06` zerstört wird, indem sie vorhersehbar in `.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..(
Trueman of the Forest ist ein interaktives textbasiertes Spiel.``` 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 eine Chosen-Prefix-Kollision:```
real 12m23.993s
user 112m24.072s
sys 2m0.194s
Ein Problem ist, dass einige Parser ZIP-Dateien immer noch verkehrt herum parsen, obwohl sie von unten nach oben geparst werden sollten:
Ein Weg, um sicherzustellen, dass beide Dateien korrekt geparst werden, ist, zwei UniColl-Blöcke zu verketten,
um jeweils das 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.
Beispiel: Hier ist ein Assembler-Quellcode, der die Struktur eines dualen ZIP beschreibt, das zwei verschiedene Archivdateien beherbergen kann.
Nach zwei Unicoll-Berechnungen ergeben sich die beiden kollidierenden Dateien: collision1.zip ⟷ collision2.zip
Auch wenn sich das Zip-Format selbst nicht so generisch wie Gzip ausnutzen lässt, können einige Formate, die auf Zip basieren, innerhalb von Zip-Archiven mit vordefinierter Struktur generisch ausgenutzt werden. Um die Zip-Kollision generisch zu machen, müssen einige Vorsichtsmaßnahmen getroffen werden.
Manche Formate bestehen aus mehreren Dateien, die in einem Zip-Archiv gespeichert sind, und verlassen sich auf eine Wurzeldatei mit einem festen Dateinamen, die auf andere Dateien im Archiv verweist. Viele von ihnen verwenden XML oder Text für die Wurzeldatei und speichern die anderen Dateien unverändert.
Idee : zwei Dateisätze im selben Archiv koexistieren lassen und auf jeweils einen der beiden Sätze verweisen. Eine generische Wurzeldatei kann 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 Quellen im selben Archiv ab - d. h. in verschiedenen Unterverzeichnissen.
Ändere die Wurzeldatei so, dass sie abwechselnd auf jeden der beiden Sätze verweist.
Da der Zeitstempel, die Länge und die CRC der Wurzeldatei sowohl im Local File Header - vor dem Dateiinhalt - als auch im Central Directory - nach dem Dateiinhalt - gespeichert sind, sollten sich diese Werte zwischen den beiden Versionen der Dateien nicht ändern.
Central Directory falsch ist, wird diese Kopie des Werts vom Parser möglicherweise ignoriert, 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 Wurzeldateien typischerweise in XML oder Text mit strengen Syntaxen vorliegen und dadurch ungültig würden.
CrcHack hilft sehr beim Fälschen von CRCs mit beliebigen Bits und ohne Brute-Force, wobei sichergestellt wird, dass die Ausgabedatei ASCII ist und dass die geänderten Bits weiterhin in einem Kommentar stehen.Das Verwenden des extra field einer zusätzlichen Dummy-Datei -- selbst einer leeren -- im Archiv nach der Wurzeldatei ist eine elegante Möglichkeit, Hashclash-Kollisionsblöcke zu speichern: Auf diese Weise behält das Zip-Archiv eine Standardstruktur bei und lässt sich danach sogar mit Standardwerkzeugen einfach manipulieren.
Extra Fields haben keine CRC32, und ihre 16-Bit-Länge wird zuvor in den Headern deklariert. Sie haben ihr eigenes internes Format ID:2 Size:2 Data, das aber normalerweise ignoriert wird, und sind sowohl im Local File Header als auch im Central Directory enthalten, 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
Indem man also die Inhalte der Root-Datei vorab definiert und ASCII-CRC32s fälscht, lässt sich eine generische, wiederverwendbare Hashclash-Kollision für ein bestimmtes ZIP-basiertes Format berechnen.
### Zusammenfassung der Anforderungen
- zwei oder mehr Präfixe
- ein oder mehrere Dateitypen (Polyglots funktionieren problemlos)
- eine XML-Root-Datei mit festem Dateinamen, fester Dateilänge und CRC: Diese Informationen sind zweimal vorhanden, vor und nach den Kollisionsblöcken
- Die Inhalte sind beliebiges XML
- Padding ist möglich, sogar über einen XML-Kommentar, um die gleiche Länge zu erreichen.
- Die CRC kann (über CrcHack) für jeden Inhalt gesetzt werden.
- Beide Sätze von Dateien koexistieren im Suffix, wahrscheinlich in verschiedenen Verzeichnissen. Einige Tools 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/decalage2/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/decalage2/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/decalage2/collisions/blob/HEAD/scripts/extendzip.py), um diese Wurzelpaare mit einem gemeinsamen Suffix zu kombinieren.
Einige Kollisions-PoCs:
- Office Open XML: Excel ([1](https://github.com/decalage2/collisions/blob/HEAD/examples/free/md5-1.xls) - [2](https://github.com/decalage2/collisions/blob/HEAD/examples/free/md5-2.xls)), Powerpoint ([1](https://github.com/decalage2/collisions/blob/HEAD/examples/free/md5-1.pptx) - [2](https://github.com/decalage2/collisions/blob/HEAD/examples/free/md5-2.pptx)), Word ([1](https://github.com/decalage2/collisions/blob/HEAD/examples/free/md5-1.docx) - [2](https://github.com/decalage2/collisions/blob/HEAD/examples/free/md5-2.docx)).
- Open Container Format: Epub ([1](https://github.com/decalage2/collisions/blob/HEAD/examples/collision-1.epub) - [2](https://github.com/decalage2/collisions/blob/HEAD/examples/collision-2.epub)).
- Open Packaging Conventions: 3MF ([1](https://github.com/decalage2/collisions/blob/HEAD/examples/collision-1.3mf) - [2](https://github.com/decalage2/collisions/blob/HEAD/examples/collision-2.3mf)), XPS ([1](https://github.com/decalage2/collisions/blob/HEAD/examples/collision-1.xps) - [2](https://github.com/decalage2/collisions/blob/HEAD/examples/collision-2.xps)).
Einige Formate mit mehreren Dateien auf ZIP-Basis lassen sich nicht generisch ausnutzen:
- Quake PK3: ein ZIP aus Dateien ohne spezifisches Wurzelelement.
- 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!
## 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 aneinanderzureihen
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 das durch zwei Dateitypen in derselben Datei zu erreichen.
### Gültigkeit
Eine andere Strategie wäre, den Dateityp zu beseitigen, um die Scananerkennung als beschädigte Datei zu umgehen.
Es reicht, die magische Signatur zu überschreiben.
Wenn man beide Dateien (gültig oder ungültig) mit einem Format anhängt,
das nicht bei Offset 0 beginnen muss (Archiv, wie ZIP/RAR/...), würde ein anderer Dateityp sichtbar.
Dies ermöglicht Polyglot-Kollisionen ohne eine Chosen-Prefix-Kollision:
1. UniColl verwenden, um eine magische Signatur zu aktivieren oder zu deaktivieren, zum Beispiel bei einer PNG:
2. ein ZIP-Archiv anhängen
Obwohl beide Dateien technisch gesehen gültige ZIPs sind, sehen die meisten Parser den ersten gefundenen Dateityp, und da sie bei Offset 0 zu scannen beginnen, sehen sie einen anderen Dateityp.
Beispiele:
⟷ [ungültig](https://github.com/decalage2/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. `holiday.jpg` senden
2. auf die Whitelist setzen lassen
3. `evil.exe` senden, das dieselbe MD5 hat.
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 polycoll*
*PE/PNG polycoll*
#### PE - JPG
Da ein PE-Header normalerweise kleiner als 0x500 Bytes ist, passt er perfekt in einen JPG-Kommentar:
1. mit DOS/JPG-Headern beginnen
2. Der JPEG-Kommentar springt über den PE-Header
3. Das vollständige JPG-Bild einfügen
4. Die gesamten PE-Spezifikationen einfügen
Auch hier ist die Kollision [sofort](https://github.com/decalage2/collisions/blob/HEAD/scripts/jpgpe.py)
Beispiele: [fastcoll.exe](https://github.com/decalage2/collisions/blob/HEAD/examples/jpg-pe.exe) ⟷ [Marc.jpg](https://github.com/decalage2/collisions/blob/HEAD/examples/jpg-pe.jpg)
#### PDF - PE
Das Zusammenführen einer PDF mit einer Dummy-Datei mit `mutool` ist eine gute generische Methode, um Objekte neu anzuordnen
und dann die ersten beiden Objekte verwerfbar zu machen (Dummy-Seite und -Inhalt),
was perfekt für ein hostendes `stream`-Objekt unbekannter Länge als `1 0` geeignet ist,
dessen Länge später (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,
also muss sie in der PDF wieder eingefügt werden, anstelle des Werts,
aber die meisten Referenzen `2 0 R` sind kleiner als hartkodierte Längen.
Glücklicherweise kann dies behoben werden, ohne Objekt-Offsets zu verändern,
also muss die XREF nicht gepatcht werden.
Hier ist ein [Skript](https://github.com/decalage2/collisions/blob/HEAD/scripts/pdfpe.py), um zum Beispiel sofort einen PDF-Viewer ([Sumatra](https://www.sumatrapdfreader.org/free-pdf-reader.html) ist leichtgewichtig und eigenständig) und ein PDF-Dokument kollidieren zu lassen:
Beispiele: [Poster.pdf](https://github.com/decalage2/collisions/blob/HEAD/examples/pepdf.pdf) ⟷ [Sumatra.exe](https://github.com/decalage2/collisions/blob/HEAD/examples/pepdf.exe)
*ein PDF-Viewer, der eine PDF (die selbst eine PDF zeigt) mit derselben 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 sofort einsetzbar, wiederverwendbar und generisch.
Beispiele: [Hello.pdf](https://github.com/decalage2/collisions/blob/HEAD/examples/png-pdf.pdf) ⟷ [1x1.png](https://github.com/decalage2/collisions/blob/HEAD/examples/png-pdf.png)
### PileUps (Multi-Kollision)
Kryptografische Kollisionen sind nicht auf zwei Dateien beschränkt!
Wie im [Nostradamus](https://www.win.tue.nl/hashclash/Nostradamus/) Experiment von 2008 gezeigt,
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 des gesamten zuvor erworbenen Wissens
habe ich 3 Chosen-Prefix-Kollisionen verwendet, um 4 verschiedene Präfixe für verschiedene Dateitypen zu erstellen:
Dokument (PDF), Video (MP4), ausführbare Datei (PE) und Bild (PNG).
*Diagramm eines PE/PNG/MP4/PDF-Pileups*
Dieses Skript ist generisch und sofort einsetzbar:
Beispiele: [commodore.pdf](https://github.com/decalage2/collisions/blob/HEAD/examples/pileup.pdf) ⟷ [diagram.png](https://github.com/decalage2/collisions/blob/HEAD/examples/pileup.png) ⟷ [kidmo.mp4](https://github.com/decalage2/collisions/blob/HEAD/examples/pileup.mp4) ⟷ [sumatra18.exe](https://github.com/decalage2/collisions/blob/HEAD/examples/pileup.exe)
Da du möglicherweise nur eine einzelne Datei weitergeben kannst
und es unmöglich ist, die anderen Präfixwerte daraus zu erraten,
besteht eine Lösung darin, alle Präfixe der Kollision in JavaScript-Code einzubetten
und sie in deine PoCs einzufügen,
wodurch deine Dateien zu [HTML-Polyglotten](https://github.com/decalage2/collisions/blob/HEAD/examples/polyglot.html) werden, um 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** Polyglot,
der ein 80-seitiges Dokument, erzeugt mit PDFLaTeX, einen PDF-Viewer für Windows,
ein PNG-Diagramm und ein kurzes 'Kollisions'-MP4-Video von [KidMoGraph](https://www.kidmograph.com/)
mit einem HTML-Payload kombiniert, 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 gänzlich auf MD5, denn Datei-Inspektion ist einfach zu zeitaufwändig und zu riskant!
### Kollidiere sie alle!
Eine weitere Verwendung von sofortigen, wiederverwendbaren und generischen Kollisionen wäre, jede 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 dem Entfernen der Signatur geschieht – das könnte man sogar auf Bibliotheksebene tun!
Aus strenger Parsing-Perspektive zeigen alle deine Dateien denselben Inhalt,
und die bösartigen Bilder würden als eine Datei mit derselben MD5 wie zuvor gesammelt offenbart.
Nehmen wir zwei Dateien:
⟷
und kollidieren sie mit derselben PNG.
Sie zeigen nun dasselbe Dummy-Bild und sind auf Dateiebene absolut identisch bis zum 2. Bild!
⟷
Ihr Schadcode ist jeweils hinter einer Datei mit derselben MD5 versteckt.
### Belastende Dateien
Ein weiterer Anwendungsfall für Kollisionen ist es, etwas Belastendes in etwas Harmlosem, aber Wünschenswertem zu verstecken: Wenn das Einzige, was zur Beweissammlung dient, der Vergleich schwacher Hashes ist, dann kannst du nicht leugnen, dass du die andere Datei nicht hast (die belastenden Inhalt zeigt, aber harmlosen 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 Präfixe haben, die wiederverwendet werden können:
wenn keine Art von Datencontainer zwischen der magischen Signatur
und den Standard-Headern 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 trotzdem 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 der Dateistruktur.
### ELF
Der ELF-Header wird bei Offset 0 benötigt und enthält von Anfang an kritische Informationen wie 32b/64b,
Endianness und ABI,
daher ist es unmöglich, ein universelles Präfix und dann Kollisionsblöcke
vor kritischen Parametern zu haben, die für die Originaldatei spezifisch sind.
### Mach-O
Mach-O beginnt nicht einmal mit derselben magischen Zahl für 32b (`feedface`) und 64b (`feedfacf`).
Kurz darauf folgen Anzahl und Größe der Kommandos (wie Segmentdefinition, Symtab, Version, ...).
Wie bei ELF sind wiederverwendbare Kollisionen nicht möglich.
### Java Class
Direkt nach der magischen Zahl befinden sich die Versionen (was problematisch sein kann),
aber auch die Anzahl der Constant-Pool-Einträge, die für jede Datei ziemlich 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.
Zuerst ein *UTF8-Literal* einfügen, um Informationen auszurichten,
dann ein weiteres deklarieren, dessen Länge durch eine UniColl missbraucht wird (die Länge wird als 16 Bytes Big Endian gespeichert).
Dies erfordert jedoch 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 Archives sind eine Sequenz aneinandergereihter Header und Dateiinhalte, die alle auf 512 Bytes ausgerichtet sind.
Es gibt keine zentrale Struktur für die gesamte Datei. Also keinen globalen Header oder Kommentar irgendeiner Art, den man missbrauchen könnte.
Ein Trick wäre, eine Dummy-Datei variabler Länge zu beginnen, aber die Länge steht immer am selben Offset, was nicht mit UniColl kompatibel ist, was bedeutet, dass hier nur Chosen-Prefix-Kollisionen nützlich sind.
## Übersicht der Ausnutzungen
Format | Generisch? | FastColl | UniColl | Shattered | HashClash / Shambles
-------- | -------- | :------: | :-----: | --------- | :-------:
PDF | Y | | x | | x
JPG | Y (1) | | x | x (2) | x
GZ | Y | | x | | x
PNG | Y/N (3) | | x | | x
MP4 | Y (4) | | x | x (5) | x
PE | Y | | | | x
ZIP-basiert (6) | Y | | | | 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 bis zu einem gewissen Grad durch Manipulation der Scan-Kodierung 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 verlangt, dass PNGs 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ätzliche Aufbereitung, aber die Exploit-Strategie ist dieselbe – nur dass die Kollision nicht zwischen Unterformaten möglich ist, 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 UniColls für ein vollständiges Archiv, und diese Kollisionen hängen vom Inhalt beider Dateien ab.
## Testdateien
[Hier](https://github.com/decalage2/collisions/blob/HEAD/examples/free/README.md) sind freie (urheberrechtsfreie, PII-freie) Test-Kollisionspaare.
# Referenzen
Fachartikel:
- 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/decalage2/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 at 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)
[](https://www.youtube.com/watch?v=Y-oJWEYKVLA)
- 2019 KILL MD5 at 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/)
[](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/decalage2/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 ist es, keinen zu großen Vor- oder Nachteil zu geben, der auf der Rechenleistung basiert, auf die jeder Spieler Zugriff hat.
# Danksagungen
All dies war dank [Marc Stevens](https://marc-stevens.nl/research/) möglich,
nicht nur für seine kryptografischen Beiträge, sondern auch für seine ständige Hilfe und Anregungen!
Dank auch an Philippe Teuwen für sein umfangreiches Feedback zu Dateiformaten im Allgemeinen.
# Fazit
**Tötet MD5!**
Wenn du nicht aktiv nach Fehlbildungen oder Kollisionsblöcken in Dateien suchst, verwende MD5 nicht!
Es ist kein kryptografischer Hash, es ist eine Spielzeugfunktion!
| Präfix | = | Präfix |
|---|
| Kollision A | ≠ | Kollision B |
| A | = | |
| = | B |