Re: Hash Table Collisions (n.runs-SA-2011.004)

[Gé Weijers <ge@...>]

On Friday, January 6, 2012, Jay Carlson  wrote:
> I wonder if combining a secret seed with the contents of the
>
> accumulated hash to choose how far to jump ahead each time is
> sufficiently annoying. Instead of jumping ahead stepsize, jump ahead
> stepsize+(h%stepsize) and mix a few bytes in. We don't need to always
> use the same number of samples for a given length either, right?

If the string is long enough (say >= 100 chars) you have a 50% chance of not hitting any 32 indices if you randomly choose 4 positions. So it's easy enough to create collisions by trying until the victim grinds to a halt.

Using a combinations of a secret seed (or better: a universal hashing scheme, which would be a small # of secret seeds) and using on-demand-only hashing for long strings is the best approach I've heard so far.

Gé

-- 
Gé