International Association
for Cryptologic Research

We analyze the composition of symmetric encryption and digital signatures in secure group messaging protocols where group members share a symmetric encryption key. In particular, we analyze the chat encryption algorithms underlying MLS, Session, Signal, and Matrix using the formalism of symmetric signcryption introduced by Jaeger, Kumar, and Stepanovs (Eurocrypt 2024). We identify theoretical attacks against each of the constructions we analyze that result from the insufficient binding between the symmetric encryption scheme and the digital signature scheme. In the case of MLS and Session, these translate into practically exploitable replay attacks by a group-insider. For Signal this leads to a forgery attack by a group-outsider with access to a user's signing key, an attack previously discovered by Balbás, Collins, and Gajland (Asiacrypt 2023). In Matrix there are mitigations in the broader ecosystem that prevent exploitation. We provide formal security theorems that each of the four constructions are secure up to these attacks.

Secure group messaging applications have been widely deployed to protect the everyday conversations of billions of users worldwide. These applications use different cryptographic algorithms to provide varying privacy and authenticity guarantees. Due to their widespread use, particularly in sensitive contexts like protests and conflicts, analyzing the security of these applications has been the focus of numerous academic works. Most of these focus on analyzing the more "novel" key agreement primitive. Due to the inherent complexities, few works attempt to rigorously analyze an application as a whole, and even fewer focus on the chat encryption primitive specifically. The latter may be attributed to the assumption that, after decades of cryptographic research, encrypting conversations (using symmetric/asymmetric primitives) is well understood, rendering chat encryption a seemingly trivial or "folklore" primitive. Despite its perceived simplicity, throughout our work across two papers, we find that some widely used group messaging applications implement chat encryption insecurely, potentially exposing them to exploitable attacks. This talk highlights the importance of analyzing the compositions of symmetric encryption and digital signatures used in several group chat encryption algorithms. Isolating chat encryption allows one to systematically identify potential attacks that result from the lack of proper "binding" between the signing and encryption components. This is reflected in our analysis of chat encryption in three widely deployed group messaging applications: Keybase, MLS, and Session. While Keybase had a good intuition for combining symmetric encryption and digital signatures, their solution was brittle; its security relied on non-cryptographic elements such as message serialization formats. MLS and Session did not implement proper binding in their compositions, exposing them to attacks where a group member can impersonate another by replaying their messages. Additionally, Session is susceptible to message re-ordering attacks by non-group members such as the platform server. Independent analysis of chat encryption allowed us to narrowly target the corresponding security goals and specify a set of conditions required for proper binding between the signing and encryption components. Developers of chat encryption algorithms need only check that these conditions are met to ensure that the security goals are achieved.

We introduce a new cryptographic primitive called symmetric signcryption, which differs from traditional signcryption because the sender and recipient share a secret key. We prove that a natural composition of symmetric encryption and signatures achieves strong notions of security against attackers that can learn and control many keys. We then identify that the core encryption algorithm of the Keybase encrypted messaging protocol can be modeled as a symmetric signcryption scheme. We prove the security of this algorithm, though our proof requires assuming non-standard, brittle security properties of the underlying primitives.

We give the first examples of public-key encryption schemes which can be proven to achieve multi-challenge, multi-user CCA security via reductions that are tight in time, advantage, and memory. Our constructions are obtained by applying the KEM-DEM paradigm to variants of Hashed ElGamal and the Fujisaki-Okamoto transformation that are augmented by adding uniformly random strings to their ciphertexts. The reductions carefully combine recent proof techniques introduced by Bhattacharyya'20 and Ghoshal-Ghosal-Jaeger-Tessaro'22. Our proofs for the augmented ECIES version of Hashed-ElGamal make use of a new computational Diffie-Hellman assumption wherein the adversary is given access to a pairing to a random group, which we believe may be of independent interest.