[Search] [txt|pdf|bibtex] [Tracker] [Email] [Diff1] [Diff2] [Nits]

Versions: 00 01 02 03 04                                                
Network Working Group                                       Sandra Murphy
INTERNET DRAFT                                Trusted Information Systems
draft-murphy-bgp-secr-01.txt                                  August 1998


                         BGP Security Analysis



Status of this Memo

This document is an Internet-Draft.  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."

To view the entire list of current Internet-Drafts, please check the
"1id-abstracts.txt" listing contained in the Internet-Drafts Shadow
Directories on ftp.is.co.za (Africa), ftp.nordu.net (Northern Europe),
ftp.nis.garr.it (Southern Europe), munnari.oz.au (Pacific Rim),
ftp.ietf.org (US East Coast), or ftp.isi.edu (US West Coast).


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 data it communicates or of its own
behavior.  There are no mechanisms in BGP to protect against attacks
that modify, delete, forge, or replay data, any of which has the
potential to be destructive of overall network routing behavior.

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









Murphy                     Expires: Feb 1999                    [Page 1]


INTERNET DRAFT           BGP Security Analysis               August 1998


Table of Contents


 Status of this Memo ..............................................    1
 Abstract .........................................................    1
1 Introduction ....................................................    4
2 Vulnerabilities .................................................    5
3 Possible Protections ............................................    5
3.1 Threats from non-BGP peers ....................................    5
3.1.1 IP level protection .........................................    6
3.1.2 TCP level protection ........................................    6
3.1.3 BGP level protection ........................................    6
3.2 Threats from BGP peers ........................................    7
3.3 Sign Originating AS ...........................................    7
3.4 Sign Originating AS and Predecessor Information ...............    8
3.5 Sign Originating AS and AS_PATH ...............................    9
3.5.1 Special Considerations ......................................   11
3.6 Rely on Registries ............................................   12
4 Security Costs ..................................................   13
4.1 Protecting the Peer-Peer Link .................................   13
4.2 Sign Originating AS ...........................................   14
4.3 Sign Originating AS and Predecessor Information ...............   14
4.4 Sign Originating AS and AS_PATH ...............................   14
4.5 Rely on Registries ............................................   14
5 Authentication vs Authorization .................................   15
5.1 Authentication without Authorization ..........................   15
5.2 Authorization without Authentication ..........................   15
6 Security Considerations .........................................   16
7 References ......................................................   16
8 Author's Address ................................................   16
A Appendix A - Vulnerabilities ....................................   18
A.1 OPEN ..........................................................   18
A.2 KEEPALIVE .....................................................   18
A.3 NOTIFICATION ..................................................   18
A.4 UPDATE ........................................................   18
A.4.1 Unfeasible Routes Length, Total Path Attribute Length .......   18
A.4.2 Withdrawn Routes ............................................   19
A.4.3 Path Attributes .............................................   19
 Attribute Flags, Attribute Type Codes, Attribute Length ..........   19
 ORIGIN ...........................................................   19
 AS_PATH ..........................................................   20
 Originating Routes ...............................................   20
 NEXT_HOP .........................................................   21
 MULTI_EXIT_DISC ..................................................   21
 LOCAL_PREF .......................................................   21





Murphy                     Expires: Feb 1999                    [Page 2]


INTERNET DRAFT           BGP Security Analysis               August 1998


 ATOMIC_AGGREGATE .................................................   21
 AGGREGATOR .......................................................   22
A.4.4 NLRI ........................................................   22















































Murphy                     Expires: Feb 1999                    [Page 3]


INTERNET DRAFT           BGP Security Analysis               August 1998


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].
We propose several different security solutions to protect these
vulnerabilities, discuss the benefits derived from each solution and its
cost.

It is clear that the Internet is vulnerable to attack through its
routing protocols.  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 non-BGP peers or
true BGP peers.

