TCP sequence number inference attack on Linux

TCP sequence number inference attack on Linux

[Zhiyun Qian]

Dear sir or madam,

My name is Zhiyun Qian, a recent PhD graduate from University of
Michigan. As our recent research effort, along with my colleagues, we
identified a vulnerability related to Linux. Details described in our
paper published at this year's ACM Conference on Computer and
Communications Security (CCS): Collaborative TCP Sequence Number
Inference Attack available
http://web.eecs.umich.edu/~zhiyunq/pub/ccs12_TCP_sequence_number_inference.pdf

Keywords: TCP, sequence number inference, DelayedAckLost counter,
privilege-escalation attack

The vulnerability would allow an local malicious program to gain write
access to TCP connections of other applications. An example attack
scenario (on android) would be "an attacker uploads a seemingly benign
app to the google play, when run at the background, it can inject
malicious HTML payload into a webpage open by the browser".

The problem is caused by the common TCP stats counters (the specific
counter I found is DelayedACKLost) maintained by the kernel (but
exposed to user space). By reading and reporting such counters to an
external attacker (colluded), the aforementioned attack can be
accomplished.

It is essentially a side-channel attack (using TCP stats counters to
infer TCP sequence numbers), but it is so real and easy to carry out
that I believe it should be considered a vulnerability. From a
difference perspective, this attack can be considered as a privilege
escalation attack since it allows a local non-privileged program to
gain write access to TCP connections made by other processes.

The lines of code in kernel impacted by the attack is:
net/ipv4/tcp_input.c at line 4166 (as in the latest kernel v3.7.1)

4160 static void tcp_send_dupack(struct sock *sk, const struct sk_buff *skb)
4161 {
4162        struct tcp_sock *tp = tcp_sk(sk);
4163
4164        if (TCP_SKB_CB(skb)->end_seq != TCP_SKB_CB(skb)->seq &&
4165            before(TCP_SKB_CB(skb)->seq, tp->rcv_nxt)) {
4166                NET_INC_STATS_BH(sock_net(sk), LINUX_MIB_DELAYEDACKLOST);
4167                tcp_enter_quickack_mode(sk);
4168
4169                if (tcp_is_sack(tp) && sysctl_tcp_dsack) {
4170                        u32 end_seq = TCP_SKB_CB(skb)->end_seq;
4171
4172                        if (after(TCP_SKB_CB(skb)->end_seq, tp->rcv_nxt))
4173                                end_seq = tp->rcv_nxt;
4174                        tcp_dsack_set(sk, TCP_SKB_CB(skb)->seq, end_seq);
4175                }
4176        }
4177
4178        tcp_send_ack(sk);
4179 }


IMHO, an easy fix to the problem is to disallow unprivileged access to
counters such as DelayedAckLost. However, this solution may not be
ideal. A better way is to always enforce both acknowledgement number
and sequence number check on each incoming TCP packet instead of
checking one at a time. Currently, Linux TCP stack first only
validates the SEQ number and then subsequently the ACK number. If the
sequence number is invalid, the delayedAckLost counter will be
incremented (information about sequence number leaked already
regardless of the ACK number). To make attacker's job much harder (we
should require the attacker to guess both the valid sequence number
and ACK number at the same time). For instance, following RFC 5961:
(SND.UNA - MAX.SND.WND) <= SEG.ACK <= SND.NXT, this would require the
attacker to send many times (on the order of 10000) more packets to
conduct the same attack.

Please feel free to ask me any questions regarding this vulnerability.

Best,
-Zhiyun

Re: TCP sequence number inference attack on Linux

[Eric Dumazet]

