[MLS] Improve FS granularity at a cost

[Konrad Kohbrok <[e-mail]>]

Currently, when a member of a group does not issue an update for a while and
then gets compromised, the adversary gets to see all the key material back until
that member had last sent an update. The application could enforce a policy,
where members have to issue updates in regular intervals, but in specific
scenarios, but we might be able to do better for a price.

Again, if this was already suggested earlier and for some reason didn't make it
into the document, I'm sorry.

In the case of an honest-but-lazy group member which is online, but doesn't send
updates, we could still get some FS guarantees in case that member gets corrupted.

One way of doing this could be puncturable encryption [1], where after a
decryption operation, the receiver "punctures" their private key such that a
certain set of ciphertexts (in our case, every ciphertext decrypted until that
point) can no longer be decrypted with this copy of the key, giving us forward
secrecy. I'm not intimately familiar with the details, but I think this doesn't
work with any public key encryption scheme, so it might limit our choice there.

Another way would be if with every update (or maybe with a special "UpdateAll"
handshake message), the updating node contributes to the key of every node
they would KEM an update to. Since we have to make sure that every node is still
aware of the (new) public key of every node that was impacted that way, we could
do something like this:

(This is similar to Yevgeniy's "delta" proposal for garbage collection or might
even be the same thing seen in a different light.) Along with the regular KEMed
secrets, the updating node (A) encrypts some additional randomness. Then, every
node changes their private and public keys using that randomness.

Revisiting the example from Section 5.4.:

         G
       /   \
      /     \
     E       _
    / \     / \
   A   B   C   D

Let's say A updates its secret key to X. Then, along with the relevant secrets
for the nodes in the resolution of its direct path, the ciphertext sent also
contains some fresh randomness r. The message sent to C for example would look
like this:

E(pk(C), r||h(h(X)))

Then E would update its private key to be Er and its public key to be
(g^E)^r=g^(Er)

Now every node can compute the new public key of every other node updated this
way, because they know the old key and they all received the same randomness
(resulting in n DH-operations for every node). If a node gets compromised, the
adversary only get the new key (Er), but won't be able to derive E from it and
thus can't access key material that was previously KEMed under that key.

Of course, this doesn't work if the victim is not online, but I still think it
might be a realistic threat model.

The catch here is that every member has to do log(n) exponentiations.

Konrad

[1]: https://ieeexplore.ieee.org/abstract/document/7163033