Subject: [New Issue] Inconsistent behavior with NCIDs

From: Kashyap Thimmaraju <[email-masked]>
Date: Thu, 12 Nov 2020 17:36:19 +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.

In this email I’ve described my work on the new connection ID (NCID) for 
server implementations.

ANALYSIS

The draft does not specify how servers should handle new CIDs (NCID) where:

 1.

    All the NCIDs are the same as the client generated SCID

 2.

    All the NCIDs are the same as the client generated DCID

 3.

    All the NCIDs are the same but different from the client generated
    SCID and DCID

EVALUATION

The primary goal of my evaluation is to observe how implementations 
behave to the 3 test cases outlined in the analysis. To conduct this 
experiment I adopted the following methodology. First, I created a 
client that uses deterministic CIDs for the source and destination CIDs 
and the NCIDs (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 
rows in the table below. To conduct the experiment, I always had the 
client open a QUIC connection with source CID 1 and destination CID 2. 
The NCID that was then used was either all 1, or all 2, or all 3. The 
connection was kept open (if possible) for a maximum of 10s with the 
server, and then closed. 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 
QUIC connection obtained a successful handshake or not. If not, I 
collected any error messages.

RESULTS

The results from my evaluation are shown in the table below. In 
particular, I found that either the handshake succeeded or the handshake 
failed due to a PROTOCOL_VIOLATION, Error Code: 10 message from the 
server. When I had tested this on quant early on, çase aresulted in 
crashing the server (see https://github.com/NTAP/quant/issues/68 
<https://github.com/NTAP/quant/issues/68>). The difference in behaviours 
raises the question on how servers should respond to such messages and 
what amount of detail should be provided in the reason of the error message.

TEST CASE : HANDSHAKE COMPLETED : PROTCOL VIOLATION

A : Aioquic, Cloudflare, Neqo, Nginx, Pquic, Akamai, Ats, Chromium, F5, 
Quinn, Mvfst : Lsquic, mvfst, ngtcp2, picoquic, quant, quicly

B : Aioquic, Cloudflare, Neqo, Nginx, Pquic, Mvfst : Ngtcp2, picoquic, 
quant, quicly

C : Aioquic, Cloudflare, Neqo, Nginx, Pquic, Akamai, Ats, Chromium, F5, 
Quinn, Mvfst : Lsquic, ngtcp2, picoquic, quant, quicly

*
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: Christian Huitema <[email-masked]>
Date: Thu, 12 Nov 2020 15:41:18 -0800

The *spec says "**If an endpoint receives a NEW_CONNECTION_ID frame that
repeats a previously issued connection ID with a different Stateless
Reset Token or a different sequence number, or if a sequence number is
used for different connection IDs, the endpoint MAY treat that receipt
as a connection error of type PROTOCOL_VIOLATION." This is a "MAY", and
it is not surprising that some implementations have stricter checks than
other.*

*Note that clients may well send a single ***NCID with the same value as
the client generated SCID. That's not a protocol violation.**

**-- Christian Huitema **

**

*It does not test against the *

On 11/12/2020 8:36 AM, 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.
>
>
> In this email I’ve described my work on the new connection ID (NCID)
> for server implementations.
>
>
> ANALYSIS
>
> client that uses deterministic CIDs for the source and destination
> CIDs and the NCIDs (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 rows in the table below. To conduct the experiment, I
> always had the client open a QUIC connection with source CID 1 and
> destination CID 2. The NCID that was then used was either all 1, or
> all 2, or all 3. The connection was kept open (if possible) for a
> maximum of 10s with the server, and then closed. 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 QUIC connection obtained a
> successful handshake or not. If not, I collected any error messages.
>
>
> RESULTS
>
> particular, I found that either the handshake succeeded or the
> handshake failed due to a PROTOCOL_VIOLATION, Error Code: 10 message
> from the server. When I had tested this on quant early on, çase
> aresulted in crashing the server (see
> https://github.com/NTAP/quant/issues/68). The difference in behaviours
> A : Aioquic, Cloudflare, Neqo, Nginx, Pquic, Akamai, Ats, Chromium,
> F5, Quinn, Mvfst : Lsquic, mvfst, ngtcp2, picoquic, quant, quicly
>
> C : Aioquic, Cloudflare, Neqo, Nginx, Pquic, Akamai, Ats, Chromium,
> F5, Quinn, Mvfst : Lsquic, ngtcp2, picoquic, quant, quicly
>
> *
> Sincerely,
> --

---

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

What I think was unsaid in Christian's reply was that the checks necessary to enforce this require state that an endpoint might not retain.  I'm not clear about the exact test cases here and whether it would be reasonable to expect that an endpoint remember the values that are being duplicated.  But that seems to be the source of the observed behaviour.  Happy to be corrected if this is wrong.

My implementation of NEW_CONNECTION_ID in neqo, which hasn't landed yet, will only reject a duplicate value if it duplicates an active value.  Remembering more values requires an arbitrary amount of additional state.  I would expect similar behaviour from other implementations.

neqo currently doesn't do anything with NEW_CONNECTION_ID, it just throws them away without looking at then.  So these results are unsurprising.

I think that the fundamentals here are important to examine though.  If you are communicating with a peer that has no interest in protecting your privacy, there are many covert channels available to it that would allow it to exfiltrate your information.  The spin bit works well for that.  The endpoint can also, at some cost, implement packet number skipping or reencoding so that the ciphertext carries a low bitrate signal.  IPv6 flow labels, which an adversary could write to, and which most endpoints are not checking are a very easy channel to exploit.  Timing of packets is noisy, but probably usable.  The possibilities seem endless.

So we have to assume that your privacy - with respect to use of connection IDs, and in most other respects - is at the mercy of your peer.  I don't think that we have any system that would prevent them from doing bad things (if such a thing exists or could exist, please contact me; I will do what I can to support credible ideas that need research).  We have tried to build a protocol in which it is as easy as possible for an endpoint to do the right thing, we might even have a few places where it is hard to do the wrong thing and evade notice, but that doesn't mean that we can guarantee compliance.

In light of that, I don't see any problem inherent to the specification.  Unless it is to say that protecting privacy requires cooperation from both endpoints.  Maybe that isn't well-enough understood that it can remain unsaid, I don't know.

Cheers,
Martin

On Fri, Nov 13, 2020, at 10:41, Christian Huitema wrote:
> The *spec says "**If an endpoint receives a NEW_CONNECTION_ID frame 
> that repeats a previously issued connection ID with a different 
> Stateless Reset Token or a different sequence number, or if a sequence 
> number is used for different connection IDs, the endpoint MAY treat 
> that receipt as a connection error of type PROTOCOL_VIOLATION." This is 
> a "MAY", and it is not surprising that some implementations have 
> stricter checks than other.*
> 
> *Note that clients may well send a single ***NCID with the same value 
> as the client generated SCID. That's not a protocol violation.**
> 
> * *
> > * *
> > 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.
> 
> > 
> > In this email I’ve described my work on the new connection ID (NCID) for server implementations.
> 
> > 
> > ANALYSIS
> 
> >  1. All the NCIDs are the same as the client generated SCID
> 
> >  2. All the NCIDs are the same as the client generated DCID
> 
> >  3. All the NCIDs are the same but different from the client generated SCID and DCID
> 
> > 
> > EVALUATION
> 
> > The primary goal of my evaluation is to observe how implementations behave to the 3 test cases outlined in the analysis. To conduct this experiment I adopted the following methodology. First, I created a client that uses deterministic CIDs for the source and destination CIDs and the NCIDs (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 rows in the table below. To conduct the experiment, I always had the client open a QUIC connection with source CID 1 and destination CID 2. The NCID that was then used was either all 1, or all 2, or all 3. The connection was kept open (if possible) for a maximum of 10s with the server, and then closed. 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 QUIC connection obtained a successful handshake or not. If not, I collected any error messages.
> 
> > 
> > RESULTS
> 
> > The results from my evaluation are shown in the table below. In particular, I found that either the handshake succeeded or the handshake failed due to a PROTOCOL_VIOLATION, Error Code: 10 message from the server. When I had tested this on quant early on, çase a resulted in crashing the server (see https://github.com/NTAP/quant/issues/68). The difference in behaviours raises the question on how servers should respond to such messages and what amount of detail should be provided in the reason of the error message.
> 
> > 
> > A : Aioquic, Cloudflare, Neqo, Nginx, Pquic, Akamai, Ats, Chromium, F5, Quinn, Mvfst : Lsquic, mvfst, ngtcp2, picoquic, quant, quicly
> 
> > B : Aioquic, Cloudflare, Neqo, Nginx, Pquic, Mvfst : Ngtcp2, picoquic, quant, quicly
> 
> > C : Aioquic, Cloudflare, Neqo, Nginx, Pquic, Akamai, Ats, Chromium, F5, Quinn, Mvfst : Lsquic, ngtcp2, picoquic, quant, quicly
> 
> *
> > Sincerely,
> > --

---

From: Jana Iyengar <[email-masked]>
Date: Fri, 13 Nov 2020 15:51:18 -0800

Hi Kashyap,

Thanks again for doing this work.

I am a bit confused about the experiment however. You said:
"I always had the client open a QUIC connection with source CID 1 and
destination CID 2. The NCID that was then used was either all 1, or all 2,
or all 3."

(i) Does the server generate and send a new source connection ID when it
responds to the client Initial packet?

(ii) Given that your final conclusions are "HANDSHAKE COMPLETED" or
"PROTOCOL_VIOLATION", when is the NCID sent? Along with the Initial
packets? If that is the case, it should be a PROTOCOL_VIOLATION, since NCID
frames are disallowed in Initial or Handshake packets.

(iii) What is the NCID value? When you say "either all 1, or all 2, or all
3", I don't understand what 1, 2, and 3 are.

- jana

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

> What I think was unsaid in Christian's reply was that the checks necessary
> to enforce this require state that an endpoint might not retain.  I'm not
> clear about the exact test cases here and whether it would be reasonable to
> expect that an endpoint remember the values that are being duplicated.  But
> that seems to be the source of the observed behaviour.  Happy to be
> corrected if this is wrong.
>
> My implementation of NEW_CONNECTION_ID in neqo, which hasn't landed yet,
> will only reject a duplicate value if it duplicates an active value.
> Remembering more values requires an arbitrary amount of additional state.
> I would expect similar behaviour from other implementations.
>
> neqo currently doesn't do anything with NEW_CONNECTION_ID, it just throws
> them away without looking at then.  So these results are unsurprising.
>
> I think that the fundamentals here are important to examine though.  If
> you are communicating with a peer that has no interest in protecting your
> privacy, there are many covert channels available to it that would allow it
> to exfiltrate your information.  The spin bit works well for that.  The
> endpoint can also, at some cost, implement packet number skipping or
> reencoding so that the ciphertext carries a low bitrate signal.  IPv6 flow
> labels, which an adversary could write to, and which most endpoints are not
> checking are a very easy channel to exploit.  Timing of packets is noisy,
> but probably usable.  The possibilities seem endless.
>
> So we have to assume that your privacy - with respect to use of connection
> IDs, and in most other respects - is at the mercy of your peer.  I don't
> think that we have any system that would prevent them from doing bad things
> (if such a thing exists or could exist, please contact me; I will do what I
> can to support credible ideas that need research).  We have tried to build
> a protocol in which it is as easy as possible for an endpoint to do the
> right thing, we might even have a few places where it is hard to do the
> wrong thing and evade notice, but that doesn't mean that we can guarantee
> compliance.
>
> In light of that, I don't see any problem inherent to the specification.
> Unless it is to say that protecting privacy requires cooperation from both
> endpoints.  Maybe that isn't well-enough understood that it can remain
> unsaid, I don't know.
>
> Cheers,
> Martin
>
> 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.
> >
> > >
> experiment I adopted the following methodology. First, I created a client
> that uses deterministic CIDs for the source and destination CIDs and the
> NCIDs (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 rows in the table
> below. To conduct the experiment, I always had the client open a QUIC
> connection with source CID 1 and destination CID 2. The NCID that was then
> used was either all 1, or all 2, or all 3. The connection was kept open (if
> possible) for a maximum of 10s with the server, and then closed. 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 QUIC connection obtained a successful
> handshake or not. If not, I collected any error messages.
> >
> > >
> > > RESULTS
> >
> failed due to a PROTOCOL_VIOLATION, Error Code: 10 message from the server.
> When I had tested this on quant early on, çase a resulted in crashing the
> server (see https://github.com/NTAP/quant/issues/68). The difference in
> behaviours raises the question on how servers should respond to such
> messages and what amount of detail should be provided in the reason of the
> error message.
> >
> > >

---

From: Kashyap Thimmaraju <[email-masked]>
Date: Wed, 25 Nov 2020 14:32:07 +0100

Hi QUIC-WG,

Thanks for recognizing my work and effort.

I was not part of the mailing list (but I am now :)) when you replied
so I've had to manually copy your responses. Below I've included the
person's name and replied to their comments/remarks.

 > Christian Huitema

Thanks for pointing that out.

 > Martin Thomson
 > What I think was unsaid in Christian's reply was that the checks 
necessary to
 > enforce this require state that an endpoint might not retain. I'm not 
clear
 > about the exact test cases here and whether it would be reasonable to 
expect
 > that an endpoint remember the values that are being duplicated.  But that
 > seems to be the source of the observed behaviour.  Happy to be 
corrected if
 > this is wrong.

To remember the values being duplicated is one issue, i.e., when all the
NCIDs are the same as the SCID or DCID. However, if they are different 
from the
SCID and client-generated DCID but always the same this enables linkability.

 > I think that the fundamentals here are important to examine though.  
If you are
 > communicating with a peer that has no interest in protecting your 
privacy, there
 > are many covert channels available to it that would allow it to 
exfiltrate your
 > information.  The spin bit works well for that.  The endpoint can 
also, at some
 > cost, implement packet number skipping or reencoding so that the 
ciphertext
 > carries a low bitrate signal.  IPv6 flow labels, which an adversary 
could write
 > to, and which most endpoints are not checking are a very easy channel to
 > exploit.  Timing of packets is noisy, but probably usable.  The 
possibilities
 > seem endless.

This relates to the CID-based attacks where I described the covert channel I
believe? Nevertheless, I think what you are referring to are side channels
(where one peer wants to exfiltrate some private information from its
counterpart unwittingly). You raised some interesting ideas that I would
definitely look into, e.g., using the spin bit and packet number skipping.

 > IDs, and in most other respects - is at the mercy of your peer.  I 
don't think
 > that we have any system that would prevent them from doing bad things 
(if such
 > a thing exists or could exist, please contact me; I will do what I can to
 > support credible ideas that need research).  We have tried to build a 
protocol
 > in which it is as easy as possible for an endpoint to do the right 
thing, we
 > might even have a few places where it is hard to do the wrong thing 
and evade
 > notice, but that doesn't mean that we can guarantee compliance.

I agree that the privacy of one end-point relies on the other end-point.
However, I'm actually refering to cases where multiple CIDs are shared 
within an
NCID frame. This is definitely not good for both end-points, as this enables
linkability of the QUIC connection. How could this be used? Well the 
attacker
can simply link the flow after connection migration or by observing it for a
long time. Does she gain anything else? I can't think of other gains.

 > endpoints.  Maybe that isn't well-enough understood that it can 
remain unsaid,
 > I don't know.

Well we could say that multiple NCIDs within a frame MUST be unique to 
prevent
linkability?

 > Jana Iyengar
all 2,
 > responds to the client Initial packet?

This depends on the implementation. Except for Akamai and Chromium all 
the other
servers generated their own CID.

 > frames are disallowed in Initial or Handshake packets.

They are sent after the Initial packets. Attached are a couple of pcaps with
their keys from quicly. Here you see the client sends the NCIDs after 
the server
has sent NCIDs to the client.

 > 3", I don't understand what 1, 2, and 3 are.

I think the pcap will help clarify that. For example, if the client 
sends 3 NCID
frames, each frame has the value 0100000000000000 for the Connection ID.

Sincerely,

Besucheranschrift: