The Internet's Achilles heel

[bascule]

The Internet is composed of thousands of Autonomous Systems (ASes) which route between each other using the Border Gateway Protocol (BGP). In recent years the size of the BGP routing table has been exponentially ballooning in size... breaking over one million entries and still continuing to grow. Even with routing hardware exponentially increasing in power, it is barely able to keep the pace with the ever-expanding size of the BGP routing table.

One major problem has been a lack of input validation on new entries in the BGP table inserted by a given AS. Several redundant or useless entries have been spotted in the BGP table, and are partially blamed for the BGP table's exponential growth. The other major problem is that any AS is trusted implicitly and is allowed to insert entries in the BGP table. This is further compounded by the fact that several vulnerabilities have been found in several key BGP implementations utilized by the Internet's routing architecture.

I certainly think the day will come when we see the release of an exploit (or worse, a worm) which can be used to compromise one or more AS routers, at which point the attacker will be free to spam the BGP routing table with malicious or garbage entries. With hardware barely able to keep pace with the requirements as is, if the BGP routing table were spammed/corrupted with a large number of malicious entries it could lead to a global Internet meltdown, at least until the compromized AS routers could be secured and the BGP table preened of malicious entries or reconstructed from scratch.

While I'm certainly not the first person to be worried about this possibility, considering few security enhancements or input validation improvements have been added to BGP since its introduction following the conversion to CIDR addressing in 1994, it certainly doesn't seem to be a problem which has been seriously addressed to any large degree.

Is anyone else worried?

[pc-0x90]

The Internet is composed of thousands ...

TLDR

----------

[bascule]

TLDR

Try this on for size:

http://forum.defcon.org/showthread.php?t=2743

[highwizard]

Thank you for that wonderful commentary, chicken little.

[bascule]

Thank you for that wonderful commentary, chicken little.

Just because the sky isn't falling right now doesn't mean it can't happen!

[yankee]

The Internet is composed of thousands of Autonomous Systems (ASes) which route between each other using the Border Gateway Protocol (BGP). In recent years the size of the BGP routing table has been exponentially ballooning in size... breaking over one million entries and still continuing to grow. Even with routing hardware exponentially increasing in power, it is barely able to keep the pace with the ever-expanding size of the BGP routing table.

I'm not sure a million is quite right. Right now I think it's around 142,000 networks. Still, that's not small. Router vendors have attacked the problem with faster hardware and quicker lookup algorithms, but they also come up with stuff like netflow. Most people think netflow's main use is to provide info re: current IP sessions, but really it's a database of current sessions so that Cisco (and Juniper) routers can search it first for active stuff before it tries to do a lookup in the full route table. The ability to export it was just a nice add-on. Back to the point--in big routers, each interface card keeps its own netflow database. When a packet comes in, the card generally only has to do a lookup in its db of current connections.

One major problem has been a lack of input validation on new entries in the BGP table inserted by a given AS. Several redundant or useless entries have been spotted in the BGP table, and are partially blamed for the BGP table's exponential growth. The other major problem is that any AS is trusted implicitly and is allowed to insert entries in the BGP table. This is further compounded by the fact that several vulnerabilities have been found in several key BGP implementations utilized by the Internet's routing architecture.

This isn't entirely true. Though probably many ISP's that accept BGP routes don't bother to validate if the given BGP neighbor is advertising only the routes their supposed to, there is a way to do this. I'm not a BGP guru, but I think it's like this in Cisco-ese:

router bgp your-AS-here
neighbor xxx.xxx.xxx.xxx distribute-list 10 in

then add...

access-list 10 permit 10.0.0.0 0.255.255.255
access-list 10 permit 11.0.0.0 0.255.255.255
access-list 10 deny any

Re: the vulnerabilities, any net admin that's not using hashing for their BGP session deserves the butt kickin' when it comes. This has been part of BGP implementations for quite some time. See RFC 2385.

[bascule]

I'm not sure a million is quite right. Right now I think it's around 142,000 networks.

You are correct, sir. I'll be sure to do my homework next time, unlike Michael Moore...

Here is a graph of the BGP table size over time:

http://bgp.potaroo.net/

Current size appears to be a little more than 170,000 entries.

Still, that's not small. Router vendors have attacked the problem with faster hardware and quicker lookup algorithms, but they also come up with stuff like netflow. Most people think netflow's main use is to provide info re: current IP sessions, but really it's a database of current sessions so that Cisco (and Juniper) routers can search it first for active stuff before it tries to do a lookup in the full route table. The ability to export it was just a nice add-on. Back to the point--in big routers, each interface card keeps its own netflow database. When a packet comes in, the card generally only has to do a lookup in its db of current connections.

