SPHINCS+ is a stateless hash-based signature scheme and a finalist in the NIST 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 demonstrated that the construction based on SHA-256 did not have DM-SPR at the necessary security level to prove the claimed NIST category five security of 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 which 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.
Proceedings of PQCrypto 2022: The Thirteenth International Conference on Post-Quantum Cryptography
September 28-30, 2022
This conference is online (It's hosted by Youtube which is owned by Google, so I'll just call this California), CA, US
, Cooper, D.
and Kelsey, J.
Breaking Category Five SPHINCS+ with SHA-256, Proceedings of PQCrypto 2022: The Thirteenth International Conference on Post-Quantum Cryptography, This conference is online (It's hosted by Youtube which is owned by Google, so I'll just call this California), CA, US, [online], https://doi.org/10.1007/978-3-031-17234-2_23, https://tsapps.nist.gov/publication/get_pdf.cfm?pub_id=935143
(Accessed November 29, 2023)