Subject: [quicwg/base-drafts] rate-limiting the CID issuance needs to be allowed (#2436)

From: Kazuho Oku <[email-masked]>
Date: Wed, 06 Feb 2019 23:38:16 -0800

At the moment, the transport draft assumes that the issuer of CIDs is going to issue new ones as the consumer retires them. Quoting from [section 5.1.1 of the transport draft](https://quicwg.org/base-drafts/draft-ietf-quic-transport.html#rfc.section.5.1.1), the issuer _SHOULD do this by **always** supplying a new connection ID when a connection ID is retired by its peer or when the endpoint receives a packet with a previously unused connection ID_ (emphasis mine).

However, simply following the provision introduces a DoS attack vector.

Malicious clients can connect to a server and consume CIDs as fast as they can. Assuming that the server tries to provide 8 spare CIDs, a client with 10ms RTT can consume 800 CIDs per second (≈ 2<sup>16</sup> CIDs per minute per connection). This is especially a risk to servers using minimally-sized CIDs (which is 32-bits). An attacker controlling 256 connections can consume all the CIDs in 4 hours. Because a server cannot reuse a CID as frequently as that (because it cannot rotate the secret used to generate stateless reset tokens very often). This would be a risk for clustered servers using longer CIDs as well, because the number-space used to identify each path within each server is expected to consume only some of the bits of the CID.

Therefore, it is preferable to clarify that a server might want to rate-limit the issuance of CIDs or simply limit the total number of CIDs being issued for each connection. Hence PR #2428.

Initially pointed out in 
https://github.com/quicwg/base-drafts/issues/2403#issuecomment-460255684 as part of the issue, opening a issue dedicated to the problem as [suggested by @martinthomson ](https://github.com/quicwg/base-drafts/pull/2428#pullrequestreview-200896573).

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

---

From: MikkelFJ <[email-masked]>
Date: Thu, 07 Feb 2019 00:37:43 -0800

If the server ties CID’s to 5-tuples I suppose the problem is much reduced, although multiple connections over same 5-tuple happens?

-- 
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/2436#issuecomment-461330327

---

From: Kazuho Oku <[email-masked]>
Date: Thu, 07 Feb 2019 00:47:38 -0800

@mikkelfj I do not think that's a viable option, because a stateless reset token cannot be tied to a particular client IP address.

Assuming that the server ties CID’s to 5-tuples, an attacker that observes the CID can send a packet carrying that CID from a different client address to obtain the stateless reset token, then use that to terminate a connection.

-- 
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/2436#issuecomment-461333247

---

From: MikkelFJ <[email-masked]>
Date: Thu, 07 Feb 2019 00:53:59 -0800

So you are saying that a reset cannot be tied to a 5-tuple.

-- 
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/2436#issuecomment-461335103

---

From: Kazuho Oku <[email-masked]>
Date: Thu, 07 Feb 2019 00:54:58 -0800

Correct. Or maybe I should have pointed out that if a server ties CID to 5-tuple, a connection would die once a NAT rebinding happens (without client knowing 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/2436#issuecomment-461335381

---

From: Christian Huitema <[email-masked]>
Date: Fri, 08 Feb 2019 07:38:22 +0000 (UTC)

Yes, I think rate limit is a plausible solution. But the malicious clients can also set up a connection, get half a dozen CID, then set a new connection, etc. So it boils down to how many connection per second the server will support (100? 1000? 10000? Multiply by size of farm?) and how often the CID encryption key will rotate. That, multiplied by the number of CID per connection, gives a number. Log2 of that gives the minimum size in bits. For a server doing 10000 connections per second, 16 CID per connection, 24 hours for the key, the result is 34 bits. Add 2 for managing key rotations, then add routing bits in the case of a farm. We should be good with 40 bits for a single server, 56 bits for a small farm, 64 bits for a larger farm.

-- 
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/2436#issuecomment-461716497

---

From: MikkelFJ <[email-masked]>
Date: Fri, 08 Feb 2019 01:00:06 -0800

Scary numbers, but what is the problem with potential early reuse?
Say a server has 10000 connections and 20000 active CID's, and 30000 CID's total because peer has an extra.

A new CID is issued, and an old is retired. In counter mode, the CID's are cycled and can already generate conflicts after truncation to 32-bits. These conflicts can be checked against the 30K CID table. If a CID's rotate fast enough, conflicts happen faster, but they won't happen on any currently recognised CID's by that instance.

This is just from a 5-minute speculation, I could clearly be missing something important. But I think it  is important to consider how conflicts are dealt with.

-- 
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/2436#issuecomment-461734436

---

From: Martin Thomson <[email-masked]>
Date: Fri, 08 Feb 2019 01:13:28 -0800

Those are not scary numbers.  It almost fits into the smallest possible connection ID.

Keep in mind that you really don't want to reuse values: if you reuse values over that period, you risk reusing a value for which a stateless reset was sent.  That might increase the number a little.

With 100,000 active connections per server in a 1000 server cluster issuing 16 connection IDs per second for each connection (which is a very high rate, but you have to allow for those connections being new ones), you need 47 bits worth of space if you don't want to repeat once a day.  Add 3 for a week's worth of key identifier and that's 50 bits.  That's still short of the 64 bits that gQUIC had for connection IDs.  If you want to assign randomly, you can do that with 100 bits and avoid the birthday paradox.

The numbers seem to play out nicely.

-- 
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/2436#issuecomment-461737728

---

From: MikkelFJ <[email-masked]>
Date: Fri, 08 Feb 2019 09:19:10 +0000 (UTC)

Well, not scary, but it rules out 32-bit. But that was naive 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/2436#issuecomment-461739280

---

From: Mike Bishop <[email-masked]>
Date: Fri, 08 Feb 2019 17:28:26 +0000 (UTC)

The fact that it's a SHOULD seems to imply that the server can throttle the issuance of CIDs if it so chooses.  So if it wants to have a 16-per-second or lower limit, it's free to do so.  @kazuho, is the concern around the combination of "SHOULD ... always"?

-- 
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/2436#issuecomment-461880971

---

From: Kazuho Oku <[email-masked]>
Date: Fri, 08 Feb 2019 10:07:25 -0800

@MikeBishop Partly yes. "always" indeed seemed strange to me.

What I want to see is something along the lines of "don't blame the server if a client runs out of CIDs when retiring them at high rate", as well as clarifying the reasons why a server developers might want to  limit the issuance of CIDs (as a guidance).

PS. Honestly speaking, I'm interested in simply capping the total number of CIDs issued for each connection rather than rate-limiting. That'd be fine for H3, because a server running out of CIDs can send GOAWAY.

-- 
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/2436#issuecomment-461893065

---

From: MikkelFJ <[email-masked]>
Date: Fri, 08 Feb 2019 18:43:04 +0000 (UTC)

> PS. Honestly speaking, I'm interested in simply capping the total number of CIDs issued for each connection rather than rate-limiting. That'd be fine for H3, because a server running out of CIDs ca…

That would be annoying for long running connections because they might have a policy of rotating CID infrequently. Suddenly having to kill a connection the has no relation to H3 semantics is not good. I'd be happy to set a limit per day.

-- 
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/2436#issuecomment-461903637

---

From: Kazuho Oku <[email-masked]>
Date: Fri, 08 Feb 2019 11:13:13 -0800

@mikkelfj 
> Suddenly having to kill a connection that has no relation to H3 semantics is not good.

GOAWAY is a way of requesting the client to create a new connection for the following requests. It's a the opposite of suddenly killing a connection.

-- 
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/2436#issuecomment-461913126

---

From: MikkelFJ <[email-masked]>
Date: Fri, 08 Feb 2019 11:15:44 -0800

It's the IETF equivalent of an offer you can't refuse.
And the one offering it doesn't have a choice either, if counting to max is the only option, and max is designed low to deal with many short lived connections.

-- 
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/2436#issuecomment-461913885

---

From: MikkelFJ <[email-masked]>
Date: Fri, 08 Feb 2019 11:17:38 -0800

As also discussed on the mailing list in another context: if you are offered to start a new connection mid up-load of multiple Gigabytes, or hours of transaction processing, the one transport endpoint might be happy, but both application endpoints will be sad and disappointed.

-- 
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/2436#issuecomment-461914451

---

From: Kazuho Oku <[email-masked]>
Date: Fri, 08 Feb 2019 19:32:00 +0000 (UTC)

> if you are offered to start a new connection mid up-load of multiple Gigabytes, or hours of transaction processing,

That's an untypical scenario for HTTP.

Note also that even if the client runs out of spare CIDs, it can still continue using the connection. The only thing the client cannot do is initiate a voluntary migration. Considering the fact that migration is not a mandatory feature (both for client and server), I do not think there's a strong reason to argue against endpoints refusing to provide additional room for migration at certain moments.

-- 
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/2436#issuecomment-461919062

---

From: MikkelFJ <[email-masked]>
Date: Fri, 08 Feb 2019 11:39:32 -0800

As I mentioned earlier, I am concerned about non-HTTP uses cases, and for that matter also about mixing the layers. Transport should not rely on GOAWAY, and HTTP layer should be not concerned with refreshing CID's.

If you at all risk running out of CID's and you can't do anything about it, then you are not going to rotate CID's at all. That might also not be necessary, but is what will happen.

A limit per day is unproblematic, like at most 2 migrations per day without migration, reset counter on migration. If client is able to migrate enough to still cause a problem, we might need a total daily cap.

>From another perspective: If the concern regarding conflicts only has to do with a low risk of stateless reset, I'd rather have that than a high risk of running out of CID's.

-- 
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/2436#issuecomment-461921648

---

From: Kazuho Oku <[email-masked]>
Date: Fri, 08 Feb 2019 17:07:00 -0800

> I am concerned about non-HTTP uses cases, and for that matter also about mixing the layers. Transport should not rely on GOAWAY, and HTTP layer should be not concerned with refreshing CID's.

Fair enough. Though my point is that _for HTTP/3_ (which happens to be the primary target of QUIC v1) just capping the number of CIDs is totally fine. The proposal does not mandate such behavior. It's merely clarifying that such behavior is permissible.

When you are to define an application protocol for QUIC v1 that requires the connections to survive lots of migrations, you would be required to clarify that the servers should support that, regardless of the outcome of this issue. That is because, as stated in [my previous comment](
https://github.com/quicwg/base-drafts/issues/2436#issuecomment-461919062), migration is an optional feature of QUIC v1. Running out of CID is no worse than connecting to a server that does not support migration in terms of the transport spec.

To put it another way, while I can understand your concern, I think it's orthogonal to this 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/2436#issuecomment-461997482

---

From: MikkelFJ <[email-masked]>
Date: Fri, 08 Feb 2019 23:19:49 -0800

> The proposal does not mandate such behavior. It's merely clarifying that such behavior is permissible.

I was concerned that you wanted to make it a requirement. Anyway, I'd also like that behaviour is reasonable predictable so app protocols don't have too many constraints on deployments. A stack used for HTTP might well be used for other things.

I'm still wondering if there are benefits to rotating CID's when not migrating, but I think there is since you might want to refresh routing tables. This is starting to be a separate, but related issue, but one thing is rate limiting, the other is convincing peer to rotate or not rotate within a given time frame, with no migration. I'd be best if transport could take the guesswork out of this.

Overall, I could see a requirement to rotate daily and requirement to supply a min count of CID's daily, just to ensure all entities, including middle boxes have something to work from.

-- 
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/2436#issuecomment-462021395

---

From: Martin Thomson <[email-masked]>
Date: Sun, 10 Feb 2019 16:23:51 -0800

Predictability here also - unfortunately - could mean exposing details of server resource constraints to clients.  Or other details that might advantage an attacker.  That is because the resource in question is shared.  Though individuals might be given caps on their own usage that are independent of others (the sequence number might cap out at 200, for instance), anything more concrete and actionable might expose information about how much spare capacity the server truly has.

-- 
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/2436#issuecomment-462195820

---

From: MikkelFJ <[email-masked]>
Date: Sun, 10 Feb 2019 22:44:39 -0800

@martinthomson yes, that is a balance to strike, but a conservative limit of 1-2 per day ought to be reasonable unless I'm missing something. Or, we should entirely avoid rotation non-migration as a general principle.

-- 
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/2436#issuecomment-462231304

---

From: Martin Thomson <[email-masked]>
Date: Mon, 11 Feb 2019 08:06:17 +0000 (UTC)

1-2 connection IDs per day is probably totally inadequate for someone who is mobile.  That's a more realistic number for key rotations.  I can imagine 1 every 15 minutes on average being 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/2436#issuecomment-462244453

---

From: MikkelFJ <[email-masked]>
Date: Mon, 11 Feb 2019 04:39:01 -0800

that was for non-migration, if rotation is needed at all

-- 
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/2436#issuecomment-462313336

---

From: Mike Bishop <[email-masked]>
Date: Mon, 11 Feb 2019 23:47:59 +0000 (UTC)

I think the point is to mandate a minimum frequency of migrations.  However, what that minimum frequency should be will depend on the server's infrastructure, which is too variable to get a good requirement into the spec.  I've written up the PLEASE_RETIRE_CID frame [here](https://mikebishop.github.io/please-retire/draft-bishop-quic-please-retire.html).

-- 
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/2436#issuecomment-462542234

---

From: martinduke <[email-masked]>
Date: Tue, 12 Feb 2019 13:26:20 -0800

I strongly support limiting Connection ID pulls. Beyond the DoS issues, for servers with a relatively limited pool of connection IDs, for whatever reason, allowing an attacker to open a connection and getting a large sample of connection IDs from one server can open up various attempts to crack the route encoding scheme.

-- 
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/2436#issuecomment-462941805

---

From: erickinnear <[email-masked]>
Date: Tue, 12 Feb 2019 14:29:01 -0800

There *aren't* any CID pulls, though, isn't the whole idea here that the server only issues as many as it's willing to support? 

-- 
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/2436#issuecomment-462962923

---

From: martinduke <[email-masked]>
Date: Tue, 12 Feb 2019 14:30:52 -0800

RETIRE_CONNECTION_ID is, in effect, a pull, if we SHOULD supply a new one every time we get it. There are security considerations that apply to that recommendation.

-- 
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/2436#issuecomment-462963621

---

From: erickinnear <[email-masked]>
Date: Tue, 12 Feb 2019 14:36:48 -0800

But isn't it not *actually* a pull, specifically for this reason? In other words, isn't it a SHOULD and not a MUST to say "please provide a new one, unless you have a really good reason that you cannot/should not", for some of the reasons highlighted above?

-- 
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/2436#issuecomment-462965718

---

From: martinduke <[email-masked]>
Date: Tue, 12 Feb 2019 22:42:05 +0000 (UTC)

I think if the spec has a SHOULD that raises known security concerns without mentioning those concerns, that's a 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/2436#issuecomment-462967709

---

From: Martin Thomson <[email-masked]>
Date: Tue, 12 Feb 2019 14:46:25 -0800

@martinduke, that is the point of @kazuho's PR.  To include some justification for the SHOULD.

-- 
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/2436#issuecomment-462969325

---

From: martinduke <[email-masked]>
Date: Tue, 12 Feb 2019 14:48:52 -0800

@martinthomson Yes, I'm in full support of the PR.

-- 
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/2436#issuecomment-462970218

---

From: Jana Iyengar <[email-masked]>
Date: Thu, 21 Feb 2019 18:17:22 -0800

This issue is worth noting in the draft, and the PR looks good 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/2436#issuecomment-466246762