Deniable Key Exchanges for Secure Messaging

ABSTRACT

In the wake of recent revelations of mass government surveillance, secure messaging protocols have come under renewed scrutiny. A widespread weakness of existing solutions is the lack of strong deniability properties that allow users to plausibly deny sending messages or participating in conversations if the security of their communications is later compromised. Deniable authenticated key exchanges (DAKEs), the cryptographic protocols responsible for providing deniability in secure messaging applications, cannot currently provide all desirable properties simultaneously. We introduce two new DAKEs with provable security and deniability properties in the Generalized Universal Composability framework. Our primary contribution is the introduction of Spawn, the first non-interactive DAKE that offers forward secrecy and achieves deniability against both offline and online judges; Spawn can be used to improve the deniability properties of the popular TextSecure secure messaging application. We also introduce an interactive dual-receiver cryptosystem that can improve the performance of the only existing interactive DAKE with competitive security properties. To encourage adoption, we implement and evaluate the performance of our schemes while relying solely on standard-model assumptions.

References

1. M. Bellare, D. Pointcheval, and P. Rogaway. Authenticated Key Exchange Secure Against Dictionary Attacks. In Advances in Cryptology--EUROCRYPT, pages 139--155. Springer, 2000.
2. A. Bender, J. Katz, and R. Morselli. Ring Signatures: Stronger Definitions, and Constructions without Random Oracles. In Theory of Cryptography, pages 60--79. Springer, 2006.
3. N. Borisov, I. Goldberg, and E. Brewer. Off-the-Record Communication, or, Why Not To Use PGP. In Workshop on Privacy in the Electronic Society, pages 77--84. ACM, 2004.
4. R. Canetti. Universally Composable Security: A New Paradigm for Cryptographic Protocols. In Foundations of Computer Science, pages 136--145. IEEE, 2001.
5. R. Canetti. Universally Composable Signature, Certification, and Authentication. In Computer Security Foundations Workshop, pages 219--233. IEEE, 2004.
6. R. Canetti, U. Feige, O. Goldreich, and M. Naor. Adaptively Secure Multi-party Computation. Technical report, Massachusetts Institute of Technology, 1996. http://theory.csail.mit.edu/ftp-data/pub/people/oded/dynamic.ps.
7. R. Canetti and H. Krawczyk. Security Analysis of IKE's Signature-Based Key-Exchange Protocol. In Advances in Cryptology--CRYPTO 2002, pages 143--161. Springer, 2002.
8. S. G. Choi, D. Dachman-Soled, T. Malkin, and H. Wee. Improved Non-Committing Encryption with Applications to Adaptively Secure Protocols. In Advances in Cryptology--ASIACRYPT 2009, pages 287--302. Springer, 2009.
9. S. S. Chow, M. Franklin, and H. Zhang. Practical Dual-Receiver Encryption. In Topics in Cryptology--CT-RSA 2014, pages 85--105. Springer, 2014.
10. R. Cramer and V. Shoup. A Practical Public Key Cryptosystem Provably Secure against Adaptive Chosen Ciphertext Attack. In Advances in Cryptology--CRYPTO'98, pages 13--25. Springer, 1998.
11. I. Damgård and J. B. Nielsen. Improved Non-Committing Encryption Schemes Based on a General Complexity Assumption. In Advances in Cryptology--CRYPTO 2000, pages 432--450. Springer, 2000.
12. Y. Dodis, J. Katz, A. Smith, and S. Walfish. Composability and On-Line Deniability of Authentication. In Theory of Cryptography, pages 146--162. Springer, 2009.
13. A. Fiat and A. Shamir. How To Prove Yourself: Practical Solutions to Identification and Signature Problems. In Advances in Cryptology--CRYPTO'86, pages 186--194. Springer, 1987.
14. Go Project. The Go Programming Language. https://golang.org/, 2009. Accessed 2015-04--13.
15. M. Hearn. Value of deniability. Mailing list discussion, https://moderncrypto.org/mail-archive/messaging/2014/001173.html, 2014. Accessed 2015-04-02.
16. H. Krawczyk. SIGMA: The 'SIGn-and-MAc' Approach to Authenticated Diffie-Hellman and its Use in the IKE protocols. In Advances in Cryptology--CRYPTO 2003, pages 400--425. Springer, 2003.
17. B. Lynn. The Pairing-Based Cryptography Library. https://crypto.stanford.edu/pbc/, 2006. Accessed 2015-04--13.
18. U. D. of Commerce / National Institute of Standards & Technology. Digital Signature Standard (DSS), 2013.
19. Open Whisper Systems. Open WhisperSystems. https://www.whispersystems.org/, 2013. Accessed 2014--11-02.
20. Open Whisper Systems. Open Whisper Systems partners with WhatsApp to provide end-to-end encryption. https://www.whispersystems.org/blog/whatsapp/, 2014. Accessed 2014--12--23.
21. T. Perrin. Axolotl Ratchet. https://github.com/trevp/axolotl/wiki, 2013. Accessed 2014--11-02.
22. C. Rackoff and D. R. Simon. Non-Interactive Zero-Knowledge Proof of Knowledge and Chosen Ciphertext Attack. In Advances in Cryptology--CRYPTO'91, pages 433--444. Springer, 1992.
23. L. Reyzin and N. Reyzin. Better than BiBa: Short One-time Signatures with Fast Signing and Verifying. In Information Security and Privacy, pages 144--153. Springer, 2002.
24. R. L. Rivest, A. Shamir, and Y. Tauman. How to Leak a Secret. In Advances in Cryptology--ASIACRYPT 2001, pages 552--565. Springer, 2001.
25. C.-P. Schnorr. Efficient Signature Generation by Smart Cards. Journal of Cryptology, 4(3):161--174, 1991.
26. H. Shacham and B. Waters. Efficient Ring Signatures without Random Oracles. In Public Key Cryptography, pages 166--180. Springer, 2007.
27. N. Unger. Deniable Key Exchanges for Secure Messaging. Master's thesis, University of Waterloo, 2015. http://hdl.handle.net/10012/9406.
28. N. Unger, S. Dechand, J. Bonneau, S. Fahl, H. Perl, I. Goldberg, and M. Smith. SoK: Secure Messaging. In Symposium on Security and Privacy. IEEE, 2015.
29. S. Walfish. Enhanced Security Models for Network Protocols. PhD thesis, New York University, 2008.
30. J. Zhang, J. Ma, and S. Moon. Universally composable one-time signature and broadcast authentication. Science China Information Sciences, 53(3):567--580, 2010.
31. H. Zhu, T. Araragi, T. Nishide, and K. Sakurai. Universally Composable Non-committing Encryptions in the Presence of Adaptive Adversaries. In e-Business and Telecommunications, pages 274--288. Springer, 2012.

Index Terms

• Security and privacy

  • Human and societal aspects of security and privacy

  • Network security

• Social and professional topics

  • Computing / technology policy

    • Privacy policies