Re: [MLS] Re-randomized TreeKEM
Konrad Kohbrok <konrad.kohbrok@datashrine.de> Mon, 21 October 2019 12:20 UTC
Return-Path: <konrad.kohbrok@datashrine.de>
X-Original-To: mls@ietfa.amsl.com
Delivered-To: mls@ietfa.amsl.com
Received: from localhost (localhost [127.0.0.1]) by ietfa.amsl.com (Postfix) with ESMTP id C6A6712022A for <mls@ietfa.amsl.com>; Mon, 21 Oct 2019 05:20:41 -0700 (PDT)
X-Virus-Scanned: amavisd-new at amsl.com
X-Spam-Flag: NO
X-Spam-Score: -2.598
X-Spam-Level:
X-Spam-Status: No, score=-2.598 tagged_above=-999 required=5 tests=[BAYES_00=-1.9, RCVD_IN_DNSWL_LOW=-0.7, SPF_HELO_NONE=0.001, SPF_NONE=0.001] autolearn=ham autolearn_force=no
Received: from mail.ietf.org ([4.31.198.44]) by localhost (ietfa.amsl.com [127.0.0.1]) (amavisd-new, port 10024) with ESMTP id iODMzQkubH85 for <mls@ietfa.amsl.com>; Mon, 21 Oct 2019 05:20:38 -0700 (PDT)
Received: from mx2a.mailbox.org (mx2a.mailbox.org [80.241.60.219]) (using TLSv1.2 with cipher ECDHE-RSA-AES256-GCM-SHA384 (256/256 bits)) (No client certificate requested) by ietfa.amsl.com (Postfix) with ESMTPS id 6A10C120289 for <mls@ietf.org>; Mon, 21 Oct 2019 05:20:38 -0700 (PDT)
Received: from smtp2.mailbox.org (smtp2.mailbox.org [80.241.60.241]) (using TLSv1.2 with cipher ECDHE-RSA-CHACHA20-POLY1305 (256/256 bits)) (No client certificate requested) by mx2a.mailbox.org (Postfix) with ESMTPS id 57ECCA33C1 for <mls@ietf.org>; Mon, 21 Oct 2019 14:20:36 +0200 (CEST)
X-Virus-Scanned: amavisd-new at heinlein-support.de
Received: from smtp2.mailbox.org ([80.241.60.241]) by gerste.heinlein-support.de (gerste.heinlein-support.de [91.198.250.173]) (amavisd-new, port 10030) with ESMTP id xCpHZx1S79aV for <mls@ietf.org>; Mon, 21 Oct 2019 14:20:31 +0200 (CEST)
To: mls@ietf.org
References: <5b1d9cb1-509a-da7d-1361-188dfe0f21d6@wickr.com> <4BEAE096-9597-4619-ADD4-CE13E899481B@inria.fr> <CAMvzKsgMvLP5mmk8fOoTopKhFM6+EQzognv4Eq_FfMHSs9qwiA@mail.gmail.com> <5673C061-B15D-4DD2-A90C-4F179E82C31A@inria.fr> <133ba15a-037f-6a3b-182c-836b14ba233b@wickr.com> <8E87A52E-62CB-4CC0-A715-F236B03AC9E1@gmail.com>
From: Konrad Kohbrok <konrad.kohbrok@datashrine.de>
Message-ID: <dbe0eb1a-7a6a-4973-0951-7b6dd6f74a56@datashrine.de>
Date: Mon, 21 Oct 2019 14:20:30 +0200
MIME-Version: 1.0
In-Reply-To: <8E87A52E-62CB-4CC0-A715-F236B03AC9E1@gmail.com>
Content-Type: text/plain; charset="utf-8"
Content-Language: de-DE
Content-Transfer-Encoding: 8bit
Archived-At: <https://mailarchive.ietf.org/arch/msg/mls/y1EULsayK2htwIQS60DPnt2ue18>
Subject: Re: [MLS] Re-randomized TreeKEM
X-BeenThere: mls@ietf.org
X-Mailman-Version: 2.1.29
Precedence: list
List-Id: Messaging Layer Security <mls.ietf.org>
List-Unsubscribe: <https://www.ietf.org/mailman/options/mls>, <mailto:mls-request@ietf.org?subject=unsubscribe>
List-Archive: <https://mailarchive.ietf.org/arch/browse/mls/>
List-Post: <mailto:mls@ietf.org>
List-Help: <mailto:mls-request@ietf.org?subject=help>
List-Subscribe: <https://www.ietf.org/mailman/listinfo/mls>, <mailto:mls-request@ietf.org?subject=subscribe>
X-List-Received-Date: Mon, 21 Oct 2019 12:20:43 -0000
Hi Karthik, I think you got it right with regard to the additional guarantees gained by RTreeKEM. Regarding your UPKE proposal: Wouldn't A then also have to send the private keys of each key pair to all leaves of the sub-tree blonging to the node that the key pair is generated for? Otherwise, only A could decrypt updates sent to those keys. These private keys would have to be encrypted under some previous one-time key that is subsequently deleted. Cheers, Konrad On 21.10.19 15:03, 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 <jalwen@wickr.com >> <mailto:jalwen@wickr.com>> 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 >>>> <karthikeyan.bhargavan@inria.fr <mailto:karthikeyan.bhargavan@inria.fr> >>>> <mailto:karthikeyan.bhargavan@inria.fr>> 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 <jalwen@wickr.com >>>>> <mailto:jalwen@wickr.com> >>>> <mailto:jalwen@wickr.com>> wrote: >>>>> >>>>> <FS-TreeKEM.pdf> >>>> >>>> _______________________________________________ >>>> MLS mailing list >>>> MLS@ietf.org <mailto:MLS@ietf.org> <mailto:MLS@ietf.org> >>>> https://www.ietf.org/mailman/listinfo/mls >>>> >>> >>> >>> _______________________________________________ >>> MLS mailing list >>> MLS@ietf.org <mailto:MLS@ietf.org> >>> https://www.ietf.org/mailman/listinfo/mls >>> >> >> _______________________________________________ >> MLS mailing list >> MLS@ietf.org <mailto:MLS@ietf.org> >> https://www.ietf.org/mailman/listinfo/mls > > > _______________________________________________ > MLS mailing list > MLS@ietf.org > https://www.ietf.org/mailman/listinfo/mls >
- [MLS] Re-randomized TreeKEM Joel Alwen
- Re: [MLS] Re-randomized TreeKEM Karthik Bhargavan
- Re: [MLS] Re-randomized TreeKEM Yevgeniy Dodis
- Re: [MLS] Re-randomized TreeKEM Karthik Bhargavan
- Re: [MLS] Re-randomized TreeKEM Karthik Bhargavan
- Re: [MLS] Re-randomized TreeKEM Joel Alwen
- Re: [MLS] Re-randomized TreeKEM Brendan McMillion
- Re: [MLS] Re-randomized TreeKEM Karthikeyan Bhargavan
- Re: [MLS] Re-randomized TreeKEM Konrad Kohbrok
- Re: [MLS] Re-randomized TreeKEM Benjamin Beurdouche
- Re: [MLS] Re-randomized TreeKEM Konrad Kohbrok
- Re: [MLS] Re-randomized TreeKEM Joel Alwen
- Re: [MLS] Re-randomized TreeKEM Joel Alwen
- Re: [MLS] Re-randomized TreeKEM Yevgeniy Dodis
- Re: [MLS] Re-randomized TreeKEM Yevgeniy Dodis
- Re: [MLS] Re-randomized TreeKEM Brendan McMillion
- Re: [MLS] Re-randomized TreeKEM Joel Alwen
- Re: [MLS] Re-randomized TreeKEM Richard Barnes
- Re: [MLS] Re-randomized TreeKEM Karthikeyan Bhargavan
- Re: [MLS] Re-randomized TreeKEM Richard Barnes
- Re: [MLS] Re-randomized TreeKEM Benjamin Beurdouche
- Re: [MLS] Re-randomized TreeKEM Brendan McMillion
- Re: [MLS] Re-randomized TreeKEM Dennis Jackson
- Re: [MLS] Re-randomized TreeKEM Konrad Kohbrok
- Re: [MLS] Re-randomized TreeKEM Yevgeniy Dodis
- Re: [MLS] Re-randomized TreeKEM Brendan McMillion
- Re: [MLS] Re-randomized TreeKEM Dennis Jackson
- Re: [MLS] Re-randomized TreeKEM Yevgeniy Dodis
- Re: [MLS] Re-randomized TreeKEM Yevgeniy Dodis
- Re: [MLS] Re-randomized TreeKEM Brendan McMillion
- Re: [MLS] Re-randomized TreeKEM Konrad Kohbrok
- Re: [MLS] Re-randomized TreeKEM Raphael Robert
- Re: [MLS] Re-randomized TreeKEM Brendan McMillion
- Re: [MLS] Re-randomized TreeKEM Dennis Jackson
- Re: [MLS] Re-randomized TreeKEM Brendan McMillion
- Re: [MLS] Re-randomized TreeKEM Dennis Jackson
- Re: [MLS] Re-randomized TreeKEM Joel Alwen
- Re: [MLS] Re-randomized TreeKEM Konrad Kohbrok
- Re: [MLS] Re-randomized TreeKEM Richard Barnes