Re: [MLS] Re-randomized TreeKEM

Raphael Robert <> Thu, 24 October 2019 10:09 UTC

Return-Path: <>
Received: from localhost (localhost []) by (Postfix) with ESMTP id 8CF93120DAB for <>; Thu, 24 Oct 2019 03:09:50 -0700 (PDT)
X-Virus-Scanned: amavisd-new at
X-Spam-Flag: NO
X-Spam-Score: -1.898
X-Spam-Status: No, score=-1.898 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_PASS=-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 XzAHh_vS1WHu for <>; Thu, 24 Oct 2019 03:09:47 -0700 (PDT)
Received: from ( [IPv6:2a00:1450:4864:20::42c]) (using TLSv1.2 with cipher ECDHE-RSA-AES128-GCM-SHA256 (128/128 bits)) (No client certificate requested) by (Postfix) with ESMTPS id D6A9E120DA8 for <>; Thu, 24 Oct 2019 03:09:46 -0700 (PDT)
Received: by with SMTP id l10so24960590wrb.2 for <>; Thu, 24 Oct 2019 03:09:46 -0700 (PDT)
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed;; s=20150623; h=from:message-id:mime-version:subject:date:in-reply-to:cc:to :references; bh=JmcOJw7n6NKrtEwJihsamlS7cV9+qaS7D2BcO17LFNo=; b=zhwc6LgObV4NULo7EQj3MuKApicTHtYnZHfpfwEEVSHy2DN3aQHsfTkkX3EfXi93gk FvbmvOfkP0JXDjm4555arXb0rn6YxVqXC5jfnZ5d5IIchEb5hTlWzq9YTD/ToQ0qy5m9 nZZU050Sb9/n7HYaOmscTU9ZW/VhHEUNZg0JgaF/6LkBHqp3g9dzWX7bgdSWPhGjkK6M EP9eCbPcud1xSEVcWkKVEVIJfpShOitCZWZWtWFiab7jlZnRq12VdEDhxUU3wM+2hjXa eUozD5wax0DlG36c7FXMWuVLNDWMG8FeC1/UJxEt3kUlzObevTnUBKXqCXVTYIOHKE1t b8aA==
X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed;; s=20161025; h=x-gm-message-state:from:message-id:mime-version:subject:date :in-reply-to:cc:to:references; bh=JmcOJw7n6NKrtEwJihsamlS7cV9+qaS7D2BcO17LFNo=; b=NKnirpHhqErCg4OozlXXKyYFhoRp6EjTPqjGxj3Qg92MjSmVCKcrE+hraK4UpNUC0L vlOtlrI2iPBRF1LY5xRr9OT8UCWeIKC+uzAZjCiLDmD34mMRhrAP+9OLorkgzPac/ETn V5tvRDqRyGMZfvKJlBqIgGQY+kTDGP1OIlB+MdYIV+TdxSZ9S3515YifZA08q4JLzaTw CvY4g7nNVt4DBPlhoNHaX1MsSMVHBJw4KKYW+NQrkL9LkRhDoTForQMSoBlDrgjjrs/B pjaw0GvddYgnacOVYXTnOcGoqZS3FLx2Fu6SbnH7u1+W9GN43lxEUXKp3VSmBQEh+ARy 9c4Q==
X-Gm-Message-State: APjAAAVONlMo1aUCNl0Qg2tHjXrxKjPSFtIuyny062yePUtRpu+AhMbH VX617W1v3ostwiBPBKARfouwRA==
X-Google-Smtp-Source: APXvYqzqxVmZCwfIzrMCyl3bpgdUJRAA+5pUVqbJBMeYKwhhOeBBI4FhBGOd4dazwIc4+SAREcBYFg==
X-Received: by 2002:adf:f90f:: with SMTP id b15mr3106468wrr.76.1571911785016; Thu, 24 Oct 2019 03:09:45 -0700 (PDT)
Received: from rmbp.wire.local ( []) by with ESMTPSA id r188sm2316559wmr.17.2019. (version=TLS1_2 cipher=ECDHE-RSA-AES128-GCM-SHA256 bits=128/128); Thu, 24 Oct 2019 03:09:43 -0700 (PDT)
From: Raphael Robert <>
Message-Id: <>
Content-Type: multipart/alternative; boundary="Apple-Mail=_50F0AA02-7EF9-41A6-985D-6643AEB6957C"
Mime-Version: 1.0 (Mac OS X Mail 12.4 \(3445.104.11\))
Date: Thu, 24 Oct 2019 12:09:41 +0200
In-Reply-To: <>
Cc: Richard Barnes <>, Karthikeyan Bhargavan <>, Joel Alwen <>, Messaging Layer Security WG <>, Yevgeniy Dodis <>
To: Benjamin Beurdouche <>
References: <> <>
X-Mailer: Apple Mail (2.3445.104.11)
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 10:09:51 -0000

