Re: [MLS] Re-randomized TreeKEM

Brendan McMillion <> Tue, 22 October 2019 01:09 UTC

Return-Path: <>
Received: from localhost (localhost []) by (Postfix) with ESMTP id 662F7120AB5 for <>; Mon, 21 Oct 2019 18:09:09 -0700 (PDT)
X-Virus-Scanned: amavisd-new at
X-Spam-Flag: NO
X-Spam-Score: -1.999
X-Spam-Status: No, score=-1.999 tagged_above=-999 required=5 tests=[BAYES_00=-1.9, DKIMWL_WL_HIGH=-0.001, DKIM_SIGNED=0.1, DKIM_VALID=-0.1, DKIM_VALID_AU=-0.1, HTML_MESSAGE=0.001, RCVD_IN_DNSWL_NONE=-0.0001, SPF_HELO_NONE=0.001, SPF_PASS=-0.001, URIBL_BLOCKED=0.001] autolearn=ham autolearn_force=no
Authentication-Results: (amavisd-new); dkim=pass (1024-bit key)
Received: from ([]) by localhost ( []) (amavisd-new, port 10024) with ESMTP id a7zYyjbTOldD for <>; Mon, 21 Oct 2019 18:09:07 -0700 (PDT)
Received: from ( [IPv6:2607:f8b0:4864:20::829]) (using TLSv1.2 with cipher ECDHE-RSA-AES128-GCM-SHA256 (128/128 bits)) (No client certificate requested) by (Postfix) with ESMTPS id 10E1D120AB1 for <>; Mon, 21 Oct 2019 18:09:07 -0700 (PDT)
Received: by with SMTP id g50so10092754qtb.4 for <>; Mon, 21 Oct 2019 18:09:07 -0700 (PDT)
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed;; s=google; h=mime-version:references:in-reply-to:from:date:message-id:subject:to :cc; bh=WR68MsIgxlG4tEeDCvv9BpwT/tfzMb9jXJqN7P40jUI=; b=bfSHJiFxYv7Lw24J9MBqEgB0PNYgirfOWq7t7Mtz7LtCoZMmTDgXFcAT4owW2Fe6Uy Bo0Pbsb0SdhQXpEBj5fssju+Bqf5wquVRLWUWB3hiEfuSqFcghWGAQtcI27il7NsLvXk FKA6Misa2uwyNND8qpEnz68eeu0r0SgIi7IhA=
X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed;; s=20161025; h=x-gm-message-state:mime-version:references:in-reply-to:from:date :message-id:subject:to:cc; bh=WR68MsIgxlG4tEeDCvv9BpwT/tfzMb9jXJqN7P40jUI=; b=YsDP1+JG8DlyhK087b3G/ErqoeV+TrKVA7X23pwHLnRou0d/9aLEyQWRJhnhef6Wm2 r5RAhB9Dh2qIUxC8sSZsR6D4iRLL6ZngVmweQbF3GOhm7DaXVBirkzFHemkS8l8udSu4 YpUJ5uyCuI3ZXGmv45HFZbmZkge6iub+F+PzskP4/PwBAoqGl3pbYBN5is7uhwsd9c0Y KVHwhJRwlKpAmij9mzqbZ/X8dHw3yAMvgKm6bm+b60q8g0ZfLLiIwDxIwUlZAaQKjBhd BoZsrg1Zu8yXgzmsiyAPQ4sWstVkiynA6hhDkBUnJgBzCz1jd/UdVw9pmuDv+pDcbu6b BXaA==
X-Gm-Message-State: APjAAAUX9e31EB8yTArnJcn8OxI44CjD7/unAYskVJar+AVpwruSIves 2ZjGmkC8PNdysR9D7y3PehLHYv9r16wpuVXnRW1LT3VPxA8D1w==
X-Google-Smtp-Source: APXvYqxR4pxq6lTPiISKznnMIxo83MUiNdxM7+y2mCnCutRwWMYhmgMVIwPGzb0jqjiHDeYfmDE+h0cAKzrGr0QjNPY=
X-Received: by 2002:ad4:538b:: with SMTP id i11mr569732qvv.211.1571706545759; Mon, 21 Oct 2019 18:09:05 -0700 (PDT)
MIME-Version: 1.0
References: <> <> <> <> <> <> <>
In-Reply-To: <>
From: Brendan McMillion <>
Date: Mon, 21 Oct 2019 18:08:53 -0700
Message-ID: <>
To: Joel Alwen <>
Cc: Messaging Layer Security WG <>
Content-Type: multipart/alternative; boundary="0000000000005a2a4c0595757267"
Archived-At: <>
Subject: Re: [MLS] Re-randomized TreeKEM
X-Mailman-Version: 2.1.29
Precedence: list
List-Id: Messaging Layer Security <>
List-Unsubscribe: <>, <>
List-Archive: <>
List-Post: <>
List-Help: <>
List-Subscribe: <>, <>
X-List-Received-Date: Tue, 22 Oct 2019 01:09:09 -0000

