RE: Increasing QUIC connection ID size

Mikkel Fahnøe Jørgensen <mikkelfj@gmail.com> Fri, 12 January 2018 16:57 UTC

Return-Path: <mikkelfj@gmail.com>
X-Original-To: quic@ietfa.amsl.com
Delivered-To: quic@ietfa.amsl.com
Received: from localhost (localhost [127.0.0.1]) by ietfa.amsl.com (Postfix) with ESMTP id 6FB3D12D942 for <quic@ietfa.amsl.com>; Fri, 12 Jan 2018 08:57:38 -0800 (PST)
X-Virus-Scanned: amavisd-new at amsl.com
X-Spam-Flag: NO
X-Spam-Score: -2.698
X-Spam-Level:
X-Spam-Status: No, score=-2.698 tagged_above=-999 required=5 tests=[BAYES_00=-1.9, DKIM_SIGNED=0.1, DKIM_VALID=-0.1, DKIM_VALID_AU=-0.1, FREEMAIL_FROM=0.001, HTML_MESSAGE=0.001, RCVD_IN_DNSWL_LOW=-0.7, SPF_PASS=-0.001, UNPARSEABLE_RELAY=0.001] autolearn=ham autolearn_force=no
Authentication-Results: ietfa.amsl.com (amavisd-new); dkim=pass (2048-bit key) header.d=gmail.com
Received: from mail.ietf.org ([4.31.198.44]) by localhost (ietfa.amsl.com [127.0.0.1]) (amavisd-new, port 10024) with ESMTP id uk2I_0Zs41ca for <quic@ietfa.amsl.com>; Fri, 12 Jan 2018 08:57:33 -0800 (PST)
Received: from mail-io0-x22d.google.com (mail-io0-x22d.google.com [IPv6:2607:f8b0:4001:c06::22d]) (using TLSv1.2 with cipher ECDHE-RSA-AES128-GCM-SHA256 (128/128 bits)) (No client certificate requested) by ietfa.amsl.com (Postfix) with ESMTPS id 2A53712D861 for <quic@ietf.org>; Fri, 12 Jan 2018 08:57:33 -0800 (PST)
Received: by mail-io0-x22d.google.com with SMTP id f34so1250780ioi.13 for <quic@ietf.org>; Fri, 12 Jan 2018 08:57:33 -0800 (PST)
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20161025; h=from:in-reply-to:references:mime-version:date:message-id:subject:to :cc; bh=2PEjS2gkNSOzDkrlKKUOCC5KEPPbMIirIc+1r/js2HM=; b=eAmKFbEgLFXJ/lpJ4u6vtC5/g0aXGbTebmc8PoanHnWFFbyaVZRYZkhP1ufocv/aZ/ c+LfYA2K8QxXlFqgyin5ZWQ2lTf16Z4xr1WAH5vKpei4MRWA1q0oAwMjNoaDovSU9SEj VSnR15b2TRwthjx5/wlWj4sK7IWagsXaLLWr5ZCFblqBVwR6XxWPtJOlLta5zN+18lys A/Mk2I5Q88sv2LDU7kRJGIKriRwDxW+Evq8awY6o5f19MqA7e/Ho0tRriQB1okNl6vIi 5yK7fLNenv12mjJquSWgjSgHEQLfzTQx+T6GyYM3foL7rnWAoxg3AP5mbK5tjhvlNPUf Ut0w==
X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20161025; h=x-gm-message-state:from:in-reply-to:references:mime-version:date :message-id:subject:to:cc; bh=2PEjS2gkNSOzDkrlKKUOCC5KEPPbMIirIc+1r/js2HM=; b=fc2AYlWtrtoQUbGyY/hrRQFysVuDwFarwZEX2IVuvKz86SlGjX+kAH8H77Qb9GPYgA rnJwUpCiJGxyALLl2oVC5WF0hNGaoa60Te9DfIa3kchCcQa73m5WMsGPNW2+US+zFIUs VjZZ5rh3ZTs/gQmQ+PRbBLEa9thaRR/DdVrGictG5NiQ26GfwAFvtIAIt1TuZtcS2njz lKstimb+Q88Ssv33GAbpJMPjBv/9A3TBl2Ooo5G3WnMsjnFBNemI6e0GklDENA3aPuUT Z2uHD51YC42BnnYF+myDm0matHQ75mJlzKiKffW/1e7BCyuhD/pA8RoJHKrmH9CzlTdW nlSg==
X-Gm-Message-State: AKGB3mKyIFxJ9fdDMWN2No5k3eoOzdlyRaDD9fZy8A/sidybZkG2cclF YkhZl3jhpljJcs3Ed+IdgXHKxyUoIt5AbXlwxDY=
X-Google-Smtp-Source: ACJfBounakIkpZSNInLDrAdtrsxfwL+D5sNkbS2LgzDd/YtIoibih4FEjR5YPXbuc8Z2XlQwgBTciapMdUkavgzwlWU=
X-Received: by 10.107.57.3 with SMTP id g3mr27130472ioa.297.1515776252486; Fri, 12 Jan 2018 08:57:32 -0800 (PST)
Received: from 1058052472880 named unknown by gmailapi.google.com with HTTPREST; Fri, 12 Jan 2018 11:57:31 -0500
From: =?UTF-8?Q?Mikkel_Fahn=C3=B8e_J=C3=B8rgensen?= <mikkelfj@gmail.com>
In-Reply-To: <808c94738a52489d913279b1e6db100f@usma1ex-dag1mb5.msg.corp.akamai.com>
References: <CAAZdMad=YnTyXG-q0ACpT=tyCSX1GgRLvb=8HT3Au=e9_XT5Ag@mail.gmail.com> <d2a6136f93654eb1a5c7970cfb41f7ad@usma1ex-dag1mb5.msg.corp.akamai.com> <CAN1APdf7MqhdQ-+VMOwsNgz_F+OZK-8CzndwWTQq4FPM52ro9Q@mail.gmail.com> <1142e1ee-ae7b-b0be-625a-4136c6085c08@huitema.net> <CAKcm_gNyrW1rVMrO3oF06+YH6cCEf2KQgTKRtQ-JrvWa1cpYKA@mail.gmail.com> <69f4ff2b505d4574b369ed872df9b1be@usma1ex-dag1mb5.msg.corp.akamai.com> <CAKcm_gNg6Q5Y7ebKZUFDGAFa8WmiC03wOzizLGcxGOTQNhSTMw@mail.gmail.com> <808c94738a52489d913279b1e6db100f@usma1ex-dag1mb5.msg.corp.akamai.com>
X-Mailer: Airmail (420)
MIME-Version: 1.0
Date: Fri, 12 Jan 2018 11:57:31 -0500
Message-ID: <CAN1APdfNit=2MJA2JryN=tsppaLjEVAYoyfFfSCUEtZ-0rwDqQ@mail.gmail.com>
Subject: RE: Increasing QUIC connection ID size
To: "Lubashev, Igor" <ilubashe@akamai.com>, Ian Swett <ianswett@google.com>
Cc: "huitema@huitema.net" <huitema@huitema.net>, "quic@ietf.org" <quic@ietf.org>
Content-Type: multipart/alternative; boundary="001a114ac18016a78d05629729fb"
Archived-At: <https://mailarchive.ietf.org/arch/msg/quic/V_dAzHls2Sq6UfDZl4T8Hh-21mg>
X-BeenThere: quic@ietf.org
X-Mailman-Version: 2.1.22
Precedence: list
List-Id: Main mailing list of the IETF QUIC working group <quic.ietf.org>
List-Unsubscribe: <https://www.ietf.org/mailman/options/quic>, <mailto:quic-request@ietf.org?subject=unsubscribe>
List-Archive: <https://mailarchive.ietf.org/arch/browse/quic/>
List-Post: <mailto:quic@ietf.org>
List-Help: <mailto:quic-request@ietf.org?subject=help>
List-Subscribe: <https://www.ietf.org/mailman/listinfo/quic>, <mailto:quic-request@ietf.org?subject=subscribe>
X-List-Received-Date: Fri, 12 Jan 2018 16:57:38 -0000

