1. bookVolume 2019 (2019): Issue 3 (July 2019)
Journal Details
License
Format
Journal
eISSN
2299-0984
First Published
16 Apr 2015
Publication timeframe
4 times per year
Languages
English
access type Open Access

ConsenSGX: Scaling Anonymous Communications Networks with Trusted Execution Environments

Published Online: 12 Jul 2019
Page range: 331 - 349
Received: 30 Nov 2018
Accepted: 16 Mar 2019
Journal Details
License
Format
Journal
eISSN
2299-0984
First Published
16 Apr 2015
Publication timeframe
4 times per year
Languages
English
Abstract

Anonymous communications networks enable individuals to maintain their privacy online. The most popular such network is Tor, with about two million daily users; however, Tor is reaching limits of its scalability. One of the main scalability bottlenecks of Tor and similar network designs originates from the requirement of distributing a global view of the servers in the network to all network clients. This requirement is in place to avoid epistemic attacks, in which adversaries who know which parts of the network certain clients do and do not know about can rule in or out those clients from being responsible for particular network traffic.

In this work, we introduce a novel solution to this scalability problem by leveraging oblivious RAM constructions and trusted execution environments in order to enable clients to fetch only the parts of the network view they require, without the directory servers learning which parts are being fetched. We compare the performance of our design with the current Tor mechanism and other related works to show one to two orders of magnitude better performance from an end-to-end perspective. We analyse the requirements to actually deploy such a scheme today and conclude that it would only require a small fraction (<2.5%) of the relays to have the required hardware support; moreover, these relays can perform their roles with minimal network bandwidth requirements.

Keywords

[1] C. Aguilar-Melchor, J. Barrier, L. Fousse, and M.-O. Killijian. XPIR: Private Information Retrieval for Everyone. Proceedings on Privacy Enhancing Technologies, 2016.10.1515/popets-2016-0010Search in Google Scholar

[2] A. Ahmad, K. Kim, M. I. Sarfaraz, and B. Lee. OBLIVIATE: A Data Oblivious Filesystem for Intel SGX. In 25th Network and Distributed System Security Symposium (NDSS), 2018.10.14722/ndss.2018.23284Search in Google Scholar

[3] I. Anati, S. Gueron, S. Johnson, and V. Scarlata. Innovative Technology for CPU Based Attestation and Sealing, 2013. https://software.intel.com/en-us/articles/innovative-technology-for-cpu-based-attestation-and-sealing.Search in Google Scholar

[4] S. Angel, H. Chen, K. Laine, and S. Setty. PIR with compressed queries and amortized query processing. In 39th IEEE Symposium on Security and Privacy (S&P). IEEE, 2018.10.1109/SP.2018.00062Search in Google Scholar

[5] ARM. ARM Security Technology: Building a Secure System using TrustZone Technology, 2015. http://infocenter.arm.com/help/topic/com.arm.doc.prd29-genc-009492c/PRD29-GENC-009492C_trustzone_security_whitepaper.pdf.Search in Google Scholar

[6] R. Barbulescu and S. Duquesne. Updating Key Size Estimations for Pairings. Cryptology ePrint Archive, Report 2017/334, 2017.Search in Google Scholar

[7] J. Bi, M. Liu, and X. Wang. Cryptanalysis of a homomorphic encryption scheme from ISIT 2008. In IEEE International Symposium on Information Theory (ISIT), 2012.10.1109/ISIT.2012.6283832Search in Google Scholar

[8] D. Bleichenbacher, A. Kiayias, and M. Yung. Decoding of Interleaved Reed Solomon Codes over Noisy Data. In International Colloquium on Automata, Languages, and Programming. Springer, 2003.10.1007/3-540-45061-0_9Search in Google Scholar

[9] D. Boneh, C. Gentry, B. Lynn, and H. Shacham. Aggregate and Verifiably Encrypted Signatures from Bilinear Maps. In International Conference on the Theory and Applications of Cryptographic Techniques. Springer, 2003.10.1007/3-540-39200-9_26Search in Google Scholar

[10] D. Boneh, B. Lynn, and H. Shacham. Short signatures from the Weil pairing. In International Conference on the Theory and Application of Cryptology and Information Security. Springer, 2001.10.1007/3-540-45682-1_30Search in Google Scholar

[11] Z. Brakerski and V. Vaikuntanathan. Efficient Fully Homomorphic Encryption from (Standard) LWE. SIAM Journal on Computing, 2014.10.1137/120868669Search in Google Scholar

