Ray Perlner, National Institute of Standards and Technology
John Kelsey, National Institute of Standards and Technology, KU Leuven
David Cooper, National Institute of Standards and Technology
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.
@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},
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.