Archive for 2016

Let’s have a little talk about BGP convergence.

We tend to make a number of assumptions about the Internet, and sometimes these assumptions don’t always stand up to critical analysis. . . . On the Internet anyone can communicate with anyone else – right? -via APNIC

Geoff Huston’s recent article on the reality of Internet connectivity—no, everyone cannot connect to everyone—prompted a range of reactions from various folks I know.

For instance, BGP is broken! After all, any routing protocol that can’t provide basic reachability to every attached destination must be broken, right? The problem with this statement is it assumes BGP is, at core, a routing protocol. To set the record straight, BGP is not, at heart, a routing protocol in the traditional sense of the term. BGP is a system used to describe bilateral peering arrangements between independent parties in a way that provides loop free reachability information. The primary focus of BGP is not loop free reachability, but policy.

After all, BGP convergence is a big deal, right? Part of the problem here is that we use BGP as a routing protocol in some situations (for instance, on data center fabrics), so we have a hard time adjusting our thinking to the original peering policy based focus it was designed for. In the larger ‘net, it’s not a bug that some destinations are unreachable from some sources. It’s an expression of policy, and hence it’s a feature. There are certainly times when such policies are unintentional, but unintentional/unplanned policy is policy just the same as intentional/planned policy is.

We shouldn’t declare BGP broken for doing something it’s supposed to do.

There’s another point here, as well: Some networks never converge. And that’s okay. This is, perhaps, even harder for network engineers to get their heads around. I’ve spent twenty years making sure networks converge quickly, as loop free as possible, with as little chance for failure as possible, and using the least number of resources possible. But every network in the world doesn’t always have to converge to a single view of the topology and reachability. Really!

The problem here is the micro and macro views of the world. The ‘net doesn’t converge for two reason.

First, there’s that pesky policy problem again. Policy, in the real world, never converges. There are always contradictory policies, and policies will often form bistable states. This is maddening, of course, to the mind of an engineer, but it’s just reality intruding on our little bubble. Bubbles are, after all, meant to be burst.

Second, there’s that whole CAP theorem thing in there someplace. Not many people understand the application of CAP to routing, so I’m stuffing a post or two on this on my todo list, but just remember: you can choose to a Consistent database, a database that is Accessible by every reader/user all the time, or a database that can be Partitioned. If you think about it, routing protocols are readable by every network device all the time, and they are partitioned among all the routers/intermediate systems in the network. Which means… They aren’t going to be consistent.

As in, if you feed a routing protocol enough changes often enough, it won’t ever converge—because it’s eventual consistency will always be catching up with reality. This is just the way the world is built—piling all the SDN unicorn magic in the world into routing isn’t going to solve this one, folks. On a network the size of the Internet, someone, somewhere, is always going to be changing something. This cripples BGP convergence; the ‘net never converges.

In the history of ideas, perhaps BGP shouldn’t float to the top as one of the most brilliant (and Tony and Yaakov would probably even agree with you)—but it has, on the other hand, been one of the most successful. It’s just tight enough to work often enough to rely on the connectivity as described, and it’s just loose enough to allow policies to be injected where they need to be. No such system is ever going to be “perfect.”

We could beat our heads against a wall trying, of course, but even virtual reality has physical limitations.

In part 1 of this series, I looked at the general problem of securing BGP, and ended by asking three questions. In part 2 and part 3, I considered the third question: what can we actually prove in a packet switched network. For this section, I want to return to the first question:

Should we focus on a centralized solution to this problem, or a distributed one?

There are, as you might expect, actually two different problems within this problem:

• Assuming we’re using some sort of encryption to secure the information used in path validation, where do the keys come from? Should each AS build its own private/public key pairs, have anyone they want to validate the keys, and then advertise them? Or should there be some central authority that countersigns keys, such as the Regional Internet Registries (RIRs) so everyone has a single trust root?
• Should the information used to validate paths be distributed or stored in a somewhat centralized database? At the extreme ends of this answer are two possibilities: every eBGP speaker individually maintains a database of path validation information, just like they maintain reachability information; or there are a few servers (like the root DNS servers) which act as a source of truth, and which are synchronized somehow to each AS.

