Border Gateway Protocol, the Internet’s routing glue, lacks strong security says Rik Farrow

If peers aren’t checking digital signatures on the data exchanged, an attacker could inject routes that might be trusted because of their source

People have been predicting the Internet’s catastrophic fall ever since it became popular in 1995. So far, these predictions haven’t materialised. True, some localised disruptions have occurred, such as the Distributed Denial of Service (DDoS) attacks against e-commerce sites in 2000, and the DNS problems that made a few sites disappear in 2001, including Microsoft-controlled websites such as msnbc.com.

But when network engineers gather to discuss real Internet instability, Border Gateway Protocol (BGP) always comes up. BGP-4 distributes routing information between routers that interconnect different network providers, and is crucial to the Internet’s moment-to-moment functioning. But BGP-4 lacks a security design to protect the Internet’s interconnectivity.

BGP-4 does have security features, but organisations can ignore these features, or accidentally or intentionally misconfigure them, with serious consequences. This article describes how BGP works, explains its security features, and shows what can happen when things go wrong as they did in April 1997.

Routing shortcuts?
To understand BGP, you first need to understand routing and how it works. TCP/IP is a packet-switched protocol, so each time a packet arrives at a router, the router must decide the packet’s next hop that is the next connected router on the path. This process continues until the packet either reaches its final destination or is dropped.

Routers decide where to send a packet based on routing tables. The router looks up the packet’s destination address in the router’s routing table and forwards the packet to the next router accordingly. The routing table is the key, and setting up the routing table correctly is critical for network operations.

Organisations use Interior Gateway Protocols (IGPs), such as Open Shortest Path First (OSPF), to set up and maintain consistent routing table information on interior networks. Some router manufacturers set-up their newly installed routers to probe their interfaces for other routers and begin exchanging routing information with them. You can also statically define routing tables, meaning you can make entries for all the possible routes in a configuration file. In either case, you use a default route pointing to the Internet for network addresses not found in the organisation’s network.

Routers belonging to the large Network Service Providers (NSPs), such as WorldCom and Sprint, obviously cannot rely on default routes. They must have routing information for all network addresses. These routers exchange information using Exterior Gateway Protocols (EGPs), with BGP-4 the standard. To reduce the size of routing tables, Classless Internet Domain Routing (CIDR) replaced classful routing, which divided network addresses into three classes using 8-, 16-, or 24-bit netmasks. CIDR ignores the old classes and byte-oriented netmasks, and instead aggregates blocks of network addresses and assigns them to organisations or NSPs.

The CIDR blocks of network addresses are then divided into Autonomous Systems (ASs). An AS is a single organisation made of many CIDR blocks that control the organisation’s internal routing. Think of an AS as a way of abstracting large chunks of the Internet for routing purposes. Instead of having to route through an AS, BGP-4 arranges for routes to networks via the various ASs that they must transit.

ASs shorten the routes, and makes routing loops easier to detect. Each time a router receives a BGP-4 update, it can look for its own AS number in the AS_PATH (list of AS numbers in this route), and detect if there’s a loop. When a router sends out updates, the information consists of a network address prefix and the list of AS numbers. The first AS number on the list represents the next hop, which will be a router on the edge of that AS.

BGP-4: Beneficial, but not Bulletproof
Routers that “speak” BGP-4 use TCP connections to exchange information with neighbouring routers in other networks, called peers, that also use BGP-4. The TCP connections show if each peer is still up and reachable. When a peering connection is broken, each end of the connection withdraws all routes going through the now-unreachable neighbour. Also, whenever a BGP speaker learns of additional or withdrawn routes, it can share this information with its peers.

BGP-4 implementations support several security mechanisms. For example, neighbours can authenticate each other using a login and password. MD5 digital signatures are more common. In this case, an MD5 signature is included in the header information of each packet in a peering connection. Each neighbour is configured with a secret, included in the MD5 signature calculation, making it unlikely that an attacker could modify or inject information into a BGP peering exchange.

The trouble with these authentication and integrity mechanisms is that they require co-ordination between the organisations managing neighbouring routers. Also, the secrets that these mechanisms rely on are part of the router configuration, and anyone who views the configuration can learn the secrets. Finally, if an attacker breaks into a router, any routing information that the attacker injects goes over the authenticated connection. So, even if organisations use the optional authentication, the person controlling the router, or controlling another router trusted by this router, can inject misleading routing information.

