Subject: Authenticating connection IDs

From: "Martin Thomson" <[email-masked]>
Date: Thu, 05 Mar 2020 14:23:19 +1100

First, please read https://github.com/quicwg/base-drafts/issues/3439#issuecomment-594320754 for background.  The tl;dr is that there are some cases in which an attacker is able to choose the connection ID that is negotiated during the handshake.

https://github.com/quicwg/base-drafts/pull/3499 is a first cut at "fixing" this.  It proposes two fixes:

1. include the SCID from Initial packets in a transport parameter that is authenticated after the handshake completes

2. require that servers not reuse the client's DCID as their SCID when sending Initial packets (the same requirement already exists for Retry)

We so far have some support, but two concerns have been raised:

Issue A. Google would find it easier to deploy this if the first fix allowed the server to copy the client's choice of connection ID in the absence of a Retry.  This is understandable, and easing deployment is a worthwhile goal.  The cost is that this complicates the logic for clients marginally.  It was also observed that servers need to be able to generate new connection IDs anyway, which challenges the difficulty aspect here a little. I think that it only invalidates a subset of connection ID generation methods if you care about performance, but am open to being convinced otherwise.

Issue B.  Marten Seemann claims that the second measure is sufficient provided that endpoints validate that the connection ID does not change during the handshake.  That might work, but I can also see awkward interactions with other choices we've made, such as the client being permitted to use values from NEW_CONNECTION_ID frames in 0.5-RTT packets (similarly for 0-RTT at the server).  My understanding is that this might affect formal verification though.

No matter which outcome we choose, the effect that this would have on any formal verification that has happened is probably the key consideration for me.  This came out of research that Antoine and others did on formally verifying QUIC and this was identified as one of the few weaknesses in the record layer design.  Removing this style of weakness and making proofs simpler was something that contributed to the success of TLS 1.3.  In my view, whatever we can do here to the same end is worth doing.

This is one of our last (!) transport issues of any real substance, and I think that it's worth trying to work toward a resolution here.  Personally, I don't have strong opinions about either except to say that I would vastly prefer an imperfect solution that we can ship now with some amount of confidence in (i.e., one that wasted bytes on a transport parameter) over any extended debate.

I lean toward sticking with the proposal as it stands, but am prepared to be convinced otherwise.

Cheers,
Martin

---

From: David Schinazi <[email-masked]>
Date: Thu, 5 Mar 2020 17:00:09 -0800

I'm in full agreement that we should make changes that facilitate formal
verification, as this improves the security of the protocol. I also agree
that we should resolve this as soon as possible.

However, the current full proposal would be problematic to deploy at
Google, let me try to explain why. Servers need a mechanism to communicate
with their load balancers to get a list of new connection IDs that route to
this server. This isn't new in this proposal, and is already required for
connection migration. However, if the server and load balancer are
different machines, then the process of getting more connection IDs to the
server is asynchronous. In Google's deployment, we have periods of time
where the server does not have any fresh connection IDs available (imagine
for example that the server just ran out and is waiting to hear back from
the load balancer). In the case of connection migration, this isn't a
problem: the server completes the handshake normally, and waits to get
additional connection IDs before it sends any NEW_CONNECTION_ID frames.
This can delay the time at which a client can migrate, but doesn't block
requests on the main path. However, part (2) of Martin's current proposal
changes that: now, in order to complete the handshake, the server needs at
least one available fresh connection ID. If the server waits for the load
balancer to get that, it cannot respond to any of the client's requests
until it has that fresh connection ID. I think the performance impact here
is deal-breaking.

I would propose to take part (1) of Martin's proposal without part (2), as
that solves the formal verification issue without the negative side-effect
described above. I'll also note that for interop purposes we can deploy (1)
as a new transport parameter that is only validated when present, so we can
make part (1) of this change without breaking backwards-compatibility with
draft-27. On the other hand, part (2) would break backwards compatibility.

David

On Wed, Mar 4, 2020 at 7:23 PM Martin Thomson <[email-masked]> wrote:

