Hello,
I would like to contribute an implementation of SLH-DSA to Nettle. The implementation is based off of the reference sphincs+ implementation and leancrypto slh-dsa implementation. Included tests contain test vectors from leancrypto slh-dsa tests. Could you please review the attached patch and give me your feedback?
Kind regards, Zoltan
Zoltan Fridrich zfridric@redhat.com writes:
I would like to contribute an implementation of SLH-DSA to Nettle. The implementation is based off of the reference sphincs+ implementation and leancrypto slh-dsa implementation. Included tests contain test vectors from leancrypto slh-dsa tests.
Thanks! I've now read the spec https://nvlpubs.nist.gov/nistpubs/FIPS/NIST.FIPS.205.pdf, and it looks like there are lots of parts, all rather simple.
Unfortunately there are a couple of variations (besides the rather important parameter tradeoffs for security, speed, signature size), though:
* Signatures can be randomized or deterministic. * Signatures can be "pure" or prehash. * One can use either shake or sha2. * Some of the sha2 variants use "compressed" addresses, I don't quite understand what's the point of that additional complication.
How do these variants relate to your usecase (mainly tls?), and others'? Is there one variant that is of primary importance, which should be the first one implemented?
For the api, I think it should be possble to support "pure" signatures without requiring all of the message in memory at once, using a init/update/final-style interface for sign and verify, based on the update function of the underlying hash. Is that worth while?
It also looks like it should also be possible to generate (easy) and verify (more complex) signatures incrementally, which might be useful on very memory constrained devices, or for systems handling lots of signatures in parallel (since signatures can be somewhat large). Probably not important in the first iteration.
I haven't yet looked closely at the code, but I have some initial questions:
Does the implementation aim to be side channel silent? (According to the spec, implementations should be side channel silent *both* for signature creation and verification; in Nettle, I don't think there's any signature verify code that promises side channel silence).
Is the implementation optimized for speed? I see some potential high-level optimizations of the algorithms as described in the spec, like producing merkle root hashes, and maybe auth paths too, based on sequential processing of the leaves, rather than recursion. As well as potential microoptimizations.
Regards, /Niels
Zoltan Fridrich zfridric@redhat.com writes:
Could you please review the attached patch and give me your feedback?
I've now had a first read, with one round of comments, see below. I'm tempted to try to write a minimal implementation of just SLH-DSA-SHAKE-128s from the spec, to get a better understanding.
Regards, /Niels
--- a/slh-dsa.c 1970-01-01 01:00:00.000000000 +0100 +++ b/slh-dsa.c 2024-12-02 17:00:07.386340199 +0100
+/* Generates SLH-DSA key pair
- Format sk: [SK_SEED || SK_PRF || PUB_SEED || root]
- Format pk: [root || PUB_SEED]
- */
Why different order for the public key? I would have expected PUB_SEED followed by the root (as in figure 16 in the spec, and same order as in the secret key). Does the NIST spec or some other standard clearly specify the serialization of the keys as byte strings?
For the Nettle api, I would also consider to not include the pubkey as part of the secret key, but instead pass both pubkey and secret key to the secret key functions. Similar to, e.g., ed25519_sha512_sign.
+void +slh_dsa_generate_keypair(enum slh_dsa_mode mode,
uint8_t *pk, uint8_t *sk,void *random_ctx,nettle_random_func *random)+{
- struct slh_dsa_params p = _nettle_slh_dsa_params_get(mode);
- uint8_t seed[3 * p.n];
- random(random_ctx, sizeof(seed), seed);
- slh_dsa_generate_keypair_from_seed(mode, seed, pk, sk);
+}
+void +slh_dsa_sign(enum slh_dsa_mode mode, const uint8_t *sk,
void *random_ctx, nettle_random_func *random,size_t message_size, const uint8_t *message,uint8_t *signature)+{
I think I would prefer separate top-level functions for the different algorithm variants, rather than the enum slh_dsa_mode. They could all call the same internal function, passing the appropriate params struct as argument.
- struct slh_dsa_params p = _nettle_slh_dsa_params_get(mode);
- slh_dsa_ctx ctx;
- const uint8_t *sk_prf = sk + p.n;
- const uint8_t *pk = sk + 2 * p.n;
- uint8_t root[p.n];
- uint8_t optrand[p.n];
- uint8_t mhash[p.fors_msg_bytes];
I don't think variable size arrays are quite portable. You would need to either use the TMP_ALLOC macros, or if you do separate top-level functions, each can allocated the needed constant amount of storage.
- uint32_t wots_addr[8] = {0};
- uint32_t tree_addr[8] = {0};
- uint32_t i, idx_leaf;
- uint64_t tree;
- memcpy(ctx.sk_seed, sk, p.n);
- memcpy(ctx.pub_seed, pk, p.n);
- _nettle_set_type(&p, wots_addr, SLH_DSA_ADDR_TYPE_WOTS);
- _nettle_set_type(&p, tree_addr, SLH_DSA_ADDR_TYPE_HASHTREE);
- /* Optionally, signing can be made non-deterministic using optrand.
This can help counter side-channel attacks that would benefit fromgetting a large number of traces when the signer uses the same nodes. */- if (random_ctx && random)
- random(random_ctx, sizeof(optrand), optrand);
- else
- memcpy(optrand, pk, sizeof(optrand));
So this function supports borth random and deterministic signatures. Minor detail: I think it should be just if (random), it's fine for some randomness generators to use NULL random_ctx (e.g., for an application where random state is global).
- /* Compute the digest randomization value. */
- p.gen_message_random(&p, signature, sk_prf, optrand, message, message_size);
- /* Derive the message digest and leaf index from R, PK and M. */
- p.hash_message(&p, mhash, &tree, &idx_leaf, signature, pk, message, message_size);
- signature += p.n;
- _nettle_set_tree_addr(&p, wots_addr, tree);
- _nettle_set_keypair_addr(&p, wots_addr, idx_leaf);
- /* Sign the message hash using FORS. */
- _nettle_fors_sign(&p, signature, root, mhash, &ctx, wots_addr);
- signature += p.fors_bytes;
- for (i = 0; i < p.d; i++)
- {
_nettle_set_layer_addr(&p, tree_addr, i);_nettle_set_tree_addr(&p, tree_addr, tree);_nettle_copy_subtree_addr(&p, wots_addr, tree_addr);_nettle_set_keypair_addr(&p, wots_addr, idx_leaf);
One possible microoptimization, when we make lots of hashes with a common prefix, could be to copy the underlying hash context (e.g., sha3_256_ctx for shake256) after calling <hash>_update on that prefix. But maybe doens't matter much if prefix is small compared to the hash function's block size.
diff --color -ruNp a/slh-dsa-context.h b/slh-dsa-context.h --- a/slh-dsa-context.h 1970-01-01 01:00:00.000000000 +0100 +++ b/slh-dsa-context.h 2024-12-02 15:41:43.292643667 +0100
+typedef struct
- {
- uint8_t pub_seed[32];
- uint8_t sk_seed[32];
- } slh_dsa_ctx;
It could make some sense to collect all the internal declarations into a single slh-dsa-internal.h.
diff --color -ruNp a/slh-dsa-fors.c b/slh-dsa-fors.c --- a/slh-dsa-fors.c 1970-01-01 01:00:00.000000000 +0100 +++ b/slh-dsa-fors.c 2024-12-02 16:59:07.186076254 +0100
+void +_nettle_fors_pk_from_sig(const struct slh_dsa_params *p,
uint8_t *pk, const uint8_t *sig,const uint8_t *m, const slh_dsa_ctx* ctx,const uint32_t fors_addr[8])+{
- uint32_t indices[p->fors_trees];
- uint8_t roots[p->fors_trees * p->n];
- /* Hash horizontally across all tree roots to derive the public key. */
- p->thash(p, pk, roots, p->fors_trees, ctx, fors_pk_addr);
If we could call the underlying hash function's update method for each root as it is computed, we wouldn't need to allocate any array of roots.
diff --color -ruNp a/slh-dsa.h b/slh-dsa.h --- a/slh-dsa.h 1970-01-01 01:00:00.000000000 +0100 +++ b/slh-dsa.h 2024-12-02 15:34:51.201341870 +0100
+void +slh_dsa_generate_keypair_from_seed(enum slh_dsa_mode mode,
const uint8_t *seed,uint8_t *pk, uint8_t *sk);+void +slh_dsa_generate_keypair(enum slh_dsa_mode mode,
uint8_t *pk, uint8_t *sk,void *random_ctx, nettle_random_func *random);
Not sure how to best think about the keypair and key generation. The secret key (or rather, the secret part of the secret key), SK.seed and SK.prf, are arbitrary random byte strings of the right size, analogous to ed25519. So we don't strictly need any function for generating a valid secret, just using the random byte generator is fine. We do need a function to derive the public key from such a secret, but then the public key includes it's own randomization, which is unusual.
diff --color -ruNp a/slh-dsa-hash.c b/slh-dsa-hash.c --- a/slh-dsa-hash.c 1970-01-01 01:00:00.000000000 +0100 +++ b/slh-dsa-hash.c 2024-12-02 16:53:03.160423482 +0100
+/* Computes the message-dependent randomness R,
- using a secret seed and an optional
- randomization value as well as the message.
- */
+void +_nettle_gen_message_random_shake(const struct slh_dsa_params *p,
uint8_t *R, const uint8_t *sk_prf,const uint8_t *optrand,const uint8_t *m,unsigned long long mlen)
Should be size_t, not unsigned long long. And nettle convention on argument order is to have length followed by the pointer.
Also, these functions should either be static, or have slh somewhere in the names.
diff --color -ruNp a/slh-dsa-params.c b/slh-dsa-params.c --- a/slh-dsa-params.c 1970-01-01 01:00:00.000000000 +0100 +++ b/slh-dsa-params.c 2024-12-02 16:58:28.762269523 +0100
+struct slh_dsa_params +_nettle_slh_dsa_params_get(enum slh_dsa_mode mode) +{
- struct slh_dsa_params p;
I think it is better to define one static const struct for each variant (a bit similar to struct ecc_curve).
diff --color -ruNp a/slh-dsa-params.h b/slh-dsa-params.h --- a/slh-dsa-params.h 1970-01-01 01:00:00.000000000 +0100 +++ b/slh-dsa-params.h 2024-12-02 16:51:06.559969811 +0100
+struct slh_dsa_params
- {
- unsigned n; /* Hash output length in bytes */
- unsigned full_height; /* Height of the hypertree */
- unsigned d; /* Number of subtree layer */
- /* FORS tree dimensions */
- unsigned fors_height;
- unsigned fors_trees;
- unsigned wots_w; /* Winternitz parameter */
- unsigned addr_bytes;
- /* WOTS parameters */
- unsigned wots_logw;
- unsigned wots_len1;
- unsigned wots_len2;
- unsigned wots_len;
- unsigned wots_bytes;
- unsigned wots_pk_bytes;
- unsigned tree_height; /* Subtree size */
- /* FORS parameters */
- unsigned fors_msg_bytes;
- unsigned fors_bytes;
- unsigned fors_pk_bytes;
- /* Resulting SLH-DSA sizes */
- unsigned bytes;
- unsigned pk_bytes;
- unsigned sk_bytes;
- /* Offsets of various fields in the address structure */
- unsigned offset_layer; /* The byte used to specify the Merkle tree layer */
- unsigned offset_tree; /* The start of the 8 byte field used to specify the tree */
- unsigned offset_type; /* The byte used to specify the hash type (reason) */
- unsigned offset_kp_addr; /* The start of the 4 byte field used to specify the key pair address */
- unsigned offset_chain_addr; /* The byte used to specify the chain address (which Winternitz chain) */
- unsigned offset_hash_addr; /* The byte used to specify the hash address (where in the Winternitz chain) */
- unsigned offset_tree_hgt; /* The byte used to specify the height of this node in the FORS or Merkle tree */
- unsigned offset_tree_index; /* The start of the 4 byte field used to specify
the node in the FORS or Merkle tree */
It's unfortunate that we have the "compressed" addresses, that seems to add complexity, and unclear for what gain.
- /* Hash specific functions */
- void (*thash)(const struct slh_dsa_params *,
uint8_t *, const uint8_t *,uint32_t, const slh_dsa_ctx *,uint32_t[8]);- void (*prf_addr)(const struct slh_dsa_params *,
uint8_t *, const slh_dsa_ctx *,const uint32_t[8]);- void (*gen_message_random)(const struct slh_dsa_params *,
uint8_t *, const uint8_t *,const uint8_t *,const uint8_t *,unsigned long long);- void (*hash_message)(const struct slh_dsa_params *,
uint8_t *, uint64_t *,uint32_t *, const uint8_t *,const uint8_t *, const uint8_t *,unsigned long long);
Would make sense with typedefs for these function types.
diff --color -ruNp a/slh-dsa-thash.c b/slh-dsa-thash.c --- a/slh-dsa-thash.c 1970-01-01 01:00:00.000000000 +0100 +++ b/slh-dsa-thash.c 2024-12-02 16:43:52.812842310 +0100
+/* Takes an array of inblocks concatenated arrays of N bytes.
- */
+void +_nettle_thash_shake(const struct slh_dsa_params *p,
uint8_t *out, const uint8_t *in,uint32_t inblocks, const slh_dsa_ctx *ctx,uint32_t addr[8])+{
- uint8_t buf[p->n + p->addr_bytes + inblocks * p->n];
- struct sha3_256_ctx hash_ctx;
- memcpy(buf, ctx->pub_seed, p->n);
- memcpy(buf + p->n, addr, p->addr_bytes);
- memcpy(buf + p->n + p->addr_bytes, in, inblocks * p->n);
There's no need for allocation and memcpy, just call sha3_256_update multiple times.
- sha3_256_init(&hash_ctx);
- sha3_256_update(&hash_ctx, sizeof(buf), buf);
- sha3_256_shake(&hash_ctx, p->n, out);
+}
diff --color -ruNp a/slh-dsa-utils.c b/slh-dsa-utils.c --- a/slh-dsa-utils.c 1970-01-01 01:00:00.000000000 +0100 +++ b/slh-dsa-utils.c 2024-12-02 16:59:18.728318592 +0100
+void +_nettle_u32_to_bytes(uint8_t *out, uint32_t in) +{
- out[0] = (uint8_t)(in >> 24);
- out[1] = (uint8_t)(in >> 16);
- out[2] = (uint8_t)(in >> 8);
- out[3] = (uint8_t)in;
+}
This is same as Nettle's WRITE_UINT32. Somewhat related, it looked like the algorithm descriptions in the spec had some unneeded conversions, e.g., converting certain digest bytes to an integer, and then only writing that integer back into an ADDR. Instead of directly copying the relevant bytes.
+/* Computes a root node given a leaf and an auth path.
- Expects address to be complete other than
- the tree_height and tree_index.
- */
+void +_nettle_compute_root(const struct slh_dsa_params *p,
uint8_t *root, const uint8_t *leaf,uint32_t leaf_idx, uint32_t idx_offset,const uint8_t *auth_path,uint32_t tree_height, const slh_dsa_ctx *ctx,uint32_t addr[8])+{
- uint32_t i;
- uint8_t buffer[2 * p->n];
- /* If leaf_idx is odd (last bit = 1),
- current path element is a right child
- and auth_path has to go left.
- Otherwise it is the other way around. */
- if (leaf_idx & 1)
- {
memcpy(buffer + p->n, leaf, p->n);memcpy(buffer, auth_path, p->n);- }
- else
- {
memcpy(buffer, leaf, p->n);memcpy(buffer + p->n, auth_path, p->n);- }
- auth_path += p->n;
I think all memcpy calls in this function could be eliminated.
+/* For a given leaf index, computes the authentication path
- and the resulting root node using Merkle's TreeHash algorithm.
- Expects the layer and tree parts of the tree_addr to be set,
- as well as the tree type (i.e. ADDR_TYPE_HASHTREE or ADDR_TYPE_FORSTREE).
- Applies the offset idx_offset to indices before building addresses,
- so that it is possible to continue counting indices across trees.
- */
+void +_nettle_treehash(const struct slh_dsa_params *p,
uint8_t *root, uint8_t *auth_path,const slh_dsa_ctx* ctx, uint32_t leaf_idx,uint32_t idx_offset, uint32_t tree_height,void (*gen_leaf)(uint8_t* /* leaf */,const slh_dsa_ctx* /* ctx */,uint32_t /* addr_idx */,const uint32_t[8] /* tree_addr */),uint32_t tree_addr[8])+{
I haven't read this in detail, but it was something like this I expected when I wrote about processing all leafs sequentially, rather than recursing. I like that. It also looks like it should be side-channel silent, i.e., no branches or memory addresses depending on the secret key?
diff --color -ruNp a/slh-dsa-utilsx1.c b/slh-dsa-utilsx1.c --- a/slh-dsa-utilsx1.c 1970-01-01 01:00:00.000000000 +0100 +++ b/slh-dsa-utilsx1.c 2024-12-02 16:41:37.290990469 +0100
+/* Generate the entire Merkle tree, computing the authentication path for
- leaf_idx, and the resulting root node using Merkle's TreeHash algorithm.
- Expects the layer and tree parts of the tree_addr to be set, as well as the
- tree type (i.e. SPX_ADDR_TYPE_HASHTREE or SPX_ADDR_TYPE_FORSTREE)
- This expects tree_addr to be initialized to the addr structures for the
- Merkle tree nodes
- Applies the offset idx_offset to indices before building addresses, so that
- it is possible to continue counting indices across trees.
- This works by using the standard Merkle tree building algorithm,
- */
+void +_nettle_treehashx1(const struct slh_dsa_params *p,
uint8_t *root, uint8_t *auth_path,const slh_dsa_ctx* ctx, uint32_t leaf_idx,uint32_t idx_offset, uint32_t tree_height,void (*gen_leaf)(const struct slh_dsa_params *,uint8_t* /* Where to write the leaves */,const slh_dsa_ctx* /* ctx */,uint32_t idx, void *info),uint32_t tree_addr[8], void *info)+{
It's unclear how this differs from _nettle_treehash further above? Or in general, whats the meaning of "x1" suffix on some functions?
diff --color -ruNp a/slh-dsa-wots.c b/slh-dsa-wots.c --- a/slh-dsa-wots.c 1970-01-01 01:00:00.000000000 +0100 +++ b/slh-dsa-wots.c 2024-12-02 16:59:28.665527230 +0100
+/* base_w algorithm as described in draft.
- Interprets an array of bytes as integers in base w.
- This only works when log_w is a divisor of 8.
- */
If log_w is always 4, no need to have a more general conversion. (And maybe we don't even need an explicit conversion, of we can extract the right nibbles on the fly). I think the checksum, as well as other parts of wots could be simplifyed quite a lot for this special case.
--- a/slh-dsa-wotsx1.c 1970-01-01 01:00:00.000000000 +0100 +++ b/slh-dsa-wotsx1.c 2024-12-02 16:59:44.395857500 +0100
+/* This generates a WOTS public key
- It also generates the WOTS signature if leaf_info
- indicates that we're signing with this WOTS key
- */
+void +_nettle_wots_gen_leafx1(const struct slh_dsa_params *p,
uint8_t *dest, const slh_dsa_ctx *ctx,uint32_t leaf_idx, void *v_info)+{
- struct slh_dsa_leaf_info_x1 *info = v_info;
- uint32_t *leaf_addr = info->leaf_addr;
- uint32_t *pk_addr = info->pk_addr;
- unsigned int i, k;
- uint8_t pk_buffer[p->wots_bytes];
- uint8_t *buffer;
- uint32_t wots_k_mask;
- if (leaf_idx == info->wots_sign_leaf)
- {
/* We're traversing the leaf that's signing;* generate the WOTS signature */wots_k_mask = 0;- }
- else
- {
/* Nope, we're just generating pk's;* turn off the signature logic */wots_k_mask = (uint32_t)~0;- }
Not sure I get why wots_k_mask is used? Is it intended to improve sidechannel-silence or performance?
Niels Möller nisse@lysator.liu.se writes:
I'm tempted to try to write a minimal implementation of just SLH-DSA-SHAKE-128s from the spec, to get a better understanding.
I've made some progress at that, see https://git.lysator.liu.se/nisse/poc-slh-dsa, the main building blocks are there, but some important top-level things to put it all together is still missing.
One question on the slh_dsa_sign function in your patch: Does that correspond to the "slh_sign_internal" algorithm in the spec? I.e., without the prepending of a context string (or just two zero bytes of context is empty), as specified in the "slh_sign" algorithm in the spec?
Regards, /Niels
Niels Möller nisse@lysator.liu.se writes:
Niels Möller nisse@lysator.liu.se writes:
I'm tempted to try to write a minimal implementation of just SLH-DSA-SHAKE-128s from the spec, to get a better understanding.
I've made some progress at that
And now it appears to pass tests, also for the top-level sign and verify functions. I think structure is a bit different, separate sign and verify functions for each building block, and no conditional outputs in the middle of the code.
There are no memcpy calls except for handling the "addr" arrays. (I'mnot so happy with the addr handling in my code; almost all bugs I had to fix were related to missing initialization or confusion on which fields in the address were expected to be assigned or cleared on entry to the various functions; I'd consider refactoring to have most or all functions take structured inputs (e.g, uint64_t tree_idx) instead of the addr arguments, and do local serialization where needed).
If this code will be useful for Nettle remains to be seen, but I hope it at least can provide some inspiration.
Regards, /Niels
Hello,
sorry for the delay. I have done some changes to the patch based on your review comments. Right now I just need to know what the API should look like because there needs to be the pure and hash variants, init, update, final variants and you wrote about the specific param variants as well. I am not sure how to put them all together without creating tons of specific functions. Could you please describe how the nettle API should look like with all these variants? I will submit the updated patch after I fix the API.
Unfortunately there are a couple of variations (besides the rather important parameter tradeoffs for security, speed, signature size), though:
- Signatures can be randomized or deterministic.
- Signatures can be "pure" or prehash.
- One can use either shake or sha2.
- Some of the sha2 variants use "compressed" addresses, I don't quite
understand what's the point of that additional complication. How do these variants relate to your usecase (mainly tls?), and others'? Is there one variant that is of primary importance, which should be the first one implemented?
We want to use SLH-DSA for document signing. I think I will need to add the pure and prehash API signing functions. But otherwise whether shake or sha2 variant is available it does not matter.
For the api, I think it should be possible to support "pure" signatures without requiring all of the message in memory at once, using a init/update/final-style interface for sign and verify, based on the update function of the underlying hash. Is that worth while?
Sounds like a good idea. I can add it in.
Does the implementation aim to be side channel silent? (According to the spec, implementations should be side channel silent *both* for signature creation and verification; in Nettle, I don't think there's any signature verify code that promises side channel silence).
I think so, yes.
Is the implementation optimized for speed? I see some potential high-level optimizations of the algorithms as described in the spec, like producing merkle root hashes, and maybe auth paths too, based on sequential processing of the leaves, rather than recursion. As well as potential microoptimizations.
I believe the reference implementation does have some high level optimizations.
Why different order for the public key? I would have expected PUB_SEED followed by the root (as in figure 16 in the spec, and same order as in the secret key). Does the NIST spec or some other standard clearly specify the serialization of the keys as byte strings?
It seems to be a typo in the comment. When I checked the logic it is indeed pk: [PUB_SEED || root]
For the Nettle api, I would also consider to not include the pubkey as part of the secret key, but instead pass both pubkey and secret key to the secret key functions. Similar to, e.g., ed25519_sha512_sign.
That seems redundant to me when the spec defines a secret key to contain the public key too. Did you mean that the secret key shouldnt contain the public key part?
I think I would prefer separate top-level functions for the different algorithm variants, rather than the enum slh_dsa_mode. They could all call the same internal function, passing the appropriate params struct as argument.
What about the pure and pre-hash variants and init, update and final api? Can you describe how you would like the API to look like?
It's unclear how this differs from _nettle_treehash further above? Or in general, whats the meaning of "x1" suffix on some functions?
I don't exactly know but I think it is some kind of optimization where the number determines how many addresses are processed at once. Here is an example of x8 from the reference implementation https://github.com/sphincs/sphincsplus/blob/7ec789ace6874d875f4bb84cb61b8115...
Not sure I get why wots_k_mask is used? Is it intended to improve sidechannel-silence or performance?
To me it seems to only switch the logic to generate WOTS signatures. I don't know whether it aims to improve either performance or sidechannel-silence.
Kind regards, Zoltan
Zoltan Fridrich zfridric@redhat.com writes:
We want to use SLH-DSA for document signing. I think I will need to add the pure and prehash API signing functions. But otherwise whether shake or sha2 variant is available it does not matter.
Do you think it would be reasonable to drop the sha2 variants in the first iteration? Then we wouldn't get the complexities of dealing with either "normal" or "compressed" addresses.
For the api, I think it should be possible to support "pure" signatures without requiring all of the message in memory at once, using a init/update/final-style interface for sign and verify, based on the update function of the underlying hash. Is that worth while?
Sounds like a good idea. I can add it in.
Unfortunately, after a closer look I don't think this is doable. For pure signing, the message is hashed twice, once with the secret prf to produce the randomizer, and then together with randomizer and public key to produce the "digest". It should be possibly to do for the verify operation only, but I don't think that's worth the effort.
It seems to be a typo in the comment. When I checked the logic it is indeed pk: [PUB_SEED || root]
That's good.
For the Nettle api, I would also consider to not include the pubkey as part of the secret key, but instead pass both pubkey and secret key to the secret key functions. Similar to, e.g., ed25519_sha512_sign.
That seems redundant to me when the spec defines a secret key to contain the public key too. Did you mean that the secret key shouldnt contain the public key part?
I'm thinking of something analogous to Nettle's ed25519 api,
void ed25519_sha512_sign (const uint8_t *pub, const uint8_t *priv, size_t length, const uint8_t *msg, uint8_t *signature);
int ed25519_sha512_verify (const uint8_t *pub, size_t length, const uint8_t *msg, const uint8_t *signature);
Here, the pub argument is the same for both functions, and the priv argument is the additional private information needed for signing. If we do this for dsa-slh, pub would include PK.seed and PK.root, and priv would include SK.seed and SK.prf, which seems straightforward to me.
(Signing applications would still be free to store public and private parts together whenever convenient).
Nettle isn't totally consistent though, some older signing functions take only a private key argument which then needs to include everything, others take public key as an additional argument. But I prefer the separate style (it's seems more flexible, and it's also more explicit about what's public and private), if there's no strong reason to do it differently.
I think I would prefer separate top-level functions for the different algorithm variants, rather than the enum slh_dsa_mode. They could all call the same internal function, passing the appropriate params struct as argument.
What about the pure and pre-hash variants and init, update and final api? Can you describe how you would like the API to look like?
Since it seems we can't have the init/update/final variant, I would suggest
void dsa_slh_shake128_sign (const uint8_t *pub, const uint8_t *priv, size_t length, const uint8_t *msg, uint8_t *signature); void dsa_slh_shake128_verify (const uint8_t *pub, size_t length, const uint8_t *msg, const uint8_t *signature);
for the pure variant, and
void dsa_slh_shake128_ph_sha256_sign (const uint8_t *pub, const uint8_t *priv, const uint8_t *digest, uint8_t *signature); void dsa_slh_shake128_ph_sha256_verify (const uint8_t *pub, const uint8_t *digest, const uint8_t *signature);
for the prehash with sha256 variant. There will be lots of functions, but they should all be simple wrappers around some internal function like
void _nettle_dsa_slh_sign_internal (const struct dsa_slh_variant *alg, const uint8_t *pub, const uint8_t *priv, size_t prefix_length, const uint8_t *prefix, size_t length, const uint8_t *msg, uint8_t *signature);
(with the prefix, including the extra zero bytes or prehash object id, passed as a separate argument to avoid allocation and copying of the message).
For link-time dependencies, it's desirable that code specific to one slh-dsa variant is referenced indirectly via the struct dsa_slh_variant, and that source files are organized so that applications using only a single variant don't link-depend on unrelated code.
(The name dsa_slh_variant is a tentative name I made up, feel free to use something different).
Another naming question, should it be dsa_slh_shake128, or maybe dsa_slh128_shake ? There's a shake128 algorithm, but that's *not* used for dsa-slh, it uses shake256. Instead, 128/192/256 refers to the size of the values used internally in slh-dsa and in the resulting signature.
It's unclear how this differs from _nettle_treehash further above? Or in general, whats the meaning of "x1" suffix on some functions?
I don't exactly know but I think it is some kind of optimization where the number determines how many addresses are processed at once. Here is an example of x8 from the reference implementation https://github.com/sphincs/sphincsplus/blob/7ec789ace6874d875f4bb84cb61b8115...
I don't get exactly how that 8-way operations works. It would be interesting to know what performance improvements they see from that (if it's a significant performance boost, we should consider adding something like that later).
And it's still unclear to me what's the difference between _nettle_treehash and _nettle_treehashx1 in the patch.
Not sure I get why wots_k_mask is used? Is it intended to improve sidechannel-silence or performance?
To me it seems to only switch the logic to generate WOTS signatures. I don't know whether it aims to improve either performance or sidechannel-silence.
I think it makes the code harder to understand when signature bytes are copied out to the result in a conditional in the middle a loop (both for wots and for the merkle inclusion proofs). I like the structure in my prototype better, see https://git.lysator.liu.se/nisse/poc-slh-dsa/-/blob/main/wots.c?ref_type=hea...
wots_chain (public_seed, addr, 0, msg, sig, sig); sha3_256_update (ctx, _SLH_DSA_128_SIZE, wots_chain (public_seed, addr, msg, 15 - msg, sig, pub));
where first line produces the signature, and second line extends the chain to produce the corresponding public key. But you probably don't want to do any extensive refactoring now.
To aid later refactoring, it would help with unit tests for the various components (even just using the intermadiate values from the top-level tests is helpful; that's what I did for my prototype).
Another useful addition would be benchmarking in examples/hogweed-benchmark.c.
Regards, /Niels
Another naming question, should it be dsa_slh_shake128, or maybe dsa_slh128_shake ?
We could stick to the spec param names like slh_dsa_shake_128s. Also do you prefer slh_dsa or dsa_slh prefix?
Do you think it would be reasonable to drop the sha2 variants in the first iteration?
Yes, I think its fine to just have shake variants in the first iteration.
On Wed, Jan 29, 2025 at 10:15 AM Niels Möller nisse@lysator.liu.se wrote:
Zoltan Fridrich zfridric@redhat.com writes:
We want to use SLH-DSA for document signing. I think I will need to add
the
pure and prehash API signing functions. But otherwise whether shake or
sha2
variant is available it does not matter.
Do you think it would be reasonable to drop the sha2 variants in the first iteration? Then we wouldn't get the complexities of dealing with either "normal" or "compressed" addresses.
For the api, I think it should be possible to support "pure" signatures without requiring all of the message in memory at once, using a init/update/final-style interface for sign and verify, based on the update function of the underlying hash. Is that worth while?
Sounds like a good idea. I can add it in.
Unfortunately, after a closer look I don't think this is doable. For pure signing, the message is hashed twice, once with the secret prf to produce the randomizer, and then together with randomizer and public key to produce the "digest". It should be possibly to do for the verify operation only, but I don't think that's worth the effort.
It seems to be a typo in the comment. When I checked the logic it is
indeed
pk: [PUB_SEED || root]
That's good.
For the Nettle api, I would also consider to not include the pubkey as part of the secret key, but instead pass both pubkey and secret key to the secret key functions. Similar to, e.g., ed25519_sha512_sign.
That seems redundant to me when the spec defines a secret key to contain the public key too. Did you mean that the secret key shouldnt contain the public key part?
I'm thinking of something analogous to Nettle's ed25519 api,
void ed25519_sha512_sign (const uint8_t *pub, const uint8_t *priv, size_t length, const uint8_t *msg, uint8_t *signature);
int ed25519_sha512_verify (const uint8_t *pub, size_t length, const uint8_t *msg, const uint8_t *signature);
Here, the pub argument is the same for both functions, and the priv argument is the additional private information needed for signing. If we do this for dsa-slh, pub would include PK.seed and PK.root, and priv would include SK.seed and SK.prf, which seems straightforward to me.
(Signing applications would still be free to store public and private parts together whenever convenient).
Nettle isn't totally consistent though, some older signing functions take only a private key argument which then needs to include everything, others take public key as an additional argument. But I prefer the separate style (it's seems more flexible, and it's also more explicit about what's public and private), if there's no strong reason to do it differently.
I think I would prefer separate top-level functions for the different algorithm variants, rather than the enum slh_dsa_mode. They could all call the same internal function, passing the appropriate params struct as argument.
What about the pure and pre-hash variants and init, update and final api? Can you describe how you would like the API to look like?
Since it seems we can't have the init/update/final variant, I would suggest
void dsa_slh_shake128_sign (const uint8_t *pub, const uint8_t *priv, size_t length, const uint8_t *msg, uint8_t *signature); void dsa_slh_shake128_verify (const uint8_t *pub, size_t length, const uint8_t *msg, const uint8_t *signature);
for the pure variant, and
void dsa_slh_shake128_ph_sha256_sign (const uint8_t *pub, const uint8_t *priv, const uint8_t *digest, uint8_t *signature); void dsa_slh_shake128_ph_sha256_verify (const uint8_t *pub, const uint8_t *digest, const uint8_t *signature);
for the prehash with sha256 variant. There will be lots of functions, but they should all be simple wrappers around some internal function like
void _nettle_dsa_slh_sign_internal (const struct dsa_slh_variant *alg, const uint8_t *pub, const uint8_t *priv, size_t prefix_length, const uint8_t *prefix, size_t length, const uint8_t *msg, uint8_t *signature);
(with the prefix, including the extra zero bytes or prehash object id, passed as a separate argument to avoid allocation and copying of the message).
For link-time dependencies, it's desirable that code specific to one slh-dsa variant is referenced indirectly via the struct dsa_slh_variant, and that source files are organized so that applications using only a single variant don't link-depend on unrelated code.
(The name dsa_slh_variant is a tentative name I made up, feel free to use something different).
Another naming question, should it be dsa_slh_shake128, or maybe dsa_slh128_shake ? There's a shake128 algorithm, but that's *not* used for dsa-slh, it uses shake256. Instead, 128/192/256 refers to the size of the values used internally in slh-dsa and in the resulting signature.
It's unclear how this differs from _nettle_treehash further above? Or in general, whats the meaning of "x1" suffix on some functions?
I don't exactly know but I think it is some kind of optimization where
the
number determines how many addresses are processed at once. Here is an example of x8 from the reference implementation
https://github.com/sphincs/sphincsplus/blob/7ec789ace6874d875f4bb84cb61b8115...
I don't get exactly how that 8-way operations works. It would be interesting to know what performance improvements they see from that (if it's a significant performance boost, we should consider adding something like that later).
And it's still unclear to me what's the difference between _nettle_treehash and _nettle_treehashx1 in the patch.
Not sure I get why wots_k_mask is used? Is it intended to improve sidechannel-silence or performance?
To me it seems to only switch the logic to generate WOTS signatures. I don't know whether it aims to improve either performance or sidechannel-silence.
I think it makes the code harder to understand when signature bytes are copied out to the result in a conditional in the middle a loop (both for wots and for the merkle inclusion proofs). I like the structure in my prototype better, see https://git.lysator.liu.se/nisse/poc-slh-dsa/-/blob/main/wots.c?ref_type=hea...
wots_chain (public_seed, addr, 0, msg, sig, sig); sha3_256_update (ctx, _SLH_DSA_128_SIZE, wots_chain (public_seed, addr, msg, 15 - msg, sig, pub));
where first line produces the signature, and second line extends the chain to produce the corresponding public key. But you probably don't want to do any extensive refactoring now.
To aid later refactoring, it would help with unit tests for the various components (even just using the intermadiate values from the top-level tests is helpful; that's what I did for my prototype).
Another useful addition would be benchmarking in examples/hogweed-benchmark.c.
Regards, /Niels
-- Niels Möller. PGP key CB4962D070D77D7FCB8BA36271D8F1FF368C6677. Internet email is subject to wholesale government surveillance.
Zoltan Fridrich zfridric@redhat.com writes:
Do you think it would be reasonable to drop the sha2 variants in the first iteration?
Yes, I think its fine to just have shake variants in the first iteration.
I'm leaning towards starting with slh_dsa_shake_128s based on my rather minimal code (about 1000 lines, including comments), and iterate from there.
Regards, /Niels
Niels Möller nisse-SamgB31n2u5IcsJQ0EH25Q@public.gmane.org writes:
void dsa_slh_shake128_sign (const uint8_t *pub, const uint8_t *priv, size_t length, const uint8_t *msg, uint8_t *signature);
...
Another naming question, should it be dsa_slh_shake128, or maybe dsa_slh128_shake ? There's a shake128 algorithm, but that's *not* used for dsa-slh, it uses shake256. Instead, 128/192/256 refers to the size of the values used internally in slh-dsa and in the resulting signature.
It would be nice to get naming right... some considerations:
- SPHINCS+ is the original name, and is the only one with a stable specification: https://sphincs.org/data/sphincs+-round3-submission-nist.zip
- The DSA-SLH specification aren't final, are they? NIST is known to make last minute incompatible changes that can complicate naming, or make a small change in five years that modify the algorithm.
- https://github.com/sphincs/sphincsplus has a table with names of the core primitives that are available, but the hash choice needs to be added too.
- Using "s" (for "small") and "f" (for "fast") variants is in common use.
- Round 2 submission of SPHINCS+ introduced the variants "simple" and "robust" which has consequences for naming.
The most complete list of parameter names I can find is page 55 of the round 3 submission, I'm including the complete list of variants below.
Some ideas based on the above:
void sphincp_128ss_sha2_sign (const uint8_t *pub, const uint8_t *priv, size_t length, const uint8_t *msg, uint8_t *signature);
sphincp_192fr_sha3_sign (const uint8_t *pub,
sphincp_192fr_sha3_sign (const uint8_t *pub,
Or more expanded as
sphincp_smallsimple128_sha2_sign (const uint8_t *pub, sphincp_fastrobust192_sha2_sign (const uint8_t *pub, sphincp_fastsimple256_sha3_sign (const uint8_t *pub,
Using 'sha2' and 'sha3' seems clearer than including hash size like 'shake256' or 'sha256'.
Expanding 'small', 'fast, 'simple' and 'robust' may avoid some confusion. I've made the mistake of confusing 'small' with 'simple' when I used 's' myself.
/Simon
SPHINCS+ -SHAKE256-128s-simple SPHINCS+ -SHAKE256-128s-robust SPHINCS+ -SHAKE256-128f-simple SPHINCS+ -SHAKE256-128f-robust SPHINCS+ -SHAKE256-192s-simple SPHINCS+ -SHAKE256-192s-robust SPHINCS+ -SHAKE256-192f-simple SPHINCS+ -SHAKE256-192f-robust SPHINCS+ -SHAKE256-256s-simple SPHINCS+ -SHAKE256-256s-robust SPHINCS+ -SHAKE256-256f-simple SPHINCS+ -SHAKE256-256f-robust
SPHINCS+ -SHA-256-128s-simple SPHINCS+ -SHA-256-128s-robust SPHINCS+ -SHA-256-128f-simple SPHINCS+ -SHA-256-128f-robust SPHINCS+ -SHA-256-192s-simple SPHINCS+ -SHA-256-192s-robust SPHINCS+ -SHA-256-192f-simple SPHINCS+ -SHA-256-192f-robust SPHINCS+ -SHA-256-256s-simple SPHINCS+ -SHA-256-256s-robust SPHINCS+ -SHA-256-256f-simple SPHINCS+ -SHA-256-256f-robust
SPHINCS+ -Haraka-128s-simple SPHINCS+ -Haraka-128s-robust SPHINCS+ -Haraka-128f-simple SPHINCS+ -Haraka-128f-robust SPHINCS+ -Haraka-192f-simple SPHINCS+ -Haraka-192f-robust SPHINCS+ -Haraka-192s-simple SPHINCS+ -Haraka-192s-robust SPHINCS+ -Haraka-256f-simple SPHINCS+ -Haraka-256f-robust SPHINCS+ -Haraka-256s-simple SPHINCS+ -Haraka-256s-robust
SPHINCS+ -Haraka-128s-simple SPHINCS+ -Haraka-128s-robust SPHINCS+ -Haraka-128f-simple SPHINCS+ -Haraka-128f-robust SPHINCS+ -Haraka-192s-simple SPHINCS+ -Haraka-192s-robust SPHINCS+ -Haraka-192f-simple SPHINCS+ -Haraka-192f-robust SPHINCS+ -Haraka-256s-simple SPHINCS+ -Haraka-256s-robust SPHINCS+ -Haraka-256f-simple SPHINCS+ -Haraka-256f-robust
SPHINCS+ -SHA-256-128s-simple SPHINCS+ -SHA-256-128s-robust SPHINCS+ -SHA-256-128f-simple SPHINCS+ -SHA-256-128f-robust SPHINCS+ -SHA-256-192s-simple SPHINCS+ -SHA-256-192s-robust SPHINCS+ -SHA-256-192f-simple SPHINCS+ -SHA-256-192f-robust SPHINCS+ -SHA-256-256s-simple SPHINCS+ -SHA-256-256s-robust SPHINCS+ -SHA-256-256f-simple SPHINCS+ -SHA-256-256f-robust
SPHINCS+ -SHAKE256-128s-simple SPHINCS+ -SHAKE256-128s-robust SPHINCS+ -SHAKE256-128f-simple SPHINCS+ -SHAKE256-128f-robust SPHINCS+ -SHAKE256-192s-simple SPHINCS+ -SHAKE256-192s-robust SPHINCS+ -SHAKE256-192f-simple SPHINCS+ -SHAKE256-192f-robust SPHINCS+ -SHAKE256-256s-simple SPHINCS+ -SHAKE256-256s-robust SPHINCS+ -SHAKE256-256f-simple SPHINCS+ -SHAKE256-256f-robust
Zoltan Fridrich zfridric@redhat.com writes:
Another naming question, should it be dsa_slh_shake128, or maybe dsa_slh128_shake ?
We could stick to the spec param names like slh_dsa_shake_128s. Also do you prefer slh_dsa or dsa_slh prefix?
I was a bit careless, it seems. The spec name slh_dsa_shake_128s looks reasonable, and we could stay consistent with that.
Simon Josefsson simon@josefsson.org writes:
It would be nice to get naming right...
I agree, thanks for helping out.
- The DSA-SLH specification aren't final, are they? NIST is known to make last minute incompatible changes that can complicate naming, or make a small change in five years that modify the algorithm.
According to https://csrc.nist.gov/pubs/fips/205/final, the version published 2024-08-13 is final. And it includes some changes (context string, domain-separation stuff) which, as I have understood it, makes the spec incompatible with the earlier SPHINCS+ proposal.
I would expect that the NIST version is the one that will be deployed in practice. For that reason, I'd lean towards using the NIST names.
I would also lean towards initially not supporting non-empty context string.
- Using "s" (for "small") and "f" (for "fast") variants is in common use.
Makes sense, I think we should have that in our naming.
- Round 2 submission of SPHINCS+ introduced the variants "simple" and "robust" which has consequences for naming.
Those are new to me (I have only read the NIST spec, I haven't followed along in the process leading up to that).
Which of those variants made it into the NIST spec? Is there a short explanation for when one would want one or the other?
Using 'sha2' and 'sha3' seems clearer than including hash size like 'shake256' or 'sha256'.
I agree the hash size should be attached to the signature algorithm rather than to the underlying hash algorithm. But I think "shake" rather than "sha3" seems reasonably clear too.
Expanding 'small', 'fast, 'simple' and 'robust' may avoid some confusion. I've made the mistake of confusing 'small' with 'simple' when I used 's' myself.
Right, if we're going to have them all, then "s" as abbreviation gets confusing.
Regards, /Niels
On Wed, 2025-01-29 at 12:08 +0100, Niels Möller wrote:
Zoltan Fridrich zfridric@redhat.com writes:
Another naming question, should it be dsa_slh_shake128, or maybe dsa_slh128_shake ?
We could stick to the spec param names like slh_dsa_shake_128s. Also do you prefer slh_dsa or dsa_slh prefix?
I was a bit careless, it seems. The spec name slh_dsa_shake_128s looks reasonable, and we could stay consistent with that.
Simon Josefsson simon@josefsson.org writes:
It would be nice to get naming right...
I agree, thanks for helping out.
- The DSA-SLH specification aren't final, are they? NIST is known to make last minute incompatible changes that can complicate naming, or make a small change in five years that modify the algorithm.
According to https://csrc.nist.gov/pubs/fips/205/final, the version published 2024-08-13 is final. And it includes some changes (context string, domain-separation stuff) which, as I have understood it, makes the spec incompatible with the earlier SPHINCS+ proposal.
I would expect that the NIST version is the one that will be deployed in practice. For that reason, I'd lean towards using the NIST names.
This is correct, SPHINCS+ is just an historical artifact that nobody should use, let alone implement, at this point.
And given SLH-DSA is not interoperable with SPHINCS+ it makes no sense to use sphincs derived naming.
I would also lean towards initially not supporting non-empty context string.
- Using "s" (for "small") and "f" (for "fast") variants is in common use.
Makes sense, I think we should have that in our naming.
I strongly suggest looking around at what others do which is mainly to try to stay close to the naming suggested via FIPS205. Specifically in section 11 of FIPS 205 there is a table of parameter sets that defines these names:
SLH-DSA-SHA2-128s SLH-DSA-SHAKE-128s SLH-DSA-SHA2-128f SLH-DSA-SHAKE-128f SLH-DSA-SHA2-192s SLH-DSA-SHAKE-192s SLH-DSA-SHA2-192f SLH-DSA-SHAKE-192f SLH-DSA-SHA2-256s SLH-DSA-SHAKE-256s SLH-DSA-SHA2-256f SLH-DSA-SHAKE-256f
I think it is ok to avoid capitalization and convert hyphen to dash, but otherwise I recommend following exactly this nomenclature to avoid confusion in users.
- Round 2 submission of SPHINCS+ introduced the variants "simple" and "robust" which has consequences for naming.
Those are new to me (I have only read the NIST spec, I haven't followed along in the process leading up to that).
Which of those variants made it into the NIST spec? Is there a short explanation for when one would want one or the other?
Please follow just FIPS 205, we do not need any more "variants" or complexity really, SLH is already too complex in the number of choices as it is.
Using 'sha2' and 'sha3' seems clearer than including hash size like 'shake256' or 'sha256'.
I agree the hash size should be attached to the signature algorithm rather than to the underlying hash algorithm. But I think "shake" rather than "sha3" seems reasonably clear too.
SHAKE is not SHA3, using SHA3 would be incorrect and confusing.
Expanding 'small', 'fast, 'simple' and 'robust' may avoid some confusion. I've made the mistake of confusing 'small' with 'simple' when I used 's' myself.
Right, if we're going to have them all, then "s" as abbreviation gets confusing.
Only the small and fast variants are relevant, the others are just historic and should not be implemented now.
HTH, Simo.
Niels Möller nisse-SamgB31n2u5IcsJQ0EH25Q@public.gmane.org writes:
I would also lean towards initially not supporting non-empty context string.
Why? The empty string is the default context value.
/Simon
I have changed the API and I have done some refactoring. I tried to fix all of the review comments although some of the optimizations I wasn't able to do. I am attaching the patch.
Should the API have pk,sk,sig size functions for every parameter set?
I have seen progression on https://git.lysator.liu.se/nisse/poc-slh-dsa/-/tree/main so I am not sure whether you plan to use this patch or whether you would like to use your own slh-dsa nettle implementation?
Regards, Zoltan
On Wed, Jan 29, 2025 at 8:38 PM Simon Josefsson simon@josefsson.org wrote:
Niels Möller nisse-SamgB31n2u5IcsJQ0EH25Q@public.gmane.org writes:
I would also lean towards initially not supporting non-empty context
string.
Why? The empty string is the default context value.
/Simon _______________________________________________ nettle-bugs mailing list -- nettle-bugs@lists.lysator.liu.se To unsubscribe send an email to nettle-bugs-leave@lists.lysator.liu.se
Zoltan Fridrich zfridric@redhat.com writes:
Should the API have pk,sk,sig size functions for every parameter set?
I think the base api should be constants (#define) for each variant. If useful, one could add some kind of struct representing a signature algorithm, similar in spirit to struct nettle_mac.
I have seen progression on https://git.lysator.liu.se/nisse/poc-slh-dsa/-/tree/main so I am not sure whether you plan to use this patch or whether you would like to use your own slh-dsa nettle implementation?
First, I want to say that even if your patch doesn't end up in Nettle, it has been very helpful to have your working code when debugging my implementation: most of my unit tests are based on running your code under gdb and examining input and output values of relevant parts, and when I got wrong output, I've been able to compared behavior step by step. It's been fun to look into slh-dsa.
I'm leaning towards using my implementation. I've pushed a sligthly cleaned up version to the branch slh-dsa-shake-128s in the nettle repo (also appended below as a patch, excluding the tests and ChangeLog). I think main technical benefit is that I've tried harder do avoid temporary allocation and copies. I'm also thinking of the potential of generalizing the merkle tree utilities for other applications, e.g., transparency logs.
That said, there's going to be some additional complexity when adding support for additional variants.
Questions for you as well as for others on the list:
1. Does the public api look reasonable? Four functions, slh_dsa_shake_128s_root, slh_dsa_shake_128s_generate_keypair, slh_dsa_shake_128s_sign, slh_dsa_shake_128s_verify.
2. What should be the order and priorities when adding additional features?
* More security/speed/size variants, initial implementation only has one of the six {128,192,256}{s,f}?
* Add sha2 variants (rather than sha3 shake only)?
* Add support for non-empty context string?
* Add support for prehash variants?
* Add support for non-deterministic variants?
It's unclear to me which features are most relevant for applications, but I think it makes sense to add only the most important right away, and add additional features later, when real use cases appear.
3. Does the implementation choices look reasonable, or will it fall apart when generalizing to support more variants?
Before adding more features, I would also like to add (1) tests for proper side-channel silence, and (2) benchmarks. And as soon as the dust has settled on the public API, docs are also rather important.
Regards, /Niels
diff --git a/Makefile.in b/Makefile.in index 71ad761e..6b3f4c1e 100644 --- a/Makefile.in +++ b/Makefile.in @@ -226,7 +226,9 @@ hogweed_SOURCES = sexp.c sexp-format.c \ ed25519-sha512.c ed25519-sha512-pubkey.c \ ed25519-sha512-sign.c ed25519-sha512-verify.c \ ed448-shake256.c ed448-shake256-pubkey.c \ - ed448-shake256-sign.c ed448-shake256-verify.c + ed448-shake256-sign.c ed448-shake256-verify.c \ + slh-fors.c slh-merkle.c slh-shake.c slh-wots.c slh-xmss.c \ + slh-dsa-shake-128s.c
OPT_SOURCES = fat-arm.c fat-arm64.c fat-ppc.c fat-s390x.c fat-x86_64.c mini-gmp.c
@@ -246,7 +248,7 @@ HEADERS = aes.h arcfour.h arctwo.h asn1.h blowfish.h balloon.h \ ocb.h pbkdf2.h \ pgp.h pkcs1.h pss.h pss-mgf1.h realloc.h ripemd160.h rsa.h \ salsa20.h sexp.h serpent.h \ - sha.h sha1.h sha2.h sha3.h sm3.h sm4.h streebog.h twofish.h \ + sha.h sha1.h sha2.h sha3.h slh-dsa.h sm3.h sm4.h streebog.h twofish.h \ umac.h yarrow.h xts.h poly1305.h nist-keywrap.h \ drbg-ctr.h
@@ -279,6 +281,7 @@ DISTFILES = $(SOURCES) $(HEADERS) getopt.h getopt_int.h \ ctr-internal.h chacha-internal.h sha3-internal.h \ salsa20-internal.h umac-internal.h hogweed-internal.h \ rsa-internal.h pkcs1-internal.h dsa-internal.h eddsa-internal.h \ + slh-dsa-internal.h \ gmp-glue.h ecc-internal.h fat-setup.h oaep.h \ mini-gmp.h asm.m4 m4-utils.m4 \ nettle.texinfo nettle.info nettle.html nettle.pdf sha-example.c diff --git a/slh-dsa-internal.h b/slh-dsa-internal.h new file mode 100644 index 00000000..ed42ef2e --- /dev/null +++ b/slh-dsa-internal.h @@ -0,0 +1,193 @@ +/* slh-dsa-internal.h + + Copyright (C) 2025 Niels Möller + + This file is part of GNU Nettle. + + GNU Nettle is free software: you can redistribute it and/or + modify it under the terms of either: + + * the GNU Lesser General Public License as published by the Free + Software Foundation; either version 3 of the License, or (at your + option) any later version. + + or + + * the GNU General Public License as published by the Free + Software Foundation; either version 2 of the License, or (at your + option) any later version. + + or both in parallel, as here. + + GNU Nettle is distributed in the hope that it will be useful, + but WITHOUT ANY WARRANTY; without even the implied warranty of + MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU + General Public License for more details. + + You should have received copies of the GNU General Public License and + the GNU Lesser General Public License along with this program. If + not, see http://www.gnu.org/licenses/. +*/ + +#ifndef NETTLE_SLH_DSA_INTERNAL_H_INCLUDED +#define NETTLE_SLH_DSA_INTERNAL_H_INCLUDED + +#include <stdint.h> + +/* Name mangling */ +#define _slh_shake_init _nettle_slh_shake_init +#define _slh_shake _nettle_slh_shake +#define _wots_gen _nettle_wots_gen +#define _wots_sign _nettle_wots_sign +#define _wots_verify _nettle_wots_verify +#define _merkle_root _nettle_merkle_root +#define _merkle_sign _nettle_merkle_sign +#define _merkle_verify _nettle_merkle_verify +#define _fors_gen _nettle_fors_gen +#define _fors_sign _nettle_fors_sign +#define _fors_verify _nettle_fors_verify +#define _xmss_gen _nettle_xmss_gen +#define _xmss_sign _nettle_xmss_sign +#define _xmss_verify _nettle_xmss_verify + +/* Size of a single hash, including the seed and prf parameters */ +#define _SLH_DSA_128_SIZE 16 + +#define SLH_DSA_D 7 +#define SLH_DSA_M 30 + +/* Fields always big-endian */ +struct slh_address_tree +{ + uint32_t layer; + uint32_t pad; /* Always zero */ + uint64_t tree_idx; +}; + +/* Fields always big-endian */ +struct slh_address_hash +{ + uint32_t type; + uint32_t keypair; + /* height for XMSS_TREE and FORS_TREE, chain address for WOTS_HASH. */ + uint32_t height_chain; + /* index for XMSS_TREE and FORS_TREE, hash address for WOTS_HASH. */ + uint32_t index_hash; +}; + +enum slh_addr_type + { + SLH_WOTS_HASH = 0, + SLH_WOTS_PK = 1, + SLH_XMSS_TREE = 2, + SLH_FORS_TREE = 3, + SLH_FORS_ROOTS = 4, + SLH_WOTS_PRF = 5, + SLH_FORS_PRF = 6, + }; + +struct slh_merkle_ctx_public +{ + const uint8_t *seed; + struct slh_address_tree at; + unsigned keypair; /* Used only by fors_leaf and fors_node. */ +}; + +struct slh_merkle_ctx_secret +{ + struct slh_merkle_ctx_public pub; + const uint8_t *secret_seed; +}; + +struct sha3_256_ctx; +void +_slh_shake_init (struct sha3_256_ctx *ctx, const uint8_t *public_seed, + const struct slh_address_tree *at, const struct slh_address_hash *ah); +void +_slh_shake (const uint8_t *public_seed, + const struct slh_address_tree *at, const struct slh_address_hash *ah, + const uint8_t *secret, uint8_t *out); + +#define _WOTS_SIGNATURE_LENGTH 35 +/* 560 bytes */ +#define WOTS_SIGNATURE_SIZE (_WOTS_SIGNATURE_LENGTH*_SLH_DSA_128_SIZE) + +void +_wots_gen (const uint8_t *public_seed, const uint8_t *secret_seed, const struct slh_address_tree *at, + uint32_t keypair, uint8_t *pub); + +void +_wots_sign (const uint8_t *public_seed, const uint8_t *secret_seed, const struct slh_address_tree *at, + unsigned keypair, const uint8_t *msg, uint8_t *signature, uint8_t *pub); + +/* Computes candidate public key from signature. */ +void +_wots_verify (const uint8_t *public_seed, const struct slh_address_tree *at, + unsigned keypair, const uint8_t *msg, const uint8_t *signature, uint8_t *pub); + +/* Merkle tree functions. Could be generalized for other merkle tree + applications, by using const void* for the ctx argument. */ +typedef void merkle_leaf_hash_func (const struct slh_merkle_ctx_secret *ctx, unsigned index, uint8_t *out); +typedef void merkle_node_hash_func (const struct slh_merkle_ctx_public *ctx, unsigned height, unsigned index, + const uint8_t *left, const uint8_t *right, uint8_t *out); + +void +_merkle_root (const struct slh_merkle_ctx_secret *ctx, + merkle_leaf_hash_func *leaf_hash, merkle_node_hash_func *node_hash, + unsigned height, unsigned start, uint8_t *root, + /* Must have space for (height + 1) node hashes */ + uint8_t *stack); + +void +_merkle_sign (const struct slh_merkle_ctx_secret *ctx, + merkle_leaf_hash_func *leaf_hash, merkle_node_hash_func *node_hash, + unsigned height, unsigned idx, uint8_t *signature); + +/* The hash argument is both input (leaf hash to be verified) and output (resulting root hash). */ +void +_merkle_verify (const struct slh_merkle_ctx_public *ctx, merkle_node_hash_func *node_hash, + unsigned height, unsigned idx, const uint8_t *signature, uint8_t *hash); + +/* Use k Merkle trees, each of size 2^a. Signs messages of size + k * a = 168 bits or 21 octets. */ +#define FORS_A 12 +#define FORS_K 14 + +#define FORS_MSG_SIZE 21 +/* 2912 bytes */ +#define FORS_SIGNATURE_SIZE (FORS_K * (FORS_A + 1) * _SLH_DSA_128_SIZE) + +/* Generates a single secret value, and corresponding leaf hash. */ +void +_fors_gen (const struct slh_merkle_ctx_secret *ctx, unsigned index, uint8_t *sk, uint8_t *leaf); + +/* Computes a fors signature as well as the public key. */ +void +_fors_sign (const struct slh_merkle_ctx_secret *fors_ctx, + const uint8_t *msg, uint8_t *signature, uint8_t *pub); + +/* Computes candidate public key from signature. */ +void +_fors_verify (const struct slh_merkle_ctx_public *ctx, + const uint8_t *msg, const uint8_t *signature, uint8_t *pub); + +#define XMSS_H 9 +/* Just the auth path, excluding the wots signature, 144 bytes. */ +#define XMSS_AUTH_SIZE (XMSS_H * _SLH_DSA_128_SIZE) +#define XMSS_SIGNATURE_SIZE (WOTS_SIGNATURE_SIZE + XMSS_AUTH_SIZE) + +void +_xmss_gen (const uint8_t *public_seed, const uint8_t *secret_seed, + uint8_t *root); + +/* Signs using wots, then signs wots public key using xmss. Also + returns the xmss public key (i.e., root hash).*/ +void +_xmss_sign (const struct slh_merkle_ctx_secret *ctx, + unsigned idx, const uint8_t *msg, uint8_t *signature, uint8_t *pub); + +void +_xmss_verify (const struct slh_merkle_ctx_public *ctx, + unsigned idx, const uint8_t *msg, const uint8_t *signature, uint8_t *pub); + +#endif /* NETTLE_SLH_DSA_INTERNAL_H_INCLUDED */ diff --git a/slh-dsa-shake-128s.c b/slh-dsa-shake-128s.c new file mode 100644 index 00000000..1e1aa63b --- /dev/null +++ b/slh-dsa-shake-128s.c @@ -0,0 +1,200 @@ +/* slh-dsa-shake-128s.c + + SLH-DSA (FIPS 205) signatures. + + Copyright (C) 2025 Niels Möller + + This file is part of GNU Nettle. + + GNU Nettle is free software: you can redistribute it and/or + modify it under the terms of either: + + * the GNU Lesser General Public License as published by the Free + Software Foundation; either version 3 of the License, or (at your + option) any later version. + + or + + * the GNU General Public License as published by the Free + Software Foundation; either version 2 of the License, or (at your + option) any later version. + + or both in parallel, as here. + + GNU Nettle is distributed in the hope that it will be useful, + but WITHOUT ANY WARRANTY; without even the implied warranty of + MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU + General Public License for more details. + + You should have received copies of the GNU General Public License and + the GNU Lesser General Public License along with this program. If + not, see http://www.gnu.org/licenses/. +*/ + +#if HAVE_CONFIG_H +# include "config.h" +#endif + +#include <assert.h> +#include <string.h> + +#include "bswap-internal.h" +#include "memops.h" +#include "sha3.h" +#include "slh-dsa.h" +#include "slh-dsa-internal.h" + +void +slh_dsa_shake_128s_root (const uint8_t *public_seed, const uint8_t *private_seed, + uint8_t *root) +{ + _xmss_gen (public_seed, private_seed, root); +} + +void +slh_dsa_shake_128s_generate_keypair (uint8_t *pub, uint8_t *priv, + void *random_ctx, nettle_random_func *random) +{ + random (random_ctx, SLH_DSA_SHAKE_128S_SEED_SIZE, pub); + random (random_ctx, 2*SLH_DSA_SHAKE_128S_SEED_SIZE, priv); + slh_dsa_shake_128s_root (pub, priv, pub + SLH_DSA_SHAKE_128S_SEED_SIZE); +} + +static const uint8_t slh_pure_prefix[2] = {0, 0}; + +static void +slh_digest (struct sha3_256_ctx *ctx, + const uint8_t *randomizer, const uint8_t *pub, + size_t length, const uint8_t *msg, + uint8_t *digest, uint64_t *tree_idx, unsigned *leaf_idx) +{ + uint64_t x; + unsigned i; + + sha3_256_update (ctx, _SLH_DSA_128_SIZE, randomizer); + sha3_256_update (ctx, 2*_SLH_DSA_128_SIZE, pub); + sha3_256_update (ctx, sizeof(slh_pure_prefix), slh_pure_prefix); + sha3_256_update (ctx, length, msg); + sha3_256_shake (ctx, SLH_DSA_M, digest); + + /* Split digest as + +----+------+-----+ + | md | tree | leaf| + +----+------+-----+ + 21 7 2 + + The first 21 octets are the digest signed with fors, the next 7 + octets represent 54 bits selecting the tree, the last 2 octets + represent 9 bits selecting the key in that tree. + + Left over high bits are discarded. + */ + x = digest[21] & 0x3f; /* Discard 2 high-most bits of 56 */ + for (i = 22; i < 28; i++) + x = (x << 8) + digest[i]; + *tree_idx = x; + /* Discard 7 high-most bits of 16 */ + *leaf_idx = ((digest[28] & 1) << 8) + digest[29]; +} + +/* Only the "pure" and deterministic variant. */ +void +slh_dsa_shake_128s_sign (const uint8_t *pub, const uint8_t *priv, + size_t length, const uint8_t *msg, + uint8_t *signature) +{ + struct sha3_256_ctx ctx; + uint8_t digest[SLH_DSA_M]; + uint8_t root[_SLH_DSA_128_SIZE]; + + uint64_t tree_idx; + unsigned leaf_idx; + int i; + + struct slh_merkle_ctx_secret merkle_ctx = + { + { + pub, { 0, }, 0, + }, + priv, + }; + /* First the "randomizer" */ + sha3_256_init (&ctx); + sha3_256_update (&ctx, _SLH_DSA_128_SIZE, priv + _SLH_DSA_128_SIZE); + sha3_256_update (&ctx, _SLH_DSA_128_SIZE, pub); + sha3_256_update (&ctx, sizeof(slh_pure_prefix), slh_pure_prefix); + sha3_256_update (&ctx, length, msg); + sha3_256_shake (&ctx, _SLH_DSA_128_SIZE, signature); + + slh_digest (&ctx, signature, pub, length, msg, digest, &tree_idx, &leaf_idx); + + signature += _SLH_DSA_128_SIZE; + + merkle_ctx.pub.at.tree_idx = bswap64_if_le (tree_idx); + merkle_ctx.pub.keypair = leaf_idx; + + _fors_sign (&merkle_ctx, digest, signature, root); + signature += FORS_SIGNATURE_SIZE; + + _xmss_sign (&merkle_ctx, leaf_idx, root, signature, root); + + for (i = 1; i < SLH_DSA_D; i++) + { + signature += XMSS_SIGNATURE_SIZE; + + leaf_idx = tree_idx & ((1<< XMSS_H) - 1); + tree_idx >>= XMSS_H; + + merkle_ctx.pub.at.layer = bswap32_if_le(i); + merkle_ctx.pub.at.tree_idx = bswap64_if_le (tree_idx); + + _xmss_sign (&merkle_ctx, leaf_idx, root, signature, root); + } + assert (memeql_sec (root, pub + _SLH_DSA_128_SIZE, sizeof(root))); +} + +int +slh_dsa_shake_128s_verify (const uint8_t *pub, + size_t length, const uint8_t *msg, + const uint8_t *signature) +{ + struct sha3_256_ctx ctx; + uint8_t digest[SLH_DSA_M]; + uint8_t root[_SLH_DSA_128_SIZE]; + + uint64_t tree_idx; + unsigned leaf_idx; + int i; + + struct slh_merkle_ctx_public merkle_ctx = + { + pub, { 0, }, 0 + }; + + sha3_256_init (&ctx); + slh_digest (&ctx, signature, pub, length, msg, digest, &tree_idx, &leaf_idx); + + signature += _SLH_DSA_128_SIZE; + + merkle_ctx.at.tree_idx = bswap64_if_le (tree_idx); + merkle_ctx.keypair = leaf_idx; + + _fors_verify (&merkle_ctx, digest, signature, root); + signature += FORS_SIGNATURE_SIZE; + + _xmss_verify (&merkle_ctx, leaf_idx, root, signature, root); + + for (i = 1; i < SLH_DSA_D; i++) + { + signature += XMSS_SIGNATURE_SIZE; + + leaf_idx = tree_idx & ((1<< XMSS_H) - 1); + tree_idx >>= XMSS_H; + + merkle_ctx.at.layer = bswap32_if_le(i); + merkle_ctx.at.tree_idx = bswap64_if_le (tree_idx); + + _xmss_verify (&merkle_ctx, leaf_idx, root, signature, root); + } + return memcmp (root, pub + _SLH_DSA_128_SIZE, sizeof(root)) == 0; +} diff --git a/slh-dsa.h b/slh-dsa.h new file mode 100644 index 00000000..975eb696 --- /dev/null +++ b/slh-dsa.h @@ -0,0 +1,86 @@ +/* slh-dsa.h + + SLH-DSA (FIPS 205) signatures. + + Copyright (C) 2025 Niels Möller + + This file is part of GNU Nettle. + + GNU Nettle is free software: you can redistribute it and/or + modify it under the terms of either: + + * the GNU Lesser General Public License as published by the Free + Software Foundation; either version 3 of the License, or (at your + option) any later version. + + or + + * the GNU General Public License as published by the Free + Software Foundation; either version 2 of the License, or (at your + option) any later version. + + or both in parallel, as here. + + GNU Nettle is distributed in the hope that it will be useful, + but WITHOUT ANY WARRANTY; without even the implied warranty of + MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU + General Public License for more details. + + You should have received copies of the GNU General Public License and + the GNU Lesser General Public License along with this program. If + not, see http://www.gnu.org/licenses/. +*/ + +#ifndef NETTLE_SLH_DSA_H +#define NETTLE_SLH_DSA_H + +#include "nettle-types.h" + +#ifdef __cplusplus +extern "C" { +#endif + +/* Name mangling */ +#define slh_dsa_shake_128s_root nettle_slh_dsa_shake_128s_root +#define slh_dsa_shake_128s_generate_keypair nettle_slh_dsa_shake_128s_generate_keypair +#define slh_dsa_shake_128s_sign nettle_slh_dsa_shake_128s_sign +#define slh_dsa_shake_128s_verify nettle_slh_dsa_shake_128s_verify + +/* Key layout: + private: + secret_seed + prf + public: + public_seed + root +*/ + +#define SLH_DSA_SHAKE_128S_SEED_SIZE 16 +#define SLH_DSA_SHAKE_128S_KEY_SIZE 32 +#define SLH_DSA_SHAKE_128S_SIGNATURE_SIZE 7856 + +/* Computes public key root, from the two seeds. */ +void +slh_dsa_shake_128s_root (const uint8_t *public_seed, const uint8_t *private_seed, + uint8_t *root); + +void +slh_dsa_shake_128s_generate_keypair (uint8_t *pub, uint8_t *key, + void *random_ctx, nettle_random_func *random); + +/* Only the "pure" and deterministic variant. */ +void +slh_dsa_shake_128s_sign (const uint8_t *pub, const uint8_t *priv, + size_t length, const uint8_t *msg, + uint8_t *signature); + +int +slh_dsa_shake_128s_verify (const uint8_t *pub, + size_t length, const uint8_t *msg, + const uint8_t *signature); + +#ifdef __cplusplus +} +#endif + +#endif /* NETTLE_SLH_DSA_H */ diff --git a/slh-fors.c b/slh-fors.c new file mode 100644 index 00000000..27a31a82 --- /dev/null +++ b/slh-fors.c @@ -0,0 +1,178 @@ +/* slh-fors.c + + Forest of Random Subsets, part of SLH-DSA (FIPS 205) + + Copyright (C) 2025 Niels Möller + + This file is part of GNU Nettle. + + GNU Nettle is free software: you can redistribute it and/or + modify it under the terms of either: + + * the GNU Lesser General Public License as published by the Free + Software Foundation; either version 3 of the License, or (at your + option) any later version. + + or + + * the GNU General Public License as published by the Free + Software Foundation; either version 2 of the License, or (at your + option) any later version. + + or both in parallel, as here. + + GNU Nettle is distributed in the hope that it will be useful, + but WITHOUT ANY WARRANTY; without even the implied warranty of + MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU + General Public License for more details. + + You should have received copies of the GNU General Public License and + the GNU Lesser General Public License along with this program. If + not, see http://www.gnu.org/licenses/. +*/ + +#if HAVE_CONFIG_H +# include "config.h" +#endif + +#include <assert.h> + +#include "bswap-internal.h" +#include "sha3.h" +#include "slh-dsa-internal.h" + +void +_fors_gen (const struct slh_merkle_ctx_secret *ctx, + unsigned idx, uint8_t *sk, uint8_t *leaf) +{ + struct slh_address_hash ah = + { + bswap32_if_le (SLH_FORS_PRF), + bswap32_if_le (ctx->pub.keypair), + 0, + bswap32_if_le(idx), + }; + assert (idx < (FORS_K << FORS_A)); + + _slh_shake (ctx->pub.seed, &ctx->pub.at, &ah, ctx->secret_seed, sk); + + ah.type = bswap32_if_le (SLH_FORS_TREE); + _slh_shake (ctx->pub.seed, &ctx->pub.at, &ah, sk, leaf); +} + +static void +fors_leaf (const struct slh_merkle_ctx_secret *ctx, unsigned idx, uint8_t *out) +{ + _fors_gen (ctx, idx, out, out); +} + +static void +fors_node (const struct slh_merkle_ctx_public *ctx, unsigned height, unsigned index, + const uint8_t *left, const uint8_t *right, uint8_t *out) +{ + struct sha3_256_ctx sha3; + struct slh_address_hash ah = + { + bswap32_if_le (SLH_FORS_TREE), + bswap32_if_le (ctx->keypair), + bswap32_if_le (height), + bswap32_if_le (index), + }; + _slh_shake_init (&sha3, ctx->seed, &ctx->at, &ah); + sha3_256_update (&sha3, _SLH_DSA_128_SIZE, left); + sha3_256_update (&sha3, _SLH_DSA_128_SIZE, right); + sha3_256_shake (&sha3, _SLH_DSA_128_SIZE, out); +} + +static void +fors_sign_one (const struct slh_merkle_ctx_secret *ctx, + unsigned idx, uint8_t *signature, struct sha3_256_ctx *pub) +{ + uint8_t hash[_SLH_DSA_128_SIZE]; + assert (idx < (FORS_K << FORS_A)); + + _fors_gen (ctx, idx, signature, hash); + + _merkle_sign (ctx, fors_leaf, fors_node, FORS_A, idx, + signature + _SLH_DSA_128_SIZE); + _merkle_verify (&ctx->pub, fors_node, FORS_A, idx, signature + _SLH_DSA_128_SIZE, hash); + + sha3_256_update (pub, _SLH_DSA_128_SIZE, hash); +} + +void +_fors_sign (const struct slh_merkle_ctx_secret *ctx, + const uint8_t *msg, uint8_t *signature, uint8_t *pub) +{ + struct slh_address_hash ah = + { + bswap32_if_le(SLH_FORS_ROOTS), + bswap32_if_le(ctx->pub.keypair), + 0, 0, + }; + struct sha3_256_ctx sha3; + unsigned i; + + assert (FORS_A == 12); /* Specialized code */ + + _slh_shake_init (&sha3, ctx->pub.seed, &ctx->pub.at, &ah); + + for (i = 0; i < FORS_K; i += 2, msg += 3, signature += 2*(FORS_A + 1) * _SLH_DSA_128_SIZE) + { + unsigned m0 = ((unsigned) msg[0] << 4) + (msg[1] >> 4); + unsigned m1 = ((msg[1] & 0xf) << 8) + msg[2]; + fors_sign_one (ctx, (i << FORS_A) + m0, signature, &sha3); + fors_sign_one (ctx,((i+1) << FORS_A) + m1, + signature + (FORS_A + 1) * _SLH_DSA_128_SIZE, &sha3); + } + + sha3_256_shake (&sha3, _SLH_DSA_128_SIZE, pub); +} + +static void +fors_verify_one (const struct slh_merkle_ctx_public *ctx, + unsigned idx, const uint8_t *signature, struct sha3_256_ctx *pub) +{ + uint8_t root[_SLH_DSA_128_SIZE]; + struct slh_address_hash ah = + { + bswap32_if_le (SLH_FORS_TREE), + bswap32_if_le (ctx->keypair), + 0, + bswap32_if_le(idx), + }; + assert (idx < (FORS_K << FORS_A)); + + _slh_shake (ctx->seed, &ctx->at, &ah, signature, root); + _merkle_verify (ctx, fors_node, FORS_A, idx, signature + _SLH_DSA_128_SIZE, root); + + sha3_256_update (pub, _SLH_DSA_128_SIZE, root); +} + +void +_fors_verify (const struct slh_merkle_ctx_public *ctx, + const uint8_t *msg, const uint8_t *signature, uint8_t *pub) +{ + struct sha3_256_ctx sha3; + unsigned i; + struct slh_address_hash ah = + { + bswap32_if_le (SLH_FORS_ROOTS), + bswap32_if_le (ctx->keypair), + 0, 0, + }; + + assert (FORS_A == 12); /* Specialized code */ + + _slh_shake_init (&sha3, ctx->seed, &ctx->at, &ah); + + for (i = 0; i < FORS_K; i += 2, msg += 3, signature += 2*(FORS_A + 1) * _SLH_DSA_128_SIZE) + { + unsigned m0 = ((unsigned) msg[0] << 4) + (msg[1] >> 4); + unsigned m1 = ((msg[1] & 0xf) << 8) + msg[2]; + fors_verify_one (ctx, (i << FORS_A) + m0, signature, &sha3); + fors_verify_one (ctx, ((i+1) << FORS_A) + m1, + signature + (FORS_A + 1) * _SLH_DSA_128_SIZE, &sha3); + } + sha3_256_shake (&sha3, _SLH_DSA_128_SIZE, pub); +} diff --git a/slh-merkle.c b/slh-merkle.c new file mode 100644 index 00000000..5a611d4e --- /dev/null +++ b/slh-merkle.c @@ -0,0 +1,123 @@ +/* slh-merkle.c + + Copyright (C) 2025 Niels Möller + + This file is part of GNU Nettle. + + GNU Nettle is free software: you can redistribute it and/or + modify it under the terms of either: + + * the GNU Lesser General Public License as published by the Free + Software Foundation; either version 3 of the License, or (at your + option) any later version. + + or + + * the GNU General Public License as published by the Free + Software Foundation; either version 2 of the License, or (at your + option) any later version. + + or both in parallel, as here. + + GNU Nettle is distributed in the hope that it will be useful, + but WITHOUT ANY WARRANTY; without even the implied warranty of + MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU + General Public License for more details. + + You should have received copies of the GNU General Public License and + the GNU Lesser General Public License along with this program. If + not, see http://www.gnu.org/licenses/. +*/ + +#if HAVE_CONFIG_H +# include "config.h" +#endif + +#include <assert.h> + +#include "slh-dsa-internal.h" + +/* Computes root hash of a tree. + Example for height == 2, 4 entries: + + i = 0 ==> stack: [0], i = 1 + i = 1 ==> stack: [0, 1] ==> [0|1], i = 2 + i = 2 ==> stack: [0|1, 2], i = 3 + i = 3 ==> stack: [0|1, 2, 3] ==> [0|1, 2|3] ==> [0|1|2|3], i = 4 + + The size of the stack equals popcount(i) +*/ +void +_merkle_root (const struct slh_merkle_ctx_secret *ctx, + merkle_leaf_hash_func *leaf_hash, merkle_node_hash_func *node_hash, + unsigned height, unsigned start, uint8_t *root, + /* Must have space for (height + 1) node hashes */ + uint8_t *stack) +{ + unsigned stack_size = 0; + unsigned i; + assert (height > 0); + assert ( (start & ((1<<height) - 1)) == 0); + + for (i = 0; i < (1<<height); i++) + { + /* Leaf index. */ + unsigned idx = start + i; + unsigned h; + assert (stack_size <= height); + + leaf_hash (ctx, idx, stack + stack_size++ * _SLH_DSA_128_SIZE); + + for (h = 1; (idx&1); h++) + { + assert (stack_size >= 2); + idx >>= 1; + stack_size--; + if (h == height) + { + assert (stack_size == 1); + node_hash (&ctx->pub, h, idx, + stack + (stack_size - 1) * _SLH_DSA_128_SIZE, + stack + stack_size * _SLH_DSA_128_SIZE, + root); + return; + } + node_hash (&ctx->pub, h, idx, + stack + (stack_size - 1) * _SLH_DSA_128_SIZE, + stack + stack_size * _SLH_DSA_128_SIZE, + stack + (stack_size - 1)* _SLH_DSA_128_SIZE); + } + } +} + +void +_merkle_sign (const struct slh_merkle_ctx_secret *ctx, + merkle_leaf_hash_func *leaf_hash, merkle_node_hash_func *node_hash, + unsigned height, unsigned idx, uint8_t *signature) +{ + unsigned h; + /* By generating the path from the end, we can use the output area + as the temporary stack. */ + for (h = height; --h > 0;) + _merkle_root (ctx, leaf_hash, node_hash, h, (idx & -(1 << h)) ^ (1 << h), + signature + h*_SLH_DSA_128_SIZE, signature); + + leaf_hash (ctx, idx ^ 1, signature); +} + +void +_merkle_verify (const struct slh_merkle_ctx_public *ctx, merkle_node_hash_func *node_hash, + unsigned height, unsigned idx, const uint8_t *signature, uint8_t *hash) +{ + unsigned h; + + for (h = 1; h <= height; h++, signature += _SLH_DSA_128_SIZE) + { + unsigned right = idx & 1; + idx >>= 1; + if (right) + node_hash (ctx, h, idx, signature, hash, hash); + else + node_hash (ctx, h, idx, hash, signature, hash); + } +} diff --git a/slh-shake.c b/slh-shake.c new file mode 100644 index 00000000..83dbe9de --- /dev/null +++ b/slh-shake.c @@ -0,0 +1,58 @@ +/* slh-prf.c + + Copyright (C) 2025 Niels Möller + + This file is part of GNU Nettle. + + GNU Nettle is free software: you can redistribute it and/or + modify it under the terms of either: + + * the GNU Lesser General Public License as published by the Free + Software Foundation; either version 3 of the License, or (at your + option) any later version. + + or + + * the GNU General Public License as published by the Free + Software Foundation; either version 2 of the License, or (at your + option) any later version. + + or both in parallel, as here. + + GNU Nettle is distributed in the hope that it will be useful, + but WITHOUT ANY WARRANTY; without even the implied warranty of + MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU + General Public License for more details. + + You should have received copies of the GNU General Public License and + the GNU Lesser General Public License along with this program. If + not, see http://www.gnu.org/licenses/. +*/ + +#if HAVE_CONFIG_H +# include "config.h" +#endif + +#include "sha3.h" +#include "slh-dsa-internal.h" + +void +_slh_shake_init (struct sha3_256_ctx *ctx, const uint8_t *public_seed, + const struct slh_address_tree *at, const struct slh_address_hash *ah) +{ + sha3_256_init (ctx); + sha3_256_update (ctx, _SLH_DSA_128_SIZE, public_seed); + sha3_256_update (ctx, sizeof(*at), (const uint8_t *) at); + sha3_256_update (ctx, sizeof(*ah), (const uint8_t *) ah); +} + +void +_slh_shake (const uint8_t *public_seed, + const struct slh_address_tree *at, const struct slh_address_hash *ah, + const uint8_t *secret, uint8_t *out) +{ + struct sha3_256_ctx ctx; + _slh_shake_init (&ctx, public_seed, at, ah); + sha3_256_update (&ctx, _SLH_DSA_128_SIZE, secret); + sha3_256_shake (&ctx, _SLH_DSA_128_SIZE, out); +} diff --git a/slh-wots.c b/slh-wots.c new file mode 100644 index 00000000..a74d84dd --- /dev/null +++ b/slh-wots.c @@ -0,0 +1,209 @@ +/* slh-wots.c + + WOTS+ one-time signatures, part of SLH-DSA (FIPS 205) + + Copyright (C) 2025 Niels Möller + + This file is part of GNU Nettle. + + GNU Nettle is free software: you can redistribute it and/or + modify it under the terms of either: + + * the GNU Lesser General Public License as published by the Free + Software Foundation; either version 3 of the License, or (at your + option) any later version. + + or + + * the GNU General Public License as published by the Free + Software Foundation; either version 2 of the License, or (at your + option) any later version. + + or both in parallel, as here. + + GNU Nettle is distributed in the hope that it will be useful, + but WITHOUT ANY WARRANTY; without even the implied warranty of + MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU + General Public License for more details. + + You should have received copies of the GNU General Public License and + the GNU Lesser General Public License along with this program. If + not, see http://www.gnu.org/licenses/. +*/ + +#if HAVE_CONFIG_H +# include "config.h" +#endif + +#include "slh-dsa-internal.h" + +#include "sha3.h" +#include "bswap-internal.h" + +/* If s == 0, returns src and leaves dst unchanged. Otherwise, returns + dst. For the ah argument, leaves ah->keypair and ah->height_chain + unchanged, but overwrites the other fields. */ +static const uint8_t * +wots_chain (const uint8_t *public_seed, const struct slh_address_tree *at, + struct slh_address_hash *ah, + unsigned i, unsigned s, + const uint8_t *src, uint8_t *dst) +{ + unsigned j; + + if (s == 0) + return src; + + ah->type = bswap32_if_le (SLH_WOTS_HASH); + ah->index_hash = bswap32_if_le(i); + + _slh_shake (public_seed, at, ah, src, dst); + + for (j = 1; j < s; j++) + { + ah->index_hash = bswap32_if_le(i + j); + _slh_shake (public_seed, at, ah, dst, dst); + } + + return dst; +} + +static void +wots_pk_init (const uint8_t *public_seed, const struct slh_address_tree *at, + unsigned keypair, struct slh_address_hash *ah, struct sha3_256_ctx *ctx) +{ + ah->type = bswap32_if_le (SLH_WOTS_PK); + ah->keypair = bswap32_if_le (keypair); + ah->height_chain = 0; + ah->index_hash = 0; + + _slh_shake_init (ctx, public_seed, at, ah); +} + +void +_wots_gen (const uint8_t *public_seed, const uint8_t *secret_seed, const struct slh_address_tree *at, + uint32_t keypair, uint8_t *pub) +{ + struct slh_address_hash ah; + struct sha3_256_ctx ctx; + unsigned i; + + wots_pk_init (public_seed, at, keypair, &ah, &ctx); + + for (i = 0; i < _WOTS_SIGNATURE_LENGTH; i++) + { + uint8_t out[_SLH_DSA_128_SIZE]; + + /* Generate secret value. */ + ah.type = bswap32_if_le (SLH_WOTS_PRF); + ah.height_chain = bswap32_if_le(i); + ah.index_hash = 0; + _slh_shake (public_seed, at, &ah, secret_seed, out); + + /* Hash chain. */ + wots_chain (public_seed, at, &ah, 0, 15, out, out); + + sha3_256_update (&ctx, _SLH_DSA_128_SIZE, out); + } + sha3_256_shake (&ctx, _SLH_DSA_128_SIZE, pub); +} + +/* Produces signature hash corresponding to the ith message nybble. Modifies addr. */ +static void +wots_sign_one (const uint8_t *public_seed, + const uint8_t *secret_seed, const struct slh_address_tree *at, + uint32_t keypair, + unsigned i, uint8_t msg, uint8_t *sig, struct sha3_256_ctx *ctx) +{ + struct slh_address_hash ah; + uint8_t pub[_SLH_DSA_128_SIZE]; + sig += i*_SLH_DSA_128_SIZE; + + /* Generate secret value. */ + ah.type = bswap32_if_le (SLH_WOTS_PRF); + ah.keypair = bswap32_if_le (keypair); + ah.height_chain = bswap32_if_le(i); + ah.index_hash = 0; + _slh_shake (public_seed, at, &ah, secret_seed, sig); + + /* Hash chain. */ + wots_chain (public_seed, at, &ah, 0, msg, sig, sig); + + sha3_256_update (ctx, _SLH_DSA_128_SIZE, + wots_chain (public_seed, at, &ah, msg, 15 - msg, sig, pub)); +} + +void +_wots_sign (const uint8_t *public_seed, const uint8_t *secret_seed, const struct slh_address_tree *at, + unsigned keypair, const uint8_t *msg, uint8_t *signature, uint8_t *pub) +{ + struct slh_address_hash ah; + struct sha3_256_ctx ctx; + unsigned i; + uint32_t csum; + + wots_pk_init (public_seed, at, keypair, &ah, &ctx); + + for (i = 0, csum = 15*32; i < _SLH_DSA_128_SIZE; i++) + { + uint8_t m0, m1; + m0 = msg[i] >> 4; + csum -= m0; + wots_sign_one(public_seed, secret_seed, at, keypair, 2*i, m0, signature, &ctx); + + m1 = msg[i] & 0xf; + csum -= m1; + wots_sign_one(public_seed, secret_seed, at, keypair, 2*i + 1, m1, signature, &ctx); + } + + wots_sign_one (public_seed, secret_seed, at, keypair, 32, csum >> 8, signature, &ctx); + wots_sign_one (public_seed, secret_seed, at, keypair, 33, (csum >> 4) & 0xf, signature, &ctx); + wots_sign_one (public_seed, secret_seed, at, keypair, 34, csum & 0xf, signature, &ctx); + + sha3_256_shake (&ctx, _SLH_DSA_128_SIZE, pub); +} + +static void +wots_verify_one (struct sha3_256_ctx *ctx, const uint8_t *public_seed, const struct slh_address_tree *at, + uint32_t keypair, unsigned i, uint8_t msg, const uint8_t *signature) +{ + struct slh_address_hash ah; + uint8_t out[_SLH_DSA_128_SIZE]; + signature += i*_SLH_DSA_128_SIZE; + + ah.keypair = bswap32_if_le (keypair); + ah.height_chain = bswap32_if_le(i); + + sha3_256_update (ctx, _SLH_DSA_128_SIZE, + wots_chain (public_seed, at, &ah, msg, 15 - msg, signature, out)); +} + +void +_wots_verify (const uint8_t *public_seed, const struct slh_address_tree *at, + unsigned keypair, const uint8_t *msg, const uint8_t *signature, uint8_t *pub) +{ + struct slh_address_hash ah; + struct sha3_256_ctx ctx; + unsigned i; + uint32_t csum; + + wots_pk_init (public_seed, at, keypair, &ah, &ctx); + + for (i = 0, csum = 15*32; i < _SLH_DSA_128_SIZE; i++) + { + uint8_t m0, m1; + m0 = msg[i] >> 4; + csum -= m0; + wots_verify_one(&ctx, public_seed, at, keypair, 2*i, m0, signature); + + m1 = msg[i] & 0xf; + csum -= m1; + wots_verify_one(&ctx, public_seed, at, keypair, 2*i + 1, m1, signature); + } + + wots_verify_one (&ctx, public_seed, at, keypair, 32, csum >> 8, signature); + wots_verify_one (&ctx, public_seed, at, keypair, 33, (csum >> 4) & 0xf, signature); + wots_verify_one (&ctx, public_seed, at, keypair, 34, csum & 0xf, signature); + + sha3_256_shake (&ctx, _SLH_DSA_128_SIZE, pub); +} diff --git a/slh-xmss.c b/slh-xmss.c new file mode 100644 index 00000000..1f0a36bc --- /dev/null +++ b/slh-xmss.c @@ -0,0 +1,104 @@ +/* slh-xmss.c + + The eXtended Merkle Signature Scheme, part of SLH-DSA (FIPS 205) + + Copyright (C) 2025 Niels Möller + + This file is part of GNU Nettle. + + GNU Nettle is free software: you can redistribute it and/or + modify it under the terms of either: + + * the GNU Lesser General Public License as published by the Free + Software Foundation; either version 3 of the License, or (at your + option) any later version. + + or + + * the GNU General Public License as published by the Free + Software Foundation; either version 2 of the License, or (at your + option) any later version. + + or both in parallel, as here. + + GNU Nettle is distributed in the hope that it will be useful, + but WITHOUT ANY WARRANTY; without even the implied warranty of + MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU + General Public License for more details. + + You should have received copies of the GNU General Public License and + the GNU Lesser General Public License along with this program. If + not, see http://www.gnu.org/licenses/. +*/ + +#if HAVE_CONFIG_H +# include "config.h" +#endif + +#include "bswap-internal.h" +#include "sha3.h" +#include "slh-dsa-internal.h" + +static void +xmss_leaf (const struct slh_merkle_ctx_secret *ctx, unsigned idx, uint8_t *leaf) +{ + _wots_gen (ctx->pub.seed, ctx->secret_seed, &ctx->pub.at, idx, leaf); +} + +static void +xmss_node (const struct slh_merkle_ctx_public *ctx, unsigned height, unsigned index, + const uint8_t *left, const uint8_t *right, uint8_t *out) +{ + struct sha3_256_ctx sha3; + struct slh_address_hash ah = + { + bswap32_if_le (SLH_XMSS_TREE), + 0, + bswap32_if_le (height), + bswap32_if_le (index), + }; + + _slh_shake_init (&sha3, ctx->seed, &ctx->at, &ah); + sha3_256_update (&sha3, _SLH_DSA_128_SIZE, left); + sha3_256_update (&sha3, _SLH_DSA_128_SIZE, right); + sha3_256_shake (&sha3, _SLH_DSA_128_SIZE, out); +} + +void +_xmss_gen (const uint8_t *public_seed, const uint8_t *secret_seed, + uint8_t *root) +{ + struct slh_merkle_ctx_secret ctx = + { + { + public_seed, + /* Everything zero, except layer and type. */ + { bswap32_if_le(SLH_DSA_D-1), 0, 0, } , + 0, + }, + secret_seed + }; + uint8_t stack[(XMSS_H + 1)*_SLH_DSA_128_SIZE]; + _merkle_root (&ctx, xmss_leaf, xmss_node, XMSS_H, 0, root, stack); +} + +void +_xmss_sign (const struct slh_merkle_ctx_secret *ctx, + unsigned idx, const uint8_t *msg, uint8_t *signature, uint8_t *pub) +{ + _wots_sign (ctx->pub.seed, ctx->secret_seed, &ctx->pub.at, idx, msg, signature, pub); + signature += WOTS_SIGNATURE_SIZE; + + _merkle_sign (ctx, xmss_leaf, xmss_node, XMSS_H, idx, signature); + _merkle_verify (&ctx->pub, xmss_node, XMSS_H, idx, signature, pub); +} + +void +_xmss_verify (const struct slh_merkle_ctx_public *ctx, + unsigned idx, const uint8_t *msg, const uint8_t *signature, uint8_t *pub) +{ + _wots_verify (ctx->seed, &ctx->at, idx, msg, signature, pub); + signature += WOTS_SIGNATURE_SIZE; + + _merkle_verify (ctx, xmss_node, XMSS_H, idx, signature, pub); +}
1. The slh_dsa_shake_128s_root seems to serve the same purpose as the slh_keygen_internal function in the spec. The spec says: "
*Other than for testing purposes, the interfaces for key generation and signature generationspecified in this section should not be made available to applications, as any random valuesrequired for key generation and signature generation shall be generated by the cryptographicmodule*". So perhaps slh_dsa_shake_128s_root should not be exposed as a public API function. Otherwise, the API looks good. Eventually there should also be the pre-hash variants for sign and verify present in the API.
2. I think first there should be at least one fast and short option available. * More security/speed/size variants, initial implementation only has one of the six {128,192,256}{s,f}? I don't have an order preference for the other points.
3. I cannot tell. I think you would need to propagate specific sizes for different parameter sets anyway.
Regards, Zoltan
On Fri, Feb 14, 2025 at 9:59 PM Niels Möller nisse@lysator.liu.se wrote:
Zoltan Fridrich zfridric@redhat.com writes:
Should the API have pk,sk,sig size functions for every parameter set?
I think the base api should be constants (#define) for each variant. If useful, one could add some kind of struct representing a signature algorithm, similar in spirit to struct nettle_mac.
I have seen progression on https://git.lysator.liu.se/nisse/poc-slh-dsa/-/tree/main so I am not
sure
whether you plan to use this patch or whether you would like to use your own slh-dsa nettle implementation?
First, I want to say that even if your patch doesn't end up in Nettle, it has been very helpful to have your working code when debugging my implementation: most of my unit tests are based on running your code under gdb and examining input and output values of relevant parts, and when I got wrong output, I've been able to compared behavior step by step. It's been fun to look into slh-dsa.
I'm leaning towards using my implementation. I've pushed a sligthly cleaned up version to the branch slh-dsa-shake-128s in the nettle repo (also appended below as a patch, excluding the tests and ChangeLog). I think main technical benefit is that I've tried harder do avoid temporary allocation and copies. I'm also thinking of the potential of generalizing the merkle tree utilities for other applications, e.g., transparency logs.
That said, there's going to be some additional complexity when adding support for additional variants.
Questions for you as well as for others on the list:
Does the public api look reasonable? Four functions, slh_dsa_shake_128s_root, slh_dsa_shake_128s_generate_keypair, slh_dsa_shake_128s_sign, slh_dsa_shake_128s_verify.
What should be the order and priorities when adding additional features?
More security/speed/size variants, initial implementation only has one of the six {128,192,256}{s,f}?
Add sha2 variants (rather than sha3 shake only)?
Add support for non-empty context string?
Add support for prehash variants?
Add support for non-deterministic variants?
It's unclear to me which features are most relevant for applications, but I think it makes sense to add only the most important right away, and add additional features later, when real use cases appear.
Does the implementation choices look reasonable, or will it fall apart when generalizing to support more variants?
Before adding more features, I would also like to add (1) tests for proper side-channel silence, and (2) benchmarks. And as soon as the dust has settled on the public API, docs are also rather important.
Regards, /Niels
diff --git a/Makefile.in b/Makefile.in index 71ad761e..6b3f4c1e 100644 --- a/Makefile.in +++ b/Makefile.in @@ -226,7 +226,9 @@ hogweed_SOURCES = sexp.c sexp-format.c \ ed25519-sha512.c ed25519-sha512-pubkey.c \ ed25519-sha512-sign.c ed25519-sha512-verify.c \ ed448-shake256.c ed448-shake256-pubkey.c \
ed448-shake256-sign.c ed448-shake256-verify.c
ed448-shake256-sign.c ed448-shake256-verify.c \slh-fors.c slh-merkle.c slh-shake.c slh-wots.cslh-xmss.c \
slh-dsa-shake-128s.cOPT_SOURCES = fat-arm.c fat-arm64.c fat-ppc.c fat-s390x.c fat-x86_64.c mini-gmp.c
@@ -246,7 +248,7 @@ HEADERS = aes.h arcfour.h arctwo.h asn1.h blowfish.h balloon.h \ ocb.h pbkdf2.h \ pgp.h pkcs1.h pss.h pss-mgf1.h realloc.h ripemd160.h rsa.h \ salsa20.h sexp.h serpent.h \
sha.h sha1.h sha2.h sha3.h sm3.h sm4.h streebog.h twofish.h \
sha.h sha1.h sha2.h sha3.h slh-dsa.h sm3.h sm4.h streebog.htwofish.h \ umac.h yarrow.h xts.h poly1305.h nist-keywrap.h \ drbg-ctr.h
@@ -279,6 +281,7 @@ DISTFILES = $(SOURCES) $(HEADERS) getopt.h getopt_int.h \ ctr-internal.h chacha-internal.h sha3-internal.h \ salsa20-internal.h umac-internal.h hogweed-internal.h \ rsa-internal.h pkcs1-internal.h dsa-internal.h eddsa-internal.h \
slh-dsa-internal.h \ gmp-glue.h ecc-internal.h fat-setup.h oaep.h \ mini-gmp.h asm.m4 m4-utils.m4 \ nettle.texinfo nettle.info nettle.html nettle.pdf sha-example.cdiff --git a/slh-dsa-internal.h b/slh-dsa-internal.h new file mode 100644 index 00000000..ed42ef2e --- /dev/null +++ b/slh-dsa-internal.h @@ -0,0 +1,193 @@ +/* slh-dsa-internal.h
- Copyright (C) 2025 Niels Möller
- This file is part of GNU Nettle.
- GNU Nettle is free software: you can redistribute it and/or
- modify it under the terms of either:
* the GNU Lesser General Public License as published by the FreeSoftware Foundation; either version 3 of the License, or (at youroption) any later version.- or
* the GNU General Public License as published by the FreeSoftware Foundation; either version 2 of the License, or (at youroption) any later version.- or both in parallel, as here.
- GNU Nettle is distributed in the hope that it will be useful,
- but WITHOUT ANY WARRANTY; without even the implied warranty of
- MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
- General Public License for more details.
- You should have received copies of the GNU General Public License and
- the GNU Lesser General Public License along with this program. If
- not, see http://www.gnu.org/licenses/.
+*/
+#ifndef NETTLE_SLH_DSA_INTERNAL_H_INCLUDED +#define NETTLE_SLH_DSA_INTERNAL_H_INCLUDED
+#include <stdint.h>
+/* Name mangling */ +#define _slh_shake_init _nettle_slh_shake_init +#define _slh_shake _nettle_slh_shake +#define _wots_gen _nettle_wots_gen +#define _wots_sign _nettle_wots_sign +#define _wots_verify _nettle_wots_verify +#define _merkle_root _nettle_merkle_root +#define _merkle_sign _nettle_merkle_sign +#define _merkle_verify _nettle_merkle_verify +#define _fors_gen _nettle_fors_gen +#define _fors_sign _nettle_fors_sign +#define _fors_verify _nettle_fors_verify +#define _xmss_gen _nettle_xmss_gen +#define _xmss_sign _nettle_xmss_sign +#define _xmss_verify _nettle_xmss_verify
+/* Size of a single hash, including the seed and prf parameters */ +#define _SLH_DSA_128_SIZE 16
+#define SLH_DSA_D 7 +#define SLH_DSA_M 30
+/* Fields always big-endian */ +struct slh_address_tree +{
- uint32_t layer;
- uint32_t pad; /* Always zero */
- uint64_t tree_idx;
+};
+/* Fields always big-endian */ +struct slh_address_hash +{
- uint32_t type;
- uint32_t keypair;
- /* height for XMSS_TREE and FORS_TREE, chain address for WOTS_HASH. */
- uint32_t height_chain;
- /* index for XMSS_TREE and FORS_TREE, hash address for WOTS_HASH. */
- uint32_t index_hash;
+};
+enum slh_addr_type
- {
- SLH_WOTS_HASH = 0,
- SLH_WOTS_PK = 1,
- SLH_XMSS_TREE = 2,
- SLH_FORS_TREE = 3,
- SLH_FORS_ROOTS = 4,
- SLH_WOTS_PRF = 5,
- SLH_FORS_PRF = 6,
- };
+struct slh_merkle_ctx_public +{
- const uint8_t *seed;
- struct slh_address_tree at;
- unsigned keypair; /* Used only by fors_leaf and fors_node. */
+};
+struct slh_merkle_ctx_secret +{
- struct slh_merkle_ctx_public pub;
- const uint8_t *secret_seed;
+};
+struct sha3_256_ctx; +void +_slh_shake_init (struct sha3_256_ctx *ctx, const uint8_t *public_seed,
const struct slh_address_tree *at, const structslh_address_hash *ah); +void +_slh_shake (const uint8_t *public_seed,
const struct slh_address_tree *at, const structslh_address_hash *ah,
const uint8_t *secret, uint8_t *out);+#define _WOTS_SIGNATURE_LENGTH 35 +/* 560 bytes */ +#define WOTS_SIGNATURE_SIZE (_WOTS_SIGNATURE_LENGTH*_SLH_DSA_128_SIZE)
+void +_wots_gen (const uint8_t *public_seed, const uint8_t *secret_seed, const struct slh_address_tree *at,
uint32_t keypair, uint8_t *pub);+void +_wots_sign (const uint8_t *public_seed, const uint8_t *secret_seed, const struct slh_address_tree *at,
unsigned keypair, const uint8_t *msg, uint8_t *signature,uint8_t *pub);
+/* Computes candidate public key from signature. */ +void +_wots_verify (const uint8_t *public_seed, const struct slh_address_tree *at,
unsigned keypair, const uint8_t *msg, const uint8_t*signature, uint8_t *pub);
+/* Merkle tree functions. Could be generalized for other merkle tree
- applications, by using const void* for the ctx argument. */
+typedef void merkle_leaf_hash_func (const struct slh_merkle_ctx_secret *ctx, unsigned index, uint8_t *out); +typedef void merkle_node_hash_func (const struct slh_merkle_ctx_public *ctx, unsigned height, unsigned index,
const uint8_t *left, const uint8_t*right, uint8_t *out);
+void +_merkle_root (const struct slh_merkle_ctx_secret *ctx,
merkle_leaf_hash_func *leaf_hash, merkle_node_hash_func*node_hash,
unsigned height, unsigned start, uint8_t *root,/* Must have space for (height + 1) node hashes */uint8_t *stack);+void +_merkle_sign (const struct slh_merkle_ctx_secret *ctx,
merkle_leaf_hash_func *leaf_hash, merkle_node_hash_func*node_hash,
unsigned height, unsigned idx, uint8_t *signature);+/* The hash argument is both input (leaf hash to be verified) and output (resulting root hash). */ +void +_merkle_verify (const struct slh_merkle_ctx_public *ctx, merkle_node_hash_func *node_hash,
unsigned height, unsigned idx, const uint8_t *signature,uint8_t *hash);
+/* Use k Merkle trees, each of size 2^a. Signs messages of size
- k * a = 168 bits or 21 octets. */
+#define FORS_A 12 +#define FORS_K 14
+#define FORS_MSG_SIZE 21 +/* 2912 bytes */ +#define FORS_SIGNATURE_SIZE (FORS_K * (FORS_A + 1) * _SLH_DSA_128_SIZE)
+/* Generates a single secret value, and corresponding leaf hash. */ +void +_fors_gen (const struct slh_merkle_ctx_secret *ctx, unsigned index, uint8_t *sk, uint8_t *leaf);
+/* Computes a fors signature as well as the public key. */ +void +_fors_sign (const struct slh_merkle_ctx_secret *fors_ctx,
const uint8_t *msg, uint8_t *signature, uint8_t *pub);+/* Computes candidate public key from signature. */ +void +_fors_verify (const struct slh_merkle_ctx_public *ctx,
const uint8_t *msg, const uint8_t *signature, uint8_t *pub);+#define XMSS_H 9 +/* Just the auth path, excluding the wots signature, 144 bytes. */ +#define XMSS_AUTH_SIZE (XMSS_H * _SLH_DSA_128_SIZE) +#define XMSS_SIGNATURE_SIZE (WOTS_SIGNATURE_SIZE + XMSS_AUTH_SIZE)
+void +_xmss_gen (const uint8_t *public_seed, const uint8_t *secret_seed,
uint8_t *root);+/* Signs using wots, then signs wots public key using xmss. Also
- returns the xmss public key (i.e., root hash).*/
+void +_xmss_sign (const struct slh_merkle_ctx_secret *ctx,
unsigned idx, const uint8_t *msg, uint8_t *signature, uint8_t*pub);
+void +_xmss_verify (const struct slh_merkle_ctx_public *ctx,
unsigned idx, const uint8_t *msg, const uint8_t *signature,uint8_t *pub);
+#endif /* NETTLE_SLH_DSA_INTERNAL_H_INCLUDED */ diff --git a/slh-dsa-shake-128s.c b/slh-dsa-shake-128s.c new file mode 100644 index 00000000..1e1aa63b --- /dev/null +++ b/slh-dsa-shake-128s.c @@ -0,0 +1,200 @@ +/* slh-dsa-shake-128s.c
- SLH-DSA (FIPS 205) signatures.
- Copyright (C) 2025 Niels Möller
- This file is part of GNU Nettle.
- GNU Nettle is free software: you can redistribute it and/or
- modify it under the terms of either:
* the GNU Lesser General Public License as published by the FreeSoftware Foundation; either version 3 of the License, or (at youroption) any later version.- or
* the GNU General Public License as published by the FreeSoftware Foundation; either version 2 of the License, or (at youroption) any later version.- or both in parallel, as here.
- GNU Nettle is distributed in the hope that it will be useful,
- but WITHOUT ANY WARRANTY; without even the implied warranty of
- MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
- General Public License for more details.
- You should have received copies of the GNU General Public License and
- the GNU Lesser General Public License along with this program. If
- not, see http://www.gnu.org/licenses/.
+*/
+#if HAVE_CONFIG_H +# include "config.h" +#endif
+#include <assert.h> +#include <string.h>
+#include "bswap-internal.h" +#include "memops.h" +#include "sha3.h" +#include "slh-dsa.h" +#include "slh-dsa-internal.h"
+void +slh_dsa_shake_128s_root (const uint8_t *public_seed, const uint8_t *private_seed,
uint8_t *root)+{
- _xmss_gen (public_seed, private_seed, root);
+}
+void +slh_dsa_shake_128s_generate_keypair (uint8_t *pub, uint8_t *priv,
void *random_ctx, nettle_random_func*random) +{
- random (random_ctx, SLH_DSA_SHAKE_128S_SEED_SIZE, pub);
- random (random_ctx, 2*SLH_DSA_SHAKE_128S_SEED_SIZE, priv);
- slh_dsa_shake_128s_root (pub, priv, pub + SLH_DSA_SHAKE_128S_SEED_SIZE);
+}
+static const uint8_t slh_pure_prefix[2] = {0, 0};
+static void +slh_digest (struct sha3_256_ctx *ctx,
const uint8_t *randomizer, const uint8_t *pub,size_t length, const uint8_t *msg,uint8_t *digest, uint64_t *tree_idx, unsigned *leaf_idx)+{
- uint64_t x;
- unsigned i;
- sha3_256_update (ctx, _SLH_DSA_128_SIZE, randomizer);
- sha3_256_update (ctx, 2*_SLH_DSA_128_SIZE, pub);
- sha3_256_update (ctx, sizeof(slh_pure_prefix), slh_pure_prefix);
- sha3_256_update (ctx, length, msg);
- sha3_256_shake (ctx, SLH_DSA_M, digest);
- /* Split digest as
+----+------+-----+| md | tree | leaf|+----+------+-----+21 7 2- The first 21 octets are the digest signed with fors, the next 7
- octets represent 54 bits selecting the tree, the last 2 octets
- represent 9 bits selecting the key in that tree.
- Left over high bits are discarded.
- */
- x = digest[21] & 0x3f; /* Discard 2 high-most bits of 56 */
- for (i = 22; i < 28; i++)
- x = (x << 8) + digest[i];
- *tree_idx = x;
- /* Discard 7 high-most bits of 16 */
- *leaf_idx = ((digest[28] & 1) << 8) + digest[29];
+}
+/* Only the "pure" and deterministic variant. */ +void +slh_dsa_shake_128s_sign (const uint8_t *pub, const uint8_t *priv,
size_t length, const uint8_t *msg,uint8_t *signature)+{
- struct sha3_256_ctx ctx;
- uint8_t digest[SLH_DSA_M];
- uint8_t root[_SLH_DSA_128_SIZE];
- uint64_t tree_idx;
- unsigned leaf_idx;
- int i;
- struct slh_merkle_ctx_secret merkle_ctx =
- {
{pub, { 0, }, 0,},priv,- };
- /* First the "randomizer" */
- sha3_256_init (&ctx);
- sha3_256_update (&ctx, _SLH_DSA_128_SIZE, priv + _SLH_DSA_128_SIZE);
- sha3_256_update (&ctx, _SLH_DSA_128_SIZE, pub);
- sha3_256_update (&ctx, sizeof(slh_pure_prefix), slh_pure_prefix);
- sha3_256_update (&ctx, length, msg);
- sha3_256_shake (&ctx, _SLH_DSA_128_SIZE, signature);
- slh_digest (&ctx, signature, pub, length, msg, digest, &tree_idx,
&leaf_idx);
- signature += _SLH_DSA_128_SIZE;
- merkle_ctx.pub.at.tree_idx = bswap64_if_le (tree_idx);
- merkle_ctx.pub.keypair = leaf_idx;
- _fors_sign (&merkle_ctx, digest, signature, root);
- signature += FORS_SIGNATURE_SIZE;
- _xmss_sign (&merkle_ctx, leaf_idx, root, signature, root);
- for (i = 1; i < SLH_DSA_D; i++)
- {
signature += XMSS_SIGNATURE_SIZE;leaf_idx = tree_idx & ((1<< XMSS_H) - 1);tree_idx >>= XMSS_H;merkle_ctx.pub.at.layer = bswap32_if_le(i);merkle_ctx.pub.at.tree_idx = bswap64_if_le (tree_idx);_xmss_sign (&merkle_ctx, leaf_idx, root, signature, root);- }
- assert (memeql_sec (root, pub + _SLH_DSA_128_SIZE, sizeof(root)));
+}
+int +slh_dsa_shake_128s_verify (const uint8_t *pub,
size_t length, const uint8_t *msg,const uint8_t *signature)+{
- struct sha3_256_ctx ctx;
- uint8_t digest[SLH_DSA_M];
- uint8_t root[_SLH_DSA_128_SIZE];
- uint64_t tree_idx;
- unsigned leaf_idx;
- int i;
- struct slh_merkle_ctx_public merkle_ctx =
- {
pub, { 0, }, 0- };
- sha3_256_init (&ctx);
- slh_digest (&ctx, signature, pub, length, msg, digest, &tree_idx,
&leaf_idx);
- signature += _SLH_DSA_128_SIZE;
- merkle_ctx.at.tree_idx = bswap64_if_le (tree_idx);
- merkle_ctx.keypair = leaf_idx;
- _fors_verify (&merkle_ctx, digest, signature, root);
- signature += FORS_SIGNATURE_SIZE;
- _xmss_verify (&merkle_ctx, leaf_idx, root, signature, root);
- for (i = 1; i < SLH_DSA_D; i++)
- {
signature += XMSS_SIGNATURE_SIZE;leaf_idx = tree_idx & ((1<< XMSS_H) - 1);tree_idx >>= XMSS_H;merkle_ctx.at.layer = bswap32_if_le(i);merkle_ctx.at.tree_idx = bswap64_if_le (tree_idx);_xmss_verify (&merkle_ctx, leaf_idx, root, signature, root);- }
- return memcmp (root, pub + _SLH_DSA_128_SIZE, sizeof(root)) == 0;
+} diff --git a/slh-dsa.h b/slh-dsa.h new file mode 100644 index 00000000..975eb696 --- /dev/null +++ b/slh-dsa.h @@ -0,0 +1,86 @@ +/* slh-dsa.h
- SLH-DSA (FIPS 205) signatures.
- Copyright (C) 2025 Niels Möller
- This file is part of GNU Nettle.
- GNU Nettle is free software: you can redistribute it and/or
- modify it under the terms of either:
* the GNU Lesser General Public License as published by the FreeSoftware Foundation; either version 3 of the License, or (at youroption) any later version.- or
* the GNU General Public License as published by the FreeSoftware Foundation; either version 2 of the License, or (at youroption) any later version.- or both in parallel, as here.
- GNU Nettle is distributed in the hope that it will be useful,
- but WITHOUT ANY WARRANTY; without even the implied warranty of
- MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
- General Public License for more details.
- You should have received copies of the GNU General Public License and
- the GNU Lesser General Public License along with this program. If
- not, see http://www.gnu.org/licenses/.
+*/
+#ifndef NETTLE_SLH_DSA_H +#define NETTLE_SLH_DSA_H
+#include "nettle-types.h"
+#ifdef __cplusplus +extern "C" { +#endif
+/* Name mangling */ +#define slh_dsa_shake_128s_root nettle_slh_dsa_shake_128s_root +#define slh_dsa_shake_128s_generate_keypair nettle_slh_dsa_shake_128s_generate_keypair +#define slh_dsa_shake_128s_sign nettle_slh_dsa_shake_128s_sign +#define slh_dsa_shake_128s_verify nettle_slh_dsa_shake_128s_verify
+/* Key layout:
- private:
secret_seedprf- public:
public_seedroot+*/
+#define SLH_DSA_SHAKE_128S_SEED_SIZE 16 +#define SLH_DSA_SHAKE_128S_KEY_SIZE 32 +#define SLH_DSA_SHAKE_128S_SIGNATURE_SIZE 7856
+/* Computes public key root, from the two seeds. */ +void +slh_dsa_shake_128s_root (const uint8_t *public_seed, const uint8_t *private_seed,
uint8_t *root);+void +slh_dsa_shake_128s_generate_keypair (uint8_t *pub, uint8_t *key,
void *random_ctx, nettle_random_func*random);
+/* Only the "pure" and deterministic variant. */ +void +slh_dsa_shake_128s_sign (const uint8_t *pub, const uint8_t *priv,
size_t length, const uint8_t *msg,uint8_t *signature);+int +slh_dsa_shake_128s_verify (const uint8_t *pub,
size_t length, const uint8_t *msg,const uint8_t *signature);+#ifdef __cplusplus +} +#endif
+#endif /* NETTLE_SLH_DSA_H */ diff --git a/slh-fors.c b/slh-fors.c new file mode 100644 index 00000000..27a31a82 --- /dev/null +++ b/slh-fors.c @@ -0,0 +1,178 @@ +/* slh-fors.c
- Forest of Random Subsets, part of SLH-DSA (FIPS 205)
- Copyright (C) 2025 Niels Möller
- This file is part of GNU Nettle.
- GNU Nettle is free software: you can redistribute it and/or
- modify it under the terms of either:
* the GNU Lesser General Public License as published by the FreeSoftware Foundation; either version 3 of the License, or (at youroption) any later version.- or
* the GNU General Public License as published by the FreeSoftware Foundation; either version 2 of the License, or (at youroption) any later version.- or both in parallel, as here.
- GNU Nettle is distributed in the hope that it will be useful,
- but WITHOUT ANY WARRANTY; without even the implied warranty of
- MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
- General Public License for more details.
- You should have received copies of the GNU General Public License and
- the GNU Lesser General Public License along with this program. If
- not, see http://www.gnu.org/licenses/.
+*/
+#if HAVE_CONFIG_H +# include "config.h" +#endif
+#include <assert.h>
+#include "bswap-internal.h" +#include "sha3.h" +#include "slh-dsa-internal.h"
+void +_fors_gen (const struct slh_merkle_ctx_secret *ctx,
unsigned idx, uint8_t *sk, uint8_t *leaf)+{
- struct slh_address_hash ah =
- {
bswap32_if_le (SLH_FORS_PRF),bswap32_if_le (ctx->pub.keypair),0,bswap32_if_le(idx),- };
- assert (idx < (FORS_K << FORS_A));
- _slh_shake (ctx->pub.seed, &ctx->pub.at, &ah, ctx->secret_seed, sk);
- ah.type = bswap32_if_le (SLH_FORS_TREE);
- _slh_shake (ctx->pub.seed, &ctx->pub.at, &ah, sk, leaf);
+}
+static void +fors_leaf (const struct slh_merkle_ctx_secret *ctx, unsigned idx, uint8_t *out) +{
- _fors_gen (ctx, idx, out, out);
+}
+static void +fors_node (const struct slh_merkle_ctx_public *ctx, unsigned height, unsigned index,
const uint8_t *left, const uint8_t *right, uint8_t *out)+{
- struct sha3_256_ctx sha3;
- struct slh_address_hash ah =
- {
bswap32_if_le (SLH_FORS_TREE),bswap32_if_le (ctx->keypair),bswap32_if_le (height),bswap32_if_le (index),- };
- _slh_shake_init (&sha3, ctx->seed, &ctx->at, &ah);
- sha3_256_update (&sha3, _SLH_DSA_128_SIZE, left);
- sha3_256_update (&sha3, _SLH_DSA_128_SIZE, right);
- sha3_256_shake (&sha3, _SLH_DSA_128_SIZE, out);
+}
+static void +fors_sign_one (const struct slh_merkle_ctx_secret *ctx,
unsigned idx, uint8_t *signature, struct sha3_256_ctx *pub)+{
- uint8_t hash[_SLH_DSA_128_SIZE];
- assert (idx < (FORS_K << FORS_A));
- _fors_gen (ctx, idx, signature, hash);
- _merkle_sign (ctx, fors_leaf, fors_node, FORS_A, idx,
signature + _SLH_DSA_128_SIZE);- _merkle_verify (&ctx->pub, fors_node, FORS_A, idx, signature +
_SLH_DSA_128_SIZE, hash);
- sha3_256_update (pub, _SLH_DSA_128_SIZE, hash);
+}
+void +_fors_sign (const struct slh_merkle_ctx_secret *ctx,
const uint8_t *msg, uint8_t *signature, uint8_t *pub)+{
- struct slh_address_hash ah =
- {
bswap32_if_le(SLH_FORS_ROOTS),bswap32_if_le(ctx->pub.keypair),0, 0,- };
- struct sha3_256_ctx sha3;
- unsigned i;
- assert (FORS_A == 12); /* Specialized code */
- _slh_shake_init (&sha3, ctx->pub.seed, &ctx->pub.at, &ah);
- for (i = 0; i < FORS_K; i += 2, msg += 3, signature += 2*(FORS_A + 1) *
_SLH_DSA_128_SIZE)
- {
unsigned m0 = ((unsigned) msg[0] << 4) + (msg[1] >> 4);unsigned m1 = ((msg[1] & 0xf) << 8) + msg[2];fors_sign_one (ctx, (i << FORS_A) + m0, signature, &sha3);fors_sign_one (ctx,((i+1) << FORS_A) + m1,signature + (FORS_A + 1) * _SLH_DSA_128_SIZE, &sha3);- }
- sha3_256_shake (&sha3, _SLH_DSA_128_SIZE, pub);
+}
+static void +fors_verify_one (const struct slh_merkle_ctx_public *ctx,
unsigned idx, const uint8_t *signature, structsha3_256_ctx *pub) +{
- uint8_t root[_SLH_DSA_128_SIZE];
- struct slh_address_hash ah =
- {
bswap32_if_le (SLH_FORS_TREE),bswap32_if_le (ctx->keypair),0,bswap32_if_le(idx),- };
- assert (idx < (FORS_K << FORS_A));
- _slh_shake (ctx->seed, &ctx->at, &ah, signature, root);
- _merkle_verify (ctx, fors_node, FORS_A, idx, signature +
_SLH_DSA_128_SIZE, root);
- sha3_256_update (pub, _SLH_DSA_128_SIZE, root);
+}
+void +_fors_verify (const struct slh_merkle_ctx_public *ctx,
const uint8_t *msg, const uint8_t *signature, uint8_t *pub)+{
- struct sha3_256_ctx sha3;
- unsigned i;
- struct slh_address_hash ah =
- {
bswap32_if_le (SLH_FORS_ROOTS),bswap32_if_le (ctx->keypair),0, 0,- };
- assert (FORS_A == 12); /* Specialized code */
- _slh_shake_init (&sha3, ctx->seed, &ctx->at, &ah);
- for (i = 0; i < FORS_K; i += 2, msg += 3, signature += 2*(FORS_A + 1) *
_SLH_DSA_128_SIZE)
- {
unsigned m0 = ((unsigned) msg[0] << 4) + (msg[1] >> 4);unsigned m1 = ((msg[1] & 0xf) << 8) + msg[2];fors_verify_one (ctx, (i << FORS_A) + m0, signature, &sha3);fors_verify_one (ctx, ((i+1) << FORS_A) + m1,signature + (FORS_A + 1) * _SLH_DSA_128_SIZE,&sha3);
- }
- sha3_256_shake (&sha3, _SLH_DSA_128_SIZE, pub);
+} diff --git a/slh-merkle.c b/slh-merkle.c new file mode 100644 index 00000000..5a611d4e --- /dev/null +++ b/slh-merkle.c @@ -0,0 +1,123 @@ +/* slh-merkle.c
- Copyright (C) 2025 Niels Möller
- This file is part of GNU Nettle.
- GNU Nettle is free software: you can redistribute it and/or
- modify it under the terms of either:
* the GNU Lesser General Public License as published by the FreeSoftware Foundation; either version 3 of the License, or (at youroption) any later version.- or
* the GNU General Public License as published by the FreeSoftware Foundation; either version 2 of the License, or (at youroption) any later version.- or both in parallel, as here.
- GNU Nettle is distributed in the hope that it will be useful,
- but WITHOUT ANY WARRANTY; without even the implied warranty of
- MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
- General Public License for more details.
- You should have received copies of the GNU General Public License and
- the GNU Lesser General Public License along with this program. If
- not, see http://www.gnu.org/licenses/.
+*/
+#if HAVE_CONFIG_H +# include "config.h" +#endif
+#include <assert.h>
+#include "slh-dsa-internal.h"
+/* Computes root hash of a tree.
- Example for height == 2, 4 entries:
- i = 0 ==> stack: [0], i = 1
- i = 1 ==> stack: [0, 1] ==> [0|1], i = 2
- i = 2 ==> stack: [0|1, 2], i = 3
- i = 3 ==> stack: [0|1, 2, 3] ==> [0|1, 2|3] ==> [0|1|2|3], i = 4
- The size of the stack equals popcount(i)
+*/ +void +_merkle_root (const struct slh_merkle_ctx_secret *ctx,
merkle_leaf_hash_func *leaf_hash, merkle_node_hash_func*node_hash,
unsigned height, unsigned start, uint8_t *root,/* Must have space for (height + 1) node hashes */uint8_t *stack)+{
- unsigned stack_size = 0;
- unsigned i;
- assert (height > 0);
- assert ( (start & ((1<<height) - 1)) == 0);
- for (i = 0; i < (1<<height); i++)
- {
/* Leaf index. */unsigned idx = start + i;unsigned h;assert (stack_size <= height);leaf_hash (ctx, idx, stack + stack_size++ * _SLH_DSA_128_SIZE);for (h = 1; (idx&1); h++){assert (stack_size >= 2);idx >>= 1;stack_size--;if (h == height){assert (stack_size == 1);node_hash (&ctx->pub, h, idx,stack + (stack_size - 1) * _SLH_DSA_128_SIZE,stack + stack_size * _SLH_DSA_128_SIZE,root);return;}node_hash (&ctx->pub, h, idx,stack + (stack_size - 1) * _SLH_DSA_128_SIZE,stack + stack_size * _SLH_DSA_128_SIZE,stack + (stack_size - 1)* _SLH_DSA_128_SIZE);}- }
+}
+void +_merkle_sign (const struct slh_merkle_ctx_secret *ctx,
merkle_leaf_hash_func *leaf_hash, merkle_node_hash_func*node_hash,
unsigned height, unsigned idx, uint8_t *signature)+{
- unsigned h;
- /* By generating the path from the end, we can use the output area
as the temporary stack. */- for (h = height; --h > 0;)
- _merkle_root (ctx, leaf_hash, node_hash, h, (idx & -(1 << h)) ^ (1 <<
h),
signature + h*_SLH_DSA_128_SIZE, signature);- leaf_hash (ctx, idx ^ 1, signature);
+}
+void +_merkle_verify (const struct slh_merkle_ctx_public *ctx, merkle_node_hash_func *node_hash,
unsigned height, unsigned idx, const uint8_t *signature,uint8_t *hash) +{
- unsigned h;
- for (h = 1; h <= height; h++, signature += _SLH_DSA_128_SIZE)
- {
unsigned right = idx & 1;idx >>= 1;if (right)node_hash (ctx, h, idx, signature, hash, hash);elsenode_hash (ctx, h, idx, hash, signature, hash);- }
+} diff --git a/slh-shake.c b/slh-shake.c new file mode 100644 index 00000000..83dbe9de --- /dev/null +++ b/slh-shake.c @@ -0,0 +1,58 @@ +/* slh-prf.c
- Copyright (C) 2025 Niels Möller
- This file is part of GNU Nettle.
- GNU Nettle is free software: you can redistribute it and/or
- modify it under the terms of either:
* the GNU Lesser General Public License as published by the FreeSoftware Foundation; either version 3 of the License, or (at youroption) any later version.- or
* the GNU General Public License as published by the FreeSoftware Foundation; either version 2 of the License, or (at youroption) any later version.- or both in parallel, as here.
- GNU Nettle is distributed in the hope that it will be useful,
- but WITHOUT ANY WARRANTY; without even the implied warranty of
- MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
- General Public License for more details.
- You should have received copies of the GNU General Public License and
- the GNU Lesser General Public License along with this program. If
- not, see http://www.gnu.org/licenses/.
+*/
+#if HAVE_CONFIG_H +# include "config.h" +#endif
+#include "sha3.h" +#include "slh-dsa-internal.h"
+void +_slh_shake_init (struct sha3_256_ctx *ctx, const uint8_t *public_seed,
const struct slh_address_tree *at, const structslh_address_hash *ah) +{
- sha3_256_init (ctx);
- sha3_256_update (ctx, _SLH_DSA_128_SIZE, public_seed);
- sha3_256_update (ctx, sizeof(*at), (const uint8_t *) at);
- sha3_256_update (ctx, sizeof(*ah), (const uint8_t *) ah);
+}
+void +_slh_shake (const uint8_t *public_seed,
const struct slh_address_tree *at, const structslh_address_hash *ah,
const uint8_t *secret, uint8_t *out)+{
- struct sha3_256_ctx ctx;
- _slh_shake_init (&ctx, public_seed, at, ah);
- sha3_256_update (&ctx, _SLH_DSA_128_SIZE, secret);
- sha3_256_shake (&ctx, _SLH_DSA_128_SIZE, out);
+} diff --git a/slh-wots.c b/slh-wots.c new file mode 100644 index 00000000..a74d84dd --- /dev/null +++ b/slh-wots.c @@ -0,0 +1,209 @@ +/* slh-wots.c
- WOTS+ one-time signatures, part of SLH-DSA (FIPS 205)
- Copyright (C) 2025 Niels Möller
- This file is part of GNU Nettle.
- GNU Nettle is free software: you can redistribute it and/or
- modify it under the terms of either:
* the GNU Lesser General Public License as published by the FreeSoftware Foundation; either version 3 of the License, or (at youroption) any later version.- or
* the GNU General Public License as published by the FreeSoftware Foundation; either version 2 of the License, or (at youroption) any later version.- or both in parallel, as here.
- GNU Nettle is distributed in the hope that it will be useful,
- but WITHOUT ANY WARRANTY; without even the implied warranty of
- MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
- General Public License for more details.
- You should have received copies of the GNU General Public License and
- the GNU Lesser General Public License along with this program. If
- not, see http://www.gnu.org/licenses/.
+*/
+#if HAVE_CONFIG_H +# include "config.h" +#endif
+#include "slh-dsa-internal.h"
+#include "sha3.h" +#include "bswap-internal.h"
+/* If s == 0, returns src and leaves dst unchanged. Otherwise, returns
- dst. For the ah argument, leaves ah->keypair and ah->height_chain
- unchanged, but overwrites the other fields. */
+static const uint8_t * +wots_chain (const uint8_t *public_seed, const struct slh_address_tree *at,
struct slh_address_hash *ah,unsigned i, unsigned s,const uint8_t *src, uint8_t *dst)+{
- unsigned j;
- if (s == 0)
- return src;
- ah->type = bswap32_if_le (SLH_WOTS_HASH);
- ah->index_hash = bswap32_if_le(i);
- _slh_shake (public_seed, at, ah, src, dst);
- for (j = 1; j < s; j++)
- {
ah->index_hash = bswap32_if_le(i + j);_slh_shake (public_seed, at, ah, dst, dst);- }
- return dst;
+}
+static void +wots_pk_init (const uint8_t *public_seed, const struct slh_address_tree *at,
unsigned keypair, struct slh_address_hash *ah, structsha3_256_ctx *ctx) +{
- ah->type = bswap32_if_le (SLH_WOTS_PK);
- ah->keypair = bswap32_if_le (keypair);
- ah->height_chain = 0;
- ah->index_hash = 0;
- _slh_shake_init (ctx, public_seed, at, ah);
+}
+void +_wots_gen (const uint8_t *public_seed, const uint8_t *secret_seed, const struct slh_address_tree *at,
uint32_t keypair, uint8_t *pub)+{
- struct slh_address_hash ah;
- struct sha3_256_ctx ctx;
- unsigned i;
- wots_pk_init (public_seed, at, keypair, &ah, &ctx);
- for (i = 0; i < _WOTS_SIGNATURE_LENGTH; i++)
- {
uint8_t out[_SLH_DSA_128_SIZE];/* Generate secret value. */ah.type = bswap32_if_le (SLH_WOTS_PRF);ah.height_chain = bswap32_if_le(i);ah.index_hash = 0;_slh_shake (public_seed, at, &ah, secret_seed, out);/* Hash chain. */wots_chain (public_seed, at, &ah, 0, 15, out, out);sha3_256_update (&ctx, _SLH_DSA_128_SIZE, out);- }
- sha3_256_shake (&ctx, _SLH_DSA_128_SIZE, pub);
+}
+/* Produces signature hash corresponding to the ith message nybble. Modifies addr. */ +static void +wots_sign_one (const uint8_t *public_seed,
const uint8_t *secret_seed, const struct slh_address_tree*at,
uint32_t keypair,unsigned i, uint8_t msg, uint8_t *sig, struct sha3_256_ctx*ctx) +{
- struct slh_address_hash ah;
- uint8_t pub[_SLH_DSA_128_SIZE];
- sig += i*_SLH_DSA_128_SIZE;
- /* Generate secret value. */
- ah.type = bswap32_if_le (SLH_WOTS_PRF);
- ah.keypair = bswap32_if_le (keypair);
- ah.height_chain = bswap32_if_le(i);
- ah.index_hash = 0;
- _slh_shake (public_seed, at, &ah, secret_seed, sig);
- /* Hash chain. */
- wots_chain (public_seed, at, &ah, 0, msg, sig, sig);
- sha3_256_update (ctx, _SLH_DSA_128_SIZE,
wots_chain (public_seed, at, &ah, msg, 15 - msg, sig,pub)); +}
+void +_wots_sign (const uint8_t *public_seed, const uint8_t *secret_seed, const struct slh_address_tree *at,
unsigned keypair, const uint8_t *msg, uint8_t *signature,uint8_t *pub) +{
- struct slh_address_hash ah;
- struct sha3_256_ctx ctx;
- unsigned i;
- uint32_t csum;
- wots_pk_init (public_seed, at, keypair, &ah, &ctx);
- for (i = 0, csum = 15*32; i < _SLH_DSA_128_SIZE; i++)
- {
uint8_t m0, m1;m0 = msg[i] >> 4;csum -= m0;wots_sign_one(public_seed, secret_seed, at, keypair, 2*i, m0,signature, &ctx);
m1 = msg[i] & 0xf;csum -= m1;wots_sign_one(public_seed, secret_seed, at, keypair, 2*i + 1, m1,signature, &ctx);
- }
- wots_sign_one (public_seed, secret_seed, at, keypair, 32, csum >> 8,
signature, &ctx);
- wots_sign_one (public_seed, secret_seed, at, keypair, 33, (csum >> 4) &
0xf, signature, &ctx);
- wots_sign_one (public_seed, secret_seed, at, keypair, 34, csum & 0xf,
signature, &ctx);
- sha3_256_shake (&ctx, _SLH_DSA_128_SIZE, pub);
+}
+static void +wots_verify_one (struct sha3_256_ctx *ctx, const uint8_t *public_seed, const struct slh_address_tree *at,
uint32_t keypair, unsigned i, uint8_t msg, const uint8_t*signature) +{
- struct slh_address_hash ah;
- uint8_t out[_SLH_DSA_128_SIZE];
- signature += i*_SLH_DSA_128_SIZE;
- ah.keypair = bswap32_if_le (keypair);
- ah.height_chain = bswap32_if_le(i);
- sha3_256_update (ctx, _SLH_DSA_128_SIZE,
wots_chain (public_seed, at, &ah, msg, 15 - msg,signature, out)); +}
+void +_wots_verify (const uint8_t *public_seed, const struct slh_address_tree *at,
unsigned keypair, const uint8_t *msg, const uint8_t*signature, uint8_t *pub) +{
- struct slh_address_hash ah;
- struct sha3_256_ctx ctx;
- unsigned i;
- uint32_t csum;
- wots_pk_init (public_seed, at, keypair, &ah, &ctx);
- for (i = 0, csum = 15*32; i < _SLH_DSA_128_SIZE; i++)
- {
uint8_t m0, m1;m0 = msg[i] >> 4;csum -= m0;wots_verify_one(&ctx, public_seed, at, keypair, 2*i, m0, signature);m1 = msg[i] & 0xf;csum -= m1;wots_verify_one(&ctx, public_seed, at, keypair, 2*i + 1, m1,signature);
- }
- wots_verify_one (&ctx, public_seed, at, keypair, 32, csum >> 8,
signature);
- wots_verify_one (&ctx, public_seed, at, keypair, 33, (csum >> 4) & 0xf,
signature);
- wots_verify_one (&ctx, public_seed, at, keypair, 34, csum & 0xf,
signature);
- sha3_256_shake (&ctx, _SLH_DSA_128_SIZE, pub);
+} diff --git a/slh-xmss.c b/slh-xmss.c new file mode 100644 index 00000000..1f0a36bc --- /dev/null +++ b/slh-xmss.c @@ -0,0 +1,104 @@ +/* slh-xmss.c
- The eXtended Merkle Signature Scheme, part of SLH-DSA (FIPS 205)
- Copyright (C) 2025 Niels Möller
- This file is part of GNU Nettle.
- GNU Nettle is free software: you can redistribute it and/or
- modify it under the terms of either:
* the GNU Lesser General Public License as published by the FreeSoftware Foundation; either version 3 of the License, or (at youroption) any later version.- or
* the GNU General Public License as published by the FreeSoftware Foundation; either version 2 of the License, or (at youroption) any later version.- or both in parallel, as here.
- GNU Nettle is distributed in the hope that it will be useful,
- but WITHOUT ANY WARRANTY; without even the implied warranty of
- MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
- General Public License for more details.
- You should have received copies of the GNU General Public License and
- the GNU Lesser General Public License along with this program. If
- not, see http://www.gnu.org/licenses/.
+*/
+#if HAVE_CONFIG_H +# include "config.h" +#endif
+#include "bswap-internal.h" +#include "sha3.h" +#include "slh-dsa-internal.h"
+static void +xmss_leaf (const struct slh_merkle_ctx_secret *ctx, unsigned idx, uint8_t *leaf) +{
- _wots_gen (ctx->pub.seed, ctx->secret_seed, &ctx->pub.at, idx, leaf);
+}
+static void +xmss_node (const struct slh_merkle_ctx_public *ctx, unsigned height, unsigned index,
const uint8_t *left, const uint8_t *right, uint8_t *out)+{
- struct sha3_256_ctx sha3;
- struct slh_address_hash ah =
- {
bswap32_if_le (SLH_XMSS_TREE),0,bswap32_if_le (height),bswap32_if_le (index),- };
- _slh_shake_init (&sha3, ctx->seed, &ctx->at, &ah);
- sha3_256_update (&sha3, _SLH_DSA_128_SIZE, left);
- sha3_256_update (&sha3, _SLH_DSA_128_SIZE, right);
- sha3_256_shake (&sha3, _SLH_DSA_128_SIZE, out);
+}
+void +_xmss_gen (const uint8_t *public_seed, const uint8_t *secret_seed,
uint8_t *root)+{
- struct slh_merkle_ctx_secret ctx =
- {
{public_seed,/* Everything zero, except layer and type. */{ bswap32_if_le(SLH_DSA_D-1), 0, 0, } ,0,},secret_seed- };
- uint8_t stack[(XMSS_H + 1)*_SLH_DSA_128_SIZE];
- _merkle_root (&ctx, xmss_leaf, xmss_node, XMSS_H, 0, root, stack);
+}
+void +_xmss_sign (const struct slh_merkle_ctx_secret *ctx,
unsigned idx, const uint8_t *msg, uint8_t *signature, uint8_t*pub) +{
- _wots_sign (ctx->pub.seed, ctx->secret_seed, &ctx->pub.at, idx, msg,
signature, pub);
- signature += WOTS_SIGNATURE_SIZE;
- _merkle_sign (ctx, xmss_leaf, xmss_node, XMSS_H, idx, signature);
- _merkle_verify (&ctx->pub, xmss_node, XMSS_H, idx, signature, pub);
+}
+void +_xmss_verify (const struct slh_merkle_ctx_public *ctx,
unsigned idx, const uint8_t *msg, const uint8_t *signature,uint8_t *pub) +{
- _wots_verify (ctx->seed, &ctx->at, idx, msg, signature, pub);
- signature += WOTS_SIGNATURE_SIZE;
- _merkle_verify (ctx, xmss_node, XMSS_H, idx, signature, pub);
+}
-- Niels Möller. PGP key CB4962D070D77D7FCB8BA36271D8F1FF368C6677. Internet email is subject to wholesale government surveillance.
Zoltan Fridrich zfridric@redhat.com writes:
- The slh_dsa_shake_128s_root seems to serve the same purpose as the
slh_keygen_internal function in the spec.
I think that's right.
*Other than for testing purposes, the interfaces for key generation and signature generationspecified in this section should not be made available to applications, as any random valuesrequired for key generation and signature generation shall be generated by the cryptographicmodule*". So perhaps slh_dsa_shake_128s_root should not be exposed as a public API function.
I'm not that concerned with those requirements, Nettle doesn't try to be a "cryptographic module" in the fips sense. And it doesn't have any way to generate random bits "internally", it has to rely on the randomness function passed by the application (and today, I think a function just reading /dev/random is the reasonable choice in most cases).
That said, I'm not sure there's a good usecase for exposing this function. I would have been happier if keys had been designed so that private key is any random string, and public key derived from the private key in a fully determinsitic way. (It's not obvious to me why the spec says that the public_seed must be independently generated, rather than just computed based on hashing of the private key, but I think I should conform to the spec on this).
Otherwise, the API looks good. Eventually there should also be the pre-hash variants for sign and verify present in the API.
- I think first there should be at least one fast and short option
available.
Makes sense, I'm working on adding slh-dsa-shake-128f. Current speed on my laptop:
$ ./examples/hogweed-benchmark slh-dsa-shake name size sign/s verify/s slh-dsa-shake-s 128 0.76 992.98 slh-dsa-shake-f 128 20.19 337.95
$ ./examples/hogweed-benchmark eddsa name size sign/s verify/s eddsa 255 24990.3 6626.5 eddsa 448 6645.6 1797.3
So for verify operations (consider signed firmware updates in some embedded system expected to operate for decades), it's only about one order of magnitude slower than classic signatures.
Another question: All other public key algorithms are in libhogweed, and depend on GMP bignum functions. But the motivation for the nettle/hogweed split was to avoid a runtime shared library dependency on GMP for applications that don't use any algorithms based on bignums. And therefore, it seems slh-dsa belongs in libnettle, not libhogweed. Do you agree?
Regards, /Niels
Niels Möller nisse-SamgB31n2u5IcsJQ0EH25Q@public.gmane.org writes:
- I think first there should be at least one fast and short option
available.
Makes sense, I'm working on adding slh-dsa-shake-128f.
Having 256-bit options would be nice, as a conservative long-term signature algorithm choice, any chance you could add those?
The SHA2 alternatives would be nice too, some environments have better performance for SHA2 than SHAKE.
$ ./examples/hogweed-benchmark slh-dsa-shake name size sign/s verify/s slh-dsa-shake-s 128 0.76 992.98 slh-dsa-shake-f 128 20.19 337.95
$ ./examples/hogweed-benchmark eddsa name size sign/s verify/s eddsa 255 24990.3 6626.5 eddsa 448 6645.6 1797.3
So for verify operations (consider signed firmware updates in some embedded system expected to operate for decades), it's only about one order of magnitude slower than classic signatures.
Interesting - my perception is that SPHINCS+ verification is faster than Ed25519 (at the end of [1] suggests 5-10 times faster). Could this be explained by SHA2 vs SHAKE? Zoltan, what benchmarks did your implementation get?
/Simon
[1] https://blog.josefsson.org/2024/12/23/openssh-and-git-on-a-post-quantum-sphi...
from Niels:
Another question: All other public key algorithms are in libhogweed, and depend on GMP bignum functions. But the motivation for the nettle/hogweed split was to avoid a runtime shared library dependency on GMP for applications that don't use any algorithms based on bignums. And therefore, it seems slh-dsa belongs in libnettle, not libhogweed. Do you agree?
Yes, I think that sounds reasonable.
from Simon:
Interesting - my perception is that SPHINCS+ verification is faster than Ed25519 (at the end of [1] suggests 5-10 times faster). Could this be explained by SHA2 vs SHAKE? Zoltan, what benchmarks did your implementation get?
I used the reference sphincs+ implementation https://github.com/sphincs/sphincsplus/tree/master together with some patches from leancrypto to make it conform to the NIST standard. I haven't done any benchmarks on my patch, but there are benchmarking tests in the reference implementation. https://github.com/sphincs/sphincsplus/blob/master/ref/test/benchmark.c
On Fri, Feb 21, 2025 at 11:06 AM Simon Josefsson simon@josefsson.org wrote:
Niels Möller nisse-SamgB31n2u5IcsJQ0EH25Q@public.gmane.org writes:
- I think first there should be at least one fast and short option
available.
Makes sense, I'm working on adding slh-dsa-shake-128f.
Having 256-bit options would be nice, as a conservative long-term signature algorithm choice, any chance you could add those?
The SHA2 alternatives would be nice too, some environments have better performance for SHA2 than SHAKE.
$ ./examples/hogweed-benchmark slh-dsa-shake name size sign/s verify/s slh-dsa-shake-s 128 0.76 992.98 slh-dsa-shake-f 128 20.19 337.95
$ ./examples/hogweed-benchmark eddsa name size sign/s verify/s eddsa 255 24990.3 6626.5 eddsa 448 6645.6 1797.3
So for verify operations (consider signed firmware updates in some embedded system expected to operate for decades), it's only about one order of magnitude slower than classic signatures.
Interesting - my perception is that SPHINCS+ verification is faster than Ed25519 (at the end of [1] suggests 5-10 times faster). Could this be explained by SHA2 vs SHAKE? Zoltan, what benchmarks did your implementation get?
/Simon
[1] https://blog.josefsson.org/2024/12/23/openssh-and-git-on-a-post-quantum-sphi... _______________________________________________ nettle-bugs mailing list -- nettle-bugs@lists.lysator.liu.se To unsubscribe send an email to nettle-bugs-leave@lists.lysator.liu.se
Simon Josefsson simon@josefsson.org writes:
Interesting - my perception is that SPHINCS+ verification is faster than Ed25519 (at the end of [1] suggests 5-10 times faster). Could this be explained by SHA2 vs SHAKE?
That could certainly be part of it. On my machine, sha256 runs at 1140 MB/s (using sha_ni instrutions), and sha3_256 runs at 190, so that's a factor 6 difference. And that's benchmarking for large messages, numbers will be somewhat different for small messages, and for slh-dsa, the number of calls to underlying sha256_compress / sha3_permute will depend on how its hashing operations interact with the respective block sizes, 64 bytes for sha256, 136 bytes for shake256.
Regards, /Niels
nettle-bugs@lists.lysator.liu.se
-
Niels Möller -
Simo Sorce -
Simon Josefsson -
Zoltan Fridrich