Subject: [Sframe] To tree or not to tree?

From: Richard Barnes <[email-masked]>
Date: Fri, 20 Nov 2020 10:17:11 -0500

Hi all,

One point that was raised during the SFrame meeting at IETF 109 was whether
the MLS-SFrame integration should re-use the MLS "secret tree" structure.

For those who might not be deep in MLS, the secret tree provides forward
secrecy for MLS messages sent within an epoch, without the need to generate
base keys for all participants [1].  In other words, if you have a group
where (a) only a few participants are speaking and (b) they ratchet their
key after each message, then the secret tree assures that compromise of any
group member with current state won't leak the keys for messages that have
already been sent/received.

Let's consider three possible integrations:

1. SFrame uses the same secret tree as MLS (export at the leaves)
2. SFrame exports a single secret, then makes its own secret tree
3. SFrame exports a single secret, then uses a simpler scheme (like the
current one)

I would posit that (1) is not workable.  That requires a tight coupling
between the MLS and SFrame stacks, which will often not be tractable, e.g.,
in situations where the media logic is in a separate thread or process from
the MLS logic.

(2) only adds value over (3) if SFrame senders ratchet their keys.
Otherwise, there's no forward secrecy boundary; criterion (b) above doesn't
apply.  The current MLS-SFrame document has no provision for ratcheting
within an epoch.  We could do it, but it would require more bits of header
to send a "generation" as MLS does, to indicate how many times you've
ratcheted.  It also seems like situations where you have mostly silent
participants are more rare in real-time cases than in messaging cases.

So my preference would still be for (3), largely because intra-epoch
forward secrecy seems like a pretty secondary consideration here.  If
intra-epoch forward secrecy is a problem people want to solve, then we
should do ratcheting, and we should do the secret tree.

--Richard

[1]
https://github.com/mlswg/mls-protocol/blob/master/draft-ietf-mls-protocol.md#secret-tree-secret-tree

---

From: Raphael Robert <[email-masked]>
Date: Fri, 20 Nov 2020 17:23:40 +0100

Thanks for the detailed write-up!

I agree that option 1 is very problematic for a number of reasons and I don’t see a good reason to pursue it.
I think you hit the nail on the head when you asked whether we want into-epoch forward secrecy or not.

In uses cases where call participants comes together ad-hoc as an ephemeral group, there is certainly little need for it. In other scenarios, where a fixed set of participants have reoccurring calls it might well be that there won’t be an epoch change for a considerable time (because no one joins or leaves the group). For these use cases option 2 & 3 come into play.
Option 2 solves the problem, but the solution comes at the price of implementation complexity.
Option 3 could be much simpler, namely it would be enough to use a unique session ID to derive a base key that is unique to the session:

sframe_epoch_secret = MLS-Exporter("SFrame 10 MLS", "", AEAD.Nk)
session_secret = HKDF-Expand(sframe_epoch_secret, session_id, AEAD.Nk)
sender_base_key[index] = HKDF-Expand(session_secret, encode_big_endian(index, 8), AEAD.Nk)

This is easy to implement and efficient but a little more error-prone since forward secrecy will only be achieved if session_id is unique between sessions. Re-using the same value will not yield forward secrecy.

Raphael

> On 20 Nov 2020, at 16:17, Richard Barnes <[email-masked]> wrote:
> 
> Hi all,
> 
> One point that was raised during the SFrame meeting at IETF 109 was whether the MLS-SFrame integration should re-use the MLS "secret tree" structure.  
> 
> For those who might not be deep in MLS, the secret tree provides forward secrecy for MLS messages sent within an epoch, without the need to generate base keys for all participants [1].  In other words, if you have a group where (a) only a few participants are speaking and (b) they ratchet their key after each message, then the secret tree assures that compromise of any group member with current state won't leak the keys for messages that have already been sent/received.
> 
> 3. SFrame exports a single secret, then uses a simpler scheme (like the current one)
> 
> I would posit that (1) is not workable.  That requires a tight coupling between the MLS and SFrame stacks, which will often not be tractable, e.g., in situations where the media logic is in a separate thread or process from the MLS logic.
> 
> (2) only adds value over (3) if SFrame senders ratchet their keys.  Otherwise, there's no forward secrecy boundary; criterion (b) above doesn't apply.  The current MLS-SFrame document has no provision for ratcheting within an epoch.  We could do it, but it would require more bits of header to send a "generation" as MLS does, to indicate how many times you've ratcheted.  It also seems like situations where you have mostly silent participants are more rare in real-time cases than in messaging cases.
> 
> So my preference would still be for (3), largely because intra-epoch forward secrecy seems like a pretty secondary consideration here.  If intra-epoch forward secrecy is a problem people want to solve, then we should do ratcheting, and we should do the secret tree.
> 
> --Richard
> 
> [1] https://github.com/mlswg/mls-protocol/blob/master/draft-ietf-mls-protocol.md#secret-tree-secret-tree <https://github.com/mlswg/mls-protocol/blob/master/draft-ietf-mls-protocol.md#secret-tree-secret-tree>-- 
> Sframe mailing list
> [email-masked]
> https://www.ietf.org/mailman/listinfo/sframe