Post-Quantum Cryptography Advanced

XMSS and LMS Hash-Based Signatures

XMSS and LMS sign with nothing but a hash function, so quantum computers do not break them. Learn how Winternitz chains and Merkle trees work, why a signer must never reuse a one-time key, and how a reused key lets an attacker forge a message.

Pashalis Laoutaris October 20, 2026 34 min read

Try it

Interactive LMS and HSS Signatures Visualizer

🔐 LMS Signatures

Variant:

Field 1:

Field 2:

Field 3:

Field 4:

Field 5:

Field 6:

Speed:

Enter text and click a button to start!

–

XMSS and LMS Hash-Based Signatures

Introduction

Most digital signatures rest on a hard problem from number theory, such as factoring or the discrete logarithm. A large quantum computer would solve those problems. Hash-based signatures take a different road. They use only a cryptographic hash function, and the only way to forge a signature is to attack that function. No quantum attack is known that breaks hash functions in this way, and the schemes in this guide have published specifications in RFC 8391, RFC 8554, and NIST Special Publication 800-208.

The price is a strange one. These schemes are stateful. The private key changes with every signature, and if a signer ever uses the same state twice, the security is gone. This guide explains the two standard schemes, LMS (with its multi-level form HSS) and XMSS. It builds both in Python, checks LMS against the test vectors of RFC 8554, and then breaks it on purpose by signing with one key several times.

The stateless alternatives are the SPHINCS+ guide, the Dilithium guide, and the Falcon guide. They avoid the state at the cost of larger signatures or other assumptions. The SHA-2 guide covers the hash function used here.

History and Standards
One-Time Signatures with Hash Chains
From One Key to Many: the Merkle Tree
HSS: a Tree of Trees
XMSS
LMS Compared with XMSS
The State Problem
Interactive Visualizer
A Worked Example
Python Implementation
Where It Is Used
Limitations
Security Status
FAQ
References

History and Standards

The ideas are old. RFC 8554 says that one-time signature systems, and general signature systems built from them, have been known since 1979 from the work of Merkle. They were well studied in the 1990s and have received renewed attention in the last decade, because they are post-quantum secure and suit compact implementations. The RFC names Lamport, Diffie, Winternitz, and Merkle as the authors of the underlying one-time scheme.

LMS is the Leighton-Micali Signature system, an adaptation of that work that Leighton and Micali published in 1995. RFC 8554, “Leighton-Micali Hash-Based Signatures”, was written by McGrew, Curcio, and Fluhrer of Cisco and published in April 2019. It says that it rests on U.S. Patent 5,432,852, which was issued over twenty years earlier and has expired. The RFC defines LM-OTS, the one-time scheme, LMS, the many-time scheme, and HSS, a hierarchy of LMS trees.

XMSS is the eXtended Merkle Signature Scheme. Buchmann, Dahmen, and Hülsing proposed it in 2011. RFC 8391, written by Hülsing, Butin, Gazdag, Rijneveld, and Mohaisen, specifies it in May 2018, together with the one-time scheme WOTS+ and a multi-tree variant called XMSS^MT. Both RFCs are informational documents of the Crypto Forum Research Group, not Internet standards.

NIST followed with Special Publication 800-208, “Recommendation for Stateful Hash-Based Signature Schemes”. It specifies LMS, XMSS, and their multi-tree variants HSS and XMSS^MT. The publication approves four hash functions for them: SHA-256, SHA-256/192, SHAKE256/256, and SHAKE256/192. This guide uses SHA-256 with 32-byte outputs, the first of these.

One-Time Signatures with Hash Chains

Start with a one-time signature. A hash chain applies a hash function over and over: x, H(x), H(H(x)), and so on. Going forward is easy and going back is infeasible. A one-time key has many chains. The private key is the start x of each chain, and the public key is built from their ends.

To sign, the signer writes the message hash as a list of small numbers, called digits. For each chain, the signer releases the value at the step that the digit names. A digit of 5 means that the signer publishes H^5(x). The verifier takes that value, hashes it the remaining steps to the end of the chain, and checks that the end matches the public key. Nobody can walk a chain backward, so only the key owner can produce the values.

The width w decides the trade-off. LM-OTS allows w of 1, 2, 4, or 8 bits per digit. A wider digit needs fewer chains, which gives a shorter signature, but each chain is longer and takes more hashing. RFC 8554 gives the numbers. A chain has 2^w - 1 steps, and the signature is 4 + n * (p + 1) bytes, where p is the number of chains. With n = 32 the signatures take 8516, 4292, 2180, and 1124 bytes for w of 1, 2, 4, and 8, with 265, 133, 67, and 34 chains. I recomputed p and the checksum shift ls with the algorithm of Appendix B of the RFC, and they match its table.

There is a trap. An attacker who sees a signature can walk any chain forward, which raises a digit. To stop this, the scheme adds a checksum. It is the sum of how far each digit is from its maximum, written as extra digits and signed as well. Raising a message digit lowers the checksum, and a lower checksum digit would need a value from earlier in a chain, which the attacker does not have.

The message is not signed directly. The signer picks a random 32-byte value C and computes Q = SHA-256(I || q || 0x8181 || C || message). The digest Q and its checksum give the digits. Every hash in the scheme starts with the 16-byte identifier I of the tree and the 32-bit number q of the leaf, and every kind of hash has its own fixed tag. This keeps one hash from being mistaken for another. RFC 8554 explains the choice of 16 bytes for I: the input of a chain step is then 55 bytes long, which SHA-256 hashes in a single compression step.

