Origin authentication in interdomain routing

ABSTRACT

Attacks against Internet routing are increasing in number and severity. Contributing greatly to these attacks is the absence of origin authentication: there is no way to validate claims of address ownership or location. The lack of such services enables not only attacks by malicious entities, but indirectly allow seemingly inconsequential miconfigurations to disrupt large portions of the Internet. This paper considers the semantics, design, and costs of origin authentication in interdomain routing. We formalize the semantics of address delegation and use on the Internet, and develop and characterize broad classes of origin authentication proof systems. We estimate the address delegation graph representing the current use of IPv4 address space using available routing data. This effort reveals that current address delegation is dense and relatively static: as few as 16 entities perform 80% of the delegation on the Internet. We conclude by evaluating the proposed services via traced based simulation. Our simulation shows the enhanced proof systems can reduce significantly reduce resource costs associated with origin authentication.

REFERENCES

• 1: W. Aiello , F. Chung, Random Evolution in Massive Graphs, Proceedings of the 42nd IEEE symposium on Foundations of Computer Science, p.510, October 14-17, 2001
• 2: William Aiello , Sachin Lodha , Rafail Ostrovsky, Fast Digital Identity Revocation (Extended Abstract), Proceedings of the 18th Annual International Cryptology Conference on Advances in Cryptology, p.137-152, August 23-27, 1998
• 3: ARIN. American Registry for Internet Numbers, May 2003. http://www.arin.net/.
• 4: A. Barabasi and R. Albert. Emergence of Scaling in Random Networks. Science, 286:509--512, 1999.
• 5: 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
• 6: B. W. (editor). Secure Origin BGP (soBGP) Certificates. Internet Research Task Force, June 2003. (draft-weis-sobgp-certificates-00.txt).
• 7: R. W. (editor). Deployment Considerations for Secure Origin BGP (soBGP). Internet Research Task Force, October 2002. (draft-white-sobgp-bgp-extensions-00.txt).
• 8: Michalis Faloutsos , Petros Faloutsos , Christos Faloutsos, On power-law relationships of the Internet topology, Proceedings of the conference on Applications, technologies, architectures, and protocols for computer communication, p.251-262, August 30-September 03, 1999, Cambridge, Massachusetts, United States
• 9: 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 Network and Distributed Systems Security 2003. Internet Society, February 2003. San Diego, California. (Draft).
• 10: B. Green. BGP Security Update: Is the Sky Falling? NANOG 25, June 2002.
• 11: Y. Hu, A. Perrig, and D. Johnson. Efficient Security Mechanisms for Routing Protocols. In Proceedings of Network and Distributed Systems Security 2003. Internet Society, February 2003. San Diego, California.
• 12: G. Huston. Bgp table data, February 2003. http://bgp.potaroo.net/.
• 13: IANA. Autonomous System Numbers, March 2003.
• 14: IANA. Internet Protocol V4 Address Space, February 2003. http://www.iana.org/assignments/ipv4-address-space.
• 15: IANA. The Internet Assigned Numbers Authority, May 2003. http://www.iana.org/.
• 16: ICANN. The Internet Corporation for Assigned Names and Numbers, May 2003. http://www.icann.org/.
• 17: S. Kent, C. Lynn, J. Mikkelson, and K. Seo. Secure Border Gateway Protocol (S-BGP) --- Real World Performance and Deployment Issues. In Proceedings of Network and Distributed Systems Security 2000. Internet Society, February 2000.
• 18: S. Kent, C. Lynn, and K. Seo. Secure Border Gateway Protocol (Secure-BGP). IEEE Journal on Selected Areas in Communications, 18(4):582--592, April 2000.
• 19: 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
• 20: R. Merkle. Protocols for Public key Cryptosystems. In Proceedings of the 1980 Symposium on Security and Privacy, pages 122--133. IEEE, April 1980. Oakland, CA.
• 21: D. Meyer. The RouteViews Project, May 2003. http://www.routeviews.org/.
• 22: S. Micali, Efficient Certificate Revocation, Massachusetts Institute of Technology, Cambridge, MA, 1996
• 23: S. Misel. Wow, as7007! http://www.merit.edu/mail.archives/nanog/1997-04/msg00340.html.
• 24: S. Murphy. BGP Security Vulnerabilities Analysis (Draft). Internet Research Task Force, February 2002. (draft-murphy-bgp-vuln-00.txt).
• 25: M. Naor and K. Nassim. Certificate Revocation and Certificate Update. In Proceedings of the 7th USENIX Security Symposium, pages 217--228, January 1998.
• 26: R. Perlman. Network layer Protocols with Byzantine Robustness. Technical Report MIT/LCS/TR-429, October 1988.
• 27: Y. Rekhter and T. Li. A Border Gateway Protocol 4 (BGP 4). Internet Engineering Task Force, March 1995. RFC 1771.
• 28: Jennifer Rexford , Jia Wang , Zhen Xiao , Yin Zhang, BGP routing stability of popular destinations, Proceedings of the 2nd ACM SIGCOMM Workshop on Internet measurment, November 06-08, 2002, Marseille, France [doi>10.1145/637201.637232]
• 29: R. Rivest. The MD5 Message Digest Algorithm. Internet Engineering Task Force, April 1992. RFC 1321.
• 30: K. Seo, C. Lynn, and S. Kent. Public-Key Infrastructure for the Secure Border Gateway Protocol (S-BGP). In Proceedings of DARPA Information Survivability Conference and Exposition II. IEEE, June 2001.
• 31: B. Smith and J. Garcia-Luna-Aceves. Securing the border gateway routing protocol. In Proceedings of Global Internet '96, pages 103--116, November 1996.
• 32: John W. Stewart, III, BGP4: Inter-Domain Routing in the Internet, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1998
• 33: L. Subramanian, S. Agarwal, J. Rexford, and R. H. Katz. Characterizing the Internet Hierarchy from Multiple Vantage Points. In Proceedings of IEEE INFOCOM 2002. IEEE, June 2002.
• 34: Z. Wenzel, J. Klensin, R. Bush, and S. Huter. Guide to Administrative Procedures for the Internet Infrastructure. Internet Engineering Task Force, August 2000. RFC 2901.
• 35: Xiaoliang Zhao , Dan Pei , Lan Wang , Dan Massey , Allison Mankin , S. Felix Wu , Lixia Zhang, An analysis of BGP multiple origin AS (MOAS) conflicts, Proceedings of the 1st ACM SIGCOMM Workshop on Internet Measurement, November 01-02, 2001, San Francisco, California, USA [doi>10.1145/505202.505207]
• 36: G. K. Zipf. Human Behaviour and the Principle of Least Effort. Hafner, 1949.

INDEX TERMS

Primary Classification:
  D. Software
  D.4 OPERATING SYSTEMS
      D.4.6 Security and Protection

General Terms:
Security

Keywords:
BGP, address management, delegation, routing, security