As an IP protocol, BGP is subject to all the IP attacks, like IP
spoofing, session stealing, SYN attacks, etc.  Under the present BGP
design, any non-BGP peer source can inject believable BGP packets into
the communication between BGP peers and thereby inject bogus routing
information or break the peer to peer connection.  With IP spoofing, the
non-BGP peer sources of bogus BGP information can reside anywhere in the
world.  Furthermore, non-BGP peer sources can disrupt communications
between BGP peers by breaking their TCP connection with spoofed RST
packets.  BGP speakers themselves can inject bogus routing information
masquerading as information from any other legitimate BGP speaker.
Bogus information from either non-BGP or BGP sources can affect routing
behavior in the Internet over a wide, possibly unbounded, area.

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
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.  Traffic to that network could be delayed or the network could
become unreachable from areas where the bogus information is accepted.
If the bogus information makes it appear that an autonomous system





Murphy                     Expires: Feb 1999                    [Page 4]


INTERNET DRAFT           BGP Security Analysis               August 1998


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.

2.  Vulnerabilities

There are four different BGP message types - OPEN, KEEPALIVE,
NOTIFICATION, and UPDATE.  A discussion of the vulnerabilities arising
from each message and the ability of non-BGP peers or BGP peers to
exploit the vulnerabilities is contained in Appendix A.  Suffice it to
say here that non-BGP peers can use bogus OPEN, KEEPALIVE, or
NOTIFICATION messages to disrupt the BGP peer-peer connections and can
use bogus UPDATE messages to disrupt routing.  Non-BGP peers 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.

3.  Possible Protections

3.1.  Threats from non-BGP peers

Non-BGP peers can be prevented from disrupting routing by providing
cryptographic protection of the BGP peer-peer connection.  The
cryptography chosen should protect the source authenticity and integrity
of the message and should also protect against replay.  As the
protection is only of the peer-peer communications, asymmetric
cryptography is not needed.  Protection against spoofing in the peer-
peer connection could be provided by:

     IP level protection as defined by IPSEC [7]

     TCP level protection as defined by [8]

     BGP level protection as defined by [9]

Prevention of IP spoofing completely removes any risk associated with
bogus OPEN, KEEPALIVE, or NOTIFICATION messages, as the only
vulnerabilities from these messages come from non-BGP peers.  It also





Murphy                     Expires: Feb 1999                    [Page 5]


INTERNET DRAFT           BGP Security Analysis               August 1998


protects against all threats from bogus UPDATE messages and from bogus
TCP messages arising from non-BGP peers.

3.1.1.  IP level protection

Protection as specified for the IPSEC AH header [7] can be used to
provide connectionless integrity, data origin authentication, and an
optional anti-replay service.

3.1.2.  TCP level protection

It is possible to protect the peer-peer connection by applying
cryptographic protection at the TCP level to provide connectionless
integrity and data origin authentication.  This has been in use with
some vendors for some time as specified in [8].  Note, however, that the
protections specified in [8] were put in place some time ago.  The IPSEC
protections have advanced since that time.  In particular, the
protections of [8] use MD5 directly, where the IPSEC protections mandate
the use of HMAC-MD5 because of recently publicized concerns of
collisions in MD5.  Also, [8] does not have the provisions for anti-
reply found in IPSEC.  The TCP sequence numbers do provide some
protection against replay. But as some packets, notably a RST packet,
need only be within the receive window to be accepted, the TCP sequence
number protection is not complete.  Finally, [8] has no provisions for
multiple keys to be used in rekeying.  As these are pairwise keys used
for long-lived sessions, the inability to specify multiple keys may not
cause operational difficulties.

Although the TCP level protection specified in [8] has deficiencies when
compared with the protection of IPSEC [7], it is vastly preferable to a
unprotected connection.  If IPSEC is not available, then the TCP level
protection of [8] should definitely be used.  When IPSEC is available,
IPSEC is preferable.

3.1.3.  BGP level protection

Cryptographic protection of the peer-peer connection at the BGP level is
specified in [9].  Note that applying the cryptographic protection
within BGP does not provide the same protection as applying it within
TCP, as TCP information other than the payload (BGP) data, particularly
the RST field, could still be spoofed in ways that would harm the
connection.








