Public comments on SP 800-230: Additional SLH-DSA Parameter Sets for Limited Signature Use Cases
Stern, Morgan B
We would like to thank the team at NIST for their work on this draft publication. As ML-DSA and stateful hash-based signatures are contained in CNSA, we do not have a use case for SLH-DSA. Even with the smaller parameter sets, the signature size is still larger than algorithms already available in CNSA 2.0. Further, the proposed parameter sets carry risk involving state.
Our main concerns revolve around the enforcement of the signature limit.
* The current parameters lead to the algorithm precisely hitting the security target. That means that any overuse will immediately lead to a security degradation. Perhaps a cushion could be built into the parameters to allow for some accidental misuse.
* We ask that more specifics regarding use cases be included in this document. This could include citing cases where this parameter set should not be used because users would not be able to guarantee adherence to the signing limit based purely on heuristics.
* The rate limiting of signatures could help prevent a key from being used too many times. Alternatively, the speed of signing could be used to inform the lifetime of the key. Assuming it takes at least a minute to generate a signature, one could generate signatures for 30 years straight and stay under the 2^24 limit.
* Multiple devices sharing a signing key adds to the risk of key overuse. Tracking key use over multiple devices could be even more complicated than tracking state management in LMS/XMSS. Perhaps adopt weaker forms of restrictions from SP 800-208; for example, require use in physical modules, and/or disallow key export except in order to securely back up.
* We view the slower (relative to FIPS 205) signing time as a benefit to the security of the newly proposed parameter set for the reasons above. As such, the final paragraph in Section 3 which suggests caching values in order to speed up signature time seems misguided and should be removed.
Morgan Stern
NSA Cybersecurity
Chris Fenner
Hi Morgan,
Thanks for the detailed comments on the proposed parameter sets for firmware/certificate signing.
A few of your suggestions seem to be suggesting improvements to the wording of SP 800-230 itself, which I'll leave to NIST to respond to/incorporate. For what it's worth, they seem like reasonable suggestions to me. I'd like to address a few general technical points (i.e., not related to the wording of the SP) from your message in more detail.
Given that CNSA 2.0 approves all parameters of LMS/XMSS for all classification levels, with SHA-256/192 recommended, I'd like to make the following concrete proposal: Please (re)consider adding just SLH-DSA-SHA2/SHAKE-192-24 to CNSA 2.0. I believe this would be justifiable on a similar basis as the allowance for SHA-256/192 for LMS/XMSS: The security of SLH-DSA, LMS, and XMSS alike rely only on the security of the hash function, not e.g., module lattice problems (in addition to the security of the hash function). As detailed below, there are also significant performance benefits as compared to ML-DSA.
As you point out in your message, 2^24 was chosen as a "rate-limiter-friendly" amount of signatures: a 1 signature per minute rate limiter (fine for firmware signing) would allow continuous signing with one key to maintain full security strength for 31.9 years.
> Even with the smaller parameter sets, the signature size is still larger than algorithms already available in CNSA 2.0.
For SLH-DSA-SHA2/SHAKE-192-24 the signature+public key is 7800 bytes, 8% larger than ML-DSA-87 at 7219 bytes.
SLH-DSA-SHA2-192-24 should take around 600K clock cycles ([1]) for verification, around 26x faster than ML-DSA-87, which requires around 16M clock cycles for verification ([2]). This is of special note for things like PCI devices, which need to come online for link training within 100ms.
Code size is a little harder to estimate, but given that SLH-DSA verification just requires hashing in some loops, it should be significantly smaller than ML-DSA (which requires hashing in loops plus NTT and matrix operations)
This is why in certain environments (e.g., ROM implementation of a signature verification over first-stage mutable firmware) SLH-DSA is currently used - making CNSA 2.0 compliance impossible for such types of devices.
> the proposed parameter sets carry risk involving state.
LMS and XMSS, already allowed by CNSA 2.0, carry much more significant risk (catastrophic key leakage) involving state. It is a bit surprising to see this risk called out for SLH-DSA when it is considered mitigable for LMS and XMSS.
> Multiple devices sharing a signing key adds to the risk of key overuse. Tracking key use over multiple devices could be even more complicated than tracking state management in LMS/XMSS.
Given the key use limitations can be expressed as a rate limit, this seems not too complex, especially compared to the equivalent system required (if even allowed?) for LMS/XMSS (i.e., some kind of mutex-protected counter shared among all instances, or sectorization which complicates adding/removing signers to/from the pool).
> The current parameters lead to the algorithm precisely hitting the security target. That means that any overuse will immediately lead to a security degradation. Perhaps a cushion could be built into the parameters to allow for some accidental misuse.
The parameter sets chosen by NIST from among the proposed parameter sets ([3]) were chosen partly based on their having such a cushion. According to my calculations [4], SLH-DSA-*-192-24 maintains:
[in green below] 128 bits of security at 2^31.75 signatures (signing every second for 114 years)
[in yellow below] 112 bits of security at 2^33.5 signatures (signing every second for 385 years)
[in red below] 80 bits of security at 2^37 signatures (signing every second for 4,355 years)
While this topic of overuse safety did not get mentioned in the SP 800-230 draft itself, it came up repeatedly and at length during the discussions that led to SP 800-230 ([5]):
Overuse safety was introduced and discussed in detail in the initial paper NIST published ([6]) when they opened the request for feedback.
Folks in the community expressed initial skepticism about the criticality of overuse safety within the context of a firmware signing infrastructure, but NIST made the case for it staying in the conversation as different parameter sets were discussed and compared.
The very long sign times of the *-24 parameter sets also provide a natural deterrent against overuse. At 1M short hashes/sec, a "typical HSM" (per the NIST paper) will take around 21-24 minutes to sign an SLH-DSA-*-24 signature. This means that 20 "typical HSMs" in parallel could not exceed a 1 sig/min rate limit even if they tried.
The overuse safety of SLH-DSA (all parameter sets) compares very favorably to the catastrophic breakage of "overuse" for LMS/XMSS due to the gradual falloff of security level vs leaking the key more or less directly if a leaf OTS key is reused.
[1] Back-of-the-napkin estimate for SLH-DSA-*-192-24 verification clock cycles based on the number of short hashes required (508) and the number of clock cycles required for one hash of an SLH-DSA verify operation, around 1200 if we divide the total clock cycles required for SLH-DSA-SHA2-128s (2712044 according to [7]) by the number of hashes it requires (2214)
[2] https://arxiv.org/html/2603.19340v5
[3] https://groups.google.com/a/list.nist.gov/g/pqc-forum/c/vtMTuE_3u-0/m/ZRjih8F9DAAJ
[4] I recently fixed a floating-point precision issue in my toolset that was causing overuse resilience to be slightly underestimated for a few -192-24 and -256-24 parameter sets: https://github.com/chrisfenner/slh-dsa-rls
[5] https://groups.google.com/a/list.nist.gov/g/pqc-forum/c/vtMTuE_3u-0/m/LzPijzC9AQAJ
[6] https://eprint.iacr.org/archive/2024/018/1737032157.pdf
[7] https://sphincs.org/data/sphincs+-r3.1-specification.pdf