PQC Code Signing Guide: LMS State, HSMs and Boot Verification Under CNSA 2.0

Software and firmware signing is the first place post-quantum cryptography becomes mandatory, and the hardest to undo: a boot ROM that verifies only a classical signature cannot be patched after the device ships. NSA's CNSA 2.0 puts software and firmware signing at the front of its transition, recommends the stateful hash-based schemes LMS and XMSS for it now, and allows ML-DSA as validated implementations arrive. This guide covers what that means in engineering terms: which signature to use for which signed object, how to size LMS trees, how to keep one-time key state safe inside hardware security modules, and what a bootloader must be able to do to verify a post-quantum signature. It is written for firmware, product security and PKI engineers who already run a classical signing service. For the algorithms themselves see the ML-DSA and SLH-DSA Post-Quantum Signatures Guide; for signing service basics see the Code Signing Security Guide; for every CNSA 2.0 category date see CNSA 2.0 Transition.

Key takeaways

• Signing goes first. NSA's CNSA 2.0 FAQ (version 2.1, December 2024) wants software and firmware signing to begin moving now with LMS or XMSS, and expects new National Security Systems acquisitions to be CNSA 2.0 compliant from 1 January 2027.
• Single trees only for NSS. NSA prefers LMS with SHA-256/192, approves all XMSS parameter sets, and does not allow the multi-tree forms HSS and XMSS^MT, which changes how you build signing capacity and resilience.
• State lives in hardware. NIST SP 800-208 requires stateful key and signature generation in FIPS 140 Level 3 or higher hardware modules that never export the private key and write the next leaf index to non-volatile storage before releasing a signature. NSA grants no waivers for unvalidated signing hardware.
• Resilience comes from more keys, not copies. Because a copied or restored key can reuse a one-time leaf, plan several independent keys on separate modules and provision devices to accept any of them.
• The verifier sets the deadline. Immutable boot code must ship with post-quantum verification and enough key slots before the silicon tapes out; everything above it can be upgraded later.

What CNSA 2.0 requires of signing

The CNSA 2.0 FAQ is the clearest public statement of what a quantum-resistant signing programme must look like. The requirements below are taken from version 2.1 (December 2024), checked in November 2026. They bind National Security Systems directly and suppliers through contracts, and many commercial vendors use them as the benchmark.

The same FAQ states that NSA will not require hybrid certified products for NSS and advises against non-standardised hybrid solutions on mission systems except where NSA recommends them. Commercial products outside NSS often dual-sign during transition anyway; the section on boot verification covers how to do that without creating a downgrade path. For dates outside CNSA 2.0, such as NIST IR 8547 and national guidance, see the Post-Quantum Cryptography Deadlines Tracker.

Choosing a signature per signed object

The question is not "which post-quantum algorithm", it is "who verifies this signature, how often is it produced and can the verifier be updated". Stateful schemes suit few signatures checked by fixed code; stateless ML-DSA suits volume and automation.

NIST SP 800-208 itself says stateful hash-based signatures are not suitable for general use, and names firmware authentication for constrained devices as the intended case: products that need a quantum-resistant scheme soon, have long lifetimes, and could not practically switch schemes after deployment.

Sizing LMS trees

Every LMS key can sign exactly 2^h messages, where h is the tree height. SP 800-208 allows heights of 5, 10, 15, 20 and 25 for LMS, and 10, 16 and 20 for single-tree XMSS. A key that runs out cannot sign again, so size it for the product's whole signing life with margin.

Signature sizes are computed from the RFC 8554 formulas (an LM-OTS signature of 1,124 bytes plus 32 bytes per tree level and an 8-byte header); the public key is 56 bytes. The SHA-256/192 sets NSA prefers produce smaller signatures because each hash value is 24 bytes rather than 32. Exact sizes depend on the Winternitz parameter chosen, which also trades signature size against signing and verification time. SP 800-208 Section 9.2 notes that the 192-bit sets have lower generic collision resistance than the 256-bit sets, which is acceptable under NSA's guidance but should be a conscious choice.

