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:

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);

+}

-- Niels Möller. PGP key CB4962D070D77D7FCB8BA36271D8F1FF368C6677. Internet email is subject to wholesale government surveillance.