// HACKER NEWS — CYBERSECURITY
Solving for faster SHA-1 collision detection
tl;dr: I discovered collision-detecting SHA-1 is slow and decided to build
my own. sha1dc is a rewrite of SHA-1 with
collision detection, whose code generator uses a solver to fit collision tests
into SIMD lanes. It runs at 68–81% of plain SHA-1's speed where the existing
crate runs at 28–29%, and can make git pack verification twice as fast.
As part of working on Enroute, I'm
currently deep into optimizing the performance of a git server backend. One
thing you do a lot in a git server is accepting pack files from git clients.
These pack files are untrusted input and have to be validated, which includes
checking the SHA-1 hash of the included git objects.
I'm using gitoxide and as it
turns out, pack verification can be quite slow. Verifying the pack of a bare
git/git clone (421,292 objects, 305 MiB
compressed, 7.7 GiB inflated) on my M4 takes 12.5 seconds, while spending
84% of that in SHA-1.
Underneath, it uses a crate called sha1-checked, a SHA-1 library with
collision detection, running at about 900 MiB/s on that machine. In contrast,
plain sha1 with the M4's SHA-1 hardware instructions sits at about 3 GB/s.
Wait, collision detection? Yes: What makes SHA-1 difficult for untrusted input
is that it is known to be cryptographically broken because chosen-prefix
collisions are practical. Ideally, we would of
course all be using SHA-256 for our git objects, but migrations...
Luckily, this security issue can be mitigated by detecting those manufactured
collisions within the SHA-1 state space, which is what git is doing. Using this
approach, when a git server detects a collision, it refuses to accept these
objects from the client.
On the not so lucky side, this is obviously quite slow! And thus I set out to
see if I could make things faster and improve the performance of SHA-1 with
collision detection.
To start with, I had a closer look at sha1-checked, and found something to do
straight away: it had no hardware acceleration on the detecting path. Modern
arm64 and x86_64 CPUs have SHA-1 instructions and I initially expected that
it would try and use them.
However, the catch with the hardware instructions in this case is that
collision detection runs off the internal SHA-1 message schedule and hash
state, which the hardware instructions make difficult to access.
What I changed is to spill the schedule to a buffer as it is expanded, run the
happy path through the hardware, and only fall back to a scalar recomputation
for the rare block that looks suspicious. This roughly doubled throughput on
both architectures: 928 → 1996 MB/s on Apple Silicon, ~300 → ~640 MB/s on an
AMD EPYC with sha_ni.