582 IEEE JOURNAL ON SELECTED AREAS IN COMMUNICATIONS, VOL. 18, NO. 4, APRIL 2000Secure Border Gateway Protocol (S-BGP)Stephen Kent, Charles Lynn, and Karen SeoAbstract—The Border Gateway Protocol (BGP), which is usedto distribute routing information between autonomous systems(ASes), is a critical component of the Internet's routing infra-structure. It is highly vulnerable to a variety of malicious attacks,due to the lack of a secure means of verifying the authenticity andlegitimacy of BGP control traffic. This paper describes a secure,scalable, deployable architecture (S-BGP) for an authorizationand authentication system that addresses most of the securityproblems associated with BGP. The paper discusses the vulnera-bilities and security requirements associated with BGP, describesthe S-BGP countermeasures, and explains how they address thesevulnerabilities and requirements. In addition, this paper providesa comparison of this architecture to other approaches that havebeen proposed, analyzes the performance implications of theproposed countermeasures, and addresses operational issues.Index Terms—Denial of service, digital signatures, public-keycryptography, routing, security.I. PROBLEM DESCRIPTIONINTERNET routing is based on a distributed system com-posed of many routers, grouped into management domainscalled Autonomous Systems (ASes). Routing informationis exchanged between ASes in Border Gateway Protocol(BGP) [1] UPDATE messages. BGP has proven to be highlyvulnerable to a variety of attacks [2], due to the lack of ascalable means of verifying the authenticity and legitimacyof BGP control traffic. In April 1997, we began work on thesecurity architecture described in this paper. In this sectionwe describe the problem—how the protocol works; the natureof observed BGP traffic in the Internet; the correct operationof BGP; the threat model and BGP vulnerabilities; and thegoals, constraints, and assumptions that apply to the proposedcountermeasures.A. Overview of BGPThe BGP-4 protocol, both message syntax and the route prop-agation algorithm, is described in [1]. Routers implementingBGP, BGP “speakers,” exchange routing information via UP-DATEmessages.AnUPDATE message consists of three parts: alist of address prefixes1for destinations that are no longer reach-able (via the previously specified route); a list of prefixes thatare reachable; and the characteristics of the cumulative path andcurrent inter-AS hop, contained in path attributes, that can beused to reach the address prefixes. The attribute used to specifythe inter-AS path, the AS_PATH attribute, specifies a sequenceManuscript received February 1, 1999; revised November 11, 1999. Thiswork was supported by NSA in 1997, and by DARPA.The authors are with BBN Technologies, Cambridge, MA 02138 USA.Publisher Item Identifier S 0733-8716(00)01519-5.1A prefix specifies an IP address block, and consists of a count of the mostsignificant bits in an IP address, and the value of those bits.of Autonomous Systems (ASes) along the path, each identifiedby its AS number.When propagatinganUPDATE to a neighboring AS, the BGPspeaker prepends its AS number to the sequence, and updatescertain other path attributes. Since an UPDATE can specify onlyone path, only prefixes that share that path may be aggregatedinto the UPDATE.The backbone routers of the major internet service providers(ISP’s) have a route to every reachable IP address. Analysis ofBGP UPDATE’s recorded during January 1999 showed routingdatabases that contained about 61 000 IPv4 address prefixes.Each (nonleaf) BGP speaker maintains a full routing table, andsends its best route for each prefix to each neighbor speaker.When a BGP speaker reboots, it receives complete routing ta-bles (via UPDATE’s) from each of its neighbors. The worstcase arises at Network Access Points (NAP’s), where ISP’s areconnected together via a high speed (100 Mb/s) LAN. A BGPspeaker at a NAP might have about 30 peers.On a daily basis, a BGP speaker at a NAPreceivesabout 1425UPDATE’s from each peer, an average UPDATE rate of about 1per minute per peer. This rate is affected somewhat by Internetgrowth (about 25 network prefixes are added each day), but ismostly a function of UPDATE’s sent due to link, component,or congestive failures and recoveries. Analysis shows that about50% of all UPDATE’s are sent as a result of route “flaps,” i.e.,transient communication failures that, when remedied, result ina return to the original route. This sort of routing behavior haslong been characteristic of the Internet2[3] and the proposedsecurity mechanisms take advantage of this behavior to achieveacceptable performance, as discussed in Section VI.B. Correct Operation of BGPSecurity for BGP is defined by the correct operation of BGPspeakers. This definition is based on the observation that anysuccessful attack against BGP should result in other than cor-rect operation, presumably yielding degraded operation. Cor-rect operation of BGP depends upon the integrity, authenticity,and timeliness of the routing information it distributes as well aseach BGP speaker's processing, storing, and distribution of thisinformation in accordance with both the BGP specification andwith the (local) routing policies of the BGP speaker's AS. Thefollowing statements characterize the primary correct operationfeatures of BGP.• Each UPDATE received by a BGP speakerfrom a peer wassent by the indicated peer, was not modified en route fromthe peer, and contains routing information no less recentthan the routing information previously received for theindicated prefixes from that peer.2In a discussion with David Mills, an architect of the NSFNET, he confirmedthat route flapping has been a characteristic of the Internet since the mid 1980's.0733–8716/00$10.00 © 2000 IEEEKENT et al.: SECURE BORDER GATEWAY PROTOCOL 583• The UPDATE was intended for receipt by the peer thatreceived it.• The peer that sent the UPDATE was authorized to act onbehalf of its AS to advertise the routing information con-tained within the UPDATE to BGP peers in the recipientAS.• The owner of an address space corresponding to a reach-able prefix advertised in an UPDATE was authorized byits parent organization to own that address space.• The first AS in the route was authorized, by the ownersof the address space corresponding to the set of reachableprefixes, to advertise those prefixes.• If the UPDATE indicates a withdrawn route, then the