Valid address space, bogons and martians

▼ There are some advantages to filtering out packets with invalid addresses in them. That would be a packet with a private source or destination address, for instance. Those never have any business traveling across the internet. (Not to be confused with BCP 38 filtering.) For instance, there have been instances where spammers grab an unused prefix, start announcing it in BGP, do a spam run and then drop the prefix. When packets with private addresses enter your network, bad things may happen if you use those addresses yourself. And these invalid "martian" packets are just an annoyance, using up traffic and generating log entries.

The term martian refers to packets that seem to come from Mars, as they can't come from any place here on earth. The BGP announcements for invalid address ranges are often called "bogons". I'm not sure if everyone makes that distinction, but I'll use martian for any address or address block that has a specific purpose, and that purpose means it shouldn't appear in the global routing table. IANA maintains registries of the IPv4 special purpose addresses and the IPv6 special purpose addresses. Note that some addresses are special purpose, but also globally reachable/routable. This is made explicit on the lists.

Bogons include the martians, but also any address space that is currently unused. These are the IPv4 and IPv6 full bogons lists that Team Cymru distributes. The regular, non-full bogons list has only the martians.

If you're considering filtering martians and/or bogons, it's important to realize that these lists change over time. However, martian lists are quite stable, so if you fail to update filters based on the martian lists at regular intervals, that's unlikely to result in problems. However, the full bogons lists changes daily, so it's absolutely crucial to have a solid update mechanism in place if you decide to do full bogon filtering. And note that for IPv4, the full bogons list is quite short as we're pretty much out of IPv4 space, while for IPv6 it's very long as we've barely put a dent into the IPv6 address space.

Last but not least, it's important to realize what part of the IPv4 and IPv6 address space is set aside for global unicast (= regular) use. The IPv4 address space consists of five classes:

• Class A: 0.0.0.0/1 (0.0.0.0/8 - 127.0.0.0/8), global unicast
• Class B: 128.0.0.0/2 (128.0.0.0/16 - 191.255.0.0/16), global unicast
• Class C: 192.0.0.0/3 (192.0.0.0/24 - 223.255.255.0/24), global unicast
• Class D: 224.0.0.0/4, multicast
• Class E: 240.0.0.0/4, reserved for future use

The bogons and martian lists will filter out classes D and E.

With IPv4 class E space we had the unfortunate situation that because many systems considered 240.0.0.0/4 "invalid", it was impossible to repurpose it as regular address space when we started running out of IPv4 address space. So currently, people are paying good money to obtain IPv4 address space because the RIRs don't have any anymore, but 268 million IPv4 addresses remain unused. That's $5 billion worth of IPv4 at $20 per address!

For IPv6, the situation is a bit more complex. Currently, only 2000::/3 is actually used for global unicast. So any valid (non-multicast) packet you'll see traveling across the internet starts with 2xxx: or 3xxx:. However, to avoid repeating the IPv4 class E debacle, the standards documents explicitly designate all IPv6 address space that isn't set aside for a specific different use as global unicast. From RFC 4291:

• Unspecified: ::/128
• Loopback: ::1/128
• Multicast: FF00::/8
• Link-Local unicast: FE80::/10
• Global Unicast: (everything else)

The bogons and martian lists will filter out all the non-global unicast space.

Permalink - posted 2019-11-28

Routing theory: are link state and distance vector the only games in town?

▼ During his talk about 30 years of BGP, Geoff Huston said something along the lines of "someone should come up with another type of routing protocol besides distance vector and link state". That is of course too delicious a challenge to ignore.

But what would such new routing protocol type look like? It seems really strange that there would be exactly two ways to accomplish this task, and yet, as far as I know, nobody has ever proposed something truly different. And I can't think of anything. My conclusion: distance vector and link state routing protocols, with RIP and OSPF, respectively, as the archetypical examples, are not two completely separate ways to do routing, but rather, variations of basically the same thing.

This is the information that can be relevant for routing decisions that needs to distributed to all routers:

1. Adjacencies
2. Policy restrictions
3. Metrics
4. Reachability
5. Unreachability