On Fri, 2012-12-21 at 12:58 -0500, Zhiyun Qian wrote:
> Dear sir or madam,
> 
> My name is Zhiyun Qian, a recent PhD graduate from University of
> Michigan. As our recent research effort, along with my colleagues, we
> identified a vulnerability related to Linux. Details described in our
> paper published at this year's ACM Conference on Computer and
> Communications Security (CCS): Collaborative TCP Sequence Number
> Inference Attack available
> http://web.eecs.umich.edu/~zhiyunq/pub/ccs12_TCP_sequence_number_inference.pdf
> 
> Keywords: TCP, sequence number inference, DelayedAckLost counter,
> privilege-escalation attack
> 
> The vulnerability would allow an local malicious program to gain write
> access to TCP connections of other applications. An example attack
> scenario (on android) would be "an attacker uploads a seemingly benign
> app to the google play, when run at the background, it can inject
> malicious HTML payload into a webpage open by the browser".
> 
> The problem is caused by the common TCP stats counters (the specific
> counter I found is DelayedACKLost) maintained by the kernel (but
> exposed to user space). By reading and reporting such counters to an
> external attacker (colluded), the aforementioned attack can be
> accomplished.
> 
> It is essentially a side-channel attack (using TCP stats counters to
> infer TCP sequence numbers), but it is so real and easy to carry out
> that I believe it should be considered a vulnerability. From a
> difference perspective, this attack can be considered as a privilege
> escalation attack since it allows a local non-privileged program to
> gain write access to TCP connections made by other processes.
> 
> The lines of code in kernel impacted by the attack is:
> net/ipv4/tcp_input.c at line 4166 (as in the latest kernel v3.7.1)
> 
> 4160 static void tcp_send_dupack(struct sock *sk, const struct sk_buff *skb)
> 4161 {
> 4162        struct tcp_sock *tp = tcp_sk(sk);
> 4163
> 4164        if (TCP_SKB_CB(skb)->end_seq != TCP_SKB_CB(skb)->seq &&
> 4165            before(TCP_SKB_CB(skb)->seq, tp->rcv_nxt)) {
> 4166                NET_INC_STATS_BH(sock_net(sk), LINUX_MIB_DELAYEDACKLOST);
> 4167                tcp_enter_quickack_mode(sk);
> 4168
> 4169                if (tcp_is_sack(tp) && sysctl_tcp_dsack) {
> 4170                        u32 end_seq = TCP_SKB_CB(skb)->end_seq;
> 4171
> 4172                        if (after(TCP_SKB_CB(skb)->end_seq, tp->rcv_nxt))
> 4173                                end_seq = tp->rcv_nxt;
> 4174                        tcp_dsack_set(sk, TCP_SKB_CB(skb)->seq, end_seq);
> 4175                }
> 4176        }
> 4177
> 4178        tcp_send_ack(sk);
> 4179 }
> 
> 
> IMHO, an easy fix to the problem is to disallow unprivileged access to
> counters such as DelayedAckLost. However, this solution may not be
> ideal. A better way is to always enforce both acknowledgement number
> and sequence number check on each incoming TCP packet instead of
> checking one at a time. Currently, Linux TCP stack first only
> validates the SEQ number and then subsequently the ACK number. If the
> sequence number is invalid, the delayedAckLost counter will be
> incremented (information about sequence number leaked already
> regardless of the ACK number). To make attacker's job much harder (we
> should require the attacker to guess both the valid sequence number
> and ACK number at the same time). For instance, following RFC 5961:
> (SND.UNA - MAX.SND.WND) <= SEG.ACK <= SND.NXT, this would require the
> attacker to send many times (on the order of 10000) more packets to
> conduct the same attack.
> 
> Please feel free to ask me any questions regarding this vulnerability.


I believe RFC 5961 was implemented in recent linux versions.

Is the described vulnerability still present ?

Re: TCP sequence number inference attack on Linux

[Eric Dumazet]

On Fri, 2012-12-21 at 10:31 -0800, Eric Dumazet wrote:

> I believe RFC 5961 was implemented in recent linux versions.
> 
> Is the described vulnerability still present ?
> 

By the way, I believe Chrome browser uses private network namespaces,
and statistics are per network namespace, so it should be safe.

Re: TCP sequence number inference attack on Linux

[Zhiyun Qian]

That seems like a good idea. I am not sure how it is implemented
though. Is it a new feature of Linux? Would you mind sending some
pointers for this?

Thanks.
-Zhiyun