Murphy                     Expires: Feb 1999                    [Page 6]


INTERNET DRAFT           BGP Security Analysis               August 1998


3.2.  Threats from BGP peers

Protection of the communication between BGP peers does nothing to
protect against errors introduced by the BGP speakers themselves.  BGP
speakers can introduce bogus routing information, e.g., invalid
AS_PATHs, incorrect announcements of NLRI, etc., at any time.
Furthermore, detecting the BGP peer of bogus information (if and when
the bogus-ness is detected) can be difficult if not impossible.

There are several possible solutions to prevent a BGP speaker from
inserting bogus information in its advertisements to its peers.

(1)  sign the originating AS.

(2)  sign the originating AS and predecessor information

(3)  sign the originating AS, and nest signatures of AS_PATHs to the
     number of consecutive bad routers you want to prevent from causing
     damage.

(4)  rely on a registry to say if AS_PATH and originating AS are valid

3.3.  Sign Originating AS

It would be beneficial to know which AS has first advertised a route to
a NLRI.  This could be done by including a new field which would contain
the originating AS number and the originating AS's digital signature [3]
of that plus the NLRI advertised. A digital signature is required
because the number and identities of all eventual recipients could not
be known and because non-repudiation would be desired.  This field could
be verified against an Internet registry, if a complete and accurate
registry existed.  If routing was disturbed by the presence of this
advertisement, then the culprit could be determined.

If a structure exists representing ownership of network addresses, then
the owner as well as the advertiser could sign.  A representation of an
owner could be useful when Internet service providers transfer sub-
blocks of their owned addresses to smaller ISP's.  The ISP's could
advertise NLRI but the ownership of the network could still be
determined.

If routes are aggregated by a BGP speaker and the aggregated route
advertised, then the idea of "originator" and "owner" become less
useful.  There might be several "originators" and "owners" represented
among the aggregated routes.  We suggest that the AGGREGATOR field





Murphy                     Expires: Feb 1999                    [Page 7]


INTERNET DRAFT           BGP Security Analysis               August 1998


become mandatory and that an aggregating BGP speaker append its
signature of the AGGREGATOR field and the aggregated NLRI.
Unfortunately, aggregation prevents identification of the specific
culprit should it be discovered that a network is being originated in
error.

3.4.  Sign Originating AS and Predecessor Information

Reference [2] suggests several different types of cryptographic
protection of BGP.  The suggested protection against possibly faulty BGP
speakers introduces some link state topology information (see [4]) that
can be used to verify AS_PATHs.

To obviate the need to trust BGP speakers regarding NLRI information not
specific to their own AS, [2] suggests adding the following information
to the UPDATE message:

-    the AS originating the information (either the aggregator or the
     advertiser of a direct route) and

-    the predecessor of the originating AS (i.e., the neighbor to which
     the NLRI is first advertised).

This field is digitally signed along with the NLRI, the
ATOMIC_AGGREGATE, and other fields of the UPDATE message.  The signature
and the predecessor information must be included as the route in the
UPDATE message propagates across the network, i.e., it is transitive.

This information distributes a bit of link state topology information,
concerning just the last hop before the destination network's AS, into
the usual BGP distance vector (some say "path vector") protocol.  Each
BGP speaker, even those who are transit only and originate no UPDATE
messages with NLRI contained in their own AS, will transmit this
"predecessor" information.  From all the signed predecessor information
received, it would be possible to verify that each of the adjacencies
represented in an AS_PATH is legitimate.  When a segment of an AS_PATH
is a sequence, each adjacent pair in the sequence must correspond to a
received signed predecessor tuple.

The protection provided by the signed predecessor information becomes
more difficult to use past an aggregation point where a BGP speaker
advertises a less specific route which includes the NLRI.  In
particular, the rules for verifying an AS_PATH containing a segment that
is a set would be either very lenient or very complex.






