commit ad26bdfbb0084e39ea2710ae56984b7dec86e5f1
parent b45738c5eca6e1ba3ca877470c060cda8f192c77
Author: finwo <finwo@pm.me>
Date: Fri, 9 Oct 2026 16:35:07 +0200
winternitz-one-time-signature implementation
Diffstat:
| M | src/sfinx.c | | | 77 | +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ |
| A | test/02-wots.c | | | 97 | +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ |
2 files changed, 174 insertions(+), 0 deletions(-)
diff --git a/src/sfinx.c b/src/sfinx.c
@@ -1,6 +1,7 @@
#include "sfinx.h"
#include <coruus/keccak-tiny.h>
+#include <string.h>
// E4M4 {{{
//
@@ -70,4 +71,80 @@ size_t sfinx_hash_len(sfinx_hash hash) {
}
// }}}
+// WOTS {{{
+//
+// One WOTS key over an L-byte value, c = L + 2 chains of length 256
+// preimage = SHAKE256(seed), c * L bytes, c elements of L bytes
+// digits = the value bytes, then 2 checksum bytes of 255 - value[i]
+// pubkey = H of every element chained w times
+// proof = every element chained d[i] times
+// verify = chain every proof element w - d[i] times, then the pubkey hash
+
+#define SFINX_WOTS_BYTES_MAX ((SFINX_HASH_LEN_MAX + 2) * SFINX_HASH_LEN_MAX)
+#define SFINX_WOTS_DIGITS_MAX (SFINX_HASH_LEN_MAX + 2)
+
+static inline void _sfinx_wots_preimage(sfinx_hash hash, const uint8_t *seed, size_t seed_len, uint8_t *out) {
+ size_t len = sfinx_hash_len(hash);
+ _sfinx_shake256(seed, seed_len, out, (len + 2) * len);
+}
+
+static inline void _sfinx_wots_digits(sfinx_hash hash, const uint8_t *value, uint8_t *out) {
+ size_t len = sfinx_hash_len(hash);
+ uint32_t checksum = 0;
+ for (size_t i = 0; i < len; i++) {
+ out[i] = value[i];
+ checksum += 255 - value[i];
+ }
+ out[len] = (uint8_t)(checksum >> 8);
+ out[len + 1] = (uint8_t)checksum;
+}
+
+static inline void _sfinx_wots_chain(sfinx_hash hash, uint8_t *node, uint32_t steps) {
+ uint8_t next[SFINX_HASH_LEN_MAX];
+ size_t len = sfinx_hash_len(hash);
+ for (uint32_t i = 0; i < steps; i++) {
+ _sfinx_hash(hash, node, len, next);
+ memcpy(node, next, len);
+ }
+}
+
+static inline void _sfinx_wots_pubkey(sfinx_hash hash, const uint8_t *seed, size_t seed_len, uint8_t *pubkey_out) {
+ size_t len = sfinx_hash_len(hash);
+ uint8_t ends[SFINX_WOTS_BYTES_MAX];
+ _sfinx_wots_preimage(hash, seed, seed_len, ends);
+ for (size_t i = 0; i < len + 2; i++) {
+ _sfinx_wots_chain(hash, ends + i * len, 256);
+ }
+ _sfinx_hash(hash, ends, (len + 2) * len, pubkey_out);
+}
+
+static inline void _sfinx_wots_proof(sfinx_hash hash, const uint8_t *seed, size_t seed_len, const uint8_t *value,
+ uint8_t *proof_out) {
+ size_t len = sfinx_hash_len(hash);
+ uint8_t digits[SFINX_WOTS_DIGITS_MAX];
+ _sfinx_wots_preimage(hash, seed, seed_len, proof_out);
+ _sfinx_wots_digits(hash, value, digits);
+ for (size_t i = 0; i < len + 2; i++) {
+ _sfinx_wots_chain(hash, proof_out + i * len, digits[i]);
+ }
+}
+
+static inline int _sfinx_wots_verify(sfinx_hash hash, const uint8_t *pubkey, const uint8_t *value,
+ const uint8_t *proof) {
+ size_t len = sfinx_hash_len(hash);
+ uint8_t digits[SFINX_WOTS_DIGITS_MAX];
+ uint8_t ends[SFINX_WOTS_BYTES_MAX];
+ uint8_t want[SFINX_HASH_LEN_MAX];
+ uint8_t node[SFINX_HASH_LEN_MAX];
+ _sfinx_wots_digits(hash, value, digits);
+ for (size_t i = 0; i < len + 2; i++) {
+ memcpy(node, proof + i * len, len);
+ _sfinx_wots_chain(hash, node, 256 - digits[i]);
+ memcpy(ends + i * len, node, len);
+ }
+ _sfinx_hash(hash, ends, (len + 2) * len, want);
+ return memcmp(want, pubkey, len) == 0;
+}
+// }}}
+
// vim:fdm=marker:fdl=0
diff --git a/test/02-wots.c b/test/02-wots.c
@@ -0,0 +1,97 @@
+#include <string.h>
+
+#include "_tap.c"
+#include "src/sfinx.c"
+
+static void check_size(size_t got, size_t want, const char *what) {
+ tap(got == want, what, "got %zu, want %zu", got, want);
+}
+
+static void chain_manual(sfinx_hash hash, uint8_t *node, uint32_t steps) {
+ uint8_t next[SFINX_HASH_LEN_MAX];
+ size_t len = sfinx_hash_len(hash);
+ for (uint32_t i = 0; i < steps; i++) {
+ _sfinx_hash(hash, node, len, next);
+ memcpy(node, next, len);
+ }
+}
+
+int main(void) {
+ static const sfinx_hash hashes[] = {SFINX_HASH_224, SFINX_HASH_256, SFINX_HASH_384, SFINX_HASH_512};
+ static const char *labels[] = {"round trip 224", "round trip 256", "round trip 384", "round trip 512"};
+ const uint8_t *seed = (const uint8_t *)"sfinx wots seed";
+ size_t seed_len = strlen((const char *)seed);
+ uint8_t zero[SFINX_HASH_LEN_MAX] = {0};
+ uint8_t ones[SFINX_HASH_LEN_MAX];
+ uint8_t value[SFINX_HASH_LEN_MAX];
+ uint8_t digits[SFINX_WOTS_DIGITS_MAX];
+ uint8_t pubkey[SFINX_HASH_LEN_MAX];
+ uint8_t other[SFINX_HASH_LEN_MAX];
+ uint8_t proof[SFINX_WOTS_BYTES_MAX];
+ uint8_t node[SFINX_HASH_LEN_MAX];
+ uint8_t manual[SFINX_HASH_LEN_MAX];
+
+ tap_begin("sfinx WOTS");
+
+ _sfinx_wots_digits(SFINX_HASH_256, zero, digits);
+ check_size(digits[32], 0x1f, "checksum high, all zero");
+ check_size(digits[33], 0xe0, "checksum low, all zero");
+
+ memset(ones, 0xff, sizeof(ones));
+ _sfinx_wots_digits(SFINX_HASH_256, ones, digits);
+ check_size(digits[0], 0xff, "digit copies value, all one");
+ check_size(digits[32], 0x00, "checksum high, all one");
+ check_size(digits[33], 0x00, "checksum low, all one");
+
+ _sfinx_wots_digits(SFINX_HASH_512, zero, digits);
+ check_size(digits[64], 0x3f, "checksum high, L 64");
+ check_size(digits[65], 0xc0, "checksum low, L 64");
+
+ for (size_t i = 0; i < 32; i++) value[i] = (uint8_t)(i * 7 + 1);
+ _sfinx_wots_digits(SFINX_HASH_256, value, digits);
+ tap(memcmp(digits, value, 32) == 0, "digits copy the value", "digits differ");
+
+ for (size_t i = 0; i < 32; i++) node[i] = (uint8_t)(i + 1);
+ memcpy(manual, node, 32);
+ chain_manual(SFINX_HASH_256, manual, 5);
+ _sfinx_wots_chain(SFINX_HASH_256, node, 5);
+ tap(memcmp(node, manual, 32) == 0, "chain of 5 matches manual", "chain differs");
+
+ for (size_t i = 0; i < 32; i++) node[i] = (uint8_t)(i + 1);
+ memcpy(manual, node, 32);
+ _sfinx_wots_chain(SFINX_HASH_256, node, 0);
+ tap(memcmp(node, manual, 32) == 0, "chain of 0 is identity", "chain changed");
+
+ _sfinx_wots_pubkey(SFINX_HASH_256, seed, seed_len, pubkey);
+ _sfinx_wots_pubkey(SFINX_HASH_256, seed, seed_len, other);
+ tap(memcmp(pubkey, other, 32) == 0, "pubkey is deterministic", "pubkeys differ");
+
+ _sfinx_wots_pubkey(SFINX_HASH_256, (const uint8_t *)"other wots seed", 15, other);
+ tap(memcmp(pubkey, other, 32) != 0, "different seed gives a different pubkey", "pubkeys match");
+
+ _sfinx_hash(SFINX_HASH_256, (const uint8_t *)"hello", 5, value);
+ _sfinx_wots_proof(SFINX_HASH_256, seed, seed_len, value, proof);
+ tap(_sfinx_wots_verify(SFINX_HASH_256, pubkey, value, proof), "proof verifies", "verify failed");
+
+ proof[17] ^= 0x40;
+ tap(!_sfinx_wots_verify(SFINX_HASH_256, pubkey, value, proof), "tampered proof fails", "verify passed");
+
+ _sfinx_wots_proof(SFINX_HASH_256, seed, seed_len, value, proof);
+ value[3] ^= 0x01;
+ tap(!_sfinx_wots_verify(SFINX_HASH_256, pubkey, value, proof), "tampered value fails", "verify passed");
+
+ _sfinx_hash(SFINX_HASH_256, (const uint8_t *)"hello", 5, value);
+ _sfinx_wots_proof(SFINX_HASH_256, seed, seed_len, value, proof);
+ memcpy(other, pubkey, 32);
+ other[0] ^= 0x01;
+ tap(!_sfinx_wots_verify(SFINX_HASH_256, other, value, proof), "wrong pubkey fails", "verify passed");
+
+ for (size_t h = 0; h < 4; h++) {
+ _sfinx_hash(hashes[h], (const uint8_t *)"message", 7, value);
+ _sfinx_wots_pubkey(hashes[h], seed, seed_len, pubkey);
+ _sfinx_wots_proof(hashes[h], seed, seed_len, value, proof);
+ tap(_sfinx_wots_verify(hashes[h], pubkey, value, proof), labels[h], "verify failed");
+ }
+
+ return tap_plan();
+}