> First, please read
> https://github.com/quicwg/base-drafts/issues/3439#issuecomment-594320754
> for background.  The tl;dr is that there are some cases in which an
> attacker is able to choose the connection ID that is negotiated during the
> handshake.
>
> 1. include the SCID from Initial packets in a transport parameter that is
> authenticated after the handshake completes
>
> 2. require that servers not reuse the client's DCID as their SCID when
> sending Initial packets (the same requirement already exists for Retry)
>
> Issue A. Google would find it easier to deploy this if the first fix
> allowed the server to copy the client's choice of connection ID in the
> absence of a Retry.  This is understandable, and easing deployment is a
> worthwhile goal.  The cost is that this complicates the logic for clients
> marginally.  It was also observed that servers need to be able to generate
> new connection IDs anyway, which challenges the difficulty aspect here a
> little. I think that it only invalidates a subset of connection ID
> generation methods if you care about performance, but am open to being
> convinced otherwise.
>
> Issue B.  Marten Seemann claims that the second measure is sufficient
> provided that endpoints validate that the connection ID does not change
> during the handshake.  That might work, but I can also see awkward
> interactions with other choices we've made, such as the client being
> permitted to use values from NEW_CONNECTION_ID frames in 0.5-RTT packets
> (similarly for 0-RTT at the server).  My understanding is that this might
> affect formal verification though.
>
> No matter which outcome we choose, the effect that this would have on any
> formal verification that has happened is probably the key consideration for
> me.  This came out of research that Antoine and others did on formally
> verifying QUIC and this was identified as one of the few weaknesses in the
> record layer design.  Removing this style of weakness and making proofs
> simpler was something that contributed to the success of TLS 1.3.  In my
> view, whatever we can do here to the same end is worth doing.
>
> This is one of our last (!) transport issues of any real substance, and I
> think that it's worth trying to work toward a resolution here.  Personally,
> I don't have strong opinions about either except to say that I would vastly
> prefer an imperfect solution that we can ship now with some amount of
> confidence in (i.e., one that wasted bytes on a transport parameter) over
> any extended debate.
>

---

From: Matt Joras <[email-masked]>
Date: Thu, 5 Mar 2020 17:50:58 -0800

I have no objection to what David is proposing and I do believe this
problem is in general worth addressing. However I'd like to note that it's
not _required_ for a server to be in communication with its load balancer
(i.e. have the load balancer issue CIDs) in order to get CID-based routing
to function, even for large deployments. In our deployment, the server
generates CIDs based on a known scheme, and the load balancer is aware of
this scheme, so it can generate the CIDs at any time (see
https://git.io/JvVhS).

That said, what David is describing is a reasonable deployment decision
AFAICT and I don't think we should implicitly discourage it by making it
less performant. I'm also not convinced there is a serious attack threat
from using client-generated CIDs for routing but am willing to be convinced
otherwise.

Matt

---

From: "Martin Thomson" <[email-masked]>
Date: Fri, 06 Mar 2020 15:09:47 +1100

On Fri, Mar 6, 2020, at 12:50, Matt Joras wrote:
> AFAICT and I don't think we should implicitly discourage it by making 
> it less performant. I'm also not convinced there is a serious attack 
> threat from using client-generated CIDs for routing but am willing to 
> be convinced otherwise.

The threat is that this is a potentially attacker-controlled CID.

In any case, I think we have several options:

1. As proposed.  MUST change the CID.  This is difficult if CID generation is not essentially free, as Matt points out.

2. If Retry, MUST change the CID again; if not Retry, no restrictions.  This gives the client some assurance that a spoofed Retry, akin to what Antoine demonstrated, isn't in use.  This seems difficult for async CID generation for the above reasons, but a server could pack an extra connection ID in the Retry token if it wanted to ensure that one was immediately available when handling the Initial.

3. No protections.  Let the server copy the CID for an Initial and take that risk.

Note that I don't believe that risk falls exclusively on the server here.  Both endpoints share any risk, so it would be better if there were ways for each to check the other, but that is not a hard requirement.

Options 2 and 3 allow the possibility that an attacker sets the connection ID.  Absent Retry, as the client has to use the same value for the entire handshake and thereafter, we have weak protection for the connection ID via the AAD on Handshake and 1-RTT packets.  We assume that an attacker can't generate valid packets at those levels, so this should devolve to a denial of service - those packets can't be processed.  However, in option 3, if the server copies the connection ID after a Retry, there is no such protection; we have to rely on other measures.

It seems like we are gravitating toward adding a recommendation (i.e., SHOULD, not MUST, is my sense from the discussion) that servers authenticate the connection ID that a client uses when handling an Initial that contains a Retry token.  The server could use a deterministic mapping from the ODCID or bundle something in the token.  If we go with 2 or 3 - and likely regardless - I'll add that.

Cheers,
Martin

p.s.,  There is another design that might work here: take the token field out of Initial packets and use the DCID field.  Require that the server use the Retry SCID for a token too.  Lift the size limit on those fields and you have everything a server might need.  The client might send a large DCID in Initial packets after a Retry, but we repeat the token anyway.  Then of course the server has to pick a new value with its Initial packet because otherwise it would be too big.  The only problem I see is that after an Initial that uses a token from NEW_TOKEN, if there is a Retry, the ODCID transport parameter might be a little large.  Also, this is a much bigger change :)

