Subject: [tcpm] mitigating TCP ACK loop ("ACK storm") DoS attacks

From: Neal Cardwell <[email-masked]>
Date: Mon, 9 Feb 2015 21:11:46 -0500

TCP DoS scenarios involving ACK loops (aka "ACK storms" or "packet
wars") have come up previously on the TCPM list. For example, Anil
Agarwal brought them up in the Nov 2013 TCPM thread "TCP mismatched
sequence numbers issue"

I wanted to mention that our TCP team at Google has recently submitted
a patch series for Linux that mitigates such attacks by rate-limiting
the dupacks that are sent in response to out-of-window incoming
packets. The code has been in use at Google and was recently merged
into the official Linux "net-next" tree, which means that it should
land in the next official Linux release.

The patch series summary can be browsed at the following URL:

  http://git.kernel.org/cgit/linux/kernel/git/davem/net-next.git/commit/?id=f06535c599354816cfbc653ce8965804c7385c61

Below I'm including the cover letter summarizing the patch series, for
convenience/reference.

We are interested to hear any feedback folks may have.

Thanks!

neal

==============

tcp: mitigate TCP ACK loops due to out-of-window validation dupacks

This patch series mitigates "ack loop" DoS scenarios by rate-limiting
outgoing duplicate ACKs sent in response to incoming "out of window"
segments.

Background
-----------

There are several cases in which the TCP RFCs specify that a TCP
endpoint should send a pure duplicate ACK in response to a pure
duplicate ACK that appears to be invalid due to being "out of window":

(1) RFC 793 (section 3.9, page 69) specifies that endpoints should
    send a duplicate ACK in response to an ACK when the incoming
    sequence number is invalid due to being outside the receive
    window: "If an incoming segment is not acceptable, an
    acknowledgment should be sent in reply".

(2) RFC 793 (section 3.9, page 72) says: "If the ACK acknowledges
    something not yet sent (SEG.ACK > SND.NXT) then send an ACK".

(3) RFC 1323 (section 4.2.1, page 18) specifies that endpoints should
    send a duplicate ACK in response to an ACK when the PAWS check for
    the incoming timestamp value fails: "If .... SEG.TSval < TS.Recent
    and if TS.Recent is valid ... Send an acknowledgement in reply"

The problem
------------

Normally, this is not a problem. However, a buggy middlebox or
malicious man-in-the-middle can inject a few packets into the
conversation that advance each endpoint's notion of the current window
(sequence, ACK, or timestamp), without either side noticing. In this
case, from then on each side can think the other is sending invalid
segments. Thus an infinite feedback loop of duplicate ACKs can ensue,
as each endpoint receives a duplicate ACK, decides that it is invalid
(due to sequence number, ACK number, or timestamp), and then sends a
dupack in reply, which the other side decides is invalid, responding
with a dupack... ad infinitum. This ping-pong feedback loop can happen
at a very high rate.

This phenomenon can and does happen in practice. It has been seen in
datacenter and Internet contexts at Google, and has been documented by
Anil Agarwal in the Nov 2013 tcpm thread "TCP mismatched sequence
numbers issue", and Avery Fay in the Feb 2015 Linux netdev thread
"Invalid timestamp? causing tight ack loop (hundreds of thousands of
packets / sec)".

This patch series
------------------

This patch series mitigates such ack loops by rate-limiting outgoing
duplicate ACKs sent in response to incoming TCP packets that are for
an existing connection but that are invalid due to any of the reasons
mentioned above: sequence number (1), ACK field (2), or timestamp
value (3). The rate limit for such duplicate ACKs is specified by a
new sysctl, tcp_invalid_ratelimit, which specifies the minimal space
between such outbound duplicate ACKs, in milliseconds. The default is
500 (500ms), and 0 disables the mechanism.

We rate-limit these duplicate ACK responses rather than blocking them
entirely or resetting the connection, because legitimate connections
can rely on dupacks in response to some out-of-window segments. For
example, zero window probes are typically sent with a sequence number
that is below the current window, and ZWPs thus expect to thus elicit
a dupack in response.

Testing: this approach has been in use at Google for a while.

---

From: "Zimmermann, Alexander" <[email-masked]>
Date: Tue, 10 Feb 2015 08:03:26 +0000

Hi all,

I discussed this patch a bit w/ Neal yesterday. It was not clear to me
(and maybe shame on me) that exist cases in which TCP sends an (DUP)ACK
in response to a pure ACK. Parts of this „problem“ belongs to RFC793
(see background below). It’s maybe a good opportunity to include some
text about this in RFC793bis.

BTW: Do we think as WG that 793bis is a good thing to do? And if the
answer is yes, why do we not start an adoption call?

Alex

> Am 10.02.2015 um 03:11 schrieb Neal Cardwell <[email-masked]>:
> 
> tcpm mailing list
> [email-masked]
> https://www.ietf.org/mailman/listinfo/tcpm

