Breaking Category Five SPHINCS+ with SHA-256

Published

September 28, 2022

Author(s)

Ray Perlner, David Cooper, John M. Kelsey

Abstract

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 Title

Proceedings of PQCrypto 2022: The Thirteenth International Conference on Post-Quantum Cryptography

Volume

13512

Conference Dates

September 28-30, 2022

Conference Location

This conference is online (It's hosted by Youtube which is owned by Google, so I'll just call this California), CA, US

Conference Title

PQCrypto 2022

Pub Type

Conferences

Download Paper

https://doi.org/10.1007/978-3-031-17234-2_23

Local Download

Keywords

Hash-based signatures, Post-Quantum Cryptography, SPHINCS+

Citation

Perlner, R. , Cooper, D. and Kelsey, J. (2022), 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 December 6, 2024)