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]