Dr. AcoRed, or: How I Learned to Stop Worrying and Love BGP

by Draco Red & Jason Argonaut

"Gentlemen! You can't fight in here, this is the War Room!"--President Merkin Muffley

We're writing this in response to an article that was put out a few months ago, about the general state of security in internet routing protocols. For those of you who have invented your own mnemonic device to remember the OSI seven-layer model, you're already saying to yourself "Oh, my god--they'll kill the internet." For those of you with a little less training you'll soon learn why you should have that response to the phrase "routing protocol security". The short of it is because there is none. At all. Whatsoever.

Now many of you are likely asking, "What are routing protocols, and why should the lack of security scare me?" For those of you who know full well you can safely skip ahead, most of this will be review for you. Firstly we have the internet, which is exactly that--an inter-network network. Everything about the internet is based on the principle that they are multiple, independent networks that are linked together in such a way that traffic from any network can reach any other network. How each network is made up is irrelevant; from this view all that matters is the connections between networks. These networks can be a single point to point connection between you and your ISP's router, or they can be an entire class B license with nearly 65,000 systems connected to each other. Since we can presume that traffic will be transferred across a network somehow, we don't even need to think about the individual components, we just think of it as a "cloud."

The traffic that we normally need to get across the internet is a TCP/IP packet. Now if we think of the internet as a large telephone network, the individual substations are irrelevant, only the links between them matter to us. So for our data to be passed from one end of the network to the other it must be routed over a series of connections. In telephones this might be a connection from your home to the nearest telephone office, from there to a regional headquarters, across many other telephone companies' lines, to eventually reach the person who you want to call. And in telephones this is accomplished by a number of area indicators, starting with the country code (1-), than the area code (800-), relay code (666-), finally ending with a unique identifier (1234). On the internet it is much the same, only less tied to your geographical location, and more tied to your logical location. A standard IP address would start with a network address (192.168.) and than be followed be a unique identifier (1.1 the dots indicate the end of an 8 bit binary number, which is translated into decimal to make it easer for humans to work with). And how much of the address is taken up by the network address is specified by a subnet mask which would have all ones for a part that is taken up by network (255.255. again an 8 bit binary number translated into decimal) and all zeros for the area that can be assigned for unique identifiers (000.000).

