Internet DRAFT - draft-white-sobgp-bgp-extensions


Network Working Group                                        Russ White
Internet Draft                                                  (editor)
Expiration Date: March 2003                                Cisco Systems
File Name: draft-white-sobgp-bgp-extensions-00.txt          October 2002

        Deployment Considerations for Secure Origin BGP (soBGP)

   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.  Internet Drafts may be updated, replaced, or obsoleted by
   other documents at any time. It is not appropriate to use Internet
   Drafts as reference material or to cite them other than as a "working
   draft" or "work in progress".

   The list of current Internet-Drafts can be accessed at

   The list of Internet-Draft Shadow Directories can be accessed at

1. Contributors

   A large number of people contributed to this draft; we've tried to
   include all of them here (but might have missed a few). From Cisco,
   James Ng, Tim Gage, Alvaro Retana, and Dave Cook.

White, et. all                                                  [Page 1]

INTERNET DRAFT         Secure Origin BGP (soBGP)            October 2002

2. Abstract

   There is a great deal of concern over the security of routing systems
   within the Internet, particularly in relation to the Border Gateway
   Protocol [BGP], which is used to provide routing information between
   autonomous systems. This draft addresses various deployment scenarios
   and options using the extensions to BGP outlined in [SOBGP-BGP] in
   conjunction with [SOBGP-KEY] (which is not yet completed or
   published) and [SOBGP-RADIUS]. Each section of this draft discusses a
   different deployment situation or deployment option. The final
   section discusses how private key rollovers can be accomplished with
   no loss of routing information within soBGP deployments.

3. Overview of the Deployment Scenarios

   Each section below discusses a possible deployment option for soBGP;
   each could be seen as a separate deployment option, or they could be
   seen as a set of incremental steps from a very simple soBGP
   deployment in a small network to a large soBGP deployment across an

4. Deploying soBGP within Single Devices Along Autonomous System Edges

   In it's simplest form, soBGP can be deployed entirely within BGP
   speakers at the edge of an Autonomous System (AS).

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


            ^           ^
            |           |

   In this network, A is sending all the ECs, SCs, and ACs
   (certificates) it has learned from other sources to B using the
   SECURITY message type. It is passing these certificates to D via
   iBGP, and D is passing these certificates to E via eBGP. Suppose that
   B receives from A an EC for some AS, say 65400, which has been signed
   by a third party that B trusts. B would insert this EC from AS 65400
   into its local EC database.

   B can also use the connected transit AS information contained within

White, et. all                                                  [Page 2]

INTERNET DRAFT         Secure Origin BGP (soBGP)            October 2002

   the SCs to build a directed graph of the internetwork's topology,
   with each AS being a node on the graph.

   Suppose A also advertises an AC authorizing AS 65400 to advertise
   addresses within the block. B would:

        o    Look up the authorizing AS within the AC in the EC data-
             base, and retrieve the validated public key for that AS.
             Verify the signature on the AC using this public key.

        o    Verify that the serial number on the AC falls within the
             range defined by the start AC serial and end AC serial
             within the EC.

        o    If all of these checks pass, enter this AC in its local
             database as being verified and valid.

   Suppose that A advertises some prefix to B,, sourced from
   AS 65400. B would:

o    Look up the prefix within the AC database.

o    Examine the origin AS within the route, verifying it against the
     authorized AS within the AC database.

o    Examine the AS path included with the route, validating that it is
     actually a valid path through the internetwork between the source
     and the local AS.

o    If each of these tests are verified, install the route in the Adj-

5. Deploying soBGP with EC Distribution Within the BGP Protocol and
   Reflection within an AS

   A slightly more complex deployment would continue to distribute the
   entity and authorization certificates through the BGP protocol, using
   the SECURITY message type outlined in [SOBGP-BGP], but would offload
   the work of validating the information to a locally reachable server
   running RADIUS.

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


White, et. all                                                  [Page 3]

