|
URL:
|
https://www.cs.dartmouth.edu/~sws/pubs/nsz04.pdf
|
|
Entry Date:
|
2002-5-26
|
|
Abstract:
|
The Border Gateway Protocol (BGP) determines how Internet traffic is routed
throughout the entire world; malicious behavior by one or more BGP speakers
could create serious security issues. Since the protocol depends on a speaker
honestly reporting path information sent by previous speakers and involves a
large number of independent speakers, the Secure BGP (S-BGP) approach uses
public-key cryptography to ensure that a malicious speaker cannot fabricate
this information. However, such public-key cryptography is expensive: S-BGP
requires a digital signature operation on each announcement sent to each peer,
and a linear (in the length of the path) number of verifications on each
receipt. We use simulation of a 110 AS system derived from the Internet to
evaluate the impact that the processing costs of cryptography have on BGP
convergence time. We find that under heavy load the convergence time using
ordinary S-BGP is nearly twice as large as under BGP. We examine the impact of
highly aggressive caching and pre-computation optimizations for S-BGP, and find
that convergence time is much closer to BGP. However, these optimizations may
be unrealistic, and are certainly expensive of memory. We consequently use the
structure of BGP processing to design optimizations that reduce cryptographic
overhead by amortizing the cost of private-key signatures over many messages.
We call this method Signature-Amortization (S-A). We find that S-A provides as
good or better convergence times as the highly optimized S-BGP, but without the
cost and complications of caching and pre-computation. It is possible therefore
to minimize the impact route validation has on convergence, by being careful
with signatures, rather than consumptive of memory.
|
|
Results:
|
-
Introduces SA-BGP: modifications to SBGP that make the use of RSA in
SBGP
feasible. SBGP normally uses DSA because of its shorter key length and the
potential to exploit precomputation in the signature step. The flip side is
that verifications take an order of a magnitude longer in DSA than in RSA.
This paper revisits that trade-off. The main metric for comparing various
forms of (S)BGP is convergence time. SA-BGP using RSA has convergence time
comparable to SBGP using cpDSA, where cpDSA is a highly
optimised form of DSA that
employs precomputation and (potentially heavy) caching.
Two variants of SA-BGP are discussed:
-
In the first variant, SA-BGP amortises
signature generation by a BGP speaker by allowing the speaker to send the
same BGP update (thus carrying the same signature) to all of its peers (for
the same prefix and attributes). Normally under SBGP a different message
(therefore carrying a different signature) must be sent to each peer since
the peer must be named in the update. In SA-BGP the speaker enumerates
all
peers for which an update is intended in a bitmap, allowing the update to be
sent to all of these peers. An issue that is not fully solved is
how these peers can know their logical identity in the bitmap and how they
can prove this to other BGP speakers.
-
In the second SA-BGP variant further amortisation is achieved by
aggregating signature generation over multiple independent announcements
(announcements carrying different attributes and prefixes). Signature
generation is performed when the MRAI timer fires.
The experiments show that this second variant gains little
over the first variant.
For the first variant, the paper ignores the fact that a BGP speaker may want
to set per-peer attributes, which causes messages announcing the same prefix
to be different.
-
Quantifies the effects cryptographic processing has on convergence of a BGP
routing system. Unoptimised SBGP significantly increases convergence time for
highly connected routers under high load. However, convergence of SBGP over
cpDSA and of SA-BGP is close to BGP without cryptography.
-
Provides figures quantifying delay imposed by a BGP speaker's
processing of BGP update messages, with and without security
processing.
-
Provides a good overview of SBGP and the security issues SBGP focuses on
(e.g. RSA vs DSA).
|
|
Experiments:
|
-
To evaluate update processing, simulation with SSFNet is used. The simulated
topology consists of 110 ASes, each represented by a single BGP speaker, and
is
derived (using heuristics) from a large AS topology that was built from
Internet measurements. Properties of the simulation topology are:
- highest node connectivity is 24
- median node connectivity is 6
- lowest node connectivity is 2
Settings for BGP behaviour in the simulation are as follows:
- Updates are sent to all peers
- Path selection is by path length
- The default SSFNet value of the MRAI timer is used
- Each AS originates 2 prefixes
-
A local BGP router (200MHz CPU clock) was measured to determine service
time for BGP update processing (including route filtering and selection
but without SBGP processing). The resulting range that was input into
the simulation is 32.5 ms to 97.5 ms.
-
Two scenarios are measured in the simulation: (i) newly announced prefixes
and (ii) router rebooting following a crash. In both scenarios network-wide
convergence time for the affected prefixes is measured (as well as
the total number of messages, verifications and signatures generated, and
total CPU time spent on cryptographic and non-cryptographic activities).
In both
scenarios the experiment is initiated at three routers: those with highest,
median, and lowest connectivity (see above). In scenario (i) SBGP (over
DSA with or without precomputation) did not affect convergence time. Route
propagation is limited by MRAI timers. The paper therefore focuses on
scenario (ii)
in which increases in
convergence time were seen especially for well-connected routers.
-
To study a best case scenario for DSA with caching, an ideal cache of
infinite size is simulated.
|
|
Datasets:
|
March 2002 data from a RIPE monitor (peer rrc00) was used to get a
rough estimate of caching demands by SBGP over DSA with caching.
|
|
References:
|
- Provides alternative to:
- K. Zhang. Efficient Protocols for Signing Routing Messages. In
Symposium on Network and Distributed Systems Security (NDSS '98),
San Diego, California, 1998.
-
Ralf C. Hauser, Tony Przygienda, and Gene Tsudik. Lowering security
overhead in link state routing. Computer Networks, 31(8):885-894, 1999.
- Complements analysis in:
-
S. Kent, C. Lynn, and K. Seo. Secure Border Gateway Protocol. IEEE Journal
of Selected Areas in Communications, 18(4), April 2000.
|
|
Notes:
|
Revision 2 released May 9, 2003. Original revision 1, of February 2003, is available in pdf or ps.Z.
|
