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

[Joel Alwen <[e-mail]>]

To start with, I think forward secrecy (FS) within epochs can be valuable for
SFrame. (E.g. for long or repeating convo's with the same set of participants.)

Further responses are inline...

> Raphael Robert <[e-mail]> Fri, 20 November 2020 16:23 UTC 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).
> ...
> 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.

I might not get what your saying, but if I did then I don't think this gives any
FS, even between sessions, as long as they use the same value for
sframe_epoch_secret regardless of the choices of session_id. (And if they dont
use the same sframe_epoch_secret value then I don't see how the value of
session_id matters for FS.)

Suppose sframe_epoch_secret is used to derive sender_base_key[i]. After session
i is done participants still need to be able to reproduce sframe_epoch_secret if
they want derive sender_base_key[i+1] for session i+1. In that case they could
just as well recompute sender_base_key[i] again too. So no there's no FS for
session i.

Alternatively they could pre-compute all sender_key_base values for potential
future epochs but that seems inelegant to me. Bellow I describe my preferred
solution to precomputing and storing all potentially useful sender_key_base values.

>> On 20 Nov 2020, at 16:17, Richard Barnes <[e-mail]> wrote:
>> 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)

ATM I'm leaning towards option 2 or 3 (though not with a "simpler" schedule,
just different one more aligned with SFrame use cases).

When it comes to an SFrame epoch (i.e. a time period during which no one
joins/leaves the session) I think there are two constraints that informing which
FS symmetric key schedules are acceptable:

a. Parties shouldn't need to explicitly coordinate who will use which key/nonce
pairs during the epoch.
b. Ciphertexts in the media streams may be dropped and/or delivered out of order.

The tree-based symmetric key derivation hierarchy in MLS was explicitly designed
to accommodate these constraints and while being relatively efficient so, to me,
it looks like a good solution for SFrame as well. Thus option 2 doesnt sound bad
to me.



Having said that, Raphael highlights the case where epochs may be broken up into
sessions (e.g. when the same set of parties on an old call want to resume their
convo in a new call). If that's an important enough scenario to cater too then
the following Option 3 solution might be better. Namely, use one binary tree per
session and string the roots of the trees together in a symmetric ratchet (i.e.
a chain). This would minimize the state participants need to maintain between
sessions (effectively a single secret) while still giving us FS between (and
within) sessions despite them being part of the same epoch. For the sake of
concreteness:

chain_secret[0] = MLS-Exporter("SFrame 10 MLS", "", AEAD.Nk)
chain_secret[i] = HKDF-Expand(chain_secret[i-1], "chain", AEAD.Nk)
session_secret[i] = HKDF-Expand(chain_secret[i], "sesion"+session_id, AEAD.Nk)

and session_secret[i] is the secret at the root of the i-th sessions tree-based
symmetric key schedule. The j-th leaf of the tree initiates a symmetric ratchet
that defines the key/nonce pairs used to encrypt the j-th SFrame stream in the
session. So packet number k of SFrame stream j in session i is encrypted using
the key/nonce pair at position k in symmetric ratchet rooted at the leaf j of
the i-th tree; namely the one rooted at secret session_secret[i]. Yet between
session i and i+1 participants only need to store chain_secret[i+1].

- Joël