I. Introduction

BGP assumes that the routing information propagated by authenticated routers is correct. This assumption leaves the current infrastructure vulnerable to both accidental misconfigurations and deliberate attacks. Though BGP currently enables peers to transmit route announcements over authenticated channels, this approach only verifies who is speaking, but not what they say. For example, in 1997, a simple misconfiguration in a customer router caused it to advertise a short path to a large number of network prefixes, and this resulted in a massive black hole that disconnected significant portions of the Internet. Adversaries can inflict more extensive damage than misconfigurations. Adversaries can potentially render destinations unreachable, eavesdrop on data passing through them, or even impersonate a site.

More sophisticated BGP security mechanisms have been proposed (e.g., S-BGP), but they often require an extensive cryptographic key distribution infrastructure and/or a trusted central database. Neither of these two crucial ingredients have been introduced and hence these security proposals have not moved forward towards adoption. In this paper we seek measures to secure BGP that need no public key distribution nor rely on a trusted database. Our goal is not to achieve perfect security, but to provide much better security than exists at present through mechanisms that are easily deployable. The underlying vulnerability in BGP, which we primarily address in this paper, is the ability of an AS to propagate invalid routes that deviate from the actual Internet topology.

II. Our Approach: Listen and Whisper

The primary underlying vulnerability in BGP that we address in this presentation is the ability of an AS to create invalid routes. There are two types of invalid routes:

1. Invalid routes in the Control plane: This occurs when an AS propagates an advertisement with a fake AS path (i.e., one that does not exist in the Internet topology), causing other AS's to choose this route over genuine routes. A single malicious adversary can divert traffic to pass through it and then cause havoc by, for example, dropping packets (rendering destinations unreachable), eavesdropping (violating privacy), or impersonating end-hosts within the destination network (such as Web servers, etc.).
2. Invalid routes in the Data Plane: This occurs when a router forwards packets in a manner inconsistent with the routing advertisements it has received or propagated; in short, the routing path in the data plane does not match the corresponding routing path advertised in the control plane. Mao et al.** show that for nearly 8% of Internet paths, the control plane and data plane paths do not match. The prevalence of such a high mismatch ratio motivates the need for separately verifying the correctness of routes in the data plane and not merely focusing on the control plane.

II.1 Brief description of our solutions

Listen detects invalid routes in the data plane by checking whether data sent along routes reaches the intended destination. Whisper checks for consistency in the control plane.

Whisper: The objective of the Whisper method is to defend against invalid route announcements on the control plane. The primary design principle of these protocols is to use redundant network connectivity as a substitute for secure communication channels. The protocols verify route announcements of the same originator pair-wise. Unless an adversary controls the paths over which both route announcements were propagated, the verification yields an inconsistency. In this case, our protocols raise an alarm and flag the suspicious routes. On the other hand, if one route announcement is consistent with a valid route announcement, then two of our Whisper protocols also provide a certain level of confidence that the AS path in the first announcement is valid. The primary advantage of these protocols is that they have a negligible management, processing, and implementation overhead. Particularly, they do not require prior exchange of cryptographic keys.

Listen: The main idea behind the Listen method is to monitor the progress of TCP flows on the data plane. By doing this, a router can detect loss of connectivity that might be caused either by BGP misconfigurations or network failures. While the Listen approach only points to the existence of a reachability problem, determining the cause requires other mechanisms.

The Listen technique has two distinct advantages. First, early detection of reachability problems for reasonably popular prefixes (prefixes that regularly observe non-zero traffic) can virtually eliminate the possibility of long outages due to misconfigurations. Second, it is a stand-alone technique that can be incrementally deployed: a router would benefit from implementing this technique even if it is the only one to implement it. However, this technique is not robust against attackers along the downstream path that impersonate the destinations.

II.2 Level of Protection

While both these techniques can be used in isolation, they are more useful when applied in conjunction. The extent to which they provide protection against the three threat scenarios can be summarized as follows:

Misconfigurations and Isolated Adversaries:
Whisper guarantees path integrity for route advertisements in the presence of misconfigurations or isolated adversaries; i.e., any invalid route advertisement due to a misconfiguration or isolated adversary with either a fake AS path or with any of the fields of the AS path being tampered (e.g. addition, modification or deletion of AS's) will be detected. Path integrity also implies that an isolated adversary cannot exploit BGP policies to create favorable invalid routes. In addition, Whisper can identify the offending router if it is propagating a significant number of invalid routes. Listen detects reachability problems caused by errors in the data plane, but is only applicable for destination prefixes that observe TCP traffic. However, none of our solutions can prevent malicious nodes already on the path to a particular destination from eavesdropping, impersonating, or dropping packets. In particular, countermeasures (from isolated adversaries already along the path) can defeat Listen's attempts to detect problems on the data path.

Colluding Adversaries:
None of our techniques can prevent two colluding nodes from pretending there is a direct link between them by tunneling packets. Moreover, colluding nodes can exploit the current usage of BGP policies to create large-scale outages without being detectable by either Listen or Whisper. To deal with this problem, we suggest simple modifications to the BGP policy engine which in combination with Whisper can largely restrict the damage that colluding adversaries can cause. In the absence of complete knowledge of the Internet topology, these two problems also exist in the case of heavy-weight security solutions such as S-BGP.

** "Towards an Accurate AS-Level Traceroute Tool." by Z. Morley Mao, Jennifer Rexford, Jia Wang, and Randy Katz. ACM SIGCOMM 2003.

About the Presenter
Lakshminarayanan Subramanian is a Ph.D. student at UC Berkeley, working under the guidance of Prof. Randy Katz and Prof. Ion Stoica. His primary research interests are in the areas of inter-domain routing and overlay networking. Previously, Lakshmi worked on the problem of characterizing the properties of Internet topology using BGP routing tables. His current work focuses on improving the security of BGP.