Chapter 29: PKI and code signing
Migrating a production PKI to post-quantum signatures replaces the chain root and every certificate beneath it. Every certificate in a trust path, every JWKS kid that signs a token, and every code-signing key that validates a firmware image is an artifact signed with an algorithm the operator must pick. The Ed25519+ML-DSA-65 composite signature construction and the AND-mode verification rule are derived in Ch 27. This chapter gives the operator’s playbook for a production deployment that uses that construction across the certificate hierarchy, the JWKS rotation, and the code-signing pipeline.
The threat this chapter blunts is certificate-chain forgery. An attacker with a large-scale quantum computer can forge RSA-2048 and ECDSA-P256 signatures once such a machine exists. A classical-only chain that is still in use at that point is forgeable for the remainder of every deployed leaf certificate’s validity. Session confidentiality is covered in Ch 28. Stored-password hashing and webhook HMAC are out of scope for this chapter. Operator tooling for this chapter lives at solutions/ch29-pki/.
A jwt_signing touchpoint that must move by 2033
Section titled “A jwt_signing touchpoint that must move by 2033”The Ch 25 CBOM records jwt_signing as RS256 (RSA-2048 with SHA-256) deployed on 2023-01-10, with quantum-status vulnerable. Its touchpoint schema has no rotation field, so this chapter assumes a 90-day rotation cadence for that key and carries the assumption as its own. The organization’s internal policy sets a 2033 deadline for post-quantum migration of all signing touchpoints. Three external anchors sit near that date, and they come from three different documents. The UK NCSC puts the end of migration at 2035 (UK National Cyber Security Centre, 2025). NSA’s September 2022 CNSA 2.0 advisory sets 2033 as the exclusive-use date for web and cloud services, operating systems, and niche equipment including large public-key infrastructure (US National Security Agency, 2022). The CNSA 2.0 FAQ carries the CNSSP 15 gates for National Security Systems (NSS): 31 December 2031 for mandatory CNSA 2.0 use, under NSM-10’s goal of all NSS being quantum-resistant by 2035 (US National Security Agency, 2024).
The migration target in this chapter’s running example is ML-DSA-65 as the long-term end state for a general enterprise profile, with Ed25519+ML-DSA-65 as the transition-period primitive (Ch 27). CNSA-aligned NSS deployments substitute ML-DSA-87 instead, per the Ch 25-settled CNSA 2.0 algorithm suite.
Firmware signing is the secondary scenario. A device that ships a bootloader in 2026 may still be running in 2040. Its signing key must outlast every other artifact in the deployment. NSA CNSA 2.0 names LMS and XMSS as the recommended post-quantum signatures for firmware on NSS where stateful counter management is operationally tractable. The FAQ restricts that to the single-tree variants and disallows the multi-tree HSS and XMSS-MT outright (US National Security Agency, 2024). NIST SP 800-208 specifies the operational constraints (Cooper et al., 2020). Validated ML-DSA-87 is also approved under CNSA 2.0 for signing use cases and may be appropriate for higher-volume or distributed software-signing deployments on NSS. For commercial non-NSS software signing on a shorter rotation, this chapter takes SLH-DSA (FIPS 205 (National Institute of Standards and Technology, 2024)), which carries no counter to manage across a build fleet.
Two different 2030 dates apply to firmware signing and they are not interchangeable. The September 2022 advisory’s per-asset table sets exclusive CNSA 2.0 use for software and firmware signing by 2030 (US National Security Agency, 2022). The FAQ’s 31 December 2030 covers more than signing: it is the date by which all equipment and services that cannot support CNSA 2.0 are phased out (US National Security Agency, 2024). A migration plan sourced to the FAQ alone therefore misses the earlier of the two deadlines that bind a signing pipeline.
X.509 signature fields and JWKS keys
Section titled “X.509 signature fields and JWKS keys”An X.509 v3 certificate is a SEQUENCE of three fields: the inner tbsCertificate, the outer signatureAlgorithm AlgorithmIdentifier, and the outer signatureValue BIT STRING (RFC 5280 §4.1.1.2 and §4.1.1.3 (Cooper et al., 2008)). The signature bits live in signatureValue, not in the inner signature field of TBSCertificate. That inner field is itself an AlgorithmIdentifier that must equal the outer signatureAlgorithm (§4.1.2.3). Chain validation (§6) verifies each certificate’s signatureValue over the DER-encoded tbsCertificate under the issuer’s public key, walking up to a trust anchor. DER is the Distinguished Encoding Rules, the one canonical byte encoding ASN.1 permits for a given value, which is what makes a certificate’s bytes reproducible enough to sign. Changing the signature scheme means re-issuing every certificate in the path whose signatureAlgorithm must carry a new object identifier, the dotted-decimal name a standards body assigns to an algorithm.
A JWK (RFC 7517 §4 (Jones, 2015)) is a JSON object whose kty member names the key type and whose kid (§4.5) is the opaque identifier a JWT header points to. A JWKS (§5) is a JSON object whose required keys member holds an array of JWKs. The JWT signing input is the ASCII string base64url(header).base64url(payload) (RFC 7515 §5.1 (Jones et al., 2015)). The signature sits as the third dot-separated component.
The Ed25519+ML-DSA-65 composite signature construction is defined in Ch 27. The AND-mode rule (both components must verify) carries over here. The X.509 encoding is specified in draft-ietf-lamps-pq-composite-sigs (Ch 27-settled at revision -19) (Ounsworth et al., 2026). The LAMPS identifier for the Ed25519 + ML-DSA-65 composite is id-MLDSA65-Ed25519-SHA512, with OID 1.3.6.1.5.5.7.6.48 (the value pinned in Ch 27). LAMPS scope is PKIX and S/MIME (CMS), not JOSE. RFC 9881 (October 2025) specifies ML-DSA in X.509 using OIDs that NIST registered in its Computer Security Objects Register (CSOR) (Massimo et al., 2025): id-ml-dsa-65 is 2.16.840.1.101.3.4.3.18. RFC 9909 (December 2025) does the same for SLH-DSA, reproducing the CSOR identifiers (Bashiri et al., 2025): id-slh-dsa-sha2-128s is 2.16.840.1.101.3.4.3.20. XMSS and SLH-DSA are covered in Ch 15 and Ch 17 respectively.
Single ML-DSA now has finalized JOSE and COSE serialization in RFC 9964 (May 2026) (Prorock & Steele, 2026): the AKP (Algorithm Key Pair) JWK key type, with ML-DSA-44, ML-DSA-65, and ML-DSA-87 algorithm identifiers. Composite ML-DSA + Ed25519 remains draft-level in JOSE: draft-ietf-jose-pq-composite-sigs requests registration of ML-DSA-65-Ed25519 in its §7.1.5, but at revision -04 (10 September 2026) it sits at IESG state “I-D Exists”, earlier in the process than the LAMPS X.509 draft (Prabel et al., 2026). The OKP-COMPOSITE kty and Ed25519+ML-DSA-65 alg values used in the JWKS fragment below are therefore illustrative for a deployment-owned JWKS, not interoperable across JOSE libraries. Adopting the eventual JOSE profile will take more than a change of identifiers. Its examples carry the serialized composite public key in the single pub member of an AKP key rather than in two separately named members, so the key schema changes with the name.
A note on naming. This chapter writes the construction as Ed25519+ML-DSA-65 in prose and in the JWKS alg value, following the classical-first reading order that an operator sees in the deployed JWKS field. The LAMPS and JOSE drafts name the ML-DSA component first: id-MLDSA65-Ed25519-SHA512 in the LAMPS X.509 identifier and ML-DSA-65-Ed25519 in the JOSE composite draft. The two orderings refer to the same construction, and the difference is in the name rather than in the bytes. The LAMPS draft’s §4.1 serializes the composite public key as mldsaPK || tradPK (Ounsworth et al., 2026), which is the order Ch 27’s combiner implements and the order the JWKS fragment below splits on.
Step-by-step deployment
Section titled “Step-by-step deployment”The runnable package is at solutions/ch29-pki/.
CA-hierarchy migration
Section titled “CA-hierarchy migration”A three-layer PKI (root, intermediate, leaf) migrates bottom-up or top-down depending on which issuer is first to have a PQ-capable signing pipeline. The common case is top-down. The root certificate authority (CA) issues itself a new self-signed certificate whose signatureAlgorithm is the composite OID. The intermediate re-issues under a composite signature from the new root. The leaf is issued with a composite signature from the intermediate. Existing RSA or ECDSA leaves continue to validate against the old root until they expire; new leaves validate against the new root.
The size impact is the sum of composite signature sizes down the chain. Ed25519 is 64 bytes; ML-DSA-65 is 3309 bytes (FIPS 204 Table 2 (National Institute of Standards and Technology, 2024a)); the Ed25519+ML-DSA-65 composite signature is 3373 bytes. Counting the root, intermediate, and leaf as PKI inventory gives three composite signatures: 10119 signature bytes. In a typical TLS handshake the root is a trust anchor (RFC 5280 §6.1) and is not transmitted on the wire. A one-intermediate transmitted chain therefore carries the leaf and intermediate certificates only: two composite signatures, or 6746 signature bytes, plus their SubjectPublicKeyInfo, extensions, and DER overhead.
The classical baselines are 768 bytes across three RSA-2048 signatures and roughly 192 bytes raw or up to ~216 bytes DER-encoded across three ECDSA-P256 signatures. The DER form encodes Ecdsa-Sig-Value ::= SEQUENCE { r INTEGER, s INTEGER } (RFC 3279 §2.2.3 (Polk et al., 2002)), reaching at most ~72 bytes per signature. These are signature bytes only. A full certificate chain adds SubjectPublicKeyInfo, extensions, and validity fields on top. Three ML-DSA-65 public keys alone contribute roughly 5856 bytes (FIPS 204 Table 2: 1952 B per key) before DER overhead.
Cloudflare’s 2025 post-quantum review puts numbers on what that costs on the public web (Westerbaan, 2025). A first visit to one of their sites sends five signatures and two public keys, most of them the certificate chain and the rest Certificate Transparency SCTs. The median chain today, compressed, is 3.2 kB. Their 2021 experiment with artificially enlarged chains found that some clients and middleboxes break above 10 kB, and that performance drops sharply at the same point because of the initial congestion window. The 10119 signature bytes computed above are a three-deep inventory total rather than a wire total, but they land on the wrong side of that threshold on their own, before a single public key or extension is counted. The exact delta is deployment-dependent and should be measured against your traffic baseline.
A chain analyzer is the operator’s first line of triage: given a chain in leaf-first order, it classifies each signatureAlgorithm as classical, single-PQ, or composite, and labels the chain’s overall posture. A classical link above a post-quantum leaf is the deployment bug to flag: an attacker who forges the classical link forges the leaf transitively. During rollout, however, a chain can be transitionally mixed (classical leaf under a composite-capable intermediate, for example, while leaf re-issuance is still in flight). The analyzer distinguishes that case from the bug case rather than collapsing both to “mixed”.
# Block 1: pedagogical slice of pki_migration.chain_analyzer.analyze_chain (stdlib only).CLASSICAL = { "1.2.840.113549.1.1.11", # sha256WithRSAEncryption (RFC 8017) "1.2.840.10045.4.3.2", # ecdsa-with-SHA256 (RFC 5758); P-256 default "1.2.840.10045.4.3.3", # ecdsa-with-SHA384 (RFC 5758); P-384 default "1.3.101.112", # id-Ed25519 (RFC 8410)}SINGLE_PQ = { "2.16.840.1.101.3.4.3.18", # id-ml-dsa-65 (RFC 9881) "2.16.840.1.101.3.4.3.20", # id-slh-dsa-sha2-128s (RFC 9909)}COMPOSITE = { "1.3.6.1.5.5.7.6.48", # id-MLDSA65-Ed25519-SHA512 (Ch 27-settled)}
def classify(oid): if oid in CLASSICAL: return "classical" if oid in SINGLE_PQ: return "single-pq" if oid in COMPOSITE: return "composite" return "unknown"
def analyze(chain): # chain is leaf-first: chain[0] is the leaf, chain[-1] is the root. classes = tuple(classify(oid) for oid in chain) unique = set(classes) if not classes: return classes, "empty" if "unknown" in unique: return classes, "unknown-oid-present" if unique == {"classical"}: return classes, "classical-only" if unique == {"single-pq"}: return classes, "single-pq-only" if unique == {"composite"}: return classes, "composite-only" leaf = classes[0] if leaf in {"composite", "single-pq"} and "classical" in unique: return classes, "mixed-classical-above-pq-leaf" # deployment bug return classes, "mixed-transition" # rollout in progress
good = [ "1.3.6.1.5.5.7.6.48", # leaf, composite "1.3.6.1.5.5.7.6.48", # intermediate, composite "1.3.6.1.5.5.7.6.48", # root, composite]bug = [ "1.3.6.1.5.5.7.6.48", # leaf, composite "1.2.840.113549.1.1.11", # intermediate, classical (RSA-SHA256) "1.3.6.1.5.5.7.6.48", # root, composite]rollout = [ "1.2.840.10045.4.3.2", # leaf, classical (ECDSA-P256/SHA-256) "1.3.6.1.5.5.7.6.48", # intermediate, composite "1.3.6.1.5.5.7.6.48", # root, composite]
print("good:", analyze(good)[1])print("bug:", analyze(bug)[1])print("rollout:", analyze(rollout)[1])# ==> good: composite-only# ==> bug: mixed-classical-above-pq-leaf# ==> rollout: mixed-transitionEvery Python block this chapter prints is also a standalone file in the companion repository, under chapter-code/ch29/, one file per block. Appendix C covers the clone and the environment they run on.
mixed-classical-above-pq-leaf is the deployment bug the analyzer exists to catch: a composite leaf with a classical link above it is forgeable through the classical link. mixed-transition is the legitimate rollout state during re-issuance, where the leaf has not yet been upgraded but the higher links already have been. The full package carries a subject and an issuer on each certificate reference, and reports the per-certificate classes in leaf-first order alongside the verdict. An operator running a fleet-wide scan reads the offending layer off its position in the chain.
signatureAlgorithm, and the trust anchor's own key, held in the trust store, must be a composite key: the root's self-signature is not verified in path validation (RFC 5280 §6.1) and is drawn only as the usual container for that key. A classical link above a PQ leaf defeats the leaf beneath it and signals a deployment bug to remediate. The legitimate transitional pattern is the inverse: a classical leaf still under a composite intermediate during re-issuance. The byte-size key at the bottom shows the cumulative chain cost: 10119 B under Ed25519+ML-DSA-65 against roughly 216 B DER-encoded under ECDSA-P256, signatures only.A production analyzer must inspect two fields per certificate, not one. The signatureAlgorithm field says how the certificate was signed; the SubjectPublicKeyInfo field (RFC 5280 §4.1.2.7 (Cooper et al., 2008)) says which key will verify any children. A PQ or composite signature over a CA certificate does not make the subtree quantum-safe if the CA’s own signing key is classical (RSA, ECDSA, or Ed25519). A future quantum attacker who recovers the CA private key from its classical public key can sign new child certificates under that CA. The pedagogical slice above checks signatureAlgorithm only. The runnable package at solutions/ch29-pki/ is structured so a deployment can extend the per-certificate report with a parallel SubjectPublicKeyInfo audit, flagging any CA whose public-key algorithm is classical regardless of the signature on its own certificate.
JWKS and JWT migration
Section titled “JWKS and JWT migration”The JWKS migration is a kid rotation. The endpoint starts with one kid in its JWKS whose kty is RSA and whose alg is RS256 (Jones, 2015a). The migration publishes a second kid alongside the first, whose key material is an Ed25519+ML-DSA-65 composite public key. During the cutover window, the endpoint signs new JWTs under the composite kid while still validating old JWTs under either kid. The old RSA kid is retired once no active token in circulation still references it.
The JWKS for a two-kid endpoint is a JSON document with two entries under keys. A verifier reads the kid from the JWT header, looks up the matching entry, reconstructs pk = mldsa_pk || ed_pk from the composite JWK, and hands (pk, signed, sig) to composite_sig_verify from Ch 27. The full package runs the AND-mode check; the slice that follows isolates the lookup and key-reconstruction path.
# Block 2: pedagogical slice of pki_migration.jwks_verifier.verify_composite_jwt (stdlib only).import base64import json
COMPOSITE_KTY = "OKP-COMPOSITE"COMPOSITE_ALG = "Ed25519+ML-DSA-65"
def b64url_decode(s): pad = (-len(s)) % 4 return base64.urlsafe_b64decode(s + ("=" * pad))
def find_jwk(jwks, kid): for jwk in jwks["keys"]: if jwk.get("kid") == kid: return jwk raise KeyError(f"no JWK with kid={kid!r}")
def resolve_composite(jwt_compact, jwks): parts = jwt_compact.split(".") if len(parts) != 3: raise ValueError("JWT must have three dot-separated parts") header_b64, payload_b64, sig_b64 = parts header = json.loads(b64url_decode(header_b64)) kid = header.get("kid") if kid is None: raise ValueError("JWT header missing 'kid'") jwk = find_jwk(jwks, kid) if jwk.get("kty") != COMPOSITE_KTY: raise ValueError(f"kid={kid!r} kty is not {COMPOSITE_KTY}") if jwk.get("alg") != COMPOSITE_ALG or header.get("alg") != COMPOSITE_ALG: raise ValueError(f"alg mismatch: jwk={jwk.get('alg')!r} header={header.get('alg')!r}") pk = b64url_decode(jwk["mldsa_pk"]) + b64url_decode(jwk["ed_pk"]) signed = f"{header_b64}.{payload_b64}".encode("ascii") return pk, signed, b64url_decode(sig_b64)
jwks = { "keys": [ {"kty": "RSA", "alg": "RS256", "kid": "rs256-2023", "n": "AA", "e": "AQAB"}, {"kty": COMPOSITE_KTY, "alg": COMPOSITE_ALG, "kid": "composite-2026", "mldsa_pk": "AA", "ed_pk": "AA"}, ],}# header = {"kid":"composite-2026","alg":"Ed25519+ML-DSA-65"}jwt = ("eyJhbGciOiJFZDI1NTE5K01MLURTQS02NSIsImtpZCI6ImNvbXBvc2l0ZS0yMDI2In0" ".eyJzdWIiOiJhIn0.AA")
pk, signed, sig = resolve_composite(jwt, jwks)print("pk len:", len(pk), "signed len:", len(signed), "sig len:", len(sig))# ==> pk len: 2 signed len: 83 sig len: 1The kid rs256-2023 is the pre-migration classical signer; composite-2026 is the new composite signer. The verifier dispatches on kty AND alg. It requires the JWK to declare kty = OKP-COMPOSITE and alg = Ed25519+ML-DSA-65, and it requires the JWT header to declare the same alg. It then reconstructs pk = mldsa_pk || ed_pk, the LAMPS §4.1 order pinned in the naming note above, and hands (pk, signed, sig) to composite_sig_verify from Ch 27, which runs the AND-mode check. The "AA" JWK fields in the example are toy fillers. A real Ed25519 public key is 32 bytes, a real ML-DSA-65 public key is 1952 bytes, and a real composite signature is 3373 bytes.
The two components are published as separately named members rather than one concatenated blob, so a consumer that is not this verifier can read either component without knowing the other’s length. That property holds only if each member carries what its name says: mldsa_pk is the leading 1952 bytes and ed_pk the trailing 32. Splitting at the wrong offset still round-trips, because the verifier reassembles exactly what it split, so a round-trip test cannot detect the mislabelling and a published JWKS advertises the wrong bytes under both names.
Token issuers cut over to the new kid on a configured date. Verifiers accept both kids through the overlap window. The old kid is removed from the JWKS only after the longest-lived token signed under it has expired. With an issuing interval and a maximum token lifetime , a kid’s verification key must stay in the JWKS for up to from its first issuance. It overlaps the next kid for up to after cutover. The gap between those two intervals is the originator-usage-period and recipient-usage-period split SP 800-57 Part 1 §5.3.4 sets out for signature key pairs: the private key stops signing before the public key stops verifying (Barker, 2020). A 90-day kid cadence with a 30-day maximum token time-to-live (TTL) is a deployment convention rather than standards guidance: §5.3.6 recommends one to three years for a private signature key, and the document says nothing about token lifetimes.
rs256-2023 remains within its TTL. Phase 4 is where the RS256 kid leaves the JWKS. Roll back to an earlier phase if verification-success-rate drops below the 99.9 percent threshold (red dashed line, carried from Ch 28).JOSE has finalized single-ML-DSA serialization in RFC 9964 (Prorock & Steele, 2026) but not composite ML-DSA + Ed25519. The JWKS fragment above is deployment-owned. An endpoint that publishes it should version the kty (for example OKP-COMPOSITE-v1), which makes the two formats distinguishable during migration. It does not make the migration a rename. The draft composite profile carries the composite public key in one pub member of an AKP key, so a verifier needs an adapter rather than a lookup-table entry. Newly signed tokens need a transition of their own: the protected header is part of the JWS signing input, so a token whose alg changes has to be signed again (Jones et al., 2015).
A JWT signing key only inherits the PKI root’s trust if the JWKS distribution or the signing key’s own certificate is bound to that PKI. Many deployments instead trust a JWKS URL, a configuration bundle, or a service-mesh identity directly. In those cases the migration target is the verifier’s configured trust source, not the X.509 CA hierarchy that signs the TLS certificates. The kid-rotation procedure above applies to either trust model.
Code-signing pipeline
Section titled “Code-signing pipeline”Firmware signing is the hardest deployment constraint in PKI migration. A device that boots a signed image in the field, with no ability to rotate its root of trust, must verify against a signature scheme that will still be unbroken at the end of the device’s lifetime. LMS and XMSS are two approved stateful signature families that SP 800-208 §1.1 names as suited to exactly this profile: a near-term deployment, a long lifetime, and no practical way to change the verifier once the device ships (Cooper et al., 2020). Both are stateful hash-based signatures: the signer tracks a leaf index across every signing operation, and each leaf carries a one-time key. Signing two different messages under the same leaf makes forgery computationally feasible for an attacker holding both signatures, with no quantum capability required (SP 800-208 §9.1 (Cooper et al., 2020)).
Which algorithm a scenario gets depends on whether it is an NSS deployment and on whether the signer can guarantee counter state for the key’s whole life. CNSA 2.0 recommends validated LMS or XMSS for the long-lived cases. It also approves validated ML-DSA where a signing strategy needs more signatures than one LMS or XMSS key can reasonably carry, or where signing is distributed across a development environment (Cooper et al., 2020; US National Security Agency, 2024).
| Scenario | Algorithm | Signature | The constraint it buys |
|---|---|---|---|
| Firmware signing, NSS | LMS or XMSS | 2,500 B (XMSS-SHA2_10_256) | Stateful: an authoritative leaf counter for the key’s life |
| Software signing, NSS, high volume or distributed signers | ML-DSA-87 | 4,627 B | Stateless, but needs a validated implementation |
| Software signing, commercial (non-NSS) | SLH-DSA | 7,856 B (SLH-DSA-SHA2-128s) | Stateless; excluded from every NSS use |
The XMSS size is at , derived in Ch 15 and given as 2,500 bytes in RFC 8391 §5.3.1, Table 3 (Hülsing et al., 2018). ML-DSA-87’s 4,627 bytes is FIPS 204 Table 2 (National Institute of Standards and Technology, 2024a). SLH-DSA runs from 7,856 bytes (SLH-DSA-SHA2-128s) to 49,856 bytes (SLH-DSA-SHA2-256f) across FIPS 205 Table 2’s twelve parameter sets (National Institute of Standards and Technology, 2024b). On this chapter’s quarterly or annual commercial cadence, the larger signature buys the operational simplicity of stateless signing, which is why the scenario takes it. The CNSA 2.0 FAQ v2.1 is explicit that this last row cannot cross into NSS: “While SLH-DSA is hash-based, it is not part of CNSA and is not approved for any use in NSS” (US National Security Agency, 2024).
The operational failure mode for LMS and XMSS has two faces. The crash scenario: a signer increments its in-memory counter, signs, then crashes before persisting the counter. It then restarts at the old index, signs a different message with the same leaf, and catastrophically compromises the key. The concurrent-signer scenario: two processes each read the counter, each reserve the same next_leaf, and each sign distinct messages with the same WOTS+ key.
Both failure modes have the same defense, and SP 800-208 §8.1 states its ordering normatively: the cryptographic module “shall increment the leaf index of the private key … and shall store the incremented leaf index value in nonvolatile storage before exporting a signature value or accepting another request to sign a message” (Cooper et al., 2020). Serialize the entire read-check-increment-persist sequence under a single exclusive lock that no signing step starts without holding. Persist the incremented counter BEFORE the WOTS+ signing step runs. A crash during signing then wastes a leaf but never reuses one.
Persisting is harder than writing. SP 800-208 §9.1 names the trap directly: writing the update to a file is not sufficient, because the write is cached and the actual write to non-volatile memory happens later, so a crash between the two loses the state update. That is why Block 3 fsyncs the file and then fsyncs its parent directory rather than simply writing.
§9.1 also names the production answer, a hardware monotonic counter, which is guaranteed to increment each time it is read. A validated deployment keeps the counter inside the hardware module: SP 800-208 §8.1 validates key and signature generation only within a hardware cryptographic module at FIPS 140 Level 3 or higher physical security, with private keying material that cannot be exported. §8.1 also states the counter rule directly: on accepting a request to sign, the module “shall increment the leaf index of the private key” and “shall store the incremented leaf index value in nonvolatile storage before exporting a signature value or accepting another request to sign a message” (Cooper et al., 2020). A serializable database transaction is an engineering alternative outside that validation boundary, which is what the pki_migration package’s own header says; Block 3 uses a single POSIX exclusive lock on a sibling lock file as a pedagogical local-filesystem stand-in. In the pki_migration package the same lock guards creating the counter, so a provisioning run cannot rewind a counter a signer has already advanced. POSIX advisory locks are not guaranteed to coordinate signers across every network or distributed filesystem, so any deployment crossing host boundaries should move to one of the production patterns above. Block 3 and the pki_migration package it is cut from are POSIX-only: fcntl locking and directory fsync have no Windows standard-library equivalent, so on Windows run them under WSL.
# Block 3: pedagogical slice of pki_migration.xmss_index.durable_xmss_sign (stdlib only, POSIX).import fcntlimport jsonimport osfrom pathlib import Path
def _read_counter(counter_path): raw = counter_path.read_bytes() data = json.loads(raw.decode("utf-8")) if not isinstance(data.get("next_leaf"), int): raise RuntimeError(f"counter missing 'next_leaf' int at {counter_path}") if not isinstance(data.get("max_leaf"), int): raise RuntimeError(f"counter missing 'max_leaf' int at {counter_path}") return data
def _atomic_write(counter_path, state): tmp = counter_path.with_suffix(counter_path.suffix + ".tmp") raw = json.dumps({"next_leaf": state["next_leaf"], "max_leaf": state["max_leaf"]}).encode("utf-8") with tmp.open("wb") as f: f.write(raw) f.flush() os.fsync(f.fileno()) os.replace(tmp, counter_path) dir_fd = os.open(str(counter_path.parent), os.O_DIRECTORY) try: os.fsync(dir_fd) finally: os.close(dir_fd)
def burn_next_leaf(counter_path, lock_path): # One LOCK_EX covers read, check, increment, write, fsync. with lock_path.open("a+b") as lock: fcntl.flock(lock.fileno(), fcntl.LOCK_EX) data = _read_counter(counter_path) if data["next_leaf"] >= data["max_leaf"]: raise RuntimeError(f"leaf exhaustion: all {data['max_leaf']} consumed") used = data["next_leaf"] _atomic_write(counter_path, {"next_leaf": used + 1, "max_leaf": data["max_leaf"]}) return used
counter = Path("/tmp/ch29-xmss-counter.json")lock = Path("/tmp/ch29-xmss-counter.lock")counter.write_text(json.dumps({"next_leaf": 0, "max_leaf": 4}))
used = burn_next_leaf(counter, lock)print("burned leaf:", used)print("persisted:", json.loads(counter.read_text()))counter.unlink()lock.unlink()# ==> burned leaf: 0# ==> persisted: {'next_leaf': 1, 'max_leaf': 4}A signer calls burn_next_leaf to reserve and persist the next index under a single exclusive lock, then calls the WOTS+ signing step on that index outside the lock (signing is read-only against the counter). A crash between the two steps wastes a leaf but does not reuse it. A second concurrent signer blocks at LOCK_EX until the first releases, reads the already-incremented counter, and reserves the next index. The package wraps xmss_sign from Ch 15 to enforce this ordering for every call.
Firmware-signing keys (including bootloader and secure-boot keys) and blockchain validator-set keys share an operational profile. Both are signed once and verified many times: the operator publishes the public key once at device manufacture or at validator-set commit, and every device or every consensus client verifies against that key for the remainder of the deployment lifetime. The signing-latency budget is generous in both cases. Seconds-per-signature is acceptable for a quarterly firmware release or for a hard-fork activation block; the latency budget for per-block consensus and staking signatures (Ch 39) is several orders of magnitude tighter. The byte cost lands once at publication: the verifier-side public key sits in the bootloader image or in the consensus-client release for years, and the signature lands at every release or every fork-activation event. Chapter 39 walks the consensus and staking signature requirements; Chapter 41 walks the governance machinery for hard-fork-activated cryptographic transitions.
Deprecation and compatibility windows
Section titled “Deprecation and compatibility windows”Retiring the classical-only chain is gated by the client population. A CA that stops issuing classical leaves before its classical-only clients finish their own migration breaks those clients’ TLS handshakes or JWT verification. The operator’s signal is the fraction of validation traffic that resolves to the classical chain. The deprecation rule: the fraction drops below one percent for four consecutive weeks. At that point new issuance stops, the intermediate expires on its normal schedule, and the root is marked out-of-policy.
CA/Browser Forum Baseline Requirements govern public TLS certificate issuance. Ballot SC-081v3 (April 2025) reduces publicly-trusted TLS server certificate validity from 398 days to 200 days starting 15 March 2026, to 100 days starting 15 March 2027, and to 47 days starting 15 March 2029 (CA/Browser Forum, 2025). A shorter validity compresses the operator’s deprecation window: a 200-day leaf issued the day before a classical CA stops issuing will still be in circulation 200 days later. As of May 2026, no CA/Browser Forum ballot has been passed that mandates post-quantum support in publicly-trusted TLS server certificates. Internal CAs (enterprise PKI, device PKI) are not bound by Baseline Requirements and can deprecate classical-only chains on their own timeline.
Cryptanalysis: certificate-chain forgery, algorithm downgrade, and leaf reuse
Section titled “Cryptanalysis: certificate-chain forgery, algorithm downgrade, and leaf reuse”Four failure modes matter at the PKI and code-signing layer. Ch 27’s cryptanalysis section already covers the composite signature’s own exposures, and they are not repeated here. There are three. Component stripping, where a single component signature is peeled off and accepted by a standalone verifier. The context binding that makes stripping asymmetric between the ML-DSA and Ed25519 halves. And the draft’s normative prohibition on reusing a component key outside the composite. The KDF and shared-randomness failures in that same section belong to the KEM combiner and do not transfer to a construction that signs one message representative twice.
Certificate-chain forgery. A quantum adversary who can run Shor’s algorithm on CA key sizes (RSA-2048, ECDSA-P256, Ed25519) forges a chain to any identity. Every TLS endpoint, every code-signed binary, and every signed JWT that still validates under a classical CA is forgeable for the remainder of that CA’s deployed validity. Moving the chain to composite or single-PQ signatures removes the classical component as a sole trust anchor and blunts this threat.
Algorithm downgrade through alternate chains. A composite certificate cannot have its OID swapped in flight without invalidating the signature, so the realistic downgrade is alternate-chain selection. A CA that issues both a classical-only chain and a composite chain for the same subject leaves a relying party free to validate whichever it sees first. An attacker who controls path discovery (DNS-resolution metadata, an upstream proxy, a stale trust store, a classical-fallback policy in the validator) can then steer the relying party to the classical chain even when a composite is available. The TLS 1.3 transcript defends against on-path tampering during the handshake itself (Ch 28). The residual risk lives in CA issuance policy and validator algorithm policy.
Three rules cover it. Do not issue both classical and composite chains for the same identity once the composite chain is deployment-ready. Enforce an algorithm-policy minimum on the validator (single-PQ or composite required for new chains). Monitor Certificate Transparency for unexpected classical re-issuance under a composite root. The agility principle is covered in Ch 26 under the governance and policy area (RFC 7696 §2.4 on algorithm transitions (Housley, 2015)).
Stateful-key reuse on LMS and XMSS. A WOTS+ key is one-time. Signing two distinct messages under the same key reveals additional Winternitz-chain preimages and reduces the key’s EUF-CMA security below the scheme’s design floor. Forgery becomes feasible for a family of third messages whose hashes satisfy the scheme’s checksum relation (Cooper et al., 2020). The attack requires no quantum capability. It is a pure operational failure. SP 800-208 §8.1 prohibits reuse outright, in a conformance requirement that a module “shall not use an OTS key to generate a digital signature more than one time”. §9.1 names the mitigations: state updated before the signature is exported, crash-safe persistence rather than a cached write, and a hardware monotonic counter where one is available (Cooper et al., 2020). The Block 3 pattern above is the minimum; HSM-backed monotonic counters are the production standard.
Compromise of the post-migration root. The post-quantum root carries the same trust weight the classical root did. Every composite-signed certificate validates through it, every firmware image signed with its child LMS/XMSS trees traces back to it, and every JWT issued under a composite kid is an identity claim under its chain. Key-custody, HSM boundaries, air-gapped key-signing ceremonies, and per-ceremony audit trails are unchanged from classical PKI and remain the primary defense. NIST SP 800-57 §5.3 covers cryptoperiod selection and §8 covers the deprecate-retire lifecycle (Barker, 2020).
Tradeoffs
Section titled “Tradeoffs”Four dimensions capture the deployment cost of the post-quantum PKI and code-signing posture against a classical baseline:
| Dimension | Classical baseline | Post-quantum target | Delta |
|---|---|---|---|
| Three-deep chain signature bytes | ~192 B raw / ~216 B DER (ECDSA-P256) or ~768 B (RSA-2048) | ~10119 B (Ed25519+ML-DSA-65 composite) | +9 to +10 KiB on signatures; full-chain growth is larger once SubjectPublicKeyInfo and extensions are counted (Massimo et al., 2025; National Institute of Standards and Technology, 2024a) |
Leaf signatureAlgorithm verify CPU | RSA-2048 or ECDSA-P256 verify | one ML-DSA-65 verify plus one Ed25519 verify, comparable costs on measured x86-64 (Dilithium3 row) (Bernstein & Lange, 2026) | two verifications of the same order, about double one lattice verify measured against Dilithium3 (Bernstein & Lange, 2026) |
| Firmware signature bytes | ECDSA-P256 64 B; Ed25519 64 B | XMSS 2,500 B (h=10, XMSS_SHA2_10_256) or SLH-DSA-SHA2-128s 7,856 B | +2.4 KiB to +8 KiB (Cooper et al., 2020; National Institute of Standards and Technology, 2024b) |
| Operational burden on signer | Stateless classical | Stateful LMS/XMSS or stateless SLH-DSA (commercial only; SLH-DSA is excluded from NSS) | counter persistence for stateful (Cooper et al., 2020; US National Security Agency, 2024) |
Bandwidth: the composite signature dominates the TLS handshake bandwidth delta at post-quantum sizes. What crosses the wire is the transmitted chain rather than the three-deep inventory. With one intermediate that is two composite signatures at 3373 B and two composite public keys at 1984 B each, the ML-DSA-65 key and the Ed25519 key concatenated (Ounsworth et al., 2026): 10,714 bytes, about 10.7 kB of signature and key material before extensions and the rest of each certificate are counted. That extends across several 1500-byte IP segments, against one to two at classical sizes. The exact segment count is deployment-dependent and should be measured against your traffic baseline. Over a short-lived connection fleet (mobile cellular, IoT), the chain is sent once per handshake. Session resumption amortizes the cost across subsequent requests.
CPU: an AND-mode composite verify pays for both component verifications. On measured x86-64 the two are of the same order (Ed25519 verification is a double-scalar multiplication, RFC 8032 §5.1.7 (Josefsson & Liusvaara, 2017), and Dilithium3 verification costs about the same in cycles (Bernstein & Lange, 2026)), so the composite roughly doubles verification work rather than adding a small classical tax. FIPS 204 carries only size parameters, not benchmark data. CA-side signing is rare; chain verification on the validator side is the hot path. Measure against the deployment’s specific hardware profile before committing to a throughput budget.
Operational: LMS and XMSS require authoritative leaf-counter tracking in perpetuity. A firmware-signing deployment outside NSS that cannot guarantee monotonic counter persistence across every signing operation should use SLH-DSA, pay the signature-size cost, and accept the stateless trade. For NSS deployments the algorithm choices differ. CNSA 2.0 recommends LMS and XMSS per SP 800-208 for long-lived signing where stateful counter management is tractable, and also approves validated ML-DSA-87 for higher-volume or distributed software-signing use cases. SLH-DSA is not part of CNSA 2.0 and is not approved for any NSS use per the CNSA 2.0 FAQ v2.1 (US National Security Agency, 2024). The FAQ’s CNSSP 15 gates are 1 January 2027 for new NSS acquisitions, 31 December 2030 for phasing out equipment that cannot support CNSA 2.0, and 31 December 2031 for mandatory use (US National Security Agency, 2024). The 2030 exclusive-use date specific to software and firmware signing is the September 2022 advisory’s, not the FAQ’s (US National Security Agency, 2022).
Compatibility: a client whose library does not parse composite-signature OIDs treats the certificate as unknown and refuses to validate. It cannot “ignore” the composite signature and accept the leaf, because the leaf is signed end-to-end under the composite scheme. The backward-compatibility posture during transition is one of two patterns. Parallel chains: the CA issues two chains for the same subject (one classical, one composite) and the relying party receives whichever capability negotiation selects (TLS signature_algorithms extension, JWKS kid lookup). Cross-signing: the classical intermediate’s key receives a second certificate, signed by the composite root. A classical-only client keeps validating through the intermediate’s original classical-root signature. A composite-aware client validates through the cross-certificate to the composite root. The cross-signature is itself composite, so it does nothing for the legacy client: the classical path must already exist. Both patterns are policy-gated.
The security guarantee is only as strong as the path the relying party actually validates. A mixed-chain posture must not be described as fully post-quantum protected unless every security-critical signature on the selected validation path is PQ or composite. Once client-side support for composite OIDs reaches the deployment’s cutoff threshold, the classical chain is retired and the dual-path posture is removed.
Where Chapter 29 ends and Chapter 30 picks up
Section titled “Where Chapter 29 ends and Chapter 30 picks up”This chapter migrated three things that a team can own: a certificate hierarchy, a JWKS, and a signing pipeline. Each got a decision procedure that one operator can execute and one operator can verify. Re-issue top-down. Publish the second kid, drain the first, remove it when the last token expires. Reserve the leaf, persist it, then sign. The deprecation rule even reduces to a single measurement: classical validation traffic below one percent for four consecutive weeks.
Chapter 30 is the program-management bookend of Part V, and it starts by putting jwt_signing back where it came from. It is one of the five Ch 25 touchpoints, alongside the tls_endpoint_api that Chapter 28 landed and three more that neither chapter touched. The program schedules all five against NCSC’s 2028, 2031 and 2035 milestones, in four phases with gated exit criteria. It also adds a jurisdictional track these two chapters never needed: Executive Order 14412 and OMB Memorandum M-26-15, which bind U.S. civilian federal systems that CNSA 2.0 explicitly does not cover.
What changes at that scale is the character of the blocker. Nothing in this chapter fails for a reason outside the deployment: a counter is durable or it is not, a client parses the composite OID or it does not. Chapter 30’s risk register is mostly the other kind. An HSM whose firmware never ships support for stateful key material blocks LMS and XMSS no matter how correct the wrapper around them is. A device fleet whose refresh cycle runs past 2030 misses the firmware-signing deadline for reasons that have nothing to do with cryptography. Firmware is the longest tail in the program for exactly the reason this chapter opened with: those keys outlast every other key in the deployment.
Exercises
Section titled “Exercises”-
Parse an X.509 chain fixture (a sequence of
signatureAlgorithmOIDs in certificate-order) and classify each certificate as classical, single-PQ, or composite. Extend the Chapter 29 chain analyzer to flag a chain whose leaf is composite but whose intermediate or root is classical, with a one-line remediation message. -
Build a JWKS fragment for an endpoint that advertises one kid
rs256-2023(RSA) and one kidcomposite-2026(Ed25519+ML-DSA-65). Sign a JWT under the composite kid usingcomposite_sig_signfromsolutions/ch27-hybrid/, then verify it withverify_composite_jwtinsolutions/ch29-pki/. Report the JWT compact form and the verification result. -
Extend the Chapter 29 XMSS durable-counter wrapper so that a caller can supply an HSM-backed counter callback in place of the file-lock implementation. The callback’s contract is: atomically read and increment a monotonic counter, returning the pre-increment value; raise
RuntimeErroron any HSM failure. Cover the callback path with a pytest fake. -
Sketch a one-page deprecation runbook for a classical-only internal CA once its composite replacement is operational. Name the signal that the classical chain has dropped below the deprecation threshold. Name the action: stop issuance, keep the intermediate alive until it expires naturally, and on known compromise revoke the intermediate through the root’s CRL and remove the root from trust stores; a CRL cannot revoke the anchor that signs it. Name the post-deprecation audit: scan the fleet for any validator still pinned to the classical root. Name the rollback path: re-enable classical issuance if the composite chain is found to have a bug.
-
Pick one of the six Ch 26 architectural areas where PKI rollout is the direct action, and one where it is adjacent. Cite the specific Ch 26 subsection and explain why.
Worked solutions and editorial notes for these exercises are in Appendix D, Chapter 29. A separate track, for rebuilding rather than reading: the package exercises/ch29-pki has every function the chapter teaches replaced by a stub. Run PQC_IMPL=exercises pytest tests/ch29 to grade your version against the suite that proves the reference one.
References
Section titled “References”Last updated: