Abstract
Replay protection is especially important for one-time signatures (OTS) and few-time signatures (FTS) hash-based post-quantum signatures. The reason is not only that old signed messages can be replayed, but also that many OTS and FTS constructions reveal selected secret-derived values during signing [1]-[4]. This is safe only within the intended usage bound. If the same bounded-use key is used again on a different message, additional secret material may be exposed, making forgery feasible [3]-[7]. In stateful schemes such as LMS and XMSS, replay protection additionally requires preventing signer-state rollback [5]-[8]. In stateless schemes such as SPHINCS+ and SLH-DSA, rollback is avoided, but ordinary anti-replay protections and clear action scoping remain necessary [9]-[12].
1. Introduction
Digital signatures provide authenticity and integrity, but not freshness. A valid old signature can still be replayed unless the protocol rejects it using nonces, counters, timestamps, version numbers, or similar mechanisms.
This issue is sharper for one-time and few-time hash-based signatures. These schemes rely on bounded-use signing components, and in many of them a valid signature reveals part of the secret structure associated with the private key [1]-[4]. That controlled disclosure is acceptable once, or within a limited usage pattern, but reuse on another message may reveal additional information and weaken security [3]-[7]. Replay protection in these systems is therefore both a protocol problem and a key-usage problem.
In general, there are three distinct risks relevant to signature replay:
-
Protocol replay: an old valid signed message is accepted again. -
Context replay: a signature valid for one purpose is reused for another because the signed message did not bind enough context. -
State replay: a stateful signer reuses an old one-time leaf because of rollback, crash recovery, concurrency, or replication failure.
2. Replay in Classical Signature Schemes
Classical signatures provide a useful baseline. Schemes such as RSA, ECDSA, EdDSA, and Ed25519 are many-use schemes: reusing the same long-term signing key across many messages is normal and expected. Even so, they still require protocol-level replay protection. A valid old ECDSA or EdDSA signature can be replayed if the application does not enforce freshness with nonces, counters, timestamps, or similar mechanisms.
Classical schemes have their own misuse hazards. In ECDSA, for example, reusing the same ephemeral nonce to sign two different messages can reveal the private key. A key point is that in classical signatures, dangerous reuse usually concerns internal randomness rather than the long-term signing key itself.
3. Replay in Stateful and Stateless Hash-Based Signatures
Hash-based signatures are among the most established post-quantum signature families because they rely on conservative assumptions [4]-[12]. The main deployment distinction is between stateful and stateless designs.
This distinction is especially important for hash-based signatures because some constructions rely on one-time or few-time signing components. In these schemes, bounded-use signing material itself must not be reused, making replay and key-management failures more severe in this setting [1]-[7].
3.1 Replay in Stateful signature schemes
In stateful schemes such as LMS and XMSS, the signer must track which one-time leaf has already been used [5]-[8]. If state is rolled back after a crash, failover, backup restore, snapshot, or race condition, the same leaf may be used twice. Replay protection in these schemes therefore has two parts:
-
rejecting stale signed messages, and
-
preventing reuse of old signer state.
This matters because, in Lamport-style, Winternitz-style, and related hash-based signatures, signing may reveal selected private values, pre-images, or hash-chain positions [1]-[4]. A second signature under the same bounded-use key can reveal a different subset. An attacker who sees both may be able to combine them to sign unauthorized messages [3]-[7].
This is why the standards are strict about reuse. RFC 8391 states that if an XMSS secret-key state is used twice, no cryptographic security guarantees remain. RFC 8554 states that an LMS private-key value used to sign one message must not be used to sign another. NIST SP 800-208 similarly emphasizes that reuse of the same OTS key on different messages can make forgery feasible [5]-[8].
3.2 Replay in Stateless signature schemes
Stateless schemes such as SPHINCS+ and SLH-DSA were designed to remove this state-management hazard [9]-[12]. They avoid explicit signer-state tracking and therefore do not suffer from the same rollback problem that dominates LMS and XMSS deployments. However, they do not solve protocol or context replay. A stale signed command remains valid unless the application rejects it through its own freshness and context checks.
4. Action Scoping and Privilege Separation
Action scoping and privilege separation matter beyond freshness alone. If the same bounded-use signing capacity can authorize different types of actions, reuse becomes more dangerous. A key or leaf exercised for a low-risk action should not later be reusable for a higher-privilege action. Otherwise, key reuse can become a path to privilege escalation. Recent work on smart contracts also shows that replay vulnerabilities can lead to repeated or unintended authorization in practice [13], [14].
For that reason, the signed message should bind not only freshness data, but also:
-
the action type,
-
the privilege level or signer role,
-
the protocol or application context,
-
the intended target or device,
-
the relevant version, epoch, or session identifier.
5. Practical Requirements
To reduce replay risk in hash-based signature deployments, a secure deployment should therefore:
-
include nonces, counters, timestamps, epochs, or version numbers as appropriate;
-
bind signatures to context and action type;
-
enforce least privilege across different workflows;
-
prevent rollback and duplicate leaf use in stateful schemes;
-
treat backups, failover, replication, and snapshots as part of the cryptographic trust model.
6. Conclusion
Replay protection is especially important for one-time and few-time hash-based post-quantum signatures because misuse can do more than authorize a stale action. It can also expose additional secret-derived material or cause reuse of bounded-use signing state [3]-[8]. In LMS and XMSS, this makes state continuity a core security requirement [5]-[8]. In SPHINCS+ and SLH-DSA, rollback is avoided, but freshness, context binding, and action scoping remain necessary [9]-[12]. The correct model is therefore not just signature verification, but signature verification combined with anti-replay controls and safe key-use management.
References
[1] R. C. Merkle, Secrecy, Authentication, and Public Key Systems. PhD thesis, Stanford University, 1979. https://www.merkle.com/papers/Thesis1979.pdf
[2] L. Reyzin and N. Reyzin, “Better than BiBa: Short One-Time Signatures with Fast Signing and Verifying,” in Information Security and Privacy: 7th Australasian Conference, ACISP 2002, 2002. https://link.springer.com/chapter/10.1007/3-540-45450-0_22
[3] A. Hulsing, “W-OTS+: Shorter Signatures for Hash-Based Signature Schemes,” in Progress in Cryptology - AFRICACRYPT 2013, 2013. https://link.springer.com/chapter/10.1007/978-3-642-38553-7_11
[4] J. Buchmann, E. Dahmen, and A. Hulsing, “XMSS: A Practical Forward Secure Signature Scheme Based on Minimal Security Assumptions,” in Post-Quantum Cryptography: 4th International Workshop, PQCrypto 2011, 2011. https://link.springer.com/chapter/10.1007/978-3-642-25405-5_7
[5] A. Huelsing, D. Butin, S.-L. Gazdag, J. Rijneveld, and A. Mohaisen, RFC 8391: XMSS: eXtended Merkle Signature Scheme. RFC Editor, May 2018. https://www.rfc-editor.org/rfc/rfc8391
[6] D. McGrew, M. Curcio, and S. Fluhrer, RFC 8554: Leighton-Micali Hash-Based Signatures. RFC Editor, April 2019. https://www.rfc-editor.org/rfc/rfc8554
[7] D. A. Cooper, D. Apon, Q. Dang, M. Davidson, M. Dworkin, and C. Miller, Recommendation for Stateful Hash-Based Signature Schemes. NIST Special Publication 800-208, October 2020. https://doi.org/10.6028/NIST.SP.800-208
[8] P. Kampanakis and S. Fluhrer, “LMS vs XMSS: Comparison of Two Hash-Based Signature Standards,” IACR ePrint 2017/349, 2017. https://eprint.iacr.org/2017/349
[9] D. J. Bernstein, D. Hopwood, A. Hulsing, T. Lange, R. Niederhagen, L. Papachristodoulou, M. Schneider, P. Schwabe, and Z. Wilcox-O’Hearn, “SPHINCS: Practical Stateless Hash-Based Signatures,” in Advances in Cryptology - EUROCRYPT 2015, 2015. https://sphincs.cr.yp.to/sphincs-20150202.pdf
[10] D. J. Bernstein, A. Hulsing, S. Kolbl, R. Niederhagen, J. Rijneveld, and P. Schwabe, “The SPHINCS+ Signature Framework,” in Proceedings of the 2019 ACM SIGSAC Conference on Computer and Communications Security, 2019. https://sphincs.org/resources.html
[11] SPHINCS+ Team, SPHINCS+ Submission to the 3rd Round of the NIST Post-Quantum Cryptography Project, 2020. https://sphincs.org/resources.html
[12] National Institute of Standards and Technology, FIPS 205: Stateless Hash-Based Digital Signature Standard (SLH-DSA), August 13, 2024. https://csrc.nist.gov/pubs/fips/205/final
[13] Replay Attacks on Ethereum Smart Contracts. Presentation at DEF CON 26, 2018. https://doi.org/10.5446/39766
[14] Z. Wang, J. Chen, Z. Lin, W. Chen, K. Ning, J. Yu, Y. Feng, Y. Zhang, W. Zhang, and Z. Zheng, “One Signature, Multiple Payments: Demystifying and Detecting Signature Replay Vulnerabilities in Smart Contracts,” in Proceedings of the 2026 IEEE/ACM 48th International Conference on Software Engineering (ICSE 2026), 2026. https://arxiv.org/abs/2511.09134