---

From: David Schinazi <[email-masked]>
Date: Fri, 6 Mar 2020 10:51:01 -0800

Thinking about this some more, I think that forcing the server to change
connection IDs doesn't solve all our concerns: if an attacker messes with
some CIDs and gets the client to land on a target server, having that
server spin up a new CID that lands on the same server doesn't help.
Additionally, I'm not a fan of requiring the server to have CIDs on hand,
for the reasons described above. I think there is a slight tweak to the
proposal that can secure everything: we take MT's new transport parameter
and have it contain pretty much all the connection IDs that could be messed
with. If we look at both scenarios below, with the current spec
requirements, and name the CIDs, we get:

Handshake Without Retry
    C_INITIAL [S=CS1, D=CD1]->
                                           <-S_INITIAL [S=SS1,D=CS1]
    SS1 may be equal to CD1

Handshake With Retry
    C_INITIAL [S=CSa, D=CDa]->
                                       <- S_RETRY [S=SSa, D=CSa]
    C_INITIAL [S=CSa, D=SSa]
                                           <-S_INITIAL [S=SSb,D=CSa]
    SSa MUST be different from CDa
    SSb may be equal to SSa

The client's new TP contains both the CIDs that it used in the first
INITIAL packet it sent.
The server's new TP contains the source CID from its retry if there was
one, followed by both the CIDs that it used in the first INITIAL packet it
sent.

In the handshake without retry case, the client will add (CS1,CD1) in the
new TP and the server will add (SS1,CS1).
In the handshake with retry case, the client will add (CSa,CDa) in the new
TP and the server will add (SSa,SSb,CSa). Additionally, the server still
sends CDa in existing original_connection_id TP.

This would ensure that no one but the endpoints can modify connection IDs
during the handshake. If a server is concerned about letting the client
pick its CID, the server has the opportunity to change it like it does
today, but we don't force servers to do it.

Thoughts?
David

On Thu, Mar 5, 2020 at 8:10 PM Martin Thomson <[email-masked]> wrote:

