Subject: How does a server identify a new connection?

From: Kazuho Oku <[email-masked]>
Date: Thu, 29 Nov 2018 11:30:51 +0900

So far, we have been trying to spend reasonable effort to prevent
man-on-the-side attacks.

Specifically, PR #2045 (Discard Initial keys as soon as possible) is
an attempt to prevent that during the handshake.

Assuming that we adopt the PR, client's complexity of avoiding a
man-on-the-side attack becomes O(M*N) where M is the number of
server's Initial packets (assuming that ServerHello fits in one packet
and HRR is not involved) and N is the number of packets being received
[1].

However, there still exists an attack vector. The attacker can target
the server instead, racing an Initial packet. If the attacker's
Initial (that contain a different ClientHello) reaches the server
before the one sent by the client, the TLS handshake would fail,
assuming that the server considers those two Initial packets to be
belonging to the same connection.

The question is if (and how) we can prevent that from happening.

One way that might work is to use H(SCIDL || DCIDL || SCID || DCID ||
ClientHello) of the Initial packet where H is a cryptographic hash
function to identify each connection establishment attempt. In
practice, a server would remember this value for each connection, and
if the value differs from a known value, creates a new connection
context and responds with an Initial that contains a new Server CID
(even if the 5-tuple and Client's CID is identical to an existing
connection).

Does this sound sufficient to avoid the man-on-the-side attack
targeting the server racing Initial packets? Is there a better way?
Should we describe this type of construction in the drafts?

[1] https://docs.google.com/document/d/1fRsJqPinJl8N3b-bflDRV6auojfJLkxddT93j6SwHY8/edit
section 3.4

-- 
Kazuho Oku

---

From: Martin Thomson <[email-masked]>
Date: Thu, 29 Nov 2018 13:37:17 +1100

Put more simply, servers can accept multiple connections on the same
address tuple.  I don't see why not.  Of course, this still depends on
the client doing the disambiguation, because it will see the same
connection ID for multiple connections.

---

From: Kazuho Oku <[email-masked]>
Date: Thu, 29 Nov 2018 11:41:32 +0900

2018年11月29日(木) 11:37 Martin Thomson <[email-masked]>:
> address tuple.  I don't see why not.

The question is what happens if a man-on-the-side attacker races an
Initial packet with the same 5-tuple, same SCID / DCID, but having
different values in other fields.

Unless the server uses something other than 5-tuple, SCID, DCID, the
legitimate packet and the spoofed packet would look like that they
belong to the same connection. Then, if the spoofed packets reaches
the server first, the connection establishment would fail.

> Of course, this still depends on

-- 
Kazuho Oku

---

From: Martin Thomson <[email-masked]>
Date: Thu, 29 Nov 2018 13:50:39 +1100

> different values in other fields.

Yep, can't guarantee a win here.  So that makes me inclined to say
that we don't put it in the draft.  If it turns out to be useful, we
can regret it later, but writing down a defense that doesn't really
work that well doesn't seem right.

---

From: Kazuho Oku <[email-masked]>
Date: Thu, 29 Nov 2018 12:01:36 +0900

2018年11月29日(木) 11:50 Martin Thomson <[email-masked]>:
> Yep, can't guarantee a win here.

My proposal is that we _can_ guarantee a win, if we use a hash value
derived from ClientHello as an identifier of a connection attempt.

This is because ClientHello is the only thing that could be different
to cause a connection establishment attempt to fail, assuming that we
adopt PR #2045.

> So that makes me inclined to say

-- 
Kazuho Oku

---

From: Martin Thomson <[email-masked]>
Date: Thu, 29 Nov 2018 14:09:11 +1100

> derived from ClientHello as an identifier of a connection attempt.

Oh, I see now.  Why do you need to describe an identifier at all?
Just make two connections (and use your own connection IDs to identify
them).  No hashing needed.

---

From: Mikkel Fahnøe Jørgensen <[email-masked]>
Date: Thu, 29 Nov 2018 00:19:05 -0800

The connection could also fail later on mismatching TP values when
handshake completes AFAIR.
Otherwise it should, since an attacker to race an initial and forge TP’s.

The server could use the original AEAD tag instead of the original CID to
identity the connection.

On 29 November 2018 at 04.02.04, Kazuho Oku ([email-masked]) wrote:

---

