Securing BGP: A Case Study (4)

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.