> 1. As proposed.  MUST change the CID.  This is difficult if CID generation
> is not essentially free, as Matt points out.
>
> 2. If Retry, MUST change the CID again; if not Retry, no restrictions.
> This gives the client some assurance that a spoofed Retry, akin to what
> Antoine demonstrated, isn't in use.  This seems difficult for async CID
> generation for the above reasons, but a server could pack an extra
> connection ID in the Retry token if it wanted to ensure that one was
> immediately available when handling the Initial.
>
> Note that I don't believe that risk falls exclusively on the server here.
> Both endpoints share any risk, so it would be better if there were ways for
> each to check the other, but that is not a hard requirement.
>
> Options 2 and 3 allow the possibility that an attacker sets the connection
> ID.  Absent Retry, as the client has to use the same value for the entire
> handshake and thereafter, we have weak protection for the connection ID via
> the AAD on Handshake and 1-RTT packets.  We assume that an attacker can't
> generate valid packets at those levels, so this should devolve to a denial
> of service - those packets can't be processed.  However, in option 3, if
> the server copies the connection ID after a Retry, there is no such
> protection; we have to rely on other measures.
>
> It seems like we are gravitating toward adding a recommendation (i.e.,
> SHOULD, not MUST, is my sense from the discussion) that servers
> authenticate the connection ID that a client uses when handling an Initial
> that contains a Retry token.  The server could use a deterministic mapping
> from the ODCID or bundle something in the token.  If we go with 2 or 3 -
> and likely regardless - I'll add that.
>
> Cheers,
> Martin
>
> p.s.,  There is another design that might work here: take the token field
> out of Initial packets and use the DCID field.  Require that the server use
> the Retry SCID for a token too.  Lift the size limit on those fields and
> you have everything a server might need.  The client might send a large
> DCID in Initial packets after a Retry, but we repeat the token anyway.
> Then of course the server has to pick a new value with its Initial packet
> because otherwise it would be too big.  The only problem I see is that
> after an Initial that uses a token from NEW_TOKEN, if there is a Retry, the
> ODCID transport parameter might be a little large.  Also, this is a much
> bigger change :)
>
>

---

From: "Martin Thomson" <[email-masked]>
Date: Mon, 09 Mar 2020 12:24:51 +1100

Thanks for thinking this through David.

I am inclined to agree with your rationale, but I might choose to spell this slightly differently.  While this certainly adds to information we have for authentication (from 0-1 to 4-5!), this does lose something.  In the current design, the server is *required* to cooperate with the entity that generates the original_connection_id transport parameter.  In this, a server can cheat by copying the client's transport parameter.

Maybe it's best to start out with the principles.  We might frame this as authenticating every value that is *chosen* by either endpoint.  There are 4 values that are chosen during the handshake, by when they first appear:

1. The Destination Connection ID in the first Initial from the client.
2. The Source Connection ID in the first Initial from the client.
3. Optionally, the Source Connection ID in the Retry from the server.
4. The Source Connection ID in the first Initial from the server.

That's at most 4 values (not 5), so we have already saved one :)  Values 1 and 3 might influence 4, so you are suggesting that any authentication capture those.  That seems right.  But then we need to determine how best to capture those.

Maybe we don't need to worry about the server cheating on Retry.  The client could include [1, 2], and the server can provide either [3, 4] or just [4] depending on whether Retry was involved.

However, it seems like we could just as easily say that the client provides [2] and the server provides [1, 3, 4] or [1, 4].  In the former,  the server can copy 3 and 4, but it has to cooperate to recover 1; a copy is enough for producing [1, 4].  There are many ways in which we might spell this specifically in terms of transport parameters, but this is probably workable while retaining the anti-cheat property.  

I'm also looking to retain the property where the client doesn't have to change its ClientHello after Retry, in case you hadn't noticed.  It has to re-encrypt, but not rebuild, currently.  That's a nice property, I've found.

On Sat, Mar 7, 2020, at 05:51, David Schinazi wrote:
> Thinking about this some more, I think that forcing the server to 
> change connection IDs doesn't solve all our concerns: if an attacker 
> messes with some CIDs and gets the client to land on a target server, 
> having that server spin up a new CID that lands on the same server 
> doesn't help. Additionally, I'm not a fan of requiring the server to 
> have CIDs on hand, for the reasons described above. I think there is a 
> slight tweak to the proposal that can secure everything: we take MT's 
> new transport parameter and have it contain pretty much all the 
> connection IDs that could be messed with. If we look at both scenarios 
> below, with the current spec requirements, and name the CIDs, we get:
> 
> Handshake Without Retry
> one, followed by both the CIDs that it used in the first INITIAL packet 
> it sent.
> 
> In the handshake without retry case, the client will add (CS1,CD1) in 
> the new TP and the server will add (SS1,CS1).
> In the handshake with retry case, the client will add (CSa,CDa) in the 
> new TP and the server will add (SSa,SSb,CSa). Additionally, the server 
> still sends CDa in existing original_connection_id TP.
> 
> This would ensure that no one but the endpoints can modify connection 
> IDs during the handshake. If a server is concerned about letting the 
> client pick its CID, the server has the opportunity to change it like 
> it does today, but we don't force servers to do it.
> 
> Thoughts?
> David
>

