11#include <botan/internal/xmss_tree_builder.h>
13#include <botan/mem_ops.h>
14#include <botan/internal/xmss_common_ops.h>
15#include <botan/internal/xmss_hash.h>
26constexpr size_t LEAF_BATCH = 128;
31 size_t target_node_height,
35 BOTAN_ASSERT((start_idx % (
static_cast<size_t>(1) << target_node_height)) == 0,
36 "Start index must be divisible by 2^{target node height}.");
38 const size_t n = m_wots_params.element_size();
40 const size_t last_idx = (
static_cast<size_t>(1) << target_node_height) + start_idx;
42 const size_t batch = std::min<size_t>(LEAF_BATCH, last_idx - start_idx);
50 std::vector<uint8_t> node_levels(target_node_height + 1);
57 for(
size_t i = start_idx; i < last_idx; i++) {
58 const size_t b = (i - start_idx) % batch;
60 const size_t count = std::min(batch, last_idx - i);
61 compute_leaves(std::span(leaves).first(count * n), i, count, adrs, hash);
64 copy_mem(nodes[level], std::span(leaves).subspan(b * n, n));
65 node_levels[level] = 0;
70 while(level > 0 && node_levels[level] == node_levels[level - 1]) {
73 node_levels[level - 1]++;
79 return nodes[level - 1];
82void XMSS_Tree_Builder::compute_leaves(
83 std::span<uint8_t> leaves,
size_t start_idx,
size_t count,
const XMSS_Address& adrs,
XMSS_Hash& hash)
const {
85 const size_t len = m_wots_params.
len();
92 std::vector<XMSS_Address> ots_addrs(count * len, ots_adrs);
93 for(
size_t k = 0; k < count; ++k) {
94 for(
size_t i = 0; i < len; ++i) {
95 ots_addrs[k * len + i].set_ots_address(
static_cast<uint32_t
>(start_idx + k));
96 ots_addrs[k * len + i].set_chain_address(
static_cast<uint32_t
>(i));
101 wots_private_keys(keys, ots_addrs, hash);
104 const std::vector<uint8_t> from(count * len, 0);
105 const std::vector<uint8_t> to(count * len,
static_cast<uint8_t
>(m_wots_params.wots_parameter() - 1));
108 XMSS_Address ltree_adrs(adrs);
111 std::vector<XMSS_Address> ltree_addrs(count, ltree_adrs);
112 for(
size_t k = 0; k < count; ++k) {
113 ltree_addrs[k].set_ltree_address(
static_cast<uint32_t
>(start_idx + k));
118void XMSS_Tree_Builder::wots_private_keys(std::span<uint8_t> sks,
119 std::span<const XMSS_Address> addrs,
121 const size_t n = m_wots_params.element_size();
122 const size_t len = m_wots_params.len();
123 const size_t count = addrs.size();
127 switch(m_wots_derivation_method) {
129 const size_t data_len =
public_seed().size() + addrs[0].size();
130 std::vector<uint8_t> data_arena(count * data_len);
132 std::vector<std::span<uint8_t>> outputs(count);
133 std::vector<std::span<const uint8_t>> data(count);
135 for(
size_t i = 0; i < count; ++i) {
136 const auto slot = std::span(data_arena).subspan(i * data_len, data_len);
140 outputs[i] = sks.subspan(i * n, n);
144 hash.prf_keygen_batch(outputs, m_private_seed, data);
148 for(
size_t k = 0; k < count / len; ++k) {
149 const XMSS_WOTS_PrivateKey sk(m_wots_params, m_private_seed, addrs[k * len], hash);
150 for(
size_t i = 0; i < len; ++i) {
151 copy_mem(sks.subspan((k * len + i) * n, n), sk.key_data()[i]);
158 throw Invalid_State(
"WOTS derivation method is out of the enum's range");
162 switch(m_wots_derivation_method) {
169 throw Invalid_State(
"WOTS derivation method is out of the enum's range");
#define BOTAN_ASSERT_NOMSG(expr)
#define BOTAN_ASSERT(expr, assertion_made)
uint32_t get_tree_index() const
uint32_t get_tree_height() const
void set_tree_height(uint32_t value)
void set_tree_index(uint32_t value)
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)
secure_vector< uint8_t > tree_hash(size_t start_idx, size_t target_node_height, const XMSS_Address &adrs, XMSS_Hash &hash) const
XMSS_WOTS_PrivateKey wots_private_key_for(const XMSS_Address &adrs, XMSS_Hash &hash) const
const secure_vector< uint8_t > & public_seed() const
size_t element_size() const
void xmss_wots_chains(const XMSS_WOTS_Parameters ¶ms, std::span< uint8_t > nodes, std::span< const uint8_t > from, std::span< const uint8_t > to, std::span< XMSS_Address > addrs, std::span< const uint8_t > seed, XMSS_Hash &hash)
constexpr void copy_mem(T *out, const T *in, size_t n)
std::vector< T, secure_allocator< T > > secure_vector