Thesis: PQC for the RPKI

By itself, BGP is terribly insecure: it relies on every AS to be honest about the addresses it claims to own, and the routes it claims to have heard of. Attacks are possible where a network shares a seemingly excellent route, to an address it does not own, or has no good path towards. This causes other networks to redirect traffic to the malicious or misconfigured network, where it can be intercepted for eavesdropping or manipulation.

The Resource Public Key Infrastructure (RPKI) has emerged as the primary tool to address these security concerns. However, the RPKI uses digital signatures that are expected to be broken eventually, when sufficiently powerful quantum computers become available. Before that happens, the RPKI needs to be changed to use post-quantum signatures, which will remain secure against both traditional and quantum computers. My thesis lays the groundwork for such a migration, investigating what post-quantum signatures can be used, and how they can be introduced. You can find the full thesis at this website.

Resource Public Key Infrastructure

The RPKI is a decentralised database that allows legitimate holders of internet resources (such as IP addresses) to make cryptographically verifiable statements about how routing should take place.

The system is used as the foundation for several techniques that can each make some attacks harder or impossible. The most notable technique is Route Origin Validation (ROV). The legitimate holder of an IP address (verifiably) publishes which ASes are allowed to originate the address, in a Route Origin Authorization (ROA). When a network receives BGP paths for that address, it looks for ROAs for that address. If the destination AS is authorised by a ROA in the RPKI, or if there is no information about the address at all, the route is potentially legitimate. But if there are ROAs for the address, but they don’t authorise the destination AS, it is certainly not a legitimate path and should be rejected. This method has seen steadily increasing adoption since its introduction.

2 other complementary techniques also exist:

• ASPA, a new measure that checks whether AS paths are plausible by considering published statements about customer-provider relationships between ASes.

• BGPsec, which verifies that a path was indeed authorised by every AS along the way.

Only ROV is widely deployed right now, and ASPA will likely be adopted soon. BGPsec has existed for a long time but has never been used in practice. The 3 RPKI-based security measures are complementary, addressing different problems.

Post-quantum cryptography

The RPKI makes use of RSA signatures. These "traditional" digital signatures are expected to be vulnerable to attacks with powerful quantum computers. While no quantum computer currently exists that can break traditional cryptography, the development of quantum computers is progressing rapidly, and it is expected that they will be able to break RSA and other traditional cryptographic algorithms, be it in several years or several decades.

This has prompted the development of post-quantum cryptography (PQC), i.e. cryptography that aims to be secure against both traditional and quantum computers. Research is being done on various protocols to migrate to PQC, including TLS and SIDN Labs' work on DNSSEC. For the RPKI, no such work has been done until now. My thesis aims to fill that gap.

How does the RPKI work?

The RPKI consists of a hierarchy of Certificate Authorities (CAs) that each are resource holders (holders of ranges of IP addresses). CAs can also delegate resources further down to subordinate CAs, by issuing ‘resource certificates’. Each CA can then create objects such as Route Origin Authorisations (ROAs), which are published in repositories.

Relying parties (RPs), also known as validators, download all certificates and ROAs from the repositories periodically. They then validate the certificates and ROAs, yielding a verified list of IP addresses and the ASes that are allowed to originate them. The list is then sent to actual BGP routers that use it in routing.

Here is an overview of the roles in the RPKI:

What can a quantum attacker do to BGP?

A quantum computer capable of breaking RSA gives an attacker two capabilities:

• Forge any signature used in the RPKI including resource certificates and ROAs. That follows directly from breaking RSA.

• Publish objects so that validators will process them. That can be achieved in various ways (see the full thesis), such as forging a message from a subordinate CA to its parent, to fully impersonate it.

With those capabilities, an attacker can not only bypass ROV protection (by forging a ROA that authorises their malicious route). They can weaponise ROV to make BGP attacks more effective than they would be without ROV.

Here's how: instead of just creating an ROA that allows their malicious route (to bypass ROV), the attacker can also revoke legitimate ROAs. That makes legitimate routes appear “ROV-Invalid” while the attacker's route appears “ROV-Valid” (instead of both becoming “ROV-Valid”). The malicious route will then be the only option considered and will not have to compete (e.g. in length) with legitimate routes, which makes the attack more effective than a traditional BGP attack without ROV.

That creates a dangerous paradox: using ROV with quantum-vulnerable cryptography can make BGP less secure than not using ROV at all. In practice, if the quantum threat becomes real, network operators would have no choice but to disable Route Origin Validation entirely, returning us to the old unprotected BGP routing. Making the RPKI quantum-safe is not therefore just a nice security upgrade, but a necessity to keep the RPKI viable in the future.

To make the RPKI quantum-safe, we need to replace the RSA signatures with a post-quantum alternative. Additionally, there is a dependency on the security of other protocols, such as TLS and DNSSEC. Determining precisely which security properties are needed from other protocols and updating them is an essential step that must not be overlooked but is not covered by this thesis.

What signatures can we switch to?

As we have seen that it is necessary to replace RSA signatures, we now need to find a suitable replacement. We start off by establishing the requirements for a replacement signature scheme. After that, we will see which candidates meet these requirements.

What do we need from a replacement?

Post-quantum algorithms usually have larger keys and signatures, and slower signing and verification times (or at least some of those properties) compared to RSA. So our main considerations are:

• that a replacement obviously needs to be secure, and

• that it should impact the performance of the RPKI as a whole as little as possible.

Security

For security, NIST has established five security levels for post-quantum schemes, with level 1 being as secure as AES-128 (128 bits of security), up to level 5 which matches AES-256. The current RSA-2048 offers only 112 bits of security against a traditional attacker, so even a NIST level 1 scheme should provide a small increase in security against traditional attacks. We will therefore accept any signature that targets NIST level 1 or higher.

Besides the NIST target level, there are a few more considerations:

• Many post-quantum signature schemes are relatively young, so their security is not yet well understood. To stay safe against traditional attacks, even if a post-quantum scheme turns out to be insecure, a hybrid signature should be used. That is a signature that combines a post-quantum signature with a traditional signature, so that it remains secure if one of the components is broken.

• Post-quantum schemes are based on different hard mathematical problems. Some of them are trusted very much (for example, the hash-based SLH-DSA) while others are less trusted. One option that could be considered is to introduce two new post-quantum signature schemes, based on different hardness assumptions: one of them as a fallback that we can quickly switch to if the other is broken.

• There are differences between schemes in their current standardisation status. ML-DSA and SLH-DSA are very close, already becoming available in common software and in HSMs. Falcon (which will become FN-DSA) should also get standardised soon. Where the other candidates are concerned, it remains to be seen whether they will make it through NIST’s process. ML-DSA, SLH-DSA and Falcon are therefore more attractive, as they can be used sooner.

Latency

The second important aspect is the impact on performance. In the RPKI, all validators download hundreds of thousands of objects and validate all of them. The time that takes influences how long it takes for changes to propagate through the RPKI, into BGP routing. If a new signature scheme increases the amount of data that needs to be downloaded, or the time it takes to verify objects, the latency increases. Running a validator or repository could also become more expensive.

A trade-off needs to be made between schemes with small signatures but slow verification, and schemes with larger signatures but faster verification. As a basis for decision-making in that context, we model how we expect two factors of the latency to change depending on the signature algorithms' properties.

• The time it takes to download all objects from the RPKI. We assume that all objects are downloaded (no caching), and that the downloading time is proportional to the size of the RPKI. To get a baseline, we've performed measurements of how much time is spent downloading (excluding constant factors like timeouts and establishing initial connections). In our setup, the size-dependent part of a full download takes roughly 14.5 seconds. Note that this is from a relatively well-connected relying party. Many other RPs are probably slower.

• The CPU time used to verify signatures. Here we found as baseline that verifying all RSA signatures in Routinator costs roughly 13 CPU seconds.

Using those two benchmarks, we can predict for any signature scheme—based on its signature/key sizes and verification benchmarks—how much longer downloading validation will take relative to RSA-2048. The resulting numbers are not representative for all real validators but are a sound basis for comparison between different signatures.

Which candidates meet the requirements?

We have considered the post-quantum schemes that were selected for standardisation by NIST, as well as submissions to round 2 of NIST's call for additional post-quantum signatures. The call aims to standardise additional schemes that are based on other mathematical problems than those underpinning ML-DSA and Falcon, or provide a performance advantage.

Applying our method to estimate performance impact on promising candidates, we find the following results (more options are in the full thesis):

Falcon-512 shows the best performance overall, with several alternatives performing similarly. Another advantage of Falcon is that it has already been selected for standardisation by NIST (a first public draft specification as FN-DSA was supposed to be released in late 2024). The other candidates (except ML-DSA) might still be eliminated, and Falcon-512 will be widely available (in standards, software and hardware security modules) much sooner than others.

However, do note that that is based on estimated duration of full downloads and validations. There are many factors to consider that might influence what algorithm is best:

• In practice, validators usually cache objects, so they do a full download once, and many smaller incremental updates after that.

• We've also assumed full adoption of a single new signature scheme, and that the structure (number of objects, etc.) of the RPKI remains unchanged. In practice, it’s possible to reduce the number of ROAs by aggregating them into larger, more efficient ROAs, which reduces the importance of sizes.

• On the other hand, validators could also implement caching of signature verification results, so that the full verification time applies only the first time an object is downloaded, and not for every incremental update.

• Finally, the verification time can be parallelised across multiple CPU cores, and the number of cores is easier to scale up than the downloading bandwidth. That makes verification time less important.

Depending on many of those factors, the best choice of signature scheme could change, but Falcon-512 seems like a good choice overall.

Next, we need to pick a traditional component to combine with a post-quantum signature in a hybrid. Sensible options for a traditional component are RSA-2048, RSA-3072 and Ed25519. When combined with Falcon-512, we get the following performance estimates:

Given the many uncertain factors that influence the trade-off between size and verification time, there is no clear winner here. If verification caching is implemented, the verification time does not matter much. But with incremental updates being more frequent than full downloads, the bigger sizes of RSA also seem manageable.

Could we be faster?

While we've found that a hybrid with Falcon-512 works quite well as a drop-in replacement for RSA, we also present an idea that can reduce the size and verification cost of the RPKI significantly. It works by removing redundant signatures and public keys that are included in every ROA.

Signed objects (such as ROAs) in the RPKI each contain 1 public key and 2 signatures. There is a one-time-use "end-entity" (EE) certificate, issued by the resource holder, that certifies a one-time-use key pair. This key pair is then used to sign the object itself, and discarded. The EE certificate includes a signature from the issuer’s long-term private key, and the public key of the one-time key pair. Both of those are redundant. The structure of a ROA is shown in the figure below.

The reason for having a one-time-use EE certificate instead of having the resource holder sign the object directly with their long-term key is to support revocation through a Certificate Revocation List (CRL), instead of implementing some RPKI-specific revocation mechanism. Revocation is done by adding the unique serial number of the one-time-use EE certificate to a CRL. That revokes the one-time key, and with it the one-time signature on a single object.

Null Scheme

We propose what we call the Null Scheme. This is a kind of signature scheme specifically for use in one-time EE certificates in the RPKI. Instead of generating a one-time key pair, our Null Scheme works as follows:

• The signature is always the empty string.

• The public key is a hash of the message to be signed.

• Verification is done by comparing the public key to the hash of the message.

That approach is possible due to the very relaxed requirements of a signature scheme in this use case. The key pair is used only once, and the message to be signed can be known before generating the key pair. The input to the signature does not depend on the public key used for signing, which is included in the attached EE certificate (RFC 5652).

Our proposed scheme is exactly as secure as the current approach: it depends on the security of the main signature algorithm (RSA or its post-quantum replacement), and on the collision or second-preimage resistance of the hash function. Those are both also needed when two normal signatures are used.

The Null Scheme has some big advantages:

• Size: We replace 1 signature and 1 public key, with only 1 digest. When using RSA signatures and SHA-256 (the current situation), that saves 496 bytes per object. For the median-size ROA, that is a reduction from 2125 bytes to 1629 bytes, and on the whole 838 MB RPKI, we can save 172 MB of overhead.

• Verification time: We also save 1 signature verification per object. Instead, only a hash function needs to be evaluated, which is already necessary during signature verification. That saves 35% of the verification time in the whole RPKI.

Both of those performance benefits are already useful in the current RPKI, but become even more pronounced when larger and slower signature algorithms are used. When compared with using Falcon-512 + RSA-2048, the Null Scheme saves 1169+922-32 = 2059 bytes per signed object. The median ROA shrinks from 4354 to 2295 bytes, almost compensating for algorithm rollover. On the whole RPKI, 717 MB of the 1.7 GB total size with Falcon-512 + RSA-2048 could be saved. That amounts to 82% of the increase in total size when switching from RSA-2048 (838 MB).

