[MLS] Removing members from groups

[Jon Millican <[e-mail]>]

Hello all,

Before we made the drafts public, our informal group spent a lot of time discussing the various alternatives for how a member can be safely removed (or deleted) from a group. With everything now public, I wanted to present the main options that we were thinking about at the time, and present a new variant that I've been thinking about over the past few days.

The two main contenders that we considered were:

1. Replace-then-blank.
2. Mix in secret from punctured tree.

For all of these examples, I'll use this example tree, notating a node by the list of members who know its private key:



           ABCDEFGH
          /        \
         /          \
        /            \
       /              \
     ABCD            EFGH
    /    \          /    \
   /      \        /      \
  AB      CD      EF      GH
/  \    /  \    /  \    /  \
A    B  C    D  E    F  G    H



=====
Replace-then-blank.
—————————

This is perhaps the most natural way to use ART for deletion. The intuition is that you want to simply remove the evictee's leaf node from the ratcheting tree; but if you can't perform this yourself, you instead just replace their leaf key with one that they don't know, which will remain there until somebody who is capable performs the actual removal.

The mechanism for removing E works as follows:

If the deleter is F, G or H, they simply send an update to the tree that marks E as blank. These three can trivially do this, as they can perform the calculation DH(F, GH). This immediately and permanently locks out E, who now knows nothing about the tree. Nobody else is in a privileged position either; so this is ideal.

           ABCD_FGH
          /        \
         /          \
        /            \
       /              \
     ABCD            _FGH
    /    \          /    \
   /      \        /      \
  AB      CD      _F      GH
/  \    /  \    /  \    /  \
A    B  C    D  _    F  G    H



If the deleter is A, B, C or D; they cannot compute DH(F, GH), so must instead *replace* E with a key X that they must generate and then immediately destroy. This allows them to compute and transmit E's full path, and thus the tree can continue to be used, but E is again fully removed with no further knowledge of the contents of the tree.


           ABCDXFGH
         /        \
         /          \
        /            \
       /              \
     ABCD            XFGH
    /    \          /    \
   /      \        /      \
  AB      CD      XF      GH
/  \    /  \    /  \    /  \
A    B  C    D  X    F  G    H


The problem here though is that we have now put A in a privileged position, in that A could have been dishonest and failed to delete X. This isn't necessarily a problem if A is honest themself - or indeed if A continues to be in the tree - as they therefore already have access to the tree's contents; but we don't want the protocol to rely on both of these being true. Indeed, if X were to remain in the tree without ever being rotated, we could - if nothing else - suffer from weakened Post-Compromise Security.

The first mitigation here is to lazily perform the above blank operation next time a capable party (F, G and H in this situation) performs their own update.

The second is to ensure that *if A is deleted, any nodes which A was privileged over must also be re-replaced*. So, say, if B were to now delete A (which B can do directly), they would also have to generate an eviction key Y, to put in place of X, to make certain that A cannot still compute the tree's root key.


           _BCDYFGH
          /        \
         /          \
        /            \
       /              \
     _BCD            YFGH
    /    \          /    \
   /      \        /      \
  _B      CD      YF      GH
/  \    /  \    /  \    /  \
_    B  C    D  Y    F  G    H


This whole process ends up requiring a little extra book-keeping. It's not too complex, and I have a draft algorithm description for this, but having the book-keeping is something of a downside.


Advantages of replace-then-blank:
* It's a very natural way of using ART. Easy to understand.
* It seems to reasonably straight-forwardly maintain post-compromise security.

Disadvantages:
* Extra book-keeping somewhat increases protocol complexity.
* There are potential edge cases which could increase one-off delete cost to O(n). E.g. if A has deleted one of every leaf pair in a large tree, then somebody deletes A - they will also have to replace every one of A's siblings. This should be rare, and I'm pretty sure amortises away over many messages, but would still be a bad case.



=====
Mix in secret from punctured tree.
—————————

This approach uses a neat trick that we figured out to get efficient (n-1) subgroups of trees. For an example, in the tree that we've been using - if A wishes to send a message to everybody apart from E, they can encrypt it each of the public keys in E's copath: ABCD, F and GH.


           ABCDEFGH
          /        \
         /          \
        /            \
       /              \
     ABCD*           EFGH
    /    \          /    \
   /      \        /      \
  AB      CD      EF      GH*
/  \    /  \    /  \    /  \
A    B  C    D  E    F* G    H


This operation has logarithmic efficiency, as the copath is sized log(n). The principle also extends to a more general concept of "punctured trees"; whereby you can send a message to any subset of the tree based on the smallest set of keys that none of the excluded members know. This eventually degrades to linear in the worst case (every second leaf node has been excluded), but again this likely feels more edge-casey.


I believe the proposal here was:

* Keep track of all nodes who have been deleted.
* When you wish to delete a new node, generate a temporary key K, then compute a completely unbalanced tree with K as the left-most node, and each node up its copath being one of the nodes from the punctured tree. The root secret here is then KDFd into the epoch secret; making the epoch now uncomputable to E.


             KABCDFGH
            /        \
           /         GH
          /
       KABCDF
      /      \
     /        F
    /
  KABCD
