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

Privacy-Preserving Interdomain Routing at Internet Scale

Published Online: 06 Jul 2017
Page range: 147 - 167
Received: 30 Nov 2016
Accepted: 16 Mar 2017
Journal Details
License
Format
Journal
First Published
16 Apr 2015
Publication timeframe
4 times per year
Languages
English

The Border Gateway Protocol (BGP) computes routes between the organizational networks that make up today’s Internet. Unfortunately, BGP suffers from deficiencies, including slow convergence, security problems, a lack of innovation, and the leakage of sensitive information about domains’ routing preferences. To overcome some of these problems, we revisit the idea of centralizing and using secure multi-party computation (MPC) for interdomain routing which was proposed by Gupta et al. (ACM HotNets’12). We implement two algorithms for interdomain routing with state-of-the-art MPC protocols. On an empirically derived dataset that approximates the topology of today’s Internet (55 809 nodes), our protocols take as little as 6 s of topology-independent precomputation and only 3 s of online time. We show, moreover, that when our MPC approach is applied at country/region-level scale, runtimes can be as low as 0.17 s online time and 0.20 s pre-computation time. Our results motivate the MPC approach for interdomain routing and furthermore demonstrate that current MPC techniques are capable of efficiently tackling real-world problems at a large scale.

[1] S. Machiraju and R. H. Katz. Leveraging BGP dynamics to reverse-engineer routing policies. Technical Report UCB/EECS-2006-61, EECS Department, University of California, Berkeley, May 2006.Search in Google Scholar

[2] V. Giotsas and S. Zhou. Inferring AS relationships from BGP attributes. CoRR, abs/1106.2417, 2011.Search in Google Scholar

[3] D. Gupta, A. Segal, A. Panda, G. Segev, M. Schapira, J. Feigenbaum, J. Rexford, and S. Shenker. A new approach to interdomain routing based on secure multi-party computation. In Workshop on Hot Topics in Networks (HotNets’12), pages 37–42. ACM, 2012.Search in Google Scholar

[4] P. Gill, M. Schapira, and S. Goldberg. Let the market drive deployment: a strategy for transitioning to BGP security. In SIGCOMM’11, pages 14–25. ACM, 2011.Search in Google Scholar

[5] O. Goldreich, S. Micali, and A. Wigderson. How to play any mental game or a completeness theorem for protocols with honest majority. In STOC’87, pages 218–229. ACM, 1987.Search in Google Scholar

[6] D. Demmler, T. Schneider, and M. Zohner. ABY – a framework for efficient mixed-protocol secure two-party computation. In NDSS’15. The Internet Society, 2015. Code: https://github.com/encryptogroup/ABY.Search in Google Scholar

[7] C. Labovitz, A. Ahuja, A. Bose, and F. Jahanian. Delayed internet routing convergence. SIGCOMM’00, 30(4):175–187, 2000.Search in Google Scholar

[8] B. Zhang, D. Massey, and L. Zhang. Destination reachability and BGP convergence time [border gateway routing protocol]. In GLOBECOM’04, volume 3, pages 1383–1389. IEEE, 2004.Search in Google Scholar

[9] R. Oliveira, B. Zhang, D. Pei, and L. Zhang. Quantifying path exploration in the internet. IEEE/ACM Transactions on Networking, 17(2):445–458, 2009.Search in Google Scholar

[10] N. Kushman, S. Kandula, and D. Katabi. Can you hear me now?!: It must be BGP. SIGCOMM’07, 37(2):75–84, 2007.Search in Google Scholar

[11] L. Gao and J. Rexford. Stable Internet routing without global coordination. IEEE/ACM Transactions on Networking, 9(6):681–692, 2001.Search in Google Scholar

[12] A. Fabrikant, U. Syed, and J. Rexford. There’s something about MRAI: timing diversity can exponentially worsen BGP convergence. In INFOCOM’11, pages 2975–2983. IEEE, 2011.Search in Google Scholar