From: Kazuho Oku <[email-masked]>
Date: Thu, 29 Nov 2018 18:35:32 +0900

2018/11/29 17:19、Mikkel Fahnøe Jørgensen <[email-masked]>のメール:

> The connection could also fail later on mismatching TP values when handshake completes AFAIR.

TP is part of the ClientHello, therefore my understanding is that just checking the equivalence of ClientHello is sufficient.

> 
> The server could use the original AEAD tag instead of the original CID to identity the connection.

You cannot use the AEAD tag, because it changes when the client retransmits an Initial containing the same ClientHello due to PN being incremented.

---

From: Mikkel Fahnøe Jørgensen <[email-masked]>
Date: Thu, 29 Nov 2018 01:39:25 -0800

You cannot use the AEAD tag, because it changes when the client retransmits
an Initial containing the same ClientHello due to PN being incremented.

But why do we do that?

---

From: Kazuho Oku <[email-masked]>
Date: Thu, 29 Nov 2018 19:05:16 +0900

>> You cannot use the AEAD tag, because it changes when the client retransmits an Initial containing the same ClientHello due to PN being incremented.

So that the client can figure out the correct RTT. If the sever is far away, a client might retransmit an Initial containing ClientHello before it receives the response for the first one.

---

From: Mikkel Fahnøe Jørgensen <[email-masked]>
Date: Thu, 29 Nov 2018 02:15:31 -0800

But why do we do that?

So that the client can figure out the correct RTT. If the sever is far
away, a client might retransmit an Initial containing ClientHello before it
receives the response for the first one.

Not a big deal, just wondering:

If we get this early semi-implicit ACK merged, I presume no ACK will
arrive, and the servers first response would not reflect the PN of the
initial either. Wouldn’t it be better to do a new connection instead of
retransmission (I think some github issue is currently discussing this).

---

From: "Lubashev, Igor" <[email-masked]>
Date: Thu, 29 Nov 2018 15:53:24 +0000

A simpler way would be making Client Initial CID be not just a random string of bits but a hash of the rest of the CI packet.

If the H(CI) is not included in the server's initial, how does the client know which of the SI packets is a reply to the attacker's CI and which is a reply to client's own CI?

- Igor

> -----Original Message-----
> From: Kazuho Oku <[email-masked]>
> Sent: Wednesday, November 28, 2018 10:02 PM
> To: Martin Thomson <[email-masked]>
> Cc: IETF QUIC WG <[email-masked]>
> Subject: Re: How does a server identify a new connection?
> 
> 2018年11月29日(木) 11:50 Martin Thomson <[email-masked]>:
> >
> My proposal is that we _can_ guarantee a win, if we use a hash value derived
> from ClientHello as an identifier of a connection attempt.
> 
> This is because ClientHello is the only thing that could be different to cause a
> connection establishment attempt to fail, assuming that we adopt PR #2045.
>

---

From: Mike Bishop <[email-masked]>
Date: Thu, 29 Nov 2018 19:06:58 +0000

The layering on using CH is problematic.  If the server is supposed to ignore the attacker's packet, that implies that it pre-parses the contents of the Initial into the TLS data before deciding whether to actually injest the packet.  I don't think a productive solution lies there.  At the same time, I agree it would be nice to be able to protect against these attacks, iff we can find a straightforward way.  I think some of the ideas here are heading in the right direction.

IIUC, the attack is that the attacker races an Initial containing a different ClientHello, some DCID (maybe same as client’s, maybe different), the same SCID as the client (easy if the client uses zero-length), and spoofs the client’s source IP:port.

Then:

  *   If attacker uses same DCID as client but modifies the ClientHello, server can discard the packet without processing it and await the real packet
  *   If attacker uses different CID from client, server sees it as a separate connection attempt; client can identify and discard these packets (even if it used a zero-length SCID).

With no shared context, this is a challenging problem.  Handshake packets will already have this property – decryption will fail and they’ll get dropped if it’s in response to the attacker’s Initial.  But if the Initial packet received from the server was responsive to the attacker, the client will generate the wrong Handshake key and drop the real Handshake packets as well, so the attack succeeds.

If the server were to reflect back something to uniquely identify the Initial that it received, the client could discard responses to the attacker and wait for the response to its own message.  As Mikkel suggests, the authentication tag might work here, which would give us the second property.  If clients retransmit with different packet numbers, they simply remember multiple outstanding tags.  A sufficiently unique SCID is a weaker defense, but still requires the attacker to see the real packet before crafting the false one.