[12] F. Brasser, U. Müller, A. Dmitrienko, K. Kostiainen, S. Capkun, and A. Sadeghi. Software Grand Exposure: SGX Cache Attacks Are Practical. In 11th USENIX Workshop on O˙ensive Technologies (WOOT), 2017.Search in Google Scholar

[13] Brave. Brave Private Tabs with Tor. https://brave.com/tor-tabs-beta, Accessed September 2018.Search in Google Scholar

[14] J. V. Bulck, M. Minkin, O. Weisse, D. Genkin, B. Kasikci, F. Piessens, M. Silberstein, T. F. Wenisch, Y. Yarom, and R. Strackx. Foreshadow: Extracting the Keys to the Intel SGX Kingdom with Transient Out-of-Order Execution. In 27th USENIX Security Symposium, 2018.Search in Google Scholar

[15] B. Chor, O. Goldreich, E. Kushilevitz, and M. Sudan. Private Information Retrieval. In IEEE Foundations of Computer Science (FOCS), 1995.Search in Google Scholar

[16] D. Coppersmith and M. Sudan. Reconstructing Curves in Three (and Higher) Dimensional Space from Noisy Data. In 35th ACM Symposium on Theory of Computing (STOC), 2003.10.1145/780542.780563Search in Google Scholar

[17] F. Dall, G. De Micheli, T. Eisenbarth, D. Genkin, N. Heninger, A. Moghimi, and Y. Yarom. Cachequote: Efficiently Recovering Long-Term Secrets of SGX EPID via Cache Attacks. IACR Transactions on Cryptographic Hardware and Embedded Systems, 2018.10.46586/tches.v2018.i2.171-191Search in Google Scholar

[18] G. Danezis and R. Clayton. Route Fingerprinting in Anonymous Communications. In 6th IEEE International Conference on Peer-to-Peer Computing. IEEE, 2006.Search in Google Scholar

[19] G. Danezis and P. Syverson. Bridging and Fingerprinting: Epistemic Attacks on Route Selection. In 8th Privacy Enhancing Technologies Symposium (PETS). Springer, 2008.Search in Google Scholar

[20] S. Devadas, M. van Dijk, C. W. Fletcher, L. Ren, E. Shi, and D. Wichs. Onion ORAM: A Constant Bandwidth Blowup Oblivious RAM. In Theory of Cryptography Conference (TCC). Springer, 2016.10.1007/978-3-662-49099-0_6Search in Google Scholar

[21] R. Dingledine, N. Mathewson, and P. Syverson. Tor: The Second-Generation Onion Router. In 13th USENIX Security Symposium, 2004.10.21236/ADA465464Search in Google Scholar

[22] J. R. Douceur. The Sybil attack. In International Workshop on Peer-to-Peer Systems. Springer, 2002.10.1007/3-540-45748-8_24Search in Google Scholar

[23] T. Elahi, K. Bauer, M. AlSabah, R. Dingledine, and I. Goldberg. Changing of the Guards: A Framework for Understanding and Improving Entry Guard Selection in Tor. In 11th ACM Workshop on Privacy in the Electronic Society (WPES). ACM, 2012.10.1145/2381966.2381973Search in Google Scholar

[24] C. Fletcher, M. Naveed, L. Ren, E. Shi, and E. Stefanov. Bucket ORAM: Single Online Roundtrip, Constant Bandwidth Oblivious RAM. Cryptology ePrint Archive, Report 2015/1065, 2015.Search in Google Scholar

[25] I. Goldberg. Improving the Robustness of Private Information Retrieval. In 28th IEEE Symposium on Security and Privacy (S&P), 2007.10.1109/SP.2007.23Search in Google Scholar

[26] O. Goldreich and R. Ostrovsky. Software Protection and Simulation on Oblivious RAMs. Journal of the ACM (JACM), 1996.10.1145/233551.233553Search in Google Scholar

[27] S. Gueron. Intel® Advanced Encryption Standard (AES) New Instructions Set, 2010. https://www.intel.com/content/dam/doc/white-paper/advanced-encryption-standard-new-instructions-set-paper.pdf.Search in Google Scholar

[28] Intel. SGX Virtualization. https://01.org/intel-software-guard-extensions/sgx-virtualization. Accessed February 2018.Search in Google Scholar

