1. bookVolume 2018 (2018): Issue 1 (January 2018)
Journal Details
License
Format
Journal
First Published
16 Apr 2015
Publication timeframe
4 times per year
Languages
English
access type Open Access

Improved Strongly Deniable Authenticated Key Exchanges for Secure Messaging

Published Online: 11 Jan 2018
Page range: 21 - 66
Received: 31 May 2017
Accepted: 16 Sep 2017
Journal Details
License
Format
Journal
First Published
16 Apr 2015
Publication timeframe
4 times per year
Languages
English

A deniable authenticated key exchange (DAKE) protocol establishes a secure channel without producing cryptographic evidence of communication. A DAKE offers strong deniability if transcripts provide no evidence even if long-term key material is compromised (offline deniability) and no outsider can obtain evidence even when interactively colluding with an insider (online deniability). Unfortunately, existing strongly deniable DAKEs have not been adopted by secure messaging tools due to security and deployability weaknesses.

Keywords

[1] Masayuki Abe, Miyako Ohkubo, and Koutarou Suzuki. 1-out-of-n Signatures from a Variety of Keys. In International Conference on the Theory and Application of Cryptology and Information Security, pages 415–432. Springer, 2002.Search in Google Scholar

[2] Ben Adida, Susan Hohenberger, and Ronald L Rivest. Ad-Hoc-Group Signatures from Hijacked Keypairs. In in DIMACS Workshop on Theft in E-Commerce, 2005.Search in Google Scholar

[3] Chris Alexander and Ian Goldberg. Improved User Authentication in Off-The-Record Messaging. In Workshop on Privacy in the Electronic Society, pages 41–47. ACM, 2007.Search in Google Scholar

[4] Erdem Alkim, Léo Ducas, Thomas Pöppelmann, and Peter Schwabe. Post-quantum Key Exchange—A New Hope. In 25th USENIX Security Symposium (USENIX Security 16), pages 327–343. USENIX Association, 2016.Search in Google Scholar

[5] Ittai Anati, Shay Gueron, Simon Johnson, and Vincent Scarlata. Innovative Technology for CPU Based Attestation and Sealing. In 2nd International Workshop on Hardware and Architectural Support for Security and Privacy, volume 13, 2013.Search in Google Scholar

[6] Adrian Antipa, Daniel Brown, Alfred Menezes, René Struik, and Scott Vanstone. Validation of Elliptic Curve Public Keys. In Public Key Cryptography—PKC 2003, pages 211–223. Springer, 2003.Search in Google Scholar

[7] Diego de Freitas Aranha and Conrado Porto Lopes Gouvêa. RELIC is an Efficient LIbrary for Cryptography, 2009. URL https://github.com/relic-toolkit/relic. Accessed 2017-08-11.Search in Google Scholar

[8] Gilles Van Assche. Keccak Code Package, 2013. URL https://github.com/gvanas/KeccakCodePackage. Accessed 2017-08-11.Search in Google Scholar

[9] Erinn Atwater and Urs Hengartner. Shatter: Using Threshold Cryptography to Protect Single Users with Multiple Devices. In Proceedings of the 9th ACM Conference on Security & Privacy in Wireless and Mobile Networks, pages 91–102. ACM, 2016.Search in Google Scholar

[10] Mihir Bellare and Phillip Rogaway. Entity Authentication and Key Distribution. In Advances in Cryptology–CRYPTO’93, pages 232–249. Springer, 1993.Search in Google Scholar

[11] Mihir Bellare and Phillip Rogaway. Random Oracles are Practical: A Paradigm for Designing Efficient Protocols. In Proceedings of the 1st ACM conference on Computer and communications security, pages 62–73. ACM, 1993.Search in Google Scholar

[12] Mihir Bellare, Anand Desai, David Pointcheval, and Phillip Rogaway. Relations Among Notions of Security for Public-Key Encryption Schemes. In Annual International Cryptology Conference, pages 26–45. Springer, 1998.Search in Google Scholar

[13] Mihir Bellare, Joe Kilian, and Phillip Rogaway. The Security of the Cipher Block Chaining Message Authentication Code. Journal of Computer and System Sciences, 61(3): 362–399, 2000.Search in Google Scholar

