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

From: Joel Alwen <[email-masked]>
Date: Fri, 12 Apr 2019 16:07:22 +0200

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

---

From: Richard Barnes <[email-masked]>
Date: Fri, 12 Apr 2019 14:14:24 -0400

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

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

---

From: Joel Alwen <[email-masked]>
Date: Fri, 12 Apr 2019 20:27:58 +0200

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

> 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:
>