Moving from Existing RSA and ECDSA PKI Infrastructures to Quantum Resistant Alternatives

(Compiled and researched by Steve Monti

Currently, there are a vast amount of traditional PKI infrastructures based on RSA 2048-bit keys. Indeed, I have just built two such PKI hierarchies for very large customers with validity dates far beyond the projected dates of a successful quantum supremacy breakthrough date. Despite my protestations, customers still rely on RSA for the foreseeable future and have no appetite for building crypto agile audits.
When a quantum breakthrough happens (and it will happen), customers seem to think that PKI vendors will provide a patch or firmware upgrade, and everything will work as normal. Nothing could be further from the truth. In reality, the migration work required is enormous. The degree of testing of applications, devices, appliances, code, including upgrading standards and policies will be very considerable.
As a matter of urgency, I recommend that all consumers of large PKI hierarchies run a test PQ PKI in tandem with their production PKI environment to at least understand, prepare, and test for the challenges that await.
The Challenges Are Vast
I will be documenting the challenges that await institutions starting with these brief summaries:
Certificate Chains

Certificate chains (or certification paths) play a vital role in the PKI infrastructure. A certificate chain is a series of certificates issued by successive certificate authorities (CAs), linking an end-entity certificate to a trusted root certificate.

When we move from smaller RSA-based certificates to larger CRYSTALS-Dilithium based certificates, there are several implications for certificate chains:

Firstly, the overall certificate chain size will increase. If every certificate in the chain uses CRYSTALS-Dilithium, then the combined size of the chain will increase proportionally. For instance, if a typical chain has three certificates (root, intermediate, and end-entity), and each certificate chain increases by 20KB see: Table 1 approximate changes to certificate paths in KB, this is going to be considerable in large estates.

When establishing a secure connection (e.g., during a TLS handshake), the server often sends its certificate chain to the client. Larger chains will consume more bandwidth and might introduce a slight delay, especially in environments with limited bandwidth.

Validation Overhead

Clients verify certificate chains to ensure the server’s certificate is trustworthy. Larger post-quantum cryptographic signatures could increase the computational effort required to validate each certificate in the chain, leading to longer verification times. This could be especially noticeable on devices with limited computational power.

Cache and Memory Implications

Systems that cache certificate chains (for quicker access and validation) might find their cache filling up more quickly, possibly requiring more frequent cache evictions or increased cache sizes.

Data Storage

Systems that store certificate chains, like some certificate management platforms or services, will need more storage space.

Compatibility Concerns

Some older systems, protocols, or software might have limits on the size of certificates or chains they can handle. Larger Crystals-Dilithium based certificates, might exceed these limits, requiring updates or patches.