Paper 2013/017

Provable Security of S-BGP and other Path Vector Protocols: Model, Analysis and Extensions

Alexandra Boldyreva and Robert Lychev


This paper provides the provable-security treatment of path vector routing protocols. We first design a security definition for routing path vector protocols by studying, generalizing, and formalizing numerous known threats. Our model incorporates three major security goals. It is quite strong, yet simple to use. We prove by reduction that S-BGP satisfies two out of the security model’s three goals, assuming the underlying signature scheme is secure. Under the same assumption, we next show how the protocol can be modified to meet all three security goals simultaneously. We also analyze SoBGP and show that it fails to meet two security goals. Finally, we study security of partial PKI deployment of path vector protocols when not all nodes have public keys. We investigate the possibilities of relaxing the PKI requirement and relying on non-cryptographic physical security of networks that use the protocol in order to achieve possibly weaker, but still well-defined, notions of security. We also present the necessary and sufficient conditions to achieve full security in the partial PKI deployment scenario. We believe our conclusions will prove useful for protocol developers, standards bodies and government agencies.

Available format(s)
Publication info
Published elsewhere. A preliminary version of this paper appears in ACM Conference on Computer and Communications Security 2012.
Secure BGProuting protocolspath vector protocolsprotocol verificationprovable security
Contact author(s)
robert lychev @ gatech edu
2013-01-18: received
Short URL
Creative Commons Attribution


      author = {Alexandra Boldyreva and Robert Lychev},
      title = {Provable Security of S-{BGP} and other Path Vector Protocols: Model, Analysis and Extensions},
      howpublished = {Cryptology ePrint Archive, Paper 2013/017},
      year = {2013},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.