/     \
K     ABCD


A nice property to note about doing this is that the server is capable of generating such a delete message - as it relies on no private information - and this may be useful in certain circumstances.


We had a fair bit of discussion about the post-compromise security properties here, which we very scientifically deemed to be "weird PCS".

Specifically the issue here is that E isn't necessarily removed from the tree at any point. They can still compute the tree root - but don't know the epoch secret, and so cannot compute any subsequent epoch secrets (due to their chaining). This means that if E were to compromise some other tree member, and therefore learn the epoch secret, E would effectively have reinserted themselves as an observer to the group, as they can compute all future operations.

To clarify, the reason that this is weird is that we tend to think of PCS as "PCS with respect to X". So if the protocol were to have PCS with respect to any individual participant - you would expect that after this participant has updated their own leaf key, anybody who had previously compromised them would be locked out again (I don't think this is a strict definition, but it's close enough as an intuition for a sensible mode of operation for PCS). However, in this situation, we don't have PCS with respect to anybody; so long as the attacker knows the leaf key for a deleted member.

One potential mitigation here would be to follow a delete with a blank operation - as in replace-then-blank. Otherwise what we seem to probably have is a protocol with forward secrecy, and "weird PCS".

Advantages of this approach with the mitigation in place:
* Much less book-keeping required: we never put anybody in a privileged position.
* Delete can be performed by non-group-members.

Disadvantages:
* Weird - or at worst weaker - post-compromise security.
* After many deletions, deletion time complexity may degrade to linear.






Of these approaches, we went with replace-then-blank for the initial draft due to its better (or, at least, more obvious) PCS properties.






Over the past few days I thought of a new approach based on punctured trees, that I believe may tolerate less book-keeping then replace-than-blank with better PCS with punctured tree mixins. I'm not fully sure of its merits or disadvantages, so I'd really appreciate feedback on whether it makes sense.




=====
Eviction-path public key mutations.
—————————

The problem with replacing a non-(sibling or cousin) node is that you cannot compute the value of a parent node without knowing the secret value at one of its child nodes. The above deletion approaches are therefore based on the idea that you cannot change the private values in another branch of the tree without inserting yourself into a privileged position. This assumption, however, *may* not be entirely correct.

What we need here is the ability to mutate somebody else's public key to something for which they - and only they - can compute the private key. Fortunately, I believe that Diffie-Hellman itself directly provides this.

For DH private key x, the public key is g^x. If we take a different private key k, we can perform the DH operation on it to get g^(xk). So far, this is standard DH - with g^(xk) typically being used as a shared secret. We could, however, instead treat xk as the new private key, and g^(xk) as its public key. This then means that if you can securely transmit k to everybody: they can all compute g^(xk); but only the original private key owner actually knows the private key xk - by the discrete logarithm problem. NOTE: I DO NOT KNOW IF MY REASONING HERE IS QUITE CORRECT. This definitely requires input from real cryptographers.

So, let's combine this mutation with punctured trees. Now, when A wants to delete E, they compute a new secret k, and transmit it to the punctured tree excluding E - ensuring that everybody apart from E knows it. Everybody applies the mutation to every node in E's path, and immediately deletes k, resulting in the tree:


          (ABCDEFGH)k
          /        \
         /          \
        /            \
       /              \
     ABCD           (EFGH)k
    /    \          /    \
   /      \        /      \
  AB      CD     (EF)k    GH
/  \    /  \    /  \    /  \
A    B  C    D  Ek   F  G    H


(Here we are actually breaking an invariant that used to hold from ART: specifically that a parent is directly calculated as KDF(DH(children)). This will mean that nodes need to cache their entire path, as they can't directly derive them, but this feels fine in practice: it's only logarithmic in size anyway, and we likely would want to cache it in real-world usage to avoid extra recalculations.)

This has the nice property that E no longer knows any private key in the tree; including their own. This could potentially allow us to never even bother to blank it out, but unfortunately we still have a slightly weird PCS property: if E had compromised anybody shortly *before* being deleted from the tree they could learn k when it is transmitted, and thus permanently reinsert themself into the tree. It's a much smaller compromise window than in the previous solution - which is any time in the future - but it's enough that we would probably still want to include blanking when the sibling or cousin next updates. We could also periodically send a new k until the node has been blanked to improve the mitigation (which, indeed, we could also do in the above solution).


Advantages of this approach:
* Same minimal book-keeping requirements as in "Mix in secret from punctured tree".
* Deletes can, again, be performed by non-group members.
* Deletes could always be logarithmic (without periodic re-keying).
* Small pre-emptive compromise window for evictees to be able to weaken PCS (without periodic re-keying).

Disadvantages:
* Still weaker PCS than replace-then-blank.
* Weird usage of DH which I'm not confident to assert is safe.





So, these are the options; please let me know if any of it isn't clear. I'd love to gather people's thoughts, and any alternative approaches you can think of - particularly as everything we've thought of so far involves certain compromises!


Thanks!
Jon