research-article

Open access

Key Agreement for Decentralized Secure Group Messaging with Strong Security Guarantees

Authors:

Matthew Weidner,

Martin Kleppmann,

Daniel Hugenroth, and

Alastair R. BeresfordAuthors Info & Claims

CCS '21: Proceedings of the 2021 ACM SIGSAC Conference on Computer and Communications Security

November 2021

Pages 2024 - 2045

https://doi.org/10.1145/3460120.3484542

Published: 13 November 2021 Publication History

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.

References

[1]

Martin R. Albrecht, Jorge Blasco, Rikke Bjerg Jensen, and Lenka Mareková. 2021. Mesh Messaging in Large-Scale Protests: Breaking Bridgefy. In Cryptographers' Track at the RSA Conference. Springer, 375--398. https://doi.org/10.1007/978--3-030--75539--3_16

[2]

Joël Alwen, Sandro Coretti, and Yevgeniy Dodis. 2019. The Double Ratchet: Security Notions, Proofs, and Modularization for the Signal Protocol. In Advances in Cryptology -- EUROCRYPT 2019 . Springer, 129--158. Full version: https://eprint.iacr.org/2018/1037.

[3]

Joël Alwen, Sandro Coretti, Yevgeniy Dodis, and Yiannis Tselekounis. 2020. Security Analysis and Improvements for the IETF MLS Standard for Group Messaging. In Advances in Cryptology -- CRYPTO 2020, Daniele Micciancio and Thomas Ristenpart (Eds.). Springer International Publishing, Cham, 248--277. Full version: https://eprint.iacr.org/2019/1189.

Digital Library

[4]

Jacob Aron and Aviva Rutkin. 2017. Hong Kong protesters use a mesh network to organise. New Scientist (Sept. 2017). https://www.newscientist.com/article/dn26285-hong-kong-protesters-use-a-mesh-network-to-organise/ Archived at https://perma.cc/VKH7-KE9K.

[5]

Richard Barnes, Benjamin Beurdouche, Jon Millican, Emad Omara, Katriel Cohn-Gordon, and Raphael Robert. 2020. The Messaging Layer Security (MLS) Protocol. Internet-Draft draft-ietf-mls-protocol-11. Internet Engineering Task Force. https://datatracker.ietf.org/doc/html/draft-ietf-mls-protocol-11 Work in Progress.

[6]

Mihir Bellare, Asha Camper Singh, Joseph Jaeger, Maya Nyayapati, and Igors Stepanovs. 2017. Ratcheted Encryption and Key Exchange: The Security of Messaging. In Advances in Cryptology -- CRYPTO 2017. Springer, 619--650. Full version: https://eprint.iacr.org/2016/1028.

[7]

Daniel J Bernstein. 2006. Curve25519: New Diffie-Hellman Speed Records. In 9th International Conference on Theory and Practice in Public-Key Cryptography (PKC). Springer, 207--228. https://doi.org/10.1007/11745853_14

Digital Library

[8]

Karthikeyan Bhargavan, Richard Barnes, and Eric Rescorla. 2018. TreeKEM: Asynchronous Decentralized Key Management for Large Dynamic Groups. Messaging Layer Security mailing list. https://mailarchive.ietf.org/arch/msg/mls/v1CY0jFAOVOHokB4DtNqS__tX1o

[9]

Alexander Bienstock, Yevgeniy Dodis, and Paul Rösler. 2020. On the Price of Concurrency in Group Ratcheting Protocols. In Theory of Cryptography, Rafael Pass and Krzysztof Pietrzak (Eds.). Springer International Publishing, Cham, 198--228. Full version: https://eprint.iacr.org/2020/1171.

Digital Library

[10]

Simon Blöchinger and Richard von Seck. 2021. Survey of Mesh Networking Messengers . Technical Report. TU Munich Seminar IITM. https://doi.org/10.2313/NET-2021-05--1_01

[11]

