Re: [MLS] Proposal: Proposals (was: Laziness)
Richard Barnes <rlb@ipv.sx> Wed, 18 September 2019 22:16 UTC
Return-Path: <rlb@ipv.sx>
X-Original-To: mls@ietfa.amsl.com
Delivered-To: mls@ietfa.amsl.com
Received: from localhost (localhost [127.0.0.1]) by ietfa.amsl.com (Postfix) with ESMTP id CE49D1200C7 for <mls@ietfa.amsl.com>; Wed, 18 Sep 2019 15:16:25 -0700 (PDT)
X-Virus-Scanned: amavisd-new at amsl.com
X-Spam-Flag: NO
X-Spam-Score: -1.896
X-Spam-Level:
X-Spam-Status: No, score=-1.896 tagged_above=-999 required=5 tests=[BAYES_00=-1.9, DKIM_SIGNED=0.1, DKIM_VALID=-0.1, HTML_MESSAGE=0.001, RCVD_IN_DNSWL_NONE=-0.0001, SPF_HELO_NONE=0.001, SPF_NONE=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=ipv-sx.20150623.gappssmtp.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 HeW-xMuSxjUw for <mls@ietfa.amsl.com>; Wed, 18 Sep 2019 15:16:22 -0700 (PDT)
Received: from mail-ot1-x341.google.com (mail-ot1-x341.google.com [IPv6:2607:f8b0:4864:20::341]) (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 B1FF012002F for <mls@ietf.org>; Wed, 18 Sep 2019 15:16:22 -0700 (PDT)
Received: by mail-ot1-x341.google.com with SMTP id 21so1270087otj.11 for <mls@ietf.org>; Wed, 18 Sep 2019 15:16:22 -0700 (PDT)
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=ipv-sx.20150623.gappssmtp.com; s=20150623; h=mime-version:references:in-reply-to:from:date:message-id:subject:to; bh=NGh4ErRkXdM85Q5080vwzWYpO5wJxiGVBrc0zP0zV98=; b=UJ6+uHWimrTgiVZFd6GF0g9wVXO0nLJMmLfjW0Eo4D8UhOYkFBzWKmvofOr0yd7MQm 0IY+0XFnE/kL5Z5dylZZoLS6fc6ADy+TQvxBemJGQz3KG6K6hF+2yyCLPkW4D8ucb6LL npsFxinQp9peDT/n9svIIetT8nruwxf0l5MaWeoMHx8fPBfFgwcjvxgYTcX6wLKNZqOG m2ebTLET5iZOd+MbQ6tbEOVcKW7YalGBGfucJ9tEzwJ5gpP1gu9bC1ufYQ4She64xPw6 FDxZ69eplitgrTi2maHZFxK4HNUbhfObU8LnZtDXZaDiBgk+waRXUz4Y+d/DhQuBPVWT ZZkw==
X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20161025; h=x-gm-message-state:mime-version:references:in-reply-to:from:date :message-id:subject:to; bh=NGh4ErRkXdM85Q5080vwzWYpO5wJxiGVBrc0zP0zV98=; b=o0548b2JhmBVeO8A6A4jwJk7R9Y3H4fyiSv6PI1fvN1bd/xOA1ahn7+sLVJhSoWuBK tynA9AnUsvk3aBLg/tmmwTktkfHPTm/koIOtIngRqBvHnIrQicYlwE0TWn2k/LjEBPeP XqQ6fEzaAZ/6vgiHqOMLvVhYNEwHNnV4Tz04vVHN0vl9IBMgOIKyMNcnWfFAsu1TnZBi euWcBmYkgB+MiOOTTZH80J4lJrq2quOGRaZdgCU2bAr8JNOiBflbQHSOjhsgnfxKsShT SYZB2XQeNGxGPBBt8tsV4Zh5xrrwIIjhckmXATxD4nwOUfa1EjB30yaYaGfJuM+ngDvy 9vZg==
X-Gm-Message-State: APjAAAWX5FHBIVO1feiPftKjLRXcg0o2ajtv2P14iyIzIkGL9/+1YYPc fU7Tx1rtfZiozmx+nwL/8KodH0yknxEfqbHyXejaUsvzX+Fa6A==
X-Google-Smtp-Source: APXvYqwP59xJGHV+SCITxtrToiVon1TZ+UkVIES7lpUO+j+rh64UwBxOyTjXvRZ1b6Fe3c0VvJsx2CW5V2jnqTxMbyM=
X-Received: by 2002:a9d:6d82:: with SMTP id x2mr1566720otp.42.1568844981503; Wed, 18 Sep 2019 15:16:21 -0700 (PDT)
MIME-Version: 1.0
References: <CAL02cgSbgkYyMcm=w8+oF+R5GBKaaofV3_x_VF0rMc0jWhs+Kg@mail.gmail.com>
In-Reply-To: <CAL02cgSbgkYyMcm=w8+oF+R5GBKaaofV3_x_VF0rMc0jWhs+Kg@mail.gmail.com>
From: Richard Barnes <rlb@ipv.sx>
Date: Wed, 18 Sep 2019 18:16:08 -0400
Message-ID: <CAL02cgQR5yf50avMgf0hXttADqcC+_iWORcnycP50DpgDw6wnA@mail.gmail.com>
To: Messaging Layer Security WG <mls@ietf.org>
Content-Type: multipart/alternative; boundary="000000000000d4a90e0592db2f44"
Archived-At: <https://mailarchive.ietf.org/arch/msg/mls/Wu-KCTAHnWLWULABrbGWj0nvVkw>
Subject: Re: [MLS] Proposal: Proposals (was: Laziness)
X-BeenThere: mls@ietf.org
X-Mailman-Version: 2.1.29
Precedence: list
List-Id: Messaging Layer Security <mls.ietf.org>
List-Unsubscribe: <https://www.ietf.org/mailman/options/mls>, <mailto:mls-request@ietf.org?subject=unsubscribe>
List-Archive: <https://mailarchive.ietf.org/arch/browse/mls/>
List-Post: <mailto:mls@ietf.org>
List-Help: <mailto:mls-request@ietf.org?subject=help>
List-Subscribe: <https://www.ietf.org/mailman/listinfo/mls>, <mailto:mls-request@ietf.org?subject=subscribe>
X-List-Received-Date: Wed, 18 Sep 2019 22:16:26 -0000
I've written up a PR that implements this proposal: https://github.com/mlswg/mls-protocol/pull/209 Please take a look; there's plenty in there to disagree about, and several OPEN ISSUEs. I would like to have this landed in the next week or so, so that we can rebase some other PRs on it (e.g., non-destructive add) and publish a new draft for the interim. Thanks, --Richard On Thu, Aug 22, 2019 at 6:16 PM Richard Barnes <rlb@ipv.sx> wrote: > Hey all, > > I’d like to pose a question to the group of whether we should do > “laziness” or not. The complete form will be long, but the short version > is: Do we care enough about DH overhead and server-initiated operations to > do a pretty significant refactor and possibly add some complexity to the > protocol? > > I would like to get a go/no-go on this idea before writing a PR, since > it's going to be a big PR. And it would be helpful to make that decision > in the next week or two, so that we can get the edits done and a new > version out a bit in advance of the interim. So let's get this party > started! > > # Objectives > > The overall goal is to meet two objectives: > > 1. Not requiring DH operations in groups where no messaging is happening > 2. Allow some flavor of server-initiated Add and Remove > > The first of these objectives was raised by Raphael some time ago; see his > presentation at the January interim for more details [1]. The second has > been a long-outstanding feature request, from Facebook and Cisco, among > others. > > The useful insight is that both of these require deferred operations. In > the first case, you want to defer DH operations until someone wants to send > a message. In the second case, you might have the server propose an > operation that it can’t do, so that the execution of the operation is > deferred until someone in the group does it. > > # Proposal > > The proposal here is to refactor the protocol from “immediate mode” to > “deferred mode”. None of the underlying tree math changes, just how we > talk about it. > > * Add, Remove, and Update become “Proposals” that describe an operation, > rather than carrying the information to accomplish the information > immediately > * Add = “Please add ${ClientInitKey}” > * Update = “Please replace the leaf at ${index} with ${key} and blank > its direct path” > * Remove = “Please remove the member at ${index} > * Each epoch contains a set of proposals, followed by a Commit message > * None of the proposed changes take effect until the Commit message > * If there are outstanding proposals, you SHOULD send a Commit before > sending a message > * A Commit message contains: > * A description of which proposals were applied and how > * In particular, the committer chooses the positions where new members > are added > * A direct path that KEMs new entropy to the group (basically an > update from the Committer) > * The committer also generates Welcome messages for any new participants > * With handshake encryption, the Welcome just needs to have the key > for the Commit > * The Commit should commit to the state of the tree after the > proposals are executed (just like handshake messages do today) > * ... so the new joiner doesn't need to see the proposals, just the > Commit > > # Observations > > * In the framework above, there's no need to synchronize proposals, just > Commits > * If the Commit includes the proposals by value or hash, then we can just > run the transcript over the Commit messages, and the proposals will be > included transitively > * Note that proposals can overwrite one another, e.g., an update and a > remove for the same slot > * If we refactor in the above form, an application could reconstruct what > we have now by always sending a (Proposal, Commit) combo > * In fact, one way to view this is as splitting off the Commit from the > current Handshake messages > > # Benefits > > * We get the objectives that we set out to achieve: > * Quiescent groups can just pile up proposals, and Commit before > messaging > * The server can synthesize Add and Remove proposals as long as > clients have a way to authenticate them (e.g., a designated sender index > for the server) > * There's a certain conceptual simplicity to only having one message that > advances the group state > * With regard to the "ghost account" concerns that DKG raised at the IETF > meeting, this ensures that the proposals to add users are part of the > transcript, thus visible to the group > > # Costs > > * The longer you go before a Commit, the more expensive the Commit is, > since the proposals are all destructive, in the sense that they blank out > parts of the tree > * The logic for a new joiner might get more complicated, since they're not > actually added until the Commit. In particular, you can't send an Add > proposal and have the new member immediately able to transmit, you have to > do a Commit as well. > * At least in the form above, we lose the property that Adds are constant > time, since you would always do an asymmetric ratchet operation. If this > were a problem, you could special-case it (if the Commit only has Adds...) > * Retry logic might get more complicated; need to wait for a Commit before > I know whether my change made it in > * The protocol gets more verbose since you need the glue to refer to the > proposals from the Commit > > ----- > > Thanks for reading all the way to the bottom! > > Personally, I'm pretty split on this. On the one hand, I think this can > be done pretty elegantly. On the other hand, it does feel more complex, > and I'm worried we're spending a lot of complexity budget on some fairly > niche use cases. On the third hand, I do think we need server-initiated > Add/Remove, and all the approaches that come to mind end up looking kind of > like this > > Happy to have questions / comments here, or if there’s enough interest, it > might be good to have a quick phone call. > > —Richard >
- [MLS] Proposal: Proposals (was: Laziness) Richard Barnes
- Re: [MLS] Proposal: Proposals (was: Laziness) Richard Barnes
- Re: [MLS] Proposal: Proposals (was: Laziness) Stephen Farrell
- Re: [MLS] Proposal: Proposals (was: Laziness) Raphael Robert
- Re: [MLS] Proposal: Proposals (was: Laziness) Raphael Robert
- Re: [MLS] Proposal: Proposals (was: Laziness) Stephen Farrell
- Re: [MLS] Proposal: Proposals (was: Laziness) Raphael Robert
- Re: [MLS] Proposal: Proposals (was: Laziness) Stephen Farrell
- Re: [MLS] Proposal: Proposals (was: Laziness) Richard Barnes
- Re: [MLS] Proposal: Proposals (was: Laziness) Stephen Farrell
- Re: [MLS] Proposal: Proposals (was: Laziness) Richard Barnes
- Re: [MLS] Proposal: Proposals (was: Laziness) Karthik Bhargavan
- Re: [MLS] Proposal: Proposals (was: Laziness) Richard Barnes
- Re: [MLS] Proposal: Proposals (was: Laziness) Karthik Bhargavan
- Re: [MLS] Proposal: Proposals (was: Laziness) Katriel Cohn-Gordon
- Re: [MLS] Proposal: Proposals (was: Laziness) Richard Barnes
- Re: [MLS] Proposal: Proposals (was: Laziness) Jon Millican
- Re: [MLS] Proposal: Proposals (was: Laziness) Richard Barnes