Breaking Category Five SPHINCS+ with SHA-256

Note: A preparatory talk "Basics of MD Hashes and Hash-Based Signatures" (by John Kelsey) was given immediately prior to this one, in the same crypto reading club meeting (2022-Oct-19).

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. In this talk we describe a forgery attack that reduces the classical security of certain parameter sets of SPHINCS+ by about 40 bits of security, in particular this affects the parameter sets which attempt to provide 256 bits of classical security using the hash function SHA-256. To lead up to this result we will provide background on the design of SPHINCS+, as well as the properties of SHA-256 that arise from its use of the Merkle-Damgård construction. The discussion of the Merkle-Damgård construction will include previous related results such as the “herding” attack of Kelsey and Kohno, and a recent observation by Sydney Antonov on the PQC mailing list that was a direct precursor to our attack.

Based on joint work, with David Cooper and John Kelsey, appearing at PQCrypto 2022

Suggested reading: ia.cr/2022/1061