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]