[Search] [txt|pdf|bibtex] [Tracker] [Email] [Diff1] [Diff2] [Nits]

Versions: 00 01 02                                                      
Network Working Group                                           R. White
Internet-Draft                                             Cisco Systems
Expires: November 20, 2005                                  May 19, 2005


Architecture and Deployment Considerations for Secure Origin BGP (soBGP)
                   draft-white-sobgp-architecture-01

Status of this Memo

   By submitting this Internet-Draft, each author represents that any
   applicable patent or other IPR claims of which he or she is aware
   have been or will be disclosed, and any of which he or she becomes
   aware will be disclosed, in accordance with Section 6 of BCP 79.

   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 Internet-Draft will expire on November 20, 2005.

Copyright Notice

   Copyright (C) The Internet Society (2005).

Abstract

   There is a great deal of concern over the security of internetworks
   built using the Border Gateway Protocol to provide routing
   information to autonomous systems connected to the internetwork.
   This draft provides an architecture for a secure distributed registry
   of routing information to address these concerns.  The draft begins
   with an overview of the operation of this system, and then follows
   with various deployment scenarios, starting with what we believe will
   be the most common deployment option.




White                   Expires November 20, 2005               [Page 1]


Internet-Draft       soBGP Architecture & Deployment            May 2005


1.  Motivation

2.  Overview

   There are two fundamental pieces of a routing system that need to be
   secured:

   o  Adjacencies between devices running the routing protocol.
   o  Information carried within the routing protocol.

   While security between [BGP] speakers has been addressed in a number
   of ways, including cryptographic authentication [BGP-MD5] and
   limiting the attack radius through TTL mechanisms [GTSH], security
   for the information carried within BGP is not considered a solved
   problem.

   This draft proposes a possible solution to securing the information
   within BGP, using the certificates and protocol extensions proposed
   in [SOBGP-BGPTRANSPORT], [SOBGP-CERTIFICATE], and [SOBGP-RADIUS].

   There are three major modifications to this draft since the last
   edition was published

   o  An additional short section has been added on the impact of soBGP
      on internetwork convergence.  This is a rough cut at an analysis
      of this work, at this point.
   o  An additional section on incremental deployment, in terms of
      deploying parts of the soBGP system to solve specific problems.
   o  A section on aggregation considerations has been added.

3.  General Theory

   soBGP provides a secure registry mechanism against which a BGP
   speaker can check:

   o  The authorization of the AS listed as the originating AS in any
      received update to advertise reachability to the prefix listed in
      the update.
   o  The validity of the AS Path contained in the update.

   A valid AS Path, in this document, is a path that has the following
   attributes:

   o  Each autonomous system listed in the AS Path is an actual
      participant in the internetwork.
   o  Each pair of autonomous systems listed in the AS Path are actually
      interconnected.




White                   Expires November 20, 2005               [Page 2]


