When we looked at route authorization, we discussed how Resource Public Key Infrastructure (RPKI)—or more specifically, route origin authorizations—could prevent some types of BGP hijacking, but not all of it. We also mentioned that Autonomous System Provider Authorization (ASPA), a draft standard that extends RPKI to also authenticate the AS path, could prevent unauthorized networks from acting as upstreams. (For more information about upstreams, see my post on autonomous systems).

Essentially, an ASPA is a type of resource certificate in RPKI, just like Route Origin Authorizations (ROAs), which describes which ASNs are allowed to announce a certain IP prefix. However, ASPAs describe which networks are allowed to act as upstreams for any given AS.

There are two parts to deploying ASPA:

  1. Creating an ASPA resource certificate for your network and publishing it, so that everyone knows who your upstreams are; and
  2. Checking routes you receive from other networks, rejecting the ones that are invalid according to ASPA.

The first part is fairly straightforward, with RPKI software like Krill offering support out of the box. One simply has to set up delegated RPKI with the RIR that issued the ASN. I’ll give a quick overview of the process, but it’s not the main focus today.

Unfortunately, the second part is less than trivial, since ASPA is just a draft standard, not widely supported by router software. Only OpenBGPd, which I don’t use, has implemented experimental support. However, that doesn’t mean we can’t use ASPA today—we simply need to implement it ourselves. Thus, I embarked on this journey to implement ASPA filtering in the bird 2 filter language.

Publishing ASPA objects with Krill

First, you need to set up Krill. You can do so by following their install and setup instructions. I strongly suggest you use the RPKI publication server from your RIR when following the guide if possible, which should be if you received your ASN from APNIC, ARIN, or RIPE NCC. Note that you will also need to add your RIR as a parent in Krill so that they delegate to you the ability to sign ASPA objects.

Once that’s done, you can simply run a single command to create the ASPA object (see docs). For example, I did this for AS541481:

$ krillc aspas add --aspa '54148 => 835, 924, 6939, 20473, 21738, 34927, 37988, 47272, 50917, 53667'

That’s it! You can check that all your upstreams are listed with a green padlock on bgp.tools, e.g. mine. You should see a padlock to the right of the flag next to every upstream. If that’s the case, it means you have successfully deployed ASPA certification.

Validating AS paths with ASPA

Now comes the hard part of validating AS paths with ASPA. Each ASPA object only describes the upstream relationship between two networks, and we have to somehow generalize that to the entire AS path for every route on the Internet.

On the surface, this looks fairly simple. We just need to make sure every AS in the AS path is allowed to upstream the AS that comes after, right? Wrong! Or more precisely, that only works in some limited cases.

Let’s explore the three possible types of BGP peers:

  1. Downstream: A BGP downstream is only supposed to announce to you their customer cone. This means that every AS path you get from a downstream is them, followed by their downstreams, followed by the downstreams of those downstreams, etc. In this case, the naïve algorithm of checking that every ASN is allowed to upstream the next one actually works. You can also augment it by checking that you are listed as an allowed upstream for that downstream.
  2. Peer: A BGP peer is also supposed to announce to you their customer cone. In this case, a very similar situation with the downstream arises, but of course, your peer wouldn’t list you as an allowed upstream, since you aren’t allowed to announce your peer’s routes to anyone else.
  3. Upstream: A BGP upstream announces to you all the routes on the Internet. This is where things get complicated.

Recall from the post about ASes that an upstream may get its routes from a downstream, a peer, or their own upstreams, which will do the same. Now, let’s consider this hypothetical scenario:

A diagram showing the relationships between some example ASes

As before, upstream ASes are displayed above their downstreams, and a dashed line represents a peering relationship.

Let’s say that you are AS64500 and AS64501 is your upstream. If they get the route from AS64502, which is a downstream of AS64501, then:

  1. AS64501 would list AS64502 as an upstream in ASPA; and
  2. You’ll get the AS path 64501 64502, which checks out according to the naïve algorithm.

