Subject: draft-murphy-bgp-vuln-02.txt

From: [email-masked]
Date: Fri, 25 Oct 2002 14:59:01 -0400 (EDT)

Network Working Group                                      Sandra Murphy
INTERNET DRAFT                                                  NAI Labs
draft-murphy-bgp-vuln-02.txt                                October 2002

                 BGP Security Vulnerabilities Analysis

Status of this Memo

This document is an Internet-Draft and is subject to 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
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/1id-abstracts.html

The list of Internet-Draft Shadow Directories can be accessed at
http://www.ietf.org/shadow.html

Abstract

BGP, along with a host of other infrastructure protocols designed before
the Internet environment became perilous, is designed with little
consideration for protection of the information it carries.  There are
no mechanisms in BGP to protect against attacks that modify, delete,
forge, or replay data, any of which has the potential to disrupt overall
network routing behavior.

This internet draft discusses some of the security issues with BGP
routing data dissemination.  A companion work, [5], discusses possible
security solutions and the costs of those solutions.  This internet
draft does not discuss security issues with forwarding of packets.

Murphy                     Expires: April 2003                  [Page 1]

INTERNET DRAFT    BGP Security Vulnerabilities Analysis     October 2002

Table of Contents

 Status of this Memo ..............................................    1
 Abstract .........................................................    1
1 Introduction ....................................................    3
2 Vulnerabilities and Risks .......................................    5
2.1 OPEN ..........................................................    5
2.2 KEEPALIVE .....................................................    6
2.3 NOTIFICATION ..................................................    6
2.4 UPDATE ........................................................    6
2.4.1 Unfeasible Routes Length, Total Path Attribute Length .......    6
2.4.2 Withdrawn Routes ............................................    6
2.4.3 Path Attributes .............................................    7
 Attribute Flags, Attribute Type Codes, Attribute Length ..........    7
 ORIGIN ...........................................................    7
 AS_PATH ..........................................................    7
 Originating Routes ...............................................    8
 NEXT_HOP .........................................................    9
 MULTI_EXIT_DISC ..................................................    9
 LOCAL_PREF .......................................................    9
 ATOMIC_AGGREGATE .................................................    9
 AGGREGATOR .......................................................   10
2.4.4 NLRI ........................................................   10
2.5 BGP Extensions ................................................   10
2.5.1 Communities .................................................   10
2.5.2 Confederations ..............................................   11
3 Security Considerations .........................................   11
4 References ......................................................   11
5 Author's Address ................................................   12

Murphy                     Expires: April 2003                  [Page 2]

INTERNET DRAFT    BGP Security Vulnerabilities Analysis     October 2002

1.  Introduction

The inter-domain routing protocol BGP was created when the Internet
environment had not yet reached the present contentious state.
Consequently, the BGP protocol was not designed with protection against
deliberate or accidental errors causing disruptions of routing behavior.

We here discuss the vulnerabilities of BGP, based on the BGP RFC [1] and
on [2].  Readers are expected to be familiar with the BGP RFC and the
behavior of BGP.  A companion work, [5], proposes several different
security solutions to protect these vulnerabilities and discuss the
benefits derived from each solution and its cost.

It is clear that the Internet is vulnerable to attack through its
routing protocols and BGP is no exception.  Faulty, misconfigured or
deliberately malicious sources can disrupt overall Internet behavior by
injecting bogus routing information into the BGP distributed routing
database (by modifying, forging, or replaying BGP packets).  The same
methods can also be used to disrupt local and overall network behavior
by breaking the distributed communication of information between BGP
peers.  The sources of bogus information can be either outsiders or true
BGP peers.

Under the present BGP design, cryptographic authentication of the peer-
peer communication is not mandated.  As a TCP/IP protocol, BGP is
subject to all the TCP/IP attacks, like IP spoofing, session stealing,
etc.  Any outsider can inject believable BGP messages into the
communication between BGP peers and thereby inject bogus routing
information or break the peer to peer connection.  Any break in the peer
to peer communication has a ripple effect on routing that can be wide
spread.  Furthermore, outsider sources can also disrupt communications
between BGP peers by breaking their TCP connection with spoofed RST
packets.  Outsider sources of bogus BGP information can reside anywhere
in the world.

BGP speakers themselves can inject bogus routing information, either by
masquerading as information from any other legitimate BGP speaker, or by
distributing unauthentic routing information as themselves.
Historically, misconfigured and faulty routers have been responsible for
widespread disruptions in the Internet.

