Re: [MLS] Re-randomized TreeKEM

Joel Alwen <> Thu, 24 October 2019 20:19 UTC

Return-Path: <>
Received: from localhost (localhost []) by (Postfix) with ESMTP id 7AAE612008C for <>; Thu, 24 Oct 2019 13:19:34 -0700 (PDT)
X-Virus-Scanned: amavisd-new at
X-Spam-Flag: NO
X-Spam-Score: -1.9
X-Spam-Status: No, score=-1.9 tagged_above=-999 required=5 tests=[BAYES_00=-1.9, DKIM_SIGNED=0.1, DKIM_VALID=-0.1, RCVD_IN_DNSWL_NONE=-0.0001, SPF_HELO_NONE=0.001, SPF_PASS=-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 2KXypV0IOQ1d for <>; Thu, 24 Oct 2019 13:19:32 -0700 (PDT)
Received: from ( [IPv6:2a00:1450:4864:20::42f]) (using TLSv1.2 with cipher ECDHE-RSA-AES128-GCM-SHA256 (128/128 bits)) (No client certificate requested) by (Postfix) with ESMTPS id 3C873120071 for <>; Thu, 24 Oct 2019 13:19:32 -0700 (PDT)
Received: by with SMTP id p4so27481072wrm.8 for <>; Thu, 24 Oct 2019 13:19:32 -0700 (PDT)
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed;; s=20150623; h=subject:to:cc:references:from:openpgp:autocrypt:message-id:date :user-agent:mime-version:in-reply-to:content-language :content-transfer-encoding; bh=vfKr3hXbRRcg3FrTh60FGQwPZBbwvyAatCM3/bNEw3M=; b=dpyRIiA2LKlBhAz5HOt/NIda4WgjRNKzCg6sLg0RfMaytn+j2ejedEYA3jusaIkC58 gCebBxUWwH5HGxFx/FHv1B1CSCWykcF1p2rDRMx8dI/+21JnOiash+mrT3Dggsep52nQ CQpbcZTMnKfYU4wTU6LACAe6V0ktxhXpLXltnHZSJxX9JdPqhU2BDvtoXRnqhI/zk+TC N4MCerPdVQgDkh4tm2XKnhoYYn9ghO0r01kS9M2LuG9gf1osdLLh0UwI41YSdOzuYAyB 5w6bTpgLHu5a2DhV1NKpyvu17lqenuUz1a/KXf+gELKtB8Hy3hTqqwFDCLCIaEP5W63y s9aA==
X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed;; s=20161025; h=x-gm-message-state:subject:to:cc:references:from:openpgp:autocrypt :message-id:date:user-agent:mime-version:in-reply-to :content-language:content-transfer-encoding; bh=vfKr3hXbRRcg3FrTh60FGQwPZBbwvyAatCM3/bNEw3M=; b=URI/v/+AJ+slkhWCPwsgDQkNECkT9IiPCH9jbr0qdei/eXr+8Yt2+mM7qPVw5icxZb J5/G8XHinYruTNu7DD7+od0bJCiTQLXwfYFI4kVoF0GUlLFEAU8dAoT3uzCMSVAngvD8 MKeXriImGjbuBVx0K4sLV8la80Oz7lejgCDnpjOXfOB7sT/tWlGfJTX4Y9D09BsE5qj8 GJ0gItccT5YKjCO/8lyU9rlFz/MqYwi+5fgQ5GtOCutuliV0QReBf6eUcVcx9PhcvpZI SS2xaPORMaP6FK+/rJlSmNfCNYV990e7eJq56LGIeujqbQ6hoN0mFmUTGYH/XjTz/0i/ pf1Q==
X-Gm-Message-State: APjAAAVVFiTSahs5mSPzAvuguN/xTzvikzVtkVuqr8VMo4/CUzULpXuC 8SzoPVBaByH49Eb8fs5XFZ+8hj0gSFI=
X-Google-Smtp-Source: APXvYqx/360/SRJr487n/TNc9fUd+6xIvukCIToyAI5E9StjgFVlSyprXa4bGjnQShTSbdMTEU5vpg==
X-Received: by 2002:a5d:4112:: with SMTP id l18mr5506454wrp.123.1571948369761; Thu, 24 Oct 2019 13:19:29 -0700 (PDT)
Received: from [] ( []) by with ESMTPSA id v10sm19890867wrm.26.2019. (version=TLS1_2 cipher=ECDHE-RSA-AES128-GCM-SHA256 bits=128/128); Thu, 24 Oct 2019 13:19:29 -0700 (PDT)
To: Raphael Robert <>, Benjamin Beurdouche <>
Cc: Richard Barnes <>, Karthikeyan Bhargavan <>, Messaging Layer Security WG <>, Yevgeniy Dodis <>
References: <> <> <>
From: Joel Alwen <>
Openpgp: preference=signencrypt
Autocrypt:; keydata= mQENBFyIZvABCAC65JupY1w7gzhhNo41ftIk09n7Lid9p31jDR8Jefv9R5sWL+HZFGDeABAY 1J1JvV6vOaMsfdy9iUFfGS1GhMJ3+mh799SIsB3JSfPq/eq6Jut57D2yPtILmc7ZbuJyBHg0 xuYfKCQQAYikW+v2LJQU1Y+BUDbVldpzxSc8Z3PPSfunWdzhY6qAAhyCv+Y8EzJlQivMwD5B f6737krf8SoBsjsqCHQrRo/r+BSj5Wtd5/K3FkmWLOUAFoYK23+cpoFntGJKZfss27gDPhyS gX9ibXcBGQqBEF4qDPEzEHK8iQmXTxLul5Y7lQ6ADf69xH15WM4GmRBeCvR3Uanxcr2/ABEB AAG0HUpvZWwgQWx3ZW4gPGphbHdlbkB3aWNrci5jb20+iQFUBBMBCAA+FiEEYFNg9IH2SV6e 03O3FR5tDZv8eygFAlyIZvICGwMFCQHhM4AFCwkIBwIGFQoJCAsCBBYCAwECHgECF4AACgkQ FR5tDZv8eyjSywgApQNIRcL4IKTJ0I4XwcQRhICu1Bht3c2fUnG2YziJXjGf6DZ49uKKtuIu fk8mNS+vKRLoLZ7+u+Pv/Yjmk8jtrr6Saz1vnfsle3GgmXG5JaKOM5cOfeo5JnlNUP3QonR7 LMZwY1qVKg2mzNmwi0jG1zIGgQ5fiAwqe+YTNFli5bc/H1O9LcSmbrLV9OyucARq11DIiAvU fDknZ17OahQls+9mgfAXH5vZjzo296tYvzkOJQ2A6GPxdMHIXGbJM/vjuMe2QJl6C0zaqOtm JvFcx/HpNhmugYI9OsNAd7846HASDp8BKyfY5FYP7bn0/JBuCpg18Aykru6xyFjG3gv0L7kB DQRciGbxAQgA0Qx9LlxvJ0LGZlZRVyV8kPIxg8pNMmxJwJJ+JnTciW0LpfigfdAvGVf6PU0x 3V6SJKtz8D61c8KLyztxwPGRgJX2TRK3zvTlT5mqqnGYMAANttCF1+8DNpiYOMg3ibPRby46 4JPhMgWgvCJ1vHGu9cghjn1ttWIwBuKBXMc8HgACKYWsYZJiYtFEsnOdsD6aPWCg6NiImoc7 vRwNMKNNtDPxY95Yj4CRiLPVrZje3LyJlA9S+y2/p3w69R4AVLSRzAwDlupjXYs03QdNjGjP 2IR2u8RhstDgqW8+Bk3p7wjJ1kHTHgyox81/aHbnIRGKksPGPMPT3bvbpxevfqZ7ywARAQAB iQE8BBgBCAAmFiEEYFNg9IH2SV6e03O3FR5tDZv8eygFAlyIZvECGwwFCQHhM4AACgkQFR5t DZv8eygbLQf+OHSG6K9qiPdYxe61IR2kZdyogc2ArEGrl6AmcNzySXC8wlnreZo3FjfkD6xV CQWwWDxI7B0JPM86IcfCfn45ADeI8rwm6yYIs00B4ag9Mmo0GQ4kQd2aTy60/QaE2ZSrnEtt 0fuz1G8DGnhPnOnMyCnCnkSNuTNG20OlI0cn5EJSxBS4fXVeBMBaV91DEmvLU6DjL+fOBQPq CXIbFY7XffOmC4VxtAGhTadJ8WmUD8ZezXNs8c40Btpukr7j4piUshITfazPGEMXzTUTkimf fAhNX1QQBsfP9kjfjxBn6jDl+lDJY34mANWwEJ8BKjgr09P0sOz4zjjFL62GcFczQA==
Message-ID: <>
Date: Thu, 24 Oct 2019 22:19:29 +0200
User-Agent: Mozilla/5.0 (Windows NT 10.0; WOW64; rv:60.0) Gecko/20100101 Thunderbird/60.9.0
MIME-Version: 1.0
In-Reply-To: <>
Content-Type: text/plain; charset=utf-8
Content-Language: en-US
Content-Transfer-Encoding: 8bit
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: Thu, 24 Oct 2019 20:19:34 -0000

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