/* wc_xmss_impl.c * * Copyright (C) 2006-2026 wolfSSL Inc. * * This file is part of wolfSSL. * * wolfSSL is free software; you can redistribute it and/or modify * it under the terms of the GNU General Public License as published by * the Free Software Foundation; either version 3 of the License, or * (at your option) any later version. * * wolfSSL is distributed in the hope that it will be useful, * but WITHOUT ANY WARRANTY; without even the implied warranty of * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the * GNU General Public License for more details. * * You should have received a copy of the GNU General Public License * along with this program; if not, write to the Free Software * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1335, USA */ /* Based on: * o RFC 8391 - XMSS: eXtended Merkle Signature Scheme * o [HDSS] "Hash-based Digital Signature Schemes", Buchmann, Dahmen and Szydlo * from "Post Quantum Cryptography", Springer 2009. * o [OPX] "Optimal Parameters for XMSS^MT", Hulsing, Rausch and Buchmann * * TODO: "Simple and Memory-efficient Signature Generation of XMSS^MT" * (https://ece.engr.uvic.ca/~raltawy/SAC2021/9.pdf) */ #include #include #include #ifdef NO_INLINE #include #else #define WOLFSSL_MISC_INCLUDED #include #endif #if defined(WOLFSSL_HAVE_XMSS) /* Indices into Hash Address. */ #define XMSS_ADDR_LAYER 0 #define XMSS_ADDR_TREE_HI 1 #define XMSS_ADDR_TREE 2 #define XMSS_ADDR_TYPE 3 #define XMSS_ADDR_OTS 4 #define XMSS_ADDR_LTREE 4 #define XMSS_ADDR_TREE_ZERO 4 #define XMSS_ADDR_CHAIN 5 #define XMSS_ADDR_TREE_HEIGHT 5 #define XMSS_ADDR_HASH 6 #define XMSS_ADDR_TREE_INDEX 6 #define XMSS_ADDR_KEY_MASK 7 /* Types of hash addresses. */ #define WC_XMSS_ADDR_TYPE_OTS 0 #define WC_XMSS_ADDR_TYPE_LTREE 1 #define WC_XMSS_ADDR_TYPE_TREE 2 /* Byte to include in hash to create unique sequence. */ #define XMSS_HASH_PADDING_F 0U #define XMSS_HASH_PADDING_H 1U #define XMSS_HASH_PADDING_HASH 2U #define XMSS_HASH_PADDING_PRF 3U #define XMSS_HASH_PADDING_PRF_KEYGEN 4U /* Fixed parameter values. */ #define XMSS_WOTS_W 16U #define XMSS_WOTS_LOG_W 4U #define XMSS_WOTS_LEN2 3U #define XMSS_CSUM_SHIFT 4U #define XMSS_CSUM_LEN 2U /* Length of the message to the PRF. */ #define XMSS_PRF_M_LEN 32U /* Length of index encoding when doing XMSS. */ #define XMSS_IDX_LEN 4U /* Size of the N when using SHA-256 and 32 byte padding. */ #define XMSS_SHA256_32_N WC_SHA256_DIGEST_SIZE /* Size of the padding when using SHA-256 and 32 byte padding. */ #define XMSS_SHA256_32_PAD_LEN 32U /* Calculate PRF data length for parameters. */ #define XMSS_HASH_PRF_DATA_LEN(params) \ ((word32)(params)->pad_len + (params)->n + WC_XMSS_ADDR_LEN) /* PRF data length when using SHA-256 with 32 byte padding. */ #define XMSS_HASH_PRF_DATA_LEN_SHA256_32 \ (XMSS_SHA256_32_PAD_LEN + XMSS_SHA256_32_N + WC_XMSS_ADDR_LEN) /* Calculate chain hash data length for parameters. */ #define XMSS_CHAIN_HASH_DATA_LEN(params) \ ((word32)(params)->pad_len + 2U * (params)->n) /* Chain hash data length when using SHA-256 with 32 byte padding. */ #define XMSS_CHAIN_HASH_DATA_LEN_SHA256_32 \ (XMSS_SHA256_32_PAD_LEN + 2U * XMSS_SHA256_32_N) /* Calculate rand hash data length for parameters. */ #define XMSS_RAND_HASH_DATA_LEN(params) \ ((word32)(params)->pad_len + 3U * (params)->n) /* Rand hash data length when using SHA-256 with 32 byte padding. */ #define XMSS_RAND_HASH_DATA_LEN_SHA256_32 \ (XMSS_SHA256_32_PAD_LEN + 3U * XMSS_SHA256_32_N) /* Encode pad value into byte array. Front fill with 0s. * * RFC 8391: 2.4 * * @param [in] n Number to encode. * @param [out] a Array to hold encoding. * @param [in] l Length of array. */ #define XMSS_PAD_ENC(n, a, l) \ do { \ XMEMSET(a, 0, l); \ (a)[(l) - 1] = (byte)(n); \ } while (0) /******************************************** * Index 32/64 bits ********************************************/ /* Index of 32 or 64 bits. */ typedef union wc_Idx { #if WOLFSSL_XMSS_MAX_HEIGHT > 32 /* 64-bit representation. */ w64wrapper u64; #endif #if WOLFSSL_XMSS_MIN_HEIGHT <= 32 /* 32-bit representation. */ word32 u32; #endif } wc_Idx; #if WOLFSSL_XMSS_MAX_HEIGHT > 32 /* Set index to zero. * * Index is up to 64-bits. * * @param [out] idx 32/64-bit index to zero. */ #define WC_IDX_ZERO(idx) w64Zero(&(idx).u64) #else /* Set index to zero. * * Index is no more than 32-bits. * * @param [out] idx 32/64-bit index to zero. */ #define WC_IDX_ZERO(idx) idx.u32 = 0 #endif #if WOLFSSL_XMSS_MAX_HEIGHT > 32 /* Decode 64-bit index. * * @param [out] i Index from encoding. * @param [in] c Count of bytes to decode to index. * @param [in] a Array to decode from. * @param [out] ret Return value. */ #define IDX64_DECODE(i, c, a, ret) \ if ((c) == 5) { \ word32 t; \ ato32((a) + 1, &t); \ (i) = w64From32((a)[0], t); \ } \ else if ((c) == 8) { \ ato64(a, &(i)); \ } /* Decode 64-bit index. * * @param [out] i Index from encoding. * @param [in] c Count of bytes to decode to index. * @param [in] a Array to decode from. * @param [out] ret Return value. */ #define XMSS_IDX64_DECODE(i, c, a, ret) \ do { \ IDX64_DECODE(i, c, a, ret) \ else { \ (ret) = NOT_COMPILED_IN; \ } \ } while (0) /* Check whether index is valid. * * @param [in] i Index to check. * @param [in] c Count of bytes i was encoded in. * @param [in] h Full tree Height. */ #define IDX64_INVALID(i, c, h) \ ((w64GetHigh32(w64Add32(i, 1, NULL)) >> ((h) - 32)) != 0) /* Set 64-bit index as hash address value for tree. * * @param [in] i Index to set. * @param [in] c Count of bytes to encode into. * @param [in] h Height of tree. * @param [out] a Hash address to encode into. * @param [out] l Index of leaf. */ #define IDX64_SET_ADDR_TREE(i, c, h, a, l) \ if ((c) > 4) { \ (l) = w64GetLow32(i) & (((word32)1U << (h)) - 1U); \ (i) = w64ShiftRight(i, h); \ (a)[XMSS_ADDR_TREE_HI] = w64GetHigh32(i); \ (a)[XMSS_ADDR_TREE] = w64GetLow32(i); \ } #endif /* WOLFSSL_XMSS_MAX_HEIGHT > 32 */ #if WOLFSSL_XMSS_MIN_HEIGHT <= 32 /* Decode 32-bit index. * * @param [out] i Index from encoding. * @param [in] c Count of bytes to decode to index. * @param [in] a Array to decode from. * @param [out] ret Return value. */ #define IDX32_DECODE(i, c, a, ret) \ if ((c) == 4) { \ ato32(a, &(i)); \ } \ else if ((c) == 3) { \ ato24(a, &(i)); \ } /* Decode 32-bit index. * * @param [out] i Index from encoding. * @param [in] c Count of bytes to decode to index. * @param [in] a Array to decode from. * @param [out] ret Return value. */ #define XMSS_IDX32_DECODE(i, c, a, ret) \ do { \ IDX32_DECODE(i, c, a, ret) \ else { \ (ret) = NOT_COMPILED_IN; \ } \ } while (0) /* Check whether 32-bit index is valid. * * @param [in] i Index to check. * @param [in] c Count of bytes i was encoded in. * @param [in] h Full tree Height. */ #define IDX32_INVALID(i, c, h) \ ((((i) + 1) >> (h)) != 0) /* Set 32-bit index as hash address value for tree. * * @param [in] i Index to set. * @param [in] c Count of bytes to encode into. * @param [in] h Height of tree. * @param [out] a Hash address to encode into. * @param [out] l Index of leaf. */ #define IDX32_SET_ADDR_TREE(i, c, h, a, l) \ if ((c) <= 4) { \ (l) = ((i) & (((word32)1U << (h)) - 1U)); \ (i) >>= params->sub_h; \ (a)[XMSS_ADDR_TREE] = (i); \ } #endif /* WOLFSSL_XMSS_MIN_HEIGHT <= 32 */ #if (WOLFSSL_XMSS_MAX_HEIGHT > 32) && (WOLFSSL_XMSS_MIN_HEIGHT <= 32) /* Decode 32/64-bit index. * * @param [out] idx Index from encoding. * @param [in] c Count of bytes to decode to index. * @param [in] a Array to decode from. * @param [out] ret Return value. */ #define WC_IDX_DECODE(idx, c, a, ret) \ do { \ IDX64_DECODE((idx).u64, c, a, ret) \ else \ IDX32_DECODE((idx).u32, c, a, ret) \ else { \ (ret) = NOT_COMPILED_IN; \ } \ } while (0) /* Check whether index is valid. * * @param [in] i Index to check. * @param [in] c Count of bytes i was encoded in. * @param [in] h Full tree Height. */ #define WC_IDX_INVALID(i, c, h) \ ((((c) > 4) && IDX64_INVALID((i).u64, c, h)) || \ (((c) <= 4) && IDX32_INVALID((i).u32, c, h))) /* Set 32/64-bit index as hash address value for tree. * * @param [in] i Index to set. * @param [in] c Count of bytes to encode into. * @param [in] h Height of tree. * @param [out] a Hash address to encode into. * @param [out] l Index of leaf. */ #define WC_IDX_SET_ADDR_TREE(idx, c, h, a, l) \ do { \ IDX64_SET_ADDR_TREE((idx).u64, c, h, a, l) \ else \ IDX32_SET_ADDR_TREE((idx).u32, c, h, a, l) \ } while (0) #elif WOLFSSL_XMSS_MAX_HEIGHT > 32 /* Decode 64-bit index. * * @param [out] idx Index from encoding. * @param [in] c Count of bytes to decode to index. * @param [in] a Array to decode from. * @param [out] ret Return value. */ #define WC_IDX_DECODE(idx, c, a, ret) \ do { \ IDX64_DECODE((idx).u64, c, a, ret) \ } while (0) /* Check whether index is valid. * * @param [in] i Index to check. * @param [in] c Count of bytes i was encoded in. * @param [in] h Full tree Height. */ #define WC_IDX_INVALID(i, c, h) \ IDX64_INVALID((i).u64, c, h) /* Set 64-bit index as hash address value for tree. * * @param [in] i Index to set. * @param [in] c Count of bytes to encode into. * @param [in] h Height of tree. * @param [out] a Hash address to encode into. * @param [out] l Index of leaf. */ #define WC_IDX_SET_ADDR_TREE(idx, c, h, a, l) \ do { \ IDX64_SET_ADDR_TREE((idx).u64, c, h, a, l) \ } while (0) #else /* Decode 32-bit index. * * @param [out] idx Index from encoding. * @param [in] c Count of bytes to decode to index. * @param [in] a Array to decode from. * @param [out] ret Return value. */ #define WC_IDX_DECODE(idx, c, a, ret) \ do { \ IDX32_DECODE((idx).u32, c, a, ret) \ else { \ (ret) = NOT_COMPILED_IN; \ } \ } while (0) /* Check whether index is valid. * * @param [in] i Index to check. * @param [in] c Count of bytes i was encoded in. * @param [in] h Full tree Height. */ #define WC_IDX_INVALID(i, c, h) \ IDX32_INVALID((i).u32, c, h) /* Set 32-bit index as hash address value for tree. * * @param [in] i Index to set. * @param [in] c Count of bytes to encode into. * @param [in] h Height of tree. * @param [out] a Hash address to encode into. * @param [out] l Index of leaf. */ #define WC_IDX_SET_ADDR_TREE(idx, c, h, a, l) \ do { \ IDX32_SET_ADDR_TREE(idx.u32, c, h, a, l) \ } while (0) #endif /* (WOLFSSL_XMSS_MAX_HEIGHT > 32) && (WOLFSSL_XMSS_MIN_HEIGHT <= 32) */ #ifndef WOLFSSL_XMSS_VERIFY_ONLY /* Update index by adding one to big-endian encoded value. * * @param [in, out] a Array index is encoded in. * @param [in] l Length of encoded index. */ static void wc_idx_update(unsigned char* a, word32 l) { word32 i; for (i = l; i > 0; i--) { if ((++a[i - 1]) != 0) { break; } } } /* Copy index from source buffer to destination buffer. * * Index is put in the back of the destination buffer. * * @param [in] s Source buffer. * @param [in] sl Length of index in source. * @param [in, out] d Destination buffer. * @param [in] dl Length of destination buffer. */ static void wc_idx_copy(const unsigned char* s, word32 sl, unsigned char* d, word32 dl) { /* Zero the destination first so an invariant violation produces a * deterministic empty buffer rather than reusing prior contents. */ XMEMSET(d, 0, dl); /* Caller must size the destination at least as large as the source. * Without this guard, dl - sl wraps to ~4 GB and corrupts memory. */ if (dl < sl) { return; } XMEMCPY(d + dl - sl, s, sl); } #endif /******************************************** * Hash Address. ********************************************/ /* Set the hash address based on subtree. * * @param [out] a Hash address. * @param [in] s Subtree hash address. * @param [in] t Type of hash address. */ #define XMSS_ADDR_SET_SUBTREE(a, s, t) \ do { \ (a)[XMSS_ADDR_LAYER] = (s)[XMSS_ADDR_LAYER]; \ (a)[XMSS_ADDR_TREE_HI] = (s)[XMSS_ADDR_TREE_HI]; \ (a)[XMSS_ADDR_TREE] = (s)[XMSS_ADDR_TREE]; \ (a)[XMSS_ADDR_TYPE] = (t); \ XMEMSET((a) + 4, 0, sizeof(a) - 4 * sizeof(*(a)));\ } while (0) /* Set the OTS hash address based on subtree. * * @param [out] a Hash address. * @param [in] s Subtree hash address. */ #define XMSS_ADDR_OTS_SET_SUBTREE(a, s) \ XMSS_ADDR_SET_SUBTREE(a, s, WC_XMSS_ADDR_TYPE_OTS) /* Set the L-tree address based on subtree. * * @param [out] a Hash address. * @param [in] s Subtree hash address. */ #define XMSS_ADDR_LTREE_SET_SUBTREE(a, s) \ XMSS_ADDR_SET_SUBTREE(a, s, WC_XMSS_ADDR_TYPE_LTREE) /* Set the hash tree address based on subtree. * * @param [out] a Hash address. * @param [in] s Subtree hash address. */ #define XMSS_ADDR_TREE_SET_SUBTREE(a, s) \ XMSS_ADDR_SET_SUBTREE(a, s, WC_XMSS_ADDR_TYPE_TREE) #ifdef LITTLE_ENDIAN_ORDER /* Set a byte value into a word of an encoded address. * * @param [in, out] a Encoded hash address. * @param [in] i Index of word. * @param [in] b Byte to set. */ #define XMSS_ADDR_SET_BYTE(a, i, b) \ ((word32*)(a))[i] = (word32)(b) << 24 #else /* Set a byte value into a word of an encoded address. * * @param [in, out] a Encoded hash address. * @param [in] i Index of word. * @param [in] b Byte to set. */ #define XMSS_ADDR_SET_BYTE(a, i, b) \ ((word32*)(a))[i] = (b) #endif /* LITTLE_ENDIAN_ORDER */ /* Convert hash address to bytes. * * @param [out] bytes Array to encode into. * @param [in] addr Hash address. */ static void wc_xmss_addr_encode(const HashAddress addr, byte* bytes) { c32toa((addr)[0], (bytes) + (0 * 4)); c32toa((addr)[1], (bytes) + (1 * 4)); c32toa((addr)[2], (bytes) + (2 * 4)); c32toa((addr)[3], (bytes) + (3 * 4)); c32toa((addr)[4], (bytes) + (4 * 4)); c32toa((addr)[5], (bytes) + (5 * 4)); c32toa((addr)[6], (bytes) + (6 * 4)); c32toa((addr)[7], (bytes) + (7 * 4)); } /******************************************** * HASHING ********************************************/ #if !defined(WOLFSSL_WC_XMSS_SMALL) && defined(WC_XMSS_SHA256) && \ !defined(WC_XMSS_FULL_HASH) /* Set hash data and length into SHA-256 digest. * * @param [in, out] state XMSS/MT state with SHA-256 digest. * @param [in] data Data to add to hash. * @param [in] len Number of bytes in data. * Must be less than a block. * @param [in] total_len Number of bytes updated so far. */ #define XMSS_SHA256_SET_DATA(state, data, len, total_len) \ do { \ XMEMCPY((state)->digest.sha256.buffer, data, len); \ (state)->digest.sha256.buffLen = (len); \ (state)->digest.sha256.loLen = (total_len); \ } while (0) /* Save the SHA-256 state to cache. * * @param [in, out] state XMSS/MT state with SHA-256 digest and state cache. */ #define XMSS_SHA256_STATE_CACHE(state) \ (state)->dgst_state[0] = (state)->digest.sha256.digest[0]; \ (state)->dgst_state[1] = (state)->digest.sha256.digest[1]; \ (state)->dgst_state[2] = (state)->digest.sha256.digest[2]; \ (state)->dgst_state[3] = (state)->digest.sha256.digest[3]; \ (state)->dgst_state[4] = (state)->digest.sha256.digest[4]; \ (state)->dgst_state[5] = (state)->digest.sha256.digest[5]; \ (state)->dgst_state[6] = (state)->digest.sha256.digest[6]; \ (state)->dgst_state[7] = (state)->digest.sha256.digest[7]; \ /* Restore the SHA-256 state from cache and set length. * * @param [in, out] state XMSS/MT state with SHA-256 digest and state cache. * @param [in] len Number of bytes of data hashed so far. */ #define XMSS_SHA256_STATE_RESTORE(state, len) \ do { \ (state)->digest.sha256.digest[0] = (state)->dgst_state[0]; \ (state)->digest.sha256.digest[1] = (state)->dgst_state[1]; \ (state)->digest.sha256.digest[2] = (state)->dgst_state[2]; \ (state)->digest.sha256.digest[3] = (state)->dgst_state[3]; \ (state)->digest.sha256.digest[4] = (state)->dgst_state[4]; \ (state)->digest.sha256.digest[5] = (state)->dgst_state[5]; \ (state)->digest.sha256.digest[6] = (state)->dgst_state[6]; \ (state)->digest.sha256.digest[7] = (state)->dgst_state[7]; \ (state)->digest.sha256.loLen = (len); \ } while (0) /* Restore the SHA-256 state from cache and set data and length. * * @param [in, out] state XMSS/MT state with SHA-256 digest and cache. * @param [in] data Data to add to hash. * @param [in] len Number of bytes in data. * Must be less than a block. * @param [in] total_len Number of bytes updated so far. */ #define XMSS_SHA256_STATE_RESTORE_DATA(state, data, len, total_len) \ do { \ (state)->digest.sha256.digest[0] = (state)->dgst_state[0]; \ (state)->digest.sha256.digest[1] = (state)->dgst_state[1]; \ (state)->digest.sha256.digest[2] = (state)->dgst_state[2]; \ (state)->digest.sha256.digest[3] = (state)->dgst_state[3]; \ (state)->digest.sha256.digest[4] = (state)->dgst_state[4]; \ (state)->digest.sha256.digest[5] = (state)->dgst_state[5]; \ (state)->digest.sha256.digest[6] = (state)->dgst_state[6]; \ (state)->digest.sha256.digest[7] = (state)->dgst_state[7]; \ XMSS_SHA256_SET_DATA(state, data, len, total_len); \ } while (0) #endif /* !WOLFSSL_WC_XMSS_SMALL && WC_XMSS_SHA256 && !WC_XMSS_FULL_HASH */ /* Hash the data into output buffer. * * @param [in] state XMSS/MT state including digest and parameters. * @param [in] in Data to digest. * @param [in] inlen Length of data to digest in bytes. * @param [out] out Buffer to put digest into. */ static WC_INLINE void wc_xmss_hash(XmssState* state, const byte* in, word32 inlen, byte* out) { int ret; const XmssParams* params = state->params; #ifdef WC_XMSS_SHA256 /* Full SHA-256 digest. */ if ((params->hash == WC_HASH_TYPE_SHA256) && (params->n == WC_SHA256_DIGEST_SIZE)) { ret = wc_Sha256Update(&state->digest.sha256, in, inlen); if (ret == 0) { ret = wc_Sha256Final(&state->digest.sha256, out); } } #if WOLFSSL_WC_XMSS_MIN_HASH_SIZE <= 192 && WOLFSSL_WC_XMSS_MAX_HASH_SIZE >= 192 /* Partial SHA-256 digest. */ else if (params->hash == WC_HASH_TYPE_SHA256) { byte buf[WC_SHA256_DIGEST_SIZE]; ret = wc_Sha256Update(&state->digest.sha256, in, inlen); if (ret == 0) { ret = wc_Sha256Final(&state->digest.sha256, buf); } if (ret == 0) { XMEMCPY(out, buf, params->n); } } #endif else #endif /* WC_XMSS_SHA256 */ #ifdef WC_XMSS_SHA512 /* Full SHA-512 digest. */ if (params->hash == WC_HASH_TYPE_SHA512) { ret = wc_Sha512Update(&state->digest.sha512, in, inlen); if (ret == 0) { ret = wc_Sha512Final(&state->digest.sha512, out); } } else #endif /* WC_XMSS_SHA512 */ #ifdef WC_XMSS_SHAKE128 /* Digest with SHAKE-128. */ if (params->hash == WC_HASH_TYPE_SHAKE128) { ret = wc_Shake128_Update(&state->digest.shake, in, inlen); if (ret == 0) { ret = wc_Shake128_Final(&state->digest.shake, out, params->n); } } else #endif /* WC_XMSS_SHAKE128 */ #ifdef WC_XMSS_SHAKE256 /* Digest with SHAKE-256. */ if (params->hash == WC_HASH_TYPE_SHAKE256) { ret = wc_Shake256_Update(&state->digest.shake, in, inlen); if (ret == 0) { ret = wc_Shake256_Final(&state->digest.shake, out, params->n); } } else #endif /* WC_XMSS_SHAKE256 */ { /* Unsupported digest function. */ ret = NOT_COMPILED_IN; } if (state->ret == 0) { /* Store any digest failures for public APIs to return. */ state->ret = ret; } } #if !defined(WOLFSSL_WC_XMSS_SMALL) && defined(WC_XMSS_SHA256) #ifndef WC_XMSS_FULL_HASH /* Chain hashing. * * RFC 8391: 3.1.2, Algorithm 2: chain - Chaining Function * ... * ADRS.setKeyAndMask(0); * KEY = PRF(SEED, ADRS); * ADRS.setKeyAndMask(1); * BM = PRF(SEED, ADRS); * tmp = F(KEY, tmp XOR BM); * return tmp; * * @param [in] state XMSS/MT state including digest and parameters. * @param [in] tmp Temporary buffer holding chain data. * @param [in] addr Hash address as a byte array. * @param [out] hash Buffer to hold hash. */ static void wc_xmss_chain_hash_sha256_32(XmssState* state, const byte* tmp, byte* addr, byte* hash) { /* Offsets into chain hash data. */ byte* pad = state->buf; byte* key = pad + XMSS_SHA256_32_PAD_LEN; byte* bm = key + XMSS_SHA256_32_N; int ret; /* Calculate n-byte key - KEY. */ ((word32*)addr)[XMSS_ADDR_KEY_MASK] = 0; /* Copy back state after first 64 bytes. */ XMSS_SHA256_STATE_RESTORE_DATA(state, addr, WC_XMSS_ADDR_LEN, XMSS_HASH_PRF_DATA_LEN_SHA256_32); /* Calculate hash. */ ret = wc_Sha256Final(&state->digest.sha256, key); if (ret == 0) { /* Calculate n-byte bit mask - BM. */ addr[XMSS_ADDR_KEY_MASK * 4 + 3] = 1; /* Copy back state after first 64 bytes. */ XMSS_SHA256_STATE_RESTORE_DATA(state, addr, WC_XMSS_ADDR_LEN, XMSS_HASH_PRF_DATA_LEN_SHA256_32); /* Calculate hash. */ ret = wc_Sha256Final(&state->digest.sha256, bm); } if (ret == 0) { /* Function padding set in caller. */ xorbuf(bm, tmp, XMSS_SHA256_32_N); ret = wc_Sha256Update(&state->digest.sha256, state->buf, XMSS_CHAIN_HASH_DATA_LEN_SHA256_32); } if (ret == 0) { /* Calculate the chain hash. */ ret = wc_Sha256Final(&state->digest.sha256, hash); } if (state->ret == 0) { /* Store any digest failures for public APIs to return. */ state->ret = ret; } } #else /* Chain hashing. * * Padding, seed, addr for PRF set by caller into prf_buf. * * RFC 8391: 3.1.2, Algorithm 2: chain - Chaining Function * ... * ADRS.setKeyAndMask(0); * KEY = PRF(SEED, ADRS); * ADRS.setKeyAndMask(1); * BM = PRF(SEED, ADRS); * tmp = F(KEY, tmp XOR BM); * return tmp; * * @param [in] state XMSS/MT state including digest and parameters. * @param [in] tmp Temporary buffer holding chain data. * @param [out] out Buffer to hold hash. */ static void wc_xmss_chain_hash_sha256_32(XmssState* state, const byte* tmp, byte* hash) { byte* addr = state->prf_buf + XMSS_SHA256_32_PAD_LEN + XMSS_SHA256_32_N; /* Offsets into chain hash data. */ byte* pad = state->buf; byte* key = pad + XMSS_SHA256_32_PAD_LEN; byte* bm = key + XMSS_SHA256_32_N; /* Calculate n-byte key - KEY. */ ((word32*)addr)[XMSS_ADDR_KEY_MASK] = 0; wc_xmss_hash(state, state->prf_buf, XMSS_HASH_PRF_DATA_LEN_SHA256_32, key); /* Calculate the n-byte mask. */ addr[XMSS_ADDR_KEY_MASK * 4 + 3] = 1; wc_xmss_hash(state, state->prf_buf, XMSS_HASH_PRF_DATA_LEN_SHA256_32, bm); /* Function padding set in caller. */ xorbuf(bm, tmp, XMSS_SHA256_32_N); /* Calculate the chain hash. */ wc_xmss_hash(state, state->buf, XMSS_CHAIN_HASH_DATA_LEN_SHA256_32, hash); } #endif /* !WC_XMSS_FULL_HASH */ #endif /* !WOLFSSL_WC_XMSS_SMALL && WC_XMSS_SHA256 */ /* Chain hashing. * * Padding, seed, addr for PRF set by caller into prf_buf. * * RFC 8391: 3.1.2, Algorithm 2: chain - Chaining Function * ... * ADRS.setKeyAndMask(0); * KEY = PRF(SEED, ADRS); * ADRS.setKeyAndMask(1); * BM = PRF(SEED, ADRS); * tmp = F(KEY, tmp XOR BM); * return tmp; * * @param [in] state XMSS/MT state including digest and parameters. * @param [in] tmp Temporary buffer holding chain data. * @param [out] hash Buffer to hold hash. */ static void wc_xmss_chain_hash(XmssState* state, const byte* tmp, byte* hash) { const XmssParams* params = state->params; byte* addr = state->prf_buf + params->pad_len + params->n; /* Offsets into chain hash data. */ byte* pad = state->buf; byte* key = pad + params->pad_len; byte* bm = key + params->n; /* Calculate n-byte key - KEY. */ ((word32*)addr)[XMSS_ADDR_KEY_MASK] = 0; wc_xmss_hash(state, state->prf_buf, XMSS_HASH_PRF_DATA_LEN(params), key); /* Calculate n-byte bit mask - BM. */ addr[XMSS_ADDR_KEY_MASK * 4 + 3] = 1; wc_xmss_hash(state, state->prf_buf, XMSS_HASH_PRF_DATA_LEN(params), bm); /* Function padding set in caller. */ xorbuf(bm, tmp, params->n); /* Calculate the chain hash. */ wc_xmss_hash(state, state->buf, XMSS_CHAIN_HASH_DATA_LEN(params), hash); } #if !defined(WOLFSSL_WC_XMSS_SMALL) && defined(WC_XMSS_SHA256) #ifndef WC_XMSS_FULL_HASH /* Randomized tree hashing. * * RFC 8391: 4.1.4, Algorithm 7: RAND_HASH * ... * ADRS.setKeyAndMask(0); * KEY = PRF(SEED, ADRS); * ADRS.setKeyAndMask(1); * BM_0 = PRF(SEED, ADRS); * ADRS.setKeyAndMask(2); * BM_1 = PRF(SEED, ADRS); * return H(KEY, (LEFT XOR BM_0) || (RIGHT XOR BM_1)); * * @param [in] state XMSS/MT state including digest and parameters. * @param [in] data Input data. * @param [in] addr Hash address. * @param [out] hash Buffer to hold hash. */ static void wc_xmss_rand_hash_sha256_32_prehash(XmssState* state, const byte* data, HashAddress addr, byte* hash) { int ret; /* Offsets into rand hash data. */ byte* pad = state->buf; byte* key = pad + XMSS_SHA256_32_PAD_LEN; byte* bm0 = key + XMSS_SHA256_32_N; byte* bm1 = bm0 + XMSS_SHA256_32_N; byte addr_buf[WC_XMSS_ADDR_LEN]; addr[XMSS_ADDR_KEY_MASK] = 0; wc_xmss_addr_encode(addr, addr_buf); /* Calculate n-byte key - KEY. */ XMSS_SHA256_STATE_RESTORE_DATA(state, addr_buf, WC_XMSS_ADDR_LEN, XMSS_HASH_PRF_DATA_LEN_SHA256_32); /* Calculate hash. */ ret = wc_Sha256Final(&state->digest.sha256, key); /* Calculate n-byte mask - BM_0. */ if (ret == 0) { addr_buf[XMSS_ADDR_KEY_MASK * 4 + 3] = 1; /* Copy back state after first 64 bytes. */ XMSS_SHA256_STATE_RESTORE_DATA(state, addr_buf, WC_XMSS_ADDR_LEN, XMSS_HASH_PRF_DATA_LEN_SHA256_32); /* Calculate hash. */ ret = wc_Sha256Final(&state->digest.sha256, bm0); } /* Calculate n-byte mask - BM_1. */ if (ret == 0) { addr_buf[XMSS_ADDR_KEY_MASK * 4 + 3] = 2; /* Copy back state after first 64 bytes. */ XMSS_SHA256_STATE_RESTORE_DATA(state, addr_buf, WC_XMSS_ADDR_LEN, XMSS_HASH_PRF_DATA_LEN_SHA256_32); /* Calculate hash. */ ret = wc_Sha256Final(&state->digest.sha256, bm1); } if (ret == 0) { XMSS_PAD_ENC(XMSS_HASH_PADDING_H, pad, XMSS_SHA256_32_PAD_LEN); /* XOR into bm0 and bm1. */ xorbuf(bm0, data, XMSS_SHA256_32_N * 2); ret = wc_Sha256Update(&state->digest.sha256, state->buf, XMSS_RAND_HASH_DATA_LEN_SHA256_32); } if (ret == 0) { ret = wc_Sha256Final(&state->digest.sha256, hash); } if (state->ret == 0) { /* Store any digest failures for public APIs to return. */ state->ret = ret; } } #endif /* !WC_XMSS_FULL_HASH */ /* Randomized tree hashing. * * RFC 8391: 4.1.4, Algorithm 7: RAND_HASH * ... * ADRS.setKeyAndMask(0); * KEY = PRF(SEED, ADRS); * ADRS.setKeyAndMask(1); * BM_0 = PRF(SEED, ADRS); * ADRS.setKeyAndMask(2); * BM_1 = PRF(SEED, ADRS); * return H(KEY, (LEFT XOR BM_0) || (RIGHT XOR BM_1)); * * @param [in] state XMSS/MT state including digest and parameters. * @param [in] data Input data. * @param [in] pk_seed Random public seed. * @param [in] addr Hash address. * @param [out] hash Buffer to hold hash. */ static void wc_xmss_rand_hash_sha256_32(XmssState* state, const byte* data, const byte* pk_seed, HashAddress addr, byte* hash) { byte* addr_buf = state->prf_buf + XMSS_SHA256_32_PAD_LEN + XMSS_SHA256_32_N; /* Offsets into rand hash data. */ byte* pad = state->buf; byte* key = pad + XMSS_SHA256_32_PAD_LEN; byte* bm0 = key + XMSS_SHA256_32_N; byte* bm1 = bm0 + XMSS_SHA256_32_N; #ifndef WC_XMSS_FULL_HASH int ret; /* Encode padding byte for PRF. */ XMSS_PAD_ENC(XMSS_HASH_PADDING_PRF, state->prf_buf, XMSS_SHA256_32_PAD_LEN); /* Append public seed for PRF. */ XMEMCPY(state->prf_buf + XMSS_SHA256_32_PAD_LEN, pk_seed, XMSS_SHA256_32_N); /* Set key mask to initial value and append encoding. */ addr[XMSS_ADDR_KEY_MASK] = 0; wc_xmss_addr_encode(addr, addr_buf); /* Calculate n-byte key - KEY. */ ret = wc_Sha256Update(&state->digest.sha256, state->prf_buf, XMSS_SHA256_32_PAD_LEN + XMSS_SHA256_32_N); if (ret == 0) { /* Copy state after first 64 bytes. */ XMSS_SHA256_STATE_CACHE(state); /* Copy in remaining 32 bytes to buffer. */ XMSS_SHA256_SET_DATA(state, addr_buf, WC_XMSS_ADDR_LEN, XMSS_HASH_PRF_DATA_LEN_SHA256_32); /* Calculate hash. */ ret = wc_Sha256Final(&state->digest.sha256, key); } /* Calculate n-byte mask - BM_0. */ if (ret == 0) { addr_buf[XMSS_ADDR_KEY_MASK * 4 + 3] = 1; /* Copy back state after first 64 bytes. */ XMSS_SHA256_STATE_RESTORE_DATA(state, addr_buf, WC_XMSS_ADDR_LEN, XMSS_HASH_PRF_DATA_LEN_SHA256_32); /* Calculate hash. */ ret = wc_Sha256Final(&state->digest.sha256, bm0); } /* Calculate n-byte mask - BM_1. */ if (ret == 0) { addr_buf[XMSS_ADDR_KEY_MASK * 4 + 3] = 2; /* Copy back state after first 64 bytes. */ XMSS_SHA256_STATE_RESTORE_DATA(state, addr_buf, WC_XMSS_ADDR_LEN, XMSS_HASH_PRF_DATA_LEN_SHA256_32); /* Calculate hash. */ ret = wc_Sha256Final(&state->digest.sha256, bm1); } if (ret == 0) { XMSS_PAD_ENC(XMSS_HASH_PADDING_H, pad, XMSS_SHA256_32_PAD_LEN); /* XOR into bm0 and bm1. */ xorbuf(bm0, data, 2 * XMSS_SHA256_32_N); ret = wc_Sha256Update(&state->digest.sha256, state->buf, XMSS_RAND_HASH_DATA_LEN_SHA256_32); } if (ret == 0) { ret = wc_Sha256Final(&state->digest.sha256, hash); } if (state->ret == 0) { /* Store any digest failures for public APIs to return. */ state->ret = ret; } #else /* Encode padding byte for PRF. */ XMSS_PAD_ENC(XMSS_HASH_PADDING_PRF, state->prf_buf, XMSS_SHA256_32_PAD_LEN); /* Append public seed for PRF. */ XMEMCPY(state->prf_buf + XMSS_SHA256_32_PAD_LEN, pk_seed, XMSS_SHA256_32_N); /* Set key mask to initial value and append encoding. */ addr[XMSS_ADDR_KEY_MASK] = 0; wc_xmss_addr_encode(addr, addr_buf); /* Calculate n-byte key - KEY. */ wc_xmss_hash(state, state->prf_buf, XMSS_HASH_PRF_DATA_LEN_SHA256_32, key); /* Calculate n-byte mask - BM_0. */ addr_buf[XMSS_ADDR_KEY_MASK * 4 + 3] = 1; wc_xmss_hash(state, state->prf_buf, XMSS_HASH_PRF_DATA_LEN_SHA256_32, bm0); /* Calculate n-byte mask - BM_1. */ addr_buf[XMSS_ADDR_KEY_MASK * 4 + 3] = 2; wc_xmss_hash(state, state->prf_buf, XMSS_HASH_PRF_DATA_LEN_SHA256_32, bm1); XMSS_PAD_ENC(XMSS_HASH_PADDING_H, state->buf, XMSS_SHA256_32_PAD_LEN); xorbuf(bm0, data, 2 * XMSS_SHA256_32_N); wc_xmss_hash(state, state->buf, XMSS_RAND_HASH_DATA_LEN_SHA256_32, hash); #endif /* WC_XMSS_FULL_HASH */ } #endif /* !WOLFSSL_WC_XMSS_SMALL && WC_XMSS_SHA256 */ /* Randomized tree hashing. * * RFC 8391: 4.1.4, Algorithm 7: RAND_HASH * ... * ADRS.setKeyAndMask(0); * KEY = PRF(SEED, ADRS); * ADRS.setKeyAndMask(1); * BM_0 = PRF(SEED, ADRS); * ADRS.setKeyAndMask(2); * BM_1 = PRF(SEED, ADRS); * return H(KEY, (LEFT XOR BM_0) || (RIGHT XOR BM_1)); * * @param [in] state XMSS/MT state including digest and parameters. * @param [in] data Input data. * @param [in] pk_seed Random public seed. * @param [in] addr Hash address. * @param [out] hash Buffer to hold hash. */ static void wc_xmss_rand_hash(XmssState* state, const byte* data, const byte* pk_seed, HashAddress addr, byte* hash) { const XmssParams* params = state->params; #if !defined(WOLFSSL_WC_XMSS_SMALL) && defined(WC_XMSS_SHA256) if ((params->pad_len == XMSS_SHA256_32_PAD_LEN) && (params->n == XMSS_SHA256_32_N) && (params->hash == WC_HASH_TYPE_SHA256)) { wc_xmss_rand_hash_sha256_32(state, data, pk_seed, addr, hash); } else #endif /* !WOLFSSL_WC_XMSS_SMALL && WC_XMSS_SHA256 */ { byte* addr_buf = state->prf_buf + params->pad_len + params->n; /* Offsets into rand hash data. */ byte* pad = state->buf; byte* key = pad + params->pad_len; byte* bm0 = key + params->n; byte* bm1 = bm0 + params->n; const word32 len = XMSS_HASH_PRF_DATA_LEN(params); /* Encode padding byte for PRF. */ XMSS_PAD_ENC(XMSS_HASH_PADDING_PRF, state->prf_buf, params->pad_len); /* Append public seed for PRF. */ XMEMCPY(state->prf_buf + params->pad_len, pk_seed, params->n); /* Set key mask to initial value and append encoding. */ addr[XMSS_ADDR_KEY_MASK] = 0; wc_xmss_addr_encode(addr, addr_buf); /* Calculate n-byte key - KEY. */ wc_xmss_hash(state, state->prf_buf, len, key); /* Calculate n-byte mask - BM_0. */ addr_buf[XMSS_ADDR_KEY_MASK * 4 + 3] = 1; wc_xmss_hash(state, state->prf_buf, len, bm0); /* Calculate n-byte mask - BM_1. */ addr_buf[XMSS_ADDR_KEY_MASK * 4 + 3] = 2; wc_xmss_hash(state, state->prf_buf, len, bm1); XMSS_PAD_ENC(XMSS_HASH_PADDING_H, pad, params->pad_len); xorbuf(bm0, data, 2U * params->n); wc_xmss_hash(state, state->buf, XMSS_RAND_HASH_DATA_LEN(params), hash); } } #if !defined(WOLFSSL_WC_XMSS_SMALL) || defined(WOLFSSL_XMSS_VERIFY_ONLY) #if !defined(WOLFSSL_WC_XMSS_SMALL) && defined(WC_XMSS_SHA256) /* Randomized tree hashing. * * RFC 8391: 4.1.4, Algorithm 7: RAND_HASH * ... * ADRS.setKeyAndMask(0); * KEY = PRF(SEED, ADRS); * ADRS.setKeyAndMask(1); * BM_0 = PRF(SEED, ADRS); * ADRS.setKeyAndMask(2); * BM_1 = PRF(SEED, ADRS); * return H(KEY, (LEFT XOR BM_0) || (RIGHT XOR BM_1)); * * @param [in] state XMSS/MT state including digest and parameters. * @param [in] left First half of data. * @param [in] right Second half of data. * @param [in] pk_seed Random public seed. * @param [in] addr Hash address. * @param [out] hash Buffer to hold hash. */ static void wc_xmss_rand_hash_lr_sha256_32(XmssState* state, const byte* left, const byte* right, const byte* pk_seed, HashAddress addr, byte* hash) { byte* addr_buf = state->prf_buf + XMSS_SHA256_32_PAD_LEN + XMSS_SHA256_32_N; /* Offsets into rand hash data. */ byte* pad = state->buf; byte* key = pad + XMSS_SHA256_32_PAD_LEN; byte* bm0 = key + XMSS_SHA256_32_N; byte* bm1 = bm0 + XMSS_SHA256_32_N; #ifndef WC_XMSS_FULL_HASH int ret; /* Encode padding byte for PRF. */ XMSS_PAD_ENC(XMSS_HASH_PADDING_PRF, state->prf_buf, XMSS_SHA256_32_PAD_LEN); /* Append public seed for PRF. */ XMEMCPY(state->prf_buf + XMSS_SHA256_32_PAD_LEN, pk_seed, XMSS_SHA256_32_N); /* Set key mask to initial value and append encoding. */ addr[XMSS_ADDR_KEY_MASK] = 0; wc_xmss_addr_encode(addr, addr_buf); /* Calculate n-byte key - KEY. */ ret = wc_Sha256Update(&state->digest.sha256, state->prf_buf, XMSS_SHA256_32_PAD_LEN + XMSS_SHA256_32_N); if (ret == 0) { /* Copy state after first 64 bytes. */ XMSS_SHA256_STATE_CACHE(state); /* Copy in remaining 32 bytes to buffer. */ XMSS_SHA256_SET_DATA(state, addr_buf, WC_XMSS_ADDR_LEN, XMSS_HASH_PRF_DATA_LEN_SHA256_32); /* Calculate hash. */ ret = wc_Sha256Final(&state->digest.sha256, key); } /* Calculate n-byte mask - BM_0. */ if (ret == 0) { addr_buf[XMSS_ADDR_KEY_MASK * 4 + 3] = 1; /* Copy back state after first 64 bytes. */ XMSS_SHA256_STATE_RESTORE_DATA(state, addr_buf, WC_XMSS_ADDR_LEN, XMSS_HASH_PRF_DATA_LEN_SHA256_32); /* Calculate hash. */ ret = wc_Sha256Final(&state->digest.sha256, bm0); } /* Calculate n-byte mask - BM_1. */ if (ret == 0) { addr_buf[XMSS_ADDR_KEY_MASK * 4 + 3] = 2; /* Copy back state after first 64 bytes. */ XMSS_SHA256_STATE_RESTORE_DATA(state, addr_buf, WC_XMSS_ADDR_LEN, XMSS_HASH_PRF_DATA_LEN_SHA256_32); /* Calculate hash. */ ret = wc_Sha256Final(&state->digest.sha256, bm1); } if (ret == 0) { XMSS_PAD_ENC(XMSS_HASH_PADDING_H, pad, XMSS_SHA256_32_PAD_LEN); /* XOR into bm0 and bm1. */ XMEMCPY(state->prf_buf, left, XMSS_SHA256_32_N); XMEMCPY(state->prf_buf + XMSS_SHA256_32_N, right, XMSS_SHA256_32_N); xorbuf(bm0, state->prf_buf, 2 * XMSS_SHA256_32_N); ret = wc_Sha256Update(&state->digest.sha256, state->buf, XMSS_RAND_HASH_DATA_LEN_SHA256_32); } if (ret == 0) { ret = wc_Sha256Final(&state->digest.sha256, hash); } if (state->ret == 0) { /* Store any digest failures for public APIs to return. */ state->ret = ret; } #else /* Encode padding byte for PRF. */ XMSS_PAD_ENC(XMSS_HASH_PADDING_PRF, state->prf_buf, XMSS_SHA256_32_PAD_LEN); /* Append public seed for PRF. */ XMEMCPY(state->prf_buf + XMSS_SHA256_32_PAD_LEN, pk_seed, XMSS_SHA256_32_N); /* Set key mask to initial value and append encoding. */ addr[XMSS_ADDR_KEY_MASK] = 0; wc_xmss_addr_encode(addr, addr_buf); /* Calculate n-byte key - KEY. */ wc_xmss_hash(state, state->prf_buf, XMSS_HASH_PRF_DATA_LEN_SHA256_32, key); /* Calculate n-byte mask - BM_0. */ addr_buf[XMSS_ADDR_KEY_MASK * 4 + 3] = 1; wc_xmss_hash(state, state->prf_buf, XMSS_HASH_PRF_DATA_LEN_SHA256_32, bm0); /* Calculate n-byte mask - BM_1. */ addr_buf[XMSS_ADDR_KEY_MASK * 4 + 3] = 2; wc_xmss_hash(state, state->prf_buf, XMSS_HASH_PRF_DATA_LEN_SHA256_32, bm1); XMSS_PAD_ENC(XMSS_HASH_PADDING_H, state->buf, XMSS_SHA256_32_PAD_LEN); XMEMCPY(state->prf_buf, left, XMSS_SHA256_32_N); XMEMCPY(state->prf_buf + XMSS_SHA256_32_N, right, XMSS_SHA256_32_N); xorbuf(bm0, state->prf_buf, 2 * XMSS_SHA256_32_N); wc_xmss_hash(state, state->buf, XMSS_RAND_HASH_DATA_LEN_SHA256_32, hash); #endif /* WC_XMSS_FULL_HASH */ } #endif /* !WOLFSSL_WC_XMSS_SMALL && WC_XMSS_SHA256 */ /* Randomized tree hashing - left and right separate parameters. * * RFC 8391: 4.1.4, Algorithm 7: RAND_HASH * ... * ADRS.setKeyAndMask(0); * KEY = PRF(SEED, ADRS); * ADRS.setKeyAndMask(1); * BM_0 = PRF(SEED, ADRS); * ADRS.setKeyAndMask(2); * BM_1 = PRF(SEED, ADRS); * return H(KEY, (LEFT XOR BM_0) || (RIGHT XOR BM_1)); * * @param [in] state XMSS/MT state including digest and parameters. * @param [in] left First half of data. * @param [in] right Second half of data. * @param [in] pk_seed Random public seed. * @param [in] addr Hash address. * @param [out] hash Buffer to hold hash. */ static void wc_xmss_rand_hash_lr(XmssState* state, const byte* left, const byte* right, const byte* pk_seed, HashAddress addr, byte* hash) { const XmssParams* params = state->params; #if !defined(WOLFSSL_WC_XMSS_SMALL) && defined(WC_XMSS_SHA256) if ((params->pad_len == XMSS_SHA256_32_PAD_LEN) && (params->n == XMSS_SHA256_32_N) && (params->hash == WC_HASH_TYPE_SHA256)) { wc_xmss_rand_hash_lr_sha256_32(state, left, right, pk_seed, addr, hash); } else #endif /* !WOLFSSL_WC_XMSS_SMALL && WC_XMSS_SHA256 */ { byte* addr_buf = state->prf_buf + params->pad_len + params->n; /* Offsets into rand hash data. */ byte* pad = state->buf; byte* key = pad + params->pad_len; byte* bm0 = key + params->n; byte* bm1 = bm0 + params->n; const word32 len = XMSS_HASH_PRF_DATA_LEN(params); /* Encode padding byte for PRF. */ XMSS_PAD_ENC(XMSS_HASH_PADDING_PRF, state->prf_buf, params->pad_len); /* Append public seed for PRF. */ XMEMCPY(state->prf_buf + params->pad_len, pk_seed, params->n); /* Set key mask to initial value and append encoding. */ addr[XMSS_ADDR_KEY_MASK] = 0; wc_xmss_addr_encode(addr, addr_buf); /* Calculate n-byte key - KEY. */ wc_xmss_hash(state, state->prf_buf, len, key); /* Calculate n-byte mask - BM_0. */ addr_buf[XMSS_ADDR_KEY_MASK * 4 + 3] = 1; wc_xmss_hash(state, state->prf_buf, len, bm0); /* Calculate n-byte mask - BM_1. */ addr_buf[XMSS_ADDR_KEY_MASK * 4 + 3] = 2; wc_xmss_hash(state, state->prf_buf, len, bm1); XMSS_PAD_ENC(XMSS_HASH_PADDING_H, pad, params->pad_len); XMEMCPY(state->prf_buf, left, params->n); XMEMCPY(state->prf_buf + params->n, right, params->n); xorbuf(bm0, state->prf_buf, 2U * params->n); wc_xmss_hash(state, state->buf, XMSS_RAND_HASH_DATA_LEN(params), hash); } } #endif /* !WOLFSSL_WC_XMSS_SMALL || WOLFSSL_XMSS_VERIFY_ONLY */ /* Compute message hash from the random r, root, index and message. * * RFC 8391: 4.1.9, Algorithm 12: XMSS_sign * ... * byte[n] M' = H_msg(r || getRoot(SK) || (toByte(idx_sig, n)), M); * RFC 8391: 5.1 * H_msg: SHA2-256(toByte(2, 32) || KEY || M) * H_msg: SHA2-512(toByte(2, 64) || KEY || M) * H_msg: SHAKE128(toByte(2, 32) || KEY || M, 256) * H_msg: SHAKE256(toByte(2, 64) || KEY || M, 512) * * @param [in] state XMSS/MT state including digest and parameters. * @param [in] random Random value of n bytes. * @param [in] root Public root. * @param [in] idx Buffer holding encoded index. * @param [in] idx_len Length of encoded index in bytes. * @param [in] m Message to hash. * @param [in] mlen Length of message. * @param [out] hash Buffer to hold hash. */ static void wc_xmss_hash_message(XmssState* state, const byte* random, const byte* root, const byte* idx, word8 idx_len, const byte* m, word32 mlen, byte* hash) { int ret; const XmssParams* params = state->params; word32 padKeyLen = XMSS_RAND_HASH_DATA_LEN(params); /* Offsets into message hash data. */ byte* padKey = state->buf; byte* pad = padKey; byte* key = pad + params->pad_len; byte* root_sk = key + params->n; byte* idx_sig = root_sk + params->n; /* idx_len encodes a leaf number (4 or 8 bytes per RFC 8391) and is * front-padded into an n-byte field. n >= 24 for every supported * parameter set, so idx_len <= n always holds in valid params, but * guard explicitly: if the invariant is ever violated, the (word32) * cast on the subtraction would otherwise produce an around 4 GB * XMEMSET. */ if (idx_len > params->n) { state->ret = WC_FAILURE; return; } /* Set prefix data before message. */ XMSS_PAD_ENC(XMSS_HASH_PADDING_HASH, pad, params->pad_len); XMEMCPY(key, random, params->n); XMEMCPY(root_sk, root, params->n); XMEMSET(idx_sig, 0, (word32)(params->n - idx_len)); XMEMCPY(idx_sig + params->n - idx_len, idx, idx_len); /* Hash the padding and key first. */ #ifdef WC_XMSS_SHA256 if (params->hash == WC_HASH_TYPE_SHA256) { ret = wc_Sha256Update(&state->digest.sha256, padKey, padKeyLen); } else #endif /* WC_XMSS_SHA256 */ #ifdef WC_XMSS_SHA512 if (params->hash == WC_HASH_TYPE_SHA512) { ret = wc_Sha512Update(&state->digest.sha512, padKey, padKeyLen); } else #endif /* WC_XMSS_SHA512 */ #ifdef WC_XMSS_SHAKE128 if (params->hash == WC_HASH_TYPE_SHAKE128) { ret = wc_Shake128_Update(&state->digest.shake, padKey, padKeyLen); } else #endif /* WC_XMSS_SHAKE128 */ #ifdef WC_XMSS_SHAKE256 if (params->hash == WC_HASH_TYPE_SHAKE256) { ret = wc_Shake256_Update(&state->digest.shake, padKey, padKeyLen); } else #endif /* WC_XMSS_SHAKE256 */ { /* Unsupported digest function. */ ret = NOT_COMPILED_IN; } if (ret == 0) { /* Generate hash of message - M'. */ wc_xmss_hash(state, m, mlen, hash); } else if (state->ret == 0) { /* Store any digest failures for public APIs to return. */ state->ret = ret; } } #ifndef WOLFSSL_XMSS_VERIFY_ONLY /* Compute PRF with key and message. * * RFC 8391: 5.1 * PRF: SHA2-256(toByte(3, 32) || KEY || M) * PRF: SHA2-512(toByte(3, 64) || KEY || M) * PRF: SHAKE128(toByte(3, 32) || KEY || M, 256) * PRF: SHAKE256(toByte(3, 64) || KEY || M, 512) * * @param [in] state XMSS/MT state including digest and parameters. * @param [in] key Key used to derive pseudo-random from. * @param [in] m 32 bytes of data to derive pseudo-random from. * @param [out] prf Buffer to hold pseudo-random data. */ static void wc_xmss_prf(XmssState* state, const byte* key, const byte* m, byte* prf) { const XmssParams* params = state->params; byte* pad = state->prf_buf; byte* key_buf = pad + params->pad_len; byte* m_buf = key_buf + params->n; /* 00[0..pl-1] || 03 || key[0..n-1] || m[0..31] */ XMSS_PAD_ENC(XMSS_HASH_PADDING_PRF, pad, params->pad_len); XMEMCPY(key_buf, key, params->n); XMEMCPY(m_buf, m, XMSS_PRF_M_LEN); /* Hash the PRF data. */ wc_xmss_hash(state, state->prf_buf, (word32)params->pad_len + params->n + XMSS_PRF_M_LEN, prf); } #ifdef XMSS_CALL_PRF_KEYGEN /* Compute PRF for keygen with key and message. * * NIST SP 800-208: 5.1, 5.2, 5.3, 5.4 * PRFkeygen (KEY, M): SHA-256(toByte(4, 32) || KEY || M) * PRFkeygen (KEY, M): T192(SHA-256(toByte(4, 4) || KEY || M)) * PRFkeygen (KEY, M): SHAKE256(toByte(4, 32) || KEY || M, 256) * PRFkeygen (KEY, M): SHAKE256(toByte(4, 4) || KEY || M, 192) * * @param [in] state XMSS/MT state including digest and parameters. * @param [in] key Key of n bytes used to derive pseudo-random from. * @param [in] m n + 32 bytes of data to derive pseudo-random from. * @param [out] prf Buffer to hold pseudo-random data. */ static void wc_xmss_prf_keygen(XmssState* state, const byte* key, const byte* m, byte* prf) { const XmssParams* params = state->params; byte* pad = state->prf_buf; byte* key_buf = pad + params->pad_len; byte* m_buf = key_buf + params->n; /* 00[0..pl-1] || 04 || key[0..n-1] || m[0..n+31] */ XMSS_PAD_ENC(XMSS_HASH_PADDING_PRF_KEYGEN, pad, params->pad_len); XMEMCPY(key_buf, key, params->n); XMEMCPY(m_buf, m, params->n + XMSS_PRF_M_LEN); /* Hash the PRF keygen data. */ wc_xmss_hash(state, state->prf_buf, params->pad_len + 2 * params->n + XMSS_PRF_M_LEN, prf); } #endif /* XMSS_CALL_PRF_KEYGEN */ #endif /* !WOLFSSL_XMSS_VERIFY_ONLY */ /******************************************** * WOTS ********************************************/ #ifndef WOLFSSL_XMSS_VERIFY_ONLY #if !defined(WOLFSSL_WC_XMSS_SMALL) && defined(WC_XMSS_SHA256) /* Expand private seed with PRF keygen. * * RFC 8391: 4.1.3 * "the existence of a method getWOTS_SK(SK, i) is assumed" * NIST SP 800-208: 7.2.1, Algorithm 10' * ... * for ( j=0; j < len; j++) { * ADRS.setChainAddress(j); * sk[j] = PRFkeygen(S_XMSS, SEED || ADRS); * } * * @param [in] state XMSS/MT state including digest and parameters. * @param [in] sk_seed Buffer holding private seed. * @param [in] pk_seed Random public seed. * @param [in] addr Hash address as a byte array. * @param [out] gen_seed Buffer to hold seeds. */ static void wc_xmss_wots_get_wots_sk_sha256_32(XmssState* state, const byte* sk_seed, const byte* pk_seed, byte* addr, byte* gen_seed) { const XmssParams* params = state->params; word32 i; byte* pad = state->prf_buf; byte* s_xmss = pad + XMSS_SHA256_32_PAD_LEN; byte* seed = s_xmss + XMSS_SHA256_32_N; byte* addr_buf = seed + XMSS_SHA256_32_N; int ret; ((word32*)addr)[XMSS_ADDR_CHAIN] = 0; ((word32*)addr)[XMSS_ADDR_HASH] = 0; ((word32*)addr)[XMSS_ADDR_KEY_MASK] = 0; XMSS_PAD_ENC(XMSS_HASH_PADDING_PRF_KEYGEN, pad, XMSS_SHA256_32_PAD_LEN); XMEMCPY(s_xmss, sk_seed, XMSS_SHA256_32_N); XMEMCPY(seed, pk_seed, XMSS_SHA256_32_N); XMEMCPY(addr_buf, addr, WC_XMSS_ADDR_LEN); #ifndef WC_XMSS_FULL_HASH ret = wc_Sha256Update(&state->digest.sha256, pad, XMSS_SHA256_32_PAD_LEN + XMSS_SHA256_32_N); if (ret == 0) { /* Copy state after first 64 bytes. */ XMSS_SHA256_STATE_CACHE(state); ret = wc_Sha256Update(&state->digest.sha256, seed, XMSS_SHA256_32_N + WC_XMSS_ADDR_LEN); } if (ret == 0) { ret = wc_Sha256Final(&state->digest.sha256, gen_seed); } for (i = 1; (ret == 0) && (i < params->wots_len); i++) { gen_seed += XMSS_SHA256_32_N; addr_buf[XMSS_ADDR_CHAIN * 4 + 3] = (byte)i; XMSS_SHA256_STATE_RESTORE(state, 64); ret = wc_Sha256Update(&state->digest.sha256, seed, XMSS_SHA256_32_N + WC_XMSS_ADDR_LEN); if (ret == 0) { ret = wc_Sha256Final(&state->digest.sha256, gen_seed); } } #else ret = wc_Sha256Update(&state->digest.sha256, state->prf_buf, XMSS_SHA256_32_PAD_LEN + 2 * XMSS_SHA256_32_N + WC_XMSS_ADDR_LEN); if (ret == 0) { ret = wc_Sha256Final(&state->digest.sha256, gen_seed); } for (i = 1; (ret == 0) && i < params->wots_len; i++) { gen_seed += XMSS_SHA256_32_N; addr_buf[XMSS_ADDR_CHAIN * 4 + 3] = (byte)i; ret = wc_Sha256Update(&state->digest.sha256, state->prf_buf, XMSS_SHA256_32_PAD_LEN + 2 * XMSS_SHA256_32_N + WC_XMSS_ADDR_LEN); if (ret == 0) { ret = wc_Sha256Final(&state->digest.sha256, gen_seed); } } #endif /* WC_XMSS_FULL_HASH*/ if (state->ret == 0) { /* Store any digest failures for public APIs to return. */ state->ret = ret; } } #endif /* !WOLFSSL_WC_XMSS_SMALL && WC_XMSS_SHA256 */ /* Expand private seed with PRF keygen. * * RFC 8391: 4.1.3 * "the existence of a method getWOTS_SK(SK, i) is assumed" * NIST SP 800-208: 7.2.1 * Algorithm 10' * ... * for ( j=0; j < len; j++) { * ADRS.setChainAddress(j); * sk[j] = PRFkeygen(S_XMSS, SEED || ADRS); * } * * @param [in] state XMSS/MT state including digest and parameters. * @param [in] sk_seed Buffer holding private seed. * @param [in] pk_seed Random public seed. * @param [in] addr Hash address as a byte array. * @param [out] gen_seed Buffer to hold seeds. */ static void wc_xmss_wots_get_wots_sk(XmssState* state, const byte* sk_seed, const byte* pk_seed, byte* addr, byte* gen_seed) { const XmssParams* params = state->params; word32 i; #ifdef XMSS_CALL_PRF_KEYGEN byte* seed = state->buf; byte* addr_buf = seed + params->n; #else byte* pad = state->prf_buf; byte* s_xmss = pad + params->pad_len; byte* seed = s_xmss + params->n; byte* addr_buf = seed + params->n; const word32 len = (word32)params->pad_len + params->n * 2U + WC_XMSS_ADDR_LEN; #endif /* XMSS_CALL_PRF_KEYGEN */ /* Ensure hash address fields are 0. */ ((word32*)addr)[XMSS_ADDR_CHAIN] = 0; ((word32*)addr)[XMSS_ADDR_HASH] = 0; ((word32*)addr)[XMSS_ADDR_KEY_MASK] = 0; #ifdef XMSS_CALL_PRF_KEYGEN /* Copy the seed and address into PRF keygen message buffer. */ XMEMCPY(seed, pk_seed, params->n); XMEMCPY(addr_buf, addr, WC_XMSS_ADDR_LEN); wc_xmss_prf_keygen(state, sk_seed, state->buf, gen_seed); for (i = 1; i < params->wots_len; i++) { gen_seed += params->n; addr_buf[XMSS_ADDR_CHAIN * 4 + 3] = (byte)i; wc_xmss_prf_keygen(state, sk_seed, state->buf, gen_seed); } #else /* Copy the PRF keygen fields into one buffer. */ XMSS_PAD_ENC(XMSS_HASH_PADDING_PRF_KEYGEN, pad, params->pad_len); XMEMCPY(s_xmss, sk_seed, params->n); XMEMCPY(seed, pk_seed, params->n); XMEMCPY(addr_buf, addr, WC_XMSS_ADDR_LEN); /* Fill output with hashes of different chain hash addresses. */ wc_xmss_hash(state, state->prf_buf, len, gen_seed); for (i = 1; i < params->wots_len; i++) { gen_seed += params->n; addr_buf[XMSS_ADDR_CHAIN * 4 + 3] = (byte)i; wc_xmss_hash(state, state->prf_buf, len, gen_seed); } #endif /* XMSS_CALL_PRF_KEYGEN */ } #endif /* !WOLFSSL_XMSS_VERIFY_ONLY */ #if !defined(WOLFSSL_WC_XMSS_SMALL) && defined(WC_XMSS_SHA256) /* Chain hashing to calculate node hash. * * RFC 8391: 3.1.2, Algorithm 2 - recursive. * This function is an iterative version. * * @param [in] state XMSS/MT state including digest and parameters. * @param [in] data Initial data to hash. * @param [in] start Starting hash value in hash address. * @param [in] steps Size of step. * @param [in] pk_seed Random public seed. * @param [in] addr Hash address as a byte array. * @param [out] hash Chained hash. */ static void wc_xmss_chain_sha256_32(XmssState* state, const byte* data, unsigned int start, unsigned int steps, const byte* pk_seed, byte* addr, byte* hash) { if (steps > 0) { word32 i; byte* pad = state->prf_buf; byte* seed = pad + XMSS_SHA256_32_PAD_LEN; #ifndef WC_XMSS_FULL_HASH int ret; /* Set data for PRF hash. */ XMSS_PAD_ENC(XMSS_HASH_PADDING_PRF, pad, XMSS_SHA256_32_PAD_LEN); XMEMCPY(seed, pk_seed, XMSS_SHA256_32_N); /* Hash first 64 bytes. */ ret = wc_Sha256Update(&state->digest.sha256, state->prf_buf, XMSS_SHA256_32_PAD_LEN + XMSS_SHA256_32_N); if (ret == 0) { /* Copy state after first 64 bytes. */ XMSS_SHA256_STATE_CACHE(state); /* Only do this once for all chain hash calls. */ XMSS_PAD_ENC(XMSS_HASH_PADDING_F, state->buf, state->params->pad_len); /* Set address. */ XMSS_ADDR_SET_BYTE(addr, XMSS_ADDR_HASH, start); wc_xmss_chain_hash_sha256_32(state, data, addr, hash); /* Iterate 'steps' calls to the hash function. */ for (i = start+1; i < (start+steps) && i < XMSS_WOTS_W; i++) { addr[XMSS_ADDR_HASH * 4 + 3] = (byte)i; wc_xmss_chain_hash_sha256_32(state, hash, addr, hash); } } else if (state->ret == 0) { /* Store any digest failures for public APIs to return. */ state->ret = ret; } #else const XmssParams* params = state->params; byte* addr_buf = seed + XMSS_SHA256_32_N; /* Set data for PRF hash. */ XMSS_PAD_ENC(XMSS_HASH_PADDING_PRF, pad, XMSS_SHA256_32_PAD_LEN); XMEMCPY(seed, pk_seed, params->n); XMEMCPY(addr_buf, addr, WC_XMSS_ADDR_LEN); /* Only do this once for all chain hash calls. */ XMSS_PAD_ENC(XMSS_HASH_PADDING_F, state->buf, params->pad_len); /* Set address. */ XMSS_ADDR_SET_BYTE(addr_buf, XMSS_ADDR_HASH, start); wc_xmss_chain_hash_sha256_32(state, data, hash); /* Iterate 'steps' calls to the hash function. */ for (i = start+1; i < (start+steps) && i < XMSS_WOTS_W; i++) { addr_buf[XMSS_ADDR_HASH * 4 + 3] = (byte)i; wc_xmss_chain_hash_sha256_32(state, hash, hash); } #endif /* !WC_XMSS_FULL_HASH */ } else if (hash != data) { XMEMCPY(hash, data, XMSS_SHA256_32_N); } } #endif /* !WOLFSSL_WC_XMSS_SMALL && WC_XMSS_SHA256 */ /* Chain hashing to calculate node hash. * * RFC 8391: 3.1.2, Algorithm 2 - recursive. * This function is an iterative version. * * @param [in] state XMSS/MT state including digest and parameters. * @param [in] data Initial data to hash. * @param [in] start Starting hash value in hash address. * @param [in] steps Size of step. * @param [in] pk_seed Random public seed. * @param [in] addr Hash address as a byte array. * @param [out] hash Chained hash. */ static void wc_xmss_chain(XmssState* state, const byte* data, unsigned int start, unsigned int steps, const byte* pk_seed, byte* addr, byte* hash) { const XmssParams* params = state->params; if (steps > 0) { word32 i; byte* pad = state->prf_buf; byte* seed = pad + params->pad_len; byte* addr_buf = seed + params->n; /* Set data for PRF hash. */ XMSS_PAD_ENC(XMSS_HASH_PADDING_PRF, pad, params->pad_len); XMEMCPY(seed, pk_seed, params->n); XMEMCPY(addr_buf, addr, 32); /* Only do this once for all chain hash calls. */ XMSS_PAD_ENC(XMSS_HASH_PADDING_F, state->buf, params->pad_len); /* Set address. */ XMSS_ADDR_SET_BYTE(addr_buf, XMSS_ADDR_HASH, start); wc_xmss_chain_hash(state, data, hash); /* Iterate 'steps' calls to the hash function. */ for (i = start+1; i < (start+steps) && i < XMSS_WOTS_W; i++) { addr_buf[XMSS_ADDR_HASH * 4 + 3] = (byte)i; wc_xmss_chain_hash(state, hash, hash); } } else if (hash != data) { XMEMCPY(hash, data, params->n); } } /* Convert base on message and add checksum. * * RFC 8391:, 2.6, Algorithm 1: base_w * int in = 0; * int out = 0; * unsigned int total = 0; * int bits = 0; * int consumed; * * for ( consumed = 0; consumed < out_len; consumed++ ) { * if ( bits == 0 ) { * total = X[in]; * in++; * bits += 8; * } * bits -= lg(w); * basew[out] = (total >> bits) AND (w - 1); * out++; * } * return basew; * * base_w implemented for w == 16 (lg(w) == 4). * * RFC 8391: 3.1.5, Algorithm 5: * ... * csum = 0; * * # Convert message to base w * msg = base_w(M, w, len_1); * # Compute checksum * for ( i = 0; i < len_1; i++ ) { * csum = csum + w - 1 - msg[i]; * } * * # Convert csum to base w * csum = csum << ( 8 - ( ( len_2 * lg(w) ) % 8 )); * len_2_bytes = ceil( ( len_2 * lg(w) ) / 8 ); * msg = msg || base_w(toByte(csum, len_2_bytes), w, len_2); * * len_1 == 8 * n / 4 = n * 2 * Implemented for len_2 == 3 * * @param [in] m Message data. * @param [in] n Number of bytes in hash. * @param [out] msg Message in new base. */ static void wc_xmss_msg_convert(const byte* m, word8 n, word8* msg) { word8 i; /* csum is word16: the WOTS+ checksum below relies on arithmetic * wrapping at 2^16 (max accumulated value 1920 fits, but the algorithm * treats the field as a fixed-width 16-bit integer per RFC 8391 * Algorithm 7 step 4). */ word16 csum = 0; /* Split each full byte of m into two bytes of msg. */ for (i = 0; i < n; i++) { msg[0] = (word8)(m[i] >> 4); msg[1] = (word8)(m[i] & 0xf); csum = (word16)(csum + XMSS_WOTS_W - 1U - msg[0]); csum = (word16)(csum + XMSS_WOTS_W - 1U - msg[1]); msg += 2; } /* Append checksum to message. (Maximum value: 1920 = 64 * 2 * 15) */ msg[0] = (word8)( csum >> 8) ; msg[1] = (word8)((csum >> 4) & 0x0f); msg[2] = (word8)((csum ) & 0x0f); } #ifndef WOLFSSL_XMSS_VERIFY_ONLY /* WOTS+ generate public key with private seed. * * RFC 8391: 4.1.6, Algorithm 9: * ... * pk = WOTS_genPK (getWOTS_SK(SK, s + i), SEED, ADRS); * RFC 8391, 3.1.4, Algorithm 4: WOTS_genPK * ... * for ( i = 0; i < len; i++ ) { * ADRS.setChainAddress(i); * pk[i] = chain(sk[i], 0, w - 1, SEED, ADRS); * } * return pk; * * WOTS_genPK only used in Algorithm 9 and it is convenient to combine with * getWOTS_SK due to parameter specific implementations. * * @param [in] state XMSS/MT state including digest and parameters. * @param [in] sk Random private seed. * @param [in] seed Random public seed. * @param [in] addr Hashing address. * @param [out] pk Public key. */ static void wc_xmss_wots_gen_pk(XmssState* state, const byte* sk, const byte* seed, HashAddress addr, byte* pk) { const XmssParams* params = state->params; byte* addr_buf = state->encMsg; word32 i; /* Ensure chain address is 0 and encode into a buffer. */ addr[XMSS_ADDR_CHAIN] = 0; wc_xmss_addr_encode(addr, addr_buf); #if !defined(WOLFSSL_WC_XMSS_SMALL) && defined(WC_XMSS_SHA256) if ((params->pad_len == XMSS_SHA256_32_PAD_LEN) && (params->n == XMSS_SHA256_32_N) && (params->hash == WC_HASH_TYPE_SHA256)) { /* Expand the private seed - getWOTS_SK */ wc_xmss_wots_get_wots_sk_sha256_32(state, sk, seed, addr_buf, pk); /* Calculate chain hash. */ wc_xmss_chain_sha256_32(state, pk, 0, XMSS_WOTS_W - 1, seed, addr_buf, pk); for (i = 1; i < params->wots_len; i++) { pk += params->n; addr_buf[XMSS_ADDR_CHAIN * 4 + 3] = (byte)i; wc_xmss_chain_sha256_32(state, pk, 0, XMSS_WOTS_W - 1, seed, addr_buf, pk); } } else #endif /* !WOLFSSL_WC_XMSS_SMALL && WC_XMSS_SHA256 */ { /* Expand the private seed - getWOTS_SK */ wc_xmss_wots_get_wots_sk(state, sk, seed, addr_buf, pk); /* Calculate chain hash. */ wc_xmss_chain(state, pk, 0, XMSS_WOTS_W - 1, seed, addr_buf, pk); for (i = 1; i < params->wots_len; i++) { pk += params->n; addr_buf[XMSS_ADDR_CHAIN * 4 + 3] = (byte)i; wc_xmss_chain(state, pk, 0, XMSS_WOTS_W - 1, seed, addr_buf, pk); } } } /* Generate a signature from a privatge key and message. * * RFC 8391: 4.1.9, Algorithm 11: treeSig * sig_ots = WOTS_sign(getWOTS_SK(SK, idx_sig), * M', getSEED(SK), ADRS); * RFC 8391: 3.1.5, Algorithm 5: WOTS_sign * (Convert message to base w and append checksum in base w) * ... * for ( i = 0; i < len; i++ ) { * ADRS.setChainAddress(i); * sig[i] = chain(sk[i], 0, msg[i], SEED, ADRS); * } * return sig; * * WOTS_sign only used in Algorithm 11 and convenient to do getWOTS_SK due to * hash address reuse and parameter specific implementations. * * @param [in] state XMSS/MT state including digest and parameters. * @param [in] m Message hash to sign. * @param [in] sk Random private seed. * @param [in] seed Random public seed. * @param [in] addr Hashing address. * @param [out] sig Calculated XMSS/MT signature. */ static void wc_xmss_wots_sign(XmssState* state, const byte* m, const byte* sk, const byte* seed, HashAddress addr, byte* sig) { const XmssParams* params = state->params; byte* addr_buf = state->pk; word32 i; /* Convert message to base w and append checksum in base w. */ wc_xmss_msg_convert(m, params->n, state->encMsg); /* Set initial chain value and encode hash address. */ addr[XMSS_ADDR_CHAIN] = 0; wc_xmss_addr_encode(addr, addr_buf); #if !defined(WOLFSSL_WC_XMSS_SMALL) && defined(WC_XMSS_SHA256) if ((params->pad_len == XMSS_SHA256_32_PAD_LEN) && (params->n == XMSS_SHA256_32_N) && (params->hash == WC_HASH_TYPE_SHA256)) { /* Expand the private seed - getWOTS_SK */ wc_xmss_wots_get_wots_sk_sha256_32(state, sk, seed, addr_buf, sig); /* Calculate chain hash. */ wc_xmss_chain_sha256_32(state, sig, 0, state->encMsg[0], seed, addr_buf, sig); for (i = 1; i < params->wots_len; i++) { sig += params->n; addr_buf[XMSS_ADDR_CHAIN * 4 + 3] = (byte)i; wc_xmss_chain_sha256_32(state, sig, 0, state->encMsg[i], seed, addr_buf, sig); } } else #endif /* !WOLFSSL_WC_XMSS_SMALL && WC_XMSS_SHA256 */ { /* Expand the private seed - getWOTS_SK */ wc_xmss_wots_get_wots_sk(state, sk, seed, addr_buf, sig); /* Calculate chain hash. */ wc_xmss_chain(state, sig, 0, state->encMsg[0], seed, addr_buf, sig); for (i = 1; i < params->wots_len; i++) { sig += params->n; addr_buf[XMSS_ADDR_CHAIN * 4 + 3] = (byte)i; wc_xmss_chain(state, sig, 0, state->encMsg[i], seed, addr_buf, sig); } } } #endif /* !WOLFSSL_XMSS_VERIFY_ONLY */ /* Compute WOTS+ public key value from signature and message. * * RFC 8319: 3.1.6 * Algorithm 6: WOTS_pkFromSig * (Convert message to base w and append checksum in base w) * ... * for ( i = 0; i < len; i++ ) { * ADRS.setChainAddress(i); * tmp_pk[i] = chain(sig[i], msg[i], w - 1 - msg[i], SEED, ADRS); * } * return tmp_pk; * * @param [in] state XMSS/MT state including digest and parameters. * @param [in] sig XMSS/MT Signature. * @param [in] m Message to verify. * @param [in] seed Random public seed. * @param [in] addr Hashing address. * @param [out] pk Public key. */ static void wc_xmss_wots_pk_from_sig(XmssState* state, const byte* sig, const byte* m, const byte* seed, HashAddress addr, byte* pk) { const XmssParams* params = state->params; byte* addr_buf = state->stack; word32 i; /* Convert message to base w and append checksum in base w. */ wc_xmss_msg_convert(m, params->n, state->encMsg); /* Start with address with chain value of 0. */ addr[XMSS_ADDR_CHAIN] = 0; wc_xmss_addr_encode(addr, addr_buf); #if !defined(WOLFSSL_WC_XMSS_SMALL) && defined(WC_XMSS_SHA256) if ((params->pad_len == XMSS_SHA256_32_PAD_LEN) && (params->n == XMSS_SHA256_32_N) && (params->hash == WC_HASH_TYPE_SHA256)) { /* Calculate chain hash. */ wc_xmss_chain_sha256_32(state, sig, state->encMsg[0], XMSS_WOTS_W - 1 - state->encMsg[0], seed, addr_buf, pk); for (i = 1; i < params->wots_len; i++) { sig += params->n; pk += params->n; /* Update chain. */ addr_buf[XMSS_ADDR_CHAIN * 4 + 3] = (byte)i; wc_xmss_chain_sha256_32(state, sig, state->encMsg[i], XMSS_WOTS_W - 1 - state->encMsg[i], seed, addr_buf, pk); } } else #endif /* !WOLFSSL_WC_XMSS_SMALL && WC_XMSS_SHA256 */ { /* Calculate chain hash. */ wc_xmss_chain(state, sig, state->encMsg[0], XMSS_WOTS_W - 1 - state->encMsg[0], seed, addr_buf, pk); for (i = 1; i < params->wots_len; i++) { sig += params->n; pk += params->n; /* Update chain. */ addr_buf[XMSS_ADDR_CHAIN * 4 + 3] = (byte)i; wc_xmss_chain(state, sig, state->encMsg[i], XMSS_WOTS_W - 1 - state->encMsg[i], seed, addr_buf, pk); } } } /******************************************** * L-TREE - unbalanced binary hash tree ********************************************/ /* Compute leaves of L-tree from WOTS+ public key and compress to single value. * * RFC 8391: 4.1.5, Algorithm 8: ltree * unsigned int len' = len; * ADRS.setTreeHeight(0); * while ( len' > 1 ) { * for ( i = 0; i < floor(len' / 2); i++ ) { * ADRS.setTreeIndex(i); * pk[i] = RAND_HASH(pk[2i], pk[2i + 1], SEED, ADRS); * } * if ( len' % 2 == 1 ) { * pk[floor(len' / 2)] = pk[len' - 1]; * } * len' = ceil(len' / 2); * ADRS.setTreeHeight(ADRS.getTreeHeight() + 1); * } * return pk[0]; * * @param [in] state XMSS/MT state including digest and parameters. * @param [in] pk WOTS+ public key. * @param [in] seed Random public seed. * @param [in] addr Hashing address. * @param [out] pk0 N-byte compressed public key value pk[0]. */ static void wc_xmss_ltree(XmssState* state, byte* pk, const byte* seed, HashAddress addr, byte* pk0) { const XmssParams* params = state->params; word8 len = params->wots_len; word32 h = 0; #if !defined(WOLFSSL_WC_XMSS_SMALL) && defined(WC_XMSS_SHA256) && \ !defined(WC_XMSS_FULL_HASH) /* Precompute hash state after first 64 bytes (common to all hashes). */ if ((params->pad_len == XMSS_SHA256_32_PAD_LEN) && (params->n == XMSS_SHA256_32_N) && (params->hash == WC_HASH_TYPE_SHA256)) { byte* prf_buf = state->prf_buf; int ret; XMSS_PAD_ENC(XMSS_HASH_PADDING_PRF, prf_buf, XMSS_SHA256_32_PAD_LEN); XMEMCPY(prf_buf + XMSS_SHA256_32_PAD_LEN, seed, XMSS_SHA256_32_N); ret = wc_Sha256Update(&state->digest.sha256, prf_buf, XMSS_SHA256_32_PAD_LEN + XMSS_SHA256_32_N); if (ret == 0) { /* Copy state after first 64 bytes. */ XMSS_SHA256_STATE_CACHE(state); } else if (state->ret == 0) { /* Store any digest failures for public APIs to return. */ state->ret = ret; } } #endif /* !WOLFSSL_WC_XMSS_SMALL && WC_XMSS_SHA256 && !WC_XMSS_FULL_HASH */ while (len > 1) { word8 i; word8 len2 = len >> 1; addr[XMSS_ADDR_TREE_HEIGHT] = h++; for (i = 0; i < len2; i++) { addr[XMSS_ADDR_TREE_INDEX] = i; #if !defined(WOLFSSL_WC_XMSS_SMALL) && defined(WC_XMSS_SHA256) && \ !defined(WC_XMSS_FULL_HASH) if ((params->pad_len == XMSS_SHA256_32_PAD_LEN) && (params->n == XMSS_SHA256_32_N) && (params->hash == WC_HASH_TYPE_SHA256)) { wc_xmss_rand_hash_sha256_32_prehash(state, pk + i * 2 * XMSS_SHA256_32_N, addr, pk + i * XMSS_SHA256_32_N); } else #endif /* !WOLFSSL_WC_XMSS_SMALL && WC_XMSS_SHA256 && * !WC_XMSS_FULL_HASH */ { wc_xmss_rand_hash(state, pk + i * 2 * params->n, seed, addr, pk + i * params->n); } } if (len & 1) { XMEMCPY(pk + len2 * params->n, pk + (len - 1) * params->n, params->n); } len = (word8)(len2 + (len & 1)); } /* Return compressed public key value pk[0]. */ XMEMCPY(pk0, pk, params->n); } #ifndef WOLFSSL_XMSS_VERIFY_ONLY #ifdef WOLFSSL_WC_XMSS_SMALL /******************************************** * TREE HASH ********************************************/ #ifndef WOLFSSL_SMALL_STACK /* Compute internal nodes of Merkle tree. * * Implementation always starts at index 0. (s = 0) * * Build authentication path, if required, rather than duplicating work. * When node is generated, copy out to authentication path array of nodes. * * RFC 8391: 4.1.6, Algorithm 9: treeHash * if( s % (1 << t) != 0 ) return -1; * for ( i = 0; i < 2^t; i++ ) { * SEED = getSEED(SK); * ADRS.setType(0); # Type = OTS hash address * ADRS.setOTSAddress(s + i); * pk = WOTS_genPK (getWOTS_SK(SK, s + i), SEED, ADRS); * ADRS.setType(1); # Type = L-tree address * ADRS.setLTreeAddress(s + i); * node = ltree(pk, SEED, ADRS); * ADRS.setType(2); # Type = hash tree address * ADRS.setTreeHeight(0); * ADRS.setTreeIndex(i + s); * while ( Top node on Stack has same height t' as node ) { * ADRS.setTreeIndex((ADRS.getTreeIndex() - 1) / 2); * node = RAND_HASH(Stack.pop(), node, SEED, ADRS); * ADRS.setTreeHeight(ADRS.getTreeHeight() + 1); * } * Stack.push(node); * } * return Stack.pop(); * RFC 8391: 4.1.9, (Example) buildAuth * for ( j = 0; j < h; j++ ) { * k = floor(i / (2^j)) XOR 1; * auth[j] = treeHash(SK, k * 2^j, j, ADRS); * } * * @param [in] state XMSS/MT state including digest and parameters. * @param [in] sk_seed Random private seed. * @param [in] pk_seed Random public seed. * @param [in] leafIdx Index of lead node. * @param [in] subtree_addr Address of subtree. * @param [out] root Root node of the tree. * @param [out] auth_path Nodes of the authentication path. */ static void wc_xmss_treehash(XmssState* state, const byte* sk_seed, const byte* pk_seed, word32 leafIdx, const word32* subtree, byte* root, byte* auth_path) { const XmssParams* params = state->params; const word8 n = params->n; byte* node = state->stack; HashAddress ots; HashAddress ltree; HashAddress tree; word8 height[WC_XMSS_MAX_TREE_HEIGHT + 1]; word8 offset = 0; word32 max = (word32)1U << params->sub_h; word32 i; /* Copy hash address into one for each purpose. */ XMSS_ADDR_OTS_SET_SUBTREE(ots, subtree); XMSS_ADDR_LTREE_SET_SUBTREE(ltree, subtree); XMSS_ADDR_TREE_SET_SUBTREE(tree, subtree); for (i = 0; i < max; i++) { word8 h; /* Calculate WOTS+ public key. */ ots[XMSS_ADDR_OTS] = i; wc_xmss_wots_gen_pk(state, sk_seed, pk_seed, ots, state->pk); /* Calculate public value. */ ltree[XMSS_ADDR_LTREE] = i; wc_xmss_ltree(state, state->pk, pk_seed, ltree, node); /* Initial height at this offset is 0. */ h = height[offset] = 0; /* Copy node, at height 0, out if on authentication path. */ if ((auth_path != NULL) && ((leafIdx ^ 0x1) == i)) { XMEMCPY(auth_path, node, n); } /* Top node on Stack has same height t' as node. */ while ((offset >= 1) && (h == height[offset - 1])) { word32 tree_idx = i >> (h + 1); node -= n; /* Calculate hash of node. */ tree[XMSS_ADDR_TREE_HEIGHT] = h; tree[XMSS_ADDR_TREE_INDEX] = tree_idx; wc_xmss_rand_hash(state, node, pk_seed, tree, node); /* Update offset and height. */ offset--; h = ++height[offset]; /* Copy node out if on authentication path. */ if ((auth_path != NULL) && (((leafIdx >> h) ^ 0x1) == tree_idx)) { XMEMCPY(auth_path + h * n, node, n); } } offset++; node += n; } /* Copy the root node. */ XMEMCPY(root, state->stack, n); } #else /* Compute internal nodes of Merkle tree. * * Implementation always starts at index 0. (s = 0) * * Build authentication path, if required, rather than duplicating work. * When node is generated, copy out to authentication path array of nodes. * * RFC 8391: 4.1.6, Algorithm 9: treeHash * if( s % (1 << t) != 0 ) return -1; * for ( i = 0; i < 2^t; i++ ) { * SEED = getSEED(SK); * ADRS.setType(0); # Type = OTS hash address * ADRS.setOTSAddress(s + i); * pk = WOTS_genPK (getWOTS_SK(SK, s + i), SEED, ADRS); * ADRS.setType(1); # Type = L-tree address * ADRS.setLTreeAddress(s + i); * node = ltree(pk, SEED, ADRS); * ADRS.setType(2); # Type = hash tree address * ADRS.setTreeHeight(0); * ADRS.setTreeIndex(i + s); * while ( Top node on Stack has same height t' as node ) { * ADRS.setTreeIndex((ADRS.getTreeIndex() - 1) / 2); * node = RAND_HASH(Stack.pop(), node, SEED, ADRS); * ADRS.setTreeHeight(ADRS.getTreeHeight() + 1); * } * Stack.push(node); * } * return Stack.pop(); * RFC 8391: 4.1.9, (Example) buildAuth * for ( j = 0; j < h; j++ ) { * k = floor(i / (2^j)) XOR 1; * auth[j] = treeHash(SK, k * 2^j, j, ADRS); * } * * @param [in] state XMSS/MT state including digest and parameters. * @param [in] sk_seed Random private seed. * @param [in] pk_seed Random public seed. * @param [in] leafIdx Index of lead node. * @param [in] subtree_addr Address of subtree. * @param [out] root Root node of the tree. * @param [out] auth_path Nodes of the authentication path. */ static void wc_xmss_treehash(XmssState* state, const byte* sk_seed, const byte* pk_seed, word32 leafIdx, const word32* subtree, byte* root, byte* auth_path) { const XmssParams* params = state->params; const word8 n = params->n; byte* node = state->stack; HashAddress addr; word8 height[WC_XMSS_MAX_TREE_HEIGHT + 1]; word8 offset = 0; word32 max = (word32)1U << params->sub_h; word32 i; XMSS_ADDR_SET_SUBTREE(addr, subtree, 0); for (i = 0; i < max; i++) { word8 h; /* Calculate WOTS+ public key. */ addr[XMSS_ADDR_TYPE] = WC_XMSS_ADDR_TYPE_OTS; addr[XMSS_ADDR_LTREE] = i; wc_xmss_wots_gen_pk(state, sk_seed, pk_seed, addr, state->pk); /* Calculate public value. */ addr[XMSS_ADDR_TYPE] = WC_XMSS_ADDR_TYPE_LTREE; wc_xmss_ltree(state, state->pk, pk_seed, addr, node); addr[XMSS_ADDR_TYPE] = WC_XMSS_ADDR_TYPE_TREE; addr[XMSS_ADDR_TREE_ZERO] = 0; /* Initial height at this offset is 0. */ h = height[offset] = 0; /* Copy node out if on authentication path. */ if ((auth_path != NULL) && ((leafIdx ^ 0x1) == i)) { XMEMCPY(auth_path, node, n); } /* Top node on Stack has same height t' as node. */ while ((offset >= 1) && (h == height[offset - 1])) { word32 tree_idx = i >> (h + 1); node -= n; /* Calculate hash of node. */ addr[XMSS_ADDR_TREE_HEIGHT] = h; addr[XMSS_ADDR_TREE_INDEX] = tree_idx; wc_xmss_rand_hash(state, node, pk_seed, addr, node); /* Update offset and height. */ offset--; h = ++height[offset]; /* Copy node out if on authentication path. */ if ((auth_path != NULL) && (((leafIdx >> h) ^ 0x1) == tree_idx)) { XMEMCPY(auth_path + h * n, node, n); } } offset++; node += n; /* Reset hash address ready for use as OTS and LTREE. */ addr[XMSS_ADDR_TREE_HEIGHT] = 0; addr[XMSS_ADDR_TREE_INDEX] = 0; } /* Copy the root node. */ XMEMCPY(root, state->stack, n); } #endif /* !WOLFSSL_SMALL_STACK */ /******************************************** * MAKE KEY ********************************************/ /* Derives XMSSMT (and XMSS) key pair from seeds. * * RFC 8391: 4.1.7, Algorithm 10: XMSS_keyGen. * ... * initialize SK_PRF with a uniformly random n-byte string; * setSK_PRF(SK, SK_PRF); * * # Initialization for common contents * initialize SEED with a uniformly random n-byte string; * setSEED(SK, SEED); * setWOTS_SK(SK, wots_sk)); * ADRS = toByte(0, 32); * root = treeHash(SK, 0, h, ADRS); * * SK = idx || wots_sk || SK_PRF || root || SEED; * PK = OID || root || SEED; * return (SK || PK); * * wots_sk, SK_PRF and SEED passed in as seed. * Store seed for wots_sk instead of generated wots_sk. * OID not stored in PK this is handled in upper layer. * * @param [in] state XMSS/MT state including digest and parameters. * @param [in] seed Random seeds. * @param [out] sk Secret/Private key. * @param [out] pk Public key. * @return 0 on success. * @return <0 on digest failure. */ int wc_xmssmt_keygen(XmssState* state, const unsigned char* seed, unsigned char* sk, unsigned char* pk) { const XmssParams* params = state->params; const word8 n = params->n; const byte* seed_priv = seed; const byte* seed_pub = seed + 2 * n; /* Offsets into secret/private key. */ byte* sk_idx = sk; byte* sk_seed = sk_idx + params->idx_len; byte* sk_pub = sk_seed + 2 * n; /* Offsets into public key. */ byte* pk_root = pk; byte* pk_seed = pk_root + n; /* Set first index to 0 in private key. */ XMEMSET(sk_idx, 0, params->idx_len); /* Set private key seed and private key for PRF in to private key. */ XMEMCPY(sk_seed, seed_priv, 2U * n); /* Set public key seed into public key. */ XMEMCPY(pk_seed, seed_pub, n); /* Set all address values to zero. */ XMEMSET(state->addr, 0, sizeof(HashAddress)); /* Set depth into address. */ state->addr[XMSS_ADDR_LAYER] = (word32)(params->d - 1); /* Compute root node into public key. */ wc_xmss_treehash(state, sk_seed, pk_seed, 0, state->addr, pk_root, NULL); /* Append public key (root node and public seed) to private key. */ XMEMCPY(sk_pub, pk_root, 2U * n); /* Return any errors that occurred during hashing. */ return state->ret; } /******************************************** * SIGN ********************************************/ /** * Sign message using XMSS/XMSS^MT. * * RFC 8391: 4.1.9, Algorithm 11: treeSig * auth = buildAuth(SK, idx_sig, ADRS); * ADRS.setType(0); # Type = OTS hash address * ADRS.setOTSAddress(idx_sig); * sig_ots = WOTS_sign(getWOTS_SK(SK, idx_sig), * M', getSEED(SK), ADRS); * Sig = sig_ots || auth; * return Sig; * RFC 8391: 4.2.4, Algorithm 16: XMSSMT_sign * # Init * ADRS = toByte(0, 32); * SEED = getSEED(SK_MT); * SK_PRF = getSK_PRF(SK_MT); * idx_sig = getIdx(SK_MT); * * # Update SK_MT * setIdx(SK_MT, idx_sig + 1); * * # Message compression * byte[n] r = PRF(SK_PRF, toByte(idx_sig, 32)); * byte[n] M' = H_msg(r || getRoot(SK_MT) || (toByte(idx_sig, n)), M); * * # Sign * Sig_MT = idx_sig; * unsigned int idx_tree * = (h - h / d) most significant bits of idx_sig; * unsigned int idx_leaf = (h / d) least significant bits of idx_sig; * SK = idx_leaf || getXMSS_SK(SK_MT, idx_tree, 0) || SK_PRF * || toByte(0, n) || SEED; * ADRS.setLayerAddress(0); * ADRS.setTreeAddress(idx_tree); * Sig_tmp = treeSig(M', SK, idx_leaf, ADRS); * Sig_MT = Sig_MT || r || Sig_tmp; * for ( j = 1; j < d; j++ ) { * root = treeHash(SK, 0, h / d, ADRS); * idx_leaf = (h / d) least significant bits of idx_tree; * idx_tree = (h - j * (h / d)) most significant bits of idx_tree; * SK = idx_leaf || getXMSS_SK(SK_MT, idx_tree, j) || SK_PRF * || toByte(0, n) || SEED; * ADRS.setLayerAddress(j); * ADRS.setTreeAddress(idx_tree); * Sig_tmp = treeSig(root, SK, idx_leaf, ADRS); * Sig_MT = Sig_MT || Sig_tmp; * } * return SK_MT || Sig_MT * * buildAuth from treeSig done inside treeHash as this is more efficient. * * @param [in] state XMSS/MT state including digest and parameters. * @param [in] m Buffer holding message. * @param [in] mlen Length of message in buffer. * @param [in, out] sk Secret/Private key. * @param [out] sig Signature. * @return 0 on success. * @return <0 on digest failure. */ int wc_xmssmt_sign(XmssState* state, const unsigned char* m, word32 mlen, unsigned char* sk, unsigned char* sig) { int ret = 0; const XmssParams* params = state->params; const word8 n = params->n; const word8 hs = params->sub_h; const word16 hsn = (word16)(hs * n); const byte* sk_seed = sk + params->idx_len; const byte* pk_seed = sk + params->idx_len + 3 * n; wc_Idx idx; byte* sig_r = sig + params->idx_len; byte root[WC_XMSS_MAX_N]; unsigned int i; WC_IDX_ZERO(idx); /* Set all address values to zero and set type to OTS. */ XMEMSET(state->addr, 0, sizeof(HashAddress)); state->addr[XMSS_ADDR_TYPE] = WC_XMSS_ADDR_TYPE_OTS; /* Copy the index into the signature data: Sig_MT = idx_sig. */ XMEMCPY(sig, sk, params->idx_len); /* Read index from the secret key. */ WC_IDX_DECODE(idx, params->idx_len, sk, ret); /* Validate index in secret key. */ if ((ret == 0) && (WC_IDX_INVALID(idx, params->idx_len, params->h))) { /* Set index to maximum value to distinguish from valid value. */ XMEMSET(sk, 0xFF, params->idx_len); /* Zeroize the secret key. */ ForceZero(sk + params->idx_len, params->sk_len - params->idx_len); ret = KEY_EXHAUSTED_E; } /* Update SK_MT */ if (ret == 0) { /* Increment the index in the secret key. */ wc_idx_update(sk, params->idx_len); } /* Message compression */ if (ret == 0) { const byte* sk_prf = sk + params->idx_len + n; /* byte[n] r = PRF(SK_PRF, toByte(idx_sig, 32)); */ wc_idx_copy(sig, params->idx_len, state->buf, XMSS_PRF_M_LEN); wc_xmss_prf(state, sk_prf, state->buf, sig_r); ret = state->ret; } if (ret == 0) { const byte* pub_root = sk + params->idx_len + 2 * n; /* byte[n] M' = H_msg(r || getRoot(SK_MT) || (toByte(idx_sig, n)), M); */ wc_xmss_hash_message(state, sig_r, pub_root, sig, params->idx_len, m, mlen, root); ret = state->ret; /* Place WOTS+ signatures after index and 'r'. */ sig += params->idx_len + n; } /* Sign. */ for (i = 0; (ret == 0) && (i < params->d); i++) { word32 idx_leaf = 0; /* Set layer, tree and OTS leaf index into hash address. */ state->addr[XMSS_ADDR_LAYER] = i; WC_IDX_SET_ADDR_TREE(idx, params->idx_len, hs, state->addr, idx_leaf); /* treeSig || treeHash = sig_ots || auth */ state->addr[XMSS_ADDR_OTS] = idx_leaf; /* Create WOTS+ signature for tree into signature (sig_ots). */ wc_xmss_wots_sign(state, root, sk_seed, pk_seed, state->addr, sig); ret = state->ret; if (ret == 0) { sig += params->wots_sig_len; /* Add authentication path (auth) and calc new root. */ wc_xmss_treehash(state, sk_seed, pk_seed, idx_leaf, state->addr, root, sig); ret = state->ret; sig += hsn; } } return ret; } #else /******************************************** * Fast C implementation ********************************************/ /* Tree hash data - needs to be unpacked from binary. */ typedef struct TreeHash { /* Next index to update in tree - max 20 bits. */ word32 nextIdx; /* Number of stack entries used by tree - 0... */ word8 used; /* Tree is finished. */ word8 completed; } TreeHash; /* BDS state. */ typedef struct BdsState { /* Stack of nodes - subtree height + 1 nodes. */ byte* stack; /* Height of stack node - subtree height + 1 of 0... */ byte* height; /* Authentication path for next index - subtree height nodes. */ byte* authPath; /* Hashes of nodes kept - subtree height / 2 nodes. */ byte* keep; /* Tree hash instances - subtree height minus K instances. */ byte* treeHash; /* Hashes of nodes for tree hash - one for each tree hash instance. */ byte* treeHashNode; /* Hashes of nodes to retain - based on K parameter. */ byte* retain; /* Next leaf to calculate - max 20 bits. */ word32 next; /* Current offset into stack - 0... */ word8 offset; } BdsState; /* Index to BDS state accounting for swapping. * * @param [in] idx Index of node. * @param [in] i Depth of tree. * @param [in] hs Height of subtree. * @param [in] d Depth/number of trees. * @return Index of working BDS state. */ #define BDS_IDX(idx, i, hs, d) \ ((word8)(((((idx) >> ((hs) * ((i) + 1))) & 1) == 0) ? (i) : ((d) + (i)))) /* Index to alternate BDS state accounting for swapping. * * @param [in] idx Index of node. * @param [in] i Depth of tree. * @param [in] hs Height of subtree. * @param [in] d Depth/number of trees. * @return Index of alternate BDS state. */ #define BDS_ALT_IDX(idx, i, hs, d) \ ((word8)(((((idx) >> ((hs) * ((i) + 1))) & 1) == 0) ? ((d) + (i)) : (i))) /******************************************** * Tree Hash APIs ********************************************/ /* Initialize the tree hash data at specified index for the BDS state. * * @param [in, out] bds BDS state. * @param [in] i Index of tree hash. */ static void wc_xmss_bds_state_treehash_init(BdsState* bds, word32 i) { byte* sk = bds->treeHash + i * 4U; c32to24(0, sk); sk[3] = 0 | (1U << 7); } /* Set next index into tree hash data at specified index for the BDS state. * * @param [in, out] bds BDS state. * @param [in] i Index of tree hash. * @param [in] nextIdx Next index for tree hash. */ static void wc_xmss_bds_state_treehash_set_next_idx(BdsState* bds, int i, word32 nextIdx) { byte* sk = bds->treeHash + i * 4; c32to24(nextIdx, sk); sk[3] = 0 | (0 << 7); } /* Mark tree hash, at specified index for the BDS state, as complete. * * @param [in, out] bds BDS state. * @param [in] i Index of tree hash. */ static void wc_xmss_bds_state_treehash_complete(BdsState* bds, int i) { byte* sk = bds->treeHash + i * 4; sk[3] |= 1 << 7; /* // NOLINT(clang-analyzer-core.NullDereference) */ } /* Get the tree hash data at specified index for the BDS state. * * @param [in] bds BDS state. * @param [in] i Index of tree hash. * @param [out] treeHash Tree hash instance to fill out. */ static void wc_xmss_bds_state_treehash_get(BdsState* bds, int i, TreeHash* treeHash) { byte* sk = bds->treeHash + i * 4; ato24(sk, &treeHash->nextIdx); treeHash->used = sk[3] & 0x7f; treeHash->completed = sk[3] >> 7; } /* Set the tree hash data at specified index for the BDS state. * * @param [in, out] bds BDS state. * @param [in] i Index of tree hash. * @param [in] treeHash Tree hash data. */ static void wc_xmss_bds_state_treehash_set(BdsState* bds, int i, TreeHash* treeHash) { byte* sk = bds->treeHash + i * 4; c32to24(treeHash->nextIdx, sk); sk[3] = (byte)(treeHash->used | (treeHash->completed << 7)); } /******************************************** * BDS State APIs ********************************************/ /* Allocate memory for BDS state. * * When using a static BDS state (XMSS) then pass in handle to data for bds. * * @param [in] params XMSS/MT parameters. * @param [in, out] bds Handle to BDS state. May be NULL if not allocated. * @return 0 on success. * @return MEMORY_E on dynamic memory allocation failure. */ static int wc_xmss_bds_state_alloc(const XmssParams* params, BdsState** bds, void* heap) { const word8 cnt = (word8)(2 * params->d - 1); int ret = 0; if (*bds == NULL) { /* Allocate memory for BDS states. */ *bds = (BdsState*)XMALLOC(sizeof(BdsState) * cnt, heap, DYNAMIC_TYPE_TMP_BUFFER); if (*bds == NULL) { ret = MEMORY_E; } else { XMEMSET(*bds, 0, sizeof(BdsState) * cnt); } } return ret; } /* Dispose of allocated memory associated with BDS state. * * @param [in] bds BDS state. * @param [in] heap Dynamic memory hint. */ static void wc_xmss_bds_state_free(BdsState* bds, void* heap) { /* BDS states was allocated - must free. */ XFREE(bds, heap, DYNAMIC_TYPE_TMP_BUFFER); } /* Load the BDS state from the secret/private key. * * @param [in] state XMSS/MT state including digest and parameters. * @param [in] sk Secret/private key. * @param [out] bds BDS states. * @param [out] wots_sigs WOTS signatures when XMSS^MT. */ static int wc_xmss_bds_state_load(const XmssState* state, byte* sk, BdsState* bds, byte** wots_sigs) { const XmssParams* params = state->params; const word8 n = params->n; const word8 hs = params->sub_h; const word8 hsk = (word8)(params->sub_h - params->bds_k); const word8 k = params->bds_k; const word32 retainLen = XMSS_RETAIN_LEN(k, n); int i; /* Skip past standard SK = idx || wots_sk || SK_PRF || root || SEED; */ sk += params->idx_len + 4 * n; if (2 * (int)params->d - 1 <= 0) return WC_FAILURE; for (i = 0; i < 2 * (int)params->d - 1; i++) { /* Set pointers into SK. */ bds[i].stack = sk; sk += (hs + 1) * n; bds[i].height = sk; sk += hs + 1; bds[i].authPath = sk; sk += hs * n; bds[i].keep = sk; sk += (hs >> 1) * n; bds[i].treeHash = sk; sk += hsk * 4; bds[i].treeHashNode = sk; sk += hsk * n; bds[i].retain = sk; sk += retainLen; /* Load values - big-endian encoded. */ ato24(sk, &bds[i].next); sk += 3; bds[i].offset = sk[0]; sk += 1; } if (wots_sigs != NULL) { *wots_sigs = sk; } return 0; } /* Store the BDS state into the secret/private key. * * @param [in] state XMSS/MT state including digest and parameters. * @param [in, out] sk Secret/private key. * @param [in] bds BDS states. */ static int wc_xmss_bds_state_store(const XmssState* state, byte* sk, BdsState* bds) { int i; const XmssParams* params = state->params; const word8 n = params->n; const word8 hs = params->sub_h; const word8 hsk = (word8)(params->sub_h - params->bds_k); const word8 k = params->bds_k; const word32 skip = (word32)((hs + 1) * n + /* BdsState.stack */ hs + 1 + /* BdsState.height */ hs * n + /* BdsState.authPath */ (hs >> 1) * n + /* BdsState.keep */ hsk * 4 + /* BdsState.treeHash */ hsk * n) + /* BdsState.treeHashNode */ XMSS_RETAIN_LEN(k, n); /* BdsState.retain */ /* Ignore standard SK = idx || wots_sk || SK_PRF || root || SEED; */ sk += params->idx_len + 4 * n; if (2 * (int)params->d - 1 <= 0) return WC_FAILURE; for (i = 0; i < 2 * (int)params->d - 1; i++) { /* Skip pointers into sk. */ sk += skip; /* Save values - big-endian encoded. */ c32to24(bds[i].next, sk); /* NOLINT(clang-analyzer-core.CallAndMessage) */ sk += 3; sk[0] = bds[i].offset; sk += 1; } return 0; } /******************************************** * BDS ********************************************/ /* Compute node at next index. * * RFC 8391: 4.1.6, Algorithm 9: treeHash * ... * ADRS.setType(0); # Type = OTS hash address * ADRS.setOTSAddress(s + i); * pk = WOTS_genPK (getWOTS_SK(SK, s + i), SEED, ADRS); * ADRS.setType(1); # Type = L-tree address * ADRS.setLTreeAddress(s + i); * node = ltree(pk, SEED, ADRS); * ADRS.setType(2); # Type = hash tree address * ADRS.setTreeHeight(0); * ADRS.setTreeIndex(i + s); * while ( Top node on Stack has same height t' as node ) { * ADRS.setTreeIndex((ADRS.getTreeIndex() - 1) / 2); * node = RAND_HASH(Stack.pop(), node, SEED, ADRS); * ADRS.setTreeHeight(ADRS.getTreeHeight() + 1); * } * Stack.push(node); * ... * * @param [in] state XMSS/MT state including digest and parameters. * @param [in] bds BDS state. * @param [in] sk_seed Random secret/private seed. * @param [in] pk_seed Random public seed. * @param [in] addr Hash address. * @param [out] root Root node. */ static void wc_xmss_bds_next_idx(XmssState* state, BdsState* bds, const byte* sk_seed, const byte* pk_seed, HashAddress addr, word32 i, word8* height, word8* offset, word8** sp) { const XmssParams* params = state->params; const word8 hs = params->sub_h; const word8 hsk = (word8)(params->sub_h - params->bds_k); const word8 n = params->n; word8 o = *offset; word8* node = *sp; word8 h; /* Calculate WOTS+ public key. */ addr[XMSS_ADDR_TYPE] = WC_XMSS_ADDR_TYPE_OTS; addr[XMSS_ADDR_OTS] = (word32)i; wc_xmss_wots_gen_pk(state, sk_seed, pk_seed, addr, state->pk); /* Calculate public value. */ addr[XMSS_ADDR_TYPE] = WC_XMSS_ADDR_TYPE_LTREE; wc_xmss_ltree(state, state->pk, pk_seed, addr, node); addr[XMSS_ADDR_TYPE] = WC_XMSS_ADDR_TYPE_TREE; addr[XMSS_ADDR_TREE_ZERO] = 0; /* Initial height at this offset is 0. */ h = height[o] = 0; /* HDSS, Section 4.5, 2: TREEHASH[h].push(v[h][3]) * Copy right node to tree hash nodes if second right node. */ if ((hsk > 0) && (i == 3)) { XMEMCPY(bds->treeHashNode, node + n, n); } /* Top node on Stack has same height t' as node. */ while ((o >= 1) && (h == height[o - 1])) { /* HDSS, Section 4.5, 1: AUTH[h] = v[h][1], h = 0,...,H-1. * Cache left node if on authentication path. */ if ((i >> h) == 1) { if (bds->authPath == NULL) { state->ret = WC_FAILURE; return; } XMEMCPY(bds->authPath + h * n, node, n); } /* This is a right node. */ else if (h < hsk) { /* HDSS, Section 4.5, 2: TREEHASH[h].push(v[h][3]) * Copy right node to tree hash if second right node. */ if ((i >> h) == 3) { XMEMCPY(bds->treeHashNode + h * n, node, n); } } else { /* HDSS, Section 4.5, 3: RETAIN[h].push(v[j][2j+3] for * h = H-K,...,H-2 and j = 2^(H-h-1)-2,...,0. * Retain high right nodes. */ word32 ro = (word32)(((word32)1U << (hs - 1 - h)) + h - hs + (((i >> h) - 3) >> 1)); XMEMCPY(bds->retain + ro * n, node, n); } node -= n; /* Calculate hash of node. */ addr[XMSS_ADDR_TREE_HEIGHT] = h; addr[XMSS_ADDR_TREE_INDEX] = (word32)(i >> (h + 1)); wc_xmss_rand_hash(state, node, pk_seed, addr, node); /* Update offset and height. */ o--; h = ++height[o]; } *offset = o; *sp = node; } /* Compute initial Merkle tree and store nodes. * * HDSS, Section 4.5, The algorithm, Initialization. * 1. We store the authentication path for the first leaf (s = 0): * AUTH[h] = v[h][1], h = 0,...,H-1. * 2. Depending on the parameter K, we store the next right authentication * node for each height h = 0,...,H-K-1 in the treehash instances: * TREEHASH[h].push(v[h][3]). * 3. Finally we store the right authentication nodes clode to the root using * the stacks RETAIN[h]: * RETAIN[h].push(v[j][2j+3] for h = H-K,...,H-2 and j = 2^(H-h-1)-2,...,0. * * RFC 8391: 4.1.6, Algorithm 9: treeHash * if( s % (1 << t) != 0 ) return -1; * for ( i = 0; i < 2^t; i++ ) { * SEED = getSEED(SK); * [Compute node at next index] * } * return Stack.pop(); * * @param [in] state XMSS/MT state including digest and parameters. * @param [in] bds BDS state. * @param [in] sk_seed Random secret/private seed. * @param [in] pk_seed Random public seed. * @param [in] addr Hash address. * @param [out] root Root node. */ static void wc_xmss_bds_treehash_initial(XmssState* state, BdsState* bds, const byte* sk_seed, const byte* pk_seed, const HashAddress addr, byte* root) { const XmssParams* params = state->params; const word8 hsk = (word8)(params->sub_h - params->bds_k); const word8 n = params->n; word8* node = state->stack; HashAddress addrCopy; word8 height[WC_XMSS_MAX_TREE_HEIGHT + 1]; word8 offset = 0; word32 maxIdx = (word32)1U << params->sub_h; word32 i; /* First signing index will be 0 - setup BDS state. */ bds->offset = 0; bds->next = 0; /* Reset the hash tree status. */ if (bds->treeHash != NULL) { for (i = 0; i < hsk; i++) { wc_xmss_bds_state_treehash_init(bds, i); } } /* Copy hash address into local. */ XMSS_ADDR_OTS_SET_SUBTREE(addrCopy, addr); /* Compute each node in tree. */ for (i = 0; i < maxIdx; i++) { wc_xmss_bds_next_idx(state, bds, sk_seed, pk_seed, addrCopy, i, height, &offset, &node); offset++; node += n; /* Rest the hash address for reuse. */ addrCopy[XMSS_ADDR_TREE_HEIGHT] = 0; addrCopy[XMSS_ADDR_TREE_INDEX] = 0; } /* Copy the root node. */ XMEMCPY(root, state->stack, n); } /* Update internal nodes of Merkle tree at next index. * * RFC 8391: 4.1.6, Algorithm 9: treeHash * ... * SEED = getSEED(SK); * ADRS.setType(0); # Type = OTS hash address * ADRS.setOTSAddress(s + i); * pk = WOTS_genPK (getWOTS_SK(SK, s + i), SEED, ADRS); * ADRS.setType(1); # Type = L-tree address * ADRS.setLTreeAddress(s + i); * node = ltree(pk, SEED, ADRS); * ADRS.setType(2); # Type = hash tree address * ADRS.setTreeHeight(0); * ADRS.setTreeIndex(i + s); * while ( Top node on Stack has same height t' as node ) { * ADRS.setTreeIndex((ADRS.getTreeIndex() - 1) / 2); * node = RAND_HASH(Stack.pop(), node, SEED, ADRS); * ADRS.setTreeHeight(ADRS.getTreeHeight() + 1); * } * Stack.push(node); * * @param [in] state XMSS/MT state including digest and parameters. * @param [in, out] bds BDS state. * @param [in] height Height of nodes to update. * @param [in] sk_seed Random secret/private seed. * @param [in] pk_seed Random public seed. * @param [in] addr Hash address. */ static void wc_xmss_bds_treehash_update(XmssState* state, BdsState* bds, word8 height, const byte* sk_seed, const byte* pk_seed, const HashAddress addr) { const XmssParams* params = state->params; const word8 n = params->n; HashAddress addrLocal; TreeHash treeHash[1]; byte* sp = bds->stack + bds->offset * n; byte* node = state->stack + WC_XMSS_MAX_STACK_LEN - n; word8 h; /* Get the tree hash data. */ wc_xmss_bds_state_treehash_get(bds, height, treeHash); /* Copy hash address into local as OTS type. */ XMSS_ADDR_OTS_SET_SUBTREE(addrLocal, addr); /* Calculate WOTS+ public key. */ addrLocal[XMSS_ADDR_OTS] = treeHash->nextIdx; wc_xmss_wots_gen_pk(state, sk_seed, pk_seed, addrLocal, state->pk); /* Calculate public value. */ addrLocal[XMSS_ADDR_TYPE] = WC_XMSS_ADDR_TYPE_LTREE; wc_xmss_ltree(state, state->pk, pk_seed, addrLocal, node); addrLocal[XMSS_ADDR_TYPE] = WC_XMSS_ADDR_TYPE_TREE; addrLocal[XMSS_ADDR_TREE_ZERO] = 0; /* Initial height is 0. */ h = 0; /* Top node on Stack has same height t' as node. */ while ((treeHash->used > 0) && (h == bds->height[bds->offset - 1])) { sp -= n; /* Copy from stack to before last calculated node. */ node -= n; XMEMCPY(node, sp, n); /* Calculate hash of node. */ addrLocal[XMSS_ADDR_TREE_HEIGHT] = h; addrLocal[XMSS_ADDR_TREE_INDEX] = treeHash->nextIdx >> (h + 1); wc_xmss_rand_hash(state, node, pk_seed, addrLocal, node); /* Update used, offset and height. */ treeHash->used--; bds->offset--; h++; } /* Check whether we reached the height we wanted to update. */ if (h == height) { /* Cache node. */ XMEMCPY(bds->treeHashNode + height * n, node, n); treeHash->completed = 1; } else { /* Push calculated node onto stack. */ XMEMCPY(sp, node, n); treeHash->used++; /* Update BDS state. */ bds->height[bds->offset] = h; bds->offset++; treeHash->nextIdx++; } /* Set the tree hash data back. */ wc_xmss_bds_state_treehash_set(bds, height, treeHash); } /* Updates hash trees that need it most. * * Algorithm 4.6: Authentication path computation, Step 5. * * @param [in] state XMSS/MT state including digest and parameters. * @param [in, out] bds BDS state. * @param [in] updates Current number of updates. * @param [in] sk_seed Random secret/private seed. * @param [in] pk_seed Random public seed. * @param [in] addr Hash address. * @return Number of available updates. */ static word8 wc_xmss_bds_treehash_updates(XmssState* state, BdsState* bds, word8 updates, const byte* sk_seed, const byte* pk_seed, const HashAddress addr) { const XmssParams* params = state->params; const word8 hs = params->sub_h; const word8 hsk = (word8)(params->sub_h - params->bds_k); if (bds->treeHash == NULL) { state->ret = WC_FAILURE; return 0; } while (updates > 0) { word8 minH = hs; word8 h = hsk; word8 i; /* Step 5.a. k <- min{ h: TREEHASH(h).height() = min[j=0..H-K-1]{TREEHASH(j.height()} } */ for (i = 0; i < hsk; i++) { TreeHash treeHash[1]; wc_xmss_bds_state_treehash_get(bds, i, treeHash); if (treeHash->completed) { /* Finished - ignore. */ } else if (treeHash->used == 0) { /* None used, low height. */ if (i < minH) { h = i; minH = i; } } /* Find the height of lowest in cache. */ else { word8 j; word8 lowH = hs; byte* height = bds->height + bds->offset - treeHash->used; for (j = 0; j < treeHash->used; j++) { lowH = (word8)min(height[j], lowH); } if (lowH < minH) { /* New lowest height. */ h = i; minH = lowH; } } } /* If none lower, then stop. */ if (h == hsk) { break; } /* Step 5.b. TREEHASH(k).update() */ /* Update tree to the lowest height. */ wc_xmss_bds_treehash_update(state, bds, h, sk_seed, pk_seed, addr); updates--; } return updates; } /* Update BDS at next leaf. * * Don't do anything if processed all leaves. * * @param [in] state XMSS/MT state including digest and parameters. * @param [in, out] bds BDS state. * @param [in] sk_seed Random secret/private seed. * @param [in] pk_seed Random public seed. * @param [in] addr Hash address. */ static void wc_xmss_bds_update(XmssState* state, BdsState* bds, const byte* sk_seed, const byte* pk_seed, const HashAddress addr) { if (bds->next < ((word32)1U << state->params->sub_h)) { const XmssParams* params = state->params; byte* sp = bds->stack + bds->offset * params->n; HashAddress addrCopy; XMSS_ADDR_OTS_SET_SUBTREE(addrCopy, addr); if (bds->height == NULL) { state->ret = WC_FAILURE; return; } wc_xmss_bds_next_idx(state, bds, sk_seed, pk_seed, addrCopy, bds->next, bds->height, &bds->offset, &sp); bds->offset++; bds->next++; } } /* Find index of lowest zero bit. * * Supports max up to 31. * * @param [in] n Number to evaluate. * @param [in] max Max number of bits. * @param [out] b Next bit above first zero bit. * @return Index of lowest bit that is zero. */ static word8 wc_xmss_lowest_zero_bit_index(word32 n, word8 max, word8* b) { word8 i; /* Check each bit from lowest for a zero bit. */ for (i = 0; i < max; i++) { if ((n & 1) == 0) { break; } n >>= 1; } /* Return next bit after 0 bit. */ *b = (n >> 1) & 1; return i; } /* Returns auth path for node leafIdx and computes for next leaf node. * * HDSS, Algorithm 4.6: Authentication path computation, Steps 1-4. * * @param [in] state XMSS/MT state including digest and parameters. * @param [in, out] bds BDS state. * @param [in] leafIdx Current leaf index. * @param [in] sk_seed Random secret/private seed. * @param [in] pk_seed Random public seed. * @param [in] addr Hash address. */ static void wc_xmss_bds_auth_path(XmssState* state, BdsState* bds, const word32 leafIdx, const byte* sk_seed, const byte* pk_seed, HashAddress addr) { const XmssParams* params = state->params; const word8 n = params->n; const word8 hs = params->sub_h; const word8 hsk = (word8)(params->sub_h - params->bds_k); word8 tau; byte* node = state->encMsg; word8 parent; if ((bds->keep == NULL) || (bds->authPath == NULL)) { state->ret = WC_FAILURE; return; } /* Step 1. Find the height of first left node in authentication path. */ tau = wc_xmss_lowest_zero_bit_index(leafIdx, hs, &parent); if (tau == 0) { /* Step 2. Keep node if parent is a left node. * if s/(2^tau+1) is even and tau < H-1 then KEEP[tau] <- AUTH[tau] */ if (parent == 0) { XMEMCPY(bds->keep, bds->authPath, n); } /* Step 3. if tau = 0 then AUTH[0] <- LEAFCALC(s) */ /* Calculate WOTS+ public key. */ addr[XMSS_ADDR_TYPE] = WC_XMSS_ADDR_TYPE_OTS; addr[XMSS_ADDR_OTS] = leafIdx; wc_xmss_wots_gen_pk(state, sk_seed, pk_seed, addr, state->pk); /* Calculate public value. */ addr[XMSS_ADDR_TYPE] = WC_XMSS_ADDR_TYPE_LTREE; wc_xmss_ltree(state, state->pk, pk_seed, addr, bds->authPath); } else { byte* authPath; byte* nodes; word8 i; authPath = bds->authPath + tau * n; /* Step 4.a. = AUTH[tau-1] || KEEP[tau-1] * Only keeping half of nodes, so need to copy out before updating. */ XMEMCPY(node, authPath - n, n); XMEMCPY(node + n, bds->keep + ((tau - 1) >> 1) * n, n); /* Step 2. Keep node if parent is a left node. * if s/(2^tau+1) is even and tau < H-1 then KEEP[tau] <- AUTH[tau] */ if ((tau < hs - 1) && (parent == 0)) { XMEMCPY(bds->keep + (tau >> 1) * n, authPath, n); } /* Step 4.a. AUTH[tau] <- g() */ addr[XMSS_ADDR_TYPE] = WC_XMSS_ADDR_TYPE_TREE; addr[XMSS_ADDR_TREE_ZERO] = 0; addr[XMSS_ADDR_TREE_HEIGHT] = (word32)(tau - 1); addr[XMSS_ADDR_TREE_INDEX] = leafIdx >> tau; wc_xmss_rand_hash(state, node, pk_seed, addr, authPath); /* Step 4.b. */ authPath = bds->authPath; nodes = bds->treeHashNode; /* for h = 0 to tau - 1 do */ for (i = 0; i < tau; i++) { /* if h < H - K then AUTH[h] <- TREEHASH[h].pop()*/ if (i < hsk) { XMEMCPY(authPath, nodes, n); nodes += n; } /* if h >= H - K then AUTH[h] <- RETAIN[h].pop()*/ else { word32 o = (word32)(((word32)1U << (hs - 1 - i)) + i - hs + (((leafIdx >> i) - 1) >> 1)); XMEMCPY(authPath, bds->retain + o * n, n); } authPath += n; } /* Step 4.c. Initialize treehash instances for heights: * 0, ..., min{tau-1, H - K - 1} */ tau = (word8)min(tau, hsk); for (i = 0; i < tau; i++) { word32 startIdx = leafIdx + 1U + 3U * ((word32)1U << i); if (startIdx < ((word32)1U << hs)) { wc_xmss_bds_state_treehash_set_next_idx(bds, i, startIdx); } } } } /******************************************** * XMSS ********************************************/ /* Derives XMSS key pair from seeds. * * RFC 8391: 4.1.7, Algorithm 10: XMSS_keyGen. * ... * initialize SK_PRF with a uniformly random n-byte string; * setSK_PRF(SK, SK_PRF); * * # Initialization for common contents * initialize SEED with a uniformly random n-byte string; * setSEED(SK, SEED); * setWOTS_SK(SK, wots_sk)); * ADRS = toByte(0, 32); * root = treeHash(SK, 0, h, ADRS); * * SK = idx || wots_sk || SK_PRF || root || SEED; * PK = OID || root || SEED; * return (SK || PK); * * HDSS, Section 4.5, The algorithm, Initialization. * * wots_sk, SK_PRF and SEED passed in as seed. * Store seed for wots_sk instead of generated wots_sk. * OID not stored in PK this is handled in upper layer. * BDS state is appended to SK: * SK = idx || wots_sk || SK_PRF || root || SEED || BDS_STATE; * * @param [in] state XMSS/MT state including digest and parameters. * @param [in] seed Secret/Private and public seed. * @param [out] sk Secret key. * @param [out] pk Public key. * @return 0 on success. * @return MEMORY_E on dynamic memory allocation failure. * @return <0 on digest failure. */ int wc_xmss_keygen(XmssState* state, const unsigned char* seed, unsigned char* sk, unsigned char* pk) { #if WOLFSSL_XMSS_MIN_HEIGHT <= 32 int ret = 0; const XmssParams* params = state->params; const word8 n = params->n; /* Offset of root node in public key. */ byte* pk_root = pk; WC_DECLARE_VAR(bds, BdsState, 1, 0); #ifdef WOLFSSL_SMALL_STACK /* Allocate memory for tree hash instances and put in BDS state. */ ret = wc_xmss_bds_state_alloc(params, &bds, state->heap); if (ret == 0) #endif { /* Setup pointers into sk - assumes sk is initialized to zeros. */ ret = wc_xmss_bds_state_load(state, sk, bds, NULL); } if (ret == 0) { /* Offsets into seed. */ const byte* seed_priv = seed; const byte* seed_pub = seed + 2 * n; /* Offsets into secret/private key. */ word32* sk_idx = (word32*)sk; byte* sk_seeds = sk + params->idx_len; /* Offsets into public key. */ byte* pk_seed = pk + n; /* Set first index to 0 in private key. idx_len always 4. */ *sk_idx = 0; /* Set private key seed and private key for PRF in to private key. */ XMEMCPY(sk_seeds, seed_priv, 2U * n); /* Set public key seed into public key. */ XMEMCPY(pk_seed, seed_pub, n); /* Set all address values to zero. */ XMEMSET(state->addr, 0, sizeof(HashAddress)); /* Hash address layer is 0. */ /* Compute root node into public key. */ wc_xmss_bds_treehash_initial(state, bds, sk_seeds, pk_seed, state->addr, pk_root); /* Return any errors that occurred during hashing. */ ret = state->ret; } if (ret == 0) { /* Offset of root node in private key. */ byte* sk_root = sk + params->idx_len + 2 * n; /* Append public key (root node and public seed) to private key. */ XMEMCPY(sk_root, pk_root, 2U * n); /* Store BDS state back into secret/private key. */ ret = wc_xmss_bds_state_store(state, sk, bds); } #ifdef WOLFSSL_SMALL_STACK /* Dispose of allocated data of BDS states. */ wc_xmss_bds_state_free(bds, state->heap); #endif return ret; #else (void)state; (void)pk; (void)sk; (void)seed; return NOT_COMPILED_IN; #endif /* WOLFSSL_XMSS_MIN_HEIGHT <= 32 */ } /* Sign a message with XMSS. * * RFC 8391: 4.1.9, Algorithm 11: treeSig * ... * ADRS.setType(0); # Type = OTS hash address * ADRS.setOTSAddress(idx_sig); * sig_ots = WOTS_sign(getWOTS_SK(SK, idx_sig), * M', getSEED(SK), ADRS); * Sig = sig_ots || auth; * return Sig; * RFC 8391: 4.1.9, Algorithm 12: XMSS_sign * idx_sig = getIdx(SK); * setIdx(SK, idx_sig + 1); * ADRS = toByte(0, 32); * byte[n] r = PRF(getSK_PRF(SK), toByte(idx_sig, 32)); * byte[n] M' = H_msg(r || getRoot(SK) || (toByte(idx_sig, n)), M); * Sig = idx_sig || r || treeSig(M', SK, idx_sig, ADRS); * return (SK || Sig); * * HDSS, Section 4.5, The algorithm, Update and output phase. * * 'auth' was built at key generation or after computing previous signature. * Build next authentication path after signature created. * * @param [in] state XMSS/MT state including digest and parameters. * @param [in] m Buffer holding message. * @param [in] mlen Length of message in buffer. * @param [in, out] sk Secret/Private key. * @param [out] sm Signature and message data. * @param [in, out] smlen On in, length of signature and message buffer. * On out, length of signature and message data. * @return 0 on success. * @return <0 on digest failure. */ int wc_xmss_sign(XmssState* state, const unsigned char* m, word32 mlen, unsigned char* sk, unsigned char* sig) { #if WOLFSSL_XMSS_MIN_HEIGHT <= 32 int ret = 0; const XmssParams* params = state->params; const word8 n = params->n; const word8 h = params->h; const word8 hk = (word8)(params->h - params->bds_k); const byte* sk_seed = sk + XMSS_IDX_LEN; const byte* pk_seed = sk + XMSS_IDX_LEN + 3 * n; byte node[WC_XMSS_MAX_N]; word32 idx; byte* sig_r = sig + XMSS_IDX_LEN; WC_DECLARE_VAR(bds, BdsState, 1, 0); #ifdef WOLFSSL_SMALL_STACK /* Allocate memory for tree hash instances and put in BDS state. */ ret = wc_xmss_bds_state_alloc(params, &bds, state->heap); if (ret == 0) #endif { /* Load the BDS state from secret/private key. */ ret = wc_xmss_bds_state_load(state, sk, bds, NULL); } if (ret == 0) { /* Copy the index into the signature data: Sig = idx_sig || ... */ *((word32*)sig) = *((word32*)sk); /* Read index from the secret key. */ ato32(sk, &idx); /* Check index is valid. */ if (IDX32_INVALID(idx, XMSS_IDX_LEN, h)) { /* Set index to maximum value to distinguish from valid value. */ XMEMSET(sk, 0xFF, XMSS_IDX_LEN); /* Zeroize the secret key. */ ForceZero(sk + XMSS_IDX_LEN, params->sk_len - XMSS_IDX_LEN); ret = KEY_EXHAUSTED_E; } } /* Update SK_MT */ if (ret == 0) { /* Increment the index in the secret key. */ c32toa(idx + 1, sk); } /* Message compression */ if (ret == 0) { const byte* sk_prf = sk + XMSS_IDX_LEN + n; /* byte[n] r = PRF(SK_PRF, toByte(idx_sig, 32)); */ wc_idx_copy(sig, params->idx_len, state->buf, XMSS_PRF_M_LEN); wc_xmss_prf(state, sk_prf, state->buf, sig_r); ret = state->ret; } if (ret == 0) { const byte* pub_root = sk + XMSS_IDX_LEN + 2 * n; /* Compute the message hash. */ wc_xmss_hash_message(state, sig_r, pub_root, sig, XMSS_IDX_LEN, m, mlen, node); ret = state->ret; /* Place new signature data after index and 'r'. */ sig += XMSS_IDX_LEN + n; } if (ret == 0) { /* Set all address values to zero and set type to OTS. */ XMEMSET(state->addr, 0, sizeof(HashAddress)); state->addr[XMSS_ADDR_TYPE] = WC_XMSS_ADDR_TYPE_OTS; /* treeSig || treeHash = sig_ots || auth */ state->addr[XMSS_ADDR_OTS] = idx; /* Create WOTS+ signature for tree into signature (sig_ots). */ wc_xmss_wots_sign(state, node, sk_seed, pk_seed, state->addr, sig); ret = state->ret; } if (ret == 0) { sig += params->wots_sig_len; /* Add authentication path (auth) and calc new root. */ XMEMCPY(sig, bds->authPath, (word32)h * n); ret = state->ret; } if (ret == 0) { /* Update BDS state - update authentication path for next index. */ /* Check not last node. */ if (idx < ((word32)1U << h) - 1U) { /* Calculate next authentication path node. */ wc_xmss_bds_auth_path(state, bds, idx, sk_seed, pk_seed, state->addr); ret = state->ret; if (ret == 0) { /* Algorithm 4.6: Step 5. */ wc_xmss_bds_treehash_updates(state, bds, hk >> 1, sk_seed, pk_seed, state->addr); ret = state->ret; } } } if (ret == 0) { /* Store BDS state back into secret/private key. */ ret = wc_xmss_bds_state_store(state, sk, bds); } #ifdef WOLFSSL_SMALL_STACK /* Dispose of allocated data of BDS states. */ wc_xmss_bds_state_free(bds, state->heap); #endif return ret; #else (void)state; (void)m; (void)mlen; (void)sk; (void)sig; return NOT_COMPILED_IN; #endif /* WOLFSSL_XMSS_MIN_HEIGHT <= 32 */ } /******************************************** * XMSS^MT ********************************************/ /* Generate a XMSS^MT key pair from seeds. * * RFC 8391: 4.2.2, Algorithm 15: XMSS^MT_keyGen. * ... * # Example initialization * idx_MT = 0; * setIdx(SK_MT, idx_MT); * initialize SK_PRF with a uniformly random n-byte string; * setSK_PRF(SK_MT, SK_PRF); * initialize SEED with a uniformly random n-byte string; * setSEED(SK_MT, SEED); * * # Generate reduced XMSS private keys * ADRS = toByte(0, 32); * for ( layer = 0; layer < d; layer++ ) { * ADRS.setLayerAddress(layer); * for ( tree = 0; tree < * (1 << ((d - 1 - layer) * (h / d))); * tree++ ) { * ADRS.setTreeAddress(tree); * for ( i = 0; i < 2^(h / d); i++ ) { * wots_sk[i] = WOTS_genSK(); * } * setXMSS_SK(SK_MT, wots_sk, tree, layer); * } * } * * SK = getXMSS_SK(SK_MT, 0, d - 1); * setSEED(SK, SEED); * root = treeHash(SK, 0, h / d, ADRS); * setRoot(SK_MT, root); * * PK_MT = OID || root || SEED; * return (SK_MT || PK_MT); * * HDSS, Section 4.5, The algorithm, Initialization. * OPX, Section 2, Key Generation. * * wots_sk, SK_PRF and SEED passed in as seed. * Store seed for wots_sk instead of generated wots_sk. * OID not stored in PK this is handled in upper layer. * BDS state is appended to SK: * SK = idx || wots_sk || SK_PRF || root || SEED || BDS_STATE; * * @param [in] state XMSS/MT state including digest and parameters. * @param [in] seed Secret/Private and public seed. * @param [out] sk Secret key. * @param [out] pk Public key. * @return 0 on success. * @return MEMORY_E on dynamic memory allocation failure. * @return <0 on digest failure. */ int wc_xmssmt_keygen(XmssState* state, const unsigned char* seed, unsigned char* sk, unsigned char* pk) { int ret = 0; const XmssParams* params = state->params; const word8 n = params->n; unsigned char* sk_seed = sk + params->idx_len; unsigned char* pk_root = pk; unsigned char* pk_seed = pk + n; word8 i; byte* wots_sigs; BdsState* bds = NULL; /* Allocate memory for BDS states and tree hash instances. */ ret = wc_xmss_bds_state_alloc(params, &bds, state->heap); if (ret == 0) { /* Load the BDS state from secret/private key. */ ret = wc_xmss_bds_state_load(state, sk, bds, &wots_sigs); } if (ret == 0) { /* Offsets into seed. */ const byte* seed_priv = seed; const byte* seed_pub = seed + 2 * params->n; /* Set first index to 0 in private key. */ XMEMSET(sk, 0, params->idx_len); /* Set private key seed and private key for PRF in to private key. */ XMEMCPY(sk_seed, seed_priv, 2U * n); /* Set public key seed into public key. */ XMEMCPY(pk_seed, seed_pub, n); /* Set all address values to zero. */ XMEMSET(state->addr, 0, sizeof(HashAddress)); /* Hash address layer is 0 = bottom-most layer. */ } /* Setup state and compute WOTS+ signatures for all but top-most subtree. */ for (i = 0; (ret == 0) && (i < params->d - 1); i++) { /* Compute root for subtree. */ wc_xmss_bds_treehash_initial(state, bds + i, sk_seed, pk_seed, state->addr, pk_root); ret = state->ret; if (ret == 0) { /* Create signature for subtree for first index. */ state->addr[XMSS_ADDR_LAYER] = (word32)(i + 1); wc_xmss_wots_sign(state, pk_root, sk_seed, pk_seed, state->addr, wots_sigs + i * params->wots_sig_len); ret = state->ret; } } if (ret == 0) { /* Compute root for top-most subtree. */ wc_xmss_bds_treehash_initial(state, bds + i, sk_seed, pk_seed, state->addr, pk_root); /* Return any errors that occurred during hashing. */ ret = state->ret; } if (ret == 0) { /* Offset of root node in private key. */ unsigned char* sk_root = sk_seed + 2 * n; /* Append public key (root node and public seed) to private key. */ XMEMCPY(sk_root, pk_root, 2U * n); /* Store BDS state back into secret/private key. */ ret = wc_xmss_bds_state_store(state, sk, bds); } /* Dispose of allocated data of BDS states. */ wc_xmss_bds_state_free(bds, state->heap); return ret; } #if !defined(WORD64_AVAILABLE) && (WOLFSSL_XMSS_MAX_HEIGHT > 32) #error "Support not available - use XMSS small code option" #endif #if (WOLFSSL_XMSS_MAX_HEIGHT > 32) typedef word64 XmssIdx; #define IDX_MAX_BITS 64 #else typedef word32 XmssIdx; #define IDX_MAX_BITS 32 #endif /* Decode index into word. * * @param [out] idx Index from encoding. * @param [in] c Count of bytes to decode to index. * @param [in] a Array to decode from. */ static void xmss_idx_decode(XmssIdx* idx, word8 c, const unsigned char* a) { word8 i; XmssIdx n = 0; for (i = 0; i < c; i++) { n <<= 8; n += a[i]; } *idx = n; } /* Check whether index is valid. * * @param [in] i Index to check. * @param [in] h Full tree Height. */ static int xmss_idx_invalid(XmssIdx i, word8 h) { return ((i + 1) >> h) != 0; } /* Get tree and leaf index from index. * * @param [in] i Index to split. * @param [in] h Tree height. * @param [out] t Tree index. * @param [out] l Leaf index. */ static void xmss_idx_get_tree_leaf(XmssIdx i, word8 h, XmssIdx* t, word32* l) { *l = (word32)i & (((word32)1U << h) - 1U); *t = i >> h; } /* Set the index into address as the tree index. * * @param [in] i Tree index. * @param [in, out] a Hash address. */ static void xmss_idx_set_addr_tree(XmssIdx i, HashAddress a) { #if IDX_MAX_BITS == 32 a[XMSS_ADDR_TREE_HI] = 0; a[XMSS_ADDR_TREE] = i; #else a[XMSS_ADDR_TREE_HI] = (word32)(i >> 32); a[XMSS_ADDR_TREE] = (word32)(i ); #endif } /* Sign message with XMSS^MT. * * RFC 8391: 4.1.9, Algorithm 11: treeSig * ... * ADRS.setType(0); # Type = OTS hash address * ADRS.setOTSAddress(idx_sig); * sig_ots = WOTS_sign(getWOTS_SK(SK, idx_sig), * M', getSEED(SK), ADRS); * Sig = sig_ots || auth; * return Sig; * RFC 8391: 4.2.4, Algorithm 16: XMSS^MT_sign. * ... * # Init * ADRS = toByte(0, 32); * SEED = getSEED(SK_MT); * SK_PRF = getSK_PRF(SK_MT); * idx_sig = getIdx(SK_MT); * * # Update SK_MT * setIdx(SK_MT, idx_sig + 1); * * # Message compression * byte[n] r = PRF(SK_PRF, toByte(idx_sig, 32)); * byte[n] M' = H_msg(r || getRoot(SK_MT) || (toByte(idx_sig, n)), M); * * # Sign * Sig_MT = idx_sig; * unsigned int idx_tree * = (h - h / d) most significant bits of idx_sig; * unsigned int idx_leaf = (h / d) least significant bits of idx_sig; * SK = idx_leaf || getXMSS_SK(SK_MT, idx_tree, 0) || SK_PRF * || toByte(0, n) || SEED; * ADRS.setLayerAddress(0); * ADRS.setTreeAddress(idx_tree); * Sig_tmp = treeSig(M', SK, idx_leaf, ADRS); * Sig_MT = Sig_MT || r || Sig_tmp; * for ( j = 1; j < d; j++ ) { * root = treeHash(SK, 0, h / d, ADRS); * idx_leaf = (h / d) least significant bits of idx_tree; * idx_tree = (h - j * (h / d)) most significant bits of idx_tree; * SK = idx_leaf || getXMSS_SK(SK_MT, idx_tree, j) || SK_PRF * || toByte(0, n) || SEED; * ADRS.setLayerAddress(j); * ADRS.setTreeAddress(idx_tree); * Sig_tmp = treeSig(root, SK, idx_leaf, ADRS); * Sig_MT = Sig_MT || Sig_tmp; * } * return SK_MT || Sig_MT; * * 'auth' was built at key generation or after computing previous signature. * * @param [in] state XMSS/MT state including digest and parameters. * @param [in, out] bds BDS state. * @param [in] idx Index to sign with. * @param [in] wots_sigs Pre-computed WOTS+ signatures. * @param [in] m Buffer holding message. * @param [in] mlen Length of message in buffer. * @param [in, out] sk Secret/Private key. * @param [out] sig Signature and message data. * @return 0 on success. * @return <0 on digest failure. */ static int wc_xmssmt_sign_msg(XmssState* state, BdsState* bds, XmssIdx idx, byte* wots_sigs, const unsigned char* m, word32 mlen, unsigned char* sk, unsigned char* sig) { int ret; const XmssParams* params = state->params; const word8 n = params->n; const word8 hs = params->sub_h; const word8 idx_len = params->idx_len; const byte* sk_prf = sk + idx_len + n; byte* sig_mt = sig; byte* sig_r = sig + idx_len; byte node[WC_XMSS_MAX_N]; /* Message compression */ /* byte[n] r = PRF(SK_PRF, toByte(idx_sig, 32)); */ wc_idx_copy(sig_mt, idx_len, state->buf, XMSS_PRF_M_LEN); wc_xmss_prf(state, sk_prf, state->buf, sig_r); ret = state->ret; if (ret == 0) { const byte* pub_root = sk + idx_len + 2 * n; /* byte[n] M' = H_msg(r || getRoot(SK_MT) || (toByte(idx_sig, n)), M); */ wc_xmss_hash_message(state, sig_r, pub_root, sig, idx_len, m, mlen, node); ret = state->ret; /* Place new signature data after index and 'r'. */ sig += idx_len + n; } /* Sign */ if (ret == 0) { const byte* sk_seed = sk + idx_len; const byte* pk_seed = sk + idx_len + 3 * n; XmssIdx idx_tree; word32 idx_leaf; /* Set all address values to zero and set type to OTS. */ XMEMSET(state->addr, 0, sizeof(HashAddress)); state->addr[XMSS_ADDR_TYPE] = WC_XMSS_ADDR_TYPE_OTS; /* Fist iteration - calculate signature. */ /* Set layer, tree and OTS leaf index into hash address. */ state->addr[XMSS_ADDR_LAYER] = 0; xmss_idx_get_tree_leaf(idx, hs, &idx_tree, &idx_leaf); xmss_idx_set_addr_tree(idx_tree, state->addr); /* treeSig || treeHash = sig_ots || auth */ state->addr[XMSS_ADDR_OTS] = idx_leaf; /* Create WOTS+ signature for tree into signature (sig_ots). */ wc_xmss_wots_sign(state, node, sk_seed, pk_seed, state->addr, sig); ret = state->ret; } if (ret == 0) { word8 i; byte *authPath; sig += params->wots_sig_len; /* Add authentication path. */ authPath = bds[BDS_IDX(idx, 0, hs, params->d)].authPath; if (authPath == NULL) { state->ret = WC_FAILURE; return state->ret; } XMEMCPY(sig, authPath, (word32)hs * n); sig += hs * n; /* Remaining iterations from storage. */ for (i = 1; i < params->d; i++) { /* Copy out precomputed signature into signature (sig_ots). */ XMEMCPY(sig, wots_sigs + (i - 1) * params->wots_sig_len, params->wots_sig_len); sig += params->wots_sig_len; /* Add authentication path (auth) and calc new root. */ authPath = bds[BDS_IDX(idx, i, hs, params->d)].authPath; if (authPath == NULL) { state->ret = WC_FAILURE; return state->ret; } XMEMCPY(sig, authPath, (word32)hs * n); sig += hs * n; } ret = state->ret; } return ret; } /* Compute BDS state for signing next index. * * HDSS, Section 4.5, The algorithm, Update and output phase. * OPX, Section 2, Signature Generation. Para 2 and 3. * * @param [in] state XMSS/MT state including digest and parameters. * @param [in, out] bds BDS state. * @param [in] idx Index to sign with. * @param [in] wots_sigs Pre-computed WOTS+ signatures. * @param [in] m Buffer holding message. * @param [in] mlen Length of message in buffer. * @param [in, out] sk Secret/Private key. * @param [out] sig Signature and message data. * @return 0 on success. * @return <0 on digest failure. */ static int wc_xmssmt_sign_next_idx(XmssState* state, BdsState* bds, XmssIdx idx, byte* wots_sigs, unsigned char* sk) { int ret = 0; const XmssParams* params = state->params; const word8 n = params->n; const word8 h = params->h; const word8 hs = params->sub_h; const word8 hsk = (word8)(params->sub_h - params->bds_k); const byte* sk_seed = sk + params->idx_len; const byte* pk_seed = sk + params->idx_len + 3 * n; XmssIdx idx_tree; int computeAuthPath = 1; unsigned int updates; word8 i; /* Update BDS state - update authentication path for next index. */ /* HDSS, Algorithm 4.6, Step 5: repeat (H - K) / 2 times. */ updates = hsk >> 1; idx_tree = (idx >> hs) + 1; /* Check whether last tree. */ if (idx_tree < ((XmssIdx)1 << (h - hs))) { /* Set hash address to next tree. */ state->addr[XMSS_ADDR_LAYER] = 0; xmss_idx_set_addr_tree(idx_tree, state->addr); /* Update BDS state. */ wc_xmss_bds_update(state, &bds[BDS_ALT_IDX(idx, 0, hs, params->d)], sk_seed, pk_seed, state->addr); ret = state->ret; } for (i = 0; (ret == 0) && (i < params->d); i++) { word32 idx_leaf; word8 bds_i = BDS_IDX(idx, i, hs, params->d); word8 alt_i = BDS_ALT_IDX(idx, i, hs, params->d); /* Check not last at height. */ if (((idx + 1) << (IDX_MAX_BITS - ((i + 1) * hs))) != 0) { state->addr[XMSS_ADDR_LAYER] = i; xmss_idx_get_tree_leaf(idx >> (hs * i), hs, &idx_tree, &idx_leaf); xmss_idx_set_addr_tree(idx_tree, state->addr); idx_tree++; if (computeAuthPath) { /* Compute authentication path for tree. */ wc_xmss_bds_auth_path(state, &bds[bds_i], idx_leaf, sk_seed, pk_seed, state->addr); ret = state->ret; computeAuthPath = 0; } if (ret == 0) { /* HDSS, Algorithm 4.6: Step 5. */ updates = wc_xmss_bds_treehash_updates(state, &bds[bds_i], (word8)updates, sk_seed, pk_seed, state->addr); ret = state->ret; } /* Check tree not first, updates to do, tree not last at height and * next leaf in alt state is not last. */ if ((ret == 0) && (i > 0) && (updates > 0) && (idx_tree < ((XmssIdx)1 << (h - (hs * (i + 1))))) && (bds[alt_i].next < ((XmssIdx)1 << h))) { xmss_idx_set_addr_tree(idx_tree, state->addr); /* Update alternative BDS state. */ wc_xmss_bds_update(state, &bds[alt_i], sk_seed, pk_seed, state->addr); ret = state->ret; updates--; } } /* Last at height. */ else { /* Set layer, tree and OTS leaf index into hash address. */ state->addr[XMSS_ADDR_LAYER] = (word32)(i + 1); idx_tree = (idx + 1) >> ((i + 1) * hs); xmss_idx_get_tree_leaf(idx_tree, hs, &idx_tree, &idx_leaf); xmss_idx_set_addr_tree(idx_tree, state->addr); /* Cache WOTS+ signature for new tree. */ state->addr[XMSS_ADDR_OTS] = idx_leaf; wc_xmss_wots_sign(state, bds[alt_i].stack, sk_seed, pk_seed, state->addr, wots_sigs + i * params->wots_sig_len); ret = state->ret; if (ret == 0) { word8 d; /* Reset old BDS state. */ bds[bds_i].offset = 0; bds[bds_i].next = 0; /* Done an update. */ updates--; /* Need to compute authentication path in next tree up. */ computeAuthPath = 1; /* Mark the tree hashes as complete in new BDS state. */ for (d = 0; d < hsk; d++) { wc_xmss_bds_state_treehash_complete(&bds[alt_i], d); } } } } return ret; } /* Sign a message with XMSS^MT and update BDS state for signing next index. * * RFC 8391: 4.2.4, Algorithm 16: XMSS^MT_sign. * HDSS, Section 4.5, The algorithm, Update and output phase. * * @param [in] state XMSS/MT state including digest and parameters. * @param [in] m Buffer holding message. * @param [in] mlen Length of message in buffer. * @param [in, out] sk Secret/Private key. * @param [out] sig Signature and message data. * @return 0 on success. * @return MEMORY_E on dynamic memory allocation failure. * @return <0 on digest failure. */ int wc_xmssmt_sign(XmssState* state, const unsigned char* m, word32 mlen, unsigned char* sk, unsigned char* sig) { int ret = 0; const XmssParams* params = state->params; const word8 h = params->h; const word8 idx_len = params->idx_len; XmssIdx idx = 0; byte* sig_mt = sig; byte* wots_sigs; BdsState* bds = NULL; /* Allocate memory for BDS states and tree hash instances. */ ret = wc_xmss_bds_state_alloc(params, &bds, state->heap); if (ret == 0) { /* Load the BDS state from secret/private key. */ ret = wc_xmss_bds_state_load(state, sk, bds, &wots_sigs); } if (ret == 0) { /* Copy the index into the signature data: Sig_MT = idx_sig. */ XMEMCPY(sig_mt, sk, idx_len); /* Read index from the secret key. */ xmss_idx_decode(&idx, idx_len, sk); } if ((ret == 0) && xmss_idx_invalid(idx, h)) { /* Set index to maximum value to distinguish from valid value. */ XMEMSET(sk, 0xFF, idx_len); /* Zeroize the secret key. */ ForceZero(sk + idx_len, params->sk_len - idx_len); ret = KEY_EXHAUSTED_E; } if (ret == 0) { /* Increment the index in the secret key. */ wc_idx_update(sk, idx_len); /* Compute signature. */ ret = wc_xmssmt_sign_msg(state, bds, idx, wots_sigs, m, mlen, sk, sig); } /* Only update if not last index. */ if ((ret == 0) && (idx < (((XmssIdx)1 << h) - 1))) { /* Update BDS state for signing next index. */ ret = wc_xmssmt_sign_next_idx(state, bds, idx, wots_sigs, sk); } if (ret == 0) { /* Store BDS state back into secret/private key. */ ret = wc_xmss_bds_state_store(state, sk, bds); } /* Dispose of allocated data of BDS states. */ wc_xmss_bds_state_free(bds, state->heap); return ret; } #endif /* WOLFSSL_WC_XMSS_SMALL */ /* Check if more signatures are possible with secret/private key. * * @param [in] params XMSS parameters * @param [in] sk Secret/private key. * @return 1 when signatures possible. * @return 0 when key exhausted. */ int wc_xmss_sigsleft(const XmssParams* params, unsigned char* sk) { int ret = 0; wc_Idx idx; WC_IDX_ZERO(idx); /* Read index from the secret key. */ WC_IDX_DECODE(idx, params->idx_len, sk, ret); /* Check validity of index. */ if ((ret == 0) && (WC_IDX_INVALID(idx, params->idx_len, params->h))) { ret = KEY_EXHAUSTED_E; } return ret == 0; } #endif /* !WOLFSSL_XMSS_VERIFY_ONLY */ /******************************************** * SIGN OPEN - Verify ********************************************/ #if !defined(WOLFSSL_WC_XMSS_SMALL) || defined(WOLFSSL_XMSS_VERIFY_ONLY) /* Compute root node with leaf and authentication path. * * RFC 8391: 4.1.10, Algorithm 13: XMSS_rootFromSig * ... * for ( k = 0; k < h; k++ ) { * ADRS.setTreeHeight(k); * if ( (floor(idx_sig / (2^k)) % 2) == 0 ) { * ADRS.setTreeIndex(ADRS.getTreeIndex() / 2); * node[1] = RAND_HASH(node[0], auth[k], SEED, ADRS); * } else { * ADRS.setTreeIndex((ADRS.getTreeIndex() - 1) / 2); * node[1] = RAND_HASH(auth[k], node[0], SEED, ADRS); * } * node[0] = node[1]; * } * return node[0]; * * @param [in] state XMSS/MT state including digest and parameters. * @param [in] idx_leaf Index of leaf node. * @param [in] auth_path Authentication path. * @param [in] pk_seed Random public seed. * @param [in] addr Hash address. * @param [in, out] root On in, leaf node. On out, root node. */ static void wc_xmss_compute_root(XmssState* state, word32 idx_leaf, const byte* auth_path, const byte* pk_seed, HashAddress addr, byte* root) { const XmssParams* params = state->params; const word8 n = params->n; const byte* b[2][2] = { { root, auth_path }, { auth_path, root } }; word8 i; for (i = 0; i < params->sub_h; i++) { /* Get which side the leaf is on. */ word8 s = idx_leaf & 1; /* Set tree height and index. */ addr[XMSS_ADDR_TREE_HEIGHT] = i; idx_leaf >>= 1; addr[XMSS_ADDR_TREE_INDEX] = idx_leaf; /* Put the result into buffer position for next RAND_HASH. */ wc_xmss_rand_hash_lr(state, b[s][0], b[s][1], pk_seed, addr, root); /* Move to next auth path node. */ b[0][1] += n; b[1][0] += n; } } #else /* Compute root node with leaf and authentication path. * * RFC 8391: 4.1.10, Algorithm 13: XMSS_rootFromSig * ... * for ( k = 0; k < h; k++ ) { * ADRS.setTreeHeight(k); * if ( (floor(idx_sig / (2^k)) % 2) == 0 ) { * ADRS.setTreeIndex(ADRS.getTreeIndex() / 2); * node[1] = RAND_HASH(node[0], auth[k], SEED, ADRS); * } else { * ADRS.setTreeIndex((ADRS.getTreeIndex() - 1) / 2); * node[1] = RAND_HASH(auth[k], node[0], SEED, ADRS); * } * node[0] = node[1]; * } * return node[0]; * * @param [in] state XMSS/MT state including digest and parameters. * @param [in] idx_leaf Index of leaf node. * @param [in] auth_path Authentication path. * @param [in] pk_seed Random public seed. * @param [in] addr Hash address. * @param [in, out] node On in, leaf node. On out, root node. */ static void wc_xmss_compute_root(XmssState* state, word32 idx_leaf, const byte* auth_path, const byte* pk_seed, HashAddress addr, byte* node) { const XmssParams* params = state->params; const word8 n = params->n; byte buffer[2 * WC_XMSS_MAX_N]; byte* b[2][2] = { { buffer, buffer + n }, { buffer + n, buffer } }; word8 i; /* Setup buffer for first RAND_HASH. */ XMEMCPY(b[idx_leaf & 1][0], node, n); XMEMCPY(b[idx_leaf & 1][1], auth_path, n); auth_path += n; for (i = 0; i < params->sub_h - 1; i++) { /* Set tree height and index. */ addr[XMSS_ADDR_TREE_HEIGHT] = i; idx_leaf >>= 1; addr[XMSS_ADDR_TREE_INDEX] = idx_leaf; /* Put the result into buffer position for next RAND_HASH. */ wc_xmss_rand_hash(state, buffer, pk_seed, addr, b[idx_leaf & 1][0]); /* Put auth path node into other half of buffer. */ XMEMCPY(b[idx_leaf & 1][1], auth_path, n); /* Move to next auth path node. */ auth_path += n; } addr[XMSS_ADDR_TREE_HEIGHT] = i; idx_leaf >>= 1; addr[XMSS_ADDR_TREE_INDEX] = idx_leaf; /* Last iteration into output node. */ wc_xmss_rand_hash(state, buffer, pk_seed, addr, node); } #endif /* !WOLFSSL_WC_XMSS_SMALL || WOLFSSL_XMSS_VERIFY_ONLY */ /* Compute a root node from a tree signature. * * RFC 8391: 4.1.10, Algorithm 13: XMSS_rootFromSig * ADRS.setType(0); # Type = OTS hash address * ADRS.setOTSAddress(idx_sig); * pk_ots = WOTS_pkFromSig(sig_ots, M', SEED, ADRS); * ADRS.setType(1); # Type = L-tree address * ADRS.setLTreeAddress(idx_sig); * byte[n][2] node; * node[0] = ltree(pk_ots, SEED, ADRS); * ADRS.setType(2); # Type = hash tree address * ADRS.setTreeIndex(idx_sig); * [Compute root with leaf and authentication path] * * Computing the root from the leaf and authentication path can be implemented * in different ways and is therefore extracted to its own function. * * @param [in] state XMSS/MT state including digest and parameters. * @param [in] pk_seed Random public seed. * @param [in] sig WOTS+ signature for this tree. * @param [in] idx_sig Index of signature leaf in this tree. * @param [in, out] addr Hash address. * @param [in, out] node On in, previous root node. * On out, root node of this subtree. */ static void wc_xmss_root_from_sig(XmssState* state, const byte* pk_seed, const byte* sig, word32 idx_sig, HashAddress addr, byte* node) { const XmssParams* params = state->params; byte* wots_pk = state->pk; const byte* auth_path = sig + params->wots_sig_len; /* Compute WOTS+ public key value from signature. */ addr[XMSS_ADDR_TYPE] = WC_XMSS_ADDR_TYPE_OTS; addr[XMSS_ADDR_OTS] = idx_sig; wc_xmss_wots_pk_from_sig(state, sig, node, pk_seed, addr, wots_pk); /* Compute leaves of L-tree from WOTS+ public key. */ addr[XMSS_ADDR_TYPE] = WC_XMSS_ADDR_TYPE_LTREE; /* XMSS_ADDR_LTREE is same as XMSS_ADDR_OTS in index and value. */ wc_xmss_ltree(state, wots_pk, pk_seed, addr, node); /* Compute root node from leaf and authentication path. */ addr[XMSS_ADDR_TYPE] = WC_XMSS_ADDR_TYPE_TREE; addr[XMSS_ADDR_TREE_ZERO] = 0; wc_xmss_compute_root(state, idx_sig, auth_path, pk_seed, addr, node); } /* Verify message with signature using XMSS/MT. * * RFC 8391: 4.2.5, Algorithm 17: XMSSMT_verify * idx_sig = getIdx(Sig_MT); * SEED = getSEED(PK_MT); * ADRS = toByte(0, 32); * * byte[n] M' = H_msg(getR(Sig_MT) || getRoot(PK_MT) * || (toByte(idx_sig, n)), M); * * unsigned int idx_leaf * = (h / d) least significant bits of idx_sig; * unsigned int idx_tree * = (h - h / d) most significant bits of idx_sig; * Sig' = getXMSSSignature(Sig_MT, 0); * ADRS.setLayerAddress(0); * ADRS.setTreeAddress(idx_tree); * byte[n] node = XMSS_rootFromSig(idx_leaf, getSig_ots(Sig'), * getAuth(Sig'), M', SEED, ADRS); * for ( j = 1; j < d; j++ ) { * idx_leaf = (h / d) least significant bits of idx_tree; * idx_tree = (h - j * h / d) most significant bits of idx_tree; * Sig' = getXMSSSignature(Sig_MT, j); * ADRS.setLayerAddress(j); * ADRS.setTreeAddress(idx_tree); * node = XMSS_rootFromSig(idx_leaf, getSig_ots(Sig'), * getAuth(Sig'), node, SEED, ADRS); * } * if ( node == getRoot(PK_MT) ) { * return true; * } else { * return false; * } * * @param [in] state XMSS/MT state including digest and parameters. * @param [in] m Message buffer. * @param [in] mlen Length of message in bytes. * @param [in] sig Buffer holding signature. * @param [in] pk Public key. * @return 0 on success. * @return MEMORY_E on dynamic memory allocation failure. * @return SIG_VERIFY_E on verification failure. * @return <0 on digest failure. */ int wc_xmssmt_verify(XmssState* state, const unsigned char* m, word32 mlen, const unsigned char* sig, const unsigned char* pk) { const XmssParams* params = state->params; const word8 n = params->n; int ret = 0; const byte* pub_root = pk; const byte* pk_seed = pk + n; byte node[WC_XMSS_MAX_N]; wc_Idx idx; word32 idx_leaf = 0; unsigned int i; /* Set 32/64-bit index to 0. */ WC_IDX_ZERO(idx); /* Set all address values to zero. */ XMEMSET(state->addr, 0, sizeof(HashAddress)); if (ret == 0) { /* Convert the index bytes from the signature to an integer. */ WC_IDX_DECODE(idx, params->idx_len, sig, ret); } if (ret == 0) { const byte* sig_r = sig + params->idx_len; /* byte[n] M' = H_msg(getR(Sig_MT) || getRoot(PK_MT) || * (toByte(idx_sig, n)), M); */ wc_xmss_hash_message(state, sig_r, pub_root, sig, params->idx_len, m, mlen, node); ret = state->ret; } if (ret == 0) { /* Set tree of hash address. */ WC_IDX_SET_ADDR_TREE(idx, params->idx_len, params->sub_h, state->addr, idx_leaf); /* Skip to first WOTS+ signature and derive root. */ sig += params->idx_len + n; wc_xmss_root_from_sig(state, pk_seed, sig, idx_leaf, state->addr, node); ret = state->ret; } /* Calculate root of remaining subtrees up to top. */ for (i = 1; (ret == 0) && (i < params->d); i++) { /* Set layer and tree. */ state->addr[XMSS_ADDR_LAYER] = i; WC_IDX_SET_ADDR_TREE(idx, params->idx_len, params->sub_h, state->addr, idx_leaf); /* Skip to next WOTS+ signature and derive root. */ sig += params->wots_sig_len + params->sub_h * n; wc_xmss_root_from_sig(state, pk_seed, sig, idx_leaf, state->addr, node); ret = state->ret; } /* Compare calculated node with public key root. */ if ((ret == 0) && (XMEMCMP(node, pub_root, n) != 0)) { ret = SIG_VERIFY_E; } return ret; } #endif /* WOLFSSL_HAVE_XMSS */