[14] Mihir Bellare, David Pointcheval, and Phillip Rogaway. Authenticated Key Exchange Secure Against Dictionary Attacks. In Advances in Cryptology–EUROCRYPT, pages 139–155. Springer, 2000.Search in Google Scholar

[15] Adam Bender, Jonathan Katz, and Ruggero Morselli. Ring Signatures: Stronger Definitions, and Constructions without Random Oracles. In Theory of Cryptography, pages 60–79. Springer, 2006.Search in Google Scholar

[16] Daniel J Bernstein. Curve25519: new Diffie-Hellman speed records. In Public Key Cryptography—PKC 2006, pages 207–228. Springer, 2006.Search in Google Scholar

[17] Daniel J Bernstein, Niels Duif, Tanja Lange, Peter Schwabe, and Bo-Yin Yang. High-speed high-security signatures. Journal of Cryptographic Engineering, 2(2): 77–89, 2012.Search in Google Scholar

[18] Dan Boneh, Craig Gentry, Ben Lynn, and Hovav Shacham. Aggregate and Verifiably Encrypted Signatures from Bilinear Maps. In International Conference on the Theory and Applications of Cryptographic Techniques, pages 416–432. Springer, 2003.Search in Google Scholar

[19] Nikita Borisov, Ian Goldberg, and Eric Brewer. Off-the-Record Communication, or, Why Not To Use PGP. In Workshop on Privacy in the Electronic Society, pages 77–84. ACM, 2004.Search in Google Scholar

[20] Colin Boyd, Wenbo Mao, and Kenneth G Paterson. Key Agreement using Statically Keyed Authenticators. In Applied Cryptography and Network Security, pages 248–262. Springer, 2004.Search in Google Scholar

[21] Emmanuel Bresson, Jacques Stern, and Michael Szydlo. Threshold Ring Signatures and Applications to Ad-hoc Groups. In Annual International Cryptology Conference, pages 465–480. Springer, 2002.Search in Google Scholar

[22] Jan Camenisch and Markus Stadler. Efficient Group Signature Schemes for Large Groups. In Annual International Cryptology Conference, pages 410–424. Springer, 1997.Search in Google Scholar

[23] Ran Canetti. Universally composable security: A new paradigm for cryptographic protocols. In Foundations of Computer Science, 2001. Proceedings. 42nd IEEE Symposium on, pages 136–145. IEEE, 2001.Search in Google Scholar

[24] Ran Canetti and Hugo Krawczyk. Security Analysis of IKE’s Signature-based Key-Exchange Protocol. In Advances in Cryptology–CRYPTO’02, pages 143–161. Springer, 2002.Search in Google Scholar

[25] Ran Canetti and Hugo Krawczyk. Universally Composable Notions of Key Exchange and Secure Channels. In International Conference on the Theory and Applications of Cryptographic Techniques, pages 337–351. Springer, 2002.Search in Google Scholar

[26] Ran Canetti, Yevgeniy Dodis, Rafael Pass, and Shabsi Walfish. Universally Composable Security with Global Setup. In Theory of Cryptography Conference, pages 61–85. Springer, 2007.Search in Google Scholar

[27] CertiVox. MIRACL Cryptographic SDK, 2012. URL https://github.com/miracl/MIRACL. Accessed 2017-08-11.Search in Google Scholar

[28] Sanjit Chatterjee, Neal Koblitz, Alfred Menezes, and Palash Sarkar. Another Look at Tightness II: Practical Issues in Cryptography. IACR Cryptology ePrint Archive, 2016:360, 2016.Search in Google Scholar

[29] Sherman SM Chow, Siu-Ming Yiu, and Lucas CK Hui. Efficient Identity Based Ring Signature. In International Conference on Applied Cryptography and Network Security, pages 499–512. Springer, 2005.Search in Google Scholar

[30] Sherman SM Chow, Matthew Franklin, and Haibin Zhang. Practical Dual-Receiver Encryption. In Cryptographers’ Track at the RSA Conference, pages 85–105. Springer, 2014.Search in Google Scholar

[31] Michele Ciampi, Giuseppe Persiano, Alessandra Scafuro, Luisa Siniscalchi, and Ivan Visconti. Improved OR Composition of Sigma-Protocols. In Theory of Cryptography Conference, pages 112–141. Springer, 2016.Search in Google Scholar

