SLHDSA¶
Stateless Hash-Based Digital Signature Algorithm (SLH-DSA) is a digital signature scheme based on SPHINCS+ and standardized by NIST as FIPS 205. It is one of the three signature schemes selected at the end of the third round of the NIST PQC competition.
As the name implies, it is based on hash functions. More precisely, it relies on the preimage resistance and related properties, not on the collision resistance.
Note
As with the other selected candidates, SLH-DSA introduces some changes to the round 3 version of SPHINCS+, meaning that they are not compatible.
Overview¶
SLH-DSA is based on 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¶
Parameter |
Description |
---|---|
\(n\) |
The security parameter is the length in bytes of the messages that may be signed with WOTS+, as well as the length of the private key, public key and signature elements. |
\(h\) |
The height of the XMSS hypertree. |
\(d\) |
The number of layers of XMSS trees. |
\(h'\) |
The height of a XMSS tree. |
\(a\) |
The value such that \(2^a\) is the number of byte strings in a single set of a FORS private key. |
\(k\) |
The number of Merkle trees in FORS, conforming the private key. |
\(lg_w\) |
The number of bits that are encoded with each WOTS+ hash chain used. |
Note that the values are valid for both SHA-2 and SHAKE variants. For example, SLH-DSA-128s applies to both SLH-DSA-SHA2-128s and SLH-DSA-SHAKE-128s.
Parameter set |
\(n\) |
\(h\) |
\(d\) |
\(h'\) |
\(a\) |
\(k\) |
\(lg_w\) |
\(m\) |
security category |
---|---|---|---|---|---|---|---|---|---|
SLH-DSA-128s |
16 |
63 |
7 |
9 |
12 |
14 |
4 |
30 |
1 |
SLH-DSA-128f |
16 |
66 |
22 |
3 |
6 |
33 |
4 |
34 |
1 |
SLH-DSA-192s |
24 |
63 |
7 |
9 |
14 |
17 |
4 |
39 |
3 |
SLH-DSA-192f |
24 |
66 |
22 |
3 |
8 |
33 |
4 |
42 |
3 |
SLH-DSA-256s |
32 |
64 |
8 |
8 |
14 |
22 |
4 |
47 |
5 |
SLH-DSA-256f |
32 |
68 |
17 |
4 |
9 |
35 |
4 |
49 |
5 |
Parameter set |
Public key |
Private key |
Signature |
---|---|---|---|
SLH-DSA-128s |
32 |
64 |
7856 |
SLH-DSA-128f |
32 |
64 |
17088 |
SLH-DSA-192s |
48 |
96 |
16224 |
SLH-DSA-192f |
48 |
96 |
35664 |
SLH-DSA-256s |
64 |
128 |
29792 |
SLH-DSA-256f |
64 |
128 |
49856 |
Implementations¶
The reference implementation can be found on GitHub:
sphincs/sphincsplus. Work for updating
the reference implementation to match the FIPS 205 standard can be found in the
consistent-basew
branch.
It has optimized implementations for the previous version, including an AVX2 version of SPHINCS+-SHA256 and 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.
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.