Murphy                     Expires: Feb 1999                    [Page 8]


INTERNET DRAFT           BGP Security Analysis               August 1998


While this predecessor information assures that each adjacency in a
sequence of an AS_PATH is valid, it does not ensure that the AS_PATH as
a whole is valid.  Each AS's decision regarding routes it will advertise
and traffic it will transit is individual and totally unconstrained.
The fact that a valid path of ASs exists to a destination does not
ensure that the corresponding AS_PATH is valid.  This mechanism also
does not assure that any information which comes from one router alone
(LOCAL_PREF, NEXT_HOP, AGGREGATOR, etc.) is accurate.  A router, then,
can still falsely announce that its neighbor should be forwarded the
traffic for an NLRI.

3.5.  Sign Originating AS and AS_PATH

A protection against possibly faulty BGP speakers that does provide some
assurance that the AS_PATH is valid involves nested digital signatures
of the AS_PATH.

Each BGP speaker would receive signed AS_PATH information (including the
ATOMIC_AGGREGATE attribute and NLRI) from its peer.  After making its
routing decision, it would augment the chosen AS_PATH with its own AS
and sign the resulting route (NLRI + AS_PATH) and ATOMIC_AGGREGATE.  The
BGP speaker would pass to its peers the augmented AS_PATH, its
signature, and the signature it received from its peer which covers the
base AS_PATH from which the augmented AS_PATH was formed.  The peer
receiving this information can verify that the received AS_PATH was
indeed constructed with some basis in reality by verifying the signature
of the BGP speaker's peer over the tail of the received AS_PATH.  The
BGP speaker's signature will be passed on by the peer to provide similar
assurance that it constructed its advertised AS_PATH legitimately.

This procedure as described protects against one consecutive faulty
router in the path.  If it is desired to protect against more possibly
faulty routers in the path, then the procedure can be nested
arbitrarily.  To protect against K consecutive faulty routers, each
router would receive signed AS_PATH information from its neighbor along
with K signatures of the preceding K BGP speakers in the path, each
successive signature covering a shorter suffix of the AS_PATH.  It would
pass on a newly constructed AS_PATH along with its own signature, its
neighbor's signature and K-1 of the included nested signatures.

A BGP speaker could snip out a suffix of the data it received as well as
the associated signatures and pass those on as the proof that its
AS_PATH was based on reality.  To prevent this, the signatures generated
should cover not only the route information but the intended receiver as
well.





Murphy                     Expires: Feb 1999                    [Page 9]


INTERNET DRAFT           BGP Security Analysis               August 1998


For example, consider a case where it was decided to protect against
only one faulty BGP speaker.  Suppose AS1 receives an AS_PATH from AS2
of 'AS2 AS3 ... ASk'.  (In this discussion as well as the next,
ATOMIC_AGGREGATE will be included in the signature, but is omitted for
brevity.) Then AS1 should also receive AS2's signature of "AS1, 'AS2 AS3
... ASk', Ni" and AS3's signature of "AS2, 'AS3 ... ASk', Ni".  AS1
would compute a path as 'AS1 AS2 AS3 ... ASk', and pass on to AS0 this
path along with its signature of "AS0, 'AS1 AS2 AS3 ... ASk', Ni" and
AS2's signature of "AS1, 'AS2 AS3 ... ASk', Ni".

The procedure in its full glory is as follows, where sign(A,B,C)[ASk]
means the signature of the data A,B,C generated with the key belonging
to ASk:

     Given that it has been decided to protect against K faulty BGP
     speakers:

     When AS0 receives an UPDATE with AS_PATH 'ASi ... ASj' for NLRI N,
     it

     -    verifies the signature from the UPDATE:

               sign(AS0,'ASi ... ASj', N)[ASi],

          this is a sanity check

     -    verifies the K signatures from the UPDATE:

               sign(ASi,'ASi+1 ... ASj', N)[ASi+1],
               sign(ASi+1,'ASi+2 ... ASj', N)[ASi+2], ... ,
               sign(ASi+K-1, 'ASi+K ... ASj', N)[ASi+K]

          If any signature fails to validate, then ASi did not have a
          valid basis for the route sent to AS0.  AS0 should drop the
          route.

     When AS0 chooses the AS_PATH 'ASi ... ASj' for NLRI N to send to
     its neighbor ASn, it

     -    signs (ASn, 'AS0 ASi ... ASj', N)[AS0] and includes it in the
     UPDATE

     -    sends the K signatures in the UPDATE:







Murphy                     Expires: Feb 1999                   [Page 10]


INTERNET DRAFT           BGP Security Analysis               August 1998


               sign(AS0,'ASi ... ASj', N)[ASi],
               sign(ASi,'ASi+1 ... ASj', N)[ASi+1], ... ,
               sign(ASi+K-2, 'ASi+K-1 ... ASj', N)[ASi+K-1]

This discussion is predicated on the use of asymmetric cryptography.
Each autonomous system would be required to possess an asymmetric key
pair.  The public key would have to be accessible to all recipients of
the digital signature.  The private key would have to be available to
all BGP speakers in the autonomous system, but protected from exposure.
Alternatively, each BGP speaker could possess its own asymmetric key
pair, at the cost of further complicating the protocol.  The protocol
would have to be altered to include the identity of the BGP speaker
within the AS who produces the AS_PATH and signature so that the
signature verification procedure could choose the correct public key to
use.  Each BGP speaker with N peers needs to generate N signatures for
each route announced, one for each peer.

Symmetric cryptography could be used to protect the information by using
a keyed cryptographic hash instead of a digital signature.  However, in
order to provide the same level of protection against faulty routing,
each BGP speaker would have to share a different secret key with each of
its neighbors and each of its neighbors' neighbors.  For N peers, each
with M peers, this means N*M+N keys and N*M+M keyed cryptographic hashes
of each update.  (In the case that it is desired to protect against k>1
faulty BGP speakers, the number of keys would grow exponentially - a
different key with all neighbors, 2-hops-away neighbors, 3-hops-away
neighbors, and k+1-hop-away neighbors.) This is obviously not a scalable
solution.  It may also require autonomous systems to reveal their
peering agreements where they would not wish to do so.

3.5.1.  Special Considerations

Note that this scheme becomes more complicated when one of the BGP
speakers performs aggregation of a set of routes.  To assure recipients
of the validity of the aggregated route, it would be necessary to pass
on the text and signatures of each of the aggregated component routes.
This means an enormous increase in transmission bandwidth at each
aggregation point and a similar increase in verification time at each
verification point's peers.  This cost would not have to be passed on to
further neighbors further than K (the nesting level of signatures) hops
away, but it does violate the spirit of aggregation.  Alternatively, an
aggregation point could be treated as another type of origination point,
and signatures and verification would stop at that point.
Unfortunately, that provides a mechanism for malicious BGP peers to
announce bogus routes, simply by claiming to have aggregated the





Murphy                     Expires: Feb 1999                   [Page 11]


INTERNET DRAFT           BGP Security Analysis               August 1998


information.  Aggregation also prevents identification of the specific
culprit should it be discovered that a network is being originated in
error.

Note that this scheme does not assure that the received route is the
best route the peer could have computed.  In particular, it does not
guard against a peer that does not announce the best result of its
decision process - a peer that replays previous announcements, perhaps,
or does not change its announcements when it receives withdrawn routes,
or replays withdrawal information after a route is reestablished.  These
are a matter for the internal correct operation of the router and cannot
be precluded by security protection.  This mechanism also does not
assure that any information which comes from one router alone
(LOCAL_PREF, NEXT_HOP, AGGREGATOR, etc.) is accurate.  With these
fields, a router can still falsely announce that its neighbor should be
forwarded the traffic for an NLRI.

