TCP/IP stack interpretation of acceptable packet

TCP/IP stack interpretation of acceptable packet

[Oliver Zheng]

I was investigating behaviour of the TCP/IP stacks and noticed that
Linux has a peculiarity. When a packet is received with the correct
sequence number but incorrect acknowledgement number (in my tests, it
was higher than the correct acknowledgement number), the stack accepts
the packet as a valid packet and passes the data up to the application
(I do not know whether the ack information is accepted). According to
the list of tests described here in the TCP RFC 793 [1], accepting a
packet requires the packet to satisfy both sequence and
acknowledgement number tests; otherwise, the entirety of the packet
(its data and its acknowledgement information confirming reception of
previous data) should be dropped. Is this intentional, a bug, or am I
misinterpreting something? A nice flow chart that explains this
procedure is here [2].

Not to instigate flame, but Windows does this correctly, or at least
correctly in my interpretation of the spec.

[1] http://tools.ietf.org/html/rfc793#page-69
[2] http://www.medianet.kent.edu/techreports/TR2005-07-22-tcp-EFSM.pdf (page 17)

Cheers,
Oliver

Re: TCP/IP stack interpretation of acceptable packet

[Andi Kleen]

Oliver Zheng <mailinglists+netdev@oliverzheng.com> writes:

> I was investigating behaviour of the TCP/IP stacks and noticed that
> Linux has a peculiarity. When a packet is received with the correct
> sequence number but incorrect acknowledgement number (in my tests, it
> was higher than the correct acknowledgement number), the stack accepts
> the packet as a valid packet and passes the data up to the application
> (I do not know whether the ack information is accepted). According to
> the list of tests described here in the TCP RFC 793 [1], accepting a
> packet requires the packet to satisfy both sequence and
> acknowledgement number tests; otherwise, the entirety of the packet
> (its data and its acknowledgement information confirming reception of
> previous data) should be dropped. Is this intentional, a bug, or am I
> misinterpreting something? A nice flow chart that explains this
> procedure is here [2].

Sounds like a bug to me, when the ack is outside the window.

-Andi
-- 
ak@linux.intel.com -- Speaking for myself only.

[PATCH net-next-2.6] Re: TCP/IP stack interpretation of acceptable packet

[John Dykstra]

On Tue, 2009-02-24 at 14:59 -0800, Oliver Zheng wrote:
> When a packet is received with the correct
> sequence number but incorrect acknowledgement number (in my tests, it
> was higher than the correct acknowledgement number), the stack accepts
> the packet as a valid packet and passes the data up to the application

TCP's fast path currently accepts segments who ack data that was never
sent.  The slow path and processing for states other than ESTABLISHED
discard such segments.

RFC793 says (Section 3.9) that not only should such segments be
discarded, but that an ACK should be sent to the peer.  I can't see what
that accomplishes, and it seems to badly interact with fast
retransmit--under some conditions with crafted packets you can get the
two stacks ACKing each other forever.  So I left that out of this patch:


[PATCH net-next-2.6] tcp: Discard segments that ack data not yet sent

Discard incoming packets whose ack field iincludes data not yet sent.
This is consistent with RFC 793 Section 3.9.

Change tcp_ack() to distinguish between too-small and too-large ack
field values.  Keep segments with too-large ack fields out of the fast
path, and change slow path to discard them.

Reported-by:  Oliver Zheng <mailinglists+netdev@oliverzheng.com>
Signed-off-by: John Dykstra <john.dykstra1@gmail.com>
---
 net/ipv4/tcp_input.c |   31 +++++++++++++++++++------------
 1 files changed, 19 insertions(+), 12 deletions(-)

diff --git a/net/ipv4/tcp_input.c b/net/ipv4/tcp_input.c
index fae78e3..01544cd 100644
--- a/net/ipv4/tcp_input.c
+++ b/net/ipv4/tcp_input.c
@@ -3587,16 +3587,19 @@ static int tcp_ack(struct sock *sk, struct sk_buff *skb, int flag)
 	u32 prior_fackets;
 	int prior_packets;
 	int frto_cwnd = 0;