[32] Michele Ciampi, Giuseppe Persiano, Alessandra Scafuro, Luisa Siniscalchi, and Ivan Visconti. Online/Offline OR Composition of Sigma Protocols. In Annual International Conference on the Theory and Applications of Cryptographic Techniques, pages 63–92. Springer, 2016.Search in Google Scholar

[33] Craig Costello, Patrick Longa, and Michael Naehrig. Efficient algorithms for supersingular isogeny Diffie-Hellman. In Advances in Cryptology. Springer, 2016.Search in Google Scholar

[34] Ronald Cramer and Victor Shoup. Design and Analysis of Practical Public-Key Encryption Schemes Secure against Adaptive Chosen Ciphertext Attack. SIAM Journal on Computing, 33(1):167–226, 2003.10.1137/S0097539702403773Open DOISearch in Google Scholar

[35] Ronald Cramer, Ivan Damgård, and Berry Schoenmakers. Proofs of Partial Knowledge and Simplified Design of Witness Hiding Protocols. In Annual International Cryptology Conference, pages 174–187. Springer, 1994.Search in Google Scholar

[36] Mario Di Raimondo, Rosario Gennaro, and Hugo Krawczyk. Secure Off-the-Record Messaging. In Proceedings of the 2005 ACM Workshop on Privacy in the Electronic Society, pages 81–89. ACM, 2005.Search in Google Scholar

[37] Mario Di Raimondo, Rosario Gennaro, and Hugo Krawczyk. Deniable Authentication and Key Exchange. In Conference on Computer and Communications Security, pages 400–409. ACM, 2006.Search in Google Scholar

[38] Theodore Diament, Homin K Lee, Angelos D Keromytis, and Moti Yung. The Dual Receiver Cryptosystem and Its Applications. In Proceedings of the 11th ACM Conference on Computer and Communications Security, pages 330–343. ACM, 2004.Search in Google Scholar

[39] Whitfield Diffie and Martin Hellman. New Directions in Cryptography. IEEE transactions on Information Theory, 22(6):644–654, 1976.Search in Google Scholar

[40] Roger Dingledine. Tor security advisory: DH handshake flaw, 2005. URL http://archives.seul.org/or/announce/Aug-2005/msg00002.html. Accessed 2017-08-11.Search in Google Scholar

[41] Yevgeniy Dodis, Aggelos Kiayias, Antonio Nicolosi, and Victor Shoup. Anonymous Identification in Ad Hoc Groups. In International Conference on the Theory and Applications of Cryptographic Techniques, pages 609–626. Springer, 2004.Search in Google Scholar

[42] Yevgeniy Dodis, Jonathan Katz, Adam Smith, and Shabsi Walfish. Composability and On-Line Deniability of Authentication. In Theory of Cryptography, pages 146–162. Springer, 2009.Search in Google Scholar

[43] Danny Dolev, Cynthia Dwork, and Moni Naor. Non-Malleable Cryptography. In SIAM Journal on Computing, pages 542–552, 1998.Search in Google Scholar

[44] Cynthia Dwork, Moni Naor, and Amit Sahai. Concurrent Zero-Knowledge. In Symposium on Theory of Computing, pages 409–418. ACM, 1998.Search in Google Scholar

[45] Taher ElGamal. A Public Key Cryptosystem and a Signature Scheme Based on Discrete Logarithms. IEEE Transactions on Information Theory, 31(4):469–472, 1985.10.1109/TIT.1985.1057074Open DOISearch in Google Scholar

[46] Sebastian Faust, Markulf Kohlweiss, Giorgia Azzurra Marson, and Daniele Venturi. On the Non-malleability of the Fiat-Shamir Transform. In International Conference on Cryptology in India, pages 60–79. Springer, 2012.Search in Google Scholar

[47] Amos Fiat and Moni Naor. Broadcast Encryption. In Annual International Cryptology Conference, pages 480–491. Springer, 1993.Search in Google Scholar

[48] Amos Fiat and Adi Shamir. How To Prove Yourself: Practical Solutions to Identification and Signature Problems. In Advances in Cryptology–CRYPTO’86, pages 186–194. Springer, 1987.Search in Google Scholar