Let’s discuss the first problem first. Another way to phrase this question is: should we use a single root to provide trust for the cryptographic keys, or should we use something like a web of trust? The diagram below might be helpful in understanding these two options.

Assume, for a moment, that AS 65000 has just received some information that purports to be from AS65002. How can AS65000 validate this information? Assuming AS65002 has signed this information with its private key, AS65000 needs to find AS6500’2 public key and validate the signature. There are a number of ways AS65000 could find AS65002’s key—a URI or a distributed database of some type would do nicely—but how does AS65000 actually know that the public key it finds belongs to the real AS65002?

This is a matter finding a third party that will say/validate/attest that this public key actually belongs to AS65002. Normally this is done by the third party signing the key with their private key, which can then be validated using their private key—but then you run into an infinite regress. You can’t go on checking everyone’s public key for all of eternity; you have to stop and trust someone someplace to tell you the truth about these keys. Where do you stop? The answer to this question is the key difference between a single set of trusted roots and a web of trust.

In the single set of roots (left side of the diagram), AS65000 would stop at either RIR1 or RIR2 because they are a single set of entities everyone participating in the system should trust. In the web of trust (right side of the diagram), you stop looking when you find someone you trust who trusts the person you’re receiving information from. If AS65000 trusts AS65001 to tell the truth about AS65002, then AS65001’s signature on AS65002’s certificate should be enough for AS65000 to trust the public key it retrieved for AS65002. Multiple steps through the web of trust are possible, as well. Assume AS65000 trusts AS65003, and AS65003 trusts AS65004 to tell the truth about AS65002. AS65000 might decide that because AS65003 trusts AS65004, it can trust AS65004, as well, and accept the public key for AS65002. This is a form of transitive trust, where you trust someone because you trust someone who trusts them.

There are, of course, advantages and disadvantages to each system.

In the first system, trust is rooted in an entity that can be held financially responsible for telling the truth. This often means, however, that they will charge to use their service; this additional cost can be an effective barrier to entry as the services provided by the root entity become more complex, or as the value of the system being anchored in this entity increase. The centralized repository of trust is also a risk—the certificate used by the single trusted entity is a high value target. Finally, the single trust entity is a political risk for those who operate within the system. A single contract mistake, or a single problem of any other sort, causes the value of anyone operating a network (in this case) to immediately drop to nothing. While the single root provides an easy way to prevent abuse within the system, it’s also a single place from which to abuse those within the system.

In the second, trust is not rooted in any single entity, but rather in what might be called community consensus. This type of system is more resilient to attack, but it can also be abused through shell entities and bad actors. In operating a web of trust, you can quickly run into byzantine failures which are difficult to resolve. Beyond this, the amount of processing required to validate a certificate will depend on the number of links in the transitive trust chain you have to cross before you find someone you trust to tell the truth.

Which one is better? It really comes down to business objectives rather than technical superiority. Which one better fits the kind of system being secured? Web of trust models tend to work better in smaller communities with personal relationships. Rooted trust models tend to provide more security in diverse environments where the participants are competitors.

I can see your eyes glazing over at this point, so I’ll leave the answer to the second question ’til next time.

In part 1 of this series, I pointed out that there are three interesting questions we can ask about BGP security. The third question I outlined there was this: What is it we can actually prove in a packet switched network? This is the first question I want dive in too—this is a deep dive, so be prepared for a long series. 🙂 This question feels like it is actually asking three different things, what we might call “subquestions,” or perhaps “supporting points.” These three questions are:

• If I send a packet to the peer I received this update from, will it actually reach the advertised destination?
• If I send this information to this destination, will it actually reach the intended recipient?
• If I send a packet to the peer I received this update from, will it pass through an adversary who is redirecting the traffic so they can observe it?

These are the things I can try to prove, or would like to know, in a packet switched network. Note that I want to intentionally focus on the data plane and then transfer these questions to the control plane (BGP). This is the crucial point to remember: If I start with the technical or engineering problem, I’m going to end up asking, and answering, the wrong questions.