---

From: Antoine Delignat-Lavaud <[email-masked]>
Date: Mon, 9 Mar 2020 10:57:09 +0000

Trying to catch up with the mailing list thread - David's observation is the
same as the one I made on the GitHub issue here
https://github.com/quicwg/base-drafts/issues/3439#issuecomment-595358978 and
is also why I am unconvinced that forcing servers to change source CID in
their initial is not a sufficient countermeasure. In Martin's terminology,
[3] remains unauthenticated, and Mikkel correctly pointed out (on the issue
tracker) that this may enable downgrades if servers configured with the same
token key use different versions. 

The idea to authenticate [1,3,4] in server QTP seems like the best so far,
and for most implementations that correctly implement retry this will not
require much if any change as [1] will already be part of the token for
ODCID TP validation. Including [4] in server TP may seem redundant, but it
actually provides robustness against crazy implementations that may try to
use a malleable CID encoding, such as null byte padding.

Antoine 

-----Original Message-----
From: QUIC <[email-masked]> On Behalf Of Martin Thomson
Sent: 09 March 2020 01:25
To: [email-masked]
Subject: [EXTERNAL] Re: Authenticating connection IDs

I am inclined to agree with your rationale, but I might choose to spell this
slightly differently.  While this certainly adds to information we have for
authentication (from 0-1 to 4-5!), this does lose something.  In the current
design, the server is *required* to cooperate with the entity that generates
the original_connection_id transport parameter.  In this, a server can cheat
by copying the client's transport parameter.

Maybe it's best to start out with the principles.  We might frame this as
authenticating every value that is *chosen* by either endpoint.  There are 4
values that are chosen during the handshake, by when they first appear:

That's at most 4 values (not 5), so we have already saved one :)  Values 1
and 3 might influence 4, so you are suggesting that any authentication
capture those.  That seems right.  But then we need to determine how best to
capture those.

Maybe we don't need to worry about the server cheating on Retry.  The client
could include [1, 2], and the server can provide either [3, 4] or just [4]
depending on whether Retry was involved.

However, it seems like we could just as easily say that the client provides
[2] and the server provides [1, 3, 4] or [1, 4].  In the former,  the server
can copy 3 and 4, but it has to cooperate to recover 1; a copy is enough for
producing [1, 4].  There are many ways in which we might spell this
specifically in terms of transport parameters, but this is probably workable
while retaining the anti-cheat property.  

I'm also looking to retain the property where the client doesn't have to
change its ClientHello after Retry, in case you hadn't noticed.  It has to
re-encrypt, but not rebuild, currently.  That's a nice property, I've found.