From One Key to Many: the Merkle Tree

A one-time key signs one message. To sign many, LMS builds a binary tree. Each leaf holds the hash of one one-time public key. Each inner node is the hash of its two children. The root is the public key of the whole tree, and it has only 32 bytes, plus the identifier and two type codes, which makes 56 bytes.

A tree of height h has 2^h leaves and signs 2^h messages. The private key is all the one-time private keys, which the RFC lets you derive from a single secret seed with x[i] = SHA-256(I || q || i || 0xff || SEED). The signer also keeps the number q of the next unused leaf. That number is the state.

A signature holds the leaf number q, the one-time signature, and the authentication path. That path is the h siblings of the nodes on the way from the leaf to the root. A verifier completes the chains, rebuilds the one-time public key and the leaf, and then hashes upward with the path, putting each sibling on the left or the right. If the result equals the root in the public key, the signature is valid.

The RFC gives a count of the cost. Generating the public key of a one-time key takes p * (2^w - 1) + 1 hashes, which is 8,671 for w = 8. A tree needs one such key for every leaf, which is why the key generation of a large tree is slow.

HSS: a Tree of Trees

A tree with a million leaves needs a million one-time keys before it can publish its root. HSS avoids that cost. It stacks LMS trees in up to eight levels. The top tree signs the public keys of trees below it, and the lowest tree signs the actual messages. An HSS public key is the number of levels and the public key of the top tree, which is 60 bytes. A signature holds one LMS signature for each level, and the public keys of the lower trees.

When the lowest tree is used up, the signer builds a fresh one and has the tree above sign it. Two levels of height 10 can sign 2^20 messages. At the start, only the top tree and the first tree of the lower level must be computed, which is 2,048 leaves and not a million. The price is a longer signature and a longer verification, since every level must verify.

XMSS

XMSS has the same shape: a one-time scheme under a Merkle tree. It differs in the details, which aim at weaker assumptions about the hash function.

WOTS+. The chains are walked with a keyed hash F and a bitmask, in each step. A pseudorandom function PRF of a public seed and an address gives the key and the mask for every single hash call. The address is a 32-byte string that names the position of the call in the structure.
Fixed width. All parameter sets of the RFC use the Winternitz parameter 16. With SHA-256 that gives 67 chains, and an XMSS signature of 4 + 32 + (67 + h) * 32 bytes: 2,500, 2,692, and 2,820 bytes for the heights 10, 16, and 20. Those are the sizes in Table 3 of RFC 8391.
L-trees. The 67 values of a one-time public key are compressed into one leaf by a small unbalanced tree, with a randomized hash at each node.
Randomized tree hash. Every node of the main tree is H(KEY, (LEFT xor BM0) || (RIGHT xor BM1)), where the key and the masks come from PRF.
Message hash. The message is hashed with a randomizer r, the root of the tree, and the leaf index. The RFC gives the reason: this makes the hash depend on the position and on the user, which stops an attack that targets many users at once.

An XMSS public key is the identifier of the parameter set, the root, and the public seed, which is 68 bytes. The RFC states the result of these choices in its abstract. XMSS relies only on properties of the hash function, and it is even secure when the collision resistance of the hash function is broken. That is a weaker requirement than the one for most signature schemes.

The multi-tree variant XMSS^MT stacks XMSS trees in the way that HSS stacks LMS trees. I did not implement it.

LMS Compared with XMSS

RFC 8554 makes the comparison in its last section. XMSS signatures are slightly shorter than HSS signatures for equivalent security and an equal number of signatures. HSS has other advantages. Its operations are roughly four times faster than the comparable XMSS ones when SHA-256 is used. The reason is that the hash in the Winternitz chain dominates the cost, and XMSS needs four compression-function calls for it where HSS needs one. HSS is also somewhat simpler, since each hash call is a prefix followed by the data.

My own code agrees with the direction. A tree of 32 leaves with 67 chains of 15 steps takes about 0.03 seconds as an LMS tree and about 0.20 seconds as an XMSS tree in my Python, which is about 6.1 times as long. This is a measurement of my teaching code on one computer, and it counts more than the chain hashes. For equal chain counts, the sizes agree with the RFC as well. LMS with w = 4 and height 10 gives a signature of 2508 bytes, and XMSS with height 10 gives 2,500.

The State Problem

Both schemes depend on one rule: a one-time key must sign at most one message. RFC 8554 requires that each one-time private key be used at most once, and the CFRG notes in both RFCs repeat the warning. If a secret key state is used twice, no cryptographic security guarantees remain, and it becomes feasible to forge a signature on a new message. The notes say that developers should not use these schemes except in systems that prevent the reuse of secret key states.

NIST SP 800-208 describes why this is hard. The signing process should happen in a highly controlled environment. A routine action can cause reuse. The publication names writing the state to a file as an example. A write can be cached and reach the storage only later, so a crash after a signature was exported can bring back the old state. The publication requires that the leaf index be stored in nonvolatile storage before a signature leaves the module.

