Subject: [New Issue] CID based attacks

From: Kashyap Thimmaraju <[email-masked]>
Date: Thu, 12 Nov 2020 17:34:03 +0100

**

*Dear QUIC WG,*

*

I’m Kashyap Thimmaraju, a postdoctoral researcher at Humboldt University 
Berlin. Recently I discovered a couple of attacks with the QUIC 
protocol. Lars Eggert recommended that I share my findings with the WG 
to discuss the impact and relevance of these findings.

Broadly speaking, the attacks deal with the Connection ID (CID), which 
I’ve elaborated on below.

ANALYSIS

The draft specifies and recommends several important points on secure 
usage of the CID, e.g., i) the same CID MUST NOT be used multiple times 
over the same connection to prevent an eavesdropper from correlating the 
end-points; ii) end-points should associate a sequence number with each 
CID to detect reuse within the same connection; iii) CIDs should be 
(pseudo) randomly generated as they are also used for packet security 
and; iv) CIDs can be very long (max. 20 bytes).

The draft, however, does not specify how servers should handle the case 
when successive incoming connections to a server use the same 
destination CID.  Indeed, it can be seen that  based on the assumption 
that the CIDs are (pseudo) randomly generated with a maximum length of 
20 bytes, the probability of such a collision is very low.

Hence, I posit the following: If the server (implementation) does not 
permit the use of the same destination CID across successive connections 
(for a specific timeout), then an attacker can exploit this behaviour in 
at least 2 ways:

 1.

    She can enumerate the number of server instancesbehind the domain
    name/public IP address: if the handshake does not complete on the
    second/successive attempt, then she infers that she has reached the
    same instance; if the handshake succeeds then it is a new instance.

 2.

    Create a covert channel: we can assume that a sender and receiver
    agree upon a set of CIDs to use at specific times. For each time
    interval, the sender and receiver use the same destination CID. The
    sender sends a 1 by connecting to the server and a 0 by not
    connecting. The receiver always attempts to connect to the server.
    If the receiver could not complete the handshake, it’s a 1, if the
    handshake completes it’s a 0. Using this scheme a binary string can
    be covertly communicated in one direction.

EVALUATION

The primary goal of my evaluation is to identify implementations, if 
any, that prevent two subsequent QUIC connections from using the same 
destination CID. To conduct this experiment I adopted the following 
methodology. First, I created a client that uses deterministic CIDs for 
the source and destination CIDs (I modified LiteSpeed Technologies 
open-source QUIC client). Second, I used 15 implementations from those 
listed on the QUIC Working Group’s GitHub page1: either manually built 
Docker containers or the public test server. The list of servers tested 
are shown across the two rows in Table 1. To conduct the experiment, I 
had the client open and hold a QUIC connection with source CID 1 and 
destination CID 2 for a maximum of 10s with the server, and then close 
it. We then idle for 10s and repeat the steps a second time. I saved the 
debug logs of the client, packet traces and session keys. I then 
repeated the process for each of the 15 implementations. Finally, to 
obtain the results of the test, I searched the debug log of the client 
or the packet trace to confirm whether the second QUIC connection 
obtained a successful handshake or not. The absence of a successful 
handshake indicates a vulnerable implementation.

RESULTS

The results from my evaluation are shown in the table below. In 
particular, I found 4 out of 15 implementations to be vulnerable to the 
enumeration and covert channel attacks, namely, Apache Traffic Server 
(ATS), Chromium, LiteSpeed and NGTCP2. In an evaluation of the 
throughput using Lsquic clients and server on my desktop I measured a 
throughput of ~30 bps.

VULNERABLE : IMPLEMENTATION

NO : Akamai, F5, Quinn, Aioquic, Quiche, Proxygen, Neqo, Nginx, 
Picoquic, Quant, Quicly

YES : ATS, Chromium, Lsquic, Ngctcp2

*
Sincerely,

-- 
Dr.-Ing Kashyap Thimmaraju

Lehrstuhl für Technische Informatik
Institut für Informatik
Humboldt-Universität zu Berlin

Besucheranschrift:
Rudower Chaussee 25, 12489 Berlin
Haus 4, 3. OG

[email-masked]

