[PATCH net 0/2] inet: make exception handling less predictible

[PATCH net 0/2] inet: make exception handling less predictible

[Eric Dumazet]

From: Eric Dumazet <edumazet@google.com>

This second round of patches is addressing Keyu Man recommendations
to make linux hosts more robust against a class of brute force attacks.

Eric Dumazet (2):
  ipv6: make exception cache less predictible
  ipv4: make exception cache less predictible

 net/ipv4/route.c | 44 +++++++++++++++++++++++++++++---------------
 net/ipv6/route.c |  5 ++++-
 2 files changed, 33 insertions(+), 16 deletions(-)

-- 
2.33.0.259.gc128427fd7-goog

[PATCH net 1/2] ipv6: make exception cache less predictible

[Eric Dumazet]

From: Eric Dumazet <edumazet@google.com>

Even after commit 4785305c05b2 ("ipv6: use siphash in rt6_exception_hash()"),
an attacker can still use brute force to learn some secrets from a victim
linux host.

One way to defeat these attacks is to make the max depth of the hash
table bucket a random value.

Before this patch, each bucket of the hash table used to store exceptions
could contain 6 items under attack.

After the patch, each bucket would contains a random number of items,
between 6 and 10. The attacker can no longer infer secrets.

This is slightly increasing memory size used by the hash table,
we do not expect this to be a problem.

Following patch is dealing with the same issue in IPv4.

Fixes: 35732d01fe31 ("ipv6: introduce a hash table to store dst cache")
Signed-off-by: Eric Dumazet <edumazet@google.com>
Reported-by: Keyu Man <kman001@ucr.edu>
Cc: Wei Wang <weiwan@google.com>
Cc: Martin KaFai Lau <kafai@fb.com>
---
 net/ipv6/route.c | 5 ++++-
 1 file changed, 4 insertions(+), 1 deletion(-)

