[PATCH net] tcp: make challenge acks less predictable

[PATCH net] tcp: make challenge acks less predictable

[Eric Dumazet]

From: Eric Dumazet <edumazet@google.com>

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. This might be done later.

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>
---
diff --git a/Documentation/networking/ip-sysctl.txt b/Documentation/networking/ip-sysctl.txt
index 9ae929395b24..391ed93a8e49 100644
--- a/Documentation/networking/ip-sysctl.txt
+++ b/Documentation/networking/ip-sysctl.txt
@@ -732,7 +732,7 @@ tcp_limit_output_bytes - INTEGER
 tcp_challenge_ack_limit - INTEGER
 	Limits number of Challenge ACK sent per second, as recommended
 	in RFC 5961 (Improving TCP's Robustness to Blind In-Window Attacks)
-	Default: 100
+	Default: 1000
 
 UDP variables:
 
diff --git a/net/ipv4/tcp_input.c b/net/ipv4/tcp_input.c
index d6c8f4cd0800..25f95a41090a 100644
--- a/net/ipv4/tcp_input.c
+++ b/net/ipv4/tcp_input.c
@@ -87,7 +87,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;
@@ -3455,10 +3455,11 @@ not_rate_limited:
 static void tcp_send_challenge_ack(struct sock *sk, const struct sk_buff *skb)
 {
 	/* unprotected vars, we dont care of overwrites */
-	static u32 challenge_timestamp;
+	static unsigned int challenge_window = HZ;
+	static unsigned long challenge_timestamp;
 	static unsigned int challenge_count;
 	struct tcp_sock *tp = tcp_sk(sk);
-	u32 now;
+	unsigned long now;
 
 	/* First check our per-socket dupack rate limit. */
 	if (tcp_oow_rate_limited(sock_net(sk), skb,
@@ -3467,9 +3468,11 @@ static void tcp_send_challenge_ack(struct sock *sk, const struct sk_buff *skb)
 		return;
 
 	/* Then check the check host-wide RFC 5961 rate limit. */
-	now = jiffies / HZ;
-	if (now != challenge_timestamp) {
+	now = jiffies;
+	if (time_before(now, challenge_timestamp) ||
+	    time_after_eq(now, challenge_timestamp + challenge_window)) {
 		challenge_timestamp = now;
+		challenge_window = HZ/2 + prandom_u32_max(HZ);
 		challenge_count = 0;
 	}
 	if (++challenge_count <= sysctl_tcp_challenge_ack_limit) {

Re: [PATCH net] tcp: make challenge acks less predictable

[Eric Dumazet]

On Fri, 2016-07-08 at 17:27 -0700, Yue Cao wrote:
> Hi Eric, 
> 
> 
> Thank you for the email. After rethinking the suggested patch, our
> side-channel attack might still work.
> 
> 
> The main idea behind the patch is to change challenge_count lifetime
> from 1s to a random value in the range [0.5s, 1.5s), which creates a
> time synchronization issue at the attacker's end. 
> 
> 
> In our modified attack, 
> 1. Instead of sending several packets throughout the 1s duration,
> attacker sends fewer packets in a short period (e.g. 0.1s, or even
> shorter). It is likely that this short period will be included in one
> challenge_count lifetime at the server’s end.
> 2. If this short period covers two challenge_counts’ lifetime or some
> rare case that attacker is not sure, attacker can repeat sending same
> packets after a short period (e.g. 1.5s) to confirm it. 
> 3. These packets should include one or more spoofed packets and 1005(a
> value bigger than 1001) packets to exhaust such side channel. 
> 
> 
> In summary, if the attacker receives less than 1000 packets from the
> server, it must be a good guess. If the attacker receives more than
> 1000 packets from the server, this short period covers two
> challenge_counts’ lifetime and the attacker has to repeat sending same
> packets after a short duration. If the attacker receives exactly 1000
> packets from the server, it is most likely a wrong guess. However, the
> attacker would better repeat sending packets to confirm it since these
> 1000 packets may be sent from two continuous challenge_counts’
> lifetime(though it’s a rare case).

OK so all we need is to vary the 1000 value a bit so that attacker can
not predict it, as Linus first did.

I will send a V2, thanks a lot !

[PATCH v2 net] tcp: make challenge acks less predictable

[Eric Dumazet]

From: Eric Dumazet <edumazet@google.com>

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>
---
 net/ipv4/tcp_input.c |   15 ++++++++++-----
 1 file changed, 10 insertions(+), 5 deletions(-)

diff --git a/net/ipv4/tcp_input.c b/net/ipv4/tcp_input.c
index d6c8f4cd0800..91868bb17818 100644
--- a/net/ipv4/tcp_input.c
+++ b/net/ipv4/tcp_input.c
@@ -87,7 +87,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;
@@ -3458,7 +3458,7 @@ static void tcp_send_challenge_ack(struct sock *sk, const struct sk_buff *skb)
 	static u32 challenge_timestamp;
 	static unsigned int challenge_count;
 	struct tcp_sock *tp = tcp_sk(sk);
-	u32 now;
+	u32 count, now;
 
 	/* First check our per-socket dupack rate limit. */
 	if (tcp_oow_rate_limited(sock_net(sk), skb,
@@ -3466,13 +3466,18 @@ static void tcp_send_challenge_ack(struct sock *sk, const struct sk_buff *skb)
 				 &tp->last_oow_ack_time))
 		return;
 
-	/* Then check the check host-wide RFC 5961 rate limit. */
+	/* Then check host-wide RFC 5961 rate limit. */
 	now = jiffies / HZ;
 	if (now != challenge_timestamp) {
+		u32 half = (sysctl_tcp_challenge_ack_limit + 1) >> 1;
+
 		challenge_timestamp = now;
-		challenge_count = 0;
+		WRITE_ONCE(challenge_count, half +
+			   prandom_u32_max(sysctl_tcp_challenge_ack_limit));
 	}
-	if (++challenge_count <= sysctl_tcp_challenge_ack_limit) {
+	count = READ_ONCE(challenge_count);
+	if (count > 0) {
+		WRITE_ONCE(challenge_count, count - 1);
 		NET_INC_STATS(sock_net(sk), LINUX_MIB_TCPCHALLENGEACK);
 		tcp_send_ack(sk);
 	}

Re: [PATCH v2 net] tcp: make challenge acks less predictable

[Neal Cardwell]

On Sun, Jul 10, 2016 at 4:04 AM, Eric Dumazet <eric.dumazet@gmail.com> wrote:
>
> From: Eric Dumazet <edumazet@google.com>
>
> 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>

Thanks, Eric!

neal

Re: [PATCH v2 net] tcp: make challenge acks less predictable

[Yue Cao]

This second patch does make our attack much harder but it's still
possible to do such off-path attack with enough network bandwidth.
Here is our modified attack for this second patch.

Modified Attack:
Main idea of our attack is to send multiple same spoofed packets in 1
second so attacker can confirm if it's a right guess or wrong guess.
In more detail, attacker sends more than 1000 (e.g. 1500) spoofed
packets for a same guessed value at beginning. After that, attacker
sends 1500 packets during the same second to determine whether
previous guess is right or wrong, by using following rules:
If attacker receives less than 500 Challenge ACKs, it's a right guess.
For a example, if 1500 spoofed packets are sent with a correct
value(right guess), all Challenge ACKs will be sent to victim client
in that second and attacker receives nothing. Otherwise, it's a wrong
guess.

Since this global rate limit always leaks some information as a
side-channel, we are wondering if eliminating it completely would be a
good idea. In fact, according to our latest test, FreeBSD and Windows
do not have any such rate limit implemented. Looking forward to your
replies.

Best,
Yue

On Sun, Jul 10, 2016 at 5:55 AM, Neal Cardwell <ncardwell@google.com> wrote:
>
> On Sun, Jul 10, 2016 at 4:04 AM, Eric Dumazet <eric.dumazet@gmail.com> wrote:
> >
> > From: Eric Dumazet <edumazet@google.com>
> >
> > 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>
>
> Thanks, Eric!
>
> neal

Re: [PATCH v2 net] tcp: make challenge acks less predictable

[Eric Dumazet]

On Sun, 2016-07-10 at 11:28 -0700, Yue Cao wrote:
> This second patch does make our attack much harder but it's still
> possible to do such off-path attack with enough network bandwidth.
> Here is our modified attack for this second patch.
> 
> Modified Attack:
> Main idea of our attack is to send multiple same spoofed packets in 1
> second so attacker can confirm if it's a right guess or wrong guess.
> In more detail, attacker sends more than 1000 (e.g. 1500) spoofed
> packets for a same guessed value at beginning. After that, attacker
> sends 1500 packets during the same second to determine whether
> previous guess is right or wrong, by using following rules:
> If attacker receives less than 500 Challenge ACKs, it's a right guess.
> For a example, if 1500 spoofed packets are sent with a correct
> value(right guess), all Challenge ACKs will be sent to victim client
> in that second and attacker receives nothing. Otherwise, it's a wrong
> guess.
> 
> Since this global rate limit always leaks some information as a
> side-channel, we are wondering if eliminating it completely would be a
> good idea. In fact, according to our latest test, FreeBSD and Windows
> do not have any such rate limit implemented. Looking forward to your
> replies.

Are you sure Windows is implementing RFC 5961 ? Linux got in in 3.6.

We do want RFC 5961, compared to the small nuisance of the attack you
describe.

Nuisance of having a way for hackers to send a RST packet after
consuming thousands of probe packets is nothing, compared to the
nuisance of ACK storms we had before rate limiting was added in 3.6 (and
refined in 4.0). This was a serious problem for real servers, because of
buggy firewalls and appliances.

You probably know that if someone worries about TCP flows being
compromised, it should use SSL, so that traffic injection is less likely
to happen.

Most TCP flows in the Internet are short lived (less than 1 minute).

Having to establish about 500 flows to the victim is already a
challenge, since the victim would already be in trouble if it was
allowing so many idle flows.

So the 'solution' would be to backport
f2b2c582e82429270d5818fbabe653f4359d7024
("tcp: mitigate ACK loops for connections as tcp_sock")

Then apply the v2 patch so that the limit is randomized.

Then set the default limit to 2^31

Re: [PATCH v2 net] tcp: make challenge acks less predictable

[Yuchung Cheng]

On Sun, Jul 10, 2016 at 1:04 AM, Eric Dumazet <eric.dumazet@gmail.com> wrote:
> From: Eric Dumazet <edumazet@google.com>
>
> 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: Yuchung Cheng <ycheng@google.com>

Nice fix. I like v2 a lot.

>  net/ipv4/tcp_input.c |   15 ++++++++++-----
>  1 file changed, 10 insertions(+), 5 deletions(-)
>
> diff --git a/net/ipv4/tcp_input.c b/net/ipv4/tcp_input.c
> index d6c8f4cd0800..91868bb17818 100644
> --- a/net/ipv4/tcp_input.c
> +++ b/net/ipv4/tcp_input.c
> @@ -87,7 +87,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;
> @@ -3458,7 +3458,7 @@ static void tcp_send_challenge_ack(struct sock *sk, const struct sk_buff *skb)
>         static u32 challenge_timestamp;
>         static unsigned int challenge_count;
>         struct tcp_sock *tp = tcp_sk(sk);
> -       u32 now;
> +       u32 count, now;
>
>         /* First check our per-socket dupack rate limit. */
>         if (tcp_oow_rate_limited(sock_net(sk), skb,
> @@ -3466,13 +3466,18 @@ static void tcp_send_challenge_ack(struct sock *sk, const struct sk_buff *skb)
>                                  &tp->last_oow_ack_time))
>                 return;
>
> -       /* Then check the check host-wide RFC 5961 rate limit. */
> +       /* Then check host-wide RFC 5961 rate limit. */
>         now = jiffies / HZ;
>         if (now != challenge_timestamp) {
> +               u32 half = (sysctl_tcp_challenge_ack_limit + 1) >> 1;
> +
>                 challenge_timestamp = now;
> -               challenge_count = 0;
> +               WRITE_ONCE(challenge_count, half +
> +                          prandom_u32_max(sysctl_tcp_challenge_ack_limit));
>         }
> -       if (++challenge_count <= sysctl_tcp_challenge_ack_limit) {
> +       count = READ_ONCE(challenge_count);
> +       if (count > 0) {
> +               WRITE_ONCE(challenge_count, count - 1);
>                 NET_INC_STATS(sock_net(sk), LINUX_MIB_TCPCHALLENGEACK);
>                 tcp_send_ack(sk);
>         }
>
>

Re: [PATCH v2 net] tcp: make challenge acks less predictable

[David Miller]

From: Eric Dumazet <eric.dumazet@gmail.com>
Date: Sun, 10 Jul 2016 10:04:02 +0200

> From: Eric Dumazet <edumazet@google.com>
> 
> 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>

Applied and queued up for -stable, thanks Eric.

Re: [PATCH v2 net] tcp: make challenge acks less predictable

[Yue Cao]

I see your point and I agree with you that SSL protects victims from
this hijacking attack, especially with full HSTS.

For Windows case, since Windows is a black box for us, we tested its
Challenge ACK mechanism with Windows Server 2012 R2 Base and Windows
Server 2008 R2 from Amazon EC2. The results show that Windows also add
some strategies to mitigate blind in-window attack problem, but the
mitigated results are not as same as what mentioned in RFC 5961.

Please let me know if I said something wrong. Thanks for the fix!

Best,
Yue

On Mon, Jul 11, 2016 at 1:02 AM, Eric Dumazet <eric.dumazet@gmail.com> wrote:
> On Sun, 2016-07-10 at 11:28 -0700, Yue Cao wrote:
>> This second patch does make our attack much harder but it's still
>> possible to do such off-path attack with enough network bandwidth.
>> Here is our modified attack for this second patch.
>>
>> Modified Attack:
>> Main idea of our attack is to send multiple same spoofed packets in 1
>> second so attacker can confirm if it's a right guess or wrong guess.
>> In more detail, attacker sends more than 1000 (e.g. 1500) spoofed
>> packets for a same guessed value at beginning. After that, attacker
>> sends 1500 packets during the same second to determine whether
>> previous guess is right or wrong, by using following rules:
>> If attacker receives less than 500 Challenge ACKs, it's a right guess.
>> For a example, if 1500 spoofed packets are sent with a correct
>> value(right guess), all Challenge ACKs will be sent to victim client
>> in that second and attacker receives nothing. Otherwise, it's a wrong
>> guess.
>>
>> Since this global rate limit always leaks some information as a
>> side-channel, we are wondering if eliminating it completely would be a
>> good idea. In fact, according to our latest test, FreeBSD and Windows
>> do not have any such rate limit implemented. Looking forward to your
>> replies.
>
> Are you sure Windows is implementing RFC 5961 ? Linux got in in 3.6.
>
> We do want RFC 5961, compared to the small nuisance of the attack you
> describe.
>
> Nuisance of having a way for hackers to send a RST packet after
> consuming thousands of probe packets is nothing, compared to the
> nuisance of ACK storms we had before rate limiting was added in 3.6 (and
> refined in 4.0). This was a serious problem for real servers, because of
> buggy firewalls and appliances.
>
> You probably know that if someone worries about TCP flows being
> compromised, it should use SSL, so that traffic injection is less likely
> to happen.
>
> Most TCP flows in the Internet are short lived (less than 1 minute).
>
> Having to establish about 500 flows to the victim is already a
> challenge, since the victim would already be in trouble if it was
> allowing so many idle flows.
>
> So the 'solution' would be to backport
> f2b2c582e82429270d5818fbabe653f4359d7024
> ("tcp: mitigate ACK loops for connections as tcp_sock")
>
> Then apply the v2 patch so that the limit is randomized.
>
> Then set the default limit to 2^31
>
>
>