---

From: Wesley Eddy <[email-masked]>
Date: Tue, 10 Feb 2015 20:19:39 -0500

> text about this in RFC793bis.

I would be tempted to say "yes", however, to keep from opening the door
to all kinds of changes and making RFC793bis intractable to get
consensus on, I had proposed to only make changes that are already in
other RFCs updating 793 or in verified errata.

So, maybe someone should submit an errata on this? :)

> answer is yes, why do we not start an adoption call?

Sounds good to me :).

-- 
Wes Eddy
MTI Systems

---

From: Jeremy Harris <[email-masked]>
Date: Wed, 11 Feb 2015 10:39:39 +0000

> 500 (500ms), and 0 disables the mechanism.

Would it not scale better over different link speeds to use a
packet-counting approach rather than a rate limit?   For example,
output a dupACK only for alternate triggers.
-- 
Cheers,
  Jeremy

---

From: Neal Cardwell <[email-masked]>
Date: Wed, 11 Feb 2015 08:20:52 -0500

> output a dupACK only for alternate triggers.

In our case the most common problem was with a middlebox that was not
only (a) desynchronizing the endpoints' notions of the window, but
also (b) duplicating packets to a high degree. So sending a dupack
once per 2 or even once per 32 packets was not enough to break the
loop. If we had responded to one in every 64 incoming out-of-window
packets, that probably would have broken the DoS loop.

However, if we respond to only one in every 64 incoming out-of-window
packets then responses to legitimate traffic become too infrequent.
For example, if the out-of-window packets are zero window probes that
the remote endpoint is sending in an exponentially-backed-off fashion
(very common), then I'd imagine that responding to only 1 in 64
exponentially-backed-off window-probe packets means that the remote
endpoint is often going to give up and close the connection before
they ever get an ACK with a non-zero window.

As for different link speeds, two ACKs per second means we bound
outgoing dupacks to 1Kbit/sec, which is tolerable for most Internet
hosts. If we were to use a packet-counting approach, then with a
middlebox multiplying incoming packets there is no bound on the
outgoing bit rate of our dupacks, and we are more likely to overload
the remote host's link.

neal

---

From: Mirja Kühlewind <[email-masked]>
Date: Tue, 17 Feb 2015 14:47:28 +0100

Hi all,

I probably have a stupid question, but I'll ask anyway as rate-limiting the ACK 
seems to help the problem but also seems to be kind of a hack and might not 
resolvie the actually cause of the problem.

The question is, why does RFC 793 (section 3.9, page 72) say: "If the ACK 
acknowledges something not yet sent (SEG.ACK > SND.NXT) then send an ACK"?

In this situation the two end points seem to be out of syn, so you have two options:
1) reset the connection and start over.
2) try to resyn which probably means you discard/invalidate (?) the data that 
have been wrongly acknowledged...

What do I miss?

Mirja

On 10.02.2015 03:11, Neal Cardwell wrote:
> _______________________________________________
> tcpm mailing list
> [email-masked]

-- 
------------------------------------------
Dipl.-Ing. Mirja Kühlewind
Communication Systems Group
Institute TIK, ETH Zürich
Gloriastrasse 35, 8092 Zürich, Switzerland

Room ETZ G93
phone: +41 44 63 26932
email: [email-masked]
------------------------------------------

---

From: "Scharf, Michael (Michael)" <[email-masked]>
Date: Tue, 17 Feb 2015 14:17:33 +0000

> So, maybe someone should submit an errata on this? :)

Indeed, this issue should be recorded. Yet, regarding a solution, I wonder if an errata would indeed be sufficient. If the event processing in RFC 793 has to be modified, it seems to modify TCP on-the-wire in this specific corner case.

Does somebody know what stacks other than Linux do in this case? 

Michael (as individual)

---

From: Eric Dumazet <[email-masked]>
Date: Tue, 17 Feb 2015 07:23:16 -0800

Hi Mirja

I believe RFC 5961 might give appropriate answers to your question ?

In general, we try to be conservative and gentle in our responses to
apparently 'bad incoming' packets.
Resetting a connection should only happen if we are certain the
incoming packet is totally legitimate,
not some leftover or malicious packet.

But in some cases, being gentle can generate pathological ack storms.

On Tue, Feb 17, 2015 at 5:47 AM, Mirja Kühlewind
<[email-masked]> wrote:
> Hi all,
>
> I probably have a stupid question, but I'll ask anyway as rate-limiting the
> ACK seems to help the problem but also seems to be kind of a hack and might
> not resolvie the actually cause of the problem.
>
> 2) try to resyn which probably means you discard/invalidate (?) the data
> that have been wrongly acknowledged...
>
> What do I miss?
>
> Mirja
>
>
>
>