December 11, 2010

Prefix Hijacking - How to Differ Between Misconfiguration and Intention?

Today, prefix hijacking events are mainly considered from a technical point of view, rarely from a political perspective. However, especially in the context of cyberwarfare, the OSI layer 8 perspective becomes more and more important. Considering a prefix hijacking event from this perspective, an important issue is the "intention" behind the event: Did we have observe the impact of a simple configuration error or did we fall victim to an intended attack? Even if most hijacking events we have observed so far can be traced back to misconfiguration, some events were also already associated with a deliberate attack in the past.

Reasons and Implications

Most hijacking events comply with distinct patterns and indicators. However, even if these patterns, for example the number of MOAS conflicts an AS is involved with, make prefix hijacking usually easy to detect, researchers can only read little into the intention. It is not clear whether we observe a misconfiguration or an intended attack. The fact that the reasons for an event are usually hard to determine unambiguously gives opinion leaders space for interpretation or - being more critical - to substantiate their individual positions: Attackers may cloud their intention by referring to misconfiguration, media and politicians may inflate events to increase the circulation or fan fears to reinforce the own arguments.

How to Differ Between Misconfiguration and Intention?

In principle, the best solution for the problem I sketched above would be to make use of techniques like Secure BGP (S-BGP) throughout the Internet. This would allow us to protect BGP against all likely misconfiguration and attack scenarios. However, S-BGP and comparable concepts are still far from being used in production systems, most probably as a full validation of global routing information is complex, resource intensive, and difficult to deploy globally. But as cyberwarfare will become a more and more realistic scenario in the future, we should urgently become capable to differ between attacks against the routing and misconfiguration.
Focusing this subgoal, an interesting alternative to S-BGP seems to be BGP Prefix Origin Validation, a concept which is currently under discussion in the Secure Inter Domain Routing working group. The basic idea behind the draft is not to sign the whole AS-path, but only the origin. This allows ASs to validate whether an AS originating a prefix is authorized by the prefix holder to do so. Even if this limited authentication cannot prevent all possible threats to the IDR routing, it allows operators to detect the typical globally relevant configuration errors. In principle, only those wrong updates may remain undetected where the correct origin is specified. If this is the case, i.e. if a hijacker specifies an invalid next-hop or even an invalid path, prefix hijacking is most likely not a result of a simple misconfiguration. An intended attack or at least a very good explanation by the source of the hijacking event can be expected.

Benefits of Prefix Origin Validation

All in all, a simple solution allowing operators to validate whether the origin is authorized to announce a prefix has two important advantages: Firstly, those prefix hijacking events that dominate today can be effectively detected without inducing the problems comprehensive solutions come along with. Secondly, it avoids that AS operators are falsely blamed to steal Internet traffic with intent. Both aspects are highly relevant from a technical and political perspective, which argues for the solution - even if it cannot address all relevant threats.


UB

November 27, 2010

BGP Path Selection - What's the right perspective?

Using classical BGP as specified in RFC4271, the routing information a router learns from its neighborhood depends on the perspective of its BGP peers. The peer speakers provide those paths they have chosen as best path and use for traffic forwarding. Simply speaking, we can say that BGP implements a sender-based selection of advertised routing information.

Receiver-based Selection of Advertised Routing Information

A few weeks ago, I wrote about “BGP Optimal Route Reflection”, a new draft that was published a few days before the 79th IETF meeting in Beijing. In principle, the draft proposes to combine classical Route Reflection with a receiver-based selection of routing information: Instead of advertising their own best paths, reflectors shall advertise the best known path(s) according to the topological position of the client. Generally, every client may be provided with different information. Today, I read a post in the blog of Cristel Pelsser, another researcher who is working on solutions for the iBGP anomaly problems. In her post, she describes a new concept of distributed Route Servers that provide routers with customized routing information matching to their topological position. Similar to the centralized iBGP Route Server architecture we proposed in 2009, this scheme implements a received-based selection of advertised routing information. Having now at least three schemes that implement a receiver-based selection of advertised routing information, it seems that this idea attracts the interest of more and more protocol designers and researchers. Thus, let’s have a closer look at the pros and cons of the basic idea.

Advantages of a Receiver-based Selection of Advertised Paths