Chiming in as well, I think that RTreeKEM starts to sound like a promising improvement to TreeKEM. Thanks to all who participated!

I like the idea that better FS can be achieved at a relatively moderate cost (slightly larger message size).
Particularly in very large groups, it is unreasonable to assume that all members can issue Updates at a high frequency, because this would simply be unfeasible in terms of bandwidth/processing power. RTreeKEM seems to address this particular issue elegantly.

For me the fundamental new development since the interim is that we wouldn’t need to throw away crypto primitives like curve 25519. I would however like to point out that the current proposal with UPKE/clamping means that the usual crypto libraries (libsodium, WebCrypto, etc.) still cannot be used out of the box. 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. This poses a new risk, because it requires a higher expertise than just implementing the protocol layer (as it would be the case with TreeKEM). If we move to adopting RTreeKEM, we should pay special attention to that.

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.

But none of the above is a good enough reason to discard RTreeKEM at this point! I’m looking forward to further discussions!


> On 23 Oct 2019, at 00:10, Benjamin Beurdouche <> wrote:
> That’s my opinion as well... :)
> B.
>> On Oct 22, 2019, at 11:34 PM, Richard Barnes <> wrote:
>> Since it appears I haven't chimed in on this thread -- I am generally OK with this change, if folks think it would improve the FS properties of the protocol, and assuming that Joël's / Mike's solution to the X25519 problem works out.  
>> On the one hand, if we have to shove X25519 overboard, my bias would probably be against making this change, barring some really strong security rationale.  
>> On the other hand, if we can get confidence that the X25519 solution works (or that the failures are rare and tolerable), then this seems like a pretty minor burden from an engineering POV (a little more code, 2x the DH operations on Update/Commit), so if there's security benefit, great.
>> On Tue, Oct 22, 2019 at 5:26 PM Karthikeyan Bhargavan < <>> wrote:
>> Indeed!
>> Like I said, it would be a ridiculous design for MLS.
>> I was simply trying to understand the guarantees.
>> -Karthik
>>> On 22 Oct 2019, at 23:20, Richard Barnes < <>> wrote:
>>> Just so we're clear, I would be *strongly* opposed to putting anything like this naïve UPKE scheme into MLS..  For the simple reason that it expands the size of Welcome message by a factor of K.  RTreeKEM or nothing :)
>>> --Richard
>>> On Mon, Oct 21, 2019 at 6:53 PM Yevgeniy Dodis < <>> wrote:
>>> Great summary, Karthik!
>>> As I put in the other thread, comparison with the "naive" UPKE (for K=100 or less) might be a good idea.
>>> Pros of Naive Scheme: 
>>> - more general, uses any PKE
>>> - using stream ciphers to generate K key pairs as needed makes the efficiency hit noticeably less than a factor of K,
>>> and perhaps closer to a factor of 2 (see below), but unclear a-priori.
>>> - for K>1, offers non-trivial (but still sub-optimal) security enhancement over basic TreeKEM (K=1)
>>> Cons (pros of RTreeKEM):
>>> - Public key storage increases by at least factor of K
>>> - While the naive use increases secret storage and computation by a factor of K, using stream cipher, after i uses one can only store the 
>>> current seed to generate last (K-i) keys. However, K public keys should be published right away, so we must 
>>> lose at least factor of 2 compared to TreeKEM to generate all keys twice (but possibly factor of K if people update too frequently, so all but 
>>> 1 of the K keys gets used). So overall efficiency hit between 2 and K, which might already be comparable or worse than RTreeKEM.
>>> - Still much worse security than RTreeKEM, but possibly more expensive too, already for small K!
>>> Please let us know if you think this should be explored further.
>>> Yevgeniy
>>> On Mon, Oct 21, 2019 at 8:03 AM Karthikeyan Bhargavan < <>> wrote:
>>> I see. So, here’s how I read the improvements proposed in RTreeKEM.
>>> Currently, in TreeKEM (like in ART before it) we rely on each member to regularly *send* updates in order to get both PCS and FS for the group secrets.
>>> The informal secrecy guarantees we get are that:
>>> - (FS) if member A sends an update in epoch N (moving the epoch to N+1), and if A gets compromised in epoch N+1, the messages sent in epoch N remain secret
>>> - (PCS) if member A sends an update in epoch N (moving the epoch to N+1), and if A was (passively) compromised in epoch N, the messages sent in epoch N+1 remain secret
>>> In other words, each member who sends an update gets local protection against compromise, encouraging vulnerable members to keep sending updates...
>>> However, as Joel, Sandro, Yevgeniy, and Yiannis note in their paper, we could do better, at least for FS, if we use one-time decryption keys.
>>> If each recipient deletes the old decryption key after processing an update, then even just by *processing* an update, we get an additional  guarantee:
>>> - (FS’) if member A processes an update in epoch N (moving the epoch to N+1), and if A gets compromised in epoch N+1, the messages sent in epoch N remain secret
>>> It is also worth remembering that Signal also has a notion of one-time prekeys that work similarly for new messaging sessions.
>>> Although the following would be a bit ridiculous to use in large dynamic groups, here  is a sketch to achieve the receiver FS guarantee without the need for new crypto.
>>> - Every time a member A sends an update, it generates fresh node secrets for nodes on the path from A to the root
>>> - From each node secret, A generates a large number K (= 100) private-public encryption keypairs and sends the public keys with the update..
>>> - On receiving the update, each member B stores all K public keys for each node in its co-path
>>> - Each of these public keys can be used only once for sending an update, after which the private key is deleted from all recipients.
>>> - The last public key at each node is not deleted; it can only be replaced when one of the members under that node sends a new update (with a fresh batch of public keys)..
>>> As far as I understand, the above scheme can be seen as an (inefficient) implementation of UPKE, right?
>>> Of course, it increases the size of each update by K, and only provides FS for K updates, after which some member has to send an update.
>>> Conversely, it does not require any new crypto algorithm. Is this a good baseline to compare UPKE schemes against?
>>> If I am mis-reading something, do let me know!
>>> -Karthik
>>>> On 17 Oct 2019, at 17:18, Joel Alwen < <>> wrote:
>>>> I think the challenge with the hash-forward approach is how to do that
>>>> homomorphically. I.e.. what we need are two algorithms; one to refresh
>>>> the PK without knowing the SK (but possibly knowing a secret
>>>> rerandomizer delta if needed) and one to update SK (again possibly using
>>>> delta). So to use a hash-forward approach their must be:
>>>> 1) a way to evolve PK forward to PK' and
>>>> 2) a *one-way* method to evolve SK forward to SK' compatible PK'.
>>>> One-wayness is what gives us Forward Secrecy and "compatibility" between
>>>> the two key evolution methods is what allows for asynchronous (i.e. 1
>>>> packet) updates.
>>>> Currently we use a secret re-randomizer delta to ensure the SK update
>>>> method is one-way. That is, without the delta you cant "undo" the
>>>> update. But that would break if we (at least naively) used some public
>>>> delta, say hash(ciphertext). So I think this is the challenge that we'd
>>>> have to overcome.. Basically, make sure we SK evolution is one-way but
>>>> also compatible the public evolution of PK.
>>>> Now one way sweet way to get all this (and more) would be to use a HIBE.
>>>> Initial, PK for a ratchet tree node (i.e. its "identity" since this is a
>>>> HIBE now) is simply the empty vector PK := () while the secret key is
>>>> the master public key for a fresh HIBE instance SK := MSK. We also
>>>> include, as a second component of the nodes PK, the master public key
>>>> PK_0 = MPK. To "hash forward" / "re-randomize" when sending a ciphertext
>>>> C to that node we can do:
>>>> PK' := (PK, hash(C)).
>>>> SK' := DeriveHIBEKey(PK, SK).
>>>> So simply append hash(C) to the identity for that node and derive the
>>>> corresponding HIBE key.
>>>> Ignoring the problems with using HIBE for a second, this is a very cool
>>>> solution. We don't need to send out the updated PK since everyone in the
>>>> group (and even the adversary) can compute it for themselves. We also
>>>> dont need a re-randomize delta as part of the plaintext because we're
>>>> using delta := hash(ciphertext) so the plaintext is shorter again.
>>>> Moreover, HIBE security means that learning SK' doesn't tell you
>>>> anything interesting about SK. In particular, we have forward security.
>>>> (In fact, FS will hold even if hash(C) were chosen *completely*
>>>> adversarially, say, as part of a malicious update in an insider attack!)
>>>> Of course, the problem with this solution is that we're using HIBE.
>>>> Worse, with unbounded depth because each new ciphertext sent to a node
>>>> results in going one depth further into the hierarchy. AFAIK all HIBE
>>>> constructions have pretty horrible (read exponential) efficiency as a
>>>> function of their depth. (And I won't mention the state of
>>>> standardization and open implementations for HIBE.)
>>>> Now there could be a totally different approach that entirly avoids
>>>> HIBE. But even with this approach there's at least some glimer of hope
>>>> to improve on it because, if we don't wory about insider attacks we can
>>>> assume C is honestly generated which means hash(C) really has a ton of
>>>> entropy. So we dont seem to need the full expresivity HIBE identities
>>>> allow us. Rather we only need HIBE for "random" identities. Still, that
>>>> seems like a pretty slim hope for major efficiency improvement. It also
>>>> doesn't do anything to address the lack of implementations and standards.
>>>> - Joël
>>>> On 17/10/2019 16:37, Karthik Bhargavan wrote:
>>>>> Thanks Yevgeniy,
>>>>> This helps a lot.
>>>>> To further my understanding, another question:
>>>>>>  Intuitively, the sender will not only encrypt the message, but also a
>>>>>> random Delta value. It will change public key using homomorthism by
>>>>>> multiplying with g^Delta (in specific DH based scheme), while the
>>>>>> recipient will decrypt Delta (using old secret key), and add it to the
>>>>>> old secret key to get there new one. So now corrupting (old sk plus
>>>>>> Delta) will not help decrypting the ciphertext just decepted, emailing
>>>>>> forward secrecy. 
>>>>> I see that in the DH-based scheme, this Delta needs to be private,
>>>>> otherwise the adversary can compute sk once it knows sk+Delta.
>>>>> But, in general, is it possible to conceive of a UPKE scheme where the
>>>>> recipient effectively “hashes forward” its symmetric key,
>>>>> where this one way hash-forward function does not have to rely on an
>>>>> externally chosen secret value?
>>>>> Best,
>>>>> Karthik
>>>>>> This is the high level, hope it makes sense.
>>>>>> Thanks for your question,
>>>>>> Yevgeniy
>>>>>> On Thu, Oct 17, 2019, 1:43 AM Karthik Bhargavan
>>>>>> < <>
>>>>>> < <>>> wrote:
>>>>>>    Hi Joel,
>>>>>>    This looks very interesting. It is new to me since I was not at
>>>>>>    the interim.
>>>>>>    After reading the paper and the slides, I am still a bit fuzzy
>>>>>>    about what the recipient of an update needs to do.
>>>>>>    For example, for the running example in your slide deck, it would
>>>>>>    help if I could see:
>>>>>>    - what secret keys does each leaf need to keep
>>>>>>    - how do these secrets change when an update from some other node
>>>>>>    is received.
>>>>>>    Just working this out for one update is enough.
>>>>>>    I know that this is made precise in the eprint, but it would be
>>>>>>    faster if you could help us understand it :)
>>>>>>    Best,
>>>>>>    Karthik
>>>>>>> On 16 Oct 2019, at 23:51, Joel Alwen < <>
>>>>>>    < <>>> wrote:
>>>>>>> <FS-TreeKEM.pdf>
>>>>>>    _______________________________________________
>>>>>>    MLS mailing list
>>>>>> <> < <>>
>>>>>> <>
>>>>> _______________________________________________
>>>>> MLS mailing list
>>>>> <>
>>>>> <>
>>>> _______________________________________________
>>>> MLS mailing list
>>>> <>
>>>> <>
>>> _______________________________________________
>>> MLS mailing list
>>> <>
>>> <>
>>> _______________________________________________
>>> MLS mailing list
>>> <>
>>> <>
>>> _______________________________________________
>>> MLS mailing list
>>> <>
>>> <>
>> _______________________________________________
>> MLS mailing list
> _______________________________________________
> MLS mailing list