ACM SIGSAC Conference on Computer and Communications Security (CCS)

Key Agreement for Decentralized Secure Group Messaging with Strong Security Guarantees

Matthew Weidner, Martin Kleppmann, Daniel Hugenroth, Alastair R. Beresford

Published Nov 12, 2021• 28 citations

Abstract

Secure group messaging protocols, providing end-to-end encryption for group communication, need to handle mobile devices frequently being offline, group members being added or removed, and the possibility of device compromises during long-lived chat sessions. Existing work targets a centralized network model in which all messages are routed through a single server, which is trusted to provide a consistent total order on updates to the group state. In this paper we adapt secure group messaging for decentralized networks that have no central authority. Servers may still optionally be used, but they are trusted less. We define decentralized continuous group key agreement (DCGKA), a new cryptographic primitive encompassing the core of a decentralized secure group messaging protocol; we give a practical construction of a DCGKA protocol and prove its security; and we describe how to construct a full messaging protocol from DCGKA. In the face of device compromise our protocol achieves forward secrecy and post-compromise security. We evaluate the performance of a prototype implementation, and demonstrate that our protocol has practical efficiency.

DOI: 10.1145/3460120.3484542

Related papers

CGKA-FA: Secure and Flexible Group Key Agreement with Authentication Update

Kaisei Kajita, Keita EMURA, Kazuto Ogawa +2 more

Secure messaging (SM) protocols allow users to communicate securely over an untrusted infrastructure. Alwen et al. formally defined the key agreement protocol used in secure group messaging (SGM) as continuous group key agreement (CGKA) at CRYPTO 2020. In their CGKA protocol, all of the group members have the same rights to execute algorithms, and a trusted third party is needed. On the other hand, some applications such as a broadcasting service may have an administrator in the group. When the administrator as the group manager (GM) is distinguished from other group members, i.e., in a one-to-many setting, it would be better for the GM and the other group members to have different authorities. We propose a new CGKA protocol, called CGKA with flexible authorization (CGKA-FA) by incorporating a ratcheting digital signature scheme (Cremers et al. at USENIX Security 2021) into the existing CGKA protocol and demonstrate that such a simple modification allows us to provide flexible authorization. Our proposed protocol does not need an external public key infrastructure (PKI) functionality as a trusted third party. So no third party outside the group handles confidential information of users and thus no one except group members can read messages regardless of key updates. In our CGKA-FA protocol, it is possible to set privileges of users in a group flexibly, which is highly compatible with the field of broadcasting.

Journal of Information ProcessingJan 1, 20260 citations

A Concrete Treatment of Efficient Continuous Group Key Agreement via Multi-Recipient PKEs

Keitaro Hashimoto, Shuichi Katsumata, Eamonn W. Postlethwaite +2 more

Continuous group key agreements (CGKAs) are a class of protocols that can provide strong security guarantees to secure group messaging protocols such as Signal and MLS. Protection against device compromise is provided by commit messages: at a regular rate, each group member may refresh their key material by uploading a commit message, which is then downloaded and processed by all the other members. In practice, propagating commit messages dominates the bandwidth consumption of existing CGKAs.

ACM SIGSAC Conference on Computer and Communications Security (CCS)Nov 12, 202128 citations

Continuous Group Key Agreement with Flexible Authorization and Its Applications

Kaisei Kajita, Keita Emura, Kazuto Ogawa +2 more

