Adversarial examples for fast hash functions

iibobev about 8 hours ago 2 commentsRead Article on thomasahle.com

⚡ Community Insights

Discussion Sentiment

100% Positive

Analyzed from 112 words in the discussion.

Discussion (2 Comments)Read Original on HackerNews

thomasahle•about 3 hours ago

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.

AlotOfReading•2 minutes ago

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.