Towards cleaning up RPKI INVALIDs

nusenu
7 min readSep 15, 2018

--

Up until not too long ago basically no network operator actually protected herself by implementing route origin validation (ROV) to make BGP hijacking attacks harder.

Implementing ROV means that BGP prefix-origin pairs are validated against route origin authorizations (ROAs) before they are considered. An autonomous system (AS) performing ROV is less vulnerable to BGP hijacking than an AS not doing so.

Example of a ROA: The following ROA authorizes the AS13335 to announce the prefix 1.1.1.0/24 (other ASes are not authorized to announce 1.1.1.0/24 and their prefix would be flagged as INVALID if they were to announce it):

Figure 1: An example of a ROA

Motivation

ROV is gaining traction (examples: 1, 2, 3, 4, 5, 6, 7) but one problem is the amount of broken legacy ROAs that cause many INVALID prefix-origin pairs. This wasn’t a problem for the IP holders creating the incorrect ROAs in the past since there was no negative effect of broken ROAs while no one performed validation. So these old broken ROAs causing many INVALIDs are to some extend blocking wider ROV adoption.

We would like to help reduce the amount of INVALID prefix-origin pairs to lower the barrier for ROV and to reduce the management overhead for those that have already deployed ROV in their networks.
In this post we will analyze INVALIDs to answer the following questions:

  • How does the distribution of INVALIDs look like across RIRs?
  • Which ROAs cause most INVALIDs?
  • Which IP holder could eliminate many INVALIDs by modifying just a few ROAs?
  • How many entities would we have to contact to solve all INVALIDs causing unreachable prefixes?

Answers to these questions should help us to efficiently contact affected parties. Starting to clean up the INVALIDs rather sooner than later will reduce the required effort to do so (otherwise the number of INVALIDs will just keep growing).

INVALIDs we do NOT care about

As of 2018–09–14 there are more than 6700 INVALID prefix-origin pairs (IPv4 + IPv6) but how many prefixes would actually become unreachable in a ROV environment? To answer that question we filter the complete set of INVALIDs to those that actually result in unreachable IP space.

Here are a few example of INVALIDs we do NOT care about because they do not result in unreachable IP space (alternative prefix-origin pairs are covering for an INVALID).

VALID/unknown Less-specific available

Even though 5.1.0.0/23 is INVALID due to an ASN mismatch it is still reachable because it is a part of 5.1.0.0/19 (which is VALID):

Figure 2: Less-specific covers for more-specific

VALID Equally-specific available

Figure 3: Equally-specific prefix-origin pair is availalbe

Multiple VALID more-specifics available

Figure 4: Multiple more-specific cover for INVALID less-specific (100% overlap)

After filtering these cases that do not result in unreachable prefixes we are down to 2415 (IPv4:2323 + IPv6:92) prefix-origin pairs (2403 unique prefixes). This remaining set is actually unreachable in an environment that performs route origin validation.

There are also prefixes with partial reachability as seen in the example bellow, but for simplicity we consider the entire prefix (202.57.120.0/21) unreachable even though 1/2 of it is reachable. So this one is also part of the 2415 prefix-origin pairs we consider unreachable.

Figure 5: Example of a partially (50%) reachable prefix

Distribution of INVALIDs by RIR

Most INVALIDs are in the LACNIC region. This is just by the number of prefix-origin pairs, it doesn’t say anything about the size of the affected IP space, since a single prefix can be much more relevant (i.e /16) than many others (i.e. /24).

Break Down by Reason

Most of the time INVALIDs are caused by a mismatch in the announcing ASN:

Affected Prefix-Origin Pairs  Reason
1338 INVALID_ASN
1077 INVALID_LENGTH

Break Down by RIR and Reason

Number of affected prefix-origin pairs by RIR and reason:

 693 LACNIC INVALID_ASN
509 LACNIC INVALID_LENGTH
404 RIPE INVALID_ASN
334 APNIC INVALID_LENGTH
203 RIPE INVALID_LENGTH
193 APNIC INVALID_ASN
47 ARIN INVALID_ASN
31 ARIN INVALID_LENGTH
1 AfriNIC INVALID_ASN

Break down by announcing AS (top 10)

Number of affected prefix-origin pairs by announcing AS:

 180 AS14080
128 AS23650
111 AS52308
79 AS22080
64 AS35104
59 AS43554
52 AS52228
51 AS10299
46 AS264797
38 AS45774

