Network Working Group                                           R. White
Internet-Draft                                                  B. Akyol
Expires: April 1, 2005                                     Cisco Systems
                                                             N. Feamster
                                                            October 2004


              Considerations in Validating the Path in BGP
                   draft-white-pathconsiderations-04

Status of this Memo

   This document is an Internet-Draft and is subject to all provisions
   of section 3 of RFC 3667.  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 become aware will be disclosed, in accordance with
   RFC 3668.

   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 April 1, 2005.

Copyright Notice

   Copyright (C) The Internet Society (2004).

Abstract

   A good deal of thought has gone into, and is currently being given
   to, validating the path to a destination advertised by BGP.  The
   purpose of this work is to explain the issues in validating a path
   with BGP, in the expectation that it will help in the evaluation of
   schemes such as [SOBGP] and [S-BGP] that seek to improve path
   validation.



White, et al.            Expires April 1, 2005                  [Page 1]


Internet-Draft       Path Validation Considerations         October 2004


   There are many issues we need to consider when securing [BGP],
   including (but possibly not limited to):
   o  The autonomous system (AS) originating an advertisement indicating
      a specific prefix (or block of IP address) space is reachable
      within that AS is authorized, through some mechanism, to advertise
      the prefix.
   o  If an advertisement is withdrawn, the withdrawing AS was
      originally authorized to advertise the prefix.
   o  If an AS receives an advertisement, the peer sending the update
      has a path to the destination prefix in the update.
   o  If an AS receives an advertisement, it is authorized to transmit
      traffic along the AS Path advertised in the update.
   o  If a BGP speaker receives an advertisement, traffic forwarded to
      the peer advertising the update will follow the path described in
      the AS Path.
   o  If an AS receives an advertisement from a peer other than the
      originating AS, the advertising speaker is authorized to advertise
      the entire address block within the advertisement.

   We believe the first issue, proving a path from the BGP speaker
   advertising an update containing a specific prefix to destinations
   within that prefix, is generally provable.  The second issue, proving
   the source of a withdraw is actually authorized to withdraw the
   indicated routing information, is outside the scope of this draft.

   This draft shows these last three assumptions cannot be held to be
   true in a path vector routing system, such as [BGP].

1.  Background

   With the heightened interest in network security, the security of the
   information carried within the routing system is being looked at with
   great interest.  While there are techniques available for securing
   the relationship between two devices exchanging routing protocol
   information, such as [BGP-MD5], these techniques do not ensure
   various aspects of the information carried within routing protocols.
   One issue that cannot be addressed through peer authentication is the
   validity of the path represented by a BGP speaker when advertising
   reachability to a specific prefix.

   To place this in more direct terms, consider this small network.

        10.1.1.0/24--(AS A)---(AS B)--(AS C)

   Assume C has received an advertisement for 10.1.1.0/24 from B, with
   an AS Path of {A, B}.  We can ask four questions about this update:
   o  Does a path actually exist from the advertising router to the
      destination advertised?



White, et al.            Expires April 1, 2005                  [Page 2]


Internet-Draft       Path Validation Considerations         October 2004


   o  Is C authorized, though receiving this advertisement, to transit
      traffic along this path to each reachable destination within the
      prefix advertised?
   o  Will traffic forwarded to some destination within 10.1.1.0/24
      actually follow the path described in the update advertised by B?
   o  Is B actually authorized to advertise this address space to C? In
      other words, is it possible for C to prove A has authorized B to
      readvertise this address space?

   The primary question we would like to examine in this draft is which
   of these four questions can actually be answered within [BGP] or
   other path-vector protocols.  This draft contends that these meanings
   of path validity cannot be verified in [BGP].  We've chosen these
   four items to consider because they represent a fairly focused area
   within [BGP] security, these areas overlap in their understanding of
   the routing system as a whole, and they are easy to understand.
   Beyond this, these considerations may have a large impact on any
   system designed to secure [BG}.

   We will first examine some fundamental concepts of routing and path
   selection in general, then we will proceed through some examples, and
   re-examine each question above in light of each of those examples.
   In each example, we will discuss policy, in terms of an acceptable
   path for the receiver of the traffic (the originator of the
   advertisement) or the transmitter of the traffic.

2.  Analysis

   To begin, we review some of the concepts of routing, since we need to
   keep these concepts fixed firmly in place while we examine these
   questions.  After this, four examples will be undertaken with BGP to
   show why the second of two questions cannot be answered in a path
   vector routing system.  Finally, a short section on transitive
   authorization in a path vector protocol is provided, which considers
   the reasons behind the results we find in the examples.

