Quantum-Resistant Stateful Hash-Based Signature Schemes

First Available CNSA 2.0 Compliant Code Signing Solution

What Are Stateful Hash-Based Signature Schemes?

Stateful hash-based signature (HBS) schemes are digital signature schemes believed to be resistant to the threat posed by a cryptographically relevant quantum computer.  NIST has standardized two stateful HBS schemes under SP 800-208: the Leighton-Micali Signature (LMS) system and the eXtended Merkle Signature Scheme (XMSS), including their multi-tree variants, the Hierarchical Signature System (HSS) and multi-tree XMSS.  Stateful HBS schemes differ from other asymmetric signature schemes in that a HBS private key is comprised of a predefined set of one-time signature (OTS) private keys.  “State” refers to the capacity to enforce single usage of each OTS private key across the lifespan of the HBS private key.

CNSA 2.0

In September 2022, NSA released the Commercial National Security Algorithm Suite 2.0 (CNSA 2.0), setting timelines for the adoption of quantum-resistant algorithms in national security systems.  Under CNSA 2.0, vendors are encouraged to adopt stateful HBS schemes as defined in SP 800-208 immediately for all software and firmware code signing, with a requirement to support them by 2025.

Comparing to Classical Algorithms

While LMS signatures are considerably larger than signatures generated with legacy RSA keys, they remain smaller than the highest security level ML-DSA signatures and significantly smaller than the stateless hash-based signature algorithm SPHINCS+. In use cases such as application software signing, the signature size has little impact on the solution. However, for memory-constrained devices such as IOT devices, smartcards, or embedded hardware that are validating firmware signatures, the signature size may be a factor.

LMS (2-tier)


LMS (3-tier)



Level 5


256 bits


4096 bits

Signature Size

2,912 bytes

4,368 bytes

4,595 bytes

49,856 bytes

512 bytes

Private Key Size

324 bytes

324 bytes

4,864 bytes

128 bytes

512 bytes

Public Key Size

172 bytes

172 bytes

2,592 bytes

64 bytes

512 bytes

In general, the generation of keys in an LMS/HSS tree takes significantly longer than other algorithms. However, for LMS/HSS the vendor would typically be generating a larger number of LMS/HSS keys to last the lifetime of the product during a “key ceremony” operation. The key generation process is performed on an infrequent basis and is thus usually not a major factor in selection of code signing architecture design.

Performance of signature verification is heavily dependent on the characteristics of the device performing the verification. For example, a vendor of an embedded hardware device with a time budget for code verification during hardware boot-up would be concerned with signature verification performance. Alternatively, a software vendor performing a software update on a server class computer would likely have little concern regarding signature verification performance.

When to Use Stateful HBS for Code Signing Support

The code signing requirements for each vendor’s products will determine whether or not an LMS/HSS architecture is feasible. There are certain use cases such as resource constrained devices or massive code signing volumes that are not good matches for an LMS/HSS code signing solution. However, with proper upfront planning, most code signing requirements can be met using a set of LMS/HSS capable hardware security module (HSM). Read our White Paper: Quantum-Resistant Code Signing Secured by Hardware Security Modules to see reference architectures illustrate a solution for a hypothetical code signing use case.

SP 800-208 and Hardware Security Modules

SP 800-208 requires that all stateful HBS key generation and signature algorithms be implemented within a FIPS 140 certified HSM with Level 3 physical security.  Furthermore, the HSM “shall not allow for the export of private keying material.”  In practice, in order to maintain conformity to the standards, private keys cannot be cloned to other HSMs to establish high availability and redundancy.  Nor can backup and restore operations be performed to create offline cold storage backups of the keying material.  These limitations are intended to ensure that the state of the OTS signature keys is always enforced and keys are never reused, which would introduce cryptologic vulnerabilities into the signature scheme.

For vendors making use of LMS/HSS to sign software or firmware, this means that the entire lifecycle of the stateful HBS private keys must be considered at instantiation of the signature scheme, and keying material be generated across a distributed cache of HSMs to ensure redundancy over that lifetime.

Thales Luna Hardware Security Modules Support of LMS/HSS

LMS/HSS enables customers to begin their transition to quantum-resistant software and firmware signing. Thales has two separate LMS/HSS implementations that are both compliant with SP 800-208 and PKCS#11 v3.

Luna T-Series HSM Release 7.13.0

Thales TCT released support for LMS mechanisms, along with its multi-tree variant HSS, in all Luna T-Series HSMs  starting in version 7.13.0.

Luna 7 Functionality Modules

Thales has also released a Functionality Module (FM) that can be installed on existing Luna 7 HSMs without doing a firmware upgrade.


White Paper: Quantum Resistant Code Signing Secured by HSMs

Download this white paper to learn more about Quantum Resistant Code Signing with Thales’ LMS/HSS implementations that are both compliant with SP 800-208 and PKCS#11 v3.