Correct me if I'm wrong, but as I understand the speed of BGP table lookups, for new connections only, is barely able to keep the pace for high volume traffic periods, and that number of compromised AS routers inserting large volumes of properly crafted records could very possibly push the tables beyond the maximum size as allowed by available memory or push it beyond the ability of routers' CPUs to perform lookups on the table at a rate sufficient to handle incoming demand.

This isn't entirely true. Though probably many ISP's that accept BGP routes don't bother to validate if the given BGP neighbor is advertising only the routes their supposed to, there is a way to do this.

Problems still remain with
1. Routers which do not properly validate new BGP entries
2. Spamming the table with a large number of valid BGP routes
3. Spamming the table with routes which appear valid for a given AS, but disrupt the flow of traffic to the AS

the vulnerabilities, any net admin that's not using hashing for their BGP session deserves the butt kickin' when it comes. This has been part of BGP implementations for quite some time. See RFC 2385.

However, this can't protect against malicious BGP traffic from a compromised host/router...

[yankee]

You are correct, sir. I'll be sure to do my homework next time, unlike Michael Moore...

...nothing to add here. Well said.

Correct me if I'm wrong, but as I understand the speed of BGP table lookups, for new connections only, is barely able to keep the pace for high volume traffic periods, and that number of compromised AS routers inserting large volumes of properly crafted records could very possibly push the tables beyond the maximum size as allowed by available memory or push it beyond the ability of routers' CPUs to perform lookups on the table at a rate sufficient to handle incoming demand.

I'm not sure--or in truth, I haven't had the time or motivation to really dig into it. I would think that on nearly any routing platform you would be correct. One things for sure, if even a few AS routers are compromised, a good portion of the Ineternet could be screwed.

I've been toying with the idea of doing some research in this area (inspired by Xam's talk last year on RTT) to see variance in time between between routing SYN packets and ACK packets on netflow-able routers with large route tables. Not fully baked yet though....

Problems still remain with
1. Routers which do not properly validate new BGP entries
2. Spamming the table with a large number of valid BGP routes
3. Spamming the table with routes which appear valid for a given AS, but disrupt the flow of traffic to the AS

It think number one is the most disturbing, since it's the one the net admins might actually have control over. I'm not sure to what degree summarization would have in reducing the effects of numbers two and three. Something to think about.

[macuber]

Slammer

I believe when Slammer was released, one of the byproducts was a massive number of lookups to the root name servers....reversing the source address of all those packets hitting firewalls etc. If you bring down the internet's dns system, you have effectively brought down the internet. No one can surf anywhere or send email etc. So attacking BGP wouldn't be necessary. Now I'm sure corrective action has been taken to safeguard the root name servers since Slammer....but.....

[bascule]

I believe when Slammer was released, one of the byproducts was a massive number of lookups to the root name servers....reversing the source address of all those packets hitting firewalls etc. If you bring down the internet's dns system, you have effectively brought down the internet. No one can surf anywhere or send email etc. So attacking BGP wouldn't be necessary. Now I'm sure corrective action has been taken to safeguard the root name servers since Slammer....but.....

The difficulty and exposure in compromising AS routers is substantially less than writing a worm which performs a DDoS attack against the root servers. Furthermore, it is highly unlikely that either a bandwidth attack or bombarding NSI's servers with lookups could take them down... they're multi-homed and fault tolerant, with considerable engineering in place to prevent a DDoS from being feasible. While many of the other (volunteer run) root servers could (and have in the past) go down in the wake of a DDoS attack, as long as NSI's remain running the Internet's DNS architecture will continue to function.

[skroo]

I believe when Slammer was released, one of the byproducts was a massive number of lookups to the root name servers....reversing the source address of all those packets hitting firewalls etc. If you bring down the internet's dns system, you have effectively brought down the internet.

Not exactly. The amount of traffic it generated per link was the greater concern, not the type of traffic.

We got hit pretty hard by it at work. What we found was happening was link saturation by infected hosts to the point where routing protocols (such as BGP) were unable to communicate between links. When this hapens, the worm's effectively cutting off its oxygen supply - it keeps cranking out the traffic, but the traffic never reaches its destination because the links don't know how to route between each other. As a result, the DoS it's attempting to perform on the root name servers never takes place since the traffic can't leave the local network.

No one can surf anywhere or send email etc. So attacking BGP wouldn't be necessary. Now I'm sure corrective action has been taken to safeguard the root name servers since Slammer....but.....

No one can do anything at that point, at least not locally - note that Slammer singularly failed to take down the public Internet as was predicted it would. One solution was to write ACLs that only permitted lookups to the root name servers from designated IP addresses, namely our valid forwarding name servers. However, this still left hundreds of megabits of traffic saturating first-hop links that couldn't handle it, so disinfection and patching was ultimately the only recourse.

And don't ask why we weren't patched in the first place. I've fought this battle already and don't care to reiterate it.