Note that the verification process chooses the key to use based on the
AS's mentioned in the AS_PATH.  If it is valid for a BGP speaker not to
prepend its own AS to the AS_PATH before transmitting it to a peer, i.e.
if a BGP speaker is allowed to pass on an AS_PATH in which it's own AS
is not the first in the PATH, then the AS's mentioned in the AS_PATH are
not necessarily the AS's that produced the signature.  In that case,
this verification process could be using the wrong key.  This signature
scheme would have to be complicated by requiring either

     that the sender's AS be included in the UPDATE message and the
     signature (so that the verification process could find the
     appropriate key for the signature)

     or that each sender know the private key of the first AS in the
     AS_PATH (so that the signature and verification processes would be
     using the same key).

Sharing keys between AS's makes those AS's indistinguishable to the
cryptography; the second alternative design should only be chosen with
that caution clearly understood.

3.6.  Rely on Registries

The Internet registries can provide data that will help to assure that
AS_PATHS and NLRI origination data are correct.  If the data registered
in the Internet registries can be assumed to be correct, then the
peering information in the database can be used to verify each pair of
AS's in an AS_PATH sequence segment are truly peers.  Depending on the





Murphy                     Expires: Feb 1999                   [Page 12]


INTERNET DRAFT           BGP Security Analysis               August 1998


sophistication of the information recorded in the registry, the
registries might also be used to verify that the AS_PATH as a whole was
valid.

The assurance provided by this protection would rely on the completeness
of the registry, on the authenticity of the registry data and on the
protection it received in storage and transit.  The protection is useful
if data from the registry is either available locally or retrievable
with an acceptable lag time.

The assurance provided by this protection also relies on the openness of
the data recorded in the registries.  To be truly useful, each
autonomous system's policy would have to be recorded in the registry, in
order that the AS_PATH as a whole can be verified to be valid.
Information about policy, however, can be sensitive to an autonomous
system and not openly available to every other autonomous system.  Any
restrictions on the availability of information stored in the registry
will restrict its applicability as a protection mechanism.

4.  Security Costs

Choosing the protection to apply in any situation depends on the
perception of the risk of attack, of the damage that can result, of the
benefits derived from providing the protection, and of the cost of
providing the protection.  This section discusses the cost of each of
the protection options mentioned above.

4.1.  Protecting the Peer-Peer Link

The cost of this protection is the processing required for the
cryptography and the need to establish and manage the cryptographic
keys.  The cryptography need not be computationally expensive; HMAC or
similar algorithms can be used.  Shared secret keys are adequate for
this protection, as the protection applies only to the communication
between peers, so the key management cost is low.  Ideally, a separate
key should be used for each BGP peering.  One key might be used for
multiple peerings with a reduction in the level of protection that is
provided.  However, it is best to remember that apocryphally, the more
places know a secret, the more chances it will be exposed.

This level of protection is low cost and protects against the vast
number of possible adversaries (i.e., any non-BGP speaker in the
internet).







Murphy                     Expires: Feb 1999                   [Page 13]


INTERNET DRAFT           BGP Security Analysis               August 1998


4.2.  Sign Originating AS

The cost of signing the originating AS of each route is the cost of
providing a public key infrastructure to generate an asymmetric key pair
for each autonomous system and to distribute and maintain the public
keys associated with each autonomous system.

4.3.  Sign Originating AS and Predecessor Information

This scheme requires the same public key infrastructure as is needed if
one simply signs the originating AS information.  It also requires that
each adjacency for a BGP speaker be signed (the "predecessor"
information) and transmitted along with an AS_PATH.  Essentially, each
BGP speaker must announce its peers, something that does not currently
occur in the BGP protocol.  Each BGP speaker must compute one signature
for each NLRI in each UPDATE message transmitted and must verify one
signature for each NLRI in each UPDATE message received.  (Each UPDATE
message must be separately signed because the mechanism described in [2]
includes a sequence number, the Withdrawn Routes and the Unfeasible
Route Length fields, so the information to be signed changes with each
message.  These fields are protected from non-BGP peers by the peer-peer
communication protection and so do not need to be digitally signed.  If
only the NLRI, ATOMIC_AGGREGATE and predecessor information were signed
each time, then the signature might not have to be computed with each
new UPDATE message, i.e., AS_PATH changes would not induce new signature
computations.)  The predecessor information in each route must be stored
by the recipient indefinitely.  Each route received must be verified by
comparison to the store of predecessor information previously received
in UPDATE messages from all AS sources.

