Subject: [MLS] Prevent/Reduce collisions of commit_secrets

From: Cornelissen Eric <[email-masked]>
Date: Mon, 7 Sep 2020 14:14:59 +0000

Hi all,

I want to propose a slight modification to the direct_path derivation to prevent (to some extend) collisions at the root of the tree. In short, an adversarial group member can pre-compute a direct_path for a lower level and use the path_secret of its current node as the leaf_secret for the current direct_path derivation. The result is that the root_secret will be the same between two trees with a (significantly) different structure.

We can resolve this problem in a couple of ways (for concreteness I added the derivation logic at the end of this message) (clearly, this list is not exhaustive):

  1.  Add an increasing counter, starting from the leaf, to the path_secret derivation (*)
  2.  Add the node index of each node in the direct_path to the path_secret derivation
  3.  Add the node hash of each node in the direct_path to the path_secret derivation
  4.  Add (something derived from) the previous epoch's path_secret of each node in the direct_path to the path_secret derivation (**)

All of these solution guarantee that the adversary has to find collisions to cause the same commit_secret.  Additionally, the first two solutions prevent collisions within a group, the other two solutions potentially prevent collisions between groups as well.

Regards,

Eric

(*) Note that an increasing counter starting from the root won't work because it would be the same between the two trees I described in the attack.

(**) This is based on an earlier proposal raised by Joël & Sandro in the mailing list, see <https://mailarchive.ietf.org/arch/msg/mls/ZR84smU5xeLrziNTk5W1P1Z1nQI/> https://mailarchive.ietf.org/arch/msg/mls/ZR84smU5xeLrziNTk5W1P1Z1nQI/ (the MLS Specific Fix). I simplify the proposal here as the specifics can be found there and I think any discussion regarding it belongs in that thread.

----------

Below you can find concrete derivation of each proposal, For simplicity I use the context of ExpandWithLabel to include the additional information.

1. counter
    path_secret[0] = ExpandWithLabel(leaf_secret, "path", 0, KEM.Nh)
    path_secret[n] = ExpandWithLabel(path_secret[n-1], "path", n, KEM.Nh)

2. node index (where index(node[i]) returns the node index of node i)
    path_secret[0] = ExpandWithLabel(leaf_secret, "path", index(node[0]), KEM.Nh)
    path_secret[n] = ExpandWithLabel(path_secret[n-1], "path", index(node[n]), KEM.Nh)

3. node hash (where hash(node[i]) returns the node index of node i)
    path_secret[0] = ExpandWithLabel(leaf_secret, "path", hash(node[0]), KEM.Nh)
    path_secret[n] = ExpandWithLabel(path_secret[n-1], "path", hash(node[n]), KEM.Nh)

4. previous epoch path_secret (where path_secret[e, i] is path_secret[i] in epoch e), ignoring blanks for simplicity
    path_secret[e+1, 0] = ExpandWithLabel(leaf_secret, "path", path_secret[e, 0], KEM.Nh)
    path_secret[e+1, n] = ExpandWithLabel(path_secret[n-1], "path", path_secret[e, n], KEM.Nh)