• Count every signature: test builds, re-signs after a failed release and emergency patches all consume leaves. Separate test keys from production keys so test volume never spends production capacity.
• Prefer more keys to taller trees: several height-10 or height-15 keys on separate modules give both capacity and resilience, and match the distribution option in SP 800-208 Section 7 that stays within NSA's single-tree rule.

State management in HSMs

RFC 8554 is blunt about the risk: if a secret key state is used twice, no cryptographic security guarantees remain. Every operational habit that copies a key, including backups, cluster replication, VM snapshots and key export for disaster recovery, is a potential leaf reuse. SP 800-208 Section 8.1 therefore sets requirements for the module:

• Validated hardware: FIPS 140-2 or FIPS 140-3 at physical security Level 3 or higher, with a non-modifiable or limited operational environment, approved mode only and no bypass mode.
• No export: the module must not allow export of private keying material, so conventional HSM backup and cloning of the key is excluded.
• Index before signature: the module increments the leaf index on each request and stores it in non-volatile storage before it releases the signature or accepts the next request. Section 9.1 warns that cached writes can be lost on power failure, and suggests hardware monotonic counters.
• Each OTS key once: the module must never use a one-time key for more than one signature.

RFC 9708 adds the same warnings for CMS deployments: track used leaves with integrity protection, and handle failed writes, VM snapshots and cloning explicitly.

Designing for module failure

Without export, a failed module takes its key with it. SP 800-208 Section 7 offers two answers. The first is to create several independent stateful keys on different modules and configure verifiers to accept signatures from any of them. The second distributes one key's leaves across modules using two-level HSS or XMSS^MT, with bottom-level keys generated up front in the key ceremony. NSA does not allow HSS or XMSS^MT for NSS, so CNSA 2.0 products use the first option: provision two or more public keys, from separate modules held in separate locations, into the verifier. Record which key signed each release, retire keys deliberately, and test that a device still boots when the primary key's module is gone.

For the module itself, see the HSM Deployment and Operations Guide. Confirm with the HSM supplier, in writing, that its stateful signing implementation is CMVP-validated for LMS or XMSS and how it persists the index.

Bootloader verification constraints

The verifier, not the signer, sets the real deadline. Boot code in mask ROM or one-time programmable memory cannot be updated after manufacture, so its post-quantum capability is fixed when the chip design is frozen. NIST SP 800-193 frames platform firmware resilience as protection, detection and recovery; a quantum-resistant verifier is part of protection, and the ability to recover with a different key is part of recovery.

• Key slots: reserve space in fuses or OTP for hashes of several post-quantum public keys, so a lost module or a compromised key can be retired without new silicon. The NVIDIA case shows why revocation is hard once verifiers trust a key: after NVIDIA Code-Signing Certificates Stolen 2022, expired certificates were still accepted for driver signing and revoking them would have broken legitimate drivers.
• Memory and size: hash-based verification needs only a hash function, which boot ROMs usually have in hardware, but signatures are kilobytes rather than the 64 to 512 bytes of classical schemes. Check flash layout, image headers and the RAM available to the first-stage loader.
• Boot time: verification of LMS is fast, but slow hash hardware and large Winternitz parameters add measurable boot time on small microcontrollers. Measure it on the target part, not a development board.
• Algorithm agility in updatable stages: second-stage loaders and update agents should carry an algorithm identifier in the image header and be able to add ML-DSA verification through a signed update.
• Anti-rollback: pair signatures with a security version number checked against a monotonic counter, so an attacker cannot install an older image signed only with a classical key.

Dual signing during transition

Many products will carry both a classical and a post-quantum signature on the same image while verifiers in the field are mixed. The verifier policy decides whether this adds security. "Accept either" lets an attacker who breaks the classical scheme bypass the post-quantum one. "Require both where supported" is the safe default: devices with post-quantum capability check both signatures, and older devices keep their classical check until retired. Write the policy into the image format so the device cannot be told to skip a check by the image itself.

Implementation steps

