Breaking Category Five SPHINCS+ with SHA-256

Abstract

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.

Available format(s)
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
See all versions
Short URL
https://ia.cr/2022/1061

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}
}

Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.