Realizing iBGP via a full-mesh, a router certainly learns a path that optimizes its traffic forwarding costs (the formal prove may be found in our KIVS 2011 paper). Implementing an information reduction by means of Route Reflection (or AS Confederations), this property gets lost in general. To avoid problems at this point, the routing decision of a Route Reflector must reflect the local views of its clients. This usually limits the topological size of the clusters, which forces Network Operators to set up a high number of reflectors in their ASs.
If the best path decision of a reflector is separated from the information it provides to its clients, it can be located independently of its clients. For example, as proposed by Raszuk et al., this allows operators to centralize the reflectors. In a next step, reflectors may be replaced by several party-centralized Route Servers or even by one centralized Router Server. This may reduce the effort to operate existing or establish new POPs significantly.
Taking Add-path into account, there is no reason why routers should not be provided with several paths. As we could show in 2008, providing routers with several paths that match to their topological position, routing anomalies can inherently be avoided (without affecting the semantics of iBGP), while the scalability of the routing is ensured. Thus, a receiver-based selection of advertised routing information allows us to solve the iBGP anomaly problem in practice.

Drawbacks of a Receiver-based Path Selection

Generally, a receiver-based reduction of routing information comes along with several highly interesting advantages. However, as so often in the real world, advantages come along with disadvantages: Using classical BGP, it is very easy to implement the path announcement process. In principle, a router simply determines and advertises its best path to all BGP peers that do not already know the best path. Using a receiver-based selection of advertised information, deciding which information has to be advertised to which peer is not that easy any more: The sender must see things from the receiver’s topological perspective. In general, this perspective may differ from receiver to receiver, which results in additional effort for the sender. But even if this scheme is more complicated than the classical sender-based selection of advertised routing information, the effort seems to be manageable in practice: Up to step c) of the path selection process (comparison of MEDs), routing decisions are independent of the routers’ topological points of view. The most costly sub-decisions are identical for all routers.

Next Steps

From my point of view, standardizing techniques to implement a receiver-based reduction of routing information is a logical step to ensure scalability and solve the anomaly problem iBGP comes along with. Starting with a concept that extends the functionality of Route Reflectors certainly makes it easy for Network Operators to integrate the concept in their ASs. However, the (formally provable) benefits that come along with a server-based architecture should motivate us to think about leaving the known way of Route Reflection and think about Route Servers.

November 25, 2010

What do they exactly deny??

I am sure that most people who are interested in Internet Security have heared about the prefix hijacking event that has appeared on April, 8th 2010. Triggered by a U.S. government report published at the beginning of last week, the event gained high attention in media this month. In brief: China Telecom hijacked a huge number of address prefixes for around 18 minutes. 

Plausible Denial

On wednesday last week, reuters reported that "The spokesman of China Telecom Corporation Limited denied any hijack of internet traffic". An interesting questions is what does this exactly mean? Data publicly available in the Internet and gathered from different independent ASs unambiguously show that a high number of public prefixes was hijacked by China Telecom. Of course, traffic directed to these prefixes was hijacked.

 

As it seems unlikely that China Telecom denies facts everyone could verify in principle, I belive the interpretation I found on dailytech.com seems to be most plausile: They reported that "China Telecom did not deny the incident occurred, but did deny that it intentionally 'hijacked' U.S. citizens' traffic." As described in my last post, this makes pefectly sense.

Prefixes and Traffic

Another aspect I want to mention here concerns the statement you find on several blogs and media that around 11/15/etc. percent of the Internet traffic was hijacked. From the techincal perspective this is not quite correct. Even if the order of magnitude matches the proportion of global prefixes that was hijacked, this does not mean that the same proportion of the global traffic was hijacked: Generally, the amount of traffic forwarded to different address spaces differs significantly. Details on that may be found in the Arbor Networks blog.

UB

November 18, 2010

U.S. Commission accuses China of data hijacking...

...is the title of an article published yesterday on Spiegel Online (German), one of the biggest news-websites in Germany (an article discussing this topic may also be found on cnn.com). Referring to a report published by the United States-China Economic and Security Review Commission on Wednesday, they raise the question whether a prefix-hijacking event observed in April 2010 and caused by a Chinese ISP could have been a deliberated (eavesdropping) attack against the U.S. government and U.S. companies. Even if the article does not give a final answer to this question, it suggests that this interpretation of the event is likely.

