Aggregated path authentication for efficient BGP security

ABSTRACT

The 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 of these risks. However, many performance and deployment issues prevent S-BGP's real-world deployment. Previous work has explored improving S-BGP processing latencies, but space problems, such as increased message size and memory cost, remain the major obstacles. In this paper, we design aggregated path authentication schemes by combining two efficient cryptographic techniques---signature amortization and aggregate signatures. We propose six constructions for aggregated path authentication that substantially improve efficiency of S-BGP's path authentication on both speed and space criteria. Our performance evaluation shows that the new schemes achieve such an efficiency that they may overcome the space obstacles and provide a real-world practical solution for BGP security.

REFERENCES

• 1: 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]
• 2: Paulo S. L. M. Barreto , Ben Lynn , Michael Scott, Efficient Implementation of Pairing-Based Cryptosystems, Journal of Cryptology, v.17 n.4, p.321-334, September 2004 [doi>10.1007/s00145-004-0311-z]
• 3: Paulo S.L.M. Berreto. A note on efficient computation of cube roots in characteristic 3. Cryptology ePrint Archive, Report 2004/305. http://eprint.iacr.org/2004/305, 2004.
• 4: Dan Boneh, Craig Gentry, Ben Lynn, and Hovav Shacham. A Survey of Two Signature Aggregation Techniques. RSA CryptoBytes, 6(2):1--10, 2003.
• 5: Dan Boneh, Craig Gentry, Ben Lynn, and Hovav Shacham. Aggregate and Verifiably Encrypted Signatures from Bilinear Maps. In Proceedings of Eurocrypt 2003, number 2656 in LNCS, pages 416--432. Springer-Verlag, 2003.
• 6: Dan Boneh , Ben Lynn , Hovav Shacham, Short Signatures from the Weil Pairing, Proceedings of the 7th International Conference on the Theory and Application of Cryptology and Information Security: Advances in Cryptology, p.514-532, December 09-13, 2001
• 7: Dan Boneh , Ben Lynn , Hovav Shacham, Short Signatures from the Weil Pairing, Journal of Cryptology, v.17 n.4, p.297-319, September 2004 [doi>10.1007/s00145-004-0314-9]
• 8: CIDR BGP Reports from AS1221 (Telstra), May 2005. http://www.cidr-report.org/as1221/.
• 9: I. Duursma and H.-S. Lee. Tate pairing implementation for hyperelliptic curves y2 = xp - x + d. In Advances in Cryptology - Asiacrypt 2003, number 2894 in LNCS, pages 111--123. Springer-Verlag, 2003.
• 10: 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
• 11: Gerhard Frey , Hans-Georg Rück, A remark concerning m-divisibility and the discrete logarithm in the divisor class group of curves, Mathematics of Computation, v.62 n.206, p.865-874, April 1994 [doi>10.2307/2153546]
• 12: Steven D. Galbraith , Keith Harrison , David Soldera, Implementing the Tate Pairing, Proceedings of the 5th International Symposium on Algorithmic Number Theory, p.324-337, July 07-12, 2002
• 13: Lixin Gao, On inferring autonomous system relationships in the internet, IEEE/ACM Transactions on Networking (TON), v.9 n.6, p.733-745, December 2001 [doi>10.1109/90.974527]
• 14: Geoffrey Goodell, William Aiello, Timothy Griffin, John Ioannidis, Patrick McDaniel, and Aviel Rubin. Working around BGP: An Incremental Approach to Improving Security and Accuracy in Interdomain Routing. In The 10th Annual Network and Distributed System Security Symposium, San Diego, California, February 2003.
• 15: Michael Goodrich. Efficient and Secure Network Routing Algorithms. provisional patent filing, http://www.cs.jhu.edu/~goodrich/cgc/pubs/rout-ing.pdf, January 2001.
• 16: P. Grabher and D. Page. Hardware Acceleration of the Tate Pairing in Characteristic Three. In Workshop on Cryptographic Hardware and Embedded Systems 2005 (CHES 2005), Edinburgh, Scotland, August 2005.
• 17: R. Granger, D. Page, and M. Stam. On Small Characteristic Algebraic Tori in Pairing-Based Cryptography. Cryptology ePrint Archive, Report 2004/132. http://eprint.iacr.org/2004/132, 2004.
• 18: Timothy G. Griffin , Gordon Wilfong, An analysis of BGP convergence properties, Proceedings of the conference on Applications, technologies, architectures, and protocols for computer communication, p.277-288, August 30-September 03, 1999, Cambridge, Massachusetts, United States
• 19: Vipul Gupta , Matthew Millard , Stephen Fung , Yu Zhu , Nils Gura , Hans Eberle , Sheueling Chang Shantz, Sizzle: A Standards-Based End-to-End Security Architecture for the Embedded Internet (Best Paper), Proceedings of the Third IEEE International Conference on Pervasive Computing and Communications, p.247-256, March 08-12, 2005 [doi>10.1109/PERCOM.2005.41]
• 20: R. Housley, W. Polk, W. Ford, and D. Solo. Internet X.509 Public Key Infrastructure Certificate and CRL Profile. RFC3280, http://www.ietf.org/rfc3280.txt, April 2002.
• 21: Russ Housley. S-BGP memory issues are the obstacle for real-world deployment. Personal communication, April 2005.
• 22: 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
• 23: Stephen Kent, Charles Lynn, Joanne Mikkelson, and Karen Seo. Secure Border Gateway Protocol (S-BGP) -- Real World Performance and Deployment Issues. In The 7th Annual Network and Distributed System Security Symposium (NDSS'00), San Diego, California, February 2000.
• 24: Stephen Kent, Charles Lynn, and Karen Seo. Secure Border Gateway Protocol. IEEE Journal of Selected Areas in Communications, 18(4):582--592, April 2000.
• 25: Steve Kent. Securing the Border Gateway Protocol: A Status Update. In Seventh IFIP TC-6 TC-11 Conference on Communications and Multimedia Security, October 2003.
• 26: T. Kerins, W. P. Marnane, E. M. Popovici, and P.S.L.M. Barreto. Efficient hardware for the Tate pairing calculation in characteristic three. In Workshop on Cryptographic Hardware and Embedded Systems 2005 (CHES 2005), Edinburgh, Scotland, August 2005.
• 27: Craig Labovitz , Abha Ahuja , Abhijit Bose , Farnam Jahanian, Delayed Internet routing convergence, Proceedings of the conference on Applications, Technologies, Architectures, and Protocols for Computer Communication, p.175-187, August 28-September 01, 2000, Stockholm, Sweden
• 28: Anna Lysyanskaya, Silvio Micali, Leonid Reyzin, and Hovav Shacham. Sequential Aggregate Signatures from Trapdoor Permutations. In Eurocrypt 2004, volume 3027 ofLNCS, pages 74--90. Springer-Verlag, 2004.
• 29: Zhuoqing Morley Mao , Ramesh Govindan , George Varghese , Randy H. Katz, Route flap damping exacerbates internet routing convergence, Proceedings of the 2002 conference on Applications, technologies, architectures, and protocols for computer communications, August 19-23, 2002, Pittsburgh, Pennsylvania, USA
• 30: R. Merkle. Protocols for Public Key Cryptosystems. In Proc 1980 Symposium on Security and Privacy, IEEE Computer Society, pages 122--133, April 1980.
• 31: Victor S. Miller, The Weil Pairing, and Its Efficient Calculation, Journal of Cryptology, v.17 n.4, p.235-261, September 2004 [doi>10.1007/s00145-004-0315-8]
• 32: Multiprecision Integer and Rational Arithmetic C/C++ Library (MIRACL).
• 33: Multi-threaded Routing Toolkit. http://www.mrtd.net.
• 34: S. Murphy. BGP Security Vulnerabilities Analysis. Internet-Draft http://www.ietf.org/internet-drafts/draft-murphy-bgp-vuln-01.txt, October 2004.
• 35: David M. Nicol, Sean W. Smith, and Meiyuan Zhao. Evaluation of Efficient Security for BGP Route Announcements using Parallel Simulation. Simulation Practice and Theory Journal, special issue on Modeling and Simulation of Distributed Systems and Networks, 12(3--4):187--216, July 2004.
• 36: Andy T. Ogielski and James H. Cowie. SSFNet: Scalable Simulation Framework - Network Models. http://www.ssfnet.org.
• 37: Brian Joseph Premore , David M. Nicol, An analysis of convergence properties of the border gateway protocol using discrete event simulation, 2003
• 38: Y. Rekhter and T. Li. A Border Gateway Protocol 4 (BGP-4). RFC1771, http://www.ietf.org/rfc1771.txt, March 1995.
• 39: The Route Views Project. http://www.antc.uoregon.edu/route-views/.
• 40: M. Scott and Paulo S.L.M. Barreto. Compressed Pairings. In Advances in Cryptology - CRYPTO'2004, number 3152 in LNCS, pages 140--156. Springer-Verlag, 2004. Updated version: Cryptology ePrint Archive, Report 2004/032. http://eprint.iacr.org/2004/032.
• 41: B. Smith and J.J. Garcia-Luna-Aceves. Efficient Security Mechanisms for the Border Gateway Routing Protocol. Computer Communications (Elsevier), 21(3):203--210, 1998.
• 42: Lakshminarayanan Subramanian, Volker Roth, Ion Stoica, Scott Shenker, and Randy H. Katz. Listen and Whisper: Security Mechanisms for BGP. In Proceedings of First Symposium on Networked Systems Design and Implementation (NSDI 2004), March 2004.
• 43: Tao Wan, Evangelos Kranakis, and P.C. van Oorschot. Pretty Secure BGP (psBGP). In The 12th Annual Network and Distributed System Security Symposium (NDSS'05), San Diego, California, February 2005.
• 44: Russ White. Securing BGP Through Secure Origin BGP. The Internet Protocol Journal, 6(3):15--22, September 2003.
• 45: ANSI X9.63. The Elliptic Curve Digital Signature Algorithm (ECDSA). American Bankers Association, 1999.
• 46: Meiyuan Zhao, Sean W. Smith, and David M. Nicol. Evaluating the Performance Impact of PKI on BGP Security. In 4th Annual PKI R&D Workshop, April 2005.

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.0 General
          Subjects: Security and protection (e.g., firewalls)

General Terms:
Design, Performance, Security

Keywords:
BGP, authentication, performance, routing, security