Internet Engineering Task Force Charles Lynn Internet Draft Joanne Mikkelson draft-clynn-s-bgp-protocol-00.txt Karen Seo BBN Technologies October 1999 Secure BGP (S-BGP) 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 an Internet standards track 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 (March 1999). 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 Expires April 2000 Lynn, Mikkelson, Seo [Page 1] Internet Draft Secure BGP October 1999 countermeasures and to be interoperable with the current BGP so as to 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 . . . . . . . 4 1.2. Overview of the S-BGP Architecture . . . . . . . . . . . . 6 1.2.1. Public Key Infrastructures (PKIs) . . . . . . . . . . . . 6 1.2.1.1. PKI for Assignment of IP Address Blocks . . . . . . . . 7 1.2.1.2. PKI for Assignment of AS Numbers and Router Association with 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 2. Terminology . . . . . . . . . . . . . . . . . . . . . . . . . 11 3. Attestation Path Attribute . . . . . . . . . . . . . . . . . 16 3.1. Attestation Path Attribute Formats . . . . . . . . . . . . 17 3.1.1. Route and Address Attestations . . . . . . . . . . . . . 17 3.1.2. RA Sequences and Aggregation . . . . . . . . . . . . . . 23 3.1.3. Certificates and CRLs . . . . . . . . . . . . . . . . . . 24 3.2. Processing Rules . . . . . . . . . . . . . . . . . . . . . 24 3.2.1. Overview of Certificate, AA, and CRLs Processing/ Verification . . . 25 3.2.2. Route Attestation Processing . . . . . . . . . . . . . . 26 3.2.2.1. Route Attestation Validation . . . . . . . . . . . . . 28 3.2.2.2. Route Attestation Creation . . . . . . . . . . . . . . 32 3.2.3. BGP Phase Processing . . . . . . . . . . . . . . . . . . 35 3.2.3.1. Phase 1 Processing . . . . . . . . . . . . . . . . . . 35 3.2.3.2. Phase 2 Processing . . . . . . . . . . . . . . . . . . 36 3.2.3.3. Phase 3 Processing . . . . . . . . . . . . . . . . . . 36 3.2.4. S-BGP Processing . . . . . . . . . . . . . . . . . . . . 37 3.2.4.1. Unknown Path Attributes and Canonicalization . . . . . 37 Expires April 2000 Lynn, Mikkelson, Seo [Page 2] Internet Draft Secure BGP October 1999 3.2.4.2. Receive Processing . . . . . . . . . . . . . . . . . . 38 3.2.4.3. Send Processing . . . . . . . . . . . . . . . . . . . . 40 3.2.4.4. Background Processing . . . . . . . . . . . . . . . . . 42 3.2.5. Non-S-BGP Speakers . . . . . . . . . . . . . . . . . . . 43 3.2.5.1. Validation . . . . . . . . . . . . . . . . . . . . . . 44 3.2.5.2. Policy . . . . . . . . . . . . . . . . . . . . . . . . 44 4. Processing Optimizations . . . . . . . . . . . . . . . . . . 45 5. Certificates . . . . . . . . . . . . . . . . . . . . . . . . 46 6. Address Attestations . . . . . . . . . . . . . . . . . . . . 46 7. Security Considerations . . . . . . . . . . . . . . . . . . . 47 8. Acknowledgements . . . . . . . . . . . . . . . . . . . . . . 47 9. References . . . . . . . . . . . . . . . . . . . . . . . . . 47 Appendices A. Example Certificates (Extensions), Hashes, Signatures . . . . 49 B. Policy Support . . . . . . . . . . . . . . . . . . . . . . . 49 C. Configuration . . . . . . . . . . . . . . . . . . . . . . . . 49 D. NOC Support . . . . . . . . . . . . . . . . . . . . . . . . . 50 Intellectual Property Rights . . . . . . . . . . . . . . . . . . 51 Full Copyright Statement . . . . . . . . . . . . . . . . . . . . 51 Author's Addresses . . . . . . . . . . . . . . . . . . . . . . . 52 Table of Figures Figure 1: Address Space PKI Structure . . . . . . . . . . . . . x Figure 2: AS Ownership and Router ID PKI . . . . . . . . . . . x Figure 3: Terminology Example . . . . . . . . . . . . . . . . . x Figure 4: Structure of an Address or Route Attestation . . . . x Figure 5: Route and Address Attestation and Authenticator Headers . . . x Figure 6: Issuer Part . . . . . . . . . . . . . . . . . . . . . x Figure 7: Formats of Issuer Name Forms . . . . . . . . . . . . x Figure 8: Signature Part . . . . . . . . . . . . . . . . . . . x Figure 9: CoverageMask Field . . . . . . . . . . . . . . . . . x Figure 10: Validity Part . . . . . . . . . . . . . . . . . . . . x Figure 11: Explicit PA Part . . . . . . . . . . . . . . . . . . x Figure 12: Prefix Encoding . . . . . . . . . . . . . . . . . . . x Figure 13: Subject Part . . . . . . . . . . . . . . . . . . . . x Figure 14: Aggregation Example . . . . . . . . . . . . . . . . . x Figure 15: CRL Section . . . . . . . . . . . . . . . . . . . . . x Figure 16: Certificate Section . . . . . . . . . . . . . . . . . x Expires April 2000 Lynn, Mikkelson, Seo [Page 3] Internet Draft Secure BGP October 1999 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) [RFC1771] 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 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. A companion document [JSAC] has been written which describes the S-BGP architecture. It provides a discussion of the vulnerabilities and security requirements associated with BGP and a high-level description of S-BGP's components, and how the components work together to address these vulnerabilities. It also includes a comparison of this architecture with other approaches that have been proposed, and an overview of performance and operational issues. Another document [NDSS00] contains experimental data collected from a prototype implementation of S-BGP in the GateD (TM) BGP implementation. This document assumes that the reader is familiar with BGP, related networking technology, and general security terms and concepts. 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 Expires April 2000 Lynn, Mikkelson, Seo [Page 4] Internet Draft Secure BGP October 1999 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. * 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. * The UPDATE was intended for receipt by the peer that received it. * 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. * The owner of an address space corresponding to a reachable prefix advertised in an UPDATE was authorized by its parent organization to own that address space. * The first AS in the route was authorized, by the owners of the address space corresponding to the set of reachable prefixes, to advertise those prefixes. * If the UPDATE indicates a withdrawn route, then the peer withdrawing the route was a legitimate advertiser for that route, prior to its withdrawal. * 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. * 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 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. Expires April 2000 Lynn, Mikkelson, Seo [Page 5] Internet Draft Secure BGP October 1999 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 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. The countermeasures should be dynamic, responding quickly to topology changes, including the addition of a new AS, network, or router. 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. The approach adopted to securing BGP route distribution involves two Public Key Infrastructures (PKIs), a new transitive path attribute containing "attestations", and the use of IPsec. These components are used by a 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 pair of Public Key Infrastructures (PKIs), based on X.509 v3 certificates containing private S-BGP extensions, is used to provide assurance that the AS numbers and IP address prefixes being advertised have been authorized for use by their respective owners. See [JSAC] for a more detailed description of the PKIs and an overview of S-BGP. A new BGP optional transitive path attribute, the Attestation Path Attribute, is used to carry digital signatures that protect the prefixes (NLRI or Multiprotocol Reachable NLRI), the AS Path, and optionally other transitive path attributes as a BGP UPDATE is propagated between ASes. IPsec, in conjunction with a certificate issued to each BGP speaker, provides authentication of BGP peers and provides data integrity for the TCP connection between them. It also protects the connection from replay attacks. 1.2.1. Public Key Infrastructures (PKIs) 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 ownership, AS number ownership, AS identification, and BGP router identification and authorization to represent an AS. The PKIs involve three kinds of certificates. See [RFC2459] for certificate and CRL formats. The concepts and terms address Expires April 2000 Lynn, Mikkelson, Seo [Page 6] Internet Draft Secure BGP October 1999 atestation (AA) and route attestation (RA) are described in section 1.2.2. There already exist procedures and personnel to manage the assignment of IP address prefixes and AS numbers. S-BGP builds upon this existing infrastructure to manage these certificates. The PKIs that must be created to support S-BGP will overlay the existing administrative framework, based on the ICANN, regional registries, ISPs, etc. 1.2.1.1. PKI for Assignment of IP Address Blocks The first type of certificate binds a public key to an organization and to a set of IP address families and prefixes. These certificates, in conjunction with address attestations, are used to verify that the IP address space owner has authorized one or more ASes to advertise the address space. The certificates are arranged into a singly-rooted hierarchy that parallels the existing IP address allocation system. Thus the Internet Corporation for Assigned Names and Numbers (ICANN) is the root, and the next tier generally will consist of registries such as APNIC, ARIN, and RIPE. (Because of historic allocation of addresses, this characterization is a simplification of the actual certification tree. For example, some ISPs and subscriber organizations hold addresses assigned directly by the Internet Assigned Numbers Authority (IANA), the predecessor to the ICANN.) The next tier generally consists of ISPs. An additional tier represents DSPs or subscribers that own IP address blocks. Note that only those entities that own IP address blocks need these certificates. Figure 1 illustrates this certification tree, showing the organizations that are represented at each tier. Expires April 2000 Lynn, Mikkelson, Seo [Page 7] Internet Draft Secure BGP October 1999 ICANN All Addr blocks | +------------------------+-------------------------+ | | | APNIC ARIN RIPE Addr blocks Addr blocks Addr blocks | +-----------+----+++-----+------------+----+++-----+ | | ||| | | ||| | AT&T DSP 1 ... GTE-I ISP 2 ... MCI Addr Addr Addr Addr Addr block(s) block(s) block(s) block(s) block(s) | | | | ..--+--.. ..--+--.. ..--+--.. ..--+--.. | | | | Subscriber A DSP 3 Subscriber B ISP 4 Addr Addr Addr Addr block(s) block(s) block(s) block(s) | | | ... ... ... Figure 1: Address Space PKI Structure 1.2.1.2. PKI for Assignment of AS Numbers and Router Association with an AS The second type of certificate binds a public key to an organization and a set of AS numbers, and the third binds a public key to an AS number and to a BGP router ID. Together, these two types of certificates allow BGP speakers to authenticate one another, and to verify that a given speaker is authorized to represent a specified AS. Here too, the ICANN is the root of the hierarchy and the second tier consists of registries. (The certificates issued by the ICANN to registries are conventional in format and are employed to permit use of a single root for all classes of certificates.) The third tier consists of ISPs, DSPs, and subscribers. The second type of certificate is issued at the second tier, and the third type at the third tier. Lower tiers generally represent ASes and routers associated with higher tier organizations. Note that only those entities that own an AS number, that manage S-BGP speakers, or that participate in a BGP peering session need these certificates. Figure 2 illustrates a simple example of the tree structure for these two types of certificates, noting the organizations involved at the top three tiers, and the ASes and routers that populate the lower tiers. Expires April 2000 Lynn, Mikkelson, Seo [Page 8] Internet Draft Secure BGP October 1999 ICANN All AS Numbers | +------------------------+-------------------------+ | | | APNIC ARIN RIPE AS Numbers AS Numbers AS Numbers | +-----------+----+++-----+------------+----+++-----+ | | ||| | | ||| | AT&T DSP 1 ... GTE-I ISP 2 ... MCI AS Numbers AS# W AS Numbers AS Numbers AS Numbers | | | | | ..--+--.. ... +-------+--++++++ ... ..--+--.. | | |||||| | DSP 3 AS# Z Routers in AS# Z ISP 4 AS# X AS# Y | | +--+---------+++ +----------++++--+ | ||| | |||| AS# X Routers in AS# X AS# Y Routers in AS# Y Figure 2: AS Ownership and Router ID PKI 1.2.1.3. Use of the Certificates in the PKIs The certificates described above are used to enable verification of: * An organization's authorization to "own" a block of addresses The first type of certificate (section 1.2.1.1) is used to verify that an organization is authorized to "own" a block of addresses, and to in turn authorize one or more ASes to advertise them. In particular, the signature on an address attestation must be verifiable using the public key in a certificate containing the address block or blocks that include the address block(s) in the address attestation. * An organization's ownership of an AS number The second type of certificate (section 1.2.1.2) is used to verify that an AS has been assigned by ICANN to the holder of a particular public key, e.g., an organization. They are used to verify the certificates associated with ASes and the S-BGP speakers within those ASes through the AS number linkage and the usual subordinate certificate signature checks. * An AS's identity The second type of certificate (section 1.2.1.2) is used to verify the signature of an AS on a route attestation, or on AA and certificate extract files. Expires April 2000 Lynn, Mikkelson, Seo [Page 9] Internet Draft Secure BGP October 1999 * A router's identity and its association with an AS The third type of certificate (section 1.2.1.2) is used to verify the signature of a router on a route attestation and in conjunction with the second type to make sure that the router is authorized to act on behalf of the AS. * Identity and authorization of a BGP peer The third type of certificate (section 1.2.1.2) can be used by the BGP routers to authenticate each other when setting up IPsec protected peering sessions. 1.2.2. Attestations "Attestations" constitute the second major component of the architecture. They form the heart of S-BGP, and represent a conceptually straightforward means of achieving the critical security guarantees 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 keys and certificates from the PKIs described above. They enable each BGP speaker that receives a route advertisement to verify that each AS along the path has been authorized by the preceding AS along the path to advertise the route, and that the originating AS has been authorized by the owner of each IP address prefix contained in the UPDATE to advertise those prefixes. The attestations are carried in a new BGP optional transitive path attribute that contains digital signatures protecting the transitive routing information. Conceptually, there are two types of attestations: * Route attestations (RAs) - where the issuer is a router authorized to represent the AS (or the AS itself) and the subject is a transit AS or another AS providing third party advertisements for an AS that is not running BGP. * Address attestations (AAs) - where the issuer is the organization that owns the address prefixes contained in the attestation and the subject is one or more ASes that are authorized to advertise these 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, RFC2410] is used to provide data and partial sequence integrity, and peer entity authentication for BGP control traffic. Because it is implemented at Expires April 2000 Lynn, Mikkelson, Seo [Page 10] Internet Draft Secure BGP October 1999 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. 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. 2. Terminology There are several terms, e.g., "first RA" and "last 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 the sections to follow. The terms are ordered for readability (minimal forward references) 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]. Protected Transitive Information The transitive routing information that S-BGP protects using digital signatures. The term includes both the prefixes in either the NLRI field or Multiprotocol Reachable NLRI path attribute, as well as a configurable set of other path attributes that contain information distributed beyond a single AS hop. Certificates 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. Certificates used with S-BGP contain private extensions [X509EXT] used to convey authorization to use IP address blocks, AS numbers, or to bind a BGP Identifier to a specific AS. Certificates containing S-BGP extensions are issued to ICANN, the Registries (APNIC, ARIN, RIPE, etc.), organizations that own IP address blocks or Autonomous System numbers, Autonomous Systems, and BGP speakers (routers). See [RFC2459]. Certificate Extract A condensation of the information in a certificate to only that needed for ongoing S-BGP operation. The S-BGP related certificates are gathered by an AS's management (NOC), verified, extracted, and signed using the AS's private key. The extracted certificates are periodically uploaded to the S-BGP speakers in the AS. The integrity of the file containing extracts is assured Expires April 2000 Lynn, Mikkelson, Seo [Page 11] Internet Draft Secure BGP October 1999 by appending an authenticator to the extacts and signing the result. Certificate Revocation Lists (CRLs) CRLs are periodically issued by a Certification Authority and contain a list of identifiers of certificates that have been revoked. The list is digitally signed by the Certification Authority using its private key. See [RFC2459]. Attestation Path Attribute 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 four sections of information in the following order: Route Attestations, Address Attestations, Certificate Revocation Lists, and Certificates. Each entry in one of the sections, i.e., an individual RA, AA, etc., is protected by a digital signature. Typically, only the RA section will be present in S-BGP advertisements. Address Attestation (AA) An AA consists of an attestation header followed by five parts, in the following order: Issuer, Signature, Validity, Explicit PA, and Subject. An address attestation conveys authorization from the owner of a block of IP addresses (the issuer) for one or more ASes (the subject) to originate an advertisement for the specified prefix(es). AAs are usually uploaded to an S-BGP speaker by the speaker's NOC, in the form of a signed list of AA extracts. Address Attestation Extract (AA extract) An AA extract consists of an attestation header followed by three parts, in the following order: Validity, Explicit PA, and Subject. AAs are obtained in bulk from a first tier repository by each AS's NOC, verified, extracted (the Issuer and Signature parts are discarded), and collected into a file that has an authnticator appended and is then digitally signed using the AS's private key. The file is uploaded to S-BGP speakers in the AS. Issuer (Part of an AA or RA) The Issuer part contains information that identifies the entity that signed the attestation so that the entity's certificate, containing its public key, can be found for use in verifying the signature. An issuer may be identified by an AS number, a DNS name, or an IP v4 or v6 address. Signature (Part of an AA or RA) The Signature part identifies the digital hash and signature algorithms used to sign the attestation. Also present are the bytes of the signature and an indication of which of possibly multiple valid certificates should be used to verify the signature. RAs also have a bit mask identifying the protected Expires April 2000 Lynn, Mikkelson, Seo [Page 12] Internet Draft Secure BGP October 1999 transitive information that is protected by the digital signature. The digital signature protects the Validity, Explicit PA, and Subject parts of an AA or RA. The algorithms 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. Validity (Part of an AA or RA) The Validity part contains the date and time before which and after which the attestation is not valid. Also present are the "R-bit" (used for revocation) and, in an RA, the "A-bit" (used to indicate path aggregation) and the RASequenceLength field. Explicit PA (Part of an AA or RA) The Explicit PA (path attribute) part contains a canonicalized version of the protected transitive information included in the digital signature. Explicit Data When a copy of the protected transitive information is placed into the Explicit PA part of an attestation, it is called explicit data. Implicit Data When the protected transitive information can be obtained from either the UPDATE's NLRI or path attributes, or from explicit data in a subsequent RA, it may be omitted from the Explicit PA part of an RA. The omitted redundant information is called implicit data. Use of implicit data reduces the size of an RA. Subject (Part of an AA or RA) The use of the Subject part differs between AAs and RAs. In an AA, it contains the AS number(s) of the ASes that are being authorized by the issuer of the AA to originate the prefixes in the prefix pseudo path attribute (see 3.1.1 e) in the Explicit PA part. The Subject part of an RA contains the AS number of the AS that is being authorized by the issuer (an S-BGP capable exit border router, identified by its BGP Identifier) to place the route into its Adj-RIB-In. Authenticator (or an extract file) An authenticator consists of the Type, Issuer, Signature, Validity, and Subject parts. Both the issuer and the subject are the AS. The authenticator (with the SignatureBytes field set to zeros) is included in the information to be signed. Route Attestation (RA) An RA consists of an attestation header followed by a sequence of five parts, in the following order: Issuer, Signature, Validity, Explicit PA, and Subject. A route attestation is used to protect Expires April 2000 Lynn, Mikkelson, Seo [Page 13] Internet Draft Secure BGP October 1999 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. RA Sequence As an 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. 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). 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. RA Sequence Length (RASL) 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. It is necessary to enable subsequent speakers to resolve implicit data. When combined with the RA subject, the count enables detection of the malicious removal of RAs from an advertisement. Expires April 2000 Lynn, Mikkelson, Seo [Page 14] Internet Draft Secure BGP October 1999 UPDATE UPDATE Sent to AS 2 by AS 8 Sent to AS 8 by AS 5 +-----------------------+ +-----------------------+ | Path Attributes | | Path Attributes | | ASP: 8,8,5 | | ASP: 5 | | Attestations | | Attestations | Last RA --> | RA | | | | Issuer: U.7 | | | | Sig: ... | | | | Validity | | | | RASL: 2 | | | | ExpPA | | | Explicit -> | Pfxs: 10.1/16 | | | Data -> | ASP: 8,8,5 | | | | Subject: AS 2 | | | First RA -> | RA | | RA | | Issuer: N.8 | | Issuer: N.8 | | Sig: ... | | Sig: ... | | Validity | | Validity | | RASL: 1 | | RASL: 1 | | ExpPA | | ExpPA | Implicit -> | | | Pfxs: 10.1/16 | Data -> | | | ASP: 5 | | Subject: AS 8 | | Subject: AS 8 | | NLRI: 10.1/16 | | NLRI: 10.1/16 | +-----------------------+ +-----------------------+ AS 2 AS 8 AS 5 ............. .................... ............. : +------+: :+------+ +------+: :+------+ : : |BGP Id|: :|BGP Id| |BGP Id|: :|BGP Id| : : | F.5 |: <-- :| U.7 | | U.5 |: <-- :| N.8 | : : +------+: :+------+ +------+: :+------+ : :...........: :..................: :...........: .... +--+ : : Autonomous System | | S-BGP border router :..: +--+ Figure 3: Terminology Example First RA In the absence of aggregation, the RASequenceLength field counts the number of RAs present, beginning with 1 for the "first RA", i.e., the one added by the route originator, AS 5. Last RA When an AS receives an advertisement, the RA immediately following the attestation path attribute header is called the "last RA". The RA designated by the term last RA changes on exit from each S-BGP capable AS; the first RA does not. Expires April 2000 Lynn, Mikkelson, Seo [Page 15] Internet Draft Secure BGP October 1999 Next RA The "next RA" is the one prepended immediately after the current RA. In the diagram, "next" moves to the left. Previous RA The "previous RA" is the one prepended immediately before the current RA. In the diagram, "previous" moves to the right. RA Sub-Sequence When a 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 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 RASequenceLength field of the locally generated RA is set to one more than the number of RAs that were concatenated. Alternatively, it is set to 1 plus the sum of the RASequenceLength fields of the last RA in each of the RA sub-sequences. 3. Attestation Path Attribute 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 is logically divided into four ordered sections, each of which may contain zero or more entries: Route Attestations (which are also ordered), Address Attestations, Certificate Revocation Lists, and Certificates. The route attestation section usually has at least one entry. The ordering of the RAs in the route attestation section is described in sections 2 and 3.1.2. The information in the latter three sections, which is both voluminous and changes at a low rate, is usually distributed out-of- band to each S-BGP speaker, e.g., it is uploaded by the speaker's management. 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 prepended by the AS's exit border router and identifies (in the Subject part) the AS 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 next AS and the identity of that AS. The identity of the 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 Expires April 2000 Lynn, Mikkelson, Seo [Page 16] Internet Draft Secure BGP October 1999 to use the information in the advertisement. The 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. The attestation path attribute has Type Code TBD. The BGP path attribute header is as described in [RFC1771]. The following sections describe the attestation path attribute value. 3.1. Attestation Path Attribute Formats Address attestations and route attestations share a common format, described in section 3.1.1. Certificates and CRLs share a simpler format, described in section 3.1.3. Each logically related set of fields in an attestation is called a "part". An S-BGP part code is assigned to the sections for RAs, AAs, CRLs, and certificates, as well as to each defined 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 Type field. Following the Type field is the length in octets of the remainder of the attestation part. Note that this length does not include the two octets containing the Type and length. For all attestation parts except the Validity part, the length is a twelve-bit value; see below for discussion of the Validity part. The parts of an address or route attestation are as follows: +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Type (length = 2 octets) | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-... | Issuer (variable length) +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-... | Signature (variable length) +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-... ----- | Validity (length = 10 for RAs, 8 for AAs) ^ +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-... | | Explicit PA (variable length) Signed +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-... | | Subject (length = 6 for RAs, variable for AAs) v +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-... ----- Figure 4: Structure of an Address or Route Attestation Expires April 2000 Lynn, Mikkelson, Seo [Page 17] Internet Draft Secure BGP October 1999 a) Type part (part codes 8, 9, and 14): The part code in this part is 8 for a route attestation, and 9 an for address attestation, and 14 for an extract file authenticator. The twelve-bit length is the length of the rest of the attestation (not including the Type part). 0 1 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ |1 0 0 0| AttestationLength | RA +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ |1 0 0 1| AttestationLength | AA +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ |1 1 1 0| AuthenticatorLength | Extract File Authenticator +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ Figure 5: Route and Address Attestation and Authenticator Headers b) Issuer part (part code 1): The Issuer part identifies the entity which signed the attestation. The public key which should be used to verify the signature is in a certificate issued to this entity. The issuer can be described by one of four name formats: an AS number, an IPv4 address, an IPv6 address, or a DNS name. The AF/Type field is a two-octet field following the length field that indicates the format of the following name. The values for this field are taken from the Address Family number space of [RFC1700]. I.e., it is 1 for an IPv4 address and 2 for an IPv6 address, TBD for an AS number, and TBD for a DNS name. The length of the name is the IssuerLength less two 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 0 1| IssuerLength | AF/Type | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | IssuerData (variable length) +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+... Figure 6: Issuer Part The IssuerData field contains the identity of the issuer encoded in one of the following four formats: Expires April 2000 Lynn, Mikkelson, Seo [Page 18] Internet Draft Secure BGP October 1999 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | AS Number (length 2) | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | IPv4 (length 4) | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | IPv6 (length 16) | | | | | | | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | DNS Name (N+1 zero-terminated) +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-... Figure 7: Formats of Issuer Name Forms c) Signature part (part code 2): The Signature part contains the information necessary to verify the protected transitive information associated with the attestation. The SignatureAlgorithmID follows the SignatureLength field and is two octets long. Currently one signature algorithm is defined, DSA with the SHA-1 hash; this algorithm is assigned an ID of 3. The next field is a one-octet KeyHash used to identify which of multiple valid certificates for the issuer was used to generate the signature. For DSA, the value of the hash is the first octet of the public key. Following the hash is a one-octet CoverageLen field, providing the length in octets of the immediately following CoverageMask field. (See the next paragraph for a description of the CoverageMask field.) The final field in the Signature part is the signature itself, 40 octets for DSA. Expires April 2000 Lynn, Mikkelson, Seo [Page 19] Internet Draft Secure BGP October 1999 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 | SignatureAlgorithmID | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | KeyHash | CoverageLen | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+... | CoverageMask (variable length) +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | SignatureBytes (40 octets for DSA signature) | | | | | | | | | | | | | | | | | | | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ Figure 8: Signature Part The CoverageMask field describes which BGP path attributes have been included in the signature. Only RAs have a CoverageMask; AAs do not, and set the CoverageLen to zero. Each bit corresponds to a Path Attribute Type Code. For each path attribute covered by the signature, the bit must be set to 1. The BGP-4 NLRI is assigned bit zero. 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 useage, and the one bits correspond to attributes which MAY be protected, according to local policy. 0 1 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+... |1 1 1 0 0 0 1 1 1 0 0 1 0 0 0 0 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+... 0-NLRI or MP_REACH_NLRI, 1-ORIGIN, 2-AS_PATH, 6-ATOMIC_AGGREGATE, 7-AGGREGATOR, 8-COMMUNITIES, 11-DPA, (others defined in future) Figure 9: CoverageMask Field d) Validity part (part code 3): The Validity part specifies the time range for which the attestation should be considered valid. The Type field is four Expires April 2000 Lynn, Mikkelson, Seo [Page 20] Internet Draft Secure BGP October 1999 bits, as with all parts. However, the Len field is also only four bits. This value is the length of the Validity part less the first TWO octets. Note that the length is always 8 for RAs and 6 for AAs, as AAs have neither an A-bit nor an RASequenceLength field. The first bit after the Len field is the revoked bit (R-bit). This bit is set to 1 when other attestations for the same Issuer, Explicit PA, and Subject should be flushed from any caches and RIBs. The remainder of the first three octets encode the Not- Valid-Before (NVB) time, the four following octets encode the Not-Valid-After (NVA) time, and, in the case of an RA, the last two octets RASegmentLength field (RASL). The year field of the NVB represents the magnitude of a negative offset from the year in the NVA. Below, the number of bits devoted to each of the time fields is listed. The year in the NVA is the four-digit calendar year. The range of Month is 1-12, Day is 1-31, Hour is 0-23, and Minute is 0-59. The RASegmentLength 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 first bit of this field, the aggregated bit (A-bit), is set to 1 in an RA created by a S-BGP speaker which has performed aggregation on the AS_PATH, and is set to 0 otherwise. 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 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ NVB |0 0 1 1| Len |R|YrP:3|Month:4| Day:5 | Hour:5 | Minute:6 | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ NVA | Year:12 |Month:4| Day:5 | Hour:5 | Minute:6 | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ |A| RASequenceLength | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ Figure 10: Validity Part e) Explicit PA part (part code 4): The Explicit PA part contains a canonicalized copy of the protected transitive information. The path attributes to be protected are specified by local policy and indicated by a bit in the CoverageMask as described above. The validation process must be able to find the actual values included in 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 [RFC1771]). The individual path attributes in the ExplicitPAs field are sorted by ascending type code. Expires April 2000 Lynn, Mikkelson, Seo [Page 21] Internet Draft Secure BGP October 1999 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| Length | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-... | ExplicitPAs (variable length) -- sequence of path attributes +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-... Figure 11: Explicit PA Part Prefixes, from either the NLRI field or from the Multiprotocol Reachable NLRI path attribute, are encoded in the ExplicitPAs field as a mandatory transitive path attribute with Type Code 0, as shown in the figure below. The value of the attribute consists of a two-octet AddressFamily field and a one-octet SAFI field (see [MPE]). In the case of NLRI, the AddressFamily field contains 1 (IPv4) and the SAFI is usually 1 (unicast). The individual prefixes are sorted by ascending address/mask length. Sorting the prefixes by the speaker which creates the RA simplifies RA validation for all speakers that receive an RA. Since the prefix information uses Type Code 0, the prefixes will always 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 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+... |0 1 0 E 0 0 0 0| Type Code 0 | Length :Extended Length +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+... | AddressFamily | SAFI | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+... | PrefixLength | Prefix (other PrefixLength/Prefix pairs) +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+... Figure 12: Prefix Encoding This encoding is used to make the prefix invariant between NLRI and Multiprotocol Reachable NLRI, since IPv4 prefixes may be encoded in either format, and the encoding can be changed as an UPDATE message propagates through ASes. f) Subject part (part code 5): The Subject part identifies the subject of the attestation. The subject of an RA is the AS number of the BGP speaker to which the UPDATE message will be sent; the length of the Subject part is always four octets. The subject of an AA may be a list of AS numbers, e.g., when the organization owning the prefixes is multihomed to different ASes. In this case, the length of the Subject part is variable, and the number of AS numbers present may be arrived at by subtracting two octets from the SubjectLength and dividing by two. Expires April 2000 Lynn, Mikkelson, Seo [Page 22] Internet Draft Secure BGP October 1999 The AF/Type field should be filled in as it is for the Issuer part. 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| SubjectLength | AF/Type | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | AS number | (possibly more AS numbers) +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+... Figure 13: Subject Part 3.1.2. RA Sequences and Aggregation The order of RAs in the RA sequence in an attestation 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 attestation path attribute before advertising the route to an external peer. The RASegmentLength (RASL) field in the Validity part of the locally generated RA is set to one more than the RASL field of the last RA in the received attestation path attribute. 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, b, c; and RA z. RA a and RA z are the last RAs in their respective RA sequences. Note that the RA sequence RA a, b, c is itself the result of an aggregation, but RA lcl does not need to be cognisant of that fact. 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 RASL field is set to one more than the sum of the RASL fields of the last RAs in each of the RA sequences being concatenated (1 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) | | | | | | | | | | RASL: 5 | | RASL: 3 | | RASL: 1 | | RASL: 1 | | RASL: 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 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 RASL field Expires April 2000 Lynn, Mikkelson, Seo [Page 23] Internet Draft Secure BGP October 1999 contains the number of RAs in the aggregate associated with that RA (lcl): 5. The sequences that were concatenated are found by first subtracting 1 from the working count (resulting in 4). The RASL field of the RA previous to it, 3 from RA a, is used to determine the RA sequence length of a component of the aggregation; that count is subtracted from the working count (resulting in 1). If the count is greater than zero there is another component of the aggregation so the RASL count in the RA previous to the sequence (RA z) is used to repeat the process. 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 can be validated (see section 3.2.2.2). 3.1.3. Certificates and CRLs Certificats and CRLs, when included as part of an attestation attribute, have the following 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 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ |1 0 1 0| Length | Format | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | CRLs (variable length) +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-... Figure 15: CRL Section +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ |1 0 1 1| Length | Format | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Certificates (variable length) +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-... Figure 16: Certificate Section 3.2. Processing Rules The processing rules for an attestation path attribute are deceptively simple, until one considers all the details and bookkeeping. Upon initialization, the speaker's private key is activated for use. Private keys SHOULD be stored in cryptographic hardware, e.g., on a PCMCIA card, and activated via a software method. Expires April 2000 Lynn, Mikkelson, Seo [Page 24] Internet Draft Secure BGP October 1999 Any initializing of security functions is performed; this includes loading data uploaded from the NOC. The certificates for the speaker, its NOC, the S-BGP certification hierarchy roots (ICANN certificates), and, optionally, the configured peers are loaded. The public keys from those certificates are placed into the public key cache. Any uploaded files containing extracted AAs and certificates are validated (by verifying the signature placed into those files by the NOC) and loaded into the AA cache and public key caches, respectively. Depending on the implementation of the AA cache chosen, this action may have the side effect of pre-building a routing table without any Adj-RIB-Ins. IPsec SAs are negotiated for each peering session. Additional support, described in the sections to follow and the Appendix B, is recommended to help manage the incremental deployment of S-BGP. 3.2.1. Overview of Certificate, AA, and CRLs Processing/Verification When an UPDATE message containing an attestation path attribute is received its contents is validated. Any validation failures are auditable events. (See section 7, Auditing, of [RFC2401].) Certificate Processing If any Certificates are present, their signature should be verified by checking the signature using the public key associated with the issuer specified in the certificate. Any Certificate that cannot be authenticated MUST be ignored. The public key in a verified certificate is added to the public key cache, along with its Not-Valid-Before and Not-Valid-After times. The new cache entry should be linked to the certificate used for verification so that when the certificate expires, or is revoked, entires that were verified using it can also be removed from the caches. Any verified Certificates received in an UPDATE should be forwarded to each peer, no later than the next time an UPDATE is sent to that peer. Address Attestation Processing Each AA should be validated by verifying its signature using the public key associated with the issuer specified in the AA. AA verification includes verifying that the issuer of the AA has a verified certificate containing the prefixes found in the Explicit PA part of the AA. Any AA that cannot be authenticated should be Expires April 2000 Lynn, Mikkelson, Seo [Page 25] Internet Draft Secure BGP October 1999 ignored. For each prefix in a validated AA, an entry is created in the prefix origination cache containing the originating ASes specified in the Subject part of the AA. If the R-bit is set in the Validity part, any other cache entries for the prefix should be deleted. If the R-bit is not set, the originating ASes should be added to any already cached for the prefix. The validity interval should be retained so that any expired AAs can be deleted. An AA whose Not-Valid-Before time is in the future should not be used to validate prefix advertisements. Any validated AAs received in an UPDATE should be forwarded to each peer, no later that the next time an UPDATE is sent to that peer for one of the prefixes listed in the AA. Certificate Revocation List Processing If any CRLs are present, their signature should be verified using the public key associated with the issuer specified in the CRL. Any CRL that cannot be verified MUST be ignored. The public key of each certificate identified in a verified CRL MUST be removed from the public key cache. Any other certificates, AAs, or RAs that were signed using the private key associated with a revoked certificate MUST also be deleted, recursively. This may result in peers or ASes (no longer valid certificates), or prefixes (due to no longer valid AAs) and/or routes (due to no longer valid ASes, AAs, or RAs) being removed from the RIBs and consequently withdrawals being sent. Any verified CRLs received in an UPDATE should be forwarded to each peer, no later than the next time an UPDATE is sent to that peer, and should be forwarded as soon as possible. 3.2.2. Route Attestation Processing The processing of route attestations, which are used to validate the integrity of the AS path and, optionally, other transitive path attributes, is more involved. The signatures in received RAs are verified. In order to verify an RA's signature, all the signed information (the Validity, Explicit PA, and Subject parts) must be identified. The Validity and Subject parts contain all the data needed for their verification. However, the Explicit PA part may 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 other RAs is located by successively looking for that data in the next RAs. RA validation also includes both verifying that each AS in the AS Expires April 2000 Lynn, Mikkelson, Seo [Page 26] Internet Draft Secure BGP October 1999 path has a corresponding RA, and verifying that the protected transitive information is consistent through all the RAs in the advertisement. Routes (per prefixes) that are successfully validated SHOULD be given a higher preference than routes that cannot be validated. Installation of routes that cannot be validated in the Loc-RIB is a local policy issue. Routes for which validation fails SHOULD NOT be installed in the LOC-RIB. Note: if all routes for a given prefix result in verification failures (as opposed to unable to verify), local policy MAY specify that such a route be used. 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 Issuer part contains the speaker's BGP Router ID, encoded as an IPv4 address. The Signature part contains: an AgorithmIdentifier field with the value TBD indicating DSA with the SHA-1 hash; the KeyHash field contains the most significant byte of the speaker's DSA public key ("y"); 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 concatenation of the 20-byte "r" and 20-byte "s" values generated by the DSA. Issue: can an exxisting number space be used for the Agorithm Identifier instead of creating yet another one? One candidate is based on [RFC2459] id-dsa-with-sha1 ::= { iso(1) member- body(2) us(840) x9-57 (10040) x9cm(4) 3 }. Another is based on IKE for a basis might be better: some combination of the 16-bit Authentication Method = DSS signatures (2), and the 16-bit Hash Algorithm = SHA (2)). The Validity part contains: an Not-Valid-After time that is in the future but does not exceed the Not-Valid-After time of the certificate used to sign the RA. (A new advertisement MUST be sent before the selected Not-Valid-After time.) The Not-Valid- Before time should not be greater than the the current time. Selection of the validity interval is an local policy decision. The A-bit and RASegmentLength 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 RASegmentLength field is set to 1. The A-bit is set to 0. Expires April 2000 Lynn, Mikkelson, Seo [Page 27] Internet Draft Secure BGP October 1999 If the speaker is neither originating the route nor performing aggregation, the RA is prepend it to any RAs that were received with the AS path used in the UPDATE. Its RASegmentLength field is set to 1 more than the contents of the RASegmentLength field in the last RA in the received attestation path attribute. The A-bit is set to 0. If the speaker is performing aggregation, then the RA signed by the speaker is prepended to the concatenated of the RAs associated with each of the AS paths that are being aggregated. Its RASegmentLength 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. 3.2.2.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 field, and the AS_PATH and MP_REACH_NLRI path attributes). 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 a cached AA. 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 and as input to the signature verification function. Path attributes marked as protected in the CoverageMask which are not stored 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.4.1 for discussion of validation of unknown path attributes. For the RA previous to the last RA, any implicit data is copied from the now resolved data in the last RA. The propagation of resolved data from each RA to the previous RA is repeated for all RAs in the sequence until all the RAs have been processed. If an RA indicates, by having the A-bit set, that it corresponds Expires April 2000 Lynn, Mikkelson, Seo [Page 28] Internet Draft Secure BGP October 1999 to an aggregation point, the resolved data for that RA is propagated to the last RA in each of the aggregated sub-sequences (see section 3.1.3). The individual sub-sequences are then processed as above until the all the RAs in the 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 is copied verbatim into the ExplicitPAs field. 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. 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 propageted through successive ASes, canonicalization is used to make the protected prefix information invarient between the two encodings (see 3.1.1. 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 is generated for the NLRI, as well as an AF and a SAFI, so that the NLRI is represented in the same format as if it had been in MP_REACH_NLRI path attribute (section 3.1.2, 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 MP_REACH_NLRI path attribute may be compared against a canonicalized NLRI. Propagation of Explicit Data to Previous RAs Special handling is required when propagating prefix and AS_PATH information from one RA to the previous one in an RA sequence. If the RA being verified is not the last RA in an RA sequence, all AS numbers after and including the AS number in the Subject part of the RA should be removed. Note that multiple AS numbers would be removed it the AS_PATH between the adjacent RAs actuall transited one or more non-S-BGP ASes. 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 is explicit in Expires April 2000 Lynn, Mikkelson, Seo [Page 29] Internet Draft Secure BGP October 1999 the ExplicitPAs field, so this disassembly is straightforward. Validation requires that each AS number in the AS_SET be represented in one of the sub-sequence AS_PATHs. If an AS number appears in the AS_SET but not the sub-sequence AS_PATHs, it may be the case that the aggregate includes routes advertised to the aggregator by non-S-BGP speakers; see section 3.2.5.1. Otherwise, verification fails. Validation of Signed RA Parts The Validity part contains Not-Valid-Before and Not-Valid-After times. If the verification occurs at a time after the Not-Valid- After time, validation fails. If verification occurs before the Not-Valid-Before time, validation fails, but the route should be preserved so that it may be used after the Not-Valid-Before time. If the R-bit in the Validity part is set to 1, any previously cached RAs for any of the prefixes in the advertisement should be invalidated. The Subject part of an RA describes the AS number that the route was advertised to for each hop. Validation should ensure that for each RA except the first RA in an RA sequence or an aggregated RA sub-sequence, the AS number in the Subject part of the previous RA is the same as the last AS number in the canonicalized AS_PATH for the RA being validated. 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, validation must ensure that the path attributes in the UPDATE are the same as those in the last RA. Path attributes which do not need to be canonicalized should be byte-compared against the same explicit path attributes. The AS_PATH path attribute in the UPDATE and the NLRI or MP_REACH_NLRI path attribute should be canonicalized and then byte-compared against the AS_PATH and NLRI in the explicit data, if they are present there. If any path attribute in the UPDATE does not match the same path attribute in the ExplicitPAs field of the last RA, validation fails. Policy may dictate that in this case 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 Explicit PA part of an RA is validated through the following validation steps and the signature verification. Validation of Prefixes Prefixes found in the NLRI/MP_REACH_NLRI path attribute must be validated against Address Attestations. The AAs authorize certain Expires April 2000 Lynn, Mikkelson, Seo [Page 30] Internet Draft Secure BGP October 1999 ASes to originate a route for certain prefixes. Through this section "NLRI" refers to a canonicalized NLRI. The AS which originated a prefix may be 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 which were aggregated. If not all prefixes in the NLRI were advertised by originating AS numbers, validation fails. Policy may allow use of all prefixes except those without AA validation. For each prefix in the NLRI, an AA must be present which lists the originating AS number in its Subject. Otherwise, validation fails. Again, policy may allow use of the set of prefixes for which an AA validates the originating AS. Is it desirable to be more strict with NLRI checking, and require that each RA in a sequence have a NLRI which is equal to or a subset of the NLRI associated with the previous RA, except in aggregation, where the aggregated NLRI must be equal to or a subset of the union of the sub-sequence NLRIs? Policy may specify this. If a non-S-BGP speaker originated a route or performed aggregation on a set of non-S-BGP routes, finding AS number and prefix pairs requires more steps and not all prefixes may be able to be matched to an originating AS number. See section 3.2.5.1 for discussion of this and changes necessary to the validation process. Signature Verification The signature of an RA must be verified for validation to be successful. Verification of the signature requires that each covered path attribute be placed into an Explicit PA part. If any path attributes were implicit, a new Explicit PA part must be temporarily constructed for this purpose. The length field of the Explicit PA part must be set appropriately. The path attributes should 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 be necessary because an S-BGP speaker SHOULD sort them before including the RA in an advertised route. The signature should be verified against the Validity part, the Explicit PA part, and the Subject part. They are signed and verified in one contiguous block. The public key used for verification is determined from the Issuer part of the RA and the KeyHash field of the Signature part. If signature verification fails, validation of the RA fails. Expires April 2000 Lynn, Mikkelson, Seo [Page 31] Internet Draft Secure BGP October 1999 3.2.2.2. Route Attestation Creation This section describes the steps necessary to properly create a Route Attestation. The correct NLRI which will be advertised with the route must be available so that it may be signed. If aggregation has been performed, the RA sequences for each aggregated route must be available; otherwise only the RA sequence received for the route being advertised is used. In a situation where S-BGP is partially deployed, there may not be any RA sequence, or for an aggregate, only a subset of RA sequences may exist. Several parts and fields of an RA created by a given S-BGP speaker change rarely. These include the Issuer part, the Not-Valid-Before and Not-Valid-After fields of the Validity part, and the SignatureAlgorithmID and KeyHash 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 Explicit PA part. Several other parts cannot be completely created until this has been done. After the discussion of the construction of the parts of the new RA, details of how the Explicit PA parts of the last RA in each RA sequence may be altered to reduce the size of the attestation attribute are provided. Type part The AttestationLength field of the Type part cannot be determined until the Explicit PA part has been filled with the explicit form of the protected transitive information. The Type field of the Type part can be set to 8 (RA) immediately. Issuer part The data in the Issuer part the BGP Identifier contained in the certificate whose private key will be used to sign the new RA. It uses the IPv4 encoding. Signature part The SignatureAlgorithmID and KeyHash are determined by the Certificate as well. The Length 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.c) and which are present in the UPDATE may have the corresponding bit in the coverage mask set to Expires April 2000 Lynn, Mikkelson, Seo [Page 32] Internet Draft Secure BGP October 1999 1. Unknown path attributes may also be covered if the path attribute was protected by the last RA in the received sequence. Local policy may specify particular path attributes which are not protected (including unknown attributes); the corresponding bits for these should be set to 0 in the coverage mask. 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 computed, the length in octets of the coverage mask and the length of the Signature part are known, and the Signature part (less the signature itself) is complete. Validity part The Len field of the Validity part is has the value 8 for an RA. The Not-Valid-Before and Not-Valid-After times are constrained to be within the validity interval in the certificate containing the public key that corresponds to the private key that will be used to sign the new RA. It is recommended that the Not-Valid-Before time not be in the far past. The RASequenceLength field should be computed as one more than the sum of the RASL 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. Explicit PA part For each path attribute marked as protected by the coverage mask, a copy of the path attribute MUST be placed in the Explicit PA part. This is done to handle cases where the speaker the route is being advertised to is not S-BGP capable. A non-S-BGP speaker may change path attributes but it can not insert unedited versions into the RA's ExplicitPAs field since it is not S-BGP capable. The requirement that the last RA in all attestation attributes make all path attributes explicit allows S-BGP speakers which receive the route after it has traversed non-S-BGP capable ASes to validate the RA sequence. Note that for proper validation by another S-BGP speaker, the explicit path attribute MUST be in the canonical form so that it may be compared against canonicalized implicit path attributes. Note that 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 in ascending order by prefix (not prefix length) (see section 3.2.2.1). All covered path attributes are copied into the ExplicitPAs field. S-BGP speakers SHOULD sort the path attributes by Type Code in ascending numerical order in the ExplicitPAs field. Once the explicit path attributes are copied, the Length Expires April 2000 Lynn, Mikkelson, Seo [Page 33] Internet Draft Secure BGP October 1999 field of the Explicit PA part may be set. Once the Explicit PA part is complete, the AttestationLength field of the Type part may be filled in, as the length of the Subject part is the same for all RAs. Subject part The Subject field is computed from the AS number of the peer to which the route is being advertised. It may be computed at any time, but in the case where the same route is being advertised to peers in more than one AS, it is more efficient to create all other parts of the RA first, as described here. This way, a hash may be created of all parts except the Subject, and final hashes may be computed for each RA from this initial hash and the Subject part for each RA. Signature After all parts of the RA are constructed, the signature must be computed. It covers the Validity, Explicit PA, and Subject parts, which are hashed as one contiguous block. The hash is signed, using the key specified by the Issuer part and the KeyHash field. 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 are concatenated into one sequence as described in section 3.1.2 before the new RA is prepended. Further processing of these received sequences SHOULD be done, however. Since most path attributes can be implicitly derived from the next RA in a sequence (section 3.1.1.1), UPDATE message sizes can be reduced if explicit path attributes listed in the received sequences' RAs can be removed. As the new RA must have all path attributes listed explicitly, the new RA's previous RAs may leave all path attributes implicit so long as they can be deduced from the explicit data in the new RA. The processing done here will speak only of the last RA in each received RA sequence, assuming that all S-BGP speakers have converted explicit data to implicit before prepending an RA. It is possible that this is not the case; a speaker can recursively apply the comments here to all RAs in a sequence. 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 Expires April 2000 Lynn, Mikkelson, Seo [Page 34] Internet Draft Secure BGP October 1999 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. Note that the Length field of the Explicit PA part must be altered to reflect this change. (It will be recomputed before signature verification after the implicit data is filled in.) If any path attributes other than the AS_PATH differ, then the data must be left explicit in the last RA. Note that this includes any unknown protected path attributes, as the speaker will set the Partial bit in the unknown Path Attribute Flags, so the Flags will differ between the new RA and the last RA. If the new RA does not protect a path attribute covered by the last RA, this path attribute must be left in the Explicit PA of the last RA. The AS_PATH will differ in the explicit data of the new RA and the last RA of the received RA sequence. However, if it is possible to obtain the correct AS_PATH attribute for the last RA by canonicalizing the explicit AS_PATH in the new RA for the last RA (section 3.1.1.1), the AS_PATH may be removed from the ExplicitPAs field of the last 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. Note however that the AS_PATH attribute and the canonicalized NLRI MUST remain in the Explicit PA of the last RA of each sub-sequence, because aggregation removes the information necessary to reconstruct these from the AS_PATH and NLRI in the new RA. 3.2.3. BGP Phase Processing The S-BGP Decision Process differs from the specifications of BGP-4 [draft-ietf-idr-bgp4-09.txt, RFC 1771], and route servers [RFC 1863] in the following ways. 3.2.3.1. Phase 1 Processing The degree of preference for each route received from an external peer calculated during Phase 1 SHOULD take into consideration the results of the verification of received RAs, and the presence of AAs for each prefix received. The attestation path attribute SHOULD be passed to all internal peers that are sent the advertisement. Expires April 2000 Lynn, Mikkelson, Seo [Page 35] Internet Draft Secure BGP October 1999 3.2.3.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 advertisements MAY modify this step to initiate and/or await the results of the Attestation verification step. Issue: this might be better described as pahse 1.5 3.2.3.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 informaion. The signed information includes the Subject part, which identifies the AS to which the advertisement is to be sent. An implementation MAY cache the RAs so created to reduce time required to create and sign an RA for use with subsequent advertisements to the same AS for the same protected transitive path attributes. Protected data is made explicit in all prepended RAs and whenever it either differs from the NLRI/Multiprotocol Reachable NLRI or protected transitive path attributes, or the data cannot be derived from explicit data in a subsequent 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 Explicit PA part of the first received RA SHOULD be made implicit (by removing it from the peer RA's ExplicitPAs field -- note that the Explicit part's Length field is updated accordingly but the CoverageMask field in the Signature part of that RA remains unchanged), this reducing the size of the attestations. They MAY also be removed from all subsequent RAs, up to, but not including, the point where the values differ. The only predictable changes 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 AS numbers to the first AS_SEQUENCE in the AS Path. Use of S-BGP within Confederations [RFC1965], while straight forward, is left for future study since all members of a Confederation are presumed to be part of the same management domain. Expires April 2000 Lynn, Mikkelson, Seo [Page 36] Internet Draft Secure BGP October 1999 3.2.4. 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 A. The processing specific to the attestation attribute and the changes necessary to the three BGP decision phases are described in sections 3.2.2 and 3.2.3; they are referred to in this section, which should provide an overview of all changes necessary to support S-BGP. New dimensions are added to a BGP speaker's configurations, as well as to the local policy. Some of the operational aspects of S-BGP discussed below rely on good configuration of a speaker.> 3.2.4.1. 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 properly be byte-compared against the explicit path attribute found in the RA's Explicit PA part (section 3.2.2.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 RA's explicit data as well as in the new RA's explicit data, as the speaker for which the path attribute is unknown sets the Partial bit in the Path Attribute Flags. Since this causes the path attribute to change, it will be placed in the explicit data of the last RA of the received RA sequence, as usual (section 3.2.2.2). If local policy stipulates removal of the unknown path attribute, it will again 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. As of now, only the AS_PATH and NLRI/MP_REACH_NLRI need be canonicalized for verification (section 3.2.2.1). However, if an unknown path attribute is defined 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 previous to the last RA which carry the unknown path attribute in an implicit form cannot be validated. (This presumes that canonicalization is only necessary for path attributes which may change from peer to peer.) It is not sufficient to simply allow validation to fail. Policy may allow previous RAs to be considered validated by the last RA. Since Expires April 2000 Lynn, Mikkelson, Seo [Page 37] Internet Draft Secure BGP October 1999 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 yet. 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 Explicit PA, 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. 3.2.4.2. Receive Processing After an UPDATE has been read 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 change for S-BGP is in the addition of more syntax checking of an UPDATE. The attestation attribute must be syntactically correct. The lengths of the RAs and any AAs, Certificates, or CRLs must add up to the length of the attestation attribute. The lengths of the parts of each RA must add up to the length of the RA. There must be exactly as many RAs in the RA sequence as claimed by the RASequenceLength field of the last RA, and any sub-sequences from aggregation must have the correct number of RAs as listed in the RASL of the sub-sequence's last RA, and the lengths of these sub-sequences must be equal to one less than the number in the RASL of the aggregator's RA. It should be expected that the Parital bit of the address attestation has been set by non-S-BGP speakers. Issue: What level of error reporting (error codes) is desired? 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 validation. AAs, Certificates and CRLs Expires April 2000 Lynn, Mikkelson, Seo [Page 38] Internet Draft Secure BGP October 1999 may be separated from the RA sequence at this time. They are processed as described in section 3.2.1. Note that RAs received from internal peers need not have their signature verified as that happens when an advertisement in received from an external peer. Likewise, RA validation (section 3.2.2.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. Full validation could be undertaken here, especially if the signature verification can be moved to another processor (section 4), but this is less efficient. Because of the time it takes to verify a signature, it is more efficient to delay validation if any route received would not be used immediately, for example, in cases where there is a already a preferential route. However, at a point where the S-BGP information becomes relevant, the RAs must be validated. This may be when local policy uses S-BGP information. Or it may be when the route is selected as the best route; at this point, validation must occur before the route may be used or advertise. RA validation can also happen during idle time, so that if a route validated this way is chosen, no further work need be done at that time. For example, policy may choose to use a route because is is the only route available for a certain address; in this case the RAs would not need to be validated. No S-BGP information is actually used. If another route arrives for that address, and local policy would use information carried by S-BGP for choosing a route, both routes must then be validated. Or alternately, if the best route is chosen without using S-BGP, validation of only the best route would be necessary (unless validation fails, causing another route to be preferred). 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 discarded the route because it 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 authorised. Caching of UPDATEs may noticably reducing processing overhead due to S-BGP. The Adj-RIB-In effectively requires a single-UPDATE cache per route. Caching is discussed in section 4, but building the receive cache would occur here at the same stage as placing the route into the Adj-RIB-In. Expires April 2000 Lynn, Mikkelson, Seo [Page 39] Internet Draft Secure BGP October 1999 The next part of UPDATE processing affected by S-BGP is the decision function (see section 3.2.3). 3.2.4.3. Send Processing An important aspect of the decision function which needs special attention for S-BGP is aggregation. Local policy describing when 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 that the full AS_PATH and NLRI/MP_REACH_NLRI must be present in the Explicit PA 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. If the decision function causes the S-BGP speaker to originate a route, the set of prefixes originated must be within the set of prefixes authorized by AAs in the system, either previously out-of- band via NOCs or by a new AA which must be propagated as part of the attestation attribute. Three situations may arise after a route has been chosen to be advertised. The route may be advertised to a peer in the same AS or confederation. The route may have been received from another peer, and an RA must be created and signed for the speaker's AS. Finally, 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 or confederation. However, any AAs, Certificates, or CRLs which were received in-band and have not yet been forwarded to the peer the route is being advertised to must be added to the attestation attribute, even though the RA sequence is unchanged. The second situation imposes some requirements on the code which produces an UPDATE messsage to advertise a route. As the path attributes are being built into the UPDATE, the attestation attribute must be properly created. This requires building a new RA sequence if aggregation has occurred, prepending an RA to the RA sequence, and including any necessary AAs, Certificates or CRLs. In order to properly create the new RA, all other path attributes and the NLRI must be available, as well as the AS number of the peer the route is being advertised to. If the speaker performed aggregation to create the route, the RA sequence 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 Expires April 2000 Lynn, Mikkelson, Seo [Page 40] Internet Draft Secure BGP October 1999 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.2.2. Note that a BGP implementation may require some change of the current method of building UPDATE messages to allow all protectable path attributes and the NLRI to be available while creating the attestation attribute. The creation of an RA causes 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 completed UPDATE messages until the signature is computed. After the signature is computed, a speaker may wish to cache this new RA, so that if it needs to be advertised again, the signature does not need to be computed again. 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 but the second is found in the send cache so no signature is needed, the second UPDATE message must be queued after the first, to preserve the UPDATE order. 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. Effectively 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 where one would have been sufficient without S-BGP. The NLRI must be restricted in size at the originating speaker because an UPDATE message cannot feasibly be split once protected by an RA. Note that splitting the NLRI actually increases the UPDATE size as the old, large NLRI must be made explicit in the last received RA, when it would not have been before 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. Possibly, during intialization (section 3.2.4.3) an RA was created for each set of originated routes, though it is not necessary, as RA creation is the same for this case as other cases, except that there are no previous RAs. The creation of the RA requires the same information as it does for the second situation above. Similarly, the signature computation may be delayed, and a send cache of RAs for originated routes may be created. It is possible that AAs, Certificates, or CRLs need to be added to the attestation attribute, if they are too new to have been Expires April 2000 Lynn, Mikkelson, Seo [Page 41] Internet Draft Secure BGP October 1999 distributed out-of-band. 3.2.4.4. Background Processing Some processing of local S-BGP information may occur in spare time as a background process. Since RAs, certificates, and AAs may expire, attention must be paid to keep routing information current. The NOC may upload more data to the S-BGP speaker, containing new certificates or AAs. These would be those produced enough in advance of their Not-Valid-Before times that in-band distribution is not necessary. If the NOC uploads any CRLs, they MUST be processed as described in section 3.2, which may cause deletion of certificates and route withdrawals. Locally stored certificates and AAs which have expired should be removed. Any routes which were validated using them are no longer valid; they should be either re-validated, as newer certificates or AAs may be available, or they are no longer valid and appropriate action should be taken. This might include re-computing the best route to each prefix, possibly resulting in sending withdrawals and advertising a new, validated route. Local policy may allow expired routes to remain, e.g., in cases where no other route is available or all other routes have failed validations. 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, as with expired certificates and AAs. 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 Validity part) if the certificate 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 the expired RA was prepended to an RA sequence by a speaker and the route is still in the Loc-RIB (it is the best route to the destination) 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 not happen if one of the other RAs will expire very soon. 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. However, if the session is not re-established within a configurable interval, the cached routes should be removed. Expires April 2000 Lynn, Mikkelson, Seo [Page 42] Internet Draft Secure BGP October 1999 Depending on the implementation, this may require a periodic processing of the cache. Finally, idle time may be spent verifying RAs in the, e.g., second best routes, which have not yet been verified. This could occur if they validate a route which has not been chosen for advertisement to any peers. Since the route might be advertised in the future, if RAs are verified during idle time, the computation need not occur at the time of the advertisement. (Delayed verification of RAs is discussed in section 3.2.4.2.) 3.2.5. Non-S-BGP Speakers The design of S-BGP allows for the gradual deployment of S-BGP capability throughout an internet. One of the most important requirements in a partially-deployed scenario is for every S-BGP speaker to make the protected path attributes fully explicit in the RA it generates. Doing so eliminates the possibility that would otherwise exist of having to try and resolve implicit data that could have been changed as an advertisement trasnsited a non-S-BGP capable portion of the internet. There are three cases where non-S-BGP speakers affect the operation of S-BGP. The first is the case where a non-S-BGP speaker originates a route which is not aggregated before it is advertised to an S-BGP speaker. In the second case, a non-S-BGP speaker aggregates the AS_PATH from several non-S-BGP speakers. Note that if one or all of the routes have an attestation attribute, a non-S-BGP speaker may not aggregate due to the unknown path attribute (see [RFC1771]). The third case is when a non-S-BGP speaker receives a route from an S-BGP speaker and eventually an S-BGP speaker receives the route after one or more hops through non-S-BGP speakers. At this point, the attestation attribute should have the Partial bit set to 1; however, this cannot be relied upon for validation as it is not signed. These three cases impact proper validation. Local policy may specify what to do for each case not only for incomplete validation but also for how a partially-validated route may be used for route advertisements. For example, policy may allow partially-validated routes to have a higher preference in route selection, in cases where no fully-validated route is available. 3.2.5.1. Validation This section assumes that the last RA in the attestation attribute has each protected path attribute in the ExplicitPAs field, as this is required by S-BGP (section 3.2.2.2). For the first case above, no attestation attribute is present, so no Expires April 2000 Lynn, Mikkelson, Seo [Page 43] Internet Draft Secure BGP October 1999 RAs can be validated. Policy would dictate whether such a route must be disregarded. It is possible that the originating AS does have a Certificate authorizing the AS to advertise the prefixes in the NLRI, but that the AS's BGP speaker does not yet handle S-BGP. In this case, validation of the NLRI could still occur but the NLRI can only be trusted as much as the originating AS number. Also, the hops between the originating AS and the S-BGP speaker cannot be trusted. Again, policy may allow for this level of validation. The second case is very similar to the first case. However, the originating AS for each prefix cannot be determined if the first element in the AS_PATH is an AS_SET. If the first element is an AS_SEQUENCE, this case is reduced to the second case above. Since the originating AS cannot be determined, even the weak NLRI validation cannot be carried out. It would be possible to try to determine that every prefix in the NLRI could have been originated by any of the ASes authorized for that prefix in any AA covering that prefix. For the third case, all RAs can be verified, using the explicit data from the last RA. However, any changes or lack of changes to the protected path attributes cannot be verified. It may be of interest to verify that the AS_PATH has only been prepended to, that the NLRI is equal or subset to the last signed one, that the ORIGIN attribute hasn't changed, etc. Assuming that an S-BGP speaker has chosen to advertise a route with one of these cases, the next S-BGP speaker which attempts to validate the route has a more complex set of policy choices, especially with aggregates. For example, a speaker may be able to determine the originating AS for some prefixes in an aggregation due to the existence of some RA sub-sequences; then the remaining prefixes could be treated approximately as the second case above. In summary, effort can be expended in validating portions of NLRIs and AS_PATHs in this way but elements of the AS_PATH which were added by non-S-BGP speakers still cannot be trusted. Further, there is little that can be done to partially validate other path attributes, unless it is known that they cannot change when passing through non- S-BGP speakers. This will result in the introduction of several new kinds of S-BGP specific policy to allow such partially-validated routes to be used when S-BGP is only partially deployed. 3.2.5.2. Policy [This section will be supplied in a future version of this document.] Expires April 2000 Lynn, Mikkelson, Seo [Page 44] Internet Draft Secure BGP October 1999 4. Processing Optimizations There are several processing options that can be used to improve the efficiency of S-BGP. 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 by a NAP or a customer site. Use of Implicit Data Protected data is made explicit in all prepended RAs and whenever it either differs from the NLRI/Multiprotocol Reachable NLRI or protected transitive path attributes, or the data cannot be derived from explicit data in a subsequent RA. When the explicit data in an RA that is being prepended to an attestation is the same as the data in the RA that was prepended by the peer AS, it SHOULD be made implicit (by removing it from the peer AS's RA), this 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* realized by moving the signing and verifiying operations to another processor. 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, 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 this. Note that performing the SHA-1 hash in hardware might not be faster than doing the hashing in software, as passing the data to be hashed to the crypto processor takes time. Use of a hardware cryptographic processor that protects the private key(s) used to sign the hashed information provides much better secruity than techniques that hold the private key(s) in router memory. An external processor may also allow for 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 noticable perfomance improvement. RA Caching 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 Expires April 2000 Lynn, Mikkelson, Seo [Page 45] Internet Draft Secure BGP October 1999 used to validate the route each time it flaps, reducing processing overhead from S-BGP. Likewise, a flapping route being advertised by the peer requires sending multiple locally-generated RAs; in this case a send cache will reduce the number of signatures to be computed. An RA cache can also be maintained when a session is retminated, so that if the session is re-established, any routes sent to and received from that peer which have already been validated can be used without incurring S-BGP overhead again (beyond verifying that the received route is in fact the same as the cached one). 5. Certificates S-BGP uses X.509 v3 certificates consistent with the PKIX specification [RFC2459] 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]. The S-BGP architecture calls for the storage and distribution of all S-BGP related certificates in a two tier repository with the top level servers replicated at well connected points throughout the internet. Mechanisms for the communication of certificates and CRLs to one of these repositories by certificate signers, i.e., the registries (APNIC, ARIN, and RIPE) and the owners of AS numbers, is TBD. The management of an AS is responsible for maintaining the second level of the hierarchy by periodically downloading the complete certificate database (or incremental updates to it). The protocols supported by the top level repositories for bulk certificate and CRL retrieval to be used is TBD. 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: serialNumber, validity, subjectPublicKeyInfo (public key), and the following extensions: issuerAltName, subjectAltName, and (from [X509EXT]) the IP Address Block Certificate Extension, the Autonomous System Number Extension, and the Router Authorization Certificate Extension. 6. Address Attestations The owners of IP address blocks, i.e., those organizations which have been issued a certificate containing an IP Address Block Certificate Expires April 2000 Lynn, Mikkelson, Seo [Page 46] Internet Draft Secure BGP October 1999 Extension, need to generate and sign an AA that authorizes one or more ASes to advertise those address blocks. The resulting AAs should be sent to one of the top level repositories as described in the previous section. 7. Security Considerations Security is central to the design of this protocol, and these security considerations permeate the specification. 8. Acknowledgements Many individuals contributed to the design and development of S-BGP. As members of the architecture team, 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 implementation. This work was made possible by support from NSA and DARPA. 9. References [RFC2119] Bradner, S., "Key words for use in RFCs to Indicate Requirement Level", BCP 14, RFC 2119, March 1997. [DPA] Chen, E., Bates, T., "Destination Preference Attribute for BGP", draft-ietf-idr-bgp-dpa-04.txt, January 1996 [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. [JSAC] Kent, S., Lynn, C., Seo, K., "Secure Border Gateway Protocol (S-BGP)", to appear in IEEE JSAC. [MPE] Bates, T., Chandra, R., Katz, D., Rekhter, Y., "Multiprotocol Extensions for BGP-4", draft-ietf-idr-bgp4-multiprotocol-v2-03.txt, September 1999. [MPLS] Rekhter, y., Rosen, E., "Carrying Label Information in BGP-4", draft-ietf-mpls-bgp4-mpls-03.txt, September 1999. Expires April 2000 Lynn, Mikkelson, Seo [Page 47] Internet Draft Secure BGP October 1999 [Murphy] Murphy, S., "BGP Security Analysis", draft-murphy-bgp-secr-03.txt, June 1999. [NDSS00] Kent, S., Lynn, C., Mikkelson, J., Seo, K., "Secure Border Gateway Protocol (S-BGP) -- Real World Performance and Deployment Issues", to appear in the Proceedings of the Network and Distributed System Security Symposium, San Diego California, February 2000. [RFC1700] Reynolds, J., Postel, J., "Assigned Numbers", RFC 1700, October 1994. [RFC1771] Rekhter, Y., Li, T., "A Border Gateway Protocol 4 (BGP- 4)", RFC 1771, March 1995. [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 [RFC2026] Bradner, S., "The Internet Standards Process -- Revision 3", RFC 2026, BCP 00009, October 1996. [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. [RFC2459] Housley, R., Ford, W., Polk, W., Solo, D., "Internet X.509 Public Key Infrastructure Certificate and CRL Profile", RFC 2459, January 1999. [SHA-1] Federal Information Processing Standards Publication (FIPS Expires April 2000 Lynn, Mikkelson, Seo [Page 48] Internet Draft Secure BGP October 1999 PUB) 180-1, "Secure Hash Standard", U.S. Department of Commerce / National Institute of Standards and Technology, April 1995. [X509EXT] Lynn, C., "X.509 Extensions for Authorization of IP Addresses, AS Numbers, and Routers within an AS", draft- clynn-bgp-x509-auth-01.txt, October 1999. Appendices A. Example Certificates (Extensions), Hashes, Signatures This section will be provided in a subesequent version of this document when all the TDB values have been assignd. B. Policy Support There are two basic types of policy that are needed for S-BGP. The first deals with policy to be implemented specifically for S-BGP, and the second is policy related to the incomplete deployment of S-BGP throughout the internet. Much more needed here. C. Configuration S-BGP requires additional configuration information. Some of the information is specific to the incremental deployment of S-BGP in the internet, i.e., to restrict the countermeasures information from being passed to legacy systems that may not be able to handle the attestation path attribute (insufficient space to hold it all). Where to find / how to aaccess the speaker's private key Where to find the NOC's public key The name of the file(s) containing AA extracts, Certificate extracts. Per NOC, how to negotiate an IPsec transport-mode ESP security association Per peer, how to negotiate an IPsec transport-mode ESP security association Per peer, no not send attestations Expires April 2000 Lynn, Mikkelson, Seo [Page 49] Internet Draft Secure BGP October 1999 D. NOC Support S-BGP uses out-of-band distribution for Address Attestations, Certificate Revocation Lists, and Certificates. An S-BGP speaker will eventually need the certificate of each AS exit border router through which and advertisement passed on its way to the speaker, and will eventually need an Address Attestation for each prefix in one of its Adj-RIBs-In. There are two tiers in the distribution hierarchy. The first tier consists of servers at several well know and highly connected locations such as a major peering point. These servers are sent certificates and CRLs by the registries and organizations owning AS numbers. End organizations that are given ownership of IP address blocks create and sign Address Attestations that authorize their provider to advertise their address block, and send them to the servers. The second tier consists of the NOCs of the organizations that manage ASes. They transfer from the first tier servers the complete set of AAs, certificates, and CRLs (or incremental updates to the set). The NOC then validates the information received, digests it, and uploads it to their S-BGP speakers, along with the each speaker's certificate. 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 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 ownership the the AS number to the organization. (The registry sends a copy of the resulting certificate to the first tier servers.) 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 the top-level distribution points. 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 transferring ownership of the address blocks to the organization. (The registry Expires April 2000 Lynn, Mikkelson, Seo [Page 50] Internet Draft Secure BGP October 1999 sends a copy of the resulting certificate to the first tier servers.) 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 MERCHANTABILITY OR FITNESS FOR A PARTICULAR PURPOSE. Expires April 2000 Lynn, Mikkelson, Seo [Page 51] Internet Draft Secure BGP October 1999 Author's Addresses Charles Lynn BBN Technologies 10 Moulton Street Cambridge, MA 02138 USA E-mail: CLynn@BBN.Com Telephone: +1 (617) 873-3367 Joanne Mikkelson BBN Technologies 10 Moulton Street Cambridge, MA 02138 USA E-mail: JMMikkel@BBN.Com Telephone: +1 (617) 873-4598 Karen Seo BBN Technologies 10 Fawcett Street Cambridge, MA 02138 USA E-mail: KSeo@BBN.Com Telephone: +1 (617) 873-3152 Expires April 2000 Lynn, Mikkelson, Seo [Page 52]