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.

How git uses SHA-1 and why it has to be slow(er)#

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.

Low-hanging fruit#

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.

At the time, I wrapped this up into a pull request to sha1-checked, which is currently open, waiting on the 0.11 release before review.

But then I became curious to see how much better we could do.

The wall of constants#

With the simple fix of the way, the next bottleneck quickly became visible.

As 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.

On 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.

However, there was a problem. Here is what this code looks like in sha1-checked, which seems to be a more or less direct translation of the original C code, which in turn was generated by a tool from the data files of the research paper behind it:

mask &= (((w[44] ^ w[45]) >> 29) & 1).wrapping_sub(1)
    | !(DV_I_48_0_BIT | DV_I_51_0_BIT | DV_I_52_0_BIT
        | DV_II_45_0_BIT | DV_II_46_0_BIT | DV_II_50_0_BIT | DV_II_51_0_BIT);
mask &= ((w[47] ^ (w[50] >> 25)) & (1 << 4)).wrapping_sub((1) << 4)
    | !(DV_I_47_0_BIT | DV_I_49_0_BIT | DV_I_51_0_BIT
        | DV_II_45_0_BIT | DV_II_51_0_BIT | DV_II_56_0_BIT);

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.

I 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.

Reading the paper#

So 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.

It turns out that SHA-1 collision attacks are built from patterns of message differences called disturbance vectors, and the paper selects the 32 cheapest to attack with (32 because the mask is a 32-bit integer). What the detector tries to figure out is whether a block could be part of an attack along any of those 32 vectors.

For each vector, the paper derives seven to fifteen so-called unavoidable bit conditions, which are relations between pairs of bits of the expanded message that must hold if an attack along that vector is in progress. Each one is cheap to check, and if it fails, that vector can be crossed off.

Using 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.

Here 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.

The 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.

However, could SIMD units change what a good choice looks like?

A 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.

Starting over#

At 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.

And so, sha1dc was born. It is a bottom-up rebuild of SHA-1 with collision detection in Rust. It uses the SHA-1 instructions on x86_64 and arm64 for the hashing itself, and generates neon, 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.

How it works#

When 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.

That is why sha1dc generates checks in two parts, with the split between them representing the break-even point:

• The prefix runs on every block, unconditionally. Its unit is a group: one pair of vector loads covering up to 4 or 8 conditions of one shape at consecutive 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 disqualified previously by the prefix.

To accomplish this, sha1dc uses a solver. The solver's job is to decide which conditions go into the vector prefix, and in which groups, so that the prefix rules out as many blocks as it can for the number of groups it is allowed. Whatever it does not rule out falls to the scalar tail. The tension is that a group only pays for its full four lanes when four conditions of the same shape line up at consecutive words, and the conditions that line up best are not necessarily the ones that rule out the most blocks.

Think of a random block being hashed. Each independent condition a vector has in the prefix is a coin flip: the two bits either match or they do not. So a vector with r such conditions survives with probability 2^(−r), and summing that over the 32 vectors gives the expected number of survivors, which is how the 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.

How it's tested#

When it comes to testing, I am a big fan of fuzzing and property tests to suss out problems that fixed test batteries won't find. So naturally there are plenty 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.

Luckily, 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.

The tests in sha1dc generate 64 such witnesses per vector, 2,048 in all, from a single seed, so that the checks behind even the rarest vector run.

Final results#

The first version of sha1dc is now published on crates.io, and it narrows the gap to plain SHA-1 to 19–32%, depending on the instruction set.

Microbenchmarking#

Measuring 16 KiB of pseudo-random input against two baselines:

1. The sha1 crate, which does no detection but has hardware-acceleration.
2. The sha1-checked crate, which does detection but has no hardware-acceleration.

Throughput in MiB/s, and as a fraction of the sha1 row:

Given that both sha1 and sha1dc use the machine's SHA-1 instructions, the gap between them is, all else being equal, the cost of collision detection in sha1dc: 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 hardware acceleration. When adding my PR against sha1-checked, it gives a clearer picture: the hardware SHA-1 instructions take it to 46% to 61% of plain SHA-1, and the vector check takes it the rest of the way, another 1.3× to 1.5× on top.

Real world performance#

This all started with wanting to make git faster, so how are we doing? We're measuring gitoxide, which normally gets its SHA-1 from gix-hash, which wraps sha1-checked. For testing, sha1dc was swapped in. All tests ran on my M4 machine, and I picked the fastest of five runs.

The numbers from the start of this post move the way they should: SHA-1 with detection goes from 84% of the single-threaded pack verify to 73%, with zlib inflation rising from 11% to 18% as the hashing shrinks around it.

What's next#

While we're already using this in Enroute, I would also love to upstream this into gitoxide itself so that the whole Rust-based git ecosystem can benefit.

That said, the single biggest thing in the pack verify profile is still SHA-1, so this journey is far from over. Stay tuned!