Bogus routing information can have many different effects on routing
behavior.  If the bogus information removes routing information for a
particular network, that network can become unreachable for the portion
of the Internet that accepts the bogus information.  If the bogus

Murphy                     Expires: April 2003                  [Page 3]

INTERNET DRAFT    BGP Security Vulnerabilities Analysis     October 2002

information changes the route to a network, then packets destined for
that network may be forwarded by a sub-optimal path, or a path that does
not follow the expected policy, or a path that will not forward the
traffic.  As a consequence, traffic to that network could be delayed by
a longer than necessary path.  The network could become unreachable from
areas where the bogus information is accepted.  Traffic might also be
forwarded along a path that permits some adversary a view of the data.
If the bogus information makes it appear that an autonomous system
originates a network when it does not, then packets for that network may
not be deliverable for the portion of the Internet that accepts the
bogus information.  A false announcement that an autonomous systems
originates a network may also fragment aggregated address blocks in
other parts of the Internet and cause routing problems for other
networks.

The damage that might result from these attacks are:

     starvation: data traffic destined for a node is forwarded to a part
     of the network that cannot deliver it,

     network congestion: more data traffic is forwarded through some
     portion of the network than would otherwise need to carry the
     traffic,

     blackhole: large amounts of traffic are directed to be forwarded
     through one router that cannot handle the increased level of
     traffic and drops many/most/all packets,

     delay: data traffic destined for a node is forwarded along a path
     that is in some way inferior to the path it would otherwise take,

     looping: data traffic is forwarded along a path that loops, so that
     the data is never delivered,

     eavesdrop: data traffic is forwarded through some router or network
     that would otherwise not see the traffic, affording an opportunity
     to see the data,

     partition: some portion of the network believes that it is
     partitioned from the rest of the network when it is not,

     cut: some portion of the network believes that it has no route to
     some network that is in fact connected,

Murphy                     Expires: April 2003                  [Page 4]

INTERNET DRAFT    BGP Security Vulnerabilities Analysis     October 2002

     churn: the forwarding in the network changes at a rapid pace,
     resulting in large variations in the data delivery patterns (and
     adversely affecting congestion control techniques),

     instability: BGP become unstable so that convergence on a global
     forwarding state is not achieved, and

     overload: the BGP messages themselves become a significant portion
     of the traffic the network carries.

2.  Vulnerabilities and Risks

The risks in BGP arise from three fundamental vulnerabilities:

     no mechanism has been mandated that provides strong protection of
     the integrity, freshness and source authenticity of the messages in
     peer-peer BGP communications.

     no mechanism has been specified to validate the authority of an AS
     to announce NLRI information.

     no mechanism has been specified to ensure the authenticity of the
     AS_PATH announced by an AS.

There are four different BGP message types - OPEN, KEEPALIVE,
NOTIFICATION, and UPDATE.  This section contains a discussion of the
vulnerabilities arising from each message and the ability of outsiders
or BGP peers to exploit the vulnerabilities.  To summarize, outsiders
can use bogus OPEN, KEEPALIVE, or NOTIFICATION messages to disrupt the
BGP peer-peer connections and can use bogus UPDATE messages to disrupt
routing.  Outsiders can also disrupt BGP peer-peer connections by
inserting bogus TCP RST packets.  BGP peers themselves are permitted to
break peer-peer connections at any time, and so they cannot be said to
be issuing "bogus" OPEN, KEEPALIVE or NOTIFICATION messages.  However,
BGP peers can disrupt routing by issuing bogus UPDATE messages.  In
particular, bogus ATOMIC_AGGREGATE and AS_PATH attributes and bogus NLRI
in UPDATE messages can disrupt routing.

Each message introduces certain different vulnerabilities and risks.

2.1.  OPEN

Because receipt of a new OPEN message in the Established state will
cause the close of the BGP peering session and thereby induce the
release of all resources and deletion of all associated routes, the

Murphy                     Expires: April 2003                  [Page 5]

INTERNET DRAFT    BGP Security Vulnerabilities Analysis     October 2002

ability to spoof this message can lead to a severe disruption of
routing.

2.2.  KEEPALIVE

Receipt of a KEEPALIVE message when the peering connection is in the
OpenSent state can lead to a failure to establish a connection.  The
ability to spoof this message is a vulnerability.  To exploit this
vulnerability deliberately, the KEEPALIVE must be carefully timed in the
sequence of messages exchanged between the peers; otherwise, it causes
no damage.

