Claude Fable knocked 20 bits off most popular hashes

An audit run with Claude Fable found that most popular fast hashes have inputs on which they collide far more often than they should, at least 20 bits below expectation. The author published the results in a September 20 post on the Thomasahle blog. Fable also went through the few hashes that come with published collision proofs. It verified some of them in Lean and found mistakes in others.

The hashes came from SMHasher, a large project that tests the statistical properties of hashes empirically. Its “Quality problems” column records statistics, and adversarial inputs are a separate question. A hash can pass every distribution test and still have input pairs that an attacker can make collide on purpose, or that cause accidentally quadratic slowdowns. Fable went looking for those pairs.

What “20 bits below” means

The post measures hashes against a provable standard. A hash is b-bit universal if any two distinct inputs of length L collide with probability at most L · 2^-b. That probability is taken over the secret key, or seed, the hash runs with. The seed matters because a fixed, deterministic function offers no guarantee against chosen inputs: anyone who knows it can pick inputs that all land in one bucket. Drawing the function at random from a family is what makes a collision bound possible in the first place.

The score on the post’s chart is that b, in bits, adjusted for message length, and it is logarithmic in the collision bound. Most of the hashes Fable examined have inputs that score at least 20 bits below expectation.

The evidence is a pair of colliding messages, which the post calls a witness. One 32-byte pair gave 9, 12, 11 and 11 collisions per 2^30 keys in wyhash, rapidhash v1, rapidhash v3 and XXH3-64. A different pair selected for XXH3-64 collided about 527 times in every 2^36 keys, a sampled rate pooled across 527 events. A witness only caps a score from above, and search effort was unequal across hashes, so the post says the caps “do not rank hashes.” Separate marks on the chart flag pairs that collide for every seed.

Which collision hurts where

The post sorts the weaknesses into four kinds. All of them are built from inputs chosen without knowing the key, and each maps to the systems it threatens:

• Seed-independent pair: the same two inputs collide for every key. Relevant to fingerprinting, hash-based equality, deduplication and approximate membership filters.
• Few-way collisions: a small set collides for some keys. Relevant to cuckoo hashing, bounded-capacity buckets, hash-indexed caches and hardware tables.
• Weak-key multicollision: a large fixed set collides for a fraction of keys. Relevant to randomized dictionaries, long-lived caches and hash-based partitioning.
• Multicollision: a large fixed set collides for every key. Relevant to maps and sets, hash-based database operations, sharding and distinct-count sketches.

The last kind turns into hash flooding, the denial-of-service attack where a server’s hash table degrades into a list. The post says the audit found “flooding-grade key-free multicollisions for many hashes.” Its examples of hashes that trade quality on adversarial inputs for speed include komihash, a5hash, HighwayHash, SpookyHash, aHash and t1ha2.

Many of the attacks reused the same bad patterns across hash families, the post says. The per-hash appendix covers CityHash64, FarmHash64, gxhash, MurmurHash3, the XXH3 variants, Go maphash, Abseil Hash, .NET Marvin and foldhash, among others.

Auditing the proofs

UMASH now has both of its headline bounds proved, by different routes. One goes through the implemented mod-8p accumulator, the other through the C fingerprint’s two independent multipliers. The proved scores are 56.18 and 83.99 bits, the second about 84 on inputs of up to 246 words. The post lists the conditions: ideal full keys, a fixed seed and full C outputs. Key derivation, per-call seeds and masked outputs fall outside the theorems, and the paper’s 162/q projection step remains unvalidated.

HalftimeHash came out worse. Its four 64-bit styles get a corrected 63-bit bound under stated execution assumptions and length limits. The original advanced 24-byte function was refuted, and its repaired version is plotted separately. The author’s conclusion is that published proofs are not all audited equally well: some of the gaps could be fixed, and others required code changes.

SipHash-1-3 and SipHash-2-4 remain unresolved, with neither a proof nor a counterexample from the audit. The post cites a 2014 analysis by Dobraunig, Mendel and Schläffer that reports collision characteristics of 2^-167 for SipHash-1-x and 2^-236.3 for SipHash-2-4. The audit’s own search found nothing above 2^-26.4 per pair.

The author is blunt about how far to trust the machine output. The per-hash appendix, he warns, “contains AI slop, and I can’t guarantee everything is correct. I only trust the concrete examples found and measured.”

Is provable slower?

The post’s answer is no, and its evidence is the author’s own hash. ChainHash, built on his work with Jakob Tejs on fast polynomial evaluation, carries a machine-checked 63.0-bit guarantee from 64 uniformly random key bytes. It still ran at 28.31 bytes per cycle on Intel Xeon, the highest throughput of the set there, and 26.26 on Apple M2 Pro, second highest. ChainHash-128 has a machine-checked 127-bit guarantee from 128 random key bytes and ran at 14.43 bytes per cycle on Xeon and 10.26 on M2. All speeds were measured on 256 KiB messages, and the two machines’ timers use different cycle conventions, so the post compares hashes only on the same host.

The author also argues against the obvious overreaction. He hopes people will not respond by “switching everything to ‘cryptographically secure’ hashes like SHA or using AES native instructions,” because provably secure hashes are, in his words, “plentiful and fast.”

What the maintainers said

All findings went to maintainers before publication. Their consensus was that only true multicollision attacks, where a large set of inputs collide with high probability, are worth fixing. A hash could in principle resist multicollisions without being universal. The author calls that “a fair position,” in particular because changing a hash in a backwards-compatible way is hard. He adds that the collisions show the heuristic hashes are not simply universal hashes still waiting for a proof.

The maintainers’ replies are public, in the discussions for xxHash, komihash, MuseAir and foldhash.