Motivated by this interpretation, I had a closer look at this event yesterday evening. The following analyses are based on the data provided by the Route Views Project. The event took place at April 8th, starting at around 3:54 p.m. UTC. At this point in time, AS23724 (China Telecom Corp. Ltd., the largest ISP in the People's Republic of China) started to originate at least 22,311 address prefixes. This is around 6.84% of the number of prefixes covered by the global routing table at this point in time. Before the event started, China Telecom originated 39 global prefixes. The events last for around 18 minutes.

From my point of view, four aspects seem to be relevant to assess the intention behind this event: Firstly, an important question is who is involved in the event. The report tells us that
, a state-owned Chinese telecommunications firm ‘‘hijacked’’ massive volumes of Internet traffic. [...]
China Telecom advertised erroneous network traffic routes that instructed U.S. and other foreign Internet traffic to travel through Chinese servers. [...]
This incident affected traffic to and from U.S. government (".gov") and military (".mil") sites, including those for the Senate, the army, the navy, the marine corps, the air force, the office of secretary of Defense, the National Aeronautics and Space Administration, the Department of Commerce, the National Oceanic and Atmospheric Administration, and many others. Certain commercial websites were also affected, such as those for Dell, Yahoo!, Microsoft, and IBM.
Even if this is indeed right, also organizations and companies from other countries were affected. Examples are France Telecom (109.211.0.0/16), Vodafone Ireland (e.g. 109.76.0.0/15), Sanyo (110.172.48.0/22), the Russian Institute for Public Networks (195.209.160.0/19), the Australian Department of Defence (203.10.234.0/24), and ChinaNet (many, many 110.x.x.x/24 networks), but also a lot of other companies and organizations could be mentioned. In fact, most parts of the "first world" were affected (the full list of Org-Names can be found here).

The second important aspect is the precision of the "attack". The event that has appeared on April 8th affected a lot of different organizations: We find the U.S. government, government organizations from other countries, business concerns from Europe, telcos from Asia, but also several other companies and organizations from many different countries. Obviously, purposefully redirecting such different kinds of traffic at the same time to the same destination does not really makes sense in practice.

Thirdly, the duration of the event should be kept in mind. 18 minutes is not that much time. It's seems not to be long enough to hijack specific information from any of the affected organizations (even if it is theoretically indeed enough time to gather IP- or mail-addresses). However, it seems long enough to identify and correct an error in the configuration.

Fourthly, China Telecom did not try to hide the prefix hijacking. In all new AS-paths, AS23724 can be identified as origin of the information announcement. After a few minutes, the event and its origin was clearly visible in the whole world.

All in all, from my point of view, an intended hijacking of network traffic is highly unlikely. I would guess that we have observed a simple but fatal configuration failure. If someone would try to hijack or eavesdrop on traffic, a plausible strategy would be to attack few prefixes that belong to one target. Most likely, the attacker would try to cloud the attack or at least its source, for example by manipulating parts of the AS-path.

However, even if we have observed most likely a simple misconfiguration event in this case, the basic problem lasts: BGP is highly vulnerable to misconfiguration and intended attacks. Most likely, a good attack could be hidden effectively today. But the report also has an upside: Politicians and the public start to become aware of the problem.

UB

Update: Of course, I am not the only one who had a closer look at the hijacking event on April, 8th 2010. Some further interesting details may be found in the renesys and Arbor Networks blogs.

October 30, 2010

IETF 79 IDR WG, what's up? Correctness, Correctness, Correctness!

Hi experts,

being concerned about the correctness of the iBGP routing, the recent days were really exciting. Certainly motivated by the upcoming IETF meeting, two new drafts focussing the correctness of the iBGP routing became available. These are the "Stable iBGP Decision Process with Route-Reflection" (available since yesterday) and the "BGP Optimal Route Reflection (BGP-ORR)" (available since 2010/10/16) drafts.

Let's have a closer look at the former draft first: The basic goal of the authors, Jamak et al., is to force stable routing decisions in ASs that implement BGP Route Reflection. To reach this, the authors proposed to prefer paths learned from close Route Reflection clusters over those learned from distant clusters. Technically speaking, they proposed to evaluate the CLUSTER_LIST length right after the LOCAL_PREF, the AS-path length, and the Origin Number (i.e. right before the MED attribute, cf. RFC4271, section 9.1.2.2). In principle, this implements the necessary condition Griffin et al. specified in 2002 to ensure forwarding correctness. So, the basic idea is well known in the scientific community and the resulting property (that is that the routing converges) is formally verified.

Even if convergence independent of any network design rules is an important property, the concept comes along with two fundamental disadvantages that - from my point of view - outweigh the advantages:
Firstly, hot-potato routing is "subverted". Let assume that as shown in figure 1, two paths p and q to the destination exist. Both paths specify the same LOCAL_PREF, AS-path length, Origin Number, peer-AS, and MED. In this case, BGP usually implements hot-potato routing, meaning that traffic is forwarded via the shortest path out of the AS (here path q). In the example I sketched below, the shortest path is the cluster-external path q from v's point of view. Since the cluster-internal paths are preferred, traffic is forwarded via path p. Unnecessary IGP costs are induced.
Secondly, ASs loose the ability to specify primary and secondary exit-/entry-points by means of the MED attribute. If the primary path for a prefix is cluster-external while a backup path for the same prefix is cluster-internal (both paths specify equivalent global path attributes), the backup path is preferred. Obviously, this is highly unwanted. To avoid this problem, Jamak et al. proposed to make use of communities, but realizing this in practice may be difficult in general.

Figure 1: Hot-potato routing does not work.

The second draft, BGP Optimal Route Reflection, is proposed by Raszuk et al.. In contrast to the former draft, the main goal of this proposal is to ensure that hot-potato routing is realized even if Route Reflection is used. Using classical Route Reflection, a reflector provides its clients with its best path. If the topological position of a client differs significantly from the topological position of its reflector, this method may cause situations where routers do not learn the closest exit-point.
In principle, this problem could be solved by using Add-path to advertise all available exit-points to a client. However, as this scheme may cause serious scalability problems in practice, Raszuk et al. proposed to provide clients only with information on their closest exit-point.
Putting aside the principal idea, a very interesting aspect of this draft is the paradigm shift it specifies. While today, the routing information a router advertises is strictly chosen from its local point of view, this drafts recommends to implement a "receiver-based" selection of advertised routing information. In principle, this selection may differ from receiver to receiver. Thinking this idea through to the end, it leads us to a Route Server based iBGP routing architecture (slides), in which every router is provided with specific routing information that ensures optimal, consistent, and stable routing decisions.
Even if ensuring hot-potato routing is an interesting feature, Raszuk et al.'s proposals is only a small step towards inherently optimal routing decisions. Indeed, unnecessary internal forwarding costs are avoided, but traffic may still be forwarded via an exit-point that specifies a suboptimal MED for its peer-AS group. Traffic may be forwarded via backup path into an AS even if the primary exit-/entry-point is available.

Even if the new drafts can sadly not entirely solve the correctness problems of iBGP, I'm really happy to see that network protocol designers working for the global players start to think about the correctness of this protocol. Its still a long path, but I am sure we are on the right way!

UB

October 24, 2010

My very first post - or: about this blog...

Hi folks,

I spent the last few minutes to think about the topic of the first post on "IDR issues". For sure, the best I could do is to use this opportunity to introduce myself and explain the basic idea behind this blog.

So, let's start with the latter: "IDR issues": what is this blog about? A brief look at wikipedia is not really helpful at this point: "Indonesian Rupiah" or "Inner Distribution Road" is not what I have really in mind with IDR. IDR stands for "Inter-Domain Routing", which - simply speaking - terms routing of global addresses in the Internet. Today, the Border Gateway Protocol (BGP) is used for that purposes.

Even if the Border Gateway Protocol works fine in principle, BGP in its current state seems not to be the answer to everything. For example, by applying common (Autonomous System-)internal BGP schemes like BGP Route Reflection and AS Confederations, routing may end up in sub-optimal or inconsistent states. Routing processes may behave non-deterministic or even non-convergent. Besides operational problems, also security problems are present: In principle, it is really easy to hijack IP address space or eavesdrop on someones global network traffic. Obviously, all these possibilities are highly unwanted and problematic. Discussing these - for many, many people highly important but yet unknown - aspects and potential problem solutions is what I want to do in this blog. So, this is another technical geek blog ;-).

After sketching the basic idea behind this blog, its a good idea to introduce myself. My name is Uli Bornhauser. I am a computer scientist at the University of Bonn, Germany, and researching in the area of the correctness and security of the Border Gateway Protocol. If you are interested in more details, you can have a look at my website.

Finally, I want to say a few words about the "comment policy". If you have any remarks or suggestions, I'm very happy to hear about them! For that purpose, you can use the "post a comment" function you usually find at the end of each post or directly send me an email. You find my email address on my website.

For the future, I plan to write new posts every few weeks. Looking forward to see you again...

UB
photo taken at "The Cell", Denver, CA, USA