4.4.  Sign Originating AS and AS_PATH

This scheme requires the same public key infrastructure as is needed if
one simply signs the originating AS information.  For each UPDATE
message received, K signatures (the level of protection from consecutive
faulty routers) must be verified per NLRI included in the UPDATE.  For
each UPDATE message transmitted, one signature must be computed for each
NLRI per recipient. As discussed before, prevention of cut and paste
attacks requires that the signature include the recipient, so computing
one signature per AS_PATH and NLRI announced is insufficient.

4.5.  Rely on Registries

The cost of relying on registries would vary considerably depending on
the protection provided to the information in storage and in transit.





Murphy                     Expires: Feb 1999                   [Page 14]


INTERNET DRAFT           BGP Security Analysis               August 1998


Any latency, above that caused by the use of cryptography, would depend
on the mechanism used to protect the registry information (e.g.,
anything from frequent complete download to real-time query and
response).

5.  Authentication vs Authorization

5.1.  Authentication without Authorization

Each of the schemes described above provide authentication of the
information received.  This is not sufficient for secure operation - the
BGP participants also need assurance that a BGP announcing a route is
authorized to announce that route.  Signing the predecessor information,
nesting signatures of the AS_PATH, or consulting the registry for AS
peering arrangements help to prove that a BGP peer has a valid authority
for announcing a route (either that the connectivity exists or that the
peer based the route on a valid route from its peer).  None of the
schemes provide any assurance that a BGP speaker originating an NLRI is
authorized to advertise that NLRI.

Authorization implies an authority to which one can refer.  To prove the
authority to originate an NLRI, there must be an infrastructure for
assigning NLRI to autonomous systems.  The Internet registries could
serve as this authority, providing the registry itself contained valid
information, the communication with the registry was secure, etc.  Work
is ongoing to provide assurance about information contained in the
registries using RPS [5].  Other proposals suggest using the DNS inverse
lookup tree as a distributed mechanism for maintaining authorization
information [6].

5.2.  Authorization without Authentication

Schemes have been proposed to provide authorization for AS announcements
of NLRI.  As mentioned above, work is ongoing to provide for
authorization and authentication of network assignments to autonomous
systems, of peering agreements, transit policies, etc., for those
Internet registries employing the RPS [5].  Another scheme proposes to
use the DNS reverse lookup tree, CNAMES and a new AS resource record to
associate networks with autonomous systems [6].  These mechanisms
provide assurance that the AS announcing an NLRI is authorized to do so,
but they will not provide assurance of the authenticity of the source of
the announcement.  This provides protection against misconfigured or
faulty BGP speakers accidentally announcing bogus direct connections to
NLRI, but not against malicious BGP speakers making deliberate bogus
announcements.  Protected Internet registries can also be used to verify





Murphy                     Expires: Feb 1999                   [Page 15]


INTERNET DRAFT           BGP Security Analysis               August 1998


authorization for AS_PATH information, as long as autonomous systems
maintain complete information of their peering agreements and transit
policies in the registries.

6.  Security Considerations

This entire memo is about security considerations.

7.  References

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

[2]  B. Smith and J.J. Garcia-Luna-Aceves, ``Securing the Border Gateway
     Routing Protocol,'' Proc. Global Internet'96, London, UK, 20-21
     November 1996.

[3]  Bruce Schneier.  Applied Cryptography Protocols, Algorithms, and
     Source Code in C, John Wiley & Sons, Inc 1994.

[4]  RFC 1583, OSPF Version 2.  John Moy.  March 1994.