2.1  A Short Analysis of Routing

   Routing protocols are designed, in short, to discover a set of loop
   free paths to each reachable destination within a network (or
   internetwork).  The loop free path chosen to reach a specific
   destination may not be the shortest path, and it may not always be
   the "best" path (depending on the definition of "best"), but it
   should always be a loop free path, or routing, and the routing
   protocol, has failed.

   This sheds some light on the purpose of the path included in an path
   vector protocol's routing update: the path is there to prove the path



White, et al.            Expires April 1, 2005                  [Page 3]


Internet-Draft       Path Validation Considerations         October 2004


   is loop free, rather than to provide any other information.  While
   Dijkstra's SPF and the Diffusing Update Algorithm (DUAL) both base
   their loop free path calculations on the cost of a path, path vector
   protocols, such as [BGP], prove a path is loop free by carrying a
   list of nodes the advertisement itself has traversed.  [BGP]
   specifically uses an AS Path based mechanism to prove loop freeness
   for any given update so each AS along the path may implement local
   policy without risking a loop in the routing system caused by
   competing metrics.

   We need to keep this principle in mind when considering the use of
   the path carried in a path vector protocol for setting policy.

2.2  First Example: Manual Intervention in the Path Choice

   In the small network:

                     +---(AS C)---+
          (AS A)--(AS B)        (AS E)
                     +---(AS D)---+

   A may receive an advertisement from B that E is reachable along the
   path {B, C, E}.  Based on this information, A may forward packets to
   B, expecting them to take the path described.  However, at B's edge
   router receiving this traffic, the network administrator may have
   configured a static route making the next hop to E the edge router
   with D.

   Although this is an "extreme" example, since we can hardly claim the
   information within the routing protocol is actually insufficient, we
   will still find it instructive to examine this example in light of
   the original three questions:
   o  Does a path actually exist from the advertising router to the
      destination advertised? Yes, it clearly does.
   o  Is C authorized, though receiving this advertisement, to transit
      traffic along this path to each reachable destination within the
      prefix advertised? This question isn't addressed in this example,
      since we have no idea what A or E's policies are.
   o  Will traffic forwarded to some destination within 10.1.1.0/24
      actually follow the path described in the update advertised by B?
      No, traffic forwarded by A towards B will not follow the path
      described in B's update.
   o  Is it possible for A to prove B is authorized to advertise the
      entire address space indicated in the update it received from B?
      This question doesn't come into play in this example, since we are
      not contemplating policy.

   We can safely say there is no way to prove traffic transmitted to a



White, et al.            Expires April 1, 2005                  [Page 4]


Internet-Draft       Path Validation Considerations         October 2004


   BGP peer will actually travel along the path indicated in the BGP
   update.  There is no way to account for the overriding of a routing
   protocol's information through static configuration or through other
   routing protocols running on the same devices, since routing is a hop
   by hop endeavor.

2.3  Second Example: An Unintended Reachable Destination

   Here, we return the small network outlined earlier in this draft.

         10.1.1.0/24---(AS A)---(AS B)---(AS C)

   We will assume, for argument's sake, that A and C are competitors,
   and A would like to prevent hosts within C's network from reaching
   anything within its network.  A has implemented this policy by
   advertising 10.1.1.0/24 to B with some restriction (we can use the
   NO_ADVERTISE community described in [BGP] for this purpose) so B
   cannot readvertise the destination to C.

   However, unknown to A, B is actually advertising a default route only
   to C, and not a full routing table.  If some host within C, then,
   originates a packet destined to 10.1.1.1, what will happen? The
   packet will be routed according to the default route advertised by B.
   When the edge router between B and C receives the packet, it will
   forward the packet along the 10.1.1.0/24 route learned from A,
   forwarding the traffic into A's network.

   Returning to our questions:
   o  Does a path actually exist from the advertising router to the
      destination advertised? Yes, it does.  If B doesn't know of some
      specific host connected to the internetwork, C can assume that
      host doesn't exist, thus the default route is a valid route for B
      to advertise in this case.
   o  Is C authorized, though receiving this advertisement, to transit
      traffic along this path to each reachable destination within the
      prefix advertised? No.  In fact, A has explicitly attempted to
      prevent C from using this path to reach any hosts within its
      network.
   o  Is there any way for C to prove B is authorized to advertise every
      destination reachable as indicated by the prefix in B's
      advertisement towards C? No, there is not.  The default route,
      0/0, actually indicates every possible destination is reachable
      via this path, or via this next hop, and in this case, A has a
      policy stating some destinations contained within the default
      route, 10.1.1.0/24, should not be reachable through B.
   o  Will traffic forwarded to some destination within 10.1.1.0/24
      actually follow the path described in the update advertised by B?
      No.  The path advertised with the default route ends in B, while



