[v2,net] tcp: make challenge acks less predictable
diff mbox

Message ID 1468137842.30694.58.camel@edumazet-glaptop3.roam.corp.google.com
State Accepted, archived
Delegated to: David Miller
Headers show

Commit Message

Eric Dumazet July 10, 2016, 8:04 a.m. UTC
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(-)

Comments

Neal Cardwell July 10, 2016, 12:55 p.m. UTC | #1
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
Yue Cao July 10, 2016, 6:28 p.m. UTC | #2
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
Eric Dumazet July 11, 2016, 8:02 a.m. UTC | #3
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
Yuchung Cheng July 11, 2016, 4:40 p.m. UTC | #4
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);
>         }
>
>
David Miller July 11, 2016, 8:34 p.m. UTC | #5
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.
Yue Cao July 13, 2016, 6:54 p.m. UTC | #6
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
>
>
>

Patch
diff mbox

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);
 	}