Information about http://www.cs.cmu.edu/~dwendlan/papers/grassroots.pdf
(R)Evolutionary Bootstrapping of a Global PKI for Securing BGP Yih…
Tags: address space, adrian perrig, bootstrapping, brian weis, cisco systems, cmu, cylab, david mcgrew, dfn, ebay, evol, geant, internet registries, mutual dependency, originations, pki, prefixes, public key infrastructure, wendlandt, yih,Pages: 6
Language: english
Created: Thu Nov 9 05:11:46 2006
Display cached document
Page 1
Page 2
Page 3
Page 4
Page 5
Page 6
(R)Evolutionary Bootstrapping of a Global PKI for Securing BGP
Yih-Chun Hu David McGrew Adrian Perrig Brian Weis Dan Wendlandt
UIUC Cisco Systems CMU / CyLab Cisco Systems CMU / CyLab
A BSTRACT IANA
Most secure routing proposals require the existence of
a global public-key infrastructure (PKI) to bind a pub- RIPE ARIN
lic/private key-pair to a prefix, in order to authenticate Sprint
GEANT AT&T
route originations of that prefix. A major difficulty in se-
cure routing deployment is the mutual dependency be- HP IBM XO CMU
tween the routing protocol and the establishment of a DFN
globally trusted PKI for prefixes and ASes: cryptographic EBay
mechanisms used to authenticate BGP Update messages Figure 1: Example prefix PKI structure proposed by S-BGP. IANA is
require a PKI, but without a secure routing infrastructure the sole trust root, and each entity in the figure signs the certificate of
in place, Internet registries and ISPs have little motivation the entities connected to them from a lower level of the hierarchy. This
process mirrors the delegation of IP address space.
to invest in the development and deployment of this PKI.
This paper proposes a radically different mechanism
to resolve this dilemma: an evolutionary Grassroots-PKI
that bootstraps by letting any routing entity announce and that all participants use IANA's public key to au-
self-signed certificates to claim their address space. De- thenticate other certificates regarding prefix ownership.
spite the simple optimistic security of this initial stage, we When IANA delegates IP address space to ARIN, it is-
demonstrate how a Grassroots-PKI provides ASes with sues a certificate signing ARIN's public key and the IP
strong incentives to evolve the infrastructure into a full address space, which indicates that ARIN can rightfully
top-down hierarchical PKI, as proposed in secure routing use and delegate those address blocks. Similarly, ARIN
protocols like S-BGP. Central to the Grassroots-PKI con- will sign AT&T's public key and address space delega-
cept is an attack recovery mechanism that by its very na- tion, etc. Some secure routing protocols also need cer-
ture moves the system closer to a global PKI. This admit- tificates for each AS, which can be achieved through an-
tedly controversial proposal offers a rapid and incentive- other PKI rooted at IANA, but with certificates binding
compatible approach to achieving a global routing PKI. an AS number to a public key. In this paper, we focus
on creating a PKI for verifying route originations, which
prevents route hijacks, the most prevalent type of routing
1 I NTRODUCTION attack and misconfiguration on the Internet today. While
The Border Gateway Protocol (BGP) is deployed as the not discussed in detail, creating a PKI to bind public keys
main interdomain routing protocol of the Internet. As de- to ASes can benefit from the same "grassroots" approach
scribed by RFC 1771 all routers in all Autonomous Sys- advocated in this paper.
tems (ASes) are trusted. However, as the Internet has S-BGP and soBGP [14] both require a global PKI for
grown, this ubiquitous trust assumption has been proven AS numbers and prefix ownership in order to provide se-
problematic. For example, in the "AS 7007 incident" curity guarantees. While S-BGP proposes a PKI with a
one ISP announced short paths to all destinations [10] single root at IANA, soBGP also considers a scenario
which caused a wide-spread outage of network connec- where a root of trust is formed by large ISPs signing and
tivity. Clearly, given the importance of the Internet today, trusting each other's certificates. The more recent SPV
we need a more secure routing infrastructure to prevent a protocol [6] simplifies the PKI requirement slightly by
single ISP from being able to cause global damage. not requiring per-AS certificates, but still needs a global
Researchers have proposed several protocols to secure IP address space PKI to authenticate routing announce-
BGP [3, 6, 8, 15]. Most of these protocols require that ments.
routers authenticate the owner of a network prefix. For Unfortunately, setting up such a global PKI is challeng-
example, S-BGP proposes to authenticate prefixes using ing. It requires a significant up-front investment by par-
a PKI that is rooted at IANA [8], as Figure 1 shows.1 ties like IANA to manage the private keys, organize out-
The idea is that IANA is the trusted root of the PKI, dated and incomplete registries, and issue certificates to
1 IANA is empowered to allocate address space, but they contract the ASes. Secondly, all participants need to agree upon and
actual task to ICANN. Thus, while we assume IANA as the logical root trust a particular root certificate authority (CA); creating
of the PKI, this task may well be delegated to another entity. a significant point of contention that can stall adoption.
1
While these requirements are by no means insurmount- feel this approach is promising, as it drives a network to
able, centralized entities like IANA face little pressure be as secure as it needs to be.
from ISPs to make progress, because no secure rout-
ing protocol that requires these certificates has been de- 2 R ELATED W ORK
ployed. This highlights the mutual dependence between Mechanisms to Authenticate Public Keys:
the adoption of a new secure routing protocol and the The most common PKI in use today is managed by
existence of a routing PKI. Stated another way, an AS corporate CA's like Verisign, who issue public key cer-
currently has little demand for an IANA-signed address tificates used by servers for SSL/TLS-enabled protocols
space certificate, because other ASes do not currently run like HTTPS. With HTTPS the browser authenticates the
a routing protocol that chooses routes based on these cer- server by verifying that the server's public-key is signed
tificates. Yet operators will not adopt and deploy soft- by the key of a "trusted root CA". However, due to the
ware for a secure routing protocol if its security benefits large number of online entities that must be verified and
depend entirely on a non-existent PKI. cost constraints, CAs can traditionally perform only light-
We propose evolutionary incremental deployment as weight identity checks before issuing certificates. In fact,
a revolutionary approach to bootstrap a secure routing there exists a known case where a hacker obtained a cer-
protocol: initially, prefix owners generate and use self- tificate signed for Microsoft [1]. Additionally, because of
signed certificates, completely without the need for a cen- a focus on usability over security, current web browsers
tralized PKI. As adoption increases, more trusted parties contain root key certificates from over 30 different CA's.
(e.g., tier-1 ISPs) can sign these certificates to resolve Having a large root of trust weakens the security of the
any conflicts and provide added robustness for partici- overall system, because an attacker that compromises a
pants, still without requiring the involvement of central- single CA can forge any web site. This demonstrates that
ized registries. Finally, driven by a desire to reduce the while having many different trust roots eases usability
risk of having distributed points of trust, the system may and adoption, it lacks the strong security desirable in a
reach the point where demand for centralized authentica- full routing PKI.
tion motivates action by actors such as IANA. More flexible and inexpensive mechanisms for estab-
In this paper, we study how to overcome this interde- lishing trust without a centralized authority also exist to-
pendence problem and the lack of incentives for networks day. The web of trust in pretty-good privacy (PGP) au-
to deploy secure routing. We suggest a Grassroots-PKI: thenticate public keys based on a graph of mutual trust re-
an evolutionary approach to deploy a global routing PKI lationships [16]. Unfortunately, the security of such trust
that will enable the deployment of a secure routing pro- paths quickly deteriorates even for extremely small num-
tocol. Our goal is to provide a viable deployment path bers of links [12]. Alternately, the SSH protocol supports
from no security in routing to a highly secure routing in- a "leap-of-faith" authentication model, in which users ac-
frastructure. We consider the three transitions from no cept an unauthenticated key upon first connecting to a
deployment to small deployment, from small deployment server, and use this key to verify all subsequent connec-
to large-scale deployment, and from large-scale deploy- tions. While it offers no security for the first connection,
ment to global deployment. further communication enjoys significantly improved se-
To achieve a viable deployment strategy, we need to curity and the simplicity of this model is widely recog-
provide incentives for ISPs and network administrators to nized as a reason SSH saw quick and widespread adop-
follow each transition. Clearly, the evolutionary approach tion.
does not provide as much security as an immediate global A grassroots PKI will require the ability to merge
deployment of secure routing. However, the evolutionary separate smaller PKIs into a single larger PKI. One of
approach significantly reduces deployment barriers and the largest efforts to build a PKI with many adminis-
is strictly better than the absence of routing security. Our trative entities was the Automotive Network Exchange
approach provides improved security for some networks (ANX) [11]. A central goal of ANX was to bridge trust
and worse security for none. If this scheme delayed the between the PKIs of the member sites. For the member
adoption of a global secure routing PKI, one could ar- sites to communicate securely, various ISPs also needed
gue that it was detrimental to the greater good. However, to participate in the PKI. For various reasons, ANX did
quite the opposite is true: the grassroots PKI is specifi- not fully deploy. One of these reasons seems to be the
cally designed to hasten the advent of global routing se- difficulty in setting up the trust between all of the mem-
curity, by providing powerful incentives to participate in a bers simultaneously.
routing PKI. Specifically, we provide extremely low bar- Finally, similar to BGP, securing DNS exhibits a de-
riers to joining the PKI, by letting any prefix-owner an- pendency on PKI deployment, because DNSSEC requires
nounce a key. Additionally, we design the deployment a hierarchical PKI mirroring domain name delegation in
path such that when an attacker illegitimately originates a order to authenticate DNS records. Top-level domains
route, the recovery process inevitably moves the routing (TLDs) like .com need to publish public keys and sign
infrastructure toward a secure global PKI hierarchy. We certificates for sub-domains before that sub-domain can
2
provide secure DNS responses. To circumvent this de-
GEANT HP IBM XO CMU
pendency, a recent proposal called DNSSEC Lookaside
Validation (DLV) [13] permits domain keys to be signed DFN EBay
by non-TLD "trust anchors" prior to the existence of a
full PKI. Figure 2: The flat distribution of trust with self-signed certificates. The
top five entities are trust roots with self-signed certs, while DFN and
PKIs for Secure Routing: EBay has certificates signed by their ISP's self-signed certificate.
S-BGP proposes a single PKI root at IANA and a struc-
ture that mirrors address delegation. It allows for incre-
mental deployment, but accepts a path as "secure" only intermediate steps en-route to a full PKI: first, indepen-
if the prefix ownership and AS-path can be completely dent simple PKIs based on self-signed certificates; and
verified. This requires each AS in the AS-path to have second, small hierarchies of independent complex PKIs
an IANA-rooted certificate before a particular announce- that certify their customers. For each case, we discuss
ment is considered secure. Therefore, S-BGP does not how to reduce the associated security risks while simulta-
allow for incremental deployment of the authentication neously providing incentives for adoption. At each step,
infrastructure. ASes have strong economic motivation to participate and
The soBGP effort proposes a PKI that is incremental any successful attacks will automatically drive the infras-
by nature, where a PKI is generated based on which enti- tructure toward a global PKI. Thus, our evolutionary ap-
ties participate and whom the participants choose to trust. proach begins with scattered trust points, and culminates
However, it recommends no particular structure for that in a global PKI with universal trust. Though we share the
PKI, nor does it provide a design specifically aimed at same final goal as previous routing PKI proposals, this
incentivizing participation in the PKI. bottom-up approach can greatly accelerate the process.
The SPV protocol suggests leveraging identity-based
cryptography (IBC) [2] to simplify certificate distribu- 3.1 Self-signed Prefix Certificates
tion. SPV uses the prefix as a public key, requiring the The administrative entities controlling authorization (i.e.,
prefix owner to contact a root CA to obtain the corre- the Regional Internet Registries (RIRs) or large ISPs)
sponding private key.2 However, before any routing in- may or may not initially participate in a secure routing
formation can be authenticated, SPV still requires that all PKI. Even if they do, the chain of trust extending from
participants trust the global CA, that the CA can identify these entities may not follow the existing address autho-
the legitimate owners of each prefix, and that all partici- rization infrastructure, because it is likely that some ASes
pants possess the CA's public key. lower in the hierarchy will want to adopt even though en-
tities above them in the delegation chain are not yet par-
3 A S TEP - WISE A PPROACH FOR B OOT- ticipating. Therefore, the PKI for a secure BGP routing
STRAPPING A ROUTING PKI infrastructure should be prepared to begin simply, for ex-
ample, by dealing with several trust roots [9].
Establishing a large PKI for the 20,000+ organizations We propose a grassroots-PKI, where anyone can start
involved in BGP routing is a daunting challenge, even disseminating a self-signed certificate for a prefix, dras-
when compared to initiatives like ANX (mentioned in tically lowering the complexity and cost of participation.
Section 2) which have struggled with deployment. More- With no verification process required to claim a prefix,
over, the heterogeneity of entities in the Internet is sig- this revolutionary approach has seemingly severe secu-
nificant, as ISPs span continents, languages, political ide- rity failures. However, this initially loose structure can
ologies, and cultures and no single entity can mandate rapidly transition to a high-security global PKI because
a solution. These impediments suggest that the establish- any attack makes the network more secure as a result--
ment of a PKI will not occur overnight and that individual thus, malicious actors are placed in a quandary where the
actors must have strong economic incentives to overcome best attack strategy may actually be to not attack at all!
these barriers to participation. An evolutionary approach Furthermore, as we outline below, simple rules can as-
to building a global PKI can minimize these hurdles while sure that new vulnerabilities are not introduced into the
still achieving strong security as an end result. routing system during this incremental process.
In this section, we present a multi-phased, evolution- In this stage, an AS may unilaterally decide to sign and
ary approach for establishing a global PKI. We start out announce a key for each of its prefixes without any exter-
assuming an Internet with mutually distrusting entities, nal coordination, or any ISP may use its own self-signed
with the goal of achieving a global PKI that enables any certificate to delegate prefix ownership to customers. Fig-
participant to authenticate any prefix.3 We suggest two ure 2 shows an example of small independent trust realms
2 Some people believe that identity-based cryptography obviates the
using self-signed certificates.
need for a trusted CA, which is unfortunately not the case.
ASes must simply disseminate these prefix public-key
3 As discussed earlier, a similar "grassroots" concept could also help certificates and use the corresponding private key to sign
the adoption of a global AS PKI, if required by the routing protocol. prefixes in routing announcements. Each key-pair is
3
bound to a single prefix, and that key can only authen- also encourages early adoption because creating a self-
ticate routing updates associated with that prefix or its signed certificate early (i.e., before an attack) is much
sub-prefixes. easier than later demonstrating prefix ownership to a trust
Because they are self-signed, these certificates do not anchor in order to reclaim. By adopting early, an AS
imply an endorsement from a centralized authority like achieves a high level of security (an attacker must deceive
IANA that the AS originating the prefix is its legitimate a trust anchor to be successful) at an extremely low cost.
owner. However, these self-signed prefix certificates can Accepted certificates/prefix pairs are placed in a local
be used to authenticate address space delegation between database along with a timestamp indicating when the pre-
parties within the grassroots-PKI. For example, if a large fix was first seen at that router. New routers just coming
ISP has a trusted prefix key, it can sign the key of any cus- online can be easily be pre-configured with certificates
tomer announcing a smaller portion of that address space, learned by other routers to immediately begin choosing
indicating that the ISP permits the customer to announce secure routes.
that prefix.
Self-signed certificates are distributed as transitive at- Risk. This approach has two main risks: first, an at-
tributes within the BGP update message, meaning they tacker may use self-signed certificates to try and divert
will be forwarded with route announcements even by traffic from a legitimate prefix owner, and second, an at-
ASes that are not yet participating in the secure routing tacker may compromise one of the trust anchors and issue
scheme. illegitimate certificates. We explore both possibilities.
The assumption made here is that announcing a self- Risk 1: Preferring older self-signed certificates pre-
signed certificate provides security benefits for the early vents an attacker from stealing a prefix that has already
adopters, because BGP routers apply the following list of been self-signed by its owner. However, an attacker could
precedence to decide which BGP prefix/key pairs to trust: announce a self-signed certificate before the legitimate
1. Root-signed: Prefix that is secured by a certificate owner. Our goal in this case is two-fold: first, make this
chain rooted at IANA. attack difficult, so that malicious actors do not gain any
attack power with a grassroots PKI compared to BGP to-
2. Trust-anchor-signed: Prefix with a certificate- day. Second, provide a straight-forward mechanism to
chain rooted at a well-respected "trust-anchor", such resolve this conflict that results in an even more secure
as a tier-1 ISP, registry, or corporate CA. Such an infrastructure.
oligarchy of trusted entities is similar to current web To provide the first property of introducing no addi-
security, where browsers ship with a relatively large tional vulnerabilities into the system, a router only ac-
list of trusted certificates. cepts a self-signed prefix key if that key has been propa-
gated with every preferred route to that prefix for a set
3. Self-signed: Prefix signed by a key not associated period of time (e.g. 24 hrs.). This simple yet effec-
with a trust anchor. For multiple such certificates, tive heuristic is similar in motivation to PGBGP [7], and
the oldest certificate (date first seen by the router, not builds on the intuition that at any point of time, most In-
date carried in certificate), is preferred. This model ternet routes are correct. Invalid originations for actively-
is similar to light-weight destination authentication used address space result in outages, which even today
in SSH. are recognized and manually filtered on human time-
4. Unsigned: A prefix in a BGP update as announced scales of several hours at the most. With this rule, ma-
on the Internet today. licious key announcements cannot violate existing secu-
rity mechanisms like filter lists or make it easier for an
Note that a BGP router has the highest preference attacker to divert traffic. Thus all ASes, even those not
for prefixes certified through trusted entities, which can participating in a Grassroots-PKI, are no more vulnerable
"overrule" other certificates for the same prefix that are to attacks than they are today.
only signed by less well-known entities. The key used by If an attacker nonetheless successfully has its route and
a trust anchor to sign prefix certificates is not itself a pre- key accepted, we rely on the policy of preferring certifi-
fix key, meaning that a trust anchor can sign prefix keys cates with a higher trust level as a mechanism for "re-
even if it does not own the associated address space. This voking" the invalid ownership claim. For example, if ISP
flexibility enables quick PKI development despite orga- evil.net is first to issue a self-signed certificate for one
nizations in the delegation hierarchy that do not yet par- of angel.com's prefixes, angel.com can regain control by
ticipate in the PKI. Routers install a trust anchor's public getting a trust anchor (for example, a tier-1 ISP respon-
key (used to verify prefix certificates) only if it decides sible for providing their transit connectivity) to sign an-
that party is indeed trustworthy. gel.com's prefix key. This makes angel.com's key more
The policy of preferring older self-signed certificates trusted than the key from evil.net, and angel.com will
not only protects the address space of participants from quickly reclaim its address space. The required chain
an attacker's unauthenticated route announcement, but it of communication largely mirrors today's use of reac-
4
tionary BGP filters to block invalid routing announce- RIPE AT&T Sprint
ments. However, the major difference is that with a grass-
roots PKI, the destination now become significantly more GEANT HP IBM XO CMU
resistant to all future attacks, and the overall routing sys-
tem is one step closer to a global PKI. DFN EBay
A related concern is an attacker's ability to announce a Figure 3: Three independent complex PKIs, each with a trust anchor at
new unsigned sub-prefix of another prefix that is already its root. Trust hierarchy does not necessarily mirror address delegation.
signed4 . Without a top-down PKI it is difficult to deter-
mine whether this sub-prefix is a valid route from a net-
work not yet participating in the grassroots-PKI, or an clusters from Figure 2 are collected and authenticated by
attack meant to illegitimately divert traffic. The scheme three different trust anchors.
must either accept and use less-trusted sub-prefixes, in-
Risk. This approach has two main risks. First, oper-
troducing significant vulnerability into the system, or re-
ational confusion may occur during the transition from
ject all more specific prefixes unless they are signed by a
the primary use of self-signed certificates to independent
key as or more trusted than the prefix they deaggregate.
complex PKIs. Who is qualified to be a trust anchor?
We choose the later, because legitimate sub-prefixes in
Who decides if a trust anchor should be removed be-
global routing tables are likely to be IP space obtained by
cause of bad security practices? Similar to the inclu-
multi-homed customer from one of its upstream ISPs. As
sion of trusted keys in a browser, community consensus
a result, sending traffic to the larger prefix will still re-
will play a powerful role in handling such issues. ISP
sult in the data being correctly delivered to the sub-prefix
operational organizations (e.g., NANOG) will be able to
owner. If the sub-prefix owner wants its sub-prefix ac-
develop policies, likely placing trust in organizations al-
cepted globally as a secure route, it can easily have its
ready allocated significant responsibility for running core
upstream delegate that address space by signing the cus-
network infrastructures.
tomer's key for the sub-prefix.
Second, the many trust anchors at the root of indepen-
Risk 2: While self-signed certificates provide protec-
dent PKIs are still a vulnerability, as compared to full-
tion against common BGP attacks and misconfiguration,
time CA's, these organizations likely spend less money
the large number of trust anchors still represents a legit-
on and have less experience with roles like validating the
imate vulnerability. Because any trust anchor certificate
identity of a prefix owner and protecting the private sign-
is preferred over all self-signed certificates, a prefix with
ing key from compromise. Prefix owners can achieve ad-
only a self-signed certificate is vulnerable to the compro-
ditional robustness either by having their key signed by
mise of any trust anchor. Yet this preference of trust an-
multiple trust anchors or by the most trusted of entities,
chors over self-signed certificates is required as part of
IANA. Either option is a viable path toward reaching the
the attack resolution process described above. Thus, as
third and final stage: global PKI.
demand for security increases, destinations will logically
desire to have their self-signed certificates be signed by 3.3 Global PKI
a trust anchor, even if no attack has yet occurred. This With the existence of many independent complex PKIs,
leads to our next stage of adoption: independent complex we have clearly overcome the mutual dependence cited
PKIs. earlier as a key stumbling block to deployment of a
3.2 Independent Complex PKIs full routing PKI. The existence of a number of trust an-
chors will provide an incentive for the establishment of a
For added robustness, we consider an architecture where smaller root of trust. Each trust anchor can offload a con-
islands of domains have their originally self-signed keys siderable administrative burden onto the new trust root,
certified by one or more entities designated as "trust an- and at the same time reduce its security exposure. This
chors", thus beginning to form a PKI hierarchy. economic incentive is important, since any entity assum-
As mentioned above, the resolution of routing attacks ing the burden of acting as a trust root brings upon them-
creates a certification chain from a trust anchor to the le- selves a considerable liability. We believe either IANA
gitimate prefix owner. Additionally, security conscious or a small number of the most well-respected trust an-
prefix owners are likely to preemptively have their prefix chors will fill this role. There are two likely scenarios for
keys signed by trust anchors to gain improved attack ro- a global PKI: cross-certification or consolidation under a
bustness. ISPs will also gain a competitive advantage if single-rooted hierarchy.
they offer customers a certificate path to a trust anchor.
In the course of this process, the trust anchors essen- 3.3.1 Cross-certification
tially become the roots of smaller hierarchical PKIs. Fig- Large ISPs at the root of independent complex PKIs may
ure 3 shows an example, where the formerly self-signed be willing to cross-certify each other on the basis of ex-
4 The announcement of a super-prefix is not a security concern, be- isting business relationships. But in the eyes of some,
cause IP forwarding will prefer the more specific valid route direct cross-certification "turns the hierarchy of trust into
5
the spaghetti of doubt, with multiple certificate paths pos- 5 ACKNOWLEDGMENTS
sible from leaf to roots ..." [4]. With cross-certification This research was supported in part by CyLab at Carnegie
any given BGP participant may find it difficult to known Mellon under grant DAAD19-02-1-0389 from the Army
where trust is coming from, or how reliable that trust is. Research Office, and grant CT-0433540 from the Na-
An alternative to direct cross-certification is the use of tional Science Foundation, and by a gift from Cisco.
a Bridge Certification Authority (BCA) [5]. A BCA is a We would like to thank Jennifer Rexford for interesting
CA trusted by all of the smaller PKI roots to mediate trust discussions and feedback, and the anonymous reviewers
between them. Each PKI root cross-certifies once with for their insightful suggestions.
the BCA, and trusts that the BCA will correctly mediate
policy and trust the various roots. Any mutually trusted R EFERENCES
entity could become the BCA in a secure BGP, but IANA [1] MS01-017: Erroneous VeriSign-Issued Digital Certificates Pose
may be the most natural choice. Note that as a bridge Spoofing Hazard. http://support.microsoft.com/kb/
293818.
IANA would not actually require a PKI under it.
[2] D. Boneh and M. Franklin. Identity-based encryption from the
Weil Pairing. In Advances in Cryptology -- CRYPTO '2001, pages
Risk. ANX used the Bridge CA architecture, and ex- 213229, 2001.
perienced organizational difficulties due to the number
[3] G. Goodell, W. Aiello, T. Griffin, J. Ioannidis, P. McDaniel, and
of administrative entities. Similar political complexities A. Rubin. Working around BGP: An incremental approach to im-
may render a BCA infeasible for secure BGP. proving security and accuracy in interdomain routing. In Proceed-
ings of NDSS 2003, February 2003.
3.3.2 Single-Rooted Hierarchy [4] P. Gutmann. PKI: It's not dead, just resting. Computer, 35(8):41
49, August 2002.
If IANA and the RIRs agree to participate in a routing [5] P. Hesse and D. Lemire. Managing interoperability in non-
PKI, then ISPs and other trust anchors may be willing to hierarchical public key infrastructure. In Proceedings of Net-
graft their root into a Single Rooted Hierarchy [5]. Much work and Distributed System Security Symposium, 2002, February
like the BCA case, the existence of independent trust an- 2002.
chors creates both management and security incentives to [6] Yih-Chun Hu, Adrian Perrig, and Marvin Sirbu. SPV: Secure
path vector routing for securing BGP. In Proceedings of ACM
move toward a single root. Additionally, once certificates
SIGCOMM 2004, September 2004.
become a key part of the routing protocol, centralized ad-
[7] Josh Karlin, Stephanie Forrest, and Jennifer Rexford. Pretty good
dress space delegators like IANA will be more willing to BGP: Improving BGP by cautiously adopting routes. In Proc.
participate because they could gain power over wayward International Conference on Network Protocols, November 2006.
address owners by denying them a new certificate. [8] S. Kent, C. Lynn, J. Mikkelson, and K. Seo. Secure border gate-
way protocol (S-BGP) -- real world performance and deployment
Risk. Single-rooted hierarchies have difficulties if the issues. In Proceedings of NDSS 2000, pages 103116, February
2000.
root key needs to be revoked. The approach of a single-
rooted hierarchy for a secure BGP has the remote, yet [9] John Linn. Trust models and management in public-key in-
frastructures. Available at http://citeseer.ist.psu.edu/
real, risk that route authorizations for the entire Inter- linn00trust.html.
net become invalid, causing a breakdown of interdomain
[10] S. A. Misel. Wow, AS7007! NANOG mail archives,
routing because no secure routes can be found. http://www. merit. edu/mail.archives/nanog/
1997-04/msg00340.html, 1997.
4 C ONCLUSION [11] Robert Moskowitz. History of the bca concept and other bca ef-
forts, April 2000. Available at http://csrc.nist.gov/pki/
The deployment of a global PKI needed for secure rout- twg/Archive/y2000/presentations/twg-00-15.pdf.
ing is not sufficiently incentivized to overcome opera- [12] Michael K. Reiter and Stuart G. Stubblebine. Authentication met-
tional barriers to development and adoption. Contrary to ric analysis and design. ACM Transactions on Information and
current top-down PKI proposals, we suggest a grassroots System Security, 2(2):138158, 1999.
PKI, representing a more realistic deployment path that [13] S. Weiler. Dnssec lookaside validation (dlv), draft-weiler-dnssec-
will facilitate development of a global routing PKI and dlv-01.txt. Technical report, IETF, June 2006.
the deployment of secure routing. By accepting an imper- [14] B. Weis, ed. Secure origin BGP (soBGP) certifi-
cates. Internet-Draft, July 2004. Work in progress.
fect level of security, but creating incentives for improved
Available at http://www.watersprings.org/pub/id/
robustness, we construct a global PKI through incremen- draft-weis-sobgp-certificates-02.txt.
tally staged deployment. At no point do we introduce [15] R. White. Deployment considerations for secure origin BGP
new vulnerabilities, and attacks against legacy security (soBGP), draft-white-sobgp-bgp-deployment-01.txt. Draft, IETF,
weaknesses result in a strictly more secure network that is June 2003.
closer to our goal of a global PKI. We anticipate that our [16] Philip R. Zimmermann. The Official PGP User's Guide. MIT
(r)evolutionary PKI deployment mechanism will encour- Press, Cambridge, MA, USA, 1995. ISBN 0-262-74017-6.
age a dialog in the secure routing community to consider
alternative PKI deployment strategies.
6