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

[Richard Barnes <[e-mail]>]

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]>
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]
> https://www.ietf.org/mailman/listinfo/mls
>