Security for
Wide-Area Internet Routing

by Nick Feamster

Routing is the process by which a packet is sent from one place to another. Every packet has a source and a destination, and routing is the mechanism which determines the path a packet should take in order to reach the specified destination. Routing on the Internet can be classified into two areas: local routing and wide-area routing. Local routing transports a packet to a host within particular network once it has reached that network. Wide-area routing deals with transporting a packet between networks, i.e., arcoss the Internet itself [1].

One of the burgeoning problems that has yet to be appropriately addressed from a practical standpoint is the security of wide-area Internet routing. Various research has proposed authenticated route advertisements, which I will explore below. Certain wide-area routing protocols have attempted to address some of the security issues associated with internet routing. However, some of the fundamental questions remain with respect to wide-area internet routing security, including the following:

  1. Does the issue of wide area routing boil down to a problem of authentication, or is it more fundamentally an issue of robustness? Specifically, in the context of wide area routing, is the threat really a malicious user injecting bad routes into the Internet infrastructure, or rather is it simply a problem of designing an extention to the exterior gateway protocols that is robust to operator error?

  2. Who and what are the legitimate threats in such a case? Often, the ability to do large-scale damage implies access to a backbone router; therefore, are these entities really vulnerable to "script kiddies," or should we really only be concerned with people who might have access to the Internet's backbone routers (i.e., the previously fired network administrators of large ISPs)?
The remainder of this article will begin with a brief overview of the Border Gateway Protocol (BGP), the protocol currently used as a communication between routers to disseminate routing information between autonomous systems. Next, I will explore some historical "attacks" that employ BGP. I will also consider current research in these areas, such as Secure BGP (S-BGP), and current work at Berkeley which is exploring authenticated BGP. I will conclude with a general assessment of open problems.

Overview of BGP

The Border Gateway Protocol (BGP) [6] is an exterior gateway protocol which is used to distribute routing information in the Internet. From the perspective of BGP, the Internet is partitioned into a number of autonomous systems (ASes), each of which perform their own internal routing (usually done by applying an open shortest-path first (OSPF) algorithm, such as Dijkstra's algorithm). An autonomous system is typically established as a particular administrative domain. An ISP such as BBN is AS-1; MIT is AS-3. However, link state protocols do not scale to the size of the Internet, because they require each router to have a consistent, accurate view of the entire network topology, and involve flooding, i.e., sending messages on every output link, thus generating a high amount of extraneous traffic. BGP, on the other hand, has mechanisms to prevent routing loops between autonomous systems, and it scales well because it is incremental: once routes are established, only changes (i.e., "updates" and "withdrawals") are advertised [1].

Each AS then has a BGP speaker, a router which runs the BGP routing process, which advertises all of the networks for which it has reachability information, i.e., all of the networks for which it has a path to reach. If a particular AS wants traffic to be routed to it for a given set of addresses, it then advertises those networks through a route advertisement. Similarly, an AS can also agree to be a "transit-AS": if one AS gains information about another network's reachability via another AS, it can advertise that it has reachability to that network, too, if it agrees to route packets to that network. BGP is a "path-vector" routing protocol; that is, advertisements include an attribute known as the AS-PATH, a list of ASes that much be traversed to reach the advertised network. Inclusion of the AS-PATH attribute also allows routing loops to be easily detected. Path vector algorithms such as BGP scale linearly with the number of nodes (AS's), rather than with the square of the number of nodes, as link-state protocols scale [1, 3, 4].

This section provides a very basic overview of BGP; many details have been left to other readings in the references. The basic idea is that the Internet is partitioned into administrative domains called autonomous systems, and that each AS advertises the set of networks that it knows how to reach. With this basic understanding of BGP, it's possible now to examine some of the historical attacks mounted against BGP, as well as some of the threats associated with the protocol.

Threats

Misconfiguration

There is one particularly well known example of damage that can be caused by misconfiguring a BGP peer. This occurs when a particular AS (say "AS-10") is transited by two other AS's (AS-20 and AS-30), both of which send full BGP tables to that AS. Misconfiguration occurs as follows: The upshot is that all Internet-bound traffic from any AS that is peering with AS-10 will attempt to route traffic through AS-10, thus saturating the network and making the Internet inaccessable to these peers [2].

This assumes that the AS is not performing any filtering of iBGP messages with respect to its eBGP annoucements.

Lack of Filtering

An AS can filter out certain route announcements based on certain attributes. For example, if a certain AS receives an announcement from an IP address that it does not recognize, or is not from a certain AS, then it will not accept that route advertisement. Many of the large internet service providers (ISPs), such as Sprint, AT&T, UUNet, etc., who provide access to the Internet backbone, do not filter out these routes. This is largely due to the fact that most entities obtain their Internet access from smaller ISPs (Qwest, etc.). When a smaller ISP adds a new user/network, it wants to be able to grant that user instant connectivity, and not have to tell the larger ISP that it's OK to advertise routes to these new networks. As a result, many of the larger ISPs perform no filtering of updates at all. Accepting all routes indiscriminately obviously provides potential for misconfiguration and catastrophic failure [3].

Blackholing

