Re: [MLS] Removing ART; maybe adding partial-tree
Richard Barnes <rlb@ipv.sx> Mon, 01 October 2018 21:15 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 30C28130EAF for <mls@ietfa.amsl.com>; Mon, 1 Oct 2018 14:15:00 -0700 (PDT)
X-Virus-Scanned: amavisd-new at amsl.com
X-Spam-Flag: NO
X-Spam-Score: -1.899
X-Spam-Level:
X-Spam-Status: No, score=-1.899 tagged_above=-999 required=5 tests=[BAYES_00=-1.9, DKIMWL_WL_MED=-0.001, DKIM_SIGNED=0.1, DKIM_VALID=-0.1, HTML_MESSAGE=0.001, RCVD_IN_DNSWL_NONE=-0.0001, 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 SPqAL7wGY2W5 for <mls@ietfa.amsl.com>; Mon, 1 Oct 2018 14:14:56 -0700 (PDT)
Received: from mail-oi1-x232.google.com (mail-oi1-x232.google.com [IPv6:2607:f8b0:4864:20::232]) (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 8DF0C130DE9 for <mls@ietf.org>; Mon, 1 Oct 2018 14:14:56 -0700 (PDT)
Received: by mail-oi1-x232.google.com with SMTP id v69-v6so5144836oif.1 for <mls@ietf.org>; Mon, 01 Oct 2018 14:14:56 -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 :cc; bh=NPVbJfRT/R4omFnhvQxXp0/DEBPyFFYmj2Ezp3668CQ=; b=iiJHYZvSN/Kg++FWcjF+ECZtJV9V5ovYiZda5GHZZNaDf9+KpnsYkQpE0iWX30naHY FA19yYgdnRDp6MbtholMmiDtqySb61JbncE1eWjWLEmfevqfbcO4pWVL2SeDl6Oa/XmY KlijXcAlTLIyrwamW+ImY+FwLgoGsPVf9/dYsmAtE7/Zj+xzPUbFO/fs2cLXNbWdYxpe i3Ss739BkZUUTm7acnXPn+YRu0jiVYt+/GWVmu5baCgIbF1wRNTP2Yos/H0i2HN2e6ob j5rifm90QIhqeuqkWqkAtEp02uFEpLlgTb+XPZdy2RNpUbpoBqJ4x3d9XIzzgInHI/2y YtsQ==
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:cc; bh=NPVbJfRT/R4omFnhvQxXp0/DEBPyFFYmj2Ezp3668CQ=; b=ZCzriUf8bG5sugCEG5dvRNTDuw8JEQ0jCa0sdw26e+f2izPZC/LU+D/7mhZjMuCPBM nI78y+4e6kSg/FuGaHasanM6luSkpqgtEwu3n+ilvzjFSbOa9yNrK6mYsXphkEBVY2jr 9P4IaeNMSwFymHYPv+t79BDVHl2ldUkSnoLzss46JFPtro5Gb01r4odu+FPV+VMdQf68 s4PGVQbYzT8osMeht8eTKZoL5f7b1hAy2hk05bB8CW90+1PyEjroRmLkvG8nWOzKhuNB IPNpyTs1yRuXkfMyanKZMdciUGDz4kajkkcbz6xrEIEoLDs4L55gfKb41qUYAfyGRcUr Ajww==
X-Gm-Message-State: ABuFfohTNBnJ2lTI7OZndyHbbcj2quxMVOrKVMkcQflM2hsnW9JMos/o opyU8ucdC+Xhwso87gDtizjSbX/guAwus8iVBrpGKqrPKJA=
X-Google-Smtp-Source: ACcGV62b5sKtJ1N7dIxvFdbblrX1eIswoPgi5nDM/gO+/jq0tjVBQ6nv5OV0aE66C72NjVZaBDNG4ziBNxK45T1H3sY=
X-Received: by 2002:aca:5a45:: with SMTP id o66-v6mr6331457oib.155.1538428495572; Mon, 01 Oct 2018 14:14:55 -0700 (PDT)
MIME-Version: 1.0
References: <CAL02cgSBCnjNMBHa7iJWqOYF_DNh8gUbGS4jsz57rO5=uAM1EA@mail.gmail.com> <CAKHUCzxJ-5UmvA-3_sqNvWApN=zbLMbHTrwwv+-R3m6nS1RXJw@mail.gmail.com>
In-Reply-To: <CAKHUCzxJ-5UmvA-3_sqNvWApN=zbLMbHTrwwv+-R3m6nS1RXJw@mail.gmail.com>
From: Richard Barnes <rlb@ipv.sx>
Date: Mon, 01 Oct 2018 23:14:38 +0200
Message-ID: <CAL02cgSJbB5-8z3-PA8Tk3mC8j=uehHVf=p5bmayub=MFLK0bw@mail.gmail.com>
To: Dave Cridland <dave@cridland.net>
Cc: mls@ietf.org
Content-Type: multipart/alternative; boundary="000000000000fdf48a0577314b70"
Archived-At: <https://mailarchive.ietf.org/arch/msg/mls/hlAay_1wuBCovQf8_9SEzyU8M5E>
Subject: Re: [MLS] Removing ART; maybe adding partial-tree
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: Mon, 01 Oct 2018 21:15:00 -0000
On Mon, Oct 1, 2018 at 10:34 PM Dave Cridland <dave@cridland.net> wrote: > > > On Mon, 1 Oct 2018 at 19:06, Richard Barnes <rlb@ipv.sx> wrote: > >> Hey all, >> >> At the interim last week, there was agreement to remove the discussion of >> ART from the protocol draft and focus on TreeKEM. I have implemented that >> change in the following pull request: >> >> https://github.com/mlswg/mls-protocol/pull/66 >> >> > I'm not objecting to the change - I lack sufficient cryptographic > knowledge to express an opinion - but it'd be very useful to read a > synopsis of the reasoning behind it, and a summary of the discussion. I > imagine future participants would find it useful too, and of course, all > decisions need to go by the list anyway. > To recap the discussions at the interim, I think the reasons are basically as follows, in descending order of importance: 1. ART requires each recipient of a message to do O(log N) DH operations, where as TreeKEM only requires O(1). This is a significant difference for large groups / small devices. 2. TreeKEM offers the possibility of doing Add/Remove without double join 3. TreeKEM offers the possibility of being able to merge Update messages While I don't think anyone has proved that (2) and (3) aren't possible with ART, the fact that it's contributive makes them more difficult. > I reviewed the PR for clarity/typos. > > >> If a couple of folks could give a quick review, it would be appreciated. >> I also put together a PR describing how to do the "partial tree" approach >> described at the interim and in my earlier message today. >> >> https://github.com/mlswg/mls-protocol/pull/67 >> > > Also reviewed for clarity/typos. I admit I'm mildly confused as to why > adding a node needs to blank the direct path, but at the same time I'm not > sure it makes any difference. (That is, here: > https://github.com/mlswg/mls-protocol/pull/67/commits/7a7cd37aec0ceff773600564b5c9619c3d06a115#diff-a87cc9081154f564150420544170f1c9R1113 > ). That's probably just my lack of understanding somewhere. > The reason is symmetric for Add and Remove. Recall that the invariant property the tree is supposed to have is that a node's secret value and private key are only known to the holders of leaves below that node in the tree. For both Add and Remove, you need to change the intermediate nodes above the target leaf, either to make it so that the removed member doesn't know them or so that the added member does. The question is what relationship those intermediate nodes have to the sender of the Add/Remove -- does the sender know the secret / private key or not? On the one hand, if the sender does know the private key, then you have a "double join" situation, where the sender knows something he's not supposed to. The phrase "double join" arises from the Add case, since the relevant intermediate node secrets are known both to the new member and to the sender of the Add. Effectively, they both occupy the new member's leaf, which complicates things quite a bit. For example, if you now want to evict the sender of the Add, you have to also evict the newly added leaf, etc. In the Remove case, the main impact of the double-join is that you don't have a true Remove operation, you only have a Take-over operation. That makes it difficult to imagine how you would ever compact the tree. On the other hand, if the sender doesn't know the private key, then the node has to be blank. In the Add case, there's no way (AFAIK) to set the intermediate node values to something that is known to (a) the existing members under those nodes and (b) the new member, without it also being known to the sender of the add. So the values that get decrypted to intermediate nodes during the Add are only for the purpose of computing the new root secret; the intermediate nodes can't have a non-blank value without violating the tree invariant. It may be possible to avoid blanks in the Remove case, but we would have to modify TreeKEM. You could still do the "hash to the root" trick to generate the fresh shared entropy for the epoch, but you couldn't just overwrite the values of the intermediate nodes (as is done now). You would have to fold in some entropy only known to the existing members. This is probably worth some thought. Anyway, hope that helps, --Richard > > >> >> Feedback welcome! >> >> Thanks, >> --Richard >> _______________________________________________ >> MLS mailing list >> MLS@ietf.org >> https://www.ietf.org/mailman/listinfo/mls >> >
- [MLS] Removing ART; maybe adding partial-tree Richard Barnes
- Re: [MLS] Removing ART; maybe adding partial-tree Dave Cridland
- Re: [MLS] Removing ART; maybe adding partial-tree Richard Barnes
- Re: [MLS] Removing ART; maybe adding partial-tree Cas Cremers
- Re: [MLS] Removing ART; maybe adding partial-tree Richard Barnes
- Re: [MLS] Removing ART; maybe adding partial-tree Richard Barnes