Adversarial examples for fast hash functions

# Adversarial examples for fast hash functions Source: [https://thomasahle.com/blog/adversarial-examples-for-hashes/](https://thomasahle.com/blog/adversarial-examples-for-hashes/) Contents1. [Introduction](https://thomasahle.com/blog/adversarial-examples-for-hashes/#overview) 2. [Chart: speed vs\. collision bounds](https://thomasahle.com/blog/adversarial-examples-for-hashes/#comparison) 3. [Main takeaways](https://thomasahle.com/blog/adversarial-examples-for-hashes/#takeaways) 4. Appendix1. [Appendix A\. The hard cases, hash by hash](https://thomasahle.com/blog/adversarial-examples-for-hashes/#appendix-a) 2. [Recurring patterns](https://thomasahle.com/blog/adversarial-examples-for-hashes/#recurring-patterns) 3. [CityHash64](https://thomasahle.com/blog/adversarial-examples-for-hashes/#appendix-cityhash64) 4. [FarmHash64](https://thomasahle.com/blog/adversarial-examples-for-hashes/#appendix-farmhash64) 5. [gxhash](https://thomasahle.com/blog/adversarial-examples-for-hashes/#appendix-gxhash) 6. [MurmurHash3 x64\_128](https://thomasahle.com/blog/adversarial-examples-for-hashes/#appendix-murmurhash3) 7. [MuseAir](https://thomasahle.com/blog/adversarial-examples-for-hashes/#appendix-museair) 8. [MuseAir v2](https://thomasahle.com/blog/adversarial-examples-for-hashes/#appendix-museair-v2) 9. [komihash](https://thomasahle.com/blog/adversarial-examples-for-hashes/#appendix-komihash) 10. [SpookyHash V2](https://thomasahle.com/blog/adversarial-examples-for-hashes/#appendix-spookyhash) 11. [aHash](https://thomasahle.com/blog/adversarial-examples-for-hashes/#appendix-ahash) 12. [t1ha2](https://thomasahle.com/blog/adversarial-examples-for-hashes/#appendix-t1ha2) 13. [a5hash\-64](https://thomasahle.com/blog/adversarial-examples-for-hashes/#appendix-a5hash-64) 14. [a5hash\-128](https://thomasahle.com/blog/adversarial-examples-for-hashes/#appendix-a5hash-128) 15. [HighwayHash](https://thomasahle.com/blog/adversarial-examples-for-hashes/#appendix-highwayhash) 16. [wyhash final v4\.3](https://thomasahle.com/blog/adversarial-examples-for-hashes/#appendix-wyhash) 17. [rapidhash v1](https://thomasahle.com/blog/adversarial-examples-for-hashes/#appendix-rapidhash-v1) 18. [rapidhash v3](https://thomasahle.com/blog/adversarial-examples-for-hashes/#appendix-rapidhash-v3) 19. [XXH3\-64 0\.8\.3](https://thomasahle.com/blog/adversarial-examples-for-hashes/#appendix-xxh3-64) 20. [XXH3\-128 0\.8\.3](https://thomasahle.com/blog/adversarial-examples-for-hashes/#appendix-xxh3-128) 21. [MUM v3](https://thomasahle.com/blog/adversarial-examples-for-hashes/#appendix-mum) 22. [pengyhash v0\.3](https://thomasahle.com/blog/adversarial-examples-for-hashes/#appendix-pengyhash) 23. [nmhash32 v2](https://thomasahle.com/blog/adversarial-examples-for-hashes/#appendix-nmhash32) 24. [nmhash32x v2](https://thomasahle.com/blog/adversarial-examples-for-hashes/#appendix-nmhash32x) 25. [mx3 v3](https://thomasahle.com/blog/adversarial-examples-for-hashes/#appendix-mx3) 26. [mir \(exact and inexact\)](https://thomasahle.com/blog/adversarial-examples-for-hashes/#appendix-mir) 27. [fasthash \(32\- and 64\-bit\)](https://thomasahle.com/blog/adversarial-examples-for-hashes/#appendix-fasthash) 28. [UMASH\-64/128: both headline bounds proved](https://thomasahle.com/blog/adversarial-examples-for-hashes/#appendix-umash) 29. [HalftimeHash: corrected wrapper proof](https://thomasahle.com/blog/adversarial-examples-for-hashes/#appendix-halftimehash) 30. [HalftimeHash24 \(advanced 24\-byte API, Encode3\)](https://thomasahle.com/blog/adversarial-examples-for-hashes/#appendix-halftime24) 31. [ChainHash: one function, 64 random key bytes](https://thomasahle.com/blog/adversarial-examples-for-hashes/#appendix-chainhash) 32. [ChainHash\-128](https://thomasahle.com/blog/adversarial-examples-for-hashes/#appendix-chainhash128) 33. [HalftimeHash24 fixed](https://thomasahle.com/blog/adversarial-examples-for-hashes/#appendix-halftime24-fixed) 34. [Poly1305 and GHASH](https://thomasahle.com/blog/adversarial-examples-for-hashes/#appendix-classic) 35. [SipHash\-1\-3 and SipHash\-2\-4](https://thomasahle.com/blog/adversarial-examples-for-hashes/#appendix-siphash) 36. [Go maphash](https://thomasahle.com/blog/adversarial-examples-for-hashes/#appendix-go-maphash) 37. [Abseil Hash](https://thomasahle.com/blog/adversarial-examples-for-hashes/#appendix-abseil-hash) 38. [\.NET Marvin](https://thomasahle.com/blog/adversarial-examples-for-hashes/#appendix-dotnet-marvin) 39. [foldhash\-fast 0\.2\.0](https://thomasahle.com/blog/adversarial-examples-for-hashes/#appendix-foldhash-fast) 40. [foldhash\-quality 0\.2\.0](https://thomasahle.com/blog/adversarial-examples-for-hashes/#appendix-foldhash-quality) 41. [How these results were produced](https://thomasahle.com/blog/adversarial-examples-for-hashes/#verification) 42. [Appendix B\. Reproducing the numbers](https://thomasahle.com/blog/adversarial-examples-for-hashes/#appendix-b) 5. [Prior work and acknowledgements](https://thomasahle.com/blog/adversarial-examples-for-hashes/#prior-work-and-acknowledgements) 6. [Updates and corrections](https://thomasahle.com/blog/adversarial-examples-for-hashes/#updates-and-corrections) 7. [Citation](https://thomasahle.com/blog/adversarial-examples-for-hashes/#citation) 8. [Licence](https://thomasahle.com/blog/adversarial-examples-for-hashes/#licence) [Hash functions](https://en.wikipedia.org/wiki/Hash_function)map data of arbitrary length to fixed\-size values\. The goal is to ensure that*distinct inputs*map to*distinct outputs*, except with very small probability over the randomness of a*secret key*used by the hash function\.[This property](https://en.wikipedia.org/wiki/Universal_hashing)ensures we can build fast hash tables where every data point doesn’t*collide*in the same bucket\.[1](https://thomasahle.com/blog/adversarial-examples-for-hashes/#note-bucket-bits) Hashing needs to be fast\.[xxHash](https://github.com/cyan4973/xxhash)boasts 60 GB/s, or basically as fast as you can read memory\. Such bulk hashing is useful for file synchronisation or data integrity checking\. Many popular hashes like*komihash, a5hash, HighwayHash, SpookyHash, aHash*, and*t1ha2*are willing to trade quality, at least for adversarial inputs, for more speed\. This used to be fine\. Many use cases of hashes are low risk, and it’s not worth it for attackers to do expensive cryptanalysis for inputs that make the hashes collide much more often than average\. Still, most hashes try to be*somewhat*robust, to prevent accidentally quadratic slowdowns in algorithms and DoS attacks\. The best hashes give*proofs*that*any*pair of inputs collide with low probability\.This is something unique in a world of cryptography that nobody can prove is actually secure\. Let’s say a hash isb\-bit universal if inputs of lengthLcollide with probability at mostL · 2−bfor allL\. Sometimes the dependency onLis worse, but it’s \(provably\) never better\.[2](https://thomasahle.com/blog/adversarial-examples-for-hashes/#note-length-bound)The question becomes: What is the fastest possible hash that’sb\-bit universal for some desiredb? I was able to use Claude Fable to analyse a broad selection of popular hashes from[SMhasher](https://github.com/rurban/smhasher)—a large project to empirically test statistical properties of hashes\. It found that most of them have inputs on which they perform terribly—at least 20 bits below expectation\. A few hashes have published proofs, and Fable was able to find mistakes in some and verify others in Lean\. Click on any dot in the chart to read the full analysis\. Collision score bounds versus bulk speed\. Speed is logarithmic\. Score uses square\-root spacing to give low scores more room; tick labels show the original bit values\. Solid teal circles are proved lower guarantees; hollow circles are unresolved claims\. Rust diamonds are witness upper caps; crosses mark every\-seed pairs\. Labels identify selected landmarks; every plotted variant is available in the hash selector\. Tab to a point and use arrow keys, Home or End to move between points\. Enter or Space opens its profile\. Escape closes it\. Tap a point or its label on touch screens\.  Inspect a hash Select a hash, or tap a point or label\. **Figure 1\.**Fast implementations can have very different collision guarantees\. Solid dots show what a proof guarantees; rust marks show limits exposed by specific pairs\. The guarantee and the speed measurement may use different key setups—open a profile for those assumptions\. [Full data table](https://thomasahle.com/blog/adversarial-examples-for-hashes/#chart-table-details)·[Data and provenance](https://thomasahle.com/blog/adversarial-examples-for-hashes/data.json)·[Timing reproduction](https://github.com/thomasahle/hash-benchmark-reproduction)·[Hash profiles](https://thomasahle.com/blog/adversarial-examples-for-hashes/figure/profiles.json) How to read the bounds and benchmarksOn the speed axis, equal distances represent equal ratios: moving from 1 to 2 bytes per cycle takes the same space as moving from 10 to 20\. The vertical axis uses square\-root spacing to give low collision scores more room\. Zero stays visible, and all tick labels and profile values show the original scores in bits\. The score is itself logarithmic in the collision bound; see[its definition](https://thomasahle.com/blog/adversarial-examples-for-hashes/#universality)\. Solid teal circles give proved minimum scores\. Hollow circles show unproved claims\. Rust diamonds cap the score using a specific pair of distinct messages that collide; crosses identify pairs that collide for every seed\. An asterisk means the cap uses a sampled rate\. Finding no worse pair does not prove that none exists, so these caps are not a ranking of safety\. A cross can sit above zero because the score adjusts for message length\. All plotted variants are available in the selector, including the four HalftimeHash styles, which each return 64 bits\. The separate historical[32\-byte pair A](https://thomasahle.com/blog/adversarial-examples-for-hashes/verify/xxh3-64/HISTORICAL.html)gave 9, 12, 11 and 11 collisions per 230keys in wyhash, rapidhash v1, rapidhash v3 and XXH3\-64\. The selected XXH3\-64 pair has a different measured rate: about 527 of every 2^36 keys \(sampled; 527 events, pooled\)\. Search effort was unequal; these witness caps do not rank hashes\.[Current pair and count provenance](https://thomasahle.com/blog/adversarial-examples-for-hashes/verify/xxh3-64/README.html)\. Speed is measured on 256 KiB messages, regardless of the length of the colliding pair\. “B/cycle” means bytes processed per reported timer cycle; larger is faster\. The M2 and Xeon timers use different cycle conventions, so compare hashes on the same host\. The separate short\-input measurements use 1–31 bytes\. Foldhash uses a verified port with control measurements\. GHASH is timed through OpenSSL’s GMAC interface, including setup costs\. The benchmark protocol records the timers, repeated runs and calibration details\. Both published UMASH headline bounds are now proved by different routes: the implemented mod\-8p accumulator and the C fingerprint’s two independent multipliers\. The solid points show 56\.18 and 83\.99 bits \(about 84 on L ≤ 246words\), for ideal full keys, a fixed seed and full C outputs\. Key derivation, per\-call seeds and masked outputs are outside these theorems; the paper’s 162/q projection step remains unvalidated\. The four 64\-bit HalftimeHash styles have a corrected 63\-bit bound under the stated execution assumptions and length limits\. The original advanced 24\-byte function was refuted; its repaired version is plotted separately\. ChainHash is one 64\-bit function on both hosts: 28\.31 B/cycle on Xeon and 26\.26 on M2, with a machine\-checked 63\.0\-bit guarantee from 64 uniformly random key bytes\. ChainHash\-128 is the 128\-bit function, again one function on both hosts: 14\.43 B/cycle on Xeon and 10\.26 on M2, with a machine\-checked 127\-bit guarantee from 128 random key bytes\. SipHash\-1\-3 and SipHash\-2\-4 are plotted as unresolved claims at their 64\-bit output width\. This audit supplies neither a proof nor a counterexample for these SipHash bounds\. The cited 2014 analysis reports collision characteristics of 2\-167for SipHash\-1\-x and 2\-236\.3for SipHash\-2\-4 \(Dobraunig, Mendel and Schläffer, 2014\), and our own search sees nothing above 2\-26\.4per pair\. Some historical collision examples have no matching timing, so they are absent from the chart\. See the[proof notes](https://thomasahle.com/blog/adversarial-examples-for-hashes/#appendix-umash)for the distinctions\. The main takeaways: 1. AI changes the threat model: Software that used to be secure mostly from obscurity is now easy to break\. If you can get provably correct software, take it\. 2. Provable hashes are just as fast as heuristic hashes\. Our own hash, ChainHash, built on my work with Jakob Tejs on[Fast Polynomial Evaluation](https://thomasahle.com/fast-polynomials/), had the highest throughput among all the hashes on Intel Xeon, second highest on Apple M2 Pro\. 3. Proofs of correctness are good, but verified Lean proofs are better\. Not everything published is audited equally well, and we found multiple gaps, some of which could be fixed, and others that required code changes\. All the findings were disclosed upstream to maintainers before the publication of this blog post\. You can read the maintainers’ replies in the discussions for[xxHash](https://github.com/Cyan4973/xxHash/issues/1127#issuecomment-5720905442),[komihash](https://github.com/avaneev/komihash/issues/23#issuecomment-5738942086),[MuseAir](https://github.com/eternal-io/museair/issues/4#issuecomment-5741752858), and[foldhash](https://github.com/orlp/foldhash/issues/50#issuecomment-5734983476)\. The consenus was that only true*multicollision*attacks, where a large set of inputs all collide with high probability are worth fixing\. Universal hashing protects against that, but in principle a hash could be robust to multicollisions and not be universal\. That's a fair position, in particular since changing the hash is hard to do backwards compatibly\. However, for this blog post we focus on*provable guarantees*, and the discovered collisions prove that the heuristic hashes are not just universal hashes that haven't been proven correct yet\. And we also did find flooding\-grade key\-free multicollisions for many hashes\.[3](https://thomasahle.com/blog/adversarial-examples-for-hashes/#note-multicollisions) Hash robustness: colliding inputs and affected keysFour categories of hash robustness issues, shown side by side: seed\-independent pairs, few\-way collisions, weak\-key multicollisions, and seed\-independent multicollisions\. Each category has a short definition and its most directly relevant applications\. All inputs discussed here are chosen without knowing the secret key\.Seed\-independent pairThe same two distinct inputscollide for every key\.Use for: Fingerprinting,hash\-based equality,deduplication, approximatemembership filters\.Few\-way collisionsA small set collides forsome keys\.Use for: Cuckoo hashing,bounded\-capacity buckets,hash\-indexed caches andhardware tables\.Weak\-key multicollisionA large fixed set collidesfor a fraction of keys\.Use for: Randomizeddictionaries, long\-livedcaches, hash\-basedpartitioning\.MulticollisionsA large fixed set collidesfor every key\.Use for: Maps and sets,hash\-based databaseoperations, sharding,distinct\-count sketches\.Hash robustness: colliding inputs and affected keysFour categories of hash robustness issues, shown side by side: seed\-independent pairs, few\-way collisions, weak\-key multicollisions, and seed\-independent multicollisions\. Each category has a short definition and its most directly relevant applications\. All inputs discussed here are chosen without knowing the secret key\.Seed\-independent pairThe same two distinct inputscollide for every key\.Use for: Fingerprinting,hash\-based equality,deduplication, approximatemembership filters\.Few\-way collisionsA small set collides forsome keys\.Use for: Cuckoo hashing,bounded\-capacity buckets,hash\-indexed caches andhardware tables\.Weak\-key multicollisionA large fixed set collidesfor a fraction of keys\.Use for: Randomizeddictionaries, long\-livedcaches, hash\-basedpartitioning\.MulticollisionsA large fixed set collidesfor every key\.Use for: Maps and sets,hash\-based databaseoperations, sharding,distinct\-count sketches\.Hash robustness: colliding inputs and affected keysFour categories of hash robustness issues, shown side by side: seed\-independent pairs, few\-way collisions, weak\-key multicollisions, and seed\-independent multicollisions\. Each category has a short definition and its most directly relevant applications\. All inputs discussed here are chosen without knowing the secret key\.Seed\-independent pairThe same two distinct inputscollide for every key\.Use for: Fingerprinting,hash\-based equality,deduplication, approximatemembership filters\.Few\-way collisionsA small set collides forsome keys\.Use for: Cuckoo hashing,bounded\-capacity buckets,hash\-indexed caches andhardware tables\.Weak\-key multicollisionA large fixed set collidesfor a fraction of keys\.Use for: Randomizeddictionaries, long\-livedcaches, hash\-basedpartitioning\.MulticollisionsA large fixed set collidesfor every key\.Use for: Maps and sets,hash\-based databaseoperations, sharding,distinct\-count sketches\. **Figure 2:**Inputs are chosen without knowing the secret key\. Applications indicate where each weakness is most directly relevant\.[Findings for individual hashes](https://thomasahle.com/blog/adversarial-examples-for-hashes/#note-multicollisions)\.Hopefully this work will inspire research into even faster provable hashes\. Many of the “exploits” used similar bad patterns repeated across many hash families\. Hopefully the knee\-jerk reaction is not just switching everything to “cryptographically secure” hashes like SHA or using AES native instructions\. As we have shown,*provably secure*hashes are plentiful and fast\. If anyone has issues with the above presentation, or would like me to add/update/remove any particular hash, please[contact me on Twitter](https://twitter.com/thomasahle)\. Below follows an appendix with the in\-depth analysis of each hash\. Be warned that it*contains AI slop*, and I can’t guarantee everything is correct\. I only trust the concrete examples found and measured\.