http://www.ti.informatik.hu-berlin.de

---

From: Dmitri Tikhonov <[email-masked]>
Date: Thu, 12 Nov 2020 13:15:09 -0500

Hello Kashyap,

Thank you for this research.

I will think about the security implications of your research and so I
make no claims about it, but in the meantime, I want quickly to point out
something that you may have missed:

On Thu, Nov 12, 2020 at 05:34:03PM +0100, Kashyap Thimmaraju wrote:
> Hence, I posit the following: If the server (implementation) does not permit
> the use of the same destination CID across successive connections (for a
> specific timeout),

--- 8< --- snip --- 8< ---

> Finally, to obtain the results of the test, I searched the debug log of the
> client or the packet trace to confirm whether the second QUIC connection

After a connection is closed, it may enter the Draining State [1], during
which it will ignore incoming packets with that connection's CIDs for a
period of time.

I can't speak for ATS, Chromium, and ngtcp2, but the failure to handshake
with an already-used DCID with a LiteSpeed server is most likely due to
the Draining State: it simply does not have any other rules precluding
CID reuse.  If you hit up any of the LiteSpeed public interop endpoints
[2] and give me the CID(s) you used, I will look up relevant sections
of the log file and provide them to you.

My question would be:  Why aren't connections in the other 11 implementations
enter the Draining State?

  - Dmitri.

1. https://tools.ietf.org/html/draft-ietf-quic-transport-32#section-10.2.2
2. https://github.com/quicwg/base-drafts/wiki/Implementations#lsquic

---

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

> enter the Draining State?

