tl;dr: I discovered collision-detecting SHA-1 is slow and decided to build\nmy own. sha1dc is a rewrite of SHA-1 with\ncollision detection, whose code generator uses a solver to fit collision tests\ninto SIMD lanes. It runs at 68–81% of plain SHA-1's speed where the existing\ncrate 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.
\nI'm using gitoxide and as it\nturns out, pack verification can be quite slow. Verifying the pack of a bare\ngit/git clone (421,292 objects, 305 MiB\ncompressed, 7.7 GiB inflated) on my M4 takes 12.5 seconds, while spending\n84% of that in SHA-1.
Underneath, it uses a crate called sha1-checked, a SHA-1 library with\ncollision detection, running at about 900 MiB/s on that machine. In contrast,\nplain 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...
\nLuckily, 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.
\nOn 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.
\nTo start with, I had a closer look at sha1-checked, and found something to do\nstraight away: it had no hardware acceleration on the detecting path. Modern\narm64 and x86_64 CPUs have SHA-1 instructions and I initially expected that\nit 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.
\nWhat I changed is to spill the schedule to a buffer as it is expanded, run the\nhappy path through the hardware, and only fall back to a scalar recomputation\nfor the rare block that looks suspicious. This roughly doubled throughput on\nboth architectures: 928 → 1996 MB/s on Apple Silicon, ~300 → ~640 MB/s on an\nAMD EPYC with sha_ni.
At the time, I wrapped this up into a pull\nrequest to sha1-checked,\nwhich is currently open, waiting on the 0.11 release before review.
But then I became curious to see how much better we could do.
\nWith the simple fix of the way, the next bottleneck quickly became visible.
\nAs far as I could deduct from the code at this point (we'll get to the theory in a minute), collision detection needs to do two things per block. First it runs a cheap filter: about 150 tests on individual bits of the expanded message, each of which rules out some of the known attack patterns. The filter keeps a mask with one bit per pattern and clears bits as tests fail. Then, only if the mask is still non-zero, comes an expensive recomputation of the block that settles the question for good.
\nOn ordinary data about 95% of blocks leave the filter with an empty mask, so the recomputation almost never runs. Without the filter, hashing would crawl along at around 40 MiB/s, and the filter itself is where a collision-detecting SHA-1 spends the time it spends beyond plain SHA-1.
\nHowever, there was a problem. Here is what this code looks like\nin sha1-checked, which seems to be a more or less direct\ntranslation of the original C code, which in turn was generated\nby a tool from the data files of the research paper behind it:
That goes on for about 475 lines, after 540 lines of hex tables. It is certainly correct based on the test coverage, but at least to me it is also completely opaque.
\nI simply could not see how to make it faster without understanding where the numbers came from, and there was nothing in the code to help with that.
\nSo I went back to the source: Stevens and Shumow's paper on speeding up detection explains what the filter is testing. The paper itself can be a bit dry, but they also have slides and a video presentation.
\nIt turns out that SHA-1 collision attacks are built from patterns of message\ndifferences called disturbance vectors, and the paper selects the 32 cheapest\nto attack with (32 because the mask is a 32-bit integer). What the detector\ntries to figure out is whether a block could be part of an attack along any of\nthose 32 vectors.
\nFor each vector, the paper derives seven to fifteen so-called *unavoidable bit\nconditions*, which are relations between pairs of bits of the expanded message\nthat must hold if an attack along that vector is in progress. Each one is cheap\nto check, and if it fails, that vector can be crossed off.
\nUsing these conditions, a small program from the paper's tools repository turns them into checks. It enumerates every linear combination of a vector's conditions and greedily picks, at each step, the relation that covers the most vectors not yet covered, breaking ties by how cheap the relation is to test: fewest active bits, then fewest distinct bit positions, then the smallest distance between the two words.
\nHere is why the generator works: A condition says that two particular bits of the expanded message must be equal (or must differ). Relations like that chain: if bit A must equal bit B, and bit B must equal bit C, then A must equal C. So for each disturbance vector there is not one list of pairs to check but a whole family of equivalent lists, and the generator gets to choose among them.
\nThe paper's generator chooses pairs that many vectors have in common, so that one statement can serve several of them at once. That is the choice that minimises statements and it is best for scalar computation.
\nHowever, could SIMD units change what a good choice looks like?
\nA few SSE2 or NEON instructions can compare four pairs of bits at once, but only if the four pairs can be processed simultaneously, meaning if they have the same distance between the two words, the same bit positions within them, and so on.
\nAt that point, a plan started to form: Instead of trying to hand-tune implementations for a given architecture, I wanted to take these theoretical foundations and introduce them to the world of SIMD.
\nAnd so, sha1dc was born. It is a bottom-up\nrebuild of SHA-1 with collision detection in Rust. It uses the SHA-1\ninstructions on x86_64 and arm64 for the hashing itself, and generates\nneon, sse2 and avx2 forms of the collision check.
Underneath, it uses a code generator that can be aimed at different vector units to deterministically generate code tuned to their specific characteristics.
\nWhen vectorizing the unavoidable bit conditions, every vector group is equally expensive to execute, but the effectiveness varies: The first few groups buy a lot, because each one rules out a large share of blocks for some disturbance vector. After that the returns shrink, for two reasons: Most disturbance vectors are already ruled out on most blocks, so another group barely changes anything. And second, the conditions that fit four to a group begin to run out; the leftovers would mostly fill one lane out of four.
\nThat is why sha1dc generates checks in two parts, with the split between them\nrepresenting the break-even point:
The prefix runs on every block, unconditionally. Its unit is agroup :
one pair of vector loads covering up to 4 or 8 conditions of one shape at\nconsecutive words.
The tail is a cascading sequence of scalar conditions, very similar to
the fully scalar implementation, which only runs when a block hasn't been\ndisqualified previously by the prefix.
To accomplish this, sha1dc uses a solver. The solver's job is to decide which\nconditions go into the vector prefix, and in which groups, so that the prefix\nrules out as many blocks as it can for the number of groups it is allowed.\nWhatever it does not rule out falls to the scalar tail. The tension is that a\ngroup only pays for its full four lanes when four conditions of the same shape\nline up at consecutive words, and the conditions that line up best are not\nnecessarily the ones that rule out the most blocks.
Think of a random block being hashed. Each independent condition a vector has\nin the prefix is a coin flip: the two bits either match or they do not. So a\nvector with r such conditions survives with probability 2^(−r), and summing\nthat over the 32 vectors gives the expected number of survivors, which is how\nthe solver knows statistically how often the tail has to run.
That number keeps improving with every group, but throughput does not: measured on the M4, it peaks well before the tail-entry rate bottoms out. The way this trade-off is encoded is via a budget for each instruction set: The solver receives a limit on the number of prefix groups which is set so that it maximizes throughput.
\nWhen it comes to testing, I am a big fan of fuzzing and property tests to suss\nout problems that fixed test batteries won't find. So naturally there are\nplenty of property tests in sha1dc.
However, purely random inputs have a big blind spot in this case: we only progress to the checks in the tail when none of the prefix checks have triggered, and given that we're optimizing specifically for the effectiveness of prefix checks, this becomes extremely difficult to trigger with random inputs.
\nLuckily, this also can be solved for: because SHA-1 seeds its internal buffer by linearly expanding the input block, a condition on two of its bits is an equation on the block's bits. Keeping one vector alive means satisfying at most 15 such equations, with 512 bits to play with. Computed once, you can fill the hundreds of unconstrained bits with random values, and out comes a fresh block that satisfies every condition, as many times as you like.
\nThe tests in sha1dc generate 64 such witnesses per vector, 2,048 in all, from\na single seed, so that the checks behind even the rarest vector run.
The first version of sha1dc is now\npublished on crates.io, and it narrows the gap to plain SHA-1 to 19–32%,\ndepending on the instruction set.
Measuring 16 KiB of pseudo-random input against two baselines:
\nsha1 crate, which does no detection but has hardware-acceleration.The sha1-checked crate, which does detection but has no
hardware-acceleration.
Throughput in MiB/s, and as a fraction of the sha1 row:
| implementation | Apple M4 | Xeon Platinum 8488C | Graviton4 |
|---|---|---|---|
sha1 | 2979 (100%) | 1887 (100%) | 1616 (100%) |
sha1dc | 2400 (81%) | 1285 (68%) | 1286 (80%) |
sha1-checked | 856 (29%) | 523 (28%) | 462 (29%) |
sha1-checked + PR #910 | 1712 (57%) | 877 (46%) | 980 (61%) |
Given that both sha1 and sha1dc use the machine's SHA-1 instructions, the\ngap between them is, all else being equal, the cost of collision detection in\nsha1dc: 19% to 32%, depending on the machine.
The gap to sha1-checked is bigger, 2.5× to 2.8×, with most of it due to\nhardware acceleration. When adding my PR against sha1-checked, it gives a\nclearer picture: the hardware SHA-1 instructions take it to 46% to 61% of plain\nSHA-1, and the vector check takes it the rest of the way, another 1.3× to 1.5×\non top.
This all started with wanting to make git faster, so how are we doing? We're\nmeasuring gitoxide, which normally\ngets its SHA-1 from gix-hash, which wraps sha1-checked. For testing,\nsha1dc was swapped in. All tests ran on my M4 machine, and I picked the\nfastest of five runs.
| operation | sha1-checked | sha1dc | speedup |
|---|---|---|---|
pack verify , all cores | 2.33 s | 1.09 s | 2.13× |
pack verify , one thread | 12.55 s | 6.26 s | 2.01× |
index-pack , all cores | 4.23 s | 2.79 s | 1.52× |
index-pack , one thread | 14.72 s | 8.02 s | 1.84× |
The numbers from the start of this post move the way they should: SHA-1 with\ndetection goes from 84% of the single-threaded pack verify to 73%, with zlib\ninflation rising from 11% to 18% as the hashing shrinks around it.
While we're already using this in Enroute, I would also\nlove to upstream this into gitoxide itself so that the whole Rust-based git\necosystem can benefit.
That said, the single biggest thing in the pack verify profile is still SHA-1,\nso this journey is far from over. Stay tuned!