Analysis of the SPV Secure Routing Protocol: Weaknesses and Lessons

Barath Raghavan, Saurabh Panjwani, and Anton Mityagin
Appears in: 
CCR April 2007

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.

Public Review By: 
Venkat Padmanabhan

Much attention has been paid to the problem of securing the Border Gateway Protocol (BGP), the glue that binds together the tens of thousands of disparate autonomous systems (ASes) that form the Internet. While many protocols for securing BGP have been proposed and this remains a fertile area of research, it is nice, for a change, to see a paper that analyzes an existing proposal and provides a deeper understanding of its attributes and failings rather than adding to the cacophony of proposals.
The present paper analyzes Secure Path Vector (SPV), a recent and prominent proposal for securing BGP, and points out some serious holes in it. To avoid the computational complexity of public key cryptography, SPV employs a weaker m-time signature scheme, which assures security only if an adversary has access to no more than m signatures for a given key. While this might seem problematic, this by itself isn’t the issue. Rather, as the present paper shows, the problem is the way in which SPV employs these cryptographic primitives. Essentially, an attacker, who is in possession of signed BGP Update messages corresponding to two paths of different lengths originated by the same AS, is often in a position to use a secret derived from the shorter path to forge the longer one.
While this is a well-reasoned and well-presented piece of work, the reviewers did have some criticisms. The overall impact that the attacks might have in reality isn’t clear. One would not only need to consider the prevalence of vulnerable subgraphs in the Internet topology but also whether a compromised route is in fact the preferred BGP route. Another criticism is that the problem of multi-path attacks was already acknowledged in the SPV paper, although the present paper does demonstrate that the mitigations presented there don’t work in certain cases.
Stepping back from the details, in my view the key take-away message from this paper, as exemplified by the authors’ call for reconsidering constant-time signatures, is the question of whether it makes sense to design the underpinnings of the secure Internet of the future based on “shortcuts” taken to work around (transient) performance issues.