How To Crash the Internet

rudy_wayne writes "We know you can take down Web sites with Distributed Denial of Service (DDoS) attacks. We know that a government, like Egypt's, can shut down an entire country's Internet access. And, we thought we knew that you can't take down the entire Internet. It turns out we could be wrong. In a report from New Scientist, Max Schuchard, a computer science graduate student, and his buddies claim they've found a way to launch DDoS attacks on Border Gateway Protocol (BGP) network routers that could crash the Internet."

How is this news?

[HungryHobo]

How is this news?
we've know for years that BGP has problems.
it's broken big section of the net before.

http://en.wikipedia.org/wiki/AS_7007_incident [wikipedia.org]

Don't Panic!

[Fzz]

I was quoted briefly in the New Scientist article. Here's the longer version of what I said to the reporter.

I've taken a quick look at this paper, and at the paper describing the actual attack on BGP sessions that this paper depends on (Zhang, Mao and Wang, 2007 (reference 74 in the paper).

For many years a number of us have speculated that it might be possible to bring down large parts of the Internet by inducing sufficient churn in BGP routing. In principle, it seems it might be possible, but doing it in practice is very different. The closest we've seen in the real world was Jan 25th 2003, when the SQL Slammer worm spread worldwide in a matter on minutes. It affected about 75,000 computers, and then each constantly tried to infect more victims. This causes widespread congestion, and the worldwide BGP routing table decreased in size from about 127,000 routes to 123,000. Some of this was probably due to congestion disrupting routing sessions, and some might have been due to people deliberately disconnecting to avoid further damage. In any event, the Internet backbone survived the event unscathed, but quite a few edge sites fell off the Internet.

The attack described in the paper supposes a larger number of compromised computers (250,000), but the Internet has got bigger and routers have got faster since 2003, so likely the relative traffic levels would be similar. The attack also proposes using the targetted attack described in Zhang, Mao and Wang, and targetting specific links to create maximum effect. So it's reasonable to suppose that if such an attack were successful, the impact would be greater than the Slammer event.

So, there are two questions:

• 1. could you disrupt routing associations in the way described.
• 2. if you could, would the effects be as described in the paper.

In answer to 1: Zhang, Mao and Wang describe in their paper how to defend against such attacks - by simply enabling prioritization of routing traffic - something that is possible on most commercial routers. If ISPs do this, then it seems that the attack in the paper would be thwarted. I don't know how many ISPs do enable this, but if such an attack were seen in the wild, I'm certain most of them would.

On 2: even if you could disrupt routing associations as described, I doubt the Internet would behave as described. The simulations in the paper make a lot of simplifying assumptions, which is necessary to simulate on this scale. But in hiding all the internal topology of ISP networks, they also hide bottlenecks that would make the attack less effective. And the way they model routers queuing routes internally is simply wrong - no router has a large enough queue size to delay processing by 100 minutes, as described in the paper. As a result I have no confidence in the predictions of how the global routing system responds to this attack.

To be clear: nobody knows if it's possible to bring down the global Internet routing system. The attack in the paper probably could cause significant disruption, at least until ISPs reconfigured their routers. But I doubt the attack would be successful in the way described in the paper.

Re:How is this news?

[sseshan]

This is not the same type of attack -- the AS7007 problem was a route hijack attack.

The sigcomm paper describes a more basic route convergence issue with path vector protocols

The paper describes the use of packet loss to create a BGP session failure and the impact of repeated announce/withdraw traffic to slow other routers. This is also not new. However, the appropriate point of reference is "RFC 1266 - Experience with the BGP Protocol" (http://www.faqs.org/rfcs/rfc1266.html). Read section 9 -- this points to how packet loss results in BGP failures and points to how ensuring BGP packets have priority fixes this. This was published in 1991 :-) and is generally well known.

Similarly, I haven't read the referenced NDSS paper (http://www-users.cs.umn.edu/~hopper/lci-ndss.pdf) but I am also surprised that BGP holddown timers don't prevent some of the related route churn problems.