Analysis of the SPV secure routing protocol: weaknesses and lessons

ABSTRACT

We analyze a secure routing protocol, Secure Path Vector (SPV), proposed in SIGCOMM 2004. SPV aims to provide authenticity for route announcements in the Border Gateway Protocol (BGP) using an efficient alternative to ordinary digital signatures, called constant-time signatures. Today, SPV is often considered the best cryptographic defense for BGP.

We find subtle flaws in the design of SPV which lead to attacks that can be mounted by 60% of Autonomous Systems in the Internet. In addition, we study several of SPV's design decisions and assumptions and highlight the requirements for security of routing protocols. In light of our analysis, we reexamine the need for constant-time signatures and find that certain standard digital signature schemes can provide the same level of efficiency for route authenticity.

REFERENCES

• 1: M. Bellare and B. Yee. Forward security in private key cryptography. In Proceedings of CT-RSA, Apr. 2003.
• 2: 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]
• 3: K. Butler, T. Farley, P. McDaniel, and J. Rexford. A survey of BGP security: Issues and solutions. Technical Report TD-5UGJ33, AT&T Research, Apr. 2005.
• 4: Levente Buttyán , István Vajda, Towards provable security for ad hoc routing protocols, Proceedings of the 2nd ACM workshop on Security of ad hoc and sensor networks, October 25-25, 2004, Washington DC, USA [doi>10.1145/1029102.1029119]
• 5: M. Caesar and J. Rexford. BGP routing policies in ISP networks. Technical Report UCB/CSD-05-1377, University of California, Berkeley, Mar. 2005.
• 6: CAIDA Skitter Project. http://www.caida.org/tools/measurement/skitter/.
• 7: Haowen Chan , Debabrata Dash , Adrian Perrig , Hui Zhang, Modeling adoptability of secure BGP protocol, Proceedings of the 2006 conference on Applications, technologies, architectures, and protocols for computer communications, September 11-15, 2006, Pisa, Italy
• 8: Cisco Systems. Personal communication, Apr. 2006.
• 9: Crypto++ library. http://www.eskimo.com/¿weidai/cryptlib.html.
• 10: A. Fujioka, T. Okamoto, and S. Miyaguchi. ESIGN: An efficient digital signature implementation for smart cards. In Proceedings of EUROCRYPT, Apr. 1991.
• 11: 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
• 12: S. Kent, C. Lynn, and K. Seo. Secure border gateway protocol (S-BGP). IEEE Journal on Selected Areas in Communications, 18(4), 2000.
• 13: E. Kiltz, A. Mityagin, S. Panjwani, and B. Raghavan. Append-only signatures. In Proceedings of ICALP, July 2005.
• 14: Hugo Krawczyk, Simple forward-secure signatures from any signature scheme, Proceedings of the 7th ACM conference on Computer and communications security, p.108-115, November 01-04, 2000, Athens, Greece [doi>10.1145/352600.352617]
• 15: A. Lysyanskaya, S. Micali, L. Reyzin, and H. Shacham. Sequential aggregate signatures from trapdoor permutations. In Proceedings of EUROCRYPT, May 2004.
• 16: S. Matyas, C. Meyer, and J. Oseas. Generating strong one-way functions with cryptographic algorithms. IBM Technical Disclosure Bulletin 27:5658--5659, 1985.
• 17: A. Menezes, M. Qu, D. Stinson, and Y. Wang. Evaluation of security level of cryptography: ESIGN signature scheme. CRYPTREC Project, Japan, Jan. 2001.
• 18: 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]
• 19: T. Okamoto and J. Stern. Almost uniform density of power residues and the provable security of ESIGN. In Proceedings of ASIACRYPT, Nov. 2003.
• 20: Adrian Perrig, The BiBa one-time signature and broadcast authentication protocol, Proceedings of the 8th ACM conference on Computer and Communications Security, November 05-08, 2001, Philadelphia, PA, USA [doi>10.1145/501983.501988]
• 21: 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
• 22: 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
• 23: T. Wan, E. Kranakis, and P. van Oorschot. Pretty secure BGP (psBGP). In Proceedings of ISOC NDSS, Feb. 2005.
• 24: R. White. Securing BGP through Secure Origin BGP (soBGP). The Internet Protocol Journal, Sept. 2003.
• 25: 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]

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:
Security

Keywords:
BGP, routing, secure path vector