Kevin Butler
ABSTRACT
The Border Gateway Protocol (BGP) is the de facto interdomain routing protocol on the Internet. While the serious vulnerabilities of BGP are well known, no security solution has been widely deployed. The lack of adoption is largely caused by a failure to find a balance between deployability, cost, and security. In this paper, we consider the design and performance of BGP path authentication constructions that limit resource costs by exploiting route stability. Based on a year-long study of BGP traffic and indirectly supported by findings within the networking community, we observe that routing paths are highly stable. This observation leads to comprehensive and efficient constructions for path authentication. We empirically analyze the resource consumption of the proposed constructions via trace-based simulations. This latter study indicates that our constructions can reduce validation costs by as much as 97.3% over existing proposals while requiring nominal storage resources. We conclude by considering operational issues related to incremental deployment of our solution.
- W. Aiello, K. Butler, and P. McDaniel. Implications of Path Stability for Efficient Authentication in Interdomain Routing. Technical Report NAS-TR-0002-2004, Networking and Security Research Center, Department of Computer Science and Engineering, Pennsylvania State University, University Park, PA, Oct. 2004. Revised October 2005.Google Scholar
- W. Aiello, J. Ioannidis, and P. McDaniel. Origin Authentication in Interdomain Routing. In Proceedings of ACM CCS '03, October 2003. Google ScholarDigital Library
- M. Baltatu, A. Lioy, F. Maino, and D. Mazzocchi. Security issues in control, management and routing protocols. Computer Networks (Amsterdam, Netherlands: 1999), 34(6):881--894, 2000. Elsevier Editions, Amsterdam. Google ScholarDigital Library
- A. Barbir, S. Murphy, and Y. Yang. Generic Threats to Routing Protocols (Draft). IETF, April 2004.Google Scholar
- S. Bellovin, R. Bush, T. Griffin, and J. Rexford. Slowing routing table growth by filtering based on address allocation policies. http://www.research.att.com/jrex/, June 2001.Google Scholar
- K. Butler, T. Farley, P. McDaniel, and J. Rexford. A Survey of BGP Security Issues and Solutions. Technical Report TD-5UGJ33, AT&T Labs - Research, Florham Park, NJ, Feb. 2004. ( revised June 2004).Google Scholar
- G. Goodell, W. Aiello, T. Griffin, J. Ioannidis, P. McDaniel, and A. Rubin. Working around BGP: An incremental approach to improving security and accuracy of interdomain routing. In Proceedings of NDSS '03, Feb. 2003.Google Scholar
- M. Goodrich, R. Tamassia, and A. Schwerin. Implementation of an authenticated dictionary with skip lists and commutative hashing. In Proceedings of DARPA Information Survivability Conference and Exposition II (DISCEX). IEEE Computer Society Press, June 2001. Los Angeles, CA.Google ScholarCross Ref
- Y. Hu, A. Perrig, and D. Johnson. Efficient security mechanisms for routing protocols. In Proceedings of NDSS '03, Feb. 2003.Google Scholar
- Y.-C. Hu, A. Perrig, and M. Sirbu. SPV: Secure Path Vector Routing for Securing BGP. In ACM SIGCOMM. ACM, August 2004. Google ScholarDigital Library
- G. Huston. Bgp reports, May 2005. http://bgp.potaroo.net/.Google Scholar
- IANA. Autonomous System Numbers, March 2003.Google Scholar
- ICANN. The Internet Corporation for Assigned Names and Numbers, July 2004. http://www.icann.org/.Google Scholar
- P. J. Transmission Control Protocol - DARPA Internet Protocol Program Specification. IETF, Sep. 1981. RFC 793.Google Scholar
- J. Karlin, S. Forrest, and J. Rexford. Pretty Good BGP: Protecting BGP by Cautiously Selecting Routes. Technical Report TR-CS-2005-37, University of New Mexico, Albuquerque, NM, USA, Oct. 2005.Google Scholar
- S. Kent. Securing the border gateway protocol. The Internet Protocol Journal, 6(3), Sep. 2003.Google Scholar
- S. Kent. Securing the Border Gateway Protocol: A status update. In Seventh IFIP TC-6 TC-11 Conference on Communications and Multimedia Security, Torino, Italy, Oct. 2003.Google Scholar
- S. Kent, C. Lynn, J. Mikkelson, and K. Seo. Secure Border Gateway Protocol (S-BGP) Real World Performance and Deployment Issues. In Proceedings of NDSS '00, Feb. 2000.Google Scholar
- S. Kent, C. Lynn, and K. Seo. Secure Border Gateway Protocol (S-BGP). IEEE Journal on Selected Areas in Communications, 18(4), Apr. 2000. Google ScholarDigital Library
- C. Kruegel, D. Mutz, W. Robertson, and F. Valeur. Topology-based detection of anomalous BGP messages. In Proceedings of RAID '03, Sept. 2003.Google ScholarCross Ref
- L. Lamport. Password Authentication with Insecure Communication. Commun. ACM, 24(11):770--772, Nov. 1981. Google ScholarDigital Library
- X. Meng, Z. Xu, L. Zhang, and S. Lu. An analysis of BGP routing table evolution. Technical Report TR030046, Computer Science Department, UCLA, Jan. 2003.Google Scholar
- Merit Network. The Internet Routing Registry, July 2004. http://www.irr.net/.Google Scholar
- R. Merkle. Protocols for public key cryptosystems. Oakland, CA, Apr. 1980. IEEE Symposium on Research in Security and Privacy.Google Scholar
- D. Meyer. The Route Views Project, Nov. 2006. http://www.routeviews.org/.Google Scholar
- D. Meyer and A. Partan. BGP Security, Availability,and Operator Needs. NANOG 28, June 2003.Google Scholar
- S. Murphy. BGP Security Vulnerabilities Analysis. RFC 4272, Jan. 2006.Google Scholar
- M. Naor and K. Nissim. Certificate revocation and certificate update. In Proceedings of the 7th USENIX Security Symposium, Jan. 1998. Google ScholarDigital Library
- H. Narayan, R. Govindan, and G. Varghese.The impact of address allocation and routing on the structure and implementation of routing tables. In Proceedings of ACM SIGCOMM '03, Karlsruhe, Germany, Aug. 2003. ACM. Google ScholarDigital Library
- J. Ng. Extensions to BGP to support secure origin BGP (soBGP). Internet Draft, Oct. 2002.Google Scholar
- D. Nicol, S. Smith, and M. Zhao. Evaluation of efficient security for BGP route announcements using parallel simulation. Simulation Modelling Practice and Theory, 12(3--4): 187--216, July 2004.Google Scholar
- O. Nordström and C. Dovrolis.Beware of BGP attacks. Computer Communications Review, 34(2):1--8, Apr. 2004. Google ScholarDigital Library
- Office of the President of the United States. Priority II: A National Cyberspace Security Threat and Vulnerability Reduction Program. National Strategy to Secure Cyberspace, Nov. 2004.Google Scholar
- R. Perlman. Network layer Protocols with Byzantine Robustness. PhD thesis, Massachusetts Institute of Technology, Cambridge, MA, Oct. 1988. MIT/LCS/TR-429.Google Scholar
- J. Postel. Internet Protocol. RFC 791, Sept. 1981.Google Scholar
- J. Puig, M. Achemlal, E. Jones, and D. McPherson. Generic Security Requirements for Routing Protocols ( Draft). IETF, July 2004.Google Scholar
- Y. Rekhter and P. Gross. Application of the Border Gateway Protocol in the Internet. RFC 1772, Mar. 1995. Google ScholarDigital Library
- Y. Rekhter and T. Li. A Border Gateway Protocol 4 (BGP-4). RFC 4271, Jan. 2006.Google Scholar
- J. Rexford, J. Wang, Z. Xiao, and Y. Zhang. BGP routing stability of popular destinations. In IMW '02: Proceedings of the 2nd ACM SIGCOMM Workshop on Internet measurment, pages 197--202, New York, NY, USA, 2002. ACM Press. Google ScholarDigital Library
- R. Rivest, A. Shamir, and L. Adleman. A Method for Obtaining Digital Signatures and Public-Key Cryptosystems. Communications of the ACM, 21(2):120--126, Feb. 1978. Google ScholarDigital Library
- K. Seo, C. Lynn, and S. Kent. Public-Key Infrastructure for the Secure Border Gateway Protocol (S-BGP). In IEEE DARPA Information Survivability Conference and Exposition II, June 2001.Google ScholarCross Ref
- B. Smith and J. Garcia-Luna-Aceves. Securing the border gateway routing protocol. In Proceedings of IEEE Global Internet 1996, London, UK, Nov. 1996.Google ScholarCross Ref
- L. Subramanian, V. Roth, I. Stoica, S. Shenker, and R. Katz. Listen and Whisper: Security mechanisms for BGP. In Proceedings of NSDI'04, Mar. 2004. Google ScholarDigital Library
- S. Teoh, K. Ma, S. Wu, D. Pei, L. Wang, L. Zhang, D. Massey, and R. Bush. Visual-Based Anomaly Detection for BGP Origin AS Change (OASC) Events. In Proceedings of IEEE/IFIP DSOM '03, October 2003.Google ScholarCross Ref
- T. Wan, E. Kranakis, and P. C. van Oorschot. Pretty Secure BGP (psBGP). In Proc. of NDSS '05. Internet Society (ISOC), Feb. 2005.Google Scholar
- L. Wang, X. Zhao, D. Pei, R. Bush, D. Massey, A. Mankin, S. F. Wu, and L. Zhang. Protecting bgp routes to top level DNS servers. In Proceedings of the 23rd International Conference on Distributed Computing Systems (ICDCS), May 2003. Google ScholarDigital Library
- K. Zhang, S.-T. Teoh, S.-M. Tseng, C.-N. Chuah, K.-L. Ma, and F. Wu. Performing BGP experiments on a semi-realistic internet environment. North American Network Operators Group (NANOG), October 2004. Google ScholarDigital Library
- X. Zhang, S. Wu, Z. Fu, and T.-L. Wu. Malicious Packet Dropping: How It Might Impact the TCP Performance and How We Can Detect It. In Proceedings of ICNP 2000, Nov. 2000. Google ScholarDigital Library
- M. Zhao, S. W. Smith, and D. M. Nicol. Aggregated path authentication for efficient BGP security. In Proceedings of the 12th ACM Conference on Computer and Communications Security (CCS'05), Nov. 2005. Alexandria, VA, USA. Google ScholarDigital Library
Index Terms
- Optimizing BGP security by exploiting path stability
Recommendations
Aggregated path authentication for efficient BGP security
CCS '05: Proceedings of the 12th ACM conference on Computer and communications securityThe Border Gateway Protocol (BGP) controls inter-domain routing in the Internet. BGP is vulnerable to many attacks, since routers rely on hearsay information from neighbors. Secure BGP (S-BGP) uses DSA to provide route authentication and mitigate many ...
BGP security in partial deployment: is the juice worth the squeeze?
As the rollout of secure route origin authentication with the RPKI slowly gains traction among network operators, there is a push to standardize secure path validation for BGP (i.e., S*BGP: S-BGP, soBGP, BGPSEC, etc.). Origin authentication already does ...
Neighbor-specific BGP: more flexible routing policies while improving global stability
SIGMETRICS '09The Border Gateway Protocol (BGP) offers network administrators considerable flexibility in controlling how traffic flows through their networks. However, the interaction between routing policies in different Autonomous Systems (ASes) can lead to ...
Comments