Re: [MLS] Re-randomized TreeKEM
Benjamin Beurdouche <benjamin.beurdouche@inria.fr> Tue, 22 October 2019 22:10 UTC
Return-Path: <benjamin.beurdouche@inria.fr>
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 53D7012001A for <mls@ietfa.amsl.com>; Tue, 22 Oct 2019 15:10:50 -0700 (PDT)
X-Virus-Scanned: amavisd-new at amsl.com
X-Spam-Flag: NO
X-Spam-Score: -6.897
X-Spam-Level:
X-Spam-Status: No, score=-6.897 tagged_above=-999 required=5 tests=[BAYES_00=-1.9, HTML_MESSAGE=0.001, MIME_QP_LONG_LINE=0.001, RCVD_IN_DNSWL_HI=-5, SPF_HELO_NONE=0.001, SPF_PASS=-0.001, URIBL_BLOCKED=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 kihdPeDhRiHX for <mls@ietfa.amsl.com>; Tue, 22 Oct 2019 15:10:46 -0700 (PDT)
Received: from mail2-relais-roc.national.inria.fr (mail2-relais-roc.national.inria.fr [192.134.164.83]) (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 7B1F11200FD for <mls@ietf.org>; Tue, 22 Oct 2019 15:10:45 -0700 (PDT)
X-IronPort-AV: E=Sophos;i="5.68,217,1569276000"; d="scan'208,217";a="407606584"
Received: from unknown (HELO [10.115.242.142]) ([37.166.245.78]) by mail2-relais-roc.national.inria.fr with ESMTP/TLS/AES256-GCM-SHA384; 23 Oct 2019 00:10:42 +0200
Content-Type: multipart/alternative; boundary="Apple-Mail-1D087BA6-9141-4A85-85F6-D8F4BAACD0DD"
Content-Transfer-Encoding: 7bit
From: Benjamin Beurdouche <benjamin.beurdouche@inria.fr>
Mime-Version: 1.0 (1.0)
Date: Wed, 23 Oct 2019 00:10:38 +0200
Message-Id: <3B5BE109-6C78-474F-A0E5-138DE6931CF6@inria.fr>
References: <CAL02cgSykPGZhaS26MuR78XBS9OVfBzGYVEzcRRROqbP-P-t6A@mail.gmail.com>
Cc: Karthikeyan Bhargavan <karthik.bhargavan@gmail.com>, Messaging Layer Security WG <mls@ietf.org>, Joel Alwen <jalwen@wickr.com>, Yevgeniy Dodis <dodis@cs.nyu.edu>
In-Reply-To: <CAL02cgSykPGZhaS26MuR78XBS9OVfBzGYVEzcRRROqbP-P-t6A@mail.gmail.com>
To: Richard Barnes <rlb@ipv.sx>
X-Mailer: iPhone Mail (17A878)
Archived-At: <https://mailarchive.ietf.org/arch/msg/mls/Hoo45REkRCg_a-SmAblHVYhlv04>
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: Tue, 22 Oct 2019 22:10:50 -0000
That’s my opinion as well... :) B. > On Oct 22, 2019, at 11:34 PM, Richard Barnes <rlb@ipv.sx> 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 <karthik.bhargavan@gmail.com> 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 <rlb@ipv.sx> 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 <dodis@cs.nyu.edu> 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 <karthik.bhargavan@gmail.com> 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> 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>> 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>> wrote: >>>>>>>>> >>>>>>>>> <FS-TreeKEM.pdf> >>>>>>>> >>>>>>>> _______________________________________________ >>>>>>>> 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 mailing list >>>>>> MLS@ietf.org >>>>>> https://www.ietf.org/mailman/listinfo/mls >>>>> >>>>> _______________________________________________ >>>>> MLS mailing list >>>>> MLS@ietf.org >>>>> https://www.ietf.org/mailman/listinfo/mls >>>> _______________________________________________ >>>> MLS mailing list >>>> MLS@ietf.org >>>> https://www.ietf.org/mailman/listinfo/mls >>> _______________________________________________ >>> MLS mailing list >>> 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