Internet-Draft       soBGP Architecture & Deployment            May 2005


   o  Starting from the first autonomous system (the origin AS), and
      passing through each autonomous system listed in the AS Path,
      actually results in reaching the advertising peer's AS.

   As shown in [PATH-CONSIDER], it isn't possible to verify an AS more
   than one AS hop away has authorized the advertisement of specific
   reachability information based on the AS Path.  The concept of
   policy, and soBGP's interaction with policy, is considered more fully
   in a later section in this draft.

   soBGP operates by distributing a set of signed certificates,
   described in [SOBGP-CERTIFICATE], containing the information required
   to validate the two pieces of information given above.  These
   certificates MAY be distributed using the mechanisms described in
   [SOBGP-BGPTRANSPORT], or some other mechanism.  Once these
   certificates have been received and processed (signatures validated,
   etc, as described in [SOBGP-CERTIFICATE], they form a database
   containing:

   o  A listing of IP address blocks and the AS authorized to originate
      them.
   o  Policies related to specific prefixes and blocks of addresses.
   o  A list of autonomous systems connected to each autonomous system
      within the internetwork.  This connection list is used to build a
      graph of AS interconnectivity within the internetwork, as
      described in the section Building the AS Connectivity Graph,
      below.

   This effectively forms a secure registry of routing information which
   can be used to check the validity of routing information received
   from BGP peers.  This database is termed the "authorization
   database."  No assumption about the location of the authorization
   database is made within this document.

   As BGP updates are processed, a security preference is assigned to
   each prefix, as described further in the Security Preference section
   of this document.  BGP update processing is described in the
   Receiving and Processing Updates section of this document.

4.  soBGP Operation

   Each section below provides detailed information on some aspect of
   soBGP operation.

4.1  Building the AS Connectivity Graph

   Each ASPolicycert advertised by a member of the internetwork contains
   a list of the autonomous systems the advertising AS is connected to,



White                   Expires November 20, 2005               [Page 3]


Internet-Draft       soBGP Architecture & Deployment            May 2005


   along with possible policy information about that connection.  From
   this information, a graph of AS connectivity within the internetwork
   is built.

   Any AS can be used as the starting point for building this graph,
   thus multiple disconnected graphs (representing section of the
   internetwork running soBGP and providing interconnection information)
   are possible.  If every AS within the internetwork is providing
   interconnection information, one graph can be built containing all
   the internetwork's interconnections.

   The process of creating this graph is:

   o  Begin with the local AS, or any AS for which an ASPolicycert is
      available.
   o  Examine the list of connected autonomous systems advertised by the
      current AS.
   o  Examine the ASPolicycert of each AS the current AS is advertising
      as connected, and determine if that AS is advertising a connection
      back to the current AS.  This is termed the two way connectivity
      check.
   o  If the two way connectivity check passes, the connection SHOULD be
      added to the interconnection graph, and marked as trustable.
   o  If the two way connectivity check fails, the connection MAY be
      added to the interconnection graph, but marked so a lower security
      preference will be assigned to routes containing this AS pair in
      their AS Path.
   o  Apply any policies indicated by either of the two autonomous
      systems in their ASPolicycert.  This could include, for instance,
      noting the connected autonomous system MUST NOT be used for
      transiting traffic.
   o  Repeat this process for each ASPolicycert in the authorization
      database.

   The resulting graph is called the internetwork graph.

4.2  Validating Routing Information (The Security Preference)

   soBGP provides a two tier evaluation of routes.  In the first stage,
   a BGP speaker evaluating received routing information would discard
   all routing information found to be false, or not accurately
   representing the internetwork as it exists.  Routing information not
   meeting this criteria SHOULD be discarded, as indicated in the
   processing steps outlined below.

   In the second tier, the BGP speaker assigns a Security Preference to
   the received routing information, indicating a locally significant
   trust level determined by examining the received routing information.



White                   Expires November 20, 2005               [Page 4]


Internet-Draft       soBGP Architecture & Deployment            May 2005


   The amount by which the Security Preference is increased or decreased
   for any operation described in this draft is locally significant to
   the autonomous system.  This allows the operator provide a finer
   granularity of security policy, from dropping routing information
   deemed invalid through simply preferring routes the operator deems
   "more secure."

   The operator MAY configure a lower bound.  Routes with Security
   Preferences under this lower bound SHOULD be discarded.  Any of the
   following methods may be used to implement the Security Preference
   within an autonomous system:

   o  Assign the value of the Security Preference to any of the
      attributes used in the [BGP] decision process.  Care must be taken
      with attributes for which the lower value is preferred.
   o  Use a Cost Community [COST] and its associated methods to consider
      the Security Preference at any step in the Decision Process [BGP]
      without overloading other attributes.  Care must be taken as the
      lowest value in a Cost Community is preferred.

   Several basic rules apply to all BGP speakers either evaluating the
   security level of received routing information, or using the Security
   Preference to determine which path to install in the local RIB:

   o  The method selected to implement the Security Preference MUST be
      consistent through the local autonomous system.
   o  All devices processing routes against soBGP information MUST use
      the same mechanisms and values of the Security Preference to
      ensure consistent routing within the autonomous system.
   o  The Security Preference value may be used to select among
      different routes for the same prefix; the higher value MUST be
      preferred.

   The process described below does not rule out additional policies
   added locally, or in some future draft.  For each route (prefix/
   attribute pair) within a given BGP UPDATE message:

   o  The local authorization database is examined, and the Authcert
      with the longest prefix length encompassing the range of addresses
      described by the prefix is chosen.
   o  If there is no entry in the local authorization database which
      encompasses the range of addresses described by the prefix, then
      the route is said to be unverified.  The Security Preference
      SHOULD be set to a level indicated by local policy.
   o  If there is an AS_SET in the AS_PATH, the following process MAY be
      followed:





White                   Expires November 20, 2005               [Page 5]


Internet-Draft       soBGP Architecture & Deployment            May 2005


      *  For each AS in the AS_SET, examine the set of PrefixPolicycerts
         advertised by that AS.
      *  If a PrefixPolicycert is found authorizing at least one of the
         autonomous systems in the AS_SET to advertise some component of
         the prefix, the Security Preference MAY be increased or left at
         its current value.
      *  If a PrefixPolicycert is not found authorizing at least one of
         the autonomous systems in the AS_SET to advertise some
         component of the prefix, the Security Preference MAY be
         decreased or left at its current value.
      *  If a path exists from the aggregator to each AS listed in the
         AS_SET, the Security Preference MAY be increased or left at its
         current value.
      *  If a path does not exist from the aggregator to each AS listed
         in the AS_SET, the Security Preference MAY be decreased or left
         at its current value.
   o  If there is an AS_SET in the AS_PATH, it is disregarded in all
      further processing.  The originator of the AS is considered the
      originator of the route.
   o  The second hop in the AS_PATH attribute is examined.
   o
      *  If the second hop in the AS_PATH is advertised as connected by
         the originating AS, the Security Preference for this prefix
         SHOULD be increased.
      *  If the second hop in the AS_PATH is not advertised as connected
         by the originating AS, the Security Preference for this prefix
         SHOULD be decreased.
      *  If the second hop in the AS_PATH is not advertised as connected
         by the originating AS and the originator's policy indicates the
         second hop MUST be validated, the prefix SHOULD be removed from
         further consideration.
   o  The AS_PATH attribute is compared to the internetwork graph.
   o
      *  If a series of two way verified pairwise peerings exists,
         beginning with the first AS listed in the AS_PATH, and ending
         in the advertising AS, the Security Preference SHOULD be
         increased.
      *  If a series of pairwise peerings exists, beginning with the
         first AS listed in the AS_PATH, and ending in the advertising
         AS, the Security Preference MAY be increased.  This case allows
         for the inclusion of one-way advertised AS interconnections in
         the graph.
      *  If the AS_PATH described is not contained within the
         internetwork graph, and the originator indicated the AS_PATH
         MUST be checked, the prefix SHOULD be removed from further
         consideration.





White                   Expires November 20, 2005               [Page 6]


Internet-Draft       soBGP Architecture & Deployment            May 2005


      *  Otherwise, the Security Preference SHOULD be decreased.
   o  The Authcert chosen at the first step is examined.
   o
      *  If the authorized AS in the Authcert matches the originating AS
         in the AS_PATH, the Security Preference SHOULD be increased.
      *  If the authorized AS in the Authcert does not match the
         originating AS in the AS_PATH, the prefix SHOULD be removed
         from further consideration.

4.3  Validating Received BGP UPDATES

   As BGP UPDATES are received, they MAY be processed at one of several
   points:

   o  Each prefix may be validated according to the process outlined in
      Validating Routing Information before they are installed in the
      ADJ-RIB-IN.
   o  Each prefix may be validated according to the process outlined in
      Validating Routing Information after they are installed in the
      ADJ-RIB-IN, but before they are considered in the BGP Best Path
      calculation.
   o  Each prefix may be validated according to the process outlined in
      Validating Routing Information after they are run through the Best
      Path algorithm, but before they are installed in the local RIB.
   o  Routes may be installed in the local RIB, and then validated using
      the process outlined in Validating Routing Information.  Once
      validation is accomplished, adjustments to the local RIB and
      routes advertised to BGP peers may need to be adjusted.

4.4  Requirements for Systems Running soBGP

   This section describes requirements for autonomous systems running
   soBGP, requirements for BGP speakers forming external adjacencies
   from within such autonomous systems, and devices exchanging soBGP
   certificates.

   o  Any peering session along the border of an autonomous system
      running soBGP SHOULD be authenticated through some means such as
      [BGP-MD5], IPsec ([ESP], [AH]), or through some other current,
      effective means of protecting BGP sessions from being hijacked, or
      otherwise abused.
   o  Any peering session along which soBGP certificates are exchanged
      SHOULD be authenticated through some means such as [BGP-MD5],
      IPsec ([ESP, [AH]), or through some other current, effective means
      of protecting BGP sessions from being hijacked, or otherwise
      abused.





White                   Expires November 20, 2005               [Page 7]


Internet-Draft       soBGP Architecture & Deployment            May 2005


   o  For each received route, the last (most recently added) autonomous
      system MUST be compared to the autonomous system of the BGP
      speaker advertising the route.  If the last (most recently added)
      AS in the AS Path does not match the autonomous system of the
      transmitting speaker, the route MUST be discarded.

   When soBGP is supported, a BGP speaker MUST have access to the
   authorization database.  Possible methods of access include:

   o  Have a local copy of this authorization database, and perform the
      checks described later in this document against that local
      database.
   o  Pass received routing information to a locally maintained server
      for validation against that server's copy of the authorization
      database [SOBGP-RADIUS].
   o  Accept filters built from a copy of the authorization database
      contained on a locally maintained server.

5.  soBGP Deployment

   This section begins by describing what we believe to be the most
   practical deployment of this secure registry of routing information.
   Following sections describe some other deployment options that may
   prove useful in some situations, or may prove to be more practical
   than the deployment outlined in this section.

5.1  Deploying soBGP on Distributed Registry Servers

   This deployment scenario works within three constraints:

   o  It may not be not desirable to combine routing and cryptographic
      processing of soBGP certificates on the same device.
   o  The system should be distributed, using as few centralized
      resources as possible.
   o  Trust relationships should be based on existing business and
      working relationships, rather than building new relationships
      specifically for securing the routing system.

   Assume we have a small internetwork, as shown below:
   S1 - - - - - - - - - - -S2 - - - -S3
   10.1.1.0/24---A---B-----C---D-----E---F
   | AS65000            | AS65001 | AS65002

   In this network, we assume each AS has an soBGP server locally within
   their AS, marked as S1, S2, and S3, above.  These servers are
   interconnected in a way similar to eBGP peering between AS65000,
   AS65001, and AS65002; S1 and S2 are using the mechanisms described in
   [SOBGP-BGPTRANSPORT] to distribute the certificates described in



White                   Expires November 20, 2005               [Page 8]


Internet-Draft       soBGP Architecture & Deployment            May 2005


   [SOBGP-CERTIFICATE] between them.

   Each server then processes the certificates as described in [SOBGP-
   CERTIFICATE], and either provides a set of filters or a mechanism
   through which the eBGP peering routers can authenticate routing
   information, such as described in [SOBGP-RADIUS].  This deployment
   technique provides BGP route validation that is:

   o  Fully Distributed: Local server (or set of servers) which builds
      the required databases based on received certificates, and
      distributes certificates throughout the routing system.
   o  Locally Controlled: Each local server (or set of server) is
      maintained and managed by autonomous systems participating in the
      internetwork.
   o  Based on Existing Business Relationships: Peering autonomous
      systems also peer their soBGP servers, so the system uses existing
      business relationships to provide the deployment and long term
      maintenance of the system.
   o  Very Little Impact on the Existing Routing System: The current
      processing and distribution of routing information through [BGP]
      isn't impacted in any way.  The only additional requirements on
      existing equipment are to compare the routing information to the
      database results provided by the local servers (i.e., receiving
      and processing filter lists, or through [SOBGP-RADIUS]).

5.2  Certificate Processing on Edge Peering Routers

   soBGP can also be deployed entirely within BGP speakers at the edge
   of an Autonomous System (AS).

         +-(eBGP)-+           +-(eBGP)-+
         |        |           |        |
         v        v           v        V

         A--------B-----C-----D--------E

                  ^           ^
                  |           |
                  +--(iBGP)---+

   In this network, A is sending certificates it has learned from other
   sources to B using the mechanisms described in [SOBGP-BGPTRANSPORT].
   B is passing these certificates to D via iBGP, and D is passing these
   certificates to E via eBGP.  Each edge router, B and D, process these
   certificates locally, building the databases required to validate
   received routing information from them.





White                   Expires November 20, 2005               [Page 9]


Internet-Draft       soBGP Architecture & Deployment            May 2005


5.3  Multihoming Deployment

   Multihoming presents a special challenge to the deployment of soBGP
   within a large scale internetwork.

           (---------)            (---------)
          (  AS65401  )          (  AS65402  )
         (             )        (             )
          (           )          (           )
            (---A---)              (---B---)
                |                      |
                 \                    /
                  \-----+      +-----/
                        |      |
                     (--C------D--)
                    (              )
                     (   No-AS    )
                      (----------)

   Assume No-AS has obtained a block of addresses, 10.1.1.0/24, from
   AS65401, and would like to advertise that same block of addresses
   through AS65402.  Since No-AS has no AS number, it cannot generate
   any soBGP certificates, and must rely on its upstream providers to
   work out the security impact in some way.  The simplest solution
   would be, of course, for NOAS to obtain an AS number, and fully
   participate in soBGP, but barring that, what other solutions are
   there?

   AS65401 could issue a certificate allowing AS65402 to originate just
   the prefix in question, 10.1.1.0/24, or AS65401 could simply list
   AS65402 in the certificate covering 10.1.1.0/24 as an authorized
   originator for this address space (as multiple authorized originators
   are allowed).

5.4  Proxy Advertisement of Certificates

   Note there is no requirement for a given entity which originates
   routes into the routing system to actually originate the
   corresponding certificates required for the correct origination of
   the route to be validated, and the AS Path attached to the route to
   be verified.










White                   Expires November 20, 2005              [Page 10]


Internet-Draft       soBGP Architecture & Deployment            May 2005


                   (-----------------)
                  ( Other Third Party )
                    (---------------)
                     /              \
                    /                \
           (---------)            (---------)
          (  AS65401  )          (  AS65402  )
         (             )        (             )
          (           )          (           )
            (---A---)              (---B---)
                |                      |
                 \                    /
                  \-----+      +-----/
                        |      |
                     (--C------D--)
                    (              )
                     (  AS65403   )
                      (----------)

   In this case, AS65401, AS65402, or some other third part may actually
   advertise the certificates necessary for AS65403 to originate
   validated routes.

6.  Other Considerations

   In this section, we move from specific deployment scenarios to other
   deployment considerations, such as key generation and protection, and
   memory utilization/impact.

6.1  Certificate Generation and Private Key Protection

   There is only one private/public key pair per autonomous system;
   certificates are generated as determined by local policy and as
   required to account for changes in the network.  Since the entity's
   private key is not used in any part of the operations verifying
   received information, or in generating information to transmit to
   other devices, these certificates could be generated on some secure
   central system in the AS, and the results, containing only public
   keys, can be transmitted throughout the network.

   Securing the private key of each entity should be relatively easy in
   this environment, since the location of the private key can be
   carefully constrained; no device other than the system which
   generates the required certificates needs use of the private key.

6.2  Impact on Performance and Memory Utilization

   Detailed performance and memory utilization characteristics of soBGP



White                   Expires November 20, 2005              [Page 11]


Internet-Draft       soBGP Architecture & Deployment            May 2005


   will be the subject of future investigation.  However, as this is an
   important area of consideration, we present some suggested analysis
   below.  (In other words, this is a guess).

   In terms of memory, each device running soBGP will need to store:

   o  Each of the Entitycerts Received.  The maximum number of
      Entitycerts within the routing system would be the number
      participating autonomous systems multiplied by the number of
      outstanding Entitycerts from each autonomous system.
   o  Each of the ASPolicycerts Received.  The number of ASPolicycerts
      within the system will probably be similar to the number of
      Entitycerts within the system.
   o  Each of the PrefixPolicycerts Received.  The number of
      PrefixPolicycerts within the system will depend on the number of
      address blocks each participant in the routing system advertises,
      and could double during key rollover.

   Performance will depend on the cryptographic processing requirements
   imposed by the certificate signature methods, as described in [SOBGP-
   CERTIFICATE].  However, all of this additional memory and processing
   would most likely be required on a distributed soBGP server, rather
   than on routers themselves.

   The primary impact on routers and routing protocol convergence will
   be the memory and processing requirements added from the additional
   route filters or processing as required by the deployment technique
   used.

6.3  soBGP Impact on Internetwork Convergence

   We generally assume that adding a security infrastructure on top of
   an operating system will dramatically decrease the performance of
   that system.  However, much depends on the system being modified,
   itself, and how closely to perfectly efficient that system already
   performs.  We've already examined, in prior sections, the impact of
   soBGP on memory and processor utilization in devices running these
   extensions, but we've not examined the impact of soBGP on another
   aspect of an internetwork's operation, convergence time.  In this
   section, we will examine some possible side effects of deploying
   soBGP using the following small internetwork as an example.
   +--B--C--D--+
   |           |
   A---E---F---G---K
   |           |
   +-----H-----+

   In this network, assume that:



White                   Expires November 20, 2005              [Page 12]


Internet-Draft       soBGP Architecture & Deployment            May 2005


   o  A prefers the path through {H,G} to K.
   o  E prefers the path through {F,G} to K.
   o  B prefers the path through {C,D,G} to K.

   In this network, if the link from G to K fails:

   o  A will first receive a withdraw from H, and begin to prefer the
      path through {E,F,G} to K.
   o  A will then receive a withdraw from E, and begin to prefer the
      path through {C,D,E,G} to K.
   o  A will finally receive a withdraw from C, and remove the route to
      K from its local tables.

   This processing pattern is well documented through multiple studies
   in the operations of [BGP] in large scale internetworks.  The most
   obvious answer to resolve this problem is for G to include some sort
   of information in its withdraw indicating the nature of the failure,
   so A can directly remove all paths through the link {G,K} on
   receiving the first withdraw.  This is more problematic than it
   appears, however, because [BGP] is designed for protocol efficiency,
   and withdraws are often removed from the internetwork, along with any
   information they might contain, at an early point in the convergence
   process.

   The mechanism soBGP uses to build a graph of the interconnections
   between the autonomous systems in the internetwork, however, provide
   another place where this sort of direct information about changes in
   the topology of the internetwork can be distributed.  If this network
   were running soBGP, G would be able to reissue its certificate
   claiming connectivity to K, or use some specific policy indicator to
   note the link {G,K} has failed.  On receiving this certificate, all
   the autonomous systems could remove all routes with the link {G,K} in
   their AS Paths, and the network would converge with much less
   distribution and processing of routing information.

   We believe there are probably several performance enhancements that
   may be gained through the laying of a connectivity graph on top of
   the current [BGP] provided view of an internetwork.  These types of
   efficiency gains may overcome or fully offset the added costs of
   deploying soBGP as a security system.

6.4  Aggregation

   Aggregation is a diificult problem within any system attempting to
   validate routes in an internetwork running BGP.  The primary purpose
   of aggregation is to remove information from the routing system, and
   information removed from the system cannot be validated or verified.
   This appears to be a simple observation, but it has a number of far



White                   Expires November 20, 2005              [Page 13]


Internet-Draft       soBGP Architecture & Deployment            May 2005


   reaching impacts.

   (   AS1   )  (AS4) (AS5)
   10.1.0.0/24----A-----+
                        |
   (   AS2   )          |  (AS5)
   10.1.1.0/24----------B----C
                        |
   (   AS3   )          |
   10.1.2.0/24----------+

   In this small internetwork, B is aggregating 10.1.0.0/24,
   10.1.1.0/24, and 10.1.2.0/24, into a single advertisement,
   10.1.0.0/22, towards C, using the mechanism described in [BGP].  C
   receives 10.1.0.0/22 with the combined communities of 10.1.0.0/24,
   10.1.1.0/24, and 10.1.2.0/24, and an AS Path of {(1,2,3,4),5}.  What
   information can C learn from this advertisement?

   o  10.1.0.0/22 is an aggregate, and AS5 claims it has learned some
      component of 10.1.0.0/22 through or from AS1, AS2, AS3, or AS4.
   o  AS5 claims to be able to reach AS1, AS2, AS3, and AS4.
   o  AS5 claims it can reach any existing destination within
      10.1.0.0/22, given no other longer prefix route to a component of
      this address space exists.
   o  AS5 is authorized to advertise 10.1.0.0/22.
   Can C validate any of these pieces of information?

6.4.1  The Route is an Aggregate

   C assumes 10.1.0.0/22 is an aggregate because of the AS Set contained
   in the AS Path; is there any way to validate this claim?  If C has
   the PrefixPolicycerts for 10.1.0.0/24, 10.1.1.0/24, and 10.1.2.0/24,
   it would be able to determine that some of the components of
   10.1.0.0/22 are, in fact, owned by at least some of the autonomous
   systems listed in the AS Set. This ability, however, is dependant on
   C having at least one PrefixPolicycert from AS1, AS2, or AS3, which
   depends on all certificates being flooded throughout the
   internetwork, regardless of the flow of routing information.  If
   certificates are blocked when route aggregation or filtering is
   performed at B, C will not have these certificates.

   Therefore, we can prove a route is actually an aggregate, if we have
   at least one PrefixPolicycert from one of the autonomous systems
   listed in the AS Set, and that PrefixPolicycert contains at least
   some component of the advertised aggregate.  C cannot, however,
   definitively prove the route is not an aggregate, because it cannot
   know if it simply does not have such a certificate, or if the
   aggregate isn't really an aggregate.



White                   Expires November 20, 2005              [Page 14]


Internet-Draft       soBGP Architecture & Deployment            May 2005


   If it is the policy of the internetwork in which soBGP is deployed to
   require all certificates to be flooded to all autonomous systems,
   soBGP MAY use this test to verify a route is actually an aggregate.

6.4.2  Reachability to the Members of the AS Set

   If C has the ASPolicycerts of AS1, AS2, AS3, AS4, and AS5, its local
   connectivity graph of the internetwork is going to include these
   autonomous systems.  In this case, C could verify AS5 can reach each
   of the autonomous systems included in the AS Set. Note, however, that
   in highly meshed internetworks, reachability will exist between
   almost every pair of nodes through multiple paths, so C cannot prove
   AS5 should be advertising the received aggregate along this link, or
   peering session.

   If it is the policy of the internetwork in which soBGP is deployedto
   require all certificates to be flooded to all autonomous systems,
   soBGP MAY use this test to verify connectivity between an aggregator
   and the autonomous systems listed in the AS_SET of a received
   aggregate.

6.4.3  Reachability to All Destinations Within the Aggregate

   Can C prove AS5 is able to reach every possible destination with
   10.1.0.0/22?  Assume C has PrefixPolicycerts from AS1, AS2, AS3, AS4,
   and AS5.  From these PrefixPolicycerts, C could determine AS5 could
   be receiving at least three components of 10.1.0.0/22: 10.1.0.0/24,
   10.1.1.0/24, and 10.1.2.0/24.  However, there is no way to verify AS5
   is actually receiving these components.  For instance:
   o  While AS1 may be authorized to advertise 10.1.0.0/24, and may
      normally advertise 10.1.0.0/24 to AS4, the AS1 to AS4 link may be
      failed, and therefore AS5 may not be receiving this component.
   o  AS1 may be authorized to advertise 10.1.3.0/24, but may not have
      any hosts reachable in that range of addresses, and therefore
      might not be advertising it.
   In other words, AS5 may not be receiving components of a given
   aggregate route because the component doesn't exist, or is not
   reachable through AS5.  Neither of these conditions can be verified
   by C, so AS5's reachability to all the destinations listed within an
   aggregate cannot be verified.

6.4.4  Authorization to Advertise an Aggregate

   There are at least two ways authorization to advertise an aggregate
   could be defined:






White                   Expires November 20, 2005              [Page 15]


Internet-Draft       soBGP Architecture & Deployment            May 2005


   o  The advertising autonomous system is known to have reachability to
      all the components contained within the aggregate, and is
      authorized to aggregate the address space by each of the owners of
      those components.
   o  The advertising autonomous system is authorized to directly
      advertise the address space indicated in the aggregate route.
   The first definition fails on two counts:
   o  There is no way to prove an aggregating autonomous system has
      reachability to every possible component of an advertised
      aggregate.
   o  Given the receiver of an aggregate does not know what the complete
      list of reachable components within an aggregate actually is,
      there is no way for the receiver of an aggregate to know if all
      the component's owners have actually authorized the aggregator to
      advertise the aggregate.

   This leads to the conclusion that authorization to advertise an
   aggregate can only exist in the second sense; that if an autonomous
   system has authorization to advertise the address block (because it
   has a AuthCert authorizing the advertisement of the address block),
   then the autonomous system is authorized to advertize the aggregate.

7.  Incremental Deployment of soBGP

   One of the primary concerns with any security system is the ability
   of users to incrementally deploy the system without impacting current
   network operations.  As the security system is deployed, it should
   provide greater security.  In theory, the amount of additional
   security offered verses the additional work required should be fairly
   balanced.

   There are two aspects of incremental deployment that need to be
   considered:

   o  The impact of some of the participants in the system deploying the
      security system, but not all participants deploy the system.
   o  The impact of some part of the system being deployed widely, but
      not all of the system.

7.1  Not All Connected Networks Participate

   The first consideration in incremental deployment of soBGP is asking
   what happens if all of the autonomous systems in an internetwork
   don't run soBGP.  Is there any advantage to partial deployments of
   soBGP in this sense?

   Throughout this section, we will assume soBGP certificates are
   received by all autonomous systems running soBGP, even if they are



White                   Expires November 20, 2005              [Page 16]


Internet-Draft       soBGP Architecture & Deployment            May 2005


   separated by multiple hops which are not running soBGP.  This is not
   an unreasonable assumption, since soBGP certificates can be shared in
   multiple ways, including multihop BGP sessions across non-
   participating autonomous systems.

   Assume we have the following small internetwork, what impact will
   incrementally deploying soBGP through this network have?
   (AS1) (AS2) (AS3) (AS4             )
     A-----B-----C-----D---10.1.1.0/24

   Assume AS3 and AS4 deploy soBGP, but not AS1 and AS2; is there any
   value?  When AS3 receives routes from AS4, it can verify AS4 is
   authorized to advertise 10.1.1.0/24.  Further, any routes AS3
   forwards to AS4 from AS1 or AS2 can be validated, to some degree, by
   AS4.  The AS Path can be checked to make certain AS2 is actually
   connected to AS3 (since AS3 is advertising its connectivity to AS3).
   If some route is advertised from AS2 showing an AS hop in the middle
   of those two autonomous systems, it can be safely discarded by AS4 as
   an invalid AS Path.

   We can make an alternate assumption, that AS1 and AS4 have deployed
   soBGP, while AS2 and AS3 have not.  In this case, what gains would be
   made by deploying soBGP?  Assume Router A receives a route from
   Router B with an AS Path of {B,C,D}.  If Router A has access to
   Router D's certificates, it can:

   o  Check the origin AS (the first AS in the AS Path, in this case
      AS4) is authorized to advertise the address space (in this case
      10.1.1.0/24).
   o  Check the second hop in the AS Path (in this case AS3) is actually
      attached to AS4, as advertised by AS4.
   o  Since Router A knows it is connected to AS2, through B, it can
      also validate the last AS listed in the AS Path.

   There is some gain, then, in deploying soBGP in both of these
   situations.  The gain is obviously more in the second scenario than
   the first.

7.2  Deploying Parts of soBGP

   The second question concerning incremental deploying is if
   implementing some part of soBGP, without the remainder, would be
   useful.  This question is generally placed in the context of
   validating the origination authorization of routes, and possibly the
   first hop in the AS Path, but not the entire AS Path.






White                   Expires November 20, 2005              [Page 17]


Internet-Draft       soBGP Architecture & Deployment            May 2005


   o  soBGP Authcerts could be advertised or published (for instance, on
      a Web page), to provide authorization for each origin AS to
      advertise specific address blocks.  These certificates could be
      self signed, in the most relaxed case, or signed by the entity
      authorizing the AS to advertise the address block.
   o  soBGP PrefixPolicycerts could be advertised or published (for
      instance, on a web page), to provide authorization and first hop
      checking for received routes.  The Authcert within the
      PrefixPolicycert contains the information required to validate the
      origin's authorization to originate a route.  The list of MAY
      TRANSIT autonomous systems contained in the PrefixPolicycert would
      provide the ability to check the first hop in the AS Path of any
      received route.
   o  soBGP PrefixPolicycerts and ASPolicycerts could be advertised to
      provide authorization to advertise a route from within an address
      block, and also provide the ability to validate the first hop in
      the AS Path.  The Authcert, within the PrefixPolicycert, contains
      the information required to validate the origin's authorization to
      originate a route.  The list of connected autonomous systems
      within the ASPolicycert provides the information required to
      validate the first hop in the AS Path of any received route.

   Any of these modes of operation could be mixed with a full deployment
   of soBGP, and provides checks for the first hop and origination of
   received routes.

8.  Policy Interactions with soBGP

   Beyond simply securing the information contained within the routing
   database [BGP] builds, it's also desirable to have a secure mechanism
   for an autonomous system to advertise policy information.  For
   instance, an autonomous system may not want a specific peer to
   transit traffic, or an originator may want routing information to be
   advertised only to a specific number of AS hops away from the origin.

   The sections below examine some various policies of this type, and
   possible solutions within soBGP.

8.1  Indicating Do Not Transit

   In the following small internetwork, A would like to enforce a policy
   preventing C from transiting traffic from B to A.

        A-------B--------D
        |       |
        +---C---+

   A may attempt to prevent C from transiting traffic from B to A by



White                   Expires November 20, 2005              [Page 18]


Internet-Draft       soBGP Architecture & Deployment            May 2005


   advertising its routing information to C in such a way that C cannot
   readvertise that routing information to B. The problem with this
   approach is that B must assume the lack of specific routing
   information from C indicates A has a local policy forbidding C from
   transiting traffic to A. Unfortunately, because of the nature of
   address space assignment, aggregation, filtering, and other factors,
   B cannot make this assumption.  For instance, C may receive a
   superset of the routing information A is advertising, and advertise
   those routes to B instead, in which case A will find there's no
   effective way to enforce its policy towards C.

   We find, however, that the interconnection graph laid on top of the
   routing information transmitted by each autonomous system provides a
   point where A may communicate its nontransit policy towards C
   directly to B. Using its ASPolicycert, A may indicate B is not a
   transit AS, allowing B to mark routes with the AS pair {B,A} in their
   AS Path with a lower security preference, or possibly even discarding
   such routing information altogether.

   This is a simple application of the policies available in the soBGP
   certificates; more complex policies may be expressed through similar
   means.  The certificates described in [SOBGP-CERTIFICATE] are built
   so policies may be added in the future, as well.

9.  Acknowledgements

   A large number of people contributed to this draft either by
   contributing text, ideas, or comments; we've tried to include all of
   them here (but might have missed a few): James Ng, Tim Gage, Alvaro
   Retana, Dave Cook, Brian Weis, Iljitsch van Beijnum, Bora Akyol, Tony
   Li, and Sue Hares.

10.  Security Considerations

11.  IANA Considerations

12.  References

12.1  Normative References

   [BGP]      Rekhter, Y. and T. Li, "A Border Gateway Protocol 4
              (BGP-4)", RFC 1771, March 1995.

   [SOBGP-BGPTRANSPORT]
              Ng, J., "Extensions to BGP Transport soBGP certificates",
              draft-ng-sobgp-bgp-extensions-01.txt (work in progress),
              April 2004.




White                   Expires November 20, 2005              [Page 19]


Internet-Draft       soBGP Architecture & Deployment            May 2005


   [SOBGP-CERTIFICATE]
              Weiss, B., "Secure Origin BGP (soBGP) certificates",
              draft-weis-sobgp-certificates-01.txt (work in progress),
              October 2003.

12.2  Informative References

   [COST]     Retana, A. and R. White, "BGP Custom Decision Process",
              draft-retana-bgp-custom-decision-00.txt (work in
              progress), October 2002.

   [PATH-CONSIDER]
              White, R., "Considerations in Validating the Path in
              Routing Protocols", draft-white-pathconsiderations-02.txt
              (work in progress), April 2004.

   [SOBGP-RADIUS]
              Lonvick, C., "RADIUS Attributes for soBGP Support",
              draft-lonvick-sobgp-radius-04.txt (work in progress),
              February 2004.


Author's Address

   Russ White, editor
   Cisco Systems

   Email: riw@cisco.com























White                   Expires November 20, 2005              [Page 20]


Internet-Draft       soBGP Architecture & Deployment            May 2005


Intellectual Property Statement

   The IETF takes no position regarding the validity or scope of any
   Intellectual Property Rights 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; nor does it represent that it has
   made any independent effort to identify any such rights.  Information
   on the procedures with respect to rights in RFC documents can be
   found in BCP 78 and BCP 79.

   Copies of IPR disclosures made to the IETF Secretariat 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 implementers or users of this
   specification can be obtained from the IETF on-line IPR repository at
   http://www.ietf.org/ipr.

   The IETF invites any interested party to bring to its attention any
   copyrights, patents or patent applications, or other proprietary
   rights that may cover technology that may be required to implement
   this standard.  Please address the information to the IETF at
   ietf-ipr@ietf.org.


Disclaimer of Validity

   This document and the information contained herein are provided on an
   "AS IS" basis and THE CONTRIBUTOR, THE ORGANIZATION HE/SHE REPRESENTS
   OR IS SPONSORED BY (IF ANY), THE INTERNET SOCIETY AND THE INTERNET
   ENGINEERING TASK FORCE DISCLAIM ALL WARRANTIES, EXPRESS OR IMPLIED,
   INCLUDING BUT NOT LIMITED TO ANY WARRANTY THAT THE USE OF THE
   INFORMATION HEREIN WILL NOT INFRINGE ANY RIGHTS OR ANY IMPLIED
   WARRANTIES OF MERCHANTABILITY OR FITNESS FOR A PARTICULAR PURPOSE.


Copyright Statement

   Copyright (C) The Internet Society (2005).  This document is subject
   to the rights, licenses and restrictions contained in BCP 78, and
   except as set forth therein, the authors retain all their rights.


Acknowledgment

   Funding for the RFC Editor function is currently provided by the
   Internet Society.




White                   Expires November 20, 2005              [Page 21]