It could also be fixed 62 bit connection identifier and 2 msg of the first
CID byte stores the additional length. The requirement is then that the
first 62 bits must have “enough entropy” and the remaining bits are
application or deployment specific. This will force routers to support
128-bits, but it will allow them to require it if so desired.

A router need not be concerned with the variable length aspect if the QUIC
invariant ensures that a packet length is at least long enough to read 128
bits from CID start. It can just assume the length it expects and then
validate as needed with auth tag or length, or just assume it is safe under
the conditions.

In all cases the QUIC endpoint MUST include the CID in the additional data
authentication to ensure routing data has not been tampered.

One could also take this a step further and shorten the first 64 bits, but
that is probably a rats nest: 16, 32, 64, 128 bits.



Kind Regards,
Mikkel Fahnøe Jørgensen


On 12 January 2018 at 16.51.19, Lubashev, Igor (ilubashe@akamai.com) wrote:

The point here is that if 128-bit is an option from V1, then all clients
will support it, and the server can choose to always use 128-bit connection
IDs.  The load balancer then can be sure that valid connection IDs (in
packets featuring server connection ID) can only be 128-bit.  If V1 does
not have 128-bit support, then the server must develop a less secure
version of the connection ID to fit into 64 bits, and the load balancer
must treat 64-bit connection IDs as acceptable.  Then, there is nothing to
prevent an attacker from using 64-bit connection IDs, if that’s more
convenient for them.



