Re: [MLS] New Tree-based Application Key Schedule

[Richard Barnes <[e-mail]>]

Hey Joel,

Just reviewed your PR (https://github.com/mlswg/mls-protocol/pull/146).
Sorry for the long delay; the impending Internet-Draft deadline in a week
has spurred the authors back into action.

Overall, this seems pretty much right.  My major concern is that the
mechanism seems a bit heavy-weight, in that it pulls in a bunch of context
in the key derivations.  It seems like we could get away with a much
simpler scheme (as I've outlined in the review comments), but if you think
there are reasons we need the extra context, I'm listening.

Cheers,
--Richard



On Fri, Apr 12, 2019 at 2:31 PM Joel Alwen <[e-mail]> wrote:

> Hey Richard,
>
> Thanks for your response! For the deletion schedule I think there's no
> problem with out-of-order messaging. Basically if a secret is consumed then
> just before deleting it derive any (unconsumed) children values that may
> still be needed.
>
> E.g. if in a ratchet msg j arrives before j'<j then first derive the j'-th
> key/nonce for deleteing secret j'. The same goes for any other (now
> consumed) secrets between j and j' in that ratchet. That way if any of
> those msgs arrive one can still decrypt them. But if there's a state
> leakage nothing useful for decrypting the j-th msg is leaked since keys &
> nonces are dead ends in the derivation hierarchy.
>
> Similarly in the AS Tree if a node's secret is marked as consumed then
> just before deleting it derive and store the secrets of its unconsumed
> child.
>
> - Joël
>
>
> On Fri, 12 Apr 2019, 20:14 Richard Barnes, <[e-mail]> wrote:
>
>> Hey Joël,
>>
>> Thanks a lot for putting this together.  I'll review the PR shortly.  In
>> case other folks need it, here's the link for the PR:
>>
>> https://github.com/mlswg/mls-protocol/pull/146
>>
>> Overall, I think this is a sane idea.  The thing that really sells it to
>> me is your observation that the AS tree has the same structure as the
>> ratchet tree, which points to a very elegant implementation approach:
>>
>> - Add a field to each ratchet tree node to store an app secret or nil
>> - On epoch update, clear out all the app secrets in the tree, and set the
>> root node's app secret to the epoch app secret
>> - When you need an app secret for a leaf (to encrypt or decrypt)
>>   - Search toward the root until you find a node with an app secret set
>>   - Work back out to the leaf, deriving the two app secrets for the
>> children and deleting the parent app secret
>>
>> On the "deletion schedule" idea: I might be wrong, but I don't think
>> we're going to be able to be super tight here.  Applications are going to
>> want to be able to tolerate out-of-order messages, in which case you're
>> going to want to keep around a parent secret after one or more of its
>> descendants have been consumed.  I like the "consumed" idea and
>> terminology, we just might have to apply it with a bit of flexibility.
>>
>> On the "context" question: I don't really feel strongly here.  The
>> current scheme doesn't really fold in any group context at all, which is
>> consistent with what TLS does [1].  Given that that's simpler, I might be
>> tempted to keep things that way until we find that there's some deficiency.
>>
>> --Richard
>>
>> [1] https://tools.ietf.org/html/rfc8446#section-7.2
>>
>>
>> On Fri, Apr 12, 2019 at 10:07 AM Joel Alwen <[e-mail]> wrote:
>>
>>> Hey everyone,
>>>
>>> I've submitted a PR implementing a tree-based application key schedule
>>> based on the ideas proposed by Benjamin Beurdouche, Sandro Corretti,
>>> Yevgeniy Dodis and myself.
>>>
>>> On the one hand it allows for easy handling of concurrent / out of order
>>> message delivery within an epoch (as each group member has their own
>>> independent symmetric ratchet). On the other hand it avoids having to do
>>> linear amounts of hashing and key/nonce storage as soon the moment the
>>> first message in an epoch is sent (as would be the case if we
>>> immediately seed all sender ratchets directly from application_secret as
>>> in the 03 draft).
>>>
>>> Basic idea:
>>> - The Application Key Schedule consists of a left balanced binary tree
>>> of secrets (the "AS Tree") and one symmetric ratchet per group member.
>>> The AS Tree has the same node/edge structure as the ratchet tree for
>>> that epoch. Members are assigned the same leaves.
>>> - Each node in the AS Tree is assigned a secret. The root's secret =
>>> application_secret. The secrets of children are derived from that of
>>> their parent.
>>> - The secret of a leaf is the initial secret of a symmetric hash
>>> ratchet. The ratchet generates the key/nonce sequence used by the leaf's
>>> group member to encrypt messages during that epoch.
>>>
>>> Other comments:
>>> - I included a "Deletion Schedule": keys, nonces are 'consumed' if they
>>> are used to encrypt or successfully decrypt a message. Secrets are
>>> 'consumed' if a value derived from them are consumed. Any consumed value
>>> must be immediately deleted (for reasons of forward secrecy).
>>> - Maybe the most contentious issue: I was very generous with contexts
>>> for all calls to HKDF. E.g. I included Hash(GroupState_[n]) in the
>>> context of every call. I doubt its needed to prove security against more
>>> coarse adversarial models (e.g. ones that only do all-or-nothing state
>>> leakage). Still, as a matter of the "defense in depth" principle I think
>>> including as much relevant context as possible during all key/secret
>>> derivation is a good idea. Albeit only as long as the price (in
>>> computation, complexity, etc) is not too high. To that end, I used
>>> Hash(GroupState_[n]) instead of GroupState_[n] directly in the context
>>> as it is much short, needs only to be computed once at the start of the
>>> epoch and can then be used to very cheaply to construct any context
>>> needed for the rest of the new schedule.
>>>
>>> Curious what you all think!
>>> - Joël
>>>
>>> _______________________________________________
>>> MLS mailing list
>>> [e-mail]
>>> https://www.ietf.org/mailman/listinfo/mls
>>>
>>