[5]  Curtis. Villamizar, Cenzig. Alaettinoglu, David. Meyer, Sandy.
     Murphy and Carol. Orange.  "Routing Policy System Security", May
     15, 1998.  Work in progress, available as <<draft-ietf-rps-auth-
     01.txt>> at Internet-Drafts Shadow Directories.

[6]  Tony Bates, Randy Bush, Tony Li and Yakov Rekhter.  "DNS-based NLRI
     origin AS verification in BGP", February 6, 1998.  Work in
     progress, available as <<draft-bates-bgp4-nlri-orig-verif-00.txt>>
     at Internet-Drafts Shadow Directories.

[7]  RFC1826, IP Authentication Header. R. Atkinson. August 1995.

[8]  RFCnnn, Protection of BGP Sessions via the TCP MD5 Signature
     Option.  A. Heffernan. August 1998.

[9]  T. Przygienda, "BGP-4 MD5 Authentication", 5 November 1997.  Work
     in progress, available as <<draft-przygienda-bgp-md5-00.txt>> at
     Internet-Drafts Shadow Directories.

8.  Author's Address

Sandra Murphy
Trusted Information Systems





Murphy                     Expires: Feb 1999                   [Page 16]


INTERNET DRAFT           BGP Security Analysis               August 1998


3060 Washington Road
Glenwood, MD  21738
EMail: Sandy@tis.com















































Murphy                     Expires: Feb 1999                   [Page 17]


INTERNET DRAFT           BGP Security Analysis               August 1998


A.  Appendix A - Vulnerabilities

Each message introduces certain different vulnerabilities:

A.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
ability to spoof this message can lead to a severe disruption of
routing.

A.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 or it causes no damage.

A.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.

A.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.

A.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.









Murphy                     Expires: Feb 1999                   [Page 18]


INTERNET DRAFT           BGP Security Analysis               August 1998


A.4.2.  Withdrawn Routes

A non-BGP peer could cause the elimination of existing legitimate routes
by forging or modifying this field.  A non-BGP peer 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
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 vulnerability from BGP peers via this field.

A.4.3.  Path Attributes

The path attributes present many different vulnerabilities.

Attribute Flags, Attribute Type Codes, Attribute Length

A BGP peer or a non-BGP peer could modify the attribute length or
attribute type (flags and type codes) so they did not reflect the
attribute values that followed.  If the length were modified, the likely
result would be that the UPDATE message would not parse correctly.  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.  Modifying the type code could cause the attribute value to be
interpreted as if it were the data type and value of a different
attribute.  The most likely result from modifying the attribute flags or
type code would be a parse error of the UPDATE message.  A parse error
from any modification 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 a non-BGP peer,
i.e., it presents no additional risk from 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
values 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 non-BGP peers.





Murphy                     Expires: Feb 1999                   [Page 19]


INTERNET DRAFT           BGP Security Analysis               August 1998


AS_PATH

A BGP peer or non-BGP peer 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.

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, if a
BGP peer must prepend its own AS to the AS_PATH, it might be encouraged
or discouraged from inventing an arbitrary AS_PATH, depending on its
resources and intent.  If BGP peers need not prepend its own AS, 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 non-BGP peer 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
ultimate AS tunnels the packets on 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





Murphy                     Expires: Feb 1999                   [Page 20]


INTERNET DRAFT           BGP Security Analysis               August 1998


block.

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 a non-BGP peer modifying this field could disrupt the forwarding of
traffic between the two AS's.

In the case that the NEXT_HOP address is an inter-AS peer and the
recipient of the message is an inter-AS peer of a different 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 (the NEXT_HOP peer) 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 inter-AS 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 non-
BGP peer 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 non-BGP peers 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
installed the aggregated route.  This route cannot be de-aggregated





Murphy                     Expires: Feb 1999                   [Page 21]


INTERNET DRAFT           BGP Security Analysis               August 1998


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 a non-BGP peer.

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.

A.4.4.  NLRI

By modifying or forging this field, either a non-BGP peer 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.

























Murphy                     Expires: Feb 1999                   [Page 22]