[13] K. R. B. Butler, T. R. Farley, P. McDaniel, and J. Rexford. A survey of BGP security issues and solutions. Proceedings of the IEEE, 98(1):100–122, 2010.Search in Google Scholar

[14] M. Ben-Or, S. Goldwasser, and A. Wigderson. Completeness theorems for non-cryptographic fault-tolerant distributed computation (extended abstract). In STOC’88, pages 1–10. ACM, 1988.Search in Google Scholar

[15] A. Ben-Efraim, Y. Lindell, and E. Omri. Optimizing semihonest secure multiparty computation for the internet. In CCS’16, pages 578–590. ACM, 2016.Search in Google Scholar

[16] W. Henecka and M. Roughan. STRIP: privacy-preserving vector-based routing. In International Conference on Network Protocols (ICNP’13), pages 1–10. IEEE, 2013.Search in Google Scholar

[17] J. Brickell and V. Shmatikov. Privacy-preserving graph algorithms in the semi-honest model. In ASIACRYPT’05, volume 3788 of LNCS, pages 236–252. Springer, 2005.Search in Google Scholar

[18] M. Blanton, A. Steele, and M. Alisagari. Data-oblivious graph algorithms for secure computation and outsourcing. In ASIACCS’13, pages 207–218. ACM, 2013.Search in Google Scholar

[19] H. Carter, B. Mood, P. Traynor, and K. Butler. Secure outsourced garbled circuit evaluation for mobile phones. In USENIX Security’13, pages 289–304. USENIX, 2013.Search in Google Scholar

[20] C. Liu, X. Shaun Wang, K. Nayak, Y. Huang, and E. Shi. ObliVM: A programming framework for secure computation. In S&P’15, pages 359–376. IEEE, 2015.Search in Google Scholar

[21] A. C. Yao. How to generate and exchange secrets. In FOCS’86, pages 162–167. IEEE, 1986.Search in Google Scholar

[22] D. Malkhi, N. Nisan, B. Pinkas, and Y. Sella. Fairplay -secure two-party computation system. In USENIX Security’04, pages 287–302. USENIX, 2004.Search in Google Scholar

[23] D. Bogdanov, S. Laur, and J. Willemson. Sharemind: A framework for fast privacy-preserving computations. In ESORICS’ 08, volume 5283 of LNCS, pages 192–206. Springer, 2008.Search in Google Scholar

[24] Y. Huang, D. Evans, J. Katz, and L. Malka. Faster secure two-party computation using garbled circuits. In USENIX Security’11, pages 539–554. USENIX, 2011.Search in Google Scholar

[25] S. G. Choi, K.-W. Hwang, J. Katz, T. Malkin, and D. Rubenstein. Secure multi-party computation of Boolean circuits with applications to privacy in on-line marketplaces. In CT-RSA’12, volume 7178 of LNCS, pages 416–432. Springer, 2012.Search in Google Scholar

[26] P. Bogetoft, D. L. Christensen, I. Damgård, M. Geisler, T. Jakobsen, M. Krøigaard, J. D. Nielsen, J. B. Nielsen, K. Nielsen, J. Pagter, M. Schwartzbach, and T. Toft. Secure multiparty computation goes live. In FC’09, volume 5628 of LNCS, pages 325–343. Springer, 2009.Search in Google Scholar

[27] D. Bogdanov, M. Jõemets, S. Siim, and M. Vaht. How the Estonian tax and customs board evaluated a tax fraud detection system based on secure multi-party computation. In FC’15, volume 8975 of LNCS, pages 227–234. Springer, 2015.Search in Google Scholar

[28] Y. Ishai, J. Kilian, K. Nissim, and E. Petrank. Extending oblivious transfers efficiently. In CRYPTO’03, volume 2729 of LNCS, pages 145–161. Springer, 2003.Search in Google Scholar

[29] G. Asharov, Y. Lindell, T. Schneider, and M. Zohner. More efficient oblivious transfer and extensions for faster secure computation. In CCS’13, pages 535–548. ACM, 2013.Search in Google Scholar

