[PATCH net] netlink: use jhash as hashfn for rhashtable

[PATCH net] netlink: use jhash as hashfn for rhashtable

[Daniel Borkmann]

For netlink, we shouldn't be using arch_fast_hash() as a hashing
discipline, but rather jhash() instead.

Since netlink sockets can be opened by any user, a local attacker
would be able to easily create collisions with the DPDK-derived
arch_fast_hash(), which trades off performance for security by
using crc32 CPU instructions on x86_64.

While it might have a legimite use case in other places, it should
be avoided in netlink context, though. As rhashtable's API is very
flexible, we could later on still decide on other hashing disciplines,
if legitimate.

Reference: http://thread.gmane.org/gmane.linux.kernel/1844123
Fixes: e341694e3eb5 ("netlink: Convert netlink_lookup() to use RCU protected hash table")
Cc: Herbert Xu <herbert@gondor.apana.org.au>
Cc: Thomas Graf <tgraf@suug.ch>
Cc: Hannes Frederic Sowa <hannes@stressinduktion.org>
Signed-off-by: Daniel Borkmann <dborkman@redhat.com>
---
 net/netlink/af_netlink.c | 2 +-
 1 file changed, 1 insertion(+), 1 deletion(-)

diff --git a/net/netlink/af_netlink.c b/net/netlink/af_netlink.c
index 0007b81..b6bf8e8 100644
--- a/net/netlink/af_netlink.c
+++ b/net/netlink/af_netlink.c
@@ -3130,7 +3130,7 @@ static int __init netlink_proto_init(void)
 		.head_offset = offsetof(struct netlink_sock, node),
 		.key_offset = offsetof(struct netlink_sock, portid),
 		.key_len = sizeof(u32), /* portid */
-		.hashfn = arch_fast_hash,
+		.hashfn = jhash,
 		.max_shift = 16, /* 64K */
 		.grow_decision = rht_grow_above_75,
 		.shrink_decision = rht_shrink_below_30,
-- 
1.7.11.7

Re: [PATCH net] netlink: use jhash as hashfn for rhashtable

[Thomas Graf]

On 12/08/14 at 05:30pm, Daniel Borkmann wrote:
> For netlink, we shouldn't be using arch_fast_hash() as a hashing
> discipline, but rather jhash() instead.
> 
> Since netlink sockets can be opened by any user, a local attacker
> would be able to easily create collisions with the DPDK-derived
> arch_fast_hash(), which trades off performance for security by
> using crc32 CPU instructions on x86_64.
> 
> While it might have a legimite use case in other places, it should
> be avoided in netlink context, though. As rhashtable's API is very
> flexible, we could later on still decide on other hashing disciplines,
> if legitimate.
> 
> Reference: http://thread.gmane.org/gmane.linux.kernel/1844123
> Fixes: e341694e3eb5 ("netlink: Convert netlink_lookup() to use RCU protected hash table")
> Cc: Herbert Xu <herbert@gondor.apana.org.au>
> Cc: Thomas Graf <tgraf@suug.ch>
> Cc: Hannes Frederic Sowa <hannes@stressinduktion.org>
> Signed-off-by: Daniel Borkmann <dborkman@redhat.com>

Acked-by: Thomas Graf <tgraf@suug.ch>

Re: [PATCH net] netlink: use jhash as hashfn for rhashtable

[Hannes Frederic Sowa]