Bernadette Charron-Bost. 1991. Concerning the size of logical clocks in distributed systems. Inf. Proc. Letters, Vol. 39, 1 (July 1991), 11--16. https://doi.org/10.1016/0020-0190(91)90055-M

Digital Library

[12]

Katriel Cohn-Gordon. 2018. Trivial DoS by a malicious client. https://github.com/mlswg/mls-protocol/issues/21

[13]

K. Cohn-Gordon, C. Cremers, B. Dowling, L. Garratt, and D. Stebila. 2017. A Formal Security Analysis of the Signal Messaging Protocol. In 2017 IEEE European Symposium on Security and Privacy (EuroS&P). 451--466. https://doi.org/10.1109/EuroSP.2017.27

[14]

Katriel Cohn-Gordon, Cas Cremers, and Luke Garratt. 2016. On Post-Compromise Security. In 29th IEEE Computer Security Foundations Symposium (CSF). IEEE, 164--178. https://doi.org/10.1109/CSF.2016.19

[15]

Cas Cremers, Britta Hale, and Konrad Kohbrok. 2019. Efficient Post-Compromise Security Beyond One Group. Cryptology ePrint Archive, Report 2019/477. https://eprint.iacr.org/2019/477.

[16]

Roger Dingledine, Nick Mathewson, and Paul Syverson. 2004. Tor: The Second-Generation Onion Router . Technical Report ADA465464. Naval Research Laboratory, Washington DC.

[17]

F. Betül Durak and Serge Vaudenay. 2019. Bidirectional Asynchronous Ratcheted Key Agreement with Linear Complexity. In Advances in Information and Computer Security. Springer, 343--362. Full version: https://eprint.iacr.org/2018/889.

[18]

C. J. Fidge. 1988. Timestamps in message-passing systems that preserve the partial ordering. Proceedings of the 11th Australian Computer Science Conference, Vol. 10, 1 (1988), 56--66.

[19]

Seth Gilbert and Nancy A Lynch. 2002. Brewer's conjecture and the feasibility of consistent, available, partition-tolerant web services. ACM SIGACT News, Vol. 33, 2 (June 2002), 51--59. https://doi.org/10.1145/564585.564601

Digital Library

[20]

Mojtaba Hosseini, Dewan Tanvir Ahmed, Shervin Shirmohammadi, and Nicolas D. Georganas. 2007. A survey of application-layer multicast protocols. IEEE Communications Surveys & Tutorials, Vol. 9, 3 (Sept. 2007), 58--74. https://doi.org/10.1109/comst.2007.4317616

Digital Library

[21]

