Signing Twice Is Forever: State-Management Discipline for Stateful Hash-Based Signatures Under Operational Faults
This paper evaluates state-management disciplines for stateful hash-based signatures (XMSS and LMS) under operational faults, demonstrating that only transactional claim strategies prevent catastrophic key reuse while revealing that snapshot rollback protection requires external monotonic anchors and that batched leasing offers the only safe, low-latency solution for LMS despite significant performance penalties in unpatched software libraries.
Original paper licensed under CC BY 4.0 (https://creativecommons.org/licenses/by/4.0/). This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer
In the digital world, some secrets are so valuable that they cannot be allowed to be used more than once. Imagine a master key that opens a single door; once that door is opened, the key must be destroyed. If the key is used a second time, even by accident, the entire security system collapses, and anyone watching can forge their own keys to open any door they choose. This is the reality for a specific type of digital signature called a stateful hash-based signature. These are the tools governments and security experts are turning to as they prepare for a future where powerful quantum computers might break today's most common encryption methods. Unlike other digital signatures that rely on complex mathematical puzzles, these signatures depend on the simple, unbreakable nature of a hash function, a process that turns data into a unique fingerprint. Their only weakness is not a flaw in the math, but a flaw in how they are managed: if the system forgets which door it just opened and tries to use the same key again, the security is gone forever.
The challenge lies in keeping track of this single-use key across a network of computers that might crash, restart, or be restored from backups. A new study by independent researcher Arpan Sharma investigates exactly how to manage this tracking without making mistakes. The research focuses on two approved methods, XMSS and LMS, which are now being mandated for signing critical software and firmware. The study asks a practical question: when a computer system fails or is restarted, which software rules prevent the system from accidentally reusing a key? To find the answer, the researchers built a simulated signing service that mimics a real-world environment where computers share a database. They then subjected this system to a series of harsh tests, including killing computer processes abruptly, running multiple copies of the system at the same time, and rolling the system back to an old backup snapshot, just as a real administrator might do during a recovery.
The results revealed that the most common way of handling these keys is dangerously flawed. Many systems use a simple approach where they read the current key number, sign a message, and then write the new number back to the database. This seems logical, but the study showed that if a computer crashes in the tiny split second between signing and saving, or if two computers try to sign at the same time, the system can easily lose track and reuse a key. In these tests, this common method led to the reuse of dozens, and sometimes hundreds, of keys in a single run. The researchers found that the only way to guarantee safety against crashes and concurrency is to use a "claim-first" discipline. In this method, the system must officially reserve the next key number in the database before it is ever used to sign anything. This ensures that even if the computer crashes immediately after the reservation, the key is marked as used, and the system will never try to use it again.
However, safety comes with a cost, and the study uncovered a surprising difference between the two signature methods. For one method, XMSS, the safe way of managing keys was almost free in terms of speed, adding virtually no delay to the signing process. For the other method, LMS, the situation was much more complicated. On the version of the software library used in the study, the safe method was so slow that it was practically unusable. Every time the system tried to sign a message after a restart, it had to rebuild a massive digital tree structure from scratch, taking hundreds of milliseconds for a single action. The researchers reported this issue to the software developers, who added a fix in a newer version of the library. This fix allowed the system to save a piece of the tree structure so it didn't have to rebuild it every time. While this made the safe method much faster, it did not make it fast enough to be practical for high-volume use.
The study concluded that for the LMS method, the only way to be both safe and fast is to use a "batched leasing" approach. Instead of reserving one key at a time, the system reserves a block of sixteen keys at once. It then uses those keys in memory for a while before asking for another block. This spreads the cost of the expensive tree rebuilding over many signatures, making the process fast enough for real-world use while remaining safe. The research also highlighted a fundamental limit that no software trick can overcome: if a system is rolled back to an old backup, any method that stores the key counter inside that backup will fail. The backup will contain an old key number, and the system will start reusing keys that were already used in the time between the backup and the crash. To prevent this, the researchers found that the counter must be kept in a separate, external device that cannot be rolled back, such as a specialized hardware security module. This confirms that for these specific signatures, the hardware requirement is not just a suggestion but a structural necessity.
The findings offer a clear roadmap for engineers building the next generation of secure software. They show that relying on standard database patterns is not enough and that specific, disciplined rules must be followed to avoid catastrophic security failures. For one signature type, the solution is simple and cheap. For the other, it requires a specific strategy of reserving keys in batches and, crucially, keeping the master counter outside the main database to protect against the inevitable failures of backups and snapshots. As the world moves toward quantum-resistant security, these operational details will determine whether the new systems remain secure or crumble under their own weight.
Drowning in papers in your field?
Get daily digests of the most novel papers matching your research keywords — with technical summaries, in your language.