On interdomain routing security and pretty secure BGP (psBGP)

ABSTRACT

It is well known that the Border Gateway Protocol (BGP), the IETF standard interdomain routing protocol, is vulnerable to a variety of attacks, and that a single misconfigured or malicious BGP speaker could result in large-scale service disruption. In this paper, we present Pretty Secure BGP (psBGP)---a proposal for securing BGP, including an architectural overview, design details for significant aspects, and preliminary security and operational analysis. psBGP differs from other security proposals (e.g., S-BGP and soBGP) in that it makes use of a single-level PKI for AS number authentication, a decentralized trust model for verifying the propriety of IP prefix origin, and a rating-based stepwise approach for AS_PATH (integrity) verification. psBGP trades off the strong security guarantees of S-BGP for presumed-simpler operation, e.g., using a PKI with a simple structure, with a small number of certificate types, and of manageable size. psBGP is designed to successfully defend against various (nonmalicious and malicious) threats from uncoordinated BGP speakers, and to be incrementally deployed with incremental benefits.

REFERENCES

• 1: Carlisle Adams , Steve Lloyd, Understanding Public-Key Infrastructure: Concepts, Standards, and Deployment Considerations, Macmillan Technical Publishing, 1999
• 2: William Aiello , John Ioannidis , Patrick McDaniel, Origin authentication in interdomain routing, Proceedings of the 10th ACM conference on Computer and communications security, October 27-30, 2003, Washington D.C., USA [doi>10.1145/948109.948133]
• 3: Barbir, A., Murphy, S., and Yang, Y. 2004. Generic threats to routing protocols. Internet Draft.
• 4: S. M. Bellovin, Security problems in the TCP/IP protocol suite, ACM SIGCOMM Computer Communication Review, v.19 n.2, p.32-48, April 1, 1989 [doi>10.1145/378444.378449]
• 5: Steven M. Bellovin, A Look Back at "Security Problems in the TCP/IP Protocol Suite", Proceedings of the 20th Annual Computer Security Applications Conference (ACSAC'04), p.229-249, December 06-10, 2004 [doi>10.1109/CSAC.2004.3]
• 6: Bellovin, S. and Gansner, E. 2003. Using link cuts to attack internet routing. Unpublished manuscript.
• 7: Bellovin, S., Ioannidis, J., and Bush, R. 2005. Position paper: Operational requirements for secured BGP. In DHS Secure Routing Workshop.
• 8: Boneh, D., Boyen, X., and Shacham, H. 2004. Short group signatures. In Proceedings of Crypto 2004. Vol. 3152. 41--55.
• 9: Michael Burrows , Martin Abadi , Roger Needham, A logic of authentication, ACM Transactions on Computer Systems (TOCS), v.8 n.1, p.18-36, Feb. 1990 [doi>10.1145/77648.77649]
• 10: Dempster, A. 1967. Upper and lower probabilities induced by a multivalued mapping. The Annals of Statistics 28, 325--339.
• 11: DHS. 2005. DHS secure routing workshop. Department of Homeland Security, Washington, D.C.
• 12: Gaarder, K. and Snekkenes, E. 1991. Applying a formal analysis technique to the CCIT X.509 strong two-way authentication protocol. Journal of Cryptology 3, 81--98.
• 13: Gao, L. 2000. Inferring autonomous system relationships in the Internet. In IEEE Global Internet.
• 14: Gligor, V., Kailar, R., Stubblebine, S., and Gong, L. 1991. Logics for cryptographic protocols---virtues and limitations. In Proceedings of the Computer Security Foundations Workshop IV. Los Alamitos, CA. 219--226.
• 15: Goodell, G., Aiello, W., Griffin, T., Ioannidis, J., McDaniel, P., and Rubin, A. 2003. Working around BGP: An incremental approach to improving security and accuracy of interdomain routing. In Proceedings of the 2003 ISOC Symposium on Network and Distributed Systems Security (NDSS'03). San Diego, CA. 75--85.
• 16: Richard Guida , Robert Stahl , Thomas Bunt , Gary Secrest , Joseph Moorcones, Deploying and Using Public Key Technology: Lessons Learned in Real Life, IEEE Security and Privacy, v.2 n.4, p.67-71, July 2004 [doi>10.1109/MSP.2004.41]
• 17: Hedrick, C. 1988. Routing information protocol. IETF RFC 1058.
• 18: Heffernan, A. 1998. Protection of BGP sessions via the TCP MD5 signature option. IETF RFC 2385.
• 19: Housley, R., Ford, W., Polk, W., and Solo, D. 1999. Internet X.509 public key infrastructure---certificate and CRL profile. IETF RFC 2459.
• 20: Yih-Chun Hu , Adrian Perrig , Marvin Sirbu, SPV: secure path vector routing for securing BGP, Proceedings of the 2004 conference on Applications, technologies, architectures, and protocols for computer communications, August 30-September 03, 2004, Portland, Oregon, USA
• 21: IRR. 2005. Internet routing registry. http://www.irr.net.
• 22: Just, M., Kranakis, E., and Wan, T. 2003. Resisting malicious packet dropping in wireless ad hoc networks. In Proceedings of the 2nd Annual Conference on Adhoc Networks and Wireless (ADHOCNOW'03).
• 23: Kaufman, C. 2005. The internet key exchange (IKEv2) protocol. IETF RFC 4306.
• 24: Kent, S. 2003. Securing the border gateway protocol: A status update. In Seventh IFIP TC-6 TC-11 Conference on Communications and Multimedia Security.
• 25: Kent, S. 2005. IP encapsulating security payload (ESP). IETF RFC 4303.
• 26: Kent, S. 2006. An infrastructure supporting secure internet routing. In Third European PKI Workshop.
• 27: Kent, S. and Atkinson, P. 1998a. Security architecture for the Internet protocol. IETF RFC 2401.
• 28: Kent, S. and Atkinson, P. 1998b. IP encapsulating security payload (ESP). IETF RFC 2406.
• 29: Kent, S., Lynn, C., Mikkelson, J., and Seo, K. 2000. Secure border gateway protocol (S-BGP) real world performance and deployment issues. In Proceedings of the 2000 ISOC Symposium on Network and Distributed Systems Security (NDSS'00).
• 30: Kent, S., Lynn, C., and Seo, K. 2000. Secure border gateway protocol (S-BGP). IEEE Journal on Selected Areas in Communications 18, 4 (Apr.), 582--592.
• 31: Neal Koblitz , Alfred J. Menezes, Another Look at "Provable Security", Journal of Cryptology, v.20 n.1, p.3-37, January 2007 [doi>10.1007/s00145-005-0432-z]
• 32: Kruegel, C., Mutz, D., Robertson, W., and Valeur, F. 2003. Topology-based detection of anomalous BGP messages. In Proceedings of the 6th Symposium on Recent Advances in Intrusion Detection (RAID'03).
• 33: Brijesh Kumar , Jon Crowcroft, Integrating security in inter-domain routing protocols, ACM SIGCOMM Computer Communication Review, v.23 n.5, p.36-51, Oct. 1993 [doi>10.1145/165611.165615]
• 34: Lynn, C., Kent, S., and Seo, K. 2003. X.509 Extensions for IP Addresses and AS Identifiers. draft-ietf-pkix-x509-ipaddr-as-extn-02.txt.
• 35: Chengyu Ma , Nan Hu , Yingjiu Li, On the release of CRLs in public key infrastructure, Proceedings of the 15th conference on USENIX Security Symposium, p.2-2, July 31-August 04, 2006, Vancouver, B.C., Canada
• 36: Ueli M. Maurer, Modelling a Public-Key Infrastructure, Proceedings of the 4th European Symposium on Research in Computer Security: Computer Security, p.325-350, September 25-27, 1996
• 37: Murphy S. 2002a. BGP Security Vulnerabilities Analysis. draft-murphy-bgp-vuln-00.txt.
• 38: Murphy S. 2002b. BGP Security Protections. draft-murphy-bgp-protect-00.txt.
• 39: Nicol, D., Smith, S., and Zhao, M. 2004. Evaluation of efficient security for BGP route announcements using parallel simulation. Simulation Pratice and Theory Journal, Special Issue on Modeling, 187--216.
• 40: Perlman, R. 1988. Network layer protocols with byzantine robustness. Tech. Rep. MIT/LCS/TR-429.
• 41: M. K. Reiter , S. G. Stubblebine, Toward acceptable metrics of authentication, Proceedings of the 1997 IEEE Symposium on Security and Privacy, p.10, May 04-07, 1997
• 42: Rekhter, Y. and Li, T. 1995. A border gateway protocol 4 (BGP 4). IETF RFC 1771.
• 43: Retana, A. and White, R. 2002. BGP Custom decision process. draft-retana-bgp-custom-decision-00.txt.
• 44: RouteViews. 2005. Route views project. http://www.routeviews.org.
• 45: Seo, K., Lynn, C., and Kent, S. 2001. Public-key infrastructure for the secure border gateway protocol (S-BGP). In IEEE DARPA Information Survivability Conference and Exposition II.
• 46: Shafer, G. 1976. A Mathematical Theory of Evidence. Princeton University Press, Princeton, NJ.
• 47: Lakshminarayanan Subramanian , Volker Roth , Ion Stoica , Scott Shenker , Randy H. Katz, Listen and whisper: security mechanisms for BGP, Proceedings of the 1st conference on Symposium on Networked Systems Design and Implementation, p.10-10, March 29-31, 2004, San Francisco, California
• 48: Villamizar, C., Alaettinoglu, C., Meyer, D., and Murphy, S. 1999. Routing policy system security. IETF RFC 2725.
• 49: Tao Wan, Securing routing protocols through information corroboration, Carleton University, Ottawa, Ont., Canada, 2006
• 50: Wan, T., Kranakis, E., and van Oorschot, P. 2004. S-RIP: A secure distance vector routing protocol. In Proceedings of the Applied Cryptography and Network Security (ACNS'04). Vol. 3089. 103--119.
• 51: Wan, T., Kranakis, E., and van Oorschot, P. 2005. Pretty secure BGP (psBGP). In Proceedings of the 2005 ISOC Symposium on Network and Distributed Systems Security (NDSS'05). San Diego, CA.
• 52: Wan, T., van Oorschot, P., and Kranakis, E. 2007. A selective introduction to border gateway protocol (BGP) security issues. In Proceedings of the NATO Advanced Studies Institute on Network Security and Intrusion Detection. Nork, Yerevan, Armenia. IOS Press (to appear, 2007).
• 53: White, R. 2003. Securing BGP through secure origin BGP. The Internet Protocol Journal 6, 3, 15--22.
• 54: Russ White , Danny McPherson , Srihari Sangli, Practical BGP, Addison Wesley Longman Publishing Co., Inc., Redwood City, CA, 2004
• 55: Meiyuan Zhao , Sean W. Smith , David M. Nicol, Aggregated path authentication for efficient BGP security, Proceedings of the 12th ACM conference on Computer and communications security, November 07-11, 2005, Alexandria, VA, USA [doi>10.1145/1102120.1102139]
• 56: Zhao, M., Smith, S., and Nicol, D. 2005b. Evaluating the performance impact of PKI on BGP security. In Proceedings of 4th Annual PKI Research Workshop (PKI'05). Gaithersburg, MD.
• 57: Philip R. Zimmermann, The official PGP user's guide, MIT Press, Cambridge, MA, 1995
• 58: Zsako, J. 1999. PGP authentication for RIPE database updates. IETF RFC 2726.

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.6 Internetworking

General Terms:
Reliability, Security, Standardization

Keywords:
BGP, authentication, certificates, interdomain routing, public-key infrastructure, secure routing protocols, trust