2.3.  NOTIFICATION

Receipt of a NOTIFICATION message will cause the close of the BGP
peering session and thereby induce the release of all resources and
deletion of all associated routes.  Therefore, the ability to spoof this
message can lead to a severe disruption of routing.

2.4.  UPDATE

The Update message carries the routing information.  The ability to
spoof any part of this message can lead to a disruption of routing.

2.4.1.  Unfeasible Routes Length, Total Path Attribute Length

There is a vulnerability arising from the ability to modify these
fields.  If a length is modified, the message is not likely to parse
properly, resulting in an error, the transmission of a NOTIFICATION
message and the close of the connection.  As a true BGP speaker is
always able to close a connection at any time, this vulnerability
represents an additional risk only when the source is a non-BGP speaker,
i.e., it presents no additional risk from BGP sources.

2.4.2.  Withdrawn Routes

An outsider could cause the elimination of existing legitimate routes by
forging or modifying this field.  An outsider could also cause the
elimination of reestablished routes by replaying this withdrawal
information from earlier packets.

A BGP speaker could "falsely" withdraw feasible routes using this field.
However, as the BGP speaker is authoritative for the routes it will
announce, it is allowed to withdraw any previously announced routes that
it wants.  As the receiving BGP speaker will only withdraw routes

Murphy                     Expires: April 2003                  [Page 6]

INTERNET DRAFT    BGP Security Vulnerabilities Analysis     October 2002

associated with the sending BGP speaker, there is no opportunity for a
BGP speaker to withdraw another BGP speaker's routes.  Therefore, there
is no additional risk from BGP peers via this field.

2.4.3.  Path Attributes

The path attributes present many different vulnerabilities and risks.

Attribute Flags, Attribute Type Codes, Attribute Length

A BGP peer or an outsider could modify the attribute length or attribute
type (flags and type codes) so they did not reflect the attribute values
that followed.  If the flags were modified, the flags and type code
could become incompatible (i.e., a mandatory attribute marked as
partial), or a optional attribute could be interpreted as a mandatory
attribute or vice versa.  If the type code were modified,  the attribute
value could be interpreted as if it were the data type and value of a
different attribute.

The most likely result from modifying the attribute length, flags, or
type code would be a parse error of the UPDATE message.  A parse error
would cause the transmission of a NOTIFICATION message and the close of
the connection.  As a true BGP speaker is always able to close a
connection at any time, this vulnerability represents an additional risk
only when the source is an outsider, i.e., it presents no additional
risk from a BGP peer.

ORIGIN

This field indicates whether the information was learned from IGP or EGP
information.  If the route is used in inter-AS multicast routing, a
value of INCOMPLETE may be used.  This field is not used in making
routing decisions, so there are no vulnerabilities arising from this
field, either from BGP peers or outsiders.

AS_PATH

A BGP peer or outsider could announce an AS_PATH that was not accurate
for the associated NLRI.  Forwarding for the NLRI associated with the
AS_PATH could potentially be induced to follow a sub-optimal path, a
path that did not follow some intended policy, or even a path that would
not forward the traffic.  If the path would not forward the traffic, the
NLRI would become unreachable for that portion of the Internet that
accepted the false path.  If much traffic is mis-directed, some routers
and transit networks along the announced route could become flooded with

Murphy                     Expires: April 2003                  [Page 7]

INTERNET DRAFT    BGP Security Vulnerabilities Analysis     October 2002

the mis-directed traffic.

It is not clear how far an inaccurate AS_PATH could deviate from the
true AS_PATH.  It may be that the first AS in the AS_PATH, at least,
must be a legal hop.  The RFC states that a BGP speaker prepends its own
AS to an AS_PATH before announcing it to a neighbor.  If the BGP speaker
must prepend its own AS, then a BGP speaker that produced a bogus
AS_PATH could end up receiving the traffic for the associated NLRI.
This could be desirable if the error was deliberate and the intent was
to receive traffic that would not otherwise be received.  Receiving the
mis-routed traffic could be undesirable for the faulty BGP speaker if it
were not prepared to handle the extra (mis-routed) traffic.  So,
requiring a BGP peer to prepend its own AS to the AS_PATH, might
encourage or discourage it from inventing an arbitrary AS_PATH,
depending on its resources and intent.

