Last August at DEFCON, Alex Pilosov and Tony Kapela presented a talk entitled Stealing the Internet: An Internet Scale Man-In-The-Middle Attack, which illustrated a technique for misdirecting specific Internet traffic via carefully constructed BGP routing messages. Using this approach, an attacker can redirect the incoming traffic of any victim through his own site for further inspection or alteration before ultimately passing it on to the victim. Furthermore, the attack can be carried out in a way that is largely transparent to the victim. Since this talk, Renesys staff have been repeatedly asked "So are people using this technique today?" That is, are people currently "stealing the Internet", and if so, who is attacking whom? Given the volume of routing data that Renesys has at our disposal and the number of tools we have to slice and dice it, we thought this would be a relatively straightforward question to answer. We were wrong.
Although we ultimately succeeded in answering the question and in developing a general Man-In-The-Middle (MITM) detection algorithm for the global Internet, we ended up writing a lot of code over the course of several months and burning through endless CPU cycles looking for attack evidence. Our results were presented this week at Black Hat and the complete presentation can be found here. In this blog, we'll hit on some of the highlights from the presentation.
Stealing the Internet
As in the infamous example of Pakistan hijacking YouTube, the MITM attack relies on the attacker announcing a more-specific of a prefix announced by the victim. Since the route to the most specific prefix wins, the attacker gets all traffic intended for that more-specific, rather than the rightful owner (victim). The new trick is to then pass the misdirected traffic to the victim in a way that is transparent to him. This is accomplished by creating a viable path from the attacker to the victim, one that is blind to the hijack and hence serves as an avenue for returning the hijacked traffic. This is accomplished by manipulating the Autonomous System (AS) paths that get passed around with each prefix announcement. Relative to the more-specific prefix used in the hijack, the attacker simply includes the ASes found on the viable path between himself and the victim, which serves to blind these ASes to his bogus announcement. This works because in order to prevent the endless circulation of routes, routers will not accept any routes that they think they've already seen. So while most of the Internet will see the attacker's hijack and act accordingly, those ASes on the path between the attacker and his victim will not, providing a pathway to ultimately return the stolen traffic on to the victim. That is a pretty fast summary, but all the details can be found in the aforementioned talks.
Looking for Clues
So the question is: Is someone snooping on your incoming traffic? How about on the traffic you send to your business partners? It turns out the first question is relatively easy to answer, while the second is extremely difficult. The reason the former is easy is because you presumably know your own network. Since the attack relies on injecting a more-specific of one of your prefixes into the global routing table, this is something you can have a route monitoring service watch for you. You cannot observe this yourself, since you are blind to the attack. However, most of the Internet is not blinded, so if a more-specific of one of your prefixes appears and you didn't authorize it, then someone else is messing with you.
But knowing if this is going on in general in the Internet is quite another matter, since no one can tell you exactly how every prefix should be appearing at any given point in time. There are over 270,000 of them and new more-specifics are constantly being announced. Which ones are legitimate and which ones are hijacks? At a glance, no one can say, since there is no central authoritative source to consult. So, it might seem that this question is impossible to answer, but a closer look gives us the clues we need.
Conveniently, the MITM attack was demonstrated at the DEFCON conference, so we had at least one known example to study. In this case, the victim was Sparkplug Las Vegas, Inc. (AS 20195), who had SWITCH Communications Group (AS 23005) as their sole provider. The hijacker was Pilosoft (AS 26627). The clues we need to automatically detect such hijacks can be found in the associated AS paths. Looking at the tail end of the relevant AS paths moments before the hijack took place, we see that they all have the following form. Namely, AS 20195 must go through its one provider, AS 23005, but from there the paths branch out to any of the several providers of AS 23005.
- 19151 23005 20195
- 22822 23005 20195
- 3356 23005 20195
Now let's look at the tails of a few relevant paths at the start of the hijack. Notice any difference?
- 3356 3561 26627 4436 22822 23005 20195
- 3549 3561 26627 4436 22822 23005 20195
- 1239 3561 26627 4436 22822 23005 20195
And there is even more.
Renesys computes the business relationships between all the ordered pairs of adjacent ASes we observe.
These fall into one of a handful of possible categories:
a customer to a provider relationship, a provider to a customer, two peers, and a few other,
less common and more complex arrangements.
If we draw the first artificial path given above with peers side by side and customers below their providers, we get the following depiction.
And this path makes no sense, as it violates the valley-free property of Internet routing. An AS in the "valley" (e.g., 26627) is transiting traffic for free, i.e., throwing money out. And while mistakes do occur, one business does not typically provide some other unrelated business with free Internet service. Similarly, multiple peering links (e.g., 4436_22822 and 3356_3561) in one path means that someone is providing free transit and thus is another red flag.
Catching the Thief
To alert on MITM attacks on the entire global Internet, we start by examining all the new more-specifics seen in a day. There will be hundreds of these to consider, and most days all of them will be perfectly legitimate. We then carefully examine the associated AS paths, looking for monkey business of the type described above. Full details can be found in our presentation. But the short answer is that we take great care not to miss any hijacked more-specifics. We assume our attacker does everything possible to cover his tracks, so we must be equally cautious in avoiding false negatives.
We ran our algorithm on all of our historical global BGP data from 1 July 2008 until 31 January 2009, sifting through tens of thousands of more-specifics and their associated millions of AS paths. After all of this, we found only three cases that passed all of our tests and looked like actual MITM attacks. One of these was the actual MITM demonstration conducted at DEFCON. Of the other two, upon visual inspection, one was almost certainly simple traffic engineering using BGP manipulation. The other was confirmed by email as a fail-over test gone awry.
The good news is that we can say with a great deal of certainty that the MITM attack is not yet appearing in the wild. In addition, we now have a comprehensive global approach for detecting it when it does ultimately make an appearance, one that rarely produces a false positive and studiously avoids false negatives. Only "lucky" corner cases on the edge of the Internet where the attacker is very close to the victim could escape all efforts at detection, but these could easily be thwarted by the victim himself.
The bad news is that we've built a global Internet that allows for such an attack in the first place. And even if you defend your incoming traffic by monitoring for suspicious BGP announcements related to your networks, you've done nothing to defend the data you send to others. To guard against interception of your outgoing traffic, the Internet would require a comprehensive global alarming system, one that alerts on any attempt to divert traffic through unusual third parties. But constructing such a system is non-trivial to get right, requiring a rich source of global BGP data and sophisticated real-time analytics. Unfortunately, short of getting everyone on the Internet to rigorously police their own networks, there simply is no other alternative. The problems outlined here are inherent in how we currently route traffic on the Internet and until we come up with a comprehensive, incremental replacement for BGP and get it widely deployed, we're going to be living with the consequences. We can either ignore the problem entirely or work toward a solution, while keeping a vigilant eye on our current increasingly wobbly trust-based system.