Pruning the Tree: Rethinking RPKI Architecture from the Ground up

Pruning the Tree: Rethinking RPKI Architecture from the Ground up

Speakers: Haya Schulmann

Conference: NDSS Symposium

YouTube: https://www.youtube.com/watch?v=TZ1HuIew1p8

Overview

The Resource Public Key Infrastructure (RPKI) is the security architecture for internet routing, enabling verification of BGP route announcements. With approximately 60% of announced prefixes now covered by RPKI objects, deployment has progressed beyond infancy -- making it time to evaluate whether the architecture actually works well. This talk argues that current RPKI design is unnecessarily complex and inefficient, carrying overhead from reusing existing PKI technologies rather than optimizing for its specific use case. The researchers demonstrate that by removing redundant signatures, eliminating per-object end-entity certificates, and combining manifest/CRL files, they can achieve the same security guarantees with up to 20-fold improvement in validation time.

Implemented in Routinator (the most popular RPKI validator software), the improvements reduce complexity that has been the source of numerous implementation bugs, many of which are directly attributable to the protocol's complexity.

Background

▶ Watch: RPKI overview: 60% of prefixes now covered (0:00)

RPKI enables networks to create Route Origin Authorizations (ROAs) that specify which autonomous systems are authorized to announce specific IP prefixes in BGP. These objects are signed, stored in repositories, and downloaded by validators (relying parties) that compile authorization lists for routers.

RPKI follows a hierarchical tree structure where a root Certificate Authority (CA) creates child CAs, each of which can create additional children and payload objects. Each CA requires a manifest (listing all objects created by the CA), a Certificate Revocation List (CRL) (listing revoked certificates), and can create ROAs and other authorization objects.

The complexity arises in object validation. Validating a single ROA requires checking the ROA itself, the CRL for revocation, the manifest for hash integrity, the CA certificate for signature validity, key ID correctness, and IP range compliance. Each ROA also includes its own single-use End Entity (EE) certificate -- a full certificate just for that one object. The actual authorization content (one AS number and one prefix) is just 27 bytes, while the complete ROA file exceeds 2 kilobytes -- meaning 99% is validation overhead.

The RPKI has been deployed progressively but challenges remain in both full deployment and in adding new use cases like ASPA (AS Provider Authorization). Post-quantum cryptography with larger signatures will further stress the architecture.

Key Findings

▶ Watch: 99% overhead: 27 bytes of content in 2KB ROA files (6:00)

• 99% of ROA file content is validation overhead: Only 27 bytes of a 2KB+ ROA file contain the actual authorization; the rest is certificates, signatures, and validation material
• Up to 20-fold validation time improvement: Removing redundant components while maintaining the same security guarantees dramatically reduces the computational cost of RPKI validation
• 6-fold improvement in real-world settings: Even in production scenarios with realistic data distributions, the simplified design achieves at least 6x faster validation
• End Entity certificates are unnecessary: Each ROA includes a single-use EE certificate whose primary purpose (enabling revocation) can be achieved by adding a serial number directly to the object content
• Object signatures are redundant: Since the manifest already contains hashes of all CA-issued objects, tampering with any object will cause manifest validation to fail -- the object-level signature is redundant protection
• Manifest and CRL can be combined: These serve similar roles and have nearly identical structure, reducing the number of objects that must be maintained and validated
• Complexity causes bugs: Multiple implementation bugs in RPKI software can be directly traced to the protocol's complexity; reducing complexity inherently improves security

Technical Deep Dive

▶ Watch: Up to 20-fold validation time improvement in Routinator (10:00)

The researchers identify two primary sources of unnecessary overhead:

Redundant EE Certificates: Every ROA includes a full end-entity certificate used only for that single object (as stated in the RFC). The primary justification is simplified revocation -- revoking the EE certificate revokes the object. However, this is excessive overhead for a simple revocation mechanism. The fix: remove the EE certificate and add a serial number directly to the object content, enabling revocation through the CRL without the certificate overhead.

Redundant Signatures: Each object carries its own cryptographic signature for tamper protection. However, RPKI's architecture already provides tamper protection through the manifest, which contains cryptographic hashes of all objects issued by a CA. If an attacker modifies any object, the hash mismatch causes manifest validation to fail. Therefore, object-level signatures provide redundant protection. Removing them eliminates the most computationally expensive part of validation: RPKI contains many ROAs, each previously requiring two signature verifications (one for the EE certificate, one for the object signature).

Additional Optimizations: Combining manifest and CRL into a single object (they serve similar roles with nearly identical structure), restructuring object encodings, and streamlining the validation pipeline.

The security analysis demonstrates that removing these components does not weaken security guarantees: the manifest hash mechanism provides equivalent tamper protection, and the serial number mechanism provides equivalent revocation capability.

The implementation in Routinator showed the main source of improvement is the dramatic reduction in required signature validations. With many ROAs in a full RPKI deployment, eliminating two signatures per ROA translates to massive computational savings.

Demo / Proof of Concept

▶ Watch: Q&A: IETF engagement and historical design rationale (12:00)

The researchers implemented all improvements in Routinator, the most widely used RPKI validator software. Benchmarks comparing legacy (unmodified) Routinator against the improved version show up to 20-fold reduction in validation time, with the main improvement attributable to fewer signature verifications.

The Q&A session was notably rich, with engagement from IETF participants, RPKI deployment practitioners, and routing security researchers. Key discussion points included: the historical design rationale for EE certificates (simplifying offline CA operations), the migration path (RPKI's rigid architecture makes backward-compatible changes difficult), post-quantum cryptography implications (larger signatures make the efficiency gains even more important), and the tension between proposing architectural changes and convincing the IETF community that designed the original system.

Defensive Implications

▶ Watch: Post-quantum implications and EE certificate design rationale (18:00)

• Validation performance under scale: As RPKI deployment approaches 100% prefix coverage and new object types (ASPA) are added, validation performance becomes critical for operational reliability. A 20x improvement provides significant headroom.
• Reduced implementation complexity: Simpler protocols are easier to implement correctly. The direct connection between RPKI complexity and implementation bugs means simplification inherently improves security.
• Post-quantum readiness: Post-quantum signatures are significantly larger than current algorithms. Reducing the number of signatures per object makes RPKI more tractable with post-quantum cryptography.
• Repository bandwidth: Smaller objects reduce bandwidth requirements for RPKI repositories, which must serve many validators worldwide.
• Session reset resilience: Simplified validation makes recovery from validator session resets faster, reducing windows of vulnerability during operational disruptions.

Key Takeaways

• 99% of RPKI ROA file content is validation overhead; the actual authorization is just 27 bytes
• End Entity certificates and per-object signatures are redundant given the manifest hash mechanism already provides tamper protection
• Removing these redundancies achieves up to 20-fold validation speedup while maintaining equivalent security guarantees
• Reduced complexity directly improves security by making correct implementation easier
• Post-quantum cryptography will make these efficiency gains even more critical
• Migration from the current architecture is challenging due to RPKI's rigid design, requiring community engagement through the IETF

About the Speaker(s)

Haya Schulmann delivered a clear, well-structured presentation that demonstrated deep understanding of both the cryptographic architecture and the operational deployment challenges of RPKI. The Q&A revealed extensive engagement with the IETF and routing security communities, including discussion of migration strategies and post-quantum readiness. Multiple audience members from industry (Google, USCIS, Cable Labs, Virginia Commonwealth University) engaged substantively with the research.