Paper 2022/1061
Breaking Category Five SPHINCS+ with SHA-256
, National Institute of Standards and Technology, National Institute of Standards and Technology, KU LeuvenAbstract
SPHINCS$^+$ is a stateless hash-based signature scheme that has been selected for standardization as part of the NIST post-quantum cryptography (PQC) standardization process. Its security proof relies on the distinct-function multi-target second-preimage resistance (DM-SPR) of the underlying keyed hash function. The SPHINCS$^+$ submission offered several instantiations of this keyed hash function, including one based on SHA-256. A recent observation by Sydney Antonov on the PQC mailing list demonstrated that the construction based on SHA-256 did not have DM-SPR at NIST category five, for several of the parameter sets submitted to NIST; however, it remained an open question whether this observation leads to a forgery attack. We answer this question in the affirmative by giving a complete forgery attack that reduces the concrete classical security of these parameter sets by approximately 40 bits of security. Our attack works by applying Antonov's technique to the {WOTS$^+$} public keys in {\SPHINCS}, leading to a new one-time key that can sign a very limited set of hash values. From that key, we construct a slightly altered version of the original hypertree with which we can sign arbitrary messages, yielding signatures that appear valid.
Metadata
- Available format(s)
-
PDF
- Category
- Attacks and cryptanalysis
- Publication info
- Published elsewhere. PQCrypto 2022
- Keywords
- hash-based signatures post-quantum cryptography SPHINCS+
- Contact author(s)
-
ray perlner @ nist gov
john kelsey @ nist gov
david cooper @ nist gov - History
- 2022-08-17: approved
- 2022-08-15: received
- See all versions
- Short URL
- https://ia.cr/2022/1061
- License
-
CC0
BibTeX
@misc{cryptoeprint:2022/1061,
author = {Ray Perlner and John Kelsey and David Cooper},
title = {Breaking Category Five SPHINCS+ with SHA-256},
howpublished = {Cryptology ePrint Archive, Paper 2022/1061},
year = {2022},
note = {\url{https://eprint.iacr.org/2022/1061}},
url = {https://eprint.iacr.org/2022/1061}
}
