Internet Engineering Task Force Charles Lynn Internet Draft Joanne Mikkelson draft-clynn-s-bgp-protocol-01.txt Karen Seo Expires December 2003 BBN Technologies June 2003 Secure BGP (S-BGP) draft-clynn-s-bgp-protocol-01.txt Status of this Memo This document is an Internet-Draft and is in full conformance with all provisions of Section 10 of [RFC2026]. Internet-Drafts are working documents of the Internet Engineering Task Force (IETF), its areas, and its working groups. Note that other groups may also distribute working documents as Internet-Drafts. Internet-Drafts are draft documents valid for a maximum of six months and may be updated, replaced, or obsoleted by other documents at any time. It is inappropriate to use Internet-Drafts as reference material or to cite them other than as "work in progress". The list of current Internet-Drafts can be accessed at http://www.ietf.org/ietf/1id-abstracts.txt The list of Internet-Draft Shadow Directories can be accessed at http://www.ietf.org/shadow.html. This document specifies a protocol for the Internet community, and requests discussion and suggestions for improvements. Please refer to the current edition of the "Internet Official Protocol Standards" (STD 1) for the standardization state and status of this protocol. Distribution of this memo is unlimited. Copyright (C) The Internet Society (June 2003). All Rights Reserved. Abstract The Border Gateway Protocol (BGP), which is used to distribute routing information between autonomous systems (ASes), is a critical component of the Internet's routing infrastructure. It is highly vulnerable to a variety of malicious attacks both in theory and in practice, due to the lack of a scalable means of verifying the authenticity and legitimacy of BGP control traffic. This document is a protocol specification for Secure BGP (S-BGP), an extension to BGP-4. S-BGP adheres to the principle of least privilege and uses countermeasures that create an authentication and authorization system that addresses most of the security problems associated with BGP. To facilitate adoption and deployment, S-BGP is designed to minimize the overhead (processing, bandwidth, storage) added by its countermeasures and to be interoperable with the current BGP so as to Lynn, Mikkelson, Seo [Page 1] Secure BGP June 2003 be incrementally deployable. Disclaimer The views and specification here are those of the authors and are not necessarily those of their employers. The authors and their employers specifically disclaim responsibility for any problems arising from correct or incorrect implementation or use of this specification. Table of Contents Status of this Memo . . . . . . . . . . . . . . . . . . . . . . . 1 Abstract . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1 Disclaimer . . . . . . . . . . . . . . . . . . . . . . . . . . . 2 Table of Contents . . . . . . . . . . . . . . . . . . . . . . . . 2 Table of Figures . . . . . . . . . . . . . . . . . . . . . . . . 3 1. Introduction . . . . . . . . . . . . . . . . . . . . . . . . 4 1.1. The Authorization and Authentication Problem . . . . . . . 5 1.2. Overview of the S-BGP Architecture . . . . . . . . . . . . 6 1.2.1. Public Key Infrastructure (PKI) . . . . . . . . . . . . . 7 1.2.1.1. PKI for Delegation of IP Address Blocks . . . . . . . . 7 1.2.1.2. PKI for Delegation of AS Numbers and Binding a Router to an AS . . . . 8 1.2.1.3. Use of the Certificates in the PKIs . . . . . . . . . . 9 1.2.2. Attestations . . . . . . . . . . . . . . . . . . . . . . 10 1.2.3. IPsec . . . . . . . . . . . . . . . . . . . . . . . . . . 10 1.3. Overview of an S-BGP Implementation . . . . . . . . . . . . 11 2. Terminology . . . . . . . . . . . . . . . . . . . . . . . . . 15 3. Attestation Path Attribute . . . . . . . . . . . . . . . . . 22 3.1. Attestation Path Attribute Formats . . . . . . . . . . . . 23 3.1.1. Route and Address Attestations . . . . . . . . . . . . . 23 3.1.2. RA Sequences and Aggregation . . . . . . . . . . . . . . 30 3.2. S-BGP Processing . . . . . . . . . . . . . . . . . . . . . 31 3.2.1. Route Attestation Processing . . . . . . . . . . . . . . 32 3.2.1.1. Route Attestation Validation . . . . . . . . . . . . . 34 3.2.1.2. Route Attestation Creation . . . . . . . . . . . . . . 37 3.2.2. BGP Processing Phases . . . . . . . . . . . . . . . . . . 41 3.2.2.1. Phase 1 Processing . . . . . . . . . . . . . . . . . . 41 3.2.2.2. Phase 2 Processing . . . . . . . . . . . . . . . . . . 42 3.2.2.3. Phase 3 Processing . . . . . . . . . . . . . . . . . . 42 3.2.3. S-BGP Processing . . . . . . . . . . . . . . . . . . . . 43 3.2.3.1. Receive Processing . . . . . . . . . . . . . . . . . . . 43 3.2.3.2. Send Processing . . . . . . . . . . . . . . . . . . . . 44 3.2.3.3. Background Processing . . . . . . . . . . . . . . . . . 46 3.2.3.4. Unknown Path Attributes and Canonicalization . . . . . 47 Lynn, Mikkelson, Seo [Page 2] Secure BGP June 2003 3.2.4. Interoperation with Non-S-BGP Speakers . . . . . . . . . 48 4. Processing Optimizations . . . . . . . . . . . . . . . . . . 49 5. Auditing and Event Reporting . . . . . . . . . . . . . . . . . 51 6. Infrastructure Support . . . . . . . . . . . . . . . . . . . . 51 7. Address Attestations . . . . . . . . . . . . . . . . . . . . 52 8. IANA Considerations . . . . . . . . . . . . . . . . . . . . . 53 9. Security Considerations . . . . . . . . . . . . . . . . . . . 53 10. Acknowledgments . . . . . . . . . . . . . . . . . . . . . . . 53 11. References . . . . . . . . . . . . . . . . . . . . . . . . . . 54 Appendix A. Example Certificates, Hashes, and Signatures . . . . 57 Appendix B. Configuration . . . . . . . . . . . . . . . . . . . . 58 Appendix C. Policy Support . . . . . . . . . . . . . . . . . . . 59 Appendix D. NOC Support . . . . . . . . . . . . . . . . . . . . . 75 Intellectual Property Rights . . . . . . . . . . . . . . . . . . 76 Full Copyright Statement . . . . . . . . . . . . . . . . . . . . 76 Authors' Addresses . . . . . . . . . . . . . . . . . . . . . . . 77 Table of Figures Figure 1: Address Space PKI Structure . . . . . . . . . . . . . 8 Figure 2: AS Custodianship and Router ID PKI . . . . . . . . . . 9 Figure 3: Terminology Example . . . . . . . . . . . . . . . . . 21 Figure 4: Structure of an Address or Route Attestation . . . . 24 Figure 5: Route and Address Attestation and Authenticator Headers . . . 24 Figure 6: Signer Part . . . . . . . . . . . . . . . . . . . . . 25 Figure 7: Formats of Issuer Name Forms . . . . . . . . . . . . 25 Figure 8: Signature Part . . . . . . . . . . . . . . . . . . . 26 Figure 9: CoverageMask Field . . . . . . . . . . . . . . . . . 27 Figure 10: Expiry Part . . . . . . . . . . . . . . . . . . . . . 27 Figure 11: ExplicitPA Part . . . . . . . . . . . . . . . . . . . 28 Figure 12: Prefix Encoding . . . . . . . . . . . . . . . . . . . 28 Figure 13: Target Part . . . . . . . . . . . . . . . . . . . . . 29 Figure 14: Aggregation Example . . . . . . . . . . . . . . . . . 30 Lynn, Mikkelson, Seo [Page 3] Secure BGP June 2003 1. Introduction Internet routing is based on a distributed system composed of many routers, grouped into management domains called Autonomous Systems (ASes). Routing information is exchanged between ASes in Border Gateway Protocol (BGP) [RFCbgp] UPDATE messages. This critical component of the Internet's routing infrastructure has proven to be highly vulnerable to a variety of attacks [Murphy], due to the lack of a scalable means of verifying the authenticity and legitimacy of BGP control traffic. This document provides a protocol specification for Secure BGP (S-BGP), an extension to BGP-4. S-BGP adheres to the principle of least privilege [SALTZER] and uses countermeasures that create an authentication and authorization system that addresses most of the security problems associated with BGP. To facilitate adoption and deployment, S-BGP is designed to minimize the overhead (processing, bandwidth, storage) added by its countermeasures and to be interoperable with the current BGP so as to be incrementally deployable. The S-BGP architecture is described in [JSAC]. It discusses BGP vulnerabilities and security requirements and a high-level description of S-BGP's components, and how the components work together to address these vulnerabilities. [Murphy] also discusses BGP vulnerabilities. [JSAC] includes a comparison of this architecture with other approaches that have been proposed, and an overview of performance and operational issues. See also [Murphy2]. The public key infrastructure (PKI) created to support the S-BGP authorization and authentication mechanisms is described in more detail in [DISCEX]. See also Appendix A, [X509EXT], and [X509S-BGP]. [NDSS00] contains experimental data collected from a proof of concept implementation of S-BGP in the GateD (TM) BGP implementation. [CMS03] incorporates more recent data from the Route-Views site [RVO]. A reference implementation in mrtd [MRT] is available from the S-BGP web site [S-BGP]. This document assumes that the reader is familiar with BGP, related networking technology, and general security terms and concepts. Lynn, Mikkelson, Seo [Page 4] Secure BGP June 2003 1.1. The Authorization and Authentication Problem Security for BGP is defined by the correct operation of BGP speakers. This definition is based on the observation that any successful attack against BGP should result in other than correct operation, presumably yielding degraded operation. Correct operation of BGP depends upon the integrity, authenticity, and timeliness of the routing information it distributes as well as each BGP speaker's processing, storing, and distribution of this information in accordance with both the BGP specification and with the (local, possibly confidential) routing policies of the BGP speaker's AS. The following statements characterize the primary correct operation features of BGP. 1) Each UPDATE received by a BGP speaker from a peer was sent by the indicated peer, was not modified en-route from the peer, and contains routing information no less recent than the routing information previously received for the indicated prefixes from that peer. 2) The UPDATE was intended for receipt by the peer that received it. 3) The peer that sent the UPDATE was authorized to act on behalf of its AS to advertise the routing information contained within the UPDATE to BGP peers in the recipient AS. 4) The entity with the right to use an address space corresponding to a reachable prefix advertised in an UPDATE was given custodianship of that address space by a higher-level/parent entity. 5) The originating AS was authorized, by the entity(s) with the right to use address space corresponding to the set of reachable prefixes, to advertise those prefixes. 6) If the UPDATE indicates a withdrawn route, then the peer withdrawing the route was a legitimate advertiser for that route, prior to its withdrawal. 7) The peer that sent the UPDATE correctly applied the BGP rules and its AS's routing policies in modifying, storing, and distributing the UPDATE, in selecting the route, and in deriving forwarding information from it. 8) The BGP speaker that received the UPDATE correctly applied the BGP rules and its AS's routing policies in determining whether to accept the UPDATE. The countermeasures developed for S-BGP meet the first six of these criteria, even in the face of subversion of BGP speakers (Byzantine failures). However, because the local policy features of BGP allow a speaker considerable latitude in determining how to process an Lynn, Mikkelson, Seo [Page 5] Secure BGP June 2003 UPDATE, these countermeasures cannot meet the last two criteria, i.e., such attacks could be attributed to local policies not visible outside the AS. To address such attacks within BGP, the semantics of BGP itself would have to change. Moreover, because UPDATEs do not carry sequence numbers, a BGP speaker can generate an UPDATE based on old information, e.g., withdrawing or reasserting a route based on outdated information. Thus the temporal accuracy of UPDATEs, in the face of Byzantine failures, is enforced only very coarsely by these countermeasures. 1.2. Overview of the S-BGP Architecture The design of S-BGP is based on several assumptions and constraints. First, the countermeasures must not violate the BGP specifications, e.g., any additional data carried in UPDATEs must make use of defined extension mechanisms and the maximum (BGP) message size of 4096 bytes must not be exceeded. Thus, for example, the address attestations, certificates, and CRLs needed to support S-BGP are transmitted out- of-band; and an optional, transitive, path attribute is used to carry in-band S-BGP countermeasures data. A countermeasure must operate at a rate comparable to the information that it protects as failure to do so results in synchronization discrepancies that might be exploited. Consequently, countermeasures protecting topology information needs to function at the rate of UPDATE messages while countermeasures related to the existence of ASes, networks, or S-BGP speakers can function at a slower rate. The performance impact of the countermeasures must be minimal. Finally, the countermeasures should scale, as the Internet continues to grow at a well-documented, substantial pace. See [JSAC] for a more detailed overview of S-BGP. The approach adopted to securing BGP route distribution involves a Public Key Infrastructure (PKI), a new transitive path attribute containing "attestations", and the use of IPsec. These components are used by an S-BGP speaker to validate the authenticity and data integrity of BGP UPDATEs that it receives, and to verify the identity and authorization of the senders. A Public Key Infrastructure (PKI), based on X.509 v3 certificates containing S-BGP private extensions [X509EXT] [X509S-BGP], is used to provide assurance that the AS numbers and IP address prefixes being advertised have been authorized for use by their respective custodians. See [DISCEX] for a more detailed description of the PKI. A new BGP optional transitive path attribute, the Attestation Path Attribute (ATTEST), is used to carry digital signatures that protect the prefixes (NLRI or MP_REACH_NLRI), the AS Path, and, optionally, other transitive path attributes as a BGP UPDATE propagates between ASes. IPsec, in conjunction with a certificate issued to each BGP speaker, Lynn, Mikkelson, Seo [Page 6] Secure BGP June 2003 provides authentication of BGP peers and provides data integrity for the TCP peering connection. It also protects the connection from replay attacks, as well as attacks on the TCP connection or the in- transit BGP protocol messages. 1.2.1. Public Key Infrastructure (PKI) S-BGP makes use of a Public Key Infrastructure (PKI), based on the use of X.509 v3 certificates, that supports the authentication of IP address block custodianship, AS number custodianship, AS identification, and BGP router identification and authorization to represent an AS. The PKI uses three new certificate extensions to implement this functionality. See [RFC3280] for a description of X.509 certificate and CRL formats. The concepts and terms address attestation (AA) and route attestation (RA) are described and defined in section 1.2.2. An administrative framework [RFC2050] and personnel already exist to manage the delegation of the right to use IP address prefixes and AS numbers. S-BGP builds upon this existing infrastructure to manage these certificates. The PKI that must be created to support S-BGP will overlay the existing administrative framework, based on the Regional Internet Registries (RIR), ISPs, etc. 1.2.1.1. PKI for Delegation of IP Address Blocks The IPAddrBlocks certificate extension binds a set of IP address families and prefixes to a public key. Certificates containing this extension, in conjunction with address attestations, are used to verify that the entity with the right to use an IP address space (the private key holder) has authorized one or more ASes to advertise the address space. The certificates are arranged into a hierarchy that parallels the existing IP address administrative framework. The IANA is the root certification authority (CA) of the PKI, and each RIR is a registry CA below the root. The IANA as the S-BGP root CA, cross certifies the RIR's registry CA. The third tier consists of ISPs, and subscribers that have obtained their address space assignment directly from an RIR. Additional tier(s) represent DSPs or subscribers that have been assigned IP address blocks by their provider. Note that only those entities that have the right to use an IP address block need these certificates. Entities that are "loaned" a portion of their provider's address space do not need a certificate. Figure 1 illustrates this certification hierarchy, showing the organizations that are represented at each tier. Lynn, Mikkelson, Seo [Page 7] Secure BGP June 2003 IANA All Addr blocks | +----------------------+-----------------------+ | | | APNIC Registry ARIN Registry ... RIPE Registry APNIC Addr blocks ARIN Addr blocks RIPE Addr blocks : | : | +----------+----+++-----+-----------+----+++-----+ | | ||| | | ||| | AT&T Org A ... MCI ISP 1 ... Sprint Addr Addr Addr Addr Addr block(s) block(s) block(s) block(s) block(s) | | | | ..--+--.. ..--+--.. ..--+--.. ..--+--.. | | | | Subscriber B DSP 2 Subscriber C ISP 3 Addr Addr Addr Addr block(s) block(s) block(s) block(s) | | ... ... Figure 1: Address Space PKI Structure 1.2.1.2. PKI for Delegation of AS Numbers and Binding a Router to an AS The ASIdentifiers certificate extension binds a set of AS numbers to a public key. The SBGPRouterId extension contained in certificates issued to S-BGP speakers, binds an AS number and the router's BGP ID to the speaker's public key. Together, these two certificate extensions allow BGP speakers to authenticate one another, and to verify that a given speaker is authorized to represent a specified AS. Here too, IANA is the root CA and each RIR, at the second tier, operates a registry CA. The third tier consists of ISPs, DSPs, and subscribers. The second certificate extension is issued at all tiers; and the third at the bottom tier, to S-BGP speakers. The bottom tier represents both ASes (as a management entity), and routers associated with a higher tier organization. Note that only those entities that have the right to use an AS number, that manage S-BGP speakers, or that participate in an S-BGP peering session need these certificates. Figure 2 illustrates a simple example of the hierarchy for these two types of certificates, noting the organizations involved at the top three tiers, and the ASes and routers that populate the bottom tier. Lynn, Mikkelson, Seo [Page 8] Secure BGP June 2003 IANA All AS Numbers | +----------------------+-----------------------+ | | | APNIC Registry ARIN Registry ... RIPE Registry APNIC AS Numbers ARIN AS Numbers RIPE AS Numbers : | : | +-----------+----+++-----+------------+----+++-------+ | | ||| | | ||| | AT&T Org A ... MCI ISP 1 ... Sprint AS #s W,... AS# X AS #s Y,... AS Numbers AS #s Z,... | | | | | +---+---++++ ... +---+-+++++ ... +-----+-++++ | |||| | ||||| | |||| AS# W Routers AS# Y Routers AS# Z Routers in AS W in AS Y in AS Z Figure 2: AS Custodianship and Router ID PKI 1.2.1.3. Use of the Certificates in the PKI The certificates described above are used to enable verification of: * An organization's right to use a block of IP addresses The IPAddrBlocks certificate extension (section 1.2.1.1) is used to verify that an organization has the right to use a block of IP addresses, and, using an address attestation, to authorize one or more ASes to advertise them. The signature on an address attestation must be verifiable using the public key in a certificate containing IP address block(s) that are a superset of the address prefixes in the address attestation. * An organization's right to use an AS number The ASIdentifiers certificate extension (section 1.2.1.2) is used to verify that an AS number has been assigned to the holder of a particular public key, e.g., an organization. They are used to verify the certificates associated with an AS as a management entity, and the certificates of the S-BGP speakers within those ASes, through the AS number linkage and the usual subordinate certificate validation checks. * An AS's identity The ASIdentifiers certificate extension (section 1.2.1.2) may be used to verify the signature of an AS as a management entity on, e.g., S-BGP information uploaded to S-BGP speakers -- extract file(s) of address attestations, S-BGP speaker public keys, or (S-BGP related) policy. Extract files are used to reduce the volume of data that needs to be present at each S-BGP speaker. Lynn, Mikkelson, Seo [Page 9] Secure BGP June 2003 * A router's identity and its association with an AS The SBGPRouterId certificate extension (section 1.2.1.2) is used to verify the signature of an S-BGP speaker on a route attestation and, in conjunction with the ASIdentifiers extension, to make sure that the router is authorized to act on behalf of its AS. * Identity and authorization of a BGP peer The SBGPRouterId certificate extension (section 1.2.1.2) may be used by the BGP routers to authenticate each other when setting up IPsec protected BGP peering sessions. Certificates without the private extensions used by S-BGP may also be used for this purpose, e.g., when a speaker's IPsec implementation cannot process a certificate containing the S-BGP extensions. 1.2.2. Attestations "Attestations" constitute the second major component of the S-BGP architecture. They constitute the core of S-BGP, and represent a conceptually straightforward means of achieving the critical security assurances described above. It is the use of attestations, protected by digital signatures, that permits S-BGP to counter Byzantine attacks (including misconfiguration and typographic errors). Attestations are signed and verified using the public keys from the end-entity certificates of the PKI described above. They enable each S-BGP speaker that receives a route advertisement to verify that each AS along the path has been authorized by the preceding AS to advertise the route, and that the originating AS has been authorized to advertise those prefixes by the entity with the right to use each IP address prefix contained in the UPDATE. There are two types of attestations: * Route attestations (RAs) - whose signer is an S-BGP speaker authorized to represent an AS and the target is a transit AS, or another AS providing third party advertisements for an AS that is not running BGP. Route attestations are carried in a new BGP optional transitive path attribute that contains digital signatures protecting the transitive routing information. * Address attestations (AAs) - whose signer is the entity that has the right to use the address prefixes contained in the attestation and the target is one or more ASes that are authorized to originate routes to those prefixes, e.g., the organization's internet service provider(s). 1.2.3. IPsec IPsec [RFC2401, RFC2407, RFC2408, RFC2409], specifically the encapsulating security payload (ESP) [RFC2406], is used to provide Lynn, Mikkelson, Seo [Page 10] Secure BGP June 2003 BGP control traffic with data and partial sequence integrity, and with peer entity authentication. Because it is implemented at the IP layer, IPsec protects the integrity of the TCP connections used between BGP speakers. Its anti-replay mechanisms detect and reject replayed packets more quickly than TCP, helping to reduce the effect of a denial of service attack. The IPsec anti-replay mechanisms plus TCP sequence numbers ensure the "no less recent" requirement for correct operation of BGP, relative to attacks mounted against inter- router links. ESP may be used with the NULL confidentiality algorithm [RFC2410], i.e., the BGP control traffic will be sent as clear text. If confidentiality of BGP control traffic becomes an issue, it will be easy to later enable the IPsec confidentiality mechanisms where needed, without any changes to BGP. 1.3. Overview of an S-BGP Implementation S-BGP adds three databases to a router. The originating AS database is derived from the address attestations, and the public key database is derived from the end-entity certificates of the S-BGP speakers. An S-BGP speaker also has a database expressing the AS's S-BGP related policy. The originating AS database specifies, for each network prefix that has been authorized for advertisement, the set of ASes that are authorized to originate an advertisement of the prefix. The authorization is provided by the entity with the right to use the IP address prefix, and the authorization of that right can be traced back to IANA through one of the RIRs. Each NOC verifies the address attestations and the claim of right to use an address block back to the IANA before generating a (signed) file that maps the prefixes to their respective originating AS(es). This file can be uploaded to each S-BGP speaker managed by the NOC (assuming that all the NOC's ASes use the same verification policy). Each time an UPDATE is received that advertises a route to a prefix (NLRI or MP_REACH_NLRI), the database is consulted to verify that the originating AS in the UPDATE is one authorized via an AA. Implementation Note: One way that the AA lookup table may be efficiently implemented is by a radix trie built from the prefixes. This trie might be part of a RIB. The public key database contains, for each S-BGP speaker or AS, the DSA public key(s) corresponding to the private key that some speaker will use to sign route attestations in UPDATE messages sent to peers in other ASes. Note that there may be multiple keys for a given RA signer in the database due to key rollover; a key identifier is used to distinguish between these keys. The NOC performs certificate validation for each S-BGP speaker's and AS's end-entity certificates. Lynn, Mikkelson, Seo [Page 11] Secure BGP June 2003 The certificate contains the AS identifier (number) for which the speaker is being authorized to act, and is signed by a CA of the entity that has the right to use that AS number. The validation process traces the right to use the AS identifier back to IANA. A speaker's identity (BGP Identifier), the AS that it represents, the public key, and key identifier from the certificates which pass the validation process are placed into a (signed) file that is uploaded to each S-BGP speaker managed by the NOC (assuming that all the NOC's ASes use the same verification policy). Each time an UPDATE containing the ATTEST path attribute is received that advertises a route, it contains a signed route attestation from each exit speaker along the path (corresponding to the exit speaker prepending its AS number to the AS Path attribute). The signature covers the identity of the AS(es) to which the UPDATE is being passed, as well as other transitive information in the UPDATE (e.g., Origin, AS PATH, NLRI). A speaker that receives an UPDATE verifies the signature on each RA in the ATTEST path attribute using the RA specified public key from the public key database. Implementation Note: One way that the public key lookup table may be efficiently implemented is by a radix trie built from the BGP identifiers or AS identifiers. A speaker may have a private DSA key that is used to sign route attestations. Such a private key SHOULD NOT be shared with other speakers. Alternatively, several speakers may use a shared private key, bound to the AS for which the speakers are authorized to act. It is RECOMMENDED that such a private key be stored in a hardware token so as to minimize the chance of the shared key being compromised. The shared key alternative can reduce the number of public keys for an AS in the public key database from one per inter-AS S-BGP speaker to a single key. Each speaker contains a database with its AS's S-BGP related configuration and policy information. Some parts of this information may be common throughout an AS, while other parts may be specific to the speaker, or to one of the speaker's peers, or even to particular remote AS(es) for which the local administration wants special handling. See Appendix B for examples of general configuration items, and Appendix C for examples of policy controls that a vendor might chose to implement. The BGP specification [RFCbgp] requires a speaker to retain in its Loc-RIB (or Adj-RIB-In) the path attributes that were received with each prefix. The S-BGP ATTEST path attribute is treated like any other transitive path attribute in this respect; it needs to be retained so it can be included in UPDATE messages sent to peers. Lynn, Mikkelson, Seo [Page 12] Secure BGP June 2003 An RA is used to dynamically convey authorization from one AS to the next along the AS path to use the advertisement as input to its route selection process. In order to prevent some forms of cut and paste attacks, an RA, signed by the exit speaker in an AS, includes the AS number of the AS(es) to which the UPDATE will be sent. If an UPDATE is to be sent directly to peers in multiple ASes, or indirectly via a route reflector at a NAP, special configuration is required to identify the ASes that need to be included in the target part of the RA (see, e.g., sign-AS in Appendix C.3.1). The fact that S-BGP signs transitive information in an UPDATE, and that the signature is carried in a path attribute, means that, in general, all of the other path attributes and NLRI information must be known before the signature can be generated. Since the BGP specification suggests that the path attributes be ordered by Type Code, and that both the Type Code assigned to the ATTEST path attribute may not be the largest Type Code ever assigned to transitive information, and the IPv4 NLRI follow the path attributes in an UPDATE message, the flow of control that may have been implemented in the past may have to be altered in an S-BGP implementation. This is analogous to the change that the introduction of the MP_REACH_NLRI path attribute may have necessitated. Canonical Ordering of Information The Digital Signature Algorithm (DSA) [DSA] provides an integrity service by signing a cryptographic hash (SHA-1) [SHA-1] of the information to be protected. The signer hashes the information and signs it; the receiver hashes the information and the DSA determines whether or not the computed hash matches the hash that was signed. This means that the string of octets that the signer hashed must be identical to the string of octets that the receiver hashes. If the octets are not identical, signature verification will fail. This leads to a requirement that the receiver be able to determine the ordering of the octets that the signer hashed. The BGP specification does not require that the ordering of all transitive information be preserved when propagated by a BGP speaker. For example, a BGP speaker is allowed to change: the order of ASes in an AS_SET (including removal of duplicates); the partitioning of ASes between adjacent AS_SEQUENCEs; the order of communities in the Communities [RFC1997] and Extended Communities [EXT-COMM] path attributes, or the ordering of prefixes in the NLRI or MP_REACH_NLRI path attribute. To avoid this problem, S-BGP specifies a canonical ordering for several pieces of information. A signer MUST convert information to be advertised in an UPDATE to the canonical representation before computing the hash to be signed, and the receiver MUST convert the received information to the Lynn, Mikkelson, Seo [Page 13] Secure BGP June 2003 canonical order before computing the hash required for signature verification. Path attribute data in the Explicit Data part an RA SHOULD be in canonical order. It is RECOMMENDED that speakers put the information in the path attributes and NLRI fields of an UPDATE in the canonical order whenever possible, as the CPU cost for all receivers to verify that the ordering is canonical is usually less than the cost to convert non-canonical information into the canonical order. Protection of Attributes whose Content Changes The transitive information in an UPDATE message may change as the an UPDATE is passed from one AS to the next. Three examples are the AS PATH path attribute [RFCbgp], the community path attributes [RFC1997] [EXT-COMM], and the NLRI [RFCbgp] [RFC2858]. When the protected information changes, a receiving speaker will not be able to verify the signatures on previous RAs unless it has access to the information before the change. E.g., when AS adds a community to a received community attribute, subsequent receivers need to be able to determine the communities that were present before the addition. S-BGP meets this requirement by including in each RA an area (ExplicitPA) where a speaker that is changing protected transitive information MUST store a canonicalized copy of the information as it was before the change. Note that the RA where the information is stored is the RA that was received, not the RA added by the speaker making the change. The rules for computing the hash of the protected information are specifically defined so as to allow this change to the ExplicitPA part of a received RA without invalidating the signature. Changes to the NLRI or MP_REACH_NLRI MUST also be recorded. Whenever the NLRI are changed, e.g., one or more prefixes are removed, or prefixes are aggregated, a canonicalized copy of the original NLRI information MUST be placed into the ExplicitPA part of an RA. Note that a consequence of this requirement is that one cannot make the size of an S-BGP protected UPDATE message smaller by splitting the received NLRI into multiple UPDATE messages. It is the originator's responsibility to limit the size of the NLRI included in an UPDATE to allow for the addition of RAs as the UPDATE passes from AS to AS through the network. The originator is the responsible agent, since it is the originator's networks that will be unreachable if one of their UPDATEs becomes too large to meet the BGP 4 KByte maximum packet size limit. In particular, if an ISP knows that some prefixes that it originates are multihomed to other ASes, a conservative strategy would be to place those prefixes into separate UPDATE message(s). See. e.g., max-origin in Appendix C.4.3. In other cases, e.g., the AS PATH path attribute, the change that an AS makes is usually predictable. I.e., an AS inserts its AS number one or more times to the list of ASes in the first AS_SEQUENCE. In Lynn, Mikkelson, Seo [Page 14] Secure BGP June 2003 situations where changes to a path attribute are the predictable changes, there is no need to record a copy of the pre-changed attribute in the ExplicitPA part of an RA; i.e., doing so is OPTIONAL. In the case of the AS PATH attribute, there are also situations where the change is not predictable, e.g., when aggregation has introduced an AS_SET. When changes are made that are different than the predictable change, a copy of the pre-changed information MUST be saved in the ExplicitPA part of an RA. Aggregation BGP uses "aggregation" for multiple purposes. It can be used to: 1) combine more specific prefixes into a less specific prefix in routes that a speaker originates; 2) reduce the number of entries in the routing table (Loc-RIB, etc.), and consequently to: 3) reduce the number of entries in the (hardware) forwarding tables; 4) reduce the number of UPDATE messages that need to be sent to peers and stored in their Adj-RIB-Ins; 5) reduce the size of the information passed to peers; and 6) hide information from ASes to which a speaker advertises routes that the speaker received from other AS(es). Aggregation in S-BGP is consistent with all but the last purpose (although it generally may be an AS hop after aggregation before (5) can be realized). The ability to hide information is inconsistent with the ability to verify that the information supplied has not been inappropriately modified. S-BGP sacrifices information hiding to achieve integrity, authorization, and authenticity. An S-BGP speaker that performs route aggregation places into the Attestation path attribute all of the RAs from the routes that it is aggregating, after first making explicit the protected transitive information in each of those routes. 2. Terminology There are several terms, e.g., "last RA" and "first RA", that are used throughout this document which may not be intuitive, leading to confusion and possible misunderstanding. Those terms are defined here as they will be used in this document. The terms are ordered for readability instead of alphabetically. Keywords The keywords MUST, MUST NOT, REQUIRED, SHALL, SHALL NOT, SHOULD, SHOULD NOT, RECOMMENDED, MAY, and OPTIONAL, when they appear in this document, are to be interpreted as described in [RFC2119]. Lynn, Mikkelson, Seo [Page 15] Secure BGP June 2003 Protected Transitive Information The transitive routing information that S-BGP protects using digital signatures. The term includes both the address prefixes in either the NLRI field or the MP_REACH_NLRI path attribute, as well as a configurable set of other path attributes that contain information distributed beyond a single AS hop. Examples of the latter are the Origin and Community path attributes. Certification Authority (CA) An entity that issues digital certificates (especially X.509 certificates) and vouches for the binding between the data items in a certificate. [RFC2828] Certificate A certificate document in the form of a digital data object (a data object used by a computer) that contains a sequence of data items and to which is appended a computed digital signature value that depends on that sequence of data. A digital certificate binds an identity to a public key value, and possibly to additional data items. [RFC2828] Certificates contain several items of information, including the subject's public key, that are validated by a Certification Authority which then digitally signs the information using its private key. See [RFC3280]. Certificates used with S-BGP contain private extensions used [X509EXT] to convey authorization to use IP address blocks, AS identifiers, or [X509S-BGP] to bind a BGP Identifier to a specific router and AS. Certificates containing S-BGP extensions are issued to the CAs of Regional Internet Registries (APNIC, ARIN, RIPE, etc.), organizations that have the right to use IP address blocks or Autonomous System numbers. End-entity certificates containing one of the extensions are issued to networks, Autonomous Systems, and BGP speakers (routers). Other end-entity certificates are issued for management purposes, e.g., authentication of the S-BGP certificate, CRL, and AA repositories, and for access control of changes to the content of a repository. Each NOC uploads its certificates, CRLs, and address attestations to one of the replicated S-BGP repositories, and subsequently downloads all the certificates, CRLs, and address attestations for local validation, processing, and distribution to S-BGP speakers. End Entity An entity that is the subject of a public key certificate and that is using, or is permitted and able to use, the matching private key only for a purpose or purposes other than signing a digital certificate or CRL; i.e., an entity that is not a CA. [RFC2828] S-BGP end entities include networks, autonomous systems, S-BGP Lynn, Mikkelson, Seo [Page 16] Secure BGP June 2003 speakers, the individual administrators and operators of an autonomous system, and the S-BGP repositories. See [DISCEX]. Certificate Extract A condensation of the information in a certificate to only that needed by an S-BGP speaker for ongoing S-BGP operation -- the speaker's identity (BGP Identifier), public key, key identifier, and AS number. The S-BGP related certificates are downloaded from one of the S-BGP repositories by a NOC, verified according to local policy, and extracted. The extracted certificates are periodically uploaded to the S-BGP speakers in the AS. The extracted information MAY be signed using the NOC/AS's private key, so the integrity of, and authorization to use the information, can assured by verification of the NOC's signature covering the file. Alternate mechanisms MAY be used to assure the integrity of the information. Certificate Revocation Lists (CRLs) A data structure that enumerates digital certificates that have been invalidated by their issuer prior to when they were scheduled to expire. [RFC2828] A CRL is digitally signed by a Certification Authority using its private key. See [RFC3280]. Attestation Path Attribute (ATTEST) A new BGP optional transitive path attribute used to carry S-BGP countermeasure information. An attestation path attribute consists of the standard BGP path attribute header (Flags, Type Code, and Length) followed by a sequence of Attestations. Address Attestation (AA) An address attestation consists of an attestation header followed by a sequence of five parts: Signer, Signature, Expiry, ExplicitPA, and Target. An address attestation conveys authorization by the entity with the right to use a block of IP addresses (the signer) for one or more ASes (the targets) to originate an advertisement for the prefix(es) specified in the ExplicitPA part. Each organization that generates AAs uploads them to one of the replicated S-BGP repositories. Address Attestation Extract A condensation of the information in an AA to only that needed by an S-BGP speaker for ongoing S-BGP operation -- the set of valid prefixes and their authorized originating AS(es). The AAs are downloaded from one of the S-BGP repositories by a NOC, verified according to local policy, and extracted. The extracted AAs are periodically uploaded to the S-BGP speakers in the AS. The extracted information MAY be signed using the NOC/AS's private Lynn, Mikkelson, Seo [Page 17] Secure BGP June 2003 key, so the integrity of, and authorization to use the information, can assured by verification of the NOC's signature covering the file. Alternate mechanisms MAY be used to assure the integrity of the information. Signer (Part of an AA or RA) The Signer part contains information that identifies the entity that signed the attestation so that the entity's public key can be found to verify the signature. An signer is usually identified by an IP v4 or v6 address, but may also be identified by an AS number or a DNS name. Signature (Part of an AA or RA) The Signature part identifies the digital hash function and signature algorithm used to sign the attestation. Also present are the bytes of the signature and a key identifier that specifies which public key belonging to the signer should be used to verify the signature. The Signature part of an RA has a bit mask identifying the path attributes that are protected by the digital signature. The digital signature protects the Expiry, ExplicitPA, and Target parts of an AA or RA. The algorithm specified in this document, the Digital Signature Standard [DSS] and the Secure Hash Algorithm, revision 1 [SHA-1], MUST be implemented in all S-BGP speakers. Expiry (Part of an AA or RA) The Expiry part contains the date after which the attestation is no longer valid. Also present in the expiry part of an RA are the "A-bit" (used to indicate path aggregation) and the RASC field. ExplicitPA (Part of an AA or RA) The ExplicitPA part contains a canonicalized version of the protected transitive information covered by the digital signature. Explicit Data When a canonicalized copy of the protected transitive information is placed into the ExplicitPA part of an attestation, it is called explicit data. Implicit Data When the protected transitive information can be derived from either the UPDATE's NLRI or path attributes, or from data in a previous RA, it may be omitted from the ExplicitPA part of an RA. The omitted, redundant, information is called implicit data. Use of implicit data reduces the size of an RA. Lynn, Mikkelson, Seo [Page 18] Secure BGP June 2003 Target (Part of an AA or RA) The semantics of the Target part differs between AAs and RAs. In an AA, it contains the AS number(s) of the ASes that are being authorized by the signer of the AA to originate the prefixes in the prefix pseudo path attribute (see 3.1.1, part e) in the ExplicitPA part. The Target part of an RA contains the AS number of the AS (or ASes, e.g., when route reflectors are being used) that is being authorized by the signer (e.g., an S-BGP capable exit border router) to place the route into its Adj-RIB-In. Authenticator (of an extract file) An authenticator consists of at least the identity of the signer, the key identifier of the public key to be used in verifying the signature, and the signature information. Different vendors MAY use alternate mechanisms for the encoding of extract files and for the encoding of the signature information. Some vendors MAY omit the authenticator, when alternate mechanisms provide the integrity and authenticity of the extract file content. Route Attestation (RA) An RA consists of an attestation header followed by a sequence of five parts: Signer, Signature, Expiry, ExplicitPA, and Target. A route attestation is used to ensure the integrity and authenticity of the protected transitive information being propagated in BGP UPDATE messages. An RA is prepended to the RA section of the attestation path attribute by an AS's S-BGP capable exit border router. The RA section in an attestation path attribute contains an ordered sequence of one or more RA sequences. Generated RA Each S-BGP capable exit border router of an AS prepends an RA to the RA sequence contained within an UPDATE's attestation path attribute prior to propagating the UPDATE. The prepended RA is referred to as the locally generated RA. RA Sequence As a BGP advertisement propagates through an internet, each S-BGP capable exit border router prepends a locally generated and signed RA to the RA section of the attestation path attribute in UPDATE messages sent to external peers (analogous to the prepending of an AS number to the AS PATH path attribute). See Figure 3, which depicts three ASes and a schematic of the UPDATE message that would be sent by the exit border routers (N.8 and U.7). In the figure, the advertisement is being propagated from right to left. The ordered sequence of RAs in the attestation path attribute is referred to as an RA sequence. Lynn, Mikkelson, Seo [Page 19] Secure BGP June 2003 RA Sequence Count (RASC) A count of the number of (remaining) RAs in an RA sequence, including the RA containing the count. It is used to (recursively) linearize the RAs in an aggregation tree. The aggregation tree is necessary to enable speakers to resolve and validate implicit data. When combined with the identify of the RA signer, the count enables detection of the malicious removal of, or insertion of, RAs in an attestation path attribute. Lynn, Mikkelson, Seo [Page 20] Secure BGP June 2003 UPDATE UPDATE Sent to AS 2 by AS 8 Sent to AS 8 by AS 5 +--------------------------+ +--------------------------+ | Path Attributes: | | Path Attributes: | | AS Path: 8,8,5 | | AS Path: 5 | | ... (Other path attrs) | | ... (Other path attrs) | | Attestations: | | Attestations: | Last RA --> | RA: | | | | Signer: U.0.0.7 | | | | Sig: ... | | | | Expiry | | | | Date: ... | | | | A-bit: 0 | | | | RASC: 2 | | | | ExpPA | | | Explicit -> | Prefixes:10.1/16 | | | Data -> | AS Path: 8,8,5 | | | | Target: AS 2 | | | First RA -> | RA: | | RA: | | Signer: N.0.0.8 | | Signer: N.0.0.8 | | Sig: ... | | Sig: ... | | Expiry: | | Expiry: | | Date: ... | | Date: ... | | A-bit: 0 | | A-bit: 0 | | RASC: 1 | | RASC: 1 | | ExpPA: | | ExpPA: | Implicit -> | | | Prefixes:10.1/16 | Data -> | | | AS Path: 5 | | Target: AS 8 | | Target: AS 8 | | NLRI: 10.1/16 | | NLRI: 10.1/16 | +--------------------------+ +--------------------------+ | | AS 2 | AS 8 | AS 5 ..................... | ..................... | ............ :+-------+ +-------+: V :+-------+ +-------+: V :+-------+ : :|BGP Id | |BGP Id |: :|BGP Id | |BGP Id |: :|BGP Id | : <-- :|F.0.0.1| |F.0.0.3|: <-- :|U.0.0.7| |U.0.0.5|: <-- :|N.0.0.8| : :+-------+ +-------+: :+-------+ +-------+: :+-------+ : :...................: :...................: :..........: <-- Direction of UPDATE Propagation Origin AS .... +--+ : : Autonomous System | | S-BGP border router :..: +--+ Figure 3: Terminology Example First RA (in an RA Sequence) The RA inserted by the Origin AS; the final RA in an RA Sequence. The RASC in the last RA is 1. Lynn, Mikkelson, Seo [Page 21] Secure BGP June 2003 Last RA (in an RA Sequence) When an AS receives an advertisement, the RA immediately following the attestation path attribute header is called the "Last RA", i.e., the RA added to the attestation path attribute by the peer from which the UPDATE was received. The RA designated by the term Last RA changes on exit from each S-BGP capable AS; the First RA does not. Previous, Current, and Next RA (in an RA Sequence) When processing an RA sequence, on RA at a time, the Current RA begins with the Last RA and ends with the First RA. The RA processed immediately before the Current RA is called the Previous RA; in the diagram it is to the left of the Current RA. The RA that will be processed next is called the Next RA. The Next RA is the one that was inserted before the current RA. In the diagram, the Next RA is to the right of the Current RA. RA Sub-Sequence When an S-BGP speaker performs aggregation, the received RA sequences from each of the UPDATEs that are being aggregated are concatenated into a new RA sequence representing the aggregate. Each individual RA sequence is called an RA sub-sequence of the aggregated RA sequence. When aggregation is performed, the received RA sequences of each advertisement that is to be part of the aggregate are concatenated before the locally generated RA is prepended. The RASC field of the locally generated RA is set to one more than the number of RAs that were concatenated. Equivalently, it is set to 1 plus the sum of the RASC fields of the first RA in each of the RA sub-sequences being aggregated. 3. Attestation Path Attribute (ATTEST) S-BGP uses a new optional, transitive BGP path attribute to distribute in-band security information to BGP routers in UPDATE messages. The attestation path attribute (ATTEST) contains an ordered list of Route Attestations. The use of in-band security information makes the dynamics of the protection mechanisms match the dynamics of topology changes. This is especially important when, e.g., a major fiber cut necessitates new peerings that do not exist under normal conditions. In these extraordinary situations, the ATTEST path attribute MAY also contain a set of Address Attestations, to handle the case where an organization needs to temporarily use a new provider. The ordering of the RAs in the route attestation section is described in sections 2 and 3.1.2. One route attestation is prepended to the RA sequence in the attestation path attribute in an UPDATE message by each S-BGP capable Autonomous System (AS) through which the UPDATE is propagated. It is Lynn, Mikkelson, Seo [Page 22] Secure BGP June 2003 prepended by the AS's exit border router and identifies (in the Target part) the AS(es) that are being authorized to use the route -- usually the AS(es) to which the UPDATE message is being sent. The RA contains a digital signature that protects both the protected transitive information being announced to the receiving AS(es) and the identity of those AS(es). The identity of a receiving AS is necessary both to protect against some forms of cut and splice attacks and to provide explicit authorization for the speakers in the receiving AS to use the information in the advertisement. One consequence of this requirement is that a speaker can no longer simply forward the contents of an UPDATE message to peers in different neighboring ASes unless each of those ASes has been included in the list of ASes in the target field of the RA. See, e.g., sign-AS in Appendix C.3.1. The capability to include multiple ASes in the Target part of an attestation may also be used when, e.g., the current and receiving ASes receive UPDATEs from a common external route reflector. The attestation path attribute has Type Code *IANA-TBD*. The BGP path attribute header is as described in [RFCbgp]. The following sections describe the attestation path attribute's value. 3.1. Attestation Path Attribute Formats Address attestations and route attestations share a common format, described in section 3.1.1. Each logically related set of fields in an attestation is called a "part". An S-BGP part code is assigned to the section for RAs and AAs, as well as to each part of an attestation. 3.1.1. Route and Address Attestations The parts within an attestation MUST appear in the order shown in Figure 4. Each part of an attestation starts with a four-bit Part Code field. Following the Part Code field is a 12-bit Length field that contains the length in octets of the value (remainder of the attestation part). I.e., the length does not include the two octets containing the Part Code and Length fields. The parts of an address or route attestation are as follows: Lynn, Mikkelson, Seo [Page 23] Secure BGP June 2003 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Object Type/Length(length = 2)| +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-... | Signer (variable length) +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-... | Signature (variable length) +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-... ----- | Expiry (length = 8 for RAs, 6 for AAs) ^ +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-... | | ExplicitPA (variable length) Signed +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-... | | Target (variable length) v +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-... ----- Figure 4: Structure of an Address or Route Attestation a) Attestation Objects (Part Codes 8, 9, and 14): The Part Code is 8 for a route attestation, and 9 for an address attestation. Part Code 14 is reserved for an extract file authenticator, if a vendor chooses to use this encoding. The twelve-bit length is the length of the rest of the attestation (not including the Part Code and Length). 0 1 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ |1 0 0 0| RALength | RA +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ |1 0 0 1| AALength | AA +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ |1 1 1 0| AuthenticatorLength | Encoding for an optional +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ Extract File Authenticator Figure 5: Route and Address Attestation and Authenticator Headers b) Signer part (Part Code 1): The Signer part identifies the entity which signed the attestation. The public key required to verify the signature is in a certificate issued to this entity. The signer can be described by one of four name formats: a four-octet AS number, a four-octet IPv4 address, a sixteen-octet IPv6 address, or a variable length DNS name. DNS format names MUST NOT be terminated by a NIL character. The AFI field is a two-octet field following the SignerLength field that indicates the format of the following identifier. The values for this field are taken from the Address Lynn, Mikkelson, Seo [Page 24] Secure BGP June 2003 Family Identifier number space of [IANA-AFI]. I.e., it is 1 for an IPv4 address, 2 for an IPv6 address, 18 for an AS number, and 16 for a DNS name. The SignerLength field contains two plus the length of the identifier in the SignerData field. 0 1 2 3 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ |0 0 0 1| SignerLength | AFI | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | SignerData (variable length) +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+... Figure 6: Signer Part The SignerData field contains the identity of the signer encoded in one of the following four formats: +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | AS Number (length 4) | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | IPv4 (length 4) | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | IPv6 (length 16) | | | | | | | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Textual DNS Name (N octets, not NIL terminated) +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-... Figure 7: Formats of Signer Name Forms Note that S-BGP encodes all AS numbers as four octet quantities, see [AS4Bytes]. c) Signature part (Part Code 2): The Signature part contains the information necessary to verify the integrity of the protected transitive information associated with the attestation. The signature algorithm identifier, SigAlgID, follows the SignatureLength field and is one octet long. Currently one signature algorithm is defined, DSA with the SHA-1 hash; this algorithm is assigned an ID of 2 [IANA-SAN]. Lynn, Mikkelson, Seo [Page 25] Secure BGP June 2003 The next field is a one-octet KeyId used to identify which of multiple valid public keys for the signer was used to generate the signature. For DSA, the value is the (last octet of) the SubjectKeyIdentifier field in the Subject Key Identifier extension in the signer's certificate. Following the KeyId is a one-octet CoverageLen field, providing the length in octets of the immediately following CoverageMask field. The final field in the Signature part is the signature itself, which for DSA consists of R (20 octets) followed by S (20 octets). 0 1 2 3 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ |0 0 1 0| SignatureLength | SigAlgID | KeyId | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | CoverageLen | CoverageMask (variable length) +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | SignatureBytes (40 octets for DSA signature...) | | (20 octets of DSA R) | | (20 octets of DSA S) | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ Figure 8: Signature Part The CoverageMask field identifies which BGP path attributes are protected by the signature. Only RAs have a CoverageMask; AAs do not, and set the CoverageLen field to zero. Each bit corresponds to a Path Attribute Type Code. For each path attribute covered by the signature, the corresponding CoverageMask bit MUST be set to 1. The NLRI is assigned bit zero (for either the IPv4 NLRI at the end of an UPDATE message, or for the MP_REACH_NLRI path attribute (see e, ExplicitPA part, below). In order to allow path attributes defined in the future to be part of the protected transitive information, the coverage bits are placed in ascending order starting at the leftmost bit in the network byte order mask. In the following diagram the zero bits identify attributes that are never protected due to their non- transitive usage, 1 indicates attributes that MUST always protected (when present), and the "?" bits correspond to attributes which MAY be protected, according to local policy. Note that the ATTEST path attribute itself is never protected. Lynn, Mikkelson, Seo [Page 26] Secure BGP June 2003 0 1 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+... |? ? 1 0 0 0 ? ? ? 0 0 ? 0 0 0 0 ? +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+... 0: NLRI or MP_REACH_NLRI; 1: ORIGIN; 2: AS PATH; 6: ATOMIC AGGREGATE; 7: AGGREGATOR; 8: COMMUNITIES 11: DPA; 16: EXTENDED COMMUNITY; ... (others to be defined) Figure 9: CoverageMask Field d) Expiry part (Part Code 3): The Expiry part specifies the date after which the attestation should not be considered valid. The Part Code field is four bits, and the following Length field is 12 bits. Note that the length is always 6 for RAs (which include the A-bit and RASC fields) and 4 for AAs (which do not). The first field after ExpiryLength occupies two octets and contains the four-digit year, followed by a one-octet field whose four least significant bits contain the month (1 to 12), followed by a one-octet field containing the day (1 to 31). The attestation is not valid after the specified year, month, and day. The Expiry part of an RA contains in addition a two-octet field containing the 1-bit A-bit and 11-bit RASC sub-fields. The RASC field indicates how many RAs, including the RA containing the field, remain in the RA sequence of which this RA is a member (see section 2). The A-bit field indicates whether or not the speaker performed route aggregation: 1 indicates it did, and 0 indicates it did not. 0 1 2 3 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ Expiry |0 0 1 1|ExpiryLength(AA=4,RA=6)| Year, e.g., 2002 = 0x7d2 | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | 0 |Month:4|0 0 0 Day:8 | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ |A| RASC |(RAs only) +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ Figure 10: Expiry Part e) ExplicitPA part (Part Code 4): The ExplicitPA part may contain a canonicalized version of the protected transitive information. The path attributes to be protected are specified by local policy and indicated by a bit in Lynn, Mikkelson, Seo [Page 27] Secure BGP June 2003 the CoverageMask as described above. The validation process must be able to find the actual values protected by the digital signature (to verify it) even though the values of the actual NLRI or path attributes may change as an UPDATE message is propagated from AS to AS. Information in the ExplicitPAs field is encoded as standard BGP path attributes with path attribute Flags, Type Code, and Length (see [RFCbgp]). The the information in the attribute value field is canonicalized. The individual path attributes in the ExplicitPAs field (and as hashed for signature computation and verification) MUST be sorted by ascending path attribute Type Code. 0 1 2 3 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ |0 1 0 0| ExplicitPALength | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-... | ExplicitPAs (variable length) -- sequence of path attributes +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-... Figure 11: ExplicitPA Part Prefixes, from either the NLRI field or from the MP_REACH_NLRI path attribute, are encoded in the ExplicitPAs field as an optional transitive path attribute with Type Code 0, as shown in the figure below. The attribute value consists of a two-octet AddressFamilyIndicator field (see [IANA-AFI]), a one-octet SAFI field (see [IANA-SAFI] [RFC2858]), a one-octet maximum prefix length field, and one or more prefixes. In the case of IPv4 NLRI, the AddressFamilyIndicator field contains 1 (IPv4) and the SAFI is usually 1 (unicast). The individual prefixes MUST be sorted by ascending
(but encoded in the standard way -- as a one-octet bit count and the number of prefix octets required to hold the specified number of bits; unused bits MUST be zero). Having the speaker that creates the RA sort the prefixes simplifies RA validation for all speakers that receive an RA. Since the prefix information uses path attribute Type Code 0, the prefixes will, when present, be the first entry in the ExplicitPAs field. 0 1 2 3 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+... |1 1 0 E 0 0 0 0| Type Code 0 | Length :Extended Length +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | AddressFamilyIndicator | SAFI | MaxPrefixLen | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | PrefixLength | Prefix (other PrefixLength/Prefix pairs) +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+... Figure 12: Prefix Encoding Lynn, Mikkelson, Seo [Page 28] Secure BGP June 2003 This canonicalized encoding is used to make the prefix information invariant between NLRI and MP_REACH_NLRI, since IPv4 prefixes may be encoded in either format, and the encoding may change as an UPDATE message propagates through ASes. When canonicalizing the (IPv4) NLRI field, the AddressFamilyIndicator MUST be set to 1, and the SAFI to 1 when the IPv4 addresses are unicast, or to 2 when the IPv4 addresses are multicast (within the 224/4 prefix). The maximum prefix length field, MaxPrefixLen, is zero in RAs. In an AA, it indicates the maximum prefix length of any more specific prefix that the prefix owner is authorizing to be advertised. This is used to thwart an attack where a more specific prefix is received, e.g., from an adversary or an AS not running S-BGP. If an advertisement for a more-specific is received, it is an auditable event and MUST be rejected. Note that AA information is applied to all UPDATEs received, not just those containing an ATTEST path attribute. f) Target part (Part Code 5): The Target part identifies the subject of the attestation. The target of an RA is the AS number of the BGP speaker(s) to which the UPDATE message will be sent, directly, or indirectly via a route reflector. The target of an AA is a list of AS numbers of the ASes being authorized to originate a route to the prefixes in the ExplicitData part, e.g., when the organization owning the prefixes is multihomed to different ASes. The length of the Target part is variable, and the number of AS numbers present may be computed by subtracting two octets from the TargetLength and dividing by four. AS numbers MUST be encoded as four octet values not as two octets values. The AFI field contains 18, per [IANA-AFI], to indicate the target uses the AS number format. 0 1 2 3 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ |0 1 0 1| TargetLength | AFI = 18 (AS number) | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | AS number | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | (possibly more AS numbers) +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+... Figure 13: Target Part Lynn, Mikkelson, Seo [Page 29] Secure BGP June 2003 3.1.2. RA Sequences and Aggregation The order of RAs in the RA sequence in an ATTEST path attribute is fairly straightforward when there is no aggregation. Each exit border speaker prepends its locally generated and signed RA to the RA sequence in the ATTEST path attribute before advertising the route to an external peer. The RASC (RA Sequence Count) field in the Expiry part of the locally generated RA is set to one more than the RASC field of the Last RA in the received ATTEST path attribute, or to one in a locally originated advertisement. The A-bit is set to 0. Aggregation requires that the RA sequences from each of the routes being aggregated be concatenated into a single RA sequence. There are no ordering requirements on the concatenation operation. Figure 14 illustrates RA lcl concatenating two RA sequences: RA a, RA b, RA c; and RA z. RA a and RA z are the Last RAs in their respective RA sequences. Note that in this example, the RA sequence RA a, RA b, RA c is itself the result of an aggregation, however RA lcl does not need to be cognizant of that fact when concatenating the individual RA sequences. When the aggregator's RA (RA lcl) is generated and prepended to the concatenated RA sequence the A-bit is set to 1 and the RASC field is set to one more than the sum of the RASC fields of the Last RAs in each of the RA sequences being concatenated (in the example, 1 for the lcl RA, plus 3 from RA a, plus 1 from RA z). RA lcl | RA a RA b RA c | RA z from aggregator | Last in seq. ----------------------> | Last in seq. +--------------+ +----------+ +----------+ +----------+ +----------+ | (other data) | | | | | | | | | | RASC: 5 | | RASC: 3 | | RASC: 1 | | RASC: 1 | | RASC: 1 | | A-bit: 1 | | A-bit: 1 | | A-bit: 0 | | A-bit: 0 | | A-bit: 0 | +--------------+ +----------+ +----------+ +----------+ +----------+ Figure 14: Aggregation Example An S-BGP speaker can (recursively) locate the RA sub-sequences which were concatenated during aggregation as follows. When an RA with the A-bit set is located, say RA lcl in the figure, its RASC field contains the number of RAs in the aggregate associated with that RA (lcl): 5. If the number is less than one, a parse error should be handled. The RA sequences that were concatenated are found by subtracting 1 (representing the RA of the aggregator, RA lcl) from the working count (resulting in 4). The RASC field of the next RA, 3 from RA a, is used to determine the RA sequence length of a RA sub- sequence in the aggregation; that count is subtracted from the working count (resulting in 1). If the number is less than zero, a parse error should be handled. If the count is greater than zero there is another RA sub-sequence in the aggregation. The number of RAs in the Previous RA sub-sequence, 3, is skipped to locate the Last RA in the Next RA sub-sequence, i.e., RA z. Its RASC count determines the length of the next of the RA sub-sequences. The Lynn, Mikkelson, Seo [Page 30] Secure BGP June 2003 process is repeated until the working count reaches zero. This deconstruction of the RA sequences in an aggregate is used by S-BGP speakers to determine the correspondence between the AS numbers in the AS_SET created by aggregation and the individual RA sequences, so that the authorized originating AS and path can be validated (see section 3.2.2.2). 3.2. S-BGP Processing Initialization of security functions is performed. The certificates and/or the public keys of the peers are loaded for use by IPsec. When the BGP process is initialized, the S-BGP DSA parameters are initialized from, e.g., a trusted S-BGP root certificate. A working copy of the trusted NOC's public key should be initialized, e.g., from the trusted NOC's certificate. The validated public key information for the S-BGP speakers should be loaded; an implementation may insure the integrity and authenticity of the authorized public keys by using the NOC's public key to verify a signature of the data. Similarly, the integrity and authenticity of the address attestation information used to verify the legitimacy of an originating AS should be verified. Note that digital signatures are not required if an alternate mechanism to insure integrity and authenticity of the information is being used. Implementation Note: Depending on the implementation chosen for the AA cache, this action may have the side effect of constructing a routing table without any Adj-RIB-Ins. The private key which the speaker will use to sign route attestations is activated for use. Private keys SHOULD be stored in cryptographic hardware, e.g., in a PCMCIA card, and activated via a software method. An implementation MAY choose to check that the public key corresponding to the private key that will be used to sign RAs is in the public key file by signing, e.g., a random number, and then trying to verify the signature. If the signature cannot be verified, the speaker's configuration needs to be corrected. A non-volatile cache of validated routes (containing RAs) MAY also be preloaded, with the routes all marked as inactive. If the cache is preloaded, the integrity and authenticity of the data SHOULD be verified. One way to implement the verification is to have the S-BGP speaker sign a hash of the data it wrote to the cache using its private key. S-BGP specific policy for the speaker, its peers, and other speakers Lynn, Mikkelson, Seo [Page 31] Secure BGP June 2003 and autonomous systems can be loaded on restarts. There SHOULD be a mechanism to ensure the integrity and authenticity of the configured policy. One way would be for the NOC to sign it using its private key. IPsec SAs are negotiated for each peering session as they are created. Additional support, described in the sections to follow and Appendix C, is recommended to help manage the incremental deployment of S-BGP. 3.2.1. Route Attestation Processing The processing of route attestations, which are used to validate the integrity of the AS path and other protected transitive information, consists of several steps. The structure and internal consistency of the ATTEST path attribute and the attestations that it contains needs to be checked. If an error is detected, a parse error is handled. The signatures in received RAs are verified. In order to verify an RA's signature, all the signed information (the Expiry, ExplicitPA, and Target parts) of the RA must be identified. The Expiry and Target parts contain all the data needed for their verification. However, the ExplicitPA part will usually not contain all the data identified by the CoverageMask field in the Signature part; some data might be implicit. Any implicit data in the Last RA is obtained from the NLRI and/or path attributes in the advertisement. Any implicit data in a subsequent RA is located by looking for that data in the previous RA (or in the aggregator's RA when the current RA is the Last RA in an RA sub-sequence). Note that the ExplicitPA's length field has to be adjusted to include the length of the resolved implicit data. RA validation also includes both verifying that each AS in the AS path has a corresponding RA, and verifying that the protected transitive information is consistent through all the RAs in the advertisement. Routes (per prefix) that are successfully validated SHOULD be so marked in the Adj-RIB-In and, per local policy, preferred over routes that are not protected by S-BGP mechanisms. Use of routes that cannot be validated is a local policy issue; see, e.g., Appendix C.5.1,2,3,4. Routes for which validation fails SHOULD NOT, per local policy, be candidates for the route selection process. Note: if all routes for a given prefix result in verification failures (as opposed to being un-protected), local policy MAY specify that such a route be used; see, e.g., only-route in Appendix C.1. Lynn, Mikkelson, Seo [Page 32] Secure BGP June 2003 Sending an Advertisement Whenever an advertisement is sent to an external peer, the BGP speaker SHOULD generate and sign an RA. The contents of the RA is as follows: The Signer part contains either the speaker's BGP Router Identifier, encoded as an IPv4 address, when the speaker has its own key; or, when a single key is to be used by multiple speakers in an AS, the Signer part encodes the AS number using the AS name form. The Signature part contains: an AlgorithmIdentifier field with the value 2 [IANA-SAN], indicating DSA with the SHA-1 hash; the KeyId field contains the least significant byte of the speaker's Subject Public Key Identifier; the CoverageMask field is set to a mask of the protected transitive information that appears in the UPDATE; the CoverageLen field is set to the number of bytes required to hold the CoverageMask field; and the SignatureBytes field is set to the network order concatenation of the 20-byte "R" and 20-byte "S" values generated by the DSA. The Expiry part contains: an expiration date that is in the future. Note that a new advertisement MUST be sent before the selected expiration date. Selection of the expiration date is a local policy decision. The A-bit and RASC field are set as follows: If the speaker is originating the route, there will be no received RAs, so the RA signed by the speaker will be the only RA in the attestation path attribute. Its RASC field is set to 1. The A-bit is set to 0. If the speaker is neither originating the route nor performing path aggregation, the RA is prepended to the RAs that were received with the AS path used in the UPDATE. Its RASC field is set to 1 more than the contents of the RASC field in the Last RA in the received attestation path attribute. The A-bit is set to 0. If the speaker is performing path aggregation, then the RA signed by the speaker is prepended to the concatenation of the RA sequences associated with each of the routes that are being aggregated. Its RASC field is set to 1 more than the sum of the total number of RAs in the concatenation. The A-bit is set to 1. Lynn, Mikkelson, Seo [Page 33] Secure BGP June 2003 3.2.1.1. Route Attestation Validation Several steps are necessary to validate an RA sequence. First, the protected transitive information for all RAs in the sequence must be determined, including resolution of any implicit data. Second, any canonicalization rules must be performed (this applies to the NLRI/MP_REACH_NLRI field, and the AS PATH path attribute). Each part of the RA involved in validation must be checked. Then the prefixes in the NLRI field or MP_REACH_NLRI path attribute must be validated against both the authorized prefixes from the RA sequence(s), and, for each prefix, its originating AS must be matched with cached AA information. Finally, the digital signature of each RA must be verified. The actions which should be taken if validation fails at different stages of this process are local policy decisions. Protected Transitive Information To verify a given RA, all path attributes for which the corresponding bit is set in the CoverageMask field are required to resolve implicit data as input to the signature verification function. Path attributes marked as protected in the CoverageMask which are not in the RA's ExplicitPAs field are implicit data that has to be resolved. For the Last RA in the sequence, implicit data is located in the NLRI and/or path attributes parts of the UPDATE message. That data must be canonicalized before it is used. Once canonicalized, all data for the Last RA is explicit. See section 3.2.3.4 for discussion of validation of unknown path attributes. If data for a path attribute is already explicit in the Last RA, it MUST be compared to the unprotected data from the path attribute. For the subsequent RAs, any implicit data is copied from the now explicit data in the previous RA. The propagation of resolved data from one RA to the next RA is repeated for all RAs in the sequence, until all the RAs have been processed. When processing the RA sub-sequences, any implicit data in the Last RA is copied from the RA corresponding to the aggregation point, i.e., the one with the A-bit set (see section 3.1.2). The individual RA sub-sequences are then processed as above until the all the RAs in the RA sub-sequence have been processed. Canonicalization Path attributes are canonicalized to simplify the validation process. Of the currently defined path attributes, a canonical form is defined only for the AS PATH and the MP_REACH_NLRI path attributes. For all the other protected path attributes, their contents are copied verbatim into the ExplicitPAs field. Lynn, Mikkelson, Seo [Page 34] Secure BGP June 2003 For the AS PATH attribute, adjacent AS_SEQUENCE segments are merged into a single segment (up to the standard limit of 255 ASes in a segment). The ASes in an AS_SET segment are sorted in numerically increasing order. Note that all AS numbers in the ExplicitPA part are four-octet quantities. Since IPv4 address prefixes may be carried in either the NLRI part of an UPDATE message or in the MP_REACH_NLRI path attribute, and can in fact be converted from one representation to the other as an UPDATE message is propagated through successive ASes, canonicalization is used to make the protected prefix information invariant between the two encodings (see 3.1.1, part e). The prefixes in the NLRI and MP_REACH_NLRI path attribute are sorted for canonicalization. Canonicalization of an implicit NLRI requires that a path attribute header of Type Code 0 be generated for the NLRI, as well as an AFI and a SAFI, so that the NLRI is represented in the same format as if it had been in an MP_REACH_NLRI path attribute (section 3.1.1, part e). An MP_REACH_NLRI path attribute is canonicalized by changing the Flags to mandatory transitive and the Type Code to 0, so that the prefixes in an MP_REACH_NLRI path attribute may be compared against a canonicalized NLRI. Propagation of Explicit Data to the Next RA Special handling is required when propagating explicit prefix and AS PATH information from one RA to the next one in an RA sequence. The AS number corresponding to the Previous RA MUST be one of the AS(es) in the target of the Current RA. The AS PATH for the Current RA is computed by removing the Last AS number (possibly repeated due to prepending). The AS number removed MUST belong to the AS that authorized the signer of the Previous RA. Aggregations require that the AS_SET be disassembled and the AS PATH for each sub-sequence of RAs be determined. The AS PATH path attribute for the Last RA in each sub-sequence MUST be explicit in the ExplicitPAs field, so this disassembly is straightforward. Validation requires that each AS number in the AS_SET be represented in one or more of the sub-sequence AS PATHs. Otherwise, verification fails. Validation of Signed RA Parts The Expiry part contains an expiration date. If the verification occurs at a time after the expiration date, validation fails (subject to local policy). Lynn, Mikkelson, Seo [Page 35] Secure BGP June 2003 The Target part of an RA describes the AS number(s) to which the route was advertised. Validation MUST ensure that for each RA (except the first RA in an RA sequence or an aggregated RA sub- sequence, i.e., RAs for which there is no Next RA), the AS number of the signer is one of the AS numbers in the Target part of the Next RA. Special validation of the Last RA in a sequence must be performed when this Last RA has any explicit data. Since explicit data in the Last RA should match the equivalent implicit data found in the UPDATE's path attributes and NLRI, validation MUST ensure that the path attributes and NLRI in the UPDATE are the same as the explicit data in the Last RA. Explicit data for a Path attribute that does not need to be canonicalized should be byte-compared against the corresponding path attribute. The AS PATH path attribute in the UPDATE and the NLRI or MP_REACH_NLRI path attribute is canonicalized and then byte-compared against the AS PATH and NLRI in the ExplicitPA data, if present. If any path attribute in the UPDATE does not match the corresponding path attribute in the ExplicitPAs field of the Last RA, validation fails. Policy may dictate that in the case of failure the signed, explicit version of the path attribute be used, if the signature verification succeeds. These steps of verification may be carried out before or while finding and canonicalizing implicit data. The ExplicitPA part of an RA is validated through the following validation steps and signature verification. Validation of Prefixes Prefixes found in the NLRI or MP_REACH_NLRI path attribute MUST be validated against Address Attestation information. The AAs specify the ASes authorized to originate a route for a prefix and the maximum length of a prefix. Throughout this section "NLRI" refers to a canonicalized NLRI. The AS which originated a prefix is determined from the RA sequence. If no aggregation has occurred, the First RA in the sequence will contain one AS number. This AS number is used to validate all the prefixes in the NLRI. If aggregation has occurred, the First RA of each RA sub-sequence will provide the originating AS number and the set of prefixes that it originated. If not all prefixes in the NLRI were advertised by at least one of the originating AS numbers, validation (for those prefixes) fails; this is an auditable event. Policy may allow use of all prefixes except those failing AA validation. For each prefix in the NLRI, an AA must be present which lists the originating AS number in its Target, and the prefix length must not exceed the length specified Lynn, Mikkelson, Seo [Page 36] Secure BGP June 2003 by MaxPrefixLen. Otherwise, validation fails; failure is an auditable event. Again, policy may allow use of the sub-set of prefixes for which AA validation is successful. Signature Verification The signature of an RA MUST be verified. Verification of the signature requires that each protected path attribute be placed into the ExplicitPA part. If any path attributes were implicit, a new ExplicitPA part must be temporarily constructed for this purpose. Note that this construction is logical and does not specify how it is affected by an implementation. The length field of the ExplicitPA part must be set to include all the (temporarily constructed) explicit data. The path attributes MUST be sorted in the ExplicitPAs field by the path attribute Type Code, in increasing numerical order. Note that the canonicalized NLRI will be first, with Type Code 0. If no implicit data is used, sorting should not necessary because an S-BGP speaker MUST sort them when it generated the RA it advertised. The signature is verified over the Expiry part, the constructed ExplicitPA part, and the Target part. They are hashed as a logically contiguous block. The public key used for verification is determined from the name in the Signer part of the RA and the KeyId field in the Signature part. If signature verification fails, possibly because the required key is not in the public key database, validation of the RA fails; this is an auditable event. Failure because the required key is missing from the database MAY be an indication to the NOC to look for new public keys. 3.2.1.2. Route Attestation Creation This section describes the steps necessary to create a Route Attestation. The NLRI which will be advertised with the route must be available so that it can be signed. If aggregation has been performed, the RA sequences for each aggregated route must be available and the ExplicitPA part of the Last RA in each RA sub sequence MUST have all data explicit. When route aggregation is not being performed only the RA sequence received for the route being advertised is needed. Implementation Note: Several parts and fields of an RA created by a given S-BGP speaker change slowly. These include the Signer part, the expiration date fields of the Expiry part, and the SignatureAlgorithmID and KeyId fields of the Signature part. An S-BGP speaker MAY choose to initialize these values at the initialization of the BGP process, and then update them as needed. The most involved step of creating an RA is determining the CoverageMask and building the ExplicitPA part. The signature part Lynn, Mikkelson, Seo [Page 37] Secure BGP June 2003 cannot be completed until this has been done. After the discussion of the construction of the parts of the new RA, details of how the ExplicitPA parts of the Next (or subsequent) RA(s) in each RA sequence may be altered to reduce the size of the attestation attribute are provided. Attestation Object Type The Part Code in the Attestation Object Type field is set to 8 (RA). The value of the AttestationLength field cannot be determined until the ExplicitPA part has been (logically) constructed with the explicit form of the protected transitive information. Signer part The signer of an RA is an S-BGP speaker. It is identified either by the speaker's BGP Identifier (when the speaker signs using its own DSA key), or by the number of the AS that authorized the speaker to act as its agent (when a single DSA key is used by multiple speakers). A BGP Identifier is encoded using the IPv4 name form; an AS number is encoded using the four-octet AS number name form. Note: One reason to have a single key pair used by multiple speakers is to allow the rapid deployment of new S-BGP speakers in an AS (the key can be distributed through the S-BGP Repositories and be globally available before a new router is deployed). One reason to use per-speaker keys is to reduce the impact of a key compromise. One can install a new router and have it use a shared key, then switch to a per-speaker key after enough time has elapsed for it to be propagated through the S-BGP repositories to all AS's S-BGP speakers. Signature part The SignatureAlgorithmID and KeyId are determined by the Certificate as well. The SignatureLength field and CoverageLen field of the Signature part are computed after the coverage mask has been determined. The coverage mask is computed using information about which path attributes are being placed in the UPDATE message, which path attributes were protected by the RA sequence(s) from the route(s) being covered, and policy. Only the path attributes which S-BGP may protect (see section 3.1.1, part c) and which are present in the UPDATE may have the corresponding bit in the coverage mask set to 1. Unknown path attributes may also be covered if the path attribute was protected by the Last RA in the received RA sequence. Local policy may specify particular path attributes that are not protected (including unknown attributes) when Lynn, Mikkelson, Seo [Page 38] Secure BGP June 2003 originating an UPDATE; the corresponding bits for these should be set to 0 in the coverage mask; see, e.g., send-explicit in Appendix C.5.5. Policy may specify not protecting a path attribute unless it was protected in a received RA. Once the bits of the coverage mask have been specified, the length of the coverage mask, in octets, and the length of the Signature part are known, and the Signature part (less the signature itself) is complete. Expiry part The Len field of the Expiry part has the value 6 for an RA. The expiration date is set per local policy. Operational experience will provide guidance in selecting a good value, e.g., N days in the future. The smaller the value, the more frequently an advertisement will be required to simply extend the validity period. The RASC field should be computed as one more than the sum of the RASC fields of the set of RA sequences which will be placed before the new RA in the attestation attribute, as described in section 3.1.2. If aggregation has been performed by this speaker, the A-bit is set to 1, else it is set to 0. ExplicitPA part For each path attribute marked as protected by the coverage mask, a (logical) copy of the path attribute is placed in the ExplicitPA part so that the correct signature can be computed. The explicit path attribute data MUST be in the canonical form so that it can be verified by another S-BGP speaker, including comparison against canonicalized implicit path attributes. This means that the NLRI/MP_REACH_NLRI are canonicalized to a path attribute with Type Code of 0 and that the prefixes MUST be sorted in ascending order by prefix/prefix length (not the prefix length/prefix encoding used for prefixes) (see section 3.2.1.2). All protected path attributes are hashed as part of the ExplicitPAs field. S-BGP speakers MUST sort the path attributes by Type Code in ascending numerical order in the ExplicitPAs field. Once the explicit path attributes are identified, the Length field of the ExplicitPA part may be set. Generally, the explicit data will subsequently be removed (made implicit) after signature generation to reduce the size of UPDATEs sent to peers; see, e.g., C.5.5,6. Target part The Target field is computed from the AS number(s) of the peer(s) to which the route is being advertised (or of the next forwarding Lynn, Mikkelson, Seo [Page 39] Secure BGP June 2003 hop peers in the case of external route reflection). See, e.g., sign-AS in C.3.1. Implementation Note: When the target contains a single AS number and the UPDATE will be sent to peers in multiple ASes, it can be more efficient to create the Expiry and ExplicitPA parts of the RA first, as described here. This way, a common hash may be computed that excludes the Target, and final individual hashes may then be computed for each RA from the common hash and the Target part for each RA. Signature After all parts of the RA are constructed, the signature can be computed. It covers the Expiry, ExplicitPA, and Target parts, which are hashed as one contiguous block. The hash is signed, using the key specified by the Signer part and the KeyId field of the Signature part. The resulting signature is copied into the Signature field of the Signature part. Explicit and Implicit Data in Received RAs After the new RA has been constructed, the new RA is prepended to the received RA sequence to produce the RA sequence which is placed in the attestation attribute. If the local speaker has performed aggregation, the received RA sequences for each aggregated route (in which the Last RAs have Explicit Data for at least the NLRI and AS PATH) are concatenated into one sequence as described in section 3.1.2 before the locally generated RA is prepended. Further processing of these received sequences SHOULD be done, however. Since most path attributes can be implicitly derived from the previous RA in a sequence (section 3.2.1.1), UPDATE message sizes can be reduced if explicit path attributes listed in the received sequences' RAs can be removed. Explicit data can be removed from the Last RA when the data can be deduced from the explicit data in the newly generated RA. The processing done here will speak only of the Last RA in each received RA sequence, assuming that other ASes also have converted explicit data to implicit whenever possible before prepending their locally generated RA. It is possible that this is not the case; a speaker may recursively apply the processing here to all RAs in an RA sequence; see, e.g., C.5.5,6 and C.6.4. If the S-BGP speaker creating the new RA did not perform aggregation, there is only one received RA sequence. The speaker may compare each explicit path attribute in the Last RA of this sequence against the explicit path attributes in the new RA. If a given path attribute is identical, including the path attribute Flags, then this path attribute MAY be removed from the ExplicitPAs field of the Last RA. Lynn, Mikkelson, Seo [Page 40] Secure BGP June 2003 The ExplicitPA's Length field in the Last RA must be altered to reflect the removal. Implementation Note: More efficient comparison of transitive path attributes in an UPDATE to the corresponding ones of the Last received RA maybe achieved, at the cost of more memory, by making all covered path attributes in the Last RA explicit, or at least being able to locate the canonicalized path attributes that were received -- the path attributes MUST be saved per the BGP specification. If any path attributes other than those with predictable changes, e.g., the AS PATH, differ, then the data must be left explicit in the Last received RA. Any unknown protected path attributes will be retained as explicit data as the speaker will set the Partial bit in the unknown path attribute Flags, thus creating a difference between the new RA and the Last received RA. If the new RA does not protect a path attribute covered by the Last RA, this path attribute must be left in the ExplicitPA of the Last RA. The AS PATH as computed for the explicit data of the new RA will differ from the Last received RA. However, when it is possible to compute the correct AS PATH attribute for the Last RA (by simply removing the Last AS number from the AS PATH sequence) (section 3.2.1.1), the explicit AS PATH entry MAY be removed from the ExplicitPAs field of the Last received RA. If the S-BGP speaker creating the new RA has performed aggregation, the same process may be followed for the Last RA of each received RA sequence in the aggregate. However the AS PATH attribute and the canonicalized NLRI MUST appear in the ExplicitPA of the Last RA of each RA sub-sequence, because aggregation removes the information necessary to reconstruct that information from the AS PATH and NLRI in the new RA. 3.2.2. BGP Processing Phases The S-BGP Decision Process differs from the specifications of BGP-4 [RFCbgp], and route servers [RFC1863] in the following ways. 3.2.2.1. Phase 1 Processing The degree of preference for each route received from an external peer calculated during Phase 1 MAY take into consideration the results of the verification of received RAs, and/or the presence of AA information for each advertised prefix. The attestation path attribute MUST be passed to all internal peers that are sent an advertisement. Lynn, Mikkelson, Seo [Page 41] Secure BGP June 2003 3.2.2.2. Phase 2 Processing In general, the Phase 2 installation of the best route for each distinct prefix in the appropriate Loc-RIB is unchanged. However, an implementation that performs either asynchronous or on-demand verification of attestations (or their signatures) MAY modify this step to initiate and/or await the results of the attestation verification step. 3.2.2.3. Phase 3 Processing A new step is added to Phase 3. Before disseminating routes in the Loc-RIB to each external peer, the speaker SHOULD include a signed RA that contains the protected transitive information. As an aid to incremental deployment, a speaker MUST support a per-peer configuration capability to not send an Attestation Path Attribute to a peer; see, e.g., send-RA in C.2.3. Implementation Note: An implementation MAY cache the RAs so created to reduce time required to create and sign an RA for use with subsequent advertisements of the same route to the same peer; see, e.g., out-cache-depth, C.4.7. Protected data is made explicit in a prepended RA and whenever it either differs from the NLRI/MP_REACH_NLRI or protected transitive path attributes, or the data cannot be derived from explicit data in a previous RA. The AS PATH MUST be included in the CoverageMask filed. When prepending the created or cached RA to the (possibly empty) set of RAs in the received attestation attribute, any protected path attributes that are either identical or predictable to the value in the ExplicitPA part of the Last received RA SHOULD be made implicit (by removing it from the peer RA's ExplicitPAs field and adjusting the ExplicitPA part's Length field accordingly), thus reducing the size of the attestations; see, e.g., c.5.5,6. They MAY also be removed from all subsequent RAs, up to, but not including, the point where the values differ. The only predictable change in path attributes at the current time is for the AS PATH attribute, where a predictable change is defined to be the simple addition of the Last AS numbers to the last AS_SEQUENCE in the AS path. Use of S-BGP within Confederations [RFC1965], while straight forward since all members of a Confederation are presumed to be part of the same management domain, are outside the scope of this specification. Lynn, Mikkelson, Seo [Page 42] Secure BGP June 2003 3.2.3. S-BGP Processing The use of S-BGP and the attestation attribute affects processing and sending of UPDATEs as well as the routing policy and decision functions, including choice of routes to use and advertise. An example of additions to local policies appears in Appendix C. The processing specific to the attestation attribute and the changes necessary to the three BGP decision phases are described in sections 3.1.1 and 3.1.2; they are referred to in this section, which presents an overview of all changes necessary to support S-BGP. 3.2.3.1. Receive Processing After an UPDATE has been received by an S-BGP speaker, it must perform all of the usual BGP processing, with the addition of S-BGP processing in certain places. The first S-BGP change is in the addition of more syntax and consistency checking of an UPDATE message. The attestation attribute must be syntactically correct. The lengths of the attestations must add up to the length of the attestation path attribute. The lengths of the parts of each attestation must add up to the length of the attestation. There must be exactly as many remaining RAs in the RA sequence as claimed by the RASC field of the each RA, any RA sub- sequences from aggregation must have the correct number of RAs as specified in the RASC of the RA sub-sequence's Last RA, and the lengths of these RA sub-sequences must be equal to one less than the number in the RASC of the aggregator's RA. After syntax checking, the speaker must ensure that any necessary implicit data from the UPDATE is available. Validation need not occur at this stage (including steps to ensure that implicit and explicit data is the same), but the implicit data must be available at the time of validation. It is sufficient that the RAs are stored in such a way that the storage of the other path attributes from the same UPDATE is available at the time of validation. Note that RAs received from internal peers MAY be configured to not have their signatures verified as that happens when an advertisement is received from an external peer. Likewise, RA validation (section 3.2.1.1) may occur at another time. It is also not necessary to perform all steps of validation at once. After syntax checking and preservation of potentially implicit path attributes, the S-BGP speaker may return to the usual UPDATE processing. Or, it may do all validation except for signature verification, as the latter requires far more computation, at least when performed in software. Full validation could be undertaken here, especially if the signature verification can be moved to Lynn, Mikkelson, Seo [Page 43] Secure BGP June 2003 another processor (section 4), but this may be less efficient when a flood of UPDATEs is received. Because of the time it takes to verify a signature in software, it may be more efficient to delay signature validation when a received route is not selected as the best route to one of the prefixes, i.e., in cases where there is a already a more preferred route. The reduction in signature verification operations can be significant, especially when a speaker has a large number of external peers. However, when the S-BGP information becomes relevant for route selection, the RAs must be validated. This may be when the route is selected as the best route to some prefix; validation must then occur before the route may be used (placed into the Loc-RIB) or subsequently advertised (placed into an Adj-RIB-Out). RA validation can also be scheduled during idle time, so that if a route validated this way is later selected as the best route, the validation may already have been completed. See, e.g., verify-RA in C.4.1. Policy may choose to use a route because it is the only route available for a certain prefix; in this case the RAs would not need to be validated; see, e.g., only-route in C.5.1,2,3 and C.1. When another route arrives for that prefix, and local policy would use information carried in the RAs to selecting a route, both routes must then be validated. Or alternately, if the best route is chosen without using RA information, only validation of the best route would be necessary (unless validation fails, causing another route to be selected). Note that no S-BGP changes are necessary to validate route withdrawals. Since withdrawals cause the route to be removed from the Adj-RIB-In, either the S-BGP speaker has already removed the route because its validation failed (or the route was never advertised), so the withdrawal has no effect, or validation has succeeded, so the peer withdrawing the route has previously advertised the route, and the withdrawal is authorized. Caching of more than the most recently received route for a prefix can reduce processing computational overhead due to S-BGP, at the cost of more memory. The BGP specification requires retention of the most recent UPDATE per peer per prefix in the Adj-RIB-In. Additional caching, discussed in section 4, would occur at this point in processing. The next part of UPDATE processing affected by S-BGP is the decision function (see section 3.2.2). 3.2.3.2. Send Processing An important aspect of the decision function which needs special attention for S-BGP is aggregation. Local policy describing when Lynn, Mikkelson, Seo [Page 44] Secure BGP June 2003 aggregation should be performed must take into account the fact that the UPDATE message size can increase quite dramatically when S-BGP protected routes are aggregated, as the attestation attribute for the aggregated route must include all RAs from each contributing route, and the full AS PATH and NLRI/MP_REACH_NLRI must be present in the ExplicitPA part of the Last RA for each received RA sequence. A configuration parameter for the maximum aggregated attestation attribute size must be introduced and taken into consideration when applying aggregation policies. Otherwise, an aggregation may force the UPDATE size past the maximum of 4096 octets. Three situations may arise after a route has been selected use and is to be advertised. The route may be advertised to a peer in the same AS. The route may have been received from an external peer, and an RA must be created and signed by the speaker. Or the speaker's AS may be originating a route. The first situation does not require the creation of an RA, since an RA is not prepended to the RA sequence when a route is forwarded to peers in the same AS (confederations are different ASes). The second situation imposes some requirements on the code which produces an UPDATE message to advertise an UPDATE. As the path attributes are being placed into the UPDATE, the attestation attribute must be created. This requires building a new RA sequence if aggregation has occurred. A new RA is then prepending to the RA sequence. In order to create the new RA, all other path attributes and the NLRI must be available, as well as the AS number of the peer(s) to which the UPDATE will be sent. If the speaker performed aggregation to create the route, the RA sequences from all routes which were aggregated must be available. The AS PATH attribute and the NLRI/MP_REACH_NLRI attribute must be present in the form which they will take in the UPDATE message. If the route is to be forwarded to more than one AS, it is more efficient though not required, to have the full list of ASes available as well. Then the new RA can be created, as described in section 3.2.1.2. Note that a BGP implementation may require some change to the method of building UPDATE messages to allow all protectable path attributes and the NLRI to be available while creating the attestation attribute; support for the Multiprotocol Reachable path attribute requires similar changes. The creation of an RA requires a signature to be computed. If the signature is computed asynchronously (e.g., another processor is devoted to cryptographic operations), the UPDATE message may not be available to be sent immediately after the path attributes and NLRI are written to the message. Thus it may be necessary for some BGP implementations to be changed to allow for queueing of completely formated UPDATE messages until after the signature has been computed and inserted into the Last RA. After the signature is computed, a speaker may wish to cache this new Lynn, Mikkelson, Seo [Page 45] Secure BGP June 2003 RA, so that if it needs to be advertised again, the signature does not need to be recomputed. Caching is discussed in section 4. Note that it is important that if two UPDATE messages are to be sent to the same peer, and the first requires a signature computation but the second is found in the send cache (so no signature is needed) or only withdraws routes, the second UPDATE message MUST be queued until the first has been sent so that the order of UPDATE messages is preserved. The third situation for advertising a route occurs when an S-BGP speaker originates a route. Care must be taken that the NLRI is not allowed to grow too large. A configuration parameter is necessary to limit the size of the NLRI such that enough space is left in the 4096-octet BGP message to allow inclusion of the longest expected RA sequence for that route; see, e.g., max-origin in C.4.3. This configuration should account for the radius of the Internet in ASes from the point of view of the originating AS. It may be necessary to send multiple UPDATE messages with smaller NLRI where one would have been sufficient were S-BGP not being used. The NLRI must be restricted in size at the originating speaker because an UPDATE message cannot be split to reduce the UPDATE message size when it is protected by an RA. Splitting the NLRI actually increases the UPDATE size as the old, large NLRI must be made explicit in the Last received RA, when it could have been implicit if the NLRI had not been changed. Once the NLRI for a given UPDATE message has been determined, the UPDATE can be built as usual for an S-BGP speaker. The only difference at this point from the second situation above is that the attestation attribute is new. The creation of the RA requires the same information as is needed for the second situation above. Similarly, the signature computation may be delayed, and a send cache of RAs for originated routes may be created. 3.2.3.3. Background Processing Some processing of local S-BGP information may occur as a background process. Since RAs, public keys, and AA information eventually expire, attention must be paid to keep routing information current. The NOC may upload new public keys, AA information, or policy to an S-BGP speaker. Locally stored public keys and AA information that have expired should be removed. Any routes that were validated using expired information are no longer valid; they should be either re-validated, as newer public keys or AA information becomes available, or the Phase 2 decision process should be run to select alternate routes. This might result in sending withdrawals and advertising a new, validated route. Local policy may allow expired routes to remain, e.g., in general, in cases where no other route is available, or when Lynn, Mikkelson, Seo [Page 46] Secure BGP June 2003 all other routes have failed validation. RAs which have expired must also be handled. This includes removing routes which were validated by the expired RAs, as they are no longer valid, and finding a new best route. Expired RAs must also be removed from any RA caches (section 4). Both RAs received in UPDATEs and RAs created and signed by the speaker may be cached. RAs created by the speaker could either be removed from the send cache, so that they are re-computed when the route is next advertised, or they may be left and simply re-signed (after updating the Expiry part) if the public key for the speaker is still valid. In either case, if the expired RA was created for a route originated by the speaker, the route must be advertised again, with a new RA. If a soon to expired RA was prepended to an RA sequence by a speaker and the route is still in the Loc-RIB and none of the received RAs have expired, that route should be re-advertised with a newly signed RA. Efficiency would suggest that a re-advertisement be delayed if one of the other RAs will expire before the locally generated RAs. Depending on the implementation of S-BGP, especially of the receive and send RA caches if they are used, there may be a need for other periodic clean up. For example, a receive RA cache for a given peer might not be deleted immediately when the session is terminated, so that if the session is re-established the RAs received would not need to be re-verified; see, e.g., [BGPRES]. However, if the session is not re-established within a reasonable interval, the cached routes might be removed. Depending on the implementation, this may require a periodic processing of the cache. Finally, idle time may be used to verify RAs in the, e.g., second best routes, which have not yet been verified. Since it might be advertised in the future, if RAs are verified during idle time, the verification computation might be completed before selection as the best route. (Delayed verification of RAs is discussed in section 3.2.3.1.) 3.2.3.4. Unknown Path Attributes and Canonicalization An S-BGP speaker can handle unknown protected path attributes provided that they do not need canonicalization during the verification of an RA. During verification, an implicit path attribute which does not need to be canonicalized may be byte- compared against the explicit path attribute found in the RA's ExplicitPA part (section 3.2.1.1). Thus validation can succeed despite the fact that the path attribute is unknown. When an RA protecting an unknown path attribute is forwarded as part of an advertised route, the unknown path attribute must be placed in the Last RA's explicit data as well as in the new RA's explicit data, since the speaker for which the path attribute is unknown sets the Partial bit in the Path Attribute Flags. This causes the path Lynn, Mikkelson, Seo [Page 47] Secure BGP June 2003 attribute to change, requiring it to be placed in the explicit data of the Last RA of the received RA sequence, as usual (section 3.2.1.2). If local policy stipulates removal of the unknown path attribute, it will still be placed in the explicit data of the Last RA, and the corresponding bit will not be set to 1 in the new RA's CoverageMask field. Currently only the AS PATH and NLRI/MP_REACH_NLRI path attributes need be canonicalized for verification (section 3.2.1.1). However, if an unknown path attribute is defined in the future such that the implicit form of the path attribute from the UPDATE must be canonicalized before it may be compared against the path attribute in the explicit data of the Last RA, S-BGP cannot properly validate the unknown path attribute. The signature verification may be carried out properly, but the implicit and explicit forms of the path attribute will not match. Also, any RAs subsequent to the Last RA which carry the unknown path attribute in an implicit form cannot be validated. It is not sufficient to simply allow validation to fail. Policy may allow subsequent RAs to be considered validated by the Last RA. Since the S-BGP speaker does not know how to handle the unknown path attribute, the fact that the implicit and explicit data do or do not match does not indicate whether the data is valid. If the implicit and explicit data do not match, it cannot be determined that this is because canonicalization is necessary or because the implicit data has been changed. If they do match, it cannot be determined that canonicalization would have produced non-matching data, such that validation should fail. It may be safe to assume that if the implicit and explicit data do match and the signature verification succeeds that validation has succeeded, but only if it can be determined when a path attribute requires canonicalization. A method for dealing with the issue of future path attributes which should be protected by S-BGP and which also need canonicalization has not been determined. Two simple possibilities include disallowing new attributes from having canonicalization rules, which could cause every RA in a sequence to store this path attribute in the ExplicitPA, or disallowing S-BGP protection of new path attributes which need canonicalization until all S-BGP speakers can handle the new path attribute. This issue needs further study. Specifications for new path attributes SHOULD specify whether or not they require canonicalization, and if so how the canonicalization is performed. 3.2.4. Interoperation with Non-S-BGP Speakers The design of S-BGP allows gradual deployment of S-BGP capability throughout an internet. The expected deployment scenario is for initial deployment by large, well interconnected, ASes. They have Lynn, Mikkelson, Seo [Page 48] Secure BGP June 2003 more customers that would benefit from S-BGP assurances. Over time more ASes would support S-BGP. Another scenario is for a group of users to decide to deploy S-BGP to protect their routing infrastructure. As S-BGP is incrementally deployed it would be possible for an UPDATE message to traverse both ASes that do and ASes that do not recognize and/or process the attestation path attribute. While rules and algorithms can be specified that permit some security benefits to be realized when an S-BGP protected UPDATE traverses non-S-BGP ASes, those algorithms, and their related policy controls, are sufficiently complex relative to the additional security realized that this specification does NOT RECOMMENDED that they be implemented. In the expected deployment scenario, having S-BGP protected UPDATEs pass between ASes that are using S-BGP ONLY via an AS(es) not using S-BGP would be the exception, rather than the common case. Thus there would be little to be gained from the added complexity. In addition, this specification RECOMMENDs that an AS that supports S-BGP processing only add RAs for the prefixes that the AS originates, or which were received from a peer that prepended an RA to the attestation path attribute. This has two advantages. First, the volume of routes that carry the attestation path attribute would be significantly less that the total number of routes in the Internet; this translates to significantly reduced memory requirements. Reduced memory requirements may enable more ISPs to use S-BGP without having to add more memory to their S-BGP speakers. Second, if a route is protected by S-BGP, then one has assurances that the route is authorized all the way to destination network. Since the binding between origin AS and network prefix by address attestations is both authoritative and completely out-of-band, a speaker that has S-BGP capability can perform origin verification without having to perform any attestation path attribute processing. 4. Processing Optimizations There are several processing options that can be used to improve the efficiency of an S-BGP implementation. Some choices, such as the addition of cryptographic hardware or the use of RA caches, might depend on the placement of the router, e.g., is it used at a NAP or at a customer site. Use of Implicit Data Protected data should be implicit in all prepended RAs unless it either differs from the NLRI/MP_REACH_NLRI or protected transitive path attributes, or the data cannot be derived from explicit data in a previous RA. When the data in an RA that is being prepended Lynn, Mikkelson, Seo [Page 49] Secure BGP June 2003 to an attestation is the same as the data in the Last RA that was received from a peer AS, it SHOULD be made implicit (by removing it from the Last received RA), thus reducing the size of the attestations. Cryptographic Operations on Another Processor The time required to perform cryptographic operations is quite substantial compared to the time required to do other processing of UPDATE messages. As such, a performance improvement *might* be realized by moving the signing and verifying operations to another processor instead of doing them in software. This could be specialized hardware attached to the router, via either an external interface or a PCMCIA card, or it could be a general- purpose computer, such as a PC on a router blade, to which the router may pass crypto requests. Adding any such processing will cause the cryptographic operations to be performed asynchronously, so special attention must be paid to handling and synchronization issues. Note that performing the SHA-1 hash in hardware might not be faster than doing the hashing in software, as marshalling and passing the data to be hashed to a crypto processor takes both additional space, time, and scheduling overhead. It has been observed that the advertised performance of some vendor's cryptographic accelerators may not be achievable due to the large number of public keys (10s of thousands when S-BGP is fully deployed) that are needed to verify the RA signatures. The performance loss was due to the limited memory available for public keys combined with the need for sequential transactions to unload a public key (to make room for another), load the needed key and obtain the key id assigned by the accelerator, and to then pass that key id, the hash, and signature data to the accelerator for verification. A "key agile" accelerator design that is capable of accepting the public key, hash, and signature data in a single transaction could avoid this problem. Use of a hardware cryptographic processor that protects the private key(s) used to sign the hashed information provides better security than techniques that hold the private key(s) in router memory. An external processor may also allow parallel execution of signing/verifying; since multiple RAs may be signed (for advertising to multiple peers) or verified (multiple RAs are received in an attestation attribute), this may produce a noticeable performance improvement. Performing signature verification in software and signature generation on a token might be advantageous (especially if the token is not public key agile). Lynn, Mikkelson, Seo [Page 50] Secure BGP June 2003 RA Caching Retention of a peer's Adj-RIB-In after a peering session has been terminated can speed the reestablishment of a subsequent peering session. BGPs that implement [BGPRES] will automatically gain this benefit. Another possible optimization involves caching RAs, both those received from other peers, and those created by the speaker and sent to other peers. Caching helps reduce the number of verifications and signatures necessary to handle route flaps. If a route is flapping and the received RAs for both have been verified once, a cache will allow the already-verified RAs to be used to validate the route each time it flaps, reducing processing overhead. Likewise, a flapping route being advertised by the peer requires sending multiple locally-generated RAs; in this case a cache of sent RAs can reduce the number of signatures to be computed. 5. Auditing and Event Reporting Security relevant events SHOULD be recorded and/or reported to a management station. There SHOULD be a way to limit the rate at which events are reported to a NOC. It is RECOMMENDED that rate limiting be applied on a per- speaker basis. Per-event limits MAY be implemented. The audit information should include: the identity of the signer, if it can be determined; the identity of the authorizing AS, if it can be determined; the peer from which the message was received; and the type of error or problem detected. For a missing key, the key owner and key identifier should be reported. For a missing AA, the prefix and originating AS should be reported. 6. Infrastructure Support Operation and deployment of S-BGP requires supporting infrastructure. S-BGP uses X.509 v3 certificates consistent with the PKIX specification [RFC3280] that include private extensions for the delegation of IP address blocks and AS numbers as well as the binding of a BGP Identifier to an AS. The extensions are defined in [X509EXT] and [X509S-BGP]. The Regional Internet Registries need the capability to securely obtain an organization's public key and a Certification Authority (CA) capability to generate subordinate CA certificates containing the extensions that are used to delegate the Lynn, Mikkelson, Seo [Page 51] Secure BGP June 2003 right to use IP address prefixes and AS numbers, and to make the signed certificates available to the organizations to whom the resources have been delegated. ISPs need CA capability to create end entity certificates with the appropriate extensions for their ASes, networks, S-BGP speakers, and operations personnel. They may also need the capability to issue subordinate CA certificates if they further delegate the right to use some of their address space to their multi-homed BGP customers (as opposed to loaning portions of their address space). The S-BGP architecture calls for the storage and distribution of all S-BGP related certificates, CRLs, and AAs in a distributed global repository with servers replicated at well-connected points throughout the Internet. Initial mechanisms for the communication of certificates, CRLs, and AAs to one of these repositories by certificate owners, CRL signers, and AA issuers have been developed, as has software for the repositories and for use by NOCs to manage their S-BGP assets. The management of an AS is responsible for posting their locally generated certificates, CRLs, and AAs to the repository and for periodically downloading the information in the repository for local processing and distribution to their S-BGP speakers. The HTTPS protocol is used for update (POST) and retrieval (GET) transactions with the repositories. The AS's management is responsible for certificate verification. The format of certificate extracts and the mechanisms for their communication to the S-BGP speakers within as AS are vendor specific. The extracted information should contain a representation of the following fields: Subject name, Subject Public Key Info (the DSA public key), Subject Key Identifier, the IP Address Block Certificate Extension, the Autonomous System Identifier Certificate Extension, and the Router Authorization Certificate Extension. 7. Address Attestations The owners of IP address blocks, i.e., those organizations which have been issued a certificate containing an IP Address Block Certificate Extension, need to generate and sign an AA that authorizes one or more ASes to advertise those address blocks. The resulting AAs MUST be sent to one of the top-level repositories as described in the previous section. Lynn, Mikkelson, Seo [Page 52] Secure BGP June 2003 8. IANA Considerations IANA should assign BGP Type Code *IANA-TBD* to the attestation path attribute ("ATTEST"). Replace *IANA-TBD* with the number in section 3. IANA assigned the eight bit value 2 to the DSAwithSAH1 on 31 Oct 2000 and listed it in the Signature Algorithm Number table at http://www.isi.edu/in-notes/iana/assignments/sig-alg-numbers. That URL is no available on the IANA web page. Reference [IANA-SAN] should be updated with the correct URL. IANA should create a name space for the Attestation Part Codes, e.g., attest-numbers. Values defined in this specification are: 0 Reserved 8 Route Attestation 1 Signer Part 9 Address Attestation 2 Signature Part 10 CRLs 3 Expiry Part 11 Certificates 4 ExplicitPA Part 12 5 Target Part 13 6 14 Extract file authenticator 7 15 Reserved for escape mechanism Unassigned attestation Part Codes may be assign by IANA when presented with working group consensus. 9. Security Considerations Security is central to the design of this protocol, and these security considerations permeate this specification. Security considerations related to public key technology are given in [RFC3280]. 10. Acknowledgments Many individuals contributed to the design and development of S-BGP. As members of the architecture team, Stephen Kent, Martha Steenstrup, and Luis Sanchez provided critical input to the design of the attestation and PKI schemes, evaluation of other approaches, and analysis of performance and operational issues. Sean Kennedy and John Hawkinson provided invaluable insight into real world Internet engineering and operational issues. The authors would also like to thank Michelle Casagni for her help with the analysis and Dennis Rockwell and Nicholas Shectman for their help with the proof of concept implementation. Additional thanks to Rick Altmann, Kavita Baball, Ed Bubnis, Sue-fen Cuti, Shelby Evans, Mark Fausett, Pete Fischer, Pete Foley, Charlie Gardiner, Christine Jones, Joe Kraska, Lynn, Mikkelson, Seo [Page 53] Secure BGP June 2003 Bob Masters, JB Mitchell, Tony Stein, and Carmela Stuart for their work developing the supporting repository, NOC, and certification authority software that will be needed to support S-BGP operationally. This work was made possible by support from NSA and DARPA. 11. References The following references are normative. [DSS] Federal Information Processing Standards Publication (FIPS PUB) 186-1, "Digital Signature Standard (DSS)", U.S. Department of Commerce / National Institute of Standards and Technology, December 1998. [IANA-AFI] http://www.iana.org/assignments/address-family-numbers. [IANA-SAFI]http://www.iana.org/assignments/safi-namespace. [IANA-SAN] http://www.iana.org/assignments/sig-alg-numbers. [RFC2026] Bradner, S., "The Internet Standards Process -- Revision 3", RFC 2026, BCP 00009, October 1996. [RFC2119] Bradner, S., "Key words for use in RFCs to Indicate Requirement Level", BCP 14, RFC 2119, March 1997. [RFCbgp] Rekhter, Y., Li, T., Hares, S., "A Border Gateway Protocol 4 (BGP-4)", draft-ietf-idr-bgp4-20.txt [SHA-1] Federal Information Processing Standards Publication (FIPS PUB) 180-1, "Secure Hash Standard", U.S. Department of Commerce / National Institute of Standards and Technology, April 1995. or D. Eastlake 3rd, P. Jones, "US Secure Hash Algorithm 1 (SHA1), RFC 3174, September 2001. [X509EXT] Lynn, C., Kent, S., Seo, K., "X.509 Extensions for IP Addresses and AS Identifiers", draft-ietf-pkix-x509-IPaddr-AS-extn-01.txt, June 2003. [X509S-BGP]Lynn, C., "S-BGP Authorization PKI -- X.509 Extensions and Profile", draft-clynn-bgp-x509-auth-02.txt, February 2002. The following references are informative. [AS4Bytes] Vohra, Q., Chen, E., "BGP support for four-octet AS number space", draft-ietf-idr-as4bytes-05.txt, May 2002. Lynn, Mikkelson, Seo [Page 54] Secure BGP June 2003 [BGPRES] Sangli, S. R., Rekhter, Y., Fernando, R., Scudder, J. G., Chen, E., "Graceful Restart Mechanism for BGP", draft-ietf-idr-restart-06.txt, January 2003. [CMS03] Kent, S., "Securing the Border Gateway Protocol: A Status Update", Seventh IFIP TC-6 TC-11 Conference on Communications and Multimedia Security, October 2-3, 2003, Turin, Italy [DISCEX] Lynn, C., Seo, K., "Design and Analysis of the Secure Border Gateway Protocol (S-BGP)", IEEE DISCEX Conference, January, 2000. [DPA] Chen, E., Bates, T., "Destination Preference Attribute for BGP", draft-ietf-idr-bgp-dpa-04.txt, January 1996 [EXT-COMM] Sangli, S., Tappan, D., Rekhter, Y., "BGP Extended Communities Attribute", draft-ietf-idr-bgp-ext-communities-05.txt, May 2002. [JSAC] Kent, S., Lynn, C., Seo, K., "Secure Border Gateway Protocol (S-BGP)", IEEE JSAC Issue on Network Security, April 2000. [MRT] http://www.merit.edu/~mrt, http://www.merit.edu/mrt/mrt_doc [Murphy] Murphy, S., "BGP Security Vulnerabilities Analysis", draft-murphy-bgp-vuln-00.txt, February 2002. [Murphy2] Murphy, S., "BGP Security Protections", draft-murphy-bgp-protect-00.txt, February 2002. [NDSS00] Kent, S., Lynn, C., Mikkelson, J., Seo, K., "Secure Border Gateway Protocol (S-BGP) -- Real World Performance and Deployment Issues", Proceedings of the Network and Distributed System Security Symposium, San Diego California, February 2000. [RFC1863] Haskin, D., "A BGP/IDRP Route Server alternative to a full mesh routing", RFC 1863, October 1995. [RFC1965] Traina, P., "Autonomous System Confederations for BGP", RFC 1965, June 1996 [RFC1997] Chandra, R., Li, T., Traina, P., "BGP Communities Attribute", RFC 1997, August 1996 [RFC2050] Hubbard, K., Kosters, M., Conrad, D., Karrenberg, D., Postel, J., "Internet Registry IP Allocation Guidelines", RFC 2050, BCP 00012, November 1996. Lynn, Mikkelson, Seo [Page 55] Secure BGP June 2003 [RFC2401] Kent, S., Atkinson, R., "Security Architecture for the Internet Protocol", RFC 2401, November 1998. [RFC2406] Kent, S., Atkinson, R., "IP Encapsulating Security Payload (ESP)", RFC 2406, November 1998. [RFC2407] Piper, D., "The Internet IP Security Domain of Interpretation for ISAKMP", RFC 2407, November 1998. [RFC2408] Maughan, D., Schertler, M., Schneider, M., Turner, J., "Internet Security Association and Key Management Protocol (ISAKMP)", RFC 2408, November 1998. [RFC2409] Harkins, D., Carrel, D., "The Internet Key Exchange (IKE)", RFC 2409, November 1998. [RFC2410] Glenn, R., Kent, S., "The NULL Encryption Algorithm and Its Use With IPsec", RFC 2410, November 1998. [RFC2796] Bates, T., Chandra, R., Chen, E., "BGP Route Reflection - An Alternative to Full Mesh IBGP", RFC 2796, April 2000. [RFC2828] Shirey, R., "Internet Security Glossary", RFC 2828, May 2000. [RFC2858] Bates, T., Rekhter, Y., Chandra, R., Katz, D., "Multiprotocol Extensions for BGP-4", RFC 2858, June 2000. also draft-ietf-idr-rfc2858bis-02.txt, April 2002. [RFC3107] Rekhter, Y., Rosen, E., "Carrying Label Information in BGP-4", RFC 3107, May 2001. [RFC3279] Polk, W., Housley, R., Bassham, L., "Algorithms and Identifiers for the Internet X.509 Public Key Infrastructure Certificate and Certificate Revocation List (CRL) Profile", RFC 3279, April 2002. [RFC3280] Housley, R., Polk, W., Ford, W., Solo, D., "Internet X.509 Public Key Infrastructure Certificate and Certificate Revocation List (CRL) Profile", RFC 3280, April 2002. [RVO] www.routeviews.org, /bgpdata and /route-views6/bgpdata. [SALTZER] Saltzer, J. and Schroder, M., "The Protection of Information in Computer Systems", IEEE Proceedings, 63(9), March 1975. [S-BGP] http://www.ir.bbn.com/projects/s-bgp Lynn, Mikkelson, Seo [Page 56] Secure BGP June 2003 Appendix A. Example Certificates, Hashes, and Signatures This informational appendix will be provided in a subsequent version of this document when all the TDB values have been assigned. PKI Examples Root CA Certificate text PEM Grandfather CA Certificate text PEM ISP CA Certificate ISP AS End-entity Certificate ISP Network End-entity Certificate Network Address Attestation text hex Router S-BGP End-entity Certificate ISP NOC Operator End-entity Certificate Repository CA Certificate Repository End-entity Certificate (db and SSL?) S-BGP UPDATE Message text hex Lynn, Mikkelson, Seo [Page 57] Secure BGP June 2003 Appendix B. Configuration S-BGP requires additional configuration information. This informational appendix describes configuration items that an S-BGP implementation might implement. Where to find and how to activate and use the RA signing private key. Where to find the NOC's public key. The name of the file(s) containing AA extracts, public key extracts, and S-BGP policy. Per NOC, how to negotiate an IPsec transport-mode ESP security association for upload to speakers, if required. Per peer, how to negotiate an IPsec transport-mode ESP security association. Lynn, Mikkelson, Seo [Page 58] Secure BGP June 2003 Appendix C. Policy Support This informational Appendix describes policies that an S-BGP implementation might implement. Secure BGP policy enables the incremental deployment of S-BGP, easier introduction of new S-BGP capable ASes and speakers, and the ability to work around misconfiguration in other ASes. For these reasons S-BGP policy is applied in a hierarchical manner such that policy may be specialized for particular ASes, speakers, or prefixes as appropriate by an S-BGP capable speaker. The policy levels are: * Global Policy set at the global level applies to all UPDATEs regardless of the prefixes being advertised, or the ASes or speakers from which they were originated or through which or to which they were advertised. Global policy must be set, and is the default when no more specific policy overrides it. * Autonomous System (AS) AS policy may be used when needed to override global policy, and is applied based on the AS from which an UPDATE was originated or through which or to which an UPDATE is advertised. * Speaker Speaker policy may be used when needed to override both global and AS policy, and is applied based on the individual speaker from which an UPDATE or RA was originated or to which an UPDATE is advertised. * Prefix Prefix policy may be used when needed to override global, AS, and speaker policy, and is applied based on a specific prefix. All policy is available at the global level; some policy is available for specialization to the AS, speaker, and/or prefix level. More specific policy always takes precedence. C.1. Policy Control Classes Consistent routing necessitates that BGP speakers apply the same algorithm on the same routing information. Therefore, some S-BGP functionality may need to be: * activated or deactivated based on speaker and AS capabilities, * configured for specific topologies and peering relationships, * tuned and optimized for performance and interoperability, Lynn, Mikkelson, Seo [Page 59] Secure BGP June 2003 * incrementally deployed to allow for interoperability of S-BGP capable and non-capable speakers, * extensible for the protection of new features added to BGP, and * workable around misconfigurations. These functional requirements are listed in order of significance and represent the control classes into which S-BGP policy is categorized. This section defines and categorizes the available S-BGP policy settings. Some policies provide an "only-route" setting. This setting implies that a received route may be selected even if some portion of the S-BGP verification process fails. If no other route successfully verifies for a given prefix, then a non-verified route for which the "only-route" policy applies may be selected; otherwise, no route would exist for the given prefix. This policy setting is more forgiving than outright route rejection, especially in the case of system misconfiguration, but does introduce a security risk. However, an attacker would not only have to send an invalid route update such that it passes an "only-route" policy, but also prevent all other valid routes from being received by a speaker. Several policy settings are represented as a set of BGP path attribute identifiers. Only transitive path attributes (i.e., path attributes available for S-BGP protection) may be specified in these policies. Currently defined transitive path attributes include the following. NLRI or MP_REACH_NLRI Type Code 0, only within S-BGP route attestations ORIGIN Type Code 1 AS PATH Type Code 2 ATOMIC AGGREGATE Type Code 6 AGGREGATOR Type Code 7 COMMUNITY Type Code 8 DPA Type Code 11 EXTENDED COMMUNITY Type Code 16 Additional transitive path attributes may be protected as they are defined within the BGP protocol. The NOC provides each S-BGP speaker a policy configuration file in addition to the AA and certificate extract files. The integrity of and the authorization to use the S-BGP policy is assured by the signing of the file by the NOC with, e.g., the NOC's or AS's private key. Lynn, Mikkelson, Seo [Page 60] Secure BGP June 2003 C.2. Activation General S-BGP functionality is activated or deactivated based on the following policy. C.2.1 enable-AA The "enable-AA" policy directs an S-BGP speaker to perform, or not perform, AA verification of the NLRI within received UPDATEs. This policy is applied only at the global level, and available settings include: yes AA verification of NLRI received in UPDATEs is performed. no AA verification of NLRI received in UPDATEs is not performed. The default setting is "yes"; under normal operation an S-BGP speaker should always perform NLRI origination verification using AA information. However, an S-BGP speaker newly introduced into the network may not have received AA extracts required to perform AA verification, in which case the policy may be set to "no". If this policy is set to "no", then all other policy pertaining to AA verification is not activated. C.2.2 enable-RA The "enable-RA" policy directs an S-BGP speaker to process, or not process, RAs within received UPDATEs. This policy is applied only at the global level, and available settings include: yes Processing of RAs received in UPDATEs is performed. no Processing of RAs received in UPDATEs is not performed. The default setting is "yes"; under normal operation S-BGP should always process received RAs. However, an S-BGP speaker may lack public keys required to perform RA verification of UPDATEs, or an S-BGP speaker may not peer with any other S-BGP capable speaker. In such cases the policy is best set to "no". If this policy is set to "no", then all other policy pertaining to inbound route attestations is not activated. Lynn, Mikkelson, Seo [Page 61] Secure BGP June 2003 C.2.3 send-attest The "send-attest" policy directs an S-BGP speaker to include, or not include, an attestation path attribute in outbound advertisements. This policy is applied at the global and peer (speaker) levels, and available settings include: yes An attestation path attribute is included within outbound advertisements for locally originated routes and for transit advertisements that contained an attestation path attribute. no No attestation path attribute is included in outbound advertisements, and any attestation path attribute is removed before sending a transit advertisement. The default setting is "yes"; under normal operation an S-BGP speaker should always prepend a locally generated RA within the attestation path attribute of all transit or locally originated outbound advertisements. The "no" policy setting is used when a speaker peers with a non S-BGP capable speaker. In this case, no attestation path attribute is included within the outbound advertisements. If this policy is set to "no", then all other policy pertaining to outbound advertisements is not activated. C.3. Configuration The following policy is used in configuring an S-BGP speaker for a particular topology and set of peering relationships. C.3.1 sign-AS The "sign-AS" policy allows multiple targets (peer ASes) to be identified in an RA when a single UPDATE is to be sent to multiple external peers. The target of an RA is the set of ASes being authorized to use and advertise the route associated with the RA. The default target is the AS of the speaker to which the route is being sent. In the case of external route reflectors, however, multiple targets will need to be specified because the advertised route is further propagated to the other speakers in communication with the route reflector. This policy is applied only at the peer (speaker) level and consists of a list of unique AS numbers. Note that internal route reflectors are often used for iBGP; the "sign-AS" policy does not apply in such a case because RAs are not generated and included within UPDATEs sent to internal peers. However, external route reflectors may be used at network access points (NAPs), for example, to forward received UPDATEs to multiple external speakers. Lynn, Mikkelson, Seo [Page 62] Secure BGP June 2003 C.3.2 peer-auth The "peer-auth" policy specifies which entity, if any, is responsible for performing peer authentication through the use of IPsec. This policy is applied at the global and peer levels, and available settings include: bgp The BGP speaker is responsible for performing peer authentication. system The system on which the BGP speaker resides is responsible for performing peer authentication. no No peer authentication is performed. The default policy setting is "system". Speakers on either side of a peering relationship must have consistent settings for this policy. C.3.3 peer-key The "peer-key" policy specifies the key to use for purposes of peer authentication. C.3.4 upload-port The "upload-port" policy specifies the port number and protocol over which information such as the extract and policy files is uploaded from the NOC. C.4. Tuning and Optimization Policy for tuning and optimizing the performance of a S-BGP speaker is defined as follows. C.4.1 verify-RA The "verify-RA" policy determines the time at which the RAs within a received S-BGP UPDATE undergo signature verification. This policy is applied only at the global level, and the available settings include: receipt RAs are verified prior to the route's inclusion within the Adj-RIB-In. selection RAs are verified prior to the route's inclusion within the Loc-RIB. background RAs are queued for verification at the time of the route's inclusion within the Adj-RIB-In; RAs must be verified prior to the route's inclusion within the Loc-RIB. Lynn, Mikkelson, Seo [Page 63] Secure BGP June 2003 The "receipt" setting results in the verification of all received UPDATEs. Any invalid route is detected and reported upon receiving the route, regardless of Phase 2 route selection. The early detection of invalid routes requires resources be allocated to cryptographic verification of routes that may never be selected. Greater resource efficiency is achieved by setting the policy to "selection", which is the default setting. The "background" setting combines the earlier detection of invalid routes with greater resource efficiency. C.4.2 multi-route The "multi-route" policy applies only in the case of UPDATEs that have undergone route aggregation. A given prefix may be included in multiple paths of the aggregated route. This policy directs an S-BGP speaker performing AA verification of aggregated routes for a common prefix. This policy is applied at the global and prefix levels, and available settings include: all All paths to a common prefix within a received UPDATE must be valid. one At least one path to a common prefix within a received UPDATE must be valid. The default setting is "all"; ensuring that all aggregated routes to a common prefix are valid provides greater security. The "one" setting is a more permissive alternative. C.4.3 max-origin The "max-origin" policy specifies the maximum sized NLRI to be included within originated UPDATE. This policy is applied at the global and speaker levels, and is used only in the origination, not propagation, of routes. A maximum NLRI size is used to leave sufficient space within an UPDATE for the attestation path attribute, which grows in size during propagation. The "max-origin" policy specifies the percentage of the space in an originated UPDATE less the NLRI that may be used for NLRI. Determination of the value of this policy includes factors such as expected aggregation or UPDATE NLRI splitting and the diameter of the Internet, in ASes. The default setting for this policy is 75 percent, i.e., three quarters of the remaining space in an UPDATE without NLRI may be used for NLRI. Lynn, Mikkelson, Seo [Page 64] Secure BGP June 2003 C.4.4 prefix-class The "prefix-class" policy is used to tag specific prefixes. Prefixes within different classes are not aggregated in a single UPDATE. This policy is applied only at the prefix level and is used only in the origination, not propagation, of routes. By default, all prefixes are assigned to the same class. This policy is significant in when an AS has multi-homed customers. A multi-homed customer authorizes multiple ASes to advertise routes for its prefix(es). At some AS, the route advertised by one originating AS for a prefix from a multi-homed customer will not be the best route (the route from one of the other originating ASes will be better) and, therefore, it will not be propagated further. The UPDATE that advertised the route may still be advertised for the other prefixes contained within the UPDATE'S NLRI; the multi-homed prefix is removed prior to the further propagation of the UPDATE. Modification of the NLRI requires that all the NLRI be included as explicit data within the Last received RA, which increases the size of the UPDATE. To prevent this situation, multi-homed prefixes may be assigned to a different prefix class and originated in separate UPDATEs. C.4.5 aggregate-any The "aggregate-any" policy indicates whether a S-BGP speaker may aggregate a verified and non-verified routes into a single UPDATE. This policy is applied only at the global level, and available settings include: yes Aggregation of verified and non-verified routes is allowed. no Aggregation of verified and non-verified routes is not allowed. The default setting is "no"; under normal operation a S-BGP speaker should not aggregate verified routes with non-verified routes. A more permissive alternative is provided by the "yes" setting. Use of this policy requires further study. C.4.6 in-cache-depth The "in-cache-depth" policy specifies the number of received attestation path attributes to cache for a prefix. The cache may be used to reduce the computational resources required for cryptographic verification of received UPDATEs at the expense of requiring more memory. An inbound attestation cache may be maintained for each neighboring speaker. Note that the BGP specification requires that the most recently received route for each prefix from each peer be Lynn, Mikkelson, Seo [Page 65] Secure BGP June 2003 retained in the peer's Adj-RIB-In; this policy specifies how many additional routes should be cached. C.4.7 out-cache-depth The "out-cache-depth" policy specifies the number of outbound attestation path attributes to cache. The cache may be used to reduce the computational resources required for signature generation for outbound UPDATEs at the expense of requiring more memory. An outbound attestation cache may be maintained for each neighboring speaker; this policy specifies how many routes should be cached. C.5. Incremental Deployment The following policy allows for the incremental deployment of S-BGP, during which time not all BGP speakers will implement the S-BGP security countermeasures. C.5.1 require-AA The "require-AA" policy specifies the prefixes for which AAs are required, or not required, from the ASes originating routes to those prefixes. This policy is applied at the global (i.e., all prefixes), AS (i.e., prefixes originated by a particular AS), or prefix level. Available policy settings include: yes AA required for originating AS of prefix within NLRI of received route. no No AA required for originating AS of prefix within NLRI of received route. only-route If no AA exists for originating AS of a prefix in the NLRI of a received UPDATE, use the route only if no other verified route exists. The default setting is "yes"; under normal operations S-BGP should perform AA verification of all prefixes in advertised in received UPDATEs. However, during incremental deployment many prefix owners will not have issued AAs for their prefixes. To allow routes to these prefixes to be used, the "only-route" setting is used. The "no" setting will not accept routes to prefixes that do not have an AA; it may be used in, e.g., closed user groups that do not want routes to unprotected destinations. C.5.2 require-RA The "require-RA" policy specifies requirements for RA presence in received UPDATEs, and is applied at the global (i.e., all route Lynn, Mikkelson, Seo [Page 66] Secure BGP June 2003 UPDATEs), AS (i.e., UPDATEs received from or transiting a particular AS), and speaker (i.e., UPDATE received from a particular speaker) level. Available policy settings include: yes RA required; signature must be successfully verified. no-verify RA required; signature is not verified. no No RA required. only-route RA required; if invalid signature, use route if no other verified route exits. The default policy is "yes"; under normal operation S-BGP should always require and verify RAs in all received UPDATEs. The "only-route" setting provides a more permissive alternative. In the case that an S-BGP speaker lacks the public key required for RA verification, the "no-verify" setting requires an RA but no cryptographic verification is performed. The "no" policy setting allows for speakers to accept UPDATEs from neighboring speakers that are not S-BGP capable. If, however, the "no" policy is set and an UPDATE that contains RAs is received, then the RAs are processed and verified. C.5.3 new-speaker A "new speaker" is an RA signer for which there is no public key in the database. The "new-speaker" policy directs an S-BGP speaker to either reject or accept an UPDATE that cannot be verified due to a missing public key. This policy is applied at the global and AS levels, and available settings include: reject Reject routes received for which there is no public key. accept Accept routes received for which there is no public key. only-route Accept routes received for which there is no public key when no other verified route for a prefix exists. The default policy setting is "reject". Strict security requires the successful verification of all received routes. A more permissive alternative is the "only-route" setting. The "accept" setting is useful when an AS forgets to renew an expired key, or starts sending RAs before the public key has been propagated throughout the Internet. C.5.4 new-prefix A "new prefix" is a prefix for which a speaker has no origination AA information. The "new-prefix" policy instructs an S-BGP speaker how to handle a received UPDATE that contains a prefix for which no AA information exists and, therefore, cannot undergo AA verification. Lynn, Mikkelson, Seo [Page 67] Secure BGP June 2003 This policy is applied at the global, AS, and prefix levels, and available settings include: reject Reject route for a prefix with no AA information. accept Accept route for a prefix with no AA information. Policy defaults to the "reject" setting. The "accept" policy setting is useful when a prefix owner has never issued an AA, or fails to reissue an expired AA. This policy only applies when there is no AA information for a prefix, not when the authorized originating ASes are specified but the route identifies a different originating AS. C.5.5 send-explicit The "send-explicit" policy directs an S-BGP speaker to include, or not include, protected path attributes as explicit data within the locally generated. This policy may be applied at the global (i.e., all generated RAs) and speaker (i.e., generated RAs intended for a particular peer speaker) levels. The available settings for this policy are: yes Protected path attributes in locally generated RAs are included as explicit data. no Protected path attributes in locally generated RAs are not included as explicit data, i.e., they are implicit data. The default setting is "no"; under normal operation when the content of a path attribute does not change, an S-BGP speaker should not include protected path attributes as explicit in the generated RAs prepended to outbound UPDATEs. Protected path attributes are included as explicit data by setting this policy to "yes". The "mask-explicit" policy (see section C.6.4) overrides the "no" setting. A speaker in a peer AS to which a UPDATE is sent MAY change explicit data to implicit prior to the further propagation of the UPDATE to reduce the size of the UPDATE if the data has not changed (see section C.5.6). C.5.6 make-implicit The "make-implicit" policy directs an S-BGP speaker to change, or not change, explicitly protected path attributes in the Last received RA in a received UPDATE to implicit data when advertising it to external peers. This only applies to protected path attributes that have not been modified by the speaker; all modified path attributes that are protected must be included as explicit in the Last received RA. This policy is applied at the global and peer levels, and available Lynn, Mikkelson, Seo [Page 68] Secure BGP June 2003 settings include: yes Explicit path attributes in Last received RAs are made implicit. no Explicit path attributes in Last received RAs remain as explicit. Under default operations all the data in the ExplicitPA part of the Last received RA should be implicit, i.e., the ExplicitPA part is empty and this policy setting does not apply. The default setting is "yes", which allows a speaker to reduce the size of an UPDATE by removing redundant explicit data from the RAs in its advertisements. If all the RAs within an UPDATE included an explicit copy of all protected path attributes the UPDATE may grow too large for the 4 KB UPDATE limit. The "no" setting is available to allow protected path attributes to remain as explicit within the Last received RA. This may be used when a newly defined transitive path attribute is introduced into BGP. The canonicalized format of new path attributes may not be known, and consequently, such path attributes should remain explicit in RAs. C.6. Extensibility The following policy allows an S-BGP speaker to be easily extended to handle new transitive BGP path attributes. C.6.1 mask-require The "mask-require" policy specifies the path attributes that must be protected within received RAs. If an RA in a received UPDATE does not protect all the path attributes specified by this policy, then the route must be rejected. This policy is applied at the global (i.e., all RAs), AS (i.e., RAs generated by or transiting a particular AS), and speaker (i.e., RAs generated by a particular speaker) levels. By default, the "mask-require" policy specifies that the ORIGIN and AS PATH path attributes, in addition to the NLRI, be protected within received RAs because they represent route information essential for the operation of S-BGP. C.6.2 mask-ignore The "mask-ignore" policy specifies path attributes that, except for the case of signature verification, should not cause a received UPDATE to be rejected. A path attribute to be ignored as indicated by this policy does not need to be verified for semantics or correct propagation. However, an ignored but protected path attribute needs to be sufficiently valid to result in the successful signature Lynn, Mikkelson, Seo [Page 69] Secure BGP June 2003 verification of an RA. By default, the "mask-ignore" policy is an empty set, specifying no path attributes to be ignored during verification, and is applied at the global, AS, and speaker levels. C.6.3 mask-protect The "mask-protect" policy specifies the path attributes that must be protected within locally generated RAs prepended to outbound UPDATEs. This policy is applied at the global and speaker levels. By default, the "mask-protect" policy specifies that all defined transitive path attributes be protected in generated RAs. In addition to the path attributes specified by this policy, all path attributes protected by the Last received RA must be protected. The NLRI, ORIGIN, and AS PATH represent route information essential for the operation of S-BGP and should always be protected. It is recommended that other transitive path attributes included within an UPDATE be protected, as well, to ensure greater security. However, protection of path attributes that may change frequently from speaker to speaker (e.g., communities) increases the size of RAs. Each time that a protected path attribute is modified at a speaker during route propagation an explicit copy must be included within the Last received RA. Additionally, splitting an UPDATE that contains an attestation path attribute into multiple UPDATEs only results in UPDATEs even greater in size because the protected path attributes need to be included as explicit data. This policy allows path attributes, particularly those less essential to correct operation, to be excluded from protection in consideration of the size and growth of UPDATEs. C.6.4 mask-explicit The "mask-explicit" policy directs an S-BGP speaker to include specific protected path attributes as explicit date within locally generated RAs prepended to outbound UPDATEs. This policy only applies in the case that the "send-explicit" policy (see section C.5.5) is set to "no", and is applied at the global and speaker levels. By default, the "mask-explicit" policy does not specify that any defined transitive path attributes be included as explicit within generated RAs. Transitive path attributes protected by S-BGP may need to undergo canonicalization prior to signature generation and verification. Not all S-BGP speakers may know the canonicalized format of a path attribute, especially in the case of one newly defined, and therefore such path attributes should be included as explicit date (in canonicalized form) within the RAs generated by the speaker that included the path attribute within an UPDATE. Therefore, this policy is important in enabling the incremental deployment of newly defined Lynn, Mikkelson, Seo [Page 70] Secure BGP June 2003 path attributes. C.7. Incremental Deployment Policy Examples When an S-BGP capable router is first installed (before the AS is ready to use the S-BGP protections) it should "turn S-BGP off". The following policy settings are used. Policy Level Setting ----------- ------ ------- enable-AA global no enable-RA global no send-attest global no The next step in deployment, might be to just perform NLRI origination verification, but not make any route selections based on the results; i.e., just report failures. Policy Level Setting ----------- ------ ------- enable-AA global yes require-AA global no enable-RA global no send-attest global no When all the BGP speakers are ready to use the S-BGP protection mechanisms to select routes, but peer ASes are not S-BGP capable, the speakers may initially only perform AA verification. Such a speaker would use the following policy settings. Policy Level Setting ----------- ------ ------- enable-AA global yes enable-RA global no send-attest global no Now consider an S-BGP speaker that peers with all non S-BGP capable speakers except for speaker x within AS X. Lets assume that no other speakers in AS X are S-BGP capable. Policy is set as below. Policy Level Setting ----------- ------ ------- enable-AA global yes enable-RA global yes require-RA global no require-RA speaker x yes send-attest global no send-attest speaker x yes Now, assume that all ASes and their associated speakers are S-BGP Lynn, Mikkelson, Seo [Page 71] Secure BGP June 2003 capable except for peer AS Y. Policy Level Setting ----------- ------ ------- enable-AA global yes enable-RA global yes require-RA global yes require-RA AS Y no send-attest global yes send-attest AS Y no C.8. Summary Columns heading abbreviations: G Global A AS S Speaker or peer P Prefix A default value is enclosed in [...]. Policy Section Class G A S P Type Values --------------- ------- ------------- - - - - ------- ------ enable-AA 3.1.1 Activation X _ _ _ enum [yes] no require-AA 3.4.1 Deployment X X _ X enum [yes] only-route no enable-RA 3.1.2 Activation X _ _ _ enum [yes] no require-RA 3.4.2 Deployment X X X _ enum [yes] no-verify only-route no verify-RA 3.3.1 Tuning and X _ _ _ enum receipt Optimization [selection] background new-speaker 3.4.3 Deployment X X _ _ enum [reject] only-route accept new-prefix 3.4.4 Deployment X X _ X enum [reject] accept multi-route 3.3.2 Tuning and X _ _ X enum [all] Optimization one mask-require 3.5.1 Extensibility X X X _ bitmask [NLRI] [ORIGIN] [AS PATH] ATOMIC AGG AGG COMM Lynn, Mikkelson, Seo [Page 72] Secure BGP June 2003 DPA MPREACH EXT COMM mask-ignore 3.5.2 Extensibility X X X _ bitmask NLRI ORIGIN AS PATH ATOMIC AGG AGG COMM DPA MPREACH EXT COMM send-attest 3.1.3 Activation X _ X _ enum [yes] no send-explicit 3.4.5 Deployment X _ X _ enum yes [no] make-implicit 3.4.6 Deployment X _ X _ enum [yes] no mask-protect 3.5.3 Extensibility X _ X _ bitmask [NLRI] [ORIGIN] [AS PATH] [ATOMIC AGG] [AGG] [COMM] [DPA] [MPREACH] [EXT COMM] mask-explicit 3.5.4 Extensibility X _ X _ bitmask NLRI ORIGIN AS PATH ATOMIC AGG AGG COMM DPA MPREACH EXT COMM max-origin 3.3.3 Tuning and X _ X _ percent 75% Optimization prefix-class 3.3.4 Tuning and _ _ _ X integer 0 Optimization sign-AS 3.2.1 Configuration _ _ X _ AS set null set aggregate-any 3.3.5 Tuning and X _ _ _ enum yes Optimization [no] in-cache-depth 3.3.6 Tuning and X _ X _ integer 1 Optimization out-cache-depth 3.3.7 Tuning and X _ X _ integer 1 Optimization peer-auth 3.2.2 Configuration X _ X _ enum BGP [System] No peer-key 3.2.3 Configuration X _ _ _ integer no key Lynn, Mikkelson, Seo [Page 73] Secure BGP June 2003 upload-port 3.2.4 Configuration X _ _ _ integer Lynn, Mikkelson, Seo [Page 74] Secure BGP June 2003 Appendix D. NOC Support This informational appendix describes operations that a NOC that uses S-BGP would perform. S-BGP uses out-of-band distribution of Address Attestations, Certificate Revocation Lists, and Certificates. An S-BGP speaker will eventually need the public key from the certificate of each RA signer, and will eventually need an Address Attestation for each prefix in one of its Adj-RIBs-Ins. There are two tiers in the distribution hierarchy. The first tier consists of servers at several well-known and highly connected locations such as a major peering points or ISPs. These servers are sent certificates and CRLs by the registries and organizations given the right to use AS numbers or IP address blocks. End organizations that are given the right to use IP address blocks create and sign Address Attestations that authorize their provider's AS to advertise their address block, and send the AAs to the servers. The second tier consists of the NOCs of the organizations that manage ASes. They transfer from the first tier servers the set of AAs, certificates, and CRLs. The NOC then validates the information received, digests it, and uploads the digested information to their S-BGP speakers. This preprocessing by the NOC has several advantages. First, the verification of the AAs, certificates, and CRLs is performed only once instead of having each S-BGP speaker duplicate the work. Second, digesting the information significantly reduces the volume of data that is sent to and stored in the speakers. Third, by receiving pre-validated data, the time for the S-BGP speaker to reboot from a catastrophic loss of memory is significantly reduced. Forth, in the event of a catastrophic loss of inter-AS routing, the information can still be uploaded to speakers using intra-AS routing. Certification functions performed by the NOC: Generate public/private key pair for the AS. Send the AS's public key to registry for inclusion in the certificate transferring the right to use the AS number to the organization. Generate public/private key pairs for each authorized S-BGP speaker in the AS and issue them each a certificate. Copies of the certificates are sent to an S-BGP repository. Generate a public/private key pair for the organization's ownership of IP address blocks. The public key is sent to the IP address delegation registry for inclusion in the certificate Lynn, Mikkelson, Seo [Page 75] Secure BGP June 2003 transferring the right to use the address blocks to the organization. Intellectual Property Rights The IETF takes no position regarding the validity or scope of any intellectual property or other rights that might be claimed to pertain to the implementation or use of the technology described in this document or the extent to which any license under such rights might or might not be available; neither does it represent that it has made any effort to identify any such rights. Information on the IETF's procedures with respect to rights in standards-track and standards-related documentation can be found in BCP-11. Copies of claims of rights made available for publication and any assurances of licenses to be made available, or the result of an attempt made to obtain a general license or permission for the use of such proprietary rights by implementors or users of this specification can be obtained from the IETF Secretariat. The IETF invites any interested party to bring to its attention any copyrights, patents or patent applications, or other proprietary rights which may cover technology that may be required to practice this standard. Please address the information to the IETF Executive Director. Full Copyright Statement This document and translations of it may be copied and furnished to others, and derivative works that comment on or otherwise explain it or assist in its implementation may be prepared, copied, published and distributed, in whole or in part, without restriction of any kind, provided that the above copyright notice and this paragraph are included on all such copies and derivative works. However, this document itself may not be modified in any way, such as by removing the copyright notice or references to the Internet Society or other Internet organizations, except as needed for the purpose of developing Internet standards in which case the procedures for copyrights defined in the Internet Standards process shall be followed, or as required to translate it into languages other than English. The limited permissions granted above are perpetual and will not be revoked by the Internet Society or its successors or assigns. This document and the information contained herein is provided on an "AS IS" basis and THE INTERNET SOCIETY AND THE INTERNET ENGINEERING TASK FORCE DISCLAIMS ALL WARRANTIES, EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO ANY WARRANTY THAT THE USE OF THE INFORMATION HEREIN WILL NOT INFRINGE ANY RIGHTS OR ANY IMPLIED WARRANTIES OF Lynn, Mikkelson, Seo [Page 76] Secure BGP June 2003 MERCHANTABILITY OR FITNESS FOR A PARTICULAR PURPOSE. Author's Addresses Charles Lynn BBN Technologies 10 Moulton Street Cambridge, MA 02138 USA E-mail: CLynn@BBN.Com Telephone: 617-873-3367 Joanne Mikkelson BBN Technologies 10 Moulton Street Cambridge, MA 02138 USA E-mail: JMMikkel@BBN.Com Telephone: 617-873-4598 Karen Seo BBN Technologies 10 Fawcett Street Cambridge, MA 02138 USA E-mail: KSeo@BBN.Com Telephone: 617-873-3152 Lynn, Mikkelson, Seo [Page 77]