However, the trouble begins when your upstream gets the route from elsewhere. Let’s say they receive a route from their peer, AS64503, who receives it from their downstream, AS64504. Then:

  1. AS64504 would list AS64503 as their upstream in ASPA;
  2. AS64503 would not list AS64501 as their upstream; and
  3. You’ll get the AS path 64501 64503 64504. While the 64503 64504 adjacency checks out, 64501 64503 doesn’t, and thus is the naïve algorithm broken.

Now what if AS64501 receives the route from AS64505, their upstream, who receives it from their downstream AS64506?

  1. AS64501 and AS64506 would list AS64505 as their upstream in ASPA;
  2. AS64505 would not list AS64501 as their upstream; and
  3. You’ll get the AS path 64501 64505 64506. While the 64505 64506 adjacency checks out, 64501 64505 doesn’t, and thus is the naïve algorithm also broken.

The problem only gets worse if AS64505 receives the route from their peer AS64507, who receives it from somewhere else… What do we do?

Well, the AS path is just the sequence of ASes that a packet must go through to reach a certain destination. We can make the following observations:

  1. If you are the upstream of the destination, you will necessarily pass the route downstream—either to the destination, or to another AS downstream of you that’s also an upstream of the destination;
  2. If you aren’t, but you peer with the upstream of the destination, then you should pass it to that peer, who would necessarily pass it downstream;
  3. If you can’t reach the destination through a peer or a downstream, then you must pass it to your upstream; and
  4. All traffic between networks that don’t share upstreams can be reached via peering, because traffic will eventually reach a tier 1 network, and all tier 1 networks peer with each other.

This means the AS path will go upstream a number of times (including zero) and then downstream ever after, and this transition goes through at most one peering relationship.

Let A0,…,AnA_0, \ldots, A_n be the AS path of length nn. We can then introduce the concept of up-ramps and down-ramps:

  • The up-ramp is a prefix of the AS path of length uu, such that AiA_i is the downstream of Ai+1A_{i+1} for i∈[0,u−1)i \in [0, u-1), i.e. every ASN is the upstream of the preceding ASN in the sequence; and
  • The down-ramp is a suffix of the AS path of length n−dn-d, such that Ai−1A_{i-1} is the upstream of AiA_i for i∈[d+1,n)i \in [d+1, n), i.e. every ASN is the downstream of the preceding ASN in the sequence.

Let’s look at the diagram again:

The same diagram as above

We’ll consider some examples:

AS path up-ramp down-ramp
64501 64502 64501 64501 64502
64501 64503 64504 64501 64503 64504
64501 64503 64501 64503
64501 64505 64506 64501 64505 64505 64506
64501 64505 64507 64501 64505 64507
64501 64505 64507 64508 64501 64505 64507 64508

Note that the up-ramp and down-ramp can overlap on a shared upstream with the destination.

Now, of course, it’s not always possible to identify what the relationship between two ASes is from a single AS path. ASPA might tell us whether an AS could be the upstream of its neighbour or not, but a given network might not have deployed ASPA. So instead, we need to identify the longest possible up-ramp and down-ramp in the AS path. If these touch or overlap, then the AS path checks out.

For the up-ramp, its maximum length is constrained by the smallest uu such that AuA_u isn’t a valid upstream of Au−1A_{u-1}. Thus, A0,…,Au−1A_0, \ldots, A_{u-1} forms the maximum possible up-ramp.

Similarly, for the down-ramp, its maximum length is constrained by the largest dd such that Ad−1A_{d-1} isn’t a valid upstream of AdA_d. Thus, Ad,…,AnA_d, \ldots, A_n forms the maximum possible down-ramp.

Then, if u<du < d, then the largest possible up-ramp and down-ramp aren’t long enough to form the entire AS path, which means the AS path can’t possibly be valid according to ASPA.

A side effect of this implies that deploying ASPA will not just protect yourself from route hijacking, but also increase the effectiveness of every downstream at verifying upstream AS paths, since it helps constrain the length of the up-ramp. That’s quite the incentive to do so.

Implementing this for bird

While it might be tempting to dive straight into coding the logic above in bird, it’s almost impossible to write tests for bird filters short of somehow generating a bunch of routes with a different BGP implementation, and that’s just way too painful. Instead, I chose to write a version of it in Python instead.

