Adversarial examples for fast hash functions

Non-cryptographic hashing should not mean "no guarantees". Unfortunately it's very hard to empirically test if a pseudorandom function works well on all inputs.

We analyzed 30 popular hashes and found Key-independent collisions in nearly all of them. E.g. xxh3 has pairs that collide with probability 2^{-10}, much higher than the 2^{-64} you'd expect.

However some fast hashes are good on all inputs, and we were able to verify it in Lean.