Paper 2023/1572
Faulting Winternitz One-Time Signatures to forge LMS, XMSS, or SPHINCS+ signatures
Abstract
Hash-based signature (HBS) schemes are an efficient method of guaranteeing the authenticity of data in a post-quantum world. The stateful schemes LMS and XMSS and the stateless scheme SPHINCS+ are already standardised or will be in the near future. The Winternitz one-time signature (WOTS) scheme is one of the fundamental building blocks used in all these HBS standardisation proposals. We present a new fault injection attack targeting WOTS that allows an adversary to forge signatures for arbitrary messages. The attack affects both the signing and verification processes of all current stateful and stateless schemes. Our attack renders the checksum calculation within WOTS useless. A successful fault injection allows at least an existential forgery attack and, in more advanced settings, a universal forgery attack. While checksum computation is clearly a critical point in WOTS, and thus in any of the relevant HBS schemes, its resilience against a fault attack has never been considered. To fill this gap, we theoretically explain the attack, estimate its practicability, and derive the brute-force complexity to achieve signature forgery for a variety of parameter sets. We analyse the reference implementations of LMS, XMSS and SPHINCS+ and pinpoint the vulnerable points. To harden these implementations, we propose countermeasures and evaluate their effectiveness and efficiency. Our work shows that exposed devices running signature generation or verification with any of these three schemes must have countermeasures in place.
Note: Video https://www.youtube.com/watch?v=WctgTcQhtxA Slides https://pqcrypto2023.umiacs.io/slides/7.4.pdf
Metadata
- Available format(s)
-
PDF
- Category
- Attacks and cryptanalysis
- Publication info
- Published elsewhere. PQCrypto 2023
- DOI
- 10.1007/978-3-031-40003-2_24
- Keywords
- fault injectionpost-quantum cryptographyhash-based signatureswinternitz one-time signaturesLMSXMSSSPHINCS+
- Contact author(s)
-
alexander wagner @ aisec fraunhofer de
vera wesselkamp @ tum de
felix oberhansl @ aisec fraunhofer de
marc schink @ aisec fraunhofer de
emanuele strieder @ aisec fraunhofer de - History
- 2023-10-13: approved
- 2023-10-11: received
- See all versions
- Short URL
- https://ia.cr/2023/1572
- License
-
CC BY
BibTeX
@misc{cryptoeprint:2023/1572,
author = {Alexander Wagner and Vera Wesselkamp and Felix Oberhansl and Marc Schink and Emanuele Strieder},
title = {Faulting Winternitz One-Time Signatures to forge {LMS}, {XMSS}, or {SPHINCS}+ signatures},
howpublished = {Cryptology {ePrint} Archive, Paper 2023/1572},
year = {2023},
doi = {10.1007/978-3-031-40003-2_24},
url = {https://eprint.iacr.org/2023/1572}
}