Adversarial examples for fast hash functions(thomasahle.com) |
Adversarial examples for fast hash functions(thomasahle.com) |
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.
1. A permutation that does as much as possible of the actual bit-mixing and
2. The simplest compression rule possible, though combining can be tricky.
Good permutations are much easier to design than good hashes, and one of the main ways hash functions are used is consuming integers smaller than the state space. May as well take advantage of provably ideal behavior.
h(x1, x2, ...) = T[1, x1] ^ T[2, x2] ^ ...