[MLS] Proposal: Proposals (was: Laziness)

Richard Barnes <rlb@ipv.sx> Thu, 22 August 2019 22:17 UTC

Return-Path: <rlb@ipv.sx>
X-Original-To: mls@ietfa.amsl.com
Delivered-To: mls@ietfa.amsl.com
Received: from localhost (localhost []) by ietfa.amsl.com (Postfix) with ESMTP id 94C02120C3F for <mls@ietfa.amsl.com>; Thu, 22 Aug 2019 15:17:03 -0700 (PDT)
X-Virus-Scanned: amavisd-new at amsl.com
X-Spam-Flag: NO
X-Spam-Score: -1.897
X-Spam-Status: No, score=-1.897 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] 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 ([]) by localhost (ietfa.amsl.com []) (amavisd-new, port 10024) with ESMTP id TigEzkuJc3ZJ for <mls@ietfa.amsl.com>; Thu, 22 Aug 2019 15:17:01 -0700 (PDT)
Received: from mail-oi1-x243.google.com (mail-oi1-x243.google.com [IPv6:2607:f8b0:4864:20::243]) (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 7CE2B120227 for <mls@ietf.org>; Thu, 22 Aug 2019 15:17:01 -0700 (PDT)
Received: by mail-oi1-x243.google.com with SMTP id o6so5565733oic.9 for <mls@ietf.org>; Thu, 22 Aug 2019 15:17:01 -0700 (PDT)
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=ipv-sx.20150623.gappssmtp.com; s=20150623; h=mime-version:from:date:message-id:subject:to; bh=7PUDpTcIPP2NUaFwT/AOwuDPf7WcIbBfPNw6wWxWcFA=; b=InxrejCRELhSiRWhFtgp9WhWT2oCL6ioTSyDA4BCqO8xTJGdABypGez0UJIVFHTyOx 62aXvJq+4sN9tt9/5zxUlYlQKx/xa2mMgQU9dzgLKpo+IyVwQ2uqNxae9GOCjouz2/gg bR7emvlw+uU4hTNtDSzb8Tin/V1TVRSFIpOh/284z3traO2lIpq1XzqY0bZgP2nDY2Tm gIoRt3XOXacNtUl0l+Ub2CuOuZP7qt6ZxZCfPqmT1cZ3gF4U2vSxvChAv2vmI/jDKHTi Q5pc5bVC1dpQNw4vHNSFKViDIlf0i7zJAZ1orHEGgwlW/2WfWCdkxUPD8i0n7ySsFPzN CUAw==
X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20161025; h=x-gm-message-state:mime-version:from:date:message-id:subject:to; bh=7PUDpTcIPP2NUaFwT/AOwuDPf7WcIbBfPNw6wWxWcFA=; b=EeIpns7f+M7gwAYDxn5+uRTEF7E5GCnWThSAW0I5xfErvUPwnfZTGkfHuxEXU61Shg XApqtX1sBVmeWCPDk7pn0xTdvWPXi8mGvXLUvsaCNm4qW0eZ5Vxp6RBQ+K2Irz6bynNN oqRsArQnUiQOPvJh8uZRRC8RGQLu7r+HSCE3dfOWanj8GQQcbAMXcJkr8l31jLjVpO2a o7dFOwOwX84a7mdgcSuAEvZHfqvrR7SFhCXIO7Ep7MNUJ83IhNdtaoszqaLmZ5/l7Edd IxeDgAh5rSaHMWTqljNC064pAa8ixm4XztUPRLqeJLjwC0qL+B1PPX/QijVM6G7TD8UT w49A==
X-Gm-Message-State: APjAAAWmDYl9awFrE8PA5xf+8N32lyz9/V+W90F/DreP3mLBVDTCQjOU A9pFKG0E5YcI/GBjU3VvJhdioA6IxKmiIJN5ZLa8jYmo/4NgLg==
X-Google-Smtp-Source: APXvYqwClhD/GxrPo1a8+lF0u7Anhe8HLSNHOGJeyU/l1jFv3PV7Q0bfUCL7S6bTSNxdH2mjAFLYiLBzZEv3J8rrQIU=
X-Received: by 2002:aca:d08:: with SMTP id 8mr959768oin.51.1566512220400; Thu, 22 Aug 2019 15:17:00 -0700 (PDT)
MIME-Version: 1.0
From: Richard Barnes <rlb@ipv.sx>
Date: Thu, 22 Aug 2019 18:16:43 -0400
Message-ID: <CAL02cgSbgkYyMcm=w8+oF+R5GBKaaofV3_x_VF0rMc0jWhs+Kg@mail.gmail.com>
To: Messaging Layer Security WG <mls@ietf.org>
Content-Type: multipart/alternative; boundary="0000000000006f06290590bc0c2b"
Archived-At: <https://mailarchive.ietf.org/arch/msg/mls/5dmrkULQeyvNu5k3MV_sXreybj0>
Subject: [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: Thu, 22 Aug 2019 22:17:03 -0000

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

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

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
    * 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

# Observations

* In the framework above, there's no need to synchronize proposals, just
* 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
    * 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
* 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.