06-03-2013, 09:53 AM
Symmetric Key Approaches to Securing BGP A Little Bit Trust is Enough
Symmetric Key Approaches.pdf (Size: 265.16 KB / Downloads: 20)
Abstract.
The Border Gateway Protocol (BGP) is the de facto inter-domain routing protocol that
connects autonomous systems (ASes). Despite its importance for the Internet infrastructure, BGP is
vulnerable to a variety of attacks due to lack of security mechanisms in place. Many BGP security
mechanisms have been proposed, however, none of them has been deployed because of either high cost
or high complexity. The right trade-o between eciency and security has been ever challenging.
In this paper, we attempt to trade-o between eciency and security by giving a little dose of trust to
BGP routers. We present a new
exible threat model that assumes for any path of length h, at least one
BGP router is trustworthy, where h is a parameter that can be tuned according to security requirements.
Based on this threat model, we present two new symmetric key approaches to securing BGP: the
centralized key distribution approach and the distributed key distribution approach. Comparing our
approaches to the previous SBGP scheme, our centralized approach has a 98% improvement in signature
verication. Our distributed approach has equivalent signature generation cost as in SBGP and an
improvement of 98% in signature verication. Comparing our approaches to the previous SPV scheme,
our centralized approach has a 42% improvement in signature generation and a 96% improvement
in signature verication. Our distributed approach has a 90% improvement on signature generation
cost and a 95% improvement in signature verication verication. By combining our approaches with
previous public key approaches, it is possible to simultaneously provide an increased level of security
and reduced computation cost.
Introduction
The Internet consists of independently administered networks, which are called autonomous systems (ASes).
The Border Gateway Protocol (BGP) is the de facto inter-domain routing protocol that connects ASes
together [1]. BGP provides two essential services: mapping IP prexes onto the ASes that own them and the
construction of source specic paths to each reachable prex. Every BGP router announces the IP prexes
that its AS owns in an update message and sends the message to its neighboring BGP routers. Received
update messages are recursively concatenated with an additional AS number and propagated from AS to AS
forming a routing path, which will be used to forward trac. When a BGP router receives multiple paths
for the same prex, the router chooses the best path based on multiple criteria such as path length, routing
policies, etc. Although one AS may have multiple BGP routers, all BGP routers within the same AS use the
same AS number. For simplicity, in this paper, we use the three terms \AS", \BGP router", and \router"
interchangeably when there is no confusion.
The BGP update messages are undoubtedly important as they enable ASes to construct a consistent
view of the network topology. Invalid update messages may result in incorrect routing tables, which could
lead to three types of potentially disastrous consequences. First, incorrect BGP routing tables may make a
range of IP addresses unreachable, which constitutes a deny-of-service attack. Second, incorrect BGP routing
tables may make some packets to travel through a malicious BGP router, which may launch man-in-themiddle
attacks by eavesdropping, tampering, inserting, or dropping messages. Third, incorrect BGP routing
tables may make some packets travel more hops than necessary to reach their destination, which degrades
the Internet routing performance.
BGP Overview, Security Issues and Past Solutions
In this section, we give a brief overview of the BGP protocol [1], outline the security issues in current BGP
implementations, discuss previous work, and describe our threat model and assumptions.
BGP Overview
A main objective of BGP is to advertise the routing path information for IP prexes. Towards this, BGP
routers initiate TCP connections with other BGP peers and exchange the path information in the form of
BGP update messages. For this discussion, we represent an update message as a tuple: (prex, as path),
where the prex denotes what the message needs to advertise or withdraw, and the as path denotes the
sequence of ASes through which this update message has traversed. When a BGP router receives an update
message, it will concatenate the as path eld of the message with its AS number and propagate the message
to other neighboring ASes. When a BGP router receives multiple paths for the same prex, the router chooses
the best path based on its own criteria. The information in the as path eld is critical for detecting routing
loops and deciding the best forwarding path for IP prexes. Although BGP update messages can be used to
advertise as well as withdraw IP prexes, without loss of generality, we assume that update messages contain
prex advertisement. All our discussion applies to withdraw messages as well.
BGP Security Issues
There are four major types of attacks on BGP control messages: deletion, replay, modication, and insertion.
The rst two types of attacks are out of the scope of this paper. Deleting BGP control messages seems
indistinguishable from legitimate route ltering [6]. Replay can be handled by setting expiration time for
BGP messages [6]. This paper concerns the later two types of attacks: modication and insertion. BGP path
insertion attacks are also called path forgery attacks, in which an adversary forges a path.We refer both BGP
path modication and forgery attacks as BGP path falsication attacks. There are four type of BGP control
messages: open, keepalive, notication, and update. The rst three are used by BGP to establish and maintain
BGP sessions with their peers. As stated by Hu et al., these three rst types of messages can be protected
by a point-to-point authentication protocol such as IPSec [15]. This paper concerns protecting the fourth
type of message, update messages. In particular, we concern the authenticity (to protect message insertions)
and integrity (to protect message modication) of BGP update messages. In BGP path modication attacks,
an adversary may add, remove, or alter AS numbers from the as path eld of BGP update messages. The
goal of BGP path modication and forgery attacks is to in
uence packet routing in a way that benet the
attacker.
Past Solutions for BGP Security
BGP security has been a focus of studies for some time. However, the right balance between eciency and
security as well as the right balance between practicality and complexity have been elusive. We next review
some of existing solutions. For a comprehensive survey of proposed BGP security measures, the reader can
refer to [16].
In [4], Kent et al.present S-BGP, a comprehensive framework for achieving security in BGP using two
Public-key Infrastructures (PKIs). One PKI is for issuing public-key certicates to the organizations to bind
addresses to organizations and the second PKI is for issuing public-key certicates to each BGP router to
bind AS and router associations. To validate an update, the originator of the update message, signs the
IP prexes using its private-key and sends the update to its neighboring routers. Each neighboring router
validates the update message using the several certicates produced by the originating BGP router. Upon
validating the message through signature verication, the neighboring router creates a route attestation i.e.,
it updates the as path eld, signs it with its private key and appends it to the original message to create
the new update. Every transit router veries all the attached signatures and adds its own route attestation
to the update message. Thus, the update is protected against path modication and forgery attacks in this
manner. However, S-BGP places signicant computation overhead on the BGP routers since digital signature
creation and verication are costly as studied in [13] and degrades performance of the BGP routers. For this
reason, ISPs have been reluctant to deploy S-BGP.
Threat Model and Assumptions
Next we describe our threat model and the assumptions that are used to address BGP path falsication
problems. Our threat model is based on the various falsication attacks [16] on the BGP protocol, some of
which have been detailed in Section 2.2. From these attacks, the types of falsication attacks that we address
in this work are: generation of false update messages by spoong source IP address, insertion or deletion of
AS numbers from the as path eld, and changing the order of AS numbers in the as path eld. Note that, a
combination of these attacks is also possible. We address such combined attacks as well.
We assume that one or more BGP routers could be malicious. However, we assume that there is at least
one non-malicious node along a given path of length k. We treat any misconguration of BGP routers as
malicious and accordingly address this from the point of view of falsication.
Symmetric Key Management for Securing BGP
We examine two types of symmetric key distribution approaches for securing BGP messages. In the rst
approach, a centralized controller establishes the necessary keys among the BGP routers and hence, we call
protocols using this approach as centralized key distribution protocols. In the second approach, we assume
that a centralized controller does not exist and each AS distributes the necessary keys to the BGP routers of
other ASes. We call key distribution protocols using this approach as distributed key distribution protocols.
We show the use of both these approaches to achieve authentication in the BGP.
Centralized Key Distribution Protocols
In this section, rst, we describe the square grid key distribution protocol [21] in Section 3.1. Then, in Section
3.1, we describe how the square grid protocol can be used to achieve security of the BGP update messages
in Section 3.1. Finally, in Section 3.1, we describe extensions of grid protocol that provide simular properties
while reducing the number of keys compared to the protocol in [22].