Day 18: PQC Certificate Challenges

Phase 3 · July 25, 2026

Agenda (2–3 hours)

• Read (45 min): NIST IR 8547 §4–5 (PKI migration challenges); IETF draft-ietf-lamps-dilithium-certificates
• Study (60 min): Certificate size impact, chain overhead, HSM gaps, CT log implications
• Challenge (45 min): Certificate size analysis and TLS record budget

The Certificate Size Problem

A TLS handshake transmits the server's full certificate chain.
With PQC signatures, that chain grows dramatically:

TLS 1.3 record layer limit: 16 KB per record.
A 38 KB chain requires 3 TLS records — extra TCP round trips likely.

Practical Impact on TLS Handshake

Classical TLS 1.3 handshake (ServerHello through Finished):
  Record 1 (ServerHello): ~0.2 KB
  Record 2 (EncryptedExtensions + Certificate + CertVerify + Finished): ~3.5 KB
  Total: ~3.7 KB → fits in 1-2 TCP segments

PQC TLS 1.3 handshake (ML-DSA certs):
  Record 1 (ServerHello): ~0.3 KB (larger key_share)
  Record 2 (EncryptedExtensions): ~0.1 KB
  Record 3 (Certificate — 10.5 KB chain): ~10.5 KB → spans 2+ TCP segments
  Record 4 (CertificateVerify — 3293-byte sig): ~3.4 KB
  Record 5 (Finished): ~0.1 KB
  Total: ~14.4 KB → 3-4 TCP round trips on a cold connection

For a provisioning service in the same VPC: minimal impact (low RTT).
For a service accessed over the internet or satellite link: measurable.

Mitigations for Large Cert Chains

Certificate compression (RFC 8879):

• Compresses the Certificate message using zlib or brotli
• ML-DSA certs have low entropy (lots of zeros in padding) — compresses well
• Supported in TLS 1.3, requires both sides to opt in

OCSP stapling: reduces need to include the OCSP responder cert

Shorter chains: skip sending the root cert (client already has it in trust store)

Choose ML-DSA over SLH-DSA for intermediate and leaf certs — 10× smaller signatures

Omit root from chain: clients should already have it. Standard practice.

HSM Support Gaps

Current state of HSM support for PQC (2026):

This is the critical gap: your CA hierarchy requires HSM protection for private keys.
Without HSM support, you can't use PQC for CA key material without accepting a
security downgrade (software-only key protection).

Timeline: AWS CloudHSM PQC support expected 2026-2027 based on AWS roadmap signals.

Certificate Transparency: CT Log Size Impact

CT logs append every certificate. PQC certs are 3-10× larger.

Implications:

• CT log storage costs increase proportionally
• CT log operators need to scale infrastructure
• SCT delivery (embedded in cert) grows similarly
• Current CT logs accept PQC certs but operators are discussing size limits

For your team: when issuing ML-DSA certs, expect SCTs to be larger and
consider whether your certs require CT logging (public trust) or not (private PKI).

Challenge Assignment

Run a "TLS record budget analysis" for your provisioning service:

Assume: private network, 10 ms RTT, 100 Mbps link.

1. Estimate the handshake latency for: ECDSA chain, ML-DSA chain, hybrid chain
2. Identify at which chain size an extra TCP round trip is unavoidable
3. Recommend: which combination of cert algorithms minimizes handshake overhead while meeting CNSA 2.0 requirements?
4. Does RFC 8879 (cert compression) close the gap? Estimate compressed sizes.

Add findings to "Certificate Impact" section of migration roadmap.

Resources

• RFC 8879: TLS certificate compression
• NIST IR 8547: PKI migration challenges
• IETF draft-ietf-lamps-dilithium-certificates: ML-DSA cert format
• AWS CloudHSM PQC roadmap: aws.amazon.com/cloudhsm/faqs