Network Working Group                                         Russ White
Internet Draft                                             Cisco Systems
Expiration Date: April 2004                                Nick Feamster
File Name: draft-white-pathconsiderations-00.txt                     MIT
                                                            October 2003


       Considerations in Validating the Path in Routing Protocols
                 draft-white-pathconsiderations-00.txt

   Status of this Memo

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

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

   Internet Drafts are draft documents valid for a maximum of six
   months.  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
   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.


1. Abstract

   A good deal of consideration has gone into, and is currently being
   given to, validating the path to a destination advertised by an
   adjacent router or peer, such as [S-BGP], [SOBGP], and [IRV]. Since
   much of this effort has been focused on BGP, this draft discusses
   some issues with this work in terms of BGP.

   The theory advanced by this draft is that the AS Path of a received
   advertisement can only be validated, or proven "correct", in one
   respect: that the advertiser has at least one known path to the
   destination advertised. A participant in a path vector routing
   protocol cannot verify (1) whether the path a packet takes to its
   destination corresponds to the path advertised by the routing
   protocol, or (2) whether the chosen path is in accordance with the
   policies of other ASes.



White and Feamster                                              [Page 1]


INTERNET DRAFT      Considerations in Path Security         October 2003


   Two fundamental problems with path vector protocols make path
   validation challenging.  First, path vector routing protocols
   abstract information about intra-AS routing decisions; if different
   routers within an AS choose different routes to a destination, the
   path advertised by one router in an AS might be inconsistent with the
   actual path that packets will take.  Second, ASes can remove routes
   from the routing system in accordance with their own policy; such an
   action can, in some cases, prevent another AS from enforcing its own
   policy.


2. 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 [BGP-MD5], these techniques do not ensure various aspects
   of the information carried within routing protocols. Two specific
   issues which cannot be addressed through peer authentication are
   whether or not a particular router is authorized to originate a given
   destination, and the validity of a path advertised by a given router.
   This document does not discuss the authorization to advertise a given
   destination, or prefix.

   The validity of a path advertised by a given router actually consists
   of at least three parts:

   o    Does a path from the advertising router to the destination
        advertised actually exist?

   o    Does the path advertised fall within the policies of the route's
        originator and all intermediate autonomous systems?

   o    Is the advertising router authorized to advertise a path to the
        destination?

   The primary question we would like to address here is which of these
   three requirements for path validity can be answered within a dis-
   tance vector or path vector protocol, such as BGP. This draft con-
   tends that the second and third meanings of path validity cannot be
   verified in a distance or path vector protocol. This is because (1)
   path vector protocols hide intra-AS routing decisions and (2) poli-
   cies of local ASes can remove information from the global routing
   system.

   In fact, routing protocols were never designed to provide more infor-
   mation than whether or not a path to a given destination exists.



White and Feamster                                              [Page 2]


INTERNET DRAFT      Considerations in Path Security         October 2003


   Distance and path vector protocols were never designed to:

   o    Provide a definitive path a packet forwarded to the advertising
        peer will take.

   o    Provide path information beyond the best path which is available
        to the advertising peer, or provide all possible path informa-
        tion.

   o    Provide information about all possible reachable destinations.


2.1. Proving a Definitive Packet Path From Routing Information

   No routing protocol can provide the definitive path a packet which is
   forwarded to a given peer will take, simply because routing is hop by
   hop. In the small network:

      +---C---+
   A--B       E
      +---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. B, however, may have
   other routing information, for instance, a static route, which
   directs it to make the next hop D. There is no way to account for the
   overriding of a routing protocol's information through static confi-
   guration or through other routing protocols running on the same dev-
   ices, since routing is a hop by hop endeavor.

   However, all such considerations are ignored in this document, and we
   assume that all packets transmitted will follow some path advertised
   in a routing protocol; that no such manual configuration has overrid-
   den the protocol, and that no other protocol is running which may
   provide conflicting routing information. Further, we assume that no
   quality of service, or traffic engineering of any type, is influenc-
   ing routing. Thus, we will deal with only very simple networks, with
   no overriding factors, although these show that, from the outset,
   there is no way to know the path a packet transmitted along a path
   advertised by a peer will take.