We start with the basic data structure and some boilerplate:

from dataclasses import dataclass


@dataclass
class ASPA:
    customer: int
    providers: list[int]


class Validator:
    def __init__(self, aspas: list[ASPA]):
        self.aspas = {aspa.customer: aspa for aspa in aspas}

First, we need a function to check if an upstream relationship exists from the ASPA data:

    def is_invalid_pair(self, upstream: int, downstream: int) -> bool:
        if downstream not in self.aspas:
            return False

        return upstream not in self.aspas[downstream].providers

Then, let’s get the obvious customer case out of the way:

    def is_aspa_invalid_customer(self, my_asn: int, bgp_path: list[int]) -> bool:
        for prev_asn, asn in zip(chain([my_asn], bgp_path), bgp_path):
            # Ignore AS-path prepends
            if prev_asn == asn:
                continue

            if self.is_invalid_pair(prev_asn, asn):
                return True

        return False

Note that zip(chain([my_asn], bgp_path), bgp_path) effectively creates the pairs [(my_asn, bgp_path[0]), (bgp_path[0], bgp_path[1]), ..., (bgp_path[-2], bgp_path[-1])], and that the same ASN might be repeated multiple times consecutive in an AS path for traffic engineering.

Similarly, we can do the peering case:

    def is_aspa_invalid_peer(self, bgp_path: list[int]) -> bool:
        for prev_asn, asn in zip(bgp_path, bgp_path[1:]):
            if prev_asn == asn:
                continue

            if self.is_invalid_pair(prev_asn, asn):
                return True

        return False

This is identical to the customer case except we don’t check that we are the upstream of our peer.

Finally, the complex upstream case:

    def is_aspa_invalid_upstream(self, my_asn: int, bgp_path: list[int]) -> bool:
        max_up_ramp = len(bgp_path)
        min_down_ramp = 0

        for i, (prev_asn, asn) in enumerate(zip(chain([my_asn], bgp_path), bgp_path)):
            if prev_asn == asn:
                continue

            if self.is_invalid_pair(asn, prev_asn):
                max_up_ramp = min(max_up_ramp, i)

            if self.is_invalid_pair(prev_asn, asn):
                min_down_ramp = max(min_down_ramp, i)

        return min_down_ramp > max_up_ramp

Essentially, once we’ve seen an ASN at index i that can’t upstream the previous ASN, it means the longest possible up-ramp ends at index i. Similarly, once we’ve seen an ASN at index i that can’t be a downstream of the previous ASN, it means the longest possible down-ramp can only start at index i or after. Then, in the end, if min_down_ramp > max_up_ramp, it means the longest possible ramps don’t touch, implying that the AS path is invalid.

To ensure this code works as expected, I used the unittest standard library module to create a whole suite of tests. You can see them on GitHub.

However, there still is a problem—there is no obvious way to translate the Python code into bird filters, since the filter language doesn’t have all the convenient features of Python, and any non-straightforward translation requires testing, which we can’t do in bird. To handle this, I wrote a separate version of the filters in Python, using only the language features available in bird filters, and ran the test suite against it:

    def is_aspa_invalid_customer(self, my_asn: int, bgp_path: list[int]) -> bool:
        prev_asn = my_asn

        for asn in bgp_path:
            if prev_asn != asn and self.is_invalid_pair(prev_asn, asn):
                return True
            prev_asn = asn

        return False

    def is_aspa_invalid_peer(self, bgp_path: list[int]) -> bool:
        prev_asn = bgp_path[0]

        for asn in bgp_path:
            if prev_asn != asn and self.is_invalid_pair(prev_asn, asn):
                return True
            prev_asn = asn

        return False

    def is_aspa_invalid_upstream(self, my_asn: int, bgp_path: list[int]) -> bool:
        prev_asn = my_asn
        max_up_ramp = len(bgp_path)
        min_down_ramp = 0
        i = 0

        for asn in bgp_path:
            if prev_asn != asn:
                if self.is_invalid_pair(asn, prev_asn) and max_up_ramp > i:
                    max_up_ramp = i

                if self.is_invalid_pair(prev_asn, asn):
                    min_down_ramp = i

            prev_asn = asn
            i = i + 1

        return min_down_ramp > max_up_ramp

