For two hours on Sunday, February 24, 2008, viewers across most of the world were unable to reach YouTube. The root cause of this outage was a flaw in the Border Gateway Protocol (BGP), which governs how routing data propagates across the Internet.
It all began the previous Friday when the Pakistan Telecommunications Authority ordered the nation's Internet service providers to black out a YouTube video it feared would trigger riots. Pakistan Telecommunication Company Ltd. (PTCL), Pakistan's largest Internet provider, responded by blocking the entire YouTube site through a quirk in BGP that's readily exploitable by anyone who controls a BGP-enabled router (border router) of an autonomous system (AS) such as PTCL.
As explained in RFC 4271, an AS is a network or collection of networks that "appears to other ASes to have a single coherent interior routing plan, and presents a consistent picture of the destinations that are reachable through it." Examples of ASes are the U.S. DOD's unclassified network, which is the world's largest; the Level 3 Communications backbone; and AT&T WorldNet Services. Leveraging off the interactions among the ASes, attackers can exploit flaws in BGP to deny service, reroute traffic through or to malicious hosts, expose network topologies, or even trigger instabilities that can damage vast swathes of the Internet. However, as detailed below, tools are available that can help sysadmins prevent or more easily fix these problems.
In the YouTube case, PTCL connects to the Internet solely through another AS, PCCW Ltd., a Hong Kong telecommunications company. PTCL technicians failed to warn PCCW to block the bogus route. Consequently, it spread through PCCW into the rest of the Internet.
The YouTube case was unusual because of its high profile. However, BGP blackouts of less well-known sites are common. For example, a study in 2006 found that some 200 to 1200 (between 0.2% and 1%) of the entries in a typical routing table were invalid.
On average, a bogus prefix can misroute 50% of Internet traffic, but losses may range from 0% to 100%. A prefix is a combination of a netmask and a network IP address that refers to a block of addresses. It looks something like 192.168.0/24, which is a combination of 192.168.0.0 for a network IP and 255.255.255.0 for the netmask, and points at the address block of 192.168.0.0 through 192.168.0.255.
Routing errors can be hard to detect because Internet connectivity changes often. According to a Sprint technical report, "there is continuous BGP 'noise' (around 50–200 updates/minute) interspersed with high 'churn' periods (9000 updates/minute)."
Worse, it's hard to see whether a routing change is legitimate. Most ASes try to prefer a route provided by an AS for addresses within itself, versus a route advertised by an outside source. However, BGP makes it difficult to detect routes created by outsiders, and does nothing to prevent their creation, despite the likelihood that these routes will be bogus.
The inherent complexity of BGP is another issue. Indeed, the causes of route oscillations and convergence difficulties are so obscure that researchers fail to agree on which flaws in the protocol make them possible.
Internet growth aggravates these problems. For example, from 1997 through 2005, routing tables grew from 3,000 to more than 17,000 ASes, and from 50,000 to more than 180,000 routing prefixes.
Several fixes to BGP have been proposed and rejected. In 1996, BBN Technologies proposed Secure BGP (S-BGP), which would have established a public-key infrastructure to prevent abuse of the system. Opponents said it would require routers with more memory and processing power than is feasible. The Internet Corporation for Assigned Names and Numbers (ICANN) proposed a trusted central database, but this, too, was rejected as unworkable.
An improved version of BGP is still over the horizon. Consequently, network defenders must remain alert to routing disruptions and prepared to combat them as best as possible given today's environment.
How Attackers Can Exploit BGP
Because a nation state can easily control the border routers of many ASes, both overtly and covertly, cyberwar is potentially the most serious scenario for BGP exploitation. However, any individual can get into the act by breaking into a BGP-enabled router. The Internet has many poorly managed edge networks whose border routers are more likely to suffer default passwords or remotely exploitable vulnerabilities, or allow Telnet logins.
Even without control of a border router, an attacker may send it off-path, third-party reset (RST) segments with forged source addresses of victim routers. This makes it appear as if the victim routers have gone offline, removing them from the routing table.
The TCP MD5 Signature protocol, adopted in 1998, was supposed to make it impossible to forge resets. However, discovery of mathematical flaws in MD5 and the power of today's processors mean that it only takes hours for a laptop to find a valid sequence number.
Types of BGP Attacks
- Denial of service. An attacker can black-hole portions of the Internet either by creating false routes or by killing valid ones.
In the case of YouTube, according to an analysis by Iljitsch van Beijnum, its legitimate prefix is 208.65.152.0/22, meaning the range of addresses from 208.65.152.0 to 208.65.155.255. Pakistan Telecom black-holed YouTube simply by injecting a route that pointed to a small portion of this address block, 208.65.153.0/24 (208.65.153.0 to 208.65.153.255) where YouTube had no hosts.
This caused much of the Internet's routing tables to hold two ways to reach YouTube—one legitimate, the other bogus. When the bogus route failed, it would seem reasonable for a router to try the other route. The problem is that today, when confronted by one route that maps to a subset of the other (a sub-prefix), most border routers are configured to choose the sub-prefix, and kill the prefix, regardless of the consequences.
As noted above, an attacker may also kill valid routes by sending forged packets.
- Sniffing. This requires control of a device along the path of the victim's communications. The attacker can achieve this by using BGP to detour traffic through a malicious network.
- Routing to endpoints in malicious networks. The first step is to hijack traffic away from a legitimate host and redirect it to a host controlled by the attacker. The next move in this game is to change these false route advertisements frequently. This makes it harder to detect phishing sites, futile to black-hole spam servers, and hampers law enforcement.
- Creation of route instabilities. On October 3, 2002, the UUNet segment of WorldCom's backbone suffered major outages. Later, analysts concluded that this was simply an episode of the unintentional routing instabilities that plague the Internet.
Because the causes remain poorly understood, they may blow back upon the attacker. This may deter cyberwarriors from triggering instabilities. But what if script kiddies ever popularize this means of having fun?
- Revelation of network topologies. Every BGP-enabled router possesses all the routing information of the Internet, knowledge useful for criminal operations and waging cyberwar. In theory, BGP keeps the policies underlying these interconnections private. However, most relationships among ASes are as peers (which exchange traffic at no charge to each other), customers, or providers. With patience, an attacker can use the routing table to unmask these relationships.
Researchers say that it's unnecessary to propagate all this data promiscuously. Unfortunately, no change in BGP to guard this information is imminent.
Defenses Against BGP Exploits
Defense Tactic #1: Detect False Route Announcements
- RIPE's MyASN project runs data collection points in Europe, Japan, and North America. Sysadmins can sign up to be alerted whenever changes in global routing information affect their networks.
- Renesys Routing Intelligence offers monitoring and analysis of the global routing tables.
- ASpath-tree is a free program that performs IPv6 network operation analysis based on snapshots of the BGP routing table on IPv6 routers running BGP.
- BGP Monitor is a BGP update feed from the Massachusetts Institute of Technology (MIT) border router. It includes an online, web-based search facility.
- BGP-Inspect, by Merit Network Inc./University of Maryland, offers an online, web-based research tool for BGP update messages.
Defense Tactic #2: Pretty Good BGP
In 2005, Josh Karlin of the University of New Mexico proposed to combat bogus route announcements with Pretty Good BGP (PGBGP). This simple and readily implemented improvement on BGP consists of treating all potentially malicious routes as suspicious for 24 hours, before accepting them as normal. PGBGP provides enough time to detect attacks before they can succeed, and incremental deployment provides good results.
For example, if a new prefix appears that is wholly contained within an existing prefix (as with the YouTube blackout), PGBGP would continue routing to the existing prefix and ignore the new one for a day.
Sysadmins can implement PGBGP by using the Internet Alert Registry.
Defense Tactic #3: Listen and Whisper
Lakshminarayanan Subramanian et al. have developed a combination of two techniques to cope with BGP flaws: Listen and Whisper.
- Listen detects erroneous routes by operating in the data plane of BGP, meaning situations in which a router forwards packets in a way that is inconsistent with the routing advertisements it receives or transmits.
- The problem with relying upon Listen alone is that cyberwarriors can defeat any data plane solution by impersonating legitimate end-hosts. To combat this issue, Whisper operates in the control plane of the BGP system to find false route advertisements based upon penalties chosen by detecting suspiciously long routes.
For details, see "Listen and Whisper: Security Mechanisms for BGP."
Defense Tactic # 4: An Improved Routing Protocol
Subramanian et al. propose to prevent use of BGP to reveal network topologies with their Hybrid Link-State Path-Vector (HLP) routing protocol to hide routing updates from those who should not need this information.
Their analysis suggests that HLP would cause the churn rate of route advertisements to drop by a factor of 400. Better yet, in the case of approximately 50% of links between ASes, HLP can isolate the effects of a hijacked prefix to a region 100 times smaller than that of today's BGP.
The problem with this solution is that any new protocol takes a long time and much politicking to make it into the RFCs and from there into general use.
Conclusion
An improved protocol could head off the vulnerabilities of today's BGP. In the meantime, the tactics and resources I've described above will enable sysadmins to combat BGP's problems.