Subject: [quicwg/base-drafts] Required state for retaining unacked RETIRE_CONNECTION_ID frames is unbound (#3509)

From: Kazuho Oku <[email-masked]>
Date: Tue, 10 Mar 2020 16:14:29 -0700

When an endpoint sends a RETIRE_CONNECTION_ID frame carrying a connection ID that has been active until that point, that endpoint is expected to open room for accepting a new connection ID.

That means that if the peer does not acknowledge the packets that contains RETIRE_CONNECTION_ID frame, but keeps on sending NEW_CONNECTION_ID frames with increasing values in the Retire Prior To field, the number of unacknowledged RETIRE_CONNECTION_ID frames (or to be precise, the number of unacked retiring connection IDs) keeps on increasing.

-- 
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/3509

---

From: Kazuho Oku <[email-masked]>
Date: Tue, 10 Mar 2020 16:18:16 -0700

To address the issue, I think we need to do one of the following:
* State that the attack exists, and that QUIC stacks should implement mitigations.
* Introduce MAX_CONNECTION_IDS frame. The reason we do not have similar issue in stream concurrency control is because the credit is controlled by MAX_STREAMS frames, rather than using FIN (or reset) as an implicit signal to indicate availability of new credit. We could do the same for connection IDs.

-- 
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/3509#issuecomment-597366048

---

From: Martin Thomson <[email-masked]>
Date: Tue, 10 Mar 2020 20:28:48 -0700

Mathematically, this might be unbounded, but it's more likely that in practice the limit is `2*active_connection_id_limit` as it would be unlikely that unacknowledged RETIRE_CONNECTION_ID frames would remain so once more NEW_CONNECTION_ID frames start arriving.  More so as the issuer of those NEW_CONNECTION_ID frames has to have received the RETIRE_CONNECTION_ID frames.

Adding new frames for this seems a little unwieldy, so I'd prefer to just acknowledge that the problem exists.

Note also that Retire Prior To has the effect of making this limit squishy in other ways.

(This is a design issue.)

-- 
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/3509#issuecomment-597425775

---

From: Marten Seemann <[email-masked]>
Date: Tue, 10 Mar 2020 20:50:00 -0700

I'm not sure I understand the attack here. Why would an implementation need to keep track of acknowledgements of RETIRE_CONNECTION_ID frames (other than for purposes of loss recovery, but then this applies to *any* retransmittable frame type)?

An endpoint sends a RETIRE_CONNECTION_ID frame when it decides to not use the respective CID any longer. At this point, it can forget about the connection ID altogether. It might make sense to hold on to the stateless reset token for a while (3 PTO?) longer, in order to be able to detect stateless resets, but this is an optimization and wouldn't lead to unbounded state anyway.

-- 
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/3509#issuecomment-597430322

---

From: Kazuho Oku <[email-masked]>
Date: Tue, 10 Mar 2020 20:50:54 -0700

@martinthomson 
> Mathematically, this might be unbounded, but it's more likely that in practice the limit is `2*active_connection_id_limit` as it would be unlikely that unacknowledged RETIRE_CONNECTION_ID frames wo…

I think `2*active_connection_id_limit` is fine, assuming that the endpoint would just stop retransmitting oldest RETIRE_CONNECTION_ID frames. That limit would be too stern to be used for detecting potential attacks (and therefore closing the connection with CONNECTION_VIOLATION).

-- 
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/3509#issuecomment-597430545

---

From: Kazuho Oku <[email-masked]>
Date: Tue, 10 Mar 2020 20:53:55 -0700

@marten-seemann 
> I'm not sure I understand the attack here. Why would an implementation need to keep track of acknowledgements of RETIRE_CONNECTION_ID frames (other than for purposes of loss recovery, but then this applies to _any_ retransmittable frame type)?

This is about keeping state for retransmission for recovering loss. As stated in [my first comment](https://github.com/quicwg/base-drafts/issues/3509#issuecomment-597366048), the issue is unique to RETIRE_CONNECTION_ID frames, because it is (ab)used for providing the peer additional credit, compared to other flow control that uses a dedicated frame (e.g., MAX_*) for communicating credit.

-- 
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/3509#issuecomment-597431194

---

From: Marten Seemann <[email-masked]>
Date: Tue, 10 Mar 2020 21:46:09 -0700

Thank you for the explanation, @kazuho. I think I now understood the problem.

> Mathematically, this might be unbounded, but it's more likely that in practice the limit is 2*active_connection_id_limit as it would be unlikely that unacknowledged RETIRE_CONNECTION_ID frames would remain so once more NEW_CONNECTION_ID frames start arriving. More so as the issuer of those NEW_CONNECTION_ID frames has to have received the RETIRE_CONNECTION_ID frames.

This would require endpoints to make assumptions about how the peer handles the `active_connection_id_limit` and how it issues new CIDs. This can get complicated really quickly and leave the connection in an unrecoverable state (or at the least a state with less CIDs than it should have). Introducing a new frame, as @kazuho suggested, seems a lot cleaner to me.

-- 
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/3509#issuecomment-597441915

---

From: Kazuho Oku <[email-masked]>
Date: Wed, 11 Mar 2020 19:09:34 -0700

Just to be clear, while I used RPT as a way of mounting the attack, I think it is not a requirement.

A malicious client can repeatedly migrate to a new address, initiating the use of new CID pairs, at the same time intentionally not acknowledging packets containing RETIRE_CONNECTION_ID frames sent from the server. If the client does that, the number of CIDs that the server has to track for retirement increases as time goes.

-- 
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/3509#issuecomment-597970501

---

From: Eric Kinnear <[email-masked]>
Date: Wed, 11 Mar 2020 19:28:34 -0700

Clarification question: If the person sending RCID isn't getting ACKs back, I think we still need to assume that those CIDs are being replaced? If not, then the non-RPT side of this would just mean the person sending RCID frames runs out of CIDs to use and has to stop.

So the problem statement is that: this person is running over their max_active_cid limit from the perspective of the person withholding ACKs, but each side has their own view and so the person retiring them stopped counting them as active once the frame was sent (but not acknowledged). 
And that can happen via RPT as well, just because it means that they're going to be instructed to send the RCID, but the problem is the same either way?

(Just want to make sure I'm understanding the problem correctly)

-- 
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/3509#issuecomment-597974745

---

From: Kazuho Oku <[email-masked]>
Date: Wed, 11 Mar 2020 19:47:24 -0700

@erickinnear Yes, I think your problem statement is correct.

Or to be even more concise, the problem is that the issuer of CIDs is given additional credit when it receives RCID, which happens before the consumer of CIDs drops the state it needs to retain for retransmitting RCID.

For the attack to work, an attacker has to let the peer consume and retire CIDs. RPT and intentional migration are examples that makes that happen.

-- 
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/3509#issuecomment-597978952

---

From: Mike Bishop <[email-masked]>
Date: Mon, 23 Mar 2020 13:12:22 -0700

So the issue here is fundamentally that you can induce the peer to send retransmittable frames which aren't subject to some kind of flow control, and this is the only instance we have of that.

STOP_SENDING and failing to acknowledge the RESET_STREAM appears to have a similar profile, except that the number of RESET_STREAMs you could have outstanding is bounded by the number of streams the peer has opened, which they control.

You could execute the same attack at a larger scale by choosing particular regions of stream data to never acknowledge, forcing the peer to keep them in memory for retransmission, but the peer could stop sending until that region gets through (applying backpressure) or simply reset the stream.  Since a RESET_STREAM is smaller than the data region and only one is needed per stream, this collapses into the previous case.

What's different here is that the endpoint being attacked doesn't choose whether to retire these CIDs and has no mechanism to apply backpressure.

It seems like there are a couple paths to resolving this.
- As you suggest, we could define an explicit frame that grants the additional CID space, and implementations would not send / could withhold this frame until the RCID is ACK'd.  This creates a backpressure mechanism and has the side benefit of allowing an implementation to vary the number of CIDs it wants to track over time, but the disadvantage of requiring an extra round trip before CIDs can be replaced in the normal case.
- We could mimic the "collapsing" behavior above by defining a frame that retires all CIDs up to a given sequence number.  Then the implementation under memory pressure chooses to retire a few extra CIDs and collapses the whole set waiting to be retransmitted to a single frame.

-- 
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/3509#issuecomment-602830029

---

From: Kazuho Oku <[email-masked]>
Date: Mon, 23 Mar 2020 19:31:48 -0700

@MikeBishop I think your summarization of the problem is accurate.

Regarding an attacker selectively acking packets carrying STREAM frames, yes, the attack exists, but it the sender can mitigate that problem in certain ways. We already state that in [section 21.5](https://quicwg.org/base-drafts/draft-ietf-quic-transport.html#name-stream-fragmentation-and-re).

This issue is the only case that a protocol cannot be implemented properly, with a bounded amount of state.

Regarding how we should fix the problem, _if_ we are going make a protocol change, my preference goes to applying the same design principle that we have in other places (i.e. introduce MAX_CONNECTIONS_IDS frame). I do not like designing a mechanism specific for this purpose, as there is a chance that we might make mistakes.

I can also live with what @martinthomson proposed in https://github.com/quicwg/base-drafts/issues/3509#issuecomment-597425775 (i.e. encourage leaky behavior).

-- 
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/3509#issuecomment-602974153

---

From: ianswett <[email-masked]>
Date: Tue, 24 Mar 2020 09:39:09 -0700

Similar to @martinthomson I'd prefer to acknowledge the problem and indicate that peers may want to limit the number of unacknowledged RETIRE_CONNECTION_ID frames to the number of connection IDs they support.

The other option I can imagine is to make the RETIRE_CONNECTION_ID frame cumulative, which provides a strong incentive to use connection IDs in order. Though we may have to make an exception for the connection ID in the received packet if we did that.

-- 
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/3509#issuecomment-603354443

---

From: Martin Thomson <[email-masked]>
Date: Tue, 24 Mar 2020 15:36:41 -0700

So the bounds on this aren't that terrible.  Say you had to retire 1000 connection IDs all at once.  You could track each one individually as you send RETIRE_CONNECTION_ID.  That's 1000 things to track, which might be more state than you want (it's not 1000 bits because you need to maintain relationships with packet numbers).

Or you could just keep `CID[smallest unacknowledged retire frame] - CID[largest acknowledged retire frame]` strictly limited, no matter how many connection IDs you need to retire.  Tracking that, plus what you have been requested to retire should bound the state required to implement retirement.

In other words, you do control how much state you commit to retirement, just like everything else.

-- 
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/3509#issuecomment-603540361

---

From: martinduke <[email-masked]>
Date: Wed, 25 Mar 2020 10:22:31 -0700

@martinthomson 

> Or you could just keep CID[smallest unacknowledged retire frame] - CID[largest acknowledged retire frame] strictly limited, no matter how many connection IDs you need to retire. Tracking that, plus what you have been requested to retire should bound the state required to implement retirement.

That's my preferred solution, but in my reading of the spec this is not allowed. We MUST send RCID for each sequence number for which the peer has sent retire-prior-to. I think the language in Section 5.1.2 needs 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/3509#issuecomment-603974028

---

From: martinduke <[email-masked]>
Date: Wed, 25 Mar 2020 10:35:17 -0700

@ianswett's idea of allowing RCID to be cumulative is also good and computationally cleaner, although we'd need a different frame type or an additional field in the frame (I don't think we can get rid of retiring non-continuous sequence numbers)

-- 
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/3509#issuecomment-603981003

---

From: martinduke <[email-masked]>
Date: Wed, 25 Mar 2020 10:36:14 -0700

I'm happy to file a PR for the @martinthomson or @ianswett approach based on the overall sentiment. 

-- 
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/3509#issuecomment-603981560

---

From: Mike Bishop <[email-masked]>
Date: Wed, 25 Mar 2020 12:18:30 -0700

One purely implementation option:  It's always legitimate to repeat a frame.  Therefore, if you track _only_ the smallest and largest un-acked RCID sequence numbers, you can just keep retiring the whole range every time you retransmit. ACKs will shrink the range (hopefully to zero).  There's no harm beyond unnecessary bytes in retransmitting something a few extra times to avoid excessive state tracking.

-- 
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/3509#issuecomment-604035249

---

From: Kazuho Oku <[email-masked]>
Date: Wed, 25 Mar 2020 13:42:28 -0700

@ianswett 
> The other option I can imagine is to make the RETIRE_CONNECTION_ID frame cumulative, which provides a strong incentive to use connection IDs in order. Though we may have to make an exception for th…

While I won't say that's impossible, I'd argue that the design is going to be complex.

When CIDs are used in a legitimate manner, they are not going to be retired one by one. A CID is retired when a path using that CID is abandoned.

Consider the case where an endpoint has 4 active CIDs (CID0 to CID3), and two paths. One path could be using CID0, the other path could be using CID3. When the endpoint abandon the path that is using CID3, it has to retire CID3 but it cannot retire others.

@MikeBishop The amount of CIDs that can be sent on wire at a time is restricted by the CWND, therefore there is no guarantee that you can send RCID frames for all CIDs that you want to retire at once. In other words, I think the approach at best collapses into what @martinthomson has proposed (i.e. leaky behavior).

-- 
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/3509#issuecomment-604076404

---

From: ianswett <[email-masked]>
Date: Wed, 25 Mar 2020 15:08:03 -0700

At this point, I also think @martinthomson solution is the best approach, since it is a very minor change, and changing RETIRE_CONNECTION_ID to be cumulative is a larger change than I want to accept at this point. @kazuho, thanks for your examples.

-- 
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/3509#issuecomment-604112790

---

From: ianswett <[email-masked]>
Date: Thu, 26 Mar 2020 14:56:59 -0700

One idea: Can we simplify everything by not requiring sending RETIRE_CONNECTION_ID for CIDs less than the Retire Prior To?  RETIRE_CONNECTION_ID would then only be used when a CID was used and needed to be retired so more CIDs could be issued to the user of the CID.

-- 
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/3509#issuecomment-604707294

---

From: martinduke <[email-masked]>
Date: Thu, 26 Mar 2020 15:06:31 -0700

@ianswett see my comment in the PR. More disruptive to current implementations, and eliminates a useful signal. The current proposal will not matter for well-behaved clients but will protect servers from some attacks.

-- 
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/3509#issuecomment-604711553

---

From: ianswett <[email-masked]>
Date: Thu, 26 Mar 2020 15:23:20 -0700

We haven't implemented this yet, so it's not disruptive to our implementation FWIW

I wonder how useful the signal is.  Retire Prior To is really saying "These are going away sometime soon, whether you like it or not." to the peer.  If an implementation never sent RETIRE_CONNECTION_ID, would that create a problem of some sort, because I suspect someone will do just that.

-- 
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/3509#issuecomment-604718224

---

From: Kazuho Oku <[email-masked]>
Date: Thu, 26 Mar 2020 16:47:22 -0700

@ianswett  As stated in https://github.com/quicwg/base-drafts/issues/3509#issuecomment-597970501, this attack can be mounted without using Retire Prior To.

-- 
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/3509#issuecomment-604743078

---

From: martinduke <[email-masked]>
Date: Thu, 26 Mar 2020 17:08:40 -0700

@kazuho in this case isn't the client limited by active_connection_id_limit? As a server, if the client has in no way indicated it has accepted my retirement, I'm not going to accept new CIDs.

The NCID/RPT case is different because the spec specifically allows the client to NCID speculatively assuming the server will immediately retire the CID.

-- 
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/3509#issuecomment-604748887

---

From: Kazuho Oku <[email-masked]>
Date: Thu, 26 Mar 2020 17:25:25 -0700

@martinduke 
> in this case isn't the client limited by active_connection_id_limit?

The attack here is that when a malicious client retires a CID to which the server has responded, that server would retire the CID that it has used on that path, and also provide a new CID to the client. But the client never ACKs the RCID frames that the server sends.

As an example, consider the case where a client uses sCID1 on a new path, the server responds on that path using cCID1, the client abandons that path and sends RCID (seq=sCID1). When receiving this RCID frame, the server would send RCID (seq=cCID1), and also send NCID(sCID2). The client intentionally does not ack the packet carrying these frames, but uses sCID2 on a new path, that carries NCID(cCID2), repeating this procedure.

-- 
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/3509#issuecomment-604753447

---

From: martinduke <[email-masked]>
Date: Thu, 26 Mar 2020 17:42:57 -0700

Ah, I see now that my defense doesn't work, because if I reject the NCID I have to kill the connection, and it may just be because of unlucky ack losses.

This whole section is not very precisely written and suffers from two-generals problems about when a CID is actually retired.

I will revise to account for this, but I'm not sure how.

-- 
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/3509#issuecomment-604757428

---

From: ianswett <[email-masked]>
Date: Thu, 26 Mar 2020 17:54:34 -0700

@kazuho I agree with @martinduke that there's no valid thread model without Retire Prior To.

If the peer doesn't acknowledge your retirement, then you shouldn't be issuing more CIDs, because you might exceed their limit.

-- 
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/3509#issuecomment-604760044

---

From: ianswett <[email-masked]>
Date: Thu, 26 Mar 2020 17:57:00 -0700

Let's be clear.  Running out of CIDs is not a big crisis.  You can always create a new connection with 0-RTT with a relatively small overhead.  We should be biased towards simplicity rather than never running out of CIDs.

-- 
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/3509#issuecomment-604760574

---

From: martinduke <[email-masked]>
Date: Thu, 26 Mar 2020 19:03:21 -0700

@ianswett unfortunately we are cornered by the spec.

Consider two well behaving endpoints. I'm fully stocked with CIDs and then retire one with a frame. The peer gets the RCID and issues an NCID, but the ack of RCID is lost. If I don't count the CID as retired, then I MUST close the connection. That's bad, so I have to treat the CID as retired if I sent RCID.

If you drop acks at scale, this becomes an attack.

I'm really coming around to your cumulative retire idea, but will have another go at this tomorrow.

-- 
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/3509#issuecomment-604776323

---

From: Kazuho Oku <[email-masked]>
Date: Thu, 26 Mar 2020 19:35:58 -0700

@ianswett 
> If the peer doesn't acknowledge your retirement, then you shouldn't be issuing more CIDs, because you might exceed their limit.

I think the framing is incorrect. The peer can enforce an endpoint to retire a CID (e.g., by changing RPT or discarding a path). As @martinduke points out, an endpoint is encouraged issue a new CID at this point, rather than withholding than until the ACK of RCID is received.

Note also that RCID carries the CID that *the endpoint sends* carries the CID that the peer has issued, while NCID that the endpoint carries the CID that that endpoint issues. Therefore, I am not sure what the rationale for withholding the emission of NCID until receiving an ACK for RCID would be.

> In my opinion, running out of CIDs is not a big crisis. You can always create a new connection with 0-RTT with a relatively small overhead. We should be biased towards simplicity rather than never running out of CIDs.

I agree. An endpoint is not expected to consume CID at high rate. We already discourage such behavior; see https://quicwg.org/base-drafts/draft-ietf-quic-transport.html#section-5.1.1-5.

That's why I'm fine with the leaky behavior that @martinthomson has suggested.

@martinduke 
> I'm really coming around to your cumulative retire idea, but will have another go at this tomorrow.

As previously stated, I am hesitant to have a new machinery that is unique to this purpose. There is a risk of creating something buggy, both in terms of specification and implementation. My preference goes to accepting the risk (and recommending mitigations, such as the leaky behavior), or reusing a design pattern that we already have (i.e. introduce MAX_CONNECTION_IDS frame).

-- 
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/3509#issuecomment-604783890

---

From: ianswett <[email-masked]>
Date: Fri, 27 Mar 2020 05:06:36 -0700

The cumulative idea is very appealing to me, _minus_ a future with multipath.  If two or more paths are active at once, I don't know how the peer would know that if the frame was cumulative.  The only option would be to ensure the two(or more) CIDs in use are adjacent, which is possible, but may require switching CIDs more than should be necessary.

-- 
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/3509#issuecomment-604964152

---

From: martinduke <[email-masked]>
Date: Fri, 27 Mar 2020 08:10:02 -0700

@ianswett I would suggest a cumulative RCID as a supplement to the individual RCID. A cumulative one would cleanly handle a lot of cases where there is an unboundedly large list of sequence numbers to retire. If there is a low sequence number that is still in use, the sender can choose to retire it to enable use of the cumulative frame.

-- 
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/3509#issuecomment-605052596

---

From: Nick Banks <[email-masked]>
Date: Fri, 27 Mar 2020 11:53:42 -0700

I know folks have been resistant to changing state based off receiving an acknowledgement of a packet/frame they sent, but what if we changed how the RetirePriorTo works, and instead just required the packet containing the frame to be acknowledged, instead of requiring the RCID to be sent? Would this solve the problems?

This would mean the receiver of the NCID shouldn't have to track any additional state beyond what it takes to acknowledge the packet (which they have to do anyways); it just immediately throws away the state. And the RCID packet would only be used when the endpoint that was given the CID chooses to retire it.

-- 
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/3509#issuecomment-605211494

---

From: Kazuho Oku <[email-masked]>
Date: Sun, 29 Mar 2020 20:08:12 -0700

FWIW, I have filed #3553 that fixes this issue without introducing a leaky behavior like #3547.

IMO, the observation is that the endpoints can check that the issuer of CIDs is not intentionally introducing gaps in the sequence numbers they generate. We already prohibit senders from introducing such gaps, detecting them on the receiver side would be a good thing to do.

And if endpoints start doing that, using a cumulative RCID frame is a sensible solution, as the the cumulative list of retired CIDs at any time can be represented using a SACK-like structure (i.e., max-retired + small list of active CIDs below that max.).

-- 
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/3509#issuecomment-605758299

---

From: Martin Thomson <[email-masked]>
Date: Sun, 29 Mar 2020 20:48:26 -0700

I know that you have characterized this as "leaky", but I'm not sure that I understand exactly what is being leaked.  Nothing is lost in #3547, except that the endpoint requesting retirement has to tolerate a potentially extended period without old connection IDs being retired.

In case this helps, I have no big preference between #3547 and #3550.  There is a certain elegance to #3550 that might tip me toward that, but it is slightly more disruptive.

I prefer either of those to the more disruptive change in #3553, which also has the downside of strongly encouraging connection ID changes in order to preserve a clean separation between active and retired.  #3553 doesn't force you to drop old connection IDs.  However, the encoding of the frame is just too complicated for me to accept.  I would prefer forcing a clean separation than having a complex encoding like this.

#3548 is a non-starter for me for the reasons stated.

-- 
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/3509#issuecomment-605767369

---

From: Kazuho Oku <[email-masked]>
Date: Sun, 29 Mar 2020 21:09:46 -0700

@martinthomson 
> I know that you have characterized this as "leaky", but I'm not sure that I understand exactly what is being leaked. Nothing is lost in #3547, except that the endpoint requesting retirement has to…

In the approach we take in #3547, there is a possibility that the issuer of the CID might not receive RCID frames that the peer sends, when the issuer is issuing new CIDs at high rate and the receiver is also consuming them at a hight rate. That is the consequence of endpoints limiting the amount of inflight RCID frames it tracks.

I think we can provide advice so that the "leak" would not be an issue in practice, and assuming that would happen, I am happy with #3547 being the solution.

I think #3553 is cleaner, but I acknowledge that it is more disruptive than #3547. Part of my intent behind creating #3553 is to see how a clean fix (in terms of state machinery) would look like, so that it can be compared against #3547.

> In case this helps, I have no big preference between #3547 and #3550. There is a certain elegance to #3550 that might tip me toward that, but it is slightly more disruptive.

As stated in https://github.com/quicwg/base-drafts/pull/3550#issuecomment-605540981, #3550 by itself only partly fixes the problem. I am not against adopting #3550 along with #3547 though.

#3548 is also a partial fix, I also think that it is a non-starter.

-- 
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/3509#issuecomment-605771367

---

From: Martin Thomson <[email-masked]>
Date: Sun, 29 Mar 2020 21:45:46 -0700

I think that I understand your point; thanks for your patience.

I didn't really classify it as a leak though, so the choice of words threw me a little, it's more of a lag.

Let's say that you have a pathological endpoint that sends an infinite series of NEW_CONNECTION_ID frames with Sequence Number N and Retire Prior To of (N-1).  That's legal and will never violate any limits.  But unless they maintain acknowledgments for RETIRE_CONNECTION_ID frames at a similar rate (which, to be fair should be easy as `sizeof(NEW_CONNECTION_ID) > sizeof(RETIRE_CONNECTION_ID) > sizeof(ACK)` for the same values), they could get far ahead of their peer.

I don't think that it is strictly a leak, just a lag between the connection IDs being pushed and the connection IDs being successfully retired.  Without #3547 or something else this could be problematic.  And I now understand why #3550 is really just an orthogonal refinement, though it might make other defenses less likely to be required by making `sizeof(sum(RETIRE_CONNECTION_ID))` zero in cases where an endpoint isn't using discretionary retirement.

The defense in #3553 is to make `sizeof(sum(RETIRE_CONNECTION_ID))` effectively constant, no matter how many frames need to be retired.  My main objection is really that it is a maximal design where only a minimal one is warranted.

It's probably worth pointing out that there is also the simplest defense:  If you can't keep up with RETIRE_CONNECTION_ID, stop talking to the peer that does this to you.  This is just another example from that category of abuse we don't have specific protocol mechanisms to mitigate.

-- 
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/3509#issuecomment-605779478

---

From: ianswett <[email-masked]>
Date: Mon, 30 Mar 2020 08:40:44 -0700

I agree that I'd like to see a minimal solution, so I'm leery of heading towards #3553.

In order for a peer to need to send a lot of RETIRE_CONNECTION_ID frames without Retire Prior To, a lot of 5-tuple + CID changes need to be coming in.  One way to rate limit that naturally is to stop giving out CIDs if the peer hasn't acknowledged your RETIRE_CONNECTION_ID frames.

ie: Limit the number of NEW_CONNECTION_ID frames in flight to:
`max_active_connection_ids +1 -  num(RETIRE_CONNECTION_ID frames)`

So if the peer stops acknowledging your retirements, you stop giving them new CIDs.  I think this avoids the need for any other limits?  I added 1 in my example so one NCID could be sent even if all of the peer's CIDs had just been retired, though that concern disappears if we decided to also do something like #3550

-- 
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/3509#issuecomment-606076756

---

From: martinduke <[email-masked]>
Date: Mon, 30 Mar 2020 10:01:03 -0700

What a mess we've made! Is there interest in doing a Zoom about this? Maybe 0900 Tokyo/1100 Sydney/1700 Seattle/2000 Boston on Tue/Wed?

The root cause is that the flow control mechanism isn't all that well designed. IMO #3553 is the actual correct fix to this problem, but as people say, it's disruptive.

#3548 uses ACKs as an implicit signal, which seems like a problem. #3553 has a different implicit signal, and I don't think it solves the case where the client is withholding acks for unsolicited RCIDs.

I really think we should just use #3547 or #3553 depending on our appetite for changing the wire image. #3547 is great for the RCID sender, and if the receiver won't miss any RCIDs unless it's doing pathological stuff or the ack loss patterns are tremendously unlucky.

#3553, OTOH, is a comprehensive fix to the problem.

-- 
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/3509#issuecomment-606120826

---

From: ianswett <[email-masked]>
Date: Mon, 30 Mar 2020 10:10:18 -0700

I think #3547 with some added text about limiting outstanding NCIDs when there are lots of RCIDs would be sufficiently robust.

-- 
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/3509#issuecomment-606125507

---

From: Kazuho Oku <[email-masked]>
Date: Mon, 30 Mar 2020 19:06:32 -0700

I'm fine with trying to see if we can reach an agreement on #3547.

-- 
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/3509#issuecomment-606353853

---

From: Marten Seemann <[email-masked]>
Date: Mon, 30 Mar 2020 19:51:03 -0700

I'd prefer #3553 over #3547. I can't really see why it would more disruptive than #3547.

The problem with #3547 is that it will likely work find in *most* cases, but there are some corner case (when the ACKs for RETIRE_CONNECTION_ID frames are lost), in which things will break. Properly accounting for these corner cases requires some non-trivial tracking logic in order to avoid risking the connection being closed with a CONNECTION_ID_LIMIT_ERROR.

On the other hand, #3553 seems to be conceptually simpler. I'd rather implement a few changes to my frame parser than introduce some ACK-tracking logic.

-- 
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/3509#issuecomment-606367037

---

From: Kazuho Oku <[email-masked]>
Date: Mon, 30 Mar 2020 22:28:15 -0700

Just to give another example of how an endpoint might end up required to track the retirement of more than active_connection_id_limit:
* A server tries to supply three active CIDs to the peer. At the moment, it has provided CID<sub>0</sub>, CID<sub>1</sub>, CID<sub>2</sub> to the client.
* The client sends RCID(CID<sub>1</sub>),  RCID(CID<sub>2</sub>). The server provides NCID(CID<sub>3</sub>), NCID(CID<sub>4</sub>). The two NCID frames are delivered to the client, but the ACK for the RCID frames gets lost.
* The client decides to probe two paths concurrently, by using CID<sub>3</sub> and CID<sub>4</sub>, but shortly after the packets are sent using those paths, the underlying network for those two paths disappear.
* The client now needs to make sure that RCID frames carrying 4 CIDs reach the peer.

In this example, we might argue that it would be possible for the client to figure out that CID<sub>3</sub> and CID<sub>4</sub> were provided as substitutions for CID<sub>1</sub> and CID<sub>2</sub>. But do we want to implement logic that detects such condition into our code? Note that tracking of substitutions can become tricky; if RCID(CID<sub>1</sub>) and RCID(CID<sub>2</sub>) were sent in different packets, it would be impossible for the client to see if CID<sub>4</sub> was provided as a supplement for CID<sub>1</sub> or for CID<sub>2</sub>.

-- 
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/3509#issuecomment-606408197

---

From: Nick Banks <[email-masked]>
Date: Tue, 31 Mar 2020 07:51:50 -0700

I agree with @kazuho that if we go with #3547 the limit should be higher than `active_connection_id_limit`.

-- 
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/3509#issuecomment-606676316

---

From: Jana Iyengar <[email-masked]>
Date: Tue, 31 Mar 2020 16:13:38 -0700

I finally caught up with this issue, and implementer advice is definitely my preferred way forward. We're going to need some complexity to (and some magic numbers) no matter what, let's do this while limiting mechanism to a minimum. To that end, I agree with #3547 as a good resolution.

-- 
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/3509#issuecomment-606933452