This is typically what happens in engineering. For instance, in the world of BGP, the traditional path is to ask, “how can I secure the way BGP operates?” Another example might be, “this application needs these two servers connected via layer 2,” and then we deep dive into every potential way of providing this layer 2 connectivity, tying ourselves into knots with DCI, overlays, complex control planes, and all the rest. We never back off and say, “is this really the right question to ask?” But there is always more than one way to ask the question, and it’s important to try and find the question that draws our your thinking outside the protocol.

Creative questioning is at least half of solving any problem.

Let’s process these three questions so we can take them out of the data plane and into the control plane. The first question, in BGP terms, seems to be asking something like: Is the path this peer is advertising a valid route to the destination? What do we mean by “valid?” We mean a path that will take this traffic to the destination I’m trying to reach.

The second question, in BGP terms, seems to be asking something like: How can I be certain the destination address hasn’t been hijacked, so the peer is advertising a route to a destination that isn’t the one I’m trying to reach (even though it has the same address)? This relates directly to the origin authentication problem in BGP; can I know that the actual owner of the route is the final destination of this route?

The third question, in BGP terms, seems to be asking something like: Is the path through this peer going to pass through someone I don’t want it to pass through? This third one is actually impossible to prove in real terms. We can go some way towards ensuring traffic doesn’t go through a “man in the middle,” but there’s no way, in a packet switched network, to actually be certain of this.

In my next post on this series, I want to continue looking at this line of thinking, making certain we really understand what we can prove in a packet switched network.

This post is the second series on what I consider to be a current and difficult design problem at Internet scale that involves just about every piece of the networking puzzle you can get in to—BGP security. This is designed to be a sort of case study around approaching design problems, not just at the protocol level, but at an engineering level. I will probably intersperse this series with other posts over the coming months.

What would it take to secure BGP? Let’s begin where any engineering problem should begin: what problem are we trying to solve?

In this network—in any collection of BGP autonomous systems—there are three sorts of problems that can occur at the AS level. For the purposes of this explanation, assume AS65000 is advertising 2001:db8:0:1::/64. While I’ve covered this ground before, it’s still useful to outline them:

1. AS65001 could advertise 2001:db8:0:1::/64 as if it is locally attached. This is considered a false origination, or a hijacked route.
2. AS65001 could advertise a route to 2001:db8:0:1::/64 with the AS path [65000,65001] to AS65003. This is another form of route hijacking, but instead of a direct hijack it’s a “one behind” attack. AS65001 doesn’t pretend to own the route in question, but rather to be connected to the AS that is originating the route.
3. AS65000 could consider AS65003 a customer, or rather AS65003 might be purchasing Internet connectivity from AS65000. This would mean that any routes AS65000 advertises to AS65003 are not intended to be retransmitted back to AS65004. If, for instance, 2001:db8:0:1::/64, is advertised by AS65000 to AS65003, and AS65003 readvertises it to AS65004, AS65003 would be an unintentional transit AS in the path. This could either be intentional or a mistake, of course, but either way this is an incorrect traffic pattern that can be at the root of many problems. This is considered a route leak, and is fully described in this Internet draft.

There are a number of other possibilities, but these three will be enough to deal with for thinking through the problem and solution sets. Given these are the problems, it’s in the engineering mindset to jump directly to a solution. But before we do, let’s start with at a set of questions. For instance:

1. Should we focus on a centralized solution to this problem, or a distributed one? Then there are the in-between solutions that create a single database that’s synchronized among all the participating autonomous systems.
2. Should we consider solutions that are carried within the control plane, within BGP itself, or outside? In other words, should every eBGP speaker in the system participate, or should there be some smaller set of devices participating?
3. What is it we can actually prove in a packet switched network? This might seem like an odd question, but we are in a position where we are trying to manage traffic flows through the control plane—for instance, we are trying to prevent traffic between AS65004 and AS65000 from flowing through AS65003 in the route leak case. What, specifically, can we prove in such a case?

We’ll consider these questions, starting with the last one first, in the next post.

This post kicks off a series on what I consider to be a current and difficult design problem at Internet scale that involves just about every piece of the networking puzzle you can get in to—BGP security. This is designed to be a sort of case study around approaching design problems, not just at the protocol level, but at an engineering level. I will probably intersperse this series with other posts over the coming months.[/fusion_builder_column][/fusion_builder_row][/fusion_builder_container]