Re: [MLS] Re-randomized TreeKEM

[Yevgeniy Dodis <[e-mail]>]

Hi Brandan.

To re-iterate Joel's answer, in terms of security RTreeKEM is at least as
good (and often strictly better) than TreeKEM in every dimension.
So whatever update policy somebody might apply to TreeKEM, applying the
same policy to RTReeKEM will be equally good and *likely
better* for security.

You correctly observed that RTreeKEM, by being strictly more secure, allows
for "lazier" update policies which nobody would ever consider
in the basic TreeKEM. And this leads to a potential danger of somebody
using a policy which is "too lazy" even for the more secure scheme.
But I think it is unfair to say that one would prefer a less secure scheme
because it is less likely to be mis-used.

So, in my opinion, the one and only consideration should be if efficiency
cost and slight loss of generality (as of now) justifies the gain in
security.  I hope the answer is yes, but would love to hear other opinions.

Thank you for voicing this though.
Yevgeniy

On Fri, Oct 18, 2019 at 1:49 PM Brendan McMillion <brendan=
[e-mail]> wrote:

> Hey Joel
>
> This is a pretty subtle topic so I want to state the assumption that my
> conclusion is based on upfront: RTreeKEM achieves FS and PCS after a single
> Update (and all users come online and process the update), while normal
> TreeKEM requires everyone in the group to Update before achieving the same
> security guarantee.
>
> This actually makes TreeKEM more attractive to me because it encourages
> implementors to keep the Update frequency high, and it provides an explicit
> signal to the group that everyone has processed every update. With TreeKEM,
> the policy would be “everybody Updates at least once per day”. But with
> RTreeKEM, the equivalent policy is “at least one person Updates every day”
> which isn’t as strong, because you don’t know whether or not everybody came
> online that day and processed the one Update.
>
> And if you have a high Update frequency, I don’t think the security
> properties of TreeKEM and RTreeKEM are materially different. But RTreeKEM
> has costs like being harder to implement, and restricting what algorithms
> we can use.
>
> It’s on this basis that I’m opposed to including RTreeKEM in the spec.
>
> On Oct 17, 2019, at 8:18 AM, Joel Alwen <[e-mail]> 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
> <[e-mail]
> <mailto:[e-mail] <[e-mail]>>>
> 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 <[e-mail]
>
>    <mailto:[e-mail] <[e-mail]>>> wrote:
>
>
> <FS-TreeKEM.pdf>
>
>
>    _______________________________________________
>    MLS mailing list
>    [e-mail] <mailto:[e-mail] <[e-mail]>>
>    https://www.ietf.org/mailman/listinfo/mls
>
>
>
> _______________________________________________
> MLS mailing list
> [e-mail]
> https://www.ietf.org/mailman/listinfo/mls
>
>
> _______________________________________________
> MLS mailing list
> [e-mail]
> https://www.ietf.org/mailman/listinfo/mls
>
>
> _______________________________________________
> MLS mailing list
> [e-mail]
> https://www.ietf.org/mailman/listinfo/mls
>