Re: [MLS] Subgroups

[Brendan McMillion <[e-mail]>]

Hi Marta and Joël, responses inline

On Thu, Mar 21, 2024 at 2:03 AM Mularczyk, Marta <[e-mail]> wrote:

> Hi Brendan,
>
>
>
> Thanks a lot for the input! The idea of using PRP to hide the leaf index
> is quite elegant. Here are our thoughts and questions about the overall
> design:
>
>
>
> * What were your high-level goals for the new design? Which of them were
> not met by our proposal?
>

The high-level goal was to support virtual clients in a way that preserved
privacy about a user's devices as much as possible, but also didn't require
changing the MLS wire format. For device privacy: hiding the set of
authorized devices, hiding when changes are made to this set (subject to FS
& PCS constraints), hiding which device sent a given message.


> * Do you know how available production quality implementations of FF1 are
> (especially, FIPS certified ones)? We’re a bit worried that this may be a
> blocker for adoption in some cases.
>

There are none that I'm aware of, but the NIST description also didn't
strike me as a big lift. I'm definitely open to alternatives


> * Your design reduces the effectiveness of the nonce-reuse guard mechanism
> compared to the one in MLS. E.g. in a group of 50k members, the reuse guard
> only has less than 17 bits of entropy.
>

This may be another reason to handle "device subgroups" and "organizational
subgroups" separately. For device subgroups, 50k devices for one user would
be exceptional.


> * Deriving prp_key := ExpandWithLabel(.., leaf_secret, ..) seems to
> require keeping leaf_secret over multiple epochs, which may compromise FS
> of KEM keys derived from leaf_secret. For example:
>
>    1. Virtual client Alice commits in supergroup to create epoch E1. This
>    defines leaf_secret from which, in particular, the KEM secret key sk for
>    the child node V of the root is derived (deterministically).
>    2. Bob commits in supergroup to create epoch E2. The commit’s update
>    path happens to overwrite the KEM key for node V. At this point, Alice
>    should delete sk to ensure forward secrecy for commit_secrets encrypted
>    (via path_secrets) to it.
>    3. Alice wants to send an application message in E2. So she needs the
>    prp_key for E2. For that she needs leaf_secret. But leaf_secret is still
>    available than we didn’t really get forward secrecy for past commit_secrets
>    in step 2.
>
> There seems to be an easy fix – derive prp_key from a different secret.
> E.g. prp_secret exported from the subgroup’s MLS session.
>

This is a great catch, thank you!


> * Another minor point, in MLS generating a key package kicks off PCS.
> (i.e. If Alice gets corrupted, and then generates a fresh KP we can still
> expect security from that KP.) All else being equal, we wanted to keep this
> guarantee for virtual clients * and therefore required that generating (a
> batch of) key packages requires a commit in the subgroup (which we should
> have made more clear in the write-up). I think your proposal doesn’t have
> this property since key packages are generated deterministically (apart
> from `random` but that is encrypted with the static key)?
>
> Requiring a commit every time a secret key is exported may also simplify
> the design, since the subgroup extension wouldn’t be needed?
>

I don't feel like we can say that doing a subgroup commit every time a
KeyPackage is generated actually provides PCS. For example, if I have two
devices and only one device ever generates new KeyPackages, even if it
commits every time, the other device could still be compromised. Until my
second device commits, any new KeyPackages won't provide PCS.

There is this line from section 6: "A subgroup MUST have either the same or
a stronger policy on how frequently devices must update their leaf node,
than the groups that the virtual client is a member of." -- Enforcing
regular commits from everyone is the best we can do I think