On Fri, Dec 21, 2012 at 1:52 PM, Eric Dumazet <eric.dumazet@gmail.com> wrote:
> On Fri, 2012-12-21 at 10:31 -0800, Eric Dumazet wrote:
>
>> I believe RFC 5961 was implemented in recent linux versions.
>>
>> Is the described vulnerability still present ?
>>
>
> By the way, I believe Chrome browser uses private network namespaces,
> and statistics are per network namespace, so it should be safe.
>
>
>

Re: TCP sequence number inference attack on Linux

[Eric Dumazet]

On Fri, 2012-12-21 at 14:13 -0500, Zhiyun Qian wrote:
> That seems like a good idea. I am not sure how it is implemented
> though. Is it a new feature of Linux? Would you mind sending some
> pointers for this?

I dont have details, I only remember having to fix a memory allocation
error that was hitting Chrome users.


http://comments.gmane.org/gmane.linux.network/249535


Julien said at that time :

<quote>
It happens when users start Chrome. Chrome will create one new network
NS (for the sandbox).

This has been used for a few years now, but we had our first report in
January of this year and we've been getting a few reports very
recently at a rate that is starting to worry me (crbug.com/110756).

Thanks a lot for helping with this!

Julien
</quote>

Re: TCP sequence number inference attack on Linux

[Hannes Frederic Sowa]

On Fri, Dec 21, 2012 at 02:13:12PM -0500, Zhiyun Qian wrote:
> That seems like a good idea. I am not sure how it is implemented
> though. Is it a new feature of Linux? Would you mind sending some
> pointers for this?