[49] M. Fischlin, F. Günther, B. Schmidt, and B. Warinschi. Key Confirmation in Key Exchange: A Formal Treatment and Implications for TLS 1.3. In 2016 IEEE Symposium on Security and Privacy (SP), pages 452–469, 2016.Search in Google Scholar

[50] Marc Fischlin and Sogol Mazaheri. Notions of Deniable Message Authentication. In Proceedings of the 14th ACM Workshop on Privacy in the Electronic Society, WPES ’15, pages 55–64. ACM, 2015. ISBN 978-1-4503-3820-2. 10.1145/2808138.2808143.Search in Google Scholar

[51] Marc Fischlin and Cristina Onete. Relaxed Security Notions for Signatures of Knowledge. In International Conference on Applied Cryptography and Network Security, pages 309–326. Springer, 2011.Search in Google Scholar

[52] Steven D Galbraith, Christophe Petit, Barak Shani, and Yan Bo Ti. On the security of supersingular isogeny cryptosystems. In Advances in Cryptology–ASIACRYPT, pages 63–91. Springer, 2016.Search in Google Scholar

[53] Juan A Garay, Philip MacKenzie, and Ke Yang. Strengthening Zero-Knowledge Protocols Using Signatures. In Eurocrypt, volume 2656, pages 177–194. Springer, 2003.Search in Google Scholar

[54] Rosario Gennaro, Stanisław Jarecki, Hugo Krawczyk, and Tal Rabin. Secure Distributed Key Generation for Discrete-Log Based Cryptosystems. In Advances in Cryptology–EUROCRYPT, pages 295–310. Springer, 1999.Search in Google Scholar

[55] Shafi Goldwasser, Silvio Micali, and Ronald L Rivest. A Digital Signature Scheme Secure Against Adaptive Chosen-Message Attacks. SIAM Journal on Computing, 17(2): 281–308, 1988.10.1137/0217017Open DOISearch in Google Scholar

[56] Mark Gollom. Alain Philippon phone password case: Powers of border agents and police differ, 2015. URL http://www.cbc.ca/news/1.2983841. Accessed 2017-08-11.Search in Google Scholar

[57] Loren Grush. A US-born NASA scientist was detained at the border until he unlocked his phone, 2017. URL https://www.theverge.com/2017/2/12/14583124/. Accessed 2017-08-11.Search in Google Scholar

[58] Viet Tung Hoang, Jonathan Katz, and Alex J Malozemoff. Automated Analysis and Synthesis of Authenticated Encryption Schemes. In Proceedings of the 22nd ACM SIGSAC Conference on Computer and Communications Security, pages 84–95. ACM, 2015.Search in Google Scholar

[59] Dennis Hofheinz, Jörn Müller-Quade, and Rainer Steinwandt. Initiator-Resilient Universally Composable Key Exchange. In European Symposium on Research in Computer Security, pages 61–84. Springer, 2003.Search in Google Scholar

[60] David Jao and Luca De Feo. Towards quantum-resistant cryptosystems from supersingular elliptic curve isogenies. In International Workshop on Post-Quantum Cryptography, pages 19–34. Springer, 2011.Search in Google Scholar

[61] Shaoquan Jiang and Reihaneh Safavi-Naini. An Efficient Fully Deniable Key Exchange Protocol. In Financial Cryptography and Data Security. Springer, 2008.Search in Google Scholar

[62] Jonathan Katz. Efficient and Non-Malleable Proofs of Plaintext Knowledge and Applications. In Advances in Cryptology–EUROCRYPT, pages 211–228. Springer, 2003.Search in Google Scholar

[63] John Kelsey, Shu-jen Chang, and Ray Perlner. SHA-3 Derived Functions. NIST Special Publication, 800:185, 2016.Search in Google Scholar

[64] Taechan Kim and Razvan Barbulescu. Extended Tower Number Field Sieve: A New Complexity for the Medium Prime Case. In Advances in Cryptology–CRYPTO’16, pages 543–571. Springer, 2016.Search in Google Scholar

[65] Neal Koblitz and Alfred J Menezes. The random oracle model: a twenty-year retrospective. Designs, Codes and Cryptography, 77(2-3):587–610, 2015.Search in Google Scholar

[66] Hugo Krawczyk. SKEME: A Versatile Secure Key Exchange Mechanism for Internet. In Network and Distributed System Security Symposium, pages 114–127. IEEE, 1996.Search in Google Scholar