"Blackholing" a route essentially occurs when a particular AS announces a route to a network that that AS essentially does not have. Any peer that hears an update corresponding to a blackholed route will send packets to the AS destined for the blackholed route, and packets will be dropped. It has been asserted that blackholing is one of the most effective denial of service attacks on the internet to date [2].

One example of purposeful blackholing exists whereby an AS announces blackholed networks to peers via BGP multihop, and the next hop information (i.e., how to get to the next AS in the route) would be changed to an address which would simply drop the packets.

One particularly disturbing implication of this is that it is possible to target someone else's network and blackhole it by announcing that you have a route to their network when you in fact don't. An indication that your network has been blackholed is a sudden drop in traffic to your network.

An interesting man-in-the-middle attack can also be performed in a blackholing-type fashion, if a malicious AS announces a route that it wants to blackhole, but then establishes a machine on its internal network that performs some of the same functionality as the machine on the blackholed network. This might allow such an attack as masquerading as the machine that the end host thinks it is talking to, or simply sniffing all traffic that is sent between two end hosts.

Blackholing can be accomplished if the AS is not filtering its iBGP update messages (the situation mentioned in #1 above), or via forged BGP "UPDATE" messages.

IP Spoofing

The forging of the opening of a BGP session is extremely difficult, because responses from the spoofed interface must also be disabled. Additionally, the end host will also be expecting full BGP tables, and route flapping, the frequent addition and withdrawal of a route from the routing tables, will surely occur if the session opening is not performed properly [3].

However, it is possible to insert forged BGP "UPDATE" messages (i.e., route updates) into an existing BGP session between two peers since the only sequence number included in the UPDATE packets are the TCP sequence numbers. This means that a malicious AS could potentially spoof the BGP UPDATE messages; spoofing BGP update messages boils down to essentially performing spoofing of TCP messages. (Note that this attack is not possible against modern versions of Cisco's IOS.)

Defenses

To protect against IP spoofing, Cisco's IOS allows the use of MD5 hashes for authentication of peers, and picks random TCP ISNs, thus making the insertion of a forged update message particularly difficult.

Additionally, Stephen Kent et al. have proposed a protocol referred to as Secure Border Gateway Protocol (S-BGP), which reportedly verifies the authenticity and authorization of BGP control traffic (particularly route update and withdrawal messages); furthermore, this protocol does not induce undue overhead and is incrementally deployable.

S-BGP must be adopted by ISPs, and requires PKI support by registries that allocate AS numbers to the ISPs. The architecture employs three main techniques: PKI, attestations, and IPsec. PKI is employed to verify IP address block ownership by a given AS, the relationship of an organization and a set of AS numbers, and BGP router IDs to AS numbers. Using this infrastructure, it is possible for BGP routers to authenticate one another. Attestations essentially allow each BGP speaker that receives a route advertisement to verify that each AS along the route is authorized to advertise the route, and that the "origin" AS is authorized to advertise the given block of IP addresses. IPsec is used to provide data integrity with respect to the control information passed between two BGP speakers and also defends against replay attacks [5].

Conclusion

Security for wide-area Internet routing, specifically BGP, should be defined generally as the correct operation of BGP speakers, since any attack that inhibits this functionality could be considered successful. Specifically, a secure implementation of BGP ensures [5]: The unique aspect with regard to the security of Internet routing is that "secure" Internet routing fundamentally means "correct" Internet routing. As such, authentication mechanisms, protection against forged UPDATE messages, and similar protection are not silver bullets in any respect. In particular, correct Internet routing must prevent against the propagation of errors that can result from misconfiguration and emergent properties due to router interaction (i.e., Cisco routers with Bay routers, etc.), detecting anomalies appropriately, and generally ensuring the proper delivery of packets.

In the case of Internet routing, any operation that does not result in appropriate packet forwarding behavior can be deemed an attack. It is clear that BGP is not robust to all of these attacks; furthermore, S-BGP still fails to address misconfiguration issues (does it really matter whether a BGP speaker is authenticated or not if the operator is injecting erroneous routes into the Internet?). The challenge, then, is to devise a solution for robust wide-area Internet routing.

References

1
Balabi, Hassam. "Internet Routing Architectures". Cisco Press. Indianapolis, 2000.
2
"batz". Security Issues Affecting Internet Transit Points and Backbone Providers Blackhat Briefings, 1999. http://www.blackhat.com/html/bh-usa-99/bh3-speakers.html
Powerpoint Presentation of that talk
3
Freedman, Avi. Notes on BGP Routing. http://avi.freedman.net/bigbgp.ppt
http://avi.freedman.net/bgp102.ppt
http://www.netaxs.com/~freedman/bgp.html
4
Huitema, Christian. "Routing in the Internet". Prentice Hall.
5
Kent, Stephen, et al. "Secure Border Gateway Protocol (S-BGP) -- Real World Performance and Deployment Issues". In Proceedings of the Network and Distributed System Security Symposium (NDSS 2000), San Diego, CA, February 2000.
6
Rekhter, Y. & Li, Tony. "A Border Gateway Protocol (BGP-4)" RFC 1771, March 1995.

Last Modified:
Location: www.acm.org/crossroads/columns/onpatrol/november00.html