Subject: [quicwg/base-drafts] Path Challenge Padding and Amplification Protection (#4257)

From: Nick Banks <[email-masked]>
Date: Wed, 21 Oct 2020 09:24:43 -0700

I've implemented the new requirements to pad path challenges in MsQuic and I immediately startled hitting asserts in my code during automated testing because the server ended up trying to pad beyond the 3x amplification limit for the new path.

What am I supposed to do here? Pad only up to the 3x limit? Wait until I have received enough on the path to be able to send a fully padded packet? Don't pad, but then track some state to additionally do PMTUD sometime later, after I've validated the source address?

I might have missed it, but I think this scenario needs explicit text in the spec.

-- 
You are receiving this because you are subscribed to this thread.
Reply to this email directly or view it on GitHub:
https://github.com/quicwg/base-drafts/issues/4257

---

From: Martin Thomson <[email-masked]>
Date: Wed, 21 Oct 2020 13:26:42 -0700

Can you walk through the scenario?  The server observes a NAT rebinding or migration and decides that the new client address is not validated.  It sends PATH_CHALLENGE and pads, but the packets it has received thus far are too small and therefore it immediately exceeds the 3x limit?

This seems like it might be worth fixing.  Like you, I don't have an easy answer.  If the client probes the path, there is no issue.  However, a small non-probing packet can happen and we need an answer for the server in that case.

Curiously, you could send PATH_CHALLENGE in a small packet too, but not regard any response as path validation.  The client should send PATH_RESPONSE padded and open up the server sending quota, allowing the server to properly probe.

-- 
You are receiving this because you are subscribed to this thread.
Reply to this email directly or view it on GitHub:
https://github.com/quicwg/base-drafts/issues/4257#issuecomment-713857504

---

From: Nick Banks <[email-masked]>
Date: Wed, 21 Oct 2020 13:30:32 -0700

The simplest scenario is NAT rebinding, and the first packet received on the path is small. Per-spec, we're still supposed to send a path challenge, and per my understanding, we're always supposed to pad those.

One option, at least for this scenario would be to make an exception, with the assumption that rebinding shouldn't change the MTU. But I don't care for assumptions that could really bite you if you get it wrong. Additionally, it doesn't fix the bigger problem if it wasn't NAT rebinding.

-- 
You are receiving this because you are subscribed to this thread.
Reply to this email directly or view it on GitHub:
https://github.com/quicwg/base-drafts/issues/4257#issuecomment-713859637

---

From: ianswett <[email-masked]>
Date: Wed, 21 Oct 2020 14:35:28 -0700

To repeat what @martinthomson has said before, every time we change something, we introduce some issue.

If a connection is immediately migrating prior to probing the new path with PATH_CHALLENGE, I believe it either means it's unintentional or the new path is the only one available.  In either case, if the MTU is too small, you're sunk, so making an exception to padding for cases of immediate migration seems ok to me.  The only cost is it may take a bit longer to realize the new path has a smaller MTU?

-- 
You are receiving this because you are subscribed to this thread.
Reply to this email directly or view it on GitHub:
https://github.com/quicwg/base-drafts/issues/4257#issuecomment-713890927

---

From: Kazuho Oku <[email-masked]>
Date: Wed, 21 Oct 2020 16:30:29 -0700

I might be dumb, but do we require amplification limit being applied to path challenges?

I am not sure if there's such a requirement. I do not think we have to have that.

Unlike a DDoS attack using Initial packets, an off-path attacker cannot mount a DDoS attack using spoofed packets; only an MOTS attacker can do that. I would also point out that because the server has state, it will rate-limit (or bail out from) the number of path challenges it sends.

-- 
You are receiving this because you are subscribed to this thread.
Reply to this email directly or view it on GitHub:
https://github.com/quicwg/base-drafts/issues/4257#issuecomment-713978156

---

From: Tatsuhiro Tsujikawa <[email-masked]>
Date: Thu, 22 Oct 2020 01:35:47 -0700

If I understand the spec correctly, server enforces amplification protection before it receives first client Handshake packet.
So the intended scenario is that server sends PATH_CHALLENGE in its 0.5 RTT flight.  But do we need to send them?  Because receiving client Handshake validates client address, server does not need to send PATH_CHALLENGE during handshake.

-- 
You are receiving this because you are subscribed to this thread.
Reply to this email directly or view it on GitHub:
https://github.com/quicwg/base-drafts/issues/4257#issuecomment-714329468

---

From: Nick Banks <[email-masked]>
Date: Thu, 22 Oct 2020 08:32:26 -0700

I went back and looked at the specs, @kazuho you're right that we don't seems to require amplification protection in the spec explicitly for migration, but is that really correct? I figured it was an amplification attack vector just like the handshake (though a bit less impactful since you have to handshake first). Couldn't you connect to a server that has a larger initial window and then send a request for a large response, spoofing the target IP address? Rinse and repeat?

If we really don't need to have amplification protection for migration, then I'm fine to close this issue (and go remove some code).

-- 
You are receiving this because you are subscribed to this thread.
Reply to this email directly or view it on GitHub:
https://github.com/quicwg/base-drafts/issues/4257#issuecomment-714575859

---

From: Martin Thomson <[email-masked]>
Date: Thu, 22 Oct 2020 14:28:36 -0700

Hmm, @kazuho is right, I can't find any restriction on use of paths after migration.  Our limits for anti-amplification are specifically: handshake, closing, and stateless reset.  No other mention exists.

That doesn't mean that Nick is wrong to have this code though. Without limits, an attacker could connect to a server then spoof a bunch of small packets to cause an amplification attack toward a chosen target.  

We can turn that into a low-grade amplification attack if we allow probes to be exempt from that limit.  It's low-grade then for several reasons.  It is stateful at the server and the connection establishment is expensive.  A single connection can be used to attack multiple targets, but a server won't send many packets to each.  In my half-written migration code, this results in just three packets, which isn't that useful.

After digging in more here, I think that we can make two changes, one the direct response to this issue, but the first is in response to the unstated issue that we don't have anti-amplification protection for migration.

1. Add the 3x rule for any unvalidated path.

2. Allow path probes to ignore the 3x rule.

The alternative is to leave this alone and focus on clarification.  We have a requirement that the server reduce its congestion window, so the concrete amount of amplification that can be gained without the 3x rule being in place is not that much relative to the cost of setting up the attack.

I'm ambivalent on this.  I can see the appeal of the principled fix, but getting it right could be tricky.

-- 
You are receiving this because you are subscribed to this thread.
Reply to this email directly or view it on GitHub:
https://github.com/quicwg/base-drafts/issues/4257#issuecomment-714772404

---

From: ianswett <[email-masked]>
Date: Thu, 22 Oct 2020 14:50:27 -0700

I think leaving this alone and focus on clarification SGTM.

Amplification limits are tricky, as evidenced by the repeated tweaks we've needed to enforce the 3x limit during the handshake, so adding one at this stage sounds risky.

Given there is some 'protection' by requiring the handshake to complete prior to migration, I think this protection is sufficient as long as one can't repeatedly abuse migration by immediately migrating over and over.  I'm not sure if the existing text provides enough protection or not from that situation or not?

-- 
You are receiving this because you are subscribed to this thread.
Reply to this email directly or view it on GitHub:
https://github.com/quicwg/base-drafts/issues/4257#issuecomment-714782326

---

From: Kazuho Oku <[email-masked]>
Date: Thu, 22 Oct 2020 16:48:16 -0700

I think that there is an existing MUST regarding this problem. It states that _until a peer's address is deemed valid, an endpoint MUST limit the rate at which it sends data to this address. The endpoint MUST NOT send more than a minimum congestion window's worth of data per estimated round-trip time (kMinimumWindow) ([section 9.3.1; transport draft](https://quicwg.org/base-drafts/draft-ietf-quic-transport.html#section-9.3.1-2))._

So to answer to @nibanks, current limit is not INITCWND, but 2 MTU.

I think that this limit might be a bit on the loose side, but I wonder if there is a need to change.

-- 
You are receiving this because you are subscribed to this thread.
Reply to this email directly or view it on GitHub:
https://github.com/quicwg/base-drafts/issues/4257#issuecomment-714822179

---

From: Martin Thomson <[email-masked]>
Date: Thu, 22 Oct 2020 17:17:55 -0700

Thanks for finding that kMinimumWindow thing @kazuho, that makes me much happier.  Relative to the cost of mounting the attack, I don't expect an attacker to find that attractive.

-- 
You are receiving this because you are subscribed to this thread.
Reply to this email directly or view it on GitHub:
https://github.com/quicwg/base-drafts/issues/4257#issuecomment-714831627

---

From: Nick Banks <[email-masked]>
Date: Sun, 25 Oct 2020 12:26:00 -0700

Ok, so were saying that instead of the 3x limit, we're going to use 2 MTU per Initial RTT (path challenges aren't retransmitted on loss, right?)? I'm just trying to reason about how I should update my logic. It used to be:
```c
void OnPathDataReceived(path, length) {
  if (!path->Valid) {
    path->allowance += 3 * length;
    TrySendPathChallenge(path)
  }
}
```
Now, it should be something like this?
```c
void OnPathDataReceived(path, length) {
  if (!path->Valid) {
    if (!path->HasSentChallenge || path->TimeSinceLastChallengeReset() > INIT_RTT) {
      path->allowance += 2 * MTU;
      path->lastChallengeReset = now()
    }
    TrySendPathChallenge(path)
  }
}
```
And, just so my understanding is clear, if I receive a minimum size packet (10ish byte UDP payload?) from an unvalidated path on average 1/2 x INIT_RTT, then I will be amplifying that traffic by ~100x, right?

And a man-on-the-side attacker could just take every small packet destined to my server that it sees, and race a copy, with changed source address to some target address, and I'd start doing this amplification for all those connections' packets?

-- 
You are receiving this because you are subscribed to this thread.
Reply to this email directly or view it on GitHub:
https://github.com/quicwg/base-drafts/issues/4257#issuecomment-716198478

---

From: Kazuho Oku <[email-masked]>
Date: Sun, 25 Oct 2020 16:28:38 -0700

> And, just so my understanding is clear, if I receive a minimum size packet (10ish byte UDP payload?) from an unvalidated path on average 1/2 x INIT_RTT, then I will be amplifying that traffic by ~1…

For one unvalidated path, an endpoint would send no more than 2 MTU worth of data per every Initial RTT (333ms). Therefore, while the amplification factor will be large, the amount of traffic being sent is going to be small.

For all the unvalidated paths from which an endpoint might receive data, the upper bound would be 2 MTU multiplied by the number of paths that an endpoint can validate concurrently. From what I understand, each path validation attempt is abandoned by a timeout, that is greater than 2 seconds ([section 8.2.4](https://quicwg.org/base-drafts/draft-ietf-quic-transport.html#section-8.2.4-2)).

-- 
You are receiving this because you are subscribed to this thread.
Reply to this email directly or view it on GitHub:
https://github.com/quicwg/base-drafts/issues/4257#issuecomment-716230658

---

From: Nick Banks <[email-masked]>
Date: Sun, 25 Oct 2020 17:03:47 -0700

Ok. I did some excel math to get a more accurate number, and it seems at least for IPv4, the amplification ratio is closer to 25x. To make use of this though, as you indicated Kazuho, the attacker would be limited by the 2 MTU, per unvalidated path.

Assuming a server tracks only 4 paths max, per connection, and an attacker opens 1000 connections to the server and uses them as an amplification vector, the attacker can send packets at less than 10Mbps to get almost 250 Mbps send to the target. Do this with a couple different servers (which ever you find to track the most parallel paths) and I'd say you have a pretty good attack vehicle.

And as I mentioned above, a MoTS can copy/modify/race valid connection traffic to achieve similar results.

Obviously getting a connection to the handshake confirmed state before it can be used as an amplification vector is a hurdle, but I wouldn't say it a very large one. The attacker can open connection to **many** different servers to mask it's attack origin somewhat. IMO this still seem like a very valid threat we at the very least should mention in the spec, if not actually fix.

-- 
You are receiving this because you are subscribed to this thread.
Reply to this email directly or view it on GitHub:
https://github.com/quicwg/base-drafts/issues/4257#issuecomment-716235518

---

From: Martin Thomson <[email-masked]>
Date: Sun, 25 Oct 2020 21:30:55 -0700

I think that I'd like to see the working for that, because I have a larger number, depending on how many probes are involved (at 3 probes per path, the number is 160-ish for a server that uses one byte connection IDs, or 42 for a more reasonable 8 byte CID), at last for those few paths that a server might choose to validate.  

That is, if you take the handshake cost out, which is fair if you consider them amortized, but a server will only probe so many paths.

If you take the handshake into account and leave aside the possibility that you can amortize the handshake costs across attacks on different servers, then you get a lower value.

-- 
You are receiving this because you are subscribed to this thread.
Reply to this email directly or view it on GitHub:
https://github.com/quicwg/base-drafts/issues/4257#issuecomment-716296660

---

From: Nick Banks <[email-masked]>
Date: Mon, 26 Oct 2020 08:42:21 -0700

My math:

- Assuming outgoing packets are 1 to 1 with incoming, that gives us a limit of 6 packets per second, per path
- Estimated the incoming UDP payload size to be 20 bytes
- The outgoing UDP payload size will be 1200 bytes

`Incoming Rate = (IPv4_Header_Size + UDP_Header_Size + 20) * 6 PKTS/SEC * PATHS_PER_CONN * CONNS`
`Outgoing Rate = (IPv4_Header_Size + UDP_Header_Size + 1200) * 6 PKTS/SEC * PATHS_PER_CONN * CONNS`

The amplification ratio is `(IPv4_Header_Size + UDP_Header_Size + 1200) /  (IPv4_Header_Size + UDP_Header_Size + 20)`, which is `1228 / 48 = 25.58333`. For incoming size of 28 bytes (8 byte CID) the number comes down to `21.93`.

-- 
You are receiving this because you are subscribed to this thread.
Reply to this email directly or view it on GitHub:
https://github.com/quicwg/base-drafts/issues/4257#issuecomment-716633217

---

From: Martin Thomson <[email-masked]>
Date: Mon, 26 Oct 2020 22:53:45 -0700

OK, that helps.  I didn't factor in packet headers in my calculations, but I also allow for multiple probes in response to a single non-probing packet.

What I'm concerned about then is considering the cost of the handshake.  To complete the handshake, you need to send one 1200 byte packet and one packet of about 78 bytes.  For an attack on a single host, this changes the dynamic considerably: you send `1220 + (98 + CID) + (41 + CID)` to get `3*1220`, assuming that you send three probes on new paths.  That's lower than our 3x target even if the connection ID is zero length (2.66).

Even if you amortize that setup cost across multiple targets, the amplification factor isn't as bad as I first thought. If a server probes up to 10 paths (which seems high), then you get `3*1200 / ((1318 + CID) / n + 41 + CID)` which for a CID of 8 bytes and 10 paths is 19.8.  That's much worse, but not so bad as it is spread over multiple paths.

We might limit the number of concurrent path validations, but this is not really going to change anything if they are just strung out.  Only the total amount matters if the attacker is even slightly patient.

I think that there might be some clarifications we can add:

1. Point more clearly to the requirement to limit the sending rate on unvalidated paths after migration.

2. Note that this rate limit applies to each path and that it might be necessary to limit the number of paths that are concurrently validated in this way, either per connection or across all connections (perhaps per destination if you are able).

3. Note that multiple path validations in sequence can still be used to use a single connection to attack multiple targets and that it might be necessary to limit the number of total failed path validations.

On this last point, the total exposure is fixed in total to the number of probes in each failed validation attempt (e.g., 3) times the number of failed validations that the endpoint permits (e.g., 10).  Using 3 and 10 gives the ~20x figure above, which is pretty bad, but not so far out of proportion that it couldn't be managed.  Keep in mind that the attacker needs to do all the crypto of a handshake in order to access that, plus all the protocol logic and timers over two round trips.  All that to get that 20x factor.

-- 
You are receiving this because you are subscribed to this thread.
Reply to this email directly or view it on GitHub:
https://github.com/quicwg/base-drafts/issues/4257#issuecomment-717001767

---

From: Kazuho Oku <[email-masked]>
Date: Mon, 26 Oct 2020 23:17:50 -0700

Thank you for the calculations. Something around ~20x is what I have expected too.

I tend to agree that having some cautionary text is sufficient.

I'd also point out that we have a sentence that states: _In response to an apparent migration, endpoints MUST validate the previously active path using a PATH_CHALLENGE frame._ ([section 9.3.3](https://quicwg.org/base-drafts/draft-ietf-quic-transport.html#section-9.3.3-4)). Therefore, in addition to sending bytes to the victim, servers used for the reflection attack will be sending about 1/2 of that to the initiator of the attack. I'm not sure how critical that is to the attacker, though.

-- 
You are receiving this because you are subscribed to this thread.
Reply to this email directly or view it on GitHub:
https://github.com/quicwg/base-drafts/issues/4257#issuecomment-717011871