Solving for faster SHA-1 collision detection
2 days ago
- sha1dc 是一个新的Rust SHA-1库，具有碰撞检测功能，运行速度是普通SHA-1的68–81%，而现有 crate 的速度仅为28–29%。
- Git 包验证速度慢，因为不受信任的包文件需要检测碰撞的SHA-1，这比普通SHA-1慢得多。
- 现有的 sha1-checked crate 在检测路径上缺乏硬件加速；一个 PR 添加了对正常路径使用SHA-1指令，仅对可疑块使用标量回退。
- 碰撞检测通过使用不可避免的位条件测试32个扰动向量来工作；过滤器排除攻击模式，只有极少数块需要昂贵的重新计算。
- 过滤器代码是一个475行的难以理解的标量翻译；要理解它，需要阅读Stevens和Shumow的原始研究论文。
- sha1dc 使用带有求解器的代码生成器，将碰撞检查适配到SIMD组中，生成针对每个向量单元调优的NEON、SSE2和AVX2代码。
- 求解器选择哪些条件进入向量前缀或标量尾部，平衡前缀效果与吞吐量，并为每个指令集使用预算。
- 测试使用模糊测试、属性测试和生成的满足每个向量所有条件的见证块，避免了随机输入的盲点。
- 基准测试显示，在多核包验证中，sha1dc 比 sha1-checked 快2.13倍，单线程快2.01倍，索引包加速分别为1.52倍和1.84倍。
- 这项工作旨在被整合到 gitoxide 中，但仍需进一步优化，因为SHA-1仍然是包验证的最大瓶颈。