哈希碰撞与利用

作者：Ange Albertini 与 Marc Stevens。

常见问题（TL;DR）

问：能否让一个文件获得任意的 MD2/MD4/MD5/MD6/SHA1/SHA2/SHA3 哈希，或者与另一个文件相同的哈希？
答：不能。

问：能否创建两个哈希相同的不同文件？
答：对于 MD5，在标准计算机上只需几秒钟。对于 SHA1，这可行，但对最终用户而言并不实用（复杂度：2^61.2 成本：1.1 万美元）。

问：能否通过附加数据让两个不同文件获得相同哈希？
答：对于 MD5，在标准计算机上只需几小时。对于 SHA1，这可行，但对最终用户而言并不实用（复杂度：2^63.4 成本：4.5 万美元）

问：这两个文件仍会保持有效吗？
答：一般来说是的，因为大多数文件格式都能容忍附加数据。但另一方面，文件签名很可能会失效。

问：能否制作两个内容任意但哈希相同的不同文件？
答：可以，借助特殊的文件结构可即时实现：

一个带有技巧的特殊格式头部（或一对头部），充当两种内容之间的开关（某些格式不允许此类技巧）。
基于特定头部预计算的碰撞。
两个特定格式的内容，均位于碰撞之后（在计算后追加）。

问：我可以为哪些格式获取即时 MD5 碰撞文件对？
答：JPG、PNG、GIF、GZIP、可移植可执行文件、MP4、JPEG2000、PDF、DOCX/PPTX/XSLX、EPUB、3MF、XPS。只需运行对应的脚本即可。

问：那 SHA1 呢？
答：对于 SHA1，PDF 中的 JPG 已计算并实现。

问：那已经支持 MD5 的格式（JPG、PNG……）换成 SHA1 呢？
答：它们很可能同样支持 SHA1，但相应的碰撞尚未被计算出来。

问：对于相似（但不同）的内容，计算会更快吗？
答：不会。任何微小的差异都需要一次完整的计算。

问：哪些格式没有这种捷径？
答：ELF、Mach-O、Java Class、TAR、ZIP（以及其他一些……）

问：这些格式仍能产生经典碰撞（几小时内）吗？
答：可以，只要容忍任意数量的附加数据（也就是说，ZIP 或 Class 很可能不行）。

问：你们提供碰撞示例吗？
答：提供。

简介

目标是广泛探索现有的攻击方式——并在此过程中展示 MD5 有多么脆弱（任何 JPG、PNG、PDF、MP4、PE……都能即时碰撞）—— 同时深入探索常见文件格式，以确定它们如何被现有或未来的攻击所利用。

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

本文档并非关于新攻击（最新的攻击于 2012 年被记载），而是关于现有攻击的新利用形式。

状态

已知攻击的当前状态：

让一个文件获得另一个文件的哈希或指定哈希：不可能
- 即使对 MD2 或 MD4 而言也依然不现实。
- 对更简单的哈希有效(*)
让两个不同文件获得相同 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)

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

这些差异被滥用来构造具有特定属性的合法文件。

文件格式也是自上而下工作的，且大多数按字节级块（chunk）处理。

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

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

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

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

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

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

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

虚拟块（dummy chunks）——用作注释
存在多个注释
巨大的注释（长度：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 ..
.. .. .. .. .. .. .. .. .. .. .. .. .. .. .. ..

利用：困难

这些差异不在块的起始/结束位置附近，因此很难利用，因为你无法控制任何邻近的字节。一个潜在的解决方案是暴力破解周围的字节——参见 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

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