-
-	/* If the ack is newer than sent or older than previous acks
+
+	/* If the ack is older than previous acks
 	 * then we can probably ignore it.
 	 */
-	if (after(ack, tp->snd_nxt))
-		goto uninteresting_ack;
-
 	if (before(ack, prior_snd_una))
 		goto old_ack;
 
+	/* If the ack includes data we haven't sent yet, discard
+	 * this segment (RFC793 Section 3.9).
+	 */
+	if (after(ack, tp->snd_nxt))
+		goto invalid_ack;
+
 	if (after(ack, prior_snd_una))
 		flag |= FLAG_SND_UNA_ADVANCED;
 
@@ -3686,6 +3689,10 @@ no_queue:
 		tcp_ack_probe(sk);
 	return 1;
 
+invalid_ack:
+	SOCK_DEBUG(sk, "Ack %u after %u:%u\n", ack, tp->snd_una, tp->snd_nxt);
+	return -1;
+
 old_ack:
 	if (TCP_SKB_CB(skb)->sacked) {
 		tcp_sacktag_write_queue(sk, skb, prior_snd_una);
@@ -3693,9 +3700,8 @@ old_ack:
 			tcp_try_keep_open(sk);
 	}
 
-uninteresting_ack:
-	SOCK_DEBUG(sk, "Ack %u out of %u:%u\n", ack, tp->snd_una, tp->snd_nxt);
-	return 0;
+	SOCK_DEBUG(sk, "Ack %u before %u:%u\n", ack, tp->snd_una, tp->snd_nxt);
+	return 0;
 }
 
 /* Look for tcp options. Normally only called on SYN and SYNACK packets.
@@ -5158,7 +5164,8 @@ int tcp_rcv_established(struct sock *sk, struct sk_buff *skb,
 	 */
 
 	if ((tcp_flag_word(th) & TCP_HP_BITS) == tp->pred_flags &&
-	    TCP_SKB_CB(skb)->seq == tp->rcv_nxt) {
+	    TCP_SKB_CB(skb)->seq == tp->rcv_nxt &&
+	    !after(TCP_SKB_CB(skb)->ack_seq, tp->snd_nxt)) {
 		int tcp_header_len = tp->tcp_header_len;
 
 		/* Timestamp header prediction: tcp_header_len
@@ -5311,8 +5318,8 @@ slow_path:
 		return -res;
 
 step5:
-	if (th->ack)
-		tcp_ack(sk, skb, FLAG_SLOWPATH);
+	if (th->ack && tcp_ack(sk, skb, FLAG_SLOWPATH) < 0)
+		goto discard;
 
 	tcp_rcv_rtt_measure_ts(sk, skb);
 
@@ -5649,7 +5656,7 @@ int tcp_rcv_state_process(struct sock *sk, struct sk_buff *skb,
 
 	/* step 5: check the ACK field */
 	if (th->ack) {
-		int acceptable = tcp_ack(sk, skb, FLAG_SLOWPATH);
+		int acceptable = tcp_ack(sk, skb, FLAG_SLOWPATH) > 0;
 
 		switch (sk->sk_state) {
 		case TCP_SYN_RECV:
-- 
1.5.4.3

Re: [PATCH net-next-2.6] Re: TCP/IP stack interpretation of acceptable packet

[Oliver Zheng]

On Thu, Mar 19, 2009 at 12:44:53AM +0000, John Dykstra wrote:
> RFC793 says (Section 3.9) that not only should such segments be
> discarded, but that an ACK should be sent to the peer.  I can't see what
> that accomplishes, and it seems to badly interact with fast
> retransmit--under some conditions with crafted packets you can get the
> two stacks ACKing each other forever.  So I left that out of this patch:

I think part of the original intentions for the response ack is to
generate the "ack storm". In certain cases of tcp hijacking where the
attacker is trying to resynchronize a tcp session after injecting a
packet into the stream, an ack storm raises alerts in intrusion
detection systems. Most of the times, built-in measures reset the tcp
session given an unusual large number of acks (I'm not sure how or if
Linux does this).

This was partially the original reason I was looking into this. I
noticed that Windows does not send an ack back if the received ack has
a higher than expected ack number *and* higher than expected sequence
number. For some well crafted tcp hijacking cases, this increases the
attack success rate substantially.

It's beyond my knowledge of other implications such a response ack would
cause.

Cheers,
Oliver

Re: [PATCH net-next-2.6] Re: TCP/IP stack interpretation of acceptable packet

[David Miller]

From: John Dykstra <john.dykstra1@gmail.com>
Date: Thu, 19 Mar 2009 00:44:53 +0000

> [PATCH net-next-2.6] tcp: Discard segments that ack data not yet sent
> 
> Discard incoming packets whose ack field iincludes data not yet sent.
> This is consistent with RFC 793 Section 3.9.
> 
> Change tcp_ack() to distinguish between too-small and too-large ack
> field values.  Keep segments with too-large ack fields out of the fast
> path, and change slow path to discard them.
> 
> Reported-by:  Oliver Zheng <mailinglists+netdev@oliverzheng.com>
> Signed-off-by: John Dykstra <john.dykstra1@gmail.com>

I've been mulling over this patch for more than a week :-)

Let's put this into net-next-2.6 and let it cook there for
a while.  It is possible I'll backport this into -stable
after some time.

Thanks!

Re: [PATCH net-next-2.6] Re: TCP/IP stack interpretation of acceptable packet

[Andi Kleen]

> I've been mulling over this patch for more than a week :-)
> 
> Let's put this into net-next-2.6 and let it cook there for
> a while.  It is possible I'll backport this into -stable
> after some time.

One thing that might be useful for the testing period would 
be explicit printk when such a new discard happens? Otherwise
it would be difficult to find out if something really goes wrong.

-Andi

-- 
ak@linux.intel.com -- Speaking for myself only.

Re: [PATCH net-next-2.6] Re: TCP/IP stack interpretation of acceptable packet

[John Dykstra]

On Sun, 2009-03-22 at 21:50 -0700, David Miller wrote:
> I've been mulling over this patch for more than a week :-)

FWIW, FreeBSD 6.1 discards segments with these over-eager acknowledgment
fields.  It also sends back the pure ACK that I chose not to add.  

I didn't look at any other OS's.

On Mon, 2009-03-23 at 13:28 +0100, Andi Kleen wrote:
> One thing that might be useful for the testing period would 
> be explicit printk when such a new discard happens? 

[PATCH net-next-2.6]  tcp: Log discarded segments with too-high ack fields

Log a rate-limited message when a TCP segment is discarded because
its ack field is beyond the last data sent.  This logging was suggested
by Andi Kleen.

Signed-off-by: John Dykstra <john.dykstra1@gmail.com>
---
 net/ipv4/tcp_input.c |    4 +++-
 1 files changed, 3 insertions(+), 1 deletions(-)

diff --git a/net/ipv4/tcp_input.c b/net/ipv4/tcp_input.c
index 01544cd..37343e4 100644
--- a/net/ipv4/tcp_input.c
+++ b/net/ipv4/tcp_input.c
@@ -3690,7 +3690,9 @@ no_queue:
 	return 1;
 
 invalid_ack:
-	SOCK_DEBUG(sk, "Ack %u after %u:%u\n", ack, tp->snd_una, tp->snd_nxt);
+	if (printk_ratelimit())
+		printk(KERN_NOTICE "Ack %u after %u:%u;  segment discarded\n",
+		    ack, tp->snd_una, tp->snd_nxt);
 	return -1;
 	
 old_ack:
-- 
1.5.4.3

Re: [PATCH net-next-2.6] Re: TCP/IP stack interpretation of acceptable packet

[David Miller]

From: Andi Kleen <andi@firstfloor.org>
Date: Mon, 23 Mar 2009 13:28:06 +0100

> > I've been mulling over this patch for more than a week :-)
> > 
> > Let's put this into net-next-2.6 and let it cook there for
> > a while.  It is possible I'll backport this into -stable
> > after some time.
> 
> One thing that might be useful for the testing period would 
> be explicit printk when such a new discard happens? Otherwise
> it would be difficult to find out if something really goes wrong.

No, thanks.