For the first property, Igor’s idea seems sensible.  If the initial DCID were a hash of the unencrypted packet payload, that doesn’t require interpreting the ClientHello, just the bytes at the transport.  Then the server would accept Initials with either this property or a valid token from a Retry.

HRR makes that more difficult; perhaps the client’s second Initial similarly includes proof / identification of which server Initial it’s responding to.

Of course, if clients just always used a non-zero-length SCID, this attack would be less likely to work.  Maybe the simpler change is to require a non-zero-length SCID during the handshake, then provide a way to switch to a zero-length CID post-handshake?  It doesn’t close the door as effectively, but it makes the attack harder and is a much smaller change this late in the process.

-----Original Message-----
From: QUIC <[email-masked]> On Behalf Of Lubashev, Igor
Sent: Thursday, November 29, 2018 7:53 AM
To: Kazuho Oku <[email-masked]>; Martin Thomson <[email-masked]>
Cc: IETF QUIC WG <[email-masked]>
Subject: RE: How does a server identify a new connection?

- Igor

> From: Kazuho Oku <[email-masked]<mailto:[email-masked]>>

> To: Martin Thomson <[email-masked]<mailto:[email-masked]>>

> Cc: IETF QUIC WG <[email-masked]<mailto:[email-masked]>>

> 2018年11月29日(木) 11:50 Martin Thomson <[email-masked]<mailto:[email-masked]>>:

> > On Thu, Nov 29, 2018 at 1:41 PM Kazuho Oku <[email-masked]<mailto:[email-masked]>>

> wrote:

> > > The question is what happens if a man-on-the-side attacker races

> > > an Initial packet with the same 5-tuple, same SCID / DCID, but

> > > having different values in other fields.

> to cause a connection establishment attempt to fail, assuming that we adopt PR #2045.

---

From: Christian Huitema <[email-masked]>
Date: Thu, 29 Nov 2018 12:39:04 -0800

On 11/29/2018 11:06 AM, Mike Bishop wrote:

> For the first property, Igor’s idea seems sensible.  If the initial
> DCID were a hash of the unencrypted packet payload, that doesn’t
> require interpreting the ClientHello, just the bytes at the
> transport.  Then the server would accept Initials with either this
> property or a valid token from a Retry.

This is making the assumption that if the client repeats an Initial
packet, the content will be exactly the same. I know that this is false
in at least one case: the first UDP packet contains a short Initial
packet coalesced with a 0-RTT packet; the repeated Initial packet
contains a long Initial packet, padded up to the required length.

If you want to make that work, you want the DCID to be a hash of the
crypto frame inside the Initial packet. But I don't understand very well
how that's supposed to be verified by the server. Do we want to specify
a default hash algorithm?

-- Christian Huitema

---

From: "Lubashev, Igor" <[email-masked]>
Date: Thu, 29 Nov 2018 21:36:20 +0000

> From: Christian Huitema <[email-masked]>
> 
> > require interpreting the ClientHello, just the bytes at the transport.
> > Then the server would accept Initials with either this property or a
> > valid token from a Retry.
> 
> This is making the assumption that if the client repeats an Initial packet, the
> content will be exactly the same. I know that this is false in at least one case:
> the first UDP packet contains a short Initial packet coalesced with a 0-RTT
> packet; the repeated Initial packet contains a long Initial packet, padded up
> to the required length.
> 
> If you want to make that work, you want the DCID to be a hash of the crypto
> frame inside the Initial packet.

I am not sure I see why the coalesced packet matters, since the protection is for the integrity of the Initial QUIC packet only (not the entire UDP datagram).  It seems to be better to protect the entire packet and not just the crypto frame(s).

> But I don't understand very well how that's
> supposed to be verified by the server. Do we want to specify a default hash
> algorithm?

The server would need to know the algorithm used.  Any cryptographic hash function would do, but it would need to be specified.

The downside, of course, is another case of multi-path encryption: plaintext -> DCID -> initial packet encryption.

- Igor

---

From: Christian Huitema <[email-masked]>
Date: Thu, 29 Nov 2018 13:57:00 -0800

> On Nov 29, 2018, at 1:36 PM, Lubashev, Igor <[email-masked]> wrote:
> 

