Solving for faster SHA-1 collision detection — sam reis

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.

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.