SPHINCS+#
SPHINCS+ is a “stateless hash-based signature scheme” based on the SPHINCS signature scheme [BHH+14]. Andreas Hülsing has a blog post that goes over the changes made to SPHINCS.
The latest version of the specification document at the time of writing can be found here. Other resources are listed in the Resources section of the SPHINCS+ website.
SPHINCS+ is a stateless hash-based signature scheme, which means that is doesn’t require the user to save a state, unlike stateful schemes like XMSS [BDH11]. The disadvantage of stateful schemes is that reusing one-time key pairs may be catastrophic [GBH18].
The specification provides the following overview: “At a high level, SPHINCS+ works like SPHINCS. The basic idea is to authenticate a huge number of few-time signature (FTS) key pairs using a so-called hypertree. FTS schemes are signature schemes that allow a key pair to produce a small number of signatures, e.g., in the order of ten for our parameter sets. For each new message, a (pseudo)random FTS key pair is chosen to sign the message. The signature consists then of the FTS signature and the authentication information for that FTS key pair. The authentication information is roughly a hypertree signature, i.e. a signature using a certification tree of Merkle tree signatures.”.
Parameters#
There are three different signature schemes, depending on the hash function used to instantiate the SPHINCS+ construction:
SPHINCS+-SHAKE256
SPHINCS+-SHA-256
SPHINCS+-Haraka
Haraka is a cryptographic hash function that aims to be efficient on short inputs [KLMR16]. While Haraka is not a hash function approved by the NIST, the authors included this scheme to showcase the performance of SPHINCS+ instantiated with a dedicated short-input hash function.
Each of these schemes was split into two variants during the second round of submission: a simple and a robust variant. The robust variant is the one introduced in the first round submission, while the simple variant “introduces instantiations of the tweakable hash functions similar to those of the LMS proposal [[MCF19]] for stateful hash-based signatures”.
Parameter |
Description |
|---|---|
\(n\) |
The security parameter in bytes. |
\(w\) |
The Winternitz parameter. |
\(h\) |
The height of the hypertree. |
\(d\) |
The number of layers in the hypertree. |
\(k\) |
The number of trees in FORS. |
\(t\) |
The number of leaves of a FORS tree. |
Parameter set |
\(n\) |
\(h\) |
\(d\) |
\(log(t)\) |
\(k\) |
\(w\) |
Bit security |
NIST security level |
|---|---|---|---|---|---|---|---|---|
SPHINCS+-128s |
16 |
63 |
7 |
12 |
14 |
16 |
133 |
1 |
SPHINCS+-128f |
16 |
66 |
22 |
6 |
33 |
16 |
128 |
1 |
SPHINCS+-192s |
24 |
63 |
7 |
14 |
17 |
16 |
193 |
3 |
SPHINCS+-192f |
24 |
66 |
22 |
8 |
33 |
16 |
194 |
3 |
SPHINCS+-256s |
32 |
64 |
8 |
14 |
22 |
16 |
255 |
5 |
SPHINCS+-256f |
32 |
68 |
17 |
9 |
35 |
16 |
255 |
5 |
Parameter set |
Public key |
Private key |
Signature |
|---|---|---|---|
SPHINCS+-128s |
32 |
64 |
7856 |
SPHINCS+-128f |
32 |
64 |
17088 |
SPHINCS+-192s |
48 |
96 |
16224 |
SPHINCS+-192f |
48 |
96 |
35664 |
SPHINCS+-256s |
64 |
128 |
29792 |
SPHINCS+-256f |
64 |
128 |
49856 |
Implementations#
The reference implementation can be found on GitHub: sphincs/sphincsplus. It has the three main schemes, as well as optimized implementations:
SPHINCS+-SHA256 with AVX2.
SPHINCS+-SHAKE256 with AVX2.
SPHINCS+-Haraka with AES-NI.
And include an aarch64 implementation of SPHINCS+-SHAKE256.
The Software page of the website lists some third-party implementations such as:
An integration in the Botan C++ library.
An hybrid variant, combining SPHINCS+ with the LMS scheme.
An integration in Bouncy Castle.
Some integrations not listed there are:
Benchmarks#
While there are no benchmarks on the website, an extensive one is included in the specification, in Section 10, Table 4.
Benchmarks are also available in the SUPERCOP benchmarking framework.
Considering the number of variants, no benchmarks are proposed here.
Attacks#
Some attacks have been published:
Breaking Category Five SPHINCS+ with SHA-256 [PKC22], which gives “a complete forgery attack that reduces the concrete classical security of these parameter sets by approximately 40 bits of security”.
Practical Fault Injection Attacks on SPHINCS [GKPM18], an attack that “allows the creation of a universal signature forgery that applies to all current standardisation candidates (XMSS, LMS, SPHINCS+, and Gravity-SPHINCS)”.
Grafting Trees: a Fault Attack against the SPHINCS framework [CMP18], in which the authors propose “the first fault attack against the framework underlying SPHINCS, Gravity-SPHINCS and SPHINCS+”.
On Protecting SPHINCS+ Against Fault Attacks [Gen23], in which the author “adapts the original attack to SPHINCS+ reinforced with randomized signing and extends the applicability of the attack to any combination of faulty and valid signatures”.
Bibliography#
Daniel J. Bernstein, Daira Hopwood, Andreas Hülsing, Tanja Lange, Ruben Niederhagen, Louiza Papachristodoulou, Michael Schneider, Peter Schwabe, and Zooko Wilcox-O'Hearn. Sphincs: practical stateless hash-based signatures. Cryptology ePrint Archive, Paper 2014/795, 2014. https://eprint.iacr.org/2014/795. URL: https://eprint.iacr.org/2014/795.
Johannes Buchmann, Erik Dahmen, and Andreas Hülsing. Xmss - a practical forward secure signature scheme based on minimal security assumptions. Cryptology ePrint Archive, Paper 2011/484, 2011. https://eprint.iacr.org/2011/484. URL: https://eprint.iacr.org/2011/484.
Laurent Castelnovi, Ange Martinelli, and Thomas Prest. Grafting trees: a fault attack against the sphincs framework. Cryptology ePrint Archive, Paper 2018/102, 2018. https://eprint.iacr.org/2018/102. URL: https://eprint.iacr.org/2018/102.
Aymeric Genêt. On protecting sphincs+ against fault attacks. Cryptology ePrint Archive, Paper 2023/042, 2023. https://eprint.iacr.org/2023/042. URL: https://eprint.iacr.org/2023/042.
Aymeric Genêt, Matthias J. Kannwischer, Hervé Pelletier, and Andrew McLauchlan. Practical fault injection attacks on sphincs. Cryptology ePrint Archive, Paper 2018/674, 2018. https://eprint.iacr.org/2018/674. URL: https://eprint.iacr.org/2018/674.
L. Groot Bruinderink and A.T. Hülsing. “oops, i did it again” – security of one-time signatures under two-message attacks. In Carlisle Adams and Jan Camenisch, editors, Selected Areas in Cryptography – SAC 2017, Lecture Notes in Computer Science, 299–322. Germany, 2018. Springer. 24th International Conference on Selected Areas in Cryptography (SAC 2017), SAC 2017 ; Conference date: 16-08-2017 Through 18-08-2017. doi:10.1007/978-3-319-72565-9_15.
Stefan Kölbl, Martin M. Lauridsen, Florian Mendel, and Christian Rechberger. Haraka v2 - efficient short-input hashing for post-quantum applications. Cryptology ePrint Archive, Paper 2016/098, 2016. https://eprint.iacr.org/2016/098. URL: https://eprint.iacr.org/2016/098.
David McGrew, Michael Curcio, and Scott Fluhrer. Leighton-Micali Hash-Based Signatures. Request for Comments RFC 8554, Internet Engineering Task Force, April 2019. Num Pages: 61. URL: https://datatracker.ietf.org/doc/draft-mcgrew-hash-sigs-15 (visited on 2023-07-20), doi:10.17487/RFC8554.
Ray Perlner, John Kelsey, and David Cooper. Breaking category five sphincs+ with sha-256. Cryptology ePrint Archive, Paper 2022/1061, 2022. https://eprint.iacr.org/2022/1061. URL: https://eprint.iacr.org/2022/1061.