White and Feamster                                              [Page 3]


INTERNET DRAFT      Considerations in Path Security         October 2003


3. Removal of Routing Information in Distance and Path Vector Protocols

   Distance and path vector routing protocols remove information as a
   matter of normal operation for various reasons. Several reasons
   include:

   o    Filtering of routing information based on policy.

   o    Filtering of routing information to increase routing stability,
        and decrease convergence times.

   o    Aggregation of reachable destinations.

   o    Advertisement of a single path when multiple paths of equal cost
        exist.

   It is because routing protocols routinely remove information from the
   routing system that an advertised path may only be validated in the
   sense of verifying a path from the advertiser to the destination
   exists.

   Examples

   The following two sections show small networks where, through the
   normal removal of routing information, the ability to form policy or
   ascertain authorization to advertise is destroyed. [BGP] is taken as
   the routing protocol in both of these examples, although any distance
   vector protocol would be subject to these same restrictions.


3.1. Does the Advertised Path Fall Within the Policies of the Receiver?

   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          |




White and Feamster                                              [Page 4]


INTERNET DRAFT      Considerations in Path Security         October 2003


   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.

   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}.

   This example presents one way that the intra-AS configuration of one
   AS can cause packets to follow a path inconsistent with the adver-
   tised path.  Route reflection within an AS can also cause the types
   of inconsistencies that we see in the above example.  For example,
   assume that a route reflector, RR1, advertises a route with itself as
   the next hop to its client, C1, and that RR2 advertises a route to
   the same destination through with a different AS path to C2.  If C1's
   path to RR1 in the interior routing protocol routes packets through
   either C2 or RR2, packets will not follow the path to the destination
   that C1 advertises to its neighbors.  These inconsistencies can
   result because an AS to make different routing decisions at different
   routers within its network, path vector routing depends on its



White and Feamster                                              [Page 5]


INTERNET DRAFT      Considerations in Path Security         October 2003


   interior routing protocols.

   Thus, there is no way to determine the relative merits of a path in a
   path vector protocol based on received advertisements.  Participants
   in path vector protocols cannot determine which path will be taken
   based on the advertisement alone and thus cannot prove which path is
   "safer", "more secure", etc.


3.2. Is the advertising router authorized to advertise a path to the
   destination?

   Assume we have the following small internetwork, with each node
   representing an autonomous system:

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

   Suppose D is advertising two overlapping prefixes, 10.1.2.0/24, and
   10.1.2.0/23. D would prefer that the traffic destined to 10.1.2.1
   come through its connection with C, for security reasons (D considers
   this the more secure path), but other traffic, to 10.1.3.1, for
   instance, may take the less secure path through B. To accomplish
   this, D advertises 10.1.2.0/24 to C, and does not advertise this to
   B.

   However, A does not receive the 10.1.2.0/24 advertisement from C, for
   one of several reasons:

   o    A has determined to reduce the amount of routing information it
        receives by blocking all prefixes with a prefix length longer
        than 23 bits, thus 10.1.2.0/24 is filtered at its border with C.

   o    C has a local policy of not readvertising prefixes with a prefix
        length greater than 23 bits, so 10.1.2.0/24 is filtered at C's
        edge towards A.

   o    C has a local policy of not readvertising prefixes for which
        there is a shorter prefix match, and since both 10.1.2.0/24 and
        10.1.2.0/23 exist at the border with A, 10.1.2.0/24 is not read-
        vertised to A.

   o    C has also determined that it would not like to transit traffic
        for D, and enforces this policy by not readvertising the
        10.1.2.0/24 prefix towards A.

   In other words, there are a large number of circumstances under which



White and Feamster                                              [Page 6]