Florian Jacob, Luca Becker, Jan Grashöfer, and Hannes Hartenstein. 2020. Matrix Decomposition: Analysis of an Access Control Approach on Transaction-Based DAGs without Finality. In Proceedings of the 25th ACM Symposium on Access Control Models and Technologies (Barcelona, Spain) (SACMAT '20). Association for Computing Machinery, New York, NY, USA, 81--92. https://doi.org/10.1145/3381991.3395399

Digital Library

[22]

Joseph Jaeger and Igors Stepanovs. 2018. Optimal Channel Security Against Fine-Grained State Compromise: The Safety of Messaging. In CRYPTO 2018. Springer, 33--62. Full version: https://eprint.iacr.org/2018/553.

[23]

Daniel Jost, Ueli Maurer, and Marta Mularczyk. 2019. Efficient Ratcheting: Almost-Optimal Guarantees for Secure Messaging. In EUROCRYPT 2019 . 159--188. Full version: https://eprint.iacr.org/2018/954.pdf.

[24]

Martin Kleppmann and Heidi Howard. 2020. Byzantine Eventual Consistency and the Fundamental Limits of Peer-to-Peer Databases. CoRR, Vol. abs/2012.00472 (2020). arxiv: 2012.00472 https://arxiv.org/abs/2012.00472

[25]

Hugo Krawczyk. 2010. Cryptographic Extraction and Key Derivation: The HKDF Scheme. In CRYPTO 2010 . Springer, 631--648. https://doi.org/10.1007/978--3--642--14623--7_34

[26]

Hugo Krawczyk and Pasi Eronen. 2010. HMAC-based Extract-and-Expand Key Derivation Function (HKDF) . RFC 5869. https://doi.org/10.17487/RFC5869

Digital Library

[27]

João Leitão, José Pereira, and Luís Rodrigues. 2009. Gossip-Based Broadcast. In Handbook of Peer-to-Peer Networking . Springer, 831--860. https://doi.org/10.1007/978-0--387-09751-0_29

[28]

Moxie Marlinspike and Trevor Perrin. 2016. The X3DH Key Agreement Protocol . Technical Report Revision 1. https://www.signal.org/docs/specifications/x3dh/ Archived at https://perma.cc/633M-J2WM.

[29]

Matrix.org Foundation. 2019. End-to-End Encryption implementation guide. https://matrix.org/docs/guides/end-to-end-encryption-implementation-guide Archived at https://perma.cc/75RC-HS9B.

[30]

Friedemann Mattern. 1989. Virtual Time and Global States of Distributed Systems. In Parallel & Distributed Algorithms . North-Holland, 215--226.

[31]

Emad Omara, Benjamin Beurdouche, Eric Rescorla, Srinivas Inguva, Albert Kwon, and Alan Duric. 2020. The Messaging Layer Security (MLS) Architecture. Internet-Draft draft-ietf-mls-architecture-05. Internet Engineering Task Force. https://datatracker.ietf.org/doc/html/draft-ietf-mls-architecture-05 Work in Progress.

[32]

Trevor Perrin and Moxie Marlinspike. 2016. The Double Ratchet Algorithm . Technical Report Revision 1. https://signal.org/docs/specifications/doubleratchet/ Archived at https://perma.cc/AJL9-MBSB.

[33]

Ania M Piotrowska, Jamie Hayes, Tariq Elahi, Sebastian Meiser, and George Danezis. 2017. The Loopix Anonymity System. In USENIX Security Symposium .

[34]

Bertram Poettering and Paul Rösler. 2018. Towards Bidirectional Ratcheted Key Exchange. In CRYPTO 2018. Springer, 3--32. https://doi.org/10.1007/978--3--319--96884--1_1 Full version: https://eprint.iacr.org/2018/296.

[35]

Nuno M. Preguicc a, Carlos Baquero, and Marc Shapiro. 2018. Conflict-free Replicated Data Types (CRDTs). CoRR, Vol. abs/1805.06358 (2018). arxiv: 1805.06358 http://arxiv.org/abs/1805.06358

[36]

Paul Rösler, Christian Mainka, and Jörg Schwenk. 2018. More is Less: On the End-to-End Security of Group Chats in Signal, WhatsApp, and Threema. In 2018 IEEE EuroS&P. 415--429. https://doi.org/10.1109/EuroSP.2018.00036

[37]

Marc Shapiro, Nuno Preguic ca, Carlos Baquero, and Marek Zawirski. 2011. Conflict-Free Replicated Data Types. In 13th International Symposium on Stabilization, Safety, and Security of Distributed Systems. 386--400. https://doi.org/10.1007/978--3--642--24550--3_29

[38]

Lokman Tsui. 2015. The coming colonization of Hong Kong cyberspace: government responses to the use of new technologies by the umbrella movement. Chinese J. Comm, Vol. 8, 4 (2015), 1--9. https://doi.org/10.1080/17544750.2015.1058834

[39]

Nik Unger, Sergej Dechand, Joseph Bonneau, Sascha Fahl, Henning Perl, Ian Goldberg, and Matthew Smith. 2015. SoK: Secure Messaging. In 2015 IEEE Symposium on Security and Privacy (S&P). IEEE, 232--249. https://doi.org/10.1109/SP.2015.22

Digital Library

[40]

Richard van der Hoff. 2019. Megolm group ratchet. https://gitlab.matrix.org/matrix-org/olm/-/blob/efd17631b16d1271a029e0af8f7d8e5ae795cc5d/docs/megolm.md

[41]

Matthew Weidner. 2019. Group Messaging for Secure Asynchronous Collaboration . Master's thesis. University of Cambridge, Cambridge, UK. http://mattweidner.com/acs-dissertation.pdf Archived at https://perma.cc/XA8S-BHFN.

[42]

Matthew Weidner, Martin Kleppmann, Daniel Hugenroth, and Alastair R. Beresford. 2020. Key Agreement for Decentralized Secure Group Messaging with Strong Security Guarantees. Cryptology ePrint Archive, Report 2020/1281. https://eprint.iacr.org/2020/1281.

[43]

WhatsApp. 2017. WhatsApp Encryption Overview. https://www.whatsapp.com/security/WhatsApp-Security-Whitepaper.pdf Archived at https://perma.cc/QD7M-GPG5.

Cited By

Abdmeziem MAhmed Nacer ADeroues N(2024)Group key management in the Internet of ThingsFuture Generation Computer Systems10.1016/j.future.2023.10.023152:C(273-287)Online publication date: 4-Mar-2024
https://dl.acm.org/doi/10.1016/j.future.2023.10.023
Balbás DCollins DVaudenay SCalandrino JTroncoso C(2023)Cryptographic administration for secure group messagingProceedings of the 32nd USENIX Conference on Security Symposium10.5555/3620237.3620308(1253-1270)Online publication date: 9-Aug-2023
https://dl.acm.org/doi/10.5555/3620237.3620308
Muscariello LPapalini MRoques OSardara MTran Van A(2023)Securing Scalable Real-time Multiparty Communications with Hybrid Information-centric NetworkingACM Transactions on Internet Technology10.1145/359358523:2(1-20)Online publication date: 19-May-2023
https://dl.acm.org/doi/10.1145/3593585
Show More Cited By

Index Terms

Key Agreement for Decentralized Secure Group Messaging with Strong Security Guarantees
1. Security and privacy
  1. Cryptography
    1. Key management
  2. Systems security
    1. Distributed systems security

Recommendations

How to Hide MetaData in MLS-Like Secure Group Messaging: Simple, Modular, and Post-Quantum
CCS '22: Proceedings of the 2022 ACM SIGSAC Conference on Computer and Communications Security

Secure group messaging (SGM) protocols allow large groups of users to communicate in a secure and asynchronous manner. In recent years, continuous group key agreements (CGKAs) have provided a powerful abstraction to reason on the security properties we ...
Read More
Haiku: Efficient Authenticated Key Agreement with Strong Security Guarantees for IoT
ICDCN '21: Proceedings of the 22nd International Conference on Distributed Computing and Networking

IoT devices often gather critical information that needs to be communicated in a secure manner. Authentication and secure communication in an IoT environment can be difficult because of constraints, in computing power, memory, energy and network ...
Read More
Clone Detection in Secure Messaging: Improving Post-Compromise Security in Practice
CCS '20: Proceedings of the 2020 ACM SIGSAC Conference on Computer and Communications Security

We investigate whether modern messaging apps achieve the strong post-compromise security guarantees offered by their underlying protocols. In particular, we perform a black-box experiment in which a user becomes the victim of a clone attack; in this ...
Read More

Comments

Information & Contributors

Information

Published In

cover image ACM Conferences

CCS '21: Proceedings of the 2021 ACM SIGSAC Conference on Computer and Communications Security

November 2021

3558 pages

ISBN:9781450384544

DOI:10.1145/3460120

General Chairs:
Yongdae Kim
KAIST, Republic of Korea
,
Jong Kim
POSTECH, Republic of Korea
,
Program Chairs:
Giovanni Vigna
University of California, Santa Barbara / VMware, USA
,
Elaine Shi
Carnegie Mellon University, USA

Copyright © 2021 Owner/Author.

This work is licensed under a Creative Commons Attribution International 4.0 License.

Sponsors

SIGSAC: ACM Special Interest Group on Security, Audit, and Control

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 13 November 2021

Check for updates

Author Tags

Qualifiers

Research-article

Funding Sources

EPSRC

Conference

CCS '21

Sponsor:

SIGSAC

CCS '21: 2021 ACM SIGSAC Conference on Computer and Communications Security

November 15 - 19, 2021

Virtual Event, Republic of Korea

Acceptance Rates

Overall Acceptance Rate 1,261 of 6,999 submissions, 18%

Upcoming Conference

CCS '24

Sponsor:
sigsac

ACM SIGSAC Conference on Computer and Communications Security

October 14 - 18, 2024

Salt Lake City , UT , USA

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

9
Total Citations
View Citations
1,678
Total Downloads

Downloads (Last 12 months)407
Downloads (Last 6 weeks)32

Other Metrics

View Author Metrics

Citations

Cited By

Abdmeziem MAhmed Nacer ADeroues N(2024)Group key management in the Internet of ThingsFuture Generation Computer Systems10.1016/j.future.2023.10.023152:C(273-287)Online publication date: 4-Mar-2024
https://dl.acm.org/doi/10.1016/j.future.2023.10.023
Balbás DCollins DVaudenay SCalandrino JTroncoso C(2023)Cryptographic administration for secure group messagingProceedings of the 32nd USENIX Conference on Security Symposium10.5555/3620237.3620308(1253-1270)Online publication date: 9-Aug-2023
https://dl.acm.org/doi/10.5555/3620237.3620308
Muscariello LPapalini MRoques OSardara MTran Van A(2023)Securing Scalable Real-time Multiparty Communications with Hybrid Information-centric NetworkingACM Transactions on Internet Technology10.1145/359358523:2(1-20)Online publication date: 19-May-2023
https://dl.acm.org/doi/10.1145/3593585
Rault PIgnat CPerrin O(2023)Access Control based on CRDTs for Collaborative Distributed Applications2023 IEEE 22nd International Conference on Trust, Security and Privacy in Computing and Communications (TrustCom)10.1109/TrustCom60117.2023.00187(1369-1376)Online publication date: 1-Nov-2023
https://doi.org/10.1109/TrustCom60117.2023.00187
Gafni RAviv IHaim D(2023)Multi-Party Secured Collaboration Architecture from Cloud to EdgeJournal of Computer Information Systems10.1080/08874417.2023.2248921(1-12)Online publication date: 31-Aug-2023
https://doi.org/10.1080/08874417.2023.2248921
Balbás DCollins DGajland P(2023)WhatsUpp with Sender Keys? Analysis, Improvements and Security ProofsAdvances in Cryptology – ASIACRYPT 202310.1007/978-981-99-8733-7_10(307-341)Online publication date: 4-Dec-2023
https://dl.acm.org/doi/10.1007/978-981-99-8733-7_10
Auerbach BCueto Noval MPascual-Perez GPietrzak K(2023)On the Cost of Post-compromise Security in Concurrent Continuous Group-Key AgreementTheory of Cryptography10.1007/978-3-031-48621-0_10(271-300)Online publication date: 29-Nov-2023
https://dl.acm.org/doi/10.1007/978-3-031-48621-0_10
Hashimoto KKatsumata SPrest TYin HStavrou ACremers CShi E(2022)How to Hide MetaData in MLS-Like Secure Group MessagingProceedings of the 2022 ACM SIGSAC Conference on Computer and Communications Security10.1145/3548606.3560679(1399-1412)Online publication date: 7-Nov-2022
https://dl.acm.org/doi/10.1145/3548606.3560679
Bienstock ADodis YGarg SGrogan GHajiabadi MRösler P(2022)On the Worst-Case Inefficiency of CGKATheory of Cryptography10.1007/978-3-031-22365-5_8(213-243)Online publication date: 7-Nov-2022
https://dl.acm.org/doi/10.1007/978-3-031-22365-5_8

View Options

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Get Access

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

Media

Figures

Other

Tables

View Table of Contents