White, et al.            Expires April 1, 2005                  [Page 5]


Internet-Draft       Path Validation Considerations         October 2004


      the traffic transits beyond B, into A, which is hidden in the AS
      Path B advertises.

   The basic problem here is that A is assuming that because C doesn't
   receive an advertisement for 10.1.1.0/24, it cannot reach
   10.1.1.0/24.  We can see that lack a lack of specific routing
   information is not equated with a lack of reachability, since B is
   able to advertise a less specific route to C containing the address
   space A controls.  We can extend this concept to say that all
   aggregate routes have this property: There is no way to prove that a
   BGP speaker or AS advertising an aggregate is authorized, by the
   originator of each component of that aggregate, to advertise that
   component.

   This points to a problem with the concept of ownership in a routing
   system, rather than a problem with routing protocols per se, or [BGP]
   specifically.  As long as B can continue to advertise a shorter
   prefix aggregate that consumes A's address space, A cannot set policy
   for the address space it owns.  Ownership in a routing system is not
   specific, but rather overlapping in nature, and thus authorization is
   not transitive in the traditional sense.

2.4  Third Example: Following a Specific Path

   This example is slightly more complex than the last two.  Given the
   following small network:

          10.1.1.0/25--A---B---C---D
                       |       |
                       E-------F

   Assume the following:
   o  A advertises 10.1.1.0/25 to B and E.
   o  B advertises 10.1.1.0/24 to C.
   o  E advertises the aggregate 10.1.1.0/24 to F.
   o  F advertises the aggregate 10.1.1.0/24 to C.
   o  C advertises the aggregate 10.1.1.0/24 to D, but not the more
      specific 10.1.1.0/25.

   There are a number of reasons C might advertise the aggregate, and
   not the more specific, to D, including (but not limited to):
   o  B and C both accept prefixes with a length of /25, while D does
      not, so D filters the 10.1.1.0/25 inbound from C.
   o  A has a policy that nothing originating in D may traverse B, so it
      advertises the update in such a way to prevent C from
      readvertising 10.1.1.0/25 to D.
   o  D has a policy that anything destined to A cannot traverse B, so
      it blocks 10.1.1.0/25 at its border with C (because it finds B in



White, et al.            Expires April 1, 2005                  [Page 6]


Internet-Draft       Path Validation Considerations         October 2004


      the AS Path).
   o  B has a policy that traffic originating in D will not transit B's
      network to reach A.
   o  C notes it has two advertisements covering the same address space,
      and advertises only one of them to D.

   So, there are several possible reasons information about 10.1.1.0/25
   is removed from the routing system at this point.  What is the
   practical result of removing this information? Suppose some host in D
   originates a packet destined to 10.1.1.1.  The packet will be
   forwarded based on the route to 10.1.1.0/24 in D, to C.  The edge
   router in C finds it has a route to that destination, 10.1.1.0/25,
   and forwards the traffic to B, for final transmission to A.

   Let's return to our questions:
   o  Does a path actually exist from the advertising router to the
      destination advertised? Yes, C really does have a route to
      10.1.1.1, which is contained in the update for the network
      10.1.1.0/24.
   o  Is C authorized, though receiving this advertisement, to transit
      traffic along this path to each reachable destination within the
      prefix advertised? If the reason C doesn't readvertise the
      10.1.1.0/25 route to D is because of A's, B's, or D's policy, then
      no, D is not authorized to transit the path the traffic actually
      takes to reach this destination.
   o  Will traffic forwarded to some destination within 10.1.1.0/24
      actually follow the path described in the update advertised by B?
      No.  The path described in C's advertisement to D is {C, F, E},
      while the path the traffic actually takes is {C, B, A}.
   o  Can D prove that C is authorized to advertise every possible
      address block (or prefix) within 10.1.1.0/24? No, and, in fact, in
      this case C is not authorized to advertise half of 10.1.1.0/24.
      There is no way for D to extract this information from within the
      updates it has received.

   Here we find a single example where the receiving AS cannot prove the
   transmitting AS' authorization to transit traffic, nor that the path
   of the traffic will follow the AS Path indicated in the update, nor
   that the advertising AS is authorized to actually advertise the
   entire address space indicated in the update.

   Again, we find the incomplete notion of address block ownership as
   the root of the problems in this network.  While A owns 10.1.1.0/24,
   B still maintains ownership of 10.1.1.0/24, which includes
   10.1.1.0/25, so A doesn't have complete control over the policies
   implemented or propagated through the internetwork.





White, et al.            Expires April 1, 2005                  [Page 7]


Internet-Draft       Path Validation Considerations         October 2004