On Sat, Mar 7, 2020, at 05:51, David Schinazi wrote:
> The server's new TP contains the source CID from its retry if there 
> was one, followed by both the CIDs that it used in the first INITIAL 
> packet it sent.
> 
> >  > That said, what David is describing is a reasonable deployment 
> > decision  > AFAICT and I don't think we should implicitly discourage 
> > it by making  > it less performant. I'm also not convinced there is 
> > a serious attack  > threat from using client-generated CIDs for 
> > routing but am willing to  > be convinced otherwise.
> > 
> >  1. As proposed. MUST change the CID. This is difficult if CID
generation is not essentially free, as Matt points out.
> >  Note that I don't believe that risk falls exclusively on the server
here. Both endpoints share any risk, so it would be better if there were
ways for each to check the other, but that is not a hard requirement.
> > 
> >  Options 2 and 3 allow the possibility that an attacker sets the
connection ID. Absent Retry, as the client has to use the same value for the
entire handshake and thereafter, we have weak protection for the connection
ID via the AAD on Handshake and 1-RTT packets. We assume that an attacker
can't generate valid packets at those levels, so this should devolve to a
denial of service - those packets can't be processed. However, in option 3,
if the server copies the connection ID after a Retry, there is no such
protection; we have to rely on other measures.
> >  It seems like we are gravitating toward adding a recommendation (i.e.,
SHOULD, not MUST, is my sense from the discussion) that servers authenticate
the connection ID that a client uses when handling an Initial that contains
a Retry token. The server could use a deterministic mapping from the ODCID
or bundle something in the token. If we go with 2 or 3 - and likely
regardless - I'll add that.
> > 
> >  Cheers,
> >  Martin
> > 
> >  p.s., There is another design that might work here: take the token 
> > field out of Initial packets and use the DCID field. Require that 
> > the server use the Retry SCID for a token too. Lift the size limit 
> > on those fields and you have everything a server might need. The 
> > client might send a large DCID in Initial packets after a Retry, but 
> > we repeat the token anyway. Then of course the server has to pick a 
> > new value with its Initial packet because otherwise it would be too 
> > big. The only problem I see is that after an Initial that uses a 
> > token from NEW_TOKEN, if there is a Retry, the ODCID transport 
> > parameter might be a little large. Also, this is a much bigger 
> > change :)
> >

---

From: Martin Duke <[email-masked]>
Date: Mon, 9 Mar 2020 10:17:41 -0700

Are not #2 and #4 (in MT's list) intrinsically authenticated by endpoints
dropping non-Initial packets that don't match a known connection ID?

On Mon, Mar 9, 2020 at 3:58 AM Antoine Delignat-Lavaud <antdl=
[email-masked]> wrote:

> authenticate

---

From: "Martin Thomson" <[email-masked]>
Date: Tue, 10 Mar 2020 11:50:25 +1100

On Tue, Mar 10, 2020, at 04:17, Martin Duke wrote:
> Are not #2 and #4 (in MT's list) intrinsically authenticated by 
> endpoints dropping non-Initial packets that don't match a known 
> connection ID?

The attack in question relies on another weakness, namely that the attacker is able to predict a connection ID that the endpoint is willing to accept.  Now this is a stretch, but if we have weakly authenticated connection IDs and endpoints don't carefully track what they have and have not sent in NEW_CONNECTION_ID, that isn't entirely implausible.

Mostly I see this as a concession to the modularity of security proofs.  Proofs generally prove pieces of the protocol in isolation with minimal assumptions about the properties you get from other pieces, especially properties that don't have proofs of their own.  In this case, as we don't have a proof that dropping packets is effective, that property can't be relied upon when analyzing the record layer construction (to give the example that highlighted this particular weakness).

---

From: Martin Duke <[email-masked]>
Date: Tue, 10 Mar 2020 15:23:43 -0700

Section 5.2.2
<https://quicwg.org/base-drafts/draft-ietf-quic-transport.html#name-server-packet-handling>says
"Servers MUST drop incoming packets under all other circumstances" [i.e.
there is no matching connection ID on a non-Initial, non-0RTT packet]

Let's not have a whole transport parameter to protect weak attacks on
servers that are violating the spec. I am happy to put some text in
Security Considerations if we have to explain 'no really, you MUST drop
them'.

On Mon, Mar 9, 2020 at 5:51 PM Martin Thomson <[email-masked]> wrote:

> The attack in question relies on another weakness, namely that the
> attacker is able to predict a connection ID that the endpoint is willing to
> accept.  Now this is a stretch, but if we have weakly authenticated
> connection IDs and endpoints don't carefully track what they have and have
> not sent in NEW_CONNECTION_ID, that isn't entirely implausible.
>
> Mostly I see this as a concession to the modularity of security proofs.
> Proofs generally prove pieces of the protocol in isolation with minimal
> assumptions about the properties you get from other pieces, especially
> properties that don't have proofs of their own.  In this case, as we don't
> have a proof that dropping packets is effective, that property can't be
> relied upon when analyzing the record layer construction (to give the
> example that highlighted this particular weakness).
>
>

---

