[Docs] [txt|pdf] [Tracker] [Email] [Diff1] [Diff2] [Nits]

Versions: 00 01

Internet Engineering Task Force                             Charles Lynn
Internet Draft                                          Joanne Mikkelson
draft-clynn-s-bgp-protocol-01.txt                              Karen Seo
Expires December 2003                                   BBN Technologies
                                                               June 2003

                           Secure BGP (S-BGP)
                   draft-clynn-s-bgp-protocol-01.txt

Status of this Memo

   This document is an Internet-Draft and is in full conformance with
   all provisions of Section 10 of [RFC2026].

   Internet-Drafts are working documents of the Internet Engineering
   Task Force (IETF), its areas, and its working groups.  Note that
   other groups may also distribute working documents as
   Internet-Drafts.

   Internet-Drafts are draft documents valid for a maximum of six months
   and may be updated, replaced, or obsoleted by other documents at any
   time.  It is inappropriate to use Internet-Drafts as reference
   material or to cite them other than as "work in progress".

   The list of current Internet-Drafts can be accessed at
   http://www.ietf.org/ietf/1id-abstracts.txt

   The list of Internet-Draft Shadow Directories can be accessed at
   http://www.ietf.org/shadow.html.

   This document specifies a protocol for the Internet community, and
   requests discussion and suggestions for improvements.  Please refer
   to the current edition of the "Internet Official Protocol Standards"
   (STD 1) for the standardization state and status of this protocol.
   Distribution of this memo is unlimited.

   Copyright (C) The Internet Society (June 2003).  All Rights Reserved.


Abstract

   The Border Gateway Protocol (BGP), which is used to distribute
   routing information between autonomous systems (ASes), is a critical
   component of the Internet's routing infrastructure.  It is highly
   vulnerable to a variety of malicious attacks both in theory and in
   practice, due to the lack of a scalable means of verifying the
   authenticity and legitimacy of BGP control traffic.  This document is
   a protocol specification for Secure BGP (S-BGP), an extension to
   BGP-4.  S-BGP adheres to the principle of least privilege and uses
   countermeasures that create an authentication and authorization
   system that addresses most of the security problems associated with
   BGP.  To facilitate adoption and deployment, S-BGP is designed to
   minimize the overhead (processing, bandwidth, storage) added by its
   countermeasures and to be interoperable with the current BGP so as to


                          Lynn, Mikkelson, Seo                  [Page 1]


                               Secure BGP                      June 2003


   be incrementally deployable.


Disclaimer

   The views and specification here are those of the authors and are not
   necessarily those of their employers.  The authors and their
   employers specifically disclaim responsibility for any problems
   arising from correct or incorrect implementation or use of this
   specification.


Table of Contents

   Status of this Memo  . . . . . . . . . . . . . . . . . . . . . . .  1
   Abstract   . . . . . . . . . . . . . . . . . . . . . . . . . . . .  1
   Disclaimer   . . . . . . . . . . . . . . . . . . . . . . . . . . .  2
   Table of Contents  . . . . . . . . . . . . . . . . . . . . . . . .  2
   Table of Figures   . . . . . . . . . . . . . . . . . . . . . . . .  3

   1.  Introduction   . . . . . . . . . . . . . . . . . . . . . . . .  4
   1.1.  The Authorization and Authentication Problem   . . . . . . .  5
   1.2.  Overview of the S-BGP Architecture   . . . . . . . . . . . .  6
   1.2.1.  Public Key Infrastructure (PKI)  . . . . . . . . . . . . .  7
   1.2.1.1.  PKI for Delegation of IP Address Blocks  . . . . . . . .  7
   1.2.1.2.  PKI for Delegation of AS Numbers and Binding a Router
                                                    to an AS  . . . .  8
   1.2.1.3.  Use of the Certificates in the PKIs  . . . . . . . . . .  9
   1.2.2.  Attestations   . . . . . . . . . . . . . . . . . . . . . . 10
   1.2.3.  IPsec  . . . . . . . . . . . . . . . . . . . . . . . . . . 10
   1.3.  Overview of an S-BGP Implementation  . . . . . . . . . . . . 11

   2.  Terminology  . . . . . . . . . . . . . . . . . . . . . . . . . 15

   3.  Attestation Path Attribute   . . . . . . . . . . . . . . . . . 22
   3.1.  Attestation Path Attribute Formats   . . . . . . . . . . . . 23
   3.1.1.  Route and Address Attestations   . . . . . . . . . . . . . 23
   3.1.2.  RA Sequences and Aggregation   . . . . . . . . . . . . . . 30
   3.2.  S-BGP Processing   . . . . . . . . . . . . . . . . . . . . . 31
   3.2.1.  Route Attestation Processing   . . . . . . . . . . . . . . 32
   3.2.1.1.  Route Attestation Validation   . . . . . . . . . . . . . 34
   3.2.1.2.  Route Attestation Creation   . . . . . . . . . . . . . . 37
   3.2.2.  BGP Processing Phases  . . . . . . . . . . . . . . . . . . 41
   3.2.2.1.  Phase 1 Processing   . . . . . . . . . . . . . . . . . . 41
   3.2.2.2.  Phase 2 Processing   . . . . . . . . . . . . . . . . . . 42
   3.2.2.3.  Phase 3 Processing   . . . . . . . . . . . . . . . . . . 42
   3.2.3.  S-BGP Processing   . . . . . . . . . . . . . . . . . . . . 43
   3.2.3.1.  Receive Processing . . . . . . . . . . . . . . . . . . . 43
   3.2.3.2.  Send Processing  . . . . . . . . . . . . . . . . . . . . 44
   3.2.3.3.  Background Processing  . . . . . . . . . . . . . . . . . 46
   3.2.3.4.  Unknown Path Attributes and Canonicalization   . . . . . 47


                          Lynn, Mikkelson, Seo                  [Page 2]


                               Secure BGP                      June 2003


   3.2.4.  Interoperation with Non-S-BGP Speakers   . . . . . . . . . 48

   4.  Processing Optimizations   . . . . . . . . . . . . . . . . . . 49

   5.  Auditing and Event Reporting . . . . . . . . . . . . . . . . . 51

   6.  Infrastructure Support . . . . . . . . . . . . . . . . . . . . 51

   7.  Address Attestations   . . . . . . . . . . . . . . . . . . . . 52

   8.  IANA Considerations  . . . . . . . . . . . . . . . . . . . . . 53

   9.  Security Considerations  . . . . . . . . . . . . . . . . . . . 53

   10. Acknowledgments  . . . . . . . . . . . . . . . . . . . . . . . 53

   11. References . . . . . . . . . . . . . . . . . . . . . . . . . . 54

   Appendix A.  Example Certificates, Hashes, and Signatures  . . . . 57
   Appendix B.  Configuration . . . . . . . . . . . . . . . . . . . . 58
   Appendix C.  Policy Support  . . . . . . . . . . . . . . . . . . . 59
   Appendix D.  NOC Support . . . . . . . . . . . . . . . . . . . . . 75

   Intellectual Property Rights   . . . . . . . . . . . . . . . . . . 76
   Full Copyright Statement   . . . . . . . . . . . . . . . . . . . . 76
   Authors' Addresses   . . . . . . . . . . . . . . . . . . . . . . . 77


Table of Figures

   Figure  1:  Address Space PKI Structure  . . . . . . . . . . . . .  8
   Figure  2:  AS Custodianship and Router ID PKI . . . . . . . . . .  9
   Figure  3:  Terminology Example  . . . . . . . . . . . . . . . . . 21
   Figure  4:  Structure of an Address or Route Attestation   . . . . 24
   Figure  5:  Route and Address Attestation and Authenticator
                                                       Headers  . . . 24
   Figure  6:  Signer Part  . . . . . . . . . . . . . . . . . . . . . 25
   Figure  7:  Formats of Issuer Name Forms   . . . . . . . . . . . . 25
   Figure  8:  Signature Part   . . . . . . . . . . . . . . . . . . . 26
   Figure  9:  CoverageMask Field   . . . . . . . . . . . . . . . . . 27
   Figure 10:  Expiry Part  . . . . . . . . . . . . . . . . . . . . . 27
   Figure 11:  ExplicitPA Part  . . . . . . . . . . . . . . . . . . . 28
   Figure 12:  Prefix Encoding  . . . . . . . . . . . . . . . . . . . 28
   Figure 13:  Target Part  . . . . . . . . . . . . . . . . . . . . . 29
   Figure 14:  Aggregation Example  . . . . . . . . . . . . . . . . . 30








                          Lynn, Mikkelson, Seo                  [Page 3]


                               Secure BGP                      June 2003



1.  Introduction

   Internet routing is based on a distributed system composed of many
   routers, grouped into management domains called Autonomous Systems
   (ASes).  Routing information is exchanged between ASes in Border
   Gateway Protocol (BGP) [RFCbgp] UPDATE messages.

   This critical component of the Internet's routing infrastructure has
   proven to be highly vulnerable to a variety of attacks [Murphy], due
   to the lack of a scalable means of verifying the authenticity and
   legitimacy of BGP control traffic.

   This document provides a protocol specification for Secure BGP
   (S-BGP), an extension to BGP-4.  S-BGP adheres to the principle of
   least privilege [SALTZER] and uses countermeasures that create an
   authentication and authorization system that addresses most of the
   security problems associated with BGP.

   To facilitate adoption and deployment, S-BGP is designed to minimize
   the overhead (processing, bandwidth, storage) added by its
   countermeasures and to be interoperable with the current BGP so as to
   be incrementally deployable.

   The S-BGP architecture is described in [JSAC].  It discusses BGP
   vulnerabilities and security requirements and a high-level
   description of S-BGP's components, and how the components work
   together to address these vulnerabilities.  [Murphy] also discusses
   BGP vulnerabilities.

   [JSAC] includes a comparison of this architecture with other
   approaches that have been proposed, and an overview of performance
   and operational issues.  See also [Murphy2].

   The public key infrastructure (PKI) created to support the S-BGP
   authorization and authentication mechanisms is described in more
   detail in [DISCEX].  See also Appendix A, [X509EXT], and [X509S-BGP].

   [NDSS00] contains experimental data collected from a proof of concept
   implementation of S-BGP in the GateD (TM) BGP implementation.
   [CMS03] incorporates more recent data from the Route-Views site
   [RVO].  A reference implementation in mrtd [MRT] is available from
   the S-BGP web site [S-BGP].

   This document assumes that the reader is familiar with BGP, related
   networking technology, and general security terms and concepts.







                          Lynn, Mikkelson, Seo                  [Page 4]


                               Secure BGP                      June 2003


1.1.  The Authorization and Authentication Problem

   Security for BGP is defined by the correct operation of BGP speakers.
   This definition is based on the observation that any successful
   attack against BGP should result in other than correct operation,
   presumably yielding degraded operation.  Correct operation of BGP
   depends upon the integrity, authenticity, and timeliness of the
   routing information it distributes as well as each BGP speaker's
   processing, storing, and distribution of this information in
   accordance with both the BGP specification and with the (local,
   possibly confidential) routing policies of the BGP speaker's AS.  The
   following statements characterize the primary correct operation
   features of BGP.

   1) Each UPDATE received by a BGP speaker from a peer was sent by the
      indicated peer, was not modified en-route from the peer, and
      contains routing information no less recent than the routing
      information previously received for the indicated prefixes from
      that peer.

   2) The UPDATE was intended for receipt by the peer that received it.

   3) The peer that sent the UPDATE was authorized to act on behalf of
      its AS to advertise the routing information contained within the
      UPDATE to BGP peers in the recipient AS.

   4) The entity with the right to use an address space corresponding to
      a reachable prefix advertised in an UPDATE was given custodianship
      of that address space by a higher-level/parent entity.

   5) The originating AS was authorized, by the entity(s) with the right
      to use address space corresponding to the set of reachable
      prefixes, to advertise those prefixes.

   6) If the UPDATE indicates a withdrawn route, then the peer
      withdrawing the route was a legitimate advertiser for that route,
      prior to its withdrawal.

   7) The peer that sent the UPDATE correctly applied the BGP rules and
      its AS's routing policies in modifying, storing, and distributing
      the UPDATE, in selecting the route, and in deriving forwarding
      information from it.

   8) The BGP speaker that received the UPDATE correctly applied the BGP
      rules and its AS's routing policies in determining whether to
      accept the UPDATE.

   The countermeasures developed for S-BGP meet the first six of these
   criteria, even in the face of subversion of BGP speakers (Byzantine
   failures).  However, because the local policy features of BGP allow a
   speaker considerable latitude in determining how to process an


                          Lynn, Mikkelson, Seo                  [Page 5]


                               Secure BGP                      June 2003


   UPDATE, these countermeasures cannot meet the last two criteria,
   i.e., such attacks could be attributed to local policies not visible
   outside the AS.  To address such attacks within BGP, the semantics of
   BGP itself would have to change.  Moreover, because UPDATEs do not
   carry sequence numbers, a BGP speaker can generate an UPDATE based on
   old information, e.g., withdrawing or reasserting a route based on
   outdated information.  Thus the temporal accuracy of UPDATEs, in the
   face of Byzantine failures, is enforced only very coarsely by these
   countermeasures.


1.2.  Overview of the S-BGP Architecture

   The design of S-BGP is based on several assumptions and constraints.
   First, the countermeasures must not violate the BGP specifications,
   e.g., any additional data carried in UPDATEs must make use of defined
   extension mechanisms and the maximum (BGP) message size of 4096 bytes
   must not be exceeded.  Thus, for example, the address attestations,
   certificates, and CRLs needed to support S-BGP are transmitted out-
   of-band; and an optional, transitive, path attribute is used to carry
   in-band S-BGP countermeasures data.  A countermeasure must operate at
   a rate comparable to the information that it protects as failure to
   do so results in synchronization discrepancies that might be
   exploited.  Consequently, countermeasures protecting topology
   information needs to function at the rate of UPDATE messages while
   countermeasures related to the existence of ASes, networks, or S-BGP
   speakers can function at a slower rate.  The performance impact of
   the countermeasures must be minimal.  Finally, the countermeasures
   should scale, as the Internet continues to grow at a well-documented,
   substantial pace.  See [JSAC] for a more detailed overview of S-BGP.

   The approach adopted to securing BGP route distribution involves a
   Public Key Infrastructure (PKI), a new transitive path attribute
   containing "attestations", and the use of IPsec.  These components
   are used by an S-BGP speaker to validate the authenticity and data
   integrity of BGP UPDATEs that it receives, and to verify the identity
   and authorization of the senders.

   A Public Key Infrastructure (PKI), based on X.509 v3 certificates
   containing S-BGP private extensions [X509EXT] [X509S-BGP], is used to
   provide assurance that the AS numbers and IP address prefixes being
   advertised have been authorized for use by their respective
   custodians.  See [DISCEX] for a more detailed description of the PKI.

   A new BGP optional transitive path attribute, the Attestation Path
   Attribute (ATTEST), is used to carry digital signatures that protect
   the prefixes (NLRI or MP_REACH_NLRI), the AS Path, and, optionally,
   other transitive path attributes as a BGP UPDATE propagates between
   ASes.

   IPsec, in conjunction with a certificate issued to each BGP speaker,


                          Lynn, Mikkelson, Seo                  [Page 6]


                               Secure BGP                      June 2003


   provides authentication of BGP peers and provides data integrity for
   the TCP peering connection.  It also protects the connection from
   replay attacks, as well as attacks on the TCP connection or the in-
   transit BGP protocol messages.


1.2.1.  Public Key Infrastructure (PKI)

   S-BGP makes use of a Public Key Infrastructure (PKI), based on the
   use of X.509 v3 certificates, that supports the authentication of IP
   address block custodianship, AS number custodianship, AS
   identification, and BGP router identification and authorization to
   represent an AS.  The PKI uses three new certificate extensions to
   implement this functionality.  See [RFC3280] for a description of
   X.509 certificate and CRL formats.  The concepts and terms address
   attestation (AA) and route attestation (RA) are described and defined
   in section 1.2.2.

   An administrative framework [RFC2050] and personnel already exist to
   manage the delegation of the right to use IP address prefixes and AS
   numbers.  S-BGP builds upon this existing infrastructure to manage
   these certificates.  The PKI that must be created to support S-BGP
   will overlay the existing administrative framework, based on the
   Regional Internet Registries (RIR), ISPs, etc.


1.2.1.1.  PKI for Delegation of IP Address Blocks

   The IPAddrBlocks certificate extension binds a set of IP address
   families and prefixes to a public key.  Certificates containing this
   extension, in conjunction with address attestations, are used to
   verify that the entity with the right to use an IP address space (the
   private key holder) has authorized one or more ASes to advertise the
   address space.  The certificates are arranged into a hierarchy that
   parallels the existing IP address administrative framework.

   The IANA is the root certification authority (CA) of the PKI, and
   each RIR is a registry CA below the root.  The IANA as the S-BGP root
   CA, cross certifies the RIR's registry CA.  The third tier consists
   of ISPs, and subscribers that have obtained their address space
   assignment directly from an RIR.  Additional tier(s) represent DSPs
   or subscribers that have been assigned IP address blocks by their
   provider.  Note that only those entities that have the right to use
   an IP address block need these certificates.  Entities that are
   "loaned" a portion of their provider's address space do not need a
   certificate.  Figure 1 illustrates this certification hierarchy,
   showing the organizations that are represented at each tier.






                          Lynn, Mikkelson, Seo                  [Page 7]


                               Secure BGP                      June 2003


                                 IANA
                            All Addr blocks
                                   |
            +----------------------+-----------------------+
            |                      |                       |
     APNIC Registry          ARIN Registry     ...   RIPE Registry
    APNIC Addr blocks       ARIN Addr blocks        RIPE Addr blocks
            :                      |                       :
                                   |
           +----------+----+++-----+-----------+----+++-----+
           |          |    |||     |           |    |||     |
         AT&T       Org A  ...    MCI        ISP 1  ...   Sprint
         Addr        Addr         Addr        Addr         Addr
        block(s)   block(s)     block(s)    block(s)     block(s)
           |                       |           |            |
       ..--+--..               ..--+--..   ..--+--..    ..--+--..
           |                       |           |            |
      Subscriber B               DSP 2    Subscriber C    ISP 3
         Addr                    Addr        Addr         Addr
       block(s)                block(s)    block(s)     block(s)
                                   |                        |
                                  ...                      ...

               Figure  1:  Address Space PKI Structure


1.2.1.2.  PKI for Delegation of AS Numbers and Binding a Router to an AS

   The ASIdentifiers certificate extension binds a set of AS numbers to
   a public key.  The SBGPRouterId extension contained in certificates
   issued to S-BGP speakers, binds an AS number and the router's BGP ID
   to the speaker's public key.  Together, these two certificate
   extensions allow BGP speakers to authenticate one another, and to
   verify that a given speaker is authorized to represent a specified
   AS.  Here too, IANA is the root CA and each RIR, at the second tier,
   operates a registry CA.  The third tier consists of ISPs, DSPs, and
   subscribers.

   The second certificate extension is issued at all tiers; and the
   third at the bottom tier, to S-BGP speakers.  The bottom tier
   represents both ASes (as a management entity), and routers associated
   with a higher tier organization.  Note that only those entities that
   have the right to use an AS number, that manage S-BGP speakers, or
   that participate in an S-BGP peering session need these certificates.
   Figure 2 illustrates a simple example of the hierarchy for these two
   types of certificates, noting the organizations involved at the top
   three tiers, and the ASes and routers that populate the bottom tier.






                          Lynn, Mikkelson, Seo                  [Page 8]


                               Secure BGP                      June 2003


                                 IANA
                             All AS Numbers
                                   |
            +----------------------+-----------------------+
            |                      |                       |
     APNIC Registry          ARIN Registry     ...   RIPE Registry
    APNIC AS Numbers        ARIN AS Numbers          RIPE AS Numbers
            :                      |                       :
                                   |
          +-----------+----+++-----+------------+----+++-------+
          |           |    |||     |            |    |||       |
        AT&T        Org A  ...    MCI         ISP 1  ...    Sprint
     AS #s W,...    AS# X     AS #s Y,...   AS Numbers    AS #s Z,...
          |           |            |            |              |
      +---+---++++   ...       +---+-+++++     ...       +-----+-++++
      |       ||||             |     |||||               |       ||||
    AS# W   Routers          AS# Y  Routers            AS# Z   Routers
            in AS W                 in AS Y                    in AS Z

               Figure  2:  AS Custodianship and Router ID PKI


