哈希冲突与利用

By Ange Albertini 和 Marc Stevens。

常见问题（TL;DR）

Q: 是否可以让一个文件获得任意的 MD2/MD4/MD5/MD6/SHA1/SHA2/SHA3 哈希值，或者与另一个文件相同的哈希值？
A: 不可以。

Q: 能否创建两个具有相同哈希值的文件？
A: 使用 MD5，在标准计算机上几秒钟内即可实现。使用 SHA1，是可能的，但对最终用户来说并不实用（复杂度：2^61.2 价格：$11k）。

Q: 能否通过追加内容使两个不同的文件获得相同的哈希值？
A: 使用 MD5，在标准计算机上只需几个小时。使用 SHA1，是可能的，但对最终用户来说不切实际（复杂度：2^63.4 价格：4.5 万美元）

Q: 这 2 个文件是否仍然有效？
A: 一般来说，是的，因为大多数文件格式允许追加数据。另一方面，文件签名很可能会被破坏。

Q: Can one make 2 different files with arbitrary contents and the same hash?
A: Yes, it can be instant by relying on special file structures:

a special format header (or pair) with tricks, acting as a switch between 2 contents (some formats won't allow such tricks).
pre-computed collisions, based on the specific header(s).
two contents of specific formats, both presents after the collision (added after the computation).

Q: 我可以为哪些格式获取即时 MD5 碰撞文件对？
A: JPG, PNG, GIF, GZIP, Portable Executable, MP4, JPEG2000, PDF, DOCX/PPTX/XSLX, EPUB, 3MF, XPS。只需运行相应的脚本即可。

Q: SHA1 呢？
A: 对于 SHA1，PDF 中的 JPG 已计算并实现。

Q: 对于 MD5 已支持的格式（JPG、PNG 等），但针对 SHA1 的情况呢？
A: 它们很可能也支持 SHA1，但尚未计算其碰撞。

Q: 对于相似（但不同）的内容，计算速度会更快吗？
A: 不会。任何微小的差异都需要完整的计算。

Q: 哪些格式没有这种快捷方式？
A: ELF、Mach-O、Java Class、TAR、ZIP（以及其他...）

Q: 使用这些格式，经典碰撞（在几小时内）仍然可能吗？
A: 是的，只要允许附加任意数量的数据（即很可能不适用于 ZIP 或 Class）。

Q: 你们提供碰撞的示例吗？
A: 是的。

引言

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

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

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

状态

已知攻击的当前状态：

获取一个文件以得到另一个文件的哈希或给定的哈希：不可能
- 即使对于 MD2 或 MD4 来说，目前甚至也不切实际。
- 对于更简单的哈希(*) 可行
获取两个具有相同 MD5 的不同文件：即时
- 示例：1 ⟷ 2
使两个任意文件获得相同的 MD5：几小时（72 hours.core）
- 示例：1 ⟷ 2
使两个特定文件格式（PNG、JPG、PE...）的任意文件获得相同的 MD5：即时
- 阅读下文
获取两个具有相同 SHA1 的不同文件：6500 years.core
- 获取两个具有相同 SHA-1 的不同 PDF 以展示不同的情况：即时（前缀已经计算好）

(*) 使用 crypt 的示例 - 感谢 Sven！

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

攻击

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

如果两个内容 A 和 B 具有相同的哈希值，那么向两者追加相同的内容 C 后，哈希值将保持不变。

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
A	=	A
B	=	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 ⟷ 2

变体：存在单块 MD5 碰撞，但需要五周的计算时间。

这里有一个没有前缀的 FastColl 计算的录像以及一个带有前缀的另一个录像。

UniColl 允许您控制碰撞块中的几个字节，在第一个差异之前和之后，这使其成为一种具有某些可控差异的相同前缀碰撞，几乎就像选择前缀碰撞一样。这非常方便，而且更好的是差异可以非常可预测：在 m2+= 2^8（又名 HashClash poc_no.sh 脚本中的 N=1 / m2 9）的情况下，差异是第 9 个字节的 +1，这使得它非常容易被利用，因为您甚至可以在脑海中思考碰撞：该句子的第 9 个字符将被下一个字符替换：0 被 1 替换，a 被 b 替换..

time: 几分钟（取决于你想要控制的字节数量）
space: 两个块

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 的控制力不如真正的选前缀碰撞，但它快得多，尤其是因为它只需要两个块。

这里有一段 UniColl 计算的录像。

Shattered (SHA1)

记录于 2013，计算于 2017。

time: 6500 年.CPU 和 110 年.GPU
space: 两个块

differences:

.. .. .. DD ?? ?? ?? ??
or
?? ?? ?? DD .. .. .. ..

exploitation: 中等。差异位于碰撞块的开头和结尾。因此，在前缀/后缀中，长度之前和之后都没有控制： PNG 在块类型之前存储其长度，因此它不起作用。然而，当 JP2 文件使用 JFIF 格式（与 JPG 相同）时，它将起作用，并且如果你使用 64 位长长度，MP4 和其他 atom/box 格式也可能起作用（在这种情况下，它们位于之后 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 使用了计算出的 SHA1 前缀，直接复用 PDFLaTeX 源文件中的图像（参见文章 18:10），同时也在 HTML 页面中通过 JavaScript 检查前缀的值（该文件是多语言文件，ZIP HTML 和 PDF）。

选定前缀碰撞

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

𝓐	≠	𝔅
碰撞 A	≠	碰撞 B

取两个任意前缀
将较短的填充至与较长的相同长度。两者都填充到下一个块 - 减去 12 字节

这 12 字节的随机数据将添加到两侧以随机化生日搜索

将计算并附加 X 个近碰撞块。

块数越少，计算时间越长。

例：一个块需要 400 千小时。使用 HashClash 九个块需要 72 小时·核。

前缀碰撞无所不能，但仅针对一对文件就可能耗时很长。

HashClash (MD5)

最终版本发布于 2009。

示例：让我们碰撞 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 个块。

每个块具有与 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

但即使 Shattered 比 FastColl 更容易利用，碰撞块差异的约束条件也无关紧要，因为 Shambles 是一种选定前缀碰撞（Chosen Prefix Collision）。

攻击总结

Hash	Name	Date	Duration	Prefix type	Control near diff
MD5	FastColl	2009	2s	Identical	none

 | UniColl   | 2012 | 7-40min  | Identical   | 4-10 bytes
 | HashClash | 2009 | 72h      | Chosen      | n/a
 |           |      |          |             |

SHA1 | Shattered | 2013 | 6500yr | Identical | prefix & suffix | Shambles | 2020 | ? | Chosen | n/a

利用

相同前缀碰撞通常被视为（非常）有限，而选定前缀碰撞则耗时较长。

另一种方法是通过相同前缀攻击（如 UniColl）或选定前缀攻击来构造可重用的前缀，以克服某些限制——但将该前缀对与两个有效载荷组合使用，类似于经典的相同前缀攻击。

一旦前缀对计算完成，使两个内容发生碰撞便瞬间完成：只需根据特定的文件格式调整文件数据，使其符合文件格式规范以及预计算前缀的要求即可。

标准策略

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

JPG

理论限制与变通方法：

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

<img alt='comments over each image segments' src=pics/jpgcom1.png width=500/>

每段图像上的注释

注释蹦床的工作原理

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

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

使用脚本：

21:07:35.65>jpg.py Ange.jpg Marc.jpg

21:07:35.75>

示例：

自定义扫描

2 个 MD5 碰撞的 JPG

以下是一个 JPEGTran 扫描定义示例，用于将一张 1944x2508 的 RGB 图像转换为 100% 的 JPG，包含 20 个扫描，且全部大小在 64kb 以内。

// <component>: <minbyte>-<maxbyte>, <minbit>, <maxbit>;

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

使用脚本：

19:27:04.79>png.py nintendo.png sega.png

19:27:04.87>

示例：

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

这里有一段整个操作的录屏。

a recording of a universal (abusive) PNG collision

不兼容性

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

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

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

这里有一个脚本，用于使任意一对此类文件发生碰撞，并在需要时启动 UniColl 来计算前缀对。

示例：

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

以下是调用 UniColl 时整个操作的录制，

a recording of PNG UniColl collision

以及另一个当前缀已经被计算时。

a recording of precomputed PNG collision

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

这里有一段完整操作的录像。

a recording of a GIF FastColl collision

GZIP

GZIP 规范 v4.3：RFC 1952 (1996)。

一个 Gzip 文件由一个或多个 'members'（gzip 流）拼接而成。它们都会被解压，其未压缩内容会相互追加——即使某个 member 的未压缩内容为空。
这些 members 之间可以用零分隔。零会被直接跳过，文件开头除外。任何非空字节都会被检查其签名 1F 8B。如果不匹配签名，解析将停止，这可以用于在两个 payload 之间强制停止解析，但会触发一些可能导致问题的警告。另一种策略是在文件末尾添加一个额外的空 member，并让两个 payload 的解析都在那里结束——在 member 上或其 body 上。
可选的 filename 和 file comment 以 null 结尾，而 Extra field 由 size16 定义，因此可被滥用。它由一个或多个子字段组成，每个子字段有一个 ID 及其自身的子长度，但子字段并非强制要求——官方定义的非常少。

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

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

在 member 的头部之后是其压缩 body、其 CRC32 及其未压缩大小（非强制）。因此，一个带有其 null CRC32 和大小的空数据 body 构成了一个通用的 postwrap，甚至可以由不同的 member 头部共享。

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

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

.tar.gz 仅仅是 tar 归档的 gzip 归档。与 tar 本身不同，它可以很好地与压缩的 tar 配合使用。

示例：collision1.tar.gz (Pacome) ⟷ collision2.tar.gz (Reg)

LZ4 / Zstandard

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

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

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

示例：

Portable Executable

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

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

因此策略是：

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

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

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

示例：tweakPNG.exe (GUI) ⟷ fastcoll.exe (CLI)

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

MP4 及其他

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

如果长度为零，则该 atom 占据文件的剩余部分 - 例如 JP2 文件中的 jp2c atoms。如果长度为 1，则 Type 后跟一个 64 位长度，将 atom 更改为 Type Length Value，使其与其他碰撞（如 Shattered）兼容。

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

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

第一个 atom 类型通常是 ftyp，这有助于区分实际的文件格式。

该格式相当宽松：只需链接 free atoms，利用 UniColl 滥用其长度，然后跳过第一个 payload。

对于 MP4 文件，唯一需要添加的是调整 stco（Sample Table - Chunk Offsets）或 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

☀️ ⟷ 🌙

how it should look (but your markdown doesn't render video tags)

请注意，某些查看器（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 并在不同位置显示它，例如在多页文档中。

示例：the Shattered paper, modified ⟷ the Shattered paper, original

使用在两个位置发生碰撞的 JPG 来粉碎纸张

基于 MD5 的 PDF 碰撞

借助 MD5（以及其他碰撞模式），我们可以在文档层面实现 PDF 碰撞，对两个文件均无任何限制！

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

这个（有效的）PDF

%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>>

等价于：

%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 表中也有官方的方法来跳过编号。

因此在同一个文件中存储两个文档树是没问题的。我们只需要让根对象指向这两个文档中的任意一个根对象即可。

因此我们只需要获取两个文档，重新编号对象和引用，以确保没有重叠，构造一个碰撞，使得作为 Root 对象引用的元素编号可以在保持相同哈希值的情况下被更改，这非常适合使用 N=1 的 UniColl，并相应地调整 XREF 表。

这样，我们就可以安全地碰撞任意一对 PDF，无论其页数、尺寸、图像如何……

comments

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 结构，因此需要前缀碰撞来修改包含流对象外部的结构。

colliding text

第一种情况使得展示 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 ⟷ poeMD5 B

一件真正的加密艺术创作 :)

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

碰撞的文档结构

无论你使用 UniColl 作为内联注释还是作为 dummy stream 对象中的选定前缀，策略都是相似的：打乱对象编号，然后让 Root 对象指向不同的对象，因此与 Shattered 不同，这意味着在文档级别上任意一对 PDF 都能立即发生碰撞。

一个有用的技巧是 mutool clean 的输出是可靠可预测的，因此它可以用于规范化输入的 PDF，并在保持文件重要部分不变的情况下修复合并后的 PDF。 MuTool 不会丢弃无效的键/值 - 除非被要求，并且保持它们相同的顺序，因此使用诸如 /MD5_is /REALLY_dead_now__ 这样的假字典条目来可预测地对齐内容而无需另一种类型的注释是完美的。然而它不会保留字典中的注释（所以没有内联注释技巧）

一种轻松完成对象洗牌操作而不费力的方法就是合并两个 PDF 文件通过 mutool merge 然后将 /Pages 对象拆分为两部分。

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

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

示例：使用这个脚本，碰撞 Spectre 和 Meltdown 这两篇公开的 PDF 论文不到一秒：

示例：spectre.pdf ⟷ meltdown.pdf

可能的扩展：将 UniColl 块链接起来，以在原始源文件中保留 Root 对象中可引用的各种非关键对象对——例如 Outlines、Names、AcroForm 和 Additional Actions（AA）。

在 PDFLaTeX 中

上述技术仅需一对 PDF 文件即可工作，但也可以直接通过特定的 PDFTeX 运算符从 TeX 源文件进行操作。

您可以直接定义对象——包括用于对齐的虚拟键和值——并通过在 TeX 源文件的最开始处包含以下内容来定义空对象以预留一些对象槽位：

% 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 碰撞的示例：

If ⟷ Shattered - the movie

2 使用以 JPG 格式存储图像数据的 SHA-1 碰撞 PDF

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

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

通过用作页面数据和要显示图像的 JPEG 实现两个 PDF 的 SHA-1 碰撞的示例：

Skulls & Crossbones ⟷ Golden Axe

2 使用 JPG 作为图像和页面内容的 SHA-1 碰撞 PDF

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 文件。

一个典型的中央目录结束记录，如果注释为空，则为 22 字节：

00: 504b 0506 0000 0000 0000 0000 0000 0000  PK..............
10: 0000 0000 0000                           ......

如果我们使用此作为 UniColl 和 N=2 的前缀（将前缀填充到 16 位），差异位于第 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..(

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 的文件进行碰撞）。

步骤：

将来自两个来源的两组文件放入同一归档中 - 即放入不同的子目录中。
修改根文件以交替指向每一组文件。
由于根文件的时间戳、长度和 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 碰撞。

需求摘要

两个或更多前缀
一个或多个文件类型（多态文件可无问题地工作）
一个具有固定文件名、文件长度和 CRC 的 XML 根文件：此信息在碰撞块之前和之后各出现一次
内容为任意 XML
可以通过填充，甚至通过 XML 注释，来达到相同的长度。
可以为每个内容设置 CRC（通过 CrcHack）。
两组文件共存于后缀中，可能位于不同的目录中。某些工具硬编码了路径，这可能会降低兼容性。
可能需要合并一个 Content type XML 文件以涵盖所有文件，包括受支持和不受支持的文件（碰撞块和备用文档）

示例

CRC32

一个最小的 XML 注释（仅 ASCII），使用 CrcHack 伪造 CRC32（即时计算）。

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。

echo "<!--THISKINDOFCRCISREALLYIMPRESSIVEA-->" | crchack.exe -b 4:+.8*32:.8 - 0xcafebabe
<!--THIskInDoFCRcIsrEALlyimpRESSIVea-->

碰撞

zInsider 是一个脚本，用于利用以下 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

要生成您自己的碰撞前缀，这里有一个脚本用于生成根 zip 对。在计算碰撞后，使用另一个脚本将这些根对与公共后缀组合。

一些碰撞 PoC：

Office Open XML: Excel (1 - 2), Powerpoint (1 - 2), Word (1 - 2).
Open Container Format: Epub (1 - 2).
Open Packaging Conventions: 3MF (1 - 2), XPS (1 - 2).

一些基于 Zip 的多文件格式无法被通用利用：

Quake PK3: 一个没有特定根的文件 zip。
Open Document Format: META-INF/manifest.xml 文件必须提及每个其他文件，因此它不能是通用的。
APK, JAR, XPI: META-INF/MANIFEST.mf 文件也必须提及每个其他文件，及其哈希值。

感谢 Philippe Lagadec 在 Office 文件格式方面提供的帮助！

其他

Wasm，通过自定义 section：script，示例：md5-1.wasm ⟷ md5-2.wasm

不常见的策略

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

MultiColls：多重碰撞链

没有什么能阻止将多个碰撞块串联起来，并拥有超过两个具有相同哈希值的内容。一个例子是哈希回文——它们展示了自身的 MD5 值。 PoCGTFO 14 文件包含 609 个 FastColl 碰撞，通过在同一个文件中通过两种文件类型来实现这一点。

哈希诗

Hashquines 是显示其自身哈希值的文件。相关内容见此处。

有效性

另一种策略是破坏文件类型，以损坏文件的形式绕过扫描。仅仅覆盖魔术签名就足够了。将两个文件（无论有效或无效）追加到一个不需要位于偏移量 0 处的格式（如 ZIP/RAR/... 等归档格式）中，会暴露出另一种文件类型。

这允许在不使用选定前缀碰撞的情况下实现多语言碰撞：

使用 UniColl 启用或禁用魔术签名，例如 PNG：
追加一个 ZIP 归档

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

示例：

<img alt='valid image' src=examples/png-valid.png width=300/> ⟷ 无效

PolyColls：不同文件类型的冲突

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

Attack scenario:

send holiday.jpg
get it whitelisted
send evil.exe, which has the same MD5.

在这些情况下，如果两种文件格式都需要从偏移量 0 开始，则必须发生前缀冲突。

多列布局的一些示例：

pdf-jpg polyglot collision

PDF/JPG 多联

pe-png polyglot collision

PE/PNG polycoll

PE - JPG

由于 PE 头通常小于 0x500 字节，它非常适合用作 JPG 注释：

以 DOS/JPG 头开始
JPEG 注释跳过 PE 头
放置完整的 JPG 图像
放置完整的 PE 规范

同样，碰撞是 instant

示例：fastcoll.exe ⟷ Marc.jpg

PDF - PE

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

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

这里有一个 script，例如，可以立即让 PDF 查看器（Sumatra 轻量且独立）和 PDF 文档发生碰撞：

示例：Poster.pdf ⟷ Sumatra.exe

a PDF viewer showing a PDF (itself showing a PDF) with the same MD5

a PDF viewer showing a PDF (itself showing a PDF) with the same MD5

PDF - PNG

同样地，例如可以碰撞任意 PDF 和 PNG 文件，且对两侧均无限制。这是即时、可复用且通用的。

示例：Hello.pdf ⟷ 1x1.png

PileUps (multi-collision)

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

正如 2008 年的 Nostradamus 实验所示，链式碰撞使得碰撞两个以上的文件成为可能。

第一个碰撞可以是相同或 chosen-prefix，后续的必须是 chosen-prefix。

你可以称之为 multi-collisions，我更喜欢 pileups - 更简短 :)

PE - PNG - MP4 - PDF

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

diagram of a PE/PNG/MP4/PDF pileup

PE/PNG/MP4/PDF 堆积示意图

此脚本通用且即时：

diagram of a PE/PNG/MP4/PDF pileup

示例：commodore.pdf ⟷ diagram.png ⟷ kidmo.mp4 ⟷ sumatra18.exe

由于你可能只能分发单个文件且无法从中猜测其他前缀值，一种解决方案是将碰撞的所有前缀嵌入 JavaScript 代码中并将其插入到你的 PoCs 中，将你的文件转换为 HTML polyglots 以便轻松分享相关的碰撞文件。

《PoC or GTFO》第 19 期] 就是这样一堆 and 多语言混杂的内容，结合了使用 PDFLaTeX 生成的 80 页文档、一个 Windows 平台的 PDF 查看器、一张 PNG 图表以及一段由 KidMoGraph 制作的简短“碰撞” MP4 视频，并附带一个 HTML 载荷，用于从 PDF 发布版生成其他文件（还有一个 ZIP 压缩包）：

