Re: [MLS] Re-randomized TreeKEM

Karthikeyan Bhargavan <> Tue, 22 October 2019 21:26 UTC

Return-Path: <>
Received: from localhost (localhost []) by (Postfix) with ESMTP id AFFC51200F5 for <>; Tue, 22 Oct 2019 14:26:34 -0700 (PDT)
X-Virus-Scanned: amavisd-new at
X-Spam-Flag: NO
X-Spam-Score: -1.997
X-Spam-Status: No, score=-1.997 tagged_above=-999 required=5 tests=[BAYES_00=-1.9, DKIM_SIGNED=0.1, DKIM_VALID=-0.1, DKIM_VALID_AU=-0.1, FREEMAIL_FROM=0.001, 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 xO4gXlASks_y for <>; Tue, 22 Oct 2019 14:26:31 -0700 (PDT)
Received: from ( [IPv6:2a00:1450:4864:20::333]) (using TLSv1.2 with cipher ECDHE-RSA-AES128-GCM-SHA256 (128/128 bits)) (No client certificate requested) by (Postfix) with ESMTPS id 91CB7120096 for <>; Tue, 22 Oct 2019 14:26:30 -0700 (PDT)
Received: by with SMTP id c22so8423174wmd.1 for <>; Tue, 22 Oct 2019 14:26:30 -0700 (PDT)
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed;; s=20161025; h=from:message-id:mime-version:subject:date:in-reply-to:cc:to :references; bh=J7wVzBbrA2FaShAgVGNDBcwFC83g7jWwWKqRMFu5tWo=; b=vTD77vg+3dJqWT70YBQxuy4JBbrmeNQ12EUK/SFlDPiSnQn0Dfh1LVpBlJeuCmSBDm 2ZpPy8WBEqRpcc64hc1VLDajC/zJ+g2iLBpHs52inwRM8h9ynDT1Rsdu5HxuVT6w8Og9 GwA36OTB8KgwPPxXCi1wgsBq83Z0QKOpizeBfUrawjzRVL5FRBBnSe24SQaFKzQp1cMd lyia7l0Z01ZXo3bCH88zrQR8ko+3LSmMtb6fpk3zisR28Wp8zGiYzmT1Lx7/F2hMe1h0 LN725zH4Ro7lfkzy6BB7djxuQ3dkXeS2hFu0Rfi5+o4Hf2ElNmWgflbsQ4fw3/P/lxnh ev+A==
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=J7wVzBbrA2FaShAgVGNDBcwFC83g7jWwWKqRMFu5tWo=; b=Liap4kNmbcbG+oN8GxcnLmq7d0nFhpT44N0vlvnr9+fphGl40nSnT76vG53HV0a08r 99z6X1wda1N7QlgDAHYMuhPEmASjMDODMt2PYhc3AgslWsfAU/LX5GhxLTzBweDSJkQq YWPbUYX1MTZom3xj20Is+NDie76zoq7O9R/yd4PYtgga75mRst1Yy9wYJAYN7F2ohtyO dBfKhzORr1viJkGG51O6BfKvAqApvrfv1P6ARiS7D/pv2SD3cU+r3LPsA0/JbAVcjuJ/ sq0V5qITaKnF83+VG0uK3YASokeczM9mrac1+pvnvrL/LFBBut52pfiA+VjxPSheBFeo pe3g==
X-Gm-Message-State: APjAAAVi/1GQqCLkYe6xysDwHz70nkWsUVh/RxwIUuf/CncYpG+Ii3ol uz0v5U0f6UIGE5sNgcAvfCo=
X-Google-Smtp-Source: APXvYqy5sxzVE6ToDYKbmDxWDDK5+muysgp0Al6kqgdwAQiMp6XJU3Fx97BJNoo1UlquY1rdUTPBjg==
X-Received: by 2002:a1c:2c88:: with SMTP id s130mr4993658wms.66.1571779588640; Tue, 22 Oct 2019 14:26:28 -0700 (PDT)
Received: from [] ( []) by with ESMTPSA id a3sm17342499wmc.3.2019. (version=TLS1_2 cipher=ECDHE-RSA-AES128-GCM-SHA256 bits=128/128); Tue, 22 Oct 2019 14:26:27 -0700 (PDT)
From: Karthikeyan Bhargavan <>
Message-Id: <>
Content-Type: multipart/alternative; boundary="Apple-Mail=_32B02845-F0A9-486A-8E3B-C8A793480942"
Mime-Version: 1.0 (Mac OS X Mail 12.4 \(3445.104.11\))
Date: Tue, 22 Oct 2019 23:26:26 +0200
In-Reply-To: <>
Cc: Yevgeniy Dodis <>, Joel Alwen <>, Messaging Layer Security WG <>
To: Richard Barnes <>
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: Tue, 22 Oct 2019 21:26:35 -0000


Like I said, it would be a ridiculous design for MLS.
I was simply trying to understand the guarantees.


> 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