INTERNET DRAFT         Secure Origin BGP (soBGP)            October 2002

            ^        / ^
            |       /  |
            |   +-F-+   |
            |  (Server) |
            |   ^   ^   |
            |   |   |   |
         (iBGP)-+   +-(iBGP)

   In this network, A is sending soBGP certificates towards B, along
   with routing updates and other information. While B is peering
   through iBGP with D, it is not sending soBGP certificates through
   this iBGP session; it does not negotiate sending the SECURITY message
   type to D. B is peering through iBGP to F, a server, but only nego-
   tiates carrying the SECURITY message type along this session, so that
   F only receives soBGP certificates, and no routing updates. F
   reflects these soBGP certificates to D, which then transmits them to

   As F receives ECs from B, it will validate the information carried in
   the EC using the signature from a third party it already trusts, and
   places them in a local EC database. F can use the attached transit AS
   information contained in each PC to build a directed graph represent-
   ing the internetwork's topology.

   Suppose A transmits an AC authorizing AS 65400 to advertise prefixes
   within the block:

   o    B would forward this AC on to F.

   o    F would examine its local EC database, and find the EC of the AS
        which authorized 65400 to advertise this block of addresses.

   o    F would use the public key contained within that EC to verify
        the signature on the AC.

   o    F would then check the serial number of the AC against the start
        AC serial number and the end serial number found in the EC.

   o    If these checks succeed, F would place this AC in a local data-
        base of verified ACs.

   Suppose A advertised reachability to to B:

   o    B would build an authorization request, as described in [SOBGP-
        RADIUS], and transmit it to F.

   o    F would examine it's local AC database to determine if it has a

White, et. all                                                  [Page 4]

INTERNET DRAFT         Secure Origin BGP (soBGP)            October 2002

        valid AC which covers this address space.

   o    On finding such an AC, F would then examine the origin AS in the
        advertisement, and determine if the route is, in fact, being
        originated by an authorized AS.

   o    F may also examine the AS path contained in the route and deter-
        mine if this is a valid path through the internetwork.

   o    If the checks succeed, F will build a reply, as described in
        [SOBGP-RADIUS], and transmit this to B.

   o    On receiving the reply, B will install the route in the Adj-

   It is also possible to bypass the edge routers in distributing the
   soBGP certificates within the SECURITY message type.

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

   ^                 /          ^
   |                /           |
   |            +-F-+            |
   |           (Server)          |
   |            ^   ^            |
   |            |   |            |
   +-----(eBGP)-+   +-(eBGP)-----+

   Here, A and B are peering using eBGP, but are only exchanging route
   information, and not the SECURITY message type. A and F are peering
   over a multihop eBGP session, and exchanging only the SECURITY mes-
   sage type. B and D no longer have any security information at all;
   they request information on the validity of any received route from F
   using the method described in [SOBGP-RADIUS].

   Since F is relying only on the interior routing within the local AS
   to reach the edge of the AS (to reach the link between A and B), the
   eBGP multihop session is not relying on routes learned from BGP
   itself to secure BGP.

   The eBGP session which F is learning from could also be multihop to
   another soBGP server in an adjacent AS, rather than to an edge

White, et. all                                                  [Page 5]

INTERNET DRAFT         Secure Origin BGP (soBGP)            October 2002

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

      |                            /
      |                           /          ^
      H                          /           |
   (Server)                  +-F-+            |
      ^                     (Server)          |
      |                      ^   ^            |
      |                      |   |            |
      +---------------(eBGP)-+   +-(eBGP)-----+

   Now, H, A, B, C, D, and E are all exchanging NLRI information only,
   while F and G are exchanging only SECURITY messages. In this case, B
   must be manually configured to trust the route to G learned from A,
   and A must be manually configured to trust the route to F learned
   from B (or they must use static routing, or some sort of temporary
   acceptance of the learned routes until the SECURITY messages are all
   exchanged), to prevent the circularity problem mentioned above. This
   is more complex than the previous deployment options discussed above.

6. Deploying soBGP with EC Distribution Outside the BGP Protocol

   It is also possible to deploy sobGP without carrying any of the ECs
   or SCs within the SECURITY message type within BGP.

                       (         )
                   +----C       D----+
                   |     (-----)     |
     (---------)   |                 |   (---------)
    (  AS65400  )  |                 |  (  AS65402  )
   (             B-+                 +-E             )
    ( Server A  )                       ( Server F  )
     (---------)                         (---------)

   Suppose AS65400 issues an EC signed by a third party, and then issues
   an AC issued by a separate third party (in this case, most likely
   AS65401), authorizing it to advertise addresses within the block. B advertises the AC, in which is embedded a URL to
   the EC which resides on A, to C. C passes this AC through AS65401,
   and advertises it to AS65402 through E. E passes this AC to F.