Now, we can translate this into bird filters:

function is_aspa_invalid_customer() {
    int prev_asn = MY_ASN;

    for int cur_asn in bgp_path do {
        if prev_asn != cur_asn && is_aspa_invalid_pair(prev_asn, cur_asn) then
            return true;
        prev_asn = cur_asn;
    }

    return false;
}

function is_aspa_invalid_peer() {
    int prev_asn = bgp_path.first;

    for int cur_asn in bgp_path do {
        if prev_asn != cur_asn && is_aspa_invalid_pair(prev_asn, cur_asn) then
            return true;
        prev_asn = cur_asn;
    }

    return false;
}

function is_aspa_invalid_upstream() {
    int prev_asn = MY_ASN;
    int max_up_ramp = bgp_path.len;
    int min_down_ramp = 0;
    int i = 0;

    for int cur_asn in bgp_path do {
        if prev_asn != cur_asn then {
            if is_aspa_invalid_pair(cur_asn, cur_asn) && max_up_ramp > i then
                max_up_ramp = i;

            if is_aspa_invalid_pair(prev_asn, cur_asn) then
                min_down_ramp = i;
        }

        prev_asn = cur_asn;
        i = i + 1;
    }

    return min_down_ramp > max_up_ramp;
}

ASPA data source

However, before you can use this, you need to define the is_aspa_invalid_pair function. My bird-filter repository contains the script make-bird-aspa, which generates a function that looks like this from the JSON output of RPKI validator, such as rpki-client or Routinator:

function is_aspa_invalid_pair(int upstream_asn; int downstream_asn) {
    case downstream_asn {
        54148: if upstream_asn !~ [835, 924, 6939, 20473, 21738, 34927, 37988, 47272, 50917, 53667] then return true;
        ...
    }
    return false;
}

To get the JSON input required, you can simply use mine at https://rpki.as54148.net/aspa.json to generate your filters.

If you want to do it yourself, you can either:

  1. Use rpki-client, which will create the json file at /var/lib/rpki-client/json. You should strive to run the latest version for ASPA support if you go this route, as the default version of 8.2 in Debian 12 (stable at the time of writing) is too old to validate any ASPAs and only the backports version works; or
  2. Follow the instructions in the Routinator documentation to deploy Routinator, which makes the output available over HTTP.

Putting it all together

Armed with these functions, you can now insert one of the following lines into your bird filter, depending on the peer type:

if is_aspa_invalid_customer() then reject;
if is_aspa_invalid_peer() then reject;
if is_aspa_invalid_upstream() then reject;

If you are using my filter library, there is a patch in the README that you can use to add ASPA support.

Conclusion

As I was writing this blog post, another route leak incident occurred, somehow managing to take down OVH in the process. ASPA likely would have helped OVH in rejecting these bogus routes and helped contain some of the damage.

It’s obvious that the Internet needed something like ASPA yesterday, and I hope this blog post will contribute to ASPA being implemented more widely.

Notes

  1. Readers might note that this isn’t AS200351 which I’ve previously been using for a while. I’ve decided to renumber my network to the new ARIN ASN 54148 for a combination of reasons:

    1. This is a 16-bit ASN, which is shorter and can be used with classic BGP communities, not just large communities, which still isn’t fully supported. A depressingly amount of Internet exchanges only support the 0:asn community to block route announcements, which can’t be used with 32-bit ASNs like 200351; and
    2. RIPE NCC just doesn’t handle inter-RIR transfers that well. First, they pestered a bunch of people to delete references to my network after the transfer, which wasn’t great, but hopefully, that shouldn’t have any long-term effects. The other thing is that they’ve somehow broken whois by not referring queries about AS200351 to whois.arin.net, but instead just returning ASN block not managed by the RIPE NCC. So if you want to see information about AS200351, you better run whois -h whois.arin.net AS200351 every time.

    So I basically got a bit fed up with this and decided to renumber to a proper ARIN ASN instead, which is why I am now running my network on AS54148. ↩