lua-users home
lua-l archive

[Date Prev][Date Next][Thread Prev][Thread Next] [Date Index] [Thread Index]

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.