Post-Quantum PKI — Migrating Internal CAs, Certificate Hierarchies, and Trust Stores

If your CA root cert was issued in 2020 with RSA-4096 and 25-year validity, it’s signing certificates that will be verified in 2045 — well past the most-pessimistic CRQC arrival estimates. Re-rooting your PKI is unavoidable; the question is when and how, not whether.

The PKI hierarchy in PQ context

Typical PKI hierarchy:

• Root CA (offline, very long lifetime, signs intermediate CAs).
• Intermediate CA (online, 5-10 year lifetime, signs leaf certs).
• Leaf certificates (1-13 month lifetime, signed by intermediate, used by services).

Different PQ algorithm choices for each:

Alternative: pure ML-DSA all layers. Simpler operationally; trades root-CA conservatism for size. Reasonable choice for 5-10 year horizon.

Re-rooting strategy

You can’t simply replace your root CA — every cert it signed becomes invalid. The migration has two patterns:

Pattern A — Parallel hierarchy:

1. Stand up a new PQ-rooted CA hierarchy alongside the existing one.
2. For new certificate issuance, use the PQ hierarchy. For existing certs, leave them on the classical hierarchy until expiry.
3. Distribute the new PQ root cert to all clients (browsers, OS trust stores, embedded devices).
4. After all classical-hierarchy certs have expired (5-10 years for typical fleets), retire the classical CA.

Pattern B — Cross-signed transition:

1. New PQ root cross-signs the existing classical intermediate. Existing certs validate against either hierarchy (legacy verifiers via classical chain; modern verifiers via PQ chain).
2. New issuance from the PQ root.
3. Eventually retire the cross-sign and the classical root.

Pattern A is operationally simpler. Pattern B preserves existing-cert validation across legacy and modern verifiers but requires careful chain-construction logic.

Implementation tools

EJBCA (PrimeKey) — enterprise PKI server. PQ support added in 2024 release for ML-DSA. Supports both classical and PQ in same instance.

HashiCorp Vault PKI engine — supports SSH-style certs natively; ML-DSA support pending in 2025-2026.

Smallstep step-ca — modern certificate authority. Open-source; PQ support added Q4 2024 via OQS-OpenSSL.

OpenSSL 3.5 — has the cryptographic primitives. Use as a library for custom CA implementations; limited as a CA itself.

OQS-OpenSSL (Open Quantum Safe) — comprehensive PQ-OpenSSL fork. Excellent for testing and small-scale deployment; not the recommended production CA backbone.

Microsoft Active Directory Certificate Services — PQ roadmap announced; production availability 2026-2027.

AWS Private CA — PQ support pending; AWS expected to be early adopter for managed CA service.

Certificate lifecycle in PQ

Certificate transparency (CT) logs need to handle PQ-signed certs. Major CT logs (Google’s Argon, Cloudflare’s Nimbus, Sectigo’s Mammoth) are extending support; expect production coverage 2026.

OCSP and CRL revocation: signing of OCSP responses and CRLs themselves migrates to PQ. Don’t let revocation infrastructure lag the issuance side.

HSM integration: validate that your HSM supports PQ key generation and signing operations. AWS CloudHSM has it; Thales Luna has it; Gemalto SafeNet has it from 2024 firmware. Older HSMs require firmware update or replacement.

Practical migration sequence (24-month plan)

Months 1-3: design — pick algorithms, plan hierarchy, document trust-store distribution mechanism.

Months 3-6: stand up parallel PQ CA in non-production. Issue test certs to staging environments. Validate that all consumer services can verify PQ chains (Java, .NET, Node.js, Python, Go all need at-least-2024 versions).

Months 6-12: roll out to internal services. Start with low-risk (developer tools, internal dashboards), then move to higher-stakes (admin APIs, payment flows).

Months 12-18: external-facing certs. Coordinate with public CAs (Let’s Encrypt, DigiCert, Sectigo) for PQ leaf cert issuance when they ship it.

Months 18-24: legacy CA retirement plan. Document timeline for classical root retirement (5-10 years out, when last classical-signed certs expire).

Trust-store distribution

The new PQ root must be installed in every client trust store:

• Browsers: Chrome, Firefox, Safari, Edge. Public CAs go through CCADB; private CAs need MDM / Group Policy push.
• OS trust stores: Windows certmgr, macOS Keychain, Linux ca-certificates package, iOS/Android via MDM.
• Application trust stores: Java cacerts, Mozilla NSS database (for Firefox-derived apps), Python certifi (per-virtualenv).
• Embedded devices: device firmware, IoT trust stores. Plan for firmware updates to push new roots.

For corporate deployment: roll out new root via configuration management. Test on a pilot device population before fleet-wide.

Common pitfalls

• Forgetting the OCSP responder: it signs OCSP responses; needs PQ key too.
• Java keystore format limitations: PKCS#12 supports PQ keys; older JKS may not. Use PKCS#12 going forward.
• Container base images: alpine / debian-slim ship with old ca-certificates; rebuild against current base.
• Mobile apps with pinned roots: pinning is broken when the root changes. Plan for app updates that include the new root.
• Hardcoded RSA-only validation logic: some legacy code only handles RSA. Audit and update.

FAQ

Should we wait for public CAs to ship PQ before migrating internal CA?

No. Internal CA migration can happen now and gives organisations practice for the public-CA transition. Internal-only services don’t depend on public-CA roadmap.

Will old TLS clients reject PQ-signed certs?

Old clients see an unknown signature algorithm OID and reject. Java < 17, .NET < 7, Python < 3.12 are typical floors. For B2B services with old client populations, hybrid certificate strategy (cross-sign) extends compatibility.

Is PQ leaf-cert issuance more expensive than classical?

From a public CA perspective, comparable cost. Internal CA: same operational cost; signature verification is faster than RSA-3072 in most implementations.

What about S/MIME?

S/MIME certs use the same X.509 hierarchy. Migration follows the general PKI plan. Microsoft Outlook and Apple Mail expected PQ S/MIME support 2026-2027.

How do we handle certificate-pinning during migration?

Pin the new PQ public-key fingerprint instead of the certificate fingerprint. This survives certificate renewal and gradual algorithm migration. For mobile apps, ship updates with the new pin set.

⚖️ Module 14 of 20. Advanced. Module 15 — final Advanced module — covers blockchain post-quantum readiness.