实现更快的SHA-1碰撞检测

# 求解更快的 SHA-1 碰撞检测 —— sam reis 来源: https://sam.dev/blog/faster-sha1-collision-detection **摘要:** 我发现检测碰撞的 SHA-1 速度很慢，于是决定自己构建一个。`sha1dc` (https://crates.io/crates/sha1dc) 是一个重写的带有碰撞检测功能的 SHA-1，其代码生成器使用求解器将碰撞检测测试适配到 SIMD 通道中。它的运行速度达到普通 SHA-1 的 68-81%，而现有的 crate 仅能达到 28-29%，并且能使 git 打包验证的速度翻倍。 ## Git 如何使用 SHA-1 以及为何它必须更慢 (https://sam.dev/blog/faster-sha1-collision-detection#how-git-uses-sha-1-and-why-it-has-to-be-slower) 在参与开发 Enroute (https://github.com/enroute-sh/enroute) 的过程中，我目前正深入优化 git 服务器后端的性能。git 服务器经常做的一件事是接收来自 git 客户端的打包文件。这些打包文件是不受信任的输入，必须进行验证，其中包括检查所含 git 对象的 SHA-1 哈希值。 我使用的是 `gitoxide` (https://github.com/gitoxidelabs/gitoxide)，事实证明，打包验证可能相当慢。在我的 M4 上验证一个裸 `git/git` (https://github.com/git/git) 克隆的打包文件（421,292 个对象，压缩后 305 MiB，解压后 7.7 GiB）需要 12.5 秒，其中 **84%** 的时间花费在 SHA-1 上。 底层它使用了一个名为 `sha1-checked` 的 crate，这是一个带有碰撞检测功能的 SHA-1 库，在该机器上的运行速度约为 900 MiB/s。相比之下，普通 `sha1` 使用 M4 的 SHA-1 硬件指令时，速度约为 3 GB/s。 *Apple M4 上的碰撞检测开销。sha1 crate 哈希速度为 2979 MiB/s，sha1-checked 为 856 MiB/s，是普通 SHA-1 的 29%。git/git 的单线程打包验证耗时 12.55 秒，其中 84% 用于带检测的 SHA-1；按照吞吐量比例拆分，哈希本身约 3.0 秒，碰撞检测约 7.5 秒（占运行时间的 60%），此外 zlib 耗时 1.4 秒，其他一切耗时 0.6 秒。* 等等，碰撞检测？是的：使得 SHA-1 对于不受信任的输入难以处理的原因在于，它已知在密码学上已被破解，因为选定前缀碰撞是可行的 (https://sha-mbles.github.io/)。理想情况下，我们当然都会使用 SHA-256 来存储我们的 git 对象，但是迁移…… 幸运的是，可以通过检测 SHA-1 状态空间中那些人为制造的碰撞来缓解这一安全问题，git 正是在这样做。采用这种方法时，当 git 服务器检测到碰撞，它会拒绝接受来自客户端的这些对象。 不幸的是，这显然相当慢！因此，我着手看看能否使其更快，并改进带碰撞检测的 SHA-1 的性能。 ## 低垂的果实 (https://sam.dev/blog/faster-sha1-collision-detection#low-hanging-fruit) 首先，我仔细研究了 `sha1-checked`，并发现了一些可以立即改进的地方：它在检测路径上没有硬件加速。现代 `arm64` 和 `x86_64` CPU 拥有 SHA-1 指令，我原本以为它会尝试使用它们。 然而，这里硬件指令的难点在于，碰撞检测依赖于内部的 SHA-1 消息调度和哈希状态，而硬件指令使得访问这些状态变得困难。 我所做的修改是，在消息扩展时将调度结果溢出到缓冲区，通过硬件执行快乐路径，只对少数看起来可疑的块回退到标量重计算。这在两种架构上都将吞吐量大致翻倍：Apple Silicon 上从 928 → 1996 MB/s，在带有 `sha_ni` 的 AMD EPYC 上从 ~300 → ~640 MB/s。 当时，我将此整理为一个针对 `sha1-checked` 的拉取请求 (https://github.com/RustCrypto/hashes/pull/910)，该请求目前仍然开放，等待 `0.11` 版本发布后再进行审查。 但随后我开始好奇我们还能做到多好。 ## 常量之墙 (https://sam.dev/blog/faster-sha1-collision-detection#the-wall-of-constants) 解决了这个简单的修复后，下一个瓶颈很快显现。 根据我目前对代码的理解（我们稍后会讲到理论），碰撞检测需要对每个块做两件事。首先运行一个廉价的过滤器：大约 150 个针对扩展消息各个比特的测试，每个测试排除一些已知的攻击模式。过滤器为每个模式保留一个比特位的掩码，并在测试失败时清零相应比特。然后，仅当掩码仍非零时，才会进行昂贵的块重计算，以最终确定问题。 在普通数据上，大约 95% 的块通过过滤器后掩码为空，因此重计算几乎从不执行。如果没有过滤器，哈希速度将慢到约 40 MiB/s，而过滤器本身正是碰撞检测 SHA-1 在普通 SHA-1 之外花费时间的地方。 然而，这里有个问题。以下是 `sha1-checked` 中的代码片段，看起来像是原始 C 代码（由其背后研究论文的数据文件生成）的或多或少直接翻译： ``` mask &= (((w[44] ^ w[45]) >> 29) & 1).wrapping_sub(1) | !(DV_I_48_0_BIT | DV_I_51_0_BIT | DV_I_52_0_BIT | DV_II_45_0_BIT | DV_II_46_0_BIT | DV_II_50_0_BIT | DV_II_51_0_BIT); mask &= ((w[47] ^ (w[50] >> 25)) & (1 << 4)).wrapping_sub((1) << 4) | !(DV_I_47_0_BIT | DV_I_49_0_BIT | DV_I_51_0_BIT | DV_II_45_0_BIT | DV_II_51_0_BIT | DV_II_56_0_BIT); ``` 这段代码持续了大约 475 行，在 540 行的十六进制表之后。根据测试覆盖率来看它肯定是正确的，但至少对我来说它完全不透明。 我简直看不出如何在不理解这些数字从何而来的情况下让它更快，而代码中没有任何信息有助于此。 ## 阅读论文 (https://sam.dev/blog/faster-sha1-collision-detection#reading-the-paper) 于是我回到了源头：Stevens 和 Shumow 关于加速检测的论文 (https://eprint.iacr.org/2017/173) 解释了过滤器在测试什么。论文本身可能有点枯燥，但他们也有幻灯片和视频报告 (https://www.usenix.org/conference/usenixsecurity17/technical-sessions/presentation/stevens)。 事实证明，SHA-1 碰撞攻击是由称为*扰动向量*的消息差异模式构建的，论文选择了 32 个最便宜的攻击向量（32 是因为掩码是一个 32 位整数）。检测器试图弄清楚的是，一个块是否可能成为沿这 32 个向量中任何一个进行的攻击的一部分。 对于每个向量，论文推导出 7 到 15 个所谓的*不可避免的比特条件*，这些是扩展消息比特对之间的关系，如果攻击正沿该向量进行，则这些关系必须成立。每个条件检查起来都很便宜，如果失败，就可以将该向量排除。 使用这些条件，论文工具仓库 (https://github.com/cr-marcstevens/sha1collisiondetection-tools) 中的一个小程序将它们转化为检查。它枚举一个向量条件的所有线性组合，并在每一步贪婪地选择覆盖最多尚未覆盖向量的关系，平局时根据测试该关系的廉价程度判断：活跃比特数最少，然后是不同比特位置数最少，最后是两个字之间的距离最小。 *生成器的玩具示例，如给定及如检查。两个扰动向量作用于六个比特 A 到 F：第一个要求 A=B，B=C 且 E≠F，第二个要求 A=C 且 D≠E。由于 A=B 和 B=C 意味着 A=C，第一个向量改为检查 A=C，即第二个已经检查的对，因此代码需要四个检查而不是五个，并且其中一个检查同时排除了两个向量。* 这就是生成器的工作原理：一个条件说明扩展消息的两个特定比特必须相等（或必须不同）。这样的关系可以链式传递：如果比特 A 必须等于比特 B，且比特 B 必须等于比特 C，那么 A 必须等于 C。因此，对于每个扰动向量，不是只有一个待检查的对列表，而是一整族等效列表，生成器可以在其中进行选择。 论文的生成器选择许多向量共有的对，这样一条语句就可以同时为多个向量服务。这是最小化语句数量的选择，并且最适合标量计算。 然而，SIMD 单元会改变良好选择的标准吗？ 几条 SSE2 或 NEON 指令可以一次比较四对比特，但前提是这四对可以同时处理，即它们在两个字之间具有相同的距离、在字内具有相同的比特位置，等等。 ## 重新开始 (https://sam.dev/blog/faster-sha1-collision-detection#starting-over) 那时，一个计划开始形成：我不想为特定架构手动调整实现，而是希望将这些理论基础引入 SIMD 的世界。 于是，`sha1dc` (https://github.com/srijs/sha1dc) 诞生了。它是在 Rust 中从头重建的带有碰撞检测功能的 SHA-1。它使用 `x86_64` 和 `arm64` 上的 SHA-1 指令进行哈希运算本身，并生成 `neon`、`sse2` 和 `avx2` 形式的碰撞检查。 底层它使用了一个代码生成器，该生成器可以针对不同的向量单元，确定性地生成针对其特定特性调优的代码。 ### 工作原理 (https://sam.dev/blog/faster-sha1-collision-detection#how-it-works) 在向量化不可避免的比特条件时，每个向量组的执行成本相同，但有效性各不相同：前几组能排除大量块，因为每个组都排除了某个扰动向量的大部分块。之后收益递减，原因有二：大多数扰动向量在大多数块上已经被排除，因此另一个组几乎改变不了什么；其次，适合放在一组（四个或八个）中的条件开始耗尽；剩下的大多只能填满四个通道中的一个。 这就是为什么 `sha1dc` 分两部分生成检查，两部分之间的分割代表了收支平衡点： - **前缀部分** 无条件地在每个块上运行。其单位是一个*组*：一对向量加载，在连续字上覆盖一个形状的最多 4 或 8 个条件。 - **尾部** 是一系列级联的标量条件，与完全标量实现非常相似，仅在某个块未被前缀取消资格时才运行。 *检查的形状，每个方块代表一个条件。C 派生的检查对每个块运行 47 个标量语句，并将其他 109 个条件隐藏在掩码测试之后。NEON 形式 `sha1dc` 生成的检查对每个块运行 17 个向量组，每组宽 4 个通道，总共覆盖 66 个条件，然后是一个掩码为零则返回的操作，最后是一个包含 93 个受保护条件的尾部，只有 28% 的块会到达。* 为了实现这一点，`sha1dc` 使用了一个求解器。求解器的工作是决定哪些条件放入向量前缀，以及放入哪个组，以便前缀在其允许的组数内尽可能多地排除块。它未排除的块将由标量尾部处理。矛盾在于，一个组只有在其四个通道中对齐了相同形状的四个条件时才能发挥其全部四通道的作用，而对齐最好的条件不一定是排除最多块的条件。 想象一个随机块正在被哈希。向量在前缀中的每个独立条件都是一次抛硬币：两个比特要么匹配，要么不匹配。因此，一个有 `r` 个此类条件的向量存活概率为 `2^(-r)`，对 32 个向量求和得到预期存活者数量，这就是求解器在统计上得知尾部需要运行频率的依据。 这个数字随着每个组的增加而持续改进，但吞吐量并非如此：在 M4 上测量，它在尾部进入率触底之前就达到了峰值。这种权衡通过每个指令集的预算来编码：求解器收到一个限制前缀组数的预算，该预算设置为使吞吐量最大化。 *尾部进入率和实测吞吐量相对于前缀预算的关系图（Apple M4）。NEON：当预算从 5 个组增加到 35 个组时，到达尾部的块份额从 98% 下降到 6%，而吞吐量上升至 14 到 21 个组之间的一个平台期，在 17 个组（即发布预算）时达到峰值 2364 MiB/s，然后在 35 个组时下降到 2144。标量：从 20 到 80 个语句，尾部份额从 96% 下降到 14%；吞吐量在 45 到 60 个语句时基本持平，约为 920 MiB/s，两侧均较低，发布预算为 45 个语句。* ### 测试方法 (https://sam.dev/blog/faster-sha1-collision-detection#how-its-tested) 在测试方面，我非常推崇模糊测试和属性测试，以发现固定测试集无法找出的问题。因此，`sha1dc` 中自然包含大量的属性测试。 然而，纯随机输入在此情况下有一个巨大的盲点：只有当所有前缀检查都未触发时，我们才会进入尾部检查，鉴于我们专门优化了前缀检查的有效性，使用随机输入极难触发尾部。 幸运的是，这个问题也能解决：因为 SHA-1 通过线性扩展输入块来填充其内部缓冲区，所以对其中两个比特的条件就是块比特上的一个等式。保持一个向量存活意味着最多满足 15 个这样的等式，而我们有 512 个比特可以操作。计算一次后，你可以用随机值填充数百个未受约束的比特，从而生成一个满足所有条件的新块，你可以按需生成任意多次。 `sha1dc` 中的测试为每个向量生成 64 个这样的见证块，总共 2048 个，全部源自单个种子，以确保即使最罕见的向量后面的检查也能运行。 ## 最终结果 (https://sam.dev/blog/faster-sha1-collision-detection#final-results) `sha1dc` (https://crates.io/crates/sha1dc/0.1.0) 的第一个版本现已发布在 `crates.io` 上，它将与普通 SHA-1 的差距缩小到 19-32%，具体取决于指令集。 ### 微基准测试 (https://sam.dev/blog/faster-sha1-collision-detection#microbenchmarking) 针对 16 KiB 伪随机输入，与两个基准进行比较： 1. `sha1` crate，不做检测但有硬件加速。 2. `sha1-checked` crate，做检测但无硬件加速。 *吞吐量单位为 MiB/s，以及相对于 `sha1` 行的比例：* | 实现方式 | Apple M4 | Xeon Platinum 8488C | Graviton4 | |-------------------|---------------|---------------------|---------------| | `sha1` | 2979 (100%) | 1887 (100%) | 1616 (100%) | | **`sha1dc`** | **2400 (81%)** | **1285 (68%)** | **1286 (80%)** | | `sha1-checked` | 856 (29%) | 523 (28%) | 462 (29%) | | `sha1-checked` + PR #910 (https://github.com/RustCrypto/hashes/pull/910) | 1712 (57%) | 877 (46%) | 980 (61%) | *sha1、sha1dc、sha1-checked 以及带硬件加速 PR 的 sha1-checked 在三台机器上的吞吐量。Apple M4：2979、2400 (81%)、856 (29%) 和 1712 MiB/s (57%)。Xeon Platinum 8488C：1887、1285 (68%)、523 (28%) 和 877 (46%)。Graviton4：1616、1286 (80%)、462 (29%) 和 980 (61%)。* 鉴于 `sha1` 和 `sha1dc` 都使用了机器的 SHA-1 指令，其他条件相同的情况下，它们之间的差距就是 `sha1dc` 中碰撞检测的开销：19% 到 32%，具体取决于机器。 与 `sha1-checked` 的差距更大，达到 2.5 到 2.8 倍，其中大部分归因于硬件加速。当我针对 `sha1-checked` 添加我的 PR 时，情况变得更清晰：硬件 SHA-1 指令使其达到普通 SHA-1 的 46% 到 61%，而向量检查则更进一步，再提升了 1.3 到 1.5 倍。 ### 真实世界性能 (https://sam.dev/blog/faster-sha1-collision-detection#real-world-performance) 这一切始于想让 `git` 更快，那么我们做得怎么样？我们测量的是 gitoxide (https://github.com/GitoxideLabs/gitoxide)，它通常通过封装 `sha1-checked` 的 `gix-hash` 获取 SHA-1。测试中，我们换成了 `sha1dc`。所有测试都在我的 M4 机器上进行，我选取了五次运行中最快的一次。