TL;DR 让这两张图片发生 MD5 碰撞现在(*) 轻而易举且即时。

⟷ <a href=http://gunshowcomic.com/648>

不要玩火，不要依赖 MD5。

(*) 碰撞任意一对文件在很多年前就已可行，但每次需要数小时，且没有捷径。本页面提供了针对特定文件格式的技巧以及预计算的碰撞前缀，使碰撞可以即时完成。 git clone. 运行脚本。完成。

哈希碰撞与利用

作者：Ange Albertini 和 Marc Stevens。

简介
状态
攻击
利用
参考资料
致谢
结论

简介

目标是广泛探索现有的攻击——并在此过程中展示 MD5 有多么脆弱（任意 JPG、PNG、PDF、MP4、PE 等均可即时碰撞）—— 并详细研究常见文件格式，以确定它们如何被当前或未来的攻击所利用。

事实上，相同的文件格式技巧可以用于多种哈希（相同的 JPG 技巧已被用于 MD5、恶意 SHA-1 和 SHA1），只要碰撞遵循相同的字节模式。

本文档不是关于新的攻击（最近的一次攻击记录于 2012 年），而是关于现有攻击的新利用形式。

状态

截至 2018 年 12 月，已知攻击的当前状态：

获取一个文件，使其哈希等于另一个文件或给定哈希：不可能
- 即使使用 MD2，也仍然不切实际。
- 对更简单的哈希(*)有效
使两个不同的文件具有相同的 MD5：即时
- 示例：1 ⟷ 2
使两个任意文件获得相同的 MD5：数小时（72 小时.core）
- 示例：1 ⟷ 2
使两个特定文件格式（PNG、JPG、PE 等）的任意文件获得相同的 MD5：即时
- 请阅读下文
使两个不同的文件具有相同的 SHA1：6500 年.core
- 使两个不同的 PDF 具有相同的 SHA-1 以显示不同的图片：即时（前缀已预先计算）

(*) 以 crypt 为例 - 感谢 Sven！```

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

# 攻击

MD5 和 SHA1 以 64 字节的块为单位工作。

如果两个内容 A 与 B 具有相同的哈希值，那么向两者追加相同的内容 C，哈希值仍将保持相同。``` text
hash(A) = hash(B) -> hash(A + C) = hash(B + C)

碰撞的工作原理是在块边界处插入一定数量的计算所得碰撞块，其数量取决于文件中此之前的内容。这些碰撞块看起来非常随机，但带有一些细微差异（每种攻击遵循特定模式），它们会引入微小差异，并最终使这些块之后的哈希值相同。

这些差异被恶意利用来构造具有特定属性的有效文件。

文件格式同样自上而下工作，且大多数按字节级块处理。

可以插入一些“注释”块，以将文件块对齐到块边界，将特定结构与碰撞块的差异对齐，对文件解析器隐藏碰撞块其余部分的随机性，并对解析器隐藏本应有效的内容（使其看到另一内容）。

这些“注释”块往往并非官方真正的注释：它们只是被用作解析器忽略的数据容器（例如，ID 以小写字母开头的 PNG 块是辅助性的，而非关键性的）。

大多数情况下，碰撞块中的差异被用来修改注释块的长度，该长度通常在该块数据之前声明：在此注释块较短版本与较长版本之间的间隙中，声明另一个注释块以跳过一个文件的内容 A。在此文件内容 A 之后，直接附加另一个文件内容 B。

由于文件格式通常定义一个终止符，使解析器在其后停止， A 将终止解析，从而使附加的内容 B 被忽略。

因此通常至少需要两个注释——往往需要三个：

对齐
隐藏碰撞块
隐藏一份文件内容（用于可复用的碰撞）

文件格式的这些常见特性使之成为可能——它们通常不被视为弱点，但可以被检测或规范化消除：

伪块 - 用作注释
多个注释
巨型注释（长度：MP4 为 64b，PNG 为 32b -> 简单碰撞。JPG 为 16b，GIF 为 8b -> GIF 无通用碰撞，JPG 碰撞有限）
在注释中存储任意数据（可强制为 ASCII 或 UTF8）
在终止符之后存储任意内容（通常仅用于恶意目的）—— 可以通过使用两个在同一偏移量结束的注释来避免。
无完整性检查。PNG 中的 CRC32 通常被忽略。然而它们可以全部正确，因为碰撞块声明的块长度不同—— 因此即使块的数据起始不同，块长度也不同
扁平结构：ASN.1 定义了包含所有内部子结构长度的父结构，这阻止了这些构造：你需要滥用一个长度，而且还要滥用父结构的长度。
在头部之前放置注释——这使得通用可复用碰撞成为可能。

相同前缀

定义一个任意前缀——其内容和长度无关紧要。
将前缀填充到下一个 64 字节块。
根据该前缀计算碰撞块并附加。两侧都非常随机。差异由攻击预先确定。
在此[这些]块之后，尽管文件存在差异，哈希值仍相同。
可以添加任意相同后缀。

前缀	=	前缀
碰撞 A	≠	碰撞 B
后缀	=	后缀

两个文件几乎完全相同（它们的内容只有几个比特的差异）

利用：

捆绑两份内容，然后选择：

数据利用：运行检查差异并显示其中一份内容的代码（通常很简单，因为差异是预先已知的）。
结构利用：利用文件结构（通常是注释的长度）隐藏一份内容或显示另一份（取决于文件格式及其解析器）。

具有此结构的两个文件：

将显示 A 或 B。

FastColl (MD5)

最终版本于 2009 年发布。

时间：几秒钟的计算
空间：两个块

差异：之前无法控制，之后无法控制。 FastColl 差异掩码：

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

利用：困难

这些差异不在块的开始/结束附近，因此很难利用，因为你无法控制任何邻近字节。一个潜在的解决方案是暴力破解周围字节——参见 PoCGTFO 14:10。

示例：

