sfinx.c (30388B)
1 #include "sfinx.h" 2 3 #include <finwo/keccak-fast.h> 4 #include <stdlib.h> 5 #include <string.h> 6 #include <sys/random.h> 7 #include <unistd.h> 8 9 #ifdef _REENTRANT 10 #include <pthread.h> 11 #endif 12 13 // E4M4 {{{ 14 // 15 // Log-ish number format, only positive 16 // E=0: M 17 // E>0: (16+M)<<(E-1) 18 19 static inline uint32_t _sfinx_e4m4_decode(uint8_t byte) { 20 uint8_t exponent = (uint8_t)(byte >> 4); 21 uint8_t mantissa = (uint8_t)(byte & 0x0f); 22 if (exponent == 0) { 23 return mantissa; 24 } 25 return (uint32_t)(16 + mantissa) << (exponent - 1); 26 } 27 28 static inline uint32_t _sfinx_e4m4_encode(uint32_t value, uint8_t *out) { 29 if (value <= 15) { 30 *out = (uint8_t)value; 31 return 1; 32 } 33 34 uint32_t base = value; 35 uint32_t shift = 0; 36 while (base > 31) { 37 base >>= 1; 38 if (++shift > 14) { 39 return 0; 40 } 41 } 42 if (base < 16 || (base << shift) != value) { 43 return 0; 44 } 45 46 *out = (uint8_t)(((shift + 1) << 4) | (base - 16)); 47 return 1; 48 } 49 // }}} 50 51 // Hash backend {{{ 52 // 53 // SHA3 for fixed-size hashing, SHAKE256 for the pre-image XOF 54 // _sfinx_hash(hash, in, in_len, out) 55 // _sfinx_shake256(in, in_len, out, out_len) 56 // the _batch forms drive the equal-length loops over keccak-fast's SIMD kernels 57 58 static inline void _sfinx_hash(sfinx_hash hash, const uint8_t *in, size_t in_len, uint8_t *out) { 59 switch (hash) { 60 case SFINX_HASH_224: kf_sha3_224(out, 28, in, in_len); break; 61 case SFINX_HASH_256: kf_sha3_256(out, 32, in, in_len); break; 62 case SFINX_HASH_384: kf_sha3_384(out, 48, in, in_len); break; 63 case SFINX_HASH_512: kf_sha3_512(out, 64, in, in_len); break; 64 } 65 } 66 67 static inline void _sfinx_hash_batch(sfinx_hash hash, size_t count, const uint8_t *in, size_t in_len, uint8_t *out, 68 size_t out_len) { 69 switch (hash) { 70 case SFINX_HASH_224: kf_sha3_224_batch(count, in, in_len, out, out_len); break; 71 case SFINX_HASH_256: kf_sha3_256_batch(count, in, in_len, out, out_len); break; 72 case SFINX_HASH_384: kf_sha3_384_batch(count, in, in_len, out, out_len); break; 73 case SFINX_HASH_512: kf_sha3_512_batch(count, in, in_len, out, out_len); break; 74 } 75 } 76 77 static inline void _sfinx_shake256(const uint8_t *in, size_t in_len, uint8_t *out, size_t out_len) { 78 kf_shake256(out, out_len, in, in_len); 79 } 80 81 static inline void _sfinx_shake256_batch(size_t count, const uint8_t *in, size_t in_len, uint8_t *out, size_t out_len) { 82 kf_shake256_batch(count, in, in_len, out, out_len); 83 } 84 85 size_t sfinx_hash_len(sfinx_hash hash) { 86 switch (hash) { 87 case SFINX_HASH_224: return 28; 88 case SFINX_HASH_256: return 32; 89 case SFINX_HASH_384: return 48; 90 case SFINX_HASH_512: return 64; 91 } 92 return 0; 93 } 94 95 static inline sfinx_hash _sfinx_hash_from_len(size_t len) { 96 switch (len) { 97 case 28: return SFINX_HASH_224; 98 case 32: return SFINX_HASH_256; 99 case 48: return SFINX_HASH_384; 100 case 64: return SFINX_HASH_512; 101 } 102 return 0; 103 } 104 105 #define SFINX_KID_ROOM(L) (197 - 3 * (L)) 106 #define SFINX_KID_LEN(L) ((L) < SFINX_KID_ROOM(L) ? (L) : SFINX_KID_ROOM(L)) 107 #define SFINX_CHAIN_FIT(L) ((L) + SFINX_KID_LEN(L) + 2 <= (200 - 2 * (L)) - 1) 108 109 _Static_assert(SFINX_CHAIN_FIT(28), "SHA3-224 chain step is not one permutation"); 110 _Static_assert(SFINX_CHAIN_FIT(32), "SHA3-256 chain step is not one permutation"); 111 _Static_assert(SFINX_CHAIN_FIT(48), "SHA3-384 chain step is not one permutation"); 112 _Static_assert(SFINX_CHAIN_FIT(64), "SHA3-512 chain step is not one permutation"); 113 114 static inline size_t _sfinx_kid_len(sfinx_hash hash) { 115 size_t len = sfinx_hash_len(hash); 116 return SFINX_KID_LEN(len); 117 } 118 119 static inline void _sfinx_kid(sfinx_hash hash, const uint8_t *suffix, size_t suffix_len, uint8_t *out) { 120 uint8_t full[SFINX_HASH_LEN_MAX]; 121 _sfinx_hash(hash, suffix, suffix_len, full); 122 memcpy(out, full, _sfinx_kid_len(hash)); 123 } 124 125 static inline void _sfinx_chain_batch(sfinx_hash hash, size_t count, uint8_t *x, const uint8_t *tail, size_t tail_len, 126 uint8_t from, uint32_t steps) { 127 size_t len = sfinx_hash_len(hash); 128 switch (hash) { 129 case SFINX_HASH_224: kf_sha3_224_chain(count, x, len, tail, tail_len, 1, from, steps); break; 130 case SFINX_HASH_256: kf_sha3_256_chain(count, x, len, tail, tail_len, 1, from, steps); break; 131 case SFINX_HASH_384: kf_sha3_384_chain(count, x, len, tail, tail_len, 1, from, steps); break; 132 case SFINX_HASH_512: kf_sha3_512_chain(count, x, len, tail, tail_len, 1, from, steps); break; 133 } 134 } 135 // }}} 136 137 // WOTS {{{ 138 // 139 // One WOTS key over an L-byte value, c = L + 2 chains of length 256 140 // preimage = SHAKE256(key), c * L bytes, c elements of L bytes 141 // digits = the value bytes, then 2 checksum bytes of 255 - value[i] 142 // pubkey = H of every element chained w times 143 // sign = every preimage element chained d[i] times 144 // rebuild = chain every proof element w - d[i] times, then the pubkey hash 145 // verify = rebuild over the value and compare to a known pubkey 146 147 #define SFINX_WOTS_BYTES_MAX ((SFINX_HASH_LEN_MAX + 2) * SFINX_HASH_LEN_MAX) 148 #define SFINX_WOTS_DIGITS_MAX (SFINX_HASH_LEN_MAX + 2) 149 #define SFINX_WOTS_TAIL_MAX ((SFINX_HASH_LEN_MAX + 2) * (SFINX_HASH_LEN_MAX + 1)) 150 151 // Cap on the seed-sized key staging buffer, so a large seed cannot force 256 copies at once 152 #ifndef SFINX_BATCH_KEY_BUDGET 153 #define SFINX_BATCH_KEY_BUDGET (64u * 1024u) 154 #endif 155 156 static inline void _sfinx_wots_preimage(sfinx_hash hash, const uint8_t *key, size_t key_len, uint8_t *out) { 157 size_t len = sfinx_hash_len(hash); 158 _sfinx_shake256(key, key_len, out, (len + 2) * len); 159 } 160 161 static inline void _sfinx_wots_digits(sfinx_hash hash, const uint8_t *value, uint8_t *out) { 162 size_t len = sfinx_hash_len(hash); 163 uint32_t checksum = 0; 164 for (size_t i = 0; i < len; i++) { 165 out[i] = value[i]; 166 checksum += 255 - value[i]; 167 } 168 out[len] = (uint8_t)(checksum >> 8); 169 out[len + 1] = (uint8_t)checksum; 170 } 171 172 static inline void _sfinx_wots_tails(sfinx_hash hash, const uint8_t *kid, uint8_t *out) { 173 size_t len = sfinx_hash_len(hash); 174 size_t k = _sfinx_kid_len(hash); 175 for (size_t i = 0; i < len + 2; i++) { 176 memcpy(out + i * (k + 1), kid, k); 177 out[i * (k + 1) + k] = (uint8_t)i; 178 } 179 } 180 181 static inline void _sfinx_wots_chain(sfinx_hash hash, uint8_t *node, const uint8_t *kid, uint8_t index, uint8_t from, 182 uint32_t steps) { 183 uint8_t tail[SFINX_HASH_LEN_MAX + 1]; 184 size_t k = _sfinx_kid_len(hash); 185 memcpy(tail, kid, k); 186 tail[k] = index; 187 _sfinx_chain_batch(hash, 1, node, tail, k + 1, from, steps); 188 } 189 190 static inline void _sfinx_wots_pubkey(sfinx_hash hash, const uint8_t *key, size_t key_len, size_t seed_len, 191 uint8_t *pubkey_out) { 192 size_t len = sfinx_hash_len(hash); 193 size_t count = len + 2; 194 size_t k = _sfinx_kid_len(hash); 195 uint8_t ends[SFINX_WOTS_BYTES_MAX]; 196 uint8_t kid[SFINX_HASH_LEN_MAX]; 197 uint8_t tails[SFINX_WOTS_TAIL_MAX]; 198 _sfinx_wots_preimage(hash, key, key_len, ends); 199 _sfinx_kid(hash, key + seed_len, key_len - seed_len, kid); 200 _sfinx_wots_tails(hash, kid, tails); 201 _sfinx_chain_batch(hash, count, ends, tails, k + 1, 0, 256); 202 _sfinx_hash(hash, ends, count * len, pubkey_out); 203 } 204 205 static inline sfinx_status _sfinx_wots_sign(sfinx_hash hash, const uint8_t *key, size_t key_len, size_t seed_len, 206 const uint8_t *value, size_t value_len, uint8_t *proof_out) { 207 size_t len = sfinx_hash_len(hash); 208 uint8_t digits[SFINX_WOTS_DIGITS_MAX]; 209 uint8_t kid[SFINX_HASH_LEN_MAX]; 210 if (len == 0 || value_len != len) { 211 return SFINX_ERR_ARGS; 212 } 213 _sfinx_wots_preimage(hash, key, key_len, proof_out); 214 _sfinx_wots_digits(hash, value, digits); 215 _sfinx_kid(hash, key + seed_len, key_len - seed_len, kid); 216 for (size_t i = 0; i < len + 2; i++) { 217 _sfinx_wots_chain(hash, proof_out + i * len, kid, (uint8_t)i, 0, digits[i]); 218 } 219 return SFINX_OK; 220 } 221 222 static inline void _sfinx_wots_rebuild(sfinx_hash hash, const uint8_t *value, const uint8_t *proof, const uint8_t *kid, 223 uint8_t *pubkey_out) { 224 size_t len = sfinx_hash_len(hash); 225 uint8_t digits[SFINX_WOTS_DIGITS_MAX]; 226 uint8_t ends[SFINX_WOTS_BYTES_MAX]; 227 uint8_t node[SFINX_HASH_LEN_MAX]; 228 _sfinx_wots_digits(hash, value, digits); 229 for (size_t i = 0; i < len + 2; i++) { 230 memcpy(node, proof + i * len, len); 231 _sfinx_wots_chain(hash, node, kid, (uint8_t)i, digits[i], 256 - digits[i]); 232 memcpy(ends + i * len, node, len); 233 } 234 _sfinx_hash(hash, ends, (len + 2) * len, pubkey_out); 235 } 236 237 static inline int _sfinx_wots_verify(sfinx_hash hash, const uint8_t *pubkey, const uint8_t *value, const uint8_t *proof, 238 const uint8_t *kid) { 239 uint8_t want[SFINX_HASH_LEN_MAX]; 240 _sfinx_wots_rebuild(hash, value, proof, kid, want); 241 return memcmp(want, pubkey, sfinx_hash_len(hash)) == 0; 242 } 243 // }}} 244 245 // Pool {{{ 246 // 247 // Compile-time worker pool for one top-level operation 248 // _REENTRANT: a round pulls indices from a shared counter, one scratch per worker 249 // otherwise, and for counts under two, the loop runs on the caller 250 251 typedef void (*_sfinx_job_fn)(void *ctx, size_t index, void *scratch); 252 253 #ifdef _REENTRANT 254 typedef struct { 255 struct _sfinx_pool *pool; 256 size_t index; 257 } _sfinx_worker; 258 #endif 259 260 typedef struct _sfinx_pool { 261 size_t count; 262 #ifdef _REENTRANT 263 pthread_t *threads; 264 _sfinx_worker *workers; 265 pthread_mutex_t mutex; 266 pthread_cond_t work; 267 pthread_cond_t done; 268 _sfinx_job_fn fn; 269 void *ctx; 270 size_t total; 271 size_t next; 272 size_t completed; 273 unsigned long round; 274 size_t scratch; 275 uint8_t *scratch_mem; 276 int stop; 277 #endif 278 } _sfinx_pool; 279 280 static inline size_t _sfinx_pool_scratch(size_t key_len) { 281 return key_len > SFINX_BATCH_KEY_BUDGET ? key_len : SFINX_BATCH_KEY_BUDGET; 282 } 283 284 #ifdef _REENTRANT 285 static void *_sfinx_pool_worker(void *arg) { 286 _sfinx_worker *worker = arg; 287 _sfinx_pool *pool = worker->pool; 288 uint8_t *scratch = pool->scratch_mem + (worker->index + 1) * pool->scratch; 289 unsigned long seen = 0; 290 291 for (;;) { 292 pthread_mutex_lock(&pool->mutex); 293 while (!pool->stop && pool->round == seen) { 294 pthread_cond_wait(&pool->work, &pool->mutex); 295 } 296 if (pool->stop) { 297 pthread_mutex_unlock(&pool->mutex); 298 return NULL; 299 } 300 seen = pool->round; 301 pthread_mutex_unlock(&pool->mutex); 302 for (;;) { 303 size_t i; 304 pthread_mutex_lock(&pool->mutex); 305 if (pool->next >= pool->total) { 306 pthread_mutex_unlock(&pool->mutex); 307 break; 308 } 309 i = pool->next++; 310 pthread_mutex_unlock(&pool->mutex); 311 pool->fn(pool->ctx, i, scratch); 312 pthread_mutex_lock(&pool->mutex); 313 pool->completed++; 314 if (pool->completed == pool->total) { 315 pthread_cond_broadcast(&pool->done); 316 } 317 pthread_mutex_unlock(&pool->mutex); 318 } 319 } 320 } 321 #endif 322 323 static void _sfinx_pool_destroy(_sfinx_pool *pool) { 324 #ifdef _REENTRANT 325 if (!pool) { 326 return; 327 } 328 pthread_mutex_lock(&pool->mutex); 329 pool->stop = 1; 330 pthread_cond_broadcast(&pool->work); 331 pthread_mutex_unlock(&pool->mutex); 332 for (size_t i = 0; i < pool->count; i++) { 333 pthread_join(pool->threads[i], NULL); 334 } 335 pthread_mutex_destroy(&pool->mutex); 336 pthread_cond_destroy(&pool->work); 337 pthread_cond_destroy(&pool->done); 338 free(pool->scratch_mem); 339 free(pool->threads); 340 free(pool->workers); 341 free(pool); 342 #else 343 (void)pool; 344 #endif 345 } 346 347 static _sfinx_pool *_sfinx_pool_create(size_t scratch) { 348 #ifdef _REENTRANT 349 _sfinx_pool *pool; 350 long n; 351 352 if (scratch == 0) { 353 scratch = 1; 354 } 355 n = sysconf(_SC_NPROCESSORS_ONLN); 356 if (n <= 1) { 357 return NULL; 358 } 359 pool = calloc(1, sizeof(*pool)); 360 if (!pool) { 361 return NULL; 362 } 363 pool->count = (size_t)n; 364 pool->scratch = scratch; 365 pool->scratch_mem = malloc((pool->count + 1) * scratch); 366 pool->threads = calloc(pool->count, sizeof(*pool->threads)); 367 pool->workers = calloc(pool->count, sizeof(*pool->workers)); 368 if (!pool->scratch_mem || !pool->threads || !pool->workers) { 369 free(pool->scratch_mem); 370 free(pool->threads); 371 free(pool->workers); 372 free(pool); 373 return NULL; 374 } 375 if (pthread_mutex_init(&pool->mutex, NULL) != 0) { 376 free(pool->scratch_mem); 377 free(pool->threads); 378 free(pool->workers); 379 free(pool); 380 return NULL; 381 } 382 if (pthread_cond_init(&pool->work, NULL) != 0) { 383 pthread_mutex_destroy(&pool->mutex); 384 free(pool->scratch_mem); 385 free(pool->threads); 386 free(pool->workers); 387 free(pool); 388 return NULL; 389 } 390 if (pthread_cond_init(&pool->done, NULL) != 0) { 391 pthread_cond_destroy(&pool->work); 392 pthread_mutex_destroy(&pool->mutex); 393 free(pool->scratch_mem); 394 free(pool->threads); 395 free(pool->workers); 396 free(pool); 397 return NULL; 398 } 399 for (size_t i = 0; i < pool->count; i++) { 400 pool->workers[i].pool = pool; 401 pool->workers[i].index = i; 402 } 403 for (size_t i = 0; i < pool->count; i++) { 404 if (pthread_create(&pool->threads[i], NULL, _sfinx_pool_worker, &pool->workers[i]) != 0) { 405 pool->count = i; 406 _sfinx_pool_destroy(pool); 407 return NULL; 408 } 409 } 410 return pool; 411 #else 412 (void)scratch; 413 return NULL; 414 #endif 415 } 416 417 static void _sfinx_parallel_for(_sfinx_pool *pool, size_t count, _sfinx_job_fn fn, void *ctx) { 418 uint8_t *scratch; 419 #ifdef _REENTRANT 420 if (pool && count >= 2) { 421 scratch = pool->scratch_mem; 422 pthread_mutex_lock(&pool->mutex); 423 pool->fn = fn; 424 pool->ctx = ctx; 425 pool->total = count; 426 pool->next = 0; 427 pool->completed = 0; 428 pool->round++; 429 pthread_cond_broadcast(&pool->work); 430 pthread_mutex_unlock(&pool->mutex); 431 for (;;) { 432 size_t i; 433 pthread_mutex_lock(&pool->mutex); 434 if (pool->next >= pool->total) { 435 pthread_mutex_unlock(&pool->mutex); 436 break; 437 } 438 i = pool->next++; 439 pthread_mutex_unlock(&pool->mutex); 440 fn(ctx, i, scratch); 441 pthread_mutex_lock(&pool->mutex); 442 pool->completed++; 443 if (pool->completed == pool->total) { 444 pthread_cond_broadcast(&pool->done); 445 } 446 pthread_mutex_unlock(&pool->mutex); 447 } 448 pthread_mutex_lock(&pool->mutex); 449 while (pool->completed < pool->total) { 450 pthread_cond_wait(&pool->done, &pool->mutex); 451 } 452 pthread_mutex_unlock(&pool->mutex); 453 return; 454 } 455 scratch = pool ? pool->scratch_mem : NULL; 456 #else 457 (void)pool; 458 scratch = NULL; 459 #endif 460 for (size_t i = 0; i < count; i++) { 461 fn(ctx, i, scratch); 462 } 463 } 464 // }}} 465 466 // Subtree {{{ 467 // 468 // One binary subtree of height 8, 256 WOTS leaves folded into a root 469 // leaf i is keyed by SHAKE256(seed | prefix | i) 470 // parent = H(bitlen | mask | prefix | left | right), the mask from the leaf index 471 // build returns the root, and for one leaf the 8 auth siblings, deepest first 472 // verify folds a leaf and its siblings back up to the root 473 474 static inline uint8_t _sfinx_node_mask(uint8_t bitlen, uint8_t index) { 475 return (uint8_t)(index & (0xFFu << (8 - bitlen))); 476 } 477 478 static inline void _sfinx_merkle_parent(sfinx_hash hash, uint8_t bitlen, uint8_t mask, const uint8_t *prefix, 479 size_t prefix_len, const uint8_t *left, const uint8_t *right, uint8_t *out) { 480 size_t len = sfinx_hash_len(hash); 481 uint8_t buf[2 + prefix_len + 2 * len]; 482 size_t at = 0; 483 buf[at++] = bitlen; 484 buf[at++] = mask; 485 if (prefix_len > 0) { 486 memcpy(buf + at, prefix, prefix_len); 487 at += prefix_len; 488 } 489 memcpy(buf + at, left, len); 490 at += len; 491 memcpy(buf + at, right, len); 492 at += len; 493 _sfinx_hash(hash, buf, at, out); 494 } 495 496 static inline void _sfinx_subtree_leaves(sfinx_hash hash, const uint8_t *seed, size_t seed_len, const uint8_t *prefix, 497 size_t prefix_len, size_t begin, size_t end, uint8_t *ends, uint8_t *nodes, 498 uint8_t *tails, uint8_t *keybuf) { 499 size_t len = sfinx_hash_len(hash); 500 size_t c = len + 2; 501 size_t k = _sfinx_kid_len(hash); 502 size_t key_len = seed_len + prefix_len + 1; 503 size_t tail_len = k + 1; 504 size_t chunk = SFINX_BATCH_KEY_BUDGET / key_len; 505 size_t n = end - begin; 506 507 if (chunk == 0) { 508 chunk = 1; 509 } 510 for (size_t base = 0; base < n; base += chunk) { 511 size_t m = n - base; 512 if (m > chunk) { 513 m = chunk; 514 } 515 for (size_t i = 0; i < m; i++) { 516 uint8_t *key = keybuf + i * key_len; 517 memcpy(key, seed, seed_len); 518 if (prefix_len > 0) { 519 memcpy(key + seed_len, prefix, prefix_len); 520 } 521 key[key_len - 1] = (uint8_t)(begin + base + i); 522 } 523 _sfinx_shake256_batch(m, keybuf, key_len, ends + (begin + base) * c * len, c * len); 524 for (size_t i = 0; i < m; i++) { 525 uint8_t kid[SFINX_HASH_LEN_MAX]; 526 uint8_t *key = keybuf + i * key_len; 527 _sfinx_kid(hash, key + seed_len, prefix_len + 1, kid); 528 _sfinx_wots_tails(hash, kid, tails + (begin + base + i) * c * tail_len); 529 } 530 } 531 _sfinx_chain_batch(hash, n * c, ends + begin * c * len, tails + begin * c * tail_len, tail_len, 0, 256); 532 _sfinx_hash_batch(hash, n, ends + begin * c * len, c * len, nodes + begin * len, len); 533 } 534 535 typedef struct { 536 sfinx_hash hash; 537 const uint8_t *seed; 538 size_t seed_len; 539 const uint8_t *prefix; 540 size_t prefix_len; 541 size_t chunk; 542 size_t count; 543 uint8_t *ends; 544 uint8_t *nodes; 545 uint8_t *tails; 546 } _sfinx_subtree_ctx; 547 548 static void _sfinx_subtree_job(void *vctx, size_t index, void *scratch) { 549 _sfinx_subtree_ctx *ctx = vctx; 550 size_t begin = index * ctx->chunk; 551 size_t end = begin + ctx->chunk; 552 553 if (end > ctx->count) { 554 end = ctx->count; 555 } 556 _sfinx_subtree_leaves(ctx->hash, ctx->seed, ctx->seed_len, ctx->prefix, ctx->prefix_len, begin, end, ctx->ends, 557 ctx->nodes, ctx->tails, scratch); 558 } 559 560 static inline int _sfinx_subtree_build(_sfinx_pool *pool, sfinx_hash hash, const uint8_t *seed, size_t seed_len, 561 const uint8_t *prefix, size_t prefix_len, uint8_t leaf_index, uint8_t *root_out, 562 uint8_t *auth_out) { 563 size_t len = sfinx_hash_len(hash); 564 size_t c = len + 2; 565 size_t key_len = seed_len + prefix_len + 1; 566 size_t tail_len = _sfinx_kid_len(hash) + 1; 567 size_t count = 256; 568 size_t pos = leaf_index; 569 uint8_t nodes[256 * SFINX_HASH_LEN_MAX]; 570 uint8_t *ends; 571 uint8_t *tails; 572 573 ends = malloc(count * c * len); 574 if (!ends) { 575 return 0; 576 } 577 tails = malloc(count * c * tail_len); 578 if (!tails) { 579 free(ends); 580 return 0; 581 } 582 if (pool) { 583 _sfinx_subtree_ctx ctx = { 584 .hash = hash, 585 .seed = seed, 586 .seed_len = seed_len, 587 .prefix = prefix, 588 .prefix_len = prefix_len, 589 .chunk = (count + pool->count - 1) / pool->count, 590 .count = count, 591 .ends = ends, 592 .nodes = nodes, 593 .tails = tails, 594 }; 595 size_t jobs; 596 if (ctx.chunk == 0) { 597 ctx.chunk = 1; 598 } 599 jobs = (count + ctx.chunk - 1) / ctx.chunk; 600 _sfinx_parallel_for(pool, jobs, _sfinx_subtree_job, &ctx); 601 } else { 602 size_t chunk = SFINX_BATCH_KEY_BUDGET / key_len; 603 uint8_t *keybuf; 604 if (chunk == 0) { 605 chunk = 1; 606 } 607 if (chunk > count) { 608 chunk = count; 609 } 610 keybuf = malloc(chunk * key_len); 611 if (!keybuf) { 612 free(tails); 613 free(ends); 614 return 0; 615 } 616 _sfinx_subtree_leaves(hash, seed, seed_len, prefix, prefix_len, 0, count, ends, nodes, tails, keybuf); 617 free(keybuf); 618 } 619 for (size_t bitlen = 8; bitlen-- > 0;) { 620 if (auth_out) { 621 memcpy(auth_out + (7 - bitlen) * len, nodes + (pos ^ 1) * len, len); 622 } 623 count /= 2; 624 for (size_t j = 0; j < count; j++) { 625 _sfinx_merkle_parent(hash, (uint8_t)bitlen, _sfinx_node_mask((uint8_t)bitlen, (uint8_t)(j << (8 - bitlen))), 626 prefix, prefix_len, nodes + (2 * j) * len, nodes + (2 * j + 1) * len, nodes + j * len); 627 } 628 pos >>= 1; 629 } 630 memcpy(root_out, nodes, len); 631 free(tails); 632 free(ends); 633 return 1; 634 } 635 636 static inline void _sfinx_subtree_verify(sfinx_hash hash, const uint8_t *prefix, size_t prefix_len, const uint8_t *leaf, 637 uint8_t leaf_index, const uint8_t *auth, uint8_t *root_out) { 638 size_t len = sfinx_hash_len(hash); 639 uint8_t node[SFINX_HASH_LEN_MAX]; 640 uint8_t tmp[SFINX_HASH_LEN_MAX]; 641 size_t pos = leaf_index; 642 memcpy(node, leaf, len); 643 for (size_t bitlen = 8; bitlen-- > 0;) { 644 uint8_t mask = _sfinx_node_mask((uint8_t)bitlen, (uint8_t)((pos >> 1) << (8 - bitlen))); 645 const uint8_t *sib = auth + (7 - bitlen) * len; 646 if (pos & 1) { 647 _sfinx_merkle_parent(hash, (uint8_t)bitlen, mask, prefix, prefix_len, sib, node, tmp); 648 } else { 649 _sfinx_merkle_parent(hash, (uint8_t)bitlen, mask, prefix, prefix_len, node, sib, tmp); 650 } 651 memcpy(node, tmp, len); 652 pos >>= 1; 653 } 654 memcpy(root_out, node, len); 655 } 656 // }}} 657 658 // API - Sign {{{ 659 // 660 // Thin wrappers over WOTS and Subtree, one WOTS per layer 661 // single = one WOTS over SHAKE256(seed), signs H(message) 662 // tree = N subtrees, layer k signs R_k, R_N = org = H(path | message) 663 664 sfinx_status sfinx_single_public_key(sfinx_hash hash, const uint8_t *seed, size_t seed_len, uint8_t *pubkey_out, 665 size_t pubkey_cap, size_t *pubkey_len_out) { 666 size_t len = sfinx_hash_len(hash); 667 if (len == 0 || !seed || seed_len > SFINX_SEED_LEN_MAX) { 668 return SFINX_ERR_ARGS; 669 } 670 if (!pubkey_out || pubkey_cap < len) { 671 return SFINX_ERR_NOSPACE; 672 } 673 _sfinx_wots_pubkey(hash, seed, seed_len, seed_len, pubkey_out); 674 if (pubkey_len_out) { 675 *pubkey_len_out = len; 676 } 677 return SFINX_OK; 678 } 679 680 sfinx_status sfinx_single_sign(sfinx_hash hash, const uint8_t *seed, size_t seed_len, const uint8_t *msg, 681 size_t msg_len, uint8_t *sig, size_t sig_cap, size_t *sig_len_out) { 682 size_t len = sfinx_hash_len(hash); 683 size_t need = sfinx_signature_len(hash, 0); 684 uint8_t org[SFINX_HASH_LEN_MAX]; 685 if (len == 0 || !seed || !msg || seed_len > SFINX_SEED_LEN_MAX) { 686 return SFINX_ERR_ARGS; 687 } 688 if (!sig || sig_cap < need) { 689 return SFINX_ERR_NOSPACE; 690 } 691 _sfinx_hash(hash, msg, msg_len, org); 692 _sfinx_e4m4_encode(0, sig); 693 _sfinx_e4m4_encode((uint32_t)len, sig + 1); 694 if (_sfinx_wots_sign(hash, seed, seed_len, seed_len, org, len, sig + 2) != SFINX_OK) { 695 return SFINX_ERR_ARGS; 696 } 697 if (sig_len_out) { 698 *sig_len_out = need; 699 } 700 return SFINX_OK; 701 } 702 703 sfinx_status sfinx_tree_public_key(sfinx_hash hash, const uint8_t *seed, size_t seed_len, size_t path_len, 704 uint8_t *pubkey_out, size_t pubkey_cap, size_t *pubkey_len_out) { 705 size_t len = sfinx_hash_len(hash); 706 uint8_t prefix; 707 _sfinx_pool *pool; 708 int ok; 709 if (len == 0 || !seed || seed_len > SFINX_SEED_LEN_MAX) { 710 return SFINX_ERR_ARGS; 711 } 712 if (path_len == 0 || !sfinx_path_len_valid(path_len)) { 713 return SFINX_ERR_PATH_LEN; 714 } 715 if (!pubkey_out || pubkey_cap < len) { 716 return SFINX_ERR_NOSPACE; 717 } 718 _sfinx_e4m4_encode((uint32_t)path_len, &prefix); 719 pool = _sfinx_pool_create(_sfinx_pool_scratch(seed_len + 2)); 720 ok = _sfinx_subtree_build(pool, hash, seed, seed_len, &prefix, 1, 0, pubkey_out, NULL); 721 _sfinx_pool_destroy(pool); 722 if (!ok) { 723 return SFINX_ERR_NOSPACE; 724 } 725 if (pubkey_len_out) { 726 *pubkey_len_out = len; 727 } 728 return SFINX_OK; 729 } 730 731 sfinx_status sfinx_tree_sign(sfinx_hash hash, const uint8_t *seed, size_t seed_len, const uint8_t *path, 732 size_t path_len, const uint8_t *msg, size_t msg_len, uint8_t *sig, size_t sig_cap, 733 size_t *sig_len_out) { 734 size_t len = sfinx_hash_len(hash); 735 size_t c = len + 2; 736 size_t need = sfinx_signature_len(hash, path_len); 737 uint8_t org[SFINX_HASH_LEN_MAX]; 738 uint8_t value[SFINX_HASH_LEN_MAX]; 739 uint8_t root[SFINX_HASH_LEN_MAX]; 740 uint8_t auth[8 * SFINX_HASH_LEN_MAX]; 741 uint8_t *key; 742 uint8_t *joined; 743 size_t at; 744 _sfinx_pool *pool; 745 746 if (len == 0 || !seed || !msg || seed_len > SFINX_SEED_LEN_MAX || !path || path_len == 0 || 747 !sfinx_path_len_valid(path_len)) { 748 return SFINX_ERR_ARGS; 749 } 750 if (!sig || sig_cap < need) { 751 return SFINX_ERR_NOSPACE; 752 } 753 joined = malloc(path_len + msg_len); 754 key = malloc(seed_len + path_len + 1); 755 if (!joined || !key) { 756 free(joined); 757 free(key); 758 return SFINX_ERR_NOSPACE; 759 } 760 pool = _sfinx_pool_create(_sfinx_pool_scratch(seed_len + path_len + 1)); 761 // Sign (path||message) 762 memcpy(joined, path, path_len); 763 memcpy(joined + path_len, msg, msg_len); 764 _sfinx_hash(hash, joined, path_len + msg_len, org); 765 free(joined); 766 767 // Prep sig header, sig[0..path_len] is also the derivation prefix 768 _sfinx_e4m4_encode((uint32_t)path_len, sig); 769 memcpy(sig + 1, path, path_len); 770 at = 1 + path_len; 771 _sfinx_e4m4_encode((uint32_t)len, sig + at); 772 at += 1; 773 774 memcpy(key, seed, seed_len); 775 memcpy(key + seed_len, sig, path_len + 1); 776 777 // WOTS-sign up the tree 778 memcpy(value, org, len); 779 for (size_t k = path_len; k >= 1; k--) { 780 if (!_sfinx_subtree_build(pool, hash, seed, seed_len, sig, k, sig[k], root, auth)) { 781 _sfinx_pool_destroy(pool); 782 free(key); 783 return SFINX_ERR_NOSPACE; 784 } 785 if (_sfinx_wots_sign(hash, key, seed_len + k + 1, seed_len, value, len, sig + at) != SFINX_OK) { 786 _sfinx_pool_destroy(pool); 787 free(key); 788 return SFINX_ERR_ARGS; 789 } 790 at += c * len; 791 memcpy(sig + at, auth, 8 * len); 792 at += 8 * len; 793 memcpy(value, root, len); 794 } 795 796 _sfinx_pool_destroy(pool); 797 free(key); 798 if (sig_len_out) { 799 *sig_len_out = need; 800 } 801 return SFINX_OK; 802 } 803 804 // }}} 805 806 // API - Verify {{{ 807 // 808 // Parse the layout, then walk from the top round down 809 // single: rebuild the one WOTS pubkey over H(message) and compare 810 // tree: rebuild layer k over R_k, fold subtree k-1 to R_{k-1}, R_0 is the pubkey 811 812 sfinx_status sfinx_verify(const uint8_t *pubkey, size_t pubkey_len, const uint8_t *msg, size_t msg_len, 813 const uint8_t *sig, size_t sig_len) { 814 size_t path_len; 815 size_t len; 816 size_t c; 817 size_t at; 818 sfinx_hash hash; 819 uint8_t org[SFINX_HASH_LEN_MAX]; 820 uint8_t value[SFINX_HASH_LEN_MAX]; 821 uint8_t leaf[SFINX_HASH_LEN_MAX]; 822 uint8_t root[SFINX_HASH_LEN_MAX]; 823 uint8_t kid[SFINX_HASH_LEN_MAX]; 824 const uint8_t *path; 825 uint8_t *joined; 826 827 if (!pubkey || !msg || !sig || sig_len < 2) { 828 return SFINX_ERR_ARGS; 829 } 830 path_len = _sfinx_e4m4_decode(sig[0]); 831 path = sig + 1; 832 at = 1 + path_len; 833 if (!sfinx_path_len_valid(path_len) || sig_len < at + 1) { 834 return SFINX_ERR_FORMAT; 835 } 836 len = _sfinx_e4m4_decode(sig[at]); 837 at += 1; 838 hash = _sfinx_hash_from_len(len); 839 if (!hash || len != pubkey_len || sig_len != sfinx_signature_len(hash, path_len)) { 840 return SFINX_ERR_FORMAT; 841 } 842 c = len + 2; 843 if (path_len == 0) { 844 _sfinx_hash(hash, msg, msg_len, org); 845 _sfinx_kid(hash, NULL, 0, kid); 846 return _sfinx_wots_verify(hash, pubkey, org, sig + at, kid) ? SFINX_OK : SFINX_ERR_VERIFY; 847 } 848 joined = malloc(path_len + msg_len); 849 if (!joined) { 850 return SFINX_ERR_NOSPACE; 851 } 852 memcpy(joined, path, path_len); 853 memcpy(joined + path_len, msg, msg_len); 854 _sfinx_hash(hash, joined, path_len + msg_len, org); 855 free(joined); 856 memcpy(value, org, len); 857 for (size_t k = path_len; k >= 1; k--) { 858 _sfinx_kid(hash, sig, k + 1, kid); 859 _sfinx_wots_rebuild(hash, value, sig + at, kid, leaf); 860 at += c * len; 861 _sfinx_subtree_verify(hash, sig, k, leaf, sig[k], sig + at, root); 862 at += 8 * len; 863 if (k == 1) { 864 return memcmp(root, pubkey, len) == 0 ? SFINX_OK : SFINX_ERR_VERIFY; 865 } 866 memcpy(value, root, len); 867 } 868 return SFINX_ERR_FORMAT; 869 } 870 // }}} 871 872 // API - Utilities {{{ 873 // 874 // Pure size helpers, status names, and the optional RNG 875 // sizes = E4M4(N) | path | E4M4(L) | N rounds of WOTS proof and auth path 876 877 const char *sfinx_strerror(sfinx_status status) { 878 switch (status) { 879 case SFINX_OK: return "ok"; 880 case SFINX_ERR_ARGS: return "invalid arguments"; 881 case SFINX_ERR_PATH_LEN: return "invalid path length"; 882 case SFINX_ERR_NOSPACE: return "no space available"; 883 case SFINX_ERR_FORMAT: return "invalid signature format"; 884 case SFINX_ERR_VERIFY: return "verification failed"; 885 case SFINX_ERR_RANDOM: return "random source failed"; 886 case SFINX_ERR_UNIMPLEMENTED: return "unimplemented"; 887 } 888 return "unknown error"; 889 } 890 891 #ifndef SFINX_VERSION 892 #define SFINX_VERSION "n/a-dev" 893 #endif 894 895 const char *sfinx_version(void) { 896 return SFINX_VERSION; 897 } 898 899 size_t sfinx_signature_len(sfinx_hash hash, size_t path_len) { 900 size_t len = sfinx_hash_len(hash); 901 if (len == 0) { 902 return 0; 903 } 904 if (path_len == 0) { 905 return 2 + (len + 2) * len; 906 } 907 return 2 + path_len + path_len * (len + 10) * len; 908 } 909 910 size_t sfinx_signature_len_max(sfinx_hash hash) { 911 return sfinx_signature_len(hash, SFINX_PATH_LEN_MAX); 912 } 913 914 int sfinx_path_len_valid(size_t path_len) { 915 uint8_t byte; 916 return path_len <= SFINX_PATH_LEN_MAX && _sfinx_e4m4_encode((uint32_t)path_len, &byte); 917 } 918 919 sfinx_status sfinx_signature_info(const uint8_t *sig, size_t sig_len, sfinx_hash *hash_out, size_t *path_len_out) { 920 size_t path_len; 921 sfinx_hash hash; 922 if (!sig || sig_len < 2) { 923 return SFINX_ERR_ARGS; 924 } 925 path_len = _sfinx_e4m4_decode(sig[0]); 926 if (!sfinx_path_len_valid(path_len) || sig_len < 2 + path_len) { 927 return SFINX_ERR_FORMAT; 928 } 929 hash = _sfinx_hash_from_len(_sfinx_e4m4_decode(sig[1 + path_len])); 930 if (!hash) { 931 return SFINX_ERR_FORMAT; 932 } 933 if (hash_out) { 934 *hash_out = hash; 935 } 936 if (path_len_out) { 937 *path_len_out = path_len; 938 } 939 return SFINX_OK; 940 } 941 942 sfinx_status sfinx_random_bytes(uint8_t *out, size_t len) { 943 if (!out) { 944 return SFINX_ERR_ARGS; 945 } 946 while (len > 0) { 947 size_t chunk = len > 256 ? 256 : len; 948 if (getentropy(out, chunk) != 0) { 949 return SFINX_ERR_RANDOM; 950 } 951 out += chunk; 952 len -= chunk; 953 } 954 return SFINX_OK; 955 } 956 // }}} 957 958 // vim:fdm=marker:fdl=0