January 31, 2011

RPKI-Based Origin Validation Operation - The Concept Behind

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.