Re: Increasing QUIC connection ID size

Mikkel Fahnøe Jørgensen <mikkelfj@gmail.com> Thu, 11 January 2018 23:54 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 1E8E11205F0 for <quic@ietfa.amsl.com>; Thu, 11 Jan 2018 15:54:25 -0800 (PST)
X-Virus-Scanned: amavisd-new at amsl.com
X-Spam-Flag: NO
X-Spam-Score: -2.697
X-Spam-Level:
X-Spam-Status: No, score=-2.697 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, URIBL_BLOCKED=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 OfCcvdBhe_VG for <quic@ietfa.amsl.com>; Thu, 11 Jan 2018 15:54:22 -0800 (PST)
Received: from mail-io0-x22c.google.com (mail-io0-x22c.google.com [IPv6:2607:f8b0:4001:c06::22c]) (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 E5EC61275C5 for <quic@ietf.org>; Thu, 11 Jan 2018 15:54:21 -0800 (PST)
Received: by mail-io0-x22c.google.com with SMTP id d11so3928498iog.5 for <quic@ietf.org>; Thu, 11 Jan 2018 15:54:21 -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; bh=jTaROEe+NJ3UJdRmv8OKXMhyJUQuwJgLq276piXqWNc=; b=Xv6X9MFfr+1WidvxqF1EqHxSWUriX1QBkSNS9DGdhMjjxuA6jHFP5VKSDiHzsO2QcU pBIgyF9ffZgw+KrK9w23KtLsQpeoUytROhFLtTHYQcRi39+k6Tk9gJYvcBQcuSnyG1Uf obAu1wNOd4Jrf9BR4F1OoBpqtiz06Zs+B2/MrWofB7xe4xLfPqiKAUgkS6UIotsu+ZUx NeLaec5Qdsb90Ep/ik6cRpoaHkddDS5BZeu+SouFuWtazbXuhKhbBVf8EczJOgc2gFTK 9aYF6R/T50DKGwQ/7d6UyTNdMxE0NOhi/jqELaPKiPXsgoC5E5Dtf31LWBA7u4V+X8kc 2pzg==
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; bh=jTaROEe+NJ3UJdRmv8OKXMhyJUQuwJgLq276piXqWNc=; b=VYizN/ZQJG+4/VMV3UG/Oo5MJbE6Bv7WjBovTdW/FS8Ds2xysUViPLMi4RdJd9OapA jqVghsvC4DrPkNe8+14C1u/iBcARWFaSiB2WKfaIfm54oLwdGtRAJJyYgOPgf6yo+xCy P0MYPylGOfnVa7iRYRIl2LVwvk4C18FZMXE/U/5mDblyQw2H1R706lxbZXNOC615oEPS HvHeuFE8iKgiEeD4C3fcaY97EWwcMsIheVDbefcSNhXNHviy2iGccco8BmtZwbsGHzNU OYmeqaJlCPikiSPj1WorrlD3MiTEAoXquQZm484KpPeydFA9vIf/ybO4Es2Ukq/b9aoi dboQ==
X-Gm-Message-State: AKGB3mIxVA6G8LoMC09KMxQdzLwV8BGe0WzmvpF635wo7AlhnZwl8r3d ISQImxW3/DKf1C/4pIvtvqHoNdBG6G5XNGzTdIXJd+82
X-Google-Smtp-Source: ACJfBouRpMwgMACBxHVhtiUpGV4YgMeHj7oSxUcKORP9a3DzqThYPjheNbOjLE5uM9qq04DufEobkk/KfcVtscikbCQ=
X-Received: by 10.107.5.142 with SMTP id 136mr24000220iof.239.1515714861261; Thu, 11 Jan 2018 15:54:21 -0800 (PST)
Received: from 1058052472880 named unknown by gmailapi.google.com with HTTPREST; Thu, 11 Jan 2018 15:54:20 -0800
From: =?UTF-8?Q?Mikkel_Fahn=C3=B8e_J=C3=B8rgensen?= <mikkelfj@gmail.com>
In-Reply-To: <CAN1APdfmZLUuwbnhU87yf-Kqgx3OquGFLUPHXTUnEvK1+kOKWQ@mail.gmail.com>
References: <CAAZdMad=YnTyXG-q0ACpT=tyCSX1GgRLvb=8HT3Au=e9_XT5Ag@mail.gmail.com> <CAN1APdfmZLUuwbnhU87yf-Kqgx3OquGFLUPHXTUnEvK1+kOKWQ@mail.gmail.com>
X-Mailer: Airmail (420)
MIME-Version: 1.0
Date: Thu, 11 Jan 2018 15:54:20 -0800
Message-ID: <CAN1APdfABGfy=YoYkdZgCW1JB-wQOscQEbuSLqjTwabb8bRheQ@mail.gmail.com>
Subject: Re: Increasing QUIC connection ID size
To: Victor Vasiliev <vasilvv@google.com>, IETF QUIC WG <quic@ietf.org>
Content-Type: multipart/alternative; boundary="001a113edec0e2e912056288dda7"
Archived-At: <https://mailarchive.ietf.org/arch/msg/quic/UnpQ_Vndt7-gXn1rsgt---Y275s>
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: Thu, 11 Jan 2018 23:54:25 -0000

EDIT: I didn’t propose CMAC on connection ID - it needs to change, so it
would be on the packet number for the sake of fast rejection of invalid
packets. The counter argument was that it is fast enough to check the auth
tag of the entire message.

Kind Regards,
Mikkel Fahnøe Jørgensen


On 12 January 2018 at 00.51.39, Mikkel Fahnøe Jørgensen (mikkelfj@gmail.com)
wrote:

I can also see a need for larger connection ID’s for routing purposes in
overlay networks, but I decided it was probably better to prefix the QUIC
header in that case.

It is worth noting that if you have a non-unique tuple of port-address
pairs, you need the connection ID in every packet, and that can be a lot of
overhead. So a large ID would likely isolate that version to a dedicated
purpose, and then you might as well add a packet prefix.

An alternative solution is to use the connection ID as an index into a
routing table that has the real details, but this requires that early
packets of the connection carry those details in a way that routers can
pick up which probably isn’t practical.

A more practical solution is to keep the connection ID as is to serve its
primary purpose. A given protocol version could negotiate an extension the
the clear text header. Even if those data are not directly following the
connection ID, they can easily be picked up by router. This is essentially
the same as a packet prefix, except that the QUIC invariants are now
maintained.

As to encryption: block encryption generally works by xor’ing a “random”
value to the clear text. AES produces such a value from a counter or
similar unique value per block but does not need the clear text data at
all. The output of AES is simply XOR’ed with the clear text data (this can
be different when encrypting multiple blocks). This means that if the block
size is 128 bit you can easily encrypt 64 bytes by XOR’ing with the first
64-bits of the AES output. But you likely want to zero extend instead due
to auth tag:

It is not safe to use block encryption alone. It must nearly always be
associated with an authentication tag as with AES-GCM. Otherwise an
attacker will quickly learn that, say, bit 53 and bit 32 affects routing
and can trivially cause at least 1/4 packets to land somewhere else just be
flipping either bit. A compact auth tag does not have to be very long for
such a short message but it adds to the overall size requirement and
complexity of the solution.It could be generated with CMAC that are two AES
encryption rounds. (CMAC on connection ID could, BTW, also be used to very
quickly reject invalid QUIC packets, which I have proposed earlier). The
CMAC output will be one AES block, but it can be truncated depending on the
security level required.


Kind Regards,
Mikkel Fahnøe Jørgensen


On 12 January 2018 at 00.16.21, Victor Vasiliev (vasilvv@google.com) wrote:

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.