Analyzing Group Chat Encryption in Messaging Applications

This work focuses on analyzing group chat encryption algorithms in secure messaging applications, highlighting the utility of formal analysis in identifying and fixing real-world vulnerabilities. The speaker emphasizes that end-to-end encrypted messaging applications are used by billions, making their security crucial, especially with the emergence of standards like Messaging Layer Security (MLS).

Two-Party vs. Group Messaging Security

In a two-party setting, secure messaging relies on two primitives: symmetric encryption (providing privacy and integrity) and key agreement (deriving encryption keys). While static key agreements (e.g., Keybase) offer basic privacy and integrity, more advanced solutions like the Double Ratchet algorithm (used by Signal, WhatsApp) provide additional properties like forward secrecy and post-compromise security by frequently updating keys.

Transitioning to a group setting, privacy and integrity against outsiders alone are insufficient. Since all group members share the same symmetric key, any insider could impersonate another member. Therefore, sender authenticity against group insiders is additionally required, alongside privacy and integrity against group outsiders. This is naturally achieved using digital signatures.

Symmetric Sign Encryption (SSE)

The research formalizes group chat encryption as the Symmetric Sign Encryption (SSE) primitive, combining symmetric encryption and digital signatures. This is akin to traditional asymmetric sign encryption, with public-key encryption replaced by symmetric encryption. The security goals are meticulously defined, distinguishing between two primary threat models:

• Outsider: An attacker who might compromise individual user signing keys but does not know the group’s symmetric key. (e.g., airport security agent accessing a phone’s long-term signing key).
• Insider: A group member who knows the group’s symmetric key but not other members’ signing keys. (e.g., a malicious member who has built the app from source to extract group secrets). Most attacks discovered fall into this latter model.

Generic Compositions and Context Switching Attacks

Straightforward compositions like “sign then encrypt” or “encrypt then sign” are commonly used. However, a naive approach leads to context switching attacks. For instance, in a “sign then encrypt” scheme, if a user signs a message in one group (Group Zero) and encrypts it, a malicious insider from that group can decrypt it, obtain the message and signature, and then re-encrypt it with the symmetric key of another group (Group One) they are also a part of, effectively impersonating the original sender in Group One. The core problem is that “the same signature is being interpreted in two different encryption contexts.” To prevent this, context binding is necessary, where the signature explicitly includes contextual information like the group key identifier (a unique value defining the group’s symmetric key), nonce, and sender identifier.

Analysis Methodology

The team started with a generic SSE model informed by real-world implementations (like Keybase), analyzed open-source applications’ chat encryption algorithms, adapted them to the model, and then applied security definitions to either prove their security or find attacks. Identified model attacks were then mapped back to protocol details to ascertain real-world applicability.

Case Study: Messaging Layer Security (MLS)

MLS is an IETF standard (RFC 9420) for secure messaging. It uses a complex data structure to ensure fresh symmetric keys for each message, where an encryption key is uniquely identified by a four-tuple: (group, epoch, leaf index, generation).

MLS uses a sign-then-encrypt construction. The signature covers the message payload and associated data, including the group, epoch, and leaf index, but crucially, not the generation or nonce.

Identified Attacks:

1. Insider Replay Attack: Due to the signature’s failure to bind the generation, a malicious insider can decrypt a message and signature (encrypted with G0), then re-encrypt it with a future generation key (G1), sending it to the group. This allows indefinite impersonation of the original sender. Unlike previously known MLS attacks (causality attacks requiring server collusion), this replay attack can be performed by an insider without network control or leaving a trace.
2. Reordering Attack: This also stems from the generation not being authenticated. By intercepting ciphertexts and re-encrypting them with swapped generation values, an insider with network control can cause messages to be displayed in a different order for recipients, breaking the “in-order decryption” property (the guarantee that receivers can decrypt and display messages in their original sending order).
3. Integrity of Ciphertext Attack: The signature does not authenticate the nonce. An insider can decrypt and re-encrypt with a new nonce, breaking ciphertext integrity. However, its practical impact is dubious if the application only uses plaintext, not ciphertext structure.

Mitigation and Disclosure:

The fix involves binding the generation and nonce to the signature. This could be done by including them in the associated data (MLS protocol level) or by using an application-level monotonically increasing counter. The findings were disclosed to the MLS working group, which acknowledged the attacks and updated the specification to state that MLS “doesn’t protect against replay by insiders,” with potential updates in future versions.

Previous analyses of MLS often focused on group key agreement or had security models that would not capture these specific insider attacks, particularly due to their granular threat model for key compromises.

Case Study: Session

Session is a decentralized, privacy-focused application. It was found to be vulnerable to:

• Insider Replay Attack: Similar to MLS, due to lack of binding to the group key identifier.
• General Replay Attack: Session relies on an unauthenticated timestamp within the ciphertext to detect replay. This means anybody, even an outsider, can modify the timestamp and replay messages, though practical impact is highest when executed by an insider.

Session developers were already rolling out a new protocol version that appeared to address these issues.

Case Study: Keybase

Keybase provides end-to-end encrypted group chats using a static symmetric key that never updates.

Keybase employs an encrypt-then-sign-then-encrypt construction:

1. Encrypt message body with group key -> body ciphertext.
2. Compute hash of body ciphertext, combine with sender/group key identifiers and the symmetric key itself -> header payload.
3. Sign header payload with sender’s key.
4. Encrypt the signature under the group’s symmetric key -> header ciphertext.

Identified Challenges and Security Proofs:

• Key-Dependent Messages (KDM): The signature input (header payload) directly includes the symmetric key used for encryption. This is problematic as traditional asymmetric encryption security guarantees do not hold under KDM. The researchers had to prove the scheme secure under such KDM, specifically when derived from a hashed key, which was done in the random oracle model.
• Key Reuse: The same symmetric key is used for encrypting both the body ciphertext and the header ciphertext. This is generally discouraged due to the risk of cross-context attacks.
• Implicit Context Separation: Despite lacking explicit context separation (e.g., specific prefixes), an implicit separation was found. The body ciphertext uses MessagePack serialization, which always begins with a 17-byte fixed prefix. The header ciphertext always begins with a signature. Proving that signatures are highly unlikely to contain the MessagePack prefix allowed the scheme to be considered secure.

Key Takeaways

• Message and sender authenticity are paramount in group messaging, sometimes even surpassing privacy concerns.
• Non-cryptographic encoding can play a critical role in a scheme’s security (as seen with Keybase’s MessagePack).
• Reusing keys across different contexts is dangerous and should be avoided or carefully managed with explicit context separation.
• Combining encryption with MACs and signatures is a complex task due to the interplay of many variables.
• Formal definitions and rigorous analysis are invaluable for understanding and ensuring the security of real-world protocols.

• Tags:
• Feature
• Cryptography
• Formal Verification
• Protocol Design
• Group Messaging
• End-to-End Encryption
• MLS
• Session
• Keybase
• Security Analysis
• Attack Vectors
• Sender Authenticity