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

Circuit-extension handshakes for Tor achieving forward secrecy in a quantum world

Published Online: 14 Jul 2016
Page range: 219 - 236
Received: 29 Feb 2016
Accepted: 02 Jun 2016
Journal Details
License
Format
Journal
First Published
16 Apr 2015
Publication timeframe
4 times per year
Languages
English

We propose a circuit extension handshake for Tor that is forward secure against adversaries who gain quantum computing capabilities after session negotiation. In doing so, we refine the notion of an authenticated and confidential channel establishment (ACCE) protocol and define pre-quantum, transitional, and post-quantum ACCE security. These new definitions reflect the types of adversaries that a protocol might be designed to resist. We prove that, with some small modifications, the currently deployed Tor circuit extension handshake, ntor, provides pre-quantum ACCE security. We then prove that our new protocol, when instantiated with a post-quantum key encapsulation mechanism, achieves the stronger notion of transitional ACCE security. Finally, we instantiate our protocol with NTRU-Encrypt and provide a performance comparison between ntor, our proposal, and the recent design of Ghosh and Kate.

[1] Michel Abdalla, Mihir Bellare, and Phillip Rogaway. The oracle Diffie-Hellman assumptions and an analysis of DHIES. In David Naccache, editor, Topics in Cryptology - CT-RSA 2001: The Cryptographers’ Track at RSA Conference 2001 San Francisco, CA, USA, April 8-12, 2001 Proceedings, volume 2020 of Lecture Notes in Computer Science, pages 143-158. Springer, 2001.Search in Google Scholar

[2] Florian Bergsma, Benjamin Dowling, Florian Kohlar, Jörg Schwenk, and Douglas Stebila. Multi-ciphersuite security of the secure shell (SSH) protocol. In Proceedings of the 2014 ACM SIGSAC Conference on Computer and Communications Security, CCS ’14, pages 369-381, New York, NY, USA, 2014. ACM.Search in Google Scholar

[3] Daniel J. Bernstein, Daira Hopwood, Andreas Hülsing, Tanja Lange, Ruben Niederhagen, Louiza Papachristodoulou, Michael Schneider, Peter Schwabe, and Zooko Wilcox- O’Hearn. SPHINCS: Practical stateless hash-based signatures. In Elisabeth Oswald and Marc Fischlin, editors, Advances in Cryptology - EUROCRYPT 2015: 34th Annual International Conference on the Theory and Applications of Cryptographic Techniques, Sofia, Bulgaria, April 26-30, 2015, Proceedings, Part I, volume 9056 of Lecture Notes in Computer Science, pages 368-397. Springer, 2015.Search in Google Scholar

[4] Daniel J. Bernstein, Tanja Lange, and Peter Schwabe. NaCL: Networking and cryptography library. http://nacl.cr.yp.to/, 2011.Search in Google Scholar

[5] Dan Boneh, Özgür Dagdelen, Marc Fischlin, Anja Lehmann, Christian Schaffner, and Mark Zhandry. Random oracles in a quantum world. In Dong Hoon Lee and Xiaoyun Wang, editors, Advances in Cryptology - ASIACRYPT 2011: 17th International Conference on the Theory and Application of Cryptology and Information Security, Seoul, South Korea, December 4-8, 2011. Proceedings, volume 7073 of Lecture Notes in Computer Science, pages 41-69. Springer, 2011.Search in Google Scholar

[6] Dan Boneh and Richard J. Lipton. Quantum cryptanalysis of hidden linear functions. In Don Coppersmith, editor, Advances in Cryptology 1981 - 1997: Electronic Proceedings and Index of the CRYPTO and EUROCRYPT Conferences 1981 - 1997, volume 1440 of Lecture Notes in Computer Science, chapter CRYPTO ’95, pages 424-437. Springer, 2001.Search in Google Scholar

[7] Joppe W. Bos, Craig Costello, Michael Naehrig, and Douglas Stebila. Post-quantum key exchange for the TLS protocol from the ring learning with errors problem. In 2015 IEEE Symposium on Security and Privacy, SP 2015, San Jose, CA, USA, May 17-21, 2015, pages 553-570, 2015.Search in Google Scholar

[8] Johannes Buchmann, Erik Dahmen, and Andreas Hülsing. XMSS - A practical forward secure signature scheme based on minimal security assumptions. In Bo-Yin Yang, editor, Post-Quantum Cryptography: 4th International Workshop, PQCrypto 2011, Taipei, Taiwan, November 29 - December 2, 2011. Proceedings, volume 7071 of Lecture Notes in Computer Science, pages 117-129. Springer, 2011.Search in Google Scholar

[9] Lily Chen, Stephen Jordan, Yi-Kai Liu, Dustin Moody, Rene Peralta, Ray Perlner, and Daniel Smith-Tone. Report on post-quantum cryptography. NIST Internal Report 8105. http://dx.doi.org/10.6028/NIST.IR.8105, February 2016.Search in Google Scholar

[10] NSA Information Assurance Directorate. Commercial national security algorithm suite. https://www.iad.gov/iad/programs/iad-initiatives/cnsa-suite.cfm, August 2015.Search in Google Scholar

[11] Yevgeniy Dodis, Rosario Gennaro, Johan Håstad, Hugo Krawczyk, and Tal Rabin. Randomness extraction and key derivation using the CBC, cascade and HMAC modes. In Matt Franklin, editor, Advances in Cryptology - CRYPTO 2004, volume 3152 of Lecture Notes in Computer Science, pages 494-510. Springer, 2004.Search in Google Scholar