Link state protocol OSPF doesn't do policies, and it floods updates that convey reachability between two routers (and thus implied adjacency) along with a metric. When the reachability is lost, this information is also flooded. That means that the path the OSPF updates follow can be different from the path towards a destination.

Distance vector protocol RIP doesn't deal with the reachability between pairs of routers, but rather, the reachability towards a destination. So there is no adjacency information, nor any policy information. Rather, if there is policy, it's implemented through a filter that removes reachability information. There's also no explicit unreachability information. Unlike with OSPF, updates aren't flooded throughout the network, but propagated over the links between routers.

Because a link state protocol knows all the adjacencies and reachability of the whole network, it needs to run an algorithm like the shortest path first / Dijkstra algorithm on each router to calculate paths through the network.

A distance vector protocol uses the distributed Bellman-Ford algorithm that propagates only the local notion of the best available path to the next router, so each router only has to choose between paths advertised by its neighbors.

Now let's look at BGP. BGP is definitely in the distance vector camp, but it does add a path for easy loop detection and an explicit unreachability update (withdrawal). Policy in BGP is traditionally applied locally, by simply hiding reachability and thus adjacency information from downstream neighbors.

However, a mechanism such as RPKI can be viewed as a policy distribution system. Here, the policy information isn't distributed by flooding or passing it downstream. Rather, the information is distributed out-of-band from a (more or less) central place. The internet routing registries can be viewed as central sources of adjacency information.

So we have five types of information to distribute, and three ways to distribute it (flooding, downstream, out-of-band) as well as simply not distributing and thus not using that information at all. So that's 5 x 4 = 20 possible way to accomplish routing.

Of course many of these combinations make very little sense. However, there are certainly places where we could change an existing protocol slightly and maybe gain some benefits. For instance, what if we add the idea of flooding unreachability updates to BGP? Currently, if a BGP router loses its BGP session to a neighbor, it executes the Bellman-Ford algorithm by selecting a new path. Of course if the old and the new path have the same now unreachable adjacency in common, that's not very helpful—an update replacing or withdrawing the new path will be on its way shortly. So why not add "X has lost reachability to Y" to an update, so the next router knows to look for a new path that doesn't include the X - Y adjacency?

But I don't think that we'll be able to carve out a workable new type of routing protocol from these 20 options. So link state and distance vector it is.

Permalink - posted 2019-10-15

Securing BGP: we can do it!

▼ In this month's edition of The ISP Column Why is Securing BGP just so Damn Hard? Geoff Huston asks himself exactly this question. He lists ten reasons. I don't agree with most of them: this is a solvable problem.

I think Geoff's main point is that BGP allows for arbitrary policies, which may lead to conflicting policies in different ASes and non-deterministic results.

And then, should we come up with new security mechanisms, it's hard to get them deployed because the business case for security (or business continuity in general, see IPv6) is hard: you need to spend money to keep what you already have.

So basically, BGP gives operators too much rope so they may end up hanging themselves. Interestingly, BGP's predecessor EGP was made to explicitly support the then (early 1980s) existing topology of the internet/ARPANET: a central backbone that all networks connect to in some way. In the early 1990s, the US government wanted to get out of the business of running the internet backbone, and BGP, which was created around that time, no longer makes any assumptions about the structure of the network.

This allows for conflicting policies, such as A trying to reach C through B, while B is trying to reach C through A. Obviously A and B can't both get what they want at the same time here.

Another ten years later, the work by Lixin Gao and Jennifer Rexford showed that if all networks apply a set of simple BGP policies that encode four different types of (business) relationships between networks, then BGP will reach a stable state. Hence their aptly titled paper Stable internet routing without global coordination.

Finally, in recent years we've realized that many unintended internet routing disruptions (route leaks) are caused by networks failing to properly translate their business relationships into BGP policies. See RFC 7908 types 1 - 4.

If we were to create BGP from scratch today, it would make sense to have baked-in policies for the four possible relationships between networks rather than expect every network operator to reinvent the wheel. The protocol can then check whether both sides of a BGP session agree on the type of relationship and alert the operators if that's not the case rather than let bad things happen. This would take care of most accidental route leaks.

