Re: Asymmetric CIDs

Martin Duke <martin.h.duke@gmail.com> Fri, 16 February 2018 17:52 UTC

Return-Path: <martin.h.duke@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 A9BD1124C27 for <quic@ietfa.amsl.com>; Fri, 16 Feb 2018 09:52:48 -0800 (PST)
X-Virus-Scanned: amavisd-new at amsl.com
X-Spam-Flag: NO
X-Spam-Score: -2.699
X-Spam-Level:
X-Spam-Status: No, score=-2.699 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] 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 jM9vScvYnQ28 for <quic@ietfa.amsl.com>; Fri, 16 Feb 2018 09:52:46 -0800 (PST)
Received: from mail-wm0-x22b.google.com (mail-wm0-x22b.google.com [IPv6:2a00:1450:400c:c09::22b]) (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 AC4B11200C1 for <quic@ietf.org>; Fri, 16 Feb 2018 09:52:45 -0800 (PST)
Received: by mail-wm0-x22b.google.com with SMTP id k87so4595976wmi.0 for <quic@ietf.org>; Fri, 16 Feb 2018 09:52:45 -0800 (PST)
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20161025; h=mime-version:in-reply-to:references:from:date:message-id:subject:to :cc; bh=VnwlaxtUpMXMTnWTkXteQwV01THz6bLQrYszky1NbAk=; b=SkZCOKjW2OVjFpPJftC7Di3mCJgZxUr2Tl8ajGBFfCQfPEYzD9TAHFp1OAjIiUzo3I lSrVYaOglutYv/F90Y14DR9PC5O0MspTCEso5HZTOFbOakWe+KD2su648ZMmaOu55WH0 PMgPmR/ljQ8llxvgxN/M18EQkLeC1r/+ExVyDXysnVqISYJo8ubn5xda3XDzE2iQL5kP vwIBkobz+6jthUyhfhtZHTf/Iv5smJ8QzHJjmbzW1hlL7cqTRCSm0QjAbsP0ItMtJhdJ W1FRu58biqRc8BfBAhl3106czwCcmhoSwWFefEib6bEGSRIe41FgtA8tpzJ5s28SY4Qp 2tmQ==
X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20161025; h=x-gm-message-state:mime-version:in-reply-to:references:from:date :message-id:subject:to:cc; bh=VnwlaxtUpMXMTnWTkXteQwV01THz6bLQrYszky1NbAk=; b=M+k1h884MCBLm64SXDzd3CQN7sBF/QPmHTfhuILXWY6xH9IV2IM/V3ciCHanz6rvsH ULeFbNJoqYYSIl05lWQc1TFrNVWBcAlkKS5ii3yhX1Re2Q0Th7vm9rlbJ5Jjj7Sw/L6d i57X9ASUE5NfTqinN81t8/3I/QWiZ+5yiQK9egwkKjEQUC4488piHp2E9yeip1N/Z5E2 sy2ZFWI0InahU/Q2xB5N9OrpHIBcYQE1ELDDkvpZ5fXgDSFn0keArVxuGwnIj1Xqb0dU CD3gCb9aKVaBZYXeO993Sz4z5NwEAfT2ofG4iFM8ArwalDu2/JLaSKJ/DHmWqJear10p FJKg==
X-Gm-Message-State: APf1xPAm2AogyV3I8P5Ix8OaxcnXpwit20LGEGsqWpXlxyqDwzsm9OLj H1teYrvQ9ZRhtkwYusWg/RK+dKhfJk47IAdDK6o=
X-Google-Smtp-Source: AH8x226ngEqS+VVP5lPsPqGRzOh9VsqxWfiekfaoJZHY9veRe2LYYFt9KwLoL+hRTKG5St4Re1Xr7qNx+QfIdT5tSxg=
X-Received: by 10.28.66.77 with SMTP id p74mr5293035wma.115.1518803564039; Fri, 16 Feb 2018 09:52:44 -0800 (PST)
MIME-Version: 1.0
Received: by 10.223.166.71 with HTTP; Fri, 16 Feb 2018 09:52:43 -0800 (PST)
In-Reply-To: <CAKcm_gOvf0N7sq2so38sQaD+2jHGnDpsSQHEwU8HPgSpMJRfzA@mail.gmail.com>
References: <CABcZeBMVabN9LQ42BxpSwK71hzu_TbzwqhHTJV1uJBKr5g-N3A@mail.gmail.com> <CAKcm_gOvf0N7sq2so38sQaD+2jHGnDpsSQHEwU8HPgSpMJRfzA@mail.gmail.com>
From: Martin Duke <martin.h.duke@gmail.com>
Date: Fri, 16 Feb 2018 09:52:43 -0800
Message-ID: <CAM4esxQW1-dVfJSi4zoURNV-7u0EP6h-Xdyx5Wbo0QMdrkLk=w@mail.gmail.com>
Subject: Re: Asymmetric CIDs
To: Ian Swett <ianswett@google.com>
Cc: Eric Rescorla <ekr@rtfm.com>, IETF QUIC WG <quic@ietf.org>
Content-Type: multipart/alternative; boundary="94eb2c0742eceb133c0565580252"
Archived-At: <https://mailarchive.ietf.org/arch/msg/quic/Iy5f9XCMolgvsSwdvbN69vadmWo>
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, 16 Feb 2018 17:52:49 -0000

Thanks for writing this up, ekr. This incorporates many of the suggestions
I made in objection to this project (perhaps coincidentally) and I like it
a lot.

Advantages of this:
- In the common case where most of the data is server->client, clients can
get away with shorter Conn IDs to reduce overhead.
- Omit-conn-id just becomes a case where length = 0. Does this sidestep
some of Google's transition issues?
- If a client sends NEW_CONNECTION_ID, that indicates an intention to
migrate, and is a good cue for the server to send the same. We should add a
SHOULD to specify this behavior.

I must be missing something, however, regarding implicit CIDs.

If there's a NAT rebinding, how is the server supposed to extract the CID?
Furthermore, this obviates the entire concept of using Connection ID for
routing; it's not obviously a savings to store CID length in a table vs.
just storing the destination server.

Lastly, if we encode the length somewhere that seems to solve the Stateless
Reset issue.


On Fri, Feb 16, 2018 at 9:25 AM, Ian Swett <ianswett@google.com> wrote:

> Thanks for the excellent summary EKR.  I like this design and think the
> breakage of stateless reset in certain cases is acceptable, since it only
> applies if both sides must have their preferred connection ID present in
> order to route correctly, which is a use case that's impossible in the
> status quo.  I have not come up with any other downsides.
>
> On Fri, Feb 16, 2018 at 12:01 PM, Eric Rescorla <ekr@rtfm.com> wrote:
>
>> Hi folks,
>>
>> After a bunch of discussion, the CID task force came down to rough
>> consensus that asymmetric conn IDs were probably the right
>> direction (CID task force members, please feel free to voice dissent
>> here). Here's a complete writeup of what I think would be needed
>> for asymmetric connection IDs. It's not a PR, because I think
>> something self-contained is cleaner.
>>
>> Note that if we adopt this direction, we would be sacrificing
>> public reset under some conditions (see previous emails to the
>> list) and we would need to decide if it was worth keeping at all.
>>
>>
>> OVERVIEW
>> The basic idea is that each side gets to dictate the connection IDs
>> that are used to send to it. During the handshake, you establish those
>> CIDs and then each side can issue new CIDs during the connection.  The
>> main advantage of this is that it allows for symmetric topologies in which
>> the client is also behind some kind of stateless LB/router rather than
>> just the server. See Issue #1091 for more info on this.
>>
>>
>> The overall handshake looks something like this:
>>
>> Client                                      Server
>>
>> Initial [CID=XXX] {recv-CID=YYY} ---------------->
>> <-------------- Cleartext [CID=YYY] {recv-CID=ZZZ}
>> Cleartext [CID=ZZZ], {recv-CID=YYY} ------------->
>> <-------------------------- Short header [CID=YYY]
>> Short header [CID=ZZZ] -------------------------->
>>
>>
>> The client's initial CID (XXX) is special, and either consists of
>>
>>     (a) a randomly chosen dummy CID. Proposal: require this to be
>>         8 bytes or at least a minimum. This should be the same
>>         for all Initial packets in a connection (unless a stateless
>>         reject is received, as below).
>>     (b) a CID which it received from the server in a stateless reject
>>
>> All the server's packets are sent with the client's receive CID (YYY)
>> and all subsequent client packets are sent with the server's receive
>> CID (ZZZ). The general rule is that you should send with the
>> connection ID that you most recently received (where recently
>> is defined as highest PN).
>>
>> Note: I believe it's safe to just use the sending CID as the mixin
>> for the KDF, but I haven't thought this entirely through yet.
>>
>> Finally, you can send NEW_CONNECTION_ID in either direction to provide
>> a new connection ID for the other side to use. The general assumption
>> is that you can do this at any time, just as with current QUIC, and
>> that any time you send to a new remote 3-tuple you should change CIDs
>> if you can. Note that this means that endpoints should try to make
>> sure that the other side has spare CIDs in case they need to migrate.
>>
>>
>> WIRE ENCODING
>> As we discussed in the meeting the short header should just have
>> an implicit length CID. This gives us the following short header:
>>
>>    +-+-+-+-+-+-+-+-+
>>    |0|C|K| Type (5)|
>>    +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
>>    |                                                               |
>>    +                     [Connection ID (*)]                       +  <-
>> change from 64
>>    |                                                               |
>>    +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
>>    |                      Packet Number (8/16/32)                ...
>>    +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
>>    |                     Protected Payload (*)                   ...
>>    +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
>>
>> Note that we may also be able to dispense with the C bit, if each
>> side just gets to say "send me this CID exactly", why do we want
>> to say "here is my CID but you can omit it".
>>
>>
>> We have several options about the long header. The first question
>> is where recv-CIDs go. In previous versions I suggested putting
>> them in transport parameters, or elsewhere in the TLS handshake,
>> and that might still be viable, though it has some drawbacks [0],
>> so the other alternative is to put both CIDs in in the long header.
>> This would look something like:
>>
>>    +-+-+-+-+-+-+-+-+
>>    |1|   Type (7)  |
>>    +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
>>    |  DCID-Length  |                                               |
>>    +-+-+-+-+-+-+-+-+   Dst Connection ID (*)                       +
>>    |                                                               |
>>    +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
>>    |  SCID-Length  |                                               |
>>    +-+-+-+-+-+-+-+-+   Src Connection ID (*)                       +
>>    |                                                               |
>>    +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
>>    |                         Version (32)                          |
>>    +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
>>    |                       Packet Number (32)                      |
>>    +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
>>    |                          Payload (*)                        ...
>>    +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
>>
>> The semantics here are that the first value is the CID you want to
>> send to and the second one is the value you want used to send to you
>> (I've inverted these to keep the order the same as short header).
>>
>> Two notes about this encoding:
>>
>> 1. I think we agreed that we didn't want arbitrary length CIDs up to
>> 255 bytes, and yet we have room in this length byte. I propose we
>> limit it to 31 bytes and then grease the remaining 3 bits [1].
>>
>> 2. Because the client sends its CID first, there's no way to get the
>> current QUIC semantics of the server just dictates the CID.  I propose
>> we fix that by defining a special sentinel CID (all 1s, all 0s,
>> whatever) of whatever our maximum length is that means "just use your
>> own CID".
>>
>> We can endlessly bikeshed on this structure.
>>
>>
>> Finally, we will need to update NEW_CONNECTION_ID to allow a variable
>> length CID. This would look like this:
>>
>>     0                   1                   2                   3
>>     0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1
>>    +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
>>    |                          Sequence (i)                       ...
>>    +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
>>    |  CID-Length   |                                               |
>>    +-+-+-+-+-+-+-+-+       Connection ID (*)                       +
>>    |                                                               |
>>    +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
>>    |                                                               |
>>    +                                                               +
>>    |                                                               |
>>    +                   Stateless Reset Token (128)                 +
>>    |                                                               |
>>    +                                                               +
>>    |                                                               |
>>    +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
>>
>>
>>
>> [0] However, in the transport parameters design, if the server's
>> handshake gets reordered, the client might need to send some ACKs with
>> the initial CID. However, we've agreed that the client's IP address
>> has to be stable, so this isn't a problem. Alternately, you could
>> change C->S CIDs in the short header if that was easier.
>>
>> [1] An alternative would be to have a sparse range (e.g., you can
>> express 0-7 and then 8-22 by 2s, assuming I have counted correctly)
>> and then we could pack both lengths into a single byte. As I said,
>> lots of opportunities for bikeshedding here.
>>
>>
>