1.2.1.3.  Use of the Certificates in the PKI

   The certificates described above are used to enable verification of:

    * An organization's right to use a block of IP addresses
      The IPAddrBlocks certificate extension (section 1.2.1.1) is used
      to verify that an organization has the right to use a block of IP
      addresses, and, using an address attestation, to authorize one or
      more ASes to advertise them.  The signature on an address
      attestation must be verifiable using the public key in a
      certificate containing IP address block(s) that are a superset of
      the address prefixes in the address attestation.

    * An organization's right to use an AS number
      The ASIdentifiers certificate extension (section 1.2.1.2) is used
      to verify that an AS number has been assigned to the holder of a
      particular public key, e.g., an organization.  They are used to
      verify the certificates associated with an AS as a management
      entity, and the certificates of the S-BGP speakers within those
      ASes, through the AS number linkage and the usual subordinate
      certificate validation checks.

    * An AS's identity
      The ASIdentifiers certificate extension (section 1.2.1.2) may be
      used to verify the signature of an AS as a management entity on,
      e.g., S-BGP information uploaded to S-BGP speakers -- extract
      file(s) of address attestations, S-BGP speaker public keys, or
      (S-BGP related) policy.  Extract files are used to reduce the
      volume of data that needs to be present at each S-BGP speaker.


                          Lynn, Mikkelson, Seo                  [Page 9]


                               Secure BGP                      June 2003


    * A router's identity and its association with an AS
      The SBGPRouterId certificate extension (section 1.2.1.2) is used
      to verify the signature of an S-BGP speaker on a route attestation
      and, in conjunction with the ASIdentifiers extension, to make sure
      that the router is authorized to act on behalf of its AS.

    * Identity and authorization of a BGP peer
      The SBGPRouterId certificate extension (section 1.2.1.2) may be
      used by the BGP routers to authenticate each other when setting up
      IPsec protected BGP peering sessions.  Certificates without the
      private extensions used by S-BGP may also be used for this
      purpose, e.g., when a speaker's IPsec implementation cannot
      process a certificate containing the S-BGP extensions.


1.2.2.  Attestations

   "Attestations" constitute the second major component of the S-BGP
   architecture.  They constitute the core of S-BGP, and represent a
   conceptually straightforward means of achieving the critical security
   assurances described above.  It is the use of attestations, protected
   by digital signatures, that permits S-BGP to counter Byzantine
   attacks (including misconfiguration and typographic errors).
   Attestations are signed and verified using the public keys from the
   end-entity certificates of the PKI described above.  They enable each
   S-BGP speaker that receives a route advertisement to verify that each
   AS along the path has been authorized by the preceding AS to
   advertise the route, and that the originating AS has been authorized
   to advertise those prefixes by the entity with the right to use each
   IP address prefix contained in the UPDATE.

   There are two types of attestations:

    * Route attestations (RAs) - whose signer is an S-BGP speaker
      authorized to represent an AS and the target is a transit AS, or
      another AS providing third party advertisements for an AS that is
      not running BGP.  Route attestations are carried in a new BGP
      optional transitive path attribute that contains digital
      signatures protecting the transitive routing information.

    * Address attestations (AAs) - whose signer is the entity that has
      the right to use the address prefixes contained in the attestation
      and the target is one or more ASes that are authorized to
      originate routes to those prefixes, e.g., the organization's
      internet service provider(s).


1.2.3.  IPsec

   IPsec [RFC2401, RFC2407, RFC2408, RFC2409], specifically the
   encapsulating security payload (ESP) [RFC2406], is used to provide


                          Lynn, Mikkelson, Seo                 [Page 10]


                               Secure BGP                      June 2003


   BGP control traffic with data and partial sequence integrity, and
   with peer entity authentication.  Because it is implemented at the IP
   layer, IPsec protects the integrity of the TCP connections used
   between BGP speakers.  Its anti-replay mechanisms detect and reject
   replayed packets more quickly than TCP, helping to reduce the effect
   of a denial of service attack.  The IPsec anti-replay mechanisms plus
   TCP sequence numbers ensure the "no less recent" requirement for
   correct operation of BGP, relative to attacks mounted against inter-
   router links.  ESP may be used with the NULL confidentiality
   algorithm [RFC2410], i.e., the BGP control traffic will be sent as
   clear text.  If confidentiality of BGP control traffic becomes an
   issue, it will be easy to later enable the IPsec confidentiality
   mechanisms where needed, without any changes to BGP.


1.3.  Overview of an S-BGP Implementation

   S-BGP adds three databases to a router.  The originating AS database
   is derived from the address attestations, and the public key database
   is derived from the end-entity certificates of the S-BGP speakers.
   An S-BGP speaker also has a database expressing the AS's S-BGP
   related policy.

   The originating AS database specifies, for each network prefix that
   has been authorized for advertisement, the set of ASes that are
   authorized to originate an advertisement of the prefix.  The
   authorization is provided by the entity with the right to use the IP
   address prefix, and the authorization of that right can be traced
   back to IANA through one of the RIRs.  Each NOC verifies the address
   attestations and the claim of right to use an address block back to
   the IANA before generating a (signed) file that maps the prefixes to
   their respective originating AS(es).  This file can be uploaded to
   each S-BGP speaker managed by the NOC (assuming that all the NOC's
   ASes use the same verification policy).

   Each time an UPDATE is received that advertises a route to a prefix
   (NLRI or MP_REACH_NLRI), the database is consulted to verify that the
   originating AS in the UPDATE is one authorized via an AA.

      Implementation Note:
      One way that the AA lookup table may be efficiently implemented is
      by a radix trie built from the prefixes.  This trie might be part
      of a RIB.

   The public key database contains, for each S-BGP speaker or AS, the
   DSA public key(s) corresponding to the private key that some speaker
   will use to sign route attestations in UPDATE messages sent to peers
   in other ASes.  Note that there may be multiple keys for a given RA
   signer in the database due to key rollover; a key identifier is used
   to distinguish between these keys.  The NOC performs certificate
   validation for each S-BGP speaker's and AS's end-entity certificates.


                          Lynn, Mikkelson, Seo                 [Page 11]


                               Secure BGP                      June 2003


   The certificate contains the AS identifier (number) for which the
   speaker is being authorized to act, and is signed by a CA of the
   entity that has the right to use that AS number.  The validation
   process traces the right to use the AS identifier back to IANA.  A
   speaker's identity (BGP Identifier), the AS that it represents, the
   public key, and key identifier from the certificates which pass the
   validation process are placed into a (signed) file that is uploaded
   to each S-BGP speaker managed by the NOC (assuming that all the NOC's
   ASes use the same verification policy).

   Each time an UPDATE containing the ATTEST path attribute is received
   that advertises a route, it contains a signed route attestation from
   each exit speaker along the path (corresponding to the exit speaker
   prepending its AS number to the AS Path attribute).  The signature
   covers the identity of the AS(es) to which the UPDATE is being
   passed, as well as other transitive information in the UPDATE (e.g.,
   Origin, AS PATH, NLRI).  A speaker that receives an UPDATE verifies
   the signature on each RA in the ATTEST path attribute using the RA
   specified public key from the public key database.

      Implementation Note:
      One way that the public key lookup table may be efficiently
      implemented is by a radix trie built from the BGP identifiers or
      AS identifiers.

   A speaker may have a private DSA key that is used to sign route
   attestations.  Such a private key SHOULD NOT be shared with other
   speakers.  Alternatively, several speakers may use a shared private
   key, bound to the AS for which the speakers are authorized to act.
   It is RECOMMENDED that such a private key be stored in a hardware
   token so as to minimize the chance of the shared key being
   compromised.  The shared key alternative can reduce the number of
   public keys for an AS in the public key database from one per
   inter-AS S-BGP speaker to a single key.

   Each speaker contains a database with its AS's S-BGP related
   configuration and policy information.  Some parts of this information
   may be common throughout an AS, while other parts may be specific to
   the speaker, or to one of the speaker's peers, or even to particular
   remote AS(es) for which the local administration wants special
   handling.

   See Appendix B for examples of general configuration items, and
   Appendix C for examples of policy controls that a vendor might chose
   to implement.

   The BGP specification [RFCbgp] requires a speaker to retain in its
   Loc-RIB (or Adj-RIB-In) the path attributes that were received with
   each prefix.  The S-BGP ATTEST path attribute is treated like any
   other transitive path attribute in this respect; it needs to be
   retained so it can be included in UPDATE messages sent to peers.


                          Lynn, Mikkelson, Seo                 [Page 12]


                               Secure BGP                      June 2003


   An RA is used to dynamically convey authorization from one AS to the
   next along the AS path to use the advertisement as input to its route
   selection process.  In order to prevent some forms of cut and paste
   attacks, an RA, signed by the exit speaker in an AS, includes the AS
   number of the AS(es) to which the UPDATE will be sent.  If an UPDATE
   is to be sent directly to peers in multiple ASes, or indirectly via a
   route reflector at a NAP, special configuration is required to
   identify the ASes that need to be included in the target part of the
   RA (see, e.g., sign-AS in Appendix C.3.1).

   The fact that S-BGP signs transitive information in an UPDATE, and
   that the signature is carried in a path attribute, means that, in
   general, all of the other path attributes and NLRI information must
   be known before the signature can be generated.  Since the BGP
   specification suggests that the path attributes be ordered by Type
   Code, and that both the Type Code assigned to the ATTEST path
   attribute may not be the largest Type Code ever assigned to
   transitive information, and the IPv4 NLRI follow the path attributes
   in an UPDATE message, the flow of control that may have been
   implemented in the past may have to be altered in an S-BGP
   implementation.  This is analogous to the change that the
   introduction of the MP_REACH_NLRI path attribute may have
   necessitated.


   Canonical Ordering of Information

   The Digital Signature Algorithm (DSA) [DSA] provides an integrity
   service by signing a cryptographic hash (SHA-1) [SHA-1] of the
   information to be protected.  The signer hashes the information and
   signs it; the receiver hashes the information and the DSA determines
   whether or not the computed hash matches the hash that was signed.
   This means that the string of octets that the signer hashed must be
   identical to the string of octets that the receiver hashes.  If the
   octets are not identical, signature verification will fail.

   This leads to a requirement that the receiver be able to determine
   the ordering of the octets that the signer hashed.  The BGP
   specification does not require that the ordering of all transitive
   information be preserved when propagated by a BGP speaker.  For
   example, a BGP speaker is allowed to change: the order of ASes in an
   AS_SET (including removal of duplicates); the partitioning of ASes
   between adjacent AS_SEQUENCEs; the order of communities in the
   Communities [RFC1997] and Extended Communities [EXT-COMM] path
   attributes, or the ordering of prefixes in the NLRI or MP_REACH_NLRI
   path attribute.  To avoid this problem, S-BGP specifies a canonical
   ordering for several pieces of information.

   A signer MUST convert information to be advertised in an UPDATE to
   the canonical representation before computing the hash to be signed,
   and the receiver MUST convert the received information to the


                          Lynn, Mikkelson, Seo                 [Page 13]


                               Secure BGP                      June 2003


   canonical order before computing the hash required for signature
   verification.  Path attribute data in the Explicit Data part an RA
   SHOULD be in canonical order.  It is RECOMMENDED that speakers put
   the information in the path attributes and NLRI fields of an UPDATE
   in the canonical order whenever possible, as the CPU cost for all
   receivers to verify that the ordering is canonical is usually less
   than the cost to convert non-canonical information into the canonical
   order.

   Protection of Attributes whose Content Changes

   The transitive information in an UPDATE message may change as the an
   UPDATE is passed from one AS to the next.  Three examples are the AS
   PATH path attribute [RFCbgp], the community path attributes [RFC1997]
   [EXT-COMM], and the NLRI [RFCbgp] [RFC2858].  When the protected
   information changes, a receiving speaker will not be able to verify
   the signatures on previous RAs unless it has access to the
   information before the change.  E.g., when AS adds a community to a
   received community attribute, subsequent receivers need to be able to
   determine the communities that were present before the addition.

   S-BGP meets this requirement by including in each RA an area
   (ExplicitPA) where a speaker that is changing protected transitive
   information MUST store a canonicalized copy of the information as it
   was before the change.  Note that the RA where the information is
   stored is the RA that was received, not the RA added by the speaker
   making the change.  The rules for computing the hash of the protected
   information are specifically defined so as to allow this change to
   the ExplicitPA part of a received RA without invalidating the
   signature.

   Changes to the NLRI or MP_REACH_NLRI MUST also be recorded.  Whenever
   the NLRI are changed, e.g., one or more prefixes are removed, or
   prefixes are aggregated, a canonicalized copy of the original NLRI
   information MUST be placed into the ExplicitPA part of an RA.  Note
   that a consequence of this requirement is that one cannot make the
   size of an S-BGP protected UPDATE message smaller by splitting the
   received NLRI into multiple UPDATE messages.  It is the originator's
   responsibility to limit the size of the NLRI included in an UPDATE to
   allow for the addition of RAs as the UPDATE passes from AS to AS
   through the network.  The originator is the responsible agent, since
   it is the originator's networks that will be unreachable if one of
   their UPDATEs becomes too large to meet the BGP 4 KByte maximum
   packet size limit.  In particular, if an ISP knows that some prefixes
   that it originates are multihomed to other ASes, a conservative
   strategy would be to place those prefixes into separate UPDATE
   message(s).  See. e.g., max-origin in Appendix C.4.3.

   In other cases, e.g., the AS PATH path attribute, the change that an
   AS makes is usually predictable.  I.e., an AS inserts its AS number
   one or more times to the list of ASes in the first AS_SEQUENCE.  In


                          Lynn, Mikkelson, Seo                 [Page 14]


                               Secure BGP                      June 2003


   situations where changes to a path attribute are the predictable
   changes, there is no need to record a copy of the pre-changed
   attribute in the ExplicitPA part of an RA; i.e., doing so is
   OPTIONAL.  In the case of the AS PATH attribute, there are also
   situations where the change is not predictable, e.g., when
   aggregation has introduced an AS_SET.  When changes are made that are
   different than the predictable change, a copy of the pre-changed
   information MUST be saved in the ExplicitPA part of an RA.


   Aggregation

   BGP uses "aggregation" for multiple purposes.  It can be used to:

   1) combine more specific prefixes into a less specific prefix in
      routes that a speaker originates;
   2) reduce the number of entries in the routing table (Loc-RIB, etc.),
      and consequently to:
   3) reduce the number of entries in the (hardware) forwarding tables;
   4) reduce the number of UPDATE messages that need to be sent to peers
      and stored in their Adj-RIB-Ins;
   5) reduce the size of the information passed to peers; and
   6) hide information from ASes to which a speaker advertises routes
      that the speaker received from other AS(es).

   Aggregation in S-BGP is consistent with all but the last purpose
   (although it generally may be an AS hop after aggregation before (5)
   can be realized).  The ability to hide information is inconsistent
   with the ability to verify that the information supplied has not been
   inappropriately modified.  S-BGP sacrifices information hiding to
   achieve integrity, authorization, and authenticity.

   An S-BGP speaker that performs route aggregation places into the
   Attestation path attribute all of the RAs from the routes that it is
   aggregating, after first making explicit the protected transitive
   information in each of those routes.