INTERNET DRAFT      Considerations in Path Security         October 2003


   A would not receive full routing information from C, causing A to
   only receive the two 10.1.2.0/23 advertisements from B and C. A can
   now choose between two apparently equally valid and good paths,
   choosing to forward traffic destined to 10.1.2.1 along the path {B,
   D}. There are several reasons A may choose the {B, D} path, including
   the age of the path in the local tables, router identifier of the
   peer transmitting the route, and others.  A's choice of the {B, D}
   path overrides D's implicit policy of only accepting this traffic
   along the connection with C.

   At this point, the removal of information from the routing system has
   caused A to make a routing decision which doesn't fall within the
   policies in effect for this destination. Whenever it is possible to
   remove information from the routing system, it is never possible to
   "secure the path," in any sense other than validating that both B and
   C actually do have paths to reach 10.1.1.0/24, advertised by D.

   What if D determined to resolve this by simply removing the
   10.1.2.0/23, and advertising two routes in its place, 10.1.2.0/24 and
   10.1.3.0/24? If we assume that either A has an inbound policy of not
   accepting any prefixes with a prefix length greater than 23 bits, or
   that C has a policy of not readvertising any prefixes with a prefix
   length greater than 23 bits, then A will simply not receive any rout-
   ing information for 10.1.2.0/24. This will either make 10.1.2.0/24
   unreachable, or it will cause A to follow some even shorter prefix
   length advertisement, possibly a default route, to reach D. If A can-
   not reach 10.1.2.0/24, routing has failed; if A follows some shorter
   prefix length advertisement, it could easily choose either path, thus
   continuing to defeat C's implicit policy.

   The basic problem is D has attempted to control B's ability to tran-
   sit traffic for a certain set of destinations by removing information
   from the routing system. Since D cannot control other prefixes B is
   advertising, and D also cannot control the filtering of its advertis-
   ments by other autonomous systems, it's impossible for D to control
   routing policy by removing routing information.

   Thus, lack of information cannot, in a routing system, be construed
   to mean lack of authorization to transit a given path, or provide
   reachability to a given destination, unless all possible routing
   information towards a given destination can be removed, and all pos-
   sible points of origin for that information are under the administra-
   tive control of the owner of the route.








White and Feamster                                              [Page 7]


INTERNET DRAFT      Considerations in Path Security         October 2003


4. 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, it appears logical that policy could be set
   based on the path advertised in a path vector protocol, however,
   since routing information is regularly removed from the routing sys-
   tem, it isn't possible to do so.

   [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 background
   on the problems involved in attempting to map a packet's path to an
   AS Path advertised in BGP.

   Informative References

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

   [S-BGP]
        Lynn, C, et al., "Secure BGP (S-BGP)", draft-clynn-s-bgp-
        protocol-01.txt, June 2003

   [SOBGP]
        Ng, J (Editor), "Extensions to BGP to Support Secure Origin BGP
        (soBGP)", draft-ng-sobgp-bgp-extensions-01.txt, June 2003

   [IRV] Goodell, G., et al., Working Around BGP: An Incremental
        Approach to Improving Security and Accuracy of Interdomain Rout-
        ing,
        http://www.isoc.org/isoc/conferences/ndss/03/proceedings/papers/5.pdf

   [BGP-MD5]
        Heffernon, A., Protection of BGP Sessions via the TCP MD5 Signa-
        ture Option, RFC 2385, August 1998

   [ROUTINGLOGIC]
        Nick Feamster and Hari Balakrishnan, Towards a Logic for Wide-
        Area Internet Routing, ACM SIGCOMM Worshop on Future Directions
        in Network Architecture, Germany, August 2003

   [ASTRACEROUTE]
        Zhuoqing Morley Mao, et al., Towards an Accurate ASLevel Tra-
        ceroute Tool, SIGCOMM 2003




White and Feamster                                              [Page 8]


INTERNET DRAFT      Considerations in Path Security         October 2003


5. Author's Addresses

   Russ White
   Cisco Systems
   7025 Kit Creek Road
   Research Triangle Park, NC 27709
   riw@cisco.com

   Nick Feamster
   200 Technology Square, NE43-504
   Cambridge, MA 02139-3578
   617-253-7341
   feamster@lcs.mit.edu






































White and Feamster                                              [Page 9]