Skip to main content
U.S. flag

An official website of the United States government

Official websites use .gov
A .gov website belongs to an official government organization in the United States.

Secure .gov websites use HTTPS
A lock ( ) or https:// means you’ve safely connected to the .gov website. Share sensitive information only on official, secure websites.

Breaking Category Five SPHINCS+ with SHA-256

Published

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

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 May 24, 2024)

Issues

If you have any questions about this publication or are having problems accessing it, please contact reflib@nist.gov.

Created September 28, 2022, Updated December 18, 2022