Re: [MLS] Re-randomized TreeKEM

Richard Barnes <> Fri, 25 October 2019 21:44 UTC

Return-Path: <>
Received: from localhost (localhost []) by (Postfix) with ESMTP id CC97812008F for <>; Fri, 25 Oct 2019 14:44:13 -0700 (PDT)
X-Virus-Scanned: amavisd-new at
X-Spam-Flag: NO
X-Spam-Score: -1.896
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: (amavisd-new); dkim=pass (2048-bit key)
Received: from ([]) by localhost ( []) (amavisd-new, port 10024) with ESMTP id S4jq_WfrFbfa for <>; Fri, 25 Oct 2019 14:44:09 -0700 (PDT)
Received: from ( [IPv6:2607:f8b0:4864:20::22e]) (using TLSv1.2 with cipher ECDHE-RSA-AES128-GCM-SHA256 (128/128 bits)) (No client certificate requested) by (Postfix) with ESMTPS id B16FE12004A for <>; Fri, 25 Oct 2019 14:44:09 -0700 (PDT)
Received: by with SMTP id a15so2590339oic.0 for <>; Fri, 25 Oct 2019 14:44:09 -0700 (PDT)
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed;; s=20150623; h=mime-version:references:in-reply-to:from:date:message-id:subject:to :cc; bh=snVuOSeiRtrgtAo+pS3BDk3VKlmImB3uuU+KFU22pwk=; b=zL3duBJllMtX3YtHWna2lkqeQkVlt4o+jSjqn4+ypnvX6YJ/2jL9P9DIqcuT6v/wng YI5ttLMmv6Ky/Cz3eHwsIpV9eZ5oQaxMWuF6UmP7DdzRAvD3sYNxOPFLMpnjoLlHVajj kzMXQ0azPQoGvnxc5Ae6IU8cH1lk9qjLgcIFwFNoog2qAW6l5NGttOsco6ZaHFOv7S77 Pc9zg4ssJjM0QaFAZy3OvzohYxWlZsAZ/5BBtGr9pthiGZMVuOygQYgPxs6xMhU2gaJl fbmSm7C9oJKJjYv2PEYNk5p61+8fw6cAjMKGqDvZQhKIU7MrAhURXq/BH+HE8216cyDe GjNA==
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=snVuOSeiRtrgtAo+pS3BDk3VKlmImB3uuU+KFU22pwk=; b=qoxayDOa5IejidkBZcXoB2Gaqitoz9Fu5ptenNfoTFcNPC4/iTtIVRtbhl2p7Dkb8E Sjg1X00wLOkiIULDczv6vjM0oUgyfjGxeoNFGPrD/gXabaQrj+jvMz5CtKE5iWZughf/ P4zdxBMwyXVrnpyV58N6VI/jeDjlhplDlWI5WC7FQ9cKerePrIptdwSwdLrreSPXpFfC U9wJvOEOKlrrzLnxWZWuJQrMRxSaa07vdkzVuxU8VJZITcX9agnHrXI9N5QnNvx1PU1+ AOwuDe3OCjJeUFJNUJOCI5tkixR1+M6elLjEz8zydlXPBGstwOUmCCUQ0VGzGe43B5A0 YV8Q==
X-Gm-Message-State: APjAAAWkWLq8dtXOFY5S6EfIDRpQ4CrNtJaKbFf9fp/ixHn8lbX7JUCZ Wrx+mLKxofHKpukAMyVr937Q+cxLGoDF/zZ3f9UvOQ==
X-Google-Smtp-Source: APXvYqzyabdS8KranwUtzGWzZVkseIkaaBOVmeleq535E3JZsE3syBjE0XQDWTVFtsl+nGhgqLZseV+8uYSqCzMQdKE=
X-Received: by 2002:aca:810:: with SMTP id 16mr4645310oii.149.1572039848563; Fri, 25 Oct 2019 14:44:08 -0700 (PDT)
MIME-Version: 1.0
References: <> <> <> <>
In-Reply-To: <>
From: Richard Barnes <>
Date: Fri, 25 Oct 2019 17:43:47 -0400
Message-ID: <>
To: Joel Alwen <>
Cc: Raphael Robert <>, Benjamin Beurdouche <>, Karthikeyan Bhargavan <>, Messaging Layer Security WG <>, Yevgeniy Dodis <>
Content-Type: multipart/alternative; boundary="000000000000bf27cd0595c30cdb"
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: Fri, 25 Oct 2019 21:44:14 -0000