You can check if network namespaces are in use by looking at about:sandbox in
chrome. It should be enabled by default (don't know about chromium, though).

Re: TCP sequence number inference attack on Linux

[Zhiyun Qian]

That's good to know. However, implementing RFC 5961 alone is not
sufficient. Like I said, since DelayedAckLost counter is incremented
purely upon looking at the sequence number, regardless of the ACK
number. An attacker thus can still infer the sequence number based on
DelayedAckLost counter without knowing the right ACK number.

The next question is how can the attacker eventually know the right
ACK number in order to inject real data. It turns out that this is not
hard either. First, based on the current Linux TCP stack, it accepts
incoming packets without ACK flag. Further, if ACK flag is not set,
ACK number will not be checked at all. See code in
net/ipv4/tcp_input.c, function tcp_rcv_established()

5547        if (th->ack && tcp_ack(sk, skb, FLAG_SLOWPATH) < 0)
5548                goto discard;

Second, even if ACK number is always checked before accepting the
payload, it is still possible to infer the ACK number much like how
sequence number can be inferred. The details is described in Section
3.4 of my paper, paragraph starting with "Client-side sequence number
inference".

I'm looking at the latest kernel v3.7.1 right now. I believe the
problem do still exist in today's Linux.

-Zhiyun

On Fri, Dec 21, 2012 at 1:31 PM, Eric Dumazet <erdnetdev@gmail.com> wrote:
> On Fri, 2012-12-21 at 12:58 -0500, Zhiyun Qian wrote:
>> Dear sir or madam,
>>
>> My name is Zhiyun Qian, a recent PhD graduate from University of
>> Michigan. As our recent research effort, along with my colleagues, we
>> identified a vulnerability related to Linux. Details described in our
>> paper published at this year's ACM Conference on Computer and
>> Communications Security (CCS): Collaborative TCP Sequence Number
>> Inference Attack available
>> http://web.eecs.umich.edu/~zhiyunq/pub/ccs12_TCP_sequence_number_inference.pdf
>>
>> Keywords: TCP, sequence number inference, DelayedAckLost counter,
>> privilege-escalation attack
>>
>> The vulnerability would allow an local malicious program to gain write
>> access to TCP connections of other applications. An example attack
>> scenario (on android) would be "an attacker uploads a seemingly benign
>> app to the google play, when run at the background, it can inject
>> malicious HTML payload into a webpage open by the browser".
>>
>> The problem is caused by the common TCP stats counters (the specific
>> counter I found is DelayedACKLost) maintained by the kernel (but
>> exposed to user space). By reading and reporting such counters to an
>> external attacker (colluded), the aforementioned attack can be
>> accomplished.
>>
>> It is essentially a side-channel attack (using TCP stats counters to
>> infer TCP sequence numbers), but it is so real and easy to carry out
>> that I believe it should be considered a vulnerability. From a
>> difference perspective, this attack can be considered as a privilege
>> escalation attack since it allows a local non-privileged program to
>> gain write access to TCP connections made by other processes.
>>
>> The lines of code in kernel impacted by the attack is:
>> net/ipv4/tcp_input.c at line 4166 (as in the latest kernel v3.7.1)
>>
>> 4160 static void tcp_send_dupack(struct sock *sk, const struct sk_buff *skb)
>> 4161 {
>> 4162        struct tcp_sock *tp = tcp_sk(sk);
>> 4163
>> 4164        if (TCP_SKB_CB(skb)->end_seq != TCP_SKB_CB(skb)->seq &&
>> 4165            before(TCP_SKB_CB(skb)->seq, tp->rcv_nxt)) {
>> 4166                NET_INC_STATS_BH(sock_net(sk), LINUX_MIB_DELAYEDACKLOST);
>> 4167                tcp_enter_quickack_mode(sk);
>> 4168
>> 4169                if (tcp_is_sack(tp) && sysctl_tcp_dsack) {
>> 4170                        u32 end_seq = TCP_SKB_CB(skb)->end_seq;
>> 4171
>> 4172                        if (after(TCP_SKB_CB(skb)->end_seq, tp->rcv_nxt))
>> 4173                                end_seq = tp->rcv_nxt;
>> 4174                        tcp_dsack_set(sk, TCP_SKB_CB(skb)->seq, end_seq);
>> 4175                }
>> 4176        }
>> 4177
>> 4178        tcp_send_ack(sk);
>> 4179 }
>>
>>
>> IMHO, an easy fix to the problem is to disallow unprivileged access to
>> counters such as DelayedAckLost. However, this solution may not be
>> ideal. A better way is to always enforce both acknowledgement number
>> and sequence number check on each incoming TCP packet instead of
>> checking one at a time. Currently, Linux TCP stack first only
>> validates the SEQ number and then subsequently the ACK number. If the
>> sequence number is invalid, the delayedAckLost counter will be
>> incremented (information about sequence number leaked already
>> regardless of the ACK number). To make attacker's job much harder (we
>> should require the attacker to guess both the valid sequence number
>> and ACK number at the same time). For instance, following RFC 5961:
>> (SND.UNA - MAX.SND.WND) <= SEG.ACK <= SND.NXT, this would require the
>> attacker to send many times (on the order of 10000) more packets to
>> conduct the same attack.
>>
>> Please feel free to ask me any questions regarding this vulnerability.
>
>
> I believe RFC 5961 was implemented in recent linux versions.
>
> Is the described vulnerability still present ?
>
>
>

Re: TCP sequence number inference attack on Linux

[Eric Dumazet]

On Fri, 2012-12-21 at 14:10 -0500, Zhiyun Qian wrote:
> That's good to know. However, implementing RFC 5961 alone is not
> sufficient. Like I said, since DelayedAckLost counter is incremented
> purely upon looking at the sequence number, regardless of the ACK
> number. An attacker thus can still infer the sequence number based on
> DelayedAckLost counter without knowing the right ACK number.
> 



> The next question is how can the attacker eventually know the right
> ACK number in order to inject real data. It turns out that this is not
> hard either. First, based on the current Linux TCP stack, it accepts
> incoming packets without ACK flag. 

I dont really think so.

We must discard frame is th->ack is not set. (Step 5, line 6142)



> Further, if ACK flag is not set,
> ACK number will not be checked at all. See code in
> net/ipv4/tcp_input.c, function tcp_rcv_established()
> 
> 5547        if (th->ack && tcp_ack(sk, skb, FLAG_SLOWPATH) < 0)
> 5548                goto discard;
> 
> Second, even if ACK number is always checked before accepting the
> payload, it is still possible to infer the ACK number much like how
> sequence number can be inferred. The details is described in Section
> 3.4 of my paper, paragraph starting with "Client-side sequence number
> inference".
> 
> I'm looking at the latest kernel v3.7.1 right now. I believe the
> problem do still exist in today's Linux.
> 

