[PATCH 3.10.y] tcp: make challenge acks less predictable

[PATCH 3.10.y] tcp: make challenge acks less predictable

[Charles (Chas) Williams]

From: Eric Dumazet <edumazet@google.com>

[ Upstream commit 75ff39ccc1bd5d3c455b6822ab09e533c551f758 ]

Yue Cao claims that current host rate limiting of challenge ACKS
(RFC 5961) could leak enough information to allow a patient attacker
to hijack TCP sessions. He will soon provide details in an academic
paper.

This patch increases the default limit from 100 to 1000, and adds
some randomization so that the attacker can no longer hijack
sessions without spending a considerable amount of probes.

Based on initial analysis and patch from Linus.

Note that we also have per socket rate limiting, so it is tempting
to remove the host limit in the future.

v2: randomize the count of challenge acks per second, not the period.

Fixes: 282f23c6ee34 ("tcp: implement RFC 5961 3.2")
Reported-by: Yue Cao <ycao009@ucr.edu>
Signed-off-by: Eric Dumazet <edumazet@google.com>
Suggested-by: Linus Torvalds <torvalds@linux-foundation.org>
Cc: Yuchung Cheng <ycheng@google.com>
Cc: Neal Cardwell <ncardwell@google.com>
Acked-by: Neal Cardwell <ncardwell@google.com>
Acked-by: Yuchung Cheng <ycheng@google.com>
Signed-off-by: David S. Miller <davem@davemloft.net>
[ ciwillia: backport to 3.10-stable ]
Signed-off-by: Chas Williams <ciwillia@brocade.com>
---
 net/ipv4/tcp_input.c | 14 +++++++++++---
 1 file changed, 11 insertions(+), 3 deletions(-)

diff --git a/net/ipv4/tcp_input.c b/net/ipv4/tcp_input.c
index f89087c..36df4d8 100644
--- a/net/ipv4/tcp_input.c
+++ b/net/ipv4/tcp_input.c
@@ -68,6 +68,7 @@
 #include <linux/module.h>
 #include <linux/sysctl.h>
 #include <linux/kernel.h>
+#include <linux/reciprocal_div.h>
 #include <net/dst.h>
 #include <net/tcp.h>
 #include <net/inet_common.h>
@@ -87,7 +88,7 @@ int sysctl_tcp_adv_win_scale __read_mostly = 1;
 EXPORT_SYMBOL(sysctl_tcp_adv_win_scale);
 
 /* rfc5961 challenge ack rate limiting */
-int sysctl_tcp_challenge_ack_limit = 100;
+int sysctl_tcp_challenge_ack_limit = 1000;
 
 int sysctl_tcp_stdurg __read_mostly;
 int sysctl_tcp_rfc1337 __read_mostly;
@@ -3288,12 +3289,19 @@ static void tcp_send_challenge_ack(struct sock *sk)
 	static u32 challenge_timestamp;
 	static unsigned int challenge_count;
 	u32 now = jiffies / HZ;
+	u32 count;
 
 	if (now != challenge_timestamp) {
+		u32 half = (sysctl_tcp_challenge_ack_limit + 1) >> 1;
+
 		challenge_timestamp = now;
-		challenge_count = 0;
+		challenge_count = half +
+				  reciprocal_divide(prandom_u32(),
+					sysctl_tcp_challenge_ack_limit);
 	}