Most BGP-speaking routers talk to their peers over dedicated connections so, in a way, the concept of authentication makes no sense. The interface cards in the peering routers are the only devices connected to this network. And MD5 does not authenticate routing information coming from many hops away.

Fun with filtering
The final, and most important, mechanism for protecting BGP integrity is policy-based filtering. Policy-based filtering is complex, and concerns which routing information will be accepted from (ingress) or sent to (egress) a particular neighbour.

Policy-based filtering didn’t begin as a security mechanism, but as a way to control the routes that an AS would advertise or accept. For example, imagine that your organisation is international and has its own leased lines for carrying internal traffic. Your organisation has connections to the Internet at several locations worldwide, so your private leased line does not carry traffic destined for the Internet to a single access point. In this case, your exterior routers would be running BGP-4, so your internal network has routing information about the best way to reach different networks within the Internet.

But what about the rest of the world? Do you want anybody on the Internet to be able to use your leased lines? Policy-based filtering allows you to block the advertisement of routes carrying your own AS. Your AS becomes a stub network- one that participates in the Internet, but doesn’t carry traffic destined for other ASs.

Policy-based filtering is optional. Your organisation, for example, might have a single connection to the Internet, so filtering would result in little gain. But, if you don’t handle policy-based filtering properly, amazing and embarrassing things will happen.

In April 1997, a small ISP in Florida made a mistake in configuring the router that joined its small network to Sprint. This ISP, known as AS number 7007, allowed all the routes it learned from Sprint using BGP to be exported back to Sprint as its own routes. This is easy to do, because BGP implementations can take routes from IGP and convert them into EGP routes. In this case, the IGP converted CIDR routes into classful routes. The Sprint BGP speaker wasn’t filtering properly either and began sending out updates that added AS7007 as the correct route for a portion of every CIDR block (essentially, the first class C, 24-bit-long network prefix).

This misinformation first spread through Sprint’s network, then to neighbouring NSPs, including ANS, MCI, UUNet, and others. Many routers crashed because their routing tables suddenly doubled in size (an additional route was added for each CIDR block), and the routing instability spread throughout the Internet. Remember that, when a router crashes, it drops its BGP connection with its peer, which then sends out an update withdrawing all the routes announced previously by the crashed router.

It took over an hour for the Internet to stabilise. Network managers added filters that blocked routes with AS7007. This fixed the problem until the ISP was able to solve its local problem and Sprint reconnected it to the Internet. This accident demonstrates the damage a simple routing misconfiguration can cause.

Lessons learned
NSPs have learned to be careful with their BGP route filtering. Smaller organisations can also use other tools to help them create filters. You can use routing registries, such as Merit Network’s RADB (see Resources), with free tools like the RAToolset to build BGP filters.

But does filtering solve the problem? If peers aren’t checking digital signatures on the data exchanged, an attacker could inject routes that might be trusted because of their source. Even easier, an attacker could reset the peering connection, forcing each peer to withdraw all the routes learned from its neighbour. Either attack would cause local disruption at the least.

More co-ordinated attacks would have a much broader effect. If something like a DDoS attack were used that is, if a large number of co-operating agents simultaneously subverted routers and began announcing spoofed routes an attack would cause widespread problems. Because these problems come from the routers themselves, they’re difficult to fix. Also, similar to the Internet Worm of 1988, these problems could render the Internet unusable, leaving network managers on their own to discover the source of the attack.

The defence against a distributed attack is for every BGP-speaking router to be secure against remote attacks-a tall order. At the least, system administrators must arm their routers with strong authentication and encrypted links, such as Secure Shell (SSH), whenever possible.

There have been other proposed solutions, such as including a digital signature with every AS in a routing path. This solution, proposed by BBN (www.bbn.com), relies on a non-existent PKI and requires participating routers to verify signatures on every AS in a BGP update an enormous drain on the router CPU. And this solution would not solve the problem of a distributed attack that subverted routers, because the AS numbers would still come with signatures.

In a paper presented in 1997, Arbor Network’s Craig Labovitz, and others, analysed BGP updates at Internet exchange points. They found evidence of substantially more BGP updates than were required, including many duplicates. More recently, Labovitz claims the problems haven’t gotten better. BGP-4 makes the Internet work, but it’s still not perfect, and this poses a problem that someone will someday exploit.

Rik Farrow is an independent security consultant. His website, www.spirit.com, contains security links and information about network and computer security courses. He can be reached at rik@spirit.com.

This article first appeared in Network Magazine