SPV: secure path vector routing for securing BGP

ABSTRACT

As our economy and critical infrastructure increasingly relies on the Internet, the insecurity of the underlying border gateway routing protocol (BGP) stands out as the Achilles heel. Recent misconfigurations and attacks have demonstrated the brittleness of BGP. Securing BGP has become a priority.In this paper, we focus on a viable deployment path to secure BGP. We analyze security requirements, and consider tradeoffs of mechanisms that achieve the requirements. In particular, we study how to secure BGP update messages against attacks. We design an efficient cryptographic mechanism that relies only on symmetric cryptographic primitives to guard an ASPATH from alteration, and propose the Secure Path Vector (SPV) protocol. In contrast to the previously proposed S-BGP protocol, SPV is around 22 times faster. With the current effort to secure BGP, we anticipate that SPV will contribute several alternative mechanisms to secure BGP, especially for the case of incremental deployments.

REFERENCES

• 1: F. Baker and R. Atkinson. RIP-2 MD5 Authentication. Internet Request for Comment RFC 2082, Internet Engineering Task Force, January 1997.
• 2: A. Barbir, S. Murphy, and Y. Yang. Generic Threats to Routing Protocols. Internet-Draft draft-ietf-rpsec-routing-threats-06, April 2004.
• 3: Mihir Bellare , Anand Desai , Eron Jokipii , Phillip Rogaway, A Concrete Security Treatment of Symmetric Encryption, Proceedings of the 38th Annual Symposium on Foundations of Computer Science (FOCS '97), p.394, October 19-22, 1997
• 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: John Black , Phillip Rogaway , Thomas Shrimpton, Black-Box Analysis of the Block-Cipher-Based Hash-Function Constructions from PGV, Proceedings of the 22nd Annual International Cryptology Conference on Advances in Cryptology, p.320-335, August 18-22, 2002
• 6: Dan Boneh , Matthew K. Franklin, Identity-Based Encryption from the Weil Pairing, Proceedings of the 21st Annual International Cryptology Conference on Advances in Cryptology, p.213-229, August 19-23, 2001
• 7: K. A. Bradley, S. Cheung, N. Puketza, B. Mukherjee, and R. A. Olsson. Detecting Disruptive Routers: A Distributed Network Monitoring Approach. In Proceedings of the IEEE Symposium on Research in Security and Privacy, pages 115--124, May 1998.
• 8: John W. Byers , Michael Luby , Michael Mitzenmacher , Ashutosh Rege, A digital fountain approach to reliable distribution of bulk data, Proceedings of the ACM SIGCOMM '98 conference on Applications, technologies, architectures, and protocols for computer communication, p.56-67, August 31-September 04, 1998, Vancouver, British Columbia, Canada
• 9: S. Cheung, An efficient message authentication scheme for link state routing, Proceedings of the 13th Annual Computer Security Applications Conference, p.90, December 08-12, 1997
• 10: Steven Cheung , Karl N. Levitt, Protecting routing infrastructures from denial of service using cooperative intrusion detection, Proceedings of the 1997 workshop on New security paradigms, p.94-106, September 23-26, 1997, Langdale, Cumbria, United Kingdom [doi>10.1145/283699.283744]
• 11: S. Convery, D. Cook, and M. Franz. An Attack Tree for the Border Gateway Protocol. Internet-Draft draft-ietf-rpsec-bgpattack-00, February 2004.
• 12: S. Crosby and D. Wallach. Denial of Service via Algorithmic Complexity Attacks. In Proceedings of the 11th USENIX Security Symposium, pages 29--44, August 2003.
• 13: Security of E-commerce threatened by 512-bit number factorization. http://www.cwi.nl/~kik/persb-UK.html, August 1999. CWI press release.
• 14: J. Daemen and V. Rijmen. AES Proposal: Rijndael, March 1999.
• 15: Alan Daly , William Marnane, Efficient architectures for implementing montgomery modular multiplication and RSA modular exponentiation on reconfigurable logic, Proceedings of the 2002 ACM/SIGDA tenth international symposium on Field-programmable gate arrays, February 24-26, 2002, Monterey, California, USA [doi>10.1145/503048.503055]
• 16: Shimon Even , Oded Goldreich , Silvio Micali, On-line/off-line digital signatures, Proceedings on Advances in cryptology, p.263-275, July 1989, Santa Barbara, California, United States
• 17: N. Feamster and H. Balakrishnan. Verifying the Correctness of Wide-Area Internet Routing. Technical Report MIT-LCS-TR-948, MIT, May 2004.
• 18: Oded Goldreich , Shafi Goldwasser , Silvio Micali, How to construct random functions, Journal of the ACM (JACM), v.33 n.4, p.792-807, Oct. 1986 [doi>10.1145/6490.6503]
• 19: G. Goodell, W. Aiello, T. Griffin, J. Ioannidis, P. McDaniel, and A. Rubin. Working around BGP: An Incremental Approach to Improving Security and Accuracy in Interdomain Routing. In Proceedings of NDSS 2003, February 2003.
• 20: R. Hauser , T. Przygienda , G. Tsudik, Reducing The Cost Of Security In Link-State Routing, Proceedings of the 1997 Symposium on Network and Distributed System Security, p.93, February 10-11, 1997
• 21: A. Heffernan. Protection of BGP Sessions via the TCP MD5 Signature Option. RFC 2385, August 1998.
• 22: Y.-C. Hu, D. B. Johnson, and A. Perrig. SEAD: Secure Efficient Distance Vector Routing for Mobile Wireless Ad Hoc Networks. Ad Hoc Networks, 1(1):175--192, 2003.
• 23: Y.-C. Hu, A. Perrig, and D. B. Johnson. Efficient Security Mechanisms for Routing Protocols. In Proceedings of NDSS 2003, February 2003.
• 24: Y.-C. Hu, A. Perrig, and D. B. Johnson. Packet Leashes: A Defense against Wormhole Attacks in Wireless Ad Hoc Networks. In Proceedings of the Twenty-Second Annual Joint Conference of the IEEE Computer and Communications Societies (INFOCOM 2003), April 2003.
• 25: S. Kent and R. Atkinson. IP Encapsulating Security Payload (ESP). Internet Request for Comment RFC 2406, Internet Engineering Task Force, November 1998.
• 26: S. Kent and R. Atkinson. Security Architecture for the Internet Protocol. Internet Request for Comment RFC 2401, Internet Engineering Task Force, November 1998.
• 27: 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 2000, pages 103--116, February 2000.
• 28: S. Kent, C. Lynn, and K. Seo. Secure Border Gateway Protocol (S-BGP). IEEE Journal on Selected Areas in Communications, 18(4):582--592, April 2000.
• 29: C. Kruegel, D. Mutz, W. Robertson, and F. Valeur. Topology-based Detection of Anomalous BGP Messages. In Proceedings of the Symposium on Recent Advances in Intrusion Detection (RAID), September 2003.
• 30: Brijesh Kumar, Integration of security in network routing protocols, ACM SIGSAC Review, v.11 n.2, p.18-25, Spring 1993 [doi>10.1145/153949.153953]
• 31: 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]
• 32: L. Lamport. Constructing Digital Signatures from a One-Way Function. Technical Report SRI-CSL-98, SRI International Computer Science Laboratory, October 1979.
• 33: A. Lenstra and E. Verheul. Selecting Cryptographic Key Sizes. Journal of Cryptology, 14(4):255--293, 2001.
• 34: Ratul Mahajan , David Wetherall , Tom Anderson, Understanding BGP misconfiguration, Proceedings of the 2002 conference on Applications, technologies, architectures, and protocols for computer communications, August 19-23, 2002, Pittsburgh, Pennsylvania, USA
• 35: G. Malkin. RIP Version 2. Internet Request for Comment RFC 2453, Internet Engineering Task Force, November 1998.
• 36: S. Matyas, C. Meyer, and J. Oseas. Generating Strong One-Way Functions with Cryptographic Algorithm. IBM Technical Disclosure Bulletin, 27:5658--5659, 1985.
• 37: Alfred J. Menezes , Scott A. Vanstone , Paul C. Van Oorschot, Handbook of Applied Cryptography, CRC Press, Inc., Boca Raton, FL, 1996
• 38: R. Merkle. Protocols for Public Key Cryptosystems. In 1980 IEEE Symposium on Security and Privacy, 1980.
• 39: Ralph C. Merkle, A Digital Signature Based on a Conventional Encryption Function, A Conference on the Theory and Applications of Cryptographic Techniques on Advances in Cryptology, p.369-378, August 16-20, 1987
• 40: D. Meyer. Route Views Project Page. http://www.routeviews.org.
• 41: S. A. Misel. Wow, AS7007! NANOG mail archives, http://www.merit.edu/mail.archives/nanog/1997-04/msg00340. html, 1997.
• 42: S. Murphy. BGP Security Protections. Internet-Draft draft-murphy-bgp-protect-01, October 2002.
• 43: Ola Nordström , Constantinos Dovrolis, Beware of BGP attacks, ACM SIGCOMM Computer Communication Review, v.34 n.2, April 2004 [doi>10.1145/997150.997152]
• 44: D. Pei, D. Massey, and L. Zhang. A Framework for Resilient Internet Routing Protocols. IEEE Network, 18(2):5--12, April 2004.
• 45: Radia Perlman, Interconnections: bridges and routers, Addison Wesley Longman Publishing Co., Inc., Redwood City, CA, 1992
• 46: Y. Rekhter and T. Li. A Border Gateway Protocol 4 (BGP-4). RFC 1771, March 1995.
• 47: Leonid Reyzin , Natan Reyzin, Better than BiBa: Short One-Time Signatures with Fast Signing and Verifying, Proceedings of the 7th Australian Conference on Information Security and Privacy, p.144-153, July 03-05, 2002
• 48: R. L. Rivest. The MD5 Message-Digest Algorithm. RFC 1321, April 1992.
• 49: R. L. Rivest , A. Shamir , L. Adleman, A method for obtaining digital signatures and public-key cryptosystems, Communications of the ACM, v.21 n.2, p.120-126, Feb. 1978 [doi>10.1145/359340.359342]
• 50: Pankaj Rohatgi, A compact and fast hybrid signature scheme for multicast packet authentication, Proceedings of the 6th ACM conference on Computer and communications security, p.93-100, November 01-04, 1999, Kent Ridge Digital Labs, Singapore [doi>10.1145/319709.319722]
• 51: Routing Protocol Security Requirements (rpsec). IETF working group, http://www.ietf.org/html.charters/rpsec-charter.html, 2004.
• 52: B. R. Smith and J.J. Garcia-Luna-Aceves. Securing the Border Gateway Routing Protocol. In Global Internet'96, pages 81--85, November 1996.
• 53: Bradley R. Smith , Shree Murthy , J. J. Garcia-Luna-Aceves, Securing Distance-Vector Routing Protocols, Proceedings of the 1997 Symposium on Network and Distributed System Security, p.85, February 10-11, 1997
• 54: John W. Stewart, III, BGP4: Inter-Domain Routing in the Internet, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1998
• 55: L. Subramanian, V. Roth, I. Stoica, S. Shenker, and R. Katz. Listen and Whisper: Security Mechanisms for BGP. In Proceedings of First Symposium on Networked Systems Design and Implementation (NSDI 2004), March 2004.
• 56: Nicholas Croyle Weaver , John Wawrzynek, The sfra: a fixed frequency fpga architecture, 2003
• 57: R. White. Deployment Considerations for Secure Origin BGP (soBGP), draft-white-sobgp-bgp-deployment-01.txt. Draft, Internet Engineering Task Force, June 2003. Available at http://www.watersprings.org/pub/id/draft-white-sobgp-bgp-deployment-01.txt.
• 58: A. Yaar, A. Perrig, and D. Song. SIFF: A Stateless Internet Flow Filter to Mitigate DDoS Flooding Attacks. In Proceedings of the IEEE Symposium on Security and Privacy, May 2004.
• 59: K. Zhang. Efficient Protocols for Signing Routing Messages. In Proceedings of NDSS '98, March 1998.

INDEX TERMS

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

Additional Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.2 Network Protocols
          Subjects: Routing protocols

General Terms:
Performance, Security

Keywords:
BGP, Border Gateway Protocol, interdomain routing, routing, security