2.  Terminology

   There are several terms, e.g., "last RA" and "first RA", that are
   used throughout this document which may not be intuitive, leading to
   confusion and possible misunderstanding.  Those terms are defined
   here as they will be used in this document.  The terms are ordered
   for readability instead of alphabetically.

   Keywords
      The keywords MUST, MUST NOT, REQUIRED, SHALL, SHALL NOT, SHOULD,
      SHOULD NOT, RECOMMENDED, MAY, and OPTIONAL, when they appear in
      this document, are to be interpreted as described in [RFC2119].



                          Lynn, Mikkelson, Seo                 [Page 15]


                               Secure BGP                      June 2003


   Protected Transitive Information
      The transitive routing information that S-BGP protects using
      digital signatures.  The term includes both the address prefixes
      in either the NLRI field or the MP_REACH_NLRI path attribute, as
      well as a configurable set of other path attributes that contain
      information distributed beyond a single AS hop.  Examples of the
      latter are the Origin and Community path attributes.

   Certification Authority (CA)
      An entity that issues digital certificates (especially X.509
      certificates) and vouches for the binding between the data items
      in a certificate.  [RFC2828]

   Certificate
      A certificate document in the form of a digital data object (a
      data object used by a computer) that contains a sequence of data
      items and to which is appended a computed digital signature value
      that depends on that sequence of data.  A digital certificate
      binds an identity to a public key value, and possibly to
      additional data items.  [RFC2828]

      Certificates contain several items of information, including the
      subject's public key, that are validated by a Certification
      Authority which then digitally signs the information using its
      private key.  See [RFC3280].  Certificates used with S-BGP contain
      private extensions used [X509EXT] to convey authorization to use
      IP address blocks, AS identifiers, or [X509S-BGP] to bind a BGP
      Identifier to a specific router and AS.

      Certificates containing S-BGP extensions are issued to the CAs of
      Regional Internet Registries (APNIC, ARIN, RIPE, etc.),
      organizations that have the right to use IP address blocks or
      Autonomous System numbers.  End-entity certificates containing one
      of the extensions are issued to networks, Autonomous Systems, and
      BGP speakers (routers).  Other end-entity certificates are issued
      for management purposes, e.g., authentication of the S-BGP
      certificate, CRL, and AA repositories, and for access control of
      changes to the content of a repository.

      Each NOC uploads its certificates, CRLs, and address attestations
      to one of the replicated S-BGP repositories, and subsequently
      downloads all the certificates, CRLs, and address attestations for
      local validation, processing, and distribution to S-BGP speakers.

   End Entity
      An entity that is the subject of a public key certificate and that
      is using, or is permitted and able to use, the matching private
      key only for a purpose or purposes other than signing a digital
      certificate or CRL; i.e., an entity that is not a CA.  [RFC2828]

      S-BGP end entities include networks, autonomous systems, S-BGP


                          Lynn, Mikkelson, Seo                 [Page 16]


                               Secure BGP                      June 2003


      speakers, the individual administrators and operators of an
      autonomous system, and the S-BGP repositories.  See [DISCEX].

   Certificate Extract
      A condensation of the information in a certificate to only that
      needed by an S-BGP speaker for ongoing S-BGP operation -- the
      speaker's identity (BGP Identifier), public key, key identifier,
      and AS number.  The S-BGP related certificates are downloaded from
      one of the S-BGP repositories by a NOC, verified according to
      local policy, and extracted.  The extracted certificates are
      periodically uploaded to the S-BGP speakers in the AS.  The
      extracted information MAY be signed using the NOC/AS's private
      key, so the integrity of, and authorization to use the
      information, can assured by verification of the NOC's signature
      covering the file.  Alternate mechanisms MAY be used to assure the
      integrity of the information.

   Certificate Revocation Lists (CRLs)
      A data structure that enumerates digital certificates that have
      been invalidated by their issuer prior to when they were scheduled
      to expire.  [RFC2828]

      A CRL is digitally signed by a Certification Authority using its
      private key.  See [RFC3280].

   Attestation Path Attribute (ATTEST)
      A new BGP optional transitive path attribute used to carry S-BGP
      countermeasure information.  An attestation path attribute
      consists of the standard BGP path attribute header (Flags, Type
      Code, and Length) followed by a sequence of Attestations.

   Address Attestation (AA)
      An address attestation consists of an attestation header followed
      by a sequence of five parts: Signer, Signature, Expiry,
      ExplicitPA, and Target.  An address attestation conveys
      authorization by the entity with the right to use a block of IP
      addresses (the signer) for one or more ASes (the targets) to
      originate an advertisement for the prefix(es) specified in the
      ExplicitPA part.

      Each organization that generates AAs uploads them to one of the
      replicated S-BGP repositories.

   Address Attestation Extract
      A condensation of the information in an AA to only that needed by
      an S-BGP speaker for ongoing S-BGP operation -- the set of valid
      prefixes and their authorized originating AS(es).  The AAs are
      downloaded from one of the S-BGP repositories by a NOC, verified
      according to local policy, and extracted.  The extracted AAs are
      periodically uploaded to the S-BGP speakers in the AS.  The
      extracted information MAY be signed using the NOC/AS's private


                          Lynn, Mikkelson, Seo                 [Page 17]


                               Secure BGP                      June 2003


      key, so the integrity of, and authorization to use the
      information, can assured by verification of the NOC's signature
      covering the file.  Alternate mechanisms MAY be used to assure the
      integrity of the information.

   Signer (Part of an AA or RA)
      The Signer part contains information that identifies the entity
      that signed the attestation so that the entity's public key can be
      found to verify the signature.  An signer is usually identified by
      an IP v4 or v6 address, but may also be identified by an AS number
      or a DNS name.

   Signature (Part of an AA or RA)
      The Signature part identifies the digital hash function and
      signature algorithm used to sign the attestation.  Also present
      are the bytes of the signature and a key identifier that specifies
      which public key belonging to the signer should be used to verify
      the signature.

      The Signature part of an RA has a bit mask identifying the path
      attributes that are protected by the digital signature.  The
      digital signature protects the Expiry, ExplicitPA, and Target
      parts of an AA or RA.

      The algorithm specified in this document, the Digital Signature
      Standard [DSS] and the Secure Hash Algorithm, revision 1 [SHA-1],
      MUST be implemented in all S-BGP speakers.

   Expiry (Part of an AA or RA)
      The Expiry part contains the date after which the attestation is
      no longer valid.

      Also present in the expiry part of an RA are the "A-bit" (used to
      indicate path aggregation) and the RASC field.

   ExplicitPA (Part of an AA or RA)
      The ExplicitPA part contains a canonicalized version of the
      protected transitive information covered by the digital signature.

   Explicit Data
      When a canonicalized copy of the protected transitive information
      is placed into the ExplicitPA part of an attestation, it is called
      explicit data.

   Implicit Data
      When the protected transitive information can be derived from
      either the UPDATE's NLRI or path attributes, or from data in a
      previous RA, it may be omitted from the ExplicitPA part of an RA.
      The omitted, redundant, information is called implicit data.  Use
      of implicit data reduces the size of an RA.



                          Lynn, Mikkelson, Seo                 [Page 18]


                               Secure BGP                      June 2003


   Target (Part of an AA or RA)
      The semantics of the Target part differs between AAs and RAs.

      In an AA, it contains the AS number(s) of the ASes that are being
      authorized by the signer of the AA to originate the prefixes in
      the prefix pseudo path attribute (see 3.1.1, part e) in the
      ExplicitPA part.

      The Target part of an RA contains the AS number of the AS (or
      ASes, e.g., when route reflectors are being used) that is being
      authorized by the signer (e.g., an S-BGP capable exit border
      router) to place the route into its Adj-RIB-In.

   Authenticator (of an extract file)
      An authenticator consists of at least the identity of the signer,
      the key identifier of the public key to be used in verifying the
      signature, and the signature information.  Different vendors MAY
      use alternate mechanisms for the encoding of extract files and for
      the encoding of the signature information.

      Some vendors MAY omit the authenticator, when alternate mechanisms
      provide the integrity and authenticity of the extract file
      content.

   Route Attestation (RA)
      An RA consists of an attestation header followed by a sequence of
      five parts: Signer, Signature, Expiry, ExplicitPA, and Target.  A
      route attestation is used to ensure the integrity and authenticity
      of the protected transitive information being propagated in BGP
      UPDATE messages.  An RA is prepended to the RA section of the
      attestation path attribute by an AS's S-BGP capable exit border
      router.  The RA section in an attestation path attribute contains
      an ordered sequence of one or more RA sequences.

   Generated RA
      Each S-BGP capable exit border router of an AS prepends an RA to
      the RA sequence contained within an UPDATE's attestation path
      attribute prior to propagating the UPDATE.  The prepended RA is
      referred to as the locally generated RA.

   RA Sequence
      As a BGP advertisement propagates through an internet, each S-BGP
      capable exit border router prepends a locally generated and signed
      RA to the RA section of the attestation path attribute in UPDATE
      messages sent to external peers (analogous to the prepending of an
      AS number to the AS PATH path attribute).  See Figure 3, which
      depicts three ASes and a schematic of the UPDATE message that
      would be sent by the exit border routers (N.8 and U.7).  In the
      figure, the advertisement is being propagated from right to left.
      The ordered sequence of RAs in the attestation path attribute is
      referred to as an RA sequence.


                          Lynn, Mikkelson, Seo                 [Page 19]


                               Secure BGP                      June 2003


   RA Sequence Count (RASC)
      A count of the number of (remaining) RAs in an RA sequence,
      including the RA containing the count.  It is used to
      (recursively) linearize the RAs in an aggregation tree. The
      aggregation tree is necessary to enable speakers to resolve and
      validate implicit data.  When combined with the identify of the RA
      signer, the count enables detection of the malicious removal of,
      or insertion of, RAs in an attestation path attribute.













































                          Lynn, Mikkelson, Seo                 [Page 20]


                               Secure BGP                      June 2003


                        UPDATE                       UPDATE
                Sent to AS 2 by AS 8         Sent to AS 8 by AS 5
             +--------------------------+  +--------------------------+
             | Path Attributes:         |  | Path Attributes:         |
             |   AS Path:       8,8,5   |  |   AS Path:       5       |
             |   ... (Other path attrs) |  |   ... (Other path attrs) |
             |   Attestations:          |  |   Attestations:          |
 Last RA --> |     RA:                  |  |                          |
             |       Signer:    U.0.0.7 |  |                          |
             |       Sig:       ...     |  |                          |
             |       Expiry             |  |                          |
             |         Date:    ...     |  |                          |
             |         A-bit:   0       |  |                          |
             |         RASC:    2       |  |                          |
             |       ExpPA              |  |                          |
 Explicit -> |         Prefixes:10.1/16 |  |                          |
 Data     -> |         AS Path: 8,8,5   |  |                          |
             |       Target:    AS 2    |  |                          |
 First RA -> |     RA:                  |  |     RA:                  |
             |       Signer:    N.0.0.8 |  |       Signer:    N.0.0.8 |
             |       Sig:       ...     |  |       Sig:       ...     |
             |       Expiry:            |  |       Expiry:            |
             |         Date:    ...     |  |         Date:    ...     |
             |         A-bit:   0       |  |         A-bit:   0       |
             |         RASC:    1       |  |         RASC:    1       |
             |       ExpPA:             |  |       ExpPA:             |
 Implicit -> |                          |  |         Prefixes:10.1/16 |
 Data     -> |                          |  |         AS Path: 5       |
             |       Target:    AS 8    |  |       Target:    AS 8    |
             | NLRI: 10.1/16            |  | NLRI: 10.1/16            |
             +--------------------------+  +--------------------------+
                              |                         |
                   AS 2       |          AS 8           |      AS 5
       .....................  |  .....................  |  ............
       :+-------+ +-------+:  V  :+-------+ +-------+:  V  :+-------+ :
       :|BGP Id | |BGP Id |:     :|BGP Id | |BGP Id |:     :|BGP Id | :
   <-- :|F.0.0.1| |F.0.0.3|: <-- :|U.0.0.7| |U.0.0.5|: <-- :|N.0.0.8| :
       :+-------+ +-------+:     :+-------+ +-------+:     :+-------+ :
       :...................:     :...................:     :..........:
             <-- Direction of UPDATE Propagation            Origin AS
                 ....                        +--+
                 :  :  Autonomous System     |  |  S-BGP border router
                 :..:                        +--+

                  Figure  3:  Terminology Example

   First RA (in an RA Sequence)
      The RA inserted by the Origin AS; the final RA in an RA Sequence.
      The RASC in the last RA is 1.




                          Lynn, Mikkelson, Seo                 [Page 21]


                               Secure BGP                      June 2003


   Last RA (in an RA Sequence)
      When an AS receives an advertisement, the RA immediately following
      the attestation path attribute header is called the "Last RA",
      i.e., the RA added to the attestation path attribute by the peer
      from which the UPDATE was received.  The RA designated by the term
      Last RA changes on exit from each S-BGP capable AS; the First RA
      does not.

   Previous, Current, and Next RA (in an RA Sequence)
      When processing an RA sequence, on RA at a time, the Current RA
      begins with the Last RA and ends with the First RA.  The RA
      processed immediately before the Current RA is called the Previous
      RA; in the diagram it is to the left of the Current RA.  The RA
      that will be processed next is called the Next RA.  The Next RA is
      the one that was inserted before the current RA.  In the diagram,
      the Next RA is to the right of the Current RA.

   RA Sub-Sequence
      When an S-BGP speaker performs aggregation, the received RA
      sequences from each of the UPDATEs that are being aggregated are
      concatenated into a new RA sequence representing the aggregate.
      Each individual RA sequence is called an RA sub-sequence of the
      aggregated RA sequence.

      When aggregation is performed, the received RA sequences of each
      advertisement that is to be part of the aggregate are concatenated
      before the locally generated RA is prepended.  The RASC field of
      the locally generated RA is set to one more than the number of RAs
      that were concatenated.  Equivalently, it is set to 1 plus the sum
      of the RASC fields of the first RA in each of the RA sub-sequences
      being aggregated.


3.  Attestation Path Attribute (ATTEST)

   S-BGP uses a new optional, transitive BGP path attribute to
   distribute in-band security information to BGP routers in UPDATE
   messages.  The attestation path attribute (ATTEST) contains an
   ordered list of Route Attestations.  The use of in-band security
   information makes the dynamics of the protection mechanisms match the
   dynamics of topology changes.  This is especially important when,
   e.g., a major fiber cut necessitates new peerings that do not exist
   under normal conditions.  In these extraordinary situations, the
   ATTEST path attribute MAY also contain a set of Address Attestations,
   to handle the case where an organization needs to temporarily use a
   new provider.  The ordering of the RAs in the route attestation
   section is described in sections 2 and 3.1.2.

   One route attestation is prepended to the RA sequence in the
   attestation path attribute in an UPDATE message by each S-BGP capable
   Autonomous System (AS) through which the UPDATE is propagated.  It is


                          Lynn, Mikkelson, Seo                 [Page 22]


                               Secure BGP                      June 2003


   prepended by the AS's exit border router and identifies (in the
   Target part) the AS(es) that are being authorized to use the route --
   usually the AS(es) to which the UPDATE message is being sent.  The RA
   contains a digital signature that protects both the protected
   transitive information being announced to the receiving AS(es) and
   the identity of those AS(es).  The identity of a receiving AS is
   necessary both to protect against some forms of cut and splice
   attacks and to provide explicit authorization for the speakers in the
   receiving AS to use the information in the advertisement.  One
   consequence of this requirement is that a speaker can no longer
   simply forward the contents of an UPDATE message to peers in
   different neighboring ASes unless each of those ASes has been
   included in the list of ASes in the target field of the RA. See,
   e.g., sign-AS in Appendix C.3.1.

   The capability to include multiple ASes in the Target part of an
   attestation may also be used when, e.g., the current and receiving
   ASes receive UPDATEs from a common external route reflector.

   The attestation path attribute has Type Code *IANA-TBD*.

   The BGP path attribute header is as described in [RFCbgp].  The
   following sections describe the attestation path attribute's value.


3.1.  Attestation Path Attribute Formats

   Address attestations and route attestations share a common format,
   described in section 3.1.1.  Each logically related set of fields in
   an attestation is called a "part".  An S-BGP part code is assigned to
   the section for RAs and AAs, as well as to each part of an
   attestation.


3.1.1.  Route and Address Attestations

   The parts within an attestation MUST appear in the order shown in
   Figure 4.

   Each part of an attestation starts with a four-bit Part Code field.
   Following the Part Code field is a 12-bit Length field that contains
   the length in octets of the value (remainder of the attestation
   part).  I.e., the length does not include the two octets containing
   the Part Code and Length fields.

   The parts of an address or route attestation are as follows:







                          Lynn, Mikkelson, Seo                 [Page 23]


                               Secure BGP                      June 2003


       +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
       | Object Type/Length(length = 2)|
       +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-...
       | Signer (variable length)
       +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-...
       | Signature (variable length)
       +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-...  -----
       | Expiry (length = 8 for RAs, 6 for AAs)           ^
       +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-...    |
       | ExplicitPA (variable length)                   Signed
       +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-...    |
       | Target (variable length)                         v
       +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-...  -----

          Figure  4:  Structure of an Address or Route Attestation

   a) Attestation Objects (Part Codes 8, 9, and 14):

      The Part Code is 8 for a route attestation, and 9 for an address
      attestation.  Part Code 14 is reserved for an extract file
      authenticator, if a vendor chooses to use this encoding.  The
      twelve-bit length is the length of the rest of the attestation
      (not including the Part Code and Length).

        0                   1
        0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5
       +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
       |1 0 0 0|       RALength        |   RA
       +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+

       +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
       |1 0 0 1|       AALength        |   AA
       +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+

       +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
       |1 1 1 0|  AuthenticatorLength  |   Encoding for an optional
       +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+   Extract File Authenticator

     Figure 5:  Route and Address Attestation and Authenticator Headers

   b) Signer part (Part Code 1):

      The Signer part identifies the entity which signed the
      attestation.  The public key required to verify the signature is
      in a certificate issued to this entity.  The signer can be
      described by one of four name formats: a four-octet AS number, a
      four-octet IPv4 address, a sixteen-octet IPv6 address, or a
      variable length DNS name.  DNS format names MUST NOT be terminated
      by a NIL character.  The AFI field is a two-octet field following
      the SignerLength field that indicates the format of the following
      identifier.  The values for this field are taken from the Address


                          Lynn, Mikkelson, Seo                 [Page 24]


                               Secure BGP                      June 2003


      Family Identifier number space of [IANA-AFI].  I.e., it is 1 for
      an IPv4 address, 2 for an IPv6 address, 18 for an AS number, and
      16 for a DNS name.  The SignerLength field contains two plus the
      length of the identifier in the SignerData field.

        0                   1                   2                   3
        0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1
       +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
       |0 0 0 1|      SignerLength     |              AFI              |
       +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
       | SignerData (variable length)
       +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+...

                           Figure  6:  Signer Part

      The SignerData field contains the identity of the signer encoded
      in one of the following four formats:

       +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
       |      AS Number (length 4)                                     |
       +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+

       +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
       |        IPv4 (length 4)                                        |
       +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+

       +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
       |        IPv6 (length 16)                                       |
       |                                                               |
       |                                                               |
       |                                                               |
       +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+

       +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
       |  Textual DNS Name (N octets, not NIL terminated)
       +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-...

            Figure  7:  Formats of Signer Name Forms

      Note that S-BGP encodes all AS numbers as four octet quantities,
      see [AS4Bytes].

   c) Signature part (Part Code 2):

      The Signature part contains the information necessary to verify
      the integrity of the protected transitive information associated
      with the attestation.  The signature algorithm identifier,
      SigAlgID, follows the SignatureLength field and is one octet long.
      Currently one signature algorithm is defined, DSA with the SHA-1
      hash; this algorithm is assigned an ID of 2 [IANA-SAN].



                          Lynn, Mikkelson, Seo                 [Page 25]


                               Secure BGP                      June 2003


      The next field is a one-octet KeyId used to identify which of
      multiple valid public keys for the signer was used to generate the
      signature.  For DSA, the value is the (last octet of) the
      SubjectKeyIdentifier field in the Subject Key Identifier extension
      in the signer's certificate.

      Following the KeyId is a one-octet CoverageLen field, providing
      the length in octets of the immediately following CoverageMask
      field.

      The final field in the Signature part is the signature itself,
      which for DSA consists of R (20 octets) followed by S (20 octets).

        0                   1                   2                   3
        0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1
       +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
       |0 0 1 0|    SignatureLength    |    SigAlgID   |     KeyId     |
       +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
       |  CoverageLen  | CoverageMask (variable length)
       +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
       |         SignatureBytes (40 octets for DSA signature...)       |
       |                        (20 octets of DSA R)                   |
       |                        (20 octets of DSA S)                   |
       +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+

                         Figure  8:  Signature Part

      The CoverageMask field identifies which BGP path attributes are
      protected by the signature.  Only RAs have a CoverageMask; AAs do
      not, and set the CoverageLen field to zero.  Each bit corresponds
      to a Path Attribute Type Code.  For each path attribute covered by
      the signature, the corresponding CoverageMask bit MUST be set to
      1.  The NLRI is assigned bit zero (for either the IPv4 NLRI at the
      end of an UPDATE message, or for the MP_REACH_NLRI path attribute
      (see e, ExplicitPA part, below).

      In order to allow path attributes defined in the future to be part
      of the protected transitive information, the coverage bits are
      placed in ascending order starting at the leftmost bit in the
      network byte order mask.  In the following diagram the zero bits
      identify attributes that are never protected due to their non-
      transitive usage, 1 indicates attributes that MUST always
      protected (when present), and the "?"  bits correspond to
      attributes which MAY be protected, according to local policy.
      Note that the ATTEST path attribute itself is never protected.








                          Lynn, Mikkelson, Seo                 [Page 26]


                               Secure BGP                      June 2003


        0                   1
        0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6
       +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+...
       |? ? 1 0 0 0 ? ? ? 0 0 ? 0 0 0 0 ?
       +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+...

        0: NLRI or MP_REACH_NLRI; 1: ORIGIN; 2: AS PATH;
        6: ATOMIC AGGREGATE; 7: AGGREGATOR; 8: COMMUNITIES
       11: DPA; 16: EXTENDED COMMUNITY; ... (others to be defined)

                       Figure  9:  CoverageMask Field

   d) Expiry part (Part Code 3):

      The Expiry part specifies the date after which the attestation
      should not be considered valid.  The Part Code field is four bits,
      and the following Length field is 12 bits.  Note that the length
      is always 6 for RAs (which include the A-bit and RASC fields) and
      4 for AAs (which do not).

      The first field after ExpiryLength occupies two octets and
      contains the four-digit year, followed by a one-octet field whose
      four least significant bits contain the month (1 to 12), followed
      by a one-octet field containing the day (1 to 31).  The
      attestation is not valid after the specified year, month, and day.

      The Expiry part of an RA contains in addition a two-octet field
      containing the 1-bit A-bit and 11-bit RASC sub-fields.  The RASC
      field indicates how many RAs, including the RA containing the
      field, remain in the RA sequence of which this RA is a member (see
      section 2).  The A-bit field indicates whether or not the speaker
      performed route aggregation: 1 indicates it did, and 0 indicates
      it did not.

      0                   1                   2                   3
      0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1
          +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
   Expiry |0 0 1 1|ExpiryLength(AA=4,RA=6)|    Year, e.g., 2002 = 0x7d2   |
          +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
          |   0   |Month:4|0 0 0  Day:8   |
          +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
          |A|            RASC             |(RAs only)
          +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+

                         Figure 10:  Expiry Part

   e) ExplicitPA part (Part Code 4):

      The ExplicitPA part may contain a canonicalized version of the
      protected transitive information.  The path attributes to be
      protected are specified by local policy and indicated by a bit in


                          Lynn, Mikkelson, Seo                 [Page 27]


                               Secure BGP                      June 2003


      the CoverageMask as described above.  The validation process must
      be able to find the actual values protected by the digital
      signature (to verify it) even though the values of the actual NLRI
      or path attributes may change as an UPDATE message is propagated
      from AS to AS.  Information in the ExplicitPAs field is encoded as
      standard BGP path attributes with path attribute Flags, Type Code,
      and Length (see [RFCbgp]).  The the information in the attribute
      value field is canonicalized.  The individual path attributes in
      the ExplicitPAs field (and as hashed for signature computation and
      verification) MUST be sorted by ascending path attribute Type
      Code.

        0                   1                   2                   3
        0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1
       +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
       |0 1 0 0|    ExplicitPALength   |
       +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-...
       | ExplicitPAs (variable length) -- sequence of path attributes
       +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-...

                        Figure 11:  ExplicitPA Part

      Prefixes, from either the NLRI field or from the MP_REACH_NLRI
      path attribute, are encoded in the ExplicitPAs field as an
      optional transitive path attribute with Type Code 0, as shown in
      the figure below.  The attribute value consists of a two-octet
      AddressFamilyIndicator field (see [IANA-AFI]), a one-octet SAFI
      field (see [IANA-SAFI] [RFC2858]), a one-octet maximum prefix
      length field, and one or more prefixes.  In the case of IPv4 NLRI,
      the AddressFamilyIndicator field contains 1 (IPv4) and the SAFI is
      usually 1 (unicast).  The individual prefixes MUST be sorted by
      ascending <address/mask length> (but encoded in the standard way
      -- as a one-octet bit count and the number of prefix octets
      required to hold the specified number of bits; unused bits MUST be
      zero).  Having the speaker that creates the RA sort the prefixes
      simplifies RA validation for all speakers that receive an RA.
      Since the prefix information uses path attribute Type Code 0, the
      prefixes will, when present, be the first entry in the ExplicitPAs
      field.

        0                   1                   2                   3
        0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1
       +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+...
       |1 1 0 E 0 0 0 0|  Type Code 0  |    Length     :Extended Length
       +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
       |    AddressFamilyIndicator     |     SAFI      |  MaxPrefixLen |
       +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
       |  PrefixLength |    Prefix     (other PrefixLength/Prefix pairs)
       +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+...

                        Figure 12:  Prefix Encoding


                          Lynn, Mikkelson, Seo                 [Page 28]


                               Secure BGP                      June 2003



      This canonicalized encoding is used to make the prefix information
      invariant between NLRI and MP_REACH_NLRI, since IPv4 prefixes may
      be encoded in either format, and the encoding may change as an
      UPDATE message propagates through ASes.  When canonicalizing the
      (IPv4) NLRI field, the AddressFamilyIndicator MUST be set to 1,
      and the SAFI to 1 when the IPv4 addresses are unicast, or to 2
      when the IPv4 addresses are multicast (within the 224/4 prefix).

      The maximum prefix length field, MaxPrefixLen, is zero in RAs.  In
      an AA, it indicates the maximum prefix length of any more specific
      prefix that the prefix owner is authorizing to be advertised.
      This is used to thwart an attack where a more specific prefix is
      received, e.g., from an adversary or an AS not running S-BGP.  If
      an advertisement for a more-specific is received, it is an
      auditable event and MUST be rejected.  Note that AA information is
      applied to all UPDATEs received, not just those containing an
      ATTEST path attribute.

   f) Target part (Part Code 5):

      The Target part identifies the subject of the attestation.  The
      target of an RA is the AS number of the BGP speaker(s) to which
      the UPDATE message will be sent, directly, or indirectly via a
      route reflector.  The target of an AA is a list of AS numbers of
      the ASes being authorized to originate a route to the prefixes in
      the ExplicitData part, e.g., when the organization owning the
      prefixes is multihomed to different ASes.  The length of the
      Target part is variable, and the number of AS numbers present may
      be computed by subtracting two octets from the TargetLength and
      dividing by four.  AS numbers MUST be encoded as four octet values
      not as two octets values.

      The AFI field contains 18, per [IANA-AFI], to indicate the target
      uses the AS number format.

        0                   1                   2                   3
        0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1
       +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
       |0 1 0 1|      TargetLength     |      AFI = 18 (AS number)     |
       +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
       |                           AS number                           |
       +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
       |   (possibly more AS numbers)
       +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+...

                          Figure 13:  Target Part






                          Lynn, Mikkelson, Seo                 [Page 29]


                               Secure BGP                      June 2003