感谢 Rafał Hirsz 在 JavaScript 方面提供的持续帮助。

用例

最好彻底弃用 MD5，因为文件内省既耗时又风险过高！

必须全部碰撞！

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

从严格的解析角度来看，你所有的文件都将显示相同的内容，而恶意图像将表现为一个具有先前收集的相同 MD5 值的文件。

让我们取两个文件：

并与同一 PNG 进行碰撞。

它们现在显示相同的占位图像，并且在文件级别上，直到第 2 张图像之前完全相同！

他们的恶意载荷隐藏在具有相同 MD5 的文件之后。

有罪证据文件

碰撞的另一个用例是在无害但令人向往的内容中隐藏有罪证据，但如果收集证据的唯一方法是比对弱哈希值，那么你就无法否认你不拥有另一个文件（显示有罪证据内容但隐藏无害内容）。

软件通常专注于（快速）解析，而非详细的文件分析。

一张展示 EnCase Forensic 不同选项卡下不同预览的图片

失败案例

并非所有格式都能拥有可重用的通用前缀：如果某种数据容器无法插入到魔数签名与对每个文件至关重要且特有的标准头部之间，那么通用碰撞就不可能发生。

当然，人们仍然可以将旧文件转换为新文件，甚至使用代码分支到两个不同的有效载荷，但这更像是移植有效载荷，而非碰撞文件结构。