*From:* Ian Swett [mailto:ianswett@google.com]
*Sent:* Friday, January 12, 2018 9:35 AM
*To:* Lubashev, Igor <ilubashe@akamai.com>
*Cc:* quic@ietf.org; huitema@huitema.net
*Subject:* Re: Increasing QUIC connection ID size



I think we'll want support for both no matter how we do this.



On Fri, Jan 12, 2018 at 9:13 AM, Lubashev, Igor <ilubashe@akamai.com> wrote:

If the 128-bit option is not in V1, then it will be required for the
128-bit option to be signaled in the packet's invariant section (like a bit
in the 1st byte). Otherwise, the very load balancers this is designed for
will not know whether the connection ID has 64- or 128-bit format. (It
would need to support both, since there would be clients stuck at V1.)

In fact, the security promises of having a 128-bit connection ID option
(allows for making routing info harder to forge) are greatly diminished,
when a load balancer has to support 64-bit connection IDs "forever".



-----Original Message-----
*From:* Ian Swett [ianswett@google.com]
*Received:* Friday, 12 Jan 2018, 8:59AM
*To:* Christian Huitema [huitema@huitema.net]
*CC:* IETF QUIC WG [quic@ietf.org]
*Subject:* Re: Increasing QUIC connection ID size

I would like to leave QUIC open for longer connection IDs in future
versions, so I'd like to specify the invariants in such a way that longer
connection Ids wouldn't violate them(ie: Victor's suggestion
of “middleboxes always get first 64 bits and they have useful entropy to
distinguish connections”.) but I'm reluctant to include 128 bit connection
IDs in v1 at this point.


I would also echo Christian's sentiment that the incremental overhead
starts becoming fairly large.



On Thu, Jan 11, 2018 at 9:47 PM, Christian Huitema <huitema@huitema.net>
wrote:

We have a prototype implementation in Picoquic in which the connection ID
can be split so some bits are random and some bits are used for routing to
a specific server -- thanks Igor for that. It makes for nice experiments,
but it is a denial of service waiting to happen. For example, attackers
could set the bits in such a way as to target a specific server in a pool,
or they could learn which connections are on the same server and use that
later for some kind of same server attack. It would be better if that
information was not in clear text. In fact, the picoquic implementation use
a callback to ask for the new value -- presumably from the router. That
callback could return anything, including an encrypted value.

On the other hand, it is not clear to me that we need full encryption. For
example, assume that the server that needs a connection ID can ask it from
the router. The router could pick one at random, make sure that it is
properly documented in the routing tables and that there is no collision,
and then pass it back to the server. No encryption needed, but of course
lots of state.