3.1.2.  RA Sequences and Aggregation

   The order of RAs in the RA sequence in an ATTEST path attribute is
   fairly straightforward when there is no aggregation.  Each exit
   border speaker prepends its locally generated and signed RA to the RA
   sequence in the ATTEST path attribute before advertising the route to
   an external peer.  The RASC (RA Sequence Count) field in the Expiry
   part of the locally generated RA is set to one more than the RASC
   field of the Last RA in the received ATTEST path attribute, or to one
   in a locally originated advertisement.  The A-bit is set to 0.

   Aggregation requires that the RA sequences from each of the routes
   being aggregated be concatenated into a single RA sequence.  There
   are no ordering requirements on the concatenation operation.  Figure
   14 illustrates RA lcl concatenating two RA sequences: RA a, RA b, RA
   c; and RA z.  RA a and RA z are the Last RAs in their respective RA
   sequences.  Note that in this example, the RA sequence RA a, RA b, RA
   c is itself the result of an aggregation, however RA lcl does not
   need to be cognizant of that fact when concatenating the individual
   RA sequences.  When the aggregator's RA (RA lcl) is generated and
   prepended to the concatenated RA sequence the A-bit is set to 1 and
   the RASC field is set to one more than the sum of the RASC fields of
   the Last RAs in each of the RA sequences being concatenated (in the
   example, 1 for the lcl RA, plus 3 from RA a, plus 1 from RA z).

        RA lcl     |    RA a         RA b         RA c    |    RA z
   from aggregator | Last in seq. ----------------------> | Last in seq.
   +--------------+ +----------+ +----------+ +----------+ +----------+
   | (other data) | |          | |          | |          | |          |
   | RASC:  5     | | RASC:  3 | | RASC:  1 | | RASC:  1 | | RASC:  1 |
   | A-bit: 1     | | A-bit: 1 | | A-bit: 0 | | A-bit: 0 | | A-bit: 0 |
   +--------------+ +----------+ +----------+ +----------+ +----------+

                      Figure 14:  Aggregation Example

   An S-BGP speaker can (recursively) locate the RA sub-sequences which
   were concatenated during aggregation as follows.  When an RA with the
   A-bit set is located, say RA lcl in the figure, its RASC field
   contains the number of RAs in the aggregate associated with that RA
   (lcl): 5.  If the number is less than one, a parse error should be
   handled.  The RA sequences that were concatenated are found by
   subtracting 1 (representing the RA of the aggregator, RA lcl) from
   the working count (resulting in 4).  The RASC field of the next RA, 3
   from RA a, is used to determine the RA sequence length of a RA sub-
   sequence in the aggregation; that count is subtracted from the
   working count (resulting in 1).  If the number is less than zero, a
   parse error should be handled.  If the count is greater than zero
   there is another RA sub-sequence in the aggregation.  The number of
   RAs in the Previous RA sub-sequence, 3, is skipped to locate the Last
   RA in the Next RA sub-sequence, i.e., RA z.  Its RASC count
   determines the length of the next of the RA sub-sequences.  The


                          Lynn, Mikkelson, Seo                 [Page 30]


                               Secure BGP                      June 2003


   process is repeated until the working count reaches zero.

   This deconstruction of the RA sequences in an aggregate is used by
   S-BGP speakers to determine the correspondence between the AS numbers
   in the AS_SET created by aggregation and the individual RA sequences,
   so that the authorized originating AS and path can be validated (see
   section 3.2.2.2).


3.2.  S-BGP Processing

   Initialization of security functions is performed.

   The certificates and/or the public keys of the peers are loaded for
   use by IPsec.

   When the BGP process is initialized, the S-BGP DSA parameters are
   initialized from, e.g., a trusted S-BGP root certificate.  A working
   copy of the trusted NOC's public key should be initialized, e.g.,
   from the trusted NOC's certificate.  The validated public key
   information for the S-BGP speakers should be loaded; an
   implementation may insure the integrity and authenticity of the
   authorized public keys by using the NOC's public key to verify a
   signature of the data.  Similarly, the integrity and authenticity of
   the address attestation information used to verify the legitimacy of
   an originating AS should be verified.  Note that digital signatures
   are not required if an alternate mechanism to insure integrity and
   authenticity of the information is being used.

      Implementation Note:
      Depending on the implementation chosen for the AA cache, this
      action may have the side effect of constructing a routing table
      without any Adj-RIB-Ins.

   The private key which the speaker will use to sign route attestations
   is activated for use.  Private keys SHOULD be stored in cryptographic
   hardware, e.g., in a PCMCIA card, and activated via a software
   method.  An implementation MAY choose to check that the public key
   corresponding to the private key that will be used to sign RAs is in
   the public key file by signing, e.g., a random number, and then
   trying to verify the signature.  If the signature cannot be verified,
   the speaker's configuration needs to be corrected.

   A non-volatile cache of validated routes (containing RAs) MAY also be
   preloaded, with the routes all marked as inactive.  If the cache is
   preloaded, the integrity and authenticity of the data SHOULD be
   verified.  One way to implement the verification is to have the S-BGP
   speaker sign a hash of the data it wrote to the cache using its
   private key.

   S-BGP specific policy for the speaker, its peers, and other speakers


                          Lynn, Mikkelson, Seo                 [Page 31]


                               Secure BGP                      June 2003


   and autonomous systems can be loaded on restarts.  There SHOULD be a
   mechanism to ensure the integrity and authenticity of the configured
   policy.  One way would be for the NOC to sign it using its private
   key.

   IPsec SAs are negotiated for each peering session as they are
   created.

   Additional support, described in the sections to follow and Appendix
   C, is recommended to help manage the incremental deployment of S-BGP.


3.2.1.  Route Attestation Processing

   The processing of route attestations, which are used to validate the
   integrity of the AS path and other protected transitive information,
   consists of several steps.

   The structure and internal consistency of the ATTEST path attribute
   and the attestations that it contains needs to be checked.  If an
   error is detected, a parse error is handled.

   The signatures in received RAs are verified.  In order to verify an
   RA's signature, all the signed information (the Expiry, ExplicitPA,
   and Target parts) of the RA must be identified.  The Expiry and
   Target parts contain all the data needed for their verification.
   However, the ExplicitPA part will usually not contain all the data
   identified by the CoverageMask field in the Signature part; some data
   might be implicit.  Any implicit data in the Last RA is obtained from
   the NLRI and/or path attributes in the advertisement.  Any implicit
   data in a subsequent RA is located by looking for that data in the
   previous RA (or in the aggregator's RA when the current RA is the
   Last RA in an RA sub-sequence).  Note that the ExplicitPA's length
   field has to be adjusted to include the length of the resolved
   implicit data.

   RA validation also includes both verifying that each AS in the AS
   path has a corresponding RA, and verifying that the protected
   transitive information is consistent through all the RAs in the
   advertisement.

   Routes (per prefix) that are successfully validated SHOULD be so
   marked in the Adj-RIB-In and, per local policy, preferred over routes
   that are not protected by S-BGP mechanisms.  Use of routes that
   cannot be validated is a local policy issue; see, e.g., Appendix
   C.5.1,2,3,4.  Routes for which validation fails SHOULD NOT, per local
   policy, be candidates for the route selection process.  Note: if all
   routes for a given prefix result in verification failures (as opposed
   to being un-protected), local policy MAY specify that such a route be
   used; see, e.g., only-route in Appendix C.1.



                          Lynn, Mikkelson, Seo                 [Page 32]


                               Secure BGP                      June 2003


   Sending an Advertisement

      Whenever an advertisement is sent to an external peer, the BGP
      speaker SHOULD generate and sign an RA.  The contents of the RA is
      as follows:

      The Signer part contains either the speaker's BGP Router
      Identifier, encoded as an IPv4 address, when the speaker has its
      own key; or, when a single key is to be used by multiple speakers
      in an AS, the Signer part encodes the AS number using the AS name
      form.

      The Signature part contains: an AlgorithmIdentifier field with the
      value 2 [IANA-SAN], indicating DSA with the SHA-1 hash; the KeyId
      field contains the least significant byte of the speaker's Subject
      Public Key Identifier; the CoverageMask field is set to a mask of
      the protected transitive information that appears in the UPDATE;
      the CoverageLen field is set to the number of bytes required to
      hold the CoverageMask field; and the SignatureBytes field is set
      to the network order concatenation of the 20-byte "R" and 20-byte
      "S" values generated by the DSA.

      The Expiry part contains: an expiration date that is in the
      future.  Note that a new advertisement MUST be sent before the
      selected expiration date.  Selection of the expiration date is a
      local policy decision.  The A-bit and RASC field are set as
      follows:

         If the speaker is originating the route, there will be no
         received RAs, so the RA signed by the speaker will be the only
         RA in the attestation path attribute.  Its RASC field is set to
         1.  The A-bit is set to 0.

         If the speaker is neither originating the route nor performing
         path aggregation, the RA is prepended to the RAs that were
         received with the AS path used in the UPDATE.  Its RASC field
         is set to 1 more than the contents of the RASC field in the
         Last RA in the received attestation path attribute.  The A-bit
         is set to 0.

         If the speaker is performing path aggregation, then the RA
         signed by the speaker is prepended to the concatenation of the
         RA sequences associated with each of the routes that are being
         aggregated.  Its RASC field is set to 1 more than the sum of
         the total number of RAs in the concatenation.  The A-bit is set
         to 1.







                          Lynn, Mikkelson, Seo                 [Page 33]


                               Secure BGP                      June 2003


3.2.1.1.  Route Attestation Validation

   Several steps are necessary to validate an RA sequence.  First, the
   protected transitive information for all RAs in the sequence must be
   determined, including resolution of any implicit data.  Second, any
   canonicalization rules must be performed (this applies to the
   NLRI/MP_REACH_NLRI field, and the AS PATH path attribute).  Each part
   of the RA involved in validation must be checked.  Then the prefixes
   in the NLRI field or MP_REACH_NLRI path attribute must be validated
   against both the authorized prefixes from the RA sequence(s), and,
   for each prefix, its originating AS must be matched with cached AA
   information.  Finally, the digital signature of each RA must be
   verified.  The actions which should be taken if validation fails at
   different stages of this process are local policy decisions.

   Protected Transitive Information

      To verify a given RA, all path attributes for which the
      corresponding bit is set in the CoverageMask field are required to
      resolve implicit data as input to the signature verification
      function.  Path attributes marked as protected in the CoverageMask
      which are not in the RA's ExplicitPAs field are implicit data that
      has to be resolved.

      For the Last RA in the sequence, implicit data is located in the
      NLRI and/or path attributes parts of the UPDATE message.  That
      data must be canonicalized before it is used.  Once canonicalized,
      all data for the Last RA is explicit.  See section 3.2.3.4 for
      discussion of validation of unknown path attributes.  If data for
      a path attribute is already explicit in the Last RA, it MUST be
      compared to the unprotected data from the path attribute.

      For the subsequent RAs, any implicit data is copied from the now
      explicit data in the previous RA.  The propagation of resolved
      data from one RA to the next RA is repeated for all RAs in the
      sequence, until all the RAs have been processed.

      When processing the RA sub-sequences, any implicit data in the
      Last RA is copied from the RA corresponding to the aggregation
      point, i.e., the one with the A-bit set (see section 3.1.2).  The
      individual RA sub-sequences are then processed as above until the
      all the RAs in the RA sub-sequence have been processed.

   Canonicalization

      Path attributes are canonicalized to simplify the validation
      process.  Of the currently defined path attributes, a canonical
      form is defined only for the AS PATH and the MP_REACH_NLRI path
      attributes.  For all the other protected path attributes, their
      contents are copied verbatim into the ExplicitPAs field.



                          Lynn, Mikkelson, Seo                 [Page 34]


                               Secure BGP                      June 2003


      For the AS PATH attribute, adjacent AS_SEQUENCE segments are
      merged into a single segment (up to the standard limit of 255 ASes
      in a segment).  The ASes in an AS_SET segment are sorted in
      numerically increasing order.  Note that all AS numbers in the
      ExplicitPA part are four-octet quantities.

      Since IPv4 address prefixes may be carried in either the NLRI part
      of an UPDATE message or in the MP_REACH_NLRI path attribute, and
      can in fact be converted from one representation to the other as
      an UPDATE message is propagated through successive ASes,
      canonicalization is used to make the protected prefix information
      invariant between the two encodings (see 3.1.1, part e).

      The prefixes in the NLRI and MP_REACH_NLRI path attribute are
      sorted for canonicalization.  Canonicalization of an implicit NLRI
      requires that a path attribute header of Type Code 0 be generated
      for the NLRI, as well as an AFI and a SAFI, so that the NLRI is
      represented in the same format as if it had been in an
      MP_REACH_NLRI path attribute (section 3.1.1, part e).  An
      MP_REACH_NLRI path attribute is canonicalized by changing the
      Flags to mandatory transitive and the Type Code to 0, so that the
      prefixes in an MP_REACH_NLRI path attribute may be compared
      against a canonicalized NLRI.

   Propagation of Explicit Data to the Next RA

      Special handling is required when propagating explicit prefix and
      AS PATH information from one RA to the next one in an RA sequence.

      The AS number corresponding to the Previous RA MUST be one of the
      AS(es) in the target of the Current RA.

      The AS PATH for the Current RA is computed by removing the Last AS
      number (possibly repeated due to prepending).  The AS number
      removed MUST belong to the AS that authorized the signer of the
      Previous RA.

      Aggregations require that the AS_SET be disassembled and the AS
      PATH for each sub-sequence of RAs be determined.  The AS PATH path
      attribute for the Last RA in each sub-sequence MUST be explicit in
      the ExplicitPAs field, so this disassembly is straightforward.
      Validation requires that each AS number in the AS_SET be
      represented in one or more of the sub-sequence AS PATHs.
      Otherwise, verification fails.

   Validation of Signed RA Parts

      The Expiry part contains an expiration date.  If the verification
      occurs at a time after the expiration date, validation fails
      (subject to local policy).



                          Lynn, Mikkelson, Seo                 [Page 35]


                               Secure BGP                      June 2003


      The Target part of an RA describes the AS number(s) to which the
      route was advertised.  Validation MUST ensure that for each RA
      (except the first RA in an RA sequence or an aggregated RA sub-
      sequence, i.e., RAs for which there is no Next RA), the AS number
      of the signer is one of the AS numbers in the Target part of the
      Next RA.

      Special validation of the Last RA in a sequence must be performed
      when this Last RA has any explicit data.  Since explicit data in
      the Last RA should match the equivalent implicit data found in the
      UPDATE's path attributes and NLRI, validation MUST ensure that the
      path attributes and NLRI in the UPDATE are the same as the
      explicit data in the Last RA.

      Explicit data for a Path attribute that does not need to be
      canonicalized should be byte-compared against the corresponding
      path attribute.  The AS PATH path attribute in the UPDATE and the
      NLRI or MP_REACH_NLRI path attribute is canonicalized and then
      byte-compared against the AS PATH and NLRI in the ExplicitPA data,
      if present.  If any path attribute in the UPDATE does not match
      the corresponding path attribute in the ExplicitPAs field of the
      Last RA, validation fails.  Policy may dictate that in the case of
      failure the signed, explicit version of the path attribute be
      used, if the signature verification succeeds.

      These steps of verification may be carried out before or while
      finding and canonicalizing implicit data.  The ExplicitPA part of
      an RA is validated through the following validation steps and
      signature verification.

   Validation of Prefixes

      Prefixes found in the NLRI or MP_REACH_NLRI path attribute MUST be
      validated against Address Attestation information.  The AAs
      specify the ASes authorized to originate a route for a prefix and
      the maximum length of a prefix.  Throughout this section "NLRI"
      refers to a canonicalized NLRI.

      The AS which originated a prefix is determined from the RA
      sequence.  If no aggregation has occurred, the First RA in the
      sequence will contain one AS number.  This AS number is used to
      validate all the prefixes in the NLRI.  If aggregation has
      occurred, the First RA of each RA sub-sequence will provide the
      originating AS number and the set of prefixes that it originated.

      If not all prefixes in the NLRI were advertised by at least one of
      the originating AS numbers, validation (for those prefixes) fails;
      this is an auditable event.  Policy may allow use of all prefixes
      except those failing AA validation.  For each prefix in the NLRI,
      an AA must be present which lists the originating AS number in its
      Target, and the prefix length must not exceed the length specified


                          Lynn, Mikkelson, Seo                 [Page 36]


                               Secure BGP                      June 2003


      by MaxPrefixLen.  Otherwise, validation fails; failure is an
      auditable event.  Again, policy may allow use of the sub-set of
      prefixes for which AA validation is successful.

   Signature Verification

      The signature of an RA MUST be verified.  Verification of the
      signature requires that each protected path attribute be placed
      into the ExplicitPA part.  If any path attributes were implicit, a
      new ExplicitPA part must be temporarily constructed for this
      purpose.  Note that this construction is logical and does not
      specify how it is affected by an implementation.  The length field
      of the ExplicitPA part must be set to include all the (temporarily
      constructed) explicit data.  The path attributes MUST be sorted in
      the ExplicitPAs field by the path attribute Type Code, in
      increasing numerical order.  Note that the canonicalized NLRI will
      be first, with Type Code 0.  If no implicit data is used, sorting
      should not necessary because an S-BGP speaker MUST sort them when
      it generated the RA it advertised.  The signature is verified over
      the Expiry part, the constructed ExplicitPA part, and the Target
      part.  They are hashed as a logically contiguous block.  The
      public key used for verification is determined from the name in
      the Signer part of the RA and the KeyId field in the Signature
      part.  If signature verification fails, possibly because the
      required key is not in the public key database, validation of the
      RA fails; this is an auditable event.  Failure because the
      required key is missing from the database MAY be an indication to
      the NOC to look for new public keys.