ELF

ELF 头部必须位于偏移量 0 处，并在起始处包含诸如 32b/64b、字节序和 ABI 等关键信息，因此不可能在特定于原始文件的关键参数之前拥有通用前缀，然后是碰撞块。

Mach-O

Mach-O 甚至不会以相同的魔数开头来区分 32 位（feedface）和 64 位（feedfacf）。紧随其后的是命令的数量和大小（例如段定义、符号表、版本等）。

与 ELF 类似，可重用的冲突是不可能的。

Java Class

从一开始，魔数处存放的是版本号（这可能带来麻烦），但常量池计数对于每个文件来说都相当特定，因此不存在适用于所有文件的通用碰撞。

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

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

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

TAR

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

磁带归档是一系列拼接的头部和文件内容，全部对齐到 512 字节。

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

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

利用总结

格式	通用？	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 (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

JPG 对可改进的数据存在一些限制，可以通过操作扫描编码在一定程度上加以改善。
包含 JPG 的 PDF 是 Shattered 攻击的初始实现，但这仅仅是 PDF 文档中纯粹的 JPG 技巧。
PNG：Safari/Preview 要求 PNG 的 IHDR 块必须位于第一个槽位，在任何碰撞块之前。这样做会阻止使用通用前缀，在这种情况下，碰撞仅限于特定的尺寸、色彩空间、BPP 和隔行扫描。
像 MP4 这样的 Atom/Box 格式可能允许不同的子格式使用相同的前缀。某些子格式（如 JPEG2000 或 HEIF）需要额外的整理，但利用策略是相同的——只是子格式之间不可能发生碰撞，仅针对特定子格式的前缀对才可能发生碰撞。
当使用 64 位长度时，Atom/Box 与 Shattered 兼容。
某些基于 Zip 的格式可以被通用利用。
为了获得更好的兼容性，ZIP 需要两个 UniColl 才能构成一个完整的归档，并且这些碰撞取决于两个文件的内容。

测试文件

这里是免费的（无版权、无个人身份信息）测试碰撞对。

检测

检测文件中的哈希碰撞有多种方法。

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

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

文件结构：在块边界处分析文件，如果你注意到高熵块以及可能相同的前缀/后缀，你可能能够判断它使用的是哪种碰撞，但这非常容易出错。在选定前缀碰撞的情况下，可能根本无法发现，因为除了大部分碰撞块之外，两个文件可能大部分都不同。
哈希计算：使用 Marc Stevens 的 DetectColl 的实现（C 或 Go）（参见他的 Counter-cryptanalysis 论文）。它只需要一个文件，但要求碰撞处于工作状态（确切的前缀及其对应的碰撞块），并且速度很慢。

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

签名

为简化起见，你可以使用此脚本解析 Detectcoll 的输出，并将其与[已知签名](https://github.com/corkami/collisions/blob/7f7876c431614f33f765bfc1cb62506b476