> If, on the other hand, the concern is the lack of an explicit signal
> wouldnt it be enough to have parties send out ACK msgs to the group when
> they process an update? That would consume far less bandwidth (and
> computation) than doing a full update alla TreeKEM.

Right, my concern is the lack of an explicit signal. I'm taking the
perspective of an individual user thinking, "What policy do I need to
enforce, to ensure that after X amount of time without compromise, my group
is back to a secure state?" And the answer to that question is the same
whether you're using TreeKEM or RTreeKEM: you need to require everybody to
Update, and you need to Remove the users who haven't Updated. RTreeKEM
might get to a secure state faster but it's not that much faster, and it
doesn't change the promises we can make to our users. That's what I meant
when I said the security of the two schemes isn't materially different.

Having everybody send an ACK requires either quadratic bandwidth or
trusting the server, which isn't worth it imo.

On Mon, Oct 21, 2019 at 2:50 PM Joel Alwen <> wrote:

> Hey Brendan,
> Thanks for taking the time to look at this stuff and answer! :-)
> > This actually makes TreeKEM more attractive to me because it encourages
> > implementors to keep the Update frequency high,
> If one can afford high update frequency then that's great. It helps
> RTreeKEM too by the way. The longer between updates the less PCS we have
> and the longer the corruption windows. So there's still plenty of
> incentive in RTreeKEM to update as often as you can.
> But more generally, to me a primary design goal for MLS is to get as
> much security for as little bandwidth as possible. So I'm particularly
> interested in the protocols behavior when there *isn't* that much
> bandwidth to spare for frequent updates.
> > and it provides an
> > explicit signal to the group that everyone has processed every update.
> > With TreeKEM, the policy would be “everybody Updates at least once per
> > day”. But with RTreeKEM, the equivalent policy is “at least one person
> > Updates every day” which isn’t as strong, because you don’t know whether
> > or not everybody came online that day and processed the one Update.
> If your not coming online then I'm not sure I see the difference between
> using TreeKEM or RTreeKEM. I mean, either way your not refreshing any
> key material so your preventing the group from achieving FS. Moreover,
> coming online to send a daily update TreeKEM means already requires
> processing other peoples updates first.
> If, on the other hand, the concern is the lack of an explicit signal
> wouldnt it be enough to have parties send out ACK msgs to the group when
> they process an update? That would consume far less bandwidth (and
> computation) than doing a full update alla TreeKEM.
> > But RTreeKEM has costs like being harder to implement, and restricting
> what
> > algorithms we can use.
> FYI: In the mean time it looks like we may have found a way to make
> RTreeKEM work with X25519/X448 groups. (See the email I just sent to the
> group for more on this.) Harder to implement I do agree with. Albeit IMO
> the difference is rather marginal compared to how much code is needed to
> implement the rest of MLS, not to mention all the surrounding
> infrastructure; e.g. the servers, the rest of the client, UX etc need to
> actually deploy MLS. At the end of the day, I don't think we're talking
> about much more than a few lines of code wrapping HPKE. But I might be
> wrong here.
> > It’s on this basis that I’m opposed to including RTreeKEM in the spec.
> Fair enough! :-)
> - Joël