XMSS & LMS (stateful hash-based)
XMSS and LMS are stateful hash-based signature schemes standardized by NIST in SP 800-208 (and by the IETF in RFC 8391 and RFC 8554). They offer small signatures, fast verification, and rock-solid hash-only security — but each one-time key may be used at most once, making state management mission-critical.
How it works
Both schemes build a Merkle tree of one-time signature (OTS) key pairs. The tree's root is the long-term public key; each leaf is a one-time key that signs a single message. A signature includes the OTS signature plus the authentication path proving that leaf belongs to the published root.
The decisive property is that they are stateful: every leaf index must be used at most once, and never reused. If the signer ever reuses a leaf — signing two different messages with the same one-time key — the OTS security collapses and an attacker can forge signatures. The signer must therefore reliably track and persist which indices have been consumed.
- LMS (RFC 8554, Leighton-Micali) and its multi-tree variant HSS (Hierarchical Signature System).
- XMSS (RFC 8391, eXtended Merkle Signature Scheme) and its multi-tree variant XMSS^MT.
Parameter sets
Parameters are governed by the underlying hash (typically SHA-256), the Winternitz parameter, and the tree height h, which fixes the total number of signatures available as 2^h. Representative figures:
| Scheme | Hash | Tree height (h) | Max signatures | Public key | Signature (approx.) |
|---|---|---|---|---|---|
| LMS | SHA-256 | 10 | 1024 | ~60 B | ~1.5-2.7 KB |
| XMSS | SHA-256 | 10 | 1024 | ~64 B | ~2.5 KB |
| XMSS^MT / HSS | SHA-256 | 20-60 (multi-tree) | 2^20 - 2^60 | ~64 B | larger (multi-layer) |
Higher trees allow more signatures but increase signature size and key-generation cost.
Strengths & tradeoffs
- Hash-only security. Like SLH-DSA, security reduces to the underlying hash — extremely conservative, no lattice or coding assumptions.
- Compact, fast verify. Signatures and keys are small and verification is cheap.
- Tradeoff — state. The signer must never reuse a leaf. This requires durable, atomic state tracking (ideally in hardware), and limits the total number of signatures to 2^h.
When to use it
XMSS/LMS are ideal for firmware, secure boot, and software signing: a controlled signing environment, a bounded and predictable number of signatures, and hardware that can manage the state safely. NIST SP 800-208 approves them precisely for these long-lived signing roots. If you cannot guarantee single-use state, use the stateless SLH-DSA instead.
Code example
State management with the standard openssl CLI conceptually:
# NOTE: stateful LMS/XMSS are NOT available through the OpenSSL CLI.
# OpenSSL cannot generate or sign with LMS/XMSS keys (no genpkey support;
# it errors with "Error initializing LMS context"). Use a purpose-built
# implementation that safely manages the one-time-key STATE:
# LMS/HSS : RFC 8554 reference code, Cisco "hash-sigs" library, Bouncy Castle
# XMSS : RFC 8391 "xmss-reference", Bouncy Castle
# Some stacks (AWS-LC, Bouncy Castle) can VERIFY LMS signatures even where they
# cannot generate them. The hard part is never the math - it is never reusing a
# one-time leaf index, which is why state management belongs in dedicated tooling/HSMs.Related
SP 800-208 →
The standard for stateful hash-based signatures.
Hash-based cryptography →
Merkle trees and one-time signatures.
SLH-DSA →
The stateless hash-based alternative.
Digital signatures →
Signature concepts and goals.
Standards & references
- NIST SP 800-208 — the standard approving stateful LMS/HSS and XMSS/XMSS^MT.
- RFC 8391 (XMSS) — the XMSS specification.
- RFC 8554 (LMS) — the LMS and HSS specification.
- RFC 9708 (HSS/LMS in CMS) — using HSS/LMS signatures in CMS.
- Resources — full standards register
XMSS 与 LMS 有状态哈希签名
XMSS 与 LMS 是 NIST 在 SP 800-208 中标准化的有状态哈希签名方案（IETF 亦以 RFC 8391 与 RFC 8554 定义）。它们签名小巧、验证迅速、仅依赖哈希的安全性极为稳固——但每个一次性密钥最多只能使用一次，使状态管理成为成败关键。
工作原理
两种方案都构建一棵由一次性签名（OTS）密钥对组成的 Merkle 树。树根是长期公钥；每个叶子是只签名一条消息的一次性密钥。一份签名包含 OTS 签名以及证明该叶子属于已发布树根的认证路径。
决定性特性是它们有状态：每个叶子索引最多只能使用一次，且绝不能复用。一旦签名者复用某叶子——用同一一次性密钥签两条不同消息——OTS 安全性即告崩溃，攻击者便能伪造签名。因此签名者必须可靠地跟踪并持久化已消耗的索引。
- LMS（RFC 8554，Leighton-Micali）及其多树变体 HSS（分层签名系统）。
- XMSS（RFC 8391，扩展 Merkle 签名方案）及其多树变体 XMSS^MT。
参数集
参数由底层哈希（通常 SHA-256）、Winternitz 参数与树高 h 决定，后者将可用签名总数固定为 2^h。代表性数据：
| 方案 | 哈希 | 树高 h | 最大签名数 | 公钥 | 签名（约） |
|---|---|---|---|---|---|
| LMS | SHA-256 | 10 | 1024 | 约 60 B | 约 1.5-2.7 KB |
| XMSS | SHA-256 | 10 | 1024 | 约 64 B | 约 2.5 KB |
| XMSS^MT / HSS | SHA-256 | 20-60（多树） | 2^20 - 2^60 | 约 64 B | 更大（多层） |
树越高可签名次数越多，但签名尺寸与密钥生成开销也随之增大。
优势与取舍
- 仅依赖哈希。与 SLH-DSA 一样，安全性归约到底层哈希——极为保守，无格或编码假设。
- 紧凑且验证快。签名与密钥小巧，验证成本低廉。
- 取舍——状态。签名者绝不能复用叶子。这要求持久、原子的状态跟踪（最好由硬件完成），并将签名总数限制在 2^h。
适用场景
XMSS/LMS 非常适合固件、安全启动与软件签名：受控的签名环境、有界且可预测的签名数量、以及能安全管理状态的硬件。NIST SP 800-208 正是为这类长寿命签名根而批准它们。若无法保证单次使用，请改用无状态的 SLH-DSA。
代码示例
以标准 openssl CLI 在概念上演示状态管理：
# 注意：有状态的 LMS/XMSS 无法通过 OpenSSL 命令行使用。
# OpenSSL 不能生成或用 LMS/XMSS 私钥签名（无 genpkey 支持，
# 会报 "Error initializing LMS context"）。请使用能安全管理一次性密钥
# 「状态」的专用实现：
# LMS/HSS ： RFC 8554 参考实现、Cisco "hash-sigs" 库、Bouncy Castle
# XMSS ： RFC 8391 "xmss-reference"、Bouncy Castle
# 部分实现（AWS-LC、Bouncy Castle）即便不能生成也能「验签」LMS。
# 难点从不在数学，而在于绝不重用一次性叶子索引——因此状态管理应交给专用工具/HSM。相关页面
标准与参考
- NIST SP 800-208 — 批准有状态 LMS/HSS 与 XMSS/XMSS^MT 的标准。
- RFC 8391 XMSS — XMSS 规范。
- RFC 8554 LMS — LMS 与 HSS 规范。
- RFC 9708 CMS 中的 HSS/LMS — 在 CMS 中使用 HSS/LMS 签名。
- 资源链接 — 完整标准登记册