luna - wolfssl/wolfcrypt/src/wc_xmss

   1/* wc_xmss_impl.c
   2 *
   3 * Copyright (C) 2006-2026 wolfSSL Inc.
   4 *
   5 * This file is part of wolfSSL.
   6 *
   7 * wolfSSL is free software; you can redistribute it and/or modify
   8 * it under the terms of the GNU General Public License as published by
   9 * the Free Software Foundation; either version 3 of the License, or
  10 * (at your option) any later version.
  11 *
  12 * wolfSSL is distributed in the hope that it will be useful,
  13 * but WITHOUT ANY WARRANTY; without even the implied warranty of
  14 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  15 * GNU General Public License for more details.
  16 *
  17 * You should have received a copy of the GNU General Public License
  18 * along with this program; if not, write to the Free Software
  19 * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1335, USA
  20 */
  21
  22/* Based on:
  23 *  o RFC 8391 - XMSS: eXtended Merkle Signature Scheme
  24 *  o [HDSS] "Hash-based Digital Signature Schemes", Buchmann, Dahmen and Szydlo
  25 *    from "Post Quantum Cryptography", Springer 2009.
  26 *  o [OPX] "Optimal Parameters for XMSS^MT", Hulsing, Rausch and Buchmann
  27 *
  28 * TODO: "Simple and Memory-efficient Signature Generation of XMSS^MT"
  29 *       (https://ece.engr.uvic.ca/~raltawy/SAC2021/9.pdf)
  30 */
  31
  32#include <wolfssl/wolfcrypt/libwolfssl_sources.h>
  33
  34#include <wolfssl/wolfcrypt/wc_xmss.h>
  35#include <wolfssl/wolfcrypt/hash.h>
  36
  37#ifdef NO_INLINE
  38    #include <wolfssl/wolfcrypt/misc.h>
  39#else
  40    #define WOLFSSL_MISC_INCLUDED
  41    #include <wolfcrypt/src/misc.c>
  42#endif
  43
  44#if defined(WOLFSSL_HAVE_XMSS)
  45
  46/* Indices into Hash Address. */
  47#define XMSS_ADDR_LAYER                 0
  48#define XMSS_ADDR_TREE_HI               1
  49#define XMSS_ADDR_TREE                  2
  50#define XMSS_ADDR_TYPE                  3
  51#define XMSS_ADDR_OTS                   4
  52#define XMSS_ADDR_LTREE                 4
  53#define XMSS_ADDR_TREE_ZERO             4
  54#define XMSS_ADDR_CHAIN                 5
  55#define XMSS_ADDR_TREE_HEIGHT           5
  56#define XMSS_ADDR_HASH                  6
  57#define XMSS_ADDR_TREE_INDEX            6
  58#define XMSS_ADDR_KEY_MASK              7
  59
  60/* Types of hash addresses. */
  61#define WC_XMSS_ADDR_TYPE_OTS        0
  62#define WC_XMSS_ADDR_TYPE_LTREE      1
  63#define WC_XMSS_ADDR_TYPE_TREE       2
  64
  65/* Byte to include in hash to create unique sequence. */
  66#define XMSS_HASH_PADDING_F             0U
  67#define XMSS_HASH_PADDING_H             1U
  68#define XMSS_HASH_PADDING_HASH          2U
  69#define XMSS_HASH_PADDING_PRF           3U
  70#define XMSS_HASH_PADDING_PRF_KEYGEN    4U
  71
  72/* Fixed parameter values. */
  73#define XMSS_WOTS_W                     16U
  74#define XMSS_WOTS_LOG_W                 4U
  75#define XMSS_WOTS_LEN2                  3U
  76#define XMSS_CSUM_SHIFT                 4U
  77#define XMSS_CSUM_LEN                   2U
  78
  79/* Length of the message to the PRF. */
  80#define XMSS_PRF_M_LEN                  32U
  81
  82/* Length of index encoding when doing XMSS. */
  83#define XMSS_IDX_LEN                    4U
  84
  85/* Size of the N when using SHA-256 and 32 byte padding. */
  86#define XMSS_SHA256_32_N                WC_SHA256_DIGEST_SIZE
  87/* Size of the padding when using SHA-256 and 32 byte padding. */
  88#define XMSS_SHA256_32_PAD_LEN          32U
  89
  90/* Calculate PRF data length for parameters. */
  91#define XMSS_HASH_PRF_DATA_LEN(params)                              \
  92    ((word32)(params)->pad_len + (params)->n + WC_XMSS_ADDR_LEN)
  93/* PRF data length when using SHA-256 with 32 byte padding. */
  94#define XMSS_HASH_PRF_DATA_LEN_SHA256_32                            \
  95    (XMSS_SHA256_32_PAD_LEN + XMSS_SHA256_32_N + WC_XMSS_ADDR_LEN)
  96
  97/* Calculate chain hash data length for parameters. */
  98#define XMSS_CHAIN_HASH_DATA_LEN(params)                            \
  99    ((word32)(params)->pad_len + 2U * (params)->n)
 100/* Chain hash data length when using SHA-256 with 32 byte padding. */
 101#define XMSS_CHAIN_HASH_DATA_LEN_SHA256_32                          \
 102    (XMSS_SHA256_32_PAD_LEN + 2U * XMSS_SHA256_32_N)
 103
 104/* Calculate rand hash data length for parameters. */
 105#define XMSS_RAND_HASH_DATA_LEN(params)                             \
 106    ((word32)(params)->pad_len + 3U * (params)->n)
 107/* Rand hash data length when using SHA-256 with 32 byte padding. */
 108#define XMSS_RAND_HASH_DATA_LEN_SHA256_32                           \
 109    (XMSS_SHA256_32_PAD_LEN + 3U * XMSS_SHA256_32_N)
 110
 111/* Encode pad value into byte array. Front fill with 0s.
 112 *
 113 * RFC 8391: 2.4
 114 *
 115 * @param [in]  n   Number to encode.
 116 * @param [out] a   Array to hold encoding.
 117 * @param [in]  l   Length of array.
 118 */
 119#define XMSS_PAD_ENC(n, a, l)   \
 120do {                            \
 121    XMEMSET(a, 0, l);           \
 122    (a)[(l) - 1] = (byte)(n);   \
 123} while (0)
 124
 125
 126/********************************************
 127 * Index 32/64 bits
 128 ********************************************/
 129
 130/* Index of 32 or 64 bits. */
 131typedef union wc_Idx {
 132#if WOLFSSL_XMSS_MAX_HEIGHT > 32
 133    /* 64-bit representation. */
 134    w64wrapper u64;
 135#endif
 136#if WOLFSSL_XMSS_MIN_HEIGHT <= 32
 137    /* 32-bit representation. */
 138    word32     u32;
 139#endif
 140} wc_Idx;
 141
 142#if WOLFSSL_XMSS_MAX_HEIGHT > 32
 143/* Set index to zero.
 144 *
 145 * Index is up to 64-bits.
 146 *
 147 * @param [out] idx  32/64-bit index to zero.
 148 */
 149#define WC_IDX_ZERO(idx)    w64Zero(&(idx).u64)
 150#else
 151/* Set index to zero.
 152 *
 153 * Index is no more than 32-bits.
 154 *
 155 * @param [out] idx  32/64-bit index to zero.
 156 */
 157#define WC_IDX_ZERO(idx)    idx.u32 = 0
 158#endif
 159
 160#if WOLFSSL_XMSS_MAX_HEIGHT > 32
 161/* Decode 64-bit index.
 162 *
 163 * @param [out] i    Index from encoding.
 164 * @param [in]  c    Count of bytes to decode to index.
 165 * @param [in]  a    Array to decode from.
 166 * @param [out] ret  Return value.
 167 */
 168#define IDX64_DECODE(i, c, a, ret)                      \
 169    if ((c) == 5) {                                     \
 170        word32 t;                                       \
 171        ato32((a) + 1, &t);                             \
 172        (i) = w64From32((a)[0], t);                     \
 173    }                                                   \
 174    else if ((c) == 8) {                                \
 175        ato64(a, &(i));                                 \
 176    }
 177
 178/* Decode 64-bit index.
 179 *
 180 * @param [out] i    Index from encoding.
 181 * @param [in]  c    Count of bytes to decode to index.
 182 * @param [in]  a    Array to decode from.
 183 * @param [out] ret  Return value.
 184 */
 185#define XMSS_IDX64_DECODE(i, c, a, ret)                 \
 186do {                                                    \
 187    IDX64_DECODE(i, c, a, ret)                          \
 188    else {                                              \
 189        (ret) = NOT_COMPILED_IN;                        \
 190    }                                                   \
 191} while (0)
 192
 193/* Check whether index is valid.
 194 *
 195 * @param [in] i  Index to check.
 196 * @param [in] c  Count of bytes i was encoded in.
 197 * @param [in] h  Full tree Height.
 198 */
 199#define IDX64_INVALID(i, c, h)                              \
 200    ((w64GetHigh32(w64Add32(i, 1, NULL)) >> ((h) - 32)) != 0)
 201
 202/* Set 64-bit index as hash address value for tree.
 203 *
 204 * @param [in]  i  Index to set.
 205 * @param [in]  c  Count of bytes to encode into.
 206 * @param [in]  h  Height of tree.
 207 * @param [out] a  Hash address to encode into.
 208 * @param [out] l  Index of leaf.
 209 */
 210#define IDX64_SET_ADDR_TREE(i, c, h, a, l)                 \
 211    if ((c) > 4) {                                         \
 212        (l) = w64GetLow32(i) & (((word32)1U << (h)) - 1U); \
 213        (i) = w64ShiftRight(i, h);                         \
 214        (a)[XMSS_ADDR_TREE_HI] = w64GetHigh32(i);          \
 215        (a)[XMSS_ADDR_TREE] = w64GetLow32(i);              \
 216    }
 217#endif /* WOLFSSL_XMSS_MAX_HEIGHT > 32 */
 218
 219#if WOLFSSL_XMSS_MIN_HEIGHT <= 32
 220/* Decode 32-bit index.
 221 *
 222 * @param [out] i    Index from encoding.
 223 * @param [in]  c    Count of bytes to decode to index.
 224 * @param [in]  a    Array to decode from.
 225 * @param [out] ret  Return value.
 226 */
 227#define IDX32_DECODE(i, c, a, ret)                      \
 228    if ((c) == 4) {                                     \
 229        ato32(a, &(i));                                 \
 230    }                                                   \
 231    else if ((c) == 3) {                                \
 232        ato24(a, &(i));                                 \
 233    }
 234
 235/* Decode 32-bit index.
 236 *
 237 * @param [out] i    Index from encoding.
 238 * @param [in]  c    Count of bytes to decode to index.
 239 * @param [in]  a    Array to decode from.
 240 * @param [out] ret  Return value.
 241 */
 242#define XMSS_IDX32_DECODE(i, c, a, ret)                 \
 243do {                                                    \
 244    IDX32_DECODE(i, c, a, ret)                          \
 245    else {                                              \
 246        (ret) = NOT_COMPILED_IN;                        \
 247    }                                                   \
 248} while (0)
 249
 250/* Check whether 32-bit index is valid.
 251 *
 252 * @param [in] i  Index to check.
 253 * @param [in] c  Count of bytes i was encoded in.
 254 * @param [in] h  Full tree Height.
 255 */
 256#define IDX32_INVALID(i, c, h)                          \
 257    ((((i) + 1) >> (h)) != 0)
 258
 259/* Set 32-bit index as hash address value for tree.
 260 *
 261 * @param [in]  i  Index to set.
 262 * @param [in]  c  Count of bytes to encode into.
 263 * @param [in]  h  Height of tree.
 264 * @param [out] a  Hash address to encode into.
 265 * @param [out] l  Index of leaf.
 266 */
 267#define IDX32_SET_ADDR_TREE(i, c, h, a, l)              \
 268    if ((c) <= 4) {                                     \
 269        (l) = ((i) & (((word32)1U << (h)) - 1U));       \
 270        (i) >>= params->sub_h;                          \
 271        (a)[XMSS_ADDR_TREE] = (i);                      \
 272    }
 273
 274#endif /* WOLFSSL_XMSS_MIN_HEIGHT <= 32 */
 275
 276#if (WOLFSSL_XMSS_MAX_HEIGHT > 32) && (WOLFSSL_XMSS_MIN_HEIGHT <= 32)
 277
 278/* Decode 32/64-bit index.
 279 *
 280 * @param [out] idx  Index from encoding.
 281 * @param [in]  c    Count of bytes to decode to index.
 282 * @param [in]  a    Array to decode from.
 283 * @param [out] ret  Return value.
 284 */
 285#define WC_IDX_DECODE(idx, c, a, ret)                   \
 286do {                                                    \
 287    IDX64_DECODE((idx).u64, c, a, ret)                  \
 288    else                                                \
 289    IDX32_DECODE((idx).u32, c, a, ret)                  \
 290    else {                                              \
 291        (ret) = NOT_COMPILED_IN;                        \
 292    }                                                   \
 293} while (0)
 294
 295/* Check whether index is valid.
 296 *
 297 * @param [in] i  Index to check.
 298 * @param [in] c  Count of bytes i was encoded in.
 299 * @param [in] h  Full tree Height.
 300 */
 301#define WC_IDX_INVALID(i, c, h)                         \
 302    ((((c) >  4) && IDX64_INVALID((i).u64, c, h)) ||    \
 303     (((c) <= 4) && IDX32_INVALID((i).u32, c, h)))
 304
 305/* Set 32/64-bit index as hash address value for tree.
 306 *
 307 * @param [in]  i  Index to set.
 308 * @param [in]  c  Count of bytes to encode into.
 309 * @param [in]  h  Height of tree.
 310 * @param [out] a  Hash address to encode into.
 311 * @param [out] l  Index of leaf.
 312 */
 313#define WC_IDX_SET_ADDR_TREE(idx, c, h, a, l)           \
 314do {                                                    \
 315    IDX64_SET_ADDR_TREE((idx).u64, c, h, a, l)          \
 316    else                                                \
 317    IDX32_SET_ADDR_TREE((idx).u32, c, h, a, l)          \
 318} while (0)
 319
 320#elif WOLFSSL_XMSS_MAX_HEIGHT > 32
 321
 322/* Decode 64-bit index.
 323 *
 324 * @param [out] idx  Index from encoding.
 325 * @param [in]  c    Count of bytes to decode to index.
 326 * @param [in]  a    Array to decode from.
 327 * @param [out] ret  Return value.
 328 */
 329#define WC_IDX_DECODE(idx, c, a, ret)                   \
 330do {                                                    \
 331    IDX64_DECODE((idx).u64, c, a, ret)                  \
 332} while (0)
 333
 334/* Check whether index is valid.
 335 *
 336 * @param [in] i  Index to check.
 337 * @param [in] c  Count of bytes i was encoded in.
 338 * @param [in] h  Full tree Height.
 339 */
 340#define WC_IDX_INVALID(i, c, h)                         \
 341    IDX64_INVALID((i).u64, c, h)
 342
 343/* Set 64-bit index as hash address value for tree.
 344 *
 345 * @param [in]  i  Index to set.
 346 * @param [in]  c  Count of bytes to encode into.
 347 * @param [in]  h  Height of tree.
 348 * @param [out] a  Hash address to encode into.
 349 * @param [out] l  Index of leaf.
 350 */
 351#define WC_IDX_SET_ADDR_TREE(idx, c, h, a, l)           \
 352do {                                                    \
 353    IDX64_SET_ADDR_TREE((idx).u64, c, h, a, l)          \
 354} while (0)
 355
 356#else
 357
 358/* Decode 32-bit index.
 359 *
 360 * @param [out] idx  Index from encoding.
 361 * @param [in]  c    Count of bytes to decode to index.
 362 * @param [in]  a    Array to decode from.
 363 * @param [out] ret  Return value.
 364 */
 365#define WC_IDX_DECODE(idx, c, a, ret)                   \
 366do {                                                    \
 367    IDX32_DECODE((idx).u32, c, a, ret)                  \
 368    else {                                              \
 369        (ret) = NOT_COMPILED_IN;                        \
 370    }                                                   \
 371} while (0)
 372
 373/* Check whether index is valid.
 374 *
 375 * @param [in] i  Index to check.
 376 * @param [in] c  Count of bytes i was encoded in.
 377 * @param [in] h  Full tree Height.
 378 */
 379#define WC_IDX_INVALID(i, c, h)                         \
 380    IDX32_INVALID((i).u32, c, h)
 381
 382/* Set 32-bit index as hash address value for tree.
 383 *
 384 * @param [in]  i  Index to set.
 385 * @param [in]  c  Count of bytes to encode into.
 386 * @param [in]  h  Height of tree.
 387 * @param [out] a  Hash address to encode into.
 388 * @param [out] l  Index of leaf.
 389 */
 390#define WC_IDX_SET_ADDR_TREE(idx, c, h, a, l)           \
 391do {                                                    \
 392    IDX32_SET_ADDR_TREE(idx.u32, c, h, a, l)            \
 393} while (0)
 394
 395#endif /* (WOLFSSL_XMSS_MAX_HEIGHT > 32) && (WOLFSSL_XMSS_MIN_HEIGHT <= 32) */
 396
 397#ifndef WOLFSSL_XMSS_VERIFY_ONLY
 398/* Update index by adding one to big-endian encoded value.
 399 *
 400 * @param [in, out] a  Array index is encoded in.
 401 * @param [in]      l  Length of encoded index.
 402 */
 403static void wc_idx_update(unsigned char* a, word32 l)
 404{
 405    word32 i;
 406
 407    for (i = l; i > 0; i--) {
 408        if ((++a[i - 1]) != 0) {
 409            break;
 410        }
 411    }
 412}
 413
 414/* Copy index from source buffer to destination buffer.
 415 *
 416 * Index is put in the back of the destination buffer.
 417 *
 418 * @param [in]      s   Source buffer.
 419 * @param [in]      sl  Length of index in source.
 420 * @param [in, out] d   Destination buffer.
 421 * @param [in]      dl  Length of destination buffer.
 422 */
 423static void wc_idx_copy(const unsigned char* s, word32 sl, unsigned char* d,
 424    word32 dl)
 425{
 426    /* Zero the destination first so an invariant violation produces a
 427     * deterministic empty buffer rather than reusing prior contents. */
 428    XMEMSET(d, 0, dl);
 429    /* Caller must size the destination at least as large as the source.
 430     * Without this guard, dl - sl wraps to ~4 GB and corrupts memory. */
 431    if (dl < sl) {
 432        return;
 433    }
 434    XMEMCPY(d + dl - sl, s, sl);
 435}
 436#endif
 437
 438/********************************************
 439 * Hash Address.
 440 ********************************************/
 441
 442/* Set the hash address based on subtree.
 443 *
 444 * @param [out] a  Hash address.
 445 * @param [in]  s  Subtree hash address.
 446 * @param [in]  t  Type of hash address.
 447 */
 448#define XMSS_ADDR_SET_SUBTREE(a, s, t)                \
 449do {                                                  \
 450    (a)[XMSS_ADDR_LAYER]   = (s)[XMSS_ADDR_LAYER];    \
 451    (a)[XMSS_ADDR_TREE_HI] = (s)[XMSS_ADDR_TREE_HI];  \
 452    (a)[XMSS_ADDR_TREE]    = (s)[XMSS_ADDR_TREE];     \
 453    (a)[XMSS_ADDR_TYPE]    = (t);                     \
 454    XMEMSET((a) + 4, 0, sizeof(a) - 4 * sizeof(*(a)));\
 455} while (0)
 456
 457/* Set the OTS hash address based on subtree.
 458 *
 459 * @param [out] a  Hash address.
 460 * @param [in]  s  Subtree hash address.
 461 */
 462#define XMSS_ADDR_OTS_SET_SUBTREE(a, s) \
 463    XMSS_ADDR_SET_SUBTREE(a, s, WC_XMSS_ADDR_TYPE_OTS)
 464/* Set the L-tree address based on subtree.
 465 *
 466 * @param [out] a  Hash address.
 467 * @param [in]  s  Subtree hash address.
 468 */
 469#define XMSS_ADDR_LTREE_SET_SUBTREE(a, s) \
 470    XMSS_ADDR_SET_SUBTREE(a, s, WC_XMSS_ADDR_TYPE_LTREE)
 471/* Set the hash tree address based on subtree.
 472 *
 473 * @param [out] a  Hash address.
 474 * @param [in]  s  Subtree hash address.
 475 */
 476#define XMSS_ADDR_TREE_SET_SUBTREE(a, s) \
 477    XMSS_ADDR_SET_SUBTREE(a, s, WC_XMSS_ADDR_TYPE_TREE)
 478
 479#ifdef LITTLE_ENDIAN_ORDER
 480
 481/* Set a byte value into a word of an encoded address.
 482 *
 483 * @param [in, out] a  Encoded hash address.
 484 * @param [in]      i  Index of word.
 485 * @param [in]      b  Byte to set.
 486 */
 487#define XMSS_ADDR_SET_BYTE(a, i, b)     \
 488    ((word32*)(a))[i] = (word32)(b) << 24
 489
 490#else
 491
 492/* Set a byte value into a word of an encoded address.
 493 *
 494 * @param [in, out] a  Encoded hash address.
 495 * @param [in]      i  Index of word.
 496 * @param [in]      b  Byte to set.
 497 */
 498#define XMSS_ADDR_SET_BYTE(a, i, b)     \
 499    ((word32*)(a))[i] = (b)
 500
 501#endif /* LITTLE_ENDIAN_ORDER */
 502
 503/* Convert hash address to bytes.
 504 *
 505 * @param [out] bytes  Array to encode into.
 506 * @param [in]  addr   Hash address.
 507 */
 508static void wc_xmss_addr_encode(const HashAddress addr, byte* bytes)
 509{
 510    c32toa((addr)[0], (bytes) + (0 * 4));
 511    c32toa((addr)[1], (bytes) + (1 * 4));
 512    c32toa((addr)[2], (bytes) + (2 * 4));
 513    c32toa((addr)[3], (bytes) + (3 * 4));
 514    c32toa((addr)[4], (bytes) + (4 * 4));
 515    c32toa((addr)[5], (bytes) + (5 * 4));
 516    c32toa((addr)[6], (bytes) + (6 * 4));
 517    c32toa((addr)[7], (bytes) + (7 * 4));
 518}
 519
 520/********************************************
 521 * HASHING
 522 ********************************************/
 523
 524#if !defined(WOLFSSL_WC_XMSS_SMALL) && defined(WC_XMSS_SHA256) && \
 525    !defined(WC_XMSS_FULL_HASH)
 526
 527/* Set hash data and length into SHA-256 digest.
 528 *
 529 * @param [in, out] state      XMSS/MT state with SHA-256 digest.
 530 * @param [in]      data       Data to add to hash.
 531 * @param [in]      len        Number of bytes in data.
 532 *                             Must be less than a block.
 533 * @param [in]      total_len  Number of bytes updated so far.
 534 */
 535#define XMSS_SHA256_SET_DATA(state, data, len, total_len)           \
 536do {                                                                \
 537    XMEMCPY((state)->digest.sha256.buffer, data, len);              \
 538    (state)->digest.sha256.buffLen = (len);                         \
 539    (state)->digest.sha256.loLen = (total_len);                     \
 540} while (0)
 541
 542/* Save the SHA-256 state to cache.
 543 *
 544 * @param [in, out] state  XMSS/MT state with SHA-256 digest and state cache.
 545 */
 546#define XMSS_SHA256_STATE_CACHE(state)                              \
 547    (state)->dgst_state[0] = (state)->digest.sha256.digest[0];      \
 548    (state)->dgst_state[1] = (state)->digest.sha256.digest[1];      \
 549    (state)->dgst_state[2] = (state)->digest.sha256.digest[2];      \
 550    (state)->dgst_state[3] = (state)->digest.sha256.digest[3];      \
 551    (state)->dgst_state[4] = (state)->digest.sha256.digest[4];      \
 552    (state)->dgst_state[5] = (state)->digest.sha256.digest[5];      \
 553    (state)->dgst_state[6] = (state)->digest.sha256.digest[6];      \
 554    (state)->dgst_state[7] = (state)->digest.sha256.digest[7];      \
 555
 556/* Restore the SHA-256 state from cache and set length.
 557 *
 558 * @param [in, out] state  XMSS/MT state with SHA-256 digest and state cache.
 559 * @param [in]      len    Number of bytes of data hashed so far.
 560 */
 561#define XMSS_SHA256_STATE_RESTORE(state, len)                       \
 562do {                                                                \
 563    (state)->digest.sha256.digest[0] = (state)->dgst_state[0];      \
 564    (state)->digest.sha256.digest[1] = (state)->dgst_state[1];      \
 565    (state)->digest.sha256.digest[2] = (state)->dgst_state[2];      \
 566    (state)->digest.sha256.digest[3] = (state)->dgst_state[3];      \
 567    (state)->digest.sha256.digest[4] = (state)->dgst_state[4];      \
 568    (state)->digest.sha256.digest[5] = (state)->dgst_state[5];      \
 569    (state)->digest.sha256.digest[6] = (state)->dgst_state[6];      \
 570    (state)->digest.sha256.digest[7] = (state)->dgst_state[7];      \
 571    (state)->digest.sha256.loLen = (len);                           \
 572} while (0)
 573
 574/* Restore the SHA-256 state from cache and set data and length.
 575 *
 576 * @param [in, out] state      XMSS/MT state with SHA-256 digest and cache.
 577 * @param [in]      data       Data to add to hash.
 578 * @param [in]      len        Number of bytes in data.
 579 *                             Must be less than a block.
 580 * @param [in]      total_len  Number of bytes updated so far.
 581 */
 582#define XMSS_SHA256_STATE_RESTORE_DATA(state, data, len, total_len) \
 583do {                                                                \
 584    (state)->digest.sha256.digest[0] = (state)->dgst_state[0];      \
 585    (state)->digest.sha256.digest[1] = (state)->dgst_state[1];      \
 586    (state)->digest.sha256.digest[2] = (state)->dgst_state[2];      \
 587    (state)->digest.sha256.digest[3] = (state)->dgst_state[3];      \
 588    (state)->digest.sha256.digest[4] = (state)->dgst_state[4];      \
 589    (state)->digest.sha256.digest[5] = (state)->dgst_state[5];      \
 590    (state)->digest.sha256.digest[6] = (state)->dgst_state[6];      \
 591    (state)->digest.sha256.digest[7] = (state)->dgst_state[7];      \
 592    XMSS_SHA256_SET_DATA(state, data, len, total_len);              \
 593} while (0)
 594
 595#endif /* !WOLFSSL_WC_XMSS_SMALL && WC_XMSS_SHA256 && !WC_XMSS_FULL_HASH */
 596
 597/* Hash the data into output buffer.
 598 *
 599 * @param [in]  state   XMSS/MT state including digest and parameters.
 600 * @param [in]  in      Data to digest.
 601 * @param [in]  inlen   Length of data to digest in bytes.
 602 * @param [out] out     Buffer to put digest into.
 603 */
 604static WC_INLINE void wc_xmss_hash(XmssState* state, const byte* in,
 605    word32 inlen, byte* out)
 606{
 607    int ret;
 608    const XmssParams* params = state->params;
 609
 610#ifdef WC_XMSS_SHA256
 611    /* Full SHA-256 digest. */
 612    if ((params->hash == WC_HASH_TYPE_SHA256) &&
 613            (params->n == WC_SHA256_DIGEST_SIZE)) {
 614        ret = wc_Sha256Update(&state->digest.sha256, in, inlen);
 615        if (ret == 0) {
 616            ret = wc_Sha256Final(&state->digest.sha256, out);
 617        }
 618    }
 619#if WOLFSSL_WC_XMSS_MIN_HASH_SIZE <= 192 && WOLFSSL_WC_XMSS_MAX_HASH_SIZE >= 192
 620    /* Partial SHA-256 digest. */
 621    else if (params->hash == WC_HASH_TYPE_SHA256) {
 622        byte buf[WC_SHA256_DIGEST_SIZE];
 623        ret = wc_Sha256Update(&state->digest.sha256, in, inlen);
 624        if (ret == 0) {
 625            ret = wc_Sha256Final(&state->digest.sha256, buf);
 626        }
 627        if (ret == 0) {
 628            XMEMCPY(out, buf, params->n);
 629        }
 630    }
 631#endif
 632    else
 633#endif /* WC_XMSS_SHA256 */
 634#ifdef WC_XMSS_SHA512
 635    /* Full SHA-512 digest. */
 636    if (params->hash == WC_HASH_TYPE_SHA512) {
 637        ret = wc_Sha512Update(&state->digest.sha512, in, inlen);
 638        if (ret == 0) {
 639            ret = wc_Sha512Final(&state->digest.sha512, out);
 640        }
 641    }
 642    else
 643#endif /* WC_XMSS_SHA512 */
 644#ifdef WC_XMSS_SHAKE128
 645    /* Digest with SHAKE-128. */
 646    if (params->hash == WC_HASH_TYPE_SHAKE128) {
 647        ret = wc_Shake128_Update(&state->digest.shake, in, inlen);
 648        if (ret == 0) {
 649            ret = wc_Shake128_Final(&state->digest.shake, out, params->n);
 650        }
 651    }
 652    else
 653#endif /* WC_XMSS_SHAKE128 */
 654#ifdef WC_XMSS_SHAKE256
 655    /* Digest with SHAKE-256. */
 656    if (params->hash == WC_HASH_TYPE_SHAKE256) {
 657        ret = wc_Shake256_Update(&state->digest.shake, in, inlen);
 658        if (ret == 0) {
 659            ret = wc_Shake256_Final(&state->digest.shake, out, params->n);
 660        }
 661    }
 662    else
 663#endif /* WC_XMSS_SHAKE256 */
 664    {
 665        /* Unsupported digest function. */
 666        ret = NOT_COMPILED_IN;
 667    }
 668
 669    if (state->ret == 0) {
 670        /* Store any digest failures for public APIs to return. */
 671        state->ret = ret;
 672    }
 673}
 674
 675#if !defined(WOLFSSL_WC_XMSS_SMALL) && defined(WC_XMSS_SHA256)
 676#ifndef WC_XMSS_FULL_HASH
 677/* Chain hashing.
 678 *
 679 * RFC 8391: 3.1.2, Algorithm 2: chain - Chaining Function
 680 *     ...
 681 *     ADRS.setKeyAndMask(0);
 682 *     KEY = PRF(SEED, ADRS);
 683 *     ADRS.setKeyAndMask(1);
 684 *     BM = PRF(SEED, ADRS);
 685 *     tmp = F(KEY, tmp XOR BM);
 686 *     return tmp;
 687 *
 688 * @param [in]  state  XMSS/MT state including digest and parameters.
 689 * @param [in]  tmp    Temporary buffer holding chain data.
 690 * @param [in]  addr   Hash address as a byte array.
 691 * @param [out] hash   Buffer to hold hash.
 692 */
 693static void wc_xmss_chain_hash_sha256_32(XmssState* state, const byte* tmp,
 694    byte* addr, byte* hash)
 695{
 696    /* Offsets into chain hash data. */
 697    byte* pad = state->buf;
 698    byte* key = pad + XMSS_SHA256_32_PAD_LEN;
 699    byte* bm = key + XMSS_SHA256_32_N;
 700    int ret;
 701
 702    /* Calculate n-byte key - KEY. */
 703    ((word32*)addr)[XMSS_ADDR_KEY_MASK] = 0;
 704    /* Copy back state after first 64 bytes. */
 705    XMSS_SHA256_STATE_RESTORE_DATA(state, addr, WC_XMSS_ADDR_LEN,
 706        XMSS_HASH_PRF_DATA_LEN_SHA256_32);
 707    /* Calculate hash. */
 708    ret = wc_Sha256Final(&state->digest.sha256, key);
 709
 710    if (ret == 0) {
 711        /* Calculate n-byte bit mask - BM. */
 712        addr[XMSS_ADDR_KEY_MASK * 4 + 3] = 1;
 713        /* Copy back state after first 64 bytes. */
 714        XMSS_SHA256_STATE_RESTORE_DATA(state, addr, WC_XMSS_ADDR_LEN,
 715            XMSS_HASH_PRF_DATA_LEN_SHA256_32);
 716        /* Calculate hash. */
 717        ret = wc_Sha256Final(&state->digest.sha256, bm);
 718    }
 719
 720    if (ret == 0) {
 721        /* Function padding set in caller. */
 722        xorbuf(bm, tmp, XMSS_SHA256_32_N);
 723        ret = wc_Sha256Update(&state->digest.sha256, state->buf,
 724             XMSS_CHAIN_HASH_DATA_LEN_SHA256_32);
 725    }
 726    if (ret == 0) {
 727        /* Calculate the chain hash. */
 728        ret = wc_Sha256Final(&state->digest.sha256, hash);
 729    }
 730    if (state->ret == 0) {
 731        /* Store any digest failures for public APIs to return. */
 732        state->ret = ret;
 733    }
 734}
 735#else
 736/* Chain hashing.
 737 *
 738 * Padding, seed, addr for PRF set by caller into prf_buf.
 739 *
 740 * RFC 8391: 3.1.2, Algorithm 2: chain - Chaining Function
 741 *     ...
 742 *     ADRS.setKeyAndMask(0);
 743 *     KEY = PRF(SEED, ADRS);
 744 *     ADRS.setKeyAndMask(1);
 745 *     BM = PRF(SEED, ADRS);
 746 *     tmp = F(KEY, tmp XOR BM);
 747 *     return tmp;
 748 *
 749 * @param [in]  state  XMSS/MT state including digest and parameters.
 750 * @param [in]  tmp    Temporary buffer holding chain data.
 751 * @param [out] out    Buffer to hold hash.
 752 */
 753static void wc_xmss_chain_hash_sha256_32(XmssState* state, const byte* tmp,
 754    byte* hash)
 755{
 756    byte* addr = state->prf_buf + XMSS_SHA256_32_PAD_LEN + XMSS_SHA256_32_N;
 757    /* Offsets into chain hash data. */
 758    byte* pad = state->buf;
 759    byte* key = pad + XMSS_SHA256_32_PAD_LEN;
 760    byte* bm = key + XMSS_SHA256_32_N;
 761
 762    /* Calculate n-byte key - KEY. */
 763    ((word32*)addr)[XMSS_ADDR_KEY_MASK] = 0;
 764    wc_xmss_hash(state, state->prf_buf, XMSS_HASH_PRF_DATA_LEN_SHA256_32, key);
 765    /* Calculate the n-byte mask. */
 766    addr[XMSS_ADDR_KEY_MASK * 4 + 3] = 1;
 767    wc_xmss_hash(state, state->prf_buf, XMSS_HASH_PRF_DATA_LEN_SHA256_32, bm);
 768
 769    /* Function padding set in caller. */
 770    xorbuf(bm, tmp, XMSS_SHA256_32_N);
 771    /* Calculate the chain hash. */
 772    wc_xmss_hash(state, state->buf, XMSS_CHAIN_HASH_DATA_LEN_SHA256_32, hash);
 773}
 774#endif /* !WC_XMSS_FULL_HASH */
 775#endif /* !WOLFSSL_WC_XMSS_SMALL && WC_XMSS_SHA256 */
 776
 777/* Chain hashing.
 778 *
 779 * Padding, seed, addr for PRF set by caller into prf_buf.
 780 *
 781 * RFC 8391: 3.1.2, Algorithm 2: chain - Chaining Function
 782 *     ...
 783 *     ADRS.setKeyAndMask(0);
 784 *     KEY = PRF(SEED, ADRS);
 785 *     ADRS.setKeyAndMask(1);
 786 *     BM = PRF(SEED, ADRS);
 787 *     tmp = F(KEY, tmp XOR BM);
 788 *     return tmp;
 789 *
 790 * @param [in]  state  XMSS/MT state including digest and parameters.
 791 * @param [in]  tmp    Temporary buffer holding chain data.
 792 * @param [out] hash   Buffer to hold hash.
 793 */
 794static void wc_xmss_chain_hash(XmssState* state, const byte* tmp, byte* hash)
 795{
 796    const XmssParams* params = state->params;
 797    byte* addr = state->prf_buf + params->pad_len + params->n;
 798    /* Offsets into chain hash data. */
 799    byte* pad = state->buf;
 800    byte* key = pad + params->pad_len;
 801    byte* bm = key + params->n;
 802
 803    /* Calculate n-byte key - KEY. */
 804    ((word32*)addr)[XMSS_ADDR_KEY_MASK] = 0;
 805    wc_xmss_hash(state, state->prf_buf, XMSS_HASH_PRF_DATA_LEN(params), key);
 806    /* Calculate n-byte bit mask - BM. */
 807    addr[XMSS_ADDR_KEY_MASK * 4 + 3] = 1;
 808    wc_xmss_hash(state, state->prf_buf, XMSS_HASH_PRF_DATA_LEN(params), bm);
 809
 810    /* Function padding set in caller. */
 811    xorbuf(bm, tmp, params->n);
 812    /* Calculate the chain hash. */
 813    wc_xmss_hash(state, state->buf, XMSS_CHAIN_HASH_DATA_LEN(params), hash);
 814}
 815
 816#if !defined(WOLFSSL_WC_XMSS_SMALL) && defined(WC_XMSS_SHA256)
 817#ifndef WC_XMSS_FULL_HASH
 818/* Randomized tree hashing.
 819 *
 820 * RFC 8391: 4.1.4, Algorithm 7: RAND_HASH
 821 *     ...
 822 *     ADRS.setKeyAndMask(0);
 823 *     KEY = PRF(SEED, ADRS);
 824 *     ADRS.setKeyAndMask(1);
 825 *     BM_0 = PRF(SEED, ADRS);
 826 *     ADRS.setKeyAndMask(2);
 827 *     BM_1 = PRF(SEED, ADRS);
 828 *     return H(KEY, (LEFT XOR BM_0) || (RIGHT XOR BM_1));
 829 *
 830 * @param [in]  state  XMSS/MT state including digest and parameters.
 831 * @param [in]  data   Input data.
 832 * @param [in]  addr   Hash address.
 833 * @param [out] hash   Buffer to hold hash.
 834 */
 835static void wc_xmss_rand_hash_sha256_32_prehash(XmssState* state,
 836    const byte* data, HashAddress addr, byte* hash)
 837{
 838    int ret;
 839    /* Offsets into rand hash data. */
 840    byte* pad = state->buf;
 841    byte* key = pad + XMSS_SHA256_32_PAD_LEN;
 842    byte* bm0 = key + XMSS_SHA256_32_N;
 843    byte* bm1 = bm0 + XMSS_SHA256_32_N;
 844    byte addr_buf[WC_XMSS_ADDR_LEN];
 845
 846    addr[XMSS_ADDR_KEY_MASK] = 0;
 847    wc_xmss_addr_encode(addr, addr_buf);
 848
 849    /* Calculate n-byte key - KEY. */
 850    XMSS_SHA256_STATE_RESTORE_DATA(state, addr_buf, WC_XMSS_ADDR_LEN,
 851        XMSS_HASH_PRF_DATA_LEN_SHA256_32);
 852    /* Calculate hash. */
 853    ret = wc_Sha256Final(&state->digest.sha256, key);
 854
 855    /* Calculate n-byte mask - BM_0. */
 856    if (ret == 0) {
 857        addr_buf[XMSS_ADDR_KEY_MASK * 4 + 3] = 1;
 858        /* Copy back state after first 64 bytes. */
 859        XMSS_SHA256_STATE_RESTORE_DATA(state, addr_buf, WC_XMSS_ADDR_LEN,
 860            XMSS_HASH_PRF_DATA_LEN_SHA256_32);
 861        /* Calculate hash. */
 862        ret = wc_Sha256Final(&state->digest.sha256, bm0);
 863    }
 864
 865    /* Calculate n-byte mask - BM_1. */
 866    if (ret == 0) {
 867        addr_buf[XMSS_ADDR_KEY_MASK * 4 + 3] = 2;
 868        /* Copy back state after first 64 bytes. */
 869        XMSS_SHA256_STATE_RESTORE_DATA(state, addr_buf, WC_XMSS_ADDR_LEN,
 870            XMSS_HASH_PRF_DATA_LEN_SHA256_32);
 871        /* Calculate hash. */
 872        ret = wc_Sha256Final(&state->digest.sha256, bm1);
 873    }
 874
 875    if (ret == 0) {
 876        XMSS_PAD_ENC(XMSS_HASH_PADDING_H, pad, XMSS_SHA256_32_PAD_LEN);
 877        /* XOR into bm0 and bm1. */
 878        xorbuf(bm0, data, XMSS_SHA256_32_N * 2);
 879        ret = wc_Sha256Update(&state->digest.sha256, state->buf,
 880            XMSS_RAND_HASH_DATA_LEN_SHA256_32);
 881    }
 882    if (ret == 0) {
 883        ret = wc_Sha256Final(&state->digest.sha256, hash);
 884    }
 885    if (state->ret == 0) {
 886        /* Store any digest failures for public APIs to return. */
 887        state->ret = ret;
 888    }
 889}
 890#endif /* !WC_XMSS_FULL_HASH */
 891
 892/* Randomized tree hashing.
 893 *
 894 * RFC 8391: 4.1.4, Algorithm 7: RAND_HASH
 895 *     ...
 896 *     ADRS.setKeyAndMask(0);
 897 *     KEY = PRF(SEED, ADRS);
 898 *     ADRS.setKeyAndMask(1);
 899 *     BM_0 = PRF(SEED, ADRS);
 900 *     ADRS.setKeyAndMask(2);
 901 *     BM_1 = PRF(SEED, ADRS);
 902 *     return H(KEY, (LEFT XOR BM_0) || (RIGHT XOR BM_1));
 903 *
 904 * @param [in]  state    XMSS/MT state including digest and parameters.
 905 * @param [in]  data     Input data.
 906 * @param [in]  pk_seed  Random public seed.
 907 * @param [in]  addr     Hash address.
 908 * @param [out] hash     Buffer to hold hash.
 909 */
 910static void wc_xmss_rand_hash_sha256_32(XmssState* state, const byte* data,
 911    const byte* pk_seed, HashAddress addr, byte* hash)
 912{
 913    byte* addr_buf = state->prf_buf + XMSS_SHA256_32_PAD_LEN +
 914        XMSS_SHA256_32_N;
 915    /* Offsets into rand hash data. */
 916    byte* pad = state->buf;
 917    byte* key = pad + XMSS_SHA256_32_PAD_LEN;
 918    byte* bm0 = key + XMSS_SHA256_32_N;
 919    byte* bm1 = bm0 + XMSS_SHA256_32_N;
 920#ifndef WC_XMSS_FULL_HASH
 921    int ret;
 922
 923    /* Encode padding byte for PRF. */
 924    XMSS_PAD_ENC(XMSS_HASH_PADDING_PRF, state->prf_buf, XMSS_SHA256_32_PAD_LEN);
 925    /* Append public seed for PRF. */
 926    XMEMCPY(state->prf_buf + XMSS_SHA256_32_PAD_LEN, pk_seed,
 927        XMSS_SHA256_32_N);
 928
 929    /* Set key mask to initial value and append encoding. */
 930    addr[XMSS_ADDR_KEY_MASK] = 0;
 931    wc_xmss_addr_encode(addr, addr_buf);
 932
 933    /* Calculate n-byte key - KEY. */
 934    ret = wc_Sha256Update(&state->digest.sha256, state->prf_buf,
 935        XMSS_SHA256_32_PAD_LEN + XMSS_SHA256_32_N);
 936    if (ret == 0) {
 937        /* Copy state after first 64 bytes. */
 938        XMSS_SHA256_STATE_CACHE(state);
 939        /* Copy in remaining 32 bytes to buffer. */
 940        XMSS_SHA256_SET_DATA(state, addr_buf, WC_XMSS_ADDR_LEN,
 941            XMSS_HASH_PRF_DATA_LEN_SHA256_32);
 942        /* Calculate hash. */
 943        ret = wc_Sha256Final(&state->digest.sha256, key);
 944    }
 945
 946    /* Calculate n-byte mask - BM_0. */
 947    if (ret == 0) {
 948        addr_buf[XMSS_ADDR_KEY_MASK * 4 + 3] = 1;
 949        /* Copy back state after first 64 bytes. */
 950        XMSS_SHA256_STATE_RESTORE_DATA(state, addr_buf, WC_XMSS_ADDR_LEN,
 951            XMSS_HASH_PRF_DATA_LEN_SHA256_32);
 952        /* Calculate hash. */
 953        ret = wc_Sha256Final(&state->digest.sha256, bm0);
 954    }
 955
 956    /* Calculate n-byte mask - BM_1. */
 957    if (ret == 0) {
 958        addr_buf[XMSS_ADDR_KEY_MASK * 4 + 3] = 2;
 959        /* Copy back state after first 64 bytes. */
 960        XMSS_SHA256_STATE_RESTORE_DATA(state, addr_buf, WC_XMSS_ADDR_LEN,
 961            XMSS_HASH_PRF_DATA_LEN_SHA256_32);
 962        /* Calculate hash. */
 963        ret = wc_Sha256Final(&state->digest.sha256, bm1);
 964    }
 965
 966    if (ret == 0) {
 967        XMSS_PAD_ENC(XMSS_HASH_PADDING_H, pad, XMSS_SHA256_32_PAD_LEN);
 968        /* XOR into bm0 and bm1. */
 969        xorbuf(bm0, data, 2 * XMSS_SHA256_32_N);
 970        ret = wc_Sha256Update(&state->digest.sha256, state->buf,
 971            XMSS_RAND_HASH_DATA_LEN_SHA256_32);
 972    }
 973    if (ret == 0) {
 974        ret = wc_Sha256Final(&state->digest.sha256, hash);
 975    }
 976    if (state->ret == 0) {
 977        /* Store any digest failures for public APIs to return. */
 978        state->ret = ret;
 979    }
 980#else
 981    /* Encode padding byte for PRF. */
 982    XMSS_PAD_ENC(XMSS_HASH_PADDING_PRF, state->prf_buf, XMSS_SHA256_32_PAD_LEN);
 983    /* Append public seed for PRF. */
 984    XMEMCPY(state->prf_buf + XMSS_SHA256_32_PAD_LEN, pk_seed,
 985        XMSS_SHA256_32_N);
 986
 987    /* Set key mask to initial value and append encoding. */
 988    addr[XMSS_ADDR_KEY_MASK] = 0;
 989    wc_xmss_addr_encode(addr, addr_buf);
 990
 991    /* Calculate n-byte key - KEY. */
 992    wc_xmss_hash(state, state->prf_buf, XMSS_HASH_PRF_DATA_LEN_SHA256_32, key);
 993    /* Calculate n-byte mask - BM_0. */
 994    addr_buf[XMSS_ADDR_KEY_MASK * 4 + 3] = 1;
 995    wc_xmss_hash(state, state->prf_buf, XMSS_HASH_PRF_DATA_LEN_SHA256_32, bm0);
 996    /* Calculate n-byte mask - BM_1. */
 997    addr_buf[XMSS_ADDR_KEY_MASK * 4 + 3] = 2;
 998    wc_xmss_hash(state, state->prf_buf, XMSS_HASH_PRF_DATA_LEN_SHA256_32, bm1);
 999
1000    XMSS_PAD_ENC(XMSS_HASH_PADDING_H, state->buf, XMSS_SHA256_32_PAD_LEN);
1001    xorbuf(bm0, data, 2 * XMSS_SHA256_32_N);
1002    wc_xmss_hash(state, state->buf, XMSS_RAND_HASH_DATA_LEN_SHA256_32, hash);
1003#endif /* WC_XMSS_FULL_HASH */
1004}
1005#endif /* !WOLFSSL_WC_XMSS_SMALL && WC_XMSS_SHA256 */
1006
1007/* Randomized tree hashing.
1008 *
1009 * RFC 8391: 4.1.4, Algorithm 7: RAND_HASH
1010 *     ...
1011 *     ADRS.setKeyAndMask(0);
1012 *     KEY = PRF(SEED, ADRS);
1013 *     ADRS.setKeyAndMask(1);
1014 *     BM_0 = PRF(SEED, ADRS);
1015 *     ADRS.setKeyAndMask(2);
1016 *     BM_1 = PRF(SEED, ADRS);
1017 *     return H(KEY, (LEFT XOR BM_0) || (RIGHT XOR BM_1));
1018 *
1019 * @param [in]  state    XMSS/MT state including digest and parameters.
1020 * @param [in]  data     Input data.
1021 * @param [in]  pk_seed  Random public seed.
1022 * @param [in]  addr     Hash address.
1023 * @param [out] hash     Buffer to hold hash.
1024 */
1025static void wc_xmss_rand_hash(XmssState* state, const byte* data,
1026    const byte* pk_seed, HashAddress addr, byte* hash)
1027{
1028    const XmssParams* params = state->params;
1029
1030#if !defined(WOLFSSL_WC_XMSS_SMALL) && defined(WC_XMSS_SHA256)
1031    if ((params->pad_len == XMSS_SHA256_32_PAD_LEN) &&
1032            (params->n == XMSS_SHA256_32_N) &&
1033            (params->hash == WC_HASH_TYPE_SHA256)) {
1034        wc_xmss_rand_hash_sha256_32(state, data, pk_seed, addr, hash);
1035    }
1036    else
1037#endif /* !WOLFSSL_WC_XMSS_SMALL && WC_XMSS_SHA256 */
1038    {
1039        byte* addr_buf = state->prf_buf + params->pad_len + params->n;
1040        /* Offsets into rand hash data. */
1041        byte* pad = state->buf;
1042        byte* key = pad + params->pad_len;
1043        byte* bm0 = key + params->n;
1044        byte* bm1 = bm0 + params->n;
1045        const word32 len = XMSS_HASH_PRF_DATA_LEN(params);
1046
1047        /* Encode padding byte for PRF. */
1048        XMSS_PAD_ENC(XMSS_HASH_PADDING_PRF, state->prf_buf, params->pad_len);
1049        /* Append public seed for PRF. */
1050        XMEMCPY(state->prf_buf + params->pad_len, pk_seed, params->n);
1051
1052        /* Set key mask to initial value and append encoding. */
1053        addr[XMSS_ADDR_KEY_MASK] = 0;
1054        wc_xmss_addr_encode(addr, addr_buf);
1055
1056        /* Calculate n-byte key - KEY. */
1057        wc_xmss_hash(state, state->prf_buf, len, key);
1058        /* Calculate n-byte mask - BM_0. */
1059        addr_buf[XMSS_ADDR_KEY_MASK * 4 + 3] = 1;
1060        wc_xmss_hash(state, state->prf_buf, len, bm0);
1061        /* Calculate n-byte mask - BM_1. */
1062        addr_buf[XMSS_ADDR_KEY_MASK * 4 + 3] = 2;
1063        wc_xmss_hash(state, state->prf_buf, len, bm1);
1064
1065        XMSS_PAD_ENC(XMSS_HASH_PADDING_H, pad, params->pad_len);
1066        xorbuf(bm0, data, 2U * params->n);
1067        wc_xmss_hash(state, state->buf, XMSS_RAND_HASH_DATA_LEN(params), hash);
1068    }
1069}
1070
1071#if !defined(WOLFSSL_WC_XMSS_SMALL) || defined(WOLFSSL_XMSS_VERIFY_ONLY)
1072#if !defined(WOLFSSL_WC_XMSS_SMALL) && defined(WC_XMSS_SHA256)
1073/* Randomized tree hashing.
1074 *
1075 * RFC 8391: 4.1.4, Algorithm 7: RAND_HASH
1076 *     ...
1077 *     ADRS.setKeyAndMask(0);
1078 *     KEY = PRF(SEED, ADRS);
1079 *     ADRS.setKeyAndMask(1);
1080 *     BM_0 = PRF(SEED, ADRS);
1081 *     ADRS.setKeyAndMask(2);
1082 *     BM_1 = PRF(SEED, ADRS);
1083 *     return H(KEY, (LEFT XOR BM_0) || (RIGHT XOR BM_1));
1084 *
1085 * @param [in]  state    XMSS/MT state including digest and parameters.
1086 * @param [in]  left     First half of data.
1087 * @param [in]  right    Second half of data.
1088 * @param [in]  pk_seed  Random public seed.
1089 * @param [in]  addr     Hash address.
1090 * @param [out] hash     Buffer to hold hash.
1091 */
1092static void wc_xmss_rand_hash_lr_sha256_32(XmssState* state, const byte* left,
1093    const byte* right, const byte* pk_seed, HashAddress addr, byte* hash)
1094{
1095    byte* addr_buf = state->prf_buf + XMSS_SHA256_32_PAD_LEN +
1096        XMSS_SHA256_32_N;
1097    /* Offsets into rand hash data. */
1098    byte* pad = state->buf;
1099    byte* key = pad + XMSS_SHA256_32_PAD_LEN;
1100    byte* bm0 = key + XMSS_SHA256_32_N;
1101    byte* bm1 = bm0 + XMSS_SHA256_32_N;
1102#ifndef WC_XMSS_FULL_HASH
1103    int ret;
1104
1105    /* Encode padding byte for PRF. */
1106    XMSS_PAD_ENC(XMSS_HASH_PADDING_PRF, state->prf_buf, XMSS_SHA256_32_PAD_LEN);
1107    /* Append public seed for PRF. */
1108    XMEMCPY(state->prf_buf + XMSS_SHA256_32_PAD_LEN, pk_seed,
1109        XMSS_SHA256_32_N);
1110
1111    /* Set key mask to initial value and append encoding. */
1112    addr[XMSS_ADDR_KEY_MASK] = 0;
1113    wc_xmss_addr_encode(addr, addr_buf);
1114
1115    /* Calculate n-byte key - KEY. */
1116    ret = wc_Sha256Update(&state->digest.sha256, state->prf_buf,
1117        XMSS_SHA256_32_PAD_LEN + XMSS_SHA256_32_N);
1118    if (ret == 0) {
1119        /* Copy state after first 64 bytes. */
1120        XMSS_SHA256_STATE_CACHE(state);
1121        /* Copy in remaining 32 bytes to buffer. */
1122        XMSS_SHA256_SET_DATA(state, addr_buf, WC_XMSS_ADDR_LEN,
1123            XMSS_HASH_PRF_DATA_LEN_SHA256_32);
1124        /* Calculate hash. */
1125        ret = wc_Sha256Final(&state->digest.sha256, key);
1126    }
1127
1128    /* Calculate n-byte mask - BM_0. */
1129    if (ret == 0) {
1130        addr_buf[XMSS_ADDR_KEY_MASK * 4 + 3] = 1;
1131        /* Copy back state after first 64 bytes. */
1132        XMSS_SHA256_STATE_RESTORE_DATA(state, addr_buf, WC_XMSS_ADDR_LEN,
1133            XMSS_HASH_PRF_DATA_LEN_SHA256_32);
1134        /* Calculate hash. */
1135        ret = wc_Sha256Final(&state->digest.sha256, bm0);
1136    }
1137
1138    /* Calculate n-byte mask - BM_1. */
1139    if (ret == 0) {
1140        addr_buf[XMSS_ADDR_KEY_MASK * 4 + 3] = 2;
1141        /* Copy back state after first 64 bytes. */
1142        XMSS_SHA256_STATE_RESTORE_DATA(state, addr_buf, WC_XMSS_ADDR_LEN,
1143            XMSS_HASH_PRF_DATA_LEN_SHA256_32);
1144        /* Calculate hash. */
1145        ret = wc_Sha256Final(&state->digest.sha256, bm1);
1146    }
1147
1148    if (ret == 0) {
1149        XMSS_PAD_ENC(XMSS_HASH_PADDING_H, pad, XMSS_SHA256_32_PAD_LEN);
1150        /* XOR into bm0 and bm1. */
1151        XMEMCPY(state->prf_buf, left, XMSS_SHA256_32_N);
1152        XMEMCPY(state->prf_buf + XMSS_SHA256_32_N, right, XMSS_SHA256_32_N);
1153        xorbuf(bm0, state->prf_buf, 2 * XMSS_SHA256_32_N);
1154        ret = wc_Sha256Update(&state->digest.sha256, state->buf,
1155            XMSS_RAND_HASH_DATA_LEN_SHA256_32);
1156    }
1157    if (ret == 0) {
1158        ret = wc_Sha256Final(&state->digest.sha256, hash);
1159    }
1160    if (state->ret == 0) {
1161        /* Store any digest failures for public APIs to return. */
1162        state->ret = ret;
1163    }
1164#else
1165    /* Encode padding byte for PRF. */
1166    XMSS_PAD_ENC(XMSS_HASH_PADDING_PRF, state->prf_buf, XMSS_SHA256_32_PAD_LEN);
1167    /* Append public seed for PRF. */
1168    XMEMCPY(state->prf_buf + XMSS_SHA256_32_PAD_LEN, pk_seed, XMSS_SHA256_32_N);
1169
1170    /* Set key mask to initial value and append encoding. */
1171    addr[XMSS_ADDR_KEY_MASK] = 0;
1172    wc_xmss_addr_encode(addr, addr_buf);
1173
1174    /* Calculate n-byte key - KEY. */
1175    wc_xmss_hash(state, state->prf_buf, XMSS_HASH_PRF_DATA_LEN_SHA256_32, key);
1176    /* Calculate n-byte mask - BM_0. */
1177    addr_buf[XMSS_ADDR_KEY_MASK * 4 + 3] = 1;
1178    wc_xmss_hash(state, state->prf_buf, XMSS_HASH_PRF_DATA_LEN_SHA256_32, bm0);
1179    /* Calculate n-byte mask - BM_1. */
1180    addr_buf[XMSS_ADDR_KEY_MASK * 4 + 3] = 2;
1181    wc_xmss_hash(state, state->prf_buf, XMSS_HASH_PRF_DATA_LEN_SHA256_32, bm1);
1182
1183    XMSS_PAD_ENC(XMSS_HASH_PADDING_H, state->buf, XMSS_SHA256_32_PAD_LEN);
1184    XMEMCPY(state->prf_buf, left, XMSS_SHA256_32_N);
1185    XMEMCPY(state->prf_buf + XMSS_SHA256_32_N, right, XMSS_SHA256_32_N);
1186    xorbuf(bm0, state->prf_buf, 2 * XMSS_SHA256_32_N);
1187    wc_xmss_hash(state, state->buf, XMSS_RAND_HASH_DATA_LEN_SHA256_32, hash);
1188#endif /* WC_XMSS_FULL_HASH */
1189}
1190#endif /* !WOLFSSL_WC_XMSS_SMALL && WC_XMSS_SHA256 */
1191/* Randomized tree hashing - left and right separate parameters.
1192 *
1193 * RFC 8391: 4.1.4, Algorithm 7: RAND_HASH
1194 *     ...
1195 *     ADRS.setKeyAndMask(0);
1196 *     KEY = PRF(SEED, ADRS);
1197 *     ADRS.setKeyAndMask(1);
1198 *     BM_0 = PRF(SEED, ADRS);
1199 *     ADRS.setKeyAndMask(2);
1200 *     BM_1 = PRF(SEED, ADRS);
1201 *     return H(KEY, (LEFT XOR BM_0) || (RIGHT XOR BM_1));
1202 *
1203 * @param [in]  state    XMSS/MT state including digest and parameters.
1204 * @param [in]  left     First half of data.
1205 * @param [in]  right    Second half of data.
1206 * @param [in]  pk_seed  Random public seed.
1207 * @param [in]  addr     Hash address.
1208 * @param [out] hash     Buffer to hold hash.
1209 */
1210static void wc_xmss_rand_hash_lr(XmssState* state, const byte* left,
1211    const byte* right, const byte* pk_seed, HashAddress addr, byte* hash)
1212{
1213    const XmssParams* params = state->params;
1214
1215#if !defined(WOLFSSL_WC_XMSS_SMALL) && defined(WC_XMSS_SHA256)
1216    if ((params->pad_len == XMSS_SHA256_32_PAD_LEN) &&
1217            (params->n == XMSS_SHA256_32_N) &&
1218            (params->hash == WC_HASH_TYPE_SHA256)) {
1219        wc_xmss_rand_hash_lr_sha256_32(state, left, right, pk_seed, addr, hash);
1220    }
1221    else
1222#endif /* !WOLFSSL_WC_XMSS_SMALL && WC_XMSS_SHA256 */
1223    {
1224        byte* addr_buf = state->prf_buf + params->pad_len + params->n;
1225        /* Offsets into rand hash data. */
1226        byte* pad = state->buf;
1227        byte* key = pad + params->pad_len;
1228        byte* bm0 = key + params->n;
1229        byte* bm1 = bm0 + params->n;
1230        const word32 len = XMSS_HASH_PRF_DATA_LEN(params);
1231
1232        /* Encode padding byte for PRF. */
1233        XMSS_PAD_ENC(XMSS_HASH_PADDING_PRF, state->prf_buf, params->pad_len);
1234        /* Append public seed for PRF. */
1235        XMEMCPY(state->prf_buf + params->pad_len, pk_seed, params->n);
1236
1237        /* Set key mask to initial value and append encoding. */
1238        addr[XMSS_ADDR_KEY_MASK] = 0;
1239        wc_xmss_addr_encode(addr, addr_buf);
1240
1241        /* Calculate n-byte key - KEY. */
1242        wc_xmss_hash(state, state->prf_buf, len, key);
1243        /* Calculate n-byte mask - BM_0. */
1244        addr_buf[XMSS_ADDR_KEY_MASK * 4 + 3] = 1;
1245        wc_xmss_hash(state, state->prf_buf, len, bm0);
1246        /* Calculate n-byte mask - BM_1. */
1247        addr_buf[XMSS_ADDR_KEY_MASK * 4 + 3] = 2;
1248        wc_xmss_hash(state, state->prf_buf, len, bm1);
1249
1250        XMSS_PAD_ENC(XMSS_HASH_PADDING_H, pad, params->pad_len);
1251        XMEMCPY(state->prf_buf, left, params->n);
1252        XMEMCPY(state->prf_buf + params->n, right, params->n);
1253        xorbuf(bm0, state->prf_buf, 2U * params->n);
1254        wc_xmss_hash(state, state->buf, XMSS_RAND_HASH_DATA_LEN(params), hash);
1255    }
1256}
1257#endif /* !WOLFSSL_WC_XMSS_SMALL || WOLFSSL_XMSS_VERIFY_ONLY */
1258
1259/* Compute message hash from the random r, root, index and message.
1260 *
1261 * RFC 8391: 4.1.9, Algorithm 12: XMSS_sign
1262 *    ...
1263 *    byte[n] M' = H_msg(r || getRoot(SK) || (toByte(idx_sig, n)), M);
1264 * RFC 8391: 5.1
1265 *    H_msg: SHA2-256(toByte(2, 32) || KEY || M)
1266 *    H_msg: SHA2-512(toByte(2, 64) || KEY || M)
1267 *    H_msg: SHAKE128(toByte(2, 32) || KEY || M, 256)
1268 *    H_msg: SHAKE256(toByte(2, 64) || KEY || M, 512)
1269 *
1270 * @param [in]  state     XMSS/MT state including digest and parameters.
1271 * @param [in]  random    Random value of n bytes.
1272 * @param [in]  root      Public root.
1273 * @param [in]  idx       Buffer holding encoded index.
1274 * @param [in]  idx_len   Length of encoded index in bytes.
1275 * @param [in]  m         Message to hash.
1276 * @param [in]  mlen      Length of message.
1277 * @param [out] hash      Buffer to hold hash.
1278 */
1279static void wc_xmss_hash_message(XmssState* state, const byte* random,
1280    const byte* root, const byte* idx, word8 idx_len, const byte* m,
1281    word32 mlen, byte* hash)
1282{
1283    int ret;
1284    const XmssParams* params = state->params;
1285    word32 padKeyLen = XMSS_RAND_HASH_DATA_LEN(params);
1286    /* Offsets into message hash data. */
1287    byte* padKey = state->buf;
1288    byte* pad = padKey;
1289    byte* key = pad + params->pad_len;
1290    byte* root_sk = key + params->n;
1291    byte* idx_sig = root_sk + params->n;
1292
1293    /* idx_len encodes a leaf number (4 or 8 bytes per RFC 8391) and is
1294     * front-padded into an n-byte field. n >= 24 for every supported
1295     * parameter set, so idx_len <= n always holds in valid params, but
1296     * guard explicitly: if the invariant is ever violated, the (word32)
1297     * cast on the subtraction would otherwise produce an around 4 GB
1298     * XMEMSET. */
1299    if (idx_len > params->n) {
1300        state->ret = WC_FAILURE;
1301        return;
1302    }
1303
1304    /* Set prefix data before message. */
1305    XMSS_PAD_ENC(XMSS_HASH_PADDING_HASH, pad, params->pad_len);
1306    XMEMCPY(key, random, params->n);
1307    XMEMCPY(root_sk, root, params->n);
1308    XMEMSET(idx_sig, 0, (word32)(params->n - idx_len));
1309    XMEMCPY(idx_sig + params->n - idx_len, idx, idx_len);
1310
1311    /* Hash the padding and key first. */
1312#ifdef WC_XMSS_SHA256
1313    if (params->hash == WC_HASH_TYPE_SHA256) {
1314        ret = wc_Sha256Update(&state->digest.sha256, padKey, padKeyLen);
1315    }
1316    else
1317#endif /* WC_XMSS_SHA256 */
1318#ifdef WC_XMSS_SHA512
1319    if (params->hash == WC_HASH_TYPE_SHA512) {
1320        ret = wc_Sha512Update(&state->digest.sha512, padKey, padKeyLen);
1321    }
1322    else
1323#endif /* WC_XMSS_SHA512 */
1324#ifdef WC_XMSS_SHAKE128
1325    if (params->hash == WC_HASH_TYPE_SHAKE128) {
1326        ret = wc_Shake128_Update(&state->digest.shake, padKey, padKeyLen);
1327    }
1328    else
1329#endif /* WC_XMSS_SHAKE128 */
1330#ifdef WC_XMSS_SHAKE256
1331    if (params->hash == WC_HASH_TYPE_SHAKE256) {
1332        ret = wc_Shake256_Update(&state->digest.shake, padKey, padKeyLen);
1333    }
1334    else
1335#endif /* WC_XMSS_SHAKE256 */
1336    {
1337        /* Unsupported digest function. */
1338        ret = NOT_COMPILED_IN;
1339    }
1340    if (ret == 0) {
1341        /* Generate hash of message - M'. */
1342        wc_xmss_hash(state, m, mlen, hash);
1343    }
1344    else if (state->ret == 0) {
1345        /* Store any digest failures for public APIs to return. */
1346        state->ret = ret;
1347    }
1348}
1349
1350#ifndef WOLFSSL_XMSS_VERIFY_ONLY
1351
1352/* Compute PRF with key and message.
1353 *
1354 * RFC 8391: 5.1
1355 *   PRF: SHA2-256(toByte(3, 32) || KEY || M)
1356 *   PRF: SHA2-512(toByte(3, 64) || KEY || M)
1357 *   PRF: SHAKE128(toByte(3, 32) || KEY || M, 256)
1358 *   PRF: SHAKE256(toByte(3, 64) || KEY || M, 512)
1359 *
1360 * @param [in]  state    XMSS/MT state including digest and parameters.
1361 * @param [in]  key      Key used to derive pseudo-random from.
1362 * @param [in]  m        32 bytes of data to derive pseudo-random from.
1363 * @param [out] prf      Buffer to hold pseudo-random data.
1364 */
1365static void wc_xmss_prf(XmssState* state, const byte* key, const byte* m,
1366    byte* prf)
1367{
1368    const XmssParams* params = state->params;
1369    byte* pad = state->prf_buf;
1370    byte* key_buf = pad + params->pad_len;
1371    byte* m_buf = key_buf + params->n;
1372
1373    /* 00[0..pl-1] || 03 || key[0..n-1] || m[0..31] */
1374    XMSS_PAD_ENC(XMSS_HASH_PADDING_PRF, pad, params->pad_len);
1375    XMEMCPY(key_buf, key, params->n);
1376    XMEMCPY(m_buf, m, XMSS_PRF_M_LEN);
1377
1378    /* Hash the PRF data. */
1379    wc_xmss_hash(state, state->prf_buf,
1380        (word32)params->pad_len + params->n + XMSS_PRF_M_LEN, prf);
1381}
1382
1383#ifdef XMSS_CALL_PRF_KEYGEN
1384/* Compute PRF for keygen with key and message.
1385 *
1386 * NIST SP 800-208: 5.1, 5.2, 5.3, 5.4
1387 *   PRFkeygen (KEY, M): SHA-256(toByte(4, 32) || KEY || M)
1388 *   PRFkeygen (KEY, M): T192(SHA-256(toByte(4, 4) || KEY || M))
1389 *   PRFkeygen (KEY, M): SHAKE256(toByte(4, 32) || KEY || M, 256)
1390 *   PRFkeygen (KEY, M): SHAKE256(toByte(4, 4) || KEY || M, 192)
1391 *
1392 * @param [in]  state    XMSS/MT state including digest and parameters.
1393 * @param [in]  key      Key of n bytes used to derive pseudo-random from.
1394 * @param [in]  m        n + 32 bytes of data to derive pseudo-random from.
1395 * @param [out] prf      Buffer to hold pseudo-random data.
1396 */
1397static void wc_xmss_prf_keygen(XmssState* state, const byte* key,
1398    const byte* m, byte* prf)
1399{
1400    const XmssParams* params = state->params;
1401    byte* pad = state->prf_buf;
1402    byte* key_buf = pad + params->pad_len;
1403    byte* m_buf = key_buf + params->n;
1404
1405    /* 00[0..pl-1] || 04 || key[0..n-1] || m[0..n+31] */
1406    XMSS_PAD_ENC(XMSS_HASH_PADDING_PRF_KEYGEN, pad, params->pad_len);
1407    XMEMCPY(key_buf, key, params->n);
1408    XMEMCPY(m_buf, m, params->n + XMSS_PRF_M_LEN);
1409
1410    /* Hash the PRF keygen data. */
1411    wc_xmss_hash(state, state->prf_buf, params->pad_len + 2 * params->n +
1412        XMSS_PRF_M_LEN, prf);
1413}
1414#endif /* XMSS_CALL_PRF_KEYGEN */
1415
1416#endif /* !WOLFSSL_XMSS_VERIFY_ONLY */
1417
1418/********************************************
1419 * WOTS
1420 ********************************************/
1421
1422#ifndef WOLFSSL_XMSS_VERIFY_ONLY
1423
1424#if !defined(WOLFSSL_WC_XMSS_SMALL) && defined(WC_XMSS_SHA256)
1425/* Expand private seed with PRF keygen.
1426 *
1427 * RFC 8391: 4.1.3
1428 *   "the existence of a method getWOTS_SK(SK, i) is assumed"
1429 * NIST SP 800-208: 7.2.1, Algorithm 10'
1430 *     ...
1431 *     for ( j=0; j < len; j++) {
1432 *       ADRS.setChainAddress(j);
1433 *       sk[j] = PRFkeygen(S_XMSS, SEED || ADRS);
1434 *     }
1435 *
1436 * @param [in]  state     XMSS/MT state including digest and parameters.
1437 * @param [in]  sk_seed   Buffer holding private seed.
1438 * @param [in]  pk_seed   Random public seed.
1439 * @param [in]  addr      Hash address as a byte array.
1440 * @param [out] gen_seed  Buffer to hold seeds.
1441 */
1442static void wc_xmss_wots_get_wots_sk_sha256_32(XmssState* state,
1443    const byte* sk_seed, const byte* pk_seed, byte* addr, byte* gen_seed)
1444{
1445    const XmssParams* params = state->params;
1446    word32 i;
1447    byte* pad = state->prf_buf;
1448    byte* s_xmss = pad + XMSS_SHA256_32_PAD_LEN;
1449    byte* seed = s_xmss + XMSS_SHA256_32_N;
1450    byte* addr_buf = seed + XMSS_SHA256_32_N;
1451    int ret;
1452
1453    ((word32*)addr)[XMSS_ADDR_CHAIN] = 0;
1454    ((word32*)addr)[XMSS_ADDR_HASH] = 0;
1455    ((word32*)addr)[XMSS_ADDR_KEY_MASK] = 0;
1456
1457    XMSS_PAD_ENC(XMSS_HASH_PADDING_PRF_KEYGEN, pad, XMSS_SHA256_32_PAD_LEN);
1458    XMEMCPY(s_xmss, sk_seed, XMSS_SHA256_32_N);
1459    XMEMCPY(seed, pk_seed, XMSS_SHA256_32_N);
1460    XMEMCPY(addr_buf, addr, WC_XMSS_ADDR_LEN);
1461
1462#ifndef WC_XMSS_FULL_HASH
1463    ret = wc_Sha256Update(&state->digest.sha256, pad, XMSS_SHA256_32_PAD_LEN +
1464        XMSS_SHA256_32_N);
1465    if (ret == 0) {
1466        /* Copy state after first 64 bytes. */
1467        XMSS_SHA256_STATE_CACHE(state);
1468        ret = wc_Sha256Update(&state->digest.sha256, seed, XMSS_SHA256_32_N +
1469            WC_XMSS_ADDR_LEN);
1470    }
1471    if (ret == 0) {
1472        ret = wc_Sha256Final(&state->digest.sha256, gen_seed);
1473    }
1474    for (i = 1; (ret == 0) && (i < params->wots_len); i++) {
1475        gen_seed += XMSS_SHA256_32_N;
1476        addr_buf[XMSS_ADDR_CHAIN * 4 + 3] = (byte)i;
1477        XMSS_SHA256_STATE_RESTORE(state, 64);
1478        ret = wc_Sha256Update(&state->digest.sha256, seed, XMSS_SHA256_32_N +
1479            WC_XMSS_ADDR_LEN);
1480        if (ret == 0) {
1481            ret = wc_Sha256Final(&state->digest.sha256, gen_seed);
1482        }
1483    }
1484#else
1485    ret = wc_Sha256Update(&state->digest.sha256, state->prf_buf,
1486        XMSS_SHA256_32_PAD_LEN + 2 * XMSS_SHA256_32_N + WC_XMSS_ADDR_LEN);
1487    if (ret == 0) {
1488        ret = wc_Sha256Final(&state->digest.sha256, gen_seed);
1489    }
1490    for (i = 1; (ret == 0) && i < params->wots_len; i++) {
1491        gen_seed += XMSS_SHA256_32_N;
1492        addr_buf[XMSS_ADDR_CHAIN * 4 + 3] = (byte)i;
1493        ret = wc_Sha256Update(&state->digest.sha256, state->prf_buf,
1494            XMSS_SHA256_32_PAD_LEN + 2 * XMSS_SHA256_32_N + WC_XMSS_ADDR_LEN);
1495        if (ret == 0) {
1496            ret = wc_Sha256Final(&state->digest.sha256, gen_seed);
1497        }
1498    }
1499#endif /*  WC_XMSS_FULL_HASH*/
1500
1501    if (state->ret == 0) {
1502        /* Store any digest failures for public APIs to return. */
1503        state->ret = ret;
1504    }
1505}
1506#endif /* !WOLFSSL_WC_XMSS_SMALL && WC_XMSS_SHA256 */
1507
1508/* Expand private seed with PRF keygen.
1509 *
1510 * RFC 8391: 4.1.3
1511 *   "the existence of a method getWOTS_SK(SK, i) is assumed"
1512 * NIST SP 800-208: 7.2.1
1513 *   Algorithm 10'
1514 *     ...
1515 *     for ( j=0; j < len; j++) {
1516 *       ADRS.setChainAddress(j);
1517 *       sk[j] = PRFkeygen(S_XMSS, SEED || ADRS);
1518 *     }
1519 *
1520 * @param [in]  state     XMSS/MT state including digest and parameters.
1521 * @param [in]  sk_seed   Buffer holding private seed.
1522 * @param [in]  pk_seed   Random public seed.
1523 * @param [in]  addr      Hash address as a byte array.
1524 * @param [out] gen_seed  Buffer to hold seeds.
1525 */
1526static void wc_xmss_wots_get_wots_sk(XmssState* state, const byte* sk_seed,
1527    const byte* pk_seed, byte* addr, byte* gen_seed)
1528{
1529    const XmssParams* params = state->params;
1530    word32 i;
1531#ifdef XMSS_CALL_PRF_KEYGEN
1532    byte* seed = state->buf;
1533    byte* addr_buf = seed + params->n;
1534#else
1535    byte* pad = state->prf_buf;
1536    byte* s_xmss = pad + params->pad_len;
1537    byte* seed = s_xmss + params->n;
1538    byte* addr_buf = seed + params->n;
1539    const word32 len =
1540        (word32)params->pad_len + params->n * 2U + WC_XMSS_ADDR_LEN;
1541#endif /* XMSS_CALL_PRF_KEYGEN */
1542
1543    /* Ensure hash address fields are 0. */
1544    ((word32*)addr)[XMSS_ADDR_CHAIN] = 0;
1545    ((word32*)addr)[XMSS_ADDR_HASH] = 0;
1546    ((word32*)addr)[XMSS_ADDR_KEY_MASK] = 0;
1547
1548#ifdef XMSS_CALL_PRF_KEYGEN
1549    /* Copy the seed and address into PRF keygen message buffer. */
1550    XMEMCPY(seed, pk_seed, params->n);
1551    XMEMCPY(addr_buf, addr, WC_XMSS_ADDR_LEN);
1552
1553    wc_xmss_prf_keygen(state, sk_seed, state->buf, gen_seed);
1554    for (i = 1; i < params->wots_len; i++) {
1555        gen_seed += params->n;
1556        addr_buf[XMSS_ADDR_CHAIN * 4 + 3] = (byte)i;
1557        wc_xmss_prf_keygen(state, sk_seed, state->buf, gen_seed);
1558    }
1559#else
1560    /* Copy the PRF keygen fields into one buffer. */
1561    XMSS_PAD_ENC(XMSS_HASH_PADDING_PRF_KEYGEN, pad, params->pad_len);
1562    XMEMCPY(s_xmss, sk_seed, params->n);
1563    XMEMCPY(seed, pk_seed, params->n);
1564    XMEMCPY(addr_buf, addr, WC_XMSS_ADDR_LEN);
1565
1566    /* Fill output with hashes of different chain hash addresses. */
1567    wc_xmss_hash(state, state->prf_buf, len, gen_seed);
1568    for (i = 1; i < params->wots_len; i++) {
1569        gen_seed += params->n;
1570        addr_buf[XMSS_ADDR_CHAIN * 4 + 3] = (byte)i;
1571        wc_xmss_hash(state, state->prf_buf, len, gen_seed);
1572    }
1573#endif /* XMSS_CALL_PRF_KEYGEN */
1574}
1575
1576#endif /* !WOLFSSL_XMSS_VERIFY_ONLY */
1577
1578#if !defined(WOLFSSL_WC_XMSS_SMALL) && defined(WC_XMSS_SHA256)
1579/* Chain hashing to calculate node hash.
1580 *
1581 * RFC 8391: 3.1.2, Algorithm 2 - recursive.
1582 * This function is an iterative version.
1583 *
1584 * @param [in]  state    XMSS/MT state including digest and parameters.
1585 * @param [in]  data     Initial data to hash.
1586 * @param [in]  start    Starting hash value in hash address.
1587 * @param [in]  steps    Size of step.
1588 * @param [in]  pk_seed  Random public seed.
1589 * @param [in]  addr     Hash address as a byte array.
1590 * @param [out] hash     Chained hash.
1591 */
1592static void wc_xmss_chain_sha256_32(XmssState* state, const byte* data,
1593    unsigned int start, unsigned int steps, const byte* pk_seed, byte* addr,
1594    byte* hash)
1595{
1596    if (steps > 0) {
1597        word32 i;
1598        byte* pad = state->prf_buf;
1599        byte* seed = pad + XMSS_SHA256_32_PAD_LEN;
1600#ifndef WC_XMSS_FULL_HASH
1601        int ret;
1602
1603        /* Set data for PRF hash. */
1604        XMSS_PAD_ENC(XMSS_HASH_PADDING_PRF, pad, XMSS_SHA256_32_PAD_LEN);
1605        XMEMCPY(seed, pk_seed, XMSS_SHA256_32_N);
1606
1607        /* Hash first 64 bytes. */
1608        ret = wc_Sha256Update(&state->digest.sha256, state->prf_buf,
1609             XMSS_SHA256_32_PAD_LEN + XMSS_SHA256_32_N);
1610        if (ret == 0) {
1611            /* Copy state after first 64 bytes. */
1612            XMSS_SHA256_STATE_CACHE(state);
1613            /* Only do this once for all chain hash calls. */
1614            XMSS_PAD_ENC(XMSS_HASH_PADDING_F, state->buf,
1615                state->params->pad_len);
1616
1617            /* Set address. */
1618            XMSS_ADDR_SET_BYTE(addr, XMSS_ADDR_HASH, start);
1619            wc_xmss_chain_hash_sha256_32(state, data, addr, hash);
1620            /* Iterate 'steps' calls to the hash function. */
1621            for (i = start+1; i < (start+steps) && i < XMSS_WOTS_W; i++) {
1622                addr[XMSS_ADDR_HASH * 4 + 3] = (byte)i;
1623                wc_xmss_chain_hash_sha256_32(state, hash, addr, hash);
1624            }
1625        }
1626        else if (state->ret == 0) {
1627            /* Store any digest failures for public APIs to return. */
1628            state->ret = ret;
1629        }
1630#else
1631        const XmssParams* params = state->params;
1632        byte* addr_buf = seed + XMSS_SHA256_32_N;
1633
1634        /* Set data for PRF hash. */
1635        XMSS_PAD_ENC(XMSS_HASH_PADDING_PRF, pad, XMSS_SHA256_32_PAD_LEN);
1636        XMEMCPY(seed, pk_seed, params->n);
1637        XMEMCPY(addr_buf, addr, WC_XMSS_ADDR_LEN);
1638
1639        /* Only do this once for all chain hash calls. */
1640        XMSS_PAD_ENC(XMSS_HASH_PADDING_F, state->buf, params->pad_len);
1641
1642        /* Set address. */
1643        XMSS_ADDR_SET_BYTE(addr_buf, XMSS_ADDR_HASH, start);
1644        wc_xmss_chain_hash_sha256_32(state, data, hash);
1645        /* Iterate 'steps' calls to the hash function. */
1646        for (i = start+1; i < (start+steps) && i < XMSS_WOTS_W; i++) {
1647            addr_buf[XMSS_ADDR_HASH * 4 + 3] = (byte)i;
1648            wc_xmss_chain_hash_sha256_32(state, hash, hash);
1649        }
1650#endif /* !WC_XMSS_FULL_HASH */
1651    }
1652    else if (hash != data) {
1653        XMEMCPY(hash, data, XMSS_SHA256_32_N);
1654    }
1655}
1656#endif /* !WOLFSSL_WC_XMSS_SMALL && WC_XMSS_SHA256 */
1657
1658/* Chain hashing to calculate node hash.
1659 *
1660 * RFC 8391: 3.1.2, Algorithm 2 - recursive.
1661 * This function is an iterative version.
1662 *
1663 * @param [in]  state    XMSS/MT state including digest and parameters.
1664 * @param [in]  data     Initial data to hash.
1665 * @param [in]  start    Starting hash value in hash address.
1666 * @param [in]  steps    Size of step.
1667 * @param [in]  pk_seed  Random public seed.
1668 * @param [in]  addr     Hash address as a byte array.
1669 * @param [out] hash     Chained hash.
1670 */
1671static void wc_xmss_chain(XmssState* state, const byte* data,
1672    unsigned int start, unsigned int steps, const byte* pk_seed, byte* addr,
1673    byte* hash)
1674{
1675    const XmssParams* params = state->params;
1676
1677    if (steps > 0) {
1678        word32 i;
1679        byte* pad = state->prf_buf;
1680        byte* seed = pad + params->pad_len;
1681        byte* addr_buf = seed + params->n;
1682
1683        /* Set data for PRF hash. */
1684        XMSS_PAD_ENC(XMSS_HASH_PADDING_PRF, pad, params->pad_len);
1685        XMEMCPY(seed, pk_seed, params->n);
1686        XMEMCPY(addr_buf, addr, 32);
1687
1688        /* Only do this once for all chain hash calls. */
1689        XMSS_PAD_ENC(XMSS_HASH_PADDING_F, state->buf, params->pad_len);
1690
1691        /* Set address. */
1692        XMSS_ADDR_SET_BYTE(addr_buf, XMSS_ADDR_HASH, start);
1693        wc_xmss_chain_hash(state, data, hash);
1694        /* Iterate 'steps' calls to the hash function. */
1695        for (i = start+1; i < (start+steps) && i < XMSS_WOTS_W; i++) {
1696            addr_buf[XMSS_ADDR_HASH * 4 + 3] = (byte)i;
1697            wc_xmss_chain_hash(state, hash, hash);
1698        }
1699    }
1700    else if (hash != data) {
1701        XMEMCPY(hash, data, params->n);
1702    }
1703}
1704
1705/* Convert base on message and add checksum.
1706 *
1707 * RFC 8391:, 2.6, Algorithm 1: base_w
1708 *     int in = 0;
1709 *     int out = 0;
1710 *     unsigned int total = 0;
1711 *     int bits = 0;
1712 *     int consumed;
1713 *
1714 *     for ( consumed = 0; consumed < out_len; consumed++ ) {
1715 *         if ( bits == 0 ) {
1716 *             total = X[in];
1717 *             in++;
1718 *             bits += 8;
1719 *         }
1720 *         bits -= lg(w);
1721 *         basew[out] = (total >> bits) AND (w - 1);
1722 *         out++;
1723 *     }
1724 *     return basew;
1725 *
1726 * base_w implemented for w == 16 (lg(w) == 4).
1727 *
1728 * RFC 8391: 3.1.5, Algorithm 5:
1729 *     ...
1730 *     csum = 0;
1731 *
1732 *     # Convert message to base w
1733 *     msg = base_w(M, w, len_1);
1734 *     # Compute checksum
1735 *     for ( i = 0; i < len_1; i++ ) {
1736 *           csum = csum + w - 1 - msg[i];
1737 *     }
1738 *
1739 *     # Convert csum to base w
1740 *     csum = csum << ( 8 - ( ( len_2 * lg(w) ) % 8 ));
1741 *     len_2_bytes = ceil( ( len_2 * lg(w) ) / 8 );
1742 *     msg = msg || base_w(toByte(csum, len_2_bytes), w, len_2);
1743 *
1744 * len_1 == 8 * n / 4 = n * 2
1745 * Implemented for len_2 == 3
1746 *
1747 * @param [in]  m      Message data.
1748 * @param [in]  n      Number of bytes in hash.
1749 * @param [out] msg    Message in new base.
1750 */
1751static void wc_xmss_msg_convert(const byte* m, word8 n, word8* msg)
1752{
1753    word8 i;
1754    /* csum is word16: the WOTS+ checksum below relies on arithmetic
1755     * wrapping at 2^16 (max accumulated value 1920 fits, but the algorithm
1756     * treats the field as a fixed-width 16-bit integer per RFC 8391
1757     * Algorithm 7 step 4). */
1758    word16 csum = 0;
1759
1760    /* Split each full byte of m into two bytes of msg. */
1761    for (i = 0; i < n; i++) {
1762        msg[0] = (word8)(m[i] >> 4);
1763        msg[1] = (word8)(m[i] & 0xf);
1764        csum = (word16)(csum + XMSS_WOTS_W - 1U - msg[0]);
1765        csum = (word16)(csum + XMSS_WOTS_W - 1U - msg[1]);
1766        msg += 2;
1767    }
1768
1769    /* Append checksum to message. (Maximum value: 1920 = 64 * 2 * 15) */
1770    msg[0] = (word8)( csum >> 8)        ;
1771    msg[1] = (word8)((csum >> 4) & 0x0f);
1772    msg[2] = (word8)((csum     ) & 0x0f);
1773}
1774
1775#ifndef WOLFSSL_XMSS_VERIFY_ONLY
1776
1777/* WOTS+ generate public key with private seed.
1778 *
1779 * RFC 8391: 4.1.6, Algorithm 9:
1780 *     ...
1781 *     pk = WOTS_genPK (getWOTS_SK(SK, s + i), SEED, ADRS);
1782 * RFC 8391, 3.1.4, Algorithm 4: WOTS_genPK
1783 *     ...
1784 *     for ( i = 0; i < len; i++ ) {
1785 *       ADRS.setChainAddress(i);
1786 *       pk[i] = chain(sk[i], 0, w - 1, SEED, ADRS);
1787 *     }
1788 *     return pk;
1789 *
1790 * WOTS_genPK only used in Algorithm 9 and it is convenient to combine with
1791 * getWOTS_SK due to parameter specific implementations.
1792 *
1793 * @param [in]  state  XMSS/MT state including digest and parameters.
1794 * @param [in]  sk     Random private seed.
1795 * @param [in]  seed   Random public seed.
1796 * @param [in]  addr   Hashing address.
1797 * @param [out] pk     Public key.
1798 */
1799static void wc_xmss_wots_gen_pk(XmssState* state, const byte* sk,
1800    const byte* seed, HashAddress addr, byte* pk)
1801{
1802    const XmssParams* params = state->params;
1803    byte* addr_buf = state->encMsg;
1804    word32 i;
1805
1806    /* Ensure chain address is 0 and encode into a buffer. */
1807    addr[XMSS_ADDR_CHAIN] = 0;
1808    wc_xmss_addr_encode(addr, addr_buf);
1809
1810#if !defined(WOLFSSL_WC_XMSS_SMALL) && defined(WC_XMSS_SHA256)
1811    if ((params->pad_len == XMSS_SHA256_32_PAD_LEN) &&
1812            (params->n == XMSS_SHA256_32_N) &&
1813            (params->hash == WC_HASH_TYPE_SHA256)) {
1814        /* Expand the private seed - getWOTS_SK */
1815        wc_xmss_wots_get_wots_sk_sha256_32(state, sk, seed, addr_buf,
1816            pk);
1817
1818        /* Calculate chain hash. */
1819        wc_xmss_chain_sha256_32(state, pk, 0, XMSS_WOTS_W - 1, seed, addr_buf,
1820            pk);
1821        for (i = 1; i < params->wots_len; i++) {
1822            pk += params->n;
1823            addr_buf[XMSS_ADDR_CHAIN * 4 + 3] = (byte)i;
1824            wc_xmss_chain_sha256_32(state, pk, 0, XMSS_WOTS_W - 1, seed,
1825                addr_buf, pk);
1826        }
1827    }
1828    else
1829#endif /* !WOLFSSL_WC_XMSS_SMALL && WC_XMSS_SHA256 */
1830    {
1831        /* Expand the private seed - getWOTS_SK */
1832        wc_xmss_wots_get_wots_sk(state, sk, seed, addr_buf, pk);
1833
1834        /* Calculate chain hash. */
1835        wc_xmss_chain(state, pk, 0, XMSS_WOTS_W - 1, seed, addr_buf, pk);
1836        for (i = 1; i < params->wots_len; i++) {
1837            pk += params->n;
1838            addr_buf[XMSS_ADDR_CHAIN * 4 + 3] = (byte)i;
1839            wc_xmss_chain(state, pk, 0, XMSS_WOTS_W - 1, seed, addr_buf, pk);
1840        }
1841    }
1842}
1843/* Generate a signature from a privatge key and message.
1844 *
1845 * RFC 8391: 4.1.9, Algorithm 11: treeSig
1846 *     sig_ots = WOTS_sign(getWOTS_SK(SK, idx_sig),
1847 *                         M', getSEED(SK), ADRS);
1848 * RFC 8391: 3.1.5, Algorithm 5: WOTS_sign
1849 *     (Convert message to base w and append checksum in base w)
1850 *     ...
1851 *     for ( i = 0; i < len; i++ ) {
1852 *          ADRS.setChainAddress(i);
1853 *          sig[i] = chain(sk[i], 0, msg[i], SEED, ADRS);
1854 *     }
1855 *     return sig;
1856 *
1857 * WOTS_sign only used in Algorithm 11 and convenient to do getWOTS_SK due to
1858 * hash address reuse and parameter specific implementations.
1859 *
1860 * @param [in]  state  XMSS/MT state including digest and parameters.
1861 * @param [in]  m      Message hash to sign.
1862 * @param [in]  sk     Random private seed.
1863 * @param [in]  seed   Random public seed.
1864 * @param [in]  addr   Hashing address.
1865 * @param [out] sig    Calculated XMSS/MT signature.
1866 */
1867static void wc_xmss_wots_sign(XmssState* state, const byte* m,
1868    const byte* sk, const byte* seed, HashAddress addr, byte* sig)
1869{
1870    const XmssParams* params = state->params;
1871    byte* addr_buf = state->pk;
1872    word32 i;
1873
1874    /* Convert message to base w and append checksum in base w. */
1875    wc_xmss_msg_convert(m, params->n, state->encMsg);
1876
1877    /* Set initial chain value and encode hash address. */
1878    addr[XMSS_ADDR_CHAIN] = 0;
1879    wc_xmss_addr_encode(addr, addr_buf);
1880
1881#if !defined(WOLFSSL_WC_XMSS_SMALL) && defined(WC_XMSS_SHA256)
1882    if ((params->pad_len == XMSS_SHA256_32_PAD_LEN) &&
1883            (params->n == XMSS_SHA256_32_N) &&
1884            (params->hash == WC_HASH_TYPE_SHA256)) {
1885        /* Expand the private seed - getWOTS_SK */
1886        wc_xmss_wots_get_wots_sk_sha256_32(state, sk, seed, addr_buf, sig);
1887
1888        /* Calculate chain hash. */
1889        wc_xmss_chain_sha256_32(state, sig, 0, state->encMsg[0], seed, addr_buf,
1890            sig);
1891        for (i = 1; i < params->wots_len; i++) {
1892            sig += params->n;
1893            addr_buf[XMSS_ADDR_CHAIN * 4 + 3] = (byte)i;
1894            wc_xmss_chain_sha256_32(state, sig, 0, state->encMsg[i], seed,
1895                addr_buf, sig);
1896        }
1897    }
1898    else
1899#endif /* !WOLFSSL_WC_XMSS_SMALL && WC_XMSS_SHA256 */
1900    {
1901        /* Expand the private seed - getWOTS_SK */
1902        wc_xmss_wots_get_wots_sk(state, sk, seed, addr_buf, sig);
1903
1904       /* Calculate chain hash. */
1905        wc_xmss_chain(state, sig, 0, state->encMsg[0], seed, addr_buf, sig);
1906        for (i = 1; i < params->wots_len; i++) {
1907            sig += params->n;
1908            addr_buf[XMSS_ADDR_CHAIN * 4 + 3] = (byte)i;
1909            wc_xmss_chain(state, sig, 0, state->encMsg[i], seed, addr_buf, sig);
1910        }
1911    }
1912}
1913
1914#endif /* !WOLFSSL_XMSS_VERIFY_ONLY */
1915
1916/* Compute WOTS+ public key value from signature and message.
1917 *
1918 * RFC 8319: 3.1.6
1919 *   Algorithm 6: WOTS_pkFromSig
1920 *     (Convert message to base w and append checksum in base w)
1921 *     ...
1922 *     for ( i = 0; i < len; i++ ) {
1923 *          ADRS.setChainAddress(i);
1924 *          tmp_pk[i] = chain(sig[i], msg[i], w - 1 - msg[i], SEED, ADRS);
1925 *     }
1926 *     return tmp_pk;
1927 *
1928 * @param [in]  state  XMSS/MT state including digest and parameters.
1929 * @param [in]  sig    XMSS/MT Signature.
1930 * @param [in]  m      Message to verify.
1931 * @param [in]  seed   Random public seed.
1932 * @param [in]  addr   Hashing address.
1933 * @param [out] pk     Public key.
1934 */
1935static void wc_xmss_wots_pk_from_sig(XmssState* state, const byte* sig,
1936    const byte* m, const byte* seed, HashAddress addr, byte* pk)
1937{
1938    const XmssParams* params = state->params;
1939    byte* addr_buf = state->stack;
1940    word32 i;
1941
1942    /* Convert message to base w and append checksum in base w. */
1943    wc_xmss_msg_convert(m, params->n, state->encMsg);
1944
1945    /* Start with address with chain value of 0. */
1946    addr[XMSS_ADDR_CHAIN] = 0;
1947    wc_xmss_addr_encode(addr, addr_buf);
1948
1949#if !defined(WOLFSSL_WC_XMSS_SMALL) && defined(WC_XMSS_SHA256)
1950    if ((params->pad_len == XMSS_SHA256_32_PAD_LEN) &&
1951            (params->n == XMSS_SHA256_32_N) &&
1952            (params->hash == WC_HASH_TYPE_SHA256)) {
1953        /* Calculate chain hash. */
1954        wc_xmss_chain_sha256_32(state, sig, state->encMsg[0],
1955            XMSS_WOTS_W - 1 - state->encMsg[0], seed, addr_buf, pk);
1956        for (i = 1; i < params->wots_len; i++) {
1957            sig += params->n;
1958            pk += params->n;
1959            /* Update chain. */
1960            addr_buf[XMSS_ADDR_CHAIN * 4 + 3] = (byte)i;
1961            wc_xmss_chain_sha256_32(state, sig, state->encMsg[i],
1962                XMSS_WOTS_W - 1 - state->encMsg[i], seed, addr_buf, pk);
1963        }
1964    }
1965    else
1966#endif /* !WOLFSSL_WC_XMSS_SMALL && WC_XMSS_SHA256 */
1967    {
1968        /* Calculate chain hash. */
1969        wc_xmss_chain(state, sig, state->encMsg[0],
1970            XMSS_WOTS_W - 1 - state->encMsg[0], seed, addr_buf, pk);
1971        for (i = 1; i < params->wots_len; i++) {
1972            sig += params->n;
1973            pk += params->n;
1974            /* Update chain. */
1975            addr_buf[XMSS_ADDR_CHAIN * 4 + 3] = (byte)i;
1976            wc_xmss_chain(state, sig, state->encMsg[i],
1977                XMSS_WOTS_W - 1 - state->encMsg[i], seed, addr_buf, pk);
1978        }
1979    }
1980}
1981
1982/********************************************
1983 * L-TREE - unbalanced binary hash tree
1984 ********************************************/
1985
1986/* Compute leaves of L-tree from WOTS+ public key and compress to single value.
1987 *
1988 * RFC 8391: 4.1.5, Algorithm 8: ltree
1989 *     unsigned int len' = len;
1990 *     ADRS.setTreeHeight(0);
1991 *     while ( len' > 1 ) {
1992 *       for ( i = 0; i < floor(len' / 2); i++ ) {
1993 *         ADRS.setTreeIndex(i);
1994 *         pk[i] = RAND_HASH(pk[2i], pk[2i + 1], SEED, ADRS);
1995 *       }
1996 *       if ( len' % 2 == 1 ) {
1997 *         pk[floor(len' / 2)] = pk[len' - 1];
1998 *       }
1999 *       len' = ceil(len' / 2);
2000 *       ADRS.setTreeHeight(ADRS.getTreeHeight() + 1);
2001 *     }
2002 *     return pk[0];
2003 *
2004 * @param [in]  state  XMSS/MT state including digest and parameters.
2005 * @param [in]  pk     WOTS+ public key.
2006 * @param [in]  seed   Random public seed.
2007 * @param [in]  addr   Hashing address.
2008 * @param [out] pk0    N-byte compressed public key value pk[0].
2009 */
2010static void wc_xmss_ltree(XmssState* state, byte* pk, const byte* seed,
2011    HashAddress addr, byte* pk0)
2012{
2013    const XmssParams* params = state->params;
2014    word8 len = params->wots_len;
2015    word32 h = 0;
2016
2017#if !defined(WOLFSSL_WC_XMSS_SMALL) && defined(WC_XMSS_SHA256) && \
2018    !defined(WC_XMSS_FULL_HASH)
2019    /* Precompute hash state after first 64 bytes (common to all hashes). */
2020    if ((params->pad_len == XMSS_SHA256_32_PAD_LEN) &&
2021            (params->n == XMSS_SHA256_32_N) &&
2022            (params->hash == WC_HASH_TYPE_SHA256)) {
2023        byte* prf_buf = state->prf_buf;
2024        int ret;
2025
2026        XMSS_PAD_ENC(XMSS_HASH_PADDING_PRF, prf_buf, XMSS_SHA256_32_PAD_LEN);
2027        XMEMCPY(prf_buf + XMSS_SHA256_32_PAD_LEN, seed, XMSS_SHA256_32_N);
2028
2029        ret = wc_Sha256Update(&state->digest.sha256, prf_buf,
2030            XMSS_SHA256_32_PAD_LEN + XMSS_SHA256_32_N);
2031        if (ret == 0) {
2032            /* Copy state after first 64 bytes. */
2033            XMSS_SHA256_STATE_CACHE(state);
2034        }
2035        else if (state->ret == 0) {
2036            /* Store any digest failures for public APIs to return. */
2037            state->ret = ret;
2038        }
2039    }
2040#endif /* !WOLFSSL_WC_XMSS_SMALL && WC_XMSS_SHA256 && !WC_XMSS_FULL_HASH */
2041    while (len > 1) {
2042        word8 i;
2043        word8 len2 = len >> 1;
2044
2045        addr[XMSS_ADDR_TREE_HEIGHT] = h++;
2046
2047        for (i = 0; i < len2; i++) {
2048            addr[XMSS_ADDR_TREE_INDEX] = i;
2049        #if !defined(WOLFSSL_WC_XMSS_SMALL) && defined(WC_XMSS_SHA256) && \
2050            !defined(WC_XMSS_FULL_HASH)
2051            if ((params->pad_len == XMSS_SHA256_32_PAD_LEN) &&
2052                    (params->n == XMSS_SHA256_32_N) &&
2053                    (params->hash == WC_HASH_TYPE_SHA256)) {
2054                wc_xmss_rand_hash_sha256_32_prehash(state,
2055                    pk + i * 2 * XMSS_SHA256_32_N, addr,
2056                    pk + i * XMSS_SHA256_32_N);
2057            }
2058            else
2059        #endif /* !WOLFSSL_WC_XMSS_SMALL && WC_XMSS_SHA256 &&
2060                * !WC_XMSS_FULL_HASH */
2061            {
2062                wc_xmss_rand_hash(state, pk + i * 2 * params->n,
2063                    seed, addr, pk + i * params->n);
2064            }
2065        }
2066        if (len & 1) {
2067            XMEMCPY(pk + len2 * params->n, pk + (len - 1) * params->n,
2068                params->n);
2069        }
2070        len = (word8)(len2 + (len & 1));
2071    }
2072    /* Return compressed public key value pk[0]. */
2073    XMEMCPY(pk0, pk, params->n);
2074}
2075
2076#ifndef WOLFSSL_XMSS_VERIFY_ONLY
2077
2078#ifdef WOLFSSL_WC_XMSS_SMALL
2079
2080/********************************************
2081 * TREE HASH
2082 ********************************************/
2083
2084#ifndef WOLFSSL_SMALL_STACK
2085/* Compute internal nodes of Merkle tree.
2086 *
2087 * Implementation always starts at index 0. (s = 0)
2088 *
2089 * Build authentication path, if required, rather than duplicating work.
2090 * When node is generated, copy out to authentication path array of nodes.
2091 *
2092 * RFC 8391: 4.1.6, Algorithm 9: treeHash
2093 *     if( s % (1 << t) != 0 ) return -1;
2094 *     for ( i = 0; i < 2^t; i++ ) {
2095 *       SEED = getSEED(SK);
2096 *       ADRS.setType(0);   # Type = OTS hash address
2097 *       ADRS.setOTSAddress(s + i);
2098 *       pk = WOTS_genPK (getWOTS_SK(SK, s + i), SEED, ADRS);
2099 *       ADRS.setType(1);   # Type = L-tree address
2100 *       ADRS.setLTreeAddress(s + i);
2101 *       node = ltree(pk, SEED, ADRS);
2102 *       ADRS.setType(2);   # Type = hash tree address
2103 *       ADRS.setTreeHeight(0);
2104 *       ADRS.setTreeIndex(i + s);
2105 *       while ( Top node on Stack has same height t' as node ) {
2106 *          ADRS.setTreeIndex((ADRS.getTreeIndex() - 1) / 2);
2107 *          node = RAND_HASH(Stack.pop(), node, SEED, ADRS);
2108 *          ADRS.setTreeHeight(ADRS.getTreeHeight() + 1);
2109 *       }
2110 *       Stack.push(node);
2111 *     }
2112 *     return Stack.pop();
2113 * RFC 8391: 4.1.9, (Example) buildAuth
2114 *     for ( j = 0; j < h; j++ ) {
2115 *       k = floor(i / (2^j)) XOR 1;
2116 *       auth[j] = treeHash(SK, k * 2^j, j, ADRS);
2117 *     }
2118 *
2119 * @param [in]  state         XMSS/MT state including digest and parameters.
2120 * @param [in]  sk_seed       Random private seed.
2121 * @param [in]  pk_seed       Random public seed.
2122 * @param [in]  leafIdx       Index of lead node.
2123 * @param [in]  subtree_addr  Address of subtree.
2124 * @param [out] root          Root node of the tree.
2125 * @param [out] auth_path     Nodes of the authentication path.
2126 */
2127static void wc_xmss_treehash(XmssState* state, const byte* sk_seed,
2128    const byte* pk_seed, word32 leafIdx, const word32* subtree, byte* root,
2129    byte* auth_path)
2130{
2131    const XmssParams* params = state->params;
2132    const word8 n = params->n;
2133    byte* node = state->stack;
2134    HashAddress ots;
2135    HashAddress ltree;
2136    HashAddress tree;
2137    word8 height[WC_XMSS_MAX_TREE_HEIGHT + 1];
2138    word8 offset = 0;
2139    word32 max = (word32)1U << params->sub_h;
2140    word32 i;
2141
2142    /* Copy hash address into one for each purpose.  */
2143    XMSS_ADDR_OTS_SET_SUBTREE(ots, subtree);
2144    XMSS_ADDR_LTREE_SET_SUBTREE(ltree, subtree);
2145    XMSS_ADDR_TREE_SET_SUBTREE(tree, subtree);
2146
2147    for (i = 0; i < max; i++) {
2148        word8 h;
2149
2150        /* Calculate WOTS+ public key. */
2151        ots[XMSS_ADDR_OTS] = i;
2152        wc_xmss_wots_gen_pk(state, sk_seed, pk_seed, ots, state->pk);
2153        /* Calculate public value. */
2154        ltree[XMSS_ADDR_LTREE] = i;
2155        wc_xmss_ltree(state, state->pk, pk_seed, ltree, node);
2156
2157        /* Initial height at this offset is 0. */
2158        h = height[offset] = 0;
2159        /* Copy node, at height 0, out if on authentication path. */
2160        if ((auth_path != NULL) && ((leafIdx ^ 0x1) == i)) {
2161            XMEMCPY(auth_path, node, n);
2162        }
2163
2164        /* Top node on Stack has same height t' as node. */
2165        while ((offset >= 1) && (h == height[offset - 1])) {
2166            word32 tree_idx = i >> (h + 1);
2167
2168            node -= n;
2169            /* Calculate hash of node. */
2170            tree[XMSS_ADDR_TREE_HEIGHT] = h;
2171            tree[XMSS_ADDR_TREE_INDEX] = tree_idx;
2172            wc_xmss_rand_hash(state, node, pk_seed, tree, node);
2173
2174            /* Update offset and height. */
2175            offset--;
2176            h = ++height[offset];
2177
2178            /* Copy node out if on authentication path. */
2179            if ((auth_path != NULL) && (((leafIdx >> h) ^ 0x1) == tree_idx)) {
2180                XMEMCPY(auth_path + h * n, node, n);
2181            }
2182        }
2183        offset++;
2184        node += n;
2185    }
2186
2187    /* Copy the root node. */
2188    XMEMCPY(root, state->stack, n);
2189}
2190#else
2191/* Compute internal nodes of Merkle tree.
2192 *
2193 * Implementation always starts at index 0. (s = 0)
2194 *
2195 * Build authentication path, if required, rather than duplicating work.
2196 * When node is generated, copy out to authentication path array of nodes.
2197 *
2198 * RFC 8391: 4.1.6, Algorithm 9: treeHash
2199 *     if( s % (1 << t) != 0 ) return -1;
2200 *     for ( i = 0; i < 2^t; i++ ) {
2201 *       SEED = getSEED(SK);
2202 *       ADRS.setType(0);   # Type = OTS hash address
2203 *       ADRS.setOTSAddress(s + i);
2204 *       pk = WOTS_genPK (getWOTS_SK(SK, s + i), SEED, ADRS);
2205 *       ADRS.setType(1);   # Type = L-tree address
2206 *       ADRS.setLTreeAddress(s + i);
2207 *       node = ltree(pk, SEED, ADRS);
2208 *       ADRS.setType(2);   # Type = hash tree address
2209 *       ADRS.setTreeHeight(0);
2210 *       ADRS.setTreeIndex(i + s);
2211 *       while ( Top node on Stack has same height t' as node ) {
2212 *          ADRS.setTreeIndex((ADRS.getTreeIndex() - 1) / 2);
2213 *          node = RAND_HASH(Stack.pop(), node, SEED, ADRS);
2214 *          ADRS.setTreeHeight(ADRS.getTreeHeight() + 1);
2215 *       }
2216 *       Stack.push(node);
2217 *     }
2218 *     return Stack.pop();
2219 * RFC 8391: 4.1.9, (Example) buildAuth
2220 *     for ( j = 0; j < h; j++ ) {
2221 *       k = floor(i / (2^j)) XOR 1;
2222 *       auth[j] = treeHash(SK, k * 2^j, j, ADRS);
2223 *     }
2224 *
2225 * @param [in]  state         XMSS/MT state including digest and parameters.
2226 * @param [in]  sk_seed       Random private seed.
2227 * @param [in]  pk_seed       Random public seed.
2228 * @param [in]  leafIdx       Index of lead node.
2229 * @param [in]  subtree_addr  Address of subtree.
2230 * @param [out] root          Root node of the tree.
2231 * @param [out] auth_path     Nodes of the authentication path.
2232 */
2233static void wc_xmss_treehash(XmssState* state, const byte* sk_seed,
2234    const byte* pk_seed, word32 leafIdx, const word32* subtree, byte* root,
2235    byte* auth_path)
2236{
2237    const XmssParams* params = state->params;
2238    const word8 n = params->n;
2239    byte* node = state->stack;
2240    HashAddress addr;
2241    word8 height[WC_XMSS_MAX_TREE_HEIGHT + 1];
2242    word8 offset = 0;
2243    word32 max = (word32)1U << params->sub_h;
2244    word32 i;
2245
2246    XMSS_ADDR_SET_SUBTREE(addr, subtree, 0);
2247
2248    for (i = 0; i < max; i++) {
2249        word8 h;
2250
2251        /* Calculate WOTS+ public key. */
2252        addr[XMSS_ADDR_TYPE] = WC_XMSS_ADDR_TYPE_OTS;
2253        addr[XMSS_ADDR_LTREE] = i;
2254        wc_xmss_wots_gen_pk(state, sk_seed, pk_seed, addr, state->pk);
2255        /* Calculate public value. */
2256        addr[XMSS_ADDR_TYPE] = WC_XMSS_ADDR_TYPE_LTREE;
2257        wc_xmss_ltree(state, state->pk, pk_seed, addr, node);
2258        addr[XMSS_ADDR_TYPE] = WC_XMSS_ADDR_TYPE_TREE;
2259        addr[XMSS_ADDR_TREE_ZERO] = 0;
2260
2261        /* Initial height at this offset is 0. */
2262        h = height[offset] = 0;
2263        /* Copy node out if on authentication path. */
2264        if ((auth_path != NULL) && ((leafIdx ^ 0x1) == i)) {
2265            XMEMCPY(auth_path, node, n);
2266        }
2267
2268        /* Top node on Stack has same height t' as node. */
2269        while ((offset >= 1) && (h == height[offset - 1])) {
2270            word32 tree_idx = i >> (h + 1);
2271
2272            node -= n;
2273            /* Calculate hash of node. */
2274            addr[XMSS_ADDR_TREE_HEIGHT] = h;
2275            addr[XMSS_ADDR_TREE_INDEX] = tree_idx;
2276            wc_xmss_rand_hash(state, node, pk_seed, addr, node);
2277
2278            /* Update offset and height. */
2279            offset--;
2280            h = ++height[offset];
2281
2282            /* Copy node out if on authentication path. */
2283            if ((auth_path != NULL) && (((leafIdx >> h) ^ 0x1) == tree_idx)) {
2284                XMEMCPY(auth_path + h * n, node, n);
2285            }
2286        }
2287        offset++;
2288        node += n;
2289        /* Reset hash address ready for use as OTS and LTREE. */
2290        addr[XMSS_ADDR_TREE_HEIGHT] = 0;
2291        addr[XMSS_ADDR_TREE_INDEX] = 0;
2292    }
2293
2294    /* Copy the root node. */
2295    XMEMCPY(root, state->stack, n);
2296}
2297#endif /* !WOLFSSL_SMALL_STACK */
2298
2299/********************************************
2300 * MAKE KEY
2301 ********************************************/
2302
2303/* Derives XMSSMT (and XMSS) key pair from seeds.
2304 *
2305 * RFC 8391: 4.1.7, Algorithm 10: XMSS_keyGen.
2306 *     ...
2307 *     initialize SK_PRF with a uniformly random n-byte string;
2308 *     setSK_PRF(SK, SK_PRF);
2309 *
2310 *     # Initialization for common contents
2311 *     initialize SEED with a uniformly random n-byte string;
2312 *     setSEED(SK, SEED);
2313 *     setWOTS_SK(SK, wots_sk));
2314 *     ADRS = toByte(0, 32);
2315 *     root = treeHash(SK, 0, h, ADRS);
2316 *
2317 *     SK = idx || wots_sk || SK_PRF || root || SEED;
2318 *     PK = OID || root || SEED;
2319 *     return (SK || PK);
2320 *
2321 * wots_sk, SK_PRF and SEED passed in as seed.
2322 * Store seed for wots_sk instead of generated wots_sk.
2323 * OID not stored in PK this is handled in upper layer.
2324 *
2325 * @param [in]  state   XMSS/MT state including digest and parameters.
2326 * @param [in]  seed    Random seeds.
2327 * @param [out] sk      Secret/Private key.
2328 * @param [out] pk      Public key.
2329 * @return  0 on success.
2330 * @return  <0 on digest failure.
2331 */
2332int wc_xmssmt_keygen(XmssState* state, const unsigned char* seed,
2333    unsigned char* sk, unsigned char* pk)
2334{
2335    const XmssParams* params = state->params;
2336    const word8 n = params->n;
2337    const byte* seed_priv = seed;
2338    const byte* seed_pub  = seed + 2 * n;
2339    /* Offsets into secret/private key. */
2340    byte* sk_idx  = sk;
2341    byte* sk_seed = sk_idx + params->idx_len;
2342    byte* sk_pub  = sk_seed + 2 * n;
2343    /* Offsets into public key. */
2344    byte* pk_root = pk;
2345    byte* pk_seed = pk_root + n;
2346
2347    /* Set first index to 0 in private key. */
2348    XMEMSET(sk_idx, 0, params->idx_len);
2349    /* Set private key seed and private key for PRF in to private key. */
2350    XMEMCPY(sk_seed, seed_priv, 2U * n);
2351    /* Set public key seed into public key. */
2352    XMEMCPY(pk_seed, seed_pub, n);
2353
2354    /* Set all address values to zero. */
2355    XMEMSET(state->addr, 0, sizeof(HashAddress));
2356    /* Set depth into address. */
2357    state->addr[XMSS_ADDR_LAYER] = (word32)(params->d - 1);
2358    /* Compute root node into public key. */
2359    wc_xmss_treehash(state, sk_seed, pk_seed, 0, state->addr, pk_root, NULL);
2360
2361    /* Append public key (root node and public seed) to private key. */
2362    XMEMCPY(sk_pub, pk_root, 2U * n);
2363
2364    /* Return any errors that occurred during hashing. */
2365    return state->ret;
2366}
2367
2368/********************************************
2369 * SIGN
2370 ********************************************/
2371
2372/**
2373 * Sign message using XMSS/XMSS^MT.
2374 *
2375 * RFC 8391: 4.1.9, Algorithm 11: treeSig
2376 *     auth = buildAuth(SK, idx_sig, ADRS);
2377 *     ADRS.setType(0);   # Type = OTS hash address
2378 *     ADRS.setOTSAddress(idx_sig);
2379 *     sig_ots = WOTS_sign(getWOTS_SK(SK, idx_sig),
2380 *                         M', getSEED(SK), ADRS);
2381 *     Sig = sig_ots || auth;
2382 *     return Sig;
2383 * RFC 8391: 4.2.4, Algorithm 16: XMSSMT_sign
2384 *     # Init
2385 *     ADRS = toByte(0, 32);
2386 *     SEED = getSEED(SK_MT);
2387 *     SK_PRF = getSK_PRF(SK_MT);
2388 *     idx_sig = getIdx(SK_MT);
2389 *
2390 *     # Update SK_MT
2391 *     setIdx(SK_MT, idx_sig + 1);
2392 *
2393 *     # Message compression
2394 *     byte[n] r = PRF(SK_PRF, toByte(idx_sig, 32));
2395 *     byte[n] M' = H_msg(r || getRoot(SK_MT) || (toByte(idx_sig, n)), M);
2396 *
2397 *     # Sign
2398 *     Sig_MT = idx_sig;
2399 *     unsigned int idx_tree
2400 *                   = (h - h / d) most significant bits of idx_sig;
2401 *     unsigned int idx_leaf = (h / d) least significant bits of idx_sig;
2402 *     SK = idx_leaf || getXMSS_SK(SK_MT, idx_tree, 0) || SK_PRF
2403 *           || toByte(0, n) || SEED;
2404 *     ADRS.setLayerAddress(0);
2405 *     ADRS.setTreeAddress(idx_tree);
2406 *     Sig_tmp = treeSig(M', SK, idx_leaf, ADRS);
2407 *     Sig_MT = Sig_MT || r || Sig_tmp;
2408 *     for ( j = 1; j < d; j++ ) {
2409 *        root = treeHash(SK, 0, h / d, ADRS);
2410 *        idx_leaf = (h / d) least significant bits of idx_tree;
2411 *        idx_tree = (h - j * (h / d)) most significant bits of idx_tree;
2412 *        SK = idx_leaf || getXMSS_SK(SK_MT, idx_tree, j) || SK_PRF
2413 *               || toByte(0, n) || SEED;
2414 *        ADRS.setLayerAddress(j);
2415 *        ADRS.setTreeAddress(idx_tree);
2416 *        Sig_tmp = treeSig(root, SK, idx_leaf, ADRS);
2417 *        Sig_MT = Sig_MT || Sig_tmp;
2418 *     }
2419 *     return SK_MT || Sig_MT
2420 *
2421 * buildAuth from treeSig done inside treeHash as this is more efficient.
2422 *
2423 * @param [in]      state   XMSS/MT state including digest and parameters.
2424 * @param [in]      m       Buffer holding message.
2425 * @param [in]      mlen    Length of message in buffer.
2426 * @param [in, out] sk      Secret/Private key.
2427 * @param [out]     sig     Signature.
2428 * @return  0 on success.
2429 * @return  <0 on digest failure.
2430 */
2431int wc_xmssmt_sign(XmssState* state, const unsigned char* m, word32 mlen,
2432    unsigned char* sk, unsigned char* sig)
2433{
2434    int ret = 0;
2435    const XmssParams* params = state->params;
2436    const word8 n = params->n;
2437    const word8 hs = params->sub_h;
2438    const word16 hsn = (word16)(hs * n);
2439    const byte* sk_seed = sk + params->idx_len;
2440    const byte* pk_seed = sk + params->idx_len + 3 * n;
2441    wc_Idx idx;
2442    byte* sig_r = sig + params->idx_len;
2443    byte root[WC_XMSS_MAX_N];
2444    unsigned int i;
2445
2446    WC_IDX_ZERO(idx);
2447    /* Set all address values to zero and set type to OTS. */
2448    XMEMSET(state->addr, 0, sizeof(HashAddress));
2449    state->addr[XMSS_ADDR_TYPE] = WC_XMSS_ADDR_TYPE_OTS;
2450
2451    /* Copy the index into the signature data: Sig_MT = idx_sig. */
2452    XMEMCPY(sig, sk, params->idx_len);
2453
2454    /* Read index from the secret key. */
2455    WC_IDX_DECODE(idx, params->idx_len, sk, ret);
2456    /* Validate index in secret key. */
2457    if ((ret == 0) && (WC_IDX_INVALID(idx, params->idx_len, params->h))) {
2458        /* Set index to maximum value to distinguish from valid value. */
2459        XMEMSET(sk, 0xFF, params->idx_len);
2460        /* Zeroize the secret key. */
2461        ForceZero(sk + params->idx_len, params->sk_len - params->idx_len);
2462        ret = KEY_EXHAUSTED_E;
2463    }
2464
2465    /* Update SK_MT */
2466    if (ret == 0) {
2467        /* Increment the index in the secret key. */
2468        wc_idx_update(sk, params->idx_len);
2469    }
2470
2471    /* Message compression */
2472    if (ret == 0) {
2473        const byte* sk_prf = sk + params->idx_len + n;
2474
2475        /* byte[n] r = PRF(SK_PRF, toByte(idx_sig, 32)); */
2476        wc_idx_copy(sig, params->idx_len, state->buf, XMSS_PRF_M_LEN);
2477        wc_xmss_prf(state, sk_prf, state->buf, sig_r);
2478        ret = state->ret;
2479    }
2480    if (ret == 0) {
2481        const byte* pub_root = sk + params->idx_len + 2 * n;
2482        /* byte[n] M' = H_msg(r || getRoot(SK_MT) || (toByte(idx_sig, n)), M);
2483         */
2484        wc_xmss_hash_message(state, sig_r, pub_root, sig, params->idx_len, m,
2485            mlen, root);
2486        ret = state->ret;
2487        /* Place WOTS+ signatures after index and 'r'. */
2488        sig += params->idx_len + n;
2489    }
2490
2491    /* Sign. */
2492    for (i = 0; (ret == 0) && (i < params->d); i++) {
2493        word32 idx_leaf = 0;
2494
2495        /* Set layer, tree and OTS leaf index into hash address. */
2496        state->addr[XMSS_ADDR_LAYER] = i;
2497        WC_IDX_SET_ADDR_TREE(idx, params->idx_len, hs, state->addr, idx_leaf);
2498        /* treeSig || treeHash = sig_ots || auth */
2499        state->addr[XMSS_ADDR_OTS] = idx_leaf;
2500        /*   Create WOTS+ signature for tree into signature (sig_ots). */
2501        wc_xmss_wots_sign(state, root, sk_seed, pk_seed, state->addr, sig);
2502        ret = state->ret;
2503        if (ret == 0) {
2504            sig += params->wots_sig_len;
2505            /*   Add authentication path (auth) and calc new root. */
2506            wc_xmss_treehash(state, sk_seed, pk_seed, idx_leaf, state->addr,
2507                root, sig);
2508            ret = state->ret;
2509            sig += hsn;
2510        }
2511    }
2512
2513    return ret;
2514}
2515
2516#else
2517
2518/********************************************
2519 * Fast C implementation
2520 ********************************************/
2521
2522/* Tree hash data - needs to be unpacked from binary. */
2523typedef struct TreeHash {
2524    /* Next index to update in tree - max 20 bits. */
2525    word32 nextIdx;
2526    /* Number of stack entries used by tree - 0..<subtree height>. */
2527    word8  used;
2528    /* Tree is finished. */
2529    word8  completed;
2530} TreeHash;
2531
2532/* BDS state. */
2533typedef struct BdsState {
2534    /* Stack of nodes - subtree height + 1 nodes. */
2535    byte*     stack;
2536    /* Height of stack node - subtree height + 1 of 0..<subtree height - 1>. */
2537    byte*     height;
2538    /* Authentication path for next index - subtree height nodes. */
2539    byte*     authPath;
2540    /* Hashes of nodes kept - subtree height / 2 nodes. */
2541    byte*     keep;
2542    /* Tree hash instances - subtree height minus K instances. */
2543    byte*     treeHash;
2544    /* Hashes of nodes for tree hash - one for each tree hash instance. */
2545    byte*     treeHashNode;
2546    /* Hashes of nodes to retain - based on K parameter. */
2547    byte*     retain;
2548    /* Next leaf to calculate - max 20 bits. */
2549    word32    next;
2550    /* Current offset into stack - 0..<subtree height>. */
2551    word8     offset;
2552} BdsState;
2553
2554/* Index to BDS state accounting for swapping.
2555 *
2556 * @param [in] idx  Index of node.
2557 * @param [in] i    Depth of tree.
2558 * @param [in] hs   Height of subtree.
2559 * @param [in] d    Depth/number of trees.
2560 * @return  Index of working BDS state.
2561 */
2562#define BDS_IDX(idx, i, hs, d)      \
2563    ((word8)(((((idx) >> ((hs) * ((i) + 1))) & 1) == 0) ? (i) : ((d) + (i))))
2564/* Index to alternate BDS state accounting for swapping.
2565 *
2566 * @param [in] idx  Index of node.
2567 * @param [in] i    Depth of tree.
2568 * @param [in] hs   Height of subtree.
2569 * @param [in] d    Depth/number of trees.
2570 * @return  Index of alternate BDS state.
2571 */
2572#define BDS_ALT_IDX(idx, i, hs, d)  \
2573    ((word8)(((((idx) >> ((hs) * ((i) + 1))) & 1) == 0) ? ((d) + (i)) : (i)))
2574
2575/********************************************
2576 * Tree Hash APIs
2577 ********************************************/
2578
2579/* Initialize the tree hash data at specified index for the BDS state.
2580 *
2581 * @param [in, out] bds  BDS state.
2582 * @param [in]      i    Index of tree hash.
2583 */
2584static void wc_xmss_bds_state_treehash_init(BdsState* bds, word32 i)
2585{
2586    byte* sk = bds->treeHash + i * 4U;
2587    c32to24(0, sk);
2588    sk[3] = 0 | (1U << 7);
2589}
2590
2591/* Set next index into tree hash data at specified index for the BDS state.
2592 *
2593 * @param [in, out] bds      BDS state.
2594 * @param [in]      i        Index of tree hash.
2595 * @param [in]      nextIdx  Next index for tree hash.
2596 */
2597static void wc_xmss_bds_state_treehash_set_next_idx(BdsState* bds, int i,
2598    word32 nextIdx)
2599{
2600    byte* sk = bds->treeHash + i * 4;
2601    c32to24(nextIdx, sk);
2602    sk[3] = 0 | (0 << 7);
2603}
2604
2605/* Mark tree hash, at specified index for the BDS state, as complete.
2606 *
2607 * @param [in, out] bds  BDS state.
2608 * @param [in]      i    Index of tree hash.
2609 */
2610static void wc_xmss_bds_state_treehash_complete(BdsState* bds, int i)
2611{
2612    byte* sk = bds->treeHash + i * 4;
2613    sk[3] |= 1 << 7; /* // NOLINT(clang-analyzer-core.NullDereference) */
2614}
2615
2616/* Get the tree hash data at specified index for the BDS state.
2617 *
2618 * @param [in]  bds       BDS state.
2619 * @param [in]  i         Index of tree hash.
2620 * @param [out] treeHash  Tree hash instance to fill out.
2621 */
2622static void wc_xmss_bds_state_treehash_get(BdsState* bds, int i,
2623    TreeHash* treeHash)
2624{
2625    byte* sk = bds->treeHash + i * 4;
2626    ato24(sk, &treeHash->nextIdx);
2627    treeHash->used = sk[3] & 0x7f;
2628    treeHash->completed = sk[3] >> 7;
2629}
2630
2631/* Set the tree hash data at specified index for the BDS state.
2632 *
2633 * @param [in, out]  bds       BDS state.
2634 * @param [in]       i         Index of tree hash.
2635 * @param [in]       treeHash  Tree hash data.
2636 */
2637static void wc_xmss_bds_state_treehash_set(BdsState* bds, int i,
2638    TreeHash* treeHash)
2639{
2640    byte* sk = bds->treeHash + i * 4;
2641    c32to24(treeHash->nextIdx, sk);
2642    sk[3] = (byte)(treeHash->used | (treeHash->completed << 7));
2643}
2644
2645/********************************************
2646 * BDS State APIs
2647 ********************************************/
2648
2649/* Allocate memory for BDS state.
2650 *
2651 * When using a static BDS state (XMSS) then pass in handle to data for bds.
2652 *
2653 * @param [in]      params    XMSS/MT parameters.
2654 * @param [in, out] bds       Handle to BDS state. May be NULL if not allocated.
2655 * @return  0 on success.
2656 * @return  MEMORY_E on dynamic memory allocation failure.
2657 */
2658static int wc_xmss_bds_state_alloc(const XmssParams* params, BdsState** bds,
2659    void* heap)
2660{
2661    const word8 cnt = (word8)(2 * params->d - 1);
2662    int ret = 0;
2663
2664    if (*bds == NULL) {
2665        /* Allocate memory for BDS states. */
2666        *bds = (BdsState*)XMALLOC(sizeof(BdsState) * cnt, heap,
2667            DYNAMIC_TYPE_TMP_BUFFER);
2668        if (*bds == NULL) {
2669            ret = MEMORY_E;
2670        }
2671        else {
2672            XMEMSET(*bds, 0, sizeof(BdsState) * cnt);
2673        }
2674    }
2675
2676    return ret;
2677}
2678
2679/* Dispose of allocated memory associated with BDS state.
2680 *
2681 * @param [in] bds    BDS state.
2682 * @param [in] heap   Dynamic memory hint.
2683 */
2684static void wc_xmss_bds_state_free(BdsState* bds, void* heap)
2685{
2686    /* BDS states was allocated - must free. */
2687    XFREE(bds, heap, DYNAMIC_TYPE_TMP_BUFFER);
2688}
2689
2690/* Load the BDS state from the secret/private key.
2691 *
2692 * @param [in]  state      XMSS/MT state including digest and parameters.
2693 * @param [in]  sk         Secret/private key.
2694 * @param [out] bds        BDS states.
2695 * @param [out] wots_sigs  WOTS signatures when XMSS^MT.
2696 */
2697static int wc_xmss_bds_state_load(const XmssState* state, byte* sk,
2698    BdsState* bds, byte** wots_sigs)
2699{
2700    const XmssParams* params = state->params;
2701    const word8 n = params->n;
2702    const word8 hs = params->sub_h;
2703    const word8 hsk = (word8)(params->sub_h - params->bds_k);
2704    const word8 k = params->bds_k;
2705    const word32 retainLen = XMSS_RETAIN_LEN(k, n);
2706    int i;
2707
2708    /* Skip past standard SK = idx || wots_sk || SK_PRF || root || SEED; */
2709    sk += params->idx_len + 4 * n;
2710
2711    if (2 * (int)params->d - 1 <= 0)
2712        return WC_FAILURE;
2713
2714    for (i = 0; i < 2 * (int)params->d - 1; i++) {
2715        /* Set pointers into SK. */
2716        bds[i].stack = sk;
2717        sk += (hs + 1) * n;
2718        bds[i].height = sk;
2719        sk += hs + 1;
2720        bds[i].authPath = sk;
2721        sk += hs * n;
2722        bds[i].keep = sk;
2723        sk += (hs >> 1) * n;
2724        bds[i].treeHash = sk;
2725        sk += hsk * 4;
2726        bds[i].treeHashNode = sk;
2727        sk += hsk * n;
2728        bds[i].retain = sk;
2729        sk += retainLen;
2730        /* Load values - big-endian encoded. */
2731        ato24(sk, &bds[i].next);
2732        sk += 3;
2733        bds[i].offset = sk[0];
2734        sk += 1;
2735    }
2736
2737    if (wots_sigs != NULL) {
2738        *wots_sigs = sk;
2739    }
2740
2741    return 0;
2742}
2743
2744/* Store the BDS state into the secret/private key.
2745 *
2746 * @param [in]      state   XMSS/MT state including digest and parameters.
2747 * @param [in, out] sk      Secret/private key.
2748 * @param [in]      bds     BDS states.
2749 */
2750static int wc_xmss_bds_state_store(const XmssState* state, byte* sk,
2751    BdsState* bds)
2752{
2753    int i;
2754    const XmssParams* params = state->params;
2755    const word8 n = params->n;
2756    const word8 hs = params->sub_h;
2757    const word8 hsk = (word8)(params->sub_h - params->bds_k);
2758    const word8 k = params->bds_k;
2759    const word32 skip = (word32)((hs + 1) * n +   /* BdsState.stack */
2760                        hs + 1 +                  /* BdsState.height */
2761                        hs * n +                  /* BdsState.authPath */
2762                        (hs >> 1) * n +           /* BdsState.keep */
2763                        hsk * 4 +                 /* BdsState.treeHash */
2764                        hsk * n) +                /* BdsState.treeHashNode */
2765                        XMSS_RETAIN_LEN(k, n);    /* BdsState.retain */
2766
2767    /* Ignore standard SK = idx || wots_sk || SK_PRF || root || SEED; */
2768    sk += params->idx_len + 4 * n;
2769
2770    if (2 * (int)params->d - 1 <= 0)
2771        return WC_FAILURE;
2772
2773    for (i = 0; i < 2 * (int)params->d - 1; i++) {
2774        /* Skip pointers into sk. */
2775        sk += skip;
2776        /* Save values - big-endian encoded. */
2777        c32to24(bds[i].next, sk); /* NOLINT(clang-analyzer-core.CallAndMessage) */
2778        sk += 3;
2779        sk[0] = bds[i].offset;
2780        sk += 1;
2781    }
2782
2783    return 0;
2784}
2785
2786/********************************************
2787 * BDS
2788 ********************************************/
2789
2790/* Compute node at next index.
2791 *
2792 * RFC 8391: 4.1.6, Algorithm 9: treeHash
2793 *       ...
2794 *       ADRS.setType(0);   # Type = OTS hash address
2795 *       ADRS.setOTSAddress(s + i);
2796 *       pk = WOTS_genPK (getWOTS_SK(SK, s + i), SEED, ADRS);
2797 *       ADRS.setType(1);   # Type = L-tree address
2798 *       ADRS.setLTreeAddress(s + i);
2799 *       node = ltree(pk, SEED, ADRS);
2800 *       ADRS.setType(2);   # Type = hash tree address
2801 *       ADRS.setTreeHeight(0);
2802 *       ADRS.setTreeIndex(i + s);
2803 *       while ( Top node on Stack has same height t' as node ) {
2804 *          ADRS.setTreeIndex((ADRS.getTreeIndex() - 1) / 2);
2805 *          node = RAND_HASH(Stack.pop(), node, SEED, ADRS);
2806 *          ADRS.setTreeHeight(ADRS.getTreeHeight() + 1);
2807 *       }
2808 *       Stack.push(node);
2809 *       ...
2810 *
2811 * @param [in]  state    XMSS/MT state including digest and parameters.
2812 * @param [in]  bds      BDS state.
2813 * @param [in]  sk_seed  Random secret/private seed.
2814 * @param [in]  pk_seed  Random public seed.
2815 * @param [in]  addr     Hash address.
2816 * @param [out] root     Root node.
2817 */
2818static void wc_xmss_bds_next_idx(XmssState* state, BdsState* bds,
2819    const byte* sk_seed, const byte* pk_seed, HashAddress addr, word32 i,
2820    word8* height, word8* offset, word8** sp)
2821{
2822    const XmssParams* params = state->params;
2823    const word8 hs = params->sub_h;
2824    const word8 hsk = (word8)(params->sub_h - params->bds_k);
2825    const word8 n = params->n;
2826    word8 o = *offset;
2827    word8* node = *sp;
2828    word8 h;
2829
2830    /* Calculate WOTS+ public key. */
2831    addr[XMSS_ADDR_TYPE] = WC_XMSS_ADDR_TYPE_OTS;
2832    addr[XMSS_ADDR_OTS] = (word32)i;
2833    wc_xmss_wots_gen_pk(state, sk_seed, pk_seed, addr, state->pk);
2834    /* Calculate public value. */
2835    addr[XMSS_ADDR_TYPE] = WC_XMSS_ADDR_TYPE_LTREE;
2836    wc_xmss_ltree(state, state->pk, pk_seed, addr, node);
2837    addr[XMSS_ADDR_TYPE] = WC_XMSS_ADDR_TYPE_TREE;
2838    addr[XMSS_ADDR_TREE_ZERO] = 0;
2839
2840    /* Initial height at this offset is 0. */
2841    h = height[o] = 0;
2842    /* HDSS, Section 4.5, 2: TREEHASH[h].push(v[h][3])
2843     * Copy right node to tree hash nodes if second right node. */
2844    if ((hsk > 0) && (i == 3)) {
2845        XMEMCPY(bds->treeHashNode, node + n, n);
2846    }
2847
2848    /* Top node on Stack has same height t' as node. */
2849    while ((o >= 1) && (h == height[o - 1])) {
2850        /* HDSS, Section 4.5, 1: AUTH[h] = v[h][1], h = 0,...,H-1.
2851         * Cache left node if on authentication path. */
2852        if ((i >> h) == 1) {
2853            if (bds->authPath == NULL) {
2854                state->ret = WC_FAILURE;
2855                return;
2856            }
2857            XMEMCPY(bds->authPath + h * n, node, n);
2858        }
2859        /* This is a right node. */
2860        else if (h < hsk) {
2861            /* HDSS, Section 4.5, 2: TREEHASH[h].push(v[h][3])
2862             * Copy right node to tree hash if second right node. */
2863            if ((i >> h) == 3) {
2864                XMEMCPY(bds->treeHashNode + h * n, node, n);
2865            }
2866        }
2867        else {
2868            /* HDSS, Section 4.5, 3: RETAIN[h].push(v[j][2j+3] for
2869             *   h = H-K,...,H-2 and j = 2^(H-h-1)-2,...,0.
2870             * Retain high right nodes.
2871             */
2872            word32 ro = (word32)(((word32)1U << (hs - 1 - h)) + h - hs +
2873                                 (((i >> h) - 3) >> 1));
2874            XMEMCPY(bds->retain + ro * n, node, n);
2875        }
2876
2877        node -= n;
2878        /* Calculate hash of node. */
2879        addr[XMSS_ADDR_TREE_HEIGHT] = h;
2880        addr[XMSS_ADDR_TREE_INDEX] = (word32)(i >> (h + 1));
2881        wc_xmss_rand_hash(state, node, pk_seed, addr, node);
2882
2883        /* Update offset and height. */
2884        o--;
2885        h = ++height[o];
2886    }
2887
2888    *offset = o;
2889    *sp = node;
2890}
2891
2892/* Compute initial Merkle tree and store nodes.
2893 *
2894 * HDSS, Section 4.5, The algorithm, Initialization.
2895 *   1. We store the authentication path for the first leaf (s = 0):
2896 *   AUTH[h] = v[h][1], h = 0,...,H-1.
2897 *   2. Depending on the parameter K, we store the next right authentication
2898 *   node for each height h = 0,...,H-K-1 in the treehash instances:
2899 *   TREEHASH[h].push(v[h][3]).
2900 *   3. Finally we store the right authentication nodes clode to the root using
2901 *   the stacks RETAIN[h]:
2902 *   RETAIN[h].push(v[j][2j+3] for h = H-K,...,H-2 and j = 2^(H-h-1)-2,...,0.
2903 *
2904 * RFC 8391: 4.1.6, Algorithm 9: treeHash
2905 *     if( s % (1 << t) != 0 ) return -1;
2906 *     for ( i = 0; i < 2^t; i++ ) {
2907 *       SEED = getSEED(SK);
2908 *       [Compute node at next index]
2909 *     }
2910 *     return Stack.pop();
2911 *
2912 * @param [in]  state    XMSS/MT state including digest and parameters.
2913 * @param [in]  bds      BDS state.
2914 * @param [in]  sk_seed  Random secret/private seed.
2915 * @param [in]  pk_seed  Random public seed.
2916 * @param [in]  addr     Hash address.
2917 * @param [out] root     Root node.
2918 */
2919static void wc_xmss_bds_treehash_initial(XmssState* state, BdsState* bds,
2920    const byte* sk_seed, const byte* pk_seed, const HashAddress addr,
2921    byte* root)
2922{
2923    const XmssParams* params = state->params;
2924    const word8 hsk = (word8)(params->sub_h - params->bds_k);
2925    const word8 n = params->n;
2926    word8* node = state->stack;
2927    HashAddress addrCopy;
2928    word8 height[WC_XMSS_MAX_TREE_HEIGHT + 1];
2929    word8 offset = 0;
2930    word32 maxIdx = (word32)1U << params->sub_h;
2931    word32 i;
2932
2933    /* First signing index will be 0 - setup BDS state. */
2934    bds->offset = 0;
2935    bds->next = 0;
2936    /* Reset the hash tree status. */
2937    if (bds->treeHash != NULL) {
2938        for (i = 0; i < hsk; i++) {
2939            wc_xmss_bds_state_treehash_init(bds, i);
2940        }
2941    }
2942
2943    /* Copy hash address into local. */
2944    XMSS_ADDR_OTS_SET_SUBTREE(addrCopy, addr);
2945
2946    /* Compute each node in tree. */
2947    for (i = 0; i < maxIdx; i++) {
2948        wc_xmss_bds_next_idx(state, bds, sk_seed, pk_seed, addrCopy, i, height,
2949            &offset, &node);
2950        offset++;
2951        node += n;
2952        /* Rest the hash address for reuse. */
2953        addrCopy[XMSS_ADDR_TREE_HEIGHT] = 0;
2954        addrCopy[XMSS_ADDR_TREE_INDEX] = 0;
2955    }
2956
2957    /* Copy the root node. */
2958    XMEMCPY(root, state->stack, n);
2959}
2960
2961/* Update internal nodes of Merkle tree at next index.
2962 *
2963 * RFC 8391: 4.1.6, Algorithm 9: treeHash
2964 *       ...
2965 *       SEED = getSEED(SK);
2966 *       ADRS.setType(0);   # Type = OTS hash address
2967 *       ADRS.setOTSAddress(s + i);
2968 *       pk = WOTS_genPK (getWOTS_SK(SK, s + i), SEED, ADRS);
2969 *       ADRS.setType(1);   # Type = L-tree address
2970 *       ADRS.setLTreeAddress(s + i);
2971 *       node = ltree(pk, SEED, ADRS);
2972 *       ADRS.setType(2);   # Type = hash tree address
2973 *       ADRS.setTreeHeight(0);
2974 *       ADRS.setTreeIndex(i + s);
2975 *       while ( Top node on Stack has same height t' as node ) {
2976 *          ADRS.setTreeIndex((ADRS.getTreeIndex() - 1) / 2);
2977 *          node = RAND_HASH(Stack.pop(), node, SEED, ADRS);
2978 *          ADRS.setTreeHeight(ADRS.getTreeHeight() + 1);
2979 *       }
2980 *       Stack.push(node);
2981 *
2982 * @param [in]      state    XMSS/MT state including digest and parameters.
2983 * @param [in, out] bds      BDS state.
2984 * @param [in]      height   Height of nodes to update.
2985 * @param [in]      sk_seed  Random secret/private seed.
2986 * @param [in]      pk_seed  Random public seed.
2987 * @param [in]      addr     Hash address.
2988 */
2989static void wc_xmss_bds_treehash_update(XmssState* state, BdsState* bds,
2990    word8 height, const byte* sk_seed, const byte* pk_seed,
2991    const HashAddress addr)
2992{
2993    const XmssParams* params = state->params;
2994    const word8 n = params->n;
2995    HashAddress addrLocal;
2996    TreeHash treeHash[1];
2997    byte* sp = bds->stack + bds->offset * n;
2998    byte* node = state->stack + WC_XMSS_MAX_STACK_LEN - n;
2999    word8 h;
3000
3001    /* Get the tree hash data. */
3002    wc_xmss_bds_state_treehash_get(bds, height, treeHash);
3003    /* Copy hash address into local as OTS type. */
3004    XMSS_ADDR_OTS_SET_SUBTREE(addrLocal, addr);
3005    /* Calculate WOTS+ public key. */
3006    addrLocal[XMSS_ADDR_OTS] = treeHash->nextIdx;
3007    wc_xmss_wots_gen_pk(state, sk_seed, pk_seed, addrLocal, state->pk);
3008    /* Calculate public value. */
3009    addrLocal[XMSS_ADDR_TYPE] = WC_XMSS_ADDR_TYPE_LTREE;
3010    wc_xmss_ltree(state, state->pk, pk_seed, addrLocal, node);
3011    addrLocal[XMSS_ADDR_TYPE] = WC_XMSS_ADDR_TYPE_TREE;
3012    addrLocal[XMSS_ADDR_TREE_ZERO] = 0;
3013
3014    /* Initial height is 0. */
3015    h = 0;
3016
3017    /* Top node on Stack has same height t' as node. */
3018    while ((treeHash->used > 0) && (h == bds->height[bds->offset - 1])) {
3019        sp -= n;
3020        /* Copy from stack to before last calculated node. */
3021        node -= n;
3022        XMEMCPY(node, sp, n);
3023
3024        /* Calculate hash of node. */
3025        addrLocal[XMSS_ADDR_TREE_HEIGHT] = h;
3026        addrLocal[XMSS_ADDR_TREE_INDEX] = treeHash->nextIdx >> (h + 1);
3027        wc_xmss_rand_hash(state, node, pk_seed, addrLocal, node);
3028
3029        /* Update used, offset and height. */
3030        treeHash->used--;
3031        bds->offset--;
3032        h++;
3033    }
3034
3035    /* Check whether we reached the height we wanted to update. */
3036    if (h == height) {
3037        /* Cache node. */
3038        XMEMCPY(bds->treeHashNode + height * n, node, n);
3039        treeHash->completed = 1;
3040    }
3041    else {
3042        /* Push calculated node onto stack. */
3043        XMEMCPY(sp, node, n);
3044        treeHash->used++;
3045        /* Update BDS state. */
3046        bds->height[bds->offset] = h;
3047        bds->offset++;
3048        treeHash->nextIdx++;
3049    }
3050
3051    /* Set the tree hash data back. */
3052    wc_xmss_bds_state_treehash_set(bds, height, treeHash);
3053}
3054
3055/* Updates hash trees that need it most.
3056 *
3057 * Algorithm 4.6: Authentication path computation, Step 5.
3058 *
3059 * @param [in]      state    XMSS/MT state including digest and parameters.
3060 * @param [in, out] bds      BDS state.
3061 * @param [in]      updates  Current number of updates.
3062 * @param [in]      sk_seed  Random secret/private seed.
3063 * @param [in]      pk_seed  Random public seed.
3064 * @param [in]      addr     Hash address.
3065 * @return  Number of available updates.
3066 */
3067static word8 wc_xmss_bds_treehash_updates(XmssState* state, BdsState* bds,
3068    word8 updates, const byte* sk_seed, const byte* pk_seed,
3069    const HashAddress addr)
3070{
3071    const XmssParams* params = state->params;
3072    const word8 hs = params->sub_h;
3073    const word8 hsk = (word8)(params->sub_h - params->bds_k);
3074
3075    if (bds->treeHash == NULL) {
3076        state->ret = WC_FAILURE;
3077        return 0;
3078    }
3079
3080    while (updates > 0) {
3081        word8 minH = hs;
3082        word8 h = hsk;
3083        word8 i;
3084
3085        /* Step 5.a. k <- min{ h: TREEHASH(h).height() =
3086                                  min[j=0..H-K-1]{TREEHASH(j.height()} } */
3087        for (i = 0; i < hsk; i++) {
3088            TreeHash treeHash[1];
3089
3090            wc_xmss_bds_state_treehash_get(bds, i, treeHash);
3091
3092            if (treeHash->completed) {
3093                /* Finished - ignore. */
3094            }
3095            else if (treeHash->used == 0) {
3096                /* None used, low height. */
3097                if (i < minH) {
3098                    h = i;
3099                    minH = i;
3100                }
3101            }
3102            /* Find the height of lowest in cache. */
3103            else {
3104                word8 j;
3105                word8 lowH = hs;
3106                byte* height = bds->height + bds->offset - treeHash->used;
3107
3108                for (j = 0; j < treeHash->used; j++) {
3109                    lowH = (word8)min(height[j], lowH);
3110                }
3111                if (lowH < minH) {
3112                    /* New lowest height. */
3113                    h = i;
3114                    minH = lowH;
3115                }
3116            }
3117        }
3118        /* If none lower, then stop. */
3119        if (h == hsk) {
3120            break;
3121        }
3122
3123        /* Step 5.b. TREEHASH(k).update() */
3124        /* Update tree to the lowest height. */
3125        wc_xmss_bds_treehash_update(state, bds, h, sk_seed, pk_seed, addr);
3126        updates--;
3127    }
3128    return updates;
3129}
3130
3131/* Update BDS at next leaf.
3132 *
3133 * Don't do anything if processed all leaves.
3134 *
3135 * @param [in]      state     XMSS/MT state including digest and parameters.
3136 * @param [in, out] bds       BDS state.
3137 * @param [in]      sk_seed   Random secret/private seed.
3138 * @param [in]      pk_seed   Random public seed.
3139 * @param [in]      addr      Hash address.
3140 */
3141static void wc_xmss_bds_update(XmssState* state, BdsState* bds,
3142    const byte* sk_seed, const byte* pk_seed, const HashAddress addr)
3143{
3144    if (bds->next < ((word32)1U << state->params->sub_h)) {
3145        const XmssParams* params = state->params;
3146        byte* sp = bds->stack + bds->offset * params->n;
3147        HashAddress addrCopy;
3148
3149        XMSS_ADDR_OTS_SET_SUBTREE(addrCopy, addr);
3150        if (bds->height == NULL) {
3151            state->ret = WC_FAILURE;
3152            return;
3153        }
3154        wc_xmss_bds_next_idx(state, bds, sk_seed, pk_seed, addrCopy, bds->next,
3155            bds->height, &bds->offset, &sp);
3156        bds->offset++;
3157        bds->next++;
3158    }
3159}
3160
3161/* Find index of lowest zero bit.
3162 *
3163 * Supports max up to 31.
3164 *
3165 * @param [in]  n    Number to evaluate.
3166 * @param [in]  max  Max number of bits.
3167 * @param [out] b    Next bit above first zero bit.
3168 * @return  Index of lowest bit that is zero.
3169 */
3170static word8 wc_xmss_lowest_zero_bit_index(word32 n, word8 max, word8* b)
3171{
3172    word8 i;
3173
3174    /* Check each bit from lowest for a zero bit. */
3175    for (i = 0; i < max; i++) {
3176        if ((n & 1) == 0) {
3177            break;
3178        }
3179        n >>= 1;
3180    }
3181
3182    /* Return next bit after 0 bit. */
3183    *b = (n >> 1) & 1;
3184    return i;
3185}
3186
3187/* Returns auth path for node leafIdx and computes for next leaf node.
3188 *
3189 * HDSS, Algorithm 4.6: Authentication path computation, Steps 1-4.
3190 *
3191 * @param [in]      state    XMSS/MT state including digest and parameters.
3192 * @param [in, out] bds      BDS state.
3193 * @param [in]      leafIdx  Current leaf index.
3194 * @param [in]      sk_seed  Random secret/private seed.
3195 * @param [in]      pk_seed  Random public seed.
3196 * @param [in]      addr     Hash address.
3197 */
3198static void wc_xmss_bds_auth_path(XmssState* state, BdsState* bds,
3199    const word32 leafIdx, const byte* sk_seed, const byte* pk_seed,
3200    HashAddress addr)
3201{
3202    const XmssParams* params = state->params;
3203    const word8 n = params->n;
3204    const word8 hs = params->sub_h;
3205    const word8 hsk = (word8)(params->sub_h - params->bds_k);
3206    word8 tau;
3207    byte* node = state->encMsg;
3208    word8 parent;
3209
3210    if ((bds->keep == NULL) || (bds->authPath == NULL)) {
3211        state->ret = WC_FAILURE;
3212        return;
3213    }
3214
3215    /* Step 1. Find the height of first left node in authentication path. */
3216    tau = wc_xmss_lowest_zero_bit_index(leafIdx, hs, &parent);
3217    if (tau == 0) {
3218        /* Step 2. Keep node if parent is a left node.
3219         *     if s/(2^tau+1) is even and tau < H-1 then KEEP[tau] <- AUTH[tau]
3220         */
3221        if (parent == 0) {
3222            XMEMCPY(bds->keep, bds->authPath, n);
3223        }
3224
3225        /* Step 3. if tau = 0 then AUTH[0] <- LEAFCALC(s) */
3226        /* Calculate WOTS+ public key. */
3227        addr[XMSS_ADDR_TYPE] = WC_XMSS_ADDR_TYPE_OTS;
3228        addr[XMSS_ADDR_OTS] = leafIdx;
3229        wc_xmss_wots_gen_pk(state, sk_seed, pk_seed, addr, state->pk);
3230        /* Calculate public value. */
3231        addr[XMSS_ADDR_TYPE] = WC_XMSS_ADDR_TYPE_LTREE;
3232        wc_xmss_ltree(state, state->pk, pk_seed, addr, bds->authPath);
3233    }
3234    else {
3235        byte* authPath;
3236        byte* nodes;
3237        word8 i;
3238
3239        authPath = bds->authPath + tau * n;
3240        /* Step 4.a. <node> = AUTH[tau-1] || KEEP[tau-1]
3241         * Only keeping half of nodes, so need to copy out before updating.
3242         */
3243        XMEMCPY(node, authPath - n, n);
3244        XMEMCPY(node + n, bds->keep + ((tau - 1) >> 1) * n, n);
3245
3246        /* Step 2. Keep node if parent is a left node.
3247         *     if s/(2^tau+1) is even and tau < H-1 then KEEP[tau] <- AUTH[tau]
3248         */
3249        if ((tau < hs - 1) && (parent == 0)) {
3250            XMEMCPY(bds->keep + (tau >> 1) * n, authPath, n);
3251        }
3252
3253        /* Step 4.a. AUTH[tau] <- g(<node>) */
3254        addr[XMSS_ADDR_TYPE] = WC_XMSS_ADDR_TYPE_TREE;
3255        addr[XMSS_ADDR_TREE_ZERO] = 0;
3256        addr[XMSS_ADDR_TREE_HEIGHT] = (word32)(tau - 1);
3257        addr[XMSS_ADDR_TREE_INDEX] = leafIdx >> tau;
3258        wc_xmss_rand_hash(state, node, pk_seed, addr, authPath);
3259
3260        /* Step 4.b. <Calculate new right nodes on lower heights> */
3261        authPath = bds->authPath;
3262        nodes = bds->treeHashNode;
3263        /*   for h = 0 to tau - 1 do */
3264        for (i = 0; i < tau; i++) {
3265            /*   if h < H - K then AUTH[h] <- TREEHASH[h].pop()*/
3266            if (i < hsk) {
3267                XMEMCPY(authPath, nodes, n);
3268                nodes += n;
3269            }
3270            /*   if h >= H - K then AUTH[h] <- RETAIN[h].pop()*/
3271            else {
3272                word32 o = (word32)(((word32)1U << (hs - 1 - i)) + i - hs +
3273                                    (((leafIdx >> i) - 1) >> 1));
3274                XMEMCPY(authPath, bds->retain + o * n, n);
3275            }
3276            authPath += n;
3277        }
3278
3279        /* Step 4.c. Initialize treehash instances for heights:
3280         *           0, ..., min{tau-1, H - K - 1} */
3281        tau = (word8)min(tau, hsk);
3282        for (i = 0; i < tau; i++) {
3283            word32 startIdx = leafIdx + 1U + 3U * ((word32)1U << i);
3284            if (startIdx < ((word32)1U << hs)) {
3285                wc_xmss_bds_state_treehash_set_next_idx(bds, i, startIdx);
3286            }
3287        }
3288    }
3289}
3290
3291/********************************************
3292 * XMSS
3293 ********************************************/
3294
3295/* Derives XMSS key pair from seeds.
3296 *
3297 * RFC 8391: 4.1.7, Algorithm 10: XMSS_keyGen.
3298 *     ...
3299 *     initialize SK_PRF with a uniformly random n-byte string;
3300 *     setSK_PRF(SK, SK_PRF);
3301 *
3302 *     # Initialization for common contents
3303 *     initialize SEED with a uniformly random n-byte string;
3304 *     setSEED(SK, SEED);
3305 *     setWOTS_SK(SK, wots_sk));
3306 *     ADRS = toByte(0, 32);
3307 *     root = treeHash(SK, 0, h, ADRS);
3308 *
3309 *     SK = idx || wots_sk || SK_PRF || root || SEED;
3310 *     PK = OID || root || SEED;
3311 *     return (SK || PK);
3312 *
3313 * HDSS, Section 4.5, The algorithm, Initialization.
3314 *
3315 * wots_sk, SK_PRF and SEED passed in as seed.
3316 * Store seed for wots_sk instead of generated wots_sk.
3317 * OID not stored in PK this is handled in upper layer.
3318 * BDS state is appended to SK:
3319 *     SK = idx || wots_sk || SK_PRF || root || SEED || BDS_STATE;
3320 *
3321 * @param [in]  state  XMSS/MT state including digest and parameters.
3322 * @param [in]  seed   Secret/Private and public seed.
3323 * @param [out] sk     Secret key.
3324 * @param [out] pk     Public key.
3325 * @return  0 on success.
3326 * @return  MEMORY_E on dynamic memory allocation failure.
3327 * @return  <0 on digest failure.
3328 */
3329int wc_xmss_keygen(XmssState* state, const unsigned char* seed,
3330    unsigned char* sk, unsigned char* pk)
3331{
3332#if WOLFSSL_XMSS_MIN_HEIGHT <= 32
3333    int ret = 0;
3334    const XmssParams* params = state->params;
3335    const word8 n = params->n;
3336    /* Offset of root node in public key. */
3337    byte* pk_root = pk;
3338    WC_DECLARE_VAR(bds, BdsState, 1, 0);
3339
3340#ifdef WOLFSSL_SMALL_STACK
3341    /* Allocate memory for tree hash instances and put in BDS state. */
3342    ret = wc_xmss_bds_state_alloc(params, &bds, state->heap);
3343    if (ret == 0)
3344#endif
3345    {
3346        /* Setup pointers into sk - assumes sk is initialized to zeros. */
3347        ret = wc_xmss_bds_state_load(state, sk, bds, NULL);
3348    }
3349    if (ret == 0) {
3350        /* Offsets into seed. */
3351        const byte* seed_priv = seed;
3352        const byte* seed_pub = seed + 2 * n;
3353        /* Offsets into secret/private key. */
3354        word32* sk_idx = (word32*)sk;
3355        byte* sk_seeds = sk + params->idx_len;
3356        /* Offsets into public key. */
3357        byte* pk_seed = pk + n;
3358
3359        /* Set first index to 0 in private key. idx_len always 4. */
3360        *sk_idx = 0;
3361        /* Set private key seed and private key for PRF in to private key. */
3362        XMEMCPY(sk_seeds, seed_priv, 2U * n);
3363        /* Set public key seed into public key. */
3364        XMEMCPY(pk_seed, seed_pub, n);
3365
3366        /* Set all address values to zero. */
3367        XMEMSET(state->addr, 0, sizeof(HashAddress));
3368        /* Hash address layer is 0. */
3369        /* Compute root node into public key. */
3370        wc_xmss_bds_treehash_initial(state, bds, sk_seeds, pk_seed,
3371            state->addr, pk_root);
3372        /* Return any errors that occurred during hashing. */
3373        ret = state->ret;
3374    }
3375    if (ret == 0) {
3376        /* Offset of root node in private key. */
3377        byte* sk_root = sk + params->idx_len + 2 * n;
3378
3379        /* Append public key (root node and public seed) to private key. */
3380        XMEMCPY(sk_root, pk_root, 2U * n);
3381
3382        /* Store BDS state back into secret/private key. */
3383        ret = wc_xmss_bds_state_store(state, sk, bds);
3384    }
3385
3386#ifdef WOLFSSL_SMALL_STACK
3387    /* Dispose of allocated data of BDS states. */
3388    wc_xmss_bds_state_free(bds, state->heap);
3389#endif
3390    return ret;
3391#else
3392    (void)state;
3393    (void)pk;
3394    (void)sk;
3395    (void)seed;
3396
3397    return NOT_COMPILED_IN;
3398#endif /* WOLFSSL_XMSS_MIN_HEIGHT <= 32 */
3399}
3400
3401/* Sign a message with XMSS.
3402 *
3403 * RFC 8391: 4.1.9, Algorithm 11: treeSig
3404 *     ...
3405 *     ADRS.setType(0);   # Type = OTS hash address
3406 *     ADRS.setOTSAddress(idx_sig);
3407 *     sig_ots = WOTS_sign(getWOTS_SK(SK, idx_sig),
3408 *                         M', getSEED(SK), ADRS);
3409 *     Sig = sig_ots || auth;
3410 *     return Sig;
3411 * RFC 8391: 4.1.9, Algorithm 12: XMSS_sign
3412 *     idx_sig = getIdx(SK);
3413 *     setIdx(SK, idx_sig + 1);
3414 *     ADRS = toByte(0, 32);
3415 *     byte[n] r = PRF(getSK_PRF(SK), toByte(idx_sig, 32));
3416 *     byte[n] M' = H_msg(r || getRoot(SK) || (toByte(idx_sig, n)), M);
3417 *     Sig = idx_sig || r || treeSig(M', SK, idx_sig, ADRS);
3418 *     return (SK || Sig);
3419 *
3420 * HDSS, Section 4.5, The algorithm, Update and output phase.
3421 *
3422 * 'auth' was built at key generation or after computing previous signature.
3423 * Build next authentication path after signature created.
3424 *
3425 * @param [in]      state   XMSS/MT state including digest and parameters.
3426 * @param [in]      m       Buffer holding message.
3427 * @param [in]      mlen    Length of message in buffer.
3428 * @param [in, out] sk      Secret/Private key.
3429 * @param [out]     sm      Signature and message data.
3430 * @param [in, out] smlen   On in, length of signature and message buffer.
3431 *                          On out, length of signature and message data.
3432 * @return  0 on success.
3433 * @return  <0 on digest failure.
3434 */
3435int wc_xmss_sign(XmssState* state, const unsigned char* m, word32 mlen,
3436    unsigned char* sk, unsigned char* sig)
3437{
3438#if WOLFSSL_XMSS_MIN_HEIGHT <= 32
3439    int ret = 0;
3440    const XmssParams* params = state->params;
3441    const word8 n = params->n;
3442    const word8 h = params->h;
3443    const word8 hk = (word8)(params->h - params->bds_k);
3444    const byte* sk_seed = sk + XMSS_IDX_LEN;
3445    const byte* pk_seed = sk + XMSS_IDX_LEN + 3 * n;
3446    byte node[WC_XMSS_MAX_N];
3447    word32 idx;
3448    byte* sig_r = sig + XMSS_IDX_LEN;
3449    WC_DECLARE_VAR(bds, BdsState, 1, 0);
3450
3451#ifdef WOLFSSL_SMALL_STACK
3452    /* Allocate memory for tree hash instances and put in BDS state. */
3453    ret = wc_xmss_bds_state_alloc(params, &bds, state->heap);
3454    if (ret == 0)
3455#endif
3456    {
3457        /* Load the BDS state from secret/private key. */
3458        ret = wc_xmss_bds_state_load(state, sk, bds, NULL);
3459    }
3460    if (ret == 0) {
3461        /* Copy the index into the signature data: Sig = idx_sig || ... */
3462        *((word32*)sig) = *((word32*)sk);
3463        /* Read index from the secret key. */
3464        ato32(sk, &idx);
3465
3466        /* Check index is valid. */
3467        if (IDX32_INVALID(idx, XMSS_IDX_LEN, h)) {
3468            /* Set index to maximum value to distinguish from valid value. */
3469            XMEMSET(sk, 0xFF, XMSS_IDX_LEN);
3470            /* Zeroize the secret key. */
3471            ForceZero(sk + XMSS_IDX_LEN, params->sk_len - XMSS_IDX_LEN);
3472            ret = KEY_EXHAUSTED_E;
3473        }
3474    }
3475
3476    /* Update SK_MT */
3477    if (ret == 0) {
3478        /* Increment the index in the secret key. */
3479        c32toa(idx + 1, sk);
3480    }
3481
3482    /* Message compression */
3483    if (ret == 0) {
3484        const byte* sk_prf = sk + XMSS_IDX_LEN + n;
3485
3486        /* byte[n] r = PRF(SK_PRF, toByte(idx_sig, 32)); */
3487        wc_idx_copy(sig, params->idx_len, state->buf, XMSS_PRF_M_LEN);
3488        wc_xmss_prf(state, sk_prf, state->buf, sig_r);
3489        ret = state->ret;
3490    }
3491    if (ret == 0) {
3492        const byte* pub_root = sk + XMSS_IDX_LEN + 2 * n;
3493
3494        /* Compute the message hash. */
3495        wc_xmss_hash_message(state, sig_r, pub_root, sig, XMSS_IDX_LEN, m, mlen,
3496            node);
3497        ret = state->ret;
3498        /* Place new signature data after index and 'r'. */
3499        sig += XMSS_IDX_LEN + n;
3500    }
3501
3502    if (ret == 0) {
3503        /* Set all address values to zero and set type to OTS. */
3504        XMEMSET(state->addr, 0, sizeof(HashAddress));
3505        state->addr[XMSS_ADDR_TYPE] = WC_XMSS_ADDR_TYPE_OTS;
3506        /* treeSig || treeHash = sig_ots || auth */
3507        state->addr[XMSS_ADDR_OTS] = idx;
3508        /*   Create WOTS+ signature for tree into signature (sig_ots). */
3509        wc_xmss_wots_sign(state, node, sk_seed, pk_seed, state->addr, sig);
3510        ret = state->ret;
3511    }
3512    if (ret == 0) {
3513        sig += params->wots_sig_len;
3514        /*   Add authentication path (auth) and calc new root. */
3515        XMEMCPY(sig, bds->authPath, (word32)h * n);
3516        ret = state->ret;
3517    }
3518
3519    if (ret == 0) {
3520        /* Update BDS state - update authentication path for next index. */
3521        /* Check not last node. */
3522        if (idx < ((word32)1U << h) - 1U) {
3523            /* Calculate next authentication path node. */
3524            wc_xmss_bds_auth_path(state, bds, idx, sk_seed, pk_seed,
3525                state->addr);
3526            ret = state->ret;
3527            if (ret == 0) {
3528                /* Algorithm 4.6: Step 5. */
3529                wc_xmss_bds_treehash_updates(state, bds, hk >> 1, sk_seed,
3530                    pk_seed, state->addr);
3531                ret = state->ret;
3532            }
3533        }
3534    }
3535    if (ret == 0) {
3536        /* Store BDS state back into secret/private key. */
3537        ret = wc_xmss_bds_state_store(state, sk, bds);
3538    }
3539
3540#ifdef WOLFSSL_SMALL_STACK
3541    /* Dispose of allocated data of BDS states. */
3542    wc_xmss_bds_state_free(bds, state->heap);
3543#endif
3544    return ret;
3545#else
3546    (void)state;
3547    (void)m;
3548    (void)mlen;
3549    (void)sk;
3550    (void)sig;
3551
3552    return NOT_COMPILED_IN;
3553#endif /* WOLFSSL_XMSS_MIN_HEIGHT <= 32 */
3554}
3555
3556/********************************************
3557 * XMSS^MT
3558 ********************************************/
3559
3560/* Generate a XMSS^MT key pair from seeds.
3561 *
3562 * RFC 8391: 4.2.2, Algorithm 15: XMSS^MT_keyGen.
3563 *     ...
3564 *     # Example initialization
3565 *     idx_MT = 0;
3566 *     setIdx(SK_MT, idx_MT);
3567 *     initialize SK_PRF with a uniformly random n-byte string;
3568 *     setSK_PRF(SK_MT, SK_PRF);
3569 *     initialize SEED with a uniformly random n-byte string;
3570 *     setSEED(SK_MT, SEED);
3571 *
3572 *     # Generate reduced XMSS private keys
3573 *     ADRS = toByte(0, 32);
3574 *     for ( layer = 0; layer < d; layer++ ) {
3575 *        ADRS.setLayerAddress(layer);
3576 *        for ( tree = 0; tree <
3577 *              (1 << ((d - 1 - layer) * (h / d)));
3578 *              tree++ ) {
3579 *           ADRS.setTreeAddress(tree);
3580 *           for ( i = 0; i < 2^(h / d); i++ ) {
3581 *             wots_sk[i] = WOTS_genSK();
3582 *           }
3583 *           setXMSS_SK(SK_MT, wots_sk, tree, layer);
3584 *        }
3585 *     }
3586 *
3587 *     SK = getXMSS_SK(SK_MT, 0, d - 1);
3588 *     setSEED(SK, SEED);
3589 *     root = treeHash(SK, 0, h / d, ADRS);
3590 *     setRoot(SK_MT, root);
3591 *
3592 *     PK_MT = OID || root || SEED;
3593 *     return (SK_MT || PK_MT);
3594 *
3595 * HDSS, Section 4.5, The algorithm, Initialization.
3596 * OPX, Section 2, Key Generation.
3597 *
3598 * wots_sk, SK_PRF and SEED passed in as seed.
3599 * Store seed for wots_sk instead of generated wots_sk.
3600 * OID not stored in PK this is handled in upper layer.
3601 * BDS state is appended to SK:
3602 *     SK = idx || wots_sk || SK_PRF || root || SEED || BDS_STATE;
3603 *
3604 * @param [in]  state   XMSS/MT state including digest and parameters.
3605 * @param [in]  seed    Secret/Private and public seed.
3606 * @param [out] sk      Secret key.
3607 * @param [out] pk      Public key.
3608 * @return  0 on success.
3609 * @return  MEMORY_E on dynamic memory allocation failure.
3610 * @return  <0 on digest failure.
3611 */
3612int wc_xmssmt_keygen(XmssState* state, const unsigned char* seed,
3613    unsigned char* sk, unsigned char* pk)
3614{
3615    int ret = 0;
3616    const XmssParams* params = state->params;
3617    const word8 n = params->n;
3618    unsigned char* sk_seed = sk + params->idx_len;
3619    unsigned char* pk_root = pk;
3620    unsigned char* pk_seed = pk + n;
3621    word8 i;
3622    byte* wots_sigs;
3623    BdsState* bds = NULL;
3624
3625    /* Allocate memory for BDS states and tree hash instances. */
3626    ret = wc_xmss_bds_state_alloc(params, &bds, state->heap);
3627    if (ret == 0) {
3628        /* Load the BDS state from secret/private key. */
3629        ret = wc_xmss_bds_state_load(state, sk, bds, &wots_sigs);
3630    }
3631    if (ret == 0) {
3632        /* Offsets into seed. */
3633        const byte* seed_priv = seed;
3634        const byte* seed_pub  = seed + 2 * params->n;
3635
3636        /* Set first index to 0 in private key. */
3637        XMEMSET(sk, 0, params->idx_len);
3638        /* Set private key seed and private key for PRF in to private key. */
3639        XMEMCPY(sk_seed, seed_priv, 2U * n);
3640        /* Set public key seed into public key. */
3641        XMEMCPY(pk_seed, seed_pub, n);
3642
3643        /* Set all address values to zero. */
3644        XMEMSET(state->addr, 0, sizeof(HashAddress));
3645        /* Hash address layer is 0 = bottom-most layer. */
3646    }
3647
3648    /* Setup state and compute WOTS+ signatures for all but top-most subtree. */
3649    for (i = 0; (ret == 0) && (i < params->d - 1); i++) {
3650        /* Compute root for subtree. */
3651        wc_xmss_bds_treehash_initial(state, bds + i, sk_seed, pk_seed,
3652            state->addr, pk_root);
3653        ret = state->ret;
3654        if (ret == 0) {
3655            /* Create signature for subtree for first index. */
3656            state->addr[XMSS_ADDR_LAYER] = (word32)(i + 1);
3657            wc_xmss_wots_sign(state, pk_root, sk_seed, pk_seed, state->addr,
3658                wots_sigs + i * params->wots_sig_len);
3659            ret = state->ret;
3660        }
3661    }
3662    if (ret == 0) {
3663        /* Compute root for top-most subtree. */
3664        wc_xmss_bds_treehash_initial(state, bds + i, sk_seed, pk_seed,
3665            state->addr, pk_root);
3666        /* Return any errors that occurred during hashing. */
3667        ret = state->ret;
3668    }
3669
3670    if (ret == 0) {
3671        /* Offset of root node in private key. */
3672        unsigned char* sk_root = sk_seed + 2 * n;
3673
3674        /* Append public key (root node and public seed) to private key. */
3675        XMEMCPY(sk_root, pk_root, 2U * n);
3676
3677        /* Store BDS state back into secret/private key. */
3678        ret = wc_xmss_bds_state_store(state, sk, bds);
3679    }
3680
3681    /* Dispose of allocated data of BDS states. */
3682    wc_xmss_bds_state_free(bds, state->heap);
3683    return ret;
3684}
3685
3686
3687#if !defined(WORD64_AVAILABLE) && (WOLFSSL_XMSS_MAX_HEIGHT > 32)
3688    #error "Support not available - use XMSS small code option"
3689#endif
3690
3691#if (WOLFSSL_XMSS_MAX_HEIGHT > 32)
3692    typedef word64 XmssIdx;
3693    #define IDX_MAX_BITS    64
3694#else
3695    typedef word32 XmssIdx;
3696    #define IDX_MAX_BITS    32
3697#endif
3698
3699/* Decode index into word.
3700 *
3701 * @param [out] idx  Index from encoding.
3702 * @param [in]  c    Count of bytes to decode to index.
3703 * @param [in]  a    Array to decode from.
3704 */
3705static void xmss_idx_decode(XmssIdx* idx, word8 c, const unsigned char* a)
3706{
3707    word8 i;
3708    XmssIdx n = 0;
3709
3710    for (i = 0; i < c; i++) {
3711        n <<= 8;
3712        n += a[i];
3713    }
3714
3715    *idx = n;
3716}
3717
3718/* Check whether index is valid.
3719 *
3720 * @param [in] i  Index to check.
3721 * @param [in] h  Full tree Height.
3722 */
3723static int xmss_idx_invalid(XmssIdx i, word8 h)
3724{
3725    return ((i + 1) >> h) != 0;
3726}
3727
3728/* Get tree and leaf index from index.
3729 *
3730 * @param [in]  i  Index to split.
3731 * @param [in]  h  Tree height.
3732 * @param [out] t  Tree index.
3733 * @param [out] l  Leaf index.
3734 */
3735static void xmss_idx_get_tree_leaf(XmssIdx i, word8 h, XmssIdx* t, word32* l)
3736{
3737    *l = (word32)i & (((word32)1U << h) - 1U);
3738    *t = i >> h;
3739}
3740
3741/* Set the index into address as the tree index.
3742 *
3743 * @param [in]      i  Tree index.
3744 * @param [in, out] a  Hash address.
3745 */
3746static void xmss_idx_set_addr_tree(XmssIdx i, HashAddress a)
3747{
3748#if IDX_MAX_BITS == 32
3749    a[XMSS_ADDR_TREE_HI] = 0;
3750    a[XMSS_ADDR_TREE]    = i;
3751#else
3752    a[XMSS_ADDR_TREE_HI] = (word32)(i >> 32);
3753    a[XMSS_ADDR_TREE]    = (word32)(i      );
3754#endif
3755}
3756
3757/* Sign message with XMSS^MT.
3758 *
3759 * RFC 8391: 4.1.9, Algorithm 11: treeSig
3760 *     ...
3761 *     ADRS.setType(0);   # Type = OTS hash address
3762 *     ADRS.setOTSAddress(idx_sig);
3763 *     sig_ots = WOTS_sign(getWOTS_SK(SK, idx_sig),
3764 *                         M', getSEED(SK), ADRS);
3765 *     Sig = sig_ots || auth;
3766 *     return Sig;
3767 * RFC 8391: 4.2.4, Algorithm 16: XMSS^MT_sign.
3768 *      ...
3769 *      # Init
3770 *     ADRS = toByte(0, 32);
3771 *     SEED = getSEED(SK_MT);
3772 *     SK_PRF = getSK_PRF(SK_MT);
3773 *     idx_sig = getIdx(SK_MT);
3774 *
3775 *     # Update SK_MT
3776 *     setIdx(SK_MT, idx_sig + 1);
3777 *
3778 *     # Message compression
3779 *     byte[n] r = PRF(SK_PRF, toByte(idx_sig, 32));
3780 *     byte[n] M' = H_msg(r || getRoot(SK_MT) || (toByte(idx_sig, n)), M);
3781 *
3782 *     # Sign
3783 *     Sig_MT = idx_sig;
3784 *     unsigned int idx_tree
3785 *                   = (h - h / d) most significant bits of idx_sig;
3786 *     unsigned int idx_leaf = (h / d) least significant bits of idx_sig;
3787 *     SK = idx_leaf || getXMSS_SK(SK_MT, idx_tree, 0) || SK_PRF
3788 *           || toByte(0, n) || SEED;
3789 *     ADRS.setLayerAddress(0);
3790 *     ADRS.setTreeAddress(idx_tree);
3791 *     Sig_tmp = treeSig(M', SK, idx_leaf, ADRS);
3792 *     Sig_MT = Sig_MT || r || Sig_tmp;
3793 *     for ( j = 1; j < d; j++ ) {
3794 *        root = treeHash(SK, 0, h / d, ADRS);
3795 *        idx_leaf = (h / d) least significant bits of idx_tree;
3796 *        idx_tree = (h - j * (h / d)) most significant bits of idx_tree;
3797 *        SK = idx_leaf || getXMSS_SK(SK_MT, idx_tree, j) || SK_PRF
3798 *               || toByte(0, n) || SEED;
3799 *        ADRS.setLayerAddress(j);
3800 *        ADRS.setTreeAddress(idx_tree);
3801 *        Sig_tmp = treeSig(root, SK, idx_leaf, ADRS);
3802 *        Sig_MT = Sig_MT || Sig_tmp;
3803 *     }
3804 *     return SK_MT || Sig_MT;
3805 *
3806 * 'auth' was built at key generation or after computing previous signature.
3807 *
3808 * @param [in]      state      XMSS/MT state including digest and parameters.
3809 * @param [in, out] bds        BDS state.
3810 * @param [in]      idx        Index to sign with.
3811 * @param [in]      wots_sigs  Pre-computed WOTS+ signatures.
3812 * @param [in]      m          Buffer holding message.
3813 * @param [in]      mlen       Length of message in buffer.
3814 * @param [in, out] sk         Secret/Private key.
3815 * @param [out]     sig        Signature and message data.
3816 * @return  0 on success.
3817 * @return  <0 on digest failure.
3818 */
3819static int wc_xmssmt_sign_msg(XmssState* state, BdsState* bds, XmssIdx idx,
3820    byte* wots_sigs, const unsigned char* m, word32 mlen, unsigned char* sk,
3821    unsigned char* sig)
3822{
3823    int ret;
3824    const XmssParams* params = state->params;
3825    const word8 n = params->n;
3826    const word8 hs = params->sub_h;
3827    const word8 idx_len = params->idx_len;
3828    const byte* sk_prf = sk + idx_len + n;
3829    byte* sig_mt = sig;
3830    byte* sig_r = sig + idx_len;
3831    byte node[WC_XMSS_MAX_N];
3832
3833    /* Message compression */
3834    /* byte[n] r = PRF(SK_PRF, toByte(idx_sig, 32)); */
3835    wc_idx_copy(sig_mt, idx_len, state->buf, XMSS_PRF_M_LEN);
3836    wc_xmss_prf(state, sk_prf, state->buf, sig_r);
3837    ret = state->ret;
3838    if (ret == 0) {
3839        const byte* pub_root = sk + idx_len + 2 * n;
3840        /* byte[n] M' = H_msg(r || getRoot(SK_MT) || (toByte(idx_sig, n)), M);
3841         */
3842        wc_xmss_hash_message(state, sig_r, pub_root, sig, idx_len, m, mlen,
3843            node);
3844        ret = state->ret;
3845        /* Place new signature data after index and 'r'. */
3846        sig += idx_len + n;
3847    }
3848
3849    /* Sign */
3850    if (ret == 0) {
3851        const byte* sk_seed = sk + idx_len;
3852        const byte* pk_seed = sk + idx_len + 3 * n;
3853        XmssIdx idx_tree;
3854        word32 idx_leaf;
3855
3856        /* Set all address values to zero and set type to OTS. */
3857        XMEMSET(state->addr, 0, sizeof(HashAddress));
3858        state->addr[XMSS_ADDR_TYPE] = WC_XMSS_ADDR_TYPE_OTS;
3859
3860        /* Fist iteration - calculate signature. */
3861        /* Set layer, tree and OTS leaf index into hash address. */
3862        state->addr[XMSS_ADDR_LAYER] = 0;
3863        xmss_idx_get_tree_leaf(idx, hs, &idx_tree, &idx_leaf);
3864        xmss_idx_set_addr_tree(idx_tree, state->addr);
3865        /* treeSig || treeHash = sig_ots || auth */
3866        state->addr[XMSS_ADDR_OTS] = idx_leaf;
3867        /*   Create WOTS+ signature for tree into signature (sig_ots). */
3868        wc_xmss_wots_sign(state, node, sk_seed, pk_seed, state->addr, sig);
3869        ret = state->ret;
3870    }
3871    if (ret == 0) {
3872        word8 i;
3873        byte *authPath;
3874
3875        sig += params->wots_sig_len;
3876        /*   Add authentication path. */
3877        authPath = bds[BDS_IDX(idx, 0, hs, params->d)].authPath;
3878        if (authPath == NULL) {
3879            state->ret = WC_FAILURE;
3880            return state->ret;
3881        }
3882        XMEMCPY(sig, authPath, (word32)hs * n);
3883        sig += hs * n;
3884
3885        /* Remaining iterations from storage. */
3886        for (i = 1; i < params->d; i++) {
3887            /* Copy out precomputed signature into signature (sig_ots). */
3888            XMEMCPY(sig, wots_sigs + (i - 1) * params->wots_sig_len,
3889                params->wots_sig_len);
3890            sig += params->wots_sig_len;
3891            /* Add authentication path (auth) and calc new root. */
3892            authPath = bds[BDS_IDX(idx, i, hs, params->d)].authPath;
3893            if (authPath == NULL) {
3894                state->ret = WC_FAILURE;
3895                return state->ret;
3896            }
3897            XMEMCPY(sig, authPath, (word32)hs * n);
3898            sig += hs * n;
3899        }
3900        ret = state->ret;
3901    }
3902
3903    return ret;
3904}
3905
3906/* Compute BDS state for signing next index.
3907 *
3908 * HDSS, Section 4.5, The algorithm, Update and output phase.
3909 * OPX, Section 2, Signature Generation. Para 2 and 3.
3910 *
3911 * @param [in]      state      XMSS/MT state including digest and parameters.
3912 * @param [in, out] bds        BDS state.
3913 * @param [in]      idx        Index to sign with.
3914 * @param [in]      wots_sigs  Pre-computed WOTS+ signatures.
3915 * @param [in]      m          Buffer holding message.
3916 * @param [in]      mlen       Length of message in buffer.
3917 * @param [in, out] sk         Secret/Private key.
3918 * @param [out]     sig        Signature and message data.
3919 * @return  0 on success.
3920 * @return  <0 on digest failure.
3921 */
3922static int wc_xmssmt_sign_next_idx(XmssState* state, BdsState* bds, XmssIdx idx,
3923    byte* wots_sigs, unsigned char* sk)
3924{
3925    int ret = 0;
3926    const XmssParams* params = state->params;
3927    const word8 n = params->n;
3928    const word8 h = params->h;
3929    const word8 hs = params->sub_h;
3930    const word8 hsk = (word8)(params->sub_h - params->bds_k);
3931    const byte* sk_seed = sk + params->idx_len;
3932    const byte* pk_seed = sk + params->idx_len + 3 * n;
3933    XmssIdx idx_tree;
3934    int computeAuthPath = 1;
3935    unsigned int updates;
3936    word8 i;
3937
3938    /* Update BDS state - update authentication path for next index. */
3939    /* HDSS, Algorithm 4.6, Step 5: repeat (H - K) / 2 times. */
3940    updates = hsk >> 1;
3941
3942    idx_tree = (idx >> hs) + 1;
3943    /* Check whether last tree. */
3944    if (idx_tree < ((XmssIdx)1 << (h - hs))) {
3945        /* Set hash address to next tree. */
3946        state->addr[XMSS_ADDR_LAYER] = 0;
3947        xmss_idx_set_addr_tree(idx_tree, state->addr);
3948        /* Update BDS state. */
3949        wc_xmss_bds_update(state, &bds[BDS_ALT_IDX(idx, 0, hs, params->d)],
3950            sk_seed, pk_seed, state->addr);
3951        ret = state->ret;
3952    }
3953
3954    for (i = 0; (ret == 0) && (i < params->d); i++) {
3955        word32 idx_leaf;
3956        word8 bds_i = BDS_IDX(idx, i, hs, params->d);
3957        word8 alt_i = BDS_ALT_IDX(idx, i, hs, params->d);
3958
3959        /* Check not last at height. */
3960        if (((idx + 1) << (IDX_MAX_BITS - ((i + 1) * hs))) != 0) {
3961            state->addr[XMSS_ADDR_LAYER] = i;
3962            xmss_idx_get_tree_leaf(idx >> (hs * i), hs, &idx_tree, &idx_leaf);
3963            xmss_idx_set_addr_tree(idx_tree, state->addr);
3964            idx_tree++;
3965
3966            if (computeAuthPath) {
3967                /* Compute authentication path for tree. */
3968                wc_xmss_bds_auth_path(state, &bds[bds_i], idx_leaf, sk_seed,
3969                    pk_seed, state->addr);
3970                ret = state->ret;
3971                computeAuthPath = 0;
3972            }
3973
3974            if (ret == 0) {
3975                /* HDSS, Algorithm 4.6: Step 5. */
3976                updates = wc_xmss_bds_treehash_updates(state, &bds[bds_i],
3977                    (word8)updates, sk_seed, pk_seed, state->addr);
3978                ret = state->ret;
3979            }
3980
3981            /* Check tree not first, updates to do, tree not last at height and
3982             * next leaf in alt state is not last. */
3983            if ((ret == 0) && (i > 0) && (updates > 0) &&
3984                    (idx_tree < ((XmssIdx)1 << (h - (hs * (i + 1))))) &&
3985                    (bds[alt_i].next < ((XmssIdx)1 << h))) {
3986                xmss_idx_set_addr_tree(idx_tree, state->addr);
3987                /* Update alternative BDS state. */
3988                wc_xmss_bds_update(state, &bds[alt_i], sk_seed, pk_seed,
3989                    state->addr);
3990                ret = state->ret;
3991                updates--;
3992            }
3993        }
3994        /* Last at height. */
3995        else {
3996            /* Set layer, tree and OTS leaf index into hash address. */
3997            state->addr[XMSS_ADDR_LAYER] = (word32)(i + 1);
3998            idx_tree = (idx + 1) >> ((i + 1) * hs);
3999            xmss_idx_get_tree_leaf(idx_tree, hs, &idx_tree, &idx_leaf);
4000            xmss_idx_set_addr_tree(idx_tree, state->addr);
4001            /* Cache WOTS+ signature for new tree. */
4002            state->addr[XMSS_ADDR_OTS] = idx_leaf;
4003            wc_xmss_wots_sign(state, bds[alt_i].stack, sk_seed, pk_seed,
4004                state->addr, wots_sigs + i * params->wots_sig_len);
4005            ret = state->ret;
4006
4007            if (ret == 0) {
4008                word8 d;
4009
4010                /* Reset old BDS state. */
4011                bds[bds_i].offset = 0;
4012                bds[bds_i].next = 0;
4013
4014                /* Done an update. */
4015                updates--;
4016                /* Need to compute authentication path in next tree up. */
4017                computeAuthPath = 1;
4018                /* Mark the tree hashes as complete in new BDS state. */
4019                for (d = 0; d < hsk; d++) {
4020                    wc_xmss_bds_state_treehash_complete(&bds[alt_i], d);
4021                }
4022            }
4023        }
4024    }
4025
4026    return ret;
4027}
4028
4029/* Sign a message with XMSS^MT and update BDS state for signing next index.
4030 *
4031 * RFC 8391: 4.2.4, Algorithm 16: XMSS^MT_sign.
4032 * HDSS, Section 4.5, The algorithm, Update and output phase.
4033 *
4034 * @param [in]      state   XMSS/MT state including digest and parameters.
4035 * @param [in]      m       Buffer holding message.
4036 * @param [in]      mlen    Length of message in buffer.
4037 * @param [in, out] sk      Secret/Private key.
4038 * @param [out]     sig     Signature and message data.
4039 * @return  0 on success.
4040 * @return  MEMORY_E on dynamic memory allocation failure.
4041 * @return  <0 on digest failure.
4042 */
4043int wc_xmssmt_sign(XmssState* state, const unsigned char* m, word32 mlen,
4044    unsigned char* sk, unsigned char* sig)
4045{
4046    int ret = 0;
4047    const XmssParams* params = state->params;
4048    const word8 h = params->h;
4049    const word8 idx_len = params->idx_len;
4050    XmssIdx idx = 0;
4051    byte* sig_mt = sig;
4052    byte* wots_sigs;
4053    BdsState* bds = NULL;
4054
4055    /* Allocate memory for BDS states and tree hash instances. */
4056    ret = wc_xmss_bds_state_alloc(params, &bds, state->heap);
4057    if (ret == 0) {
4058        /* Load the BDS state from secret/private key. */
4059        ret = wc_xmss_bds_state_load(state, sk, bds, &wots_sigs);
4060    }
4061    if (ret == 0) {
4062        /* Copy the index into the signature data: Sig_MT = idx_sig. */
4063        XMEMCPY(sig_mt, sk, idx_len);
4064
4065        /* Read index from the secret key. */
4066        xmss_idx_decode(&idx, idx_len, sk);
4067    }
4068    if ((ret == 0) && xmss_idx_invalid(idx, h)) {
4069        /* Set index to maximum value to distinguish from valid value. */
4070        XMEMSET(sk, 0xFF, idx_len);
4071        /* Zeroize the secret key. */
4072        ForceZero(sk + idx_len, params->sk_len - idx_len);
4073        ret = KEY_EXHAUSTED_E;
4074    }
4075
4076    if (ret == 0) {
4077        /* Increment the index in the secret key. */
4078        wc_idx_update(sk, idx_len);
4079
4080        /* Compute signature. */
4081        ret = wc_xmssmt_sign_msg(state, bds, idx, wots_sigs, m, mlen, sk, sig);
4082    }
4083
4084    /* Only update if not last index. */
4085    if ((ret == 0) && (idx < (((XmssIdx)1 << h) - 1))) {
4086        /* Update BDS state for signing next index. */
4087        ret = wc_xmssmt_sign_next_idx(state, bds, idx, wots_sigs, sk);
4088    }
4089
4090    if (ret == 0) {
4091        /* Store BDS state back into secret/private key. */
4092        ret = wc_xmss_bds_state_store(state, sk, bds);
4093    }
4094
4095    /* Dispose of allocated data of BDS states. */
4096    wc_xmss_bds_state_free(bds, state->heap);
4097    return ret;
4098}
4099
4100#endif /* WOLFSSL_WC_XMSS_SMALL */
4101
4102/* Check if more signatures are possible with secret/private key.
4103 *
4104 * @param [in] params  XMSS parameters
4105 * @param [in] sk      Secret/private key.
4106 * @return  1 when signatures possible.
4107 * @return  0 when key exhausted.
4108 */
4109
4110int wc_xmss_sigsleft(const XmssParams* params, unsigned char* sk)
4111{
4112    int ret = 0;
4113    wc_Idx idx;
4114
4115    WC_IDX_ZERO(idx);
4116    /* Read index from the secret key. */
4117    WC_IDX_DECODE(idx, params->idx_len, sk, ret);
4118    /* Check validity of index. */
4119    if ((ret == 0) && (WC_IDX_INVALID(idx, params->idx_len, params->h))) {
4120        ret = KEY_EXHAUSTED_E;
4121    }
4122
4123    return ret == 0;
4124}
4125#endif /* !WOLFSSL_XMSS_VERIFY_ONLY */
4126
4127/********************************************
4128 * SIGN OPEN - Verify
4129 ********************************************/
4130
4131#if !defined(WOLFSSL_WC_XMSS_SMALL) || defined(WOLFSSL_XMSS_VERIFY_ONLY)
4132/* Compute root node with leaf and authentication path.
4133 *
4134 * RFC 8391: 4.1.10, Algorithm 13: XMSS_rootFromSig
4135 *     ...
4136 *     for ( k = 0; k < h; k++ ) {
4137 *       ADRS.setTreeHeight(k);
4138 *       if ( (floor(idx_sig / (2^k)) % 2) == 0 ) {
4139 *         ADRS.setTreeIndex(ADRS.getTreeIndex() / 2);
4140 *         node[1] = RAND_HASH(node[0], auth[k], SEED, ADRS);
4141 *       } else {
4142 *         ADRS.setTreeIndex((ADRS.getTreeIndex() - 1) / 2);
4143 *         node[1] = RAND_HASH(auth[k], node[0], SEED, ADRS);
4144 *       }
4145 *       node[0] = node[1];
4146 *     }
4147 *     return node[0];
4148 *
4149 * @param [in]      state      XMSS/MT state including digest and parameters.
4150 * @param [in]      idx_leaf   Index of leaf node.
4151 * @param [in]      auth_path  Authentication path.
4152 * @param [in]      pk_seed    Random public seed.
4153 * @param [in]      addr       Hash address.
4154 * @param [in, out] root       On in, leaf node. On out, root node.
4155 */
4156static void wc_xmss_compute_root(XmssState* state, word32 idx_leaf,
4157    const byte* auth_path, const byte* pk_seed, HashAddress addr, byte* root)
4158{
4159    const XmssParams* params = state->params;
4160    const word8 n = params->n;
4161    const byte* b[2][2] = { { root, auth_path }, { auth_path, root } };
4162    word8 i;
4163
4164    for (i = 0; i < params->sub_h; i++) {
4165        /* Get which side the leaf is on. */
4166        word8 s = idx_leaf & 1;
4167        /* Set tree height and index. */
4168        addr[XMSS_ADDR_TREE_HEIGHT] = i;
4169        idx_leaf >>= 1;
4170        addr[XMSS_ADDR_TREE_INDEX] = idx_leaf;
4171
4172        /* Put the result into buffer position for next RAND_HASH. */
4173        wc_xmss_rand_hash_lr(state, b[s][0], b[s][1], pk_seed, addr, root);
4174        /* Move to next auth path node. */
4175        b[0][1] += n;
4176        b[1][0] += n;
4177    }
4178}
4179#else
4180/* Compute root node with leaf and authentication path.
4181 *
4182 * RFC 8391: 4.1.10, Algorithm 13: XMSS_rootFromSig
4183 *     ...
4184 *     for ( k = 0; k < h; k++ ) {
4185 *       ADRS.setTreeHeight(k);
4186 *       if ( (floor(idx_sig / (2^k)) % 2) == 0 ) {
4187 *         ADRS.setTreeIndex(ADRS.getTreeIndex() / 2);
4188 *         node[1] = RAND_HASH(node[0], auth[k], SEED, ADRS);
4189 *       } else {
4190 *         ADRS.setTreeIndex((ADRS.getTreeIndex() - 1) / 2);
4191 *         node[1] = RAND_HASH(auth[k], node[0], SEED, ADRS);
4192 *       }
4193 *       node[0] = node[1];
4194 *     }
4195 *     return node[0];
4196 *
4197 * @param [in]      state      XMSS/MT state including digest and parameters.
4198 * @param [in]      idx_leaf   Index of leaf node.
4199 * @param [in]      auth_path  Authentication path.
4200 * @param [in]      pk_seed    Random public seed.
4201 * @param [in]      addr       Hash address.
4202 * @param [in, out] node       On in, leaf node. On out, root node.
4203 */
4204static void wc_xmss_compute_root(XmssState* state, word32 idx_leaf,
4205    const byte* auth_path, const byte* pk_seed, HashAddress addr, byte* node)
4206{
4207    const XmssParams* params = state->params;
4208    const word8 n = params->n;
4209    byte buffer[2 * WC_XMSS_MAX_N];
4210    byte* b[2][2] = { { buffer, buffer + n }, { buffer + n, buffer } };
4211    word8 i;
4212
4213    /* Setup buffer for first RAND_HASH. */
4214    XMEMCPY(b[idx_leaf & 1][0], node, n);
4215    XMEMCPY(b[idx_leaf & 1][1], auth_path, n);
4216    auth_path += n;
4217
4218    for (i = 0; i < params->sub_h - 1; i++) {
4219        /* Set tree height and index. */
4220        addr[XMSS_ADDR_TREE_HEIGHT] = i;
4221        idx_leaf >>= 1;
4222        addr[XMSS_ADDR_TREE_INDEX] = idx_leaf;
4223
4224        /* Put the result into buffer position for next RAND_HASH. */
4225        wc_xmss_rand_hash(state, buffer, pk_seed, addr, b[idx_leaf & 1][0]);
4226        /* Put auth path node into other half of buffer. */
4227        XMEMCPY(b[idx_leaf & 1][1], auth_path, n);
4228        /* Move to next auth path node. */
4229        auth_path += n;
4230    }
4231
4232    addr[XMSS_ADDR_TREE_HEIGHT] = i;
4233    idx_leaf >>= 1;
4234    addr[XMSS_ADDR_TREE_INDEX] = idx_leaf;
4235    /* Last iteration into output node. */
4236    wc_xmss_rand_hash(state, buffer, pk_seed, addr, node);
4237}
4238#endif /* !WOLFSSL_WC_XMSS_SMALL || WOLFSSL_XMSS_VERIFY_ONLY */
4239
4240/* Compute a root node from a tree signature.
4241 *
4242 * RFC 8391: 4.1.10, Algorithm 13: XMSS_rootFromSig
4243 *     ADRS.setType(0);   # Type = OTS hash address
4244 *     ADRS.setOTSAddress(idx_sig);
4245 *     pk_ots = WOTS_pkFromSig(sig_ots, M', SEED, ADRS);
4246 *     ADRS.setType(1);   # Type = L-tree address
4247 *     ADRS.setLTreeAddress(idx_sig);
4248 *     byte[n][2] node;
4249 *     node[0] = ltree(pk_ots, SEED, ADRS);
4250 *     ADRS.setType(2);   # Type = hash tree address
4251 *     ADRS.setTreeIndex(idx_sig);
4252 *     [Compute root with leaf and authentication path]
4253 *
4254 * Computing the root from the leaf and authentication path can be implemented
4255 * in different ways and is therefore extracted to its own function.
4256 *
4257 * @param [in]      state    XMSS/MT state including digest and parameters.
4258 * @param [in]      pk_seed  Random public seed.
4259 * @param [in]      sig      WOTS+ signature for this tree.
4260 * @param [in]      idx_sig  Index of signature leaf in this tree.
4261 * @param [in, out] addr     Hash address.
4262 * @param [in, out] node     On in, previous root node.
4263 *                           On out, root node of this subtree.
4264 */
4265static void wc_xmss_root_from_sig(XmssState* state, const byte* pk_seed,
4266    const byte* sig, word32 idx_sig, HashAddress addr, byte* node)
4267{
4268    const XmssParams* params = state->params;
4269    byte* wots_pk = state->pk;
4270    const byte* auth_path = sig + params->wots_sig_len;
4271
4272    /* Compute WOTS+ public key value from signature. */
4273    addr[XMSS_ADDR_TYPE] = WC_XMSS_ADDR_TYPE_OTS;
4274    addr[XMSS_ADDR_OTS] = idx_sig;
4275    wc_xmss_wots_pk_from_sig(state, sig, node, pk_seed, addr, wots_pk);
4276
4277    /* Compute leaves of L-tree from WOTS+ public key. */
4278    addr[XMSS_ADDR_TYPE] = WC_XMSS_ADDR_TYPE_LTREE;
4279    /* XMSS_ADDR_LTREE is same as XMSS_ADDR_OTS in index and value. */
4280    wc_xmss_ltree(state, wots_pk, pk_seed, addr, node);
4281
4282    /* Compute root node from leaf and authentication path. */
4283    addr[XMSS_ADDR_TYPE] = WC_XMSS_ADDR_TYPE_TREE;
4284    addr[XMSS_ADDR_TREE_ZERO] = 0;
4285    wc_xmss_compute_root(state, idx_sig, auth_path, pk_seed, addr, node);
4286}
4287
4288/* Verify message with signature using XMSS/MT.
4289 *
4290 * RFC 8391: 4.2.5, Algorithm 17: XMSSMT_verify
4291 *     idx_sig = getIdx(Sig_MT);
4292 *     SEED = getSEED(PK_MT);
4293 *     ADRS = toByte(0, 32);
4294 *
4295 *     byte[n] M' = H_msg(getR(Sig_MT) || getRoot(PK_MT)
4296 *                        || (toByte(idx_sig, n)), M);
4297 *
4298 *     unsigned int idx_leaf
4299 *                   = (h / d) least significant bits of idx_sig;
4300 *     unsigned int idx_tree
4301 *                   = (h - h / d) most significant bits of idx_sig;
4302 *     Sig' = getXMSSSignature(Sig_MT, 0);
4303 *     ADRS.setLayerAddress(0);
4304 *     ADRS.setTreeAddress(idx_tree);
4305 *     byte[n] node = XMSS_rootFromSig(idx_leaf, getSig_ots(Sig'),
4306 *                                      getAuth(Sig'), M', SEED, ADRS);
4307 *     for ( j = 1; j < d; j++ ) {
4308 *        idx_leaf = (h / d) least significant bits of idx_tree;
4309 *        idx_tree = (h - j * h / d) most significant bits of idx_tree;
4310 *        Sig' = getXMSSSignature(Sig_MT, j);
4311 *        ADRS.setLayerAddress(j);
4312 *        ADRS.setTreeAddress(idx_tree);
4313 *        node = XMSS_rootFromSig(idx_leaf, getSig_ots(Sig'),
4314 *                              getAuth(Sig'), node, SEED, ADRS);
4315 *     }
4316 *     if ( node == getRoot(PK_MT) ) {
4317 *       return true;
4318 *     } else {
4319 *       return false;
4320 *     }
4321 *
4322 * @param [in]       state    XMSS/MT state including digest and parameters.
4323 * @param [in]       m        Message buffer.
4324 * @param [in]       mlen     Length of message in bytes.
4325 * @param [in]       sig      Buffer holding signature.
4326 * @param [in]       pk       Public key.
4327 * @return  0 on success.
4328 * @return  MEMORY_E on dynamic memory allocation failure.
4329 * @return  SIG_VERIFY_E on verification failure.
4330 * @return  <0 on digest failure.
4331 */
4332int wc_xmssmt_verify(XmssState* state, const unsigned char* m, word32 mlen,
4333    const unsigned char* sig, const unsigned char* pk)
4334{
4335    const XmssParams* params = state->params;
4336    const word8 n = params->n;
4337    int ret = 0;
4338    const byte* pub_root = pk;
4339    const byte* pk_seed = pk + n;
4340    byte node[WC_XMSS_MAX_N];
4341    wc_Idx idx;
4342    word32 idx_leaf = 0;
4343    unsigned int i;
4344
4345    /* Set 32/64-bit index to 0. */
4346    WC_IDX_ZERO(idx);
4347    /* Set all address values to zero. */
4348    XMEMSET(state->addr, 0, sizeof(HashAddress));
4349
4350    if (ret == 0) {
4351        /* Convert the index bytes from the signature to an integer. */
4352        WC_IDX_DECODE(idx, params->idx_len, sig, ret);
4353    }
4354
4355    if (ret == 0) {
4356        const byte* sig_r = sig + params->idx_len;
4357        /* byte[n] M' = H_msg(getR(Sig_MT) || getRoot(PK_MT) ||
4358         *                    (toByte(idx_sig, n)), M);
4359         */
4360        wc_xmss_hash_message(state, sig_r, pub_root, sig, params->idx_len, m,
4361            mlen, node);
4362        ret = state->ret;
4363    }
4364
4365    if (ret == 0) {
4366        /* Set tree of hash address. */
4367        WC_IDX_SET_ADDR_TREE(idx, params->idx_len, params->sub_h, state->addr,
4368            idx_leaf);
4369
4370        /* Skip to first WOTS+ signature and derive root. */
4371        sig += params->idx_len + n;
4372        wc_xmss_root_from_sig(state, pk_seed, sig, idx_leaf, state->addr,
4373            node);
4374        ret = state->ret;
4375    }
4376    /* Calculate root of remaining subtrees up to top. */
4377    for (i = 1; (ret == 0) && (i < params->d); i++) {
4378        /* Set layer and tree. */
4379        state->addr[XMSS_ADDR_LAYER] = i;
4380        WC_IDX_SET_ADDR_TREE(idx, params->idx_len, params->sub_h, state->addr,
4381            idx_leaf);
4382        /* Skip to next WOTS+ signature and derive root. */
4383        sig += params->wots_sig_len + params->sub_h * n;
4384        wc_xmss_root_from_sig(state, pk_seed, sig, idx_leaf, state->addr,
4385            node);
4386        ret = state->ret;
4387    }
4388    /* Compare calculated node with public key root. */
4389    if ((ret == 0) && (XMEMCMP(node, pub_root, n) != 0)) {
4390        ret = SIG_VERIFY_E;
4391    }
4392
4393    return ret;
4394}
4395#endif /* WOLFSSL_HAVE_XMSS */
4396