Solving for faster SHA-1 collision detection
The author built sha1dc, a Rust library that accelerates SHA-1 collision detection using CPU hardware instructions and a SIMD solver, doubling git pack verification speed.
read it A well-executed build log detailing how SIMD and solver-based optimizations can dramatically reduce the performance penalty of cryptographic collision detection.
summary
The author optimized SHA-1 collision detection in Rust by combining CPU hardware instructions with a solver that fits bit-condition filters into SIMD lanes. This split-prefix design routes most blocks through fast hardware while running tailored SIMD checks, achieving up to 81 percent of plain SHA-1 speed. Benchmarks show it roughly triples previous collision-detecting crates and doubles git pack verification speed in gitoxide, where it has since been upstreamed.
key points
- Standard collision-detecting SHA-1 crates run at under 30 percent of plain SHA-1 speed because scalar condition filters are expensive.
- sha1dc uses a custom solver to pack unavoidable bit conditions into SSE2, AVX2, and NEON SIMD lanes while utilizing native hardware instructions.
- The new approach reaches 68 to 81 percent of plain SHA-1 throughput, cutting git pack verification times in half.
who should read it
Rust engineers, systems programmers, and developers working on performance-critical git tooling or cryptographic verification.
discussion warm
consensus
Commenters are deeply impressed by the technical depth and performance wins, noting its practical impact as Git increasingly adopts Rust components.
pushback
A few commenters express caution about the complexity of the custom algorithm and whether it can be thoroughly proven secure against edge cases.
Hi, author here. FWIW the blog is fully hand-written. I used Claude to help me generate the visuals.
What goes into head vs. tail is actually fully deterministically decided by the solver based on a P(tail) gradient, so expressions that are more effective in filtering out blocks before they can hit the (slower) tail are preferred in the prefix.
The author provides additional context on how the solver automatically optimizes the prefix-tail tradeoff based on block survival probabilities.
Generated by an LLM from the article and thread. Check the sources before relying on it.