PQC in PKI, X.509, certificates, and digital trust.

Key establishment protects a session's secret material. A public-key infrastructure establishes which keys are trusted for which identities and purposes — a completely different, slower-moving problem. Their migration schedules overlap, but neither migration proves the other complete, and Part 11's lab deliberately left this gap open (hybrid key establishment, classical certificate). This chapter distinguishes a certificate's subject key from its issuer signature, works through RFC 9881's exact ML-DSA identifiers and byte counts, covers CRL/OCSP status infrastructure and long-lived artifact signatures, and closes with a reproducible local ML-DSA certificate authority lab whose real output — including a verified wrong-hostname rejection — is reported below.

1. Scope and current standards

Part 11 demonstrated a hybrid TLS connection authenticated by a classical certificate. This chapter examines the separate signature and trust infrastructure. You'll distinguish a certificate's subject key from its issuer signature, understand the standardized ML-DSA identifiers, generate a local chain yourself, and identify the dependencies that make trust-anchor migration genuinely slow.

The principal profile is RFC 9881, published October 2025 on the Standards Track. It specifies ML-DSA conventions for X.509 certificates and certificate revocation lists, including public and private key representations. It builds on the certificate-processing framework in RFC 5280.

2. Read a certificate as two cryptographic statements

An X.509 certificate contains a subject public key and an issuer's signature over the encoded certificate body. The subject key may be used later by the subject to sign a handshake or artifact. The issuer signature binds that key and the certificate's identity, validity, and constraints according to the CA's policy.

These algorithms need not be the same. An ML-DSA CA can issue a certificate containing an ECDSA subject key, or a classical CA can issue one containing an ML-DSA key if the software and profile permit it. The first changes the certificate signature; the second changes the subject's own signing capability. Neither alone makes every link in a trust path post-quantum — this is the exact same lesson as Part 11 §6, now applied to the chain itself.

3. Path validation remains more than signature verification

A cryptographically valid signature is only one check in certificate path validation. The verifier also considers validity periods, issuer relationships, basic constraints, path length, key usage, extended key usage, name constraints where applicable, and trust policy. Service identity verification adds the expected hostname or other application identity on top.

A migration inventory should record each certificate's subject-key algorithm and issuer-signature algorithm separately. It should also record the path actually built by important clients, because cross-signing and multiple intermediates can lead different clients to different roots entirely. Counting certificates with ML-DSA subject keys alone does not measure complete post-quantum path coverage.

The same care applies to offline verifiers. A device can retain a root for years without network access. If that root's algorithm becomes unsuitable, distributing a replacement may require a firmware update whose own authentication relies on the old root — a circular dependency. Planning this before an emergency is far more useful than simply shortening leaf-certificate lifetimes and hoping the problem stays small.

4. RFC 9881 identifiers and encoding rules

RFC 9881 uses the following NIST object identifiers. AlgorithmIdentifier parameters are absent — they are not encoded as an ASN.1 NULL value. Strict representation matters here for interoperability and for avoiding ambiguous algorithm interpretation between implementations.

The profile uses pure ML-DSA, not HashML-DSA, for these certificate and CRL signatures. The signature covers the DER-encoded to-be-signed structure, and the context is the empty string. An application-specific context from Part 8's file-signing lab must never be inserted into certificate signing unless a different protocol explicitly defines it — mixing contexts across protocols breaks the domain separation the context field exists to provide.

Private-key containers can represent a seed, expanded key, or supported combination under the profile. A seed that regenerates a private key is equally sensitive to the expanded form (Part 7 §4). When both representations are present, consistency matters: importing contradictory seed and expanded material without checking can lead different implementations to derive different public keys or signatures from the same nominal key.

Do not register a private OID merely to work around a library that lacks the standardized one. Experimental identifiers can be appropriate inside explicitly isolated research, but carrying them into production creates another migration problem down the line. The receiving parser, signer, trust engine, and protocol negotiator all need to agree on the actual algorithm being used.

5. Certificate size: count the whole chain

A leaf containing an ML-DSA-44 public key and signed by an ML-DSA-65 issuer already contains \(1{,}312+3{,}309=4{,}621\) bytes of public-key and signature payload. Names, extensions, validity fields, identifiers, and ASN.1 framing add more on top. This arithmetic is a lower-bound component total — not a predicted final certificate length.

In the executed lab below (§8), that particular leaf certificate occupied 4,912 DER bytes. Different extensions or names change the result. A chain can add one or more similarly sized intermediate certificates on top of the leaf. The root is often provisioned separately rather than transmitted at all, but the exact protocol and server configuration determine the delivered chain in practice.

Larger chains affect TLS handshake flights, caches, status responses, certificate-management APIs, and embedded parsers. A database column or message queue that assumed small certificates can fail before cryptographic verification even begins. Test maximum supported chain sizes and parser limits through the actual delivery path, not a synthetic benchmark.