[67] Hugo Krawczyk. SIGMA: The ‘SIGn-and-MAc’ approach to authenticated Diffie-Hellman and its use in the IKE protocols. In Annual International Cryptology Conference, pages 400–425. Springer, 2003.Search in Google Scholar

[68] Adam Langley. Intent to Implement and Ship: CECPQ1 for TLS, 2016. URL https://groups.google.com/a/chromium.org/forum/#!topic/security-dev/DS9pp2U0SAc. Accessed 2017-08-11.Search in Google Scholar

[69] Chae Hoon Lim and Pil Joong Lee. A Key Recovery Attack on Discrete Log-based Schemes Using a Prime Order Subgroup. In Advances in Cryptology—CRYPTO ’97, pages 249–263. Springer-Verlag, 1997.Search in Google Scholar

[70] Yehuda Lindell. General Composition and Universal Composability in Secure Multi-Party Computation. In Foundations of Computer Science, 2003. Proceedings. 44th Annual IEEE Symposium on, pages 394–403. IEEE, 2003.Search in Google Scholar

[71] Joseph K Liu, Victor K Wei, and Duncan S Wong. Linkable Spontaneous Anonymous Group Signature for Ad Hoc Groups. In Australasian Conference on Information Security and Privacy, pages 325–335. Springer, 2004.Search in Google Scholar

[72] Luke Rosiak. Here’s Cryptographic Proof That Donna Brazile Is Wrong, WikiLeaks Emails Are Real, 2016. URL http://dailycaller.com/2016/10/21/heres-cryptographicproof-that-donna-brazile-is-wrong-wikileaks-emails-arereal/. Accessed 2017-08-11.Search in Google Scholar

[73] Ben Lynn. The Pairing-Based Cryptography Library, 2006. URL https://crypto.stanford.edu/pbc/. Accessed 2017-08-11.Search in Google Scholar

[74] Marry Madden. Americans’ Attitudes About Privacy, Security and Surveillance, 2015. URL http://www.pewinternet.org/2015/05/20/americans-attitudes-about-privacysecurity-and-surveillance/. Accessed 2017-08-11.Search in Google Scholar

[75] Moxie Marlinspike and Trevor Perrin. The X3DH Key Agreement Protocol, 2016. URL https://whispersystems.org/docs/specifications/x3dh/. Accessed 2017-08-11.Search in Google Scholar

[76] Andrew Moon. Implementations of a fast Elliptic-curve Digital Signature Algorithm, 2012. URL https://github.com/floodyberry/ed25519-donna. Accessed 2017-08-11.Search in Google Scholar

[77] Moni Naor and Moti Yung. Public-key Cryptosystems Provably Secure against Chosen Ciphertext Attacks. In Proceedings of 22nd Annual ACM Symposium on Theory of Computing, pages 427–437. ACM, 1990.Search in Google Scholar

[78] Open Whisper Systems. Simplifying OTR deniability, 2013. URL https://www.whispersystems.org/blog/simplifyingotr-deniability. Accessed 2017-08-11.Search in Google Scholar

[79] Open Whisper Systems. Open Whisper Systems, 2013. URL https://www.whispersystems.org/. Accessed 2017-08-11.Search in Google Scholar

[80] Open Whisper Systems. Open Whisper Systems partners with WhatsApp to provide end-to-end encryption, 2014. URL https://www.whispersystems.org/blog/whatsapp/. Accessed 2017-08-11.Search in Google Scholar

[81] Open Whisper Systems. Open Whisper Systems partners with Google on end-to-end encryption for Allo, 2016. URL https://whispersystems.org/blog/allo/. Accessed 2017-08-11.Search in Google Scholar

[82] Open Whisper Systems. Facebook Messenger deploys Signal Protocol for end to end encryption, 2016. URL https://whispersystems.org/blog/facebook-messenger/. Accessed 2017-08-11.Search in Google Scholar

[83] OTR Development Team. Off-the-Record Messaging Protocol version 3, 2016. URL https://otr.cypherpunks.ca/Protocol-v3-4.1.1.html. Accessed 2017-08-11.Search in Google Scholar

[84] Trevor Perrin and Moxie Marlinspike. The Double Ratchet Algorithm, 2016. URL https://whispersystems.org/docs/specifications/doubleratchet/. Accessed 2017-08-11.Search in Google Scholar

[85] Ronald L Rivest, Adi Shamir, and Yael Tauman. How to Leak a Secret. In International Conference on the Theory and Application of Cryptology and Information Security, pages 552–565. Springer, 2001.Search in Google Scholar

[86] Phillip Rogaway. Authenticated-Encryption with Associated-Data. In Proceedings of the 9th ACM conference on Computer and communications security, pages 98–107. ACM, 2002.Search in Google Scholar

[87] Sven Schäge. TOPAS: 2-Pass Key Exchange with Full Perfect Forward Secrecy and Optimal Communication Complexity. In Proceedings of the 22nd ACM SIGSAC Conference on Computer and Communications Security, pages 1224–1235. ACM, 2015.Search in Google Scholar

[88] John M Schanck, William Whyte, and Zhenfei Zhang. Circuit-extension handshakes for Tor achieving forward secrecy in a quantum world. Proceedings on Privacy Enhancing Technologies, 2016(4):219–236, 2016.Search in Google Scholar

[89] Claus-Peter Schnorr. Efficient Signature Generation by Smart Cards. Journal of Cryptology, 4(3):161–174, 1991.Search in Google Scholar

[90] Hovav Shacham and Brent Waters. Efficient Ring Signatures without Random Oracles. In Public Key Cryptography, pages 166–180. Springer, 2007.Search in Google Scholar

[91] Gene Tsudik. Message Authentication with One-Way Hash Functions. ACM SIGCOMM Computer Communication Review, 22(5):29–38, 1992.10.1145/141809.141812Open DOISearch in Google Scholar

[92] Nik Unger. Deniable Key Exchanges for Secure Messaging. PhD thesis, University of Waterloo, 2015.Search in Google Scholar

[93] Nik Unger and Ian Goldberg. Deniable Key Exchanges for Secure Messaging. In Proceedings of the 22nd ACM SIGSAC Conference on Computer and Communications Security, pages 1211–1223. ACM, 2015.Search in Google Scholar

[94] Nik Unger, Sergej Dechand, Joseph Bonneau, Sascha Fahl, Henning Perl, Ian Goldberg, and Matthew Smith. SoK: Secure Messaging. In 2015 IEEE Symposium on Security and Privacy, pages 232–249, 2015.Search in Google Scholar

[95] Shabsi Walfish. Enhanced Security Models for Network Protocols. PhD thesis, New York University, 2008.Search in Google Scholar

[96] Shangping Wang, Rui Ma, Yaling Zhang, and Xiaofeng Wang. Ring signature scheme based on multivariate public key cryptosystems. Computers & Mathematics with Applications, 62(10):3973–3979, 2011.Search in Google Scholar

[97] Weiqiang Wen, Libin Wang, and Min Xie. One-Round Deniable Key Exchange with Perfect Forward Security. Technical Report 2014/904, Cryptology ePrint Archive, 2014. URL https://eprint.iacr.org/2014/661.Search in Google Scholar

[98] Hu Xiong, Zhiguang Qin, and Fagen Li. A Taxonomy of Ring Signature Schemes: Theory and Applications. IETE Journal of Research, 59(4):376–382, 2013.Search in Google Scholar

[99] Andrew Chi-Chih Yao and Yunlei Zhao. OAKE: A New Family of Implicitly Authenticated Diffie-Hellman Protocols. In Conference on Computer and Communications Security, pages 1113–1128. ACM, 2013.Search in Google Scholar

[100] Kazuki Yoneyama and Kazuo Ohta. Ring Signatures: Universally Composable Definitions and Constructions. Information and Media Technologies, 2(4):1038–1051, 2007.Search in Google Scholar

[101] Taek-Young Youn, Changhoon Lee, and Young-Ho Park. An efficient non-interactive deniable authentication scheme based on trapdoor commitment schemes. Computer Communications, 34(3):353–357, 2011.Search in Google Scholar

[102] Fangguo Zhang and Kwangjo Kim. ID-Based Blind Signature and Ring Signature from Pairings. In International Conference on the Theory and Application of Cryptology and Information Security, pages 533–547. Springer, 2002.Search in Google Scholar

Recommended articles from Trend MD

Plan your remote conference with Sciendo