**Variant**: there is a [single-block MD5 collision](https://marc-stevens.nl/research/md5-1block-collision/) but it takes five weeks of computation.

Here is a [recording](https://github.com/corkami/collisions/blob/master/examples/fastcoll.svg) of a FastColl computation without any prefix
and [another one](https://github.com/corkami/collisions/blob/master/examples/fastcoll-prefix.svg) with a prefix.


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

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

[UniColl](https://github.com/cr-marcstevens/hashclash#create-you-own-identical-prefix-collision) lets you control a few bytes in the collision blocks,
before and after the first difference, which makes it an identical-prefix collision with some controllable differences, almost like a chosen-prefix collision.
This is very handy, and even better the difference can be very predictable:
in the case of `m2+= 2^8` (a.k.a. `N=1` / `m2 9` in HashClash [poc_no.sh](https://github.com/cr-marcstevens/hashclash/blob/master/scripts/poc_no.sh#L30) script),
the difference is +1 on the 9th byte, which makes it very exploitable,
as you can even think about the collision in your head:
the 9th character of that sentence will be replaced with the next one: `0` replaced by `1`, `a` replaced by `b`..

- time: a few minutes (depends on the amount of byte you want to control )
- space: two blocks
- differences:   ```
   .. .. .. .. DD .. .. .. ..
   .. .. .. .. +1 .. .. .. ..

exploitation: 非常简单 - 差异前后的字节可控，且差异是可预测的。唯一的限制是对齐，以及你“只能”控制差异之后的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 collision 控制力弱，
但速度要快得多，尤其是因为它只需要两个块。

这里是一个 UniColl 计算的[录制](https://github.com/corkami/collisions/blob/master/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 将长度存储在 chunk 类型之前，因此这种方法行不通。但是，对于使用 JFIF 形式（与 JPG 相同）的 JP2 文件，它是可行的，并且很可能也适用于 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 源码中复用图像（参见 [article 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 核时。



选择前缀碰撞非常强大，但即使仅针对一对文件，也可能花费很长时间。


### [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 是一种非常昂贵的 chosen-prefix 碰撞，使用 9 个块。

每个块都具有与 Shattered 相同的 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

But even if Shattered is much easier to exploit than FastColl,
the constraints of the differences in the collision blocks are irrelevant
since Shambles is a Chosen Prefix Collision.


## Attacks summary

哈希 | 名称      | 日期 | 持续时间 | 前缀类型 | 差异附近控制
---- | --------- | ---- | -------- | ----------- | -----------------
MD5  | FastColl  | 2009 | 2秒      | 相同       | 无
     | UniColl   | 2012 | 7-40分钟 | 相同       | 4-10 字节
     | HashClash | 2009 | 72小时   | 选择       | 不适用
     |           |      |          |             |                   |
SHA1 | Shattered | 2013 | 6500年   | 相同       | 前缀和后缀
     | Shambles  | 2020 | ?        | 选择       | 不适用


# 利用方式

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

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

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


## 标准策略

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


### JPG



理论限制与解决办法：
- 理论上，*Application* 段应紧跟在 *Start of Image* 标记之后。
  实际上，这并非必需，因此我们的碰撞可以是通用的：唯一的限制是最小图像的大小。
- 注释的长度存储在两个字节中，因此其可存储量仅限于 65536 字节（大约相当于 400x400 照片的大小）。
- 与其跳过整个 JPG 文件，不如将该文件拆分为多个段，并在段之间添加跳转蹦床（trampolines）。

  

  *每个图像段上的注释*

  

  *注释蹦床如何工作*

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

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

使用 [脚本](https://github.com/corkami/collisions/blob/master/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/corkami/collisions/blob/master/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 由 size16 定义，因此可被滥用。它由一个或多个子字段组成，每个子字段都有一个 ID 和自身的子长度，但子字段并不强制——官方定义的很少。

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

如果顶层文件太大而无法放入额外字段，则可以将其未压缩流拆分成更小的文件，直到它们都能放入额外字段。

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

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

这里有一个脚本，用于生成两个 GZip 文件的即时 MD5 碰撞。如果输入文件很大，它的大部分时间都花在解压和重新压缩数据上——碰撞前缀是预计算的。在不解压的情况下拆分成员是不可能的，因为需要计算未压缩的 CRC32。

.tar.gz 只是 tar 归档的 gzip 压缩版本。与 tar 本身不同，它可以很好地与 gzip 压缩的 tar 一起使用。

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

LZ4 / Zstandard

LZ4 和 Zstandard 是两种不同的压缩格式，整体结构相似：它们由帧组成，每帧以一个特定的魔数开头：Zstandard 帧为 0xFD2FB528，Lz4 帧为 0x184D2204。

它们还共享相同的‘可跳过’TLV 帧，以 4 字节魔数开头，范围在 0x184D2A50 - 0x184D2A5F 之间，然后是用户数据的长度（4 字节，小端序），最后是用户数据本身。这些帧完全可选、长度任意且可重复。文件可以以这些帧开头。因此，这些帧可以串联起来，构成一个完美的通用碰撞前缀，跨两种格式。

这里有一个脚本，用于生成两个 Zstd/Lz4 文件的即时 MD5 碰撞。与 Gzip 一样，无论内容如何，从外部都可以看到 2 个不同的归档：例如，.cpio.zst。

示例：

Portable Executable

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

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

因此策略是：

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

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

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

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

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

MP4 及其他

该格式的容器是一系列称为 Atoms 的 Length Type Value 块。长度是 32 位大端序，覆盖自身、类型和值，因此正常最小长度为 8 （类型是 4 个 ASCII 字符的字符串）。

如果长度为空，则该 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（Sample Table - Chunk Offsets）或 co64（64 位版本）表，因为它们是绝对（！）偏移量，指向 mdat 影片数据——而且它们实际上是被强制执行的！

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

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

示例（视频由 KidMoGraph 提供）：

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

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

⟷

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

JPEG2000

JPEG2000 文件通常以类似 MP4 的 Atom/Box 结构开头，然后最后一个 atom jp2c 通常一直到文件末尾（空长度），从这一点开始，它遵循 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 论文，原版

Shattered 论文在两个地方使用了碰撞 JPG

使用 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/corkami/collisions/blob/master/examples/poeMD5_A.pdf) ⟷ [poeMD5 B](https://github.com/corkami/collisions/blob/master/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__` 这样的假字典条目非常适合可预测地对齐内容，而无需另一种注释。
然而，它不会保留字典中的注释（所以没有内联注释技巧）

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

为了给这个对象腾出空间，只需在两个文档前面合并一个伪 PDF。

或者，创建一个对悬空数组的假引用
以防止垃圾回收删除第二组页面。


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

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



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

**在 PDFLaTeX 中**

之前的技术仅适用于一对 PDF 文件，
但也可以直接通过 TeX 源文件来实现
借助[特定的 PDFTeX 运算符](http://texdoc.net/texmf-dist/doc/pdftex/manual/pdftex-a.pdf)。

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

如果需要，别忘了规范化 PDFLaTeX 输出——例如使用 mutool： PDFLaTeX 很难跨发行版获得可重现构建——如有必要，你甚至可能希望在执行时挂钩时间以获得精确的哈希值。

PDF 中的 JPG

你可能以为 JPG 只是图像，但在 PDF 和某些 PDF 阅读器（非浏览器，如 Evince 和 Adobe Reader）中，它可以像任何其他嵌入式对象一样被用作页面内容，即嵌入在 JPEG 图像中。

要无损存储 JPEG 数据，请将其存储为 100% 灰度，然后使用单行/单列的图片，或将数据行重复 8 次（因为 JPEG 块是 8x8），这样你的数据就能无损存储，并被 PDF 页面引用。

使用 JPEG 页面数据（灰度图片渲染颜色）作为矢量页面内容，让两个 PDF 发生 SHA-1 碰撞的示例：

如果 ⟷ 电影《Shattered》

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

可以两次引用这个碰撞 JPG：一次无损地作为页面内容，同时它又引用自身作为要显示的有损图像。同样，要显示的图像为灰度，但页面内容可以通过 PDF 操作符渲染一些颜色。

图像顶部显示的是重复 8 次的页面内容。

使用 JPEG 作为页面数据和显示图片，让两个 PDF 发生 SHA-1 碰撞的示例：

骷髅与交叉骨 ⟷ 金斧

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 06` 可预测地改为 `.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..(

$34,000 / 年 - 高级检测与响应分析师``` 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 中的存档注释。

ZIP 碰撞示意图

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

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

基于 Zip 的格式

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

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

思路 : 使两组文件共存于同一个存档中，并指向其中任意一组文件。可以将通用根文件存储在文件的开头位置，而碰撞块则存储在文件内容之外、存档内部（由于碰撞具有极高的熵，无法利用 XML 或纯 ASCII 文件进行碰撞）。

步骤：

将来自两个来源的 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 碰撞。


### 要求摘要

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


### 示例

#### CRC32

一个仅限 ASCII 的最小 XML 注释，带有通过 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/corkami/collisions/blob/master/scripts/zinsider.py) 是一个脚本，可以使用以下 ZIP+XML 格式即时生成任意文档对的 MD5 碰撞：
- Office Open XML: docx / pptx / xlsx
- Open Container Format: epub
- Open Packaging Conventions:
  - 3D manufacturing format: 3mf
  - XML Paper Specification: xps / oxps

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

一些碰撞 PoC：
- Office Open XML: Excel ([1](https://github.com/corkami/collisions/blob/master/examples/free/md5-1.xls) - [2](https://github.com/corkami/collisions/blob/master/examples/free/md5-2.xls)), Powerpoint ([1](https://github.com/corkami/collisions/blob/master/examples/free/md5-1.pptx) - [2](https://github.com/corkami/collisions/blob/master/examples/free/md5-2.pptx)), Word ([1](https://github.com/corkami/collisions/blob/master/examples/free/md5-1.docx) - [2](https://github.com/corkami/collisions/blob/master/examples/free/md5-2.docx))。
- Open Container Format: Epub ([1](https://github.com/corkami/collisions/blob/master/examples/collision-1.epub) - [2](https://github.com/corkami/collisions/blob/master/examples/collision-2.epub))。
- Open Packaging Conventions: 3MF ([1](https://github.com/corkami/collisions/blob/master/examples/collision-1.3mf) - [2](https://github.com/corkami/collisions/blob/master/examples/collision-2.3mf)), XPS ([1](https://github.com/corkami/collisions/blob/master/examples/collision-1.xps) - [2](https://github.com/corkami/collisions/blob/master/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 文件格式方面的帮助！

### 其他

- Wasm，通过自定义节（section）：[脚本](https://github.com/corkami/collisions/blob/master/scripts/wasm.py)，示例：[md5-1.wasm](https://github.com/corkami/collisions/blob/master/examples/free/md5-1.wasm) ⟷ [md5-2.wasm](https://github.com/corkami/collisions/blob/master/examples/free/md5-2.wasm)

## 不常见的策略

碰撞通常涉及两个同类型的有效文件。

### MultiColls：多碰撞链

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

#### Hashquines

Hashquines 是显示自身哈希值的文件。相关介绍见[此处](https://github.com/corkami/collisions/blob/master/hashquines)。

### 有效性

另一种策略是破坏文件类型，使其作为损坏文件绕过扫描。
只需覆盖魔数签名就足够了。
将两个文件（无论有效或无效）追加一种格式，
该格式不需要位于偏移量 0（归档，如 ZIP/RAR/...），这样就会揭示另一种文件类型。

这可以在不使用选定前缀碰撞的情况下实现多语种（polyglot）碰撞：
1. 使用 UniColl 启用或禁用魔数签名，例如 PNG：
2. 追加一个 ZIP 归档

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

示例：

 ⟷ [invalid](https://github.com/corkami/collisions/blob/master/examples/png-invalid.png)

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

也可以让碰撞的两侧具有不同的类型以降低怀疑：

攻击场景：
1. 发送 `holiday.jpg`
2. 让它进入白名单
3. 发送 `evil.exe`，它与前者具有相同的 MD5。

在这些情况下，需要选定前缀碰撞，
如果两种文件格式都需要从偏移量 0 开始。

一些 polycoll 布局的示例：

![pdf-jpg 多语种碰撞](https://assets.kitploit.com/production/public/readmes/47471/3dcd55e877a4ce9c933bf1478d0a71ede85e129b9e746414d754ffabceabe463.png)

*PDF/JPG polycoll*

![pe-png 多语种碰撞](https://assets.kitploit.com/production/public/readmes/47471/63df55a15e7ca33153f352f13ba273604df6b1ae3e1e8838b601fea39de801e0.png)

*PE/PNG polycoll*

#### PE - JPG

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

同样，碰撞是[即时](https://github.com/corkami/collisions/blob/master/scripts/jpgpe.py)的

示例：[fastcoll.exe](https://github.com/corkami/collisions/blob/master/examples/jpg-pe.exe) ⟷ [Marc.jpg](https://github.com/corkami/collisions/blob/master/examples/jpg-pe.jpg)

#### PDF - PE

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

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

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

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

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

*一个 PDF 查看器显示一个 PDF（其自身也显示一个 PDF），两者具有相同的 MD5*

#### PDF - PNG

类似地，可以碰撞例如任意的 PDF 和 PNG 文件，且对两侧没有限制。这是即时、可重用且通用的。

示例：[Hello.pdf](https://github.com/corkami/collisions/blob/master/examples/png-pdf.pdf) ⟷ [1x1.png](https://github.com/corkami/collisions/blob/master/examples/png-pdf.png)

### PileUps（多碰撞）

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

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

第一个碰撞可以是相同的或选定前缀的，接下来的碰撞则必须是选定前缀的。

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

#### PE - PNG - MP4 - PDF

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

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

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

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

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

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

由于你可能只分发单个文件，
并且不可能从它猜出其他前缀值，
一种解决方案是将碰撞的所有前缀嵌入 JavaScript 代码中，
并将其插入你的 PoC 中，
将你的文件变成 [HTML polyglots](https://github.com/corkami/collisions/blob/master/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 payload，用于从 PDF 版本生成其他文件，
（以及一个 ZIP 归档）：



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

## 使用场景

最好是彻底放弃 MD5，因为文件内省（introspection）太过耗时且风险太高！

### 把它们全部碰撞！

即时、可重用且通用的碰撞的另一个用途是，将任意给定类型（比如 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 文件没有可重用的碰撞，除选定前缀外没有其他策略。



磁带归档（Tape Archives）是一系列连接的头和文件内容，全部按 512 字节对齐。

整个文件没有中央结构。因此没有可滥用的全局头或任何类型的注释。

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

## 利用方式总结

格式        | 通用？ | FastColl | UniColl | Shattered | HashClash / Shambles
--------      | -------- | :------: | :-----: | --------- | :-------:
PDF           | 是        |          | x       |           | x
JPG           | 是 (1)    |          | x       | x (2)     | x
GZ            | 是        |          | x       |           | x
PNG           | 是/否 (3)  |          | x       |           | x
MP4           | 是 (4)    |          | x       | x (5)     | x
PE            | 是        |          |         |           | x
ZIP-based (6) | 是        |          |         |           | x
              |          |          |         |           |
GIF           | 否        | x        |         |           | x
ZIP           | 否        |          | x (7)   |           | x
              |          |          |         |           |
ELF           | 否        |          |         |           | x
TAR           | 否        |          |         |           | x
Mach-O        | 否        |          |         |           | x
Class         | 否        |          |         |           | x

1. JPG 对数据有一些限制，可以通过操纵扫描编码在一定程度上改进。
2. 带 JPG 的 PDF 是 Shattered 攻击的[初始实现](http://shattered.io)，但它只是 PDF 文档中的一个纯 JPG 技巧。
3. PNG：Safari/预览要求 PNG 的 `IHDR` 块位于第一个槽位，即任何碰撞块之前。这样做会阻止通用前缀，在这种情况下碰撞仅限于特定的尺寸、色彩空间、BPP 和隔行扫描。
4. 像 MP4 这样的 Atom/Box 格式可能适用于相同前缀的不同子格式。一些子格式如 JPEG2000 或 HEIF 需要额外的整理，但利用策略是相同的——只是碰撞不能在不同子格式之间进行，只能针对特定子格式的一对前缀。
5. 使用 64 位长度时，Atom/Box 与 Shattered 兼容。
6. 一些基于 Zip 的格式可以被通用利用。
7. 为了更好的兼容性，ZIP 需要一个完整的归档需要两个 UniColl，并且这些碰撞依赖两个文件的内容。

## 测试文件

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

# 检测

有几种不同的方法可以检测文件中的哈希碰撞。

1. 两个文件：如果你有两个或更多内容不同但哈希相同的文件，直接对它们进行 diff 即可！

然而，如果你只有一个文件，可能很难判断该文件是否包含哈希碰撞。

2. 文件结构：在块边界处分析文件，如果你注意到高熵块以及可能相同的前缀/后缀，你或许能判断它使用了哪种碰撞，但这非常容易出错。对于选定前缀碰撞，可能无法察觉，因为除了大部分碰撞块之外，两个文件可能大部分都不同。

3. 哈希计算：使用 Marc Stevens 的 DetectColl 的一种实现（[C](https://github.com/cr-marcstevens/hashclash/tree/collisiondetection/src/collisiondetection) 或 [Go](https://github.com/therealmik/detectcoll)）（参见他的 [Counter-cryptanalysis](https://marc-stevens.nl/research/papers/C13-S.pdf) 论文）。它只需要一个文件，但要求碰撞处于可用状态（确切的前缀及其对应的碰撞块），而且速度较慢。

DetectColl 会给出碰撞本身的技术信息，并在发生碰撞的哈希旁边显示 `*coll*`。

## 示例

以 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

安全哈希

由于 DetectColl 可以识别用于哈希碰撞的块，因此它可以通过安全哈希来缓解碰撞：如果检测到碰撞块，它会重新处理该块以破坏碰撞属性。因此，DetectColl 能够通过相同的哈希函数区分不同的内容，尽管文件中存在碰撞。

简言之：

对于没有碰撞的文件，安全哈希值等于标准哈希值。
对于存在碰撞的文件，安全哈希值不同，而且对于不同的文件内容，安全哈希值也会不同，尽管存在碰撞。

以 Wang 在 2005 年的原始碰撞为例：``` $ md5sum wang* 79054025255fb1a26e4bc422aef54eb4 *wang1.bin 79054025255fb1a26e4bc422aef54eb4 *wang2.bin

这些文件的安全 MD5：```
$ detectcoll wang1.bin | grep coll
*coll* ff531291d102a41aa131e0e09f64ca60 wang1.bin

我们提供全面的数据恢复服务，可帮助恢复您的``` $ detectcoll wang2.bin | grep coll coll 6a8e7124724d5c819401afc202a4fbd0 wang2.bin

## 签名

为简单起见，您可以使用此[脚本](https://github.com/corkami/collisions/blob/master/scripts/logparse.py)解析 Detectcoll 输出，并使其更轻松地与[已知签名](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

多重碰撞

安全哈希的一个小缺点是它们无法检测同一文件中的多个碰撞，但 DetectColl 仍然可以使用“标准”哈希检测碰撞。

以 PoCorGTFO 0x14（一个带有备用封面图片的 NES+PDF hashquine）为例。

安全哈希只能找到一个碰撞：``` $ 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

不安全的哈希可找出全部：```
$ detectcoll_unsafe pocorgtfo14.pdf | grep Found | wc -l
609

如果你检查最后几次碰撞：``` $ 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:

你可以注意到，最后一张与前几张并不那么接近：
这是因为前几张属于同一个图像文件（用于 hashquines），
而最后一张则是用于备用封面。


# 参考资料

论文（关于文件格式利用）：

- 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/master/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)
  
    [![利用哈希碰撞的 YouTube 视频](https://assets.kitploit.com/production/public/readmes/47471/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 视频](https://assets.kitploit.com/production/public/readmes/47471/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/corkami/collisions/blob/master/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) from *Hack.lu CTF 2017*: not related to collisions, but solved by Marc himself :p -->
这类 CTF 题目面临的一个常见挑战是，不要根据每位玩家可用的计算能力而给予过大的优势或劣势。


# 致谢

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

同样感谢 Philippe Teuwen 在文件格式方面提供的广泛反馈。


# 结论

**干掉 MD5！**

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

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

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

collisions

最受欢迎