1. Inventory verifiers: list every boot ROM, bootloader, update agent and OS loader that verifies your signatures, with whether it can be updated and what algorithms it accepts. See the Firmware and Boot Security Guide.
2. Fix the silicon requirement: for chips in design, specify LMS or XMSS verification in ROM, at least two key slots and an anti-rollback counter.
3. Stand up stateful signing: CMVP-validated modules, separate production and test keys, tree heights from projected signing volume, and a signed ceremony record for each key.
4. Test state loss in the lab: pull power during signing, restore a module from backup and fail over a cluster, and confirm no leaf index is ever reused. Do this before production keys exist.
5. Pilot dual signing: sign one product line with both classical and post-quantum signatures, verify on every device generation, and measure boot time and image size.
6. Roll out by verifier group: enable "require both" on post-quantum-capable devices first. Rollback is re-releasing the image with the classical signature only, which is why classical keys stay live during transition.
7. Add ML-DSA for volume signing: move OS, package and container signing to ML-DSA-87 as validated modules and verifier support arrive.

Decision guidance

• LMS or XMSS: choose LMS with SHA-256/192 unless your silicon, HSM or customers already standardise on XMSS. Supporting both doubles validation work for little gain.
• Stateful or ML-DSA: stateful for immutable verifiers and low volume; ML-DSA for CI-driven and high-volume signing where state handling would be fragile.
• Small vendors: one product family, two LMS keys on two validated modules, and a written ceremony is a complete programme. Rely on chip suppliers for ROM capability and ask for it in contracts; the PQC Supplier Readiness Questionnaire helps.
• Large vendors: run a central signing service with per-product keys, capacity monitoring and a key retirement schedule, and treat signing keys as privileged machine identities with owners; see Post-Quantum Migration for NHIs.

Detection and measurement

• Remaining leaves per key: alert at a threshold such as 20 percent remaining, and forecast exhaustion date from signing rate.
• Index continuity: reconcile the leaf index in each signature against the module's counter; a repeated or backwards index is a critical incident.
• Signing requests by identity: log who or what requested each signature and from which pipeline, as for classical signing.
• Coverage metrics: percentage of releases carrying a post-quantum signature; percentage of shipped device models with a post-quantum-capable root of trust; number of products relying on a single signing module.

Common failure patterns

• Restoring a stateful key from backup: a routine HSM restore rolls the index back and reuses leaves, voiding the scheme's security.
• Stateful keys in CI: parallel build agents and retried jobs consume and race on state; use ML-DSA for automated pipelines.
• One key slot in ROM: a lost module or a leaked key strands every shipped device.
• "Accept either" dual-signature policy: the post-quantum signature adds nothing against an attacker who can forge the classical one.
• Using HSS for NSS products: multi-tree is allowed by SP 800-208 but not by CNSA 2.0.
• Undersized trees: test and emergency signing exhaust a production key years early.

Framework mapping

Practitioner checklist

• List every verifier of your signatures and whether it can be updated.
• Specify LMS or XMSS verification, multiple key slots and anti-rollback in new silicon.
• Use LMS with SHA-256/192 single trees for CNSA 2.0 products; no HSS or XMSS^MT.
• Generate and use stateful keys only in CMVP-validated modules that never export them.
• Test power loss, restore and failover for leaf reuse before production keys exist.
• Provision at least two independent signing keys from separate modules into each verifier.
• Size trees from projected signing volume and monitor remaining leaves.
• Dual-sign with a "require both where supported" policy during transition.
• Plan ML-DSA-87 for high-volume software signing as validated modules arrive.

Standards and references

• NSA: The Commercial National Security Algorithm Suite 2.0 and Quantum Computing FAQ
• NIST: SP 800-208 Recommendation for Stateful Hash-Based Signature Schemes
• NIST: FIPS 204 Module-Lattice-Based Digital Signature Standard
• IRTF CFRG: RFC 8554 Leighton-Micali Hash-Based Signatures
• IETF: RFC 9708 Use of the HSS/LMS Hash-Based Signature Algorithm in the Cryptographic Message Syntax
• NIST: SP 800-193 Platform Firmware Resiliency Guidelines

Related NHI Mgmt Group resources: Post-Quantum Cryptography Migration Guide, CNSA 2.0 Transition, Linux Secure Boot and Shim Guide, Code Signing Policy Template.