2.5  Fourth Example: Interior and Exterior Paths Mismatch

   This is the most complex example we will cover in this draft.  Many
   people will note the configuration described is a misconfiguration,
   but there are many such possible situations in the interaction
   between BGP and interior gateway protocols.  Note this example
   doesn't involve the removal of information from the routing system,
   and it is specific only to BGP, not to path vector protocols in
   general.

   Assume we have the following small internetwork:

         +-----9---------------3--------+
         |                     |        |
         |            +--------+        |
         |            |                 |
         |        +---C--+              |
         |        |      |              |
         A--------B      +--------------E--10.1.1.0/24
         |        |      |              |
         |        +---D--+              |
         |                              |
         +---------------------6--7--8--+

         AS1 |   |    AS2    |         | AS5          |


   In this diagram, routers are represented by letters, and autonomous
   systems by numbers.  So:
   o  Router A is in AS1
   o  Routers B, C, and D are in AS2
   o  Router E is in AS5

   Each router is using, as its best path to 10.1.1.0/24:
   o  Router E is using its local (intra-AS) path.
   o  Router C is using the path through AS3.
   o  Router D is using the path through Router E.
   o  Router B is using the path through Router E.

   Examining the case of Router B more closely, however, we discover
   that while Router B prefers the path it has learned from Router E,
   that path has been advertised with a next hop of Router E itself.
   However, Router B's best path to this next hop (i.e., Router E), as
   determined by the interior routing protocol, is actually through
   Router C.  Thus, Router B advertises the path {2, 5} to Router A, but
   traffic actually follows the path {2, 3, 5} when Router B receives
   it.




White, et al.            Expires April 1, 2005                  [Page 8]


Internet-Draft       Path Validation Considerations         October 2004


   The system administrator of AS1 has determined there is an attacker
   in AS3, and has set policy on router A to avoid any route with AS3 in
   the AS_PATH.  So, beginning with this rule, it discards the path
   learned from AS9.  It now examines the two remaining paths, learned
   from AS2 (B) and AS6, and determines the best path is {2, 5}, through
   AS2 (B).  However, unknown to A, AS2 (B) is also connected to AS3,
   and is transiting traffic to AS5 via the path {2, 3, 5}.

   Returning to our questions:
   o  Does a path actually exist from the advertising router to the
      destination advertised? Yes.
   o  Is A authorized, though receiving this advertisement, to transit
      traffic along this path to each reachable destination within the
      prefix advertised? There is no mention of policy within this
      example, so we can't answer this question.
   o  Will traffic forwarded to some destination within 10.1.1.0/24
      actually follow the path described in the update advertised by B?
      No.  Router B advertises the path {2, 5} to Router A, but traffic
      actually follows the path {2, 3, 5}.
   o  Can Router A, from the perspective of AS1, prove that AS2 is
      authorized to advertise every possible reachable destination with
      10.1.1.0/24? Since policy isn't specified anyplace within this
      example, this question doesn't apply.

   This is only one given example of the interaction between BGP and
   interior gateway protocols resulting in one path being advertised,
   and another path being taken.  It's actually common in the case of
   route reflectors, for instance.

3.  Summary

   While it is tempting to set policy, or to infer policy, from the
   existence or non-existence of information within a routing system, it
   isn't possible to do so, since routing systems remove information on
   a regular basis.  Further, while it appears logical that policy could
   be set based on the AS Path advertised from one BGP speaker to
   another.  However, since routing information is regularly removed
   from the routing system, this isn't possible, either.

   Of the original list of issues we outlined at the beginning of this
   document, the only one we can consistently prove is the ability to
   prove a path between an advertising AS and the destinations
   advertised in BGP updates actually exists.

   [ROUTINGLOGIC] also provides some instances in which information is
   removed from the routing system, through other means (such as route
   reflectors), which could result in situations similar to the ones
   cited above.  [ASTRACEROUTE] also provides some interesting



White, et al.            Expires April 1, 2005                  [Page 9]


Internet-Draft       Path Validation Considerations         October 2004


   background on the problems involved in attempting to map a packet's
   path to an AS Path advertised in BGP.

4  Informative References

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

   [S-BGP]  Lynn, C., "Secure BGP (S-BGP)",
            draft-clynn-s-bgp-protocol-01 (work in progress), July 2003.


Authors' Addresses

   Russ White
   Cisco Systems
   riw@cisco.com

   Bora Akyol
   Cisco Systems
   bora@cisco.com

   Nick Feamster
   feamster@lcs.mit.edu



























White, et al.            Expires April 1, 2005                 [Page 10]


Internet-Draft       Path Validation Considerations         October 2004


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 (2004).  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, et al.            Expires April 1, 2005                 [Page 11]