Subject: Re: How does a server identify a new connection?

From: Kazuho Oku <[email-masked]>
Date: Mon, 3 Dec 2018 10:15:13 +0900

2018年12月1日(土) 1:44 Dmitri Tikhonov <[email-masked]>:
>
> On Fri, Nov 30, 2018 at 08:08:14AM -0800, Christian Huitema wrote:
> > > On Nov 30, 2018, at 7:37 AM, Dmitri Tikhonov <[email-masked]> wrote:
> > > 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.
> >
> > Non only feasible, but in actual use now. Do for example a search
> > for "Quantum Insert".
>
> 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.
>
> > > 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.
> >
> > 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.

How high the "cost" is depends on who you are.

If you are running a client that is struggling to create a connection,
I do not think testing 10 ServerHellos you receive to identify which
one was correct is something you can pay for. It's essentially an
automatic and safer way of hitting the reload button.

OTOH, the cost is a big issue for the server, because it needs to pay
the cost for every connection attempt it accepts.

Therefore, a strategy that puts the most cost of detecting an
mitigating man-on-the-side attacks on the client-side is a good
approach.

The minimum requirement we need to have for the server is: 1) call
different ClientHellos as different connections 2) ignore (or delay
the application of) other information carried in Initial packet that
has fatal effect on connection establishment.

I can understand that some might not want to implement such behavior.
However, I think it is beneficial to document how you could build a
man-on-the-side attack resistance server, because that would help
people actually implement such servers.

Then, we can give clients that actually see the problem the chance to
implement the costly countermeasure.

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

-- 
Kazuho Oku

---

From: Dmitri Tikhonov <[email-masked]>
Date: Sun, 2 Dec 2018 22:14:31 -0500

> > with the original.  I remain unconvinced (pleading ignorance again) that

[...]

> If you are running a client that is struggling to create a connection,

Why is the client struggling?  In other words, what attack are we
defending against?  Is this a real attack -- an adversary racing
against the very first client packet -- or a theoretical attack?

  - Dmitri.

---

From: Kazuho Oku <[email-masked]>
Date: Mon, 3 Dec 2018 13:17:06 +0900

> against the very first client packet -- or a theoretical attack?

I am not sure if the question is good way to consider how QUIC will be
attacked, because the security properties (and therefore the attack
vectors) of QUIC is different from that of TCP (that optionally have
used TLS older than 1.3).

Having that said, what we know is that 1) man-on-the-side reset
injection is a common technique, and 2) it is often coupled with
packet payload inspection [1].

With TLS 1.3, the only remaining way for a middlebox to inspect the
payload of a packet in practice is to look at the SNI of the
ClientHello. With QUIC, injection during the exchange of Initial
packets would be the only way for a man-on-the-side attacker to
disrupt the connection (assuming that we address the issue with
spoofing path challenges / responses).

Considering that, I would assume that racing a spoofed Initial to the
server will be one of the vectors to be considered by the attackers,
and therefore it's worth considering, documenting and encouraging
implementations to have the countermeasures.

[1] https://tools.ietf.org/html/draft-hall-censorship-tech-06

-- 
Kazuho Oku

---

From: Dmitri Tikhonov <[email-masked]>
Date: Mon, 3 Dec 2018 08:56:31 -0500

> used TLS older than 1.3).

The question is asked in order to understand whether the proposed
defense mechanism is reasonable to implement.  The implementation
cost on the server is high given that the attack does not exist.

> packet payload inspection [1].

The reset injection attack described in the referred paper (Section
4.2.3) injects RST packets into an-already established connection.
Both in this and in the Quantum Insert scenarios the injected
packets do not have to race the legitimate packet(s) that were used
to construct them.  This seems like an impossible problem for the
man-on-the-side to solve.

> implementations to have the countermeasures.

I agree that it's worth considering.  I have been wanting to see how
this vector could be used for an attack by the man-on-the-side, but
no explanation has been put forth so far.

  - Dmitri.

---

From: Mikkel Fahnøe Jørgensen <[email-masked]>
Date: Mon, 3 Dec 2018 09:32:58 -0500

It ought not be that difficult to race packets. I know someone who measured
a cross Atlantic datacenter to datacenter vs public network to same
location.
It was 30ms faster on the internal network. It might have been RTT in which
case a packet race it is still 15ms faster.

So if you have good connectivity it is viable to race packets over longer
distances.

On 3 December 2018 at 14.56.54, Dmitri Tikhonov ([email-masked])
wrote:

- Dmitri.

---

From: Mikkel Fahnøe Jørgensen <[email-masked]>
Date: Mon, 3 Dec 2018 09:44:13 -0500