If the router does not want to keep the state, it can indeed create a
connection ID by encrypting a <nonce, server-ID> tuple. But it does not
follow that the encryption needs to be 128 bits. For example, it could use
a 64 bit algorithm like Blowfish.

So I am not sure that we actually need to change the length. And I am a bit
concerned by the incremental overhead if the connection ID suddenly becomes
very large.



On 1/11/2018 2:25 PM, Mikkel Fahnøe Jørgensen wrote:

Actually, on encryption of connection ID, this is not so simple.



We must assume there is only a single key for many connections because the
router is not part of a key exchange. This unique value or counter used for
encrypting a single block cannot be the same for two different connections
ID’s, but it can be public. This means that it must be stored in the packet
header. And, as it turns out, random connection ID chosen by a trusted
source, can be used for such a unique value. But then it must be used to
encrypt and/or authenticate something else carrying the actual routing
information. So now you start to really need some extra payload.



Alternatively the routing information is entirely random such as content
hashed routing. Then you only need to authenticate the routing data. You
can do that with a HMAC, and CMAC could probably also work. The additional
benefit is that you can probably get away with 64-bits for all routing
information possibly including the auth tag. Say 48 bits of routing data
and 16 bits of auth tag.



Kind Regards,

Mikkel Fahnøe Jørgensen



On 12 January 2018 at 00.57.21, Lubashev, Igor (ilubashe@akamai.com) wrote:

I am interested in exploring this proposal, since it allows for more
flexible schemes of encoding routing metadata and a checksum.  I would also
like to be explicit about the connection ID size in a packet header,
though, since it greatly simplifies the implementation.



   - Igor

*From:* Victor Vasiliev [mailto:vasilvv@google.com]
*Sent:* Thursday, January 11, 2018 6:16 PM
*To:* IETF QUIC WG <quic@ietf.org>
*Subject:* Increasing QUIC connection ID size



Hi everyone,



In the current version of QUIC, the connection ID size is fixed to be a
64-bit opaque blob, and that is set as an invariant in the protocol.



I’ve looked into possibility of using a connection ID to encode the
specific server details into it (to provide stability of the connection in
case of load balancing changes, especially BGP flaps for anycast IPs), and
have chatted about this with other people I knew were interested in this.
It seems like 64 bits might be too small for this purpose, and we might
want to leave an opportunity to extend the connection ID size.



The basic idea is that you want to be able to:

   1. Store some routing metadata in the connection ID.
   2. Have some entropy that allows distinguish users with identical
   routing metadata.
   3. Have a checksum to ensure the validity of routing information
   4. Encrypt the information above to prevent disclosing the route
   information and allow generating uncorrelatable connection IDs.

There are two underlying issues here.  The first problem is that all of
this does not fit well into 64 bits, and you have to seriously compromise
on the strength of the checksum (which is bad especially if you want it to
be a MAC rather than a checksum).  The second problem is that encrypting
64-bit values fast is actually fairly hard since the block ciphers easily
available in hardware have 128-bit block size, and the performance
requirements on load balancers are tighter than on servers.



In other words, having a 128-bit connection ID provides for an easy secure
way to generate unlinkable connection IDs on migration.



So, the problem we’re trying to solve is that the connection ID is too
small.  There are two questions I believe the working group should answer
at this point:

   1. Do we want to address this problem at this point in standardization
   process?
   2. If we don’t address this problem right now, how do we structure the
   standard in a way that we can extend the connection ID in the future?

There are multiple ways to solve the problem of making connection ID
larger.  One is to just add extra bit to the “omit connection ID” field to
allow 128-bit connection IDs.  Another approach is to allow connection ID
size to be explicitly specified by the server, and then assume that the
load balancer knows that size and no one else on the path needs to read it.



There’s also a question of how much of connection IDs do middleboxes
(excluding load balancers and other boxes owned by the same entity as
either client or server) need to know.  We could go for both “middleboxes
should be always able to read the entire ID” and “middleboxes should not
read connection IDs at all options”, but I think there’s also a room for
more flexible formulations like “middleboxes always get first 64 bits and
they have useful entropy to distinguish connections”.



  -- Victor.