%T Efficient Security for BGP Route Announcements
%A David M. Nicol
%A Sean W. Smith
%A Meiyuan Zhao
%R Technical Report TR2003-440
%I Dartmouth College, Computer Science
%C Hanover, NH
%D May 2003
%U http://www.cs.dartmouth.edu/reports/TR2003-440.R2.ps.Z
%X
 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.  
%Z
 Revision 2 released May 9, 2003.  
 Original revision 1, of February 2003, is available in 
 <a href=http://www.cs.dartmouth.edu/reports/TR2003-440.R1.pdf>pdf</a> or 
 <a href=http://www.cs.dartmouth.edu/reports/TR2003-440.R1.ps.Z>ps.Z</a>.