Re: RFC: Established connections hash function

["Nikolaos D. Bougalis" <nikb@webmaster.com>]

On Thu, March 22, 2007 at 8:52 AM, Evgeniy Polyakov <johnpol@2ka.mipt.ru> 
wrote:

> It seems you do not know a history...

    I know a lot about history. I may not know the specific history you had 
in mind though.

    I do see now that this has been brought up before. Before posting, I did 
search the archives, but obviously not closely enough. I blame it on the 
early morning hour.


> It is the fastest and actually the best hash for that workloads where it
> is used, but unfortunately it is too simple for attacker to predict end
> result.

    Yes, the distribution of the vanilla function is decent, and yes it's 
very fast. But all that won't help you when chains start having tens of 
thousands of items, and you have to iterate through them constantly. But I 
guess that if it makes you feel better, you can call that "unfortunate."


>> unsigned int inet_ehashfn(const __be32 laddr, const __u16 lport,
>>                          const __be32 faddr, const __be16 fport)
>> {
>>    return jhash_3words((__force __u32)faddr, (__force __u32)laddr,
>>                        (((__force __u32)fport) << 16) + lport,
>>                        inet_ehash_rnd);
>> }
>
> And this is utterly broken. For more details please read netdev@
> archives and trivial analysis of jhash_3words().

    Utterly broken? Nonsense. I have tested the actual function I proposed 
(sans the __force and __u32 stuff, which weren't necessary in my test 
program), against real data, collected from various servers in real-time. It 
has consistently achieved lower average chain lengths than the vanilla 
function and demonstrated no artifacting, and that's trivial to verify.

    The only analysis I could find was this 
http://tservice.net.ru/~s0mbre/blog/2006/05/14#2006_05_14, which uses 
jhash_2words, and not jhash_3words, and which naively attempts to take the 
output of jhash_2words, and to perform the same mixing trick that the 
vanilla inet_ehashfn does and uses artificially generated data sets.

    But please, feel free to point out any other _unfavorable_ analyses of 
jhash_2words or jhash_3words that I may have missed.


> We can use jhash_2words(laddr, faddr, portpair^inet_ehash_rnd) though.

    Please explain to me how jhash_2words solves the issue that you claim 
jhash_3words has, when they both use the same underlying bit-mixer?

    -n