From: David Schinazi <[email-masked]>
Date: Tue, 10 Mar 2020 16:38:54 -0700

@MartinDuke I don't think we can dismiss this, the current proposal allows
MITM attackers to silently replace CIDs that we thought only the endpoints
could pick, so we should fix that. It'll make this protocol easier to
analyze if we can assume that all values are guaranteed to be picked only
by the two endpoints and collaborating load balancer (with that
collaboration cryptographically enforced).

I agree with MT's comments.
I overlooked the fact that the server needs to recover
original_connection_id from the retry token so we can't include CD1/CDa/(1)
in the client's TPs.
(I'm also working with the requirement that the client sends the same
ClientHello after a RETRY)
The natural solution would then be to not have the client send anything
new, and only add a TP on the server that contains all of the CIDs
discussed above.
We can bikeshed on how to encode that TP - we can either build something
backwards compatible, or we can replace original_connection_id and have
something clean.

David

---

From: Martin Duke <[email-masked]>
Date: Tue, 10 Mar 2020 16:51:44 -0700

Hi David,

I should be clearer.

I agree that we should mitigate the possibility of MITM rewriting the SCID
of a Retry packet.

However, ISTM that a compliant server is NOT vulnerable to rewriting the
SCID of server initial. The server already MUST drop handshake and 1rtt
packets with CIDs it did not propose.

I am open to different solutions for the first. My preference would be for
either (a) encoding the SCID in the token, or (b) "servers MUST propose a
new CID in the Initial if they processed a valid retry token." But convince
me otherwise!

---

From: "Martin Thomson" <[email-masked]>
Date: Wed, 11 Mar 2020 13:00:19 +1100

Top-posting with an update.

I have updated the PR with a design based on the discussion here.  Thanks everyone for your input.

https://github.com/quicwg/base-drafts/pull/3499 

Regarding the trade-off that we are now faced with...

I realize that making concessions in the design to better facilitate formal analysis is new to some people, but that is what this is.  We did that with TLS and it was similarly difficult.  At the time my own intuition was that the protocol was sound and the request was pretty awkward.  But I now understand a little more about the process and realize that the request was reasonable.

I don't believe that there is a concrete attack that this change addresses, but my belief is that it will greatly improve the simplicity, and therefore the reliability and availability, of security proofs for QUIC.  The message at QUIPS was pretty clear: proofs are much more difficult and brittle when we rely on indirect methods to provide security properties.

To me the cost here is small.  It's a few extra bytes and a few extra checks.

On Thu, Mar 5, 2020, at 14:23, Martin Thomson wrote:
> First, please read 
> https://github.com/quicwg/base-drafts/issues/3439#issuecomment-594320754 for background.  The tl;dr is that there are some cases in which an attacker is able to choose the connection ID that is negotiated during the handshake.
> 
> 1. include the SCID from Initial packets in a transport parameter that 
> is authenticated after the handshake completes
> 
> worthwhile goal.  The cost is that this complicates the logic for 
> clients marginally.  It was also observed that servers need to be able 
> to generate new connection IDs anyway, which challenges the difficulty 
> aspect here a little. I think that it only invalidates a subset of 
> connection ID generation methods if you care about performance, but am 
> open to being convinced otherwise.
> 
> permitted to use values from NEW_CONNECTION_ID frames in 0.5-RTT 
> packets (similarly for 0-RTT at the server).  My understanding is that 
> this might affect formal verification though.
> 
> No matter which outcome we choose, the effect that this would have on 
> any formal verification that has happened is probably the key 
> consideration for me.  This came out of research that Antoine and 
> others did on formally verifying QUIC and this was identified as one of 
> the few weaknesses in the record layer design.  Removing this style of 
> weakness and making proofs simpler was something that contributed to 
> the success of TLS 1.3.  In my view, whatever we can do here to the 
> same end is worth doing.
> 
> This is one of our last (!) transport issues of any real substance, and 
> I think that it's worth trying to work toward a resolution here.  
> Personally, I don't have strong opinions about either except to say 
> that I would vastly prefer an imperfect solution that we can ship now 
> with some amount of confidence in (i.e., one that wasted bytes on a 
> transport parameter) over any extended debate.
>

