corkami/collisionsHash collisions and exploitations
Par Ange Albertini et Marc Stevens.
Q : Est-il possible de faire en sorte qu'un fichier obtienne un MD2/MD4/MD5/MD6/SHA1/SHA2/SHA3 arbitraire, ou le même hachage qu'un autre fichier ?
R : Non.
Q : Peut-on créer 2 fichiers différents avec le même hachage ?
R : Avec MD5, en quelques secondes sur un ordinateur standard. Avec SHA1, c'est possible mais pas pratique pour les utilisateurs finaux (Complexité : 2^61.2 Prix : 11 k$).
Q : Peut-on faire en sorte que 2 fichiers différents obtiennent le même hachage en ajoutant des données ?
R : Avec MD5, en quelques heures sur un ordinateur standard. Avec SHA1, c'est possible mais pas pratique pour les utilisateurs finaux (Complexité : 2^63.4 Prix : 45 k$).
Q : Les 2 fichiers resteront-ils valides ?
R : En général, oui, car la plupart des formats de fichiers tolèrent l'ajout de données. En revanche, les signatures de fichiers seront probablement cassées.
Q : Peut-on créer 2 fichiers différents avec des contenus arbitraires et le même hachage ?
R : Oui, cela peut être instantané en s'appuyant sur des structures de fichiers spéciales :
Q : Pour quels formats puis-je obtenir instantanément une paire de fichiers en collision MD5 ?
R : JPG, PNG, GIF, GZIP, Portable Executable, MP4, JPEG2000, PDF, DOCX/PPTX/XSLX, EPUB, 3MF, XPS. Il suffit d'exécuter le script spécifique.
Q : Qu'en est-il pour SHA1 ?
R : Pour SHA1, JPG dans un PDF est calculé et implémenté.
Q : Qu'en est-il des formats déjà pris en charge pour MD5 (JPG, PNG...), mais pour SHA1 à la place ?
R : Ils sont très probablement pris en charge avec SHA1 aussi, mais leurs collisions n'ont pas été calculées.
Q : Les calculs sont-ils plus rapides pour des contenus similaires (mais différents) ?
R : Non. La moindre petite différence exige un calcul complet.
Q : Quels formats n'ont pas ce raccourci ?
R : ELF, Mach-O, Java Class, TAR, ZIP (entre autres...)
Q : Les collisions classiques (en quelques heures) sont-elles toujours possibles avec ces formats ?
R : Oui, tant qu'une quantité quelconque de données ajoutées est tolérée (c.-à-d. probablement pas ZIP ou Class).
Q : Fournissez-vous des exemples de collisions ?
R : Oui.
L'objectif est d'explorer en profondeur les attaques existantes - et de montrer au passage à quel point MD5 est faible (collisions instantanées de n'importe quel JPG, PNG, PDF, MP4, PE...) - et aussi d'explorer en détail les formats de fichiers courants pour déterminer comment ils peuvent être exploités avec des attaques présentes ou futures.
En effet, la même astuce de format de fichier peut être utilisée sur plusieurs hachages (les mêmes astuces JPG ont été utilisées pour MD5, malicious SHA-1 et SHA1), tant que les collisions suivent les mêmes motifs d'octets.
Ce document ne traite pas de nouvelles attaques (la plus récente a été documentée en 2012), mais de nouvelles formes d'exploitation d'attaques existantes.
État actuel des attaques connues :
faire en sorte qu'un fichier obtienne le hachage d'un autre fichier ou un hachage donné : impossible
obtenir deux fichiers différents avec le même MD5 : instantané
faire en sorte que deux fichiers arbitraires obtiennent le même MD5 : quelques heures (72 heures.core)
faire en sorte que deux fichiers arbitraires de formats de fichiers spécifiques (PNG, JPG, PE...) obtiennent le même MD5 : instantané
obtenir deux fichiers différents avec le même SHA1 : 6500 ans.core
(*) exemple avec crypt - merci Sven !```
import crypt crypt.crypt("5dUD&66", "br") 'brokenOz4KxMc' crypt.crypt("O!>',%$", "br") 'brokenOz4KxMc'
# Attaques
MD5 et SHA1 fonctionnent avec des blocs de 64 octets.
Si deux contenus A et B ont le même hachage, alors ajouter le même contenu C aux deux conservera le même hachage.``` text
hash(A) = hash(B) -> hash(A + C) = hash(B + C)
Les collisions fonctionnent en insérant, à une limite de bloc, un certain nombre de blocs de collision calculés qui dépend de ce qui précède dans le fichier. Ces blocs de collision ont une apparence très aléatoire avec quelques différences mineures (qui suivent un motif spécifique pour chaque attaque) et ils introduiront de petites différences tout en aboutissant finalement à des hashs de même valeur après ces blocs.
Ces différences sont exploitées pour fabriquer des fichiers valides avec des propriétés spécifiques.
Les formats de fichiers fonctionnent également de haut en bas, et la plupart d’entre eux fonctionnent par chunks au niveau octet.
Certains chunks de « commentaire » peuvent être insérés pour aligner les chunks du fichier sur les limites de blocs, pour aligner des structures spécifiques sur les différences des blocs de collision, pour masquer le reste du caractère aléatoire des blocs de collision aux analyseurs du fichier, et pour masquer un contenu par ailleurs valide à l’analyseur (afin qu’il voie un autre contenu).
Ces chunks de « commentaire » ne sont souvent pas de véritables commentaires au sens officiel : ils sont simplement utilisés comme conteneurs de données ignorés par l’analyseur (par exemple, les chunks PNG avec un ID commençant par une minuscule sont accessoires, non critiques).
La plupart du temps, une différence dans les blocs de collision est utilisée pour modifier la longueur d’un chunk de commentaire,
qui est généralement déclaré juste avant les données de ce chunk :
dans l’écart entre la version plus courte et la version plus longue de ce chunk,
un autre chunk de commentaire est déclaré pour sauter par-dessus le contenu A d’un fichier.
Après ce contenu de fichier A, il suffit d’ajouter un autre contenu de fichier B.
Comme les formats de fichiers définissent généralement un terminateur qui fait s’arrêter les analyseurs après lui,
A terminera l’analyse, ce qui fera que le contenu ajouté B sera ignoré.
Donc, en général, au moins deux commentaires sont nécessaires - souvent trois :
Ces propriétés communes des formats de fichiers rendent cela possible - elles ne sont généralement pas perçues comme des faiblesses, mais elles peuvent être détectées ou normalisées :
| Préfixe | = | Préfixe |
|---|---|---|
| Collision A | ≠ | Collision B |
| Suffixe | = | Suffixe |
Les deux fichiers sont presque identiques (leurs contenus ne présentent que quelques bits de différence)
Exploitation :
Regroupez deux contenus, puis soit :
Deux fichiers avec cette structure :
afficheront soit A, soit B.
Version finale en 2009.
.. .. .. .. .. .. .. .. .. .. .. .. .. .. .. ..
.. .. .. X. .. .. .. .. .. .. .. .. .. .. .. ..
.. .. .. .. .. .. .. .. .. .. .. .. .. X. .X ..
.. .. .. .. .. .. .. .. .. .. .. .. X. .. .. .. ..
Les différences ne sont pas proches du début/fin des blocs, il est donc très difficile de les exploiter car vous ne contrôlez aucun octet voisin. Une solution potentielle consiste à forcer par force brute les octets environnants - cf PoCGTFO 14:10.
Exemples :
Avec un préfixe vide :``` 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
Autres exemples, avec un préfixe identique : [1](https://github.com/corkami/collisions/blob/HEAD/examples/fastcoll1.bin) ⟷ [2](https://github.com/corkami/collisions/blob/HEAD/examples/fastcoll2.bin)
**Variante** : il existe une [collision MD5 à un seul bloc](https://marc-stevens.nl/research/md5-1block-collision/) mais elle nécessite cinq semaines de calcul.
Voici un [enregistrement](https://github.com/corkami/collisions/blob/HEAD/examples/fastcoll.svg) d'un calcul FastColl sans préfixe
et [un autre](https://github.com/corkami/collisions/blob/HEAD/examples/fastcoll-prefix.svg) avec un préfixe.
### [UniColl](https://github.com/corkami/collisions/blob/HEAD/unicoll.md) (MD5)
Documentée en [2012](https://www.cwi.nl/system/files/PhD-Thesis-Marc-Stevens-Attacks-on-Hash-Functions-and-Applications.pdf#page=199), implémentée en [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) vous permet de contrôler quelques octets dans les blocs de collision,
avant et après la première différence, ce qui en fait une collision à préfixe identique avec quelques différences contrôlables, presque comme une collision à préfixe choisi.
C'est très pratique, et mieux encore, la différence peut être très prévisible :
dans le cas de `m2+= 2^8` (alias `N=1` / `m2 9` dans le script HashClash [poc_no.sh](https://github.com/cr-marcstevens/hashclash/blob/master/scripts/poc_no.sh#L30)),
la différence est +1 sur le 9ème octet, ce qui la rend très exploitable,
car vous pouvez même concevoir la collision dans votre tête :
le 9ème caractère de cette phrase sera remplacé par le suivant : `0` remplacé par `1`, `a` remplacé par `b`..
- temps : quelques minutes (dépend du nombre d'octets que vous voulez contrôler )
- espace : deux blocs
- différences : ```
.. .. .. .. DD .. .. .. ..
.. .. .. .. +1 .. .. .. ..
Exemples avec N=1 et 20 octets de texte défini dans les blocs de collision :```
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 offre moins de contrôle qu'une véritable collision de préfixe choisi, mais elle est beaucoup plus rapide, surtout qu'elle ne nécessite que deux blocs.
Voici un [enregistrement](https://github.com/corkami/collisions/blob/HEAD/examples/unicoll.svg) d'un calcul UniColl.
### [Shattered](http://shattered.io) (SHA1)
Documentée en [2013](https://marc-stevens.nl/research/papers/EC13-S.pdf), calculée en [2017](http://shattered.io).
- temps: 6500 ans.CPU et 110 ans.GPU
- espace: deux blocs
- différences: ```
.. .. .. DD ?? ?? ?? ??
or
?? ?? ?? DD .. .. .. ..
La différence entre les blocs de collision de chaque côté est ce masque Xor :``` 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
Exemples : [PoC||GTFO 0x18](https://github.com/angea/pocorgtfo#0x18) utilise les préfixes SHA1 calculés,
réutilise l'image directement depuis la source PDFLaTeX (voir [article 18:10](https://archive.org/stream/pocorgtfo18#page/n62/mode/1up)),
mais vérifie aussi la valeur des préfixes via JavaScript dans la page HTML (le fichier est polyglotte, ZIP HTML et PDF).
## Collisions à préfixe choisi
Elles permettent de collisionner n'importe quel contenu.
| 𝓐 | ≠ | 𝔅 |
| :----: |:-:| :----: |
| Collision *A* | ≠ | Collision *B* |
1. prenez deux préfixes arbitraires
2. complétez le plus court pour qu'il soit aussi long que le plus long. les deux sont complétés jusqu'au bloc suivant - moins 12 octets
- ces 12 octets de données aléatoires seront ajoutés des deux côtés pour randomiser la recherche d'anniversaire
3. X blocs de quasi-collision seront calculés et ajoutés.
Moins il y a de blocs, plus le calcul est long.
Ex : [400 kheures pour un bloc](https://www.win.tue.nl/hashclash/SingleBlock/). 72 heures-cœurs pour neuf blocs avec [HashClash](https://github.com/cr-marcstevens/hashclash).
Les collisions à préfixe choisi sont toutes-puissantes, mais elles peuvent prendre beaucoup de temps, ne serait-ce que pour une paire de fichiers.
### [HashClash](https://github.com/cr-marcstevens/hashclash) (MD5)
Version finale en [2009](https://www.win.tue.nl/hashclash/ChosenPrefixCollisions/).
Exemples : collisionnons `yes` et `no`. Cela a pris trois heures sur 24 cœurs.```
'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
Voici un journal de toute l'opération.
Shambles est une collision de préfixe choisi très coûteuse qui utilise 9 blocs.
Chaque bloc a le même motif xor que 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
Mais même si Shattered est beaucoup plus facile à exploiter que FastColl,
les contraintes des différences dans les blocs de collision sont sans importance
puisque Shambles est une collision à préfixe choisi.
## Résumé des attaques
Hash | Nom | Date | Durée | Type de préfixe | Contrôle près de la diff
---- | --------- | ---- | -------- | --------------- | ------------------------
MD5 | FastColl | 2009 | 2 s | Identique | aucun
| UniColl | 2012 | 7-40 min | Identique | 4-10 octets
| HashClash | 2009 | 72 h | Choisi | n/a
| | | | |
SHA1 | Shattered | 2013 | 6500 ans | Identique | préfixe et suffixe
| Shambles | 2020 | ? | Choisi | n/a
# Exploitations
Les collisions à préfixe identique sont généralement considérées comme (très) limitées, mais le préfixe choisi prend du temps.
Une autre approche consiste à fabriquer des préfixes réutilisables via une attaque à préfixe identique comme UniColl - ou à préfixe choisi pour surmonter certaines limitations - mais à réutiliser cette paire de préfixes en combinaison avec deux charges utiles comme dans une attaque classique à préfixe identique.
Une fois la paire de préfixes calculée, la collision entre deux contenus devient instantanée :
il suffit de manipuler les données du fichier (selon les formats de fichiers spécifiques) pour qu'elles correspondent aux spécifications du format et aux exigences des préfixes précalculés.
## Stratégie standard
Collisions classiques de deux fichiers valides du même type de fichier.
### JPG
Limitations théoriques et contournements :
- le segment *Application* devrait en théorie se trouver juste après le marqueur *Start of Image*.
En pratique, ce n'est pas nécessaire, donc notre collision peut être générique : la seule limitation est la taille de la plus petite image.
- la longueur d'un commentaire est stockée sur deux octets, donc la quantité qu'il peut stocker est limitée à 65536 octets (environ la taille d'une photo 400x400)
- plutôt que de sauter par-dessus un fichier JPG complet, on peut diviser ce fichier en ses segments, et ajouter des trampolines de saut entre les segments
*commentaires sur chaque segment d'image*
*comment fonctionnent les trampolines de commentaires*
- alors que la majeure partie d'une structure JPG est composée de segments tous limités à 65536 octets,
les données compressées réelles sont stockées dans le *Entropy Coded Segment* qui ne respecte pas ces limitations :
sa taille est inconnue à l'avance et dépasse cette limite.
Elle augmente avec la taille de l'image, constituant l'essentiel de la taille du fichier dans une image de base (non progressive).
Pour faire tenir toute l'image dans des morceaux de 64 ko, le moyen simple est d'abord d'essayer d'enregistrer l'image en progressif (ce que n'importe quel logiciel peut faire, et divise l'ECS en généralement jusqu'à six scans). Le moyen plus avancé est d'utiliser *JPEGTran* avec son paramètre de ligne de commande 'wizard' `--scans` et de définir des scans personnalisés.
Il n'y a pas d'autre restriction en dehors des segments de scans,
donc une collision MD5 de deux JPG arbitraires est *instantanée*, et ne nécessite pas de collision à préfixe choisi, seulement UniColl.
Avec le [script](https://github.com/corkami/collisions/blob/HEAD/scripts/jpg.py) :```
21:07:35.65>jpg.py Ange.jpg Marc.jpg
21:07:35.75>
Exemples :
⟷
2 JPGs en collision MD5
Voici un exemple de définition des scans JPEGTran pour transformer une image RGB 1944x2508 en un JPG à 100 % avec 20 scans tenant tous dans 64 Ko.``` // : -, , ;
// 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;
Résultat :
*une image RGB 1944x2508 en JPG à 100 % avec 20 scans*
### PNG
Limitations théoriques et solutions de contournement :
- PNG utilise CRC32 à la fin de ses blocs, mais en pratique ils sont ignorés. Ils peuvent être corrects, mais ce n'est pas requis.
- les métadonnées de l'image (dimensions, espace colorimétrique...) sont stockées dans le bloc `IHDR`,
qui devrait en théorie se trouver juste après la signature (c'est-à-dire avant tout commentaire éventuel),
ce qui signifierait que nous ne pouvons précalculer que des collisions d'images ayant les mêmes métadonnées.
Cependant, ce bloc peut en réalité se trouver après un bloc de commentaire (dans la grande majorité des lecteurs, à l'exception de ceux d'Apple), donc nous pouvons placer les données de collision avant l'en-tête,
ce qui permet de faire entrer en collision n'importe quelle paire de PNG avec un seul précalcul.
Comme un bloc PNG a une longueur sur quatre octets, il n'est pas nécessaire de modifier la structure de l'un ou l'autre fichier : nous pouvons sauter par-dessus une image entière en une seule fois.
Nous pouvons insérer autant de blocs ignorés que nous voulons, donc nous pouvons en ajouter un pour l'alignement, puis un dont la longueur sera modifiée par une UniColl. ainsi la longueur sera `00` `75` et `01` `75`.
Ainsi, une collision MD5 de deux images PNG quelconques est *instantanée*, sans aucun prérequis (aucun calcul, juste quelques modifications mineures de fichiers), et ne nécessite aucune collision de préfixe choisi, juste UniColl.
Avec le [script](https://github.com/corkami/collisions/blob/HEAD/scripts/png.py) :```
19:27:04.79>png.py nintendo.png sega.png
19:27:04.87>
Exemples :
⟷
2 PNG en collision MD5 avec des propriétés différentes
Voici un enregistrement de toute l'opération.
La plupart des lecteurs acceptent sans problème les fichiers PNG qui commencent par un bloc qui n'est pas IHDR.
Cependant, certains (comme Safari et Aperçu - d'autres ?) ne le tolèrent pas. Dans ce cas, l'en-tête de l'image et ses propriétés (dimensions, espace colorimétrique) doivent être placés en premier, avant tout bloc de collision.
Dans ce cas, les deux fichiers en collision doivent avoir les mêmes propriétés. Encore une fois, UniColl suffit, et bien sûr, la paire de préfixes calculée peut être réutilisée pour toute autre paire de fichiers ayant les mêmes propriétés
Voici un script pour faire entrer en collision n'importe quelle paire de tels fichiers, qui lance UniColl si nécessaire pour calculer la paire de préfixes.
Exemples :
⟷
⟷
2 paires de PNG en collision MD5 avec des propriétés identiques pour une compatibilité maximale
Voici un enregistrement de toute l'opération lorsqu'UniColl est invoqué,
et un autre lorsque le préfixe a déjà été calculé.
Le GIF est délicat :
Cependant, les blocs de commentaires suivent une structure particulière : c'est une chaîne de <length:1> <data:length> jusqu'à ce qu'une longueur nulle soit définie.
Ainsi, tout octet non nul devient un « saut en avant » valide. Ce qui le rend approprié pour être utilisé avec FastColl,
comme illustré dans PoC||GTFO 14:11.
Donc au moins, même si nous ne pouvons pas avoir un préfixe générique, nous pouvons faire entrer en collision n'importe quelle paire de GIF ayant les mêmes métadonnées (dimensions, palette) et nous n'avons besoin que d'une seconde de FastColl pour calculer son préfixe.
Le problème est que nous ne pouvons pas sauter par-dessus une image entière comme pour PNG ou par-dessus une grande structure comme pour JPG.
Une solution possible est de manipuler les données compressées ou de diviser l'image en minuscules zones comme dans le cas du hashquine GIF, mais ce n'est pas optimal.
Une autre idée qui fonctionne génériquement est que les données d'image sont également stockées à l'aide de cette structure de séquence length data :
donc si nous prenons deux GIF sans animation, nous devons simplement :
Avec une configuration mineure (seulement quelques centaines d'octets de surcharge), nous pouvons glisser sur n'importe quelle image GIF et contourner la limitation de 256 octets. Cette idée a été suggérée par Marc, et elle est brillante !
Donc en fin de compte, les limitations actuelles du GIF pour les collisions MD5 instantanées sont :
gifsicle --use-colormap webUn raccourci facile pour normaliser des images GIF fixes est d'en faire des images d'animation de la même image, puis nous pouvons utiliser un script pour réutiliser ou calculer des blocs FastColl afin de créer une paire de fichiers qui affiche chacun d'eux.
Exemples :
⟷
2 GIF en collision MD5 - images par KidMoGraph
Voici un enregistrement de toute l'opération.
Spécifications GZIP v4.3 : RFC 1952 (1996).
1F 8B. Si la signature ne correspond pas, l'analyse s'arrêtera, ce qui peut être utilisé pour arrêter de force l'analyse entre deux charges utiles, mais déclenchera des avertissements qui pourraient poser problème. Une autre stratégie consiste à ajouter un membre vide supplémentaire à la fin du fichier et à faire en sorte que l'analyse des deux charges utiles se termine là - sur le membre ou sur son corps.filename et le file comment facultatifs sont terminés par un octet nul, tandis que le Extra field est défini par une taille de 16 bits, donc exploitable. Il est composé d'un ou plusieurs sous-champs, avec un ID et sa propre sous-longueur, mais les sous-champs ne sont pas obligatoires - très peu sont officiellement définis.Par conséquent, un membre gzip vide avec un champ supplémentaire est un hôte parasite parfait.
Si le fichier supérieur est trop grand pour tenir dans un champ supplémentaire, son flux non compressé peut être divisé en fichiers plus petits jusqu'à ce qu'ils tiennent tous dans des champs supplémentaires.
Après l'en-tête d'un membre viennent son corps compressé, son CRC32 et sa taille non compressée (non obligatoire). Par conséquent, un corps de données vide avec son CRC32 et sa taille nuls constitue un postwrap générique, qui peut même être partagé par différents en-têtes de membres.
Diverses implémentations se fient à la taille non compressée du dernier membre plutôt qu'à la somme de tous les membres. Ainsi, nos fichiers en collision sembleront avoir une taille nulle, car ces fichiers se terminent par un membre vide utilisé comme trampoline.
Voici un script pour générer des collisions MD5 instantanées de deux fichiers GZip. Il passe la plupart de son temps à décompresser et recompresser les données si les fichiers d'entrée sont volumineux - les préfixes de collision sont pré-calculés. Diviser les membres sans décompresser n'est pas possible car le CRC32 non compressé doit être calculé.
Un .tar.gz n'est que l'archive gzip d'une archive tar. Cela fonctionnera bien avec un tar compressé par gzip, contrairement à tar lui-même.
Exemples : collision1.tar.gz (Pacome) ⟷ collision2.tar.gz (Reg)
LZ4 et Zstandard sont 2 formats de compression différents, avec une structure globale similaire :
ils sont composés de trames, chacune commençant par une signature magique spécifique : 0xFD2FB528 pour les trames Zstandard, 0x184D2204 pour les trames Lz4.
Ils partagent également les mêmes trames TLV « sautables », commençant par 4 octets de magics dans la plage 0x184D2A50 - 0x184D2A5F, puis la Longueur des données utilisateur (4 octets, little-endian), puis les Données utilisateur elles-mêmes.
Ces trames sont entièrement facultatives, de n'importe quelle longueur, et répétables. Les fichiers peuvent commencer par ces trames. Ces trames peuvent donc être enchaînées pour créer un préfixe de collision générique parfait, sur 2 formats.
Voici un script pour générer des collisions MD5 instantanées de deux fichiers Zstd/Lz4. Comme pour Gzip, 2 archives différentes seront visibles de l'extérieur quel que soit le contenu : par exemple, un .cpio.zst.
Exemples :
Le Portable Executable a une structure particulière :
La stratégie est donc :
DOS/Collisions/Header1/Header2. Il suffit d'appliquer un delta aux offsets des deux tables de sections.Cela signifie qu'il est possible de faire entrer en collision instantanément n'importe quelle paire d'exécutables PE, même s'ils utilisent des sous-systèmes ou des architectures différents.
Bien que les collisions d'exécutables soient généralement triviales via n'importe quel chargeur, ce type d'exploitation est ici transparent : le code est identique et chargé à la même adresse.
Exemples : tweakPNG.exe (GUI) ⟷ fastcoll.exe (CLI)
Voici un script pour générer des collisions MD5 instantanées d'exécutables Windows.
Le conteneur de ce format est une séquence de blocs Length Type Value appelés atomes.
La longueur est un entier 32 bits big-endian et couvre elle-même, le type et la valeur, donc la longueur normale minimale est de 8
(le type est une chaîne de 4 caractères ASCII).
Si la longueur est nulle, l'atome prend le reste du fichier - comme les atomes jp2c dans les fichiers JP2.
Si elle vaut 1, alors le Type est suivi d'une longueur 64 bits, transformant l'atome en Type Length Value, ce qui le rend compatible avec d'autres collisions comme Shattered.
Certains atomes contiennent d'autres atomes : dans ce cas, ils sont appelés boîtes. C'est pourquoi cette structure autrement sans nom est appelée « atom/box ».
Ce format « atom/box » utilisé dans MP4 est en réalité un dérivé d'Apple Quicktime, et est utilisé par de nombreux autres formats (JP2, HEIF, F4V).
Le premier type d'atome est généralement ftyp, ce qui permet de différencier le format de fichier réel.
Le format est assez permissif :
il suffit d'enchaîner des atomes free, d'abuser de la longueur de l'un d'eux avec UniColl, puis de sauter par-dessus la première charge utile.
Pour les fichiers MP4, la seule chose à ajouter est d'ajuster les tables stco (Sample Table - Chunk Offsets) ou co64 (l'équivalent 64 bits), car ce sont des offsets absolus (!) pointant vers les données vidéo mdat - et ils sont réellement appliqués !
Cela donne un script qui fait entrer en collision instantanément n'importe quelle vidéo - et comme mentionné, il peut fonctionner sur d'autres formats que MP4.
Exemples (vidéos par KidMoGraph) :
longueurs 32b (standard) collision1.mp4 ⟷ collision2.mp4
⟷
longueurs 64b collisionl1.mp4 ⟷ collisionl2.mp4
⟷
Notez que certains lecteurs (OS X, Safari, FireFox) n'autorisent pas un fichier qui commence par un atome qui n'est pas ftyp.
Dans ce cas, le préfixe doit couvrir cela, et il n'est pas si générique, mais à part cela, c'est la même stratégie - seulement limitée à un seul type de fichier.
Les fichiers JPEG2000 commencent généralement par la structure Atom/Box comme MP4,
puis le dernier atome jp2c s'étend typiquement jusqu'à la fin du fichier (longueur nulle),
puis à partir de ce point, ils suivent la structure JFIF, comme JPEG (commençant par FF 4F comme marqueur de segment).
La forme purement JFIF est également tolérée, auquel cas la collision est comme pour JPEG : compatible Shattered, mais avec des commentaires limités à 64 Ko.
En revanche, si vous manipulez des fichiers JPEG2000 avec l'Atom/Box, vous n'avez pas cette limitation.
Comme mentionné précédemment, si vous essayez de faire entrer en collision cette structure et
s'il y a plus de restrictions - par exemple, commencer par un atome free n'est pas toléré par certains formats -
vous pouvez alors calculer d'autres paires de préfixes UniColl spécifiques à ce format :
JPEG2000 semble imposer un atome 'jP ' en premier avant le ftyp habituel,
mais à part cela, c'est la seule restriction : il n'y a pas besoin de déplacer quoi que ce soit.
Le script résultant est donc encore plus simple !
Exemples : collision1.jp2 ⟷ collision2.jp2
à propos de Shattered
L'exploitation de Shattered n'était pas une astuce PDF, mais une astuce JPG dans un PDF.
Elle permettait seulement à un PDF de contenir un objet compressé JPG qui pouvait avoir deux contenus différents. Les deux PDF devaient être totalement identiques par ailleurs.
Notez que les documents peuvent être tout à fait normaux et peuvent simplement rogner le JPG en collision et l'afficher à différents endroits, comme dans des documents multipages.
Exemples : le document Shattered, modifié ⟷ le document Shattered, original
le document Shattered utilisant un JPG en collision à deux endroits
Collisions PDF avec MD5
Avec MD5 (et d'autres schémas de collision), nous pouvons réaliser des collisions PDF au niveau du document, sans aucune restriction sur l'un ou l'autre fichier !
Le PDF a une structure très différente des autres formats de fichiers. Il utilise des numéros d'objets et des références pour définir une arborescence. L'ensemble du document dépend de l'élément Root.
Ce PDF (valide)``` 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>>
est équivalent à :``` 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>>
Astuces :
XREF.Ainsi, stocker deux arborescences de documents dans le même fichier est acceptable. Il suffit de faire pointer l'objet racine vers l'objet racine de l'un ou l'autre des deux documents.
Il suffit donc de prendre deux documents,
de renuméroter les objets et les références afin qu'il n'y ait aucun chevauchement,
de concevoir une collision afin que le numéro d'élément référencé comme objet racine puisse être modifié tout en conservant la même valeur de hachage,
ce qui correspond parfaitement à UniColl avec N=1, et d'ajuster la table XREF en conséquence.
De cette façon, nous pouvons faire entrer en collision en toute sécurité n'importe quelle paire de PDF, quels que soient les numéros de page, les dimensions, les images...
commentaires
Un PDF peut stocker des données étrangères de deux manières :
\r et \n).
Cela peut être utilisé à l'intérieur d'un objet dictionnaire, pour modifier par exemple une référence d'objet, via UniColl.
C'est donc un objet PDF valide même s'il contient des blocs de collision binaires - il suffit de réessayer jusqu'à ce que vous n'ayez plus de caractères de saut de ligne : ```
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
texte en collision
Le premier cas permet de mettre en évidence la beauté d'UniColl, une collision où les différences sont prévisibles, vous pouvez donc écrire de la poésie sur des données en collision - merci Jurph !
Plutôt que de modifier la structure du document et de tromper les analyseurs, nous allons simplement utiliser des blocs de collision directement pour produire du texte, avec une lecture alternative !``` 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. ^ ^
Examples: [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)
*Une véritable création artistique cryptographique :) *
(Note : j'ai merdé avec la compatibilité Adobe, mais c'est de ma faute, pas celle d'UniColl)
**structure de collision de documents**
Que vous utilisiez UniColl comme commentaire en ligne ou comme préfixe choisi dans un objet de flux factice, la stratégie est similaire :
réorganisez les numéros d'objets, puis faites pointer l'objet Root vers différents objets ; ainsi, contrairement à Shattered, cela permet une collision instantanée de toute paire arbitraire de PDF, au niveau du document.
Une astuce utile est que la sortie de [`mutool clean`](https://mupdf.com/docs/manual-mutool-clean.html) est prévisible de manière fiable,
elle peut donc être utilisée pour normaliser les PDF en entrée et réparer votre PDF fusionné tout en conservant les parties importantes du fichier non modifiées.
MuTool ne supprime pas les clés/valeurs invalides - sauf si on le lui demande, et les conserve dans le même ordre,
donc utiliser de fausses entrées de dictionnaire comme `/MD5_is /REALLY_dead_now__` est parfait pour aligner les choses de manière prévisible sans avoir besoin d'un autre type de commentaires.
Cependant, il ne conserve pas les commentaires dans les dictionnaires (donc pas d'astuce de commentaire en ligne)
Un moyen simple d'effectuer l'opération de réorganisation des objets sans prise de tête consiste simplement à fusionner les deux fichiers PDF
via `mutool merge` puis à diviser l'objet `/Pages` en deux.
Pour faire de la place pour cet objet, il suffit de fusionner un PDF factice devant les deux documents.
En option, créez une fausse référence vers le tableau pendant
pour empêcher le ramasse-miettes de supprimer le deuxième ensemble de pages.
**Exemple** :
avec ce [script](https://github.com/corkami/collisions/blob/HEAD/scripts/pdf.py),
il faut [moins d'une seconde](https://github.com/corkami/collisions/blob/HEAD/examples/pdf.log) pour faire entrer en collision les deux articles PDF publics comme Spectre et Meltdown :
Examples: [spectre.pdf](https://github.com/corkami/collisions/blob/HEAD/examples/collision1.pdf) ⟷ [meltdown.pdf](https://github.com/corkami/collisions/blob/HEAD/examples/collision2.pdf)
Extension possible : chaîner des blocs UniColl pour également conserver les paires des divers [objets non critiques](https://www.adobe.com/content/dam/acom/en/devnet/pdf/pdfs/PDF32000_2008.pdf#page=81)
qui peuvent être référencés dans l'objet Root - tels que `Outlines`, `Names`, `AcroForm` et les actions supplémentaires (`AA`) - dans les fichiers source d'origine.
**en PDFLaTeX**
Les techniques précédentes fonctionnent avec une simple paire de fichiers PDF,
mais il est également possible de le faire directement à partir des sources TeX
via [des opérateurs PDFTeX spécifiques](http://texdoc.net/texmf-dist/doc/pdftex/manual/pdftex-a.pdf).
Vous pouvez définir des objets directement - y compris des clés et valeurs factices pour les alignements - et définir des objets vides pour réserver des emplacements d'objets en incluant ceci au tout début de vos sources TeX :``` 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
N'oubliez pas de normaliser la sortie PDFLaTeX - avec mutool par exemple - si nécessaire :
PDFLaTeX est difficile à rendre reproductible d'une distribution à l'autre - vous voudrez peut-être même accrocher l'heure d'exécution pour obtenir le hash exact si nécessaire.
On pourrait s'attendre à ce que les JPG ne soient que des images, mais dans un PDF et certains lecteurs PDF (hors navigateurs, comme Evince et Adobe Reader), il peut être utilisé comme contenu de page, tout comme n'importe quel autre objet intégré, c'est-à-dire incorporé dans une image JPEG.
Pour stocker les données JPEG sans perte, stockez-les en niveaux de gris à 100 %, puis utilisez soit une image d'une seule ligne/colonne, soit répétez la ligne de données 8 fois (car les blocs JPEG sont en 8x8), et vos données sont stockées sans perte et référencées par les pages PDF.
Exemples de deux PDF en collision SHA-1 via des données de page JPEG (une image en niveaux de gris rendant des couleurs) comme contenu de page vectoriel :
2 PDF en collision SHA-1 avec données image stockées en JPG
Il est possible de référencer le JPG en collision deux fois : comme contenu de page, sans perte, qui se réfère également à lui-même en tant qu'image avec perte à afficher. Encore une fois, l'image à afficher est en niveaux de gris, mais le contenu de la page peut rendre certaines couleurs via les opérateurs PDF.
Le haut de l'image montre le contenu de la page répété 8 fois.
Exemples de deux PDF en collision SHA-1 via JPEG utilisé comme données de page et image à afficher :
Skulls & Crossbones ⟷ Golden Axe
2 PDF en collision SHA-1 avec JPG utilisé comme image et contenu de page
TL;DR Il n'existe pas de collision générique réutilisable pour ZIP, mais il y en a pour les formats basés sur ZIP. Il devrait être possible de faire entrer en collision deux fichiers en 2h.core (36 fois plus vite que chosen-prefix)
Les archives ZIP sont un sandwich de 3 couches (au moins).
D'abord vient le contenu des fichiers (séquence de structures Local File Header, une par fichier ou répertoire archivé),
puis un index (là encore, une séquence de Central Directory),
puis une structure unique qui pointe vers cet index (End Of Central Directory).
L'ordre de ces couches ne peut pas être modifié. Certains parseurs n'ont besoin que de la structure du contenu du fichier, mais ce n'est pas une façon correcte d'analyser et cela peut être abusé.
En raison de cet ordre imposé, il n'existe aucun préfixe générique qui puisse aider pour une collision quelconque.
approche non générique
Une autre approche pourrait être de simplement fusionner les deux archives, avec leurs couches fusionnées, et d'utiliser UniColl - mais avec N=2, ce qui introduit une différence sur le 4e octet - pour tuer la signature magique du End of Central Directory.
Cela signifie que l'on pourrait faire entrer en collision deux ZIP arbitraires avec un seul UniColl et 24 octets de préfixe défini.
Un End of Central Directory typique, qui fait 22 octets si le commentaire est vide :``` 00: 504b 0506 0000 0000 0000 0000 0000 0000 PK.............. 10: 0000 0000 0000 ......
Si nous utilisons ceci comme préfixe (compléter le préfixe à 16 bits) pour UniColl et `N=2`, la différence se situe au 4ème octet, détruisant la valeur magique `.P .K 05 06` en changeant cet octet de manière prévisible en `.P .K 05 86`.```
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..(
[No content provided after "INPUT:". Please paste the Markdown chunk to translate.]``` 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..(
Ce n'est pas du tout générique, mais beaucoup plus rapide qu'une collision de préfixe choisi:```
real 12m23.993s
user 112m24.072s
sys 2m0.194s
Un problème est que certains analyseurs analysent encore les fichiers ZIP à l’envers alors qu’ils devraient être analysés de bas en haut :
une façon de s’assurer que les deux fichiers sont correctement analysés est d’enchaîner deux blocs UniColl,
pour activer/désactiver chaque End of Central Directory.
Pour empêcher les analyseurs ZIP de se plaindre de l’espace inutilisé,
on peut abuser des Extra Fields,
des commentaires de fichier dans Central Directory et des commentaires d’archive dans End of Central Directory.
Exemple : voici une source d’assembly qui décrit la structure d’un double ZIP, pouvant héberger deux fichiers d’archive différents.
Après deux calculs Unicoll, on obtient les deux fichiers en collision : collision1.zip ⟷ collision2.zip
Même si le format Zip lui-même ne peut pas être exploité génériquement comme Gzip, certains formats reposant sur Zip peuvent être exploités génériquement dans des archives Zip avec une structure prédéfinie. Certaines précautions doivent être prises pour rendre la collision Zip générique.
Certains formats sont composés de plusieurs fichiers stockés dans une archive Zip, et reposent sur un fichier racine avec un nom fixe qui pointe vers d’autres fichiers de l’archive. Beaucoup d’entre eux utilisent du XML ou du texte pour le fichier racine, et stockent les autres fichiers tels quels.
Idée : faire coexister 2 ensembles de fichiers dans la même archive, et pointer vers l’un ou l’autre ensemble de fichiers. Une racine générique peut être stockée en premier, au début du fichier, mais les blocs de collision sont stockés hors du contenu du fichier, dans l’archive (car les collisions ayant une entropie très élevée, il est impossible d’exploiter des fichiers XML ou uniquement ASCII avec des collisions).
Étapes :
Placer 2 ensembles de fichiers de 2 origines dans la même archive - c.-à-d. dans des sous-répertoires différents.
Modifier le fichier racine pour pointer alternativement vers chaque ensemble.
Étant donné que l’horodatage, la longueur et le CRC du fichier racine sont stockés à la fois dans le Local File Header - avant le contenu du fichier - et dans le Central Directory - après le contenu du fichier - ces valeurs ne devraient pas changer entre les deux versions des fichiers.
Central Directory, cette copie de la valeur pourrait être ignorée par l’analyseur, mais forger un CRC32 avec une valeur constante aide à éviter entièrement le problème.
Forger le CRC en ajoutant 4 octets aléatoires ne suffira probablement pas, car ces fichiers racines sont généralement en XML ou en texte avec des syntaxes strictes, ils deviendraient donc invalides.
CrcHack aide grandement à forger des CRC avec des bits arbitraires et sans force brute, en veillant à ce que le fichier de sortie reste en ASCII et que les bits modifiés se trouvent toujours dans un commentaire.Utiliser le extra field d’un fichier factice supplémentaire -- même vide -- dans l’archive après le fichier racine est une façon élégante de stocker les blocs de collision Hashclash : ainsi, l’archive Zip conserve une structure standard et peut être facilement manipulée ensuite, même avec des outils standard.
Les Extra Fields n’ont pas de CRC32, et leur longueur de 16 bits est déclarée dans les en-têtes précédents. Ils ont leur propre format interne ID:2 Size:2 Data mais il est généralement ignoré, et ils sont présents à la fois dans le Local File Header et dans le Central Directory, mais ils peuvent être absents du Central Directory pour conserver un suffixe identique après les blocs de collision.
La présence du fichier supplémentaire qui couvre les blocs de collision dans son extra field peut devoir être déclarée dans la structure du format, comme dans le fichier [Content_Types].xml d’un document OOXML. D’autres fichiers XML du suffixe peuvent devoir être modifiés, car certains formats exigent l’utilisation de chemins absolus.
Voici la structure globale de l’exploit générique pour un format spécifique basé sur Zip :``` [Root file] (with constant CRC32)
[Dummy file] (with collision blocks in the extra field)
[...] <- rest of the archive, with 2 documents merged
Ainsi, en prédéfinissant le contenu du fichier racine et en forgeant des CRC32 ASCII, on peut calculer une collision Hashclash générique et réutilisable pour un format basé sur zip.
### Résumé des exigences
- deux préfixes ou plus
- un ou plusieurs types de fichiers (les polyglots fonctionnent sans problème)
- un fichier racine XML avec un nom de fichier, une longueur de fichier et un CRC fixes : ces informations sont présentes deux fois, avant et après les blocs de collision
- le contenu est un XML arbitraire
- le padding est possible, même via un commentaire XML, pour atteindre la même longueur.
- le CRC peut être défini (via CrcHack) sur chaque contenu.
- les deux ensembles de fichiers coexistent dans le suffixe, probablement dans des répertoires différents. Certains outils codent en dur le chemin, ce qui peut réduire la compatibilité.
- un fichier XML *Content type* peut devoir être fusionné pour couvrir tous les fichiers, pris en charge ou non (blocs de collision et document alternatif)
### Exemples
#### CRC32
Un commentaire XML minimal (ASCII uniquement) avec un CRC32 forgé (calcul instantané) avec 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-->
Un autre exemple où vous ajustez le CRC avec la casse d'un message alphabétique.```bash echo "" | crchack.exe -b 4:+.8*32:.8 - 0xcafebabe
#### Collisions
[zInsider](https://github.com/corkami/collisions/blob/HEAD/scripts/zinsider.py) est un script permettant de générer instantanément des collisions MD5 de paires de documents arbitraires à l'aide de ces formats ZIP+XML :
- Office Open XML : docx / pptx / xlsx
- Open Container Format : epub
- Open Packaging Conventions :
- format de fabrication 3D : 3mf
- XML Paper Specification : xps / oxps
Pour générer vos propres préfixes de collision, [voici un script](https://github.com/corkami/collisions/blob/HEAD/scripts/makezip.py) pour générer une paire de zips racines.
Après avoir calculé les collisions, utilisez [cet autre script](https://github.com/corkami/collisions/blob/HEAD/scripts/extendzip.py) pour combiner cette paire de racines avec un suffixe commun.
Quelques PoC de collisions :
- 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)).
Certains formats multi-fichiers basés sur Zip ne peuvent pas être exploités de manière générique :
- Quake PK3 : un zip de fichiers sans racine spécifique.
- Open Document Format : le fichier `META-INF/manifest.xml` doit référencer tous les autres fichiers, il ne peut donc pas être générique.
- APK, JAR, XPI : le fichier `META-INF/MANIFEST.mf` doit également mentionner tous les autres fichiers, avec leurs empreintes.
Merci à [Philippe Lagadec](https://twitter.com/decalage2) pour son aide sur les formats de fichiers Office !
### Autres
- Wasm, via une section personnalisée : [script](https://github.com/corkami/collisions/blob/HEAD/scripts/wasm.py), exemples : [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)
## Stratégies inhabituelles
Les collisions concernent généralement deux fichiers valides du même type.
### MultiColls : chaîne de collisions multiples
Rien n'empêche de chaîner plusieurs blocs de collision et d'avoir plus de deux contenus avec la même valeur de hachage.
Un exemple en est les *hashquines* - qui affichent leur propre valeur MD5.
Le fichier [PoCGTFO 14](https://github.com/angea/pocorgtfo#0x14) contient 609 collisions FastColl,
pour y parvenir via deux types de fichiers dans le même fichier.
#### Hashquines
Les hashquines sont des fichiers affichant leur propre valeur de hachage. Ils sont traités [ici](https://github.com/corkami/collisions/blob/HEAD/hashquines/).
### Validité
Une stratégie différente consisterait à tuer le type de fichier pour contourner l'analyse en tant que fichier corrompu.
Il suffit d'écraser la signature magique.
Ajouter aux deux fichiers (valides ou non) un format
qui n'a pas besoin d'être à l'offset 0 (archive, comme ZIP/RAR/...) révélerait un autre type de fichier.
Cela permet des collisions polyglottes sans utiliser de collision à préfixe choisi :
1. utiliser UniColl pour activer ou désactiver une signature magique, par exemple un PNG :
2. ajouter une archive ZIP
Bien que techniquement les deux fichiers soient des ZIP valides, comme la plupart des analyseurs renvoient le premier type de fichier trouvé et commencent leur analyse à l'offset 0, ils verront un type de fichier différent.
Exemples :
⟷ [invalide](https://github.com/corkami/collisions/blob/HEAD/examples/png-invalid.png)
### PolyColls : collisions de différents types de fichiers
Il est également possible d'avoir les deux côtés d'une collision avec des types différents pour éveiller moins de soupçons :
Scénario d'attaque :
1. envoyer `holiday.jpg`
2. le faire mettre sur liste blanche
3. envoyer `evil.exe`, qui a le même MD5.
Dans ces cas, une collision à préfixe choisi est nécessaire
si les deux formats de fichiers doivent démarrer à l'offset 0.
Quelques exemples d'agencements polycoll :
*Polycoll PDF/JPG*
*Polycoll PE/PNG*
#### PE - JPG
Puisqu'un en-tête PE est généralement plus petit que 0x500 octets, il s'intègre parfaitement dans un commentaire JPG :
1. commencer par les en-têtes DOS/JPG
2. le commentaire JPEG saute par-dessus l'en-tête PE
3. placer l'image JPG complète
4. placer toutes les spécifications PE
Encore une fois, la collision est [instantanée](https://github.com/corkami/collisions/blob/HEAD/scripts/jpgpe.py)
Exemples : [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
Fusionner un PDF avec un fichier factice via `mutool` est un bon moyen générique de réorganiser les objets,
puis de rendre les deux premiers objets jetables (page factice et contenu),
ce qui convient parfaitement pour héberger un objet `stream` de longueur inconnue en `1 0`,
et dont la longueur est référencée plus loin (après les blocs de collision) dans le second objet.
Le seul problème est que `mutool` intègre toujours la longueur en ligne - et supprime la référence de longueur -,
il faut donc la réinsérer dans le PDF à la place de la valeur,
mais la plupart des références `2 0 R` seront plus petites que les longueurs codées en dur.
Heureusement, cela peut être corrigé sans modifier aucun offset d'objet,
donc pas besoin de patcher le XREF.
Voici un [script](https://github.com/corkami/collisions/blob/HEAD/scripts/pdfpe.py) pour, par exemple, mettre instantanément en collision une visionneuse PDF ([Sumatra](https://www.sumatrapdfreader.org/free-pdf-reader.html) est légère et autonome) et un document PDF :
Exemples : [Poster.pdf](https://github.com/corkami/collisions/blob/HEAD/examples/pepdf.pdf) ⟷ [Sumatra.exe](https://github.com/corkami/collisions/blob/HEAD/examples/pepdf.exe)
*une visionneuse PDF affichant un PDF (qui affiche lui-même un PDF) avec le même MD5*
#### PDF - PNG
De même, il est possible de mettre en collision par exemple des fichiers PDF et PNG arbitraires, sans restriction d'aucun côté. C'est instantané, réutilisable et générique.
Exemples : [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-collision)
Les collisions cryptographiques ne se limitent pas à deux fichiers !
Comme démontré dans l'expérience [Nostradamus](https://www.win.tue.nl/hashclash/Nostradamus/) en 2008,
chaîner des collisions permet de mettre en collision plus de deux fichiers.
Les premières collisions peuvent être identiques ou à préfixe choisi ; les suivantes doivent être à préfixe choisi.
Vous pouvez les appeler multi-collisions, je préfère *pileups* - c'est plus court :)
#### PE - PNG - MP4 - PDF
Combinant toutes les connaissances acquises précédemment,
j'ai utilisé 3 collisions à préfixe choisi pour fabriquer 4 préfixes différents pour différents types de fichiers :
document (PDF), vidéo (MP4), exécutable (PE) et image (PNG).
*diagramme d'un pileup PE/PNG/MP4/PDF*
Ce script est générique et instantané :
Exemples : [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)
Comme vous ne pouvez distribuer qu'un seul fichier
et qu'il est impossible de deviner les autres valeurs de préfixe à partir de celui-ci,
une solution consiste à intégrer tous les préfixes de la collision dans du code JavaScript
et à l'insérer dans vos PoC,
transformant vos fichiers en [polyglottes HTML](https://github.com/corkami/collisions/blob/HEAD/examples/polyglot.html) pour partager facilement les fichiers en collision associés.
Le [numéro 19](https://github.com/angea/pocorgtfo#0x19) de « PoC or GTFO » est un tel pileup **et** polyglotte,
combinant un document de 80 pages généré avec PDFLaTeX, une visionneuse PDF pour Windows,
un diagramme PNG et une courte vidéo MP4 de « collision » de [KidMoGraph](https://www.kidmograph.com/)
avec une charge utile HTML pour générer les autres fichiers à partir de la version PDF
(et aussi une archive ZIP) :
Merci à Rafał Hirsz pour son aide permanente sur JavaScript.
## Cas d'utilisation
Mieux vaut abandonner complètement MD5, car l'introspection des fichiers est tout simplement trop chronophage et trop risquée !
### Percutez-les tous !
Une autre utilisation de collisions instantanées, réutilisables et génériques serait de cacher n'importe quel fichier d'un type donné - disons PNG - derrière des fichiers factices (ou le même fichier à chaque fois) - ce qui revient en fait à le concaténer au même préfixe après en avoir retiré la signature - vous pourriez même le faire au niveau de la bibliothèque !
D'un point de vue strictement syntaxique,
tous vos fichiers afficheront le même contenu,
et les images malveillantes seraient révélées comme étant un fichier ayant le même MD5 que ceux collectés précédemment.
Prenons deux fichiers :
⟷
et mettons-les en collision avec le même PNG.
Ils affichent désormais la même image factice, et ils sont absolument identiques jusqu'à la 2e image au niveau du fichier !
⟷
Leur charge utile malveillante est respectivement cachée derrière un fichier ayant le même MD5.
### Fichiers compromettants
Un autre cas d'utilisation des collisions est de cacher quelque chose de compromettant dans quelque chose d'innocent,
mais désirable : si la seule chose pour recueillir des preuves est de comparer des hachages faibles,
alors vous ne pouvez pas nier que vous n'avez pas l'autre fichier (affichant un contenu compromettant mais cachant un contenu innocent).
Les logiciels se concentrent généralement sur l'analyse (rapide), pas sur une analyse détaillée des fichiers.
*une image montrant différents aperçus sous différents onglets d'EnCase Forensic*
## Échecs
Tous les formats ne peuvent pas avoir de préfixes génériques réutilisables :
si une sorte de conteneur de données ne peut pas être insérée entre la signature magique
et les en-têtes standard, critiques et spécifiques à chaque fichier,
alors les collisions génériques ne sont pas possibles.
Bien sûr, on pourrait toujours transformer les anciens fichiers en un nouveau fichier,
et même utiliser du code pour bifurquer vers deux charges utiles différentes,
mais cela relève plus du portage de charges utiles que de la mise en collision de structures de fichiers.
### ELF
L'en-tête ELF est requis à l'offset 0 et contient des informations critiques telles que 32b/64b,
l'endianness et l'ABI dès le début,
il est donc impossible d'avoir un préfixe universel puis des blocs de collision
avant des paramètres critiques spécifiques au fichier d'origine.
### Mach-O
Les fichiers Mach-O ne commencent même pas par la même magie pour 32b (`feedface`) et 64b (`feedfacf`).
Juste après, il y a le nombre et la taille des commandes (comme la définition des segments, symtab, version, ...).
Comme pour ELF, les collisions réutilisables ne sont pas possibles.
### Java Class
Juste après la magie de début se trouvent les versions (qui peuvent être problématiques)
mais aussi le nombre d'entrées du constant pool, qui est assez spécifique à chaque fichier,
donc pas de collisions universelles pour tous les fichiers.
Cependant, de nombreux fichiers partagent une version commune et on peut compléter le constant pool le plus court pour atteindre le nombre le plus long.
D'abord, insérer un *littéral UTF8* pour aligner les informations,
puis en déclarer un autre dont la longueur est abusée par un UniColl (la longueur est stockée sur 16 octets en big endian).
Cependant, cela nécessitera une manipulation du code, car tous les index du pool seront décalés.
Des collisions MD5 instantanées réutilisables de Java Class devraient être possibles, mais nécessitent une analyse et une modification du code.
### TAR
**TL;DR** Pas de collision réutilisable pour les fichiers TAR, aucune autre stratégie que le préfixe choisi.
Les Tape Archives sont une séquence d'en-têtes et de contenus de fichiers concaténés, tous alignés sur 512 octets.
Il n'y a aucune structure centrale pour l'ensemble du fichier. Donc aucun en-tête global ni commentaire d'aucune sorte à exploiter.
Une astuce consisterait à démarrer un fichier factice de longueur variable, mais la longueur est toujours au même offset, ce qui n'est pas compatible avec UniColl, ce qui signifie que seules les collisions à préfixe choisi sont utiles ici.
## Résumé des exploitations
Format | Générique ? | 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-based (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 a certaines limitations sur les données, qui peuvent être améliorées dans une certaine mesure en manipulant l'encodage des scans.
2. PDF avec JPG est l'[implémentation initiale](http://shattered.io) de l'attaque Shattered, mais ce n'est qu'une pure astuce JPG dans un document PDF.
3. PNG : Safari/Preview exige que les PNG aient leur chunk `IHDR` en première position, avant tout bloc de collision. Cela empêche un préfixe générique, auquel cas la collision est limitée à des dimensions, un espace colorimétrique, un BPP et un entrelacement spécifiques.
4. Les formats Atom/Box comme MP4 peuvent fonctionner avec le même préfixe pour différents sous-formats. Certains sous-formats comme JPEG2000 ou HEIF nécessitent un toilettage supplémentaire, mais la stratégie d'exploitation est la même - c'est juste que la collision n'est pas possible entre sous-formats, seulement avec une paire de préfixes pour un sous-format spécifique.
5. Atom/Box est compatible Shattered lors de l'utilisation de longueurs 64 bits.
6. Certains formats basés sur Zip peuvent être exploités de manière générique.
7. Pour une meilleure compatibilité, ZIP a besoin de deux UniColl pour une archive complète, et ces collisions dépendent du contenu des deux fichiers.
## Fichiers de test
[Voici](https://github.com/corkami/collisions/blob/HEAD/examples/free/README.md) des paires de test en collision libres (sans droit d'auteur, sans données personnelles).
# Détection
Il existe différentes façons de détecter les collisions de hachage dans les fichiers.
1. Deux fichiers : si vous avez deux fichiers ou plus avec des contenus différents et le même hachage, faites-en simplement un diff !
Cependant, si vous n'avez qu'un seul fichier, il peut être difficile de savoir si le fichier contient une collision de hachage.
2. Structure du fichier : analysez le fichier aux limites des blocs, et si vous remarquez des blocs à haute entropie et peut-être un préfixe/suffixe identique, vous pourrez peut-être dire quelle collision est utilisée, mais c'est très sujet aux erreurs. Dans le cas d'une collision à préfixe choisi, il peut être impossible de la repérer, car les deux fichiers peuvent être très différents en dehors de la plupart des blocs de collision.
3. Calcul du hachage : utilisez une implémentation (en [C](https://github.com/cr-marcstevens/hashclash/tree/collisiondetection/src/collisiondetection) ou [Go](https://github.com/therealmik/detectcoll)) du DetectColl de Marc Stevens (cf. son article [Counter-cryptanalysis](https://marc-stevens.nl/research/papers/C13-S.pdf)). Elle ne nécessite qu'un seul fichier, mais elle exige que la collision soit dans un état fonctionnel (le préfixe exact et ses blocs de collision correspondants) et elle est lente.
DetectColl donne des informations techniques sur la collision elle-même et affiche `*coll*` à côté du hachage ayant subi une collision.
## Exemple
Avec le certificat du malware Flame :```
$ 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
Étant donné que DetectColl peut identifier les blocs utilisés pour une collision de hachage, il peut atténuer la collision via des hachages sûrs : si un bloc de collision est détecté, il le retraite à nouveau pour briser la propriété de collision. Ainsi, DetectColl est capable de distinguer des contenus différents via la même fonction de hachage malgré les collisions présentes dans le fichier.
En résumé :
Exemple avec la collision originale de Wang de 2005 :``` $ md5sum wang* 79054025255fb1a26e4bc422aef54eb4 *wang1.bin 79054025255fb1a26e4bc422aef54eb4 *wang2.bin
MD5 sûr sur ces fichiers :```
$ detectcoll wang1.bin | grep coll
*coll* ff531291d102a41aa131e0e09f64ca60 wang1.bin
Veuillez fournir le contenu Markdown à traduire.``` $ detectcoll wang2.bin | grep coll coll 6a8e7124724d5c819401afc202a4fbd0 wang2.bin
## Signatures
Pour simplifier, vous pouvez parser la sortie de Detectcoll avec ce [script](https://github.com/corkami/collisions/blob/HEAD/scripts/logparse.py) et la faire correspondre plus facilement à des [signatures connues](https://github.com/corkami/collisions/blob/7f7876c431614f33f765bfc1cb62506b476a2eb0/scripts/logparse.py#L15-L24):``` 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
Un inconvénient mineur des hashs sûrs est qu'ils empêchent la détection de plusieurs collisions dans le même fichier, mais DetectColl peut toujours détecter des collisions avec les hashs « standard ».
Exemples avec PoCorGTFO 0x14 (un hashquine NES+PDF avec une image de couverture alternative).
Les hashs sûrs ne peuvent trouver qu'une seule collision :``` $ 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 les trouve tous :```
$ detectcoll_unsafe pocorgtfo14.pdf | grep Found | wc -l
609
Si vous vérifiez les dernières collisions :``` $ 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:
Vous pouvez remarquer que la dernière n'est pas si proche des précédentes :
cela vient du fait que les précédentes appartiennent au même fichier image pour les hashquines,
tandis que la dernière concerne la couverture alternative.
# Références
Articles (à propos de l'exploitation des formats de fichiers) :
- 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) par Gregor "Greg" Kopf
- [A PDF That Shows Its Own MD5](https://archive.org/stream/pocorgtfo14#page/n49/mode/1up) par Mako
- [This GIF shows its own MD5!](https://archive.org/stream/pocorgtfo14#page/n52/mode/1up) par Kristoffer "spq" Janke
- [This PDF is an NES ROM that prints its own MD5 hash!](https://archive.org/stream/pocorgtfo14#page/n55/mode/1up) par Evan Sultanik, Evan Teran
- 2018:
- [Easy SHA-1 Colliding PDFs with PDFLaTeX.](https://archive.org/stream/pocorgtfo18#page/n62/mode/1up) par Ange Albertini
- 2020:
- [SHA-1 is a Shambles](https://eprint.iacr.org/2020/014.pdf) par Gaëtan Leurent, Thomas Peyrin
Présentations:
- 2017 Exploiting Hash Collisions à Black Alps:
- [diapositives](https://speakerdeck.com/ange/exploiting-hash-collisions)
[](https://speakerdeck.com/ange/exploiting-hash-collisions)
- [vidéo](https://www.youtube.com/watch?v=Y-oJWEYKVLA)
[](https://www.youtube.com/watch?v=Y-oJWEYKVLA)
- 2019 KILL MD5 à Pass the Salt:
- [diapositives](https://speakerdeck.com/ange/kill-md5)
[](https://speakerdeck.com/ange/kill-md5)
- [vidéo](https://passthesalt.ubicast.tv/videos/kill-md5-demystifying-hash-collisions/)
[](https://passthesalt.ubicast.tv/videos/kill-md5-demystifying-hash-collisions/)
Atelier (CollTris):
- [diapositives](https://speakerdeck.com/ange/colltris)
[](https://speakerdeck.com/ange/colltris)
- [vidéo](https://www.youtube.com/watch?v=BcwrMnGVyBI)
[](https://www.youtube.com/watch?v=BcwrMnGVyBI)
- [supports](https://github.com/corkami/collisions/blob/HEAD/workshop/README.md)
- sessions
- 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
Tâches CTF:
- [Prudentialv2](https://ctftime.org/task/3453), du *Boston Key Party CTF 2017*.
- [HREFIN](https://ctftime.org/task/6965), du *Google CTF 2018*.
- [Looking glass](https://ctftime.org/task/9271) du *Dragon Sector Teaser CTF 2019*.
<!-- - [Not my digest](https://ctftime.org/task/4784) du *Hack.lu CTF 2017*: sans rapport avec les collisions, mais résolu par Marc lui-même :p -->
Un défi courant pour ce genre de tâches CTF est de ne pas donner un avantage ou un handicap trop important en fonction de la puissance de calcul à laquelle chaque joueur a accès.
# Crédits
Tout ceci a été possible grâce à [Marc Stevens](https://marc-stevens.nl/research/),
non seulement pour ses contributions cryptographiques, mais aussi pour son aide et ses suggestions permanentes !
Merci également à Philippe Teuwen pour ses retours approfondis sur les formats de fichiers en général.
# Conclusion
**Tuez MD5!**
À moins de vérifier activement la présence de malformations ou de blocs de collision dans les fichiers, n'utilisez pas MD5!
Ce n'est pas une fonction de hachage cryptographique, c'est une fonction jouet!
<!-- pandoc -s -f gfm -t html README.md -o README.html -->
| Préfixe | = | Préfixe |
|---|
| Collision A | ≠ | Collision B |
| A | = | |
| = | B |