Subject: [MLS] Removing redundant ciphertexts in commits

From: "Jost Daniel" <[email-masked]>
Date: Mon, 21 Sep 2020 07:37:21 +0000

Hi all,

When working on our analysis of the standard with Joël Alwen and Marta Mularczyk, we noted some inefficiencies around commit messages.

According to our understanding of the draft, UpdatePath contains encryptions for newly added group members. More concretely, the draft states "If populating the path field: Create a UpdatePath using the new tree (which includes any new members)" and in Section 7.7 "The number of ciphertexts in the encrypted_path_secret vector MUST be equal to the length of the resolution of the corresponding copath node." However, at this point, the resolution will already contain the freshly added leaves via the unmerged_leaves list.

First, this wastes bandwidth and computation as the commit message is not intended to be received by parties being welcomed. Second, this poses an, albeit small, additional attack scenario where an attacker gets hold of the freshly added party's decryption key but not the welcome message (that may have been communicated over a secure out-of-band channel).

One potential solution would be to explicitly exclude freshly added parties from the resolution in that step, at the cost of some additional book-keeping. Of course we are open to suggestions if anybody has a better idea. If not, we are obviously happy to draft a PR.

Best,
Daniel

---

From: Joel Alwen <[email-masked]>
Date: Fri, 25 Sep 2020 16:25:52 +0200

So does anyone else see any reason for those ciphertexts? If not we can draft a
PR to get rid of them...

- Joël

On 21/09/2020 09:37, Jost Daniel wrote:
> Hi all,
> 
>  
> 
> When working on our analysis of the standard with Joël Alwen and Marta
> Mularczyk, we noted some inefficiencies around commit messages.
> 
>  
> 
> According to our understanding of the draft, UpdatePath contains encryptions for
> newly added group members. More concretely, the draft states "If populating the
> path field: Create a UpdatePath using the new tree (which includes any new
> members)" and in Section 7.7 "The number of ciphertexts in the
> encrypted_path_secret vector MUST be equal to the length of the resolution of
> the corresponding copath node." However, at this point, the resolution will
> already contain the freshly added leaves via the unmerged_leaves list.
> 
>  
> 
> First, this wastes bandwidth and computation as the commit message is not
> intended to be received by parties being welcomed. Second, this poses an, albeit
> small, additional attack scenario where an attacker gets hold of the freshly
> added party’s decryption key but not the welcome message (that may have been
> communicated over a secure out-of-band channel).
> 
>  
> 
> One potential solution would be to explicitly exclude freshly added parties from
> the resolution in that step, at the cost of some additional book-keeping. Of
> course we are open to suggestions if anybody has a better idea. If not, we are
> obviously happy to draft a PR.
> 
>  
> 
> Best,
> 
> Daniel
> 
> 
> _______________________________________________
> MLS mailing list
> [email-masked]
> https://www.ietf.org/mailman/listinfo/mls
>

---

From: Richard Barnes <[email-masked]>
Date: Fri, 25 Sep 2020 11:05:11 -0400

No, this makes sense.  I think things are the way they are because the
Commit used to be processed by the joiner, but that's no longer the case.

Thinking through how this works in practice... Right now, the order of
operations is as follows:

- Apply Update/Remove/Add proposals
- TreeKEM.encap()

I think you still want to do things in this order.  For example, you don't
want to process Add after encap(), since this will cause the new joiners to
be marked as unmerged leaves when they're really merged by the Commit.  The
better solution here seems to be to update the encap()/decap() algorithms
so that they have an additional "exclude list" argument, which lists leaves
that MUST be excluded from the computed resolution.  This has to be done on
encap() and decap() since the structure of the resolution defines the
structure of the UpdatePath.

Looking forward to the PR :)

--Richard