Neqo should.  (I'm not sure that I have a test against our command-line server though, that is almost certainly doing bad things.)

---

From: Christian Huitema <[email-masked]>
Date: Thu, 12 Nov 2020 15:23:08 -0800

> Neqo should.  (I'm not sure that I have a test against our command-line server though, that is almost certainly doing bad things.)

The description of the experiment says "*To conduct the experiment, I
had the client open and hold a QUIC connection with source CID 1 and
destination CID 2 for a maximum of 10s with the server, and then close
it. We then idle for 10s and repeat the steps a second time." Should the
draining period be longer than 10 seconds? Section 10.2 of the transport
spec says: "*The closing and draining connection states exist to ensure
that connections close cleanly and that delayed or reordered packets are
properly discarded. These states SHOULD persist for at least three times
the current Probe Timeout (PTO) interval as defined in [QUIC-RECOVERY
<https://quicwg.org/base-drafts/draft-ietf-quic-transport.html#QUIC-RECOVERY>]."
That's what picoquic implements, and that's typically way less than 10
seconds.

The description of the experiment does not say whether the successive
connection attempts used the same IP address. For Picoquic at least
that's important, because Picoquic retrieves the handshake context using
the combination of Initial DCID and client IP + port. Multiple
connection attempts using the same Initial DCID and different IP
addresses will be treated as independent connections. This was one of
the suggestion in
https://tools.ietf.org/html/draft-kazuho-quic-authenticated-handshake-01.

-- Christian Huitema

---

From: Kazuho Oku <[email-masked]>
Date: Fri, 13 Nov 2020 08:31:02 +0900

2020年11月13日(金) 8:23 Christian Huitema <[email-masked]>:

> The description of the experiment says "*To conduct the experiment, I had
> the client open and hold a QUIC connection with source CID 1 and
> destination CID 2 for a maximum of 10s with the server, and then close it.
> We then idle for 10s and repeat the steps a second time." Should the
> <https://quicwg.org/base-drafts/draft-ietf-quic-transport.html#QUIC-RECOVERY>
> ]." That's what picoquic implements, and that's typically way less than
> 10 seconds.
>
> connection attempts used the same IP address. For Picoquic at least that's
> important, because Picoquic retrieves the handshake context using the
> combination of Initial DCID and client IP + port. Multiple connection
> attempts using the same Initial DCID and different IP addresses will be
> treated as independent connections. This was one of the suggestion in

Quicly adopts the same approach. Applications of quicly are expected to
supply their own CID generation scheme, and therefore quicly does not know
if there's enough entropy in the CID to avoid collision between
server-supplied CIDs and the original DCID being generated by the client.

Therefore, during the handshake, quicly uses `4-tuple && (client-generated
DCID || server-generated CID)` as the packet routing scheme.

That's how we avoid the problem raised by Kashyap.

QUIC stacks that are guaranteed to have server-generated connection IDs
sufficiently long can rely on CID-based routing, I think. Maybe the
implementations marked "vulnerable" fall into this category.

-- Christian Huitema

-- 
Kazuho Oku

---

From: "Martin Thomson" <[email-masked]>
Date: Fri, 13 Nov 2020 10:55:04 +1100

Firstly, thanks for taking a look at this.  This is obviously a considerable amount of work and it is good to see people thinking about the way that the different pieces fit together.

This situation does not bother me very much.  As Dmitri observes, this might be down to different treatment of the draining period in implementations, but it's a little more complicated.  There are also differences you are likely to see in routing infrastructure as well.  I'll get to whether I think this needs documenting at the end.

The use of the client's destination connection ID is going to be a little weird in servers.  Neqo as a server does not use that value for very long; it's only used in combination with the remote address for as long as a handshake is live, and only as a backup for matching packets to connections where a server-provided connection ID isn't included.  This is approximately the same as picoquic and quicly, and it would surprise me if others differed.

That isn't the whole story though.  If the *routing* infrastructure does the same thing, then you are able mount the claimed attack by varying source address.  If the routing infrastructure only looks at the connection ID, then you won't reveal any information.  But either allows targeting of server instances, which is probably unwise, so I would be surprised to see that in more advanced infrastructure.  Address tuple-based routing, which might still be common, does offer some opportunities here, but that was already true as those systems can be exploited by manipulating source address.  

All in all, the question of how a load balancer directs new connections to server instances is highly relevant here.

It probably pays to see what an attacker gains.  Revealing what connection IDs are in use is something, but given the size of the space, that might not be especially valuable.  And exploiting this requires a routing infrastructure that is vulnerable to more interesting attacks, like resource exhaustion by targeting.

The covert channel is something we've already decided is not interesting.  The number of other covert channels is practically unbounded here, and the bit rate of the one you describe is far lower.

To the question of what might be said about this sort of thing, I don't see anything here for the main specifications.  We have already acknowledged that there is a need for operational guidance, particularly around the deployment of load balancers and routing infrastructure.  At this stage, we're still learning.  We have a couple of working group items that cover aspects of this.  From the manageability document that aims to look at how deployments could be managed (from different perspectives), to the load balancers draft that specifically looks at the details routing mechanisms.

Given the state of what we know, I think that it would be premature to put any text in the main document, but this should certainly help inform our work on improving the state of those other documents.

Cheers,
Martin

On Fri, Nov 13, 2020, at 03:34, Kashyap Thimmaraju wrote:
> * *
> 
> *Dear QUIC WG,*
> 
> * 
> I’m Kashyap Thimmaraju, a postdoctoral researcher at Humboldt 
> University Berlin. Recently I discovered a couple of attacks with the 
> QUIC protocol. Lars Eggert recommended that I share my findings with 
> the WG to discuss the impact and relevance of these findings.
> 
> 
> over the same connection to prevent an eavesdropper from correlating 
> the end-points; ii) end-points should associate a sequence number with 
> each CID to detect reuse within the same connection; iii) CIDs should 
> be (pseudo) randomly generated as they are also used for packet 
> security and; iv) CIDs can be very long (max. 20 bytes).
> 
> 
> permit the use of the same destination CID across successive 
> connections (for a specific timeout), then an attacker can exploit this 
> behaviour in at least 2 ways:
> 
>  1. She can enumerate the number of server instances behind the domain 
>  2. Create a covert channel: we can assume that a sender and receiver 
> sender sends a 1 by connecting to the server and a 0 by not connecting. 
> The receiver always attempts to connect to the server. If the receiver 
> could not complete the handshake, it’s a 1, if the handshake completes 
> it’s a 0. Using this scheme a binary string can be covertly 
> communicated in one direction.
> 
> 
> EVALUATION
> 
> it. We then idle for 10s and repeat the steps a second time. I saved 
> the debug logs of the client, packet traces and session keys. I then

