Network Working Group R. White Internet-Draft B. Akyol Expires: April 4, 2005 Cisco Systems N. Feamster October 4, 2004 Considerations in Validating the Path in Routing Protocols draft-white-pathconsiderations-03 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 4, 2005. Copyright Notice Copyright (C) The Internet Society (2004). 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. Since much of this effort has been focused on BGP, such as [SOBGP], [S-BGP], and [IRV], this draft discusses some issues with this work in terms of BGP. White, et al. Expires April 4, 2005 [Page 1] Internet-Draft Path Validation Considerations October 2004 One of the primary assumptions in much of this work is that the authentication of a given advertisement received by a specific BGP speaker is the same as authorization to use the path advertised. In other words, it is generally assumed that if a BGP speaker receives an advertisement for which the AS Path can somehow be verified, the speaker is authorized to transit traffic along the path specified contained in the update, and the traffic forwarded to the destination contained in the update will actually follow the path advertised. This draft shows these two assumptions cannot be held to be true in a path vector routing system. 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--A---B--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 three questions about this update: o Does a path actually exist from the advertising router to the destination advertised? 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? The primary question we would like to examine in this draft is which of these three questions can actually be answered witin a path vector protocol, such as BGP. This draft contends that the second and third meanings of path validity cannot be verified in a distance or path vector protocol. 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 White, et al. Expires April 4, 2005 [Page 2] Internet-Draft Path Validation Considerations October 2004 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 author- ization 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 inter- network). The loop free path chosen to reach a specific destination may not be the shortest path, and it may not always be the shortest 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 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. 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: +---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. 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. White, et al. Expires April 4, 2005 [Page 3] Internet-Draft Path Validation Considerations October 2004 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 exam- ple, 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 torwards B will not follow the path described in B's 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---A---B---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, we can assume that host doesn't exist, thus the default route is a valid route for B to advertise in this case. White, et al. Expires April 4, 2005 [Page 4] 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? No. In fact, A has explicity attempted to prevent C from using this path to reach any hosts within its network. 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 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 B doesn't receive an advertisement for 10.1.1.0/24, it cannot reach 10.1.1.0/24. We see, however, that lack of routing infor- mation does not imply lack of authorization, because aggregates cover many possible destinations, and the default is just the shortest prefix aggregate available. 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 read- vertising 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 the AS Path). o B has a policy that traffic originating in D will not transit B's network to reach A. White, et al. Expires April 4, 2005 [Page 5] Internet-Draft Path Validation Considerations October 2004 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 detination advertised? Yes, C really does have a route to 10.1.1.1. 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}. 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: White, et al. Expires April 4, 2005 [Page 6] Internet-Draft Path Validation Considerations October 2004 +-----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: Router A is in AS1 Routers B, C, and D are in AS2 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}. Returning to our questions: o Does a path actually exist from the advertising router to the destination advertised? Yes. White, et al. Expires April 4, 2005 [Page 7] Internet-Draft Path Validation Considerations October 2004 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}. 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. 2.6 Trasitive Authorization in Path Vector Protocols A route is carried as a prefix and its associated attributes, one of which is the AS Path, [BGP]. It is possible to verify that the prefix is originated by its authorized owner AS by multiple means including an encrypted certificate or the use of a route or address registry and checking that the first AS in the path is the AS that owns the prefix. However, this authorization can not be carried over to infer that the path associated with this prefix is in fact authorized by the originating AS. As we have shown in the examples above, BGP does not transmit routing information intact across autonomous systems. In fact, routing information is frequently summarized or filtered, with more specific prefixes hidden and sometimes completely ignored via application of routing policy. Due to application of routing pol- icy as well as the hop by hop nature of IP routing, the only facts that can be inferred from a prefix and its path attribute received by BGP are: o Originator AS is the authorized advertiser of the prefix: This can be achieved by means of use of a routing registry, or via security extensions to BGP. o The path being carried is _plausible_; that is, the path is a path that is likely to carry the packets destined for that pre- fix to the originating AS. This can be achieved by either knowledge of peering information (as can be obtained by means of a routing registry) or via security extensions to BGP. Therefore, from a security perspective, a prefix and its path can be classified in two dimensions: Originating AS :={Authorized, Unauthor- ized}, Path := {Plausible, Implausible}. White, et al. Expires April 4, 2005 [Page 8] Internet-Draft Path Validation Considerations October 2004 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, 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 system, 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. 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 Bora Akyol Cisco Systems Nick Feamster White, et al. Expires April 4, 2005 [Page 9] 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 4, 2005 [Page 10]