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

ABSTRACT

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.

References

1. Michel Abdalla, Céline Chevalier, Mark Manulis, and David Pointcheval. 2010. Flexible group key exchange with on-demand computation of subgroup keys. In AFRICACRYPT 10 (LNCS). Daniel J. Bernstein and Tanja Lange, (Eds.) Vol. 6055. Springer, Heidelberg, (May 2010), 351--368.
2. Christoph Bader, Dennis Hofheinz, Tibor Jager, Eike Kiltz, and Yong Li. 2015. Tightly-secure authenticated key exchange. In TCC 2015, Part I (LNCS). Yevgeniy Dodis and Jesper Buus Nielsen, (Eds.) Vol. 9014. Springer, Heidelberg, (Mar. 2015), 629--658.
3. Daniel J. Bernstein. 2006. Curve25519: new Diffie-Hellman speed records. In PKC 2006 (LNCS). Moti Yung, Yevgeniy Dodis, Aggelos Kiayias, and Tal Malkin, (Eds.) Vol. 3958. Springer, Heidelberg, (Apr. 2006), 207--228.
4. Dan Boneh and Alice Silverberg. 2003. Applications of multilinear forms to cryptography. In Topics in Algebraic and Noncommutative Geometry: Proceedings in Memory of Ruth Michler. Contemporary Mathematics. Vol. 324. Caroline Grant Mellesand Jean-Paul Brasseletand Gary Kennedyand Kristin Lauter and Lee McEwan, (Eds.) American Mathematical Society.
5. Dan Boneh and Mark Zhandry. 2014. Multiparty key exchange, efficient traitor tracing, and more from indistinguishability obfuscation. In CRYPTO 2014, Part I (LNCS). Juan A. Garay and Rosario Gennaro, (Eds.) Vol. 8616. Springer, Heidelberg, (Aug. 2014), 480--499.
6. Nikita Borisov, Ian Goldberg, and Eric Brewer. 2004. Off-the-record communication, or, why not to use pgp. In Proceedings of the 2004 ACM Workshop on Privacy in the Electronic Society (WPES '04). ACM.
7. Timo Brecher, Emmanuel Bresson, and Mark Manulis. 2009. Fully robust tree-Diffie-Hellman group key exchange. In CANS 09 (LNCS). Juan A. Garay, Atsuko Miyaji, and Akira Otsuka, (Eds.) Vol. 5888. Springer, Heidelberg, (Dec. 2009), 478--497.
8. Jacqueline Brendel, Marc Fischlin, Felix Günther, and Christian Janson. 2017. Prf-odh: relations, instantiations, and impossibility results. Cryptology ePrint Archive, Report 2017/517. http://eprint.iacr.org/2017/517. (2017).
9. Emmanuel Bresson, Olivier Chevassut, David Pointcheval, and Jean-Jacques Quisquater. 2001. Provably authenticated group Diffie-Hellman key exchange. In ACM CCS 01. ACM Press, (Nov. 2001), 255--264.
10. Christina Brzuska, Marc Fischlin, Bogdan Warinschi, and Stephen C. Williams. 2011. Composability of Bellare-Rogaway key exchange protocols. In ACM CCS 11. Yan Chen, George Danezis, and Vitaly Shmatikov, (Eds.) ACM Press, (Oct. 2011), 51--62.
11. Christian Cachin and Reto Strobl. 2004. Asynchronous group key exchange with failures. In Proceedings of the Twenty-third Annual ACM Symposium on Principles of Distributed Computing (PODC '04). ACM, 357--366.
12. Yi-Ruei Chen and Wen-Guey Tzeng. 2017. Group key management with efficient rekey mechanism: a semi-stateful approach for out-of-synchronized members. Computer Communications, 98.
13. Katriel Cohn-Gordon, Cas Cremers, Benjamin Dowling, Luke Garratt, and Douglas Stebila. 2016. A formal security analysis of the signal messaging protocol. Cryptology ePrint Archive, Report 2016/1013. http://eprint.iacr.org/2016/1013. (2016).
14. Katriel Cohn-Gordon, Cas Cremers, and Luke Garratt. 2016. On post-compromise security. In Computer Security Foundations Symposium (CSF), 2016 IEEE 29th. IEEE, 164--178.
15. Cas J. F. Cremers and Michele Feltz. 2012. Beyond eCK: perfect forward secrecy under actor compromise and ephemeral-key reveal. In ESORICS 2012 (LNCS). Sara Foresti, Moti Yung, and Fabio Martinelli, (Eds.) Vol. 7459. Springer, Heidelberg, (Sept. 2012), 734--751.
16. Ivan Damgård. 2007. A "proof-reading" of some issues in cryptography (invited lecture). In ICALP 2007 (LNCS). Lars Arge, Christian Cachin, Tomasz Jurdzinski, and Andrzej Tarlecki, (Eds.) Vol. 4596. Springer, Heidelberg, (July 2007), 2--11.
17. Yvo Desmedt, Tanja Lange, and Mike Burmester. 2007. Scalable authenticated tree based group key exchange for ad-hoc groups. In FC 2007 (LNCS). Sven Dietrich and Rachna Dhamija, (Eds.) Vol. 4886. Springer, Heidelberg, (Feb. 2007), 104--118.
18. eQualit.ie. 2016. (N+1)sec. (2016). https://learn.equalit.ie/wiki/Np1sec.
19. Facebook. 2017. Messenger Secret Conversations (Technical Whitepaper Version 2.0). Tech. rep. Retrieved May 2017 from https://fbnewsroomus.files.wordpress.com/2016/07/messenger-secret-conversations-technical-whitepaper.pdf.
20. Michael Farb, Yue-Hsun Lin, Tiffany Hyun-Jin Kim, Jonathan McCune, and Adrian Perrig. 2013. Safeslinger: easy-to-use and secure public-key exchange. In Proceedings of the 19th Annual International Conference on Mobile Computing and Networking (MobiCom '13). ACM, 417--428.
21. Marc Fischlin and Felix Günther. 2014. Multi-stage key exchange and the case of Google's QUIC protocol. In Proceedings of the 2014 ACM SIGSAC Conference on Computer and Communications Security. ACM, 1193--1204.
22. Ian Goldberg, Berkant Ustaoglu, Matthew Van Gundy, and Hao Chen. 2009. Multi-party off-the-record messaging. In ACM CCS 09. Ehab Al-Shaer, Somesh Jha, and Angelos D. Keromytis, (Eds.) ACM Press, (Nov. 2009), 358--368.
23. Oded Goldreich. 1997. On the foundations of modern cryptography (invited lecture). In CRYPTO'97 (LNCS). Burton S. Kaliski Jr., (Ed.) Vol. 1294. Springer, Heidelberg, (Aug. 1997), 46--74.
24. Matthew D. Green and Ian Miers. 2015. Forward secure asynchronous messaging from puncturable encryption. In 2015 IEEE Symposium on Security and Privacy. IEEE Computer Society Press, (May 2015), 305--320.
25. Antoine Joux. 2004. A one round protocol for tripartite Diffie-Hellman. Journal of Cryptology, 17, 4, (Sept. 2004), 263--276.
26. 2001. Communication-efficient group key agreement. Trusted Information: The New Decade Challenge. Springer US.
27. Yongdae Kim, Adrian Perrig, and Gene Tsudik. 2001. Communication-efficient group key agreement. In International Federation for Information Processing (IFIP SEC). Paris, France, (June 2001).
28. Yongdae Kim, Adrian Perrig, and Gene Tsudik. 2000. Simple and fault-tolerant key agreement for dynamic collaborative groups. In Proceedings of the 7th ACM Conference on Computer and Communications Security (CCS '00). ACM.
29. Yongdae Kim, Adrian Perrig, and Gene Tsudik. 2000. Simple and fault-tolerant key agreement for dynamic collaborative groups. In Proceedings of ACM Conference on Computer and Communications Security (CCS), 235--244.
30. Yongdae Kim, Adrian Perrig, and Gene Tsudik. 2004. Tree-based group key agreement. ACM Trans. Inf. Syst. Secur., (Feb. 2004).
31. N. Kobeissi, K. Bhargavan, and B. Blanchet. 2017. Automated verification for secure messaging protocols and their implementations: a symbolic and computational approach. In IEEE European Symposium on Security and Privacy (EuroS&P).
32. Brian A. LaMacchia, Kristin Lauter, and Anton Mityagin. 2007. Stronger security of authenticated key exchange. In ProvSec 2007 (LNCS). Willy Susilo, Joseph K. Liu, and Yi Mu, (Eds.) Vol. 4784. Springer, Heidelberg, (Nov. 2007), 1--16.
33. Sangwon Lee, Yongdae Kim, Kwangjo Kim, and Dae-Hyun Ryu. 2003. An efficient tree-based group key agreement using bilinear map. In ACNS 03 (LNCS). Jianying Zhou, Moti Yung, and Yongfei Han, (Eds.) Vol. 2846. Springer, Heidelberg, (Oct. 2003), 357--371.
34. Fermi Ma and Mark Zhandry. 2017. Encryptor combiners: a unified approach to multiparty nike, (h)ibe, and broadcast encryption. Cryptology ePrint Archive, Report 2017/152. http://eprint.iacr.org/2017/152. (2017).
35. Moxie Marlinspike. 2013. Forward secrecy for asynchronous messages. Blog. (Aug. 22, 2013). Retrieved May 2017 from https://whispersystems.org/blog/asynchronous-security/.
36. Moxie Marlinspike. 2016. Signal protocol documentation. (2016). Retrieved May 2017 from https://whispersystems.org/docs/.
37. Moxie Marlinspike. 2016. The x3dh key agreement protocol. Trevor Perrin, (Ed.) (Nov. 2016). Retrieved Nov. 2017 from https://signal.org/docs/specifications/x3dh/x3dh.pdf .
38. Ghita Mezzour, Ahren Studer, Michael Farb, Jason Lee, Jonathan McCune, Hsu-Chun Hsiao, and Adrian Perrig. 2010. Ho-Po Key: Leveraging Physical Constraints on Human Motion to Authentically Exchange Information in a Group. Tech. rep. Carnegie Mellon University, (Dec. 2010).
39. Jon Millican. 2018. ART prototype implementation. (2018). https://github.com/facebookresearch/asynchronousratchetingtree.
40. MLS Working Group Chairs. 2018. Messaging layer security working group. https://mlswg.github.io.
41. Open Whisper Systems. 2014. Libsignal-service-java. (2014). https://github.com/signalapp/libsignal-service-java/blob/c8d7c3c00445a81b81e0a7305151cda4534ba299/java/src/main/java/org/whispersystems/signalservice/api/SignalServiceMessageSender.java#L497.
42. Adrian Perrig. 1999. Efficient collaborative key management protocols for secure autonomous group communication. In Proceedings of International Workshop on Cryptographic Techniques and E-Commerce (CrypTEC). (July 1999), 192--202.
43. Adrian Perrig, Dawn Song, and Doug Tygar. 2001. ELK, a new protocol for efficient large-group key distribution. In Proceedings of IEEE Symposium on Security and Privacy. (May 2001).
44. 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 European Symposium on Security and Privacy, EuroS&P 2018, 415--429.
45. Benedikt Schmidt, Simon Meier, Cas Cremers, and David A. Basin. 2012. Automated analysis of diffie-hellman protocols and advanced security properties. In 25th IEEE Computer Security Foundations Symposium, CSF 2012, Cambridge, MA, USA, June 25--27, 2012, 78--94.
46. Victor Shoup. 2004. Sequences of games: a tool for taming complexity in security proofs. IACR Cryptology EPrint Archive, 2004, 332.
47. Dmitry Skiba. 2008. Trevorbernard/curve25519-java. GitHub repository. (Feb. 23, 2008). Retrieved May 2017 from https://github.com/trevorbernard/curve25519-java.
48. Mark Slee, Aditya Agarwal, and Marc Kwiatkowski. 2007. Thrift: Scalable Cross-Language Services Implementation. Tech. rep. Retrieved Nov. 2017 from https://thrift.apache.org/static/files/thrift-20070401.pdf .
49. 1990. A secure audio teleconference system. Advances in Cryptology - CRYPTO'88: Proceedings. Springer New York.
50. Michael Steiner, Gene Tsudik, and Michael Waidner. 2000. Key agreement in dynamic peer groups. IEEE Transactions on Parallel and Distributed Systems, 11, 8, (Aug. 2000), 769--780.
51. The Guardian. 2017. Contact the guardian securely. (2017). Retrieved June 2017 from https://gu.com/tip-us-off.
52. D. Wallner, E. Harder, and R. Agee. 1999. Key management for multicast: issues and architectures. RFC. United States, (1999).
53. WhatsApp. 2016. WhatsApp Encryption Overview. Tech. rep. Retrieved July 2016 from https://www.whatsapp.com/security/WhatsApp-Security-Whitepaper.pdf.
54. Chung Kei Wong, Mohamed Gouda, and Simon S. Lam. 2000. Secure group communications using key graphs. IEEE/ACM Transactions on Networking, 8, 1, (Feb. 2000), 16--30.
55. Zheng Yang, Chao Liu, Wanping Liu, Daigu Zhang, and Song Luo. 2017. A new strong security model for stateful authenticated group key exchange. International Journal of Information Security, 1--18.

Index Terms

• Information systems

  • World Wide Web

    • Web applications

      • Internet communications tools

• Networks

  • Network properties

    • Network security

      • Mobile and wireless security

      • Security protocols

  • Network protocols

    • Network protocol design

    • Protocol correctness

• Security and privacy

  • Formal methods and theory of security

    • Formal security models

  • Network security

    • Security protocols

  • Software and application security

    • Social network security and privacy