[29] Intel. Intel Trusted Execution Technology, 2007. http://www.intel.com/technology/security/. Accessed September 2018.Search in Google Scholar

[30] Intel. Software Guard Extensions (Intel® SGX) Data Center Attestation Primitives: ECDSA Quote Library API, 2018. https://download.01.org/intel-sgx/dcap-1.0/docs/SGX_ECDSA_QuoteGenReference_DCAP_API_Linux_1.0.pdf.Search in Google Scholar

[31] A. Kapadia and N. Triandopoulos. Halo: High-Assurance Locate for Distributed Hash Tables. In 16th Network and Distributed System Security Symposium (NDSS), 2008.Search in Google Scholar

[32] D. Kaplan, J. Powell, and T. Woller. AMD Memory Encryption, 2016. https://developer.amd.com/wordpress/media/2013/12/AMD_Memory_Encryption_Whitepaper_v7-Public.pdf.Search in Google Scholar

[33] S. Karandikar, S. Devadas, A. Ou, K. Asanovic, I. Lebedev, D. Song, and D. Lee. Keystone Open-source Secure Hardware Enclave, 2018. https://keystone-enclave.org/. Accessed September 2018.Search in Google Scholar

[34] T. Kim and R. Barbulescu. Extended Tower Number Field Sieve: A New Complexity for the Medium Prime Case. In CRYPTO. Springer, 2016.10.1007/978-3-662-53018-4_20Search in Google Scholar

[35] P. Kocher, J. Horn, A. Fogh, D. Genkin, D. Gruss, W. Haas, M. Hamburg, M. Lipp, S. Mangard, T. Prescher, M. Schwarz, and Y. Yarom. Spectre Attacks: Exploiting Speculative Execution. In 40th IEEE Symposium on Security and Privacy (S&P), 2019.10.1109/SP.2019.00002Search in Google Scholar

[36] S. Lee, M.-W. Shih, P. Gera, T. Kim, H. Kim, and M. Peinado. Inferring Fine-grained Control Flow Inside SGX Enclaves with Branch Shadowing. In 26th USENIX Security Symposium, 2017.Search in Google Scholar

[37] T. Lepoint and M. Tibouchi. Cryptanalysis of a (Somewhat) Additively Homomorphic Encryption Scheme Used in PIR. In 3rd Workshop on Applied Homomorphic Cryptography and Encrypted Computing (WAHC), 2015.10.1007/978-3-662-48051-9_14Search in Google Scholar

[38] M. Lipp, M. Schwarz, D. Gruss, T. Prescher, W. Haas, A. Fogh, J. Horn, S. Mangard, P. Kocher, D. Genkin, Y. Yarom, and M. Hamburg. Meltdown: Reading Kernel Memory from User Space. In 27th USENIX Security Symposium, 2018.Search in Google Scholar

[39] E. K. Lua, J. Crowcroft, M. Pias, R. Sharma, and S. Lim. A Survey and Comparison of Peer-to-Peer Overlay Network Schemes. IEEE Communications Surveys & Tutorials, 2005.Search in Google Scholar

[40] W. Lueks and I. Goldberg. Sublinear Scaling for Multi-Client Private Information Retrieval. In International Conference on Financial Cryptography and Data Security (FC). Springer, 2015.10.1007/978-3-662-47854-7_10Search in Google Scholar

[41] N. Mathewson. Proposal 300: Walking Onions: Scaling and Saving Bandwidth. https://gitweb.torproject.org/torspec.git/tree/proposals/300-walking-onions.txt, 2019. Accessed February 2019.Search in Google Scholar

[42] P. Maymounkov and D. Mazieres. Kademlia: A Peer-to-Peer Information System Based on the XOR Metric. In International Workshop on Peer-to-Peer Systems. Springer, 2002.10.1007/3-540-45748-8_5Search in Google Scholar

[43] J. McLachlan, A. Tran, N. Hopper, and Y. Kim. Scalable Onion Routing with Torsk. In 16th ACM Conference on Computer and Communications Security (CCS), 2009.10.1145/1653662.1653733Search in Google Scholar

[44] C. A. Melchor and P. Gaborit. A Fast Private Information Retrieval Protocol. In IEEE International Symposium on Information Theory (ISIT), 2008.10.1109/ISIT.2008.4595308Search in Google Scholar

[45] P. Mishra, R. Poddar, J. Chen, A. Chiesa, and R. A. Popa. Oblix: An Efficient Oblivious Search Index. In 39th IEEE Symposium on Security and Privacy (S&P). IEEE, 2018.10.1109/SP.2018.00045Search in Google Scholar