Secure messaging (SM) protocols allow users to communicate se-curely over an untrusted infrastructure. Alwen et al. formally de-fined the key agreement protocol used in secure group messaging (SGM) as continuous group key agreement (CGKA) at CRYPTO 2020. In their CGKA protocol, all of the group members have the same rights and a trusted third party is needed. On the other hand, some SGM applications may have a user in the group who has the role of an administrator. When the administrator as the group manager (GM) is distinguished from other group members, i.e., in a one-to-many setting, it would be better for the GM and the other group members to have different authorities. We achieve this flex-ible authorization by incorporating a ratcheting digital signature scheme (Cremers et al. at USENIX Security 2021) into the existing CGKA protocol and demonstrate that such a simple modification allows us to provide flexible authorization. In Alwen et al.'s CGKA protocol, an external public key infrastructure (PKI) functionality as a trusted third party manages the confidential information of users, and the PKI can read all messages until all users update their own keys. In contrast, the GM in our protocol has the same role as the PKI functionality in the group, so no third party outside the group handles confidential information of users and thus no one except group members can read messages regardless of key updates. Our proposed protocol is useful in the creation of new applications such as broadcasting services.

ACM International Workshop on Security and Privacy Analytics (IWSPA)Apr 6, 20234 citations

On Ends-to-Ends Encryption: Asynchronous Group Messaging with Strong Security Guarantees

Katriel Cohn-Gordon, Cas J. F. Cremers, Luke Garratt +2 more

In the past few years secure messaging has become mainstream, with over a billion active users of end-to-end encryption protocols such as Signal. The Signal Protocol provides a strong property called post-compromise security to its users. However, it turns out that many of its implementations provide, without notification, a weaker property for group messaging: an adversary who compromises a single group member can read and inject messages indefinitely. We show for the first time that post-compromise security can be achieved in realistic, asynchronous group messaging systems. We present a design called Asynchronous Ratcheting Trees (ART), which uses tree-based Diffie-Hellman key exchange to allow a group of users to derive a shared symmetric key even if no two are ever online at the same time. ART scales to groups containing thousands of members, while still providing provable security guarantees. It has seen significant interest from industry, and forms the basis for two draft IETF RFCs and a chartered working group. Our results show that strong security guarantees for group messaging are practically achievable in a modern setting.

Jul 1, 201818 citations

Analysis and Improvements of the Sender Keys Protocol for Group Messaging

Balbás, David, Collins, Daniel, Gajland, Phillip

Messaging between two parties and in the group setting has enjoyed widespread attention both in practice, and, more recently, from the cryptographic community. One of the main challenges in the area is constructing secure (end-to-end encrypted) and efficient messaging protocols for group conversations. The popular messaging applications WhatsApp and Signal utilise a protocol in which, instead of sharing a single group key, members have individual \textit{sender keys}, which are shared with all other group members. The Sender Keys protocol is claimed to offer forward security guarantees. However, despite its broad adoption in practice, it has never been studied formally in the cryptographic literature. In this paper we present the first analysis of the Sender Keys protocol along with some prospective improvements. To this end, we introduce a new cryptographic primitive, develop a game-based security model, present a security analysis in the passive and active settings, and propose several improvements to the protocol.

arXiv:2301.07045Jan 17, 20232 citations

Security and Efficiency of Secure Group Messaging Protocols

Guirec Lebrun

Secure Group Messagings are cryptographic protocols that allow safe group conversation within potentially large user groups. They are based on a dedicated type of group key exchange mechanism named Continuous Group Key Agreement (CGKA), which generates a continuously evolving group key in a safe and efficient way. Messaging Layer Security (MLS) is an IETF-standardized secure group messaging protocol which uses a protocol called TreeKEM as its CGKA.We study in this thesis the security and the efficiency of the CGKAs used within secure group messagings. Firstly, we propose a variant of TreeKEM (called Quarantined-TreeKEM) that solves a security issue related to inactive users, whose behavior prevents fundamental security properties to be fulfilled. Moreover, we improve the efficiency of TreeKEM, especially regarding its communication cost, by considering the best way to manage the tree graph used by that CGKA. Finally, we show that in the particular – yet common – use case where only a subset of users is granted the administration rights, we can design a new CGKA whose performances outperform those of regular decentralized CGKAs such as TreeKEM.This thesis thus aims to improve the state-of-the-art in secure group messaging protocols, in a context where strong security and energy sobriety are necessary features.

Dec 1, 20250 citations