It seems you know pretty well this code, I wonder why you dont send
patches to fix the bugs...

Its not like it has to be buggy forever.

Re: TCP sequence number inference attack on Linux

[Zhiyun Qian]

On Fri, Dec 21, 2012 at 2:27 PM, Eric Dumazet <erdnetdev@gmail.com> wrote:
> On Fri, 2012-12-21 at 14:10 -0500, Zhiyun Qian wrote:
>> That's good to know. However, implementing RFC 5961 alone is not
>> sufficient. Like I said, since DelayedAckLost counter is incremented
>> purely upon looking at the sequence number, regardless of the ACK
>> number. An attacker thus can still infer the sequence number based on
>> DelayedAckLost counter without knowing the right ACK number.
>>
>
>
>
>> The next question is how can the attacker eventually know the right
>> ACK number in order to inject real data. It turns out that this is not
>> hard either. First, based on the current Linux TCP stack, it accepts
>> incoming packets without ACK flag.
>
> I dont really think so.
>
> We must discard frame is th->ack is not set. (Step 5, line 6142)
>

If I am not mistaken, line 6142 in kernel v3.7.1 corresponds to
tcp_rcv_state_process(). According to the comments, "This function
implements the receiving procedure of RFC 793 for all states except
ESTABLISHED and TIME_WAIT." Are you referring to a different kernel
version?

>
>
>> Further, if ACK flag is not set,
>> ACK number will not be checked at all. See code in
>> net/ipv4/tcp_input.c, function tcp_rcv_established()
>>
>> 5547        if (th->ack && tcp_ack(sk, skb, FLAG_SLOWPATH) < 0)
>> 5548                goto discard;
>>
>> Second, even if ACK number is always checked before accepting the
>> payload, it is still possible to infer the ACK number much like how
>> sequence number can be inferred. The details is described in Section
>> 3.4 of my paper, paragraph starting with "Client-side sequence number
>> inference".
>>
>> I'm looking at the latest kernel v3.7.1 right now. I believe the
>> problem do still exist in today's Linux.
>>
>
> It seems you know pretty well this code, I wonder why you dont send
> patches to fix the bugs...
>
> Its not like it has to be buggy forever.
>

I have never submitted any patch before...I would do it if no one else
wants to :)

>
>

Re: TCP sequence number inference attack on Linux

[Eric Dumazet]

On Fri, 2012-12-21 at 14:49 -0500, Zhiyun Qian wrote:

> If I am not mistaken, line 6142 in kernel v3.7.1 corresponds to
> tcp_rcv_state_process(). According to the comments, "This function
> implements the receiving procedure of RFC 793 for all states except
> ESTABLISHED and TIME_WAIT." Are you referring to a different kernel
> version?

You are not mistaken, it seems code is too permissive.

We should reject a frame without ACK flag while in ESTABLISHED state.

Thats explicitly stated in RFC 973.

Then we should make all possible safety checks before even sending a
frame or changing socket variables.

(For instance the tests done in tcp_ack() should be done before calling
tcp_validate_incoming())

John Dykstra in commit 96e0bf4b5193d0 (tcp: Discard segments that ack
data not yet sent) did a step into right direction, but missed this.

Current code assumes the incoming frame is mostly legitimate.

diff --git a/net/ipv4/tcp_input.c b/net/ipv4/tcp_input.c
index a136925..2ea4937 100644
--- a/net/ipv4/tcp_input.c
+++ b/net/ipv4/tcp_input.c
@@ -5551,7 +5551,7 @@ slow_path:
 		return 0;
 
 step5:
