Patchwork Fix xfrm hash collisions by changing __xfrm4_daddr_saddr_hash to hash addresses with addition

login
register
mail settings
Submitter Jussi Mäki
Date Aug. 7, 2009, 7:38 a.m.
Message ID <alpine.DEB.1.10.0908071032171.3426@sisapiiri.net.net>
Download mbox | patch
Permalink /patch/30916/
State Accepted
Delegated to: David Miller
Headers show

Comments

Jussi Mäki - Aug. 7, 2009, 7:38 a.m.
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(-)
David Miller - Aug. 10, 2009, 4:52 a.m.
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.
--
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
Herbert Xu - Aug. 13, 2009, 2:06 a.m.
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,
David Miller - Aug. 13, 2009, 3:42 a.m.
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 :-)
--
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
Herbert Xu - Aug. 13, 2009, 3:53 a.m.
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,
David Miller - Aug. 13, 2009, 3:56 a.m.
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.
--
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
Herbert Xu - Aug. 13, 2009, 4:11 a.m.
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,
David Miller - Aug. 13, 2009, 4:18 a.m.
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 :-)
--
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
Herbert Xu - Aug. 13, 2009, 4:19 a.m.
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,

Patch

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)