From e9c9ed1a9f7fdb237c4b9f156b1bd7777f86bcd0 Mon Sep 17 00:00:00 2001 From: =?utf8?q?Niels=20M=C3=B6ller?= Date: Tue, 11 Feb 2025 20:25:06 +0100 Subject: [PATCH] Implement wots+, part of slh-dsa. --- ChangeLog | 9 ++ Makefile.in | 5 +- slh-dsa-internal.h | 92 ++++++++++++++++ slh-wots.c | 230 +++++++++++++++++++++++++++++++++++++++ testsuite/Makefile.in | 3 +- testsuite/slh-dsa-test.c | 118 ++++++++++++++++++++ 6 files changed, 455 insertions(+), 2 deletions(-) create mode 100644 slh-dsa-internal.h create mode 100644 slh-wots.c create mode 100644 testsuite/slh-dsa-test.c diff --git a/ChangeLog b/ChangeLog index 462dcf72..fcae93fa 100644 --- a/ChangeLog +++ b/ChangeLog @@ -1,3 +1,12 @@ +2025-02-11 Niels Möller + + * slh-wots.c (_wots_gen, _wots_sign, _wots_verify): New file, new functions. + * slh-dsa-internal.h: New file. + * Makefile.in (nettle_SOURCES): Add slh-wots.c. + (DISTFILES): Add slh-dsa-internal.h. + * testsuite/slh-dsa-test.c: New file. + * testsuite/Makefile.in (TS_NETTLE_SOURCES): Add slh-dsa-test.c. + 2025-03-02 Niels Möller * powerpc64/p8/gcm-aes-decrypt.asm: Avoid using lxvb16x diff --git a/Makefile.in b/Makefile.in index 71ad761e..9ee2ffca 100644 --- a/Makefile.in +++ b/Makefile.in @@ -166,7 +166,8 @@ nettle_SOURCES = aes-decrypt-internal.c aes-decrypt.c aes-decrypt-table.c \ write-be32.c write-le32.c write-le64.c \ yarrow256.c yarrow_key_event.c \ xts.c xts-aes128.c xts-aes256.c \ - drbg-ctr-aes256.c + drbg-ctr-aes256.c \ + slh-wots.c hogweed_SOURCES = sexp.c sexp-format.c \ sexp-transport.c sexp-transport-format.c \ @@ -228,6 +229,7 @@ hogweed_SOURCES = sexp.c sexp-format.c \ ed448-shake256.c ed448-shake256-pubkey.c \ ed448-shake256-sign.c ed448-shake256-verify.c + OPT_SOURCES = fat-arm.c fat-arm64.c fat-ppc.c fat-s390x.c fat-x86_64.c mini-gmp.c HEADERS = aes.h arcfour.h arctwo.h asn1.h blowfish.h balloon.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..623dad5e --- /dev/null +++ b/slh-dsa-internal.h @@ -0,0 +1,92 @@ +/* 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 + +/* Name mangling */ +#define _wots_gen _nettle_wots_gen +#define _wots_sign _nettle_wots_sign +#define _wots_verify _nettle_wots_verify + +/* Size of a single hash, including the seed and prf parameters */ +#define _SLH_DSA_128_SIZE 16 + +/* 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, + }; + +#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); + +#endif /* NETTLE_SLH_DSA_INTERNAL_H_INCLUDED */ diff --git a/slh-wots.c b/slh-wots.c new file mode 100644 index 00000000..f5dd7920 --- /dev/null +++ b/slh-wots.c @@ -0,0 +1,230 @@ +/* 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" + +static 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); +} + +static void +slh_prf (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); +} + +/* 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_prf (public_seed, at, ah, src, dst); + + for (j = 1; j < s; j++) + { + ah->index_hash = bswap32_if_le(i + j); + slh_prf (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_prf (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_prf (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/testsuite/Makefile.in b/testsuite/Makefile.in index 0699fa0d..b77f82fa 100644 --- a/testsuite/Makefile.in +++ b/testsuite/Makefile.in @@ -35,7 +35,8 @@ TS_NETTLE_SOURCES = aes-test.c aes-keywrap-test.c arcfour-test.c arctwo-test.c \ meta-hash-test.c meta-cipher-test.c\ meta-aead-test.c meta-armor-test.c meta-mac-test.c \ buffer-test.c yarrow-test.c xts-test.c pbkdf2-test.c \ - x86-ibt-test.c drbg-ctr-aes256-test.c + x86-ibt-test.c drbg-ctr-aes256-test.c \ + slh-dsa-test.c TS_HOGWEED_SOURCES = sexp-test.c sexp-format-test.c \ rsa2sexp-test.c sexp2rsa-test.c \ diff --git a/testsuite/slh-dsa-test.c b/testsuite/slh-dsa-test.c new file mode 100644 index 00000000..a0b4d0f3 --- /dev/null +++ b/testsuite/slh-dsa-test.c @@ -0,0 +1,118 @@ +/* slh-dsa-test.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/. +*/ + +#include "testutils.h" + +#include "slh-dsa-internal.h" +#include "bswap-internal.h" + +static void +test_wots_gen (const struct tstring *public_seed, const struct tstring *secret_seed, + unsigned layer, uint64_t tree_idx, uint32_t keypair, + const struct tstring *exp_pub) +{ + struct slh_address_tree at = {0}; + uint8_t pub[_SLH_DSA_128_SIZE]; + ASSERT (public_seed->length == _SLH_DSA_128_SIZE); + ASSERT (secret_seed->length == _SLH_DSA_128_SIZE); + ASSERT (exp_pub->length == _SLH_DSA_128_SIZE); + + at.layer = bswap32_if_le (layer); + at.tree_idx = bswap64_if_le (tree_idx); + _wots_gen (public_seed->data, secret_seed->data, &at, keypair, pub); + ASSERT (MEMEQ (sizeof (pub), pub, exp_pub->data)); +} + +static void +test_wots_sign (const struct tstring *public_seed, const struct tstring *secret_seed, + unsigned layer, uint64_t tree_idx, uint32_t keypair, const struct tstring *msg, + const struct tstring *exp_pub, const struct tstring *exp_sig) +{ + struct slh_address_tree at = {0}; + uint8_t sig[WOTS_SIGNATURE_SIZE]; + uint8_t pub[_SLH_DSA_128_SIZE]; + ASSERT (public_seed->length == _SLH_DSA_128_SIZE); + ASSERT (secret_seed->length == _SLH_DSA_128_SIZE); + ASSERT (msg->length == _SLH_DSA_128_SIZE); + ASSERT (exp_pub->length == _SLH_DSA_128_SIZE); + ASSERT (exp_sig->length == WOTS_SIGNATURE_SIZE); + + at.layer = bswap32_if_le (layer); + at.tree_idx = bswap64_if_le (tree_idx); + + _wots_sign (public_seed->data, secret_seed->data, &at, keypair, + msg->data, sig, pub); + ASSERT (MEMEQ(sizeof(sig), sig, exp_sig->data)); + ASSERT (MEMEQ(sizeof(pub), pub, exp_pub->data)); + + memset (pub, 0, sizeof(pub)); + _wots_verify (public_seed->data, &at, keypair, msg->data, sig, pub); + ASSERT (MEMEQ(sizeof(pub), pub, exp_pub->data)); +} + +void +test_main(void) +{ + const struct tstring *public_seed = + SHEX("b505d7cfad1b497499323c8686325e47"); + + const struct tstring *secret_seed = + SHEX("7c9935a0b07694aa0c6d10e4db6b1add"); + + test_wots_gen (public_seed, secret_seed, 6, 0, 0, + SHEX("38c9077d76d1e32933fb58a53e769ed7")); + test_wots_gen (public_seed, secret_seed, 6, 0, 1, + SHEX("a026afacc77c7d97eebe6f88c70fec2d")); + test_wots_gen (public_seed, secret_seed, 0, UINT64_C(0x29877722d7c079), 0x156, + SHEX("99747c3547770fa288a628ed15122d3e")); + + test_wots_sign (public_seed, secret_seed, 0, UINT64_C(0x29877722d7c079), 0x156, + SHEX("3961b2cab15e08c633be827744a07f01"), + SHEX("99747c3547770fa288a628ed15122d3e"), + SHEX("e1933de10e3fface 5fb8f8707c35ac13 74dc14ee8518481c 7e63d936ecc62f50" + "c7f951b87bc716dc 45e9bcfec6f6d97e 7fafdacb6db05ed3 778f21851f325e25" + "470da8dd81c41223 6d66cbee9ffa9c50 b86aa40baf213494 dfacca22aa0fb479" + "53928735ca4212cf 53a09ab0335d20a8 e62ede797c8e7493 54d636f15f3150c5" + "52797b76c091a41f 949f7fb57b42f744 1cca410264d6421f 4aa2c7e2ff4834a8" + "db0e6e7750b2e11f f1c89a42d1fbc271 8358e38325886ad1 2346cd694f9eab73" + "46c9a23b5ebe7637 bfd834a412318b01 188b0f29e3bd979f 8ae734acf1563af3" + "03d3c095e9eaeba3 5207b9df3acf9ee4 7da5c1e2652f3b86 41698f3d2260591b" + "07d00565e5d6be18 36033d2b7ef2c33b dc5cf3bba95b42df 6f73345b835341b2" + "50e2862c9f2f9cef 77cfa74cfb04c560 d8a0038c4e96cb0d a2b3e9b2cd3cecf5" + "22fda0d67e5f62b2 ee23bd42a61c7da4 8f0ea30b81af7ccb 6bb02cde272d2574" + "1325e9d91535615c 0184f2d7f226141d 79b42412721fd345 61d93663650b3c1b" + "6901872bc4c0bb15 bcd9038950b7717f 7f448b6126592076 a2bad2d63c55399c" + "243fdbdb0c8d676b 2ae455e7f0a9b18d 3fc889c43387f2cb c4dc73d7c85bfab6" + "b4b04463a3dd359c 3a8f61bfa6c4b042 4aeba4dd8a95ec12 43b2e36c29f82e1d" + "711281599b3e05e7 5492ae3425eaa7f1 4ff8c6a9630bba6e bd236f195269a481" + "e87eb3d444825ba4 424ee5b2d9efb595 d5a338f4c253f79d e9d04535206ca6db" + "c2d4c9a1ec20849b 0db3fbe10c1446d5")); +} -- 2.47.2