Separation between pre-published key packages and leaf node content

[TWal]

KeyPackages currently have two usages in the spec:

1. Pre-published key packages that you can download and put in a leaf when adding a new member
2. leaf node content that you update when doing a full Commit

Currently, things have been designed to use only one structure for both uses, leading to some weirdness such as:

• version and cipher_suite are useful in the usage 1, but are parameters of the group in usage 2.
• hpke_init_key is a good name in usage 1, but would better be named hpke_key in usage 2.
• some data is important in usage 2 and have no meaning in usage 1, hence they were designed as "mandatory-when-updating extensions" (such as ParentHash, and we were also discussing about adding the group_id in Stronger parent hashes for authenticated identities #527 to help prevent cross-group attacks)

How about using different structures for these?

// Essentially identical to KeyPackage
struct {
    ProtocolVersion version;
    CipherSuite cipher_suite;
    HPKEPublicKey hpke_init_key;
    opaque endpoint_id<0..255>;
    Credential credential;
    Extension extensions<8..2^32-1>;
    opaque signature<0..2^16-1>;
} PrePublishedKeyPackage;

struct {
    HPKEPublicKey hpke_key;
    opaque endpoint_id<0..255>;
    Credential credential;
    opaque parent_hash<0..255>;
    opaque group_id<0..255>;
    Extension extensions<8..2^32-1>;
    opaque signature<0..2^16-1>;
} LeafNodeContent;

enum {
    reserved(0),
    pre_published_key_package(1),
    leaf_node_content(2),
    (255)
} LeafNodeType;

struct LeafNode {
    // This is not included in the signature, but with the "unambiguous signature" PR that's not a problem
    LeafNodeType type;
    select(LeafNode.type) {
        case pre_published_key_package:
            PrePublishedKeyPackage data;
        case leaf_node_content:
            LeafNodeContent data;
    }
}

What would you think about refactoring KeyPackage like this?

[kkohbrok]

If we're doing this, I'd suggest including a dedicated public key to encrypt Welcome messages to for the PrePublishedKeyPackage. @psyoptix suggested this at some point. It gives us better FS guarantees, because the receiver of the Welcome can delete the corresponding private key immediately after decryption, while they might have to keep the other key around for a bit until they can actually issue an update.

This might also help clarify #538.

[tomleavy]

Ties into #537 as well because ParentHash is an example of an extension that is required and should be a field instead

[tomleavy]

@TWal one concern I have is how is that signature field in LeafNodeContent created?

[TWal]

When sending a full Commit, the participant includes a new LeafNodeContent in the UpdatePath (it replaces the leaf_key_package field).
It computes the signature with SignWithLabel(signature_key, "LeafNodeContent", LeafNodeContentTBS) where:

• LeafNodeContentTBS corresponds to all the fields of LeafNodeContent except signature (the usual thing)
• SignWithLabel comes from Unambiguous signatures #526

[tomleavy]

What about the scenario where Alice pulls down Bob's key package to add him to the group? In that case Alice can't do the conversion between formats on Bob's behalf.

[TWal]

Alice don't have to do the conversion, this is why LeafNode either contain a PrePublishedLeafPackage (when adding someone to the group) or a LeafNodeContent (when updating your own key package).

[tomleavy]

Ah somehow I missed that part in your original post. Makes sense

[bifurcation]

I like this general direction. It solves a few things.

Instead of having leaf nodes contain either a prepublished thing or a normal leaf node, how about having the prepublished thing wrap the leaf node thing? As a bonus, we get separation between the key pair used for Welcome encryption and the key pair that goes in the leaf for TreeKEM.

struct {
    HPKEPublicKey hpke_key; // used for TreeKEM
    opaque endpoint_id<0..255>;
    Credential credential;
    opaque parent_hash<0..255>; // empty when prepublished
    Extension extensions<8..2^32-1>; // MUST have capabilities
    opaque signature<0..2^16-1>;
} LeafNodeContent;

// Adds the things that aren't in the leaf node and wraps in another signature
struct {
    ProtocolVersion version;
    CipherSuite cipher_suite;
    HPKEPublicKey init_key; // used for Welcome
    LeafNodeContent leaf_node;
    Extension extensions<8..2^32-1>; // MUST have lifetime
    opaque signature<0..2^16-1>;
} KeyPackage; // no need for "PrePublished"

Then when Alice adds Bob, she extracts his LeafNodeContent and sends that in the Add. That doesn't let the other members of the group verify that Alice did the right thing w.r.t. expiry, but I'm not heartbroken about that.

We might also be able to remove the extensions field from the outer (KeyPackage) wrapping if we turn the lifetime extension into KeyPackage field. I expect we probably need leaf extensions, but would be open to making capabilities into a field.

[kkohbrok]

Why not keep sending the KeyPackage in the Add? That wouldn't cost much and would allow everyone to validate the lifetime. Note, that the lifetime is crucial in achieving PCS for pre-published key material. If I compromise Bob and get hold of the private key material of a bunch of his KeyPackages, I can add "Bob" to any group I want as long as the Credential inside the LeafNodeContent remains valid and Bob doesn't revoke the LeafNodeContent somehow.

Also, we'll have to do this if we want to enable any member to send the Welcome message as you proposed here: #525 (comment).

[TWal]

I agree that including LeafNodeContent inside KeyPackage is quite clean, but something is bothering me with this approach: I'd like that the group_id is signed by the participant occupying that leaf, to protect against cross-group attacks.

In the first message of this issue I did this by including group_id in LeafNodeContent, but in fact we don't need to store it in the leaf, we just need to include it in the LeafNodeContentTBS.

In any case, if we want to include group_id in the signature, we need a way to differentiate between leaves that triggered a commit and the ones that are "fresh". And for that I think using a tagged-union struct is the cleanest way to do it.

[kkohbrok]

It always feels a bit lazy to use an extension (and implementations have to be careful to check for their presence), but we could use a GroupId extension in the same way that we use a ParentHash extension. You will find both of them only on LeafContents that were updated at least once.

Another result of including GroupId in the KeyPackage is that the signature will explicitly sign the GroupId and I'm not sure if that doesn't completely destroy any deniability guarantees we can still get from MLS.

[bifurcation]

I don't think there's really a good way to get the group_id into the leaf. Because of prepublication, it would have to be optional, but in order to prevent attacks, you need rules to decide whether it's required in a given situation. It seems like the best you can do is basically TOFU:

• When you first get the tree, you can't validate whether the group_id should be in a given leaf or not
• Once you're a member, you require that group_id is sent in Update and UpdatePath.leaf_key_package

I could live with a solution of that character, but given it's a bit complex, might prefer to leave it out unless we get a useful property from it.

@kkohbrok - Re: Sending KeyPackage in Add - Yep, that makes sense. So you would send KeyPackage in Add, and LeafNode in Update.

[bifurcation]

I tried to worked through what would be necessary to implement this. It looks like it would require some fairly invasive changes to be made to rationalize the document's structure before making this change. But those changes should probably be made anyway. Proposal:

Preparatory PR: Rationalize layout

• Move "Cryptograhic Objects" to before "Ratchet Trees"
• Update "Ratchet Tree Nodes" to define ParentNode and LeafNode structs, with LeafNode initially just equal to KeyPackage
• Move subsections of "Key Packages" to under "Ratchet Trees"
  • Parent Hash
  • Tree Hashes
  • Update Paths
• Move Group State to its own top-level section

Main PR:

• Change LeafNode to have the required content:
  • HPKE key for TreeKEM
  • Credential
  • Parent hash
  • Capabilities
  • Extensions
  • Signature
• Change KeyPackage to refer to LeafNode for internals, plus:
  • HPKE key for Welcome
  • Lifetime
  • Extensions
  • Signature
• Add continues to send KeyPackage
• Update and Commit send LeafNode instead of KeyPackage
• Remove and Sender refer to LeafNodeRef instead of KeyPackageRef

We should probably do the preparatory PR regardless of this issue.

[bifurcation]

Discussion on working call:

• General agreement on the approach
• Should sign group_id when possible
  • Include in TBS if we at least have a flag for pre-published / in-group
  • Or we can store it
  • Or we could have independent structs for pre-published / in-group leaves
• Do we need extensions at both levels?
  • Capabilities / lifetime should probably be promoted to fields