FWIW: I did a quick PoC implementing the update primitive on top of
OpenSSL, within the crypto framework of mlspp.  It wasn't trivial, but it
wasn't too painful.  It is almost certainly not constant-time.

On Thu, Oct 24, 2019 at 4:19 PM Joel Alwen <> wrote:

> On 24/10/2019 12:09, Raphael Robert wrote:
> > This means that vendors/implementors have to implement something at a
> new layer that is somewhere in between the crypto library and the protocol
> layer.
> Yeah, thats a good point. To me, proposing a reasonable way to build UPKE
> on top of, say, libsodium is one of the main
> things I want to figure out right now (along with better understanding of
> how Mult() for X25519 can fail). Basically,
> this means implementing Mult() from, say, libsodium as going from Mult()
> -> multiplicative UPKE should be very
> straightforward using what I'd expect even the most basic interface for
> any X25519 implementation to provide. I guess
> the challenge here is going to be that both clamp() and the composite
> order are neither exported nor directly accessible
> in libsodium?
> In any case, if Mult() needs implementing from scratch then some of the
> risks I see here are:
> - Side-Channels: Mult() operates on secret keys so really it should be
> implemented with side-channel free code (e.g.
> constant time, memory access, etc.). We could mitigate this by proposing a
> specific implementation similar to whats done
> in RFC 7748.
> - Memory management: Secret keys being exported out of an X25519 library
> need to be handled safely in memory (e.g. 0-ed
> out before free, don't swap to disk, etc.) Libsodium does provide some
> memory-management functions for this very purpose.
> - Good Entropy: The re-randomizer d' needs to be sampled uniformly and
> independently. (Again I think most crypto
> libraries provide functions to do this.)
> Probably a naïve attempt at such a list of risks & mitigations. But making
> this stuff explicit seems useful for later on
> if we put this into the MLS RFCs (not to mention for a separate addendum
> RFC for 7748 describing the key-rerandomization
> technique on its own). So any input on the expected risks (and possible
> mitigations) would be very appreciated!
> On 24/10/2019 12:09, Raphael Robert wrote:
> > Finally I also understand that because of the clamping the actual
> security level of DH operations with curve 25519 is
> > not as clearly understood as it is the case with X25519 now.
> Not sure I follow what you mean here. One the one hand the UPKE
> construction is built on top of the X25519 (or X448)
> group not just Curve25519. In particular, Mult() uses the same point
> representation, clamping of scalars and scalar
> multiplication as specified in RFC 7748.
> On the other hand, if anything, I'd have thought questions about exact bit
> security are the other way round. It's X25519
> that does the clamping so that's where the question about exact bit
> security would arise no? Clamping isn't inherent to
> Curve25519 though; rather its just one way to do scalar multiplication
> mapping into a prime order sub-group based on the
> composite order Curve25519 group. But, as shown by Ristretto, other
> methods are possible that completely avoid clamping
> (and also happen to be both additively and multiplicatively homomorphic).
> In particular, I believe CDH, DDH and all the
> other usual crypto hardness assumptions are equivalent for Curve25519's
> prime order subgroup and for the Ristretto
> group. Not sure thats true for X25519 though.
> In any case, I'm no expert on this stuff so feel free to correct me if I'm
> wrong. :-)
> - Joël