If BGP peers need not prepend its own AS (or implementations do not
ensure that this is done), then a malicious BGP peer could announce a
path that begins with the AS of any BGP speaker with little impact on
itself.

Whether such an arbitrary AS_PATH is a vulnerability would depend on
whether BGP implementations check the AS_PATH (to see if the first AS is
the neighbor) and would catch the error.  If there are legitimate
situations in which a BGP speaker could pass an AS_PATH to a neighbor
without putting its own AS at the head of the AS_PATH, then there is no
way for implementations to detect totally bogus AS_PATHs.

Originating Routes

A special case of announcing a false AS_PATH occurs when the AS_PATH
advertises a direct connection to a specific network address.  An BGP
peer or outsider could disrupt routing to the network(s) listed in the
NLRI field by falsely advertising a direct connection to the network.
The NLRI would become unreachable to the portion of the network that
accepted this false route, unless the ultimate AS on the AS_PATH
undertook to tunnel the packets it was forwarded for this NLRI on toward
their true destination AS by a valid path.  But even when the packets
are tunneled to the correct destination AS, the route followed may not
be optimal or may not follow the intended policy.  Additionally, routing
for other networks in the Internet could be affected if the false
advertisement fragmented an aggregated address block, forcing the
routers to handle (issue UPDATES, store, manage) the multiple fragments
rather than the single aggregate.  False originations for multiple
addresses can result in routers and transit networks along the announced

Murphy                     Expires: April 2003                  [Page 8]

INTERNET DRAFT    BGP Security Vulnerabilities Analysis     October 2002

route to become flooded with mis-directed traffic.

NEXT_HOP

The NEXT_HOP attribute defines the IP address of the border router that
should be used as the next hop when forwarding the NLRI listed in the
UPDATE message.  If the recipient is an external peer, then the
recipient and the NEXT_HOP address must share a subnet.  It is clear
that an outsider modifying this field could disrupt the forwarding of
traffic between the two AS's.

In the case that the recipient of the message is an external peer of an
AS and the route was learned from another peer AS (this is one of two
forms of "third party" NEXT_HOP), then the BGP speaker advertising the
route has the opportunity to direct the recipient to forward traffic to
a BGP speaker at the NEXT_HOP address.  This affords the opportunity to
direct traffic at a router that may not be able to continue forwarding
the traffic.  It is unclear whether this would also require the
advertising BGP speaker to construct an AS_PATH mentioning the NEXT_HOP
external peer's AS.

MULTI_EXIT_DISC

The MULTI_EXIT_DISC attribute is used in UPDATE messages transmitted
between inter-AS BGP peers.  While the MULTI_EXIT_DISC received from an
inter-AS peer may be propagated within an AS, it may not be propagated
to other AS's.  Consequently, this field is only used in making routing
decisions internal to one AS.  Modifying this field, whether by an
outsider or an BGP peer, could influence routing within an AS to be sub-
optimal, but the effect should be limited in scope.

LOCAL_PREF

The LOCAL_PREF attribute must be included in all messages with internal
peers and excluded from messages with external peers.  Consequently,
modification of the LOCAL_PREF could effect the routing process within
the AS only.  Note that there is no requirement in the BGP RFC that the
LOCAL_PREF be consistent among the internal BGP speakers of an AS.  As
BGP peers are free to choose the LOCAL_PREF as they wish, modification
of this field is a vulnerability with respect to outsiders only.

ATOMIC_AGGREGATE

The ATOMIC_AGGREGATE field indicates that an AS somewhere along the way
has received a more specific and a less specific route to the NLRI and

Murphy                     Expires: April 2003                  [Page 9]

INTERNET DRAFT    BGP Security Vulnerabilities Analysis     October 2002

installed the aggregated route.  This route cannot be de-aggregated
because it is not certain that the route to more specific prefixes will
follow the listed AS_PATH.  Consequently, BGP speakers receiving a route
with ATOMIC_AGGREGATE are restricted from making the NLRI any more
specific.  Removing the ATOMIC_AGGREGATE attribute would remove the
restriction, possibly causing traffic intended for the more specific
NLRI to be routed incorrectly.   Adding the ATOMIC_AGGREGATE attribute
when no aggregation was done would have little effect, beyond
restricting the un-aggregated NLRI from being made more specific.  This
vulnerability exists whether the source is a BGP peer or an outsider.

AGGREGATOR

