Identity-based registry for secure interdomain routing

E-yong Kim, Klara Nahrstedt, Li Xiao, Kunsoo ParkAsiaccs 2006 · DOI

TL;DR

This paper introduces a novel "Identity-Based Registry with Authorized and Verifiable Search" (RAVS) scheme to secure interdomain routing protocols like BGP. By leveraging identity-based cryptography and a trusted third party for permission generation, RAVS allows for secure storage and retrieval of routing information without revealing sensitive data, while also ensuring the integrity and origin of the information.

What Problem Does This Paper Address?

The internet's routing infrastructure, particularly the Border Gateway Protocol (BGP), currently lacks robust security mechanisms to validate routing information. This vulnerability makes BGP susceptible to various attacks, such as route modification and misconfiguration, which can disrupt global internet connectivity. While existing solutions like route filtering and cryptographic approaches exist, they often suffer from high overhead, complexity, or lack of backward compatibility. The Internet Routing Registry (IRR), a common source for routing policy information, is also plagued by issues of incompleteness, incorrectness, and lack of authorization, making it unreliable for validating BGP updates.

Methods

The core of this paper is the proposed Identity-Based Registry with Authorized and Verifiable Search (RAVS) scheme. This scheme is built upon three key concepts:

  • Identity-Based Registry: Instead of relying on traditional Public Key Infrastructure (PKI) and certificates, RAVS uses an Autonomous System (AS) number as its identity. This identity serves as the public key, simplifying the management of cryptographic keys.
  • Authorized Search: A new component, the Search Permission Generator (SPG), acts as a trusted third party. Legitimate ASes obtain search permissions from the SPG for specific keywords (routing information) before they can query the registry. This ensures that only authorized entities can access routing data.
  • Verifiable Search: Registries are constructed using the provider's private key, allowing other ASes to verify the origin and correctness of the information. The scheme is designed such that a registry can only be successfully tested if it was created by the claimed identity and if the search query is accompanied by a valid permission.

The RAVS scheme is formally defined with algorithms for SETUP, EXTRACT, RAVS (registry creation), PERMISSION, and TESTREGISTRY. The authors also prove the scheme's security (semantic security and existential unforgeability) in the random oracle model, based on the hardness of the Elliptic Curve Discrete Logarithm Problem (ECDLP), Computational Diffie-Hellman (CDH), and Bilinear Diffie-Hellman (BDH) problems.

Datasets

Not discussed in the paper. The paper focuses on a theoretical framework and cryptographic construction rather than empirical evaluation on specific datasets.

Key Insights and Ideas

  • Identity as Public Key: The elegant use of AS numbers as identities simplifies key management, bypassing the need for complex PKI infrastructure.
  • Separation of Concerns: The introduction of the SPG as a distinct entity for permission generation, separate from the registry storage (mIRR), enhances security by limiting the trust placed in any single component.
  • Verifiability for Integrity: The verifiable nature of registries is crucial. It allows any AS to confirm that routing information originates from the claimed AS, preventing forged or tampered data from being accepted.
  • Incentivizing Participation: By requiring search permissions, the scheme implicitly incentivizes ASes to contribute their routing information to the registry to ensure the registry's completeness and thus their ability to query it effectively.
  • Backward Compatibility: A significant advantage highlighted is that the RAVS scheme does not require modifications to the BGP protocol itself or its message formats, making it easier to deploy.

Key Results

The paper presents theoretical security proofs demonstrating that the RAVS scheme is semantically secure against adaptive chosen keyword and identity attacks (IND-ID-CKA) and existentially unforgeable against adaptive chosen keyword and identity attacks (EUF-ID-CKA) in the random oracle model.

The authors also discuss how their scheme can address specific BGP threats:

  • Modification Attacks: The scheme can detect AS_PATH modifications by allowing ASes to query the registry to verify the existence of advertised paths.
  • Misconfiguration: Export misconfigurations can be mitigated by verifying advertised routes against the registry.
  • Exposing Attacks: The semantic security of the scheme prevents adversaries from learning routing information from registries without proper permissions.
  • Contamination Attacks: Existential unforgeability prevents attackers from forging registries, thus protecting the integrity of the database.

Experimental results (Tables 1 and 2) indicate that the scheme is implementable with acceptable overheads in terms of time and space, with optimized times for key operations.

Limitations and Future Work

  • Colluding Adversaries: The paper acknowledges that the method does not address colluding adversaries.
  • Deployment Challenges: While the scheme is designed for easy deployment, its effectiveness relies on widespread adoption. Incomplete participation in the mIRR would reduce the probability of detecting invalid routes.
  • Routing Policies: The paper mentions that specifying routing policies using structured languages like RPSL and constructing RAVS based on them is a direction for future work.
  • Prefix Origin Validation: The authors suggest that RAVS could be extended to address prefix origin validation, with ICANN potentially acting as a registry provider.

Summary updated

BibTeX
@inproceedings{kim2006identity,
  author = {E-yong Kim and Klara Nahrstedt and Li Xiao and Kunsoo Park},
  title = {{Identity-based registry for secure interdomain routing}},
  booktitle = {Asiaccs},
  year = {2006},
  doi = {10.1145/1128817.1128866},
}
Figure