Security Analysis and Improvements for the IETF MLS Standard for Group Messaging

Basic Info:

• Authors: Joël Alwen, Sandro Coretti, Yevgeniy Dodis, Yiannis Tselekounis
• Date: October, 2019
• Venue: preprint
• Full Version: https://eprint.iacr.org/2019/1189

This project consists of collaboration between Wickr and cryptographers at NYU and IOHK. The project started as an effort to do a formal security analysis of the core part of the MLS protocol called TreeKEM. To this end we adapted the notion of a Continuous Key Agreement from our recent paper [ACD19] (more on that paper here) to the group setting. This resulted in the new crypto primitive called Continuous Group Key Agreement (CGKA). We prove security for TreeKEM in both static and adaptive settings.

However, we soon hit a road block in that we were only able to prove unexpectedly weak forms of Forward Secrecy (FS) of TreeKEM.  It turned out that rather than being a limitation of our proof technique this was instead due to an unexpected rather severe weakness in TreeKEM’s FS property. In fact, once we uncovered the vulnerability it immediately became clear to us how to exploit it in the form of a rather serious class of attacks. What’s more, such attacks could, in turn, be extended into attacks on the PCS of MLS.

At this point, the project shifted focus to building a more secure CGKA component to replace TreeKEM in the MLS protocol. This resulted in the, so called, RTreeKEM construction. Along the way we introduced a new type of public key encryption (and KEM) called “Updateable Public Key Encryption” (UPKE). In essence, UPKE can be thought of as a truly practical way of building Forward Secure public key encryption.

Once we had constructed UPKE and RTreeKEM (from any prime-order group where the DDH holds) we went on to analyze and prove security for RTreeKEM. Concretely, we showed that RTreeKEM has at least as strong security as TreeKEM except for FS where RTreeKEM has vastly better FS properties. In particular, in a group with n people, TreeKEM requires n (at least) n/2 different group members to perform TreeKEM operations before FS is achieved. In contrast, for the same setting but using RTreeKEM the FS property is achieved immediately without the need for any further group operations!

For more about this project have look at the following resources.

• The pre-print writeup of our results over on eprint.
• A talk I gave about this project at Real World Crypto 2020.
• Slides for the talk.
• A blog post about the MLS protocol and another about this project.