This field may be included by a BGP speaker who has computed the routes
represented in the UPDATE message from aggregation of other routes.  The
field contains the AS number and IP address of the last aggregator of
the route.  It is not used in making any routing decisions, so it does
not represent a vulnerability.

2.4.4.  NLRI

By modifying or forging this field, either an outsider or BGP peer
source could cause disruption of routing to the announced network,
overwhelm a router along the announced route, cause data loss when the
announced route will not forward traffic to the announced network, route
traffic by a sub-optimal route, etc.

2.5.  BGP Extensions

Several standards track extensions have been defined for BGP, e.g., [3],
[4].  Some have present additional vulnerabilities.

2.5.1.  Communities

An optional transitive path attribute called COMMUNITIES, [3], provides
for more flexible and scalable configuration of routing policies and for
control of configuration by the service provider customer.  Routing
UPDATEs may now include a communities attribute that is used by the
receiver in deciding to accept, prefer, or distribute the UPDATE route.

An outsider could forge values in this field to affect the routing
behavior of the receiver.  In particular, the defined values for this
attribute of NO_EXPORT, NO_ADVERTISE, and NO_EXPORT_SUBCONFED offer the
opportunity to affect the distribution of those routes.

Murphy                     Expires: April 2003                 [Page 10]

INTERNET DRAFT    BGP Security Vulnerabilities Analysis     October 2002

Depending on the use the receiver makes of the communities attribute, a
BGP peer who had knowledge of the routing decision process of the
receiver could misuse communities to which it was not authorized to its
own benefit or to the harm of others.

2.5.2.  Confederations

New types for AS_PATH segments called AS_CONFED_SEQUENCE and
AS_CONFED_SET, [4], offer an alternative to ful mesh IBGP sessions.  A
confederation is a collection of autonomous systems advertised to BGP
speaker outside the confederation as a single AS but within the
confederation as if they were distinct AS's.

An outsider who was able to forge this segment type could affect routing
within the confederation and consequently routing with peers as well.

The specification [4] makes no distinction between the values for
Member-AS numbers used within a confederation and AS numbers used
outside a confederation.  The possibility exists for a BGP speaker to
include a segment type of AS_CONFED_SEQUENCE or AS_CONFED_SET and use
the same Member-AS value as used in its peer's own confederation.  This
presents an opportunity to considerably affect routing between the two
confederations and inside the peer's confederation.

3.  Security Considerations

This entire memo is about security, describing an analysis of the
vulnerabilities that exist in the BGP protocol.  A companion work, [5],
describes possible security solutions and their costs.

4.  References

[1]  Y. Rekhter and T. Li,  "A Border Gateway Protocol 4 (BGP-4)",
     RFC1771, March 1995.

[2]  Y. Rekhter and T. Li, "A Border Gateway Protocol 4 (BGP-4)", work
     in progress, November 2001.  available as
     <<draft-ietf-idr-bgp4-17.txt>> at Internet-Draft shadow sites.

[3]  R. Chandra, P. Traina, and T. Li, "BGP Communities Attribute",
     RFC1997, August 1996.

[4]  P. Traina, D. McPherson, and J. Scudder, "Autonomous System
     Confederations for BGP", RFC3065, February 2001.

Murphy                     Expires: April 2003                 [Page 11]

INTERNET DRAFT    BGP Security Vulnerabilities Analysis     October 2002

[5]  S. Murphy, "BGP Security Protections", work in progress, October,
     2002.  available as
     <<draft-murphy-bgp-protect-02.txt>> at Internet-Draft shadow sites.

5.  Author's Address

Sandra Murphy
Network Associates, Inc.
NAI Labs
3060 Washington Road
Glenwood, MD  21738
EMail: [email-masked]

Murphy                     Expires: April 2003                 [Page 12]

---

From: David Barak <[email-masked]>
Date: Mon, 28 Oct 2002 10:54:20 -0500 (EST)

I have one issue with the current draft:

ORIGIN

This field indicates whether the information was learned via the EGP
Protocol [6], by manual insertion into the BGP table, or learned by some
other means.  This field is used in routing decisions, although not
widely.  This field is subject to manipulation, but the net effect of said
manipulation would be subtle.

[6] RFC 904, EGP is now depricated.

David Barak
WorldCom
Voice: +1-703-886-5500
Fax: +1-703-886-0541

"Quis custodes ipsos custodiet?" - Juvenal
=====   Fully RFC 1925 compliant   =====