Design of an Efficient Distributed Delivery Service for Group Key Agreement Protocols

Ludovic Paillat, Claudia-Lavinia Ignat, Davide Frey, Mathieu Turuani, Amine IsmailFps 2023 · DOI

TL;DR

This paper tackles the critical availability issue in secure group messaging protocols like MLS by proposing a fully distributed "Delivery Service." By replacing a centralized server with a peer-to-peer approach using Probabilistic Reliable Broadcast and Cascade Consensus, they enhance resilience against attacks and ensure continuous group communication.

What Problem Does This Paper Address?

Modern secure messaging applications like Signal and WhatsApp rely on end-to-end encryption (E2EE) to protect user privacy. While E2EE for two-party communication is well-established, securing group communications (n-party) has been more challenging. Early solutions were inefficient (requiring pairwise encryption) or less secure. The recent Messaging Layer Security (MLS) protocol, standardized as RFC 9420, offers an efficient and secure solution for group communication, building upon the TreeKEM protocol for group key agreement.

However, a significant vulnerability in MLS (and similar protocols) lies in its reliance on a centralized "Delivery Service." This component is responsible for distributing messages between group members. Centralization makes it a prime target for denial-of-service (DoS) attacks, which can disrupt communication, prevent key refreshes, and ultimately compromise the protocol's security guarantees, particularly post-compromise security. This paper addresses the critical need for a more robust and available Delivery Service by designing a fully distributed alternative.

Methods

The authors propose a distributed Delivery Service that leverages two key communication mechanisms:

  • Probabilistic Reliable Broadcast (PRB): For "Proposal" messages (e.g., requests to add or remove members, update keys). They specifically adopt the MURMUR protocol, which offers efficient dissemination with O(log n) complexity per process. PRB is suitable here because proposal messages don't require strict ordering.
  • Cascade Consensus Protocol: For "Commit" messages, which are crucial for finalizing group state changes and require agreement among members. This protocol is built upon a Context-Adaptive Cooperation (CAC) abstraction. CAC allows for detecting conflicts between concurrent messages and, in the absence of conflicts, acts as a reliable broadcast. If conflicts arise, it triggers a more localized "Restrained Consensus" among the conflicting parties, or a classical consensus if needed.

The authors introduce a slight modification to Cascade Consensus: they delay the acknowledgment of a commit message until the client verifies its validity and all referenced proposals are received. This delay ensures "Epoch-Content Consistency" and prevents attackers from overwhelming the system with invalid commits.

Datasets

Not discussed in the paper.

Key Insights and Ideas

  • Decentralization is Key to Availability: The core insight is that the availability of secure group communication hinges on decentralizing the message delivery mechanism. A single point of failure (the central server) is a critical vulnerability.
  • Separation of Concerns for Message Types: The paper effectively identifies that different message types (Proposals vs. Commits) have different ordering and agreement requirements. This allows for the selection of specialized, efficient communication primitives for each.
  • Controlled Delay for Robustness: Introducing a controlled delay in commit message processing is a clever way to ensure consistency and prevent DoS attacks. It forces the system to wait for all necessary components (proposals) before committing to a state change, thereby enhancing robustness.
  • Leveraging Existing Primitives: The authors build upon established protocols like MURMUR and Cascade Consensus, demonstrating a pragmatic approach to solving a complex problem by integrating and adapting existing robust building blocks.

Key Results

The paper presents a formalization of the Delivery Service's role and properties, along with a novel algorithm for a fully distributed implementation. While quantitative performance results are not detailed in this excerpt, the design aims to:

  • Enhance Availability: By removing the central server, the system becomes more resilient to DoS attacks. Compromising the group now requires compromising a significant fraction of participants (e.g., one-third for Byzantine fault tolerance), rather than just a single server.
  • Maintain Security: The distributed approach does not compromise the end-to-end encryption and security guarantees of protocols like MLS.
  • Improve Scalability: The underlying mechanisms (PRB and Cascade Consensus) are designed to scale with the number of participants.

Limitations and Future Work

The authors acknowledge the following:

  • Implementation and Performance Evaluation: They plan to implement the proposed distributed Delivery Service and conduct performance evaluations in peer-to-peer networks.
  • Formal Security Analysis: A formal security analysis of the protocol is planned.
  • Offline Group Members: The current design, like TreeKEM, primarily targets online members. Future work includes designing distributed solutions for offline communication, potentially using State-Machine-Replication and State Transfer mechanisms.
  • Integration with Access Control: They aim to integrate this distributed group-key-management component with distributed access control mechanisms like ACCURE.

Summary updated

BibTeX
@inproceedings{paillat2023design,
  author = {Ludovic Paillat and Claudia-Lavinia Ignat and Davide Frey and Mathieu Turuani and Amine Ismail},
  title = {{Design of an Efficient Distributed Delivery Service for Group Key Agreement Protocols}},
  booktitle = {Fps},
  year = {2023},
  doi = {10.1007/978-3-031-57537-2\_25},
}

Loading related content...

Figure