Passing a hash test suite says nothing about chosen-input collisions
Serguey Asael Shinder2 min readThomas Dybdahl Ahle has published a systematic study of how the popular fast hash functions behave against chosen inputs rather than random ones, updated 19 September and shipped with verification code, data and an archive: https://thomasahle.com/blog/adversarial-examples-for-hashes/.
The sentence at the top is the whole argument: passing a statistical test suite does not tell you how often an attacker's chosen inputs collide — even when the attacker never learns your seed.
The context is speed. Bulk hashing runs at memory bandwidth — the post cites xxHash at 60 GB/s — and a long list of widely used functions trade adversarial quality for that speed: komihash, a5hash, HighwayHash, SpookyHash, aHash, t1ha2 among them. For years that trade was rational, because nobody was going to do cryptanalysis to slow down your hash table.
The alternative standard is a proof. A hash is b-bit universal if any two inputs of length L collide with probability at most L·2^−b. The study works through the field on that basis — CityHash64, FarmHash64, MurmurHash3, gxhash, MuseAir, MUM, pengyhash, nmhash, mx3, fasthash, SipHash-1-3 and 2-4, Poly1305 and GHASH, Go's maphash, Abseil's hash, .NET's Marvin, foldhash — separating proved guarantees from unresolved claims, and adding proved bounds for UMASH-64/128 and a corrected proof for HalftimeHash.
What it means
A test suite measures the average case; an attacker chooses the input. SMHasher-style batteries answer "does this look random over these test vectors", which is a statement about a distribution nobody is trying to break. The question that decides whether a hash table degrades under load is a different one: what is the worst an adversary can do while knowing your algorithm but not your key. Those two questions have different answers, and only one of them has been measured in most projects.
The failure mode is availability, not secrecy. Nobody reads your data because a non-cryptographic hash collided. Your map goes quadratic, a request that took 3 ms takes 3 seconds, and the service falls over — which is why language runtimes moved to SipHash-class functions for their default maps in the first place, and why "we only hash internal identifiers" deserves a second look when any of those identifiers arrives over the network.
And "we picked a fast hash" is a decision with a threat model attached, whether or not one was written down. For a checksum over files you control, 60 GB/s is the right answer. For a table keyed on user input, the right answer is a function with a proof and a seed the caller cannot observe. The useful outcome of work like this is that the boundary between those two cases can now be cited rather than argued.