Today, a new version of the RPKI-Based Origin Validation Operation was published. This draft and the fact that origin validation will become an important feature in the next years motivated me to sketch the basic idea behind the draft and the basic concepts. It shall complete the discussion on how to differ between misconfigurations and attacks I gave seven weeks ago.
The Basic Problem
As I already discussed in several different posts before, the Inter-Domain Routing we know and use today is highly susceptible to misconfigurations and attacks. In principle, every Autonomous System which is part of the global routing may intentionally or unintentionally inject incorrect routing information. For the affected prefixes, traffic may be hijacked from some parts of the Internet and forwarded to a wrong destination. Even if filters (removing routing information that is obviously incorrect) applied by provider ASs may limit the problem, today traffic hijacking cannot be avoided effectively. Authentication schemes that would allow verifying routing information exist theoretically but are not deployed in production systems for several valid reasons.
Common Prefix Hijacking Events
Analyses of different papers as well as global routing information, for example provided by the Route Views and RIPE RIS projects, show that traffic hijacking is a common problem in the global Internet. They appear from time to time and influence the global routing varyingly strong. Having tens of thousands of ASs dealing with hundreds of thousands of IP-prefixes, such events seem to be pretty normal.
As already implied, on a high level of abstraction, prefix hijacking events can be classified in two different groups: Traffic may be hijacked intentionally, for example to blackhole or eavesdrop on the real origin AS, or unintentionally, e.g. due to a local misconfiguration. While intended attacks may obscure the fact that traffic is redirected (which clearly complicates detection), misconfiguration is usually very easy to detect: An AS that leaks incorrect paths for prefixes of other ASs into the global routing specifies an incorrect origin AS. From a global point of view, multiple Origin ASs can be observed for the same prefix, a so called BGP Multiple Origin AS (MOAS) conflict is induced: Paths visible at some ASs specify one origin (wlog. the correct one), while other paths visible at other ASs (wlog. the incorrect one) specify another origin AS. Today, caused by misconfiguration and thus not obscured, most hijacking events induce a MOAS conflict.
RPKI-Based Origin AS Validation
As MOAS conflicts are almost exclusively visible from a global point of view, they seem not to be an adequate indicator for routers to detect the common prefix hijacking events in real time. But even if they could be detected locally, a MOAS conflict does not allow a router to identify the correct and the incorrect announcement. The situation is further complicated by the fact that MOAS conflicts may have valid reasons, for example multi-homed private ASs or anycast routing. This is the part where the RPKI-Based origin AS validation comes into play.
The idea behind origin AS validation is pretty simple. Based on a PKI, owners of IP-prefixes can specify the valid origin ASs for each prefix. Stored in a distributed architecture, this information can be requested by routers: the origin AS specified in an update message can be validated. This is usually implemented at the border of an AS.
Compared to more comprehensive solutions like Secure BGP, the main advantage of this approach is that it can be deployed step-by-step: The only real requirement needed is the PKI. Having such an infrastructure, routers that support the new functionality can start to validate origins. The validation process specifies paths according to their origin AS as valid, unknown (notFound), or invalid. While it seems to be reasonable to filter out invalid paths in the long term, the result of the validation process may at first only be used to define the local preferences. As the draft states, "until the community feels comfortable relying on RPKI data, routing on Invalid origin validity, though at a low preference, may be common". Prefixes without validation data can simply be routed as today, routers that do not support origin validation simply work as today. A coordinated protocol update in the whole Internet is not necessary.
Current Status of the Infrastructure
As already mentioned, the basic requirement to implement origin AS validation is the public key infrastructure. This infrastructure will be operated by the five Regional Internet Registries (RIRs). At the current point in time, we are in a "beta phase". AfriNIC, LACNIC, and RIPE NCC have started their services at the beginning of this year, while APNIC offers this service since a while. Only the North American registry ARIN is not offering the service at the moment, however, they state that they will release the service "very early in the second quarter of 2011". Tools to validate the origin AS are also available, for example provided by RIPE NCC or (also using the RIPE tool) integrated in BGPmon.
Limits of the Concept
All in all, origin AS validation is a great step forward in solving the biggest problems of the today's Inter-Domain Routing. However, it should be kept in mind that origin AS validation cannot avoid intended prefix hijacking: Hijackers may simply specify an invalid AS-path that ends with the real origin AS. To identify and avoid this kind of hijacking, other, more complex schemes are required.
If you are rather interested in the technical than the conceptual details, you should have a look at the BGPmon blog.
Showing posts with label IETF. Show all posts
Showing posts with label IETF. Show all posts
January 31, 2011
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.
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
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. |
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
Subscribe to:
Posts (Atom)