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

From: Konrad Kohbrok <[email-masked]>
Date: Wed, 23 Jan 2019 15:58:25 +0200

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

---

From: Richard Barnes <[email-masked]>
Date: Wed, 23 Jan 2019 09:29:14 -0500

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 <[email-masked]>
wrote:

> _______________________________________________
> MLS mailing list
> [email-masked]
> https://www.ietf.org/mailman/listinfo/mls
>

---

From: Karthikeyan Bhargavan <[email-masked]>
Date: Wed, 23 Jan 2019 15:59:47 +0100

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 <[email-masked]> 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:
> 
> 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:[email-masked]>> wrote:
> Hey everyone,
> 
> [email-masked] <mailto:[email-masked]>
> https://www.ietf.org/mailman/listinfo/mls <https://www.ietf.org/mailman/listinfo/mls>

---

From: Konrad Kohbrok <[email-masked]>
Date: Wed, 23 Jan 2019 17:19:10 +0200

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:
>> On 23 Jan 2019, at 15:29, Richard Barnes <[email-masked] <mailto:[email-masked]>> 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:
>>
>> 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
>>
>> On Wed, Jan 23, 2019 at 8:58 AM Konrad Kohbrok <konrad.kohbrok@datashrine..de
>> <mailto:[email-masked]>> wrote:
>>
>>     Hey everyone,
>>

---

From: Richard Barnes <[email-masked]>
Date: Wed, 23 Jan 2019 10:47:49 -0500

Ah, ok, I get it.  I misunderstood "new secret" as "fresh entropy".

In that case, this falls into the "sure, if it makes the analysis better"
bucket.  We've been treating hashes/HKDF invocations as basically free.  At
some point we might need to worry about that, but I suspect that today is
not that day.

Want to make a PR?

--Richard

On Wed, Jan 23, 2019 at 10:19 AM Konrad Kohbrok <
[email-masked]> wrote:

> node
> whom
> >> (This is of course because you need to enable each recipient to compute
> up the
> >> tree.)  So there's your log->log^2.
> >>
> >>     I just discussed the current draft with my advisor Chris Brzuska
> and he
> >>     came up
> >>     In terms of key separation, wouldn't it make for a cleaner design,
> if we
> >>     used a
> >>     parent node. This key independence would also make the proof
> easier. In
> >>     terms of

---

From: Konrad Kohbrok <[email-masked]>
Date: Wed, 23 Jan 2019 20:05:56 +0200

Sure, I'll give it a go.

Konrad

On 23/01/2019 17:47, Richard Barnes wrote:
> bucket.  We've been treating hashes/HKDF invocations as basically free.  At some
> point we might need to worry about that, but I suspect that today is not that day.
> 
> Want to make a PR?
> 
> --Richard
> 
> 
> On Wed, Jan 23, 2019 at 10:19 AM Konrad Kohbrok <[email-masked]
>     >> On 23 Jan 2019, at 15:29, Richard Barnes <[email-masked] <mailto:[email-masked]
>     <mailto:[email-masked]>>> wrote:
>     >>
>     >> <mailto:[email-masked]
>     <mailto:[email-masked]>>> wrote:
>     >>
>     >>     Hey everyone,
>     >>
>     >>     [email-masked] <mailto:[email-masked]> <mailto:[email-masked]
>     <mailto:[email-masked]>>
>     >> [email-masked] <mailto:[email-masked]> <mailto:[email-masked]
>     <mailto:[email-masked]>>