[PATCH] xfrm: xfrm hash to use Jenkins' hash

[PATCH] xfrm: xfrm hash to use Jenkins' hash

[Jussi Mäki]

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@gmail.com>
---
 net/xfrm/xfrm_hash.h |   90 ++++++++++++++++++++++++++-----------------------
 1 files changed, 48 insertions(+), 42 deletions(-)

diff --git a/net/xfrm/xfrm_hash.h b/net/xfrm/xfrm_hash.h
index d401dc8..59d4cb6 100644
--- a/net/xfrm/xfrm_hash.h
+++ b/net/xfrm/xfrm_hash.h
@@ -3,6 +3,7 @@

 #include <linux/xfrm.h>
 #include <linux/socket.h>
+#include <linux/jhash.h>

 static inline unsigned int __xfrm4_addr_hash(xfrm_address_t *addr)
 {
@@ -14,31 +15,27 @@ static inline unsigned int
__xfrm6_addr_hash(xfrm_address_t *addr)
 	return ntohl(addr->a6[2] ^ addr->a6[3]);
 }

-static inline unsigned int __xfrm4_daddr_saddr_hash(xfrm_address_t
*daddr, xfrm_address_t *saddr)
-{
-	return ntohl(daddr->a4 ^ saddr->a4);
-}
-
-static inline unsigned int __xfrm6_daddr_saddr_hash(xfrm_address_t
*daddr, xfrm_address_t *saddr)
-{
-	return ntohl(daddr->a6[2] ^ daddr->a6[3] ^
-		     saddr->a6[2] ^ saddr->a6[3]);
-}
-
-static inline unsigned int __xfrm_dst_hash(xfrm_address_t *daddr,
xfrm_address_t *saddr,
-					   u32 reqid, unsigned short family,
+static inline unsigned int __xfrm_dst_hash(xfrm_address_t *daddr,
+					   xfrm_address_t *saddr,
+					   u32 reqid,
+					   unsigned short family,
 					   unsigned int hmask)
 {
-	unsigned int h = family ^ reqid;
+	unsigned int shash = 0;
+	unsigned int dhash = 0;
+
 	switch (family) {
 	case AF_INET:
-		h ^= __xfrm4_daddr_saddr_hash(daddr, saddr);
+		shash = __xfrm4_addr_hash(saddr);
+		dhash = __xfrm4_addr_hash(daddr);
 		break;
 	case AF_INET6:
-		h ^= __xfrm6_daddr_saddr_hash(daddr, saddr);
-		break;
+		shash = __xfrm6_addr_hash(saddr);
+		dhash = __xfrm6_addr_hash(daddr);
 	}
-	return (h ^ (h >> 16)) & hmask;
+
+	return jhash_3words(shash, dhash,
+			    reqid, family) & hmask;
 }

 static inline unsigned __xfrm_src_hash(xfrm_address_t *daddr,
@@ -46,32 +43,37 @@ static inline unsigned
__xfrm_src_hash(xfrm_address_t *daddr,
 				       unsigned short family,
 				       unsigned int hmask)
 {
-	unsigned int h = family;
+	unsigned int shash = 0;
+	unsigned int dhash = 0;
 	switch (family) {
 	case AF_INET:
-		h ^= __xfrm4_daddr_saddr_hash(daddr, saddr);
+		shash = __xfrm4_addr_hash(saddr);
+		dhash = __xfrm4_addr_hash(daddr);
 		break;
 	case AF_INET6:
-		h ^= __xfrm6_daddr_saddr_hash(daddr, saddr);
-		break;
-	};
-	return (h ^ (h >> 16)) & hmask;
+		shash = __xfrm6_addr_hash(saddr);
+		dhash = __xfrm6_addr_hash(daddr);
+	}
+	return jhash_2words(shash, dhash, family) & hmask;
 }

 static inline unsigned int
-__xfrm_spi_hash(xfrm_address_t *daddr, __be32 spi, u8 proto, unsigned
short family,
+__xfrm_spi_hash(xfrm_address_t *daddr, __be32 spi, u8 proto,
+		unsigned short family,
 		unsigned int hmask)
 {
-	unsigned int h = (__force u32)spi ^ proto;
+	unsigned int h = 0;
+
 	switch (family) {
 	case AF_INET:
-		h ^= __xfrm4_addr_hash(daddr);
+		h = __xfrm4_addr_hash(daddr);
 		break;
 	case AF_INET6:
-		h ^= __xfrm6_addr_hash(daddr);
+		h = __xfrm6_addr_hash(daddr);
 		break;
 	}
-	return (h ^ (h >> 10) ^ (h >> 20)) & hmask;
+
+	return jhash_3words(h, spi, proto, family) & hmask;
 }

 static inline unsigned int __idx_hash(u32 index, unsigned int hmask)
@@ -83,7 +85,8 @@ static inline unsigned int __sel_hash(struct
xfrm_selector *sel, unsigned short
 {
 	xfrm_address_t *daddr = &sel->daddr;
 	xfrm_address_t *saddr = &sel->saddr;
-	unsigned int h = 0;
+	unsigned int shash = 0;
+	unsigned int dhash = 0;

 	switch (family) {
 	case AF_INET:
@@ -91,7 +94,8 @@ static inline unsigned int __sel_hash(struct
xfrm_selector *sel, unsigned short
 		    sel->prefixlen_s != 32)
 			return hmask + 1;

-		h = __xfrm4_daddr_saddr_hash(daddr, saddr);
+		shash = __xfrm4_addr_hash(saddr);
+		dhash = __xfrm4_addr_hash(daddr);
 		break;

 	case AF_INET6:
@@ -99,28 +103,30 @@ static inline unsigned int __sel_hash(struct
xfrm_selector *sel, unsigned short
 		    sel->prefixlen_s != 128)
 			return hmask + 1;

-		h = __xfrm6_daddr_saddr_hash(daddr, saddr);
+		shash = __xfrm6_addr_hash(saddr);
+		dhash = __xfrm6_addr_hash(daddr);
 		break;
 	};
-	h ^= (h >> 16);
-	return h & hmask;
+
+	return jhash_2words(shash, dhash, family) & hmask;
 }

 static inline unsigned int __addr_hash(xfrm_address_t *daddr,
xfrm_address_t *saddr, unsigned short family, unsigned int hmask)
 {
-	unsigned int h = 0;
+	unsigned int shash = 0;
+	unsigned int dhash = 0;

 	switch (family) {
 	case AF_INET:
-		h = __xfrm4_daddr_saddr_hash(daddr, saddr);
+		shash = __xfrm4_addr_hash(saddr);
+		dhash = __xfrm4_addr_hash(daddr);
 		break;
-
 	case AF_INET6:
-		h = __xfrm6_daddr_saddr_hash(daddr, saddr);
-		break;
-	};
-	h ^= (h >> 16);
-	return h & hmask;
+		shash = __xfrm6_addr_hash(saddr);
+		dhash = __xfrm6_addr_hash(daddr);
+	}
+
+	return jhash_2words(shash, dhash, family) & hmask;
 }

 extern struct hlist_head *xfrm_hash_alloc(unsigned int sz);
--

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

[Jussi Maki]

[-- Attachment #1: Type: text/plain, Size: 560 bytes --]

Whoops, line wrapping broke the patch, here's it again.

On Wed, Aug 5, 2009 at 10:41 AM, Jussi Mäki<joamaki@gmail.com> wrote:
> 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.

[-- Attachment #2: xfrmhash.patch --]
[-- Type: application/octet-stream, Size: 4881 bytes --]

Signed-off-by: Jussi Maki <joamaki@gmail.com>
---
 net/xfrm/xfrm_hash.h |   90 ++++++++++++++++++++++++++-----------------------
 1 files changed, 48 insertions(+), 42 deletions(-)

diff --git a/net/xfrm/xfrm_hash.h b/net/xfrm/xfrm_hash.h
index d401dc8..59d4cb6 100644
--- a/net/xfrm/xfrm_hash.h
+++ b/net/xfrm/xfrm_hash.h
@@ -3,6 +3,7 @@
 
 #include <linux/xfrm.h>
 #include <linux/socket.h>
+#include <linux/jhash.h>
 
 static inline unsigned int __xfrm4_addr_hash(xfrm_address_t *addr)
 {
@@ -14,31 +15,27 @@ static inline unsigned int __xfrm6_addr_hash(xfrm_address_t *addr)
 	return ntohl(addr->a6[2] ^ addr->a6[3]);
 }
 
-static inline unsigned int __xfrm4_daddr_saddr_hash(xfrm_address_t *daddr, xfrm_address_t *saddr)
-{
-	return ntohl(daddr->a4 ^ saddr->a4);
-}
-
-static inline unsigned int __xfrm6_daddr_saddr_hash(xfrm_address_t *daddr, xfrm_address_t *saddr)
-{
-	return ntohl(daddr->a6[2] ^ daddr->a6[3] ^
-		     saddr->a6[2] ^ saddr->a6[3]);
-}
-
-static inline unsigned int __xfrm_dst_hash(xfrm_address_t *daddr, xfrm_address_t *saddr,
-					   u32 reqid, unsigned short family,
+static inline unsigned int __xfrm_dst_hash(xfrm_address_t *daddr,
+					   xfrm_address_t *saddr,
+					   u32 reqid,
+					   unsigned short family,
 					   unsigned int hmask)
 {
-	unsigned int h = family ^ reqid;
+	unsigned int shash = 0;
+	unsigned int dhash = 0;
+
 	switch (family) {
 	case AF_INET:
-		h ^= __xfrm4_daddr_saddr_hash(daddr, saddr);
+		shash = __xfrm4_addr_hash(saddr);
+		dhash = __xfrm4_addr_hash(daddr);
 		break;
 	case AF_INET6:
-		h ^= __xfrm6_daddr_saddr_hash(daddr, saddr);
-		break;
+		shash = __xfrm6_addr_hash(saddr);
+		dhash = __xfrm6_addr_hash(daddr);
 	}
-	return (h ^ (h >> 16)) & hmask;
+
+	return jhash_3words(shash, dhash,
+			    reqid, family) & hmask;
 }
 
 static inline unsigned __xfrm_src_hash(xfrm_address_t *daddr,
@@ -46,32 +43,37 @@ static inline unsigned __xfrm_src_hash(xfrm_address_t *daddr,
 				       unsigned short family,
 				       unsigned int hmask)
 {
-	unsigned int h = family;
+	unsigned int shash = 0;
+	unsigned int dhash = 0;
 	switch (family) {
 	case AF_INET:
-		h ^= __xfrm4_daddr_saddr_hash(daddr, saddr);
+		shash = __xfrm4_addr_hash(saddr);
+		dhash = __xfrm4_addr_hash(daddr);
 		break;
 	case AF_INET6:
-		h ^= __xfrm6_daddr_saddr_hash(daddr, saddr);
-		break;
-	};
-	return (h ^ (h >> 16)) & hmask;
+		shash = __xfrm6_addr_hash(saddr);
+		dhash = __xfrm6_addr_hash(daddr);
+	}
+	return jhash_2words(shash, dhash, family) & hmask;
 }
 
 static inline unsigned int
-__xfrm_spi_hash(xfrm_address_t *daddr, __be32 spi, u8 proto, unsigned short family,
+__xfrm_spi_hash(xfrm_address_t *daddr, __be32 spi, u8 proto,
+		unsigned short family,
 		unsigned int hmask)
 {
-	unsigned int h = (__force u32)spi ^ proto;
+	unsigned int h;
+
 	switch (family) {
 	case AF_INET:
-		h ^= __xfrm4_addr_hash(daddr);
+		h = __xfrm4_addr_hash(daddr);
 		break;
 	case AF_INET6:
-		h ^= __xfrm6_addr_hash(daddr);
+		h = __xfrm6_addr_hash(daddr);
 		break;
 	}
-	return (h ^ (h >> 10) ^ (h >> 20)) & hmask;
+
+	return jhash_3words(h, spi, proto, family) & hmask;
 }
 
 static inline unsigned int __idx_hash(u32 index, unsigned int hmask)
@@ -83,7 +85,8 @@ static inline unsigned int __sel_hash(struct xfrm_selector *sel, unsigned short
 {
 	xfrm_address_t *daddr = &sel->daddr;
 	xfrm_address_t *saddr = &sel->saddr;
-	unsigned int h = 0;
+	unsigned int shash = 0;
+	unsigned int dhash = 0;
 
 	switch (family) {
 	case AF_INET:
@@ -91,7 +94,8 @@ static inline unsigned int __sel_hash(struct xfrm_selector *sel, unsigned short
 		    sel->prefixlen_s != 32)
 			return hmask + 1;
 
-		h = __xfrm4_daddr_saddr_hash(daddr, saddr);
+		shash = __xfrm4_addr_hash(saddr);
+		dhash = __xfrm4_addr_hash(daddr);
 		break;
 
 	case AF_INET6:
@@ -99,28 +103,30 @@ static inline unsigned int __sel_hash(struct xfrm_selector *sel, unsigned short
 		    sel->prefixlen_s != 128)
 			return hmask + 1;
 
-		h = __xfrm6_daddr_saddr_hash(daddr, saddr);
+		shash = __xfrm6_addr_hash(saddr);
+		dhash = __xfrm6_addr_hash(daddr);
 		break;
 	};
-	h ^= (h >> 16);
-	return h & hmask;
+
+	return jhash_2words(shash, dhash, family) & hmask;
 }
 
 static inline unsigned int __addr_hash(xfrm_address_t *daddr, xfrm_address_t *saddr, unsigned short family, unsigned int hmask)
 {
-	unsigned int h = 0;
+	unsigned int shash = 0;
+	unsigned int dhash = 0;
 
 	switch (family) {
 	case AF_INET:
-		h = __xfrm4_daddr_saddr_hash(daddr, saddr);
+		shash = __xfrm4_addr_hash(saddr);
+		dhash = __xfrm4_addr_hash(daddr);
 		break;
-
 	case AF_INET6:
-		h = __xfrm6_daddr_saddr_hash(daddr, saddr);
-		break;
-	};
-	h ^= (h >> 16);
-	return h & hmask;
+		shash = __xfrm6_addr_hash(saddr);
+		dhash = __xfrm6_addr_hash(daddr);
+	}
+
+	return jhash_2words(shash, dhash, family) & hmask;
 }
 
 extern struct hlist_head *xfrm_hash_alloc(unsigned int sz);
-- 
1.5.6.5

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

[David Miller]

From: Jussi Mäki <joamaki@gmail.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@gmail.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.

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

[Jussi Maki]

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@davemloft.net> wrote:
> From: Jussi Mäki <joamaki@gmail.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@gmail.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.
>

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

[Jussi Maki]

Hi,

Did some testing and one possible fix to this problem
would be to change the xor to addition. Would this be OK?

---
 net/xfrm/xfrm_hash.h |    2 +-
 1 files changed, 1 insertions(+), 1 deletions(-)

diff --git a/net/xfrm/xfrm_hash.h b/net/xfrm/xfrm_hash.h
index d401dc8..e5195c9 100644
--- a/net/xfrm/xfrm_hash.h
+++ b/net/xfrm/xfrm_hash.h
@@ -16,7 +16,7 @@ static inline unsigned int __xfrm6_addr_hash(xfrm_address_t *addr)
 
 static inline unsigned int __xfrm4_daddr_saddr_hash(xfrm_address_t *daddr, xfrm_address_t *saddr)
 {
-	return ntohl(daddr->a4 ^ saddr->a4);
+	return ntohl(daddr->a4 + saddr->a4);
 }
 
 static inline unsigned int __xfrm6_daddr_saddr_hash(xfrm_address_t *daddr, xfrm_address_t *saddr)
-- 
1.5.6.5

On Thu, 6 Aug 2009, Jussi Maki wrote:

> 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?

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

[David Miller]

From: Jussi Maki <joamaki@gmail.com>
Date: Thu, 6 Aug 2009 09:32:37 +0300

> 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?

Do some different mixing in __xfrm4_daddr_saddr_hash(), it's still
going to be cheaper than jhash.

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

[David Miller]

From: Jussi Maki <jmaki@sisapiiri.net.net>
Date: Thu, 6 Aug 2009 11:58:55 +0300 (EEST)

> Did some testing and one possible fix to this problem
> would be to change the xor to addition. Would this be OK?

Yes.

Please make a formal submission.

[PATCH] Fix xfrm hash collisions by changing __xfrm4_daddr_saddr_hash to hash addresses with addition

[Jussi Maki]

This patch fixes hash collisions in cases where number
of entries have incrementing IP source and destination addresses
from single respective subnets (i.e. 192.168.0.1-172.16.0.1, 
192.168.0.2-172.16.0.2, and so on.).

Signed-off-by: Jussi Maki <joamaki@gmail.com>
---
 net/xfrm/xfrm_hash.h |    2 +-
 1 files changed, 1 insertions(+), 1 deletions(-)

diff --git a/net/xfrm/xfrm_hash.h b/net/xfrm/xfrm_hash.h
index d401dc8..e5195c9 100644
--- a/net/xfrm/xfrm_hash.h
+++ b/net/xfrm/xfrm_hash.h
@@ -16,7 +16,7 @@ static inline unsigned int __xfrm6_addr_hash(xfrm_address_t *addr)
 
 static inline unsigned int __xfrm4_daddr_saddr_hash(xfrm_address_t *daddr, xfrm_address_t *saddr)
 {
-	return ntohl(daddr->a4 ^ saddr->a4);
+	return ntohl(daddr->a4 + saddr->a4);
 }
 
 static inline unsigned int __xfrm6_daddr_saddr_hash(xfrm_address_t *daddr, xfrm_address_t *saddr)
-- 
1.5.6.5

Re: [PATCH] Fix xfrm hash collisions by changing __xfrm4_daddr_saddr_hash to hash addresses with addition

[David Miller]

From: Jussi Maki <joamaki@gmail.com>
Date: Fri, 7 Aug 2009 10:38:14 +0300 (EEST)

> 
> This patch fixes hash collisions in cases where number
> of entries have incrementing IP source and destination addresses
> from single respective subnets (i.e. 192.168.0.1-172.16.0.1, 
> 192.168.0.2-172.16.0.2, and so on.).
> 
> Signed-off-by: Jussi Maki <joamaki@gmail.com>

Applied.

Re: [PATCH] Fix xfrm hash collisions by changing __xfrm4_daddr_saddr_hash to hash addresses with addition

[Herbert Xu]

Jussi Maki <joamaki@gmail.com> wrote:
>
> diff --git a/net/xfrm/xfrm_hash.h b/net/xfrm/xfrm_hash.h
> index d401dc8..e5195c9 100644
> --- a/net/xfrm/xfrm_hash.h
> +++ b/net/xfrm/xfrm_hash.h
> @@ -16,7 +16,7 @@ static inline unsigned int __xfrm6_addr_hash(xfrm_address_t *addr)
> 
> static inline unsigned int __xfrm4_daddr_saddr_hash(xfrm_address_t *daddr, xfrm_address_t *saddr)
> {
> -       return ntohl(daddr->a4 ^ saddr->a4);
> +       return ntohl(daddr->a4 + saddr->a4);
> }

What if the other side intentionally picks a destination addresses
to create collisions? Actually it's even easier than that.  We
don't include the SPI in the hash so regardless of how we hash
it, our peer can simply continue to create SAs with the same
descriptors and they'll all hash to the same bucket.

Cheers,
-- 
Visit Openswan at http://www.openswan.org/
Email: Herbert Xu ~{PmV>HI~} <herbert@gondor.apana.org.au>
Home Page: http://gondor.apana.org.au/~herbert/
PGP Key: http://gondor.apana.org.au/~herbert/pubkey.txt

Re: [PATCH] Fix xfrm hash collisions by changing __xfrm4_daddr_saddr_hash to hash addresses with addition

[David Miller]

From: Herbert Xu <herbert@gondor.apana.org.au>
Date: Thu, 13 Aug 2009 12:06:06 +1000

> Jussi Maki <joamaki@gmail.com> wrote:
>>
>> diff --git a/net/xfrm/xfrm_hash.h b/net/xfrm/xfrm_hash.h
>> index d401dc8..e5195c9 100644
>> --- a/net/xfrm/xfrm_hash.h
>> +++ b/net/xfrm/xfrm_hash.h
>> @@ -16,7 +16,7 @@ static inline unsigned int __xfrm6_addr_hash(xfrm_address_t *addr)
>> 
>> static inline unsigned int __xfrm4_daddr_saddr_hash(xfrm_address_t *daddr, xfrm_address_t *saddr)
>> {
>> -       return ntohl(daddr->a4 ^ saddr->a4);
>> +       return ntohl(daddr->a4 + saddr->a4);
>> }
> 
> What if the other side intentionally picks a destination addresses
> to create collisions? Actually it's even easier than that.  We
> don't include the SPI in the hash so regardless of how we hash
> it, our peer can simply continue to create SAs with the same
> descriptors and they'll all hash to the same bucket.

Isn't it fruitless to talk about exploiting SA IDs when such things
are setup using an encrypted negotiation sequence and some level of
trust?

Just wondering :-)

Re: [PATCH] Fix xfrm hash collisions by changing __xfrm4_daddr_saddr_hash to hash addresses with addition

[Herbert Xu]

On Wed, Aug 12, 2009 at 08:42:47PM -0700, David Miller wrote:
>
> Isn't it fruitless to talk about exploiting SA IDs when such things
> are setup using an encrypted negotiation sequence and some level of
> trust?
> 
> Just wondering :-)

It's a good question :)

However, IPsec is not always carried out between two parties
that trust each other.  In fact, quite often IPsec is used in
a hub and spoke fashion where a central IPsec gateway serves a
number of IPsec clients that may or may not be trustworthy.

Take corporate VPN servers for instance.  Yes each client is
trusted to the extent that it is being offered connectivity to
the corporate network.  However, it would not be ideal if one
rogue client can take down the entire VPN server, especially
in this case because repeatedly creating identical SAs can often
occur purely by accident.

With IKEv1, it is quite possible for the client to think that
SA negotiation failed while in fact it had been created at the
server's end.  In that case the client depending on configuration
may retry indefinitely, causing a large number of identical SAs
to be created at the server end.  

Cheers,
-- 
Visit Openswan at http://www.openswan.org/
Email: Herbert Xu ~{PmV>HI~} <herbert@gondor.apana.org.au>
Home Page: http://gondor.apana.org.au/~herbert/
PGP Key: http://gondor.apana.org.au/~herbert/pubkey.txt

Re: [PATCH] Fix xfrm hash collisions by changing __xfrm4_daddr_saddr_hash to hash addresses with addition

[David Miller]

From: Herbert Xu <herbert@gondor.apana.org.au>
Date: Thu, 13 Aug 2009 13:53:10 +1000

> Take corporate VPN servers for instance.  Yes each client is
> trusted to the extent that it is being offered connectivity to
> the corporate network.  However, it would not be ideal if one
> rogue client can take down the entire VPN server, especially
> in this case because repeatedly creating identical SAs can often
> occur purely by accident.

1) The client is on your private network, much more serious
   mischief is possible.

2) Whoever creates such a hash collision explosion can be
   precisely identified.

The ikev1 failure case is an interesting situation I hadn't
considered.

Maybe that can matter, but again the guilty party is easy to identify
and easy to block via whatever means appropriate.

Re: [PATCH] Fix xfrm hash collisions by changing __xfrm4_daddr_saddr_hash to hash addresses with addition

[Herbert Xu]

On Wed, Aug 12, 2009 at 08:56:35PM -0700, David Miller wrote:
> 
> 1) The client is on your private network, much more serious
>    mischief is possible.

Not necessarily as having an IPsec connection does not entail
full access to the network on the other side.

> 2) Whoever creates such a hash collision explosion can be
>    precisely identified.
> 
> The ikev1 failure case is an interesting situation I hadn't
> considered.
> 
> Maybe that can matter, but again the guilty party is easy to identify
> and easy to block via whatever means appropriate.

