Securing BGP through keychain-based signatures

Yin Heng, Sheng Bo, Wang Haining, Pan Jianping

Research output: Chapter in Book/Entry/PoemConference contribution

2 Scopus citations


As the major component of Internet routing infrastructure, the Border Gateway Protocol (BGP) is vulnerable to malicious attacks. While Secure BGP (S-BGP) provides a comprehensive framework to secure BGP, its high computational cost and low incremental deployment benefits seriously impede its wide usage in practice. Using a lightweight symmetric signature scheme, SPV is much faster than S-BGP. However, the speed boost comes at the price of prohibitively large signatures. Aggregated path authentication reduces the overhead of securing BGP in terms of both time and space, but the speed improvement is still limited by public key computation. In this paper, we propose a simple keychain-based signature scheme called KC-x, which has low CPU and memory overheads and provides strong incentive for incremental deployment over the Internet. As a generic framework, KC-x has the flexibility of using different signature algorithms. We implement two realizations of KC-x. One is based on RSA called KC-RSA, and the other is based on Merkle hash tree called KC-MT. After characterizing the overheads of KC-RSA and KC-MT, we evaluate their performance with real BGP workloads. Our experimental results show that KC-RSA is as efficient as SAS-V, and KC-MT is even 3-fold faster than SPV with a 40% smaller signature. Through the hybrid deployment of KC-MT and KC-RSA, KC-x can achieve both small signature and high processing rate for BGP speakers.

Original languageEnglish (US)
Title of host publication2007 Fifteenth IEEE International Workshop on Quality of Service, IWQoS 2007
Number of pages10
StatePublished - 2007
Event2007 Fifteenth IEEE International Workshop on Quality of Service, IWQoS 2007 - Evanston, IL, United States
Duration: Jun 21 2007Jun 22 2007

Publication series

NameIEEE International Workshop on Quality of Service, IWQoS
ISSN (Print)1548-615X


Other2007 Fifteenth IEEE International Workshop on Quality of Service, IWQoS 2007
Country/TerritoryUnited States
CityEvanston, IL

ASJC Scopus subject areas

  • Electrical and Electronic Engineering


Dive into the research topics of 'Securing BGP through keychain-based signatures'. Together they form a unique fingerprint.

Cite this