Compression can reduce some certificate overhead where a protocol supports it, but it does not change the raw signature size or eliminate parsing and validation work. Avoid estimating compressibility from repeated example certificates — real cryptographic values have little redundancy, while names and repeated metadata may compress very differently.

6. CA migration by trust role

Roots typically have long lifetimes and broad distribution. Intermediates can isolate issuance policy and support more frequent rotation. Leaf certificates are replaced most often but must be accepted by the entire deployed client population. A migration plan should treat these as distinct workstreams with different ownership and rollback constraints — not one flat "certificate migration" project.

One practical sequence is to establish a private test hierarchy, validate issuance and revocation tooling, exercise real clients, and only then plan trust-anchor distribution. This does not prescribe a universal public-Web-PKI rollout order — browser root programs, enterprise policy, regulated environments, and device-update mechanisms all impose genuinely different requirements.

Cross-signing can connect an intermediate to multiple trust anchors, but it can also quietly preserve a classical path that clients continue to select by default. Record the accepted path rather than assuming the presence of a new certificate changes the effective security. Path-building behavior and trust-store contents belong in the interoperability matrix (§9), not an assumption.

A CA migration also affects enrollment protocols, certificate requests, linting, audit systems, backup ceremonies, key recovery policy, and hardware signing interfaces. Test issuance under load and during failover. A command that signs one certificate successfully does not establish that the production CA can maintain its operational guarantees at scale.

7. Executed local ML-DSA chain lab

This experiment uses OpenSSL 3.5.8 on macOS ARM64. It creates a disposable ML-DSA-65 root and an ML-DSA-44 leaf, verifies the leaf for localhost, and rejects a wrong hostname. The root is trusted only through the command's explicit CAfile — nothing is installed into the operating system's trust store.

#!/usr/bin/env bash
set -euo pipefail
OPENSSL=${OPENSSL:-openssl}
LAB=$(mktemp -d)
trap 'rm -rf "$LAB"' EXIT
umask 077
cd "$LAB"
"$OPENSSL" version
"$OPENSSL" req -config /dev/null -x509 -newkey ML-DSA-65 -noenc -keyout root.key -out root.pem -days 2 -subj '/CN=PQC Lab Root' -addext 'basicConstraints=critical,CA:TRUE,pathlen:0' -addext 'keyUsage=critical,keyCertSign,cRLSign'
"$OPENSSL" req -config /dev/null -new -newkey ML-DSA-44 -noenc -keyout leaf.key -out leaf.csr -subj '/CN=localhost'
cat > leaf.ext <<'EOF'
basicConstraints=critical,CA:FALSE
keyUsage=critical,digitalSignature
extendedKeyUsage=serverAuth
subjectAltName=DNS:localhost
EOF
"$OPENSSL" x509 -req -in leaf.csr -CA root.pem -CAkey root.key -set_serial 2 -days 1 -extfile leaf.ext -out leaf.pem
"$OPENSSL" verify -CAfile root.pem -purpose sslserver -verify_hostname localhost leaf.pem
if "$OPENSSL" verify -CAfile root.pem -verify_hostname wrong.example leaf.pem > /dev/null 2>&1; then exit 1; fi
"$OPENSSL" x509 -in leaf.pem -outform DER -out leaf.der
"$OPENSSL" x509 -in leaf.pem -noout -text > leaf.txt
python3 - <<'PY'
from pathlib import Path
s=Path('leaf.txt').read_text()
assert 'ML-DSA-65' in s and 'ML-DSA-44' in s
print('Leaf DER bytes:',Path('leaf.der').stat().st_size)
print('PASS: ML-DSA issuer/subject algorithms, trusted path, hostname rejection')
PY

8. Revocation and status infrastructure

Certificate revocation lists are signed objects too. RFC 9881 explicitly profiles ML-DSA in CRLs, so an issuance migration should include CRL generation, distribution, parsing, and signature verification as part of the same project. A verifier that accepts the new leaf format but cannot process its issuer's status information may fail outright or silently follow an unintended policy.

OCSP adds another signed-response path, described by RFC 6960. The responder's certificate, signature support, delegated authority, freshness, and client behavior must all be tested under the applicable profile. A certificate-format standard should never be read as proof that every status client already supports the corresponding response signature algorithm.

Revocation semantics also affect availability directly. Some systems fail open when status cannot be fetched; others fail closed. A larger response or unsupported algorithm can turn a cryptographic migration into a reliability problem or a silent policy bypass. Preserve the intended status policy and make failures observable during canary testing, rather than discovering the fail-open behavior during an incident.

Short-lived certificates can reduce some reliance on revocation but do not remove every need for emergency distrust or key compromise response. A stolen signing key can remain dangerous during its full validity window, and long-lived signed artifacts (§9) need separate verification policy entirely. The correct choice depends on the application and its update cadence.