[30] T. Griffin, F. Shepherd, and G. Wilfong. The stable paths problem and interdomain routing. IEEE/ACM Transactions on Networking, 10(2):232–243, 2002.Search in Google Scholar

[31] P. Gill, M. Schapira, and S. Goldberg. Modeling on quicksand: dealing with the scarcity of ground truth in interdomain routing data. Computer Communication Review, 42(1):40–46, 2012.Search in Google Scholar

[32] S. Goldberg, M. Schapira, P. Hummon, and J. Rexford. How secure are secure interdomain routing protocols. In SIGCOMM’10, pages 87–98. ACM, 2010.Search in Google Scholar

[33] The CAIDA AS relationships datasets. http://www.caida.org/data/as-relationships/.Search in Google Scholar

[34] GeoLite data created by MaxMind. http://dev.maxmind.com/geoip/.Search in Google Scholar

[35] J. Boyar, R. Peralta, and D. Pochuev. On the multiplicative complexity of boolean functions over the basis (∧, ⊕, 1). Theoretical Computer Science, 235(1):43–57, 2000.Search in Google Scholar

[36] V. Kolesnikov, A.-R. Sadeghi, and T. Schneider. Improved garbled circuit building blocks and applications to auctions and computing minima. In CANS’09, volume 5888 of LNCS, pages 1–20. Springer, 2009.Search in Google Scholar

[37] V. Kolesnikov and T. Schneider. Improved garbled circuit: Free XOR gates and applications. In ICALP’08, volume 5126 of LNCS, pages 486–498. Springer, 2008.Search in Google Scholar

[38] T. Schneider and M. Zohner. GMW vs. Yao? Efficient secure two-party computation with low depth circuits. In FC’13, volume 7859 of LNCS, pages 275–292. Springer, 2013.Search in Google Scholar

[39] O. Goldreich. The Foundations of Cryptography - volume 2, Basic Applications. Cambridge University Press, 2004.Search in Google Scholar

[40] J. B. Nielsen, P. S. Nordholt, C. Orlandi, and S. S. Burra. A new approach to practical active-secure two-party computation. In CRYPTO’12, volume 7417 of LNCS, pages 681–700. Springer, 2012.Search in Google Scholar

[41] J. B. Nielsen, T. Schneider, and R. Trifiletti. Constant round maliciously secure 2PC with function-independent preprocessing using LEGO. In NDSS’17. The Internet Society, 2017.Search in Google Scholar

[42] Y. Aumann and Y. Lindell. Security against covert adversaries: Efficient protocols for realistic adversaries. In TCC’07, volume 4392 of LNCS, pages 137–156. Springer, 2007.Search in Google Scholar

[43] I. Damgård, M. Geisler, and J. B. Nielsen. From passive to covert security at low cost. In TCC’10, volume 5978 of LNCS, pages 128–145. Springer, 2010.Search in Google Scholar

[44] G. Asharov and C. Orlandi. Calling out cheaters: Covert security with public verifiability. In ASIACRYPT’12, volume 7658 of LNCS, pages 681–698. Springer, 2012.Search in Google Scholar

[45] Vladimir Kolesnikov and Alex J Malozemoff. Public verifiability in the covert model (almost) for free. In ASIACRYPT’14, volume 9453 of LNCS, pages 210–235. Springer, 2014.Search in Google Scholar

[46] A. Aly, E. Cuvelier, S. Mawet, O. Pereira, and M. Van Vyve. Securely solving simple combinatorial graph problems. In FC’13, volume 7859 of LNCS, pages 239–257. Springer, 2013.Search in Google Scholar

[47] S. Zahur, M. Rosulek, and D. Evans. Two halves make a whole: Reducing data transfer in garbled circuits using half gates. In EUROCRYPT’15, volume 9057 of LNCS, pages 220–250. Springer, 2015.Search in Google Scholar

[48] M. Bellare, V. Hoang, S. Keelveedhi, and P. Rogaway. Efficient garbling from a fixed-key blockcipher. In S&P’13, pages 478–492. IEEE, 2013.Search in Google Scholar

Recommended articles from Trend MD

Plan your remote conference with Sciendo