Keychain-based signatures for securing BGP

Heng Yin, Bo Sheng, Haining Wang, Jianping Pan

Research output: Contribution to journalArticlepeer-review

8 Scopus citations


As a 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 keychain-based signature scheme called KC-x. It has low CPU and memory overheads and provides strong incentive for incremental deployment on the Internet. As a generic framework, KC-x has the flexibility of using different signature algorithms, which can even co-exist in a hybrid deployment. We investigate two implementations of KC-x: KC-RSA based on RSA and KC-MT based on Merkle hash tree. Using real BGP workloads, our experimental results show that KC-RSA is as efficient as SAS-V (the most efficient software approach for aggregated path authentication), and KC-MT is even three times faster than SPV with 40% smaller signatures. 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)
Article number5586443
Pages (from-to)1308-1318
Number of pages11
JournalIEEE Journal on Selected Areas in Communications
Issue number8
StatePublished - Oct 2010


  • BGP
  • Keychain-based Signature
  • Performance Optimization
  • Secure Routing Protocol

ASJC Scopus subject areas

  • Computer Networks and Communications
  • Electrical and Electronic Engineering


Dive into the research topics of 'Keychain-based signatures for securing BGP'. Together they form a unique fingerprint.

Cite this