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

Joel Alwen <> Mon, 23 November 2020 13:45 UTC

Return-Path: <>
Received: from localhost (localhost []) by (Postfix) with ESMTP id 48AEF3A0B1C for <>; Mon, 23 Nov 2020 05:45:02 -0800 (PST)
X-Virus-Scanned: amavisd-new at
X-Spam-Flag: NO
X-Spam-Score: 0
X-Spam-Status: No, score=0 tagged_above=-999 required=5 tests=[DKIM_SIGNED=0.1, DKIM_VALID=-0.1, NICE_REPLY_A=-0.001, SPF_HELO_NONE=0.001, SPF_PASS=-0.001, URIBL_BLOCKED=0.001] autolearn=ham autolearn_force=no
Authentication-Results: (amavisd-new); dkim=pass (2048-bit key)
Received: from ([]) by localhost ( []) (amavisd-new, port 10024) with ESMTP id xQJHyOunjpYk for <>; Mon, 23 Nov 2020 05:45:00 -0800 (PST)
Received: from ( [IPv6:2a00:1450:4864:20::429]) (using TLSv1.2 with cipher ECDHE-RSA-AES128-GCM-SHA256 (128/128 bits)) (No client certificate requested) by (Postfix) with ESMTPS id 9864B3A0B1F for <>; Mon, 23 Nov 2020 05:45:00 -0800 (PST)
Received: by with SMTP id s8so18609371wrw.10 for <>; Mon, 23 Nov 2020 05:45:00 -0800 (PST)
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed;; s=20150623; h=subject:to:references:from:message-id:date:user-agent:mime-version :in-reply-to:content-language:content-transfer-encoding; bh=3VD31X4Xxj5g45yo3SoyeF6457Cj3fgW6wELlpTpp54=; b=QCOA4SewKhRZ4a9NSMxAUtI0yKYxyHTv46g87gEeczo4y4lePa+CA+DyqNorE52Hho EEtmoX+QVZoM+pkykBzgM6+71vpGpEiatymuAddPCG0bgVrusBKBKfYdFw46ppB2lhFl Yi/izE9kpKnRgqSzR+6U2XT8gZm6/FgF42+dR3GDSP9W/OpytaoFy2tcDIISuFIyPXPM bVVlu/vkRnMJobwT2NO2wH55jS8bdOaVqQyJ5KacoVPWOv5jG1BC30FX3uRRWlCq6uBn mpVq0DhuaruNGMhBaylS6lifxXnAtB3gLaMEeQT8f8ZJpWPn7yohF62rWzIvF13P801j jIwQ==
X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed;; s=20161025; h=x-gm-message-state:subject:to:references:from:message-id:date :user-agent:mime-version:in-reply-to:content-language :content-transfer-encoding; bh=3VD31X4Xxj5g45yo3SoyeF6457Cj3fgW6wELlpTpp54=; b=WX/ZoCis5YqssMlO5aSAIVzQHQzlIsYRcCTODV0NeD6zs/bThgsIkeE11eZGpkmXOb EHEJaVxFCfSwsTyey8SInFJcOz+bL0Jle/65lgpo9uWuqdyrRt8NFU1MGMcSvJuiDF78 27CqbQV+pTHWC/oTTrDbElDtR4uKDF/n2gPPubgQBUyxq1txSBTxZI8bbb2JQoDObZLp xORRdUXs79k1wZ6O1NPsQ1DQz0vcRS2qX6xAWbPhGtDvllU/zZcxjycibBQ11DoK95Fu vBPVEaEbTxeZxkpYs6yPEnNpU3VIq6N6+pnGD/48Y5Sb/D0ZZFo7qM/DPOCMOjfkh4lk gZfg==
X-Gm-Message-State: AOAM530+WQST7nld7RaEeeFRaqxRZtdA5GTKAkCCY0thw+9qiYRA8/gi 3a7BPvkgC4im3OnbU2x/hOiiJtH8C1lnzA==
X-Google-Smtp-Source: ABdhPJz4gP+qQwrVexymDLBe/LT2IFV5TBcuaByN/ifN6zJjyVJxoczddfovGY3rrPIeVP2yQAwsxQ==
X-Received: by 2002:adf:f3d1:: with SMTP id g17mr7844642wrp.201.1606139098843; Mon, 23 Nov 2020 05:44:58 -0800 (PST)
Received: from [] ( []) by with ESMTPSA id z6sm17224741wmi.1.2020. (version=TLS1_3 cipher=TLS_AES_128_GCM_SHA256 bits=128/128); Mon, 23 Nov 2020 05:44:58 -0800 (PST)
To:, Raphael Robert <>, Richard <>
References: <> <>
From: Joel Alwen <>
Message-ID: <>
Date: Mon, 23 Nov 2020 14:44:56 +0100
User-Agent: Mozilla/5.0 (Windows NT 10.0; Win64; x64; rv:78.0) Gecko/20100101 Thunderbird/78.5.0
MIME-Version: 1.0
In-Reply-To: <>
Content-Type: text/plain; charset=utf-8
Content-Language: en-US
Content-Transfer-Encoding: 8bit
Archived-At: <>
Subject: Re: [Sframe] To tree or not to tree?
X-Mailman-Version: 2.1.29
Precedence: list
List-Id: <>
List-Unsubscribe: <>, <>
List-Archive: <>
List-Post: <>
List-Help: <>
List-Subscribe: <>, <>
X-List-Received-Date: Mon, 23 Nov 2020 13:45:02 -0000

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

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