Solving for faster SHA-1 collision detection
2 days ago
- sha1dc is a new Rust SHA-1 library with collision detection, running at 68–81% of plain SHA-1 speed vs 28–29% for the existing crate.
- Git pack verification is slow because untrusted pack files require collision-detecting SHA-1, which is much slower than plain SHA-1.
- The existing sha1-checked crate lacked hardware acceleration on the detection path; a PR added using SHA-1 instructions for the happy path and scalar fallback only for suspicious blocks.
- Collision detection works by testing 32 disturbance vectors using unavoidable bit conditions; a filter rules out attack patterns and only rare blocks need expensive recomputation.
- The filter code was a 475-line opaque scalar translation; understanding required reading the original research paper by Stevens and Shumow.
- sha1dc uses a code generator with a solver to fit collision checks into SIMD groups, generating NEON, SSE2, and AVX2 code tuned for each vector unit.
- The solver chooses which conditions go into a vector prefix vs a scalar tail, balancing prefix effectiveness against throughput, and uses a budget per instruction set.
- Testing uses fuzzing, property tests, and generated witness blocks that satisfy all conditions for each vector, avoiding random-input blind spots.
- Benchmarks show sha1dc is 2.13× faster than sha1-checked for multi-core pack verify and 2.01× faster single-threaded, with index-pack speedups of 1.52× and 1.84×.
- The work aims to be upstreamed into gitoxide, and further optimization is still needed since SHA-1 remains the biggest pack-verify bottleneck.