Faulting Winternitz One-Time Signatures to forge LMS, XMSS, or SPHINCS+ signatures

Alexander Wagner; Vera Wesselkamp; Felix Oberhansl; Marc Schink; Emanuele Strieder

Paper 2023/1572

Faulting Winternitz One-Time Signatures to forge LMS, XMSS, or SPHINCS+ signatures

Alexander Wagner

, Fraunhofer Institute for Applied and Integrated Security, Technical University of Munich

Vera Wesselkamp

, Technical University of Munich

Felix Oberhansl

, Fraunhofer Institute for Applied and Integrated Security

Marc Schink, Fraunhofer Institute for Applied and Integrated Security, Technical University of Munich

Emanuele Strieder

, Fraunhofer Institute for Applied and Integrated Security, Technical University of Munich

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 injection post-quantum cryptography hash-based signatures winternitz one-time signatures LMS XMSS SPHINCS+
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},
      note = {\url{https://eprint.iacr.org/2023/1572}},
      url = {https://eprint.iacr.org/2023/1572}
}