An attacker might be able to force a slower packet route by misleading
backplane routers.

There is also connectivity to the Moon, Mars and deep space to consider.
I’m not sure if QUIC can handle the level of latency though.

On 3 December 2018 at 15.32.58, Mikkel Fahnøe Jørgensen ([email-masked])
wrote:

- Dmitri.

---

From: Chuck Crisler <[email-masked]>
Date: Mon, 3 Dec 2018 15:55:17 +0000

For transmission to the Moon, Mars and deep space you use really good FEC. 😊

________________________________
From: QUIC <[email-masked]> on behalf of Mikkel Fahnøe Jørgensen <[email-masked]>
Sent: Monday, December 3, 2018 9:44:13 AM
To: Kazuho Oku; Dmitri Tikhonov
Cc: Christian Huitema; IETF QUIC WG; Martin Thomson
Subject: Re: How does a server identify a new connection?

An attacker might be able to force a slower packet route by misleading backplane routers.

There is also connectivity to the Moon, Mars and deep space to consider. I’m not sure if QUIC can handle the level of latency though.

On 3 December 2018 at 15.32.58, Mikkel Fahnøe Jørgensen ([email-masked]<mailto:[email-masked]>) wrote:

It ought not be that difficult to race packets. I know someone who measured a cross Atlantic datacenter to datacenter vs public network to same location.
It was 30ms faster on the internal network. It might have been RTT in which case a packet race it is still 15ms faster.

So if you have good connectivity it is viable to race packets over longer distances.

On 3 December 2018 at 14.56.54, Dmitri Tikhonov ([email-masked]<mailto:[email-masked]>) wrote:

On Mon, Dec 03, 2018 at 01:17:06PM +0900, Kazuho Oku wrote:
> 2018年12月3日(月) 12:14 Dmitri Tikhonov <[email-masked]<mailto:[email-masked]>>:

- Dmitri.

---

From: Mikkel Fahnøe Jørgensen <[email-masked]>
Date: Mon, 3 Dec 2018 11:08:44 -0500

On 3 December 2018 at 16.55.22, Chuck Crisler (
[email-masked]) wrote:

For transmission to the Moon, Mars and deep space you use really good FEC.

That’s layer 2.

---

From: Christian Huitema <[email-masked]>
Date: Mon, 3 Dec 2018 11:17:24 -0800

On 12/3/2018 8:08 AM, Mikkel Fahnøe Jørgensen wrote:

>
> On 3 December 2018 at 16.55.22, Chuck Crisler
> ([email-masked]
> <mailto:[email-masked]>) wrote:
>

You could implement FEC at any layer, and there are examples of using it
at the link, transport and application layers. But let's come back to
Dmitri's original question about the urgency of protecting against one
or another kind of attacks. Compare these two attacks:

1) Attacker races a competing Client Hello packet:

    a- Attacker obtains a copy of the client hello

    b- Attacker formats a competing client hello

    c- server receives a client hello from attacker

    d- server receives a client hello from client

    Attack may succeed if "c" happens before "d".

2) Attacker races a competing Server hello:

   a - Attacker obtains a copy of the client hello

    b- Attacker formats a competing server response

    c- Server receives the client hello

    d- Server sends the server hello

    e- Client receives the server response from attacker

    f- Client receives the server hello from server

    Attack may succeed if "e" happens before "f"

If I was in charge of engineering at "attackers Inc.", I would place
more bets on the second attack succeeding than on the first one. The
path from attacker to client can easily be shorter than the path from
server to client, and the path from observation point to attacker may
also be shorter than the path from observation point to server. In
contrast, in the first variant, the attacker has to ensure that the sum
of the paths from observation point to attacker and from attacker to
server is shorter than the path from observation point to attacker,
which seems to violate a triangle inequality. Violating that is not
impossible but it requires pretty hard engineering, while the second
variant is much simpler to implement.

In the second variant, the attacker does not need to send a "server
hello" message. It may send a "server busy" response, causing the
connection to fail. It may also send a stateless retry, or an HRR. That
will drive the client connection in a weird state, causing it to fail
eventually. The fake "server busy" will be quite similar to a fake TCP
RST. That would be my first attack design if I was in charge of
engineering at "attackers Inc."

In fact, with Kazuho's proposed defense, the first attack devolves to
the a variant of the second one. The server will create two contexts and
send two server hellos, even if the attackers hello arrives after the
client hello. The client's defense will only succeed if it is ready to
process several independent responses to its Initial Client Hello, and
wait for the first one that produces a valid "server finished" message
-- same defense as against the second attack.

