One document matched: draft-white-pathconsiderations-02.txt
Differences from draft-white-pathconsiderations-01.txt
Network Working Group Russ White
Internet Draft Bora Akyol
Expiration Date: October 2004 Cisco Systems
File Name: draft-white-pathconsiderations-02.txt Nick Feamster
MIT
April 2004
Considerations in Validating the Path in Routing Protocols
draft-white-pathconsiderations-02.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.
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-DEPLOY], and [IRV].
Since much of this effort has been focused on BGP, this draft
discusses some issues with this work in terms of BGP.
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.
White, et al. [Page 1]
INTERNET DRAFT Considerations in Path Security April 2004
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 path
for the receiver of the traffic (the originator of the advertisement)
or the transmitter of the traffic.
White, et al. [Page 2]
INTERNET DRAFT Considerations in Path Security April 2004
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.
Although this is an "extreme" example, since we can hardly claim the
White, et al. [Page 3]
INTERNET DRAFT Considerations in Path Security April 2004
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 rout-
ing 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 can-
not 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, ori-
ginates 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:
White, et al. [Page 4]
INTERNET DRAFT Considerations in Path Security April 2004
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.
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.
White, et al. [Page 5]
INTERNET DRAFT Considerations in Path Security April 2004
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.
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 practi-
cal result of removing this information? Suppose some host in D ori-
ginates 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.
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}.
White, et al. [Page 6]
INTERNET DRAFT Considerations in Path Security April 2004
2.5. Fourth Example: A Mismatch Between the Interior and Exterior Paths
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
White, et al. [Page 7]
INTERNET DRAFT Considerations in Path Security April 2004
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.
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,
White, et al. [Page 8]
INTERNET DRAFT Considerations in Path Security April 2004
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 [soBGP, SBGP].
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}.
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 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
White, et al. [Page 9]
INTERNET DRAFT Considerations in Path Security April 2004
[SOBGP-DEPLOY]
White, R. (editor), "Architecture and Deployment Considerations
for Secure Origin BGP (soBGP) Deployment", draft-white-sobgp-
deployment-02, April 2004
[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
4. 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
Bora Akyol
Cisco Systems
170 West Tasman Drive
San Jose, CA 95134
bora@cisco.com
White, et al. [Page 10]
| PAFTECH AB 2003-2026 | 2026-04-22 12:50:54 |