快速哈希函数的对抗样本

# 快速哈希函数的对抗性示例 来源：https://thomasahle.com/blog/adversarial-examples-for-hashes/ 目录 1. 引言 (https://thomasahle.com/blog/adversarial-examples-for-hashes/#overview) 2. 图表：速度 vs. 碰撞界限 (https://thomasahle.com/blog/adversarial-examples-for-hashes/#comparison) 3. 主要结论 (https://thomasahle.com/blog/adversarial-examples-for-hashes/#takeaways) 4. 附录 1. 附录 A. 逐个分析哈希函数的难点案例 (https://thomasahle.com/blog/adversarial-examples-for-hashes/#appendix-a) 2. 反复出现的模式 (https://thomasahle.com/blog/adversarial-examples-for-hashes/#recurring-patterns) 3. CityHash64 (https://thomasahle.com/blog/adversarial-examples-for-hashes/#appendix-cityhash64) 4. FarmHash64 (https://thomasahle.com/blog/adversarial-examples-for-hashes/#appendix-farmhash64) 5. gxhash (https://thomasahle.com/blog/adversarial-examples-for-hashes/#appendix-gxhash) 6. MurmurHash3 x64_128 (https://thomasahle.com/blog/adversarial-examples-for-hashes/#appendix-murmurhash3) 7. MuseAir (https://thomasahle.com/blog/adversarial-examples-for-hashes/#appendix-museair) 8. MuseAir v2 (https://thomasahle.com/blog/adversarial-examples-for-hashes/#appendix-museair-v2) 9. komihash (https://thomasahle.com/blog/adversarial-examples-for-hashes/#appendix-komihash) 10. SpookyHash V2 (https://thomasahle.com/blog/adversarial-examples-for-hashes/#appendix-spookyhash) 11. aHash (https://thomasahle.com/blog/adversarial-examples-for-hashes/#appendix-ahash) 12. t1ha2 (https://thomasahle.com/blog/adversarial-examples-for-hashes/#appendix-t1ha2) 13. a5hash-64 (https://thomasahle.com/blog/adversarial-examples-for-hashes/#appendix-a5hash-64) 14. a5hash-128 (https://thomasahle.com/blog/adversarial-examples-for-hashes/#appendix-a5hash-128) 15. HighwayHash (https://thomasahle.com/blog/adversarial-examples-for-hashes/#appendix-highwayhash) 16. wyhash final v4.3 (https://thomasahle.com/blog/adversarial-examples-for-hashes/#appendix-wyhash) 17. rapidhash v1 (https://thomasahle.com/blog/adversarial-examples-for-hashes/#appendix-rapidhash-v1) 18. rapidhash v3 (https://thomasahle.com/blog/adversarial-examples-for-hashes/#appendix-rapidhash-v3) 19. XXH3-64 0.8.3 (https://thomasahle.com/blog/adversarial-examples-for-hashes/#appendix-xxh3-64) 20. XXH3-128 0.8.3 (https://thomasahle.com/blog/adversarial-examples-for-hashes/#appendix-xxh3-128) 21. MUM v3 (https://thomasahle.com/blog/adversarial-examples-for-hashes/#appendix-mum) 22. pengyhash v0.3 (https://thomasahle.com/blog/adversarial-examples-for-hashes/#appendix-pengyhash) 23. nmhash32 v2 (https://thomasahle.com/blog/adversarial-examples-for-hashes/#appendix-nmhash32) 24. nmhash32x v2 (https://thomasahle.com/blog/adversarial-examples-for-hashes/#appendix-nmhash32x) 25. mx3 v3 (https://thomasahle.com/blog/adversarial-examples-for-hashes/#appendix-mx3) 26. mir（精确与不精确） (https://thomasahle.com/blog/adversarial-examples-for-hashes/#appendix-mir) 27. fasthash（32位和64位） (https://thomasahle.com/blog/adversarial-examples-for-hashes/#appendix-fasthash) 28. UMASH-64/128：主要界限均已证明 (https://thomasahle.com/blog/adversarial-examples-for-hashes/#appendix-umash) 29. HalftimeHash：修正的包装器证明 (https://thomasahle.com/blog/adversarial-examples-for-hashes/#appendix-halftimehash) 30. HalftimeHash24（高级24字节API，Encode3） (https://thomasahle.com/blog/adversarial-examples-for-hashes/#appendix-halftime24) 31. ChainHash：一个函数，64个随机密钥字节 (https://thomasahle.com/blog/adversarial-examples-for-hashes/#appendix-chainhash) 32. ChainHash-128 (https://thomasahle.com/blog/adversarial-examples-for-hashes/#appendix-chainhash128) 33. HalftimeHash24 修正版 (https://thomasahle.com/blog/adversarial-examples-for-hashes/#appendix-halftime24-fixed) 34. Poly1305 和 GHASH (https://thomasahle.com/blog/adversarial-examples-for-hashes/#appendix-classic) 35. SipHash-1-3 和 SipHash-2-4 (https://thomasahle.com/blog/adversarial-examples-for-hashes/#appendix-siphash) 36. Go maphash (https://thomasahle.com/blog/adversarial-examples-for-hashes/#appendix-go-maphash) 37. Abseil Hash (https://thomasahle.com/blog/adversarial-examples-for-hashes/#appendix-abseil-hash) 38. .NET Marvin (https://thomasahle.com/blog/adversarial-examples-for-hashes/#appendix-dotnet-marvin) 39. foldhash-fast 0.2.0 (https://thomasahle.com/blog/adversarial-examples-for-hashes/#appendix-foldhash-fast) 40. foldhash-quality 0.2.0 (https://thomasahle.com/blog/adversarial-examples-for-hashes/#appendix-foldhash-quality) 41. 这些结果如何产生 (https://thomasahle.com/blog/adversarial-examples-for-hashes/#verification) 42. 附录 B. 复现数据 (https://thomasahle.com/blog/adversarial-examples-for-hashes/#appendix-b) 5. 前期工作与致谢 (https://thomasahle.com/blog/adversarial-examples-for-hashes/#prior-work-and-acknowledgements) 6. 更新与修正 (https://thomasahle.com/blog/adversarial-examples-for-hashes/#updates-and-corrections) 7. 引用 (https://thomasahle.com/blog/adversarial-examples-for-hashes/#citation) 8. 许可证 (https://thomasahle.com/blog/adversarial-examples-for-hashes/#licence) 哈希函数 (https://en.wikipedia.org/wiki/Hash_function) 将任意长度的数据映射到固定大小的值。其目标是确保*不同的输入*映射到*不同的输出*，除了在哈希函数使用的*密钥*的随机性上具有非常小的概率外。这一性质 (https://en.wikipedia.org/wiki/Universal_hashing) 使我们能够构建快速的哈希表，其中每个数据点不会*碰撞*到同一个桶中。[1] (https://thomasahle.com/blog/adversarial-examples-for-hashes/#note-bucket-bits) 哈希需要快速。xxHash (https://github.com/cyan4973/xxhash) 号称达到 60 GB/s，基本与读取内存的速度相当。这种批量哈希对于文件同步或数据完整性检查非常有用。许多流行的哈希如 *komihash, a5hash, HighwayHash, SpookyHash, aHash* 和 *t1ha2* 愿意以牺牲质量（至少对于对抗性输入）为代价换取更高速度。 这过去是可以接受的。哈希的许多应用场景风险较低，攻击者不值得为使哈希碰撞概率远高于平均值的输入进行昂贵的密码分析。尽管如此，大多数哈希试图保持*一定程度*的鲁棒性，以防止算法中的意外二次减速和拒绝服务攻击。 最好的哈希提供了*证明*，表明*任何*一对输入的碰撞概率都很低。这是密码学世界中独一无二的，在这个领域没人能证明某个东西真正安全。假设一个哈希是 b 位通用的，如果所有长度为 L 的输入对的碰撞概率不超过 L · 2^(-b)。有时对 L 的依赖关系更差，但可以（证明地）确保不会更好。[2] (https://thomasahle.com/blog/adversarial-examples-for-hashes/#note-length-bound) 问题就变成：对于某个期望的 b，什么是可能的最快 b 位通用哈希？ 我得以使用 Claude Fable 分析了来自 SMhasher (https://github.com/rurban/smhasher) 的各种流行哈希——这是一个大规模的项目，用于经验性地测试哈希的统计特性。它发现大多数哈希都存在性能极差的输入——比预期至少低 20 位。少数几个哈希有已发表的证明，Fable 能够在 Lean 中发现其中一些的错误并验证另一些。点击图表中的任何点以阅读完整分析。 碰撞分数界限与批量吞吐量。速度是按对数刻度的。分数使用平方根间距，为低分值留出更多空间；刻度标签显示原始位值。实心青色圆圈是已证明的下界保证；空心圆圈是未经解决的声明。Rust 菱形是见证的上界上限；叉号标记所有种子对。标签标识选定的地标；每个绘制的变体都可在哈希选择器中找到。 使用 Tab 键跳转到某个点，并使用方向键、Home 或 End 键在点之间移动。按 Enter 或空格键打开其配置文件。按 Escape 键关闭。在触摸屏上点击某个点或其标签。 碰撞分数界限与校正后的 Apple M2 Pro 批量吞吐量：包括 UMASH 在内的已证明保证、见证的上界上限和空心的未解决声明。 检查哈希 选择一个哈希，或点击一个点或标签。 **图 1.** 快速的实现可能具有非常不同的碰撞保证。实点显示证明所保证的内容；Rust 标记显示由特定对暴露的限制。保证和速度测量可能使用不同的密钥设置——打开配置文件查看这些假设。 完整数据表 (https://thomasahle.com/blog/adversarial-examples-for-hashes/#chart-table-details) · 数据与来源 (https://thomasahle.com/blog/adversarial-examples-for-hashes/data.json) · 计时复现 (https://github.com/thomasahle/hash-benchmark-reproduction) · 哈希配置文件 (https://thomasahle.com/blog/adversarial-examples-for-hashes/figure/profiles.json) 如何解读界限和基准 在速度轴上，相等的距离代表相等的比率：从 1 移动到 2 字节/周期所占的空间与从 10 移动到 20 相同。垂直轴使用平方根间距，为低碰撞分数提供更多空间。零点保持可见，所有刻度标签和配置文件值都显示原始的分数（以位为单位）。分数本身是碰撞界限的对数；参见其定义 (https://thomasahle.com/blog/adversarial-examples-for-hashes/#universality)。 实心青色圆圈给出已证明的最小分数。空心圆圈显示未经证明的声明。Rust 菱形使用一对特定的不同消息（它们会碰撞）来限定分数上限；叉号标识那些对于每个种子都会碰撞的对。星号表示上限使用的是采样率。未找到更差的对并不证明不存在这样的对，因此这些上限不是安全性的排名。叉号可能位于零点之上，因为分数针对消息长度进行了调整。所有绘制的变体都可在选择器中找到，包括四种 HalftimeHash 样式，它们各自返回 64 位。 单独的历史 32 字节对 A (https://thomasahle.com/blog/adversarial-examples-for-hashes/verify/xxh3-64/HISTORICAL.html) 在 wyhash, rapidhash v1, rapidhash v3 和 XXH3-64 中，每 2^30 个密钥分别产生 9、12、11 和 11 次碰撞。选定的 XXH3-64 对具有不同的测量速率：大约每 2^36 个密钥中有 527 次（采样；527 个事件，合并）。搜索努力不相等；这些见证上限并未对哈希进行排名。当前对和计数来源 (https://thomasahle.com/blog/adversarial-examples-for-hashes/verify/xxh3-64/README.html)。 速度是在 256 KiB 的消息上测量的，无论碰撞对的长度如何。“B/cycle” 表示每个报告的定时器周期处理的字节数；数值越大越快。M2 和 Xeon 定时器使用不同的周期约定，因此请在相同的主机上比较哈希。单独的短输入测量使用 1–31 字节。Foldhash 使用经过验证的移植和控制测量。GHASH 通过 OpenSSL 的 GMAC 接口进行计时，包括设置开销。基准测试协议记录了定时器、重复运行和校准细节。 UMASH 已发表的两个主要界限现在已通过不同的路径得到证明：实现的模 8p 累加器和 C 指纹的两个独立乘数。实心点显示 56.18 和 83.99 位（在 L ≤ 246 个单词时约为 84 位），适用于理想的完整密钥、固定种子和完整的 C 输出。密钥派生、每次调用的种子和掩码输出不在这些定理范围内；论文中的 162/q 投影步骤仍未验证。四种 64 位 HalftimeHash 样式在规定的执行假设和长度限制下，具有修正后的 63 位界限。原始的高级 24 字节函数被驳斥；其修复版本单独绘制。ChainHash 在两个主机上都是一个 64 位函数：在 Xeon 上为 28.31 B/cycle，在 M2 上为 26.26，并带有经过机器检查的 63.0 位保证（来自 64 个均匀随机密钥字节）。ChainHash-128 是 128 位函数，同样在两个主机上是一个函数：在 Xeon 上为 14.43 B/cycle，在 M2 上为 10.26，带有经过机器检查的 127 位保证（来自 128 个随机密钥字节）。SipHash-1-3 和 SipHash-2-4 以 64 位输出宽度绘制为未解决的声明。本次审计既未提供证明，也未提供这些 SipHash 界限的反例。引用的 2014 年分析报告 SipHash-1-x 的碰撞特征为 2^(-167)，SipHash-2-4 为 2^(-236.3)（Dobraunig, Mendel 和 Schläffer, 2014），我们自己的搜索未发现超过 2^(-26.4) 每对的碰撞。一些历史碰撞示例没有匹配的计时，因此图表中未显示。请参阅证明说明 (https://thomasahle.com/blog/adversarial-examples-for-hashes/#appendix-umash) 了解区别。 主要结论： 1. AI 改变了威胁模型：过去主要靠隐蔽性保证安全的软件现在很容易被攻破。如果你能得到可证明正确的软件，就采用它。 2. 可证明正确的哈希与启发式哈希一样快。我们自己的哈希 ChainHash，基于我与 Jakob Tejs 在快速多项式求值 (https://thomasahle.com/fast-polynomials/) 方面的工作构建，在 Intel Xeon 上具有所有哈希中最高的吞吐量，在 Apple M2 Pro 上位居第二。 3. 正确性证明很好，但经过验证的 Lean 证明更好。并非所有已发表的内容都经过同样好的审计，我们发现了多个差距，其中一些可以修复，另一些则需要代码更改。 所有发现均在本博客文章发布前已向维护者披露。你可以在 xxHash (https://github.com/Cyan4973/xxHash/issues/1127#issuecomment-5720905442)、komihash (https://github.com/avaneev/komihash/issues/23#issuecomment-5738942086)、MuseAir (https://github.com/eternal-io/museair/issues/4#issuecomment-5741752858) 和 foldhash (https://github.com/orlp/foldhash/issues/50#issuecomment-5734983476) 的讨论中阅读维护者的回复。共识是，只有真正的*多重碰撞*攻击，即一大组输入以高概率全部碰撞，才值得修复。通用哈希可以防止这种情况，但原则上一个哈希可能对多重碰撞具有鲁棒性而不是通用的。 这是一个公平的立场，特别是因为更改哈希很难向后兼容。然而，对于这篇博客文章，我们专注于*可证明的保证*，而发现的碰撞证明了这些启发式哈希不仅仅是尚未被证明正确的通用哈希。而且我们还确实为许多哈希找到了泛洪级的无密钥多重碰撞。[3] (https://thomasahle.com/blog/adversarial-examples-for-hashes/#note-multicollisions) 哈希鲁棒性：碰撞输入与受影响密钥 四种哈希鲁棒性问题类别，并列展示：种子无关对、少路碰撞、弱密钥多重碰撞和种子无关多重碰撞。每个类别都有简短的定义及其最直接相关的应用场景。此处讨论的所有输入均在不知道密钥的情况下选择。 **种子无关对**：相同的两个不同输入对*对于每个密钥*都碰撞。 **用途**：指纹识别、基于哈希的相等性判断、去重、近似成员资格过滤器。 **少路碰撞**：一小组输入对*对于某些密钥*碰撞。 **用途**：布谷鸟哈希、有界容量桶、哈希索引缓存和硬件表。 **弱密钥多重碰撞**：一大组固定输入对*对于一部分密钥*碰撞。 **用途**：随机化字典、长期缓存、基于哈希的分区。 **多重碰撞**：一大组固定输入对*对于每个密钥*都碰撞。 **用途**：映射和集合、基于哈希的数据库操作、分片、不同计数草图。 **哈希鲁棒性：碰撞输入与受影响密钥** 四种哈希鲁棒性问题类别，并列展示：种子无关对、少路碰撞、弱密钥多重碰撞和种子无关多重碰撞。每个类别都有简短的定义及其最直接相关的应用场景。此处讨论的所有输入均在不知道密钥的情况下选择。 **种子无关对**：相同的两个不同输入对