I think Kazuho's PR should be reformatted to a discussion of "attacks
during the Initial exchange", describing both the server side and the
client side attack. His proposed defense makes sense on the server side
and is relatively easy to implement, but it does not achieve much
without the corresponding defenses on the client side; these client
defense are required in any case, because the direct attack against the
client is easier to mount than the attack through the server.

I am also concerned that the actual server side defense is more complex
than expected. It only works well if the server accepts exactly one
message from the client -- I would dub that the "atomic hello"
variation. That requires a series of modification to the initial
handshake, such as treating HRR as some kind of error message, perhaps
carrying an HRR token of sort, and mandating that the initial message
only contains a single crypto frame, nothing else, in both directions.
No ACK, no connection close, nothing state changing -- all that should
only be allowed in handshake-protected message. Frankly, I don't see how
we can specify that in time for V1.

-- Christian Huitema

---

From: Mikkel Fahnøe Jørgensen <[email-masked]>
Date: Mon, 3 Dec 2018 14:42:13 -0500

Good analysis.

I think atomic hello sounds compelling even if post v1. Separating out HRR
as an error case is also in interesting, though it might open new attack
vectors.

On 3 December 2018 at 20.17.38, Christian Huitema ([email-masked])
wrote:

That’s layer 2.

You could implement FEC at any layer, and there are examples of using it at
the link, transport and application layers. But let's come back to Dmitri's
original question about the urgency of protecting against one or another
kind of attacks. Compare these two attacks:

If I was in charge of engineering at "attackers Inc.", I would place more
bets on the second attack succeeding than on the first one. The path from
attacker to client can easily be shorter than the path from server to
client, and the path from observation point to attacker may also be shorter
than the path from observation point to server. In contrast, in the first
variant, the attacker has to ensure that the sum of the paths from
observation point to attacker and from attacker to server is shorter than
the path from observation point to attacker, which seems to violate a
triangle inequality. Violating that is not impossible but it requires
pretty hard engineering, while the second variant is much simpler to
implement.

In the second variant, the attacker does not need to send a "server hello"
message. It may send a "server busy" response, causing the connection to
fail. It may also send a stateless retry, or an HRR. That will drive the
client connection in a weird state, causing it to fail eventually. The fake
"server busy" will be quite similar to a fake TCP RST. That would be my
first attack design if I was in charge of engineering at "attackers Inc."

In fact, with Kazuho's proposed defense, the first attack devolves to the a
variant of the second one. The server will create two contexts and send two
server hellos, even if the attackers hello arrives after the client hello.
The client's defense will only succeed if it is ready to process several
independent responses to its Initial Client Hello, and wait for the first
one that produces a valid "server finished" message -- same defense as
against the second attack.

I think Kazuho's PR should be reformatted to a discussion of "attacks
during the Initial exchange", describing both the server side and the
client side attack. His proposed defense makes sense on the server side and
is relatively easy to implement, but it does not achieve much without the
corresponding defenses on the client side; these client defense are
required in any case, because the direct attack against the client is
easier to mount than the attack through the server.

I am also concerned that the actual server side defense is more complex
than expected. It only works well if the server accepts exactly one message
from the client -- I would dub that the "atomic hello" variation. That
requires a series of modification to the initial handshake, such as
treating HRR as some kind of error message, perhaps carrying an HRR token
of sort, and mandating that the initial message only contains a single
crypto frame, nothing else, in both directions. No ACK, no connection
close, nothing state changing -- all that should only be allowed in
handshake-protected message. Frankly, I don't see how we can specify that
in time for V1.

-- Christian Huitema

---

From: Kazuho Oku <[email-masked]>
Date: Tue, 4 Dec 2018 10:23:11 +0900

Hi Christian,

Thank you for the analysis. My responses inline.

2018年12月4日(火) 4:17 Christian Huitema <[email-masked]>:
> On 3 December 2018 at 16.55.22, Chuck Crisler ([email-masked]) wrote:
>
> You could implement FEC at any layer, and there are examples of using it at the link, transport and application layers. But let's come back to Dmitri's original question about the urgency of protecting against one or another kind of attacks. Compare these two attacks:
>
> If I was in charge of engineering at "attackers Inc.", I would place more bets on the second attack succeeding than on the first one. The path from attacker to client can easily be shorter than the path from server to client, and the path from observation point to attacker may also be shorter than the path from observation point to server. In contrast, in the first variant, the attacker has to ensure that the sum of the paths from observation point to attacker and from attacker to server is shorter than the path from observation point to attacker, which seems to violate a triangle inequality. Violating that is not impossible but it requires pretty hard engineering, while the second variant is much simpler to implement.
>
> In the second variant, the attacker does not need to send a "server hello" message. It may send a "server busy" response, causing the connection to fail. It may also send a stateless retry, or an HRR. That will drive the client connection in a weird state, causing it to fail eventually. The fake "server busy" will be quite similar to a fake TCP RST. That would be my first attack design if I was in charge of engineering at "attackers Inc."
>
> In fact, with Kazuho's proposed defense, the first attack devolves to the a variant of the second one. The server will create two contexts and send two server hellos, even if the attackers hello arrives after the client hello. The client's defense will only succeed if it is ready to process several independent responses to its Initial Client Hello, and wait for the first one that produces a valid "server finished" message -- same defense as against the second attack.

