Re: [MLS] KDF instead of hashing up the tree

[Richard Barnes <[e-mail]>]

Note this is a little bit expensive in terms of message size; it changes
the size of an update from log(N) to log(N)^2.  It does not change the
number of DH operations

This is because you have to send the fresh secret for each intermediate
node in the tree to all its descendants.  Comparing the secrets you
generate in each case, from leaf to root, along a path of depth 3 with S0
at the leaf:

Current: S0, S1 = H(S0), S2 = H^2(S0), S3 = H^3(S0)
Proposed: S0, S1 = KDF(T0, S0), S2 = KDF(T1, S1), S3 = KDF(T2, S2)

Where T* are the fresh secrets called for here.  This doesn't change to
whom you encrypt things, but changes what you encrypt to each copath node:

Current -> Proposed
S1 -> S1, T1, T2
S2 -> S2, T2
S3 -> S3

(This is of course because you need to enable each recipient to compute up
the tree.)  So there's your log->log^2.

This discussion is not to say that I'm opposed to this idea.  It just looks
like it has some non-negligible cost, so we should make sure we know what
we're getting for that cost.

--Ricahrd



On Wed, Jan 23, 2019 at 8:58 AM Konrad Kohbrok <[e-mail]>
wrote:

> Hey everyone,
>
> I just discussed the current draft with my advisor Chris Brzuska and he
> came up
> with a suggestion that I thought I'd just quickly relay here. As I have
> only
> started following the discussion recently, I apologize if this was already
> brought up in the past.
>
> In terms of key separation, wouldn't it make for a cleaner design, if we
> used a
> KDF instead of a hash function? Instead of  generating a new leaf-node
> secret
> and then hashing it to compute the new secret for the parent node, it
> would be
> better to generate a new secret and then from that secret independently
> (i.e.
> with different labels) compute the new leaf secret and the new secret for
> the
> parent node. This key independence would also make the proof easier. In
> terms of
> overhead, this would mean two KDF operations instead of one hashing
> operation.
>
> Cheers,
> Konrad
>
> _______________________________________________
> MLS mailing list
> [e-mail]
> https://www.ietf.org/mailman/listinfo/mls
>