I wanted to see what reuse costs, so I measured it. I took an LMS tree with w = 8, reset the state by hand, and signed several different messages with the same leaf. For each of the 34 chains the attacker then knows the value at the lowest step among the signatures. A new message can be forged if its digits, checksum digits included, are all at least as high as those lowest steps, because then every needed value is a few more hash steps away. The attacker picks any message and tries random values of C until the digits fit. The result is a signature that the real public key accepts.

Signatures with one leaf	Fitting digests among 300,000 tries	First one found after
2	0	none
3	0	none
4	4	30,528 tries
5	44	5,779 tries
6	155	1,081 tries

With two or three signatures, I found nothing in 300,000 tries, so the checksum makes the attack hard at that point. With four signatures, a forged signature on the message “pay Mallory 1000000 dollars” appeared after 30,528 tries, and the real public key accepted it. More signatures make it easier, and with six it took about a thousand tries. The numbers depend on the random values, but the trend does not. Each reused leaf lowers the minima and widens the set of messages that an attacker can sign.

Interactive Visualizer

The visualizer above works with LMS and HSS, for real, using SHA-256 in your browser. It has six modes.

Sign with LMS, in four variants of w. Enter a secret seed, an identifier, a message, a leaf number from 0 to 31, and a randomizer C. If you leave C empty, the browser picks a random one. The tree has height 5, so the page can build all 32 leaves in a fraction of a second. The log shows the secret chain starts, the message digest, the digits and checksum, the signature chains, the public key of the leaf, the tree, the authentication path, and a check by verification.
Verify an LMS signature. Enter a 56-byte public key, a message, and a signature. The log shows the parsing, the digits, the finishing of the chains with a count of hashes, the rebuilding of the leaf, the walk up the tree, and the comparison. The default is the second signature of the first test case of the RFC.
Verify an HSS signature. The default is the whole first test case of the RFC, with two levels. The log shows each level in turn.

A message that starts with 0x is read as hexadecimal bytes. The messages of the RFC test cases end with a line break, so they are given this way.

A Worked Example

The first test case in Appendix F of RFC 8554 is an HSS key with 2 levels. Both trees use LMS type 5 (LMS_SHA256_M32_H5, height 5) and LM-OTS type 4 (LMOTS_SHA256_N32_W8). The identifier of the top tree is 61a5d57d37f5e46bfb7520806b07a1b8 and its root is 50650e3b31fe4a773ea29a07f09cf2ea30e579f0df58ef8e298da0434cb2b878.

The message has 162 bytes: “The powers not delegated to the United States by the Constitution, nor prohibited by it to the States, are reserved to the States respectively, or to the people.” followed by a line break. The signature is 2644 bytes long. It holds the signature of the top tree, which has leaf number 5, followed by the public key of the second tree, then the signature of the second tree on the message, with leaf number 10. The first LMS signature takes 1292 bytes, and the public key of the second tree is 0000000500000004d2f14ff6346af964569f7d6cb880a1b66c5004917da6eafe4d9ef6c6407b3db0e5485b122d9ebe15cda93cfec582d7ab.

To verify the second signature, the verifier first hashes the message with the identifier of the second tree, the leaf number, and the randomizer from the signature. The digest is c5a14747abacdb84b5aefff87139afb6c7fd8cd5d72a0e5f389c2082da173f28. With w = 8, every byte is a digit, so the first digits are 197, 161, 71, 71, 171, 172. The checksum adds up to 3692, which is the two digits 14 and 108. The verifier then finishes every chain. The 34 chains have 255 steps each, which is 8,670 in all. The signer already walked 4,080 steps less than that, so the verifier needs 4,080 hashes. Then it hashes the ends into a leaf and walks up five levels of the tree. If the result equals the root, the second tree is the one that the top tree signed, and the signature is valid.

Python Implementation

The first file implements LM-OTS, LMS, and HSS. The class LmsKey keeps the state in the field q, and signing moves it on before the signature is returned. The functions lms_verify and hss_verify check the lengths and the type codes as the RFC requires.

# lms.py
# Leighton-Micali Signatures (LMS), the one-time signatures LM-OTS under them, and the
# multi-tree HSS, as in RFC 8554. Parameter sets with SHA-256 and n = 32 only.
# Teaching code. It is slow, and it keeps its state in memory.

import hashlib
import os
import struct

D_PBLC, D_MESG, D_LEAF, D_INTR = 0x8080, 0x8181, 0x8282, 0x8383
N = 32  # bytes in a hash

# LM-OTS type code -> (w, p, ls): the Winternitz width, the number of chains, and the checksum shift
LMOTS_TYPES = {1: (1, 265, 7), 2: (2, 133, 6), 3: (4, 67, 4), 4: (8, 34, 0)}
# LMS type code -> the height h of the tree
LMS_TYPES = {5: 5, 6: 10, 7: 15, 8: 20, 9: 25}


def sha256(*parts):
    return hashlib.sha256(b"".join(parts)).digest()


def u32(x):
    return struct.pack(">I", x)


def u16(x):
    return struct.pack(">H", x)


def u8(x):
    return bytes([x])