Another nice property of the Null Scheme is that it acts just like a normal signature scheme. That means it can be introduced with only an algorithm rollover (replacing RFC 7935), without changing the RPKI specifications in any other way. That makes it relatively easy to deploy, in particular when combined with the introduction of a post-quantum signature scheme.

How can we transition?

Besides finding a suitable post-quantum signature scheme, we also need to find out how it can be introduced into the existing RPKI. We argue that an existing procedure (that has never been used) is not suitable, and propose an alternative that we think is more practical.

RFC 6916

In the early days of the RPKI, the Secure Inter-Domain Routing (SIDR) working group of the IETF defined an algorithm agility procedure in RFC 6916. The core principle of the approach is that "mixed" certificates are prohibited. That is, a resource certificate with an algorithm A subject is to be signed only with an algorithm A signature, and an algorithm B subject only with an algorithm B signature. That implies that the migration process is top-down: the root CA must create algorithm B certificates, followed by the next level, and so on, until all CAs have switched to algorithm B.

The RFC 6916 procedure starts by pinpointing 5 global milestone dates, and the algorithm (B) to switch to. In several phases, a completely separate copy of the RPKI is created, where the new algorithm is used. In the meanwhile, the old (algorithm A) RPKI continues to be used. At some point, relying parties switch from validating the A tree to the B tree, and finally, the A tree is removed.

We believe that procedure to be operationally infeasible: it requires extensive coordination between all CAs, and adherence to a timeline that is established months or years in advance. The creation of a separate copy of the RPKI takes a lot of effort, and keeping the two trees synchronised is very complicated. Finally, the approach assumes that we're migrating towards a situation where only one signature algorithm is used, whereas we've identified that allowing multiple algorithms to be used at the same time can be beneficial.

Several software implementers and RIR operators have expressed similar concerns and stated that they would prefer an alternative that uses mixed certificates. Also, back when RFC 6916 was being developed, there was a heated discussion about the fundamental assumptions of the procedure. Brian Dickson, in particular, questioned the RFC 6916 authors' assumption that a globally coordinated top-down migration is inevitable. He proposed a simpler alternative using mixed certificates.

In the end, the fundamental disagreement between Dickson and the RFC's authors was not resolved. However, the alternative did not get much traction, and after 2 years of silence, the draft was published despite the apparent lack of consensus.

Mixed-tree approach

We propose a mixed-tree alternative to RFC 6916, which is based closely on Dickson's proposal. In contrast to RFC 6916, this alternative:

• treats the introduction of new algorithm B and the deprecation of old algorithm A as separate processes (thus it supports a steady state where multiple algorithms are allowed at the same time);

• allows mixed certificates, where an algorithm A parent CA can sign a B subordinate, and vice versa;

• thus enables a laissez-faire approach, where CAs can individually decide to switch to another algorithm.

The core principle of this approach is that, before widespread migration of CAs to use new algorithm B, (almost) all relying parties must be capable of validating algorithm B signatures. With that assumption, we can accept that during the transition, there is no all-A RPKI tree. So, we do not need to maintain a separate, synchronised copy of the RPKI as in RFC 6916.

Allowing mixed certificates means that CAs can unilaterally decide to switch to a new algorithm. That reduces the amount of coordination needed, and gives CA operators more freedom to schedule their rollovers on their own terms.

Our proposal works as follows:

• Phase 0: This is the current state, before the migration begins. Relying party software maintainers may already experiment with and publish updated software that can validate algorithm B signatures, but nothing is standardised yet.