[46] P. Mittal and N. Borisov. ShadowWalker: Peer-to-peer Anonymous Communication using Redundant Structured Topologies. In 16th ACM Conference on Computer and Communications Security (CCS), pages 161–172. ACM, 2009.10.1145/1653662.1653683Search in Google Scholar

[47] P. Mittal and N. Borisov. Information Leaks in Structured Peer-to-Peer Anonymous Communication Systems. ACM Transactions on Information and System Security (TISSEC), 2012.10.1145/2133375.2133380Search in Google Scholar

[48] P. Mittal, F. Olumofin, C. Troncoso, N. Borisov, and I. Goldberg. PIR-Tor: Scalable Anonymous Communication Using Private Information Retrieval. In 20th USENIX Security Symposium, 2011.Search in Google Scholar

[49] Mozilla. Fusion: Firefox USIng Onions, 2018. https://wiki.mozilla.org/Security/Fusion. Accessed September 2018.Search in Google Scholar

[50] A. Nambiar and M. Wright. Salsa: A Structured Approach to Large-Scale Anonymity. In 13th ACM Conference on Computer and Communications Security (CCS), 2006.10.1145/1180405.1180409Search in Google Scholar

[51] O. Ohrimenko, F. Schuster, C. Fournet, A. Mehta, S. Nowozin, K. Vaswani, and M. Costa. Oblivious multi-party machine learning on trusted processors. In 25th USENIX Security Symposium, 2016.Search in Google Scholar

[52] L. Øverlier and P. Syverson. Locating Hidden Servers. In IEEE Symposium on Security and Privacy (S&P), 2006.10.1109/SP.2006.24Search in Google Scholar

[53] A. Panchenko, S. Richter, and A. Rache. NISAN: Network Information Service for Anonymization Networks. In 16th ACM Conference on Computer and Communications Security (CCS), 2009.10.1145/1653662.1653681Search in Google Scholar

[54] S. Patel, G. Persiano, and K. Yeo. Private Stateful Information Retrieval. In 25th ACM Conference on Computer and Communications Security (CCS), 2018.10.1145/3243734.3243821Search in Google Scholar

[55] A. M. Piotrowska, J. Hayes, T. Elahi, S. Meiser, and G. Danezis. The Loopix Anonymity System. In 26th USENIX Security Symposium, 2017.Search in Google Scholar

[56] A. Rane, C. Lin, and M. Tiwari. Raccoon: Closing Digital Side-channels Through Obfuscated Execution. In 24th USENIX Security Symposium, 2015.Search in Google Scholar

[57] O. Regev. On Lattices, Learning With Errors, Random Linear Codes, and Cryptography. Journal of the ACM (JACM), 2009.10.1145/1568318.1568324Search in Google Scholar

[58] L. Ren, C. Fletcher, A. Kwon, E. Stefanov, E. Shi, M. van Dijk, and S. Devadas. Constants Count: Practical Improvements to Oblivious RAM. In 24th USENIX Security Symposium, 2015.Search in Google Scholar

[59] M. Rennhard and B. Plattner. Introducing MorphMix: Peer-to-Peer Based Anonymous Internet Usage with Collusion Detection. In 1st ACM Workshop on Privacy in the Electronic Society (WPES), 2002.10.1145/644527.644537Search in Google Scholar

[60] S. Sasy, S. Gorbunov, and C. W. Fletcher. ZeroTrace: Oblivious Memory Primitives from Intel SGX. In 25th Network and Distributed System Security Symposium (NDSS), 2018.10.14722/ndss.2018.23239Search in Google Scholar

[61] M. Schuchard, A. W. Dean, V. Heorhiadi, N. Hopper, and Y. Kim. Balancing the Shadows. In 9th ACM Workshop on Privacy in the Electronic Society (WPES), 2010.10.1145/1866919.1866921Search in Google Scholar

[62] M. Schwarz, S. Weiser, D. Gruss, C. Maurice, and S. Mangard. Malware Guard Extension: Using SGX to Conceal Cache Attacks. In International Conference on Detection of Intrusions and Malware, and Vulnerability Assessment. Springer, 2017.10.1007/978-3-319-60876-1_1Search in Google Scholar

