netdev - Re: [PATCH] xfrm: xfrm hash to use Jenkins' hash

lists.openwall.net		lists / announce owl-users owl-dev john-users john-dev passwdqc-users yescrypt popa3d-users / oss-security kernel-hardening musl sabotage tlsify passwords / crypt-dev xvendor / Bugtraq Full-Disclosure linux-kernel linux-netdev linux-ext4 linux-hardening linux-cve-announce PHC
Open Source and information security mailing list archives

Hash Suite: Windows password security audit tool. GUI, reports in PDF.

[<prev] [next>] [<thread-prev] [thread-next>] [day] [month] [year] [list]

Message-ID: <ce10d01f0908052332o1db16460k58ed47849670c6de@mail.gmail.com>
Date:	Thu, 6 Aug 2009 09:32:37 +0300
From:	Jussi Maki <joamaki@...il.com>
To:	David Miller <davem@...emloft.net>
Cc:	netdev@...r.kernel.org
Subject: Re: [PATCH] xfrm: xfrm hash to use Jenkins' hash

Hi David,

Changing the (h >> 16) to ((h >> 16) ^ (h >> 24)) still has the same
problem as given in the example,
that is if you have a set of transports with incrementing addresses
(192.168.0.1-172.16.0.1, 192.168.0.2-172.16.0.2,..) they
still hash to the same value. The reason to this is that it's doing
src^dst in __xfrm4_daddr_saddr_hash.

Should I pursue with fixing the inlining issue in my patch or would
you have any suggestions how I could
fix this by perhaps modifying __xfrm4_daddr_saddr_hash?

On Wed, Aug 5, 2009 at 10:08 PM, David Miller<davem@...emloft.net> wrote:
> From: Jussi Mäki <joamaki@...il.com>
> Date: Wed, 5 Aug 2009 10:41:42 +0300
>
>> Hi,
>>
>> The current xfrm hash functions perform very poorly when a number of
>> policies have the same
>> last byte in source and destination addresses.
>>
>> For example with __xfrm_dst_hash, hmask of 0xfff:
>>
>> 192.168.0.1-172.16.0.1 hashes to 3258
>> 192.168.0.2-172.16.0.2 hashes to 3258
>> ... and so on.
>>
>> This patch addresses the issue by rewriting the xfrm
>> hash functions to use the Jenkins' hash function.
>>
>> Signed-off-by: Jussi Maki <joamaki@...il.com>
>
> jhash expands to a lot of code, and given your description of the
> problem, you could have fixed it by adding 2 instructions (see below)
> instead of 20 or 30 (jhash instruction count) at every hash
> calculation site.
>
> Simply change every instance of:
>
>        (h >> 16)
>
> with
>
>        ((h >> 16) ^ (h >> 24))
>
> As much as I love jhash, it's overkill for fixing this problem.
>
> And if we do end up using jhash, it should get inlined into a
> seperate non-inline function instead of expanding that monster
> 4 or 5 times throughout the XFRM code.
>
> I'm not applying this, either make the simple one-liner fix I
> suggested above work or move the jhash into a non-inline expansion.
>
--
To unsubscribe from this list: send the line "unsubscribe netdev" in
the body of a message to majordomo@...r.kernel.org
More majordomo info at  http://vger.kernel.org/majordomo-info.html