SLH-DSA non-standard chain lengths

[conduition]

Hi NIST PQC community,

I'm working on a protocol which will be using SLH-DSA with a bespoke parameter set targeting a signature budget of 2^40 (the 2^24 budget from NIST SP 800-230 is too small). We are still assessing different options for parameter sets, but we notice the performance/compactness gap between w=16 and w=256 param sets is very wide.

- w=16 uses hash chains of length 16, which are very fast to sign and verify, but require many chains, thus lead to larger signatures.

- w=256 uses hash chains of length 256, which are very slow to sign/verify but produce much smaller signatures.

We started to consider using parameter sets with w=32 or w=64 to bridge this gap, but upon closer inspection of FIPS-205 I believe this would not work with existing algorithms.

The first incompatibility is encountered when encoding a message as chain indexes in base `w` (e.g. page 20, algorithm 7 (`wots_sign`), line 2). In compliant implementations this would fail because `log2(w)` doesn't evenly divide `8n`, so the `base_2^b` (algorithm 1) function expects a longer message (n+1 bytes for w=32 or w=64), and will either throw a validation error or panic/abort because of an out-of-bounds access at Algorithm 1 Line 6. 

On the implementation side, this is easy to fix. Either:

1. modify Algorithms 7 and 8 to append a couple of zero-bytes at the end of message M before encoding to base w. Two bytes would be sufficient to support up to w=2^20. Or 

2. modify `base_2^b` (algorithm 1) to assume zero bits if available input is exhausted.

These modifications would not affect parameter sets with w = 2^(2^x) (i.e. 2, 4, 16, 256, 65536, ...). The extra bytes appended by option (1) would not be read at all, while the conditional branch introduced by option (2) would never be triggered. They should also not affect security because (1) is constant time and (2) branches only based on constant inputs.

I have not finished surveying FIPS-205 so I may have missed other incompatibilities. However, to my eye this presently seems like the only issue preventing use of w=32/64/128 parameter sets with FIPS-205 compliant code.

Is there any appetite in NIST to rectify this issue in the spec? 

I'm not suggesting to add any new parameter sets - only to tweak the algorithms so that compliant implementations will be drop-in compatible with `w` parameters which are not 2^(2^x). This would benefit bespoke use-cases like mine, and would permit new parameter sets to be standardized later if desired.

regards,

conduition

[dustin...@nist.gov]

> Is there any appetite in NIST to rectify this issue in the spec?

We don't plan to revise FIPS 205 at this time.  You may be interested in a draft Special Publication that we recently put out for public comment:

SP 800-230, Additional SLH-DSA Parameter Sets for Limited Signature Use Cases

https://csrc.nist.gov/pubs/sp/800/230/ipd

This Special Publication serves as a technical extension of FIPS 205, the specification for the Stateless Hash-based Digital Signature Algorithm (SLHsig). While standard SLHsig parameter sets are designed to maintain full security for up to 2^64 signatures, the resulting signature sizes and/or verification times are undesirable or prohibitive for certain applications. To address these performance constraints, this document specifies six additional SLHsig parameter sets for security levels 1, 3, and 5. These new variants are specifically tailored for use cases that require fast verification and reduced signature sizes, such as the signing of software, firmware, and digital certificates. These optimizations are achieved by establishing a strict limit of 2^24 signatures per signing key. Because of this operational limit, these parameter sets are not approved for general-purpose use, and users must perform a thorough evaluation to ensure that the signature limit is never exceeded during any signing key's lifetime.

Dustin Moody

NIST

[conduition]

Thanks Dustin, SP800-230 is not an option for my use-case, as I noted in my original email. Unfortunate that a small revision is not an option, but I understand not wanting to rock the boat at this point. Thankfully either of the changes I suggested can be made downstream on the implementation side, without affecting compatibility with the upstream FIPS-205 standard.

regards,

conduition