Re: Better hash functions (was Re: Route cache performance under stress)

[Willy Tarreau <willy@w.ods.org>]

 
> As stated, I was assuming that you masked off the lowest 12 bits and
> used that for the bucket number. This is typical in most code; if your
> function doesn't do that, you should have said so.

OK
 
> On a P2 benchmark system, hashing one byte at a time this approach
> with 64 bit multiplies and 32-bit modulation operation is just as fast
> as Perl's shift-based hash function.

I agree for recent x86 processors, but older or smaller designs would suffer
from multiply and divide.

> > the initial random, you will not exploit it. That's the whole
> > point. Try to find a generic attack against this part of code, where
> > 0x12345678 is a random number. Perhaps you can, but I couldn't.
> 
> Actually, this is relatively strightforward to break.

OK, I agree with your demo, you convinced me.

> Trust me. Find a good universal hash function in the literature and
> use it. I don't know about you, but inventing my own is beyond my
> skill. I already tried it once, in my earlier message, and made a
> mistake; I've already elided out two others I was about to make in
> this message.

well, the only hash function I wrote myself only had to suit my needs, and
didn't have to be resistant to hash attacks. But I agree that the strongest
functions you'll find are those which have been publicly available for years
and still remain uncracked.

Regards,
Willy