Botan 3.14.1
Crypto and TLS for C&
Botan::XMSS_Common_Ops Class Reference

#include <xmss_common_ops.h>

Static Public Member Functions

static void create_l_tree (secure_vector< uint8_t > &result, const wots_keysig_t &pk, XMSS_Address adrs, const secure_vector< uint8_t > &seed, XMSS_Hash &hash, size_t element_size, size_t wots_len)
static void create_l_trees (std::span< uint8_t > leaves, std::span< uint8_t > pks, std::span< XMSS_Address > addrs, std::span< const uint8_t > seed, XMSS_Hash &hash, size_t element_size, size_t wots_len)
static void randomize_tree_hash (secure_vector< uint8_t > &result, const secure_vector< uint8_t > &left, const secure_vector< uint8_t > &right, XMSS_Address adrs, const secure_vector< uint8_t > &seed, XMSS_Hash &hash, size_t element_size)
static secure_vector< uint8_t > root_from_signature (uint32_t idx_leaf, const XMSS_TreeSignature &tree_sig, const secure_vector< uint8_t > &msg, XMSS_Address adrs, const secure_vector< uint8_t > &seed, XMSS_Hash &hash, const XMSS_WOTS_Parameters &wots_params, size_t tree_height)

Detailed Description

Operations shared by XMSS signature generation and verification operations.

Definition at line 38 of file xmss_common_ops.h.

Member Function Documentation

◆ create_l_tree()

void Botan::XMSS_Common_Ops::create_l_tree ( secure_vector< uint8_t > & result,
const wots_keysig_t & pk,
XMSS_Address adrs,
const secure_vector< uint8_t > & seed,
XMSS_Hash & hash,
size_t element_size,
size_t wots_len )
static

Algorithm 8: "ltree" Create an L-tree used to compute the leaves of the binary hash tree. Takes a WOTS+ public key and compresses it to a single n-byte value.

This overload is used in multithreaded scenarios, where it is required to provide separate instances of XMSS_Hash to each thread.

Parameters
[out]resultPublic key compressed to a single n-byte value pk[0].
[in]pkWinternitz One Time Signatures+ public key.
[in]adrsAddress encoding the address of the L-Tree
[in]SEEDThe seed generated during the public key generation.
[in]HashesInstance of XMSS_Hash, that may only be used by the thread executing create_l_tree.
[in]element_sizeSize of each node in bytes, the parameter "n"
[in]wots_lenNumber of WOTS+ chains, the parameter "len"

Definition at line 49 of file xmss_common_ops.cpp.

55 {
56 const size_t n = element_size;
57 BOTAN_ASSERT_NOMSG(pk.size() == wots_len);
58
59 secure_vector<uint8_t> flat(pk.size() * n);
60 for(size_t i = 0; i < pk.size(); ++i) {
61 BOTAN_ASSERT_NOMSG(pk[i].size() == n);
62 copy_mem(std::span(flat).subspan(i * n, n), pk[i]);
63 }
64
65 result.resize(n);
66 create_l_trees(result, flat, std::span(&adrs, 1), seed, hash, element_size, wots_len);
67}
#define BOTAN_ASSERT_NOMSG(expr)
Definition assert.h:82
static void create_l_trees(std::span< uint8_t > leaves, std::span< uint8_t > pks, std::span< XMSS_Address > addrs, std::span< const uint8_t > seed, XMSS_Hash &hash, size_t element_size, size_t wots_len)
constexpr void copy_mem(T *out, const T *in, size_t n)
Definition mem_ops.h:144
std::vector< T, secure_allocator< T > > secure_vector
Definition secmem.h:128

References BOTAN_ASSERT_NOMSG, Botan::copy_mem(), and create_l_trees().

Referenced by root_from_signature().

◆ create_l_trees()

void Botan::XMSS_Common_Ops::create_l_trees ( std::span< uint8_t > leaves,
std::span< uint8_t > pks,
std::span< XMSS_Address > addrs,
std::span< const uint8_t > seed,
XMSS_Hash & hash,
size_t element_size,
size_t wots_len )
static

Algorithm 8: "ltree", applied to many WOTS+ public keys at once, batching the hash calls of each tree level across all keys.

Parameters
[out]leavesThe compressed n-byte value of each key
[in,out]pksThe WOTS+ public keys, each len*n bytes, contiguous. Destroyed by the computation.
[in,out]addrsPer key, its L-tree address with the L-tree address set. The tree height/index and key/mask mode are modified.
[in]SEEDThe public seed
[in]HashesInstance of XMSS_Hash, that may only be used by the thread executing create_l_trees.
[in]element_sizeSize of each node in bytes, the parameter "n"
[in]wots_lenNumber of WOTS+ chains, the parameter "len"

Definition at line 69 of file xmss_common_ops.cpp.

75 {
76 const size_t count = addrs.size();
77 const size_t n = element_size;
78 const size_t stride = wots_len * n;
79
80 BOTAN_ASSERT_NOMSG(leaves.size() == count * n);
81 BOTAN_ASSERT_NOMSG(pks.size() == count * stride);
82
83 if(count == 0) {
84 return;
85 }
86
87 const size_t adrs_len = addrs[0].size();
88
89 for(auto& adrs : addrs) {
90 adrs.set_tree_height(0);
91 }
92
93 // Scratch for one level's batched randomized tree hashes: per node
94 // pair the three PRF addresses (key, bitmask left/right), the key,
95 // and the masked concatenation of both child nodes
96 const size_t max_pairs = count * (wots_len / 2);
97 std::vector<uint8_t> adrs_buf(3 * max_pairs * adrs_len);
98 secure_vector<uint8_t> keys(max_pairs * n);
99 secure_vector<uint8_t> concat(max_pairs * 2 * n);
100
101 std::vector<std::span<uint8_t>> prf_outs(3 * max_pairs);
102 std::vector<std::span<const uint8_t>> prf_ins(3 * max_pairs);
103 std::vector<std::span<uint8_t>> h_outs(max_pairs);
104 std::vector<std::span<const uint8_t>> h_keys(max_pairs);
105 std::vector<std::span<const uint8_t>> h_ins(max_pairs);
106
107 const auto node = [&](size_t k, size_t i) { return pks.subspan(k * stride + i * n, n); };
108
109 size_t l = wots_len;
110
111 while(l > 1) {
112 const size_t pairs = l >> 1;
113 const size_t total = count * pairs;
114
115 // Compute the keys and both bitmasks of all of this level's node
116 // pairs with one PRF batch, the bitmasks landing in the buffer
117 // that the child nodes are then XORed into
118 for(size_t k = 0; k < count; k++) {
119 for(size_t i = 0; i < pairs; i++) {
120 const size_t p = k * pairs + i;
121 addrs[k].set_tree_index(static_cast<uint32_t>(i));
122 const auto adrs_lane = [&](size_t lane, XMSS_Address::Key_Mask mode) {
123 addrs[k].set_key_mask_mode(mode);
124 const auto dest = std::span(adrs_buf).subspan(lane * adrs_len, adrs_len);
125 copy_mem(dest, addrs[k].bytes());
126 prf_ins[lane] = dest;
127 };
128 adrs_lane(3 * p, XMSS_Address::Key_Mask::Key_Mode);
129 adrs_lane(3 * p + 1, XMSS_Address::Key_Mask::Mask_MSB_Mode);
130 adrs_lane(3 * p + 2, XMSS_Address::Key_Mask::Mask_LSB_Mode);
131
132 prf_outs[3 * p] = std::span(keys).subspan(p * n, n);
133 prf_outs[3 * p + 1] = std::span(concat).subspan(p * 2 * n, n);
134 prf_outs[3 * p + 2] = std::span(concat).subspan(p * 2 * n + n, n);
135 }
136 }
137 hash.prf_batch(std::span(prf_outs).first(3 * total), seed, std::span(prf_ins).first(3 * total));
138
139 for(size_t k = 0; k < count; k++) {
140 for(size_t i = 0; i < pairs; i++) {
141 const size_t p = k * pairs + i;
142 xor_buf(std::span(concat).subspan(p * 2 * n, n), node(k, 2 * i));
143 xor_buf(std::span(concat).subspan(p * 2 * n + n, n), node(k, 2 * i + 1));
144 h_outs[p] = node(k, i);
145 h_keys[p] = std::span(keys).subspan(p * n, n);
146 h_ins[p] = std::span(concat).subspan(p * 2 * n, 2 * n);
147 }
148 }
149 hash.h_batch(std::span(h_outs).first(total), std::span(h_keys).first(total), std::span(h_ins).first(total));
150
151 if((l & 0x01) == 0x01) {
152 for(size_t k = 0; k < count; k++) {
153 copy_mem(node(k, l >> 1), node(k, l - 1));
154 }
155 }
156 l = (l >> 1) + (l & 0x01);
157 for(auto& adrs : addrs) {
158 adrs.set_tree_height(adrs.get_tree_height() + 1);
159 }
160 }
161
162 for(size_t k = 0; k < count; k++) {
163 copy_mem(leaves.subspan(k * n, n), node(k, 0));
164 }
165}
constexpr auto concat(Rs &&... ranges)
Definition concat_util.h:95
constexpr void xor_buf(ranges::contiguous_output_range< uint8_t > auto &&out, ranges::contiguous_range< uint8_t > auto &&in)
Definition mem_ops.h:403

References BOTAN_ASSERT_NOMSG, Botan::concat(), Botan::copy_mem(), Botan::XMSS_Hash::h_batch(), Botan::XMSS_Address::Key_Mode, Botan::XMSS_Address::Mask_LSB_Mode, Botan::XMSS_Address::Mask_MSB_Mode, Botan::XMSS_Hash::prf_batch(), and Botan::xor_buf().

Referenced by create_l_tree().

◆ randomize_tree_hash()

void Botan::XMSS_Common_Ops::randomize_tree_hash ( secure_vector< uint8_t > & result,
const secure_vector< uint8_t > & left,
const secure_vector< uint8_t > & right,
XMSS_Address adrs,
const secure_vector< uint8_t > & seed,
XMSS_Hash & hash,
size_t element_size )
static

Algorithm 7: "RAND_HASH"

Generates a randomized hash.

This overload is used in multithreaded scenarios, where it is required to provide separate instances of XMSS_Hash to each thread.

Parameters
[out]resultThe resulting randomized hash.
[in]leftLeft half of the hash function input.
[in]rightRight half of the hash function input.
[in]adrsAddress of the hash function call.
[in]SEEDThe seed for G.
[in]HashesInstance of XMSS_Hash, that may only by the thread executing generate_public_key.
[in]element_sizeSize of each node in bytes, the parameter "n"

Definition at line 18 of file xmss_common_ops.cpp.

24 {
25 adrs.set_key_mask_mode(XMSS_Address::Key_Mask::Key_Mode);
27 hash.prf(key, seed, adrs.bytes());
28
29 adrs.set_key_mask_mode(XMSS_Address::Key_Mask::Mask_MSB_Mode);
30 secure_vector<uint8_t> bitmask_l;
31 hash.prf(bitmask_l, seed, adrs.bytes());
32
33 adrs.set_key_mask_mode(XMSS_Address::Key_Mask::Mask_LSB_Mode);
34 secure_vector<uint8_t> bitmask_r;
35 hash.prf(bitmask_r, seed, adrs.bytes());
36
37 BOTAN_ASSERT(bitmask_l.size() == left.size() && bitmask_r.size() == right.size(),
38 "Bitmask size doesn't match node size.");
39
40 secure_vector<uint8_t> concat_xor(element_size * 2);
41 for(size_t i = 0; i < left.size(); i++) {
42 concat_xor[i] = left[i] ^ bitmask_l[i];
43 concat_xor[i + left.size()] = right[i] ^ bitmask_r[i];
44 }
45
46 hash.h(result, key, concat_xor);
47}
#define BOTAN_ASSERT(expr, assertion_made)
Definition assert.h:69

References BOTAN_ASSERT, Botan::XMSS_Address::bytes(), Botan::XMSS_Hash::h(), Botan::XMSS_Address::Key_Mode, Botan::XMSS_Address::Mask_LSB_Mode, Botan::XMSS_Address::Mask_MSB_Mode, Botan::XMSS_Hash::prf(), and Botan::XMSS_Address::set_key_mask_mode().

Referenced by root_from_signature(), and Botan::XMSS_Tree_Builder::tree_hash().

◆ root_from_signature()

secure_vector< uint8_t > Botan::XMSS_Common_Ops::root_from_signature ( uint32_t idx_leaf,
const XMSS_TreeSignature & tree_sig,
const secure_vector< uint8_t > & msg,
XMSS_Address adrs,
const secure_vector< uint8_t > & seed,
XMSS_Hash & hash,
const XMSS_WOTS_Parameters & wots_params,
size_t tree_height )
static

Algorithm 13: "XMSS_rootFromSig" Computes a root node using a tree signature and a message.

Parameters
[in]idx_leafIndex of the WOTS+ key pair (the leaf) within the tree.
[in]tree_sigThe WOTS+ signature and authentication path.
[in]msgThe signed message (for XMSS^MT layers above the lowest: the root node of the tree below).
[in]adrsAddress of the tree. The caller presets the layer and tree address fields (both zero for XMSS).
[in]SEEDThe public seed.
[in]HashesThe hash instance to use.
[in]wots_paramsThe WOTS+ parameters.
[in]tree_heightHeight of the tree, the parameter "h" (for XMSS^MT: the height of a single layer's tree, "h/d").
Returns
An n-byte string holding the value of the root of the tree defined by the input parameters.

Definition at line 167 of file xmss_common_ops.cpp.

174 {
175 const size_t element_size = wots_params.element_size();
176
178 adrs.set_ots_address(idx_leaf);
179
180 const XMSS_WOTS_PublicKey pub_key_ots(wots_params, seed, tree_sig.ots_signature, msg, adrs, hash);
181
183 adrs.set_ltree_address(idx_leaf);
184
185 std::array<secure_vector<uint8_t>, 2> node;
186 XMSS_Common_Ops::create_l_tree(node[0], pub_key_ots.key_data(), adrs, seed, hash, element_size, wots_params.len());
187
189 adrs.set_tree_index(idx_leaf);
190
191 for(size_t k = 0; k < tree_height; k++) {
192 adrs.set_tree_height(static_cast<uint32_t>(k));
193 if(((idx_leaf / (static_cast<size_t>(1) << k)) & 0x01) == 0) {
194 adrs.set_tree_index(adrs.get_tree_index() >> 1);
196 node[1], node[0], tree_sig.authentication_path[k], adrs, seed, hash, element_size);
197 } else {
198 adrs.set_tree_index((adrs.get_tree_index() - 1) >> 1);
200 node[1], tree_sig.authentication_path[k], node[0], adrs, seed, hash, element_size);
201 }
202 node[0] = node[1];
203 }
204
205 return node[0];
206}
static void create_l_tree(secure_vector< uint8_t > &result, const wots_keysig_t &pk, XMSS_Address adrs, const secure_vector< uint8_t > &seed, XMSS_Hash &hash, size_t element_size, size_t wots_len)
static void randomize_tree_hash(secure_vector< uint8_t > &result, const secure_vector< uint8_t > &left, const secure_vector< uint8_t > &right, XMSS_Address adrs, const secure_vector< uint8_t > &seed, XMSS_Hash &hash, size_t element_size)

References Botan::XMSS_TreeSignature::authentication_path, create_l_tree(), Botan::XMSS_WOTS_Parameters::element_size(), Botan::XMSS_Address::get_tree_index(), Botan::XMSS_Address::Hash_Tree_Address, Botan::XMSS_WOTS_Base::key_data(), Botan::XMSS_WOTS_Parameters::len(), Botan::XMSS_Address::LTree_Address, Botan::XMSS_Address::OTS_Hash_Address, Botan::XMSS_TreeSignature::ots_signature, randomize_tree_hash(), Botan::XMSS_Address::set_ltree_address(), Botan::XMSS_Address::set_ots_address(), Botan::XMSS_Address::set_tree_height(), Botan::XMSS_Address::set_tree_index(), and Botan::XMSS_Address::set_type().


The documentation for this class was generated from the following files: