Adversarial examples for fast hash functions

A broad audit of fast, non-cryptographic hash functions examines whether high-throughput designs actually provide strong collision guarantees when an attacker chooses inputs without knowing the secret key. Using a combination of empirical testing (SMHasher workloads) and automated symbolic/search assistance, the audit finds many popular hashes trade collision resistance for speed and exhibit worst-case inputs that lose at least ~20 bits of expected security. Concrete weaknesses include seed-independent colliding pairs, few-way collisions, weak-key multicollisions and even seed-independent multicollisions; several implementations yield flooding-grade, key-free multicollisions. The analysis also checked published proofs, machine-checked some in Lean, and found mistakes in others, changing the practical threat model because AI tools make it easier to find adversarial inputs.

The audit presents a speed-vs-collision chart measured on Apple M2 Pro and Intel Xeon and reports specific, tested guarantees: UMASH headline bounds are now proved (about 56.18 and 83.99 bits under stated assumptions), ChainHash achieves top throughput (28.31 B/cycle on Xeon, 26.26 on M2) with a machine-checked 63-bit guarantee from 64 random key bytes and ChainHash-128 gives 127-bit guarantees. HalftimeHash needed a corrected 63-bit bound; SipHash claims remain unresolved. All findings were disclosed to maintainers. The takeaway: provable, verified universal hashes can match or exceed the speed of heuristic designs and should be preferred where robustness against chosen-input collisions matters.