---

From: David Schinazi <[email-masked]>
Date: Tue, 10 Mar 2020 19:11:16 -0700

I support the latest PR from MT (PR #3499 as of commit 2fc5157). I think
this proposal is clean, minimally intrusive, doesn't require us to change
our server CID management scheme, and achieves the stated goal of
simplifying formal security proofs. Thanks for doing this, MT.

David

On Tue, Mar 10, 2020 at 7:00 PM Martin Thomson <[email-masked]> wrote:

> I realize that making concessions in the design to better facilitate
> formal analysis is new to some people, but that is what this is.  We did
> that with TLS and it was similarly difficult.  At the time my own intuition
> was that the protocol was sound and the request was pretty awkward.  But I
> now understand a little more about the process and realize that the request
> was reasonable.
>
> I don't believe that there is a concrete attack that this change
> addresses, but my belief is that it will greatly improve the simplicity,
> and therefore the reliability and availability, of security proofs for
> QUIC.  The message at QUIPS was pretty clear: proofs are much more
> difficult and brittle when we rely on indirect methods to provide security
> properties.
>

---

From: Marten Seemann <[email-masked]>
Date: Wed, 11 Mar 2020 10:41:28 +0700

I agree with Martin Duke. The rewriting of the Retry CID seems to be worth
solving, but as I've pointed out on the issue about a week ago, dropping
packets with an unexpected CID should be both sufficient and a way more
elegant solution than another TP (plus the additional validation logic that
comes with it). I find the argument "potentially it might make proofs
easier" a bit too vague to justify adding a double layer of protection
against this attack.

---

From: Christian Huitema <[email-masked]>
Date: Tue, 10 Mar 2020 22:30:35 -0700

> I don't believe that there is a concrete attack that this change addresses, but my belief is that it will greatly improve the simplicity, and therefore the reliability and availability, of security…

Actually, there is at least one plausible attack, botnet vs server farm.
Assume botnet is not powerful enough to overload the whole farm, but
could inflict damage on specific server. Elements of the botnet can:

1) Do a connection attempt.

2) Receive a retry packet from the DOS protection box, in which the SCID
points at other segments of the farm

3) Do a connection retry but use a DCID targeting a selected subset of
the farm.

4) The DOS box sees a valid token, correctly linked to a source address,
and let the Initial pass

5) Elements of botnet repeat the process. Fraction of the farm is
overwhelmed. Service experiences partial failure.

-- Christian Huitema

---

From: "Martin Thomson" <[email-masked]>
Date: Wed, 11 Mar 2020 16:38:44 +1100

> could inflict damage on specific server. Elements of the botnet can:

Isn't it possible with authenticated connection IDs also?  You assume that the botnet can recognize which values steer to the same server nodes.  Can't they make a bunch of partial connection attempts and hold back completion of those except the ones that hit the chosen node?

This also seems to assume that connection attempts are less expensive than whatever the server does thereafter and that handshakes aren't separately protected.  Or that partially-completed handshakes are not subject to further throttling at the target node.

In any case, that seems like a generic attack capability.

---

From: Christian Huitema <[email-masked]>
Date: Tue, 10 Mar 2020 22:52:19 -0700

> Isn't it possible with authenticated connection IDs also?  You assume that the botnet can recognize which values steer to the same server nodes.  Can't they make a bunch of partial connection attem…

Bunch of connection attempts and holding would kind of work, but is not
as focused.

> This also seems to assume that connection attempts are less expensive than whatever the server does thereafter and that handshakes aren't separately protected.  Or that partially-completed handshak…
The botnet does not actually need to keep connections attempts
"partial". Elements could just as well complete the connection. The old
BLASTER worm was doing just that, have each bot spin a number of
parallel threads and in each thread loop on something like "get
http://target.example.com/". That was 17 years ago, so I expect that bot
technology has progressed.
> In any case, that seems like a generic attack capability.

I think the ability to focus is interesting. But then, I am not in the
business of writing better botnets...

-- Christian Huitema