> * An observation: Our original design created the possibility of subgroup
> clients sending application messages anonymously from their virtual
> clients; i.e. such that other subgroup members do not (have to) be able to
> deduce which subgroup member sent a virtual client’s application message.
> This is an, albeit non-standard, security property we believe has some
> interesting niche applications and plays in nicely with wider meta-data
> hiding goals.
>
>
>
> Marta & Joël
>
>
>
> *From: *MLS <[e-mail]> on behalf of Brendan McMillion <
> [e-mail]>
> *Date: *Wednesday, March 20, 2024 at 03:18
> *To: *Konrad Kohbrok <[e-mail]>
> *Cc: *MLS List <[e-mail]>
> *Subject: *RE: [EXTERNAL] [MLS] Subgroups
>
>
>
> *CAUTION*: This email originated from outside of the organization. Do not
> click links or open attachments unless you can confirm the sender and know
> the content is safe.
>
>
>
> Hi Konrad
>
>
>
> I was able to publish the draft properly here:
> https://datatracker.ietf.org/doc/draft-mcmillion-mls-subgroups/
>
>
>
> This includes some updates from your feedback, also detailed below
>
>
>
> On Tue, Mar 12, 2024 at 6:23 AM Konrad Kohbrok <
> [e-mail]> wrote:
>
> Hi Brendan,
>
>
>
> Thanks for writing this up! Some comments:
>
>
>
> # 1 Introduction and 2 Conventions and Definitions
>
>
>
> - The language in the document is very specific to the use-case of a
> single user with multiple devices. As there are a few other use-cases for
> such a virtual clients protocol, it might be better to keep the terminology
> a bit more general.
>
>
>
> Yes, that's intentional. Almost all the content of the draft is about how
> to hide which device sent a message or generated a key. That design
> constraint seems unique to the multi-device use case and wouldn't apply to
> say, subgroups representing an organization, etc.
>
>
>
> # 3.2 Private Keys
>
>
>
> - There is a third instance where emulator clients will have to share
> randomness and that is to compute `path_secret[0]` as described in 7.5 of
> the MLS spec. It shouldn’t be a problem to include just add an extra
> deterministic key derivation step, though.
>
>
>
> Ah yes, I was misled by Fig 14 of RFC 9420 into thinking that
> path_secret[0] is already derived from leaf_secret.
>
>
>
> - I always thought that we’d have to rely on commits to coordinate the
> actions of emulator clients, but the including the encrypted PrivateKeyInfo
> is a neat way of doing so indirectly. At least for KeyPackage uploads.
>
> - If an emulator client uploads KeyPackages, it should probably also
> inform other emulator clients of the KeyPackage’s hash s.t. when they
> receive a Welcome (on behalf of the virtual client) they know which key to
> use for decryption. The other emulator clients can’t learn that hash from
> the Subgroup Extension, because they might not have access to the group’s
> tree if the group relies on RatchetTreeExtensions to transmit the ratchet
> tree. I don’t think that’s covered yet.
>
>
>
> I'm not sure we need to specify a protocol mechanism for this, as it is
> not security-sensitive and there are a lot of valid ways for the DS to
> handle it. The device can use an endpoint that allows fetching KPs by
> reference, the DS can send the relevant KP along with the Welcome, or KPs
> can be synchronized in the background.
>
>
>
> # 4 Application Messages
>
>
>
> - As I’ve already mentioned in my other mail, I’m not sure relying on
> DS-client coordination to prevent key reuse is necessarily better than the
> use of an extension, but that might depend on your use-case. My hope is
> that we can eventually come up with a way to avoid both.
>
>
>
> For the functional aspect of preventing reuse: I think we need to consider
> solutions in terms of whether the DS or Strongly Consistent or Eventually
> Consistent. A Strongly Consistent DS can allow devices to check that
> they've processed all of the messages sent to a group before sending their
> own message. This would solve the problem. With an Eventually Consistent
> DS, devices may simply need to retain encryption keys for a short while
> after they're used. Clients with an Eventually Consistent DS would
> generally already be retaining secrets longer than the deletion schedule
> advises, so it would not be unusual.
>
>
>
> # 5.2 Joining Externally
>
>
>
> - The process of discarding Welcomes is not quite clear to me. Is that
> meant to be done by the other emulator clients once they come back online?
> Or do we assume that the new emulator client can somehow access the pending
> messages of the offline clients? In the latter case, how would the new
> client even know what groups they are for? In any case, we should be very
> clear about things that do or don’t work when allowing external joins this
> way.
>
>
>
> Yes, there's an assumption that the new device can discard Welcomes sent
> to the virtual client before the external join happened. The new device can
> ask the DS for the list of groups that the virtual client is a member of --
> the DS has this information as a result of supporting External Joins in the
> first place.
>
>
>
> Overall, the protocol looks like a good approach to me. Do you want to
> create a PR against the existing virtual clients doc, or do you prefer to
> maintain a separate document for now?
>
>
>
> I'm not sure what the best resolution would be
>
>
>
> Cheers,
>
> Konrad
>
>
>
>
>
> Am 11.03.2024 um 04:51 schrieb Brendan McMillion <
> [e-mail]>:
>
>
>
> Hi mls@
>
>
>
> I wrote a draft today on how I would propose implementing the subgroups /
> virtual clients feature. I'm not currently able to submit it to the
> datatracker, but it is here:
> https://bren2010.github.io/draft-subgroups/draft-mcmillion-mls-subgroups.html
>
>
>
> Handling all of the edge cases I could think of, it still came out to be
> quite a simple proposal. Any feedback would be appreciated
>
> _______________________________________________
> MLS mailing list
> [e-mail]
> https://www.ietf.org/mailman/listinfo/mls
>
>
>
>