[63] S. Shinde, Z. L. Chua, V. Narayanan, and P. Saxena. Preventing Page Faults from Telling Your Secrets. In 11th ACM Asia Conference on Computer and Communications Security (AsiaCCS), 2016.10.1145/2897845.2897885Search in Google Scholar

[64] R. Snader and N. Borisov. Improving Security and Performance in the Tor Network through Tunable Path Selection. IEEE Transactions on Dependable and Secure Computing, 2011.10.1109/TDSC.2010.40Search in Google Scholar

[65] E. Stefanov, E. Shi, and D. Song. Towards Practical Oblivious RAM. In 19th Network and Distributed System Security Symposium (NDSS), 2012.Search in Google Scholar

[66] E. Stefanov, M. Van Dijk, E. Shi, C. Fletcher, L. Ren, X. Yu, and S. Devadas. Path ORAM: An Extremely Simple Oblivious RAM Protocol. In 20th ACM Conference on Computer and Communications Security (CCS), 2013.10.1145/2508859.2516660Search in Google Scholar

[67] I. Stoica, R. Morris, D. Karger, M. F. Kaashoek, and H. Balakrishnan. Chord: A Scalable Peer-to-Peer Lookup Service for Internet Applications. ACM SIGCOMM Computer Communication Review, 2001.10.1145/383059.383071Search in Google Scholar

[68] P. Tabriz and N. Borisov. Breaking the collusion detection mechanism of MorphMix. In 6th International Workshop on Privacy Enhancing Technologies (PET), pages 368–383. Springer, 2006.10.1007/11957454_21Search in Google Scholar

[69] The Tor Project. Tor Directory Services v3. https://gitweb.torproject.org/torspec.git/tree/dir-spec.txt. Accessed September 2018.Search in Google Scholar

[70] The Tor Project. Tor Metrics. https://metrics.torproject.org/. Accessed September 2018.Search in Google Scholar

[71] The Tor Project. Who Uses Tor? https://www.torproject.org/about/torusers.html.en. Accessed September 2018.Search in Google Scholar

[72] United Nations. Universal Declaration of Human Rights (Article 12), 1948. http://www.un.org/en/universal-declaration-human-rights/. Accessed September 2018.Search in Google Scholar

[73] C. Wacek, H. Tan, K. S. Bauer, and M. Sherr. An Empirical Evaluation of Relay Selection in Tor. In 20th Network and Distributed System Security Symposium (NDSS), 2013.Search in Google Scholar

[74] D. S. Wallach. A Survey of Peer-to-Peer Security Issues. In 2002 Mext-NSF-JSPS International Conference on Software Security: Theories and Systems (ISSS). Springer, 2003.10.1007/3-540-36532-X_4Search in Google Scholar

[75] P. Wang and Y. Kim. Myrmic: Secure and Robust DHT Routing, 2006.Search in Google Scholar

[76] Q. Wang, P. Mittal, and N. Borisov. In search of an anonymous and secure lookup: attacks on structured peer-to-peer anonymous communication systems. In 17th ACM Conference on Computer and Communications Security (CCS), pages 308–318. ACM, 2010.10.1145/1866307.1866343Search in Google Scholar

[77] X. Wang, H. Chan, and E. Shi. Circuit ORAM: On Tightness of the Goldreich-Ostrovsky Lower Bound. In 22nd ACM Conference on Computer and Communications Security (CCS), 2015.10.1145/2810103.2813634Search in Google Scholar

[78] R. Wojtczuk and J. Rutkowska. Attacking Intel Trusted Execution Technology. Invisible Things Lab, 2009.Search in Google Scholar

[79] R. Wojtczuk and J. Rutkowska. Attacking SMM Memory via Intel CPU Cache Poisoning. Invisible Things Lab, 2009.Search in Google Scholar

[80] M. Wright, M. Adler, B. N. Levine, and C. Shields. Defending Anonymous Communications Against Passive Logging Attacks. In 24th IEEE Symposium on Security and Privacy (S&P). IEEE, 2003.Search in Google Scholar

[81] Y. Xu, W. Cui, and M. Peinado. Controlled-Channel Attacks: Deterministic Side Channels for Untrusted Operating Systems. In 36th IEEE Symposium on Security and Privacy (S&P), 2015.10.1109/SP.2015.45Search in Google Scholar

[82] B. Zantout and R. Haraty. I2P Data Communication System. In 10th International Conference on Networks (ICN), 2011.Search in Google Scholar

Recommended articles from Trend MD

Plan your remote conference with Sciendo