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

Raphael Robert <> Fri, 20 November 2020 16:23 UTC

Return-Path: <>
Received: from localhost (localhost []) by (Postfix) with ESMTP id 43B423A0B5D for <>; Fri, 20 Nov 2020 08:23:47 -0800 (PST)
X-Virus-Scanned: amavisd-new at
X-Spam-Flag: NO
X-Spam-Score: -1.898
X-Spam-Status: No, score=-1.898 tagged_above=-999 required=5 tests=[BAYES_00=-1.9, DKIM_SIGNED=0.1, DKIM_VALID=-0.1, HTML_MESSAGE=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 5CIhx-4GoNdZ for <>; Fri, 20 Nov 2020 08:23:45 -0800 (PST)
Received: from ( [IPv6:2a00:1450:4864:20::531]) (using TLSv1.2 with cipher ECDHE-RSA-AES128-GCM-SHA256 (128/128 bits)) (No client certificate requested) by (Postfix) with ESMTPS id D8C1E3A0B5A for <>; Fri, 20 Nov 2020 08:23:44 -0800 (PST)
Received: by with SMTP id q16so10098998edv.10 for <>; Fri, 20 Nov 2020 08:23:44 -0800 (PST)
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed;; s=20150623; h=from:message-id:mime-version:subject:date:in-reply-to:cc:to :references; bh=ytuyvQGrFX74LwkQk0tis5PscocxwncrZHllxTEVwfk=; b=v68RvJ+5ajVQDmmFFsVuxy6OIGmaeNhTXw22xZpjsDDTmU6eUjw2eF0u89Y6TfOugk cGXS7qFNMiB22PJeR1Rc2qg9YpWmQDHyoVTdU30EVNfvFDi9S98VxVI4lWVjhugU6voH htv2KbPc4TF088rha/uh8ZdATLlZC7mrlM2HyY60JJiyws0H9BjSRj6VeeiOJjZn/w6l xiMclZe0/fz+RTd9+KtwPXyf3rn0CA3CFIHRqjzylAC1/fURL2BlGLlMOAt6ity6KuhK zRW86ILn6I3DCgbe6DZElwQ5XybtzLmYoQOPnk9aFtJsZ2PB/WifGYW2jSDvRPzqLCkp 8hPw==
X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed;; s=20161025; h=x-gm-message-state:from:message-id:mime-version:subject:date :in-reply-to:cc:to:references; bh=ytuyvQGrFX74LwkQk0tis5PscocxwncrZHllxTEVwfk=; b=FYzGDfwgGDmclQcVSVap5iR+1IrnAmMLvoClMKBMkqy5jk8Dcc28WXDUnl4LtbIART yWG/u0lyQcqhW7hc7ADShE5WtdGLoQfdOPfxojVWqfEO/5uZbTFJuOAPWafpWo+iapNn onvMTh2PSvCW8pcQ5yXY7AAHel5CBSCUGARfhilx8zdbGHH6kbi9YCTiHtWTB9ZOLB0W ClC1rBRBMr1hJC6ugFRAgT8JAm532G6VGFsoANI2RQgDJDAY7VvdQiaWUiSb9XrzF+ci 1GuXE+CsDbiK+7uYQ+m1InCBcJS2Hve2VucAaHUDqW/YroJjiWjX6Fkj5JFGQK4Y2oYX rTgw==
X-Gm-Message-State: AOAM531tn+gwVIf+YH3fDqYb5QL4lK+SwP6doNXQfmWc6KQg53bkNTOt 9l56mZ0gf1cD3/KMcUregFrz+w==
X-Google-Smtp-Source: ABdhPJyae7c2YF+ZW+YvW6Rsa8Ce4zaFxHJ0v7Xqo/XM+ADngHF/biMd17gniVL459lfmRB090QXYQ==
X-Received: by 2002:aa7:dc05:: with SMTP id b5mr2506481edu.47.1605889422925; Fri, 20 Nov 2020 08:23:42 -0800 (PST)
Received: from ([]) by with ESMTPSA id a26sm1299733edt.74.2020. (version=TLS1_2 cipher=ECDHE-ECDSA-AES128-GCM-SHA256 bits=128/128); Fri, 20 Nov 2020 08:23:42 -0800 (PST)
From: Raphael Robert <>
Message-Id: <>
Content-Type: multipart/alternative; boundary="Apple-Mail=_43C6DFC5-C62A-48F9-BD17-0FCB1BA71C27"
Mime-Version: 1.0 (Mac OS X Mail 14.0 \(3654.\))
Date: Fri, 20 Nov 2020 17:23:40 +0100
In-Reply-To: <>
To: Richard Barnes <>
References: <>
X-Mailer: Apple Mail (2.3654.
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: Fri, 20 Nov 2020 16:23:47 -0000

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.


> On 20 Nov 2020, at 16:17, Richard Barnes <> 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.
> 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] <>-- 
> Sframe mailing list