Modern secure messaging protocols can offer strong security guarantees such as Post-Compromise Security (PCS) , which enables participants to heal after compromise. The core PCS mechanism in protocols like Signal  is designed for pairwise communication, making it inefficient for large groups, while recently proposed designs for secure group mes- saging, ART , IETF’s MLS Draft-11 /TreeKEM , use group keys derived from tree structures to efficiently pro- vide PCS to large groups. Until now, research on PCS designs only considered healing behaviour within a single group. In this work we provide the first analysis of the healing behaviour when a user participates in multiple groups. Sur- prisingly, our analysis reveals that the currently proposed pro- tocols based on group keys, such as ART and TreeKEM/MLS Draft-11, provide significantly weaker PCS guarantees than group protocols based on pairwise PCS channels. In fact, we show that if new users can be created dynamically, ART, TreeKEM, and MLS Draft-11 never fully heal authentication. We map the design space of healing mechanisms, analyz- ing security and overhead of possible solutions. This leads us to a promising solution based on (i) global updates that affect all current and future groups, and (ii) post-compromise secure signatures. Our solution allows group messaging pro- tocols such ART and MLS to achieve substantially stronger PCS guarantees. We provide a security definition for post- compromise secure signatures and an instantiation.
30th USENIX Security Symposium (USENIX Security 21)