On Mo, 2014-12-08 at 17:30 +0100, Daniel Borkmann wrote:
> For netlink, we shouldn't be using arch_fast_hash() as a hashing
> discipline, but rather jhash() instead.
> 
> Since netlink sockets can be opened by any user, a local attacker
> would be able to easily create collisions with the DPDK-derived
> arch_fast_hash(), which trades off performance for security by
> using crc32 CPU instructions on x86_64.
> 
> While it might have a legimite use case in other places, it should
> be avoided in netlink context, though. As rhashtable's API is very
> flexible, we could later on still decide on other hashing disciplines,
> if legitimate.
> 
> Reference: http://thread.gmane.org/gmane.linux.kernel/1844123
> Fixes: e341694e3eb5 ("netlink: Convert netlink_lookup() to use RCU protected hash table")
> Cc: Herbert Xu <herbert@gondor.apana.org.au>
> Cc: Thomas Graf <tgraf@suug.ch>
> Cc: Hannes Frederic Sowa <hannes@stressinduktion.org>
> Signed-off-by: Daniel Borkmann <dborkman@redhat.com>
> ---
>  net/netlink/af_netlink.c | 2 +-
>  1 file changed, 1 insertion(+), 1 deletion(-)
> 
> diff --git a/net/netlink/af_netlink.c b/net/netlink/af_netlink.c
> index 0007b81..b6bf8e8 100644
> --- a/net/netlink/af_netlink.c
> +++ b/net/netlink/af_netlink.c
> @@ -3130,7 +3130,7 @@ static int __init netlink_proto_init(void)
>  		.head_offset = offsetof(struct netlink_sock, node),
>  		.key_offset = offsetof(struct netlink_sock, portid),
>  		.key_len = sizeof(u32), /* portid */
> -		.hashfn = arch_fast_hash,
> +		.hashfn = jhash,
>  		.max_shift = 16, /* 64K */
>  		.grow_decision = rht_grow_above_75,
>  		.shrink_decision = rht_shrink_below_30,

Acked-by: Hannes Frederic Sowa <hannes@stressinduktion.org>

In net-next, some time soon, we should try to let all function pointers
to jhash() use one non-inline version. The other arch_fast_hash patch
adds __jhash for x86-only, we can move it over to lib/.

Thanks,
Hannes

Re: [PATCH net] netlink: use jhash as hashfn for rhashtable

[Dave Taht]

On Mon, Dec 8, 2014 at 8:56 AM, Hannes Frederic Sowa
<hannes@stressinduktion.org> wrote:
> On Mo, 2014-12-08 at 17:30 +0100, Daniel Borkmann wrote:
>> For netlink, we shouldn't be using arch_fast_hash() as a hashing
>> discipline, but rather jhash() instead.

I am not particularly happy with the amount of entropy in

static inline u32 ipv6_addr_hash(const struct in6_addr *a)
{
#if defined(CONFIG_HAVE_EFFICIENT_UNALIGNED_ACCESS) && BITS_PER_LONG == 64
        const unsigned long *ul = (const unsigned long *)a;
        unsigned long x = ul[0] ^ ul[1];

        return (u32)(x ^ (x >> 32));
#else
        return (__force u32)(a->s6_addr32[0] ^ a->s6_addr32[1] ^
                             a->s6_addr32[2] ^ a->s6_addr32[3]);
#endif
}

is this worth improving somehow?

>> Since netlink sockets can be opened by any user, a local attacker
>> would be able to easily create collisions with the DPDK-derived
>> arch_fast_hash(), which trades off performance for security by
>> using crc32 CPU instructions on x86_64.
>>
>> While it might have a legimite use case in other places, it should
>> be avoided in netlink context, though. As rhashtable's API is very
>> flexible, we could later on still decide on other hashing disciplines,
>> if legitimate.
>>
>> Reference: http://thread.gmane.org/gmane.linux.kernel/1844123
>> Fixes: e341694e3eb5 ("netlink: Convert netlink_lookup() to use RCU protected hash table")
>> Cc: Herbert Xu <herbert@gondor.apana.org.au>
>> Cc: Thomas Graf <tgraf@suug.ch>
>> Cc: Hannes Frederic Sowa <hannes@stressinduktion.org>
>> Signed-off-by: Daniel Borkmann <dborkman@redhat.com>
>> ---
>>  net/netlink/af_netlink.c | 2 +-
>>  1 file changed, 1 insertion(+), 1 deletion(-)
>>
>> diff --git a/net/netlink/af_netlink.c b/net/netlink/af_netlink.c
>> index 0007b81..b6bf8e8 100644
>> --- a/net/netlink/af_netlink.c
>> +++ b/net/netlink/af_netlink.c
>> @@ -3130,7 +3130,7 @@ static int __init netlink_proto_init(void)
>>               .head_offset = offsetof(struct netlink_sock, node),
>>               .key_offset = offsetof(struct netlink_sock, portid),
>>               .key_len = sizeof(u32), /* portid */
>> -             .hashfn = arch_fast_hash,
>> +             .hashfn = jhash,
>>               .max_shift = 16, /* 64K */
>>               .grow_decision = rht_grow_above_75,
>>               .shrink_decision = rht_shrink_below_30,
>
> Acked-by: Hannes Frederic Sowa <hannes@stressinduktion.org>
>
> In net-next, some time soon, we should try to let all function pointers
> to jhash() use one non-inline version. The other arch_fast_hash patch
> adds __jhash for x86-only, we can move it over to lib/.
>
> Thanks,
> Hannes
>
>
> --
> To unsubscribe from this list: send the line "unsubscribe netdev" in
> the body of a message to majordomo@vger.kernel.org
> More majordomo info at  http://vger.kernel.org/majordomo-info.html



-- 
Dave Täht

http://www.bufferbloat.net/projects/bloat/wiki/Upcoming_Talks

Re: [PATCH net] netlink: use jhash as hashfn for rhashtable

[Hannes Frederic Sowa]

On Mon, Dec 8, 2014, at 18:20, Dave Taht wrote:
> On Mon, Dec 8, 2014 at 8:56 AM, Hannes Frederic Sowa
> <hannes@stressinduktion.org> wrote:
> > On Mo, 2014-12-08 at 17:30 +0100, Daniel Borkmann wrote:
> >> For netlink, we shouldn't be using arch_fast_hash() as a hashing
> >> discipline, but rather jhash() instead.
> 
> I am not particularly happy with the amount of entropy in
> 
> static inline u32 ipv6_addr_hash(const struct in6_addr *a)
> {
> #if defined(CONFIG_HAVE_EFFICIENT_UNALIGNED_ACCESS) && BITS_PER_LONG ==
> 64
>         const unsigned long *ul = (const unsigned long *)a;
>         unsigned long x = ul[0] ^ ul[1];
> 
>         return (u32)(x ^ (x >> 32));
> #else
>         return (__force u32)(a->s6_addr32[0] ^ a->s6_addr32[1] ^
>                              a->s6_addr32[2] ^ a->s6_addr32[3]);
> #endif
> }
> 
> is this worth improving somehow?
> 

That's e.g. the reason why we have

commit 5a3da1fe9561828d0ca7eca664b16ec2b9bf0055
Author: Hannes Frederic Sowa <hannes@stressinduktion.org>
Date:   Fri Mar 15 11:32:30 2013 +0000

    inet: limit length of fragment queue hash table bucket lists

Note, __ipv6_addr_jhash (xoring the upper 32 bit before jhashing them)
has the same problem. I currently cannot spot any problematic users in
the kernel, flow dissector hashes are insecure by nature, local
addresses normally don't have problems with hash collisions. But maybe I
should redo an audit. :)

Bye,
Hannes

Re: [PATCH net] netlink: use jhash as hashfn for rhashtable

[David Miller]

From: Daniel Borkmann <dborkman@redhat.com>
Date: Mon,  8 Dec 2014 17:30:30 +0100

> For netlink, we shouldn't be using arch_fast_hash() as a hashing
> discipline, but rather jhash() instead.
> 
> Since netlink sockets can be opened by any user, a local attacker
> would be able to easily create collisions with the DPDK-derived
> arch_fast_hash(), which trades off performance for security by
> using crc32 CPU instructions on x86_64.
> 
> While it might have a legimite use case in other places, it should
> be avoided in netlink context, though. As rhashtable's API is very
> flexible, we could later on still decide on other hashing disciplines,
> if legitimate.
> 
> Reference: http://thread.gmane.org/gmane.linux.kernel/1844123
> Fixes: e341694e3eb5 ("netlink: Convert netlink_lookup() to use RCU protected hash table")
> Cc: Herbert Xu <herbert@gondor.apana.org.au>
> Cc: Thomas Graf <tgraf@suug.ch>
> Cc: Hannes Frederic Sowa <hannes@stressinduktion.org>
> Signed-off-by: Daniel Borkmann <dborkman@redhat.com>

I think I've seen enough of this.

First of all, you've left all of the example initializers in the
rhashtable implementation recommending to use arch_fast_hash.

Secondly, after this, openvswitch (and nfsd, ugh) are the only users
remaining.   Even though there have been claims that using this
doesn't expose to openvswitch to being hash attackable, I'm still
not entirely convinced that an attacker cannot hurt performance
of an OVS node as a result of this.

I think this whole scheme should be reverted, whatever cycles
openvswitch gains by using crc32c instructions is far outweighed
by the confusion this has caused and all of this infrastructure
created for just one or two users.

Someone send me a patch to revert all of the arch_fast_hash
stuff, and every reference thereof, or else I'll do it myself.

Thanks.

Re: [PATCH net] netlink: use jhash as hashfn for rhashtable

[Daniel Borkmann]

On 12/09/2014 08:38 PM, David Miller wrote:
> From: Daniel Borkmann <dborkman@redhat.com>
> Date: Mon,  8 Dec 2014 17:30:30 +0100
>
>> For netlink, we shouldn't be using arch_fast_hash() as a hashing
>> discipline, but rather jhash() instead.
>>
>> Since netlink sockets can be opened by any user, a local attacker
>> would be able to easily create collisions with the DPDK-derived
>> arch_fast_hash(), which trades off performance for security by
>> using crc32 CPU instructions on x86_64.
>>
>> While it might have a legimite use case in other places, it should
>> be avoided in netlink context, though. As rhashtable's API is very
>> flexible, we could later on still decide on other hashing disciplines,
>> if legitimate.
>>
>> Reference: http://thread.gmane.org/gmane.linux.kernel/1844123
>> Fixes: e341694e3eb5 ("netlink: Convert netlink_lookup() to use RCU protected hash table")
>> Cc: Herbert Xu <herbert@gondor.apana.org.au>
>> Cc: Thomas Graf <tgraf@suug.ch>
>> Cc: Hannes Frederic Sowa <hannes@stressinduktion.org>
>> Signed-off-by: Daniel Borkmann <dborkman@redhat.com>
>
> I think I've seen enough of this.
>
> First of all, you've left all of the example initializers in the
> rhashtable implementation recommending to use arch_fast_hash.
>
> Secondly, after this, openvswitch (and nfsd, ugh) are the only users
> remaining.   Even though there have been claims that using this
> doesn't expose to openvswitch to being hash attackable, I'm still
> not entirely convinced that an attacker cannot hurt performance
> of an OVS node as a result of this.
>
> I think this whole scheme should be reverted, whatever cycles
> openvswitch gains by using crc32c instructions is far outweighed
> by the confusion this has caused and all of this infrastructure
> created for just one or two users.
>
> Someone send me a patch to revert all of the arch_fast_hash
> stuff, and every reference thereof, or else I'll do it myself.

Hm, this netlink patch was actually meant to be small for -stable.

But fair enough, I can look into removing arch_fast_hash() bits
entirely, sure - we thought it was useful in that area as it needs
less than half the cycles (all discussed in [1]) as opposed to
jhash for computing the hash value in ovs, where such computations
are being done very frequently and the flow key structure size seems
to keep growing.

Regarding an attacker wanting to hurt performance, upcalls into ovs
user space component to dynamically install such colliding in-kernel
ovs flow-cache entries would be the much bigger concern then, as a
pre-required step, imho. Anyway, if you feel strong about it, lets
just remove it.

Thanks.

   [1] http://patchwork.ozlabs.org/patch/299369/

Re: [PATCH net] netlink: use jhash as hashfn for rhashtable

[David Miller]

From: Daniel Borkmann <dborkman@redhat.com>
Date: Tue, 09 Dec 2014 23:56:40 +0100

> we thought it was useful in that area as it needs less than half the
> cycles (all discussed in [1]) as opposed to jhash for computing the
> hash value in ovs, where such computations are being done very
> frequently and the flow key structure size seems to keep growing.

If that is the case, you could instead come up with a portable C hash
function that doesn't require jumping through hoops to use special CPU
instructions yet still has the better performance you're looking for.

Heck, if attackability isn't an issue, plain ole 'xor' over the u32's
of the key is sufficient and in fact is what our TCP socket hash used
to be before jhash.

> Anyway, if you feel strong about it, lets just remove it.

Please do.