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

[Richard Barnes <[e-mail]>]

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
>