We want to obtain the same hash for the first initial and for a retransmit, but the is no guarantee that the content is exactly the same. The amount of padding may differ, in which case the hash of the content will differ. Because of that, hashing of the whole content is error prone.

---

From: "Lubashev, Igor" <[email-masked]>
Date: Thu, 29 Nov 2018 22:16:43 +0000

> > I am not sure I see why the coalesced packet matters, since the protection
> is for the integrity of the Initial QUIC packet only (not the entire UDP
> datagram).  It seems to be better to protect the entire packet and not just
> the crypto frame(s).
> 
> We want to obtain the same hash for the first initial and for a retransmit, but
> the is no guarantee that the content is exactly the same. The amount of
> padding may differ, in which case the hash of the content will differ. Because
> of that, hashing of the whole content is error prone.

Padding.  Got it.  Thanks.

---

From: Kazuho Oku <[email-masked]>
Date: Fri, 30 Nov 2018 09:27:34 +0900

> I am not sure I see why the coalesced packet matters, since the protection is for the integrity of the Initial QUIC packet only (not the entire UDP datagram).  It seems to be better to protect the…

In addition to PADDING and PN being different, the content of the
CRYPTO frame will be different for the 2nd ClientHello when HRR is
involved.

Therefore, distinguishing different handshake contexts need to be done
using the CRYPTO frame of the first Initial (which is the first
ClientHello message).

> The downside, of course, is another case of multi-path encryption: plaintext -> DCID -> initial packet encryption.

The approach does not help the client, because a middlebox can spoof
the server's Initial packet. A client needs to collect all the Initial
packets it receives, and determine which one was correct. This is why
the complexity is O(N * M) on the client side, as I pointed out in the
mail that started this thread.

-- 
Kazuho Oku

---

From: Kazuho Oku <[email-masked]>
Date: Fri, 30 Nov 2018 10:49:28 +0900

I've submitted a PR that implements the proposed approach.

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

-- 
Kazuho Oku

---

From: Dmitri Tikhonov <[email-masked]>
Date: Fri, 30 Nov 2018 10:37:35 -0500

> different values in other fields.

Is such attack feasible?  By definition, the man-on-the-side cannot
delay the original packet.  For the spoofed packet to reach the
server first, the man-on-the-side would have to have access to a
different, faster path to that server.

How do other transport protocols mitigate such attacks, if at all?

I am asking these questions a) out of ignorance and b) as the
implications of the proposed change (PR 2076) begin to dawn on me.

  - Dmitri.

---

From: Christian Huitema <[email-masked]>
Date: Fri, 30 Nov 2018 08:08:14 -0800

> On Nov 30, 2018, at 7:37 AM, Dmitri Tikhonov <[email-masked]> wrote:
> 

Non only feasible, but in actual use now. Do for example a search for "Quantum Insert".

> How do other transport protocols mitigate such attacks, if at all?

The only plausible defense now is to run over IPSEC or a VPN. TLS over TCP is vulnerable to TCP level attacks.

> implications of the proposed change (PR 2076) begin to dawn on me.

Defending against inserts after the handshake is relatively easy and everybody should do it. Defending the initial handshake involves speculative initiation of many connection copies, and then rolling back the bad ones once a good one was verified. So, yes, it is costly.

Kazuho's PR changes the equation from very costly to doable. In particular, the idea of tying the initial CID to the Client Hello greatly reduces the cost of the defense on the server side, and does not burden clients much. There is still some heavy work to do to client side to fully complete the defense, but the cost is only borne by those clients who want the defense.

-- Christian Huitema

---

From: Dmitri Tikhonov <[email-masked]>
Date: Fri, 30 Nov 2018 11:44:41 -0500

> Non only feasible, but in actual use now. Do for example a search

The fundamental difference between the attack described in this thread
and Quantum Insert [1] is that in our (the former) case, the attacker
must spoof the very first Initial packet.  This makes it less likely
(I am guessing a lot less likely) for the spoofed packet to win the race
with the original.  I remain unconvinced (pleading ignorance again) that
such attack is feasible.

> Defending against inserts after the handshake is relatively easy
> and everybody should do it. Defending the initial handshake involves
> speculative initiation of many connection copies, and then rolling
> back the bad ones once a good one was verified. So, yes, it is costly.

This realization is what prompted my email.

  - Dmitri.

1. https://blog.fox-it.com/2015/04/20/deep-dive-into-quantum-insert/