In total there are 454 unique ASes involved (announcing unreachable INVALIDs).

Which ROAs cause most INVALIDs?

A single ROA can invalidate many prefixes at once, so we looked at how many prefixes a given ROA invalidated, because fixing them first would be more efficient than fixing other less relevant ROAs.

By fixing the top 10 ROAs on this list we could solve over 20% of INVALID prefix-origin pairs!

The listing bellow shows ROAs and how many INVALIDs they cause (this is a slight simplification since multiple ROAs can invalid the same prefix). The 5 columns bellow are:

  • number of affected prefix-origin pairs
  • RIR
  • ASN as seen in ROA
  • prefix as seen in ROA
  • maxLength as seen in ROA
 91 LACNIC  AS60458 181.214.0.0/15 24
78 LACNIC AS37692 191.96.0.0/16 24
62 LACNIC AS61440 191.101.0.0/16 24
59 APNIC AS23650 61.160.0.0/16 16
54 RIPE AS43554 5.105.0.0/16 16
52 LACNIC AS52228 152.231.128.0/17 17
41 APNIC AS4809 115.168.0.0/14 14
39 APNIC AS23650 61.155.0.0/16 16
37 LACNIC AS22080 200.112.128.0/19 19
35 APNIC AS23650 61.147.0.0/16 16
32 RIPE AS43343 78.158.160.0/19 19
30 LACNIC AS52308 190.108.32.0/19 19
30 LACNIC AS52308 181.114.192.0/19 19
30 LACNIC AS33182 179.61.128.0/17 24
30 APNIC AS45774 49.213.32.0/19 19
29 LACNIC AS22080 200.112.160.0/19 19
29 LACNIC AS10986 190.114.96.0/19 22
27 LACNIC AS52308 181.174.128.0/19 19
23 LACNIC AS10620 190.147.0.0/16 24
21 LACNIC AS7195 200.25.0.0/17 17

Notifying affected IP Holders

The natural next step (and that was our initial intention when looking at INVALIDs) would be to send out emails to affected IP holders and ask them to address the INVALIDs but although that could be automated, we believe the impact would be better, if that email came from some trusted entity like the RIR relevant to the affected IP holder instead of a random entity they never had any contact before (us).

Asking RIRs to reach out to their members also scales better since every RIR would only have to take care of their own members. A short break down of how many members each RIR would actually have to contact (this is a rough approximation since we use the AS number and not the actual IP holder to count members):

An approximation of how many members each RIR would have to contact to fix INVALIDs.

Sending these <500 emails could actually make a difference in bringing down the RPKI INVALIDs.

So here are a few questions for RIRs:

  • Are you currently monitoring the amount of INVALID prefixes resulting in actually unreachable IP space (in an ROV environment) in your region?
  • Would you be open to reach out to your affected members to inform them about their affected IP prefixes? (as has been suggested by Job Snijders before)
  • If that is not on your roadmap: Would you mind if others reach out to your affected members (in an automated way)? (single email per entity)

Should RIRs start such an outreach it is important to measure the amount of unreachable INVALIDs over time to see how effective the outreach program is. NIST’s RPKI monitor has graphs but they take all INVALIDs into account not just those that result in actually unreachable IP space in an ROV environment.

Future Steps

  • auto-generate results on a regular interval
  • add analysis based on IP space size (not just prefix-origin pair counts) — update (2018–09–25): done
  • reach out to NIST to suggest adding graphs about unreachable prefixes to their RPKI monitor

Acknowledgements and Disclaimers

  • We used RIPE NCC’s RPKI validator 3.0–313 software with ARIN’s TAL enabled.
  • Don’t take the numbers too serious, we made a few assumptions (RPKI validator 3 API documentation could be improved) and there might be some corner cases we didn’t take care of, but the results are sufficiently similar to other people’s results (Markus Weber from KPN is generating https://as286.net/data/ana-invalids.txt although there seems to be a disagreement on the prefix shown in Figure 4.) Update (2018–09–18): I’ve been in contact with Markus and he agrees with Figure 4 and plans to update his list accordingly.

Data

https://gist.github.com/nusenu/74e03bdbe9a2201dfd086f8fe9301300#file-2018-09-14-unreachable_invalids_prefix-origin-pairs-txt

--

--