Discussion:
TCP sequence number inference attack on Linux
(too old to reply)
Zhiyun Qian
2012-12-21 17:58:57 UTC
Permalink
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
Eric Dumazet
2012-12-21 18:31:03 UTC
Permalink
Post by 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.
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
(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 ?
Eric Dumazet
2012-12-21 18:52:11 UTC
Permalink
Post by Eric Dumazet
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.
Zhiyun Qian
2012-12-21 19:13:12 UTC
Permalink
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
Post by Eric Dumazet
Post by Eric Dumazet
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.
Eric Dumazet
2012-12-21 19:30:34 UTC
Permalink
Post by 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?
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>
Hannes Frederic Sowa
2012-12-22 02:13:56 UTC
Permalink
Post by 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?
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).
Zhiyun Qian
2012-12-21 19:10:49 UTC
Permalink
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
Post by Eric Dumazet
Post by 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.
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
(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 ?
Eric Dumazet
2012-12-21 19:27:32 UTC
Permalink
Post by 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.
I dont really think so.

We must discard frame is th->ack is not set. (Step 5, line 6142)
Post by Zhiyun Qian
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.
Zhiyun Qian
2012-12-21 19:49:03 UTC
Permalink
Post by Eric Dumazet
Post by 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.
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?
Post by Eric Dumazet
Post by Zhiyun Qian
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 :)
Eric Dumazet
2012-12-21 22:45:48 UTC
Permalink
Post by Zhiyun Qian
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
Zhiyun Qian
2012-12-21 23:52:22 UTC
Permalink
Post by Eric Dumazet
Post by Zhiyun Qian
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!
Post by Eric Dumazet
(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?
Post by Eric Dumazet
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
return 0;
- 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.
Eric Dumazet
2012-12-22 00:01:21 UTC
Permalink
Post by Zhiyun Qian
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.
Eric Dumazet
2012-12-22 00:04:36 UTC
Permalink
Post by Eric Dumazet
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.
Zhiyun Qian
2012-12-22 00:08:31 UTC
Permalink
I see. If you need any help, just let me know! E.g., I can definitely
help review the patches.

-Zhiyun
Post by Eric Dumazet
Post by Eric Dumazet
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.
Loading...