def coef(data, i, w):
    """The i-th w-bit number of the byte string."""
    return (data[i * w // 8] >> (8 - (w * (i % (8 // w)) + w))) & (2 ** w - 1)


def checksum(data, w, ls):
    total = sum((2 ** w - 1) - coef(data, i, w) for i in range(N * 8 // w))
    return u16((total << ls) & 0xFFFF)


# ---------- LM-OTS: one-time signatures ----------

def ots_private_key(seed, identifier, q, p):
    """The p secret values for leaf q, derived from one seed (Appendix A of the RFC)."""
    return [sha256(identifier, u32(q), u16(i), u8(0xFF), seed) for i in range(p)]


def _chain(identifier, q, i, start, steps_from, steps_to):
    value = start
    for j in range(steps_from, steps_to):
        value = sha256(identifier, u32(q), u16(i), u8(j), value)
    return value


def ots_public_key_hash(ots_type, identifier, q, x):
    """K, the hash of the ends of all chains."""
    w, p, _ = LMOTS_TYPES[ots_type]
    ends = [_chain(identifier, q, i, x[i], 0, 2 ** w - 1) for i in range(p)]
    return sha256(identifier, u32(q), u16(D_PBLC), *ends)


def ots_sign(ots_type, identifier, q, x, message, randomizer):
    w, p, ls = LMOTS_TYPES[ots_type]
    digest = sha256(identifier, u32(q), u16(D_MESG), randomizer, message)
    digits = digest + checksum(digest, w, ls)
    ys = [_chain(identifier, q, i, x[i], 0, coef(digits, i, w)) for i in range(p)]
    return u32(ots_type) + randomizer + b"".join(ys)


def ots_candidate(ots_type, identifier, q, message, signature):
    """The public key hash that a signature claims. It is valid when it equals K."""
    w, p, ls = LMOTS_TYPES[ots_type]
    if len(signature) != 4 + N * (p + 1) or struct.unpack(">I", signature[:4])[0] != ots_type:
        return None
    randomizer, ys = signature[4:4 + N], [signature[4 + N * (i + 1):4 + N * (i + 2)] for i in range(p)]
    digest = sha256(identifier, u32(q), u16(D_MESG), randomizer, message)
    digits = digest + checksum(digest, w, ls)
    ends = [_chain(identifier, q, i, ys[i], coef(digits, i, w), 2 ** w - 1) for i in range(p)]
    return sha256(identifier, u32(q), u16(D_PBLC), *ends)


# ---------- LMS: a Merkle tree of one-time keys ----------

class LmsKey:
    def __init__(self, lms_type, ots_type, seed, identifier):
        self.lms_type, self.ots_type, self.seed, self.identifier = lms_type, ots_type, seed, identifier
        self.h = LMS_TYPES[lms_type]
        self.q = 0  # the next unused leaf: this is the state
        _, p, _ = LMOTS_TYPES[ots_type]
        leaves = 2 ** self.h
        # node r of the tree: the root is 1, the children of r are 2r and 2r + 1, the leaves are 2^h ... 2^(h+1) - 1
        self.nodes = [None] * (2 * leaves)
        for q in range(leaves):
            k = ots_public_key_hash(ots_type, identifier, q, ots_private_key(seed, identifier, q, p))
            self.nodes[leaves + q] = sha256(identifier, u32(leaves + q), u16(D_LEAF), k)
        for r in range(leaves - 1, 0, -1):
            self.nodes[r] = sha256(identifier, u32(r), u16(D_INTR), self.nodes[2 * r], self.nodes[2 * r + 1])

    @property
    def public_key(self):
        return u32(self.lms_type) + u32(self.ots_type) + self.identifier + self.nodes[1]

    def sign(self, message, randomizer=None, q=None):
        """An LMS signature. The leaf is used once: q moves on before the signature is returned."""
        if q is None:
            q = self.q
        if q >= 2 ** self.h or q < self.q:
            raise ValueError("this leaf is used up or does not exist")
        self.q = q + 1
        _, p, _ = LMOTS_TYPES[self.ots_type]
        x = ots_private_key(self.seed, self.identifier, q, p)
        ots = ots_sign(self.ots_type, self.identifier, q, x, message, randomizer or os.urandom(N))
        path, r = [], 2 ** self.h + q
        while r > 1:
            path.append(self.nodes[r ^ 1])  # the sibling
            r //= 2
        return u32(q) + ots + u32(self.lms_type) + b"".join(path)


def lms_signature_length(signature):
    """The length of the LMS signature at the start of the bytes, or None."""
    if len(signature) < 8:
        return None
    ots_type = struct.unpack(">I", signature[4:8])[0]
    if ots_type not in LMOTS_TYPES:
        return None
    p = LMOTS_TYPES[ots_type][1]
    if len(signature) < 12 + N * (p + 1):
        return None
    lms_type = struct.unpack(">I", signature[8 + N * (p + 1):12 + N * (p + 1)])[0]
    if lms_type not in LMS_TYPES:
        return None
    return 12 + N * (p + 1) + N * LMS_TYPES[lms_type]


def lms_verify(public_key, message, signature):
    if len(public_key) != 24 + N:
        return False
    lms_type, ots_type = struct.unpack(">II", public_key[:8])
    identifier, root = public_key[8:24], public_key[24:]
    if lms_type not in LMS_TYPES or ots_type not in LMOTS_TYPES:
        return False
    h, p = LMS_TYPES[lms_type], LMOTS_TYPES[ots_type][1]
    if len(signature) != 12 + N * (p + 1) + N * h:
        return False
    q = struct.unpack(">I", signature[:4])[0]
    if struct.unpack(">I", signature[4:8])[0] != ots_type or q >= 2 ** h:
        return False
    if struct.unpack(">I", signature[8 + N * (p + 1):12 + N * (p + 1)])[0] != lms_type:
        return False
    candidate = ots_candidate(ots_type, identifier, q, message, signature[4:8 + N * (p + 1)])
    path = signature[12 + N * (p + 1):]
    r = 2 ** h + q
    node = sha256(identifier, u32(r), u16(D_LEAF), candidate)
    for i in range(h):
        sibling = path[N * i:N * (i + 1)]
        parent = r // 2
        if r % 2:
            node = sha256(identifier, u32(parent), u16(D_INTR), sibling, node)
        else:
            node = sha256(identifier, u32(parent), u16(D_INTR), node, sibling)
        r = parent
    return node == root


# ---------- HSS: a tree of LMS trees ----------

def hss_verify(public_key, message, signature):
    levels = struct.unpack(">I", public_key[:4])[0]
    key = public_key[4:]
    if len(signature) < 4 or struct.unpack(">I", signature[:4])[0] + 1 != levels:
        return False
    position = 4
    for _ in range(levels - 1):
        length = lms_signature_length(signature[position:])
        if length is None:
            return False
        sig = signature[position:position + length]
        next_key = signature[position + length:position + length + 24 + N]
        if not lms_verify(key, next_key, sig):  # the key above signed the key below
            return False
        key, position = next_key, position + length + 24 + N
    return lms_verify(key, message, signature[position:])


def hss_sign(keys, message, randomizers):
    """Sign with the lowest key, and let each key sign the public key of the one below it.
    keys[i] signs the leaf number keys[i].q, so the caller has set up the leaf numbers."""
    parts = [u32(len(keys) - 1)]
    for i in range(len(keys) - 1):
        parts += [keys[i].sign(keys[i + 1].public_key, randomizers[i], q=keys[i].q), keys[i + 1].public_key]
    parts.append(keys[-1].sign(message, randomizers[-1]))
    return b"".join(parts)


if __name__ == "__main__":
    # A small tree: 8 leaves, Winternitz width 4
    key = LmsKey(lms_type=5, ots_type=3, seed=bytes(range(32)), identifier=bytes(range(16)))
    message = b"The way to get started is to quit talking and begin doing."
    signature = key.sign(message)
    print("public key (%d bytes): %s" % (len(key.public_key), key.public_key.hex()))
    print("signature  (%d bytes): %s..." % (len(signature), signature[:48].hex()))
    print("leaf used:", struct.unpack(">I", signature[:4])[0], "| next leaf:", key.q)
    print("valid:    ", lms_verify(key.public_key, message, signature))
    print("altered:  ", lms_verify(key.public_key, message + b"!", signature))
    try:
        key.sign(message, q=0)
    except ValueError as error:
        print("leaf 0 again:", error)

Running it produces this output:

public key (56 bytes): 0000000500000003000102030405060708090a0b0c0d0e0fa0e11306c37bc1bbcccb535e4af6b0cd6211b96525158bddc4b2e6dc71ece9f8
signature  (2348 bytes): 00000000000000033f1299e8bc373f3e7cbfb86f141743d3b87e534ce533843318866dbc8a037067b99fa4c08b409622...
leaf used: 0 | next leaf: 1
valid:     True
altered:   False
leaf 0 again: this leaf is used up or does not exist

The second file implements XMSS with SHA-256, with the tree height as a parameter so that small trees are quick to build. The RFC names heights 10, 16, and 20.

# xmss.py
# XMSS (RFC 8391) with SHA-256: WOTS+, the L-trees, and the main hash tree.
# The parameter sets of the RFC are XMSS-SHA2_10_256, _16_256 and _20_256 (w = 16, n = 32).
# This code takes the tree height h as a parameter so that small trees can be built quickly.
# Teaching code. It is slow, and it keeps its state in memory.

import hashlib
import os
import struct

N, W, LEN1, LEN2 = 32, 16, 64, 3
LEN = LEN1 + LEN2  # 67 chains
OIDS = {10: 1, 16: 2, 20: 3}  # the object identifiers of XMSS-SHA2_10_256, _16_256, _20_256


def keyed(tag, key, data):
    """F, H, H_msg and PRF of the RFC: SHA-256 of the 32-byte tag, the key, and the data."""
    return hashlib.sha256(tag.to_bytes(N, "big") + key + data).digest()


def F(key, data):
    return keyed(0, key, data)


def H(key, data):
    return keyed(1, key, data)


def H_msg(key, data):
    return keyed(2, key, data)


def PRF(key, data):
    return keyed(3, key, data)


def xor(a, b):
    return bytes(x ^ y for x, y in zip(a, b))


# ---------- addresses: eight 32-bit words, 32 bytes ----------
# layer, tree (two words), type, then three words that depend on the type, and keyAndMask.

OTS, LTREE, HASH_TREE = 0, 1, 2
ADRS_TYPE, ADRS_A, ADRS_B, ADRS_C, ADRS_KM = 3, 4, 5, 6, 7  # positions of the words


def adrs_bytes(adrs):
    return struct.pack(">8I", *adrs)


def with_type(kind):
    adrs = [0] * 8
    adrs[ADRS_TYPE] = kind  # setting the type clears the words after it
    return adrs


# ---------- WOTS+ ----------

def base_w(data, count):
    digits = []
    for byte in data:
        digits += [byte >> 4, byte & 15]
    return digits[:count]


def digits_with_checksum(digest):
    digits = base_w(digest, LEN1)
    checksum = sum(W - 1 - d for d in digits)
    checksum <<= 4  # len2 * 4 = 12 bits are shifted to the top of two bytes
    return digits + base_w(checksum.to_bytes(2, "big"), LEN2)


def chain(x, start, steps, seed, adrs):
    for j in range(start, start + steps):
        adrs[ADRS_C] = j  # the hash address
        adrs[ADRS_KM] = 0
        key = PRF(seed, adrs_bytes(adrs))
        adrs[ADRS_KM] = 1
        mask = PRF(seed, adrs_bytes(adrs))
        x = F(key, xor(x, mask))
    return x


def wots_secret(secret_seed, index):
    """The 67 secret values of leaf `index` (the method of section 4.1.11 and 3.1.7)."""
    s_ots = PRF(secret_seed, index.to_bytes(32, "big"))
    return [PRF(s_ots, i.to_bytes(32, "big")) for i in range(LEN)]


def wots_public(sk, seed, adrs):
    pk = []
    for i in range(LEN):
        adrs[ADRS_B] = i  # the chain address
        pk.append(chain(sk[i], 0, W - 1, seed, adrs))
    return pk


def wots_sign(digest, sk, seed, adrs):
    sig = []
    for i, d in enumerate(digits_with_checksum(digest)):
        adrs[ADRS_B] = i
        sig.append(chain(sk[i], 0, d, seed, adrs))
    return sig


def wots_pk_from_sig(digest, sig, seed, adrs):
    pk = []
    for i, d in enumerate(digits_with_checksum(digest)):
        adrs[ADRS_B] = i
        pk.append(chain(sig[i], d, W - 1 - d, seed, adrs))
    return pk


# ---------- the trees ----------

def rand_hash(left, right, seed, adrs):
    adrs[ADRS_KM] = 0
    key = PRF(seed, adrs_bytes(adrs))
    adrs[ADRS_KM] = 1
    mask0 = PRF(seed, adrs_bytes(adrs))
    adrs[ADRS_KM] = 2
    mask1 = PRF(seed, adrs_bytes(adrs))
    return H(key, xor(left, mask0) + xor(right, mask1))


def ltree(pk, seed, adrs):
    """Compress the 67 values of a WOTS+ public key into one leaf of the tree."""
    pk, height = list(pk), 0
    while len(pk) > 1:
        adrs[ADRS_B] = height
        nxt = []
        for i in range(len(pk) // 2):
            adrs[ADRS_C] = i
            nxt.append(rand_hash(pk[2 * i], pk[2 * i + 1], seed, adrs))
        if len(pk) % 2:
            nxt.append(pk[-1])
        pk, height = nxt, height + 1
    return pk[0]


def leaf_node(secret_seed, seed, index):
    adrs = with_type(OTS)
    adrs[ADRS_A] = index
    pk = wots_public(wots_secret(secret_seed, index), seed, adrs)
    adrs = with_type(LTREE)
    adrs[ADRS_A] = index
    return ltree(pk, seed, adrs)


def hash_node(left, right, seed, height, index):
    """The parent at `index` of two nodes of the given height."""
    adrs = with_type(HASH_TREE)
    adrs[ADRS_B], adrs[ADRS_C] = height, index
    return rand_hash(left, right, seed, adrs)


class XmssKey:
    def __init__(self, h, secret_seed, sk_prf, seed):
        self.h, self.secret_seed, self.sk_prf, self.seed = h, secret_seed, sk_prf, seed
        self.idx = 0  # the next unused leaf: this is the state
        levels = [[leaf_node(secret_seed, seed, i) for i in range(2 ** h)]]
        for height in range(h):
            below = levels[-1]
            levels.append([hash_node(below[2 * i], below[2 * i + 1], seed, height, i) for i in range(len(below) // 2)])
        self.levels = levels
        self.root = levels[-1][0]

    @property
    def public_key(self):
        return (OIDS.get(self.h, 0)).to_bytes(4, "big") + self.root + self.seed

    def sign(self, message):
        if self.idx >= 2 ** self.h:
            raise ValueError("every leaf has been used")
        idx = self.idx
        self.idx += 1  # the state moves on before the signature is returned
        r = PRF(self.sk_prf, idx.to_bytes(32, "big"))
        digest = H_msg(r + self.root + idx.to_bytes(N, "big"), message)
        adrs = with_type(OTS)
        adrs[ADRS_A] = idx
        sig = wots_sign(digest, wots_secret(self.secret_seed, idx), self.seed, adrs)
        auth = [self.levels[j][(idx >> j) ^ 1] for j in range(self.h)]  # the siblings on the way to the root
        return idx.to_bytes(4, "big") + r + b"".join(sig) + b"".join(auth)


def new_key(h, randbytes=os.urandom):
    return XmssKey(h, randbytes(N), randbytes(N), randbytes(N))


def xmss_verify(public_key, message, signature, h):
    if len(public_key) != 4 + 2 * N or len(signature) != 4 + N + (LEN + h) * N:
        return False
    root, seed = public_key[4:4 + N], public_key[4 + N:]
    idx = int.from_bytes(signature[:4], "big")
    if idx >= 2 ** h:
        return False
    r = signature[4:4 + N]
    sig = [signature[4 + N + i * N:4 + N + (i + 1) * N] for i in range(LEN)]
    auth = [signature[4 + N + LEN * N + j * N:4 + N + LEN * N + (j + 1) * N] for j in range(h)]
    digest = H_msg(r + root + idx.to_bytes(N, "big"), message)
    adrs = with_type(OTS)
    adrs[ADRS_A] = idx
    pk = wots_pk_from_sig(digest, sig, seed, adrs)
    adrs = with_type(LTREE)
    adrs[ADRS_A] = idx
    node = ltree(pk, seed, adrs)
    for k in range(h):
        if (idx >> k) % 2 == 0:
            node = hash_node(node, auth[k], seed, k, idx >> (k + 1))
        else:
            node = hash_node(auth[k], node, seed, k, idx >> (k + 1))
    return node == root


if __name__ == "__main__":
    # A tree of height 3 (8 signatures) from fixed seeds
    key = XmssKey(3, bytes(range(32)), bytes(range(32, 64)), bytes(range(64, 96)))
    message = b"The way to get started is to quit talking and begin doing."
    signature = key.sign(message)
    print("public key (%d bytes): %s" % (len(key.public_key), key.public_key.hex()))
    print("signature  (%d bytes): %s..." % (len(signature), signature[:48].hex()))
    print("leaf used:", int.from_bytes(signature[:4], "big"), "| next leaf:", key.idx)
    print("valid:    ", xmss_verify(key.public_key, message, signature, 3))
    print("altered:  ", xmss_verify(key.public_key, message + b"!", signature, 3))

Running it produces this output:

public key (68 bytes): 0000000068180f2bf0d48e1d2526fb38534f38e07d875df329c04b296332cf5e62a02b1c404142434445464748494a4b4c4d4e4f505152535455565758595a5b5c5d5e5f
signature  (2276 bytes): 0000000011c3e8f92a6565812dad1b5e748d117a17f1f9f07336cf6c1eaa3a2b77071cb28b5f9135b285c4f342debc3e...
leaf used: 0 | next leaf: 1
valid:     True
altered:   False

I checked LMS against the official test vectors. Both test cases of Appendix F of RFC 8554 are read from the text of the RFC. Both verify, and a changed message, a changed public key, a wrong length, and 60 single-bit changes of each signature are all rejected. The second test case also gives the secret seeds and identifiers of its two trees. My code builds the top tree of 1,024 leaves and the second tree from them, and it reproduces the public key of the RFC. Signing with the leaf numbers and the randomizers from the RFC gives its 3860-byte signature byte for byte. The code also matches the tables of the RFC. The values p and ls equal the algorithm of Appendix B, and the signature lengths are the ones in Table 1. Random trees with all four values of w sign and verify. Used leaves and leaves beyond the tree are refused. The visualizer code has its own SHA-256, which matches OpenSSL for 306 input lengths, and it matches all 118 test vectors that this Python code produces, including both test cases of the RFC. I ran its page in a simulated browser.

For XMSS, the situation is different, and I want to say so plainly. RFC 8391 contains no test vectors. I checked my code in three ways. First, the signature sizes equal Table 3 of the RFC for the three required heights. Second, I wrote a second implementation that follows the pseudocode of the RFC literally, with the recursive chain, the stack of treeHash, and buildAuth through treeHash. It gives the same roots and the same authentication paths. Third, I read the source of the reference implementation of the XMSS authors and compared the layout of the hash inputs, the padding, the address fields, and the computation of the root. All of these agree with my code. I did not run the reference code. Signing and verifying work for every leaf of trees of heights 2, 3, and 4, and for four leaves of a full tree of 1,024 leaves with the identifier of XMSS-SHA2_10_256. Without an independent known answer, I cannot prove that my output matches other XMSS libraries byte for byte. The private key derivation is also my own choice from the RFC’s suggestions, and it differs from other libraries. A reader who needs certainty can compare with an independent implementation, such as the reference code of the XMSS authors. Because key derivation differs between libraries, the comparison needs one that accepts the secret seeds as input.

Where It Is Used

Firmware signing. NIST SP 800-208 says that stateful schemes are not suitable for general use, because they require careful state management. It names the authentication of firmware updates for constrained devices as the intended case. Such devices may stay in service for decades, and it may not be practical to change their signature verification code after deployment.
Hardware modules. The publication requires that key generation and signing be validated only inside hardware cryptographic modules with FIPS 140 Level 3 or higher. The module must not export private keying material, and it must store the incremented leaf index in nonvolatile storage before it releases a signature.
Verification anywhere. Verification needs no secret, so a verifier can be small and simple. The RFCs list compact implementations among the advantages of these schemes.

Limitations

This is a teaching implementation, not a production one:

No safe state. The code keeps the state in memory. A real signer must store the leaf index durably before it releases a signature, as SP 800-208 requires.
Slow. The code is plain Python. Building a tree of 1,024 leaves takes seconds, and larger trees would take minutes or hours. RFC 8554 reports times for key generation of 6 seconds for a tree of height 15 and 1.5 hours for height 25 with an optimized program.
Random numbers. The code accepts the seeds as given. Real keys need seeds from a secure random source.
One hash. Only SHA-256 with 32-byte outputs is implemented. The other hash functions of SP 800-208 are not.
No multi-tree XMSS. XMSS^MT is not implemented. HSS is implemented for verification and for signing with explicit state.
XMSS is unverified by vectors. The text above explains what was checked and what was not.
Large signatures. For a tree of height 5, a signature takes from 1,292 bytes (w = 8) to 8,684 bytes (w = 1), far more than the 64 bytes of an ECDSA signature.

Security Status

RFC 8554 states that LMS is provably secure in the random oracle model, as shown by Katz, and that further analysis by Fluhrer considers only the compression function of the hash as a random oracle. A corollary of that paper says that with no more than 2^64 randomly chosen LMS private keys, a signing oracle, and at most 2^120 compression computations, the probability of a single forgery is less than 2^-129. NIST SP 800-208 notes that LMS and XMSS both use randomized hashing, which makes it infeasible for anyone but the signer to find a collision between two messages.

Both CFRG documents state that the group is confident in the security of these schemes against quantum computers, given the current knowledge about quantum algorithms. They add the warning that the schemes are stateful, and that no security remains if a state is used twice. The only real risks are on the engineering side. Reusing a leaf, restoring a backup of the private key, and running two copies of the signer against the same key all lead to the forgery shown above.

FAQ

Why do these signatures survive quantum computers?

They use only a hash function. The attack of Shor breaks factoring and the discrete logarithm, but it does not help against hash functions. RFC 8554 says that hash-based signatures would still be secure even if an attacker could build a quantum computer, and RFC 8391 says that they can so far withstand known attacks using quantum computers. The CFRG documents add that this rests on the current state of knowledge about quantum algorithms.

What happens if I sign two messages with the same leaf?

The security of that leaf is gone. Anyone who sees the signatures learns the chain values at the lowest steps of the two digests. A signature on a third message becomes possible whenever its digits are at least as high as those minima. With two signatures, my search found nothing in 300,000 tries. With four, it found a forgery after about 30,000 tries. This is why the standards forbid any reuse.

Can I back up and restore the private key?

Restoring a backup brings back an old leaf number, and the signer then reuses leaves that it has already used. SP 800-208 requires that the leaf index be stored in nonvolatile storage before a signature is exported, and that the module not export private keying material, which rules out ordinary backups of the signing key.

Why use a tree and not one big one-time key?

A one-time key signs one message. The tree turns 2^h of them into one public key, which is the root. The authentication path in each signature proves that the leaf belongs to that root. HSS goes further and builds a tree of trees, so that the signer does not need to compute every leaf before publishing the public key.

Should I choose LMS or XMSS?

RFC 8554 says that HSS operations are about four times faster than XMSS with SHA-256, and that XMSS signatures are slightly shorter. XMSS rests on weaker assumptions about the hash function, because its security proof does not need collision resistance. Both are approved by NIST in SP 800-208. Pick the one that your library and your hardware module support, and check the parameter sets that are approved.

Why not use SPHINCS+ and avoid the state?

SPHINCS+ is stateless, so it cannot be broken by a repeated state. Its signatures are larger. A stateful scheme can make sense when you control the signer, when a hardware module protects the state, and when signature size matters. The SPHINCS+ guide explains the stateless design.

References

McGrew, David, Curcio, Michael, and Fluhrer, Scott. “Leighton-Micali Hash-Based Signatures.” RFC 8554, Internet Research Task Force, April 2019. Available at: https://www.rfc-editor.org/rfc/rfc8554
Hülsing, Andreas, Butin, Denis, Gazdag, Stefan-Lukas, Rijneveld, Joost, and Mohaisen, Aziz. “XMSS: eXtended Merkle Signature Scheme.” RFC 8391, Internet Research Task Force, May 2018. Available at: https://www.rfc-editor.org/rfc/rfc8391
Cooper, David, Apon, Daniel, Dang, Quynh, Davidson, Michael, Dworkin, Morris, and Miller, Carl. “Recommendation for Stateful Hash-Based Signature Schemes.” NIST Special Publication 800-208, October 2020. Available at: https://doi.org/10.6028/NIST.SP.800-208
Merkle, Ralph. “Secrecy, Authentication, and Public Key Systems.” Technical Report No. 1979-1, Information Systems Laboratory, Stanford University, 1979.
Buchmann, Johannes, Dahmen, Erik, and Hülsing, Andreas. “XMSS: A Practical Forward Secure Signature Scheme Based on Minimal Security Assumptions.” PQCrypto 2011, Lecture Notes in Computer Science 7071, 2011, pp. 117-129.
Leighton, Tom, and Micali, Silvio. “Large provably fast and secure digital signature schemes based on secure hash functions.” U.S. Patent 5,432,852, July 1995.

Interactive LMS and HSS Signatures Visualizer

🔐 LMS Signatures

XMSS and LMS Hash-Based Signatures

Introduction

Table of Contents

History and Standards

One-Time Signatures with Hash Chains

From One Key to Many: the Merkle Tree

HSS: a Tree of Trees

XMSS

LMS Compared with XMSS

The State Problem

Interactive Visualizer

A Worked Example

Python Implementation

Where It Is Used

Limitations

Security Status

FAQ

Why do these signatures survive quantum computers?

What happens if I sign two messages with the same leaf?

Can I back up and restore the private key?

Why use a tree and not one big one-time key?

Should I choose LMS or XMSS?

Why not use SPHINCS+ and avoid the state?

References