Subject: [MLS] Removing members from groups

From: Jon Millican <[email-masked]>
Date: Mon, 12 Feb 2018 11:01:32 +0000

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

---

From: Dennis Jackson <[email-masked]>
Date: Mon, 12 Feb 2018 18:08:52 +0000

Hello Jon,

I think I have a nice suggestion that would improve Option 1. The core
idea is to keep PCS by rotating the deleted keys and balance the
'ownership' of deleted members amongst the active group members. 

As you noted, you would have to replace any of the removed member keys
(X's) that A generated when A is removed from the group. There is
another issue: in the event A has bad randomness or is compromised at
the instant when they removed E, PCS no longer holds. The adversary
would know the unchanging replacement key X, which might never be
blanked if E's neighbors are inactive.  

This can be fixed by rotating X when A rotates their own key. Let
ancestor(A,E) be the closest ancestor of both A and E. Then the number
of intermediate values between E and ancestor(A,E) is the extra number
of values transmitted whenever A updates their own key. At worst this
doubles the number of values that A has to transmit when rotating their
key, e.g. when the common ancestor of A and E is the root node.

We can reduce this overhead. Let B be another group member such that
the path between ancestor(B,E) and E is smaller than ancestor(A,E) and
E). Then B should 'take over' the deletion of E by replacing X with a
value Y it has generated itself. This requires transmitting fewer extra
intermediate values than if A were to do it. (Plus if B is close enough,
B can just blank E). In the best case, this reduces overhead per
rotation from log n extra values, to 2 extra values. (Any closer B and
could just blank A)

For ease of implementation, this 'take over' can be done by B
issuing the 'Delete Member' for the X leaf node. This also has a nice
balancing property - even if A deletes a lot of members, other active
members of the group will take over the deleted members key rotation
and balance out the overhead of transmitting intermediate values. This
also limits the O(n) blowup for the deletion of a member.

I also had some ideas on how to give options 2 and 3 'true' PCS by
computing k using a subtree with leaf nodes made out of the log n nodes
on E's copath. The result is that the X value is updated whenever any
group member rotates their key, but at the cost of something like (log
log n) / 2 extra messages whenever any member rotates their key.
Overall, it seemed a lot more complex than option 1 for little to no
benefit.  

Hope that is helpful! 

All the best,
Dennis

On Mon, 12 Feb 2018 11:01:32 +0000
Jon Millican <[email-masked]> wrote:

> 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.
> 
> 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.
> 
> 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.
> 
> 
> * 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.
> 
> 
> 
> =====
> 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.
> 
> 
> * 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".
> 
> 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.
> 
> 
> 
> 
> =====
> 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).
> 
> 
> 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