idnits 2.17.1 draft-white-pathconsiderations-02.txt: Checking boilerplate required by RFC 5378 and the IETF Trust (see https://trustee.ietf.org/license-info): ---------------------------------------------------------------------------- ** Looks like you're using RFC 2026 boilerplate. This must be updated to follow RFC 3978/3979, as updated by RFC 4748. Checking nits according to https://www.ietf.org/id-info/1id-guidelines.txt: ---------------------------------------------------------------------------- ** The document seems to lack a 1id_guidelines paragraph about Internet-Drafts being working documents. ** The document seems to lack a 1id_guidelines paragraph about 6 months document validity. ** The document seems to lack a 1id_guidelines paragraph about the list of current Internet-Drafts -- however, there's a paragraph with a matching beginning. Boilerplate error? ** The document seems to lack a 1id_guidelines paragraph about the list of Shadow Directories -- however, there's a paragraph with a matching beginning. Boilerplate error? == No 'Intended status' indicated for this document; assuming Proposed Standard == The page length should not exceed 58 lines per page, but there was 9 longer pages, the longest (page 2) being 60 lines == It seems as if not all pages are separated by form feeds - found 0 form feeds but 10 pages Checking nits according to https://www.ietf.org/id-info/checklist : ---------------------------------------------------------------------------- ** The document seems to lack a Security Considerations section. ** The document seems to lack an IANA Considerations section. (See Section 2.2 of https://www.ietf.org/id-info/checklist for how to handle the case when there are no actions for IANA.) ** There is 1 instance of too long lines in the document, the longest one being 5 characters in excess of 72. ** The abstract seems to contain references ([SOBGP-DEPLOY], [S-BGP], [IRV]), which it shouldn't. Please replace those with straight textual mentions of the documents in question. == There are 30 instances of lines with private range IPv4 addresses in the document. If these are generic example addresses, they should be changed to use any of the ranges defined in RFC 6890 (or successor): 192.0.2.x, 198.51.100.x or 203.0.113.x. Miscellaneous warnings: ---------------------------------------------------------------------------- -- The document seems to lack a disclaimer for pre-RFC5378 work, but may have content which was first submitted before 10 November 2008. If you have contacted all the original authors and they are all willing to grant the BCP78 rights to the IETF Trust, then this is fine, and you can ignore this comment. If not, you may need to add the pre-RFC5378 disclaimer. (See the Legal Provisions document at https://trustee.ietf.org/license-info for more information.) -- The document date (April 2004) is 7316 days in the past. Is this intentional? Checking references for intended status: Proposed Standard ---------------------------------------------------------------------------- (See RFCs 3967 and 4897 for information about using normative references to lower-maturity documents in RFCs) -- Obsolete informational reference (is this intentional?): RFC 1771 (ref. 'BGP') (Obsoleted by RFC 4271) -- No information found for draft-white-sobgp-deployment - is the name correct? -- Obsolete informational reference (is this intentional?): RFC 2385 (ref. 'BGP-MD5') (Obsoleted by RFC 5925) Summary: 9 errors (**), 0 flaws (~~), 4 warnings (==), 5 comments (--). Run idnits with the --verbose option for more detailed information about the items above. -------------------------------------------------------------------------------- 2 Network Working Group Russ White 3 Internet Draft Bora Akyol 4 Expiration Date: October 2004 Cisco Systems 5 File Name: draft-white-pathconsiderations-02.txt Nick Feamster 6 MIT 7 April 2004 9 Considerations in Validating the Path in Routing Protocols 10 draft-white-pathconsiderations-02.txt 12 Status of this Memo 14 This document is an Internet-Draft and is in full conformance with 15 all provisions of Section 10 of RFC2026. 17 Internet Drafts are working documents of the Internet Engineering 18 Task Force (IETF), its Areas, and its Working Groups. Note that other 19 groups may also distribute working documents as Internet Drafts. 21 Internet Drafts are draft documents valid for a maximum of six 22 months. Internet Drafts may be updated, replaced, or obsoleted by 23 other documents at any time. It is not appropriate to use Internet 24 Drafts as reference material or to cite them other than as a "working 25 draft" or "work in progress". 27 The list of current Internet-Drafts can be accessed at 28 http//www.ietf.org/ietf/1id-abstracts.txt 30 The list of Internet-Draft Shadow Directories can be accessed at 31 http//www.ietf.org/shadow.html. 33 Abstract 35 A good deal of consideration has gone into, and is currently being 36 given to, validating the path to a destination advertised by an 37 adjacent router or peer, such as [S-BGP], [SOBGP-DEPLOY], and [IRV]. 38 Since much of this effort has been focused on BGP, this draft 39 discusses some issues with this work in terms of BGP. 41 One of the primary assumptions in much of this work is that the 42 authentication of a given advertisement received by a specific BGP 43 speaker is the same as authorization to use the path advertised. In 44 other words, it is generally assumed that if a BGP speaker receives 45 an advertisement for which the AS Path can somehow be verified, the 46 speaker is authorized to transit traffic along the path specified 47 contained in the update, and the traffic forwarded to the destination 48 contained in the update will actually follow the path advertised. 50 This draft shows these two assumptions cannot be held to be true in a 51 path vector routing system. 53 1. Background 55 With the heightened interest in network security, the security of the 56 information carried within the routing system is being looked at with 57 great interest. While there are techniques available for securing the 58 relationship between two devices exchanging routing protocol 59 information, such as [BGP-MD5], these techniques do not ensure 60 various aspects of the information carried within routing protocols. 61 One issue that cannot be addressed through peer authentication is the 62 validity of the path represented by a BGP speaker when advertising 63 reachability to a specific prefix. 65 To place this in more direct terms, consider this small network. 67 10.1.1.0/24--A---B--C 69 Assume C has received an advertisement for 10.1.1.0/24 from B, with 70 an AS Path of {A, B}. We can ask three questions about this update: 72 o Does a path actually exist from the advertising router to the 73 destination advertised? 75 o Is C authorized, though receiving this advertisement, to transit 76 traffic along this path to each reachable destination within the 77 prefix advertised? 79 o Will traffic forwarded to some destination within 10.1.1.0/24 80 actually follow the path described in the update advertised by 81 B? 83 The primary question we would like to examine in this draft is which 84 of these three questions can actually be answered witin a path vector 85 protocol, such as BGP. This draft contends that the second and third 86 meanings of path validity cannot be verified in a distance or path 87 vector protocol. 89 We will first examine some fundamental concepts of routing and path 90 selection in general, then we will proceed through some examples, and 91 re-examine each question above in light of each of those examples. In 92 each example, we will discuss policy, in terms of an acceptable path 93 for the receiver of the traffic (the originator of the advertisement) 94 or the transmitter of the traffic. 96 2. Analysis 98 To begin, we review some of the concepts of routing, since we need to 99 keep these concepts fixed firmly in place while we examine these 100 questions. After this, four examples will be undertaken with BGP to 101 show why the second of two questions cannot be answered in a path 102 vector routing system. Finally, a short section on transitive author- 103 ization in a path vector protocol is provided, which considers the 104 reasons behind the results we find in the examples. 106 2.1. A Short Analysis of Routing 108 Routing protocols are designed, in short, to discover a set of loop 109 free paths to each reachable destination within a network (or inter- 110 network). The loop free path chosen to reach a specific destination 111 may not be the shortest path, and it may not always be the shortest 112 path (depending on the definition of "best"), but it should always be 113 a loop free path, or routing, and the routing protocol, has failed. 115 This sheds some light on the purpose of the path included in an path 116 vector protocol's routing update: the path is there to prove the path 117 is loop free, rather than to provide any other information. While 118 Dijkstra's SPF and the Diffusing Update Algorithm (DUAL) both base 119 their loop free path calculations on the cost of a path, path vector 120 protocols, such as BGP, prove a path is loop free by carrying a list 121 of nodes the advertisement itself has traversed. 123 We need to keep this principle in mind when considering the use of 124 the path carried in a path vector protocol for setting policy. 126 2.2. First Example: Manual Intervention in the Path Choice 128 In the small network: 130 +---C---+ 131 A--B E 132 +---D---+ 134 A may receive an advertisement from B that E is reachable along the 135 path {B, C, E}. Based on this information, A may forward packets to 136 B, expecting them to take the path described. However, at B's edge 137 router receiving this traffic, the network administrator may have 138 configured a static route making the next hop to E the edge router 139 with D. 141 Although this is an "extreme" example, since we can hardly claim the 142 information within the routing protocol is actually insufficient, we 143 will still find it instructive to examine this example in light of 144 the original three questions: 146 o Does a path actually exist from the advertising router to the 147 destination advertised? Yes, it clearly does. 149 o Is C authorized, though receiving this advertisement, to transit 150 traffic along this path to each reachable destination within the 151 prefix advertised? This question isn't addressed in this exam- 152 ple, since we have no idea what A or E's policies are. 154 o Will traffic forwarded to some destination within 10.1.1.0/24 155 actually follow the path described in the update advertised by 156 B? No, traffic forwarded by A torwards B will not follow the 157 path described in B's update. 159 There is no way to account for the overriding of a routing 160 protocol's information through static configuration or through 161 other routing protocols running on the same devices, since rout- 162 ing is a hop by hop endeavor. 164 2.3. Second Example: An Unintended Reachable Destination 166 Here, we return the small network outlined earlier in this draft. 168 10.1.1.0/24---A---B---C 170 We will assume, for argument's sake, that A and C are competitors, 171 and A would like to prevent hosts within C's network from reaching 172 anything within its network. A has implemented this policy by 173 advertising 10.1.1.0/24 to B with some restriction (we can use the 174 NO_ADVERTISE community described in [BGP] for this purpose) so B can- 175 not readvertise the destination to C. 177 However, unknown to A, B is actually advertising a default route only 178 to C, and not a full routing table. If some host within C, then, ori- 179 ginates a packet destined to 10.1.1.1, what will happen? The packet 180 will be routed according to the default route advertised by B. When 181 the edge router between B and C receives the packet, it will forward 182 the packet along the 10.1.1.0/24 route learned from A, forwarding the 183 traffic into A's network. 185 Returning to our questions: 187 o Does a path actually exist from the advertising router to the 188 destination advertised? Yes, it does. If B doesn't know of some 189 specific host connected to the Internetwork, we can assume that 190 host doesn't exist, thus the default route is a valid route for 191 B to advertise in this case. 193 o Is C authorized, though receiving this advertisement, to transit 194 traffic along this path to each reachable destination within the 195 prefix advertised? No. In fact, A has explicity attempted to 196 prevent C from using this path to reach any hosts within its 197 network. 199 o Will traffic forwarded to some destination within 10.1.1.0/24 200 actually follow the path described in the update advertised by 201 B? No. The path advertised with the default route ends in B, 202 while the traffic transits beyond B, into A, which is hidden in 203 the AS Path B advertises. 205 The basic problem here is that A is assuming that because B 206 doesn't receive an advertisement for 10.1.1.0/24, it cannot 207 reach 10.1.1.0/24. We see, however, that lack of routing infor- 208 mation does not imply lack of authorization, because aggregates 209 cover many possible destinations, and the default is just the 210 shortest prefix aggregate available. 212 2.4. Third Example: Following a Specific Path 214 This example is slightly more complex than the last two. Given the 215 following small network: 217 10.1.1.0/25--A---B---C---D 218 | | 219 E-------F 221 Assume the following: 223 o A advertises 10.1.1.0/25 to B and E. 225 o B advertises 10.1.1.0/24 to C. 227 o E advertises the aggregate 10.1.1.0/24 to F. 229 o F advertises the aggregate 10.1.1.0/24 to C. 231 o C advertises the aggregate 10.1.1.0/24 to D, but not the more 232 specific 10.1.1.0/25. 234 There are a number of reasons C might advertise the aggregate, and 235 not the more specific, to D, including (but not limited to): 237 o B and C both accept prefixes with a length of /25, while D does 238 not, so D filters the 10.1.1.0/25 inbound from C. 240 o A has a policy that nothing originating in D may traverse B, so 241 it advertises the update in such a way to prevent C from read- 242 vertising 10.1.1.0/25 to D. 244 o D has a policy that anything destined to A cannot traverse B, so 245 it blocks 10.1.1.0/25 at its border with C (because it finds B 246 in the AS Path). 248 o B has a policy that traffic originating in D will not transit 249 B's network to reach A. 251 o C notes it has two advertisements covering the same address 252 space, and advertises only one of them to D. 254 So, there are several possible reasons information about 10.1.1.0/25 255 is removed from the routing system at this point. What is the practi- 256 cal result of removing this information? Suppose some host in D ori- 257 ginates a packet destined to 10.1.1.1. The packet will be forwarded 258 based on the route to 10.1.1.0/24 in D, to C. The edge router in C 259 finds it has a route to that destination, 10.1.1.0/25, and forwards 260 the traffic to B, for final transmission to A. 262 Let's return to our questions: 264 o Does a path actually exist from the advertising router to the 265 destination advertised? Yes, C really does have a route to 266 10.1.1.1. 268 o Is C authorized, though receiving this advertisement, to transit 269 traffic along this path to each reachable destination within the 270 prefix advertised? If the reason C doesn't readvertise the 271 10.1.1.0/25 route to D is because of A's, B's, or D's policy, 272 then no, D is not authorized to transit the path the traffic 273 actually takes to reach this destination. 275 o Will traffic forwarded to some destination within 10.1.1.0/24 276 actually follow the path described in the update advertised by 277 B? No. The path described in C's advertisement to D is {C, F, 278 E}, while the path the traffic actually takes is {C, B, A}. 280 2.5. Fourth Example: A Mismatch Between the Interior and Exterior Paths 282 This is the most complex example we will cover in this draft. Many 283 people will note the configuration described is a misconfiguration, 284 but there are many such possible situations in the interaction 285 between BGP and interior gateway protocols. Note this example doesn't 286 involve the removal of information from the routing system, and it is 287 specific only to BGP, not to path vector protocols in general. 289 Assume we have the following small internetwork: 291 +-----9---------------3--------+ 292 | | | 293 | +--------+ | 294 | | | 295 | +---C--+ | 296 | | | | 297 A--------B +--------------E--10.1.1.0/24 298 | | | | 299 | +---D--+ | 300 | | 301 +---------------------6--7--8--+ 303 AS1 | | AS2 | | AS5 | 305 In this diagram, routers are represented by letters, and autonomous 306 systems by numbers. So: 308 o Router A is in AS1 310 o Routers B, C, and D are in AS2 312 o Router E is in AS5 314 Each router is using, as its best path to 10.1.1.0/24: 316 o Router E is using its local (intra-AS) path. 318 o Router C is using the path through AS3. 320 o Router D is using the path through Router E. 322 o Router B is using the path through Router E. 324 Examining the case of Router B more closely, however, we discover 325 that while Router B prefers the path it has learned from Router E, 326 that path has been advertised with a next hop of Router E itself. 327 However, Router B's best path to this next hop (i.e., Router E), as 328 determined by the interior routing protocol, is actually through 329 Router C. Thus, Router B advertises the path {2, 5} to Router A, but 330 traffic actually follows the path {2, 3, 5} when Router B receives 331 it. 333 The system administrator of AS1 has determined there is an attacker 334 in AS3, and has set policy on router A to avoid any route with AS3 in 335 the AS_PATH. So, beginning with this rule, it discards the path 336 learned from AS9. It now examines the two remaining paths, learned 337 from AS2 (B) and AS6, and determines the best path is {2, 5}, through 338 AS2 (B). However, unknown to A, AS2 (B) is also connected to AS3, and 339 is transiting traffic to AS5 via the path {2, 3, 5}. 341 Returning to our questions: 343 o Does a path actually exist from the advertising router to the 344 destination advertised? Yes. 346 o Is A authorized, though receiving this advertisement, to transit 347 traffic along this path to each reachable destination within the 348 prefix advertised? There is no mention of policy within this 349 example, so we can't answer this question. 351 o Will traffic forwarded to some destination within 10.1.1.0/24 352 actually follow the path described in the update advertised by 353 B? No. Router B advertises the path {2, 5} to Router A, but 354 traffic actually follows the path {2, 3, 5}. 356 This is only one given example of the interaction between BGP and 357 interior gateway protocols resulting in one path being advertised, 358 and another path being taken. It's actually common in the case of 359 route reflectors, for instance. 361 2.6. Trasitive Authorization in Path Vector Protocols 363 A route is carried as a prefix and its associated attributes, one of 364 which is the AS Path, [BGP]. It is possible to verify that the prefix 365 is originated by its authorized owner AS by multiple means including 366 an encrypted certificate or the use of a route or address registry 367 and checking that the first AS in the path is the AS that owns the 368 prefix. However, this authorization can not be carried over to infer 369 that the path associated with this prefix is in fact authorized by 370 the originating AS. As we have shown in the examples above, BGP does 371 not transmit routing information intact across autonomous systems. 373 In fact, routing information is frequently summarized or filtered, 374 with more specific prefixes hidden and sometimes completely ignored 375 via application of routing policy. Due to application of routing pol- 376 icy as well as the hop by hop nature of IP routing, the only facts 377 that can be inferred from a prefix and its path attribute received by 378 BGP are: 380 o Originator AS is the authorized advertiser of the prefix: This 381 can be achieved by means of use of a routing registry, or via 382 security extensions to BGP [soBGP, SBGP]. 384 o The path being carried is _plausible_; that is, the path is a 385 path that is likely to carry the packets destined for that pre- 386 fix to the originating AS. This can be achieved by either 387 knowledge of peering information (as can be obtained by means of 388 a routing registry) or via security extensions to BGP. 390 Therefore, from a security perspective, a prefix and its path can be 391 classified in two dimensions: Originating AS :={Authorized, Unauthor- 392 ized}, Path := {Plausible, Implausible}. 394 3. Summary 396 While it is tempting to set policy, or to infer policy, from the 397 existence or non-existence of information within a routing system, it 398 isn't possible to do so, since routing systems remove information on 399 a regular basis. Further, it appears logical that policy could be set 400 based on the path advertised in a path vector protocol, however, 401 since routing information is regularly removed from the routing sys- 402 tem, it isn't possible to do so. 404 [ROUTINGLOGIC] also provides some instances in which information is 405 removed from the routing system, through other means (such as route 406 reflectors), which could result in situations similar to the ones 407 cited above. [ASTRACEROUTE] also provides some interesting background 408 on the problems involved in attempting to map a packet's path to an 409 AS Path advertised in BGP. 411 Informative References 413 [BGP] Rekhter, Y., and T. Li, "A Border Gateway Protocol 4 (BGP-4)", 414 RFC 1771, March 1995. 416 [S-BGP] 417 Lynn, C, et al., "Secure BGP (S-BGP)", draft-clynn-s-bgp- 418 protocol-01.txt, June 2003 420 [SOBGP-DEPLOY] 421 White, R. (editor), "Architecture and Deployment Considerations 422 for Secure Origin BGP (soBGP) Deployment", draft-white-sobgp- 423 deployment-02, April 2004 425 [IRV] Goodell, G., et al., Working Around BGP: An Incremental 426 Approach to Improving Security and Accuracy of Interdomain Rout- 427 ing, 428 http://www.isoc.org/isoc/conferences/ndss/03/proceedings/papers/5.pdf 430 [BGP-MD5] 431 Heffernon, A., Protection of BGP Sessions via the TCP MD5 Signa- 432 ture Option, RFC 2385, August 1998 434 [ROUTINGLOGIC] 435 Nick Feamster and Hari Balakrishnan, Towards a Logic for Wide- 436 Area Internet Routing, ACM SIGCOMM Worshop on Future Directions 437 in Network Architecture, Germany, August 2003 439 [ASTRACEROUTE] 440 Zhuoqing Morley Mao, et al., Towards an Accurate ASLevel Tra- 441 ceroute Tool, SIGCOMM 2003 443 4. Author's Addresses 445 Russ White 446 Cisco Systems 447 7025 Kit Creek Road 448 Research Triangle Park, NC 27709 449 riw@cisco.com 451 Nick Feamster 452 200 Technology Square, NE43-504 453 Cambridge, MA 02139-3578 454 617-253-7341 455 feamster@lcs.mit.edu 457 Bora Akyol 458 Cisco Systems 459 170 West Tasman Drive 460 San Jose, CA 95134 461 bora@cisco.com