-	if (++challenge_count <= sysctl_tcp_challenge_ack_limit) {
+	count = challenge_count;
+	if (count > 0) {
+		challenge_count = count - 1;
 		NET_INC_STATS_BH(sock_net(sk), LINUX_MIB_TCPCHALLENGEACK);
 		tcp_send_ack(sk);
 	}
-- 
2.5.5

Re: [PATCH 3.10.y] tcp: make challenge acks less predictable

[Eric Dumazet]

On Tue, Aug 16, 2016 at 4:31 PM, Charles (Chas) Williams
<ciwillia@brocade.com> wrote:
> From: Eric Dumazet <edumazet@google.com>
>
> [ Upstream commit 75ff39ccc1bd5d3c455b6822ab09e533c551f758 ]
>
> Yue Cao claims that current host rate limiting of challenge ACKS
> (RFC 5961) could leak enough information to allow a patient attacker
> to hijack TCP sessions. He will soon provide details in an academic
> paper.
>
> This patch increases the default limit from 100 to 1000, and adds
> some randomization so that the attacker can no longer hijack
> sessions without spending a considerable amount of probes.
>
> Based on initial analysis and patch from Linus.
>
> Note that we also have per socket rate limiting, so it is tempting
> to remove the host limit in the future.
>
> v2: randomize the count of challenge acks per second, not the period.
>
> Fixes: 282f23c6ee34 ("tcp: implement RFC 5961 3.2")
> Reported-by: Yue Cao <ycao009@ucr.edu>
> Signed-off-by: Eric Dumazet <edumazet@google.com>
> Suggested-by: Linus Torvalds <torvalds@linux-foundation.org>
> Cc: Yuchung Cheng <ycheng@google.com>
> Cc: Neal Cardwell <ncardwell@google.com>
> Acked-by: Neal Cardwell <ncardwell@google.com>
> Acked-by: Yuchung Cheng <ycheng@google.com>
> Signed-off-by: David S. Miller <davem@davemloft.net>
> [ ciwillia: backport to 3.10-stable ]
> Signed-off-by: Chas Williams <ciwillia@brocade.com>
> ---
>  net/ipv4/tcp_input.c | 14 +++++++++++---
>  1 file changed, 11 insertions(+), 3 deletions(-)
>
> diff --git a/net/ipv4/tcp_input.c b/net/ipv4/tcp_input.c
> index f89087c..36df4d8 100644
> --- a/net/ipv4/tcp_input.c
> +++ b/net/ipv4/tcp_input.c
> @@ -68,6 +68,7 @@
>  #include <linux/module.h>
>  #include <linux/sysctl.h>
>  #include <linux/kernel.h>
> +#include <linux/reciprocal_div.h>
>  #include <net/dst.h>
>  #include <net/tcp.h>
>  #include <net/inet_common.h>
> @@ -87,7 +88,7 @@ int sysctl_tcp_adv_win_scale __read_mostly = 1;
>  EXPORT_SYMBOL(sysctl_tcp_adv_win_scale);
>
>  /* rfc5961 challenge ack rate limiting */
> -int sysctl_tcp_challenge_ack_limit = 100;
> +int sysctl_tcp_challenge_ack_limit = 1000;
>
>  int sysctl_tcp_stdurg __read_mostly;
>  int sysctl_tcp_rfc1337 __read_mostly;
> @@ -3288,12 +3289,19 @@ static void tcp_send_challenge_ack(struct sock *sk)
>         static u32 challenge_timestamp;
>         static unsigned int challenge_count;
>         u32 now = jiffies / HZ;
> +       u32 count;
>
>         if (now != challenge_timestamp) {
> +               u32 half = (sysctl_tcp_challenge_ack_limit + 1) >> 1;
> +
>                 challenge_timestamp = now;
> -               challenge_count = 0;
> +               challenge_count = half +
> +                                 reciprocal_divide(prandom_u32(),
> +                                       sysctl_tcp_challenge_ack_limit);


ACCESS_ONCE(challenge_count) = half + reciprocal_divide(...)

>         }
> -       if (++challenge_count <= sysctl_tcp_challenge_ack_limit) {
> +       count = challenge_count;

            count = ACCESS_ONCE(challenge_count);

> +       if (count > 0) {
> +               challenge_count = count - 1;

              ACCESS_ONCE(challenge_count) = count - 1;

>                 NET_INC_STATS_BH(sock_net(sk), LINUX_MIB_TCPCHALLENGEACK);
>                 tcp_send_ack(sk);
>         }
> --
> 2.5.5
>


Thanks.

Re: [PATCH 3.10.y] tcp: make challenge acks less predictable

[Charles (Chas) Williams]

On 08/16/2016 04:36 PM, Eric Dumazet wrote:
> On Tue, Aug 16, 2016 at 4:31 PM, Charles (Chas) Williams
> <ciwillia@brocade.com> wrote:
>> From: Eric Dumazet <edumazet@google.com>
>>
>> [ Upstream commit 75ff39ccc1bd5d3c455b6822ab09e533c551f758 ]
>>
>> Yue Cao claims that current host rate limiting of challenge ACKS
>> (RFC 5961) could leak enough information to allow a patient attacker
>> to hijack TCP sessions. He will soon provide details in an academic
>> paper.
>>
>> This patch increases the default limit from 100 to 1000, and adds
>> some randomization so that the attacker can no longer hijack
>> sessions without spending a considerable amount of probes.
>>
>> Based on initial analysis and patch from Linus.
>>
>> Note that we also have per socket rate limiting, so it is tempting
>> to remove the host limit in the future.
>>
>> v2: randomize the count of challenge acks per second, not the period.
>>
>> Fixes: 282f23c6ee34 ("tcp: implement RFC 5961 3.2")
>> Reported-by: Yue Cao <ycao009@ucr.edu>
>> Signed-off-by: Eric Dumazet <edumazet@google.com>
>> Suggested-by: Linus Torvalds <torvalds@linux-foundation.org>
>> Cc: Yuchung Cheng <ycheng@google.com>
>> Cc: Neal Cardwell <ncardwell@google.com>
>> Acked-by: Neal Cardwell <ncardwell@google.com>
>> Acked-by: Yuchung Cheng <ycheng@google.com>
>> Signed-off-by: David S. Miller <davem@davemloft.net>
>> [ ciwillia: backport to 3.10-stable ]
>> Signed-off-by: Chas Williams <ciwillia@brocade.com>
>> ---
>>  net/ipv4/tcp_input.c | 14 +++++++++++---
>>  1 file changed, 11 insertions(+), 3 deletions(-)
>>
>> diff --git a/net/ipv4/tcp_input.c b/net/ipv4/tcp_input.c
>> index f89087c..36df4d8 100644
>> --- a/net/ipv4/tcp_input.c
>> +++ b/net/ipv4/tcp_input.c
>> @@ -68,6 +68,7 @@
>>  #include <linux/module.h>
>>  #include <linux/sysctl.h>
>>  #include <linux/kernel.h>
>> +#include <linux/reciprocal_div.h>
>>  #include <net/dst.h>
>>  #include <net/tcp.h>
>>  #include <net/inet_common.h>
>> @@ -87,7 +88,7 @@ int sysctl_tcp_adv_win_scale __read_mostly = 1;
>>  EXPORT_SYMBOL(sysctl_tcp_adv_win_scale);
>>
>>  /* rfc5961 challenge ack rate limiting */
>> -int sysctl_tcp_challenge_ack_limit = 100;
>> +int sysctl_tcp_challenge_ack_limit = 1000;
>>
>>  int sysctl_tcp_stdurg __read_mostly;
>>  int sysctl_tcp_rfc1337 __read_mostly;
>> @@ -3288,12 +3289,19 @@ static void tcp_send_challenge_ack(struct sock *sk)
>>         static u32 challenge_timestamp;
>>         static unsigned int challenge_count;
>>         u32 now = jiffies / HZ;
>> +       u32 count;
>>
>>         if (now != challenge_timestamp) {
>> +               u32 half = (sysctl_tcp_challenge_ack_limit + 1) >> 1;
>> +
>>                 challenge_timestamp = now;
>> -               challenge_count = 0;
>> +               challenge_count = half +
>> +                                 reciprocal_divide(prandom_u32(),
>> +                                       sysctl_tcp_challenge_ack_limit);
>
>
> ACCESS_ONCE(challenge_count) = half + reciprocal_divide(...)
>
>>         }
>> -       if (++challenge_count <= sysctl_tcp_challenge_ack_limit) {
>> +       count = challenge_count;
>
>             count = ACCESS_ONCE(challenge_count);
>
>> +       if (count > 0) {
>> +               challenge_count = count - 1;
>
>               ACCESS_ONCE(challenge_count) = count - 1;
>
>>                 NET_INC_STATS_BH(sock_net(sk), LINUX_MIB_TCPCHALLENGEACK);
>>                 tcp_send_ack(sk);
>>         }
>> --
>> 2.5.5
>>
>
>
> Thanks.

Thanks for the update.  I missed the later changes.  Coming in v3.  Sorry.

Re: [PATCH 3.10.y] tcp: make challenge acks less predictable

[Greg KH]

On Tue, Aug 16, 2016 at 04:36:40PM -0400, Eric Dumazet wrote:
> On Tue, Aug 16, 2016 at 4:31 PM, Charles (Chas) Williams
> <ciwillia@brocade.com> wrote:
> > From: Eric Dumazet <edumazet@google.com>
> >
> > [ Upstream commit 75ff39ccc1bd5d3c455b6822ab09e533c551f758 ]
> >
> > Yue Cao claims that current host rate limiting of challenge ACKS
> > (RFC 5961) could leak enough information to allow a patient attacker
> > to hijack TCP sessions. He will soon provide details in an academic
> > paper.
> >
> > This patch increases the default limit from 100 to 1000, and adds
> > some randomization so that the attacker can no longer hijack
> > sessions without spending a considerable amount of probes.
> >
> > Based on initial analysis and patch from Linus.
> >
> > Note that we also have per socket rate limiting, so it is tempting
> > to remove the host limit in the future.
> >
> > v2: randomize the count of challenge acks per second, not the period.
> >
> > Fixes: 282f23c6ee34 ("tcp: implement RFC 5961 3.2")
> > Reported-by: Yue Cao <ycao009@ucr.edu>
> > Signed-off-by: Eric Dumazet <edumazet@google.com>
> > Suggested-by: Linus Torvalds <torvalds@linux-foundation.org>
> > Cc: Yuchung Cheng <ycheng@google.com>
> > Cc: Neal Cardwell <ncardwell@google.com>
> > Acked-by: Neal Cardwell <ncardwell@google.com>
> > Acked-by: Yuchung Cheng <ycheng@google.com>
> > Signed-off-by: David S. Miller <davem@davemloft.net>
> > [ ciwillia: backport to 3.10-stable ]
> > Signed-off-by: Chas Williams <ciwillia@brocade.com>
> > ---
> >  net/ipv4/tcp_input.c | 14 +++++++++++---
> >  1 file changed, 11 insertions(+), 3 deletions(-)
> >
> > diff --git a/net/ipv4/tcp_input.c b/net/ipv4/tcp_input.c
> > index f89087c..36df4d8 100644
> > --- a/net/ipv4/tcp_input.c
> > +++ b/net/ipv4/tcp_input.c
> > @@ -68,6 +68,7 @@
> >  #include <linux/module.h>
> >  #include <linux/sysctl.h>
> >  #include <linux/kernel.h>
> > +#include <linux/reciprocal_div.h>
> >  #include <net/dst.h>
> >  #include <net/tcp.h>
> >  #include <net/inet_common.h>
> > @@ -87,7 +88,7 @@ int sysctl_tcp_adv_win_scale __read_mostly = 1;
> >  EXPORT_SYMBOL(sysctl_tcp_adv_win_scale);
> >
> >  /* rfc5961 challenge ack rate limiting */
> > -int sysctl_tcp_challenge_ack_limit = 100;
> > +int sysctl_tcp_challenge_ack_limit = 1000;
> >
> >  int sysctl_tcp_stdurg __read_mostly;
> >  int sysctl_tcp_rfc1337 __read_mostly;
> > @@ -3288,12 +3289,19 @@ static void tcp_send_challenge_ack(struct sock *sk)
> >         static u32 challenge_timestamp;
> >         static unsigned int challenge_count;
> >         u32 now = jiffies / HZ;
> > +       u32 count;
> >
> >         if (now != challenge_timestamp) {
> > +               u32 half = (sysctl_tcp_challenge_ack_limit + 1) >> 1;
> > +
> >                 challenge_timestamp = now;
> > -               challenge_count = 0;
> > +               challenge_count = half +
> > +                                 reciprocal_divide(prandom_u32(),
> > +                                       sysctl_tcp_challenge_ack_limit);
> 
> 
> ACCESS_ONCE(challenge_count) = half + reciprocal_divide(...)
> 
> >         }
> > -       if (++challenge_count <= sysctl_tcp_challenge_ack_limit) {
> > +       count = challenge_count;
> 
>             count = ACCESS_ONCE(challenge_count);
> 
> > +       if (count > 0) {
> > +               challenge_count = count - 1;
> 
>               ACCESS_ONCE(challenge_count) = count - 1;

Crap, I didn't use that for my 3.14 backport :(

I'll go update that in the next release, worse case, it's just a bit
slower than it needs to be...

thanks,

greg k-h