However, that's not the BGP we have today. So what we need to do instead is detect those route leaks and filter out the affected routing information, see my blog post on fixing route leaks for an idea on how to extend RPKI to do this. With such an extension in place, RPKI can fix all six types of route leaks mentioned in RFC 7908.

That leaves the intentional BGP hijacks, that manipulate the BGP AS path to avoid the RPKI checks. BGPsec can fix this, but unfortunately that protocol is very heavy weight and it doesn't provide many benefits in partial deployment, so it's hard to see how the whole internet is going to adopt BGPsec.

But as more networks apply stringent (extended RPKI-based?) checks, there will be fewer and fewer places where rogue networks will be able to inject false AS paths and get away with it. Contiguous parts of the internet that perform these checks will thus be protected. That last part is crucial, because "boil the ocean" type solutions, which require the entire internet to adopt the solution before we gain any benefits, are a non-starter.

However, there is one last thing we should look at: rogue networks connecting to other networks using another network's AS number. That's a hefty investment in time and money for an attacker to be able to inject false information into BGP, but with other avenues closed this could start happening.

In conclusion: after more than two decades of experience and research, we understand BGP much better and we have a good idea of what needs to be improved. RPKI is a relatively successful example of a BGP security mechanism, while BGPsec is an example of something that's on the one hand too ambitious and on the other hand doesn't fix any immediate problems (i.e., route leaks). So I think we're in a good position to improve BGP security significantly over the next few years.

Permalink - posted 2019-09-20

Be gone, AS_SETs!

▼ As I was writing my RPKI path validation draft last week, I considered the issue of filtering BGP AS paths with AS_SETs in them.

For those of you who haven't read the BGP specification recently, the idea is that if a BGP router takes a bunch of prefixes and aggregates these into a single prefix, it then adds the AS numbers in the AS paths of the original prefixes to the AS path of the new prefix in the form of an AS_SET. The AS_SET has all the AS numbers in it so loops can be detected, but for the purposes of comparing the AS path length, the AS_SET counts as a single AS hop, regardless of the number of ASes in the AS_SET. (Or the router can leave out one or more ASes and then set the ATOMIC_AGGREGATE attribute instead.)

I think aggregation was added to BGP-4 as a way to start shrinking the BGP table while BGP-3 was still in use. BGP-4 added Classless Inter-Domain Routing (CIDR), allowing it to advertise (for instance) 16 class C networks to be advertised as a /20 prefix.

However, aggregation is the easy part, you also need to get rid of those original unaggregated prefixes (the 16 class C /24s in the above example). As these may also be advertised over other paths, that's very difficult. As such, there's really not much point to this type of aggregation, and thus, no point to using AS_SETs. In fact, I didn't even mention them in my book.

Turns out that I'm not the only one who feels AS_SETs are unnecessary: there's an RFC saying the exact same thing: RFC 6472.

Of course this being the internet, the fact that AS_SETs are of no use doesn't mean people don't use them. This is what I got from RouteViews just now:

>route-views>sh ip bgp | incl {
 *   5.28.128.0/20    203.181.248.168    0 7660 2516 3356 1299 12849 {12849} i
 *   5.28.144.0/22    203.181.248.168    0 7660 2516 3356 1299 12849 {12849} i
 *   5.39.176.0/21    203.181.248.168    0 7660 2516 3356 8530 {198753} i
...

There's currently 377 out of 803582 prefixes with AS_SETs in them in the global IPv4 routing table (0.046%), and 31 of 73138 in the IPv6 BGP table (0.042%).

Note that you can filter on an AS in an AS_SET with a Cisco BGP AS path regular expression like _8111_. The _ also matches the { and } that surround an AS_SET as well as the commas separating AS numbers in an AS_SET. However, if you filter a customer's AS path like this, as I always recommend:

^(65537_)+$

it won't work, as there is nothing to match the { in this regular expression. Which is fine, there's really no good reason to use AS_SETs.

Permalink - posted 2019-06-24