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

[Konrad Kohbrok <[e-mail]>]

Exactly, thanks Karthik!

Say we have the same tree as in the example in 5.4:

         G
       /   \
      /     \
     E       _
    / \     / \
   A   B   C   D

Then A generates a fresh secret X_1secret and derives the following new secrets:
X_1kemkey=HKDF(X_1secret,"kemkey")
X_2secret=HKDF(X_1secret,"parent")

X_2kemkey=HKDF(X_2secret,"kemkey")
X_3secret=HKDF(X_2secret,"parent")

X_3kemkey=HKDF(X_3secret,"kemkey")

A then sends E(pk(B), X_2secret) to B, E(pk(C),X_3secret) to C and
E(pk(D),X_3secret) to D.

Hopefully that makes the idea a little clearer. Sorry for the terrible notation.

Konrad

On 23/01/2019 16:59, Karthikeyan Bhargavan wrote:
> If I understand correctly, Chris and Konrad are not suggesting changing the secrets.
> Instead, they are suggesting that H(.) be implemented as something like:
>
> H(x) = HKDF(x,label=”parent”)
>
> where x is the tree secret for the current node.
>
> Similarly, when generating the KEM private key for a node, we use
>
> KGEN(x) = HKDF(x,label=“kem key”)
>
> This would be a good way of making sure that each key in the protocol is
> independent, but at no additional cost.
> Am I understanding this correctly, Konrad?
>
>> On 23 Jan 2019, at 15:29, Richard Barnes <[e-mail] <mailto:[e-mail]>> wrote:
>>
>> 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 <konrad.kohbrok@datashrine..de
>> <mailto:[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] <mailto:[e-mail]>
>>     https://www.ietf.org/mailman/listinfo/mls
>>
>> _______________________________________________
>> MLS mailing list
>> [e-mail] <mailto:[e-mail]>
>> https://www.ietf.org/mailman/listinfo/mls
>