Re: [MLS] Potential issues with "add-only" commits in young groups

[Cornelissen Eric <[e-mail]>]

Hi Richard,


I will try to get in a PR to change the initial init_secret from being zero to being random.


Regarding #2, thanks for the clarification. If, as you say, a joiner does not learn the value at the root of the TreeKEM tree in the case of an "add-only" commit, then the attack I describe doesn't work. To me, it was not 100% obvious from the spec whether or not this was true or not (though it makes sense seeing that the joiner doesn't need to know that value).


Regards,

Eric

________________________________
From: Richard Barnes <[e-mail]>
Sent: Wednesday, August 5, 2020 6:58:49 PM
To: Cornelissen Eric
Cc: [e-mail]
Subject: Re: [MLS] Potential issues with "add-only" commits in young groups

Hi Eric,

Thanks for the analysis, and the detailed, clear writeup.  I agree that there are some real issues here, and with the solution approach.  Just to align on a couple of details:

#1 is clearly a problem.  Good catch.

#2 is less clear to me.  You lose me when you say ""add-only" commits allow new group members (ONLY) to learn the value at the root of the TreeKEM tree".  How do you think this happens?  As I understand the spec, this is not the case.  New members are added to the "unmerged_leaves" array at the root, but they are not told the root secret or root private key.

In any case, I agree that we should change the initial init_secret from being zero to being random.  I think I had set it to zero out of a general caution against requiring fresh entropy, and likely under the theory that the first commit would change it (before `path` was optional).  But it is clearly necessary now.  If you would like to send a PR, I would be happy to review.

Thanks,
--Richard



On Wed, Aug 5, 2020 at 9:27 AM Cornelissen Eric <[e-mail]<mailto:[e-mail]>> wrote:

Hi All,


Quick introduction: my name is Eric, I have submitted a few issues in the MLS GitHub and I did an analysis of MLS for my Master's thesis last academic year, now I'm doing a research project related to MLS with C. Bruzska.


During this project I found a potential issues with "add-only" commits if used in the early lifetime of a group. I found two particular issues that I think are most important to look at and which I will describe both here.


Note 1: Neither of the issues I describe hold when a PSK is used, hence I will only consider scenarios where PSKs are not used.

Note 2: In both attacks the attacker must record the (encrypted) Welcome message(s) send out for a group (i.e. I'm assuming a network adversary).

Note 3: I use "add-only" commit to denote an commit that does not populate the path value of a commit and "full" commit to denote a commit that does populate the path vale of a commit. This, I suppose, deviates slightly from the draft.

Note 4: I attached diagrams explaining the attacks, I hope they are understandable :)


  1.  When using an "add-only" commit for the first commit (see attachment 01.jpg for a diagram)

The first issue is w.r.t. using an "add-only" commit as the very first commit of a new group. To the best of my knowledge this would result in the input to the key schedule being to two all-zero vectors. Namely, the init_secret for the first commit is always the all-zero vector and the commit_secret will be an al-zero vector because an "add-only" commit was used.


Now, this would allow ANYONE to derive the joiner_secret and welcome_secret for the first commit. With the welcome_secret we can decrypt the Welcome message for the user(s) being added to the group. From the Welcome message we can construct the GroupContext that is used in the key schedule (GroupContext_[n] is a subset of the GroupInfo in the Welcome message).


With all this information ANYONE can compute all of the keys produced by the key schedule for the first epoch and read any communication that happens in this epoch. Furthermore, if another "add-only" commit is used the input to the key schedule for the next epoch is also known to the attacker(!) as commit_secret will again be an al-zero vector, and we know the init_secret.


  1.  When using a "Full" commit followed by "add-only" commits (see attachment 02.jpg for a diagram)

The second issue arises from the fact that "add-only" commits allow new group members (ONLY) to learn the value at the root of the TreeKEM tree in some earlier epoch E. In general this is not a problem, because they won't know the init_secret for epoch E-1. However, if only the very first commit for a group is a "full" commit new group members do know the init_secret for epoch E-1, as it is always the all-zero-vector.


>From here the attack proceeds very similarly to the other attack. Imagine a group is created by Alice. Alice adds Bob to the group with a "full" commit (hence init_secret = 0 and commit_secret ≠ 0). Next, Alice adds Charlie to the group with an "add-only" commit (not updating the TreeKEM tree). Next, Alice adds Eve to the group also with an "add-only" commit (again not updating the TreeKEM tree).


At this point, Eve learn sthe value at the root of the TreeKEM tree. Since this hasn't changed since the first epoch, Eve can find the commit_secret for the first commit of the group. This, together with the fact that init_secret is the all-zero vector, allows Eve to compute the joiner_secret and welcome_secret for the first commit. Hence, Eve can now carry out the attack described first to obtain all the keys for the epoch in which Bob was added.


Furthermore, because the commit_secret for the next commit is the all-zero vector, Eve can compute the joiner_secret and welcome_secret for the second commit as well. Hence, Even can carry out the attack described first again. In fact, even is able to do this until she reaches the commit in which she was added herself.



I believe the easiest way to mitigate these attacks (and any attacks like it) is by requiring that the init_secret of the first commit is a randomly sampled value. Alternatively, the first two commits of a group could be required to be "full" commits.


Eric.


_______________________________________________
MLS mailing list
[e-mail]<mailto:[e-mail]>
https://www.ietf.org/mailman/listinfo/mls