Abstract
Tor is currently the most popular network for anonymous Internet communication. It critically relies on volunteer nodes called bridges to relay Internet traffic when a user’s ISP blocks connections to Tor. Unfortunately, current methods for distributing bridges are vulnerable to malicious users who obtain and block bridge addresses. In this paper, we propose TorBricks, a protocol for privacy-preserving distribution of Tor bridges to n users, even when an unknown number \({t < n}\) of these users are controlled by a malicious adversary. TorBricks distributes \(O(t\log {n})\) bridges and guarantees that all honest users can connect to Tor with high probability after \(O(\log {t})\) rounds of communication with the distributor. Our empirical evaluations show that TorBricks requires at least 20x fewer bridges and two orders of magnitude less running time than the state-of-the-art.
M. Zamani—This work was done when the author was a student at the University of New Mexico.
Similar content being viewed by others
Notes
- 1.
By honest users, we mean the users that are not controlled by the censor to obtain the bridge addresses assigned to them.
- 2.
Completely blocking a service such as email would likely impose significant economic consequences for censors. However, unfortunately, email alone does not enable real-time interaction with the Web.
- 3.
We are not aware of any efficient decentralized algorithm to partition a set of n elements into k randomly-chosen disjoint subsets.
References
The Tor Project metrics: bridges in the network between March 1, 2016 and March 31, 2016
The Tor Project metrics: direct users connecting between January 1, 2015 and March 31, 2015
The Tor Project metrics: relays in the network between January 1, 2015 and March 31, 2015
TorMetrics: Directly connecting users. https://metrics.torproject.org/userstats-relay-country.html
The Tor Project: Pluggable transport (2015)
Bender, M.A., Fineman, J.T., Movahedi, M., Saia, J., Dani, V., Gilbert, S., Pettie, S., Young, M.: Resource-competitive algorithms. ACM SIGACT News 46(3), 57–71 (2015)
Bogetoft, P., et al.: Secure multiparty computation goes live. In: Dingledine, R., Golle, P. (eds.) FC 2009. LNCS, vol. 5628, pp. 325–343. Springer, Heidelberg (2009). doi:10.1007/978-3-642-03549-4_20
Boyle, E., Chung, K.-M., Pass, R.: Large-scale secure computation: multi-party computation for (parallel) RAM programs. In: Gennaro, R., Robshaw, M. (eds.) CRYPTO 2015. LNCS, vol. 9216, pp. 742–762. Springer, Heidelberg (2015). doi:10.1007/978-3-662-48000-7_36
Burnett, S., Feamster, N.: Encore: lightweight measurement of web censorship with cross-origin requests. SIGCOMM Comput. Commun. Rev. 45(4), 653–667 (2015)
Dani, V., King, V., Movahedi, M., Saia, J.: Quorums quicken queries: efficient asynchronous secure multiparty computation. In: Chatterjee, M., Cao, J., Kothapalli, K., Rajsbaum, S. (eds.) ICDCN 2014. LNCS, vol. 8314, pp. 242–256. Springer, Heidelberg (2014). doi:10.1007/978-3-642-45249-9_16
Dingledine, R.: Research problem: five ways to test bridge reachability (2011)
Dingledine, R.: Research problems: ten ways to discover Tor bridges (2011)
Dingledine, R., Mathewson, N.: Design of a blocking-resistant anonymity system. Technical report, The Tor Project Inc. (2006)
Dingledine, R., Mathewson,N., Syverson, P.: Tor: the second-generation onion router. In: Proceedings of the 13th USENIX Security Symposium, Berkeley, CA, USA (2004)
Dubhashi, D.P., Panconesi, A.: Concentration of Measure for the Analysis of Randomized Algorithms. Cambridge University Press, New York (2009)
Ensafi, R., Fifield, D., Winter, P., Feamster, N., Weaver, N., Paxson, V.: Examining how the great firewall discovers hidden circumvention servers. In: Internet Measurement Conference (IMC). ACM (2015)
Ensafi, R., Knockel, J., Alexander, G., Crandall, J.R.: Detecting intentional packet drops on the internet via TCP/IP side channels. In: Faloutsos, M., Kuzmanovic, A. (eds.) PAM 2014. LNCS, vol. 8362, pp. 109–118. Springer, Cham (2014). doi:10.1007/978-3-319-04918-2_11
Feamster, N., Balazinska, M., Wang, W., Balakrishnan, H., Karger, D.: Thwarting web censorship with untrusted messenger discovery. In: Dingledine, R. (ed.) PET 2003. LNCS, vol. 2760, pp. 125–140. Springer, Heidelberg (2003). doi:10.1007/978-3-540-40956-4_9
Gilbert, S., Saia, J., King, V., Young, M.: Resource-competitive analysis: a new perspective on attack-resistant distributed computing. In: Proceedings of the 8th International Workshop on Foundations of Mobile Computing, FOMC 2012, pp. 1:1–1:6. ACM, New York (2012)
Goldreich, O., Micali, S., Wigderson, A.: How to play any mental game. In: Proceedings of the Nineteenth Annual ACM Symposium on Theory of Computing, STOC 1987, pp. 218–229. ACM, New York (1987)
Lindell, Y., Pinkas, B.: Secure multiparty computation for privacy-preserving data mining. J. Priv. Confid. 1(1), 5 (2009)
Ling, Z., Luo, J., Yu, W., Yang, M., Fu, X.: Extensive analysis and large-scale empirical evaluation of tor bridge discovery. In: 2012 Proceedings IEEE INFOCOM, pp. 2381–2389, March 2012
Mahdian, M.: Fighting censorship with algorithms. In: Boldi, P., Gargano, L. (eds.) FUN 2010. LNCS, vol. 6099, pp. 296–306. Springer, Heidelberg (2010). doi:10.1007/978-3-642-13122-6_29
McCoy, D., Morales, J.A., Levchenko, K.: Proximax: measurement-driven proxy dissemination (short paper). In: Danezis, G. (ed.) FC 2011. LNCS, vol. 7035, pp. 260–267. Springer, Heidelberg (2012). doi:10.1007/978-3-642-27576-0_21
Mitzenmacher, M., Upfal, E., Probability, C.: Randomized Algorithms and Probabilistic Analysis. Cambridge University Press, Cambridge (2005)
Reed, I., Solomon, G.: Polynomial codes over certain finite fields. J. Soc. Ind. Appl. Math. (SIAM) 8(2), 300–304 (1960)
Rushe, D.: Google reports ‘alarming’ rise in censorship by governments. The Guardian, June 2012
Saia, J., Zamani, M.: Recent results in scalable multi-party computation. In: Italiano, G.F., Margaria-Steffen, T., Pokorný, J., Quisquater, J.-J., Wattenhofer, R. (eds.) SOFSEM 2015. LNCS, vol. 8939, pp. 24–44. Springer, Heidelberg (2015). doi:10.1007/978-3-662-46078-8_3
Shamir, A.: How to share a secret. Commun. ACM 22(11), 612–613 (1979)
Sovran, Y., Libonati, A., Li, J.: Pass it on: social networks stymie censors. In: Proceedings of the 7th International Conference on Peer-to-peer Systems, IPTPS 2008, Berkeley, CA, USA, p. 3. USENIX Association (2008)
Turner, K.: Mass surveillance silences minority opinions, according to study. The Washington Post, March 2016
Wang, Q., Lin, Z., Borisov, N., Hopper, N.: rBridge: user reputation based tor bridge distribution with privacy preservation. In: Network and Distributed System Security Symposium, NDSS 2013. The Internet Society (2013)
Winter, P., Lindskog, S.: How the great firewall of China is blocking Tor. In: 2nd USENIX Workshop on Free and Open Communications on the Internet, Berkeley, CA (2012)
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2017 Springer International Publishing AG
About this paper
Cite this paper
Zamani, M., Saia, J., Crandall, J. (2017). TorBricks: Blocking-Resistant Tor Bridge Distribution. In: Spirakis, P., Tsigas, P. (eds) Stabilization, Safety, and Security of Distributed Systems. SSS 2017. Lecture Notes in Computer Science(), vol 10616. Springer, Cham. https://doi.org/10.1007/978-3-319-69084-1_32
Download citation
DOI: https://doi.org/10.1007/978-3-319-69084-1_32
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-319-69083-4
Online ISBN: 978-3-319-69084-1
eBook Packages: Computer ScienceComputer Science (R0)