For corporate networks perhaps.  However, in other cases the
peer may be trusted even less.  For instance, if IPsec were
used for mobility purposes then you essentially don't know
the client at all.

It's like Facebook.  If one user mounts a DoS attack you can
block their account.  However, if they can simply come back
with a new account then you need to make sure that the attack
can be mitigated in other ways so that it doesn't bring the
whole thing down.

BTW, this isn't just exposed to IPsec peers.  It can also be
exposed to those behind the gateway not using IPsec.

Some IPsec applications use a policy that spawns one SA per
src/dst address pair.  In that case, even an entity that is
not on the IPsec side would be able to spawn SAs with the intent
of causing collisions.  It simply needs to send packets through
the IPsec gateway with the appropriate destination addresses.

Cheers,
-- 
Visit Openswan at http://www.openswan.org/
Email: Herbert Xu ~{PmV>HI~} <herbert@gondor.apana.org.au>
Home Page: http://gondor.apana.org.au/~herbert/
PGP Key: http://gondor.apana.org.au/~herbert/pubkey.txt

Re: [PATCH] Fix xfrm hash collisions by changing __xfrm4_daddr_saddr_hash to hash addresses with addition

[David Miller]

From: Herbert Xu <herbert@gondor.apana.org.au>
Date: Thu, 13 Aug 2009 14:11:15 +1000

> Some IPsec applications use a policy that spawns one SA per
> src/dst address pair.  In that case, even an entity that is
> not on the IPsec side would be able to spawn SAs with the intent
> of causing collisions.  It simply needs to send packets through
> the IPsec gateway with the appropriate destination addresses.

Ok, all good points.  We need to do something about this.

So probably we need to eat jhash after all.

Resistence is futile, sigh :-)

Re: [PATCH] Fix xfrm hash collisions by changing __xfrm4_daddr_saddr_hash to hash addresses with addition

[Herbert Xu]

On Wed, Aug 12, 2009 at 08:56:35PM -0700, David Miller wrote:
> 
> 2) Whoever creates such a hash collision explosion can be
>    precisely identified.

BTW the trust issue goes the other way too.  I wouldn't want
to connect to any IPsec peer if I knew that they could render
my gateway unuseable whenever they liked :)

Cheers,
-- 
Visit Openswan at http://www.openswan.org/
Email: Herbert Xu ~{PmV>HI~} <herbert@gondor.apana.org.au>
Home Page: http://gondor.apana.org.au/~herbert/
PGP Key: http://gondor.apana.org.au/~herbert/pubkey.txt