Adversarial examples for fast hash functions | Hacker News Reader

Adversarial examples for fast hash functions

thomasahle.com

10 pointsibobev3 comments

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.

Most non-CS hashes should have two parts:

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.

Yes, a good example is tabulation hashes which is

    h(x1, x2, ...) = T[1, x1] ^ T[2, x2] ^ ...

but most fast hashes are actually algebraic, typically using polynomials in some way. I'm not sure they fit into the same pattern?

Reply on news.ycombinator.com