Solving for faster SHA-1 collision detection

A developer set out to speed up SHA-1 collision detection because git pack verification was spending the majority of time in a collision-detecting SHA-1 implementation. The new Rust implementation, sha1dc, combines two practical wins: expose the internal SHA-1 message schedule so hardware SHA-1 instructions can be used on the common fast path (spilling the schedule to a buffer so only suspicious blocks trigger scalar recomputation), and replace the existing opaque scalar detector with a SIMD-aware code generator. Simple changes alone roughly doubled throughput on Apple Silicon (928 → 1996 MiB/s) and on AMD EPYC (~300 → ~640 MiB/s). Compared with the existing crate that runs at about 28-29% of plain SHA-1, sha1dc runs at 68-81% and can make git pack verification roughly twice as fast.

The core detection work stems from the Stevens-Shumow approach: 32 disturbance vectors each imply several “unavoidable bit conditions” on expanded message bits, and a cheap filter checks many such relations per block to avoid expensive recomputation. Instead of using the paper’s scalar-optimized generator, sha1dc uses a solver-driven code generator that packs compatible conditions into SIMD groups (the PREFIX) and leaves a cascading scalar fallback (the TAIL) for survivors. The solver balances group composition against an ISA-specific budget to maximize throughput; measured trade-offs show throughput plateaus well before the tail-entry rate bottoms out. Testing relies on fuzzing and property tests, with special care because random inputs rarely exercise the tail.