URL: http://www.cs.dartmouth.edu/reports/abstracts/TR2003-440
ftp://ftp.cs.dartmouth.edu/TR/TR2003-440.R2.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.