3.2.1.2.  Route Attestation Creation

   This section describes the steps necessary to create a Route
   Attestation.  The NLRI which will be advertised with the route must
   be available so that it can be signed.  If aggregation has been
   performed, the RA sequences for each aggregated route must be
   available and the ExplicitPA part of the Last RA in each RA sub
   sequence MUST have all data explicit.  When route aggregation is not
   being performed only the RA sequence received for the route being
   advertised is needed.

      Implementation Note:
      Several parts and fields of an RA created by a given S-BGP speaker
      change slowly.  These include the Signer part, the expiration date
      fields of the Expiry part, and the SignatureAlgorithmID and KeyId
      fields of the Signature part.  An S-BGP speaker MAY choose to
      initialize these values at the initialization of the BGP process,
      and then update them as needed.

   The most involved step of creating an RA is determining the
   CoverageMask and building the ExplicitPA part.  The signature part


                          Lynn, Mikkelson, Seo                 [Page 37]


                               Secure BGP                      June 2003


   cannot be completed until this has been done.  After the discussion
   of the construction of the parts of the new RA, details of how the
   ExplicitPA parts of the Next (or subsequent) RA(s) in each RA
   sequence may be altered to reduce the size of the attestation
   attribute are provided.

   Attestation Object Type
      The Part Code in the Attestation Object Type field is set to 8
      (RA).  The value of the AttestationLength field cannot be
      determined until the ExplicitPA part has been (logically)
      constructed with the explicit form of the protected transitive
      information.

   Signer part

      The signer of an RA is an S-BGP speaker.  It is identified either
      by the speaker's BGP Identifier (when the speaker signs using its
      own DSA key), or by the number of the AS that authorized the
      speaker to act as its agent (when a single DSA key is used by
      multiple speakers).  A BGP Identifier is encoded using the IPv4
      name form; an AS number is encoded using the four-octet AS number
      name form.

      Note: One reason to have a single key pair used by multiple
            speakers is to allow the rapid deployment of new S-BGP
            speakers in an AS (the key can be distributed through the
            S-BGP Repositories and be globally available before a new
            router is deployed).  One reason to use per-speaker keys is
            to reduce the impact of a key compromise.  One can install a
            new router and have it use a shared key, then switch to a
            per-speaker key after enough time has elapsed for it to be
            propagated through the S-BGP repositories to all AS's S-BGP
            speakers.

   Signature part

      The SignatureAlgorithmID and KeyId are determined by the
      Certificate as well.  The SignatureLength field and CoverageLen
      field of the Signature part are computed after the coverage mask
      has been determined.

      The coverage mask is computed using information about which path
      attributes are being placed in the UPDATE message, which path
      attributes were protected by the RA sequence(s) from the route(s)
      being covered, and policy.  Only the path attributes which S-BGP
      may protect (see section 3.1.1, part c) and which are present in
      the UPDATE may have the corresponding bit in the coverage mask set
      to 1.  Unknown path attributes may also be covered if the path
      attribute was protected by the Last RA in the received RA
      sequence.  Local policy may specify particular path attributes
      that are not protected (including unknown attributes) when


                          Lynn, Mikkelson, Seo                 [Page 38]


                               Secure BGP                      June 2003


      originating an UPDATE; the corresponding bits for these should be
      set to 0 in the coverage mask; see, e.g., send-explicit in
      Appendix C.5.5.  Policy may specify not protecting a path
      attribute unless it was protected in a received RA.

      Once the bits of the coverage mask have been specified, the length
      of the coverage mask, in octets, and the length of the Signature
      part are known, and the Signature part (less the signature itself)
      is complete.

   Expiry part

      The Len field of the Expiry part has the value 6 for an RA.  The
      expiration date is set per local policy.  Operational experience
      will provide guidance in selecting a good value, e.g., N days in
      the future.  The smaller the value, the more frequently an
      advertisement will be required to simply extend the validity
      period.

      The RASC field should be computed as one more than the sum of the
      RASC fields of the set of RA sequences which will be placed before
      the new RA in the attestation attribute, as described in section
      3.1.2.  If aggregation has been performed by this speaker, the
      A-bit is set to 1, else it is set to 0.

   ExplicitPA part

      For each path attribute marked as protected by the coverage mask,
      a (logical) copy of the path attribute is placed in the ExplicitPA
      part so that the correct signature can be computed.

      The explicit path attribute data MUST be in the canonical form so
      that it can be verified by another S-BGP speaker, including
      comparison against canonicalized implicit path attributes.  This
      means that the NLRI/MP_REACH_NLRI are canonicalized to a path
      attribute with Type Code of 0 and that the prefixes MUST be sorted
      in ascending order by prefix/prefix length (not the prefix
      length/prefix encoding used for prefixes) (see section 3.2.1.2).
      All protected path attributes are hashed as part of the
      ExplicitPAs field.  S-BGP speakers MUST sort the path attributes
      by Type Code in ascending numerical order in the ExplicitPAs
      field.  Once the explicit path attributes are identified, the
      Length field of the ExplicitPA part may be set.  Generally, the
      explicit data will subsequently be removed (made implicit) after
      signature generation to reduce the size of UPDATEs sent to peers;
      see, e.g., C.5.5,6.

   Target part

      The Target field is computed from the AS number(s) of the peer(s)
      to which the route is being advertised (or of the next forwarding


                          Lynn, Mikkelson, Seo                 [Page 39]


                               Secure BGP                      June 2003


      hop peers in the case of external route reflection).  See, e.g.,
      sign-AS in C.3.1.

         Implementation Note:
         When the target contains a single AS number and the UPDATE will
         be sent to peers in multiple ASes, it can be more efficient to
         create the Expiry and ExplicitPA parts of the RA first, as
         described here.  This way, a common hash may be computed that
         excludes the Target, and final individual hashes may then be
         computed for each RA from the common hash and the Target part
         for each RA.

   Signature

      After all parts of the RA are constructed, the signature can be
      computed.  It covers the Expiry, ExplicitPA, and Target parts,
      which are hashed as one contiguous block.  The hash is signed,
      using the key specified by the Signer part and the KeyId field of
      the Signature part.  The resulting signature is copied into the
      Signature field of the Signature part.

   Explicit and Implicit Data in Received RAs

      After the new RA has been constructed, the new RA is prepended to
      the received RA sequence to produce the RA sequence which is
      placed in the attestation attribute.  If the local speaker has
      performed aggregation, the received RA sequences for each
      aggregated route (in which the Last RAs have Explicit Data for at
      least the NLRI and AS PATH) are concatenated into one sequence as
      described in section 3.1.2 before the locally generated RA is
      prepended.

   Further processing of these received sequences SHOULD be done,
   however.  Since most path attributes can be implicitly derived from
   the previous RA in a sequence (section 3.2.1.1), UPDATE message sizes
   can be reduced if explicit path attributes listed in the received
   sequences' RAs can be removed.  Explicit data can be removed from the
   Last RA when the data can be deduced from the explicit data in the
   newly generated RA.  The processing done here will speak only of the
   Last RA in each received RA sequence, assuming that other ASes also
   have converted explicit data to implicit whenever possible before
   prepending their locally generated RA.  It is possible that this is
   not the case; a speaker may recursively apply the processing here to
   all RAs in an RA sequence; see, e.g., C.5.5,6 and C.6.4.

   If the S-BGP speaker creating the new RA did not perform aggregation,
   there is only one received RA sequence.  The speaker may compare each
   explicit path attribute in the Last RA of this sequence against the
   explicit path attributes in the new RA.  If a given path attribute is
   identical, including the path attribute Flags, then this path
   attribute MAY be removed from the ExplicitPAs field of the Last RA.


                          Lynn, Mikkelson, Seo                 [Page 40]


                               Secure BGP                      June 2003


   The ExplicitPA's Length field in the Last RA must be altered to
   reflect the removal.

      Implementation Note:
      More efficient comparison of transitive path attributes in an
      UPDATE to the corresponding ones of the Last received RA maybe
      achieved, at the cost of more memory, by making all covered path
      attributes in the Last RA explicit, or at least being able to
      locate the canonicalized path attributes that were received -- the
      path attributes MUST be saved per the BGP specification.

   If any path attributes other than those with predictable changes,
   e.g., the AS PATH, differ, then the data must be left explicit in the
   Last received RA.  Any unknown protected path attributes will be
   retained as explicit data as the speaker will set the Partial bit in
   the unknown path attribute Flags, thus creating a difference between
   the new RA and the Last received RA.  If the new RA does not protect
   a path attribute covered by the Last RA, this path attribute must be
   left in the ExplicitPA of the Last RA.

   The AS PATH as computed for the explicit data of the new RA will
   differ from the Last received RA.  However, when it is possible to
   compute the correct AS PATH attribute for the Last RA (by simply
   removing the Last AS number from the AS PATH sequence) (section
   3.2.1.1), the explicit AS PATH entry MAY be removed from the
   ExplicitPAs field of the Last received RA.

   If the S-BGP speaker creating the new RA has performed aggregation,
   the same process may be followed for the Last RA of each received RA
   sequence in the aggregate.  However the AS PATH attribute and the
   canonicalized NLRI MUST appear in the ExplicitPA of the Last RA of
   each RA sub-sequence, because aggregation removes the information
   necessary to reconstruct that information from the AS PATH and NLRI
   in the new RA.


3.2.2.  BGP Processing Phases

   The S-BGP Decision Process differs from the specifications of BGP-4
   [RFCbgp], and route servers [RFC1863] in the following ways.


3.2.2.1.  Phase 1 Processing

   The degree of preference for each route received from an external
   peer calculated during Phase 1 MAY take into consideration the
   results of the verification of received RAs, and/or the presence of
   AA information for each advertised prefix.

   The attestation path attribute MUST be passed to all internal peers
   that are sent an advertisement.


                          Lynn, Mikkelson, Seo                 [Page 41]


                               Secure BGP                      June 2003



3.2.2.2.  Phase 2 Processing

   In general, the Phase 2 installation of the best route for each
   distinct prefix in the appropriate Loc-RIB is unchanged.  However, an
   implementation that performs either asynchronous or on-demand
   verification of attestations (or their signatures) MAY modify this
   step to initiate and/or await the results of the attestation
   verification step.