I agree to the observations up to this point.

> I think Kazuho's PR should be reformatted to a discussion of "attacks during the Initial exchange", describing both the server side and the client side attack. His proposed defense makes sense on the server side and is relatively easy to implement, but it does not achieve much without the corresponding defenses on the client side; these client defense are required in any case, because the direct attack against the client is easier to mount than the attack through the server.

If it turns out to be the consensus, I am happy to reformat it as a
separate section that discusses the attacks during Initial exchange
and mitigations. The text that we would end up depends on how #2053
(allow dropping of Initial packets with invalid reserved bits) turns
out, but anyways I think it is a good idea to list the possible
attacks and explain how they can be prevented.

> I am also concerned that the actual server side defense is more complex than expected. It only works well if the server accepts exactly one message from the client -- I would dub that the "atomic hello" variation. That requires a series of modification to the initial handshake, such as treating HRR as some kind of error message, perhaps carrying an HRR token of sort, and mandating that the initial message only contains a single crypto frame, nothing else, in both directions. No ACK, no connection close, nothing state changing -- all that should only be allowed in handshake-protected message. Frankly, I don't see how we can specify that in time for V1.

While I understand the concerns, I am not sure if I agree with the
observations and the conclusion.

QUIC v1 mandates that the first ClientHello be sent in the first
packet. So we have "atomic hello".

We do not need to defend the HRR case, because in practice clients and
servers will agree on the parameters that do not require HRR; that has
been our assumption in TLS 1.3 that has been proved so far.

To put another way, QUIC v1 requires client to send ClientHello, and
the server in practice will respond with a ServerHello that contains
necessary information to derive the Handshake key.

I agree about the fact that a spoofed ACK, CONNECTION_CLOSE, or a
malformed packet can disrupt the handshake.

Therefore, man-on-the-side attack-resistant Initial exchange becomes practical:
* if the server considers different initial ClientHellos as belonging
to different connections
* if the client has the capability of rejecting the injected handshake messages
* if both peers has the capability of ignoring (or delaying the
application of) ACKs, CONNECTION_CLOSE, malformed packets

First point is what PR #2076 tries to address. Third point is what PR
#2053 is trying to address (or at least that's my hope). Then, the
remaining issue becomes the second point which is purely a client-side
problem.

To me, it seems that QUIC v1 seems pretty near to finishing the
server-side defense against man-on-the-side attacks.

-- 
Kazuho Oku

---

From: Dmitri Tikhonov <[email-masked]>
Date: Tue, 4 Dec 2018 08:54:43 -0500

On Tue, Dec 04, 2018 at 10:23:11AM +0900, Kazuho Oku wrote:
> First point is what PR #2076 tries to address.

I would like to understand what server is expected to do.  Let's say
it has several connections that have the same SCID/DCID.  Now the
second packet from the client comes in:

    Is the server to try each of its connection candidates in
    turn to see which one successfully decrypts the packet?

  - Dmitri.

---

From: Mikkel Fahnøe Jørgensen <[email-masked]>
Date: Tue, 4 Dec 2018 06:34:07 -0800

On 4 December 2018 at 14.54.50, Dmitri Tikhonov ([email-masked])
wrote:

In the general case an endpoint choses a unique DCID and should reject
everything else by AEAD, so you cannot have multiple active connections in
the configuration.
For 0-length the 5-tuple becomes a stand-in for DCID.

For the initial packet this is different because the client chooses the
DCID on behalf of the server. Here you can have conflicts and here AEAD
won’t help (I think) because the initial AEAD is derived from the random
DCID.
The defense is to use a strong random value. For man on the side attacks
this obviously isn’t enough, which is why there is a discussion.

A server cannot rule out weak random initial DCID’s because clients might
be stupid or malicous but it doesn’t matter much if also assumes man on the
side attacks. Thus, if a client choose a weak conflicting DCID by accident,
it just reduces it chance of succeeding with the handshake.

A man on the side attack winning a race to the server will be hard to
defend against because technically it is a valid connection attempt. I
think some sort of client side public key cert is needed early in the
handshake and that won’t be v1.

---

From: Mikkel Fahnøe Jørgensen <[email-masked]>
Date: Tue, 4 Dec 2018 06:40:46 -0800

On 4 December 2018 at 15.34.07, Mikkel Fahnøe Jørgensen ([email-masked])
wrote:

But it is possible, which is what Kazuho is aiming at, I think. It goes by
checksumming the client hello. But that is not is not enough because the
attacker can just create a different ClientHello using the same initial
random DCID and thereby win the competion for the chosen initial connection
id.

I proposed, in a comment somewhere, to use the ClientHello hash in the
initial DCID. This would make one of the handshakes fail because you can
not longer squat on the initial connection ID, but it does require that you
track the handshake for longer until you have proof - according to the
principles laid out by Kazuho.

Huitema suggests that an attack is easier towards the client, by pretending
to be a valid server response. This attack will work even if the DCID is
tied to the ClientHello, but eventually it will fail because the attacker
does not have the correct server certificate.

---

From: Mikkel Fahnøe Jørgensen <[email-masked]>
Date: Tue, 4 Dec 2018 06:46:07 -0800

On 4 December 2018 at 15.40.46, Mikkel Fahnøe Jørgensen ([email-masked])
wrote:

If the servers first response contained an atomic server certificate, the
client could reject an attack without tracking state. Unfortunately some
certs are too long. A defense could be that a client buffers at most one
partial certificate and otherwise waits a fixed time for one valid atomic
cert packet, or the buffered cert completes and validates in subsequent
packets.

---

From: Christian Huitema <[email-masked]>
Date: Tue, 4 Dec 2018 08:11:58 -0800

> On Dec 4, 2018, at 6:46 AM, Mikkel Fahnøe Jørgensen <[email-masked]> wrote:
> 
> If the servers first response contained an atomic server certificate

... then you would have a big privacy regression. 

-- Christian Huitema

---

From: Dmitri Tikhonov <[email-masked]>
Date: Wed, 5 Dec 2018 09:10:00 -0500

>     turn to see which one successfully decrypts the packet?

Kazuho,

You did not respond to this question, but it seems that this is
the way to implement the defense you propose on the server.  I
would like to point out that this sort of thing has a high cost
and in turn makes DoS attacks simpler.

  - Dmitri.

---

From: Christian Huitema <[email-masked]>
Date: Wed, 5 Dec 2018 12:28:25 -0800

> and in turn makes DoS attacks simpler.

I understand how to create a separate connection context on the server
for each different incoming server hello, and I am not concerned too
much by DoS attacks. Attackers can create fake client hellos at will;
whether they reuse the same ICID/SCID as current client does not change
the amount of resource consumed on the server. But I am concerned that
this solution breaks if the client needs to send multiple different
Initial messages, such as a new Client Hello in response to an HRR, or
an ACK. How do we want to handle those?

-- Christian Huitema

---

From: Kazuho Oku <[email-masked]>
Date: Thu, 6 Dec 2018 11:36:55 +0900

2018年12月6日(木) 5:28 Christian Huitema <[email-masked]>:
> I understand how to create a separate connection context on the server for each different incoming server hello, and I am not concerned too much by DoS attacks. Attackers can create fake client hellos at will; whether they reuse the same ICID/SCID as current client does not change the amount of resource consumed on the server.

Agreed.

> But I am concerned that this solution breaks if the client needs to send multiple different Initial messages, such as a new Client Hello in response to an HRR, or an ACK. How do we want to handle those?

I am not too worried about HRR and the behaviors triggered by HRR,
because a server needs to send it only when _none_ of the key shares
it supports can be found in client's first Hello. It's rare in
practice (because everyone uses X25519), and the client under attack
can be made it even rare, by including multiple key shares in the
first ClientHello.

Regarding ACKs, you need to potentially ignore or postpone applying
them. The same goes for CONNECTION_CLOSE.

-- 
Kazuho Oku

---

From: Dmitri Tikhonov <[email-masked]>
Date: Thu, 6 Dec 2018 08:30:50 -0500

On Wed, Dec 05, 2018 at 12:28:25PM -0800, Christian Huitema wrote:
> the amount of resource consumed on the server.

That's true -- I was wrong.  I thought that the server would have to
perform trial decryption for the client's second packet, making the
CPU cost quadratic.  I forgot that the server changes its SCID and
thus the second packet could only match a single context.

  - Dmitri.