• Phase 1: Phase 1 starts with the publication of the new algorithm document that obsoletes RFC 7935 and defines the new algorithm B. This document allows the use of algorithm A as well as B. It requires relying parties to accept both algorithms. In this phase, relying parties should be updated to support algorithm B, and the root CAs should publish new trust anchors (that aren't used yet), so they can be distributed together with updated relying party software. Real-world experimentation can take place using a ‘leaf’ CA. A normal CA signs a certificate for a testing CA that has a B key. That enables testing and monitoring of the readiness of RPs for the new algorithm.

• Phase 2: When enough RPs are known to accept algorithm B, CAs can widely start switching to algorithm B. In the full thesis, we propose a wide range of experiments that can be used to monitor whether RPs are ready for this. In contrast to RFC 6916, it is not necessary to coordinate a specific date when phase 2 starts. As the migration need not be top-down, a small, experimental CA can switch first. If that goes right (RPs accept the new algorithm), bigger CAs can follow safely whenever they are ready.

In this strategy, it is important to roll out RP updates as soon as possible, as those take a long time to be adopted. On the other hand, CAs’ algorithm rollovers can then be delayed until the quantum threat is really imminent.

The algorithm rollover for a single CA is very simple, following the exact same procedure that is commonly used for a normal key rollover: RFC 6489. The migrating CA requests a new certificate for the new key (now with algorithm B) and prepares copies of all its objects that are signed with the new key. Some time after the new certificate is published by the CA's parent, every object is replaced with the re-signed version. That is a familiar procedure that is known to work well in practice.

If anything goes wrong, it is also possible to roll back an RFC 6489 rollover, by simply publishing the original objects again, signed with the old key. That further mitigates the risk that some RPs might not be ready for the new algorithm yet.

The mixed-tree approach is significantly more attractive for CA operators and can achieve quantum protection earlier than RFC 6916 for several reasons:

• Easier to start migrating: The mixed-tree approach enables early experimentation through leaf CAs. A small CA can test the new algorithm in a real-world setting without waiting for every CA above them in the hierarchy to migrate first. This allows operators to gain confidence with the new technology and identify potential issues early, rather than discovering problems during a coordinated global rollout.

• More attractive for operators: The approach is much easier to implement. CA operators don't need to maintain a parallel copy of the entire RPKI tree, which would be complicated and expensive to implement. There's also no need for global coordination with strict milestone dates, so CAs can schedule their migration when they have the necessary manpower and resources available. That can make CAs less hesitant about making the transition, which can help gather the support and consensus needed to make the migration happen.

• Earlier protection for individual resources: The mixed-tree approach enables earlier quantum protection for individual CAs once they obtain an all-B chain of certificates from the root down to themselves. In contrast, RFC 6916 keeps the old algorithm A tree active throughout the entire migration period, meaning that even CAs that have published algorithm B products remain vulnerable to quantum attacks until the global migration is complete everywhere. With mixed certificates, a CA that has migrated to post-quantum signatures is immediately protected, regardless of what other CAs in the ecosystem are doing, which is a nice feature given that many small CAs can be expected to take much longer to migrate than the handful of big ones.

Implementation

To demonstrate that the mixed-tree migration approach works in practice, we implemented a proof of concept using Falcon-512 signatures in two widely used RPKI software packages: Routinator (a validator) and Krill (CA software). The implementation required only minimal changes to the shared Rust codebase that both tools rely on, with no changes needed in Routinator itself.

Our testing shows that the mixed-tree approach works as designed. We successfully created RPKI environments where different CAs use different algorithms and demonstrated that individual CAs can perform algorithm rollovers using the familiar RFC 6489 key rollover procedure that operators already know. The migration is truly a local operation for each CA: other CAs in the tree remain unaffected when one CA switches algorithms.

We've released the source code publicly to enable other implementers to test interoperability and verify our estimations of validation CPU time. This should help the RPKI community gain confidence in the approach and begin planning for the post-quantum migration.

Conclusions

My thesis presents the first work on post-quantum cryptography for the RPKI, establishing the foundation for making this critical internet infrastructure quantum-safe.

We have demonstrated that the RPKI enables severe attacks in the presence of quantum attackers, that make the RPKI dangerous to use when it is realistically vulnerable. Upgrading the RPKI to use post-quantum cryptography—before these attacks become feasible—is therefore essential to ensure routing security in the future.

Next, we have presented a methodology for comparing the performance impact that can be expected from different post-quantum signature schemes in the RPKI. Falcon-512 emerges as a good option.

The performance impact of post-quantum signatures can be mitigated by, for example, adopting our Null Scheme in RPKI signed objects. The scheme can offset much of the performance overhead of post-quantum signatures by eliminating the redundancy in one-time-use EE certificates. It can make a valuable contribution when used independently, but is particularly useful when combined with the migration to post-quantum signatures.

Finally, we have shown that the migration strategy from RFC 6916 is operationally impractical, and proposed instead a mixed-tree migration approach that allows for flexible, individual CA transitions using the proven key rollover procedure. In the proposed strategy, RP updates and TALs are distributed as soon as possible, while actual CA migrations can be delayed without problems.

The findings and recommendations presented in my thesis provide the RPKI community with the necessary groundwork to begin planning and implementing a transition to post-quantum cryptography. That process can start with the creation of early drafts that describe a possible selection of post-quantum algorithms and the migration steps to get there, which can then be discussed by the community.