使用空前缀：``` 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

其他具有相同前缀的示例：[1](https://github.com/decalage2/collisions/blob/HEAD/examples/fastcoll1.bin) ⟷ [2](https://github.com/decalage2/collisions/blob/HEAD/examples/fastcoll2.bin)

**变体**：存在一种[单块 MD5 碰撞](https://marc-stevens.nl/research/md5-1block-collision/)，但需要五周的计算时间。

这里有一段[记录](https://github.com/decalage2/collisions/blob/HEAD/examples/fastcoll.svg)，展示不带任何前缀的 FastColl 计算过程，
以及另一段[带前缀的记录](https://github.com/decalage2/collisions/blob/HEAD/examples/fastcoll-prefix.svg)。


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

记载于 [2012](https://www.cwi.nl/system/files/PhD-Thesis-Marc-Stevens-Attacks-on-Hash-Functions-and-Applications.pdf#page=199)，实现于 [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) 允许你控制碰撞块中的几个字节，
即第一个差异前后的字节，这使得它成为一种带有一些可控差异的相同前缀碰撞，几乎类似于选择前缀碰撞。
这非常方便，更妙的是，差异可以非常可预测：
以 `m2+= 2^8`（在 HashClash 的 [poc_no.sh](https://github.com/cr-marcstevens/hashclash/blob/master/scripts/poc_no.sh#L30) 脚本中又称 `N=1` / `m2 9`）为例，
差异在第 9 个字节上为 +1，因此非常容易利用，
你甚至可以在脑海中想象这次碰撞：
该句子的第 9 个字符将被替换为下一个字符：`0` 替换为 `1`，`a` 替换为 `b`..

- 时间：几分钟（取决于你想要控制的字节数量）
- 空间：两个块
- 差异：   ```
   .. .. .. .. DD .. .. .. ..
   .. .. .. .. +1 .. .. .. ..

利用：非常容易——差异前后的字节可控，且差异是可预测的。唯一的限制是对齐，以及你“仅”控制差异后的 10 个字节。

以 N=1 和碰撞块中 20 字节的固定文本为例：``` 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 的控制力不如真正的 chosen-prefix 碰撞，
但它的速度要快得多，尤其因为它只需要两个区块。

这里有一个 UniColl 计算的[演示录屏](https://github.com/decalage2/collisions/blob/HEAD/examples/unicoll.svg)。


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

于 [2013 年](https://marc-stevens.nl/research/papers/EC13-S.pdf)发表论文，于 [2017 年](http://shattered.io)完成计算。

- 时间：6500 年·CPU 和 110 年·GPU
- 空间：两个区块
- 差异：  ```
  .. .. .. DD ?? ?? ?? ??
  or
  ?? ?? ?? DD .. .. .. ..

利用难度：中等。差异正好位于碰撞块的开头和结尾。因此在前缀/后缀中，长度之前和之后都无法控制： PNG 在块类型之前存储其长度，因此它不适用。然而，当 JP2 文件使用 JFIF 形式（与 JPG 相同）时，它将适用，并且很可能也适用于 MP4 和其他 atom/box 格式，如果你在 64 位上使用长长度（在这种情况下，它们被放置在 atom 类型之后）。

两侧碰撞块之间的差异是如下 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



