Re: [MLS] Re-randomized TreeKEM

Richard Barnes <rlb@ipv.sx> Tue, 22 October 2019 21:20 UTC

Return-Path: <rlb@ipv.sx>
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 B3DE61200F5 for <mls@ietfa.amsl.com>; Tue, 22 Oct 2019 14:20:43 -0700 (PDT)
X-Virus-Scanned: amavisd-new at amsl.com
X-Spam-Flag: NO
X-Spam-Score: -1.896
X-Spam-Level:
X-Spam-Status: No, score=-1.896 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_NONE=0.001, URIBL_BLOCKED=0.001] autolearn=ham autolearn_force=no
Authentication-Results: ietfa.amsl.com (amavisd-new); dkim=pass (2048-bit key) header.d=ipv-sx.20150623.gappssmtp.com
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 xCwDsnNLlSdj for <mls@ietfa.amsl.com>; Tue, 22 Oct 2019 14:20:40 -0700 (PDT)
Received: from mail-oi1-x229.google.com (mail-oi1-x229.google.com [IPv6:2607:f8b0:4864:20::229]) (using TLSv1.2 with cipher ECDHE-RSA-AES128-GCM-SHA256 (128/128 bits)) (No client certificate requested) by ietfa.amsl.com (Postfix) with ESMTPS id 9240212008D for <mls@ietf.org>; Tue, 22 Oct 2019 14:20:40 -0700 (PDT)
Received: by mail-oi1-x229.google.com with SMTP id o205so15475900oib.12 for <mls@ietf.org>; Tue, 22 Oct 2019 14:20:40 -0700 (PDT)
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=ipv-sx.20150623.gappssmtp.com; s=20150623; h=mime-version:references:in-reply-to:from:date:message-id:subject:to :cc; bh=j+tyXaREkcjRb1FNJ8ezjrWQSEmY7ZowrQXZCr7pDxU=; b=Lt8GyZWNhUfPNQuhBhnqPB9TnhnFkOyY4ixkXPb4oQu+tl59BSVbdVxW4WH5HVxwkX Qj//wnoTL3LmImWaLoX91h7xfWJ5FXHLfkOMuFw+HYYUDHVZnKvdGwtuUx51Te8BW+FM lmJWKj25OFPLRGsoagUmIyeDbH35540x0VKF2ozg23wHxFoN2Z20ArwbOi+OEW32Ipah Q30PTnPqG+ZZ5CCX8MXbXUvRHR7e5hE2sqlpt+7fCiaTpZcywdmsEM14zBvuVf9ZjFpl BdPlMYWg2lpCfHxiVdmi0vW+zu08uznw5R/2WXW3oUgfCjz95dwrRYsfAtgkh+wgb0SS 1Rfw==
X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20161025; h=x-gm-message-state:mime-version:references:in-reply-to:from:date :message-id:subject:to:cc; bh=j+tyXaREkcjRb1FNJ8ezjrWQSEmY7ZowrQXZCr7pDxU=; b=DvgCgJiiYWFt979NeB4VPGsEwj8veKcXk9GDQU3q8ZJAEiZF6ltu+OyWktmFAOiYk6 I0aOPtG/+dz0z4/f9Q8HEQDjXLiODkUeqhHe1y8UwfGThEZskRJ9cjyyGNUflkPQSAhi TCTzzVtY+q31U7DeViXO/8kYk1Sa2QxpUhwq3ctGppPV8nkwVZ8RNv5+flZps8WoslNl KnKlalFWTEPckF7R4UtLc9zV+2LDFP+1jcuOtnncSS86BUxjq3l23dYMb+JuFZYxaFYU JWuVFRxVmn9KUuhinWxiRps8Y5EgJzUI+7zi+7jhd5BYGGyK5zgg4RM/9BLgZR+5nLXu 27LQ==
X-Gm-Message-State: APjAAAVYjsx3I5+vwSTe050PVvsYBZgg/y8BrKkOks7l3JzpmldYBsDT SdhbRxnloQAD00P/iisjcZt9tBWoKveH8MSGRAtMcA==
X-Google-Smtp-Source: APXvYqzt5QMDvUH481xLuswzIW8fawARpnvgR4F+ABCEnl2mJPs6f4ojN2fxtxXuXVUB6g8xLsURQh8qoAAZudm8jGg=
X-Received: by 2002:aca:56d6:: with SMTP id k205mr1516257oib.51.1571779239712; Tue, 22 Oct 2019 14:20:39 -0700 (PDT)
MIME-Version: 1.0
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> <CAMvzKsh-Vt3VeF3Jb37j39a=DNs5gFCR67eREAAZbBUvKxxY2A@mail.gmail.com>
In-Reply-To: <CAMvzKsh-Vt3VeF3Jb37j39a=DNs5gFCR67eREAAZbBUvKxxY2A@mail.gmail.com>
From: Richard Barnes <rlb@ipv.sx>
Date: Tue, 22 Oct 2019 17:20:19 -0400
Message-ID: <CAL02cgRO+Wdj41xoC7mJ9nQCGtmU8Uk3B3MRP-XkMs7faMPNpA@mail.gmail.com>
To: Yevgeniy Dodis <dodis@cs.nyu.edu>
Cc: Karthikeyan Bhargavan <karthik.bhargavan@gmail.com>, Messaging Layer Security WG <mls@ietf.org>, Joel Alwen <jalwen@wickr.com>
Content-Type: multipart/alternative; boundary="0000000000003fa2eb0595865f07"
Archived-At: <https://mailarchive.ietf.org/arch/msg/mls/oDUPuiRMp6w_7m7XfGxHrICPdwI>
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 21:20:44 -0000

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 <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 <jalwen@wickr.com>>>; wrote:
>>
>>
>> <FS-TreeKEM.pdf>
>>
>>
>>    _______________________________________________
>>    MLS mailing list
>>    MLS@ietf.org <mailto:MLS@ietf.org <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
>