9. Code, packages, documents, and artifacts

Software signatures often outlive an individual network session by years. A verifier may need to check an old package, boot image, container provenance statement, or document long after creation. Replacing TLS key establishment does not change any of those stored signatures — inventory their formats, signing services, trusted roots, and offline verification paths separately from the TLS migration.

Package and artifact ecosystems define their own signature containers and metadata rules. A library supporting ML-DSA does not automatically make a package manager, document viewer, or secure-boot firmware accept it. The format must identify the algorithm and bind the intended content, version, and signer identity without ambiguity — exactly the context-separation problem from Part 2 §10, recurring here at the artifact-format layer.

For a release system, sign a canonical manifest that identifies artifact digests, version, target platform, and relevant policy fields. A signature on an unlabelled digest can be replayed in another context if the surrounding format fails to bind its meaning. A post-quantum primitive cannot repair an underspecified release format — the algorithm swap and the format's binding discipline are two separate problems.

10. Timestamps and long-lived evidence

A trusted timestamp can bind a digest to an asserted time under a timestamp authority's signature; RFC 3161 defines a widely used protocol for this. It can help establish that an object existed before a later key compromise or expiration, subject to the verifier's policy and the trustworthiness of the timestamp infrastructure itself.

An archival test should restore an old object, its signatures, relevant certificates, status evidence, and timestamps in an isolated verifier. Confirm which evidence is actually needed and which external services are silently assumed to be available. This exercise often reveals undocumented dependencies that ordinary live verification quietly hides.

11. HSMs, key custody, and rotation

Hardware security modules and managed key services expose specific algorithms, parameter sets, mechanisms, and firmware versions. Ask whether they support generating keys internally, signing through the intended API, secure backup, replication, audit, and retirement. "PQC roadmap" is not an answer to those operational questions — it's a promise about a future answer.

Private-key seed formats can complicate import/export policy. A service that forbids expanded-key export but permits exporting an equivalent seed has not actually preserved non-exportability — the seed regenerates the same key (§4). Review every representation and recovery mechanism as part of the key boundary. Test that logs and diagnostic interfaces expose only public information, never seeds or expanded private material.

Rotation must update the signer, certificates or public-key distribution, verifier policy, and cached metadata coherently, all together. During overlap, document which old signatures remain acceptable and for how long. Removing a key from the active signing service does not necessarily revoke trust in its historical signatures — those are two separate actions, and conflating them either breaks valid old signatures or leaves a retired key implicitly trusted.

For an offline root, rehearse the migration ceremony and recovery process well before the old algorithm becomes urgent to replace. Ensure enough authorized personnel, compatible tooling, and verifier-update channels exist ahead of time. These organizational dependencies can dominate the schedule even when the underlying signing operation itself is fast.

12. An interoperability matrix and review questions

Build a matrix whose rows are clients or verifiers and whose columns include certificate parsing, path building, hostname checks, constraints, CRLs, OCSP where used, artifact format, and algorithm negotiation. Include old firmware and offline devices, not only current desktop libraries. Mark each cell tested, unsupported, or unknown — with a version and date attached, not a vague confidence level.

Negative tests should include an unknown issuer, expired leaf, wrong hostname, invalid basic constraints, wrong key usage, altered certificate bytes, and an unsupported algorithm. A migration that preserves only positive verification has not demonstrated that the trust engine still rejects invalid identities and paths — that's the more important half of the test matrix, and it's the half most often skipped.

Takeaways

• Subject-key algorithm and issuer-signature algorithm migrate independently. Track them as two separate fields per certificate — an ML-DSA subject key under a classical issuer signature is a real but partial migration step.
• Path validation is far more than one signature check — validity periods, constraints, key usage, and hostname matching all still apply, and a valid ML-DSA signature on the wrong hostname is still an authentication failure.
• A full ML-DSA-44-under-ML-DSA-65 chain adds ~4,600+ bytes of pure public-key/signature payload before names, extensions, and ASN.1 framing — test real parser and transport limits, don't estimate.
• CRLs and OCSP need their own migration — a verifier that accepts the new certificate format but can't parse its issuer's status information fails in a new way.
• Long-lived artifacts (packages, documents, timestamps) need migration timing, not just a new algorithm — re-signing after the old mechanism is already forgeable can bless attacker-created objects instead of protecting genuine ones.
• The reproducible lab confirmed real chain generation and validation: a 4,912-byte ML-DSA-44 leaf under an ML-DSA-65 root, correct hostname acceptance, and verified wrong-hostname rejection.

References & further reading

• RFC 9881 — the primary ML-DSA X.509/CRL profile for this entire chapter.
• RFC 5280 — §3, the underlying certificate-processing framework.
• ML-DSA-in-TLS Internet-Draft — §1, still not an RFC as of this writing.
• RFC 6960 (OCSP) — §8.
• RFC 3161 (timestamping) — §10.