White, et. all                                                  [Page 6]

INTERNET DRAFT         Secure Origin BGP (soBGP)            October 2002

   F examines this AC, and determines that in order to retrieve the EC
   which is needed to verify it, it must attach to A. The problem here
   is that F cannot reach A at this point; in fact, this is the very
   route it is attempting to verify. Thus, the circularity problem
   prevents soBGP from being deployed in this manner. We can resolve
   this problem by placing a server in AS65401.

                         ( AS65401 )
                        ( Server G  )
                         (         )
                   +----  C       D----+
                   |       (-----)     |
     (---------)   |                   |   (---------)
    (  AS65400  )  |                   |  (  AS65402  )
   (             B-+                   +-E             )
    ( Server A  )                         ( Server F  )
     (---------)                           (---------)

   Now, AS 65401 can provide, as a service to AS65400, the service of
   storing the correct ECs on G. When AS65400 advertises its AC, it can
   place a URL on A and G as the locations of the EC which will validate
   this AC.

   If E and D are configured to trust the path to G and the path to F,
   respectively, then the sequence of events would be:

   o    F receives the AC from AS65400 though iBGP peering with E; E has
        received this AC from D, which obtained it through AS65401's
        peering with AS65400.

   o    F examines this AC, and then attempts to reach the first URL
        listed as a location to retrieve the appropriate EC. Suppose
        this is a URL which resides on A.

   o    After some time, F then attempts to access the second URL, which
        resides on G.

   o    Since the path to and from G are manually configured as trusted
        paths, F reaches G, and retrieves the appropriate EC to validate
        this AC.

   o    Once the EC is retrieved, it is validated by checking the third
        party signature, either from another EC already in the local EC
        database, or through some manually configured local information.

   o    Once the retrieved EC is validated, the AC is validated using
        the public key contained in the EC.

White, et. all                                                  [Page 7]

INTERNET DRAFT         Secure Origin BGP (soBGP)            October 2002

7. Deploying soBGP with Mixed EC Distribution

   The problem with the above deployment mode is readily apparent; there
   could be many such servers as A, F, and G within a large internet-
   work, so it could take a large amount of manual explicit trust confi-
   guration in the various networks to make such a scheme work.

     (---------)            (---------)
    (  AS65401  )          (  AS65402  )
   (             E--------F             )
    ( Server D  )          ( Server G  )
      (---C---)              (---H---)
          |                      |
          |                      |
      (---B---)              (---K---)
     (         )            (         )
    ( Server A  )          ( Server L  )
     ( AS65400 )            ( AS65403 )
      (-------)              (-------)

   For instance, if AS 65400 advertises its AC with a URL which resides
   on D, routers K, H, and F would all need to maintain manual confi-
   guration to prevent circularity. This appears to be unacceptable.

   Instead, however, suppose that AS65401 and AS65402 both advertise the
   ECs necessary to validate the ACs required to reach servers D and G
   through the SECURITY message type in BGP, to their peers. These ECs
   would then propagate to each AS in this internetwork, and could be
   used to validate the ACs required to reach servers D and G.

   Once these paths are validated, A and L could then reach the URLs
   necessary to retrieve other ECs, and validate the remainder of the
   ACs they have received through the SECURITY message type from BGP
   peering sessions. This deployment provides a maximum amount of flexi-
   bility, allowing the amount of information carried within the BGP
   protocol itself to be minimized, and still allowing the routing sys-
   tem to be secured.

White, et. all                                                  [Page 8]

INTERNET DRAFT         Secure Origin BGP (soBGP)            October 2002

8. Incremental Deployment of soBGP

   As the previous sections point out, there are multiple ways to deploy
   soBGP as outlined in [SOBGP-BGP] and [SOBGP-RADIUS]. Each of these
   deployment options may be appropriate in a different stage of deploy-
   ment within an internetwork. In an initial rollout, where few enti-
   ties within the routing system are participating in soBGP, carrying
   all the information within BGP itself, and processing the information
   either on the BGP speakers or on a separate device may work.

   As the entities participating increases, however, it may not be
   advantageous to carry all the ECs available within BGP itself, since
   this could be a very large amount of information. In this case, a
   minimal number of ECs could be carried through BGP, enough to provide
   a framework through which the remaining ECs necessary to secure the
   routing system could be carried.

