Re: Asymmetric CIDs

Mikkel Fahnøe Jørgensen <mikkelfj@gmail.com> Mon, 19 February 2018 19:07 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 EE6A7127873 for <quic@ietfa.amsl.com>; Mon, 19 Feb 2018 11:07:28 -0800 (PST)
X-Virus-Scanned: amavisd-new at amsl.com
X-Spam-Flag: NO
X-Spam-Score: -1.698
X-Spam-Level:
X-Spam-Status: No, score=-1.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, FREEMAIL_REPLY=1, HTML_MESSAGE=0.001, RCVD_IN_DNSWL_LOW=-0.7, SPF_PASS=-0.001, UNPARSEABLE_RELAY=0.001] autolearn=no 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 JARRr3dNeY07 for <quic@ietfa.amsl.com>; Mon, 19 Feb 2018 11:07:26 -0800 (PST)
Received: from mail-io0-x22a.google.com (mail-io0-x22a.google.com [IPv6:2607:f8b0:4001:c06::22a]) (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 76878127735 for <quic@ietf.org>; Mon, 19 Feb 2018 11:07:26 -0800 (PST)
Received: by mail-io0-x22a.google.com with SMTP id z6so12331837iob.11 for <quic@ietf.org>; Mon, 19 Feb 2018 11:07:26 -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=qfki32fstucBNTuOLxUW8clKhqDRbfTp+WoJSm+Sp9Q=; b=HH6R2B6mpfzluJ5g4V/J8j3mR6/JnwrTlsbW6neEqPzY2IAtiaM2THO62j0ZFP5TRQ gthvJBsi1rT5fY601M2sV3+gvgAKcebmBylOpZCCOgYglhoKUDIfQ6v+ov8NeXDBshEt AbGg9wmomAcAXsnGN6nsd713GG/cvQKWefC0OsQpSgjx04k3953W0oP5yiMSOENBy0X6 OHtwVI0BeUBRCINZxX034Wtm+UdknNAUlYpSbIkpQWTdD+X9VDU/sFHtPXTU/qL308ao t4zgtykNsDnnlGVU7zvFIArb0mZOGLWsCpsNfD3Jk1f1Hun6IzWaUZY/7uX7aGbqz+A6 IJFw==
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=qfki32fstucBNTuOLxUW8clKhqDRbfTp+WoJSm+Sp9Q=; b=A4dFHXXcX4xRspoHY7gkEEZrVpJ3Flphkx8T+GFWMHup3ZXM24DlrSdWlYwjw7KZj0 SAWpbloWB6HI3KL6Ed8Q8EEoI07wwY2Lb42hu32UZYfjoAkj1FyaGOBqWnoLTD+5M6IV c/OsGft1QWuKbSxYiCh4n4pw95pt/7pbJTTIzFxMrlwGyGXpvgT8NQ8eVXsYO0QVLgHc oAShH1xO8OWEAVbjpJttsyRr+kxq3oeDhkvRkUSOQuWhKp+J+47OYiMzGDkTgOQ70l9s /h7ucgNMb5Vx6yApduZvYUhA6Rclgg1OXWQJqZJsdhtwwd8m7jVfVlAhAtQcGcXlawDl e+qQ==
X-Gm-Message-State: APf1xPCF9b94hkEcjAuEOTDgtDYa07llMM03DSRbzBUyYmF+OtpxOBzz CJ16c57qkAqcPs/MC9hPYRcZ1E+2JglWynhTIL5rKw==
X-Google-Smtp-Source: AH8x2254kz3PDmhZu7SolgyA0Kc7bUso41EqX9+Gl3425h6a3t1VSftDEb/RwF+xqENCBlgcLDrWXUx9yNLNbLMyrFc=
X-Received: by 10.107.212.7 with SMTP id l7mr2296824iog.70.1519067245679; Mon, 19 Feb 2018 11:07:25 -0800 (PST)
Received: from 1058052472880 named unknown by gmailapi.google.com with HTTPREST; Mon, 19 Feb 2018 11:07:24 -0800
From: =?UTF-8?Q?Mikkel_Fahn=C3=B8e_J=C3=B8rgensen?= <mikkelfj@gmail.com>
In-Reply-To: <CABkgnnVTeAWomSnajdPZN=KfqFWdH3E=UDe4gyG8KNafipe+Yw@mail.gmail.com>
References: <CABcZeBMVabN9LQ42BxpSwK71hzu_TbzwqhHTJV1uJBKr5g-N3A@mail.gmail.com> <CAKcm_gOvf0N7sq2so38sQaD+2jHGnDpsSQHEwU8HPgSpMJRfzA@mail.gmail.com> <CABkgnnVTeAWomSnajdPZN=KfqFWdH3E=UDe4gyG8KNafipe+Yw@mail.gmail.com>
X-Mailer: Airmail (420)
MIME-Version: 1.0
Date: Mon, 19 Feb 2018 11:07:24 -0800
Message-ID: <CAN1APde3-MnC+X1A9C0a=EKymA_fOSgyNC-a4t5Sv5tKyA99HA@mail.gmail.com>
Subject: Re: Asymmetric CIDs
To: Martin Thomson <martin.thomson@gmail.com>, Ian Swett <ianswett@google.com>
Cc: Eric Rescorla <ekr@rtfm.com>, IETF QUIC WG <quic@ietf.org>
Content-Type: multipart/alternative; boundary="f403043d0f88919b6b05659567ef"
Archived-At: <https://mailarchive.ietf.org/arch/msg/quic/w-xrSa_AzMRl0U6WYWRTwp8ONvE>
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: Mon, 19 Feb 2018 19:07:33 -0000

I don’t want to shoot down ACID at all, but if a stateless reset is
intended to be invisible (not sure why? ossification?, hardly replay?) then
it cannot reflect the clients CID because it would light up like a
Christmas tree simply because the CID is the same in both directions,
unless CID’s are somehow encrypted which would be hard for stateless reset.

On the other hand, if the reset is intentionally visible, then peer routers
could attempt to match the reverse routing path, or do some internal
broadcasting find and terminate the relevant destination.

Resets should exponentially back off, but that binds state which could be
exploited to a degree.

Resets could enter a strange ping pong pattern, especially when not routed
correctly: B sends reset to A, A does not understand reset and sends a
reset to B to silence A, which in turn sends a reset to A.

A and B is cluster, so there could be many endpoint in each so back-off
would not kick in.

As I said before, I’d prefer clients to stop sending when peer is not
responding. If a reset is to work, the other end needs to cooperate anyway.
Routers could drop packets of unwanted CID’s. This would also handle cases
where peer receives packets and ACK’s but the return path is broken
(eventually timeout will kill, but it could happen faster with a challenge).

Kind Regards,
Mikkel Fahnøe Jørgensen


On 19 February 2018 at 01.30.50, Martin Thomson (martin.thomson@gmail.com)
wrote:

The breakage of a stateless reset is limited. It is only a problem
for clients that use - and depend on - connection IDs.

A stateless reset will not carry the client-selected connection ID.
It will appear - to the network - to be a change in connection ID. If
we change connection IDs occasionally for other reasons, then this
won't be a significant problem.

The main problem is in ensuring that the packet arrives at the right
place at the client. However, it is possible that we can suggest
routing based on address tuple over short timescales at clients. In
that case, the reset might still arrive at the right place. That, or
exceptional processing for unrouteable packets.

BTW, I like ekr's idea of making the number space for connection IDs
sparse. A (short-ish) fixed limit is necessary to ensure that the
stateless reset can be constructed such that it appears plausible and
that means at least overhead + max(connection ID) + AEAD expansion +
an ACK frame.

Would also add the idea of a minimum size for connection IDs. A one
octet connection ID has awful linkability properties that are pretty
much irredeemable. You can get 8-22 with single octet steps if you
are willing to make 1-7 invalid.


On Sat, Feb 17, 2018 at 4: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.
>>
>