Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Define API for Stateless Hash-Based Digital Signature (SLH-DSA aka SPHINCS+) #97

Open
athoelke opened this issue Aug 31, 2023 · 8 comments · May be fixed by #223 or #216
Open

Define API for Stateless Hash-Based Digital Signature (SLH-DSA aka SPHINCS+) #97

athoelke opened this issue Aug 31, 2023 · 8 comments · May be fixed by #223 or #216
Labels
Crypto API Issue or PR related to the Cryptography API enhancement New feature or request

Comments

@athoelke
Copy link
Contributor

athoelke commented Aug 31, 2023

Updated 13-09-2024: The final version of the specification is now published https://csrc.nist.gov/pubs/fips/205/final.

NIST has now published a draft specification for a Digital Signature algorithm based on SPHINCS+. The algorithm is designated SLH-DSA, and will be published as FIPS 205. The draft (open for review until 22 Nov 2023) can be downloaded from https://csrc.nist.gov/pubs/fips/205/ipd.

NIST is planning to standardize 12 parameterized variants of SLH-DSA, based on three independent parameters:

  • Two hash function families: SHA2 or SHAKE
  • Three security strengths: 128, 192, and 256 bits
  • Two modes: [relatively] small signature ('s'), and [relatively] fast signature ('f')

The qualified names are SLH-DSA-<hash-family>-<strength><mode>, for example SLH-DSA-SHAKE-128s. Table 1 in the draft describes the details of the variants.

The signature algorithm is recommended to use fresh randomness, to mitigate side-channel attacks; but can also operate deterministically when the implementation does not have access to randomness, by substituting a pre-generated value from the private key in place of the random value.

As SLH-DSA makes two passes of the message for the signature algorithm, FIPS 205 also explicitly describes a pre-hash variation of SLH-DSA where the hash of the message is signed/verified, instead of the message itself.

The Crypto API should define an API for using this algorithm.

@athoelke athoelke added enhancement New feature or request Crypto API Issue or PR related to the Cryptography API labels Aug 31, 2023
@athoelke
Copy link
Contributor Author

API Design

Unlike stateful hash-based signatures that are based on similar underlying techniques (such as XMSS), SLH-DSA does not require mutable state within the secret key to track which sub-keys have been used for generating signatures. As a result, SLH-DSA should fit reasonably well within the existing asymmetric signature API.

The key sizes depend only on the security strength, but the generation of a key pair depends on the mode and hash family parameters for the algorithms that the key will be used with. Although the 'bit size' of the key is a natural fit for specifying the security strength parameter, the additional variations could be specified in a similar manner to ECC 'families'.

As a result, the key type encodes all of the parameter variation. Then, a single algorithm identifier suffices for randomized signing and verification. It is not necessary to encode the hash family in the algorithm, as this is implicit in the key type. To enable deterministic signatures, an additional algorithm can be defined, in a similar manner to ECDSA signature algorithms.

SLH-DSA is not a sign-the-hash algorithm (as defined in PSA_ALG_IS_HASH_AND_SIGN()), but does permit applications to sign a message digest when the use case cannot supply the entire message to the signature algorithm. This suggests that we do not provide psa_sign_hash() for SLH-DSA, as FIPS 205 recommends calling psa_sign_message() with the message digest in this use case; which is distinct from the behavior of sign-the-hash algorithms, or from the pre-hash variations of the EdDSA algorithms.

@athoelke
Copy link
Contributor Author

Last month, the approved versions of the new NIST PQ crypto standards was announced. That document includes a description of the comments and changes since the draft last summer.

The final specification for SLH-DSA is at https://csrc.nist.gov/pubs/fips/205/final.

Most details of the scheme are unchanged, the main change since the draft that affects the API design is that the pre-hash and pure variants of the scheme are now domain-separated via the input to the hash computation of the message representative. There are now separate External functions defined for pre-ash signature and verification.

@athoelke
Copy link
Contributor Author

The observations on ML-DSA (FIPS 204) about pure/prehash and hedged/deterministic signatures also apply here. We will probably need four algorithm definitions for SLH-DSA.