-	if (th->ack && tcp_ack(sk, skb, FLAG_SLOWPATH) < 0)
+	if (!th->ack || tcp_ack(sk, skb, FLAG_SLOWPATH) < 0)
 		goto discard;
 
 	/* ts_recent update must be made after we are sure that the packet

Re: TCP sequence number inference attack on Linux

[Zhiyun Qian]

On Fri, Dec 21, 2012 at 5:45 PM, Eric Dumazet <erdnetdev@gmail.com> wrote:
> On Fri, 2012-12-21 at 14:49 -0500, Zhiyun Qian wrote:
>
>> If I am not mistaken, line 6142 in kernel v3.7.1 corresponds to
>> tcp_rcv_state_process(). According to the comments, "This function
>> implements the receiving procedure of RFC 793 for all states except
>> ESTABLISHED and TIME_WAIT." Are you referring to a different kernel
>> version?
>
> You are not mistaken, it seems code is too permissive.
>
> We should reject a frame without ACK flag while in ESTABLISHED state.
>
> Thats explicitly stated in RFC 973.
>
> Then we should make all possible safety checks before even sending a
> frame or changing socket variables.

I completely agree!

>
> (For instance the tests done in tcp_ack() should be done before calling
> tcp_validate_incoming())
>

It seems that it is not straightforward to simply move tcp_ack()
before tcp_validate_incoming() as tcp_ack() currently assumes the tcp
sequence number is already validated and it may adjust certain states
purely depending on the ACK number. I guess the solution is to extract
all safety checks out and put at the very beginning. The rest of the
code in tcp_validate_incoming() and tcp_ack() may still need to
perform the redundant checks since if some state changes are dependent
on the sequence number or ACK number (e.g., window update).

I'm willing to help on this. Perhaps I can draft an initial patch and
you can help take a look before I submit it?

> John Dykstra in commit 96e0bf4b5193d0 (tcp: Discard segments that ack
> data not yet sent) did a step into right direction, but missed this.
>
> Current code assumes the incoming frame is mostly legitimate.
>
> diff --git a/net/ipv4/tcp_input.c b/net/ipv4/tcp_input.c
> index a136925..2ea4937 100644
> --- a/net/ipv4/tcp_input.c
> +++ b/net/ipv4/tcp_input.c
> @@ -5551,7 +5551,7 @@ slow_path:
>                 return 0;
>
>  step5:
> -       if (th->ack && tcp_ack(sk, skb, FLAG_SLOWPATH) < 0)
> +       if (!th->ack || tcp_ack(sk, skb, FLAG_SLOWPATH) < 0)
>                 goto discard;
>
>         /* ts_recent update must be made after we are sure that the packet
>
>

Neat change. This should enforce the ACK flag and ACK number check for
every packet received in established state.

Re: TCP sequence number inference attack on Linux

[Eric Dumazet]

On Fri, 2012-12-21 at 18:52 -0500, Zhiyun Qian wrote:

> It seems that it is not straightforward to simply move tcp_ack()
> before tcp_validate_incoming() as tcp_ack() currently assumes the tcp
> sequence number is already validated and it may adjust certain states
> purely depending on the ACK number. I guess the solution is to extract
> all safety checks out and put at the very beginning. The rest of the
> code in tcp_validate_incoming() and tcp_ack() may still need to
> perform the redundant checks since if some state changes are dependent
> on the sequence number or ACK number (e.g., window update).
> 
> I'm willing to help on this. Perhaps I can draft an initial patch and
> you can help take a look before I submit it?

I began coding a serie of patches.

Part of the problem comes from a 'fast path' idea that was nice 20 years
ago but no longer a real killer these days.

So some tests are duplicated, others are not correctly done.

For example, the fast path misses the more complete tests done in
tcp_ack()

Its a big mess.

Re: TCP sequence number inference attack on Linux

[Eric Dumazet]

On Fri, 2012-12-21 at 16:01 -0800, Eric Dumazet wrote:

> I began coding a serie of patches.

My goal is to make very small patches, to ease code review, and
eventually come to a state where we have more factorized code.

Re: TCP sequence number inference attack on Linux

[Zhiyun Qian]

I see. If you need any help, just let me know! E.g., I can definitely
help review the patches.

-Zhiyun

On Fri, Dec 21, 2012 at 7:04 PM, Eric Dumazet <eric.dumazet@gmail.com> wrote:
> On Fri, 2012-12-21 at 16:01 -0800, Eric Dumazet wrote:
>
>> I began coding a serie of patches.
>
> My goal is to make very small patches, to ease code review, and
> eventually come to a state where we have more factorized code.
>
>
>