9. Multihoming Deployment

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

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

   Assume No AS has obtained a block of addresses,, from
   AS65401, and would like to advertise that same block of addresses
   through AS65402. Since NOAS 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 an AC allowing AS65402 to originate just the pre-
   fix in question,, or AS65401 could simply list AS65402 in
   the AC covering as an authorized originator for this

White, et. all                                                  [Page 9]

INTERNET DRAFT         Secure Origin BGP (soBGP)            October 2002

   address space (as multiple authorized originators are allowed).

10. Private Key Rollover

   One of the most complicated problems facing the deployment of a large
   scale internetwork wide security system of this type is in the abil-
   ity for an entity to change private keys without losing routing
   information, or to revoke certain authorized ACs without revoking all
   the ACs it currently has outstanding. This problem is solved in soBGP
   through a set of interlocking serial numbers contained in the various
   soBGP certificates.

   o    Each EC has a serial number

   o    Each EC has a lowest valid serial number

   o    Each EC has a start valid AC serial number

   o    Each EC has an end valid AC serial number

   o    Each PC has a serial number

   o    Each AC has a serial number

   Assume an AS has the following soBGP certificates:

   o    An EC with a serial number of 10, a lowest valid serial number
        of 9, a start valid AC serial number of 20, and an end valid AC
        serial number of 100, and public key A.

   o    An SC with a serial number of 10.

   o    ACs with serial numbers between 20 and 30.

   To replace the current public/private key pair the AS is using:

   o    Generate a new public/private key pair, B, and build an EC from
        the public key and other information required. Assume the new EC
        is given serial number 15, with a new lowest valid serial number
        of 9.

   o    Assume the a start AC serial number is set to 31, and the end AC
        serial number is set to 100.

   o    Have the new EC signed by a trusted third party.

   o    Distribute this new EC.

White, et. all                                                 [Page 10]

INTERNET DRAFT         Secure Origin BGP (soBGP)            October 2002

   o    Generate a new set of ACs with serial numbers of 31 through 40.

   o    Once sufficient time has passed for the new EC to be distributed
        throughout the internetwork, advertise the new ACs.

   o    As the ACs are received by systems running soBGP, they will be
        validated against the new EC which they've previously received,
        and the prefixes advertised by the AS can be revalidated without
        being removed and reinstalled from the Loc-RIB in each device.

   o    Finally, to totally invalidate the older public key (if neces-
        sary), the AS can generate another new EC, using the same
        public/private key pair, B, with a serial number of 16, and a
        lowest valid serial number of 15.

   o    As this EC is distributed throughout the internetwork, the older
        EC, with public key A, will be invalidated as well.

10.1. Revoking Specific Authorization Certificates

   Within each Policy Certificate, it is possible to list Authorization
   Certificates which should no longer be honored. As with all revoca-
   tion lists, however, the revocation list can grow, over time, to
   become unreasonable in size. To resolve this, soBGP allows the ori-
   ginating AS to "clean out" the revocation list while rolling over a
   proviate key. To clean out the revocation list, the originating AS

   o    Issue a new Entity Certificate with a new private key.

   o    Issue new Authorization Certificates with serial numbers higher
        than the current highest numbered Authorization Certificate.

   o    Once the new Authorization Certificates are issued, issue a new
        Entity Certificate with the same public key, but with the same
        Begin Authentication Certificate Serial as the lowest serial
        numbered Authorization Certificate issued above.

   o    Issue a new Policy Certificate with an empty revocation list.

        12. References

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

White, et. all                                                 [Page 11]

INTERNET DRAFT         Secure Origin BGP (soBGP)            October 2002

        Ng J (editor), " Extensions to BGP to Support Secure Origin BGP
        (soBGP)", Draft-ng-sobgp-deployment-00.doc, October 2002

        12. Editor's Address

        Russ White Cisco Systems 7025 Kit Creek Road Research Triangle
        Park, NC 27709 INTERNET DRAFTsoBGP DeploymentOc-
        tober 2002

White, et. all                                                 [Page 12]