Similarly, the context parameter would require a new signature API - although as it is optional with a default of 'empty string', an initial API proposal that did not provide a means to set this parameter would be reasonable (see also the related comment on ML-DSA).

@athoelke
Copy link
Contributor Author

Given that:

  1. All of the SLH-DSA-specific parameterization is necessarily included in the key attributes (see my earlier design thoughts), as it is in ML-DSA, and,
  2. Both schemes have the same usage of an optional context,

Then, it would be technically possible for SLH-DSA and ML-DSA to share the same set of four algorithm identifier values.

I am not sure that this is the right approach here? However, we do use this type of pattern for ARC4/ChaCha/XChaCha with PSA_ALG_STREAM_CIPHER, and for all of the block-cipher mode algorithms.

@athoelke
Copy link
Contributor Author

Key attribute design details

For SLH-DSA keys we need to allocate a new Asymmetric key type, so that we can define a family for each of the SLH-DSA-SHA2-nnns, SLH-DSA-SHA2-nnnf, SLH-DSA-SHAKE-nnns, SLH-DSA-SHAKE-nnnf groups of SLH-DSA parameters.

With the new asymmetric key encoding (see #196 and the updated documentation), I suggest an ASYM-TYPE of 0x03, and the following family values:

SLH-DSA key family SLH-FAMILY P Identifier public key key-pair
SHA2-nnns 0x00 1 PSA_SLH_DSA_FAMILY_SHA2_S 0x4181 0x7181
SHA2-nnnf 0x01 0 PSA_SLH_DSA_FAMILY_SHA2_F 0x4182 0x7182
SHAKE-nnns 0x04 0 PSA_SLH_DSA_FAMILY_SHAKE_S 0x4188 0x7188
SHAKE-nnns 0x05 1 PSA_SLH_DSA_FAMILY_SHAKE_F 0x418b 0x718b

The key bits for an SLH-DSA key could be the bit-size of the key seeds (128. 192 and 256), matching the standard names for the algorithms; or could be the actual bit size of the private key/key-pair, which is four times larger (512, 768, 1024). Is there a preference for one of the bit size representations?

@athoelke
Copy link
Contributor Author

The key bits for an SLH-DSA key could be the bit-size of the key seeds (128. 192 and 256), matching the standard names for the algorithms; or could be the actual bit size of the private key/key-pair, which is four times larger (512, 768, 1024). Is there a preference for one of the bit size representations?

The current thinking is that using 128/192/256 is a more 'natural' fit for the SLH-DSA-XXX-128z, SLH-DSA-XXX-192z, SLH-DSA-XXX-256z algorithm names.

@athoelke
Copy link
Contributor Author

Then, it would be technically possible for SLH-DSA and ML-DSA to share the same set of four algorithm identifier values.

Although possible, this does not seem particularly helpful, and does not simplify either applications or documentation. So the plan is to have separate algorithm identifiers for SLH-DSA and ML-DSA.

For the algorithms, the Pure variants internally use the FIPS 205-specified hash functions for processing the message. Similar to PSA_ALG_PURE_EDDSA, we should have the algorithm identifier encode 0x00 in the HASH bits.

For the Prehash variants, the hash algorithm for the message is chosen by the application. FIPS 205 says this must be an approved hash, and should have a security strength appropriate to the strength of the chosen SLH-DSA parameter set. So the prehash algorithm identifiers should be parameterized by a hash algorithm. For comparison, the existing PSA_ALG_ED25519PH specifies exactly one hash (SHA-256), which is encoded in the algorithm identifier.

This is necessary when using the prehash algorithm for both psa_sign_message() - when the hashing is done by the implementation - and for psa_sign_hash() - when the implementation needs to encode the OID of the hash algorithm into the signature process.

@athoelke
Copy link
Contributor Author

SLH-DSA would benefit from the definition of SHAKE128-256 (the truncated-to-256-bits output of SHAK128) as a hash algorithm. This is already proposed in the ML Keys PR #210

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
Crypto API Issue or PR related to the Cryptography API enhancement New feature or request
Projects
1 participant