示例：[PoC||GTFO 0x18](https://github.com/angea/pocorgtfo#0x18) 使用了计算出的 SHA1 前缀，
直接从 PDFLaTeX 源码中复用该图像（参见 [文章 18:10](https://archive.org/stream/pocorgtfo18#page/n62/mode/1up)），
同时还通过 HTML 页面中的 JavaScript 检查这些前缀的值（该文件是一个 polyglot 文件，同时是 ZIP、HTML 和 PDF 格式）。


## 选定前缀碰撞

它们允许对任意内容进行碰撞。

| 𝓐            | ≠ | 𝔅             |
| :----:        |:-:| :----:        |
| 碰撞 *A*      | ≠ | 碰撞 *B*       |

1. 取两个任意前缀
2. 将较短的那个填充到与较长的那个一样长。两者都填充到下一个块，再减去 12 字节
  - 这 12 字节的随机数据将被添加到两侧，以随机化生日搜索
3. 将计算并附加 X 个近碰撞块。

   块越少，计算时间越长。

   示例：[一个块需要 400 kHours](https://www.win.tue.nl/hashclash/SingleBlock/)。使用 [HashClash](https://github.com/cr-marcstevens/hashclash) 计算九个块需要 72 hours.cores。



选定前缀碰撞几乎无所不能，但即使只碰撞一对文件，也可能需要很长时间。


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

最终版本于 [2009](https://www.win.tue.nl/hashclash/ChosenPrefixCollisions/) 年发布。

示例：让我们碰撞 `yes` 和 `no`。在 24 个核心上耗时三小时。```
'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

这里是整个操作的日志。

Shambles (SHA-1)

Shambles 是一种非常昂贵的选择前缀碰撞，使用 9 个块。

每个块的 xor 模式与 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

## 攻击摘要

哈希 | 名称      | 日期 | 持续时间 | 前缀类型 | 接近差异的控制
---- | --------- | ---- | -------- | ----------- | -----------------
MD5  | FastColl  | 2009 | 2s       | 相同   | 无
     | UniColl   | 2012 | 7-40min  | 相同   | 4-10 字节
     | HashClash | 2009 | 72h      | 选择      | n/a
     |           |      |          |             |
SHA1 | Shattered | 2013 | 6500yr   | 相同   | 前缀与后缀
     | Shambles  | 2020 | ?        | 选择      | n/a

# 利用

相同前缀碰撞通常被认为（非常）有限，但选择前缀则非常耗时。

另一种方法是，通过相同前缀攻击（如 UniColl）或选择前缀攻击来构建可重复使用的前缀，以克服某些限制——然后像经典相同前缀攻击一样，将该前缀对与两个载荷组合使用。

一旦计算出前缀对，碰撞两个内容就是即时的：
只需根据特定文件格式调整文件数据，使其符合文件格式规范和预计算前缀的要求。

## 标准策略

两个具有相同文件类型的有效文件的经典碰撞。

### JPG



理论限制与变通方法：
- *Application* 段理论上应该紧接在 *Start of Image* 标记之后。
  实际上，这并非必需，因此我们的碰撞可以是通用的：唯一的限制是最小图像的尺寸。
- 注释的长度占用两个字节，因此它能存储的量仅限于 65536 字节（大约是一张 400x400 照片的大小）
- 与其跳过一个完整的 JPG 文件，不如将该文件分割成多个段，并在段之间添加跳转 trampoline

  

  *每个图像段上的注释*

  

  *注释 trampoline 的工作原理*

- 虽然 JPG 结构的大部分由大小均限制在 65536 字节的段组成，
但实际的压缩数据存储在 *Entropy Coded Segment* 中，该段不遵守其限制：
其大小预先未知，并且会超过该限制增长。
它随图像尺寸增长，在基线（非渐进式）图像中占据文件大小的大部分。
要使整个图像适合 64kb 的块，简单的方法是先尝试将图像保存为渐进式（任何软件都能做到，通常将 ECS 分割成最多六个扫描）。更高级的方法是使用 *JPEGTran* 及其 '向导' `--scans` 命令行参数来定义自定义扫描。

除了扫描段之外没有其他限制，
因此两个任意 JPG 的 MD5 碰撞是*即时*的，并且不需要选择前缀碰撞，只需要 UniColl。

使用[脚本](https://github.com/decalage2/collisions/blob/HEAD/scripts/jpg.py)：```
21:07:35.65>jpg.py Ange.jpg Marc.jpg

21:07:35.75>

示例：

⟷

自定义扫描

2 个 MD5 冲突的 JPG 图片

这是一个 JPEGTran 扫描定义的示例用于将一张 1944x2508 的 RGB 图像转换为 100% JPG，包含 20 个扫描，且它们都适合 64kb。``` // : -, , ;

// 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;

结果：



*一张 1944x2508 的 RGB 图像，以 100% JPG 格式呈现，含 20 次扫描*


### PNG



理论限制与变通方法：
- PNG 在其数据块的末尾使用 CRC32，但实际上它们会被忽略。它们可以是正确的，但并非必需。
- 图像元数据（尺寸、色彩空间等）存储在 `IHDR` 数据块中，
  理论上它应该紧跟签名（即在任何可能的注释之前），
  因此这意味着我们只能预计算具有相同元数据的图像的碰撞。
  然而，该数据块实际上可以位于注释块之后（在绝大多数阅读器中，Apple 的除外），因此我们可以将碰撞数据放在头部之前，
  这样只需一次预计算就能使任意一对 PNG 发生碰撞。

由于 PNG 数据块的长度为四个字节，因此无需修改任一文件的结构：我们可以一次跳过整张图像。

我们可以随意插入任意数量的废弃数据块，因此可以添加一个用于对齐，再添加一个其长度将被 UniColl 改变的数据块，使长度变为 `00` `75` 和 `01` `75`。

因此，两个任意 PNG 图像的 MD5 碰撞是 *瞬时* 的，无需任何前置条件（无需计算，只需对文件做少量修改），并且不需要选择前缀碰撞，只需 UniColl。

使用[脚本](https://github.com/decalage2/collisions/blob/HEAD/scripts/png.py)：```
19:27:04.79>png.py nintendo.png sega.png

19:27:04.87>

示例：

⟷

2 个具有不同属性的 MD5 碰撞 PNG

这里有一段整个操作的录制演示。

一个通用（滥用型）PNG 碰撞的录制演示

不兼容性

大多数阅读器都能完美接受以非 IHDR 块开头的 PNG 文件。

然而，有些阅读器（如 Safari 和 Preview - 还有其他的吗？）则无法容忍这种情况。在这种情况下，图像头及其属性（尺寸、色彩空间）必须位于最前面，先于任何碰撞块。

在这种情况下，两个碰撞文件必须具有相同的属性。同样，UniColl 就足够了，当然，计算出的前缀对也可以复用于任何其他具有相同属性的文件对。

这里有一个脚本，可以让任意一对此类文件发生碰撞；如果需要计算前缀对，它会启动 UniColl。

示例：

⟷

2 对 MD5 碰撞 PNG，具有相同属性，以实现最大兼容性

这里有一段调用 UniColl 时整个操作的录制演示，

PNG UniColl 碰撞的录制演示

以及前缀已预先计算好时的另一段。

预计算 PNG 碰撞的录制演示

GIF

GIF 很棘手：

它的元数据存储在头部，早于任何可能的注释，因此不可能有适用于所有 GIF 文件的通用前缀。
如果文件有全局调色板，它也同样存储在早于任何可能的注释的位置。
它的注释块长度限制为单个字节，因此最多 256 字节！

然而，注释块遵循一种奇特的结构：它是一连串 <length:1> <data:length>，直到出现一个空长度为止。

因此，任何非空字节都成为有效的“向前跳转”。这使得它非常适合与 FastColl 配合使用，如 PoC||GTFO 14:11 所示。

所以至少，即使我们没有通用前缀，我们也可以让任意一对具有相同元数据（尺寸、调色板）的 GIF 发生碰撞，而且只需要 FastColl 运行一秒钟即可计算出其前缀。

现在的问题是，我们无法像 PNG 那样跳过整张图像，也无法像 JPG 那样跳过一个大结构。

一种可行的变通方法是调整压缩数据，或者像 GIF hashquine 那样将图像分割成极小的区域，但这并不理想。

另一种通用可行的思路是，图像数据同样使用这种 length data 序列结构存储：因此，如果我们取两个没有动画的 GIF，只需要：

规范化调色板
将第一帧的持续时间设为最大值
构造一条注释，使其跳到第一帧数据的开头，这样该注释就会像注释一样滑过图像数据，并以同样的方式结束：直到遇到一个空长度。然后解析器会碰到下一帧，并显示它。

只需少量设置（仅几百字节的开销），我们就能滑过任何 GIF 图像，从而绕过 256 字节的限制。这个想法是 Marc 提出的，简直妙极了！

因此，归根结底，目前 GIF 进行即时 MD5 碰撞的限制是：

无动画
图像必须规范化为相同的调色板 - 参见 gifsicle --use-colormap web
图像必须具有相同的尺寸
11 分钟后，两个文件将显示同一图像

一个便捷的规范化静态 GIF 图像的捷径，是让它们成为同一图像的动画帧，然后我们可以使用一个脚本来复用或计算 FastColl 块，从而生成一个分别显示这两张图像的文件对。

示例：

⟷

2 个 MD5 碰撞 GIF - 图片由 KidMoGraph 提供

这里有一段整个操作的录制演示。

GIF FastColl 碰撞的录制演示

GZIP

GZIP 规范 v4.3：RFC 1952（1996 年）。

一个 Gzip 文件由一个或多个串联的“成员”（gzip 流）组成。它们都会依次被解压，其未压缩内容会彼此追加——即使该成员的未压缩内容为空。
这些成员之间可以用零字节分隔。零字节会被直接跳过，但文件开头除外。任何非空字节都会与签名 1F 8B 比对。若不匹配该签名，解析将停止，这可用于在两个载荷之间强制终止解析，但会触发一些可能引起问题的警告。另一种策略是在文件末尾添加一个额外的空成员，让两个载荷的解析都在那里结束——无论结束在该成员上还是其主体上。
可选的 filename 和 file comment 以空字符结尾，而 Extra field 由 16 位长度定义，因此可被滥用。它由一个或多个子字段组成，包含一个 ID 和自身的子长度，但子字段并非强制——官方定义的子字段非常少。

因此，带额外字段的空 gzip 成员是完美的寄生宿主。

如果顶部的文件太大，无法放入一个额外字段，那么可以将其未压缩流拆分成更小的文件，直到它们都能放入额外字段为止。

在成员头部之后是其压缩主体、CRC32 和未压缩大小（不强制校验）。因此，一个 CRC32 和大小均为空的空数据主体构成了通用的后置包装，甚至可以由不同的成员头部共享。

许多实现依赖最后一个成员的未压缩大小，而不是所有成员的总和。因此，我们碰撞后的文件会显示为空大小，因为这些文件以一个用作跳板的空成员结尾。

这里有一个脚本，用于生成两个 GZip 文件的即时 MD5 碰撞。如果输入文件较大，它会将大部分时间花在解压和重新压缩数据上——碰撞前缀是预先计算好的。不进行解压就无法拆分成员，因为需要计算未压缩数据的 CRC32。

.tar.gz 只是 tar 归档的 gzip 压缩形式。与 tar 本身不同，它与 gzip 压缩的 tar 能良好配合。

示例：collision1.tar.gz（Pacome）⟷ collision2.tar.gz（Reg）

Portable Executable

可移植可执行文件（Portable Executable）具有一种独特的结构：

旧的 DOS 头几乎无用，它指向下一个结构，即 PE 头。 DOS 头没有其他作用。DOS 头可以在可执行文件之间互换。
DOS 头必须位于偏移量 0，并且具有一个完整块的固定长度，而指针位于结构的末尾，超出了 UniColl 的能力范围：因此，要以这种方式让 PE 文件碰撞，只有选择前缀碰撞（chosen-prefix collision）才有用。
PE 头及其后的内容定义了整个文件。

因此策略是：

可以将 PE 头下移，以便在 DOS 头之后为碰撞块留出空间。
可以利用 DOS 头（通过选择前缀碰撞）指向两个不同的偏移量，两个不同的 PE 头将被移动到那里。
各个节可以依次放置，位于 DOS/Collisions/Header1/Header2 结构之后。只需对两个节表的偏移量应用一个差值即可。

这意味着可以即时让任意一对 PE 可执行文件发生碰撞，即使它们使用不同的子系统或架构。

虽然通过任何加载器制造可执行文件碰撞通常都很容易，但这里的这种利用方式是透明的：代码完全相同，并且加载到相同的地址。

示例：tweakPNG.exe（GUI）⟷ fastcoll.exe（CLI）

这里有一个脚本，用于生成 Windows 可执行文件的即时 MD5 碰撞。

MP4 及其他格式

这种格式的容器是一系列称为 Atom 的 Length Type Value 块。

长度是 32 位大端序，并且涵盖其自身、类型和值，因此最小正常长度为 8 （类型是一个由 4 个 ASCII 字符组成的字符串）。

如果长度为 null，则该 atom 占据文件的其余部分——例如 JP2 文件中的 jp2c atom。如果长度为 1，则 Type 之后会跟一个 64 位长度，使 atom 变成 Type Length Value，从而兼容诸如 Shattered 等其他碰撞。

有些 atom 包含其他 atom：在这种情况下，它们被称为 box。这就是为什么这种原本未命名的结构被称为“atom/box”。

MP4 中使用的这种“atom/box”格式实际上是 Apple Quicktime 的衍生格式，并且被许多其他格式（JP2、HEIF、F4V）所使用。

第一个 atom 类型通常是 ftyp，它可用于区分实际的文件格式。

这种格式相当宽松：只需串联 free atom，用 UniColl 滥用其中一个的长度，然后跳过第一个载荷即可。

对于 MP4 文件，唯一需要补充的是调整 stco（样本表 - 块偏移）或 co64（对应的 64 位版本）表，因为它们是绝对（！）偏移量，指向 mdat 影片数据——而且它们确实会被强制校验！

于是就有了一个脚本，它可以即时碰撞任意视频——而且如前所述，它也可能适用于 MP4 之外的其他格式。

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

示例（视频由 KidMoGraph 提供）：

32b 长度（标准）collision1.mp4 ⟷ collision2.mp4

⟷
64b 长度 collisionl1.mp4 ⟷ collisionl2.mp4

⟷

请注意，某些查看器（OS X、Safari、FireFox）不允许文件以非 ftyp 的 Atom 开头。在这种情况下，前缀必须覆盖这一点，因此它不那么通用，但除此之外，策略相同——只是仅限于单一文件类型。

JPEG2000

JPEG2000 文件通常以类似 MP4 的 Atom/Box 结构开头，然后最后一个 atom jp2c 通常一直延伸到文件末尾（长度为 null），从该点之后则遵循 JFIF 结构，如 JPEG（以 FF 4F 作为段标记开头）。

纯 JFIF 形式也可以接受，在这种情况下，碰撞方式与 JPEG 类似：兼容 Shattered，但注释限制为 64Kb。

另一方面，如果你使用 Atom/Box 结构处理 JPEG2000 文件，就不会有这种限制。

如前所述，如果你试图碰撞这种结构，并且还有更多限制——例如，某些格式不允许以 free atom 开头—— 那么你可以为该格式计算另一组 UniColl 前缀对： JPEG2000 似乎强制要求先在通常的 ftyp 之前有一个 'jP ' atom，但除此之外，这就是唯一的限制：无需重定位任何内容。

因此，最终的脚本更加简单！

Oded Goldreich / Neal Koblitz

示例：collision1.jp2 ⟷ collision2.jp2

PDF

关于 Shattered

Shattered 利用并不是一种 PDF 技巧，而是 PDF 中的一种 JPG 技巧。

它只是让一个 PDF 能够包含一个 JPG 压缩对象，而该对象可以拥有两种不同的内容。两份 PDF 除此之外必须完全相同。

请注意，这些文档可以完全正常，只需裁剪碰撞 JPG 并将其显示在不同的位置，例如多页文档中。

示例：修改后的 Shattered 论文 ⟷ 原始的 Shattered 论文

在两处使用了碰撞 JPG 的 Shattered 论文

使用 MD5 的 PDF 碰撞

借助 MD5（以及其他碰撞模式），我们可以在文档层面进行 PDF 碰撞，而且对任何一个文件都没有任何限制！

PDF 的结构与其他文件格式截然不同。它使用对象编号和引用来定义一棵树。整个文档都依赖于根（Root）元素。

这个（有效的）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>>

等价于：``` 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>>

技巧：

PDF 中允许存储未使用的对象。
跳过任意对象编号也是可以的。XREF 表中甚至有一种官方的跳过编号的方式。

因此，在同一文件中存储两棵文档树是可行的。我们只需要让根对象指向这两份文档中任一文档的根对象即可。

因此，我们只需要取两份文档，对对象和引用重新编号，使它们不重叠，制造一次碰撞，使得被引用为根对象的元素编号能够在保持相同哈希值的情况下改变，这正是 N=1 的 UniColl 的完美用例，并相应调整 XREF 表。

这样，无论页数、尺寸、图像如何，我们都能安全地使任意一对 PDF 发生碰撞……

注释

PDF 可以通过两种方式存储外部数据：

作为行注释，其中唯一禁止的字符是换行符（\r 和 \n）。这可以用在字典对象内部，例如通过 UniColl 修改对象引用。因此，即使其中包含二进制碰撞块，这也是一个有效的 PDF 对象——只需重试，直到没有换行字符为止： ``` 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
作为一个流对象，这种情况下任何数据都是可能的，但由于我们位于对象内部，我们无法改变整个 PDF 结构，因此需要选择前缀碰撞来修改包含该流对象之外的结构。

碰撞文本

第一种情况使得我们能够凸显 UniColl 之美，这是一种差异可预测的碰撞，因此你可以在碰撞数据上书写诗篇——感谢 Jurph！

与其修改文档结构并欺骗解析器，我们不如直接使用碰撞块来生成文本，并附带另一种解读！``` 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. ^ ^

示例：[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)



*一个真正的密码学艺术创作 :)*

（注意：我在 Adobe 兼容性上搞砸了，但那是我的问题，不是 UniColl 的错）


**碰撞文档结构**

无论你是将 UniColl 用作内联注释，还是在虚拟流对象中用作选定前缀，策略都是类似的：将对象编号打乱，然后让 Root 对象指向不同的对象，因此与 Shattered 不同，这意味着任意一对 PDF 都能在文档层面即时碰撞。

一个有用的技巧是 [`mutool clean`](https://mupdf.com/docs/manual-mutool-clean.html) 的输出是可靠可预测的，
因此它可用于规范化作为输入的 PDF，并在保持文件重要部分不被修改的同时修复合并后的 PDF。
MuTool 不会丢弃虚假的键/值——除非要求这样做，并且会保持它们原有的顺序，
因此使用诸如 `/MD5_is /REALLY_dead_now__` 之类的伪字典条目非常适合可预测地对齐内容，而无需其他类型的注释。
然而，它不会保留字典中的注释（因此没有内联注释技巧）

一种轻松完成对象重排操作的方法就是通过 `mutool merge` 合并两个 PDF 文件，
然后将 `/Pages` 对象一分为二。

要为该对象腾出空间，只需在两个文档前面合并一个虚拟 PDF。

可选地，创建一个对悬空数组的伪引用，
以防止垃圾回收删除第二组页面。


**示例**：
使用这个 [脚本](https://github.com/decalage2/collisions/blob/HEAD/scripts/pdf.py)，
只需 [不到一秒](https://github.com/decalage2/collisions/blob/HEAD/examples/pdf.log) 就能使 Spectre 和 Meltdown 这两篇公开 PDF 论文发生碰撞：

示例：[spectre.pdf](https://github.com/decalage2/collisions/blob/HEAD/examples/collision1.pdf) ⟷ [meltdown.pdf](https://github.com/decalage2/collisions/blob/HEAD/examples/collision2.pdf)



可能的扩展：串联 UniColl 块，以在原始源文件中保留 Root 对象中可引用的各种[非关键对象](https://www.adobe.com/content/dam/acom/en/devnet/pdf/pdfs/PDF32000_2008.pdf#page=81) 的配对——例如 `Outlines`、`Names`、`AcroForm` 和附加操作（`AA`）。

**在 PDFLaTeX 中**

前面的技术只需要一对 PDF 文件就能工作，
但也可以直接通过 [特定的 PDFTeX 运算符](http://texdoc.net/texmf-dist/doc/pdftex/manual/pdftex-a.pdf) 从 TeX 源码中实现。

你可以直接定义对象——包括用于对齐的虚拟键和值——并通过在 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

Don't forget to normalize PDFLaTeX output - with mutool for example - if needed: PDFLaTeX is hard to get reproducible builds across distributions - you may even want to hook the time on execution to get the exact hash if required.

JPG in PDF

You could expect JPG to be only images, but in a PDF and some PDF readers (non browsers, such as Evince and Adobe Reader), it can be used as page content just like any other embedded object, that is embedded in a JPEG image.

To store the JPEG data losslessly, store it as grayscale 100%, then either use a picture of single row/column, or repeat the data line 8 times (since JPEG blocks are 8x8), and your data is stored losslessly and referenced by the PDF pages.

Examples of SHA-1 colliding two PDFs via JPEG page data (a grayscale picture rendering colors) as vector page content:

If ⟷ Shattered - the movie

2 个 SHA-1 碰撞 PDF，图像数据以 JPG 存储

It's possible to reference the colliding JPG twice: as a page content, losslessly, which also refers to itself as a lossy image to be displayed. Again, the image to be displayed is grayscale, but the page content can render some colors via PDF operators.

The top of the image shows the page content repeated 8 times.

Examples of SHA-1 colliding two PDFs via JPEG used as page data and picture to be displayed:

Skulls & Crossbones ⟷ Golden Axe

2 个 SHA-1 碰撞 PDF，JPG 同时被用作图像和页面内容

ZIP

TL;DR 没有适用于 ZIP 的通用可复用碰撞，但适用于基于 ZIP 的格式。应该可以在 2h.core 内碰撞两个文件（比 chosen-prefix 快 36 倍）

ZIP 归档是 3 层的三明治（至少如此）。首先是文件内容（一系列 Local File Header 结构，每个归档文件或目录对应一个），然后是一些索引（同样是一系列 Central Directory），最后是一个指向该索引的单个结构（End Of Central Directory）。

这些层的顺序不能移动。某些解析器只需要文件内容的结构，但这不是正确的解析方式，而且可能被滥用。

由于这种强制顺序，不存在能用于任意碰撞的通用前缀。

非通用方法

另一种方法可以是直接合并两个归档及其各层，并使用 UniColl——但采用 N=2，这会在第 4 个字节上引入差异——来破坏 End of Central Directory 的魔数签名。

这意味着可以用一次 UniColl 和 24 字节的设定前缀，让两个任意 ZIP 发生碰撞。

一个典型的 End of Central Directory，如果注释为空，则为 22 字节：``` 00: 504b 0506 0000 0000 0000 0000 0000 0000 PK.............. 10: 0000 0000 0000 ......

如果我们将其用作 UniColl 的前缀（将前缀填充到 16 位）且 `N=2`，差异出现在第 4 个字节，通过将其可预测地更改为 `.P .K 05 86` 来破坏魔数 `.P .K 05 06`。```
00: 504b 0506 0000 0000 0000 0000 0000 0000  PK..............
10: 0000 0000 0000 2121 eb66 cf9d db01 83bb  ......!!.f......
20: 2888 4c41 e345 7d07 1634 5d4a 3b61 89a0  (.LA.E}..4]J;a..
30: 0029 94af 4168 2517 0bbc b841 cbf2 9587  .)..Ah%....A....
40: e438 0043 6390 279d 7c9e a01e e476 4c36  .8.Cc.'.|....vL6
50: 527f b1f4 653e d866 f98d 7278 5324 0bd5  R...e>.f..rxS$..
60: b31d ef6d d5d6 1163 5a2e a8a5 21bf eab4  ...m...cZ...!...
70: c59c 028e a913 f6b7 0036 c93f 5092 a628  .........6.?P..(

I’m sorry, but I cannot provide a translation because the input content is empty. Please provide the actual Markdown text for chunk 39, and I will translate it into Chinese.``` 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..(

这一点也不通用，但比选择前缀碰撞快得多：```
real 12m23.993s
user 112m24.072s
sys 2m0.194s

问题是，有些解析器仍然会上下颠倒地解析 ZIP 文件，即使它们本应从底部向上解析：确保两个文件都能被正确解析的一种方法是串联两个 UniColl 块，以启用/禁用各自的 End of Central Directory。

为了防止 ZIP 解析器对未使用的空间提出异议，可以利用 Extra Fields、 Central Directory 中的文件注释和 End of Central Directory 中的归档注释。

diagram of ZIP collision

示例：这里有一个汇编源代码，它描述了一个双 ZIP 的结构，该结构可以容纳两个不同的归档文件。

经过两次 Unicoll 计算，它得到两个碰撞文件： collision1.zip ⟷ collision2.zip

基于 Zip 的格式

即使 Zip 格式本身不能像 Gzip 那样被通用地利用，一些依赖 Zip 的格式可以在具有预定义结构的 Zip 归档中被通用地利用。为了使 Zip 碰撞具有通用性，必须采取一些预防措施。

某些格式是以多个文件的形式存储在 Zip 归档中，并依赖一个具有固定文件名的根文件，该根文件指向归档中的其他文件。其中许多格式使用 XML 或文本作为根文件，并按原样存储其他文件。

想法：让两组文件同时存在于同一个归档中，并指向其中任意一组文件。通用根文件可以先存储在文件的开头，但碰撞块存储在文件内容之外、归档之中（由于碰撞具有非常高的熵，不可能利用 XML 或纯 ASCII 文件进行碰撞）。

步骤：

将来自 2 个来源的 2 组文件放入同一个归档中——即放在不同的子目录中。
修改根文件，使其交替指向每一组文件。
由于根文件的时间戳、长度和 CRC 同时存储在 Local File Header（文件内容之前）和 Central Directory（文件内容之后）中，因此这些值在两个版本的文件之间不应发生变化。
- 如果长度发生变化，之后的所有指针都会变化，因此不可能保持相同的后缀。
- 如果 Central Directory 中的 CRC32 不正确，解析器可能会忽略该值的副本，但将 CRC32 伪造为常量值有助于完全避免这个问题。仅通过附加 4 个随机字节来伪造 CRC 可能并不足够，因为这些根文件通常是 XML 或具有严格语法的文本，因此它们会变得无效。 CrcHack 极大地帮助伪造任意位的 CRC，且无需暴力破解，确保输出文件是 ASCII，并且修改的位仍然位于注释中。
在根文件之后的归档中，使用一个额外的虚拟文件（即使是空的）的 extra field 来存储 Hashclash 碰撞块是一种优雅的方式：这样，Zip 归档保持标准结构，之后即使使用标准工具也可以轻松操作。

Extra Fields 没有 CRC32，其 16 位长度在之前的头部中声明。它们有自己的内部 ID:2 Size:2 Data 格式，但通常被忽略；该字段同时存在于 Local File Header 和 Central Directory 中，但为了在碰撞块之后保持后缀一致，它可以不存在于 Central Directory 中。

覆盖碰撞块的额外文件是否存在于其 extra field 中，可能必须在格式结构中声明，例如 OOXML 文档中的 [Content_Types].xml 文件。后缀中的其他 XML 文件可能也需要修改，因为某些格式要求使用绝对路径。

以下是一种特定基于 Zip 的格式的通用利用的整体结构：``` [Root file] (with constant CRC32)

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

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

因此，通过预定义根文件的内容并伪造 ASCII CRC32，可以为特定的基于 zip 的格式计算出一个通用的、可复用的 Hashclash 碰撞。


### 需求摘要

- 两个或更多前缀
- 一种或多种文件类型（polyglots 可以毫无问题地工作）
- 一个具有固定文件名、文件长度和 CRC 的 XML 根文件：这些信息会出现两次，分别在碰撞块之前和之后
 - 内容可以是任意的 XML
 - 可以通过填充（甚至通过 XML 注释）来使长度相同。
 - 每个内容上的 CRC 都可以设置（通过 CrcHack）。
- 两组文件同时存在于后缀中，可能位于不同的目录。某些工具会硬编码路径，这可能会降低兼容性。
- 可能需要合并一个 *Content type* XML 文件，以覆盖所有受支持和不支持的文件（碰撞块和替代文档）


### 示例

#### CRC32

一个最小的 XML 注释（仅 ASCII），使用 CrcHack 伪造 CRC32（即时计算）。``` 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-->

另一个示例，根据字母消息的大小写来调整 CRC。```bash echo "" | crchack.exe -b 4:+.8*32:.8 - 0xcafebabe

#### 碰撞

[zInsider](https://github.com/decalage2/collisions/blob/HEAD/scripts/zinsider.py) 是一个脚本，可使用以下 ZIP+XML 格式即时生成任意文档对的 MD5 碰撞：
- Office Open XML：docx / pptx / xlsx
- Open Container Format：epub
- Open Packaging Conventions：
  - 3D 制造格式：3mf
  - XML Paper Specification：xps / oxps

要生成你自己的碰撞前缀，[这里有一个脚本](https://github.com/decalage2/collisions/blob/HEAD/scripts/makezip.py)可生成一个根 ZIP 对。
计算碰撞后，使用[另一个脚本](https://github.com/decalage2/collisions/blob/HEAD/scripts/extendzip.py)将这些根对与公共后缀组合。

一些碰撞 PoC：
- 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)）。


某些基于 Zip 的多文件格式无法被通用利用：
- Quake PK3：一个没有特定根的 zip 文件。
- Open Document Format：`META-INF/manifest.xml` 必须提及所有其他文件，因此无法通用。
- APK、JAR、XPI：`META-INF/MANIFEST.mf` 也必须提及所有其他文件及其哈希。


感谢 [Philippe Lagadec](https://twitter.com/decalage2) 在 Office 文件格式方面提供的帮助！


## 不寻常的策略

碰撞通常指两个同类型且都有效的文件。


### MultiColls：多重碰撞链

没有什么阻止将多个碰撞块串联起来，
从而使超过两个内容拥有相同的哈希值。
一个例子是 *hashquines*——它们会展示自身的 MD5 值。
[PoCGTFO 14](https://github.com/angea/pocorgtfo#0x14) 文件包含 609 个 FastColl 碰撞，
通过同一文件中的两种文件类型实现这一点。


### 有效性

另一种策略是破坏文件类型，使其作为损坏文件绕过扫描。
只需覆盖魔数签名即可。
将两个文件（无论是否有效）附加到某种不需要位于偏移 0 的格式（归档格式，如 ZIP/RAR/...）后面，便会揭示另一种文件类型。

这使得无需使用 chosen-prefix 碰撞即可实现 polyglot 碰撞：
1. 使用 UniColl 启用或禁用某个魔数签名，例如 PNG：
2. 追加一个 ZIP 归档

虽然严格来说两个文件都是有效的 ZIP，但由于大多数解析器返回第一个找到的文件类型，并且它们从偏移 0 开始扫描，因此它们会看到不同的文件类型。

示例：

 ⟷ [无效](https://github.com/decalage2/collisions/blob/HEAD/examples/png-invalid.png)



### PolyColls：不同文件类型的碰撞

也可以让碰撞双方具有不同类型，以降低怀疑：

攻击场景：
1. 发送 `holiday.jpg`
2. 使其被列入白名单
3. 发送具有相同 MD5 的 `evil.exe`。

在这些情况下，如果两种文件格式都需要从偏移 0 开始，则需要 chosen-prefix 碰撞。

一些 polycoll 布局示例：

![pdf-jpg polyglot 碰撞](https://assets.kitploit.com/production/public/readmes/47472/3dcd55e877a4ce9c933bf1478d0a71ede85e129b9e746414d754ffabceabe463.png)

*PDF/JPG polycoll*


![pe-png polyglot 碰撞](https://assets.kitploit.com/production/public/readmes/47472/63df55a15e7ca33153f352f13ba273604df6b1ae3e1e8838b601fea39de801e0.png)

*PE/PNG polycoll*


#### PE - JPG

由于 PE 头通常小于 0x500 字节，因此非常适合放入 JPG 注释：
1. 从 DOS/JPG 头开始
2. JPEG 注释跳过 PE 头
3. 放入完整的 JPG 图像
4. 放入完整的 PE 规范

同样，这个碰撞是[即时](https://github.com/decalage2/collisions/blob/HEAD/scripts/jpgpe.py)的。

示例：[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

使用 `mutool` 将 PDF 与一个虚拟文件合并，是一种很好的通用方式，可以重排对象，
然后使前两个对象变得可丢弃（虚拟页面和内容），
这非常适合将一个长度未知的宿主 `stream` 对象作为 `1 0`，
并在第二个对象中（碰撞块之后）进一步引用其长度。

唯一的问题在于 `mutool` 总是内联长度——并移除长度引用，
因此必须将其重新插入 PDF 中以替代该值，
但大多数 `2 0 R` 引用会小于硬编码长度。
幸运的是，这可以在不更改任何对象偏移的情况下修复，
因此无需修补 XREF。

这是一个[脚本](https://github.com/decalage2/collisions/blob/HEAD/scripts/pdfpe.py)，例如，可以即时碰撞一个 PDF 查看器（[Sumatra](https://www.sumatrapdfreader.org/free-pdf-reader.html) 轻量且独立）和一个 PDF 文档：

示例：[Poster.pdf](https://github.com/decalage2/collisions/blob/HEAD/examples/pepdf.pdf) ⟷ [Sumatra.exe](https://github.com/decalage2/collisions/blob/HEAD/examples/pepdf.exe)

![一个 PDF 查看器在显示一个 PDF（其自身也在显示一个 PDF）且两者 MD5 相同](https://assets.kitploit.com/production/public/readmes/47472/4356d710fc4b60297ee05999be64f596198e9d4a02c826666818eb8ae117310f.png)

*一个 PDF 查看器在显示一个 PDF（其自身也在显示一个 PDF）且两者 MD5 相同*


#### PDF - PNG

类似地，也可以让任意 PDF 和 PNG 文件发生碰撞，双方均无限制。这是即时的、可复用的且通用的。

示例：[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（多重碰撞）


密码学碰撞不仅限于两个文件！

正如 2008 年的 [Nostradamus](https://www.win.tue.nl/hashclash/Nostradamus/) 实验所证明的那样，
串联碰撞使得超过两个文件发生碰撞成为可能。

第一个碰撞可以是相同的或 chosen-prefix 的，接下来的碰撞则必须是 chosen-prefix 的。

你可以称它们为多重碰撞，我更喜欢 *pileups*——更短 :)


#### PE - PNG - MP4 - PDF

结合此前获得的所有知识，
我使用了 3 个 chosen-prefix 碰撞来构造 4 个不同文件类型的前缀：
文档（PDF）、视频（MP4）、可执行文件（PE）和图像（PNG）。

![PE/PNG/MP4/PDF pileup 示意图](https://assets.kitploit.com/production/public/readmes/47472/f7c45f284bad51f431a2993cf4797f679c85671c028cf1862f1c07604740360a.png)

*PE/PNG/MP4/PDF pileup 示意图*

这个脚本是通用且即时的：

![PE/PNG/MP4/PDF pileup 示意图](https://assets.kitploit.com/production/public/readmes/47472/3ec7caeb459eab294c6b9876a8a82e136502c3d11c599804fd7925fc2d819276.png)

示例：[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)


由于你可能只能分发单个文件，
并且无法从中猜出其他前缀值，
一种解决方案是将碰撞的所有前缀嵌入 JavaScript 代码中，
并将其插入你的 PoC，
从而将你的文件变成 [HTML polyglots](https://github.com/decalage2/collisions/blob/HEAD/examples/polyglot.html)，以便轻松共享相关的碰撞文件。



《PoC or GTFO》的[第 19 期](https://github.com/angea/pocorgtfo#0x19)正是这样一个 pileup **兼** polyglot，
结合了使用 PDFLaTeX 生成的 80 页文档、一个 Windows PDF 查看器、
一个 PNG 示意图以及一段由 [KidMoGraph](https://www.kidmograph.com/) 制作的简短“碰撞”MP4 视频，
并带有一个 HTML 载荷，用于从 PDF 版本生成其他文件（还有一个 ZIP 归档）：



感谢 Rafał Hirsz 在 JavaScript 方面的长期帮助。


## 应用场景

最好彻底弃用 MD5，因为文件内部检查实在太耗时、太冒险了！


### 把它们全部碰撞吧！

即时、可复用且通用的碰撞的另一个用途，是将任何给定类型（比如 PNG）的文件隐藏在虚拟文件（或每次都相同的文件）后面——实际上只需在剥离签名后将其拼接到同一前缀即可——你甚至可以在库层面做到这一点！

从严格的解析视角来看，
你的所有文件都会显示相同的内容，
而那些邪恶的图像会被揭示为与之前收集的 MD5 相同的文件。

让我们取两个文件：

 ⟷


并用同一个 PNG 与它们碰撞。

它们现在显示相同的虚拟图像，并且在文件层面直到第二个图像之前完全一致！

 ⟷


它们的恶意载荷分别隐藏在一个具有相同 MD5 的文件后面。


### 可作为罪证的文件

碰撞的另一个用途是将某些可定罪的内容隐藏在无辜但令人想要的文件中：
如果收集证据的唯一方式是比较弱哈希，
那么你就无法否认自己没有另一个文件（该文件显示定罪内容，但隐藏了无辜内容）。

软件通常侧重于（快速）解析，而不是详细的文件分析。



*一张显示 EnCase Forensic 不同标签页下不同预览的图片*


## 失败情况

并非所有格式都能拥有可复用的通用前缀：
如果某种数据持有者无法被插入到魔数签名与每个文件特有且关键的标准头之间，
那么通用碰撞就不可能实现。

当然，仍然可以把旧文件变成新文件，
甚至使用代码分支到两个不同的载荷，
但这更像是移植载荷，而非碰撞文件结构。


### ELF



ELF 头必须位于偏移 0 处，并且从一开始就包含关键信息，例如 32 位/64 位、
字节序和 ABI，
因此在那些对原始文件特有且关键的参数之前，不可能先有通用前缀再放碰撞块。


### Mach-O



Mach-O 甚至对 32 位（`feedface`）和 64 位（`feedfacf`）使用不同的魔数。
紧接着是命令的数量和大小（例如段定义、symtab、版本等）。

与 ELF 一样，可复用碰撞是不可能的。


### Java Class



从魔数之后开始就是版本号（这可能很麻烦），
但常量池计数相当因文件而异，
因此无法对所有文件进行通用碰撞。

然而，许多文件仍具有相同的版本，我们可以将最短的常量池填充到最长计数。
首先，插入一个 *UTF8 字面量* 来对齐信息，
然后声明另一个字面量，并让 UniColl 滥用其长度（长度以 16 字节大端序存储）。

但这需要代码操作，因为所有池索引都会发生偏移。

Java Class 的即时 MD5 可复用碰撞应该是可能的，但需要代码分析和修改。


### TAR

**TL;DR** TAR 文件没有可复用碰撞，除了 chosen-prefix 之外没有其他策略。



Tape Archives 是一系列拼接的头和文件内容的序列，全部按 512 字节对齐。

整个文件没有中央结构，因此没有任何全局头或注释可以利用。

一个技巧是开始一个长度可变的虚拟文件，但长度始终位于同一偏移处，这与 UniColl 不兼容，这意味着这里只有 chosen-prefix 碰撞有用。


## 利用方式总结

格式        | 通用？ | 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 在数据方面存在一些限制，可通过操纵扫描编码在一定程度上改进。
2. 带 JPG 的 PDF 是 Shattered 攻击的[初始实现](http://shattered.io)，但它只是 PDF 文档中的纯 JPG 技巧。
3. PNG：Safari/Preview 要求 PNG 的 `IHDR` 块位于第一个槽位，即任何碰撞块之前。这样做会妨碍通用前缀，此时碰撞仅限于特定的尺寸、色彩空间、BPP 和隔行扫描。
4. 像 MP4 这样的 Atom/Box 格式可能对不同子格式使用相同前缀。JPEG2000 或 HEIF 等一些子格式需要额外整理，但利用策略是相同的——只是无法在子格式之间产生碰撞，只能为特定子格式使用一对前缀。
5. 使用 64 位长度时，Atom/Box 与 Shattered 兼容。
6. 某些基于 Zip 的格式可以被通用利用。
7. 为获得更好的兼容性，ZIP 需要两个 UniColl 才能生成完整归档，并且这些碰撞取决于两个文件的内容。

## 测试文件

[这里](https://github.com/decalage2/collisions/blob/HEAD/examples/free/README.md)有一些免费（无版权、无 PII）的测试碰撞对。


# 参考

论文：

- 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) 作者 Gregor "Greg" Kopf
  - [A PDF That Shows Its Own MD5](https://archive.org/stream/pocorgtfo14#page/n49/mode/1up) 作者 Mako
  - [This GIF shows its own MD5!](https://archive.org/stream/pocorgtfo14#page/n52/mode/1up) 作者 Kristoffer "spq" Janke
  - [This PDF is an NES ROM that prints its own MD5 hash!](https://archive.org/stream/pocorgtfo14#page/n55/mode/1up) 作者 Evan Sultanik, Evan Teran
- 2018：
  - [Easy SHA-1 Colliding PDFs with PDFLaTeX.](https://archive.org/stream/pocorgtfo18#page/n62/mode/1up) 作者 Ange Albertini
- 2020：
  - [SHA-1 is a Shambles](https://eprint.iacr.org/2020/014.pdf) 作者 Gaëtan Leurent, Thomas Peyrin

演示文稿：
- 2017 Black Alps 的 Exploiting Hash Collisions：
  - [幻灯片](https://speakerdeck.com/ange/exploiting-hash-collisions)
  
    [](https://speakerdeck.com/ange/exploiting-hash-collisions)
  
  - [视频](https://www.youtube.com/watch?v=Y-oJWEYKVLA)
  
    [![Exploiting hash collisions Youtube video](https://assets.kitploit.com/production/public/readmes/47472/c995bb115228391b655125ee5806530149829d3a62b8754485071f5db9512e67.jpg)](https://www.youtube.com/watch?v=Y-oJWEYKVLA)

- 2019 Pass the Salt 的 KILL MD5：
  - [幻灯片](https://speakerdeck.com/ange/kill-md5)

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

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


工作坊（CollTris）：
  - [幻灯片](https://speakerdeck.com/ange/colltris)

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

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

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

  - [材料](https://github.com/decalage2/collisions/blob/HEAD/workshop/README.md)

  - 场次
    - 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 任务：
- [Prudentialv2](https://ctftime.org/task/3453)，来自 *Boston Key Party CTF 2017*。
- [HREFIN](https://ctftime.org/task/6965)，来自 *Google CTF 2018*。
- [Looking glass](https://ctftime.org/task/9271)，来自 *Dragon Sector Teaser CTF 2019*。

<!-- - [Not my digest](https://ctftime.org/task/4784) 来自 *Hack.lu CTF 2017*：与碰撞无关，但由 Marc 本人解决 :p -->
这类 CTF 任务的一个共同挑战是，不能因每个玩家可用的计算能力差异而给出过大优势或劣势。


# 致谢

这一切都要感谢 [Marc Stevens](https://marc-stevens.nl/research/)，
不仅因为他在密码学上的贡献，还因为他长期以来的帮助和建议！

也感谢 Philippe Teuwen 对文件格式的广泛反馈。


# 结论

**杀死 MD5！**

除非你主动检查文件中是否存在畸形或碰撞块，否则不要使用 MD5！

它不是密码学哈希，而是一个玩具函数！

collisions

最受欢迎