[12] Satrajit Ghosh and Aniket Kate. Post-quantum forwardsecure onion routing. In Tal Malkin, Vladimir Kolesnikov, Bishop Allison Lewko, and Michalis Polychronakis, editors, Applied Cryptography and Network Security: 13th International Conference, ACNS 2015, New York, NY, USA, June 2-5, 2015, Revised Selected Papers, volume 9092 of Lecture Notes in Computer Science, pages 263-286. Springer, 2015.Search in Google Scholar

[13] Ian Goldberg, Douglas Stebila, and Berkant Ustaoglu. Anonymity and one-way authentication in key exchange protocols. Designs, Codes and Cryptography, 67(2):245-269, 2013.Search in Google Scholar

[14] Jeff Hoffstein, Jill Pipher, John M. Schanck, Joseph H. Silverman, William Whyte, and Zhenfei Zhang. Choosing parameters for NTRUEncrypt. Cryptology ePrint Archive, Report 2015/708, 2015. http://eprint.iacr.org/2015/708.Search in Google Scholar

[15] Jeffrey Hoffstein, Jill Pipher, and Joseph H. Silverman. United States Patent: 6081597 - Public key cryptosystem method and apparatus. https://www.google.com/patents/US6081597, June 2000.Search in Google Scholar

[16] Jeffrey Hoffstein and Joseph H. Silverman. United States Patent: 7031468 - Speed enhanced cryptographic method and apparatus. https://www.google.com/patents/US7031468, April 2006.Search in Google Scholar

[17] Security Innovation. libntruencrypt: NTRUEncrypt reference implementation. https://github.com/NTRUOpenSourceProject/ntru-crypto, 2015. Version 1.0.1.Search in Google Scholar

[18] Tibor Jager, Florian Kohlar, Sven Schäge, and Jörg Schwenk. On the security of TLS-DHE in the standard model. In Reihaneh Safavi-Naini and Ran Canetti, editors, Advances in Cryptology - CRYPTO 2012, volume 7417 of Lecture Notes in Computer Science, pages 273-293. Springer, 2012.Search in Google Scholar

[19] Florian Kohlar, Sven Schäge, and Jörg Schwenk. On the security of TLS-DH and TLS-RSA in the standard model. Cryptology ePrint Archive, Report 2013/367, 2013. http://eprint.iacr.org/2013/367.Search in Google Scholar

[20] Hugo Krawczyk. Cryptographic extraction and key derivation: The HKDF scheme. In Tal Rabin, editor, Advances in Cryptology - CRYPTO 2010: 30th Annual Cryptology Conference, Santa Barbara, CA, USA, August 15-19, 2010. Proceedings, volume 6223 of Lecture Notes in Computer Science, pages 631-648. Springer, 2010.Search in Google Scholar

[21] Hugo Krawczyk, Kenneth G. Paterson, and Hoeteck Wee. On the security of the TLS protocol: A systematic analysis. In Ran Canetti and Juan A. Garay, editors, Advances in Cryptology - CRYPTO 2013: 33rd Annual Cryptology Conference, Santa Barbara, CA, USA, August 18-22, 2013. Proceedings, Part I, volume 8042 of Lecture Notes in Computer Science, pages 429-448. Springer, 2013.Search in Google Scholar

[22] Nick Mathewson. Tor proposal # 202: Two improved relay encryption protocols for Tor cells. In [26], path: root/proposals/202-improved-relay-crypto.txt, blob: 695df306.Search in Google Scholar

[23] Nick Mathewson. Tor proposal #216: Improved circuitcreation key exchange. In [26], path: root/proposals/216- ntor-handshake.txt, blob: f76e81cd.Search in Google Scholar

[24] Nick Mathewson. Tor proposal #249: Allow create cells with >505 bytes of handshake data. In [26], path: root/proposals/249-large-create-cells.txt, blob: e04b4c0c.Search in Google Scholar

[25] Nick Mathewson. Tor proposal #261: AEZ for relay cryptography. In [26], path: root/proposals/261-aez-crypto.txt, blob: 14435e7c.Search in Google Scholar

[26] The Tor Project. Torspec Git repository. https://gitweb.torproject.org/torspec.git.Search in Google Scholar

[27] John M. Schanck, William Whyte, and Zhenfei Zhang. Tor proposal #263: Request to change key exchange protocol for handshake. In [26], path: root/proposals/263-ntru-forpq- handshake.txt, blob: a6732b60.Search in Google Scholar

[28] John M. Schanck, William Whyte, and Zhenfei Zhang. Implementation of the current proposal using NTRUEncrypt. https://github.com/NTRUOpenSourceProject/ntru-tor, July 2015.Search in Google Scholar

[29] Peter W. Shor. Algorithms for quantum computation: Discrete logarithms and factoring. In Foundations of Computer Science, 1994 Proceedings., 35th Annual Symposium on, pages 124-134. IEEE Computer Society Press, 1994.Search in Google Scholar

[30] G.M. Zaverucha. Hybrid encryption in the multi-user setting. Cryptology ePrint Archive, Report 2012/159, 2012. http://eprint.iacr.org/2012/159.Search in Google Scholar

Recommended articles from Trend MD

Plan your remote conference with Sciendo