3.2.2.3.  Phase 3 Processing

   A new step is added to Phase 3.  Before disseminating routes in the
   Loc-RIB to each external peer, the speaker SHOULD include a signed RA
   that contains the protected transitive information.  As an aid to
   incremental deployment, a speaker MUST support a per-peer
   configuration capability to not send an Attestation Path Attribute to
   a peer; see, e.g., send-RA in C.2.3.

      Implementation Note:
      An implementation MAY cache the RAs so created to reduce time
      required to create and sign an RA for use with subsequent
      advertisements of the same route to the same peer; see, e.g.,
      out-cache-depth, C.4.7.

   Protected data is made explicit in a prepended RA and whenever it
   either differs from the NLRI/MP_REACH_NLRI or protected transitive
   path attributes, or the data cannot be derived from explicit data in
   a previous RA.  The AS PATH MUST be included in the CoverageMask
   filed.

   When prepending the created or cached RA to the (possibly empty) set
   of RAs in the received attestation attribute, any protected path
   attributes that are either identical or predictable to the value in
   the ExplicitPA part of the Last received RA SHOULD be made implicit
   (by removing it from the peer RA's ExplicitPAs field and adjusting
   the ExplicitPA part's Length field accordingly), thus reducing the
   size of the attestations; see, e.g., c.5.5,6.  They MAY also be
   removed from all subsequent RAs, up to, but not including, the point
   where the values differ.

   The only predictable change in path attributes at the current time is
   for the AS PATH attribute, where a predictable change is defined to
   be the simple addition of the Last AS numbers to the last AS_SEQUENCE
   in the AS path.

   Use of S-BGP within Confederations [RFC1965], while straight forward
   since all members of a Confederation are presumed to be part of the
   same management domain, are outside the scope of this specification.



                          Lynn, Mikkelson, Seo                 [Page 42]


                               Secure BGP                      June 2003



3.2.3.  S-BGP Processing

   The use of S-BGP and the attestation attribute affects processing and
   sending of UPDATEs as well as the routing policy and decision
   functions, including choice of routes to use and advertise.  An
   example of additions to local policies appears in Appendix C.  The
   processing specific to the attestation attribute and the changes
   necessary to the three BGP decision phases are described in sections
   3.1.1 and 3.1.2; they are referred to in this section, which presents
   an overview of all changes necessary to support S-BGP.


3.2.3.1.  Receive Processing

   After an UPDATE has been received by an S-BGP speaker, it must
   perform all of the usual BGP processing, with the addition of S-BGP
   processing in certain places.

   The first S-BGP change is in the addition of more syntax and
   consistency checking of an UPDATE message.  The attestation attribute
   must be syntactically correct.  The lengths of the attestations must
   add up to the length of the attestation path attribute.  The lengths
   of the parts of each attestation must add up to the length of the
   attestation.  There must be exactly as many remaining RAs in the RA
   sequence as claimed by the RASC field of the each RA, any RA sub-
   sequences from aggregation must have the correct number of RAs as
   specified in the RASC of the RA sub-sequence's Last RA, and the
   lengths of these RA sub-sequences must be equal to one less than the
   number in the RASC of the aggregator's RA.

   After syntax checking, the speaker must ensure that any necessary
   implicit data from the UPDATE is available.  Validation need not
   occur at this stage (including steps to ensure that implicit and
   explicit data is the same), but the implicit data must be available
   at the time of validation.  It is sufficient that the RAs are stored
   in such a way that the storage of the other path attributes from the
   same UPDATE is available at the time of validation.

   Note that RAs received from internal peers MAY be configured to not
   have their signatures verified as that happens when an advertisement
   is received from an external peer.

   Likewise, RA validation (section 3.2.1.1) may occur at another time.
   It is also not necessary to perform all steps of validation at once.
   After syntax checking and preservation of potentially implicit path
   attributes, the S-BGP speaker may return to the usual UPDATE
   processing.  Or, it may do all validation except for signature
   verification, as the latter requires far more computation, at least
   when performed in software.  Full validation could be undertaken
   here, especially if the signature verification can be moved to


                          Lynn, Mikkelson, Seo                 [Page 43]


                               Secure BGP                      June 2003


   another processor (section 4), but this may be less efficient when a
   flood of UPDATEs is received.

   Because of the time it takes to verify a signature in software, it
   may be more efficient to delay signature validation when a received
   route is not selected as the best route to one of the prefixes, i.e.,
   in cases where there is a already a more preferred route.  The
   reduction in signature verification operations can be significant,
   especially when a speaker has a large number of external peers.
   However, when the S-BGP information becomes relevant for route
   selection, the RAs must be validated.  This may be when the route is
   selected as the best route to some prefix; validation must then occur
   before the route may be used (placed into the Loc-RIB) or
   subsequently advertised (placed into an Adj-RIB-Out).  RA validation
   can also be scheduled during idle time, so that if a route validated
   this way is later selected as the best route, the validation may
   already have been completed.  See, e.g., verify-RA in C.4.1.

   Policy may choose to use a route because it is the only route
   available for a certain prefix; in this case the RAs would not need
   to be validated; see, e.g., only-route in C.5.1,2,3 and C.1.  When
   another route arrives for that prefix, and local policy would use
   information carried in the RAs to selecting a route, both routes must
   then be validated.  Or alternately, if the best route is chosen
   without using RA information, only validation of the best route would
   be necessary (unless validation fails, causing another route to be
   selected).

   Note that no S-BGP changes are necessary to validate route
   withdrawals.  Since withdrawals cause the route to be removed from
   the Adj-RIB-In, either the S-BGP speaker has already removed the
   route because its validation failed (or the route was never
   advertised), so the withdrawal has no effect, or validation has
   succeeded, so the peer withdrawing the route has previously
   advertised the route, and the withdrawal is authorized.

   Caching of more than the most recently received route for a prefix
   can reduce processing computational overhead due to S-BGP, at the
   cost of more memory.  The BGP specification requires retention of the
   most recent UPDATE per peer per prefix in the Adj-RIB-In.  Additional
   caching, discussed in section 4, would occur at this point in
   processing.

   The next part of UPDATE processing affected by S-BGP is the decision
   function (see section 3.2.2).


3.2.3.2.  Send Processing

   An important aspect of the decision function which needs special
   attention for S-BGP is aggregation.  Local policy describing when


                          Lynn, Mikkelson, Seo                 [Page 44]


                               Secure BGP                      June 2003


   aggregation should be performed must take into account the fact that
   the UPDATE message size can increase quite dramatically when S-BGP
   protected routes are aggregated, as the attestation attribute for the
   aggregated route must include all RAs from each contributing route,
   and the full AS PATH and NLRI/MP_REACH_NLRI must be present in the
   ExplicitPA part of the Last RA for each received RA sequence.  A
   configuration parameter for the maximum aggregated attestation
   attribute size must be introduced and taken into consideration when
   applying aggregation policies.  Otherwise, an aggregation may force
   the UPDATE size past the maximum of 4096 octets.

   Three situations may arise after a route has been selected use and is
   to be advertised.  The route may be advertised to a peer in the same
   AS.  The route may have been received from an external peer, and an
   RA must be created and signed by the speaker.  Or the speaker's AS
   may be originating a route.

   The first situation does not require the creation of an RA, since an
   RA is not prepended to the RA sequence when a route is forwarded to
   peers in the same AS (confederations are different ASes).

   The second situation imposes some requirements on the code which
   produces an UPDATE message to advertise an UPDATE.  As the path
   attributes are being placed into the UPDATE, the attestation
   attribute must be created.  This requires building a new RA sequence
   if aggregation has occurred.  A new RA is then prepending to the RA
   sequence.  In order to create the new RA, all other path attributes
   and the NLRI must be available, as well as the AS number of the
   peer(s) to which the UPDATE will be sent.  If the speaker performed
   aggregation to create the route, the RA sequences from all routes
   which were aggregated must be available.  The AS PATH attribute and
   the NLRI/MP_REACH_NLRI attribute must be present in the form which
   they will take in the UPDATE message.  If the route is to be
   forwarded to more than one AS, it is more efficient though not
   required, to have the full list of ASes available as well.  Then the
   new RA can be created, as described in section 3.2.1.2.  Note that a
   BGP implementation may require some change to the method of building
   UPDATE messages to allow all protectable path attributes and the NLRI
   to be available while creating the attestation attribute; support for
   the Multiprotocol Reachable path attribute requires similar changes.

   The creation of an RA requires a signature to be computed.  If the
   signature is computed asynchronously (e.g., another processor is
   devoted to cryptographic operations), the UPDATE message may not be
   available to be sent immediately after the path attributes and NLRI
   are written to the message.  Thus it may be necessary for some BGP
   implementations to be changed to allow for queueing of completely
   formated UPDATE messages until after the signature has been computed
   and inserted into the Last RA.

   After the signature is computed, a speaker may wish to cache this new


                          Lynn, Mikkelson, Seo                 [Page 45]


                               Secure BGP                      June 2003


   RA, so that if it needs to be advertised again, the signature does
   not need to be recomputed.  Caching is discussed in section 4.  Note
   that it is important that if two UPDATE messages are to be sent to
   the same peer, and the first requires a signature computation but the
   second is found in the send cache (so no signature is needed) or only
   withdraws routes, the second UPDATE message MUST be queued until the
   first has been sent so that the order of UPDATE messages is
   preserved.

   The third situation for advertising a route occurs when an S-BGP
   speaker originates a route.  Care must be taken that the NLRI is not
   allowed to grow too large.  A configuration parameter is necessary to
   limit the size of the NLRI such that enough space is left in the
   4096-octet BGP message to allow inclusion of the longest expected RA
   sequence for that route; see, e.g., max-origin in C.4.3.  This
   configuration should account for the radius of the Internet in ASes
   from the point of view of the originating AS.  It may be necessary to
   send multiple UPDATE messages with smaller NLRI where one would have
   been sufficient were S-BGP not being used.  The NLRI must be
   restricted in size at the originating speaker because an UPDATE
   message cannot be split to reduce the UPDATE message size when it is
   protected by an RA.  Splitting the NLRI actually increases the UPDATE
   size as the old, large NLRI must be made explicit in the Last
   received RA, when it could have been implicit if the NLRI had not
   been changed.  Once the NLRI for a given UPDATE message has been
   determined, the UPDATE can be built as usual for an S-BGP speaker.
   The only difference at this point from the second situation above is
   that the attestation attribute is new.  The creation of the RA
   requires the same information as is needed for the second situation
   above.  Similarly, the signature computation may be delayed, and a
   send cache of RAs for originated routes may be created.


3.2.3.3.  Background Processing

   Some processing of local S-BGP information may occur as a background
   process.

   Since RAs, public keys, and AA information eventually expire,
   attention must be paid to keep routing information current.  The NOC
   may upload new public keys, AA information, or policy to an S-BGP
   speaker.

   Locally stored public keys and AA information that have expired
   should be removed.  Any routes that were validated using expired
   information are no longer valid; they should be either re-validated,
   as newer public keys or AA information becomes available, or the
   Phase 2 decision process should be run to select alternate routes.
   This might result in sending withdrawals and advertising a new,
   validated route.  Local policy may allow expired routes to remain,
   e.g., in general, in cases where no other route is available, or when


                          Lynn, Mikkelson, Seo                 [Page 46]


                               Secure BGP                      June 2003


   all other routes have failed validation.

   RAs which have expired must also be handled.  This includes removing
   routes which were validated by the expired RAs, as they are no longer
   valid, and finding a new best route.  Expired RAs must also be
   removed from any RA caches (section 4).  Both RAs received in UPDATEs
   and RAs created and signed by the speaker may be cached.  RAs created
   by the speaker could either be removed from the send cache, so that
   they are re-computed when the route is next advertised, or they may
   be left and simply re-signed (after updating the Expiry part) if the
   public key for the speaker is still valid.  In either case, if the
   expired RA was created for a route originated by the speaker, the
   route must be advertised again, with a new RA.  If a soon to expired
   RA was prepended to an RA sequence by a speaker and the route is
   still in the Loc-RIB and none of the received RAs have expired, that
   route should be re-advertised with a newly signed RA.  Efficiency
   would suggest that a re-advertisement be delayed if one of the other
   RAs will expire before the locally generated RAs.

   Depending on the implementation of S-BGP, especially of the receive
   and send RA caches if they are used, there may be a need for other
   periodic clean up.  For example, a receive RA cache for a given peer
   might not be deleted immediately when the session is terminated, so
   that if the session is re-established the RAs received would not need
   to be re-verified; see, e.g., [BGPRES].  However, if the session is
   not re-established within a reasonable interval, the cached routes
   might be removed.  Depending on the implementation, this may require
   a periodic processing of the cache.

   Finally, idle time may be used to verify RAs in the, e.g., second
   best routes, which have not yet been verified.  Since it might be
   advertised in the future, if RAs are verified during idle time, the
   verification computation might be completed before selection as the
   best route.  (Delayed verification of RAs is discussed in section
   3.2.3.1.)


3.2.3.4.  Unknown Path Attributes and Canonicalization

   An S-BGP speaker can handle unknown protected path attributes
   provided that they do not need canonicalization during the
   verification of an RA.  During verification, an implicit path
   attribute which does not need to be canonicalized may be byte-
   compared against the explicit path attribute found in the RA's
   ExplicitPA part (section 3.2.1.1).  Thus validation can succeed
   despite the fact that the path attribute is unknown.  When an RA
   protecting an unknown path attribute is forwarded as part of an
   advertised route, the unknown path attribute must be placed in the
   Last RA's explicit data as well as in the new RA's explicit data,
   since the speaker for which the path attribute is unknown sets the
   Partial bit in the Path Attribute Flags.  This causes the path


                          Lynn, Mikkelson, Seo                 [Page 47]


                               Secure BGP                      June 2003


   attribute to change, requiring it to be placed in the explicit data
   of the Last RA of the received RA sequence, as usual (section
   3.2.1.2).  If local policy stipulates removal of the unknown path
   attribute, it will still be placed in the explicit data of the Last
   RA, and the corresponding bit will not be set to 1 in the new RA's
   CoverageMask field.

   Currently only the AS PATH and NLRI/MP_REACH_NLRI path attributes
   need be canonicalized for verification (section 3.2.1.1).  However,
   if an unknown path attribute is defined in the future such that the
   implicit form of the path attribute from the UPDATE must be
   canonicalized before it may be compared against the path attribute in
   the explicit data of the Last RA, S-BGP cannot properly validate the
   unknown path attribute.  The signature verification may be carried
   out properly, but the implicit and explicit forms of the path
   attribute will not match.  Also, any RAs subsequent to the Last RA
   which carry the unknown path attribute in an implicit form cannot be
   validated.

   It is not sufficient to simply allow validation to fail.  Policy may
   allow subsequent RAs to be considered validated by the Last RA.
   Since the S-BGP speaker does not know how to handle the unknown path
   attribute, the fact that the implicit and explicit data do or do not
   match does not indicate whether the data is valid.  If the implicit
   and explicit data do not match, it cannot be determined that this is
   because canonicalization is necessary or because the implicit data
   has been changed.  If they do match, it cannot be determined that
   canonicalization would have produced non-matching data, such that
   validation should fail.

   It may be safe to assume that if the implicit and explicit data do
   match and the signature verification succeeds that validation has
   succeeded, but only if it can be determined when a path attribute
   requires canonicalization.  A method for dealing with the issue of
   future path attributes which should be protected by S-BGP and which
   also need canonicalization has not been determined.  Two simple
   possibilities include disallowing new attributes from having
   canonicalization rules, which could cause every RA in a sequence to
   store this path attribute in the ExplicitPA, or disallowing S-BGP
   protection of new path attributes which need canonicalization until
   all S-BGP speakers can handle the new path attribute.  This issue
   needs further study.  Specifications for new path attributes SHOULD
   specify whether or not they require canonicalization, and if so how
   the canonicalization is performed.


3.2.4.  Interoperation with Non-S-BGP Speakers

   The design of S-BGP allows gradual deployment of S-BGP capability
   throughout an internet.  The expected deployment scenario is for
   initial deployment by large, well interconnected, ASes.  They have


                          Lynn, Mikkelson, Seo                 [Page 48]


                               Secure BGP                      June 2003


   more customers that would benefit from S-BGP assurances.  Over time
   more ASes would support S-BGP.  Another scenario is for a group of
   users to decide to deploy S-BGP to protect their routing
   infrastructure.

   As S-BGP is incrementally deployed it would be possible for an UPDATE
   message to traverse both ASes that do and ASes that do not recognize
   and/or process the attestation path attribute.  While rules and
   algorithms can be specified that permit some security benefits to be
   realized when an S-BGP protected UPDATE traverses non-S-BGP ASes,
   those algorithms, and their related policy controls, are sufficiently
   complex relative to the additional security realized that this
   specification does NOT RECOMMENDED that they be implemented.

   In the expected deployment scenario, having S-BGP protected UPDATEs
   pass between ASes that are using S-BGP ONLY via an AS(es) not using
   S-BGP would be the exception, rather than the common case.  Thus
   there would be little to be gained from the added complexity.

   In addition, this specification RECOMMENDs that an AS that supports
   S-BGP processing only add RAs for the prefixes that the AS
   originates, or which were received from a peer that prepended an RA
   to the attestation path attribute.  This has two advantages.  First,
   the volume of routes that carry the attestation path attribute would
   be significantly less that the total number of routes in the
   Internet; this translates to significantly reduced memory
   requirements.  Reduced memory requirements may enable more ISPs to
   use S-BGP without having to add more memory to their S-BGP speakers.
   Second, if a route is protected by S-BGP, then one has assurances
   that the route is authorized all the way to destination network.

   Since the binding between origin AS and network prefix by address
   attestations is both authoritative and completely out-of-band, a
   speaker that has S-BGP capability can perform origin verification
   without having to perform any attestation path attribute processing.


4.  Processing Optimizations

   There are several processing options that can be used to improve the
   efficiency of an S-BGP implementation.  Some choices, such as the
   addition of cryptographic hardware or the use of RA caches, might
   depend on the placement of the router, e.g., is it used at a NAP or
   at a customer site.

   Use of Implicit Data

      Protected data should be implicit in all prepended RAs unless it
      either differs from the NLRI/MP_REACH_NLRI or protected transitive
      path attributes, or the data cannot be derived from explicit data
      in a previous RA.  When the data in an RA that is being prepended


                          Lynn, Mikkelson, Seo                 [Page 49]


                               Secure BGP                      June 2003


      to an attestation is the same as the data in the Last RA that was
      received from a peer AS, it SHOULD be made implicit (by removing
      it from the Last received RA), thus reducing the size of the
      attestations.

   Cryptographic Operations on Another Processor

      The time required to perform cryptographic operations is quite
      substantial compared to the time required to do other processing
      of UPDATE messages.  As such, a performance improvement *might* be
      realized by moving the signing and verifying operations to another
      processor instead of doing them in software.  This could be
      specialized hardware attached to the router, via either an
      external interface or a PCMCIA card, or it could be a general-
      purpose computer, such as a PC on a router blade, to which the
      router may pass crypto requests.  Adding any such processing will
      cause the cryptographic operations to be performed asynchronously,
      so special attention must be paid to handling and synchronization
      issues.  Note that performing the SHA-1 hash in hardware might not
      be faster than doing the hashing in software, as marshalling and
      passing the data to be hashed to a crypto processor takes both
      additional space, time, and scheduling overhead.

      It has been observed that the advertised performance of some
      vendor's cryptographic accelerators may not be achievable due to
      the large number of public keys (10s of thousands when S-BGP is
      fully deployed) that are needed to verify the RA signatures.  The
      performance loss was due to the limited memory available for
      public keys combined with the need for sequential transactions to
      unload a public key (to make room for another), load the needed
      key and obtain the key id assigned by the accelerator, and to then
      pass that key id, the hash, and signature data to the accelerator
      for verification.  A "key agile" accelerator design that is
      capable of accepting the public key, hash, and signature data in a
      single transaction could avoid this problem.

      Use of a hardware cryptographic processor that protects the
      private key(s) used to sign the hashed information provides better
      security than techniques that hold the private key(s) in router
      memory.

      An external processor may also allow parallel execution of
      signing/verifying; since multiple RAs may be signed (for
      advertising to multiple peers) or verified (multiple RAs are
      received in an attestation attribute), this may produce a
      noticeable performance improvement.

      Performing signature verification in software and signature
      generation on a token might be advantageous (especially if the
      token is not public key agile).



                          Lynn, Mikkelson, Seo                 [Page 50]


                               Secure BGP                      June 2003


   RA Caching

      Retention of a peer's Adj-RIB-In after a peering session has been
      terminated can speed the reestablishment of a subsequent peering
      session.  BGPs that implement [BGPRES] will automatically gain
      this benefit.

      Another possible optimization involves caching RAs, both those
      received from other peers, and those created by the speaker and
      sent to other peers.  Caching helps reduce the number of
      verifications and signatures necessary to handle route flaps.  If
      a route is flapping and the received RAs for both have been
      verified once, a cache will allow the already-verified RAs to be
      used to validate the route each time it flaps, reducing processing
      overhead.  Likewise, a flapping route being advertised by the peer
      requires sending multiple locally-generated RAs; in this case a
      cache of sent RAs can reduce the number of signatures to be
      computed.


5.  Auditing and Event Reporting

   Security relevant events SHOULD be recorded and/or reported to a
   management station.

   There SHOULD be a way to limit the rate at which events are reported
   to a NOC.  It is RECOMMENDED that rate limiting be applied on a per-
   speaker basis.  Per-event limits MAY be implemented.

   The audit information should include: the identity of the signer, if
   it can be determined; the identity of the authorizing AS, if it can
   be determined; the peer from which the message was received; and the
   type of error or problem detected.

   For a missing key, the key owner and key identifier should be
   reported.

   For a missing AA, the prefix and originating AS should be reported.


6.  Infrastructure Support

   Operation and deployment of S-BGP requires supporting infrastructure.
   S-BGP uses X.509 v3 certificates consistent with the PKIX
   specification [RFC3280] that include private extensions for the
   delegation of IP address blocks and AS numbers as well as the binding
   of a BGP Identifier to an AS.  The extensions are defined in
   [X509EXT] and [X509S-BGP].  The Regional Internet Registries need the
   capability to securely obtain an organization's public key and a
   Certification Authority (CA) capability to generate subordinate CA
   certificates containing the extensions that are used to delegate the


                          Lynn, Mikkelson, Seo                 [Page 51]


                               Secure BGP                      June 2003


   right to use IP address prefixes and AS numbers, and to make the
   signed certificates available to the organizations to whom the
   resources have been delegated.

   ISPs need CA capability to create end entity certificates with the
   appropriate extensions for their ASes, networks, S-BGP speakers, and
   operations personnel.  They may also need the capability to issue
   subordinate CA certificates if they further delegate the right to use
   some of their address space to their multi-homed BGP customers (as
   opposed to loaning portions of their address space).

   The S-BGP architecture calls for the storage and distribution of all
   S-BGP related certificates, CRLs, and AAs in a distributed global
   repository with servers replicated at well-connected points
   throughout the Internet.  Initial mechanisms for the communication of
   certificates, CRLs, and AAs to one of these repositories by
   certificate owners, CRL signers, and AA issuers have been developed,
   as has software for the repositories and for use by NOCs to manage
   their S-BGP assets.

   The management of an AS is responsible for posting their locally
   generated certificates, CRLs, and AAs to the repository and for
   periodically downloading the information in the repository for local
   processing and distribution to their S-BGP speakers.  The HTTPS
   protocol is used for update (POST) and retrieval (GET) transactions
   with the repositories.

   The AS's management is responsible for certificate verification.  The
   format of certificate extracts and the mechanisms for their
   communication to the S-BGP speakers within as AS are vendor specific.

   The extracted information should contain a representation of the
   following fields: Subject name, Subject Public Key Info (the DSA
   public key), Subject Key Identifier, the IP Address Block Certificate
   Extension, the Autonomous System Identifier Certificate Extension,
   and the Router Authorization Certificate Extension.


7.  Address Attestations

   The owners of IP address blocks, i.e., those organizations which have
   been issued a certificate containing an IP Address Block Certificate
   Extension, need to generate and sign an AA that authorizes one or
   more ASes to advertise those address blocks.  The resulting AAs MUST
   be sent to one of the top-level repositories as described in the
   previous section.







                          Lynn, Mikkelson, Seo                 [Page 52]


                               Secure BGP                      June 2003


8.  IANA Considerations

   IANA should assign BGP Type Code *IANA-TBD* to the attestation path
   attribute ("ATTEST").  Replace *IANA-TBD* with the number in section
   3.

   IANA assigned the eight bit value 2 to the DSAwithSAH1 on 31 Oct 2000
   and listed it in the Signature Algorithm Number table at
   http://www.isi.edu/in-notes/iana/assignments/sig-alg-numbers.  That
   URL is no available on the IANA web page.  Reference [IANA-SAN]
   should be updated with the correct URL.

   IANA should create a name space for the Attestation Part Codes, e.g.,
   attest-numbers.  Values defined in this specification are:

       0   Reserved                8   Route Attestation
       1   Signer Part             9   Address Attestation
       2   Signature Part         10   CRLs
       3   Expiry Part            11   Certificates
       4   ExplicitPA Part        12
       5   Target Part            13
       6                          14   Extract file authenticator
       7                          15   Reserved for escape mechanism

   Unassigned attestation Part Codes may be assign by IANA when
   presented with working group consensus.


9.  Security Considerations

   Security is central to the design of this protocol, and these
   security considerations permeate this specification.

   Security considerations related to public key technology are given in
   [RFC3280].


10. Acknowledgments

   Many individuals contributed to the design and development of S-BGP.
   As members of the architecture team, Stephen Kent, Martha Steenstrup,
   and Luis Sanchez provided critical input to the design of the
   attestation and PKI schemes, evaluation of other approaches, and
   analysis of performance and operational issues.  Sean Kennedy and
   John Hawkinson provided invaluable insight into real world Internet
   engineering and operational issues.  The authors would also like to
   thank Michelle Casagni for her help with the analysis and Dennis
   Rockwell and Nicholas Shectman for their help with the proof of
   concept implementation.  Additional thanks to Rick Altmann, Kavita
   Baball, Ed Bubnis, Sue-fen Cuti, Shelby Evans, Mark Fausett, Pete
   Fischer, Pete Foley, Charlie Gardiner, Christine Jones, Joe Kraska,


                          Lynn, Mikkelson, Seo                 [Page 53]


                               Secure BGP                      June 2003


   Bob Masters, JB Mitchell, Tony Stein, and Carmela Stuart for their
   work developing the supporting repository, NOC, and certification
   authority software that will be needed to support S-BGP
   operationally.

   This work was made possible by support from NSA and DARPA.


11. References

   The following references are normative.

   [DSS]      Federal Information Processing Standards Publication (FIPS
              PUB) 186-1, "Digital Signature Standard (DSS)", U.S.
              Department of Commerce / National Institute of Standards
              and Technology, December 1998.

   [IANA-AFI] http://www.iana.org/assignments/address-family-numbers.

   [IANA-SAFI]http://www.iana.org/assignments/safi-namespace.

   [IANA-SAN] http://www.iana.org/assignments/sig-alg-numbers.

   [RFC2026]  Bradner, S., "The Internet Standards Process -- Revision
              3", RFC 2026, BCP 00009, October 1996.

   [RFC2119]  Bradner, S., "Key words for use in RFCs to Indicate
              Requirement Level", BCP 14, RFC 2119, March 1997.

   [RFCbgp]   Rekhter, Y., Li, T., Hares, S., "A Border Gateway Protocol
              4 (BGP-4)", draft-ietf-idr-bgp4-20.txt

   [SHA-1]    Federal Information Processing Standards Publication (FIPS
              PUB) 180-1, "Secure Hash Standard", U.S. Department of
              Commerce / National Institute of Standards and Technology,
              April 1995.
   or         D. Eastlake 3rd, P. Jones, "US Secure Hash Algorithm 1
              (SHA1), RFC 3174, September 2001.

   [X509EXT]  Lynn, C., Kent, S., Seo, K., "X.509 Extensions for IP
              Addresses and AS Identifiers",
              draft-ietf-pkix-x509-IPaddr-AS-extn-01.txt, June 2003.

   [X509S-BGP]Lynn, C., "S-BGP Authorization PKI -- X.509 Extensions and
              Profile", draft-clynn-bgp-x509-auth-02.txt, February 2002.

   The following references are informative.

   [AS4Bytes] Vohra, Q., Chen, E., "BGP support for four-octet AS number
              space", draft-ietf-idr-as4bytes-05.txt, May 2002.



                          Lynn, Mikkelson, Seo                 [Page 54]


                               Secure BGP                      June 2003


   [BGPRES]   Sangli, S. R., Rekhter, Y., Fernando, R., Scudder, J. G.,
              Chen, E., "Graceful Restart Mechanism for BGP",
              draft-ietf-idr-restart-06.txt, January 2003.

   [CMS03]    Kent, S., "Securing the Border Gateway Protocol: A Status
              Update", Seventh IFIP TC-6 TC-11 Conference on
              Communications and Multimedia Security, October 2-3, 2003,
              Turin, Italy

   [DISCEX]   Lynn, C., Seo, K., "Design and Analysis of the Secure
              Border Gateway Protocol (S-BGP)", IEEE DISCEX Conference,
              January, 2000.

   [DPA]      Chen, E., Bates, T., "Destination Preference Attribute for
              BGP", draft-ietf-idr-bgp-dpa-04.txt, January 1996

   [EXT-COMM] Sangli, S., Tappan, D., Rekhter, Y., "BGP Extended
              Communities Attribute",
              draft-ietf-idr-bgp-ext-communities-05.txt, May 2002.

   [JSAC]     Kent, S., Lynn, C., Seo, K., "Secure Border Gateway
              Protocol (S-BGP)", IEEE JSAC Issue on Network Security,
              April 2000.

   [MRT]      http://www.merit.edu/~mrt,
              http://www.merit.edu/mrt/mrt_doc

   [Murphy]   Murphy, S., "BGP Security Vulnerabilities Analysis",
              draft-murphy-bgp-vuln-00.txt, February 2002.

   [Murphy2]  Murphy, S., "BGP Security Protections",
              draft-murphy-bgp-protect-00.txt, February 2002.

   [NDSS00]   Kent, S., Lynn, C., Mikkelson, J., Seo, K., "Secure Border
              Gateway Protocol (S-BGP) -- Real World Performance and
              Deployment Issues", Proceedings of the Network and
              Distributed System Security Symposium, San Diego
              California, February 2000.

   [RFC1863]  Haskin, D., "A BGP/IDRP Route Server alternative to a full
              mesh routing", RFC 1863, October 1995.

   [RFC1965]  Traina, P., "Autonomous System Confederations for BGP",
              RFC 1965, June 1996

   [RFC1997]  Chandra, R., Li, T., Traina, P., "BGP Communities
              Attribute", RFC 1997, August 1996

   [RFC2050]  Hubbard, K., Kosters, M., Conrad, D., Karrenberg, D.,
              Postel, J., "Internet Registry IP Allocation Guidelines",
              RFC 2050, BCP 00012, November 1996.


                          Lynn, Mikkelson, Seo                 [Page 55]


                               Secure BGP                      June 2003


   [RFC2401]  Kent, S., Atkinson, R., "Security Architecture for the
              Internet Protocol", RFC 2401, November 1998.

   [RFC2406]  Kent, S., Atkinson, R., "IP Encapsulating Security Payload
              (ESP)", RFC 2406, November 1998.

   [RFC2407]  Piper, D., "The Internet IP Security Domain of
              Interpretation for ISAKMP", RFC 2407, November 1998.

   [RFC2408]  Maughan, D., Schertler, M., Schneider, M., Turner, J.,
              "Internet Security Association and Key Management Protocol
              (ISAKMP)", RFC 2408, November 1998.

   [RFC2409]  Harkins, D., Carrel, D., "The Internet Key Exchange
              (IKE)", RFC 2409, November 1998.

   [RFC2410]  Glenn, R., Kent, S., "The NULL Encryption Algorithm and
              Its Use With IPsec", RFC 2410, November 1998.

   [RFC2796]  Bates, T., Chandra, R., Chen, E., "BGP Route Reflection -
              An Alternative to Full Mesh IBGP", RFC 2796, April 2000.

   [RFC2828]  Shirey, R., "Internet Security Glossary", RFC 2828, May
              2000.

   [RFC2858]  Bates, T., Rekhter, Y., Chandra, R., Katz, D.,
              "Multiprotocol Extensions for BGP-4", RFC 2858, June 2000.
              also draft-ietf-idr-rfc2858bis-02.txt, April 2002.

   [RFC3107]  Rekhter, Y., Rosen, E., "Carrying Label Information in
              BGP-4", RFC 3107, May 2001.

   [RFC3279]  Polk, W., Housley, R., Bassham, L., "Algorithms and
              Identifiers for the Internet X.509 Public Key
              Infrastructure Certificate and Certificate Revocation List
              (CRL) Profile", RFC 3279, April 2002.

   [RFC3280]  Housley, R., Polk, W., Ford, W., Solo, D., "Internet X.509
              Public Key Infrastructure Certificate and Certificate
              Revocation List (CRL) Profile", RFC 3280, April 2002.

   [RVO]      www.routeviews.org, /bgpdata and /route-views6/bgpdata.

   [SALTZER]  Saltzer, J. and Schroder, M., "The Protection of
              Information in Computer Systems", IEEE Proceedings, 63(9),
              March 1975.

   [S-BGP]    http://www.ir.bbn.com/projects/s-bgp





                          Lynn, Mikkelson, Seo                 [Page 56]


                               Secure BGP                      June 2003


Appendix A.  Example Certificates, Hashes, and Signatures

   This informational appendix will be provided in a subsequent version
   of this document when all the TDB values have been assigned.

   PKI Examples

   Root CA Certificate
   text
   PEM

   Grandfather CA Certificate
   text
   PEM

   ISP CA Certificate

   ISP AS End-entity Certificate

   ISP Network End-entity Certificate

   Network Address Attestation
   text
   hex

   Router S-BGP End-entity Certificate

   ISP NOC Operator End-entity Certificate

   Repository CA Certificate

   Repository End-entity Certificate
   (db and SSL?)

   S-BGP UPDATE Message
   text
   hex
















                          Lynn, Mikkelson, Seo                 [Page 57]


                               Secure BGP                      June 2003


Appendix B.  Configuration

   S-BGP requires additional configuration information.  This
   informational appendix describes configuration items that an S-BGP
   implementation might implement.

   Where to find and how to activate and use the RA signing private key.

   Where to find the NOC's public key.

   The name of the file(s) containing AA extracts, public key extracts,
   and S-BGP policy.

   Per NOC, how to negotiate an IPsec transport-mode ESP security
   association for upload to speakers, if required.

   Per peer, how to negotiate an IPsec transport-mode ESP security
   association.



































                          Lynn, Mikkelson, Seo                 [Page 58]


                               Secure BGP                      June 2003


Appendix C.  Policy Support

   This informational Appendix describes policies that an S-BGP
   implementation might implement.

   Secure BGP policy enables the incremental deployment of S-BGP, easier
   introduction of new S-BGP capable ASes and speakers, and the ability
   to work around misconfiguration in other ASes.  For these reasons
   S-BGP policy is applied in a hierarchical manner such that policy may
   be specialized for particular ASes, speakers, or prefixes as
   appropriate by an S-BGP capable speaker.  The policy levels are:

    * Global
      Policy set at the global level applies to all UPDATEs regardless
      of the prefixes being advertised, or the ASes or speakers from
      which they were originated or through which or to which they were
      advertised.  Global policy must be set, and is the default when no
      more specific policy overrides it.

    * Autonomous System (AS)
      AS policy may be used when needed to override global policy, and
      is applied based on the AS from which an UPDATE was originated or
      through which or to which an UPDATE is advertised.

    * Speaker
      Speaker policy may be used when needed to override both global and
      AS policy, and is applied based on the individual speaker from
      which an UPDATE or RA was originated or to which an UPDATE is
      advertised.

    * Prefix
      Prefix policy may be used when needed to override global, AS, and
      speaker policy, and is applied based on a specific prefix.

   All policy is available at the global level; some policy is available
   for specialization to the AS, speaker, and/or prefix level.  More
   specific policy always takes precedence.


C.1.  Policy Control Classes

   Consistent routing necessitates that BGP speakers apply the same
   algorithm on the same routing information.  Therefore, some S-BGP
   functionality may need to be:

    * activated or deactivated based on speaker and AS capabilities,

    * configured for specific topologies and peering relationships,

    * tuned and optimized for performance and interoperability,



                          Lynn, Mikkelson, Seo                 [Page 59]


                               Secure BGP                      June 2003


    * incrementally deployed to allow for interoperability of S-BGP
      capable and non-capable speakers,

    * extensible for the protection of new features added to BGP, and

    * workable around misconfigurations.

   These functional requirements are listed in order of significance and
   represent the control classes into which S-BGP policy is categorized.
   This section defines and categorizes the available S-BGP policy
   settings.

   Some policies provide an "only-route" setting.  This setting implies
   that a received route may be selected even if some portion of the
   S-BGP verification process fails.  If no other route successfully
   verifies for a given prefix, then a non-verified route for which the
   "only-route" policy applies may be selected; otherwise, no route
   would exist for the given prefix.  This policy setting is more
   forgiving than outright route rejection, especially in the case of
   system misconfiguration, but does introduce a security risk.
   However, an attacker would not only have to send an invalid route
   update such that it passes an "only-route" policy, but also prevent
   all other valid routes from being received by a speaker.

   Several policy settings are represented as a set of BGP path
   attribute identifiers.  Only transitive path attributes (i.e., path
   attributes available for S-BGP protection) may be specified in these
   policies.  Currently defined transitive path attributes include the
   following.

      NLRI or MP_REACH_NLRI   Type Code 0, only within S-BGP route
                              attestations
      ORIGIN                  Type Code 1
      AS PATH                 Type Code 2
      ATOMIC AGGREGATE        Type Code 6
      AGGREGATOR              Type Code 7
      COMMUNITY               Type Code 8
      DPA                     Type Code 11
      EXTENDED COMMUNITY      Type Code 16

   Additional transitive path attributes may be protected as they are
   defined within the BGP protocol.

   The NOC provides each S-BGP speaker a policy configuration file in
   addition to the AA and certificate extract files.  The integrity of
   and the authorization to use the S-BGP policy is assured by the
   signing of the file by the NOC with, e.g., the NOC's or AS's private
   key.





                          Lynn, Mikkelson, Seo                 [Page 60]


                               Secure BGP                      June 2003


C.2.  Activation

   General S-BGP functionality is activated or deactivated based on the
   following policy.


C.2.1  enable-AA

   The "enable-AA" policy directs an S-BGP speaker to perform, or not
   perform, AA verification of the NLRI within received UPDATEs.  This
   policy is applied only at the global level, and available settings
   include:

      yes         AA verification of NLRI received in UPDATEs is
                  performed.
      no          AA verification of NLRI received in UPDATEs is not
                  performed.

   The default setting is "yes"; under normal operation an S-BGP speaker
   should always perform NLRI origination verification using AA
   information.  However, an S-BGP speaker newly introduced into the
   network may not have received AA extracts required to perform AA
   verification, in which case the policy may be set to "no".

   If this policy is set to "no", then all other policy pertaining to AA
   verification is not activated.


C.2.2  enable-RA

   The "enable-RA" policy directs an S-BGP speaker to process, or not
   process, RAs within received UPDATEs.  This policy is applied only at
   the global level, and available settings include:

      yes         Processing of RAs received in UPDATEs is performed.
      no          Processing of RAs received in UPDATEs is not
                  performed.

   The default setting is "yes"; under normal operation S-BGP should
   always process received RAs.  However, an S-BGP speaker may lack
   public keys required to perform RA verification of UPDATEs, or an
   S-BGP speaker may not peer with any other S-BGP capable speaker.  In
   such cases the policy is best set to "no".

   If this policy is set to "no", then all other policy pertaining to
   inbound route attestations is not activated.







                          Lynn, Mikkelson, Seo                 [Page 61]


                               Secure BGP                      June 2003


C.2.3  send-attest

   The "send-attest" policy directs an S-BGP speaker to include, or not
   include, an attestation path attribute in outbound advertisements.
   This policy is applied at the global and peer (speaker) levels, and
   available settings include:

      yes         An attestation path attribute is included within
                  outbound advertisements for locally originated routes
                  and for transit advertisements that contained an
                  attestation path attribute.
      no          No attestation path attribute is included in outbound
                  advertisements, and any attestation path attribute is
                  removed before sending a transit advertisement.

   The default setting is "yes"; under normal operation an S-BGP speaker
   should always prepend a locally generated RA within the attestation
   path attribute of all transit or locally originated outbound
   advertisements.  The "no" policy setting is used when a speaker peers
   with a non S-BGP capable speaker.  In this case, no attestation path
   attribute is included within the outbound advertisements.

   If this policy is set to "no", then all other policy pertaining to
   outbound advertisements is not activated.


C.3.  Configuration

   The following policy is used in configuring an S-BGP speaker for a
   particular topology and set of peering relationships.


C.3.1  sign-AS

   The "sign-AS" policy allows multiple targets (peer ASes) to be
   identified in an RA when a single UPDATE is to be sent to multiple
   external peers.  The target of an RA is the set of ASes being
   authorized to use and advertise the route associated with the RA.
   The default target is the AS of the speaker to which the route is
   being sent.  In the case of external route reflectors, however,
   multiple targets will need to be specified because the advertised
   route is further propagated to the other speakers in communication
   with the route reflector.  This policy is applied only at the peer
   (speaker) level and consists of a list of unique AS numbers.

   Note that internal route reflectors are often used for iBGP; the
   "sign-AS" policy does not apply in such a case because RAs are not
   generated and included within UPDATEs sent to internal peers.
   However, external route reflectors may be used at network access
   points (NAPs), for example, to forward received UPDATEs to multiple
   external speakers.


                          Lynn, Mikkelson, Seo                 [Page 62]


                               Secure BGP                      June 2003



C.3.2  peer-auth

   The "peer-auth" policy specifies which entity, if any, is responsible
   for performing peer authentication through the use of IPsec.  This
   policy is applied at the global and peer levels, and available
   settings include:

      bgp         The BGP speaker is responsible for performing peer
                  authentication.
      system      The system on which the BGP speaker resides is
                  responsible for performing peer authentication.
      no          No peer authentication is performed.

   The default policy setting is "system".  Speakers on either side of a
   peering relationship must have consistent settings for this policy.


C.3.3  peer-key

   The "peer-key" policy specifies the key to use for purposes of peer
   authentication.


C.3.4  upload-port

   The "upload-port" policy specifies the port number and protocol over
   which information such as the extract and policy files is uploaded
   from the NOC.


C.4.  Tuning and Optimization

   Policy for tuning and optimizing the performance of a S-BGP speaker
   is defined as follows.


C.4.1  verify-RA

   The "verify-RA" policy determines the time at which the RAs within a
   received S-BGP UPDATE undergo signature verification.  This policy is
   applied only at the global level, and the available settings include:

      receipt     RAs are verified prior to the route's inclusion within
                  the Adj-RIB-In.
      selection   RAs are verified prior to the route's inclusion within
                  the Loc-RIB.
      background  RAs are queued for verification at the time of the
                  route's inclusion within the Adj-RIB-In; RAs must be
                  verified prior to the route's inclusion within the
                  Loc-RIB.


                          Lynn, Mikkelson, Seo                 [Page 63]


                               Secure BGP                      June 2003



   The "receipt" setting results in the verification of all received
   UPDATEs.  Any invalid route is detected and reported upon receiving
   the route, regardless of Phase 2 route selection.  The early
   detection of invalid routes requires resources be allocated to
   cryptographic verification of routes that may never be selected.
   Greater resource efficiency is achieved by setting the policy to
   "selection", which is the default setting.  The "background" setting
   combines the earlier detection of invalid routes with greater
   resource efficiency.


C.4.2  multi-route

   The "multi-route" policy applies only in the case of UPDATEs that
   have undergone route aggregation.  A given prefix may be included in
   multiple paths of the aggregated route.  This policy directs an S-BGP
   speaker performing AA verification of aggregated routes for a common
   prefix.  This policy is applied at the global and prefix levels, and
   available settings include:

      all         All paths to a common prefix within a received UPDATE
                  must be valid.
      one         At least one path to a common prefix within a received
                  UPDATE must be valid.

   The default setting is "all"; ensuring that all aggregated routes to
   a common prefix are valid provides greater security.  The "one"
   setting is a more permissive alternative.


C.4.3  max-origin

   The "max-origin" policy specifies the maximum sized NLRI to be
   included within originated UPDATE.  This policy is applied at the
   global and speaker levels, and is used only in the origination, not
   propagation, of routes.  A maximum NLRI size is used to leave
   sufficient space within an UPDATE for the attestation path attribute,
   which grows in size during propagation.

   The "max-origin" policy specifies the percentage of the space in an
   originated UPDATE less the NLRI that may be used for NLRI.
   Determination of the value of this policy includes factors such as
   expected aggregation or UPDATE NLRI splitting and the diameter of the
   Internet, in ASes.  The default setting for this policy is 75
   percent, i.e., three quarters of the remaining space in an UPDATE
   without NLRI may be used for NLRI.






                          Lynn, Mikkelson, Seo                 [Page 64]


                               Secure BGP                      June 2003


C.4.4  prefix-class

   The "prefix-class" policy is used to tag specific prefixes.  Prefixes
   within different classes are not aggregated in a single UPDATE.  This
   policy is applied only at the prefix level and is used only in the
   origination, not propagation, of routes.  By default, all prefixes
   are assigned to the same class.

   This policy is significant in when an AS has multi-homed customers.
   A multi-homed customer authorizes multiple ASes to advertise routes
   for its prefix(es).  At some AS, the route advertised by one
   originating AS for a prefix from a multi-homed customer will not be
   the best route (the route from one of the other originating ASes will
   be better) and, therefore, it will not be propagated further.  The
   UPDATE that advertised the route may still be advertised for the
   other prefixes contained within the UPDATE'S NLRI; the multi-homed
   prefix is removed prior to the further propagation of the UPDATE.
   Modification of the NLRI requires that all the NLRI be included as
   explicit data within the Last received RA, which increases the size
   of the UPDATE.  To prevent this situation, multi-homed prefixes may
   be assigned to a different prefix class and originated in separate
   UPDATEs.


C.4.5  aggregate-any

   The "aggregate-any" policy indicates whether a S-BGP speaker may
   aggregate a verified and non-verified routes into a single UPDATE.
   This policy is applied only at the global level, and available
   settings include:

      yes         Aggregation of verified and non-verified routes is
                  allowed.
      no          Aggregation of verified and non-verified routes is not
                  allowed.

   The default setting is "no"; under normal operation a S-BGP speaker
   should not aggregate verified routes with non-verified routes.  A
   more permissive alternative is provided by the "yes" setting.  Use of
   this policy requires further study.


C.4.6  in-cache-depth

   The "in-cache-depth" policy specifies the number of received
   attestation path attributes to cache for a prefix.  The cache may be
   used to reduce the computational resources required for cryptographic
   verification of received UPDATEs at the expense of requiring more
   memory.  An inbound attestation cache may be maintained for each
   neighboring speaker.  Note that the BGP specification requires that
   the most recently received route for each prefix from each peer be


                          Lynn, Mikkelson, Seo                 [Page 65]


                               Secure BGP                      June 2003


   retained in the peer's Adj-RIB-In; this policy specifies how many
   additional routes should be cached.


C.4.7  out-cache-depth

   The "out-cache-depth" policy specifies the number of outbound
   attestation path attributes to cache.  The cache may be used to
   reduce the computational resources required for signature generation
   for outbound UPDATEs at the expense of requiring more memory.  An
   outbound attestation cache may be maintained for each neighboring
   speaker; this policy specifies how many routes should be cached.


C.5.  Incremental Deployment

   The following policy allows for the incremental deployment of S-BGP,
   during which time not all BGP speakers will implement the S-BGP
   security countermeasures.


C.5.1  require-AA

   The "require-AA" policy specifies the prefixes for which AAs are
   required, or not required, from the ASes originating routes to those
   prefixes.  This policy is applied at the global (i.e., all prefixes),
   AS (i.e., prefixes originated by a particular AS), or prefix level.
   Available policy settings include:

      yes         AA required for originating AS of prefix within NLRI
                  of received route.
      no          No AA required for originating AS of prefix within
                  NLRI of received route.
      only-route  If no AA exists for originating AS of a prefix in the
                  NLRI of a received UPDATE, use the route only if no
                  other verified route exists.

   The default setting is "yes"; under normal operations S-BGP should
   perform AA verification of all prefixes in advertised in received
   UPDATEs.  However, during incremental deployment many prefix owners
   will not have issued AAs for their prefixes.  To allow routes to
   these prefixes to be used, the "only-route" setting is used.  The
   "no" setting will not accept routes to prefixes that do not have an
   AA; it may be used in, e.g., closed user groups that do not want
   routes to unprotected destinations.


C.5.2  require-RA

   The "require-RA" policy specifies requirements for RA presence in
   received UPDATEs, and is applied at the global (i.e., all route


                          Lynn, Mikkelson, Seo                 [Page 66]


                               Secure BGP                      June 2003


   UPDATEs), AS (i.e., UPDATEs received from or transiting a particular
   AS), and speaker (i.e., UPDATE received from a particular speaker)
   level.  Available policy settings include:

      yes         RA required; signature must be successfully verified.
      no-verify   RA required; signature is not verified.
      no          No RA required.
      only-route  RA required; if invalid signature, use route if no
                  other verified route exits.

   The default policy is "yes"; under normal operation S-BGP should
   always require and verify RAs in all received UPDATEs.  The
   "only-route" setting provides a more permissive alternative.  In the
   case that an S-BGP speaker lacks the public key required for RA
   verification, the "no-verify" setting requires an RA but no
   cryptographic verification is performed.  The "no" policy setting
   allows for speakers to accept UPDATEs from neighboring speakers that
   are not S-BGP capable.  If, however, the "no" policy is set and an
   UPDATE that contains RAs is received, then the RAs are processed and
   verified.


C.5.3  new-speaker

   A "new speaker" is an RA signer for which there is no public key in
   the database.  The "new-speaker" policy directs an S-BGP speaker to
   either reject or accept an UPDATE that cannot be verified due to a
   missing public key.  This policy is applied at the global and AS
   levels, and available settings include:

      reject      Reject routes received for which there is no public
                  key.
      accept      Accept routes received for which there is no public
                  key.
      only-route  Accept routes received for which there is no public
                  key when no other verified route for a prefix exists.

   The default policy setting is "reject".  Strict security requires the
   successful verification of all received routes.  A more permissive
   alternative is the "only-route" setting.  The "accept" setting is
   useful when an AS forgets to renew an expired key, or starts sending
   RAs before the public key has been propagated throughout the
   Internet.


C.5.4  new-prefix

   A "new prefix" is a prefix for which a speaker has no origination AA
   information.  The "new-prefix" policy instructs an S-BGP speaker how
   to handle a received UPDATE that contains a prefix for which no AA
   information exists and, therefore, cannot undergo AA verification.


                          Lynn, Mikkelson, Seo                 [Page 67]


                               Secure BGP                      June 2003


   This policy is applied at the global, AS, and prefix levels, and
   available settings include:

      reject      Reject route for a prefix with no AA information.
      accept      Accept route for a prefix with no AA information.

   Policy defaults to the "reject" setting.  The "accept" policy setting
   is useful when a prefix owner has never issued an AA, or fails to
   reissue an expired AA.  This policy only applies when there is no AA
   information for a prefix, not when the authorized originating ASes
   are specified but the route identifies a different originating AS.


C.5.5  send-explicit

   The "send-explicit" policy directs an S-BGP speaker to include, or
   not include, protected path attributes as explicit data within the
   locally generated.  This policy may be applied at the global (i.e.,
   all generated RAs) and speaker (i.e., generated RAs intended for a
   particular peer speaker) levels.  The available settings for this
   policy are:

      yes         Protected path attributes in locally generated RAs are
                  included as explicit data.
      no          Protected path attributes in locally generated RAs are
                  not included as explicit data, i.e., they are implicit
                  data.

   The default setting is "no"; under normal operation when the content
   of a path attribute does not change, an S-BGP speaker should not
   include protected path attributes as explicit in the generated RAs
   prepended to outbound UPDATEs.  Protected path attributes are
   included as explicit data by setting this policy to "yes".  The
   "mask-explicit" policy (see section C.6.4) overrides the "no"
   setting.

   A speaker in a peer AS to which a UPDATE is sent MAY change explicit
   data to implicit prior to the further propagation of the UPDATE to
   reduce the size of the UPDATE if the data has not changed (see
   section C.5.6).


C.5.6  make-implicit

   The "make-implicit" policy directs an S-BGP speaker to change, or not
   change, explicitly protected path attributes in the Last received RA
   in a received UPDATE to implicit data when advertising it to external
   peers.  This only applies to protected path attributes that have not
   been modified by the speaker; all modified path attributes that are
   protected must be included as explicit in the Last received RA.  This
   policy is applied at the global and peer levels, and available


                          Lynn, Mikkelson, Seo                 [Page 68]


                               Secure BGP                      June 2003


   settings include:

      yes         Explicit path attributes in Last received RAs are made
                  implicit.
      no          Explicit path attributes in Last received RAs remain
                  as explicit.

   Under default operations all the data in the ExplicitPA part of the
   Last received RA should be implicit, i.e., the ExplicitPA part is
   empty and this policy setting does not apply.

   The default setting is "yes", which allows a speaker to reduce the
   size of an UPDATE by removing redundant explicit data from the RAs in
   its advertisements.  If all the RAs within an UPDATE included an
   explicit copy of all protected path attributes the UPDATE may grow
   too large for the 4 KB UPDATE limit.  The "no" setting is available
   to allow protected path attributes to remain as explicit within the
   Last received RA.  This may be used when a newly defined transitive
   path attribute is introduced into BGP.  The canonicalized format of
   new path attributes may not be known, and consequently, such path
   attributes should remain explicit in RAs.


C.6.  Extensibility

   The following policy allows an S-BGP speaker to be easily extended to
   handle new transitive BGP path attributes.


C.6.1  mask-require

   The "mask-require" policy specifies the path attributes that must be
   protected within received RAs.  If an RA in a received UPDATE does
   not protect all the path attributes specified by this policy, then
   the route must be rejected.  This policy is applied at the global
   (i.e., all RAs), AS (i.e., RAs generated by or transiting a
   particular AS), and speaker (i.e., RAs generated by a particular
   speaker) levels.  By default, the "mask-require" policy specifies
   that the ORIGIN and AS PATH path attributes, in addition to the NLRI,
   be protected within received RAs because they represent route
   information essential for the operation of S-BGP.


C.6.2  mask-ignore

   The "mask-ignore" policy specifies path attributes that, except for
   the case of signature verification, should not cause a received
   UPDATE to be rejected.  A path attribute to be ignored as indicated
   by this policy does not need to be verified for semantics or correct
   propagation.  However, an ignored but protected path attribute needs
   to be sufficiently valid to result in the successful signature


                          Lynn, Mikkelson, Seo                 [Page 69]


                               Secure BGP                      June 2003


   verification of an RA.  By default, the "mask-ignore" policy is an
   empty set, specifying no path attributes to be ignored during
   verification, and is applied at the global, AS, and speaker levels.


C.6.3 mask-protect

   The "mask-protect" policy specifies the path attributes that must be
   protected within locally generated RAs prepended to outbound UPDATEs.
   This policy is applied at the global and speaker levels.  By default,
   the "mask-protect" policy specifies that all defined transitive path
   attributes be protected in generated RAs.  In addition to the path
   attributes specified by this policy, all path attributes protected by
   the Last received RA must be protected.

   The NLRI, ORIGIN, and AS PATH represent route information essential
   for the operation of S-BGP and should always be protected.  It is
   recommended that other transitive path attributes included within an
   UPDATE be protected, as well, to ensure greater security.  However,
   protection of path attributes that may change frequently from speaker
   to speaker (e.g., communities) increases the size of RAs.  Each time
   that a protected path attribute is modified at a speaker during route
   propagation an explicit copy must be included within the Last
   received RA.  Additionally, splitting an UPDATE that contains an
   attestation path attribute into multiple UPDATEs only results in
   UPDATEs even greater in size because the protected path attributes
   need to be included as explicit data.  This policy allows path
   attributes, particularly those less essential to correct operation,
   to be excluded from protection in consideration of the size and
   growth of UPDATEs.


C.6.4  mask-explicit

   The "mask-explicit" policy directs an S-BGP speaker to include
   specific protected path attributes as explicit date within locally
   generated RAs prepended to outbound UPDATEs.  This policy only
   applies in the case that the "send-explicit" policy (see section
   C.5.5) is set to "no", and is applied at the global and speaker
   levels.  By default, the "mask-explicit" policy does not specify that
   any defined transitive path attributes be included as explicit within
   generated RAs.

   Transitive path attributes protected by S-BGP may need to undergo
   canonicalization prior to signature generation and verification.  Not
   all S-BGP speakers may know the canonicalized format of a path
   attribute, especially in the case of one newly defined, and therefore
   such path attributes should be included as explicit date (in
   canonicalized form) within the RAs generated by the speaker that
   included the path attribute within an UPDATE.  Therefore, this policy
   is important in enabling the incremental deployment of newly defined


                          Lynn, Mikkelson, Seo                 [Page 70]


                               Secure BGP                      June 2003


   path attributes.


C.7.  Incremental Deployment Policy Examples

   When an S-BGP capable router is first installed (before the AS is
   ready to use the S-BGP protections) it should "turn S-BGP off".  The
   following policy settings are used.

      Policy              Level          Setting
      -----------         ------         -------
      enable-AA           global         no
      enable-RA           global         no
      send-attest         global         no

   The next step in deployment, might be to just perform NLRI
   origination verification, but not make any route selections based on
   the results; i.e., just report failures.

      Policy              Level          Setting
      -----------         ------         -------
      enable-AA           global         yes
      require-AA          global         no
      enable-RA           global         no
      send-attest         global         no

   When all the BGP speakers are ready to use the S-BGP protection
   mechanisms to select routes, but peer ASes are not S-BGP capable, the
   speakers may initially only perform AA verification.  Such a speaker
   would use the following policy settings.

      Policy              Level          Setting
      -----------         ------         -------
      enable-AA           global         yes
      enable-RA           global         no
      send-attest         global         no

   Now consider an S-BGP speaker that peers with all non S-BGP capable
   speakers except for speaker x within AS X.  Lets assume that no other
   speakers in AS X are S-BGP capable.  Policy is set as below.

      Policy              Level          Setting
      -----------         ------         -------
      enable-AA           global         yes
      enable-RA           global         yes
      require-RA          global         no
      require-RA          speaker x      yes
      send-attest         global         no
      send-attest         speaker x      yes

   Now, assume that all ASes and their associated speakers are S-BGP


                          Lynn, Mikkelson, Seo                 [Page 71]


                               Secure BGP                      June 2003


   capable except for peer AS Y.

      Policy              Level          Setting
      -----------         ------         -------
      enable-AA           global         yes
      enable-RA           global         yes
      require-RA          global         yes
      require-RA          AS Y           no
      send-attest         global         yes
      send-attest         AS Y           no


C.8.  Summary

   Columns heading abbreviations:
      G  Global
      A  AS
      S  Speaker or peer
      P  Prefix

   A default value is enclosed in [...].

   Policy           Section Class          G A S P  Type    Values
   ---------------  ------- -------------  - - - -  ------- ------
   enable-AA         3.1.1  Activation     X _ _ _  enum    [yes]
                                                            no
   require-AA        3.4.1  Deployment     X X _ X  enum    [yes]
                                                            only-route
                                                            no
   enable-RA         3.1.2  Activation     X _ _ _  enum    [yes]
                                                            no
   require-RA        3.4.2  Deployment     X X X _  enum    [yes]
                                                            no-verify
                                                            only-route
                                                            no
   verify-RA         3.3.1  Tuning and     X _ _ _  enum    receipt
                            Optimization                    [selection]
                                                            background
   new-speaker       3.4.3  Deployment     X X _ _  enum    [reject]
                                                            only-route
                                                            accept
   new-prefix        3.4.4  Deployment     X X _ X  enum    [reject]
                                                            accept
   multi-route       3.3.2  Tuning and     X _ _ X  enum    [all]
                            Optimization                    one
   mask-require      3.5.1  Extensibility  X X X _  bitmask [NLRI]
                                                            [ORIGIN]
                                                            [AS PATH]
                                                            ATOMIC AGG
                                                            AGG
                                                            COMM


                          Lynn, Mikkelson, Seo                 [Page 72]


                               Secure BGP                      June 2003


                                                            DPA
                                                            MPREACH
                                                            EXT COMM
   mask-ignore       3.5.2  Extensibility  X X X _  bitmask NLRI
                                                            ORIGIN
                                                            AS PATH
                                                            ATOMIC AGG
                                                            AGG
                                                            COMM
                                                            DPA
                                                            MPREACH
                                                            EXT COMM
   send-attest       3.1.3  Activation     X _ X _  enum    [yes]
                                                            no
   send-explicit     3.4.5  Deployment     X _ X _  enum    yes
                                                            [no]
   make-implicit     3.4.6  Deployment     X _ X _  enum    [yes]
                                                            no
   mask-protect      3.5.3  Extensibility  X _ X _  bitmask [NLRI]
                                                            [ORIGIN]
                                                            [AS PATH]
                                                            [ATOMIC AGG]
                                                            [AGG]
                                                            [COMM]
                                                            [DPA]
                                                            [MPREACH]
                                                            [EXT COMM]
   mask-explicit     3.5.4  Extensibility  X _ X _  bitmask NLRI
                                                            ORIGIN
                                                            AS PATH
                                                            ATOMIC AGG
                                                            AGG
                                                            COMM
                                                            DPA
                                                            MPREACH
                                                            EXT COMM
   max-origin        3.3.3  Tuning and     X _ X _  percent 75%
                            Optimization
   prefix-class      3.3.4  Tuning and     _ _ _ X  integer 0
                            Optimization
   sign-AS           3.2.1  Configuration  _ _ X _  AS set  null set
   aggregate-any     3.3.5  Tuning and     X _ _ _  enum    yes
                            Optimization                    [no]
   in-cache-depth    3.3.6  Tuning and     X _ X _  integer 1
                            Optimization
   out-cache-depth   3.3.7  Tuning and     X _ X _  integer 1
                            Optimization
   peer-auth         3.2.2  Configuration  X _ X _  enum    BGP
                                                            [System]
                                                            No
   peer-key          3.2.3  Configuration  X _ _ _  integer no key


                          Lynn, Mikkelson, Seo                 [Page 73]


                               Secure BGP                      June 2003


   upload-port       3.2.4  Configuration  X _ _ _  integer




















































                          Lynn, Mikkelson, Seo                 [Page 74]


                               Secure BGP                      June 2003


Appendix D.  NOC Support

   This informational appendix describes operations that a NOC that uses
   S-BGP would perform.

   S-BGP uses out-of-band distribution of Address Attestations,
   Certificate Revocation Lists, and Certificates.  An S-BGP speaker
   will eventually need the public key from the certificate of each RA
   signer, and will eventually need an Address Attestation for each
   prefix in one of its Adj-RIBs-Ins.  There are two tiers in the
   distribution hierarchy.

   The first tier consists of servers at several well-known and highly
   connected locations such as a major peering points or ISPs.  These
   servers are sent certificates and CRLs by the registries and
   organizations given the right to use AS numbers or IP address blocks.
   End organizations that are given the right to use IP address blocks
   create and sign Address Attestations that authorize their provider's
   AS to advertise their address block, and send the AAs to the servers.

   The second tier consists of the NOCs of the organizations that manage
   ASes.  They transfer from the first tier servers the set of AAs,
   certificates, and CRLs.  The NOC then validates the information
   received, digests it, and uploads the digested information to their
   S-BGP speakers.

   This preprocessing by the NOC has several advantages.  First, the
   verification of the AAs, certificates, and CRLs is performed only
   once instead of having each S-BGP speaker duplicate the work.
   Second, digesting the information significantly reduces the volume of
   data that is sent to and stored in the speakers.  Third, by receiving
   pre-validated data, the time for the S-BGP speaker to reboot from a
   catastrophic loss of memory is significantly reduced.  Forth, in the
   event of a catastrophic loss of inter-AS routing, the information can
   still be uploaded to speakers using intra-AS routing.

   Certification functions performed by the NOC:

      Generate public/private key pair for the AS.

      Send the AS's public key to registry for inclusion in the
      certificate transferring the right to use the AS number to the
      organization.

      Generate public/private key pairs for each authorized S-BGP
      speaker in the AS and issue them each a certificate.  Copies of
      the certificates are sent to an S-BGP repository.

      Generate a public/private key pair for the organization's
      ownership of IP address blocks.  The public key is sent to the IP
      address delegation registry for inclusion in the certificate


                          Lynn, Mikkelson, Seo                 [Page 75]


                               Secure BGP                      June 2003


      transferring the right to use the address blocks to the
      organization.


Intellectual Property Rights

   The IETF takes no position regarding the validity or scope of any
   intellectual property or other rights that might be claimed to
   pertain to the implementation or use of the technology described in
   this document or the extent to which any license under such rights
   might or might not be available; neither does it represent that it
   has made any effort to identify any such rights.  Information on the
   IETF's procedures with respect to rights in standards-track and
   standards-related documentation can be found in BCP-11.  Copies of
   claims of rights made available for publication and any assurances of
   licenses to be made available, or the result of an attempt made to
   obtain a general license or permission for the use of such
   proprietary rights by implementors or users of this specification can
   be obtained from the IETF Secretariat.

   The IETF invites any interested party to bring to its attention any
   copyrights, patents or patent applications, or other proprietary
   rights which may cover technology that may be required to practice
   this standard.  Please address the information to the IETF Executive
   Director.


Full Copyright Statement

   This document and translations of it may be copied and furnished to
   others, and derivative works that comment on or otherwise explain it
   or assist in its implementation may be prepared, copied, published
   and distributed, in whole or in part, without restriction of any
   kind, provided that the above copyright notice and this paragraph are
   included on all such copies and derivative works.  However, this
   document itself may not be modified in any way, such as by removing
   the copyright notice or references to the Internet Society or other
   Internet organizations, except as needed for the purpose of
   developing Internet standards in which case the procedures for
   copyrights defined in the Internet Standards process shall be
   followed, or as required to translate it into languages other than
   English.

   The limited permissions granted above are perpetual and will not be
   revoked by the Internet Society or its successors or assigns.

   This document and the information contained herein is provided on an
   "AS IS" basis and THE INTERNET SOCIETY AND THE INTERNET ENGINEERING
   TASK FORCE DISCLAIMS ALL WARRANTIES, EXPRESS OR IMPLIED, INCLUDING
   BUT NOT LIMITED TO ANY WARRANTY THAT THE USE OF THE INFORMATION
   HEREIN WILL NOT INFRINGE ANY RIGHTS OR ANY IMPLIED WARRANTIES OF


                          Lynn, Mikkelson, Seo                 [Page 76]


                               Secure BGP                      June 2003


   MERCHANTABILITY OR FITNESS FOR A PARTICULAR PURPOSE.


Author's Addresses

   Charles Lynn
   BBN Technologies
   10 Moulton Street
   Cambridge, MA  02138
   USA
   E-mail: CLynn@BBN.Com
   Telephone: 617-873-3367

   Joanne Mikkelson
   BBN Technologies
   10 Moulton Street
   Cambridge, MA  02138
   USA
   E-mail: JMMikkel@BBN.Com
   Telephone: 617-873-4598

   Karen Seo
   BBN Technologies
   10 Fawcett Street
   Cambridge, MA  02138
   USA
   E-mail: KSeo@BBN.Com
   Telephone: 617-873-3152

























                          Lynn, Mikkelson, Seo                 [Page 77]


Html markup produced by rfcmarkup 1.129d, available from https://tools.ietf.org/tools/rfcmarkup/