Since the network addresses are not tied to a physical location like in the phone system they had to produce a way in which enough of the internet could be known to each router (branch office in telephone think) so that they can determine what the next step should be to transfer the packet across the multiple networks. Originally this information was entered in by hand, but as the internet grew this became increasingly impossible to maintain, so a dynamic system was developed to dispense this information. The way they came up with a system based on an "I'll tell everyone everything I know, and they'll do the same" system. This works because a router has to know about all the networks that are directly connected to it (if it doesn't than there will be no traffic going to that network), and the router can tell all other routers that are directly connected to it what it is directly connected to. These routers add this information to their routing tables (a mini-database for routing information) and than passes on that information to all the routers they are directly connected to (or directly to all known routers in Link-State protocols). Once all the routers have an equal understanding of the multiple connections than routing can be preformed at its highest efficiency. If there is any change to a link on any router this information is also passed to the neighboring routers through the same method.

The exact methods that are used to determine the path a packet will take from one point to another is determined by which routing protocol is being used but in general the shorter (fewest "hop" or cross router connections) path will be preferred over a longer path (with some exceptions depending on protocols). For the scope of this paper Link-State and Distance-Vector routing protocols will be treated the same as their differences are beyond the scope of this paper and they both follow that same general rule (again with some exceptions).

But the main reason that I say that there is no security in this system is because all routers trust the information passed on to it from any other router! This means that if my router were to tell my neighbors' routers that I am directly connected to the 216.239.32.0 network (I'm using Google's network at random) than traffic near me that was directed to the 216.239.32.0 network would be directed to my router (until my router overloaded from all the misdirected Google queries). In order to combat this, the people who own the major routers selectively choose which networks they accept routing updates from. After all if you are an ISP you would want your router in Seattle to be able to get updates from your router in L.A., but there is no reason for it to accept updates from your dial up clients (although there have been cases...). This makes it more difficult for a group of people to get together and all decide to "take over" a network as a denial of service attack on someone who they don't like. But such a thing is not impossible; in order to do it all you would have to do is hack a number of routers (since they're almost all Cisco it's easer than it sounds, trust me) and alter their routing tables (an easy way to do this is by making a number of sub-interfaces on the Ethernet ports--if you need it explained simpler than this I just won't do it.). Alternately, if you can obtain physical access to the routers' network cables it would be possible to perform a man-in-the-middle attack, in which a forged routing update packet is injected physically in between two routers (two cable ends, a hub, a single patch cable and any computer that can run Linux is all such a thing would take--provided that the router-to-router connection is Ethernet).

Ok, you say, this is small potatoes, DOS attacks against a remote network. My grandmother could do that with half as much trouble. But who is to say it has to be on a small scale? Let's take a lesson from the Blaster worm of late. Now, the rumor that I've heard is that an old version of the Cisco IOS source code has been passed around for years (Things To Do In Ciscoland When You're Dead, Phrack, Volume 0xa, Issue 0x38) and there are a goodly number of security bugs in it (this is important because Cisco IOS is the operating system used by over 60 percent of the routers out there). This is only underscored by the recent leak of 800MB of the more resent version 12.3 and 12.3t IOS source code. Now if I really wanted to mess things up I'd look for a bug that allows for remote execution of arbitrary code, much like Blaster, etcetera. A buffer overflow in the handling of one of the routing protocols (BGP would be ideal), the Cisco Discovery Protocol (CDP, a protocol that gives information about all directly connected Cisco devices), or the IOS implementation of Ping could easily spread a worm amongst Cisco IOS devises. If one were to shape the worm's payload to add a few thousand random networks to the routers routing table the amount of traffic that actually reaches its intended destination would quickly diminish so much that the internet would be unusable. And I would estimate there being thousands of programmers who could sit down today and write such a worm. And once such a worm was released it would affect the internet as a whole until all the infected routers are taken offline.

But why stop at an obscure and unusual practice such as programming routers? We could bring this fight to the end users just as easily. Many of the early worms spread by brute force attacks on a remote machine's user accounts, so why couldn't our worm have a similar effect? If we were to spread a Blaster type worm across a large number of Windows boxes that would scan random IP addresses for Cisco Routers and attempt to make a telnet and/or SSH connection into any that it finds, one could than easily produce a script that would add a few thousand random networks to the routers routing table--providing the same effect but using the much easier to hack windows boxes. There are easily hundreds of thousands, if not millions of programmers who could produce such a worm--either by altering a pre-existing worm or by writing a new one from scratch.

Now you know the problem, but what about the solution? The only true solution that I can think of is changing the entire nature of routing protocols, so that they can share information without trusting the information that they receive. Certificate based encrypted data transfer between routers has been proposed as a way to stop man-in-the-middle attacks, but will do little to stop bad information from a trusted source. A temporary fix would be a challenge response system for all routing information. Such a system can not stop this sort of attack but can minimize the damage done by it by periodically checking the information received in normal routing updates. In order to obtain the best mix of security and low resource usage a router could check, using software much like the open source Nmap, whether it is receiving accurate data based on random chance, the other router's reputation, and if there is anything unusual about the activity that that router is sending out. So it might do a light scan of a remote network occasionally on a router that has never sent out bad information before and has had no recent changes, a more strenuous scan of any new networks or routers that have been known in the past to send out faulty information, and a extremely deep scan of any router that say suddenly has a few thousand new networks, or repeatedly gives off bad information. This system, which I like to call the "Kludge" protocol--because that's all it is--would take up ever greater amounts of processing and networking resources as time go on. It would be immensely vulnerable to any worm that started to mimic host machines on a router (the honeyd daemon could be ported over the Cisco IOS and would be perfect for doing just that), but would offer the benefit of being able to send a reputation score for each router to a central repository, such as CERT, to track any large scale patterns that might arise from an on the internet.

To implement any such change would require patching a large majority of the routers on the internet, in an effort that would dwarf that of patching the Y2K bug. But, alternately, if a large scale attack were to occur before the router infrastructure could be patched, it would be relatively simple to re-write the worm responsible to patch the routers rather than infect them, but the ethics and legalities of this would seem to place it in the emergency-only department. But if we did lose routing on a global scale it would be the greatest emergency in recent times, one so great that it could cause the total collapse of western civilization.