diff --git a/net/ipv6/route.c b/net/ipv6/route.c
index c5e8ecb96426bda619fe242351e40dcf6ff68bcf..60334030210192660a7fa141163f36af7489d0ae 100644
--- a/net/ipv6/route.c
+++ b/net/ipv6/route.c
@@ -1657,6 +1657,7 @@ static int rt6_insert_exception(struct rt6_info *nrt,
 	struct in6_addr *src_key = NULL;
 	struct rt6_exception *rt6_ex;
 	struct fib6_nh *nh = res->nh;
+	int max_depth;
 	int err = 0;
 
 	spin_lock_bh(&rt6_exception_lock);
@@ -1711,7 +1712,9 @@ static int rt6_insert_exception(struct rt6_info *nrt,
 	bucket->depth++;
 	net->ipv6.rt6_stats->fib_rt_cache++;
 
-	if (bucket->depth > FIB6_MAX_DEPTH)
+	/* Randomize max depth to avoid some side channels attacks. */
+	max_depth = FIB6_MAX_DEPTH + prandom_u32_max(FIB6_MAX_DEPTH);
+	while (bucket->depth > max_depth)
 		rt6_exception_remove_oldest(bucket);
 
 out:
-- 
2.33.0.259.gc128427fd7-goog

[PATCH net 2/2] ipv4: make exception cache less predictible

[Eric Dumazet]

From: Eric Dumazet <edumazet@google.com>

Even after commit 6457378fe796 ("ipv4: use siphash instead of Jenkins in
fnhe_hashfun()"), an attacker can still use brute force to learn
some secrets from a victim linux host.

One way to defeat these attacks is to make the max depth of the hash
table bucket a random value.

Before this patch, each bucket of the hash table used to store exceptions
could contain 6 items under attack.

After the patch, each bucket would contains a random number of items,
between 6 and 10. The attacker can no longer infer secrets.

This is slightly increasing memory size used by the hash table,
by 50% in average, we do not expect this to be a problem.

This patch is more complex than the prior one (IPv6 equivalent),
because IPv4 was reusing the oldest entry.
Since we need to be able to evict more than one entry per
update_or_create_fnhe() call, I had to replace
fnhe_oldest() with fnhe_remove_oldest().

Also note that we will queue extra kfree_rcu() calls under stress,
which hopefully wont be a too big issue.

Fixes: 4895c771c7f0 ("ipv4: Add FIB nexthop exceptions.")
Signed-off-by: Eric Dumazet <edumazet@google.com>
Reported-by: Keyu Man <kman001@ucr.edu>
Cc: Willy Tarreau <w@1wt.eu>
Signed-off-by: David S. Miller <davem@davemloft.net>
---
 net/ipv4/route.c | 44 +++++++++++++++++++++++++++++---------------
 1 file changed, 29 insertions(+), 15 deletions(-)

diff --git a/net/ipv4/route.c b/net/ipv4/route.c
index a6f20ee3533554b210d27c4ab6637ca7a05b148b..225714b5efc0b9c6bcd2d58a62d4656cdc5a1cde 100644
--- a/net/ipv4/route.c
+++ b/net/ipv4/route.c
@@ -586,18 +586,25 @@ static void fnhe_flush_routes(struct fib_nh_exception *fnhe)
 	}
 }
 
-static struct fib_nh_exception *fnhe_oldest(struct fnhe_hash_bucket *hash)
+static void fnhe_remove_oldest(struct fnhe_hash_bucket *hash)
 {
-	struct fib_nh_exception *fnhe, *oldest;
+	struct fib_nh_exception __rcu **fnhe_p, **oldest_p;
+	struct fib_nh_exception *fnhe, *oldest = NULL;
 
-	oldest = rcu_dereference(hash->chain);
-	for (fnhe = rcu_dereference(oldest->fnhe_next); fnhe;
-	     fnhe = rcu_dereference(fnhe->fnhe_next)) {
-		if (time_before(fnhe->fnhe_stamp, oldest->fnhe_stamp))
+	for (fnhe_p = &hash->chain; ; fnhe_p = &fnhe->fnhe_next) {
+		fnhe = rcu_dereference_protected(*fnhe_p,
+						 lockdep_is_held(&fnhe_lock));
+		if (!fnhe)
+			break;
+		if (!oldest ||
+		    time_before(fnhe->fnhe_stamp, oldest->fnhe_stamp)) {
 			oldest = fnhe;
+			oldest_p = fnhe_p;
+		}
 	}
 	fnhe_flush_routes(oldest);
-	return oldest;
+	*oldest_p = oldest->fnhe_next;
+	kfree_rcu(oldest, rcu);
 }
 
 static u32 fnhe_hashfun(__be32 daddr)
@@ -676,16 +683,21 @@ static void update_or_create_fnhe(struct fib_nh_common *nhc, __be32 daddr,
 		if (rt)
 			fill_route_from_fnhe(rt, fnhe);
 	} else {
-		if (depth > FNHE_RECLAIM_DEPTH)
-			fnhe = fnhe_oldest(hash);
-		else {
-			fnhe = kzalloc(sizeof(*fnhe), GFP_ATOMIC);
-			if (!fnhe)
-				goto out_unlock;
+		/* Randomize max depth to avoid some side channels attacks. */
+		int max_depth = FNHE_RECLAIM_DEPTH +
+				prandom_u32_max(FNHE_RECLAIM_DEPTH);
 
-			fnhe->fnhe_next = hash->chain;
-			rcu_assign_pointer(hash->chain, fnhe);
+		while (depth > max_depth) {
+			fnhe_remove_oldest(hash);
+			depth--;
 		}
+
+		fnhe = kzalloc(sizeof(*fnhe), GFP_ATOMIC);
+		if (!fnhe)
+			goto out_unlock;
+
+		fnhe->fnhe_next = hash->chain;
+
 		fnhe->fnhe_genid = genid;
 		fnhe->fnhe_daddr = daddr;
 		fnhe->fnhe_gw = gw;
@@ -693,6 +705,8 @@ static void update_or_create_fnhe(struct fib_nh_common *nhc, __be32 daddr,
 		fnhe->fnhe_mtu_locked = lock;
 		fnhe->fnhe_expires = max(1UL, expires);
 
+		rcu_assign_pointer(hash->chain, fnhe);
+
 		/* Exception created; mark the cached routes for the nexthop
 		 * stale, so anyone caching it rechecks if this exception
 		 * applies to them.
-- 
2.33.0.259.gc128427fd7-goog

Re: [PATCH net 1/2] ipv6: make exception cache less predictible

[David Ahern]

On 8/29/21 3:16 PM, Eric Dumazet wrote:
> From: Eric Dumazet <edumazet@google.com>
> 
> Even after commit 4785305c05b2 ("ipv6: use siphash in rt6_exception_hash()"),
> an attacker can still use brute force to learn some secrets from a victim
> linux host.
> 
> One way to defeat these attacks is to make the max depth of the hash
> table bucket a random value.
> 
> Before this patch, each bucket of the hash table used to store exceptions
> could contain 6 items under attack.
> 
> After the patch, each bucket would contains a random number of items,
> between 6 and 10. The attacker can no longer infer secrets.
> 
> This is slightly increasing memory size used by the hash table,
> we do not expect this to be a problem.
> 
> Following patch is dealing with the same issue in IPv4.
> 
> Fixes: 35732d01fe31 ("ipv6: introduce a hash table to store dst cache")
> Signed-off-by: Eric Dumazet <edumazet@google.com>
> Reported-by: Keyu Man <kman001@ucr.edu>
> Cc: Wei Wang <weiwan@google.com>
> Cc: Martin KaFai Lau <kafai@fb.com>
> ---
>  net/ipv6/route.c | 5 ++++-
>  1 file changed, 4 insertions(+), 1 deletion(-)
> 

Reviewed-by: David Ahern <dsahern@kernel.org>

Re: [PATCH net 2/2] ipv4: make exception cache less predictible

[David Ahern]

On 8/29/21 3:16 PM, Eric Dumazet wrote:
> From: Eric Dumazet <edumazet@google.com>
> 
> Even after commit 6457378fe796 ("ipv4: use siphash instead of Jenkins in
> fnhe_hashfun()"), an attacker can still use brute force to learn
> some secrets from a victim linux host.
> 
> One way to defeat these attacks is to make the max depth of the hash
> table bucket a random value.
> 
> Before this patch, each bucket of the hash table used to store exceptions
> could contain 6 items under attack.
> 
> After the patch, each bucket would contains a random number of items,
> between 6 and 10. The attacker can no longer infer secrets.
> 
> This is slightly increasing memory size used by the hash table,
> by 50% in average, we do not expect this to be a problem.
> 
> This patch is more complex than the prior one (IPv6 equivalent),
> because IPv4 was reusing the oldest entry.
> Since we need to be able to evict more than one entry per
> update_or_create_fnhe() call, I had to replace
> fnhe_oldest() with fnhe_remove_oldest().
> 
> Also note that we will queue extra kfree_rcu() calls under stress,
> which hopefully wont be a too big issue.
> 
> Fixes: 4895c771c7f0 ("ipv4: Add FIB nexthop exceptions.")
> Signed-off-by: Eric Dumazet <edumazet@google.com>
> Reported-by: Keyu Man <kman001@ucr.edu>
> Cc: Willy Tarreau <w@1wt.eu>
> Signed-off-by: David S. Miller <davem@davemloft.net>
> ---
>  net/ipv4/route.c | 44 +++++++++++++++++++++++++++++---------------
>  1 file changed, 29 insertions(+), 15 deletions(-)
> 

Reviewed-by: David Ahern <dsahern@kernel.org>
Tested-by: David Ahern <dsahern@kernel.org>

Re: [PATCH net 2/2] ipv4: make exception cache less predictible

[kernel test robot]

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

CC: kbuild-all(a)lists.01.org
In-Reply-To: <20210829221615.2057201-3-eric.dumazet@gmail.com>
References: <20210829221615.2057201-3-eric.dumazet@gmail.com>
TO: Eric Dumazet <eric.dumazet@gmail.com>
TO: "David S . Miller" <davem@davemloft.net>
TO: Jakub Kicinski <kuba@kernel.org>
CC: netdev <netdev@vger.kernel.org>
CC: Eric Dumazet <edumazet@google.com>
CC: Willy Tarreau <w@1wt.eu>
CC: Keyu Man <kman001@ucr.edu>
CC: David Ahern <dsahern@kernel.org>

Hi Eric,

I love your patch! Perhaps something to improve:

[auto build test WARNING on net/master]

url:    https://github.com/0day-ci/linux/commits/Eric-Dumazet/inet-make-exception-handling-less-predictible/20210830-061726
base:   https://git.kernel.org/pub/scm/linux/kernel/git/davem/net.git 57f780f1c43362b86fd23d20bd940e2468237716
:::::: branch date: 4 hours ago
:::::: commit date: 4 hours ago
config: x86_64-randconfig-m001-20210829 (attached as .config)
compiler: gcc-9 (Debian 9.3.0-22) 9.3.0

If you fix the issue, kindly add following tag as appropriate
Reported-by: kernel test robot <lkp@intel.com>
Reported-by: Dan Carpenter <dan.carpenter@oracle.com>

smatch warnings:
net/ipv4/route.c:606 fnhe_remove_oldest() error: potentially dereferencing uninitialized 'oldest_p'.

vim +/oldest_p +606 net/ipv4/route.c

2ffae99d1fac272 Timo Teräs      2013-06-27  588  
adf305d00ec06cb Eric Dumazet    2021-08-29  589  static void fnhe_remove_oldest(struct fnhe_hash_bucket *hash)
4895c771c7f006b David S. Miller 2012-07-17  590  {
adf305d00ec06cb Eric Dumazet    2021-08-29  591  	struct fib_nh_exception __rcu **fnhe_p, **oldest_p;
adf305d00ec06cb Eric Dumazet    2021-08-29  592  	struct fib_nh_exception *fnhe, *oldest = NULL;
4895c771c7f006b David S. Miller 2012-07-17  593  
adf305d00ec06cb Eric Dumazet    2021-08-29  594  	for (fnhe_p = &hash->chain; ; fnhe_p = &fnhe->fnhe_next) {
adf305d00ec06cb Eric Dumazet    2021-08-29  595  		fnhe = rcu_dereference_protected(*fnhe_p,
adf305d00ec06cb Eric Dumazet    2021-08-29  596  						 lockdep_is_held(&fnhe_lock));
adf305d00ec06cb Eric Dumazet    2021-08-29  597  		if (!fnhe)
adf305d00ec06cb Eric Dumazet    2021-08-29  598  			break;
adf305d00ec06cb Eric Dumazet    2021-08-29  599  		if (!oldest ||
adf305d00ec06cb Eric Dumazet    2021-08-29  600  		    time_before(fnhe->fnhe_stamp, oldest->fnhe_stamp)) {
4895c771c7f006b David S. Miller 2012-07-17  601  			oldest = fnhe;
adf305d00ec06cb Eric Dumazet    2021-08-29  602  			oldest_p = fnhe_p;
adf305d00ec06cb Eric Dumazet    2021-08-29  603  		}
4895c771c7f006b David S. Miller 2012-07-17  604  	}
2ffae99d1fac272 Timo Teräs      2013-06-27  605  	fnhe_flush_routes(oldest);
adf305d00ec06cb Eric Dumazet    2021-08-29 @606  	*oldest_p = oldest->fnhe_next;
adf305d00ec06cb Eric Dumazet    2021-08-29  607  	kfree_rcu(oldest, rcu);
4895c771c7f006b David S. Miller 2012-07-17  608  }
4895c771c7f006b David S. Miller 2012-07-17  609  

---
0-DAY CI Kernel Test Service, Intel Corporation
https://lists.01.org/hyperkitty/list/kbuild-all(a)lists.01.org

[-- Attachment #2: config.gz --]
[-- Type: application/gzip, Size: 39595 bytes --]

Re: [PATCH net 2/2] ipv4: make exception cache less predictible

[Dan Carpenter]

[ I trimmed the CC list because this is probably a false positive and
  netdev hates static checker warnings.  - dan ]

Hi Eric,

url:    https://github.com/0day-ci/linux/commits/Eric-Dumazet/inet-make-exception-handling-less-predictible/20210830-061726
base:   https://git.kernel.org/pub/scm/linux/kernel/git/davem/net.git 57f780f1c43362b86fd23d20bd940e2468237716
config: x86_64-randconfig-m001-20210829 (attached as .config)
compiler: gcc-9 (Debian 9.3.0-22) 9.3.0

If you fix the issue, kindly add following tag as appropriate
Reported-by: kernel test robot <lkp@intel.com>
Reported-by: Dan Carpenter <dan.carpenter@oracle.com>

smatch warnings:
net/ipv4/route.c:606 fnhe_remove_oldest() error: potentially dereferencing uninitialized 'oldest_p'.

vim +/oldest_p +606 net/ipv4/route.c

adf305d00ec06cb Eric Dumazet    2021-08-29  589  static void fnhe_remove_oldest(struct fnhe_hash_bucket *hash)
4895c771c7f006b David S. Miller 2012-07-17  590  {
adf305d00ec06cb Eric Dumazet    2021-08-29  591  	struct fib_nh_exception __rcu **fnhe_p, **oldest_p;
adf305d00ec06cb Eric Dumazet    2021-08-29  592  	struct fib_nh_exception *fnhe, *oldest = NULL;
4895c771c7f006b David S. Miller 2012-07-17  593  
adf305d00ec06cb Eric Dumazet    2021-08-29  594  	for (fnhe_p = &hash->chain; ; fnhe_p = &fnhe->fnhe_next) {
adf305d00ec06cb Eric Dumazet    2021-08-29  595  		fnhe = rcu_dereference_protected(*fnhe_p,
adf305d00ec06cb Eric Dumazet    2021-08-29  596  						 lockdep_is_held(&fnhe_lock));
adf305d00ec06cb Eric Dumazet    2021-08-29  597  		if (!fnhe)
adf305d00ec06cb Eric Dumazet    2021-08-29  598  			break;

Smatch is complaining that this could break on the first iteration
through the loop...

adf305d00ec06cb Eric Dumazet    2021-08-29  599  		if (!oldest ||
adf305d00ec06cb Eric Dumazet    2021-08-29  600  		    time_before(fnhe->fnhe_stamp, oldest->fnhe_stamp)) {
4895c771c7f006b David S. Miller 2012-07-17  601  			oldest = fnhe;
adf305d00ec06cb Eric Dumazet    2021-08-29  602  			oldest_p = fnhe_p;
adf305d00ec06cb Eric Dumazet    2021-08-29  603  		}
4895c771c7f006b David S. Miller 2012-07-17  604  	}
2ffae99d1fac272 Timo Teräs      2013-06-27  605  	fnhe_flush_routes(oldest);
adf305d00ec06cb Eric Dumazet    2021-08-29 @606  	*oldest_p = oldest->fnhe_next;
adf305d00ec06cb Eric Dumazet    2021-08-29  607  	kfree_rcu(oldest, rcu);
4895c771c7f006b David S. Miller 2012-07-17  608  }

---
0-DAY CI Kernel Test Service, Intel Corporation
https://lists.01.org/hyperkitty/list/kbuild-all@lists.01.org

Re: [PATCH net 2/2] ipv4: make exception cache less predictible

[Dan Carpenter]

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

[ I trimmed the CC list because this is probably a false positive and
  netdev hates static checker warnings.  - dan ]

Hi Eric,

url:    https://github.com/0day-ci/linux/commits/Eric-Dumazet/inet-make-exception-handling-less-predictible/20210830-061726
base:   https://git.kernel.org/pub/scm/linux/kernel/git/davem/net.git 57f780f1c43362b86fd23d20bd940e2468237716
config: x86_64-randconfig-m001-20210829 (attached as .config)
compiler: gcc-9 (Debian 9.3.0-22) 9.3.0

If you fix the issue, kindly add following tag as appropriate
Reported-by: kernel test robot <lkp@intel.com>
Reported-by: Dan Carpenter <dan.carpenter@oracle.com>

smatch warnings:
net/ipv4/route.c:606 fnhe_remove_oldest() error: potentially dereferencing uninitialized 'oldest_p'.

vim +/oldest_p +606 net/ipv4/route.c

adf305d00ec06cb Eric Dumazet    2021-08-29  589  static void fnhe_remove_oldest(struct fnhe_hash_bucket *hash)
4895c771c7f006b David S. Miller 2012-07-17  590  {
adf305d00ec06cb Eric Dumazet    2021-08-29  591  	struct fib_nh_exception __rcu **fnhe_p, **oldest_p;
adf305d00ec06cb Eric Dumazet    2021-08-29  592  	struct fib_nh_exception *fnhe, *oldest = NULL;
4895c771c7f006b David S. Miller 2012-07-17  593  
adf305d00ec06cb Eric Dumazet    2021-08-29  594  	for (fnhe_p = &hash->chain; ; fnhe_p = &fnhe->fnhe_next) {
adf305d00ec06cb Eric Dumazet    2021-08-29  595  		fnhe = rcu_dereference_protected(*fnhe_p,
adf305d00ec06cb Eric Dumazet    2021-08-29  596  						 lockdep_is_held(&fnhe_lock));
adf305d00ec06cb Eric Dumazet    2021-08-29  597  		if (!fnhe)
adf305d00ec06cb Eric Dumazet    2021-08-29  598  			break;

Smatch is complaining that this could break on the first iteration
through the loop...

adf305d00ec06cb Eric Dumazet    2021-08-29  599  		if (!oldest ||
adf305d00ec06cb Eric Dumazet    2021-08-29  600  		    time_before(fnhe->fnhe_stamp, oldest->fnhe_stamp)) {
4895c771c7f006b David S. Miller 2012-07-17  601  			oldest = fnhe;
adf305d00ec06cb Eric Dumazet    2021-08-29  602  			oldest_p = fnhe_p;
adf305d00ec06cb Eric Dumazet    2021-08-29  603  		}
4895c771c7f006b David S. Miller 2012-07-17  604  	}
2ffae99d1fac272 Timo Teräs      2013-06-27  605  	fnhe_flush_routes(oldest);
adf305d00ec06cb Eric Dumazet    2021-08-29 @606  	*oldest_p = oldest->fnhe_next;
adf305d00ec06cb Eric Dumazet    2021-08-29  607  	kfree_rcu(oldest, rcu);
4895c771c7f006b David S. Miller 2012-07-17  608  }

---
0-DAY CI Kernel Test Service, Intel Corporation
https://lists.01.org/hyperkitty/list/kbuild-all(a)lists.01.org

Re: [PATCH net 1/2] ipv6: make exception cache less predictible

[Wei Wang]

On Sun, Aug 29, 2021 at 5:39 PM David Ahern <dsahern@gmail.com> wrote:
>
> On 8/29/21 3:16 PM, Eric Dumazet wrote:
> > From: Eric Dumazet <edumazet@google.com>
> >
> > Even after commit 4785305c05b2 ("ipv6: use siphash in rt6_exception_hash()"),
> > an attacker can still use brute force to learn some secrets from a victim
> > linux host.
> >
> > One way to defeat these attacks is to make the max depth of the hash
> > table bucket a random value.
> >
> > Before this patch, each bucket of the hash table used to store exceptions
> > could contain 6 items under attack.
> >
> > After the patch, each bucket would contains a random number of items,
> > between 6 and 10. The attacker can no longer infer secrets.
> >
> > This is slightly increasing memory size used by the hash table,
> > we do not expect this to be a problem.
> >
> > Following patch is dealing with the same issue in IPv4.
> >
> > Fixes: 35732d01fe31 ("ipv6: introduce a hash table to store dst cache")
> > Signed-off-by: Eric Dumazet <edumazet@google.com>
> > Reported-by: Keyu Man <kman001@ucr.edu>
> > Cc: Wei Wang <weiwan@google.com>
> > Cc: Martin KaFai Lau <kafai@fb.com>
> > ---
> >  net/ipv6/route.c | 5 ++++-
> >  1 file changed, 4 insertions(+), 1 deletion(-)
> >
>
> Reviewed-by: David Ahern <dsahern@kernel.org>
>
Reviewed-by: Wei Wang <weiwan@google.com>

Thanks Eric!

Re: [PATCH net 0/2] inet: make exception handling less predictible

[Keyu Man]

Thanks Eric and others for fixing the bug!

Keyu Man

On 8/29/2021 3:16 PM, Eric Dumazet wrote:
> From: Eric Dumazet <edumazet@google.com>
> 
> This second round of patches is addressing Keyu Man recommendations
> to make linux hosts more robust against a class of brute force attacks.
> 
> Eric Dumazet (2):
>    ipv6: make exception cache less predictible
>    ipv4: make exception cache less predictible
> 
>   net/ipv4/route.c | 44 +++++++++++++++++++++++++++++---------------
>   net/ipv6/route.c |  5 ++++-
>   2 files changed, 33 insertions(+), 16 deletions(-)
>