---

From: Jana Iyengar <[email-masked]>
Date: Fri, 13 Nov 2020 09:05:37 -0800

Thank you, Kashyap, for doing this work and for bringing it to the
working group.

I agree with Martin's assessment, specifically that the interesting exploit
on enumerating the number of servers, is very dependent on how load
balancing is done. A relevant point here is that the attacker can only
control the DCID in the first flight of Initial packets, and if the server
treats Initial packets differently than it does subsequent packets, that is
yet another way in which the surface of this exploit gets limited.

We need to gather best practices around various things as we increase
deployment, and we ought to include this one in that set.

Importantly, please continue doing this sort of work -- it is very helpful
to have academic attention to these and other aspects of the protocol and
its deployments.

- jana

On Thu, Nov 12, 2020 at 3:55 PM Martin Thomson <[email-masked]> wrote:

> Firstly, thanks for taking a look at this.  This is obviously a
> considerable amount of work and it is good to see people thinking about the
> way that the different pieces fit together.
>
> This situation does not bother me very much.  As Dmitri observes, this
> might be down to different treatment of the draining period in
> implementations, but it's a little more complicated.  There are also
> differences you are likely to see in routing infrastructure as well.  I'll
> get to whether I think this needs documenting at the end.
>
> The use of the client's destination connection ID is going to be a little
> weird in servers.  Neqo as a server does not use that value for very long;
> it's only used in combination with the remote address for as long as a
> handshake is live, and only as a backup for matching packets to connections
> where a server-provided connection ID isn't included.  This is
> approximately the same as picoquic and quicly, and it would surprise me if
> others differed.
>
> That isn't the whole story though.  If the *routing* infrastructure does
> the same thing, then you are able mount the claimed attack by varying
> source address.  If the routing infrastructure only looks at the connection
> ID, then you won't reveal any information.  But either allows targeting of
> server instances, which is probably unwise, so I would be surprised to see
> that in more advanced infrastructure.  Address tuple-based routing, which
> might still be common, does offer some opportunities here, but that was
> already true as those systems can be exploited by manipulating source
> address.
>
> All in all, the question of how a load balancer directs new connections to
> server instances is highly relevant here.
>
> It probably pays to see what an attacker gains.  Revealing what connection
> IDs are in use is something, but given the size of the space, that might
> not be especially valuable.  And exploiting this requires a routing
> infrastructure that is vulnerable to more interesting attacks, like
> resource exhaustion by targeting.
>
> The covert channel is something we've already decided is not interesting.
> The number of other covert channels is practically unbounded here, and the
> bit rate of the one you describe is far lower.
>
> To the question of what might be said about this sort of thing, I don't
> see anything here for the main specifications.  We have already
> acknowledged that there is a need for operational guidance, particularly
> around the deployment of load balancers and routing infrastructure.  At
> this stage, we're still learning.  We have a couple of working group items
> that cover aspects of this.  From the manageability document that aims to
> look at how deployments could be managed (from different perspectives), to
> the load balancers draft that specifically looks at the details routing
> mechanisms.
>
> Given the state of what we know, I think that it would be premature to put
> any text in the main document, but this should certainly help inform our
> work on improving the state of those other documents.
>
> Cheers,
> Martin
>

---

From: Lucas Pardue <[email-masked]>
Date: Fri, 13 Nov 2020 18:23:43 +0000

> to have academic attention to these and other aspects of the protocol and

+1.

Thanks Kashyap.

Cheers,
Lucas

---

From: Dmitri Tikhonov <[email-masked]>
Date: Sun, 15 Nov 2020 17:56:53 -0500

> That's what picoquic implements, and that's typically way less than 10

I ran some experiments myself and I realized that my original guess was
incorrect.  lsquic server retires the Initial DCID a short time after
handshake succeeds.  When a CID is retired, all incoming packets bearing 
it are dropped.

lsquic keeps CIDs retired for at least 30 seconds and at most forever
(old entries are purged opportunistically when new entries are added.)

I looked for guidance in the Transport Draft for how long a CID is to
stay retired (both Initial DCID and those retired via the
RETIRE_CONNECTION_ID frame), but found none.

  - Dmitri.