[PATCH] ipv6: use a stronger hash for tcp

[PATCH] ipv6: use a stronger hash for tcp

[Eric Dumazet]

From: Eric Dumazet <edumazet@google.com>

It looks like its possible to open thousands of TCP IPv6
sessions on a server, all landing in a single slot of TCP hash
table. Incoming packets have to lookup sockets in a very
long list.

We should hash all bits from foreign IPv6 addresses, using
a salt and hash mix, not a simple XOR.

inet6_ehashfn() can also separately use the ports, instead
of xoring them.

Reported-by: Neal Cardwell <ncardwell@google.com>
Signed-off-by: Eric Dumazet <edumazet@google.com>
Cc: Yuchung Cheng <ycheng@google.com>
---
 include/net/inet6_hashtables.h |    8 ++++----
 include/net/inet_sock.h        |    1 +
 include/net/ipv6.h             |   12 ++++++++++++
 net/ipv4/af_inet.c             |    9 +++++++--
 4 files changed, 24 insertions(+), 6 deletions(-)

diff --git a/include/net/inet6_hashtables.h b/include/net/inet6_hashtables.h
index 7ca75cb..fd4ee01 100644
--- a/include/net/inet6_hashtables.h
+++ b/include/net/inet6_hashtables.h
@@ -28,16 +28,16 @@
 
 struct inet_hashinfo;
 
-/* I have no idea if this is a good hash for v6 or not. -DaveM */
 static inline unsigned int inet6_ehashfn(struct net *net,
 				const struct in6_addr *laddr, const u16 lport,
 				const struct in6_addr *faddr, const __be16 fport)
 {
-	u32 ports = (lport ^ (__force u16)fport);
+	u32 ports = (((u32)lport) << 16) | (__force u32)fport;
 
 	return jhash_3words((__force u32)laddr->s6_addr32[3],
-			    (__force u32)faddr->s6_addr32[3],
-			    ports, inet_ehash_secret + net_hash_mix(net));
+			    ipv6_addr_jhash(faddr),
+			    ports,
+			    inet_ehash_secret + net_hash_mix(net));
 }
 
 static inline int inet6_sk_ehashfn(const struct sock *sk)
diff --git a/include/net/inet_sock.h b/include/net/inet_sock.h
index a4196cb..7235ae7 100644
--- a/include/net/inet_sock.h
+++ b/include/net/inet_sock.h
@@ -203,6 +203,7 @@ static inline void inet_sk_copy_descendant(struct sock *sk_to,
 extern int inet_sk_rebuild_header(struct sock *sk);
 
 extern u32 inet_ehash_secret;
+extern u32 ipv6_hash_secret;
 extern void build_ehash_secret(void);
 
 static inline unsigned int inet_ehashfn(struct net *net,
diff --git a/include/net/ipv6.h b/include/net/ipv6.h
index 851d541..d772f99 100644
--- a/include/net/ipv6.h
+++ b/include/net/ipv6.h
@@ -15,6 +15,7 @@
 
 #include <linux/ipv6.h>
 #include <linux/hardirq.h>
+#include <linux/jhash.h>
 #include <net/if_inet6.h>
 #include <net/ndisc.h>
 #include <net/flow.h>
@@ -514,6 +515,17 @@ static inline u32 ipv6_addr_hash(const struct in6_addr *a)
 #endif
 }
 
+/* more secured version of ipv6_addr_hash() */
+static inline u32 ipv6_addr_jhash(const struct in6_addr *a)
+{
+	u32 v = (__force u32)a->s6_addr32[0] ^ (__force u32)a->s6_addr32[1];
+
+	return jhash_3words(v,
+			    (__force u32)a->s6_addr32[2],
+			    (__force u32)a->s6_addr32[3],
+			    ipv6_hash_secret);
+}
+
 static inline bool ipv6_addr_loopback(const struct in6_addr *a)
 {
 #if defined(CONFIG_HAVE_EFFICIENT_UNALIGNED_ACCESS) && BITS_PER_LONG == 64
diff --git a/net/ipv4/af_inet.c b/net/ipv4/af_inet.c
index e225a4e..9cbcb94 100644
--- a/net/ipv4/af_inet.c
+++ b/net/ipv4/af_inet.c
@@ -248,8 +248,12 @@ EXPORT_SYMBOL(inet_listen);
 u32 inet_ehash_secret __read_mostly;
 EXPORT_SYMBOL(inet_ehash_secret);
 
+u32 ipv6_hash_secret __read_mostly;
+EXPORT_SYMBOL(ipv6_hash_secret);
+
 /*
- * inet_ehash_secret must be set exactly once
+ * inet_ehash_secret must be set exactly once, and to a non nul value
+ * ipv6_hash_secret must be set exactly once.
  */
 void build_ehash_secret(void)
 {
@@ -259,7 +263,8 @@ void build_ehash_secret(void)
 		get_random_bytes(&rnd, sizeof(rnd));
 	} while (rnd == 0);
 
-	cmpxchg(&inet_ehash_secret, 0, rnd);
+	if (cmpxchg(&inet_ehash_secret, 0, rnd) == 0)
+		get_random_bytes(&ipv6_hash_secret, sizeof(ipv6_hash_secret));
 }
 EXPORT_SYMBOL(build_ehash_secret);
 

Re: [PATCH] ipv6: use a stronger hash for tcp

[Hannes Frederic Sowa]

On Thu, Feb 21, 2013 at 02:18:52PM -0800, Eric Dumazet wrote:
> From: Eric Dumazet <edumazet@google.com>
> 
> It looks like its possible to open thousands of TCP IPv6
> sessions on a server, all landing in a single slot of TCP hash
> table. Incoming packets have to lookup sockets in a very
> long list.
> 
> We should hash all bits from foreign IPv6 addresses, using
> a salt and hash mix, not a simple XOR.
> 
> inet6_ehashfn() can also separately use the ports, instead
> of xoring them.

I like this change. Some weeks ago I have looked at the tcp-metrics
cache if the weak ipv6 xor hashes could be used to have negative impact
on servers. Luckily the maximum length of the lists is checked to not
grow beyond 5 entries (after that reclamation kicks in).

With IPv6 this seems to be a new attack scenario with each user having
a /64 they could generate about 2^32 hash colliding ipv6 addresses
(in case of xor hashing) where a full tcp 3whs and shutdown could be made.

Perhaps we should use ipv6_addr_jhash in the destination cache, too, and look
at other uses of ipv6_addr_hash?

Re: [PATCH] ipv6: use a stronger hash for tcp

[Eric Dumazet]

On Thu, 2013-02-21 at 23:43 +0100, Hannes Frederic Sowa wrote:

> 
> Perhaps we should use ipv6_addr_jhash in the destination cache, too, and look
> at other uses of ipv6_addr_hash?

Sure, an audit is needed, but with tcp early demux, TCP lookup was the
first weak point.

Thanks

Re: [PATCH] ipv6: use a stronger hash for tcp

[Hannes Frederic Sowa]

On Thu, Feb 21, 2013 at 02:48:23PM -0800, Eric Dumazet wrote:
> On Thu, 2013-02-21 at 23:43 +0100, Hannes Frederic Sowa wrote:
> 
> > 
> > Perhaps we should use ipv6_addr_jhash in the destination cache, too, and look
> > at other uses of ipv6_addr_hash?
> 
> Sure, an audit is needed, but with tcp early demux, TCP lookup was the
> first weak point.

I had two simple programs to test this. Perhaps they could be helpful
to somebody:

tcpproxy.c - does 3whs and teardown
gensyn6.c -  generates syn packets from /64 range

https://gist.github.com/hannes/5009267

Re: [PATCH] ipv6: use a stronger hash for tcp

[David Miller]

From: Eric Dumazet <eric.dumazet@gmail.com>
Date: Thu, 21 Feb 2013 14:18:52 -0800

> From: Eric Dumazet <edumazet@google.com>
> 
> It looks like its possible to open thousands of TCP IPv6
> sessions on a server, all landing in a single slot of TCP hash
> table. Incoming packets have to lookup sockets in a very
> long list.
> 
> We should hash all bits from foreign IPv6 addresses, using
> a salt and hash mix, not a simple XOR.
> 
> inet6_ehashfn() can also separately use the ports, instead
> of xoring them.
> 
> Reported-by: Neal Cardwell <ncardwell@google.com>
> Signed-off-by: Eric Dumazet <edumazet@google.com>

Applied, and queued up for -stable, thanks Eric.

I bet we can consolidate this slightly, to make it less
expensive yet not give up much in terms of protection.  Two
jhash3word()'s is quite a lot.

Re: [PATCH] ipv6: use a stronger hash for tcp

[Andi Kleen]

David Miller <davem@davemloft.net> writes:
>
> I bet we can consolidate this slightly, to make it less
> expensive yet not give up much in terms of protection.  Two
> jhash3word()'s is quite a lot.

jhash is not really the state of the art for general hashing anymore,
murmur3 or cityhash are generally considered faster/possibly better.

-Andi

-- 
ak@linux.intel.com -- Speaking for myself only

Re: [PATCH] ipv6: use a stronger hash for tcp

[Hannes Frederic Sowa]

On Thu, Feb 21, 2013 at 03:49:16PM -0800, Andi Kleen wrote:
> David Miller <davem@davemloft.net> writes:
> >
> > I bet we can consolidate this slightly, to make it less
> > expensive yet not give up much in terms of protection.  Two
> > jhash3word()'s is quite a lot.
> 
> jhash is not really the state of the art for general hashing anymore,
> murmur3 or cityhash are generally considered faster/possibly better.

murmur3 and cityhash are broken in terms of collision resistance.  I have
not heard anything about jenkins being affected (but have not searched
either). SipHash is a relativly new hash function specifically designed
to protect against hashdos, but I fear it could be more expansive for very
small inputs: https://131002.net/siphash/

Greetings,

  Hannes

Re: [PATCH] ipv6: use a stronger hash for tcp

[David Miller]

From: Andi Kleen <andi@firstfloor.org>
Date: Thu, 21 Feb 2013 15:49:16 -0800

> murmur3

Two multiplies per mix(), no thanks.  We might as well use a universal
hash like the one we use for ARP hashing, which incurs only one
multiply.

jhash() is definitely going to perform much better than murmur3 on a
wide range of cpus.

jhash() is just a series of simple shifts and additions to mix the
data (which every cpu can do cheaply), whereas murmur3 is jhash()'s
overhead plus two multiplies per mix pass.

For our purposes, therefore, Jenkins is still superior.

> cityhash

And cityhash uses the two multiply mix() function from murmur3, thus
has the same problem.

These hashes actually look quite terrible for kernel hash table hashes.