The Complexities of Healing in Secure Group Messaging: Why Cross-Group Effects Matter

Modern secure messaging protocols can offer strong security guarantees such as Post-Compromise Security (PCS) [18], which enables participants to heal after compromise. The core PCS mechanism in protocols like Signal [34] is designed for pairwise communication, making it inefficient for large groups, while recently proposed designs for secure group mes- saging, ART [19], IETF’s MLS Draft-11 [7]/TreeKEM [11], 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.