Botan 3.14.1
Crypto and TLS for C&
xmss_tree_builder.cpp
Go to the documentation of this file.
1/*
2 * XMSS Tree Builder
3 * (C) 2016,2017,2018 Matthias Gierlings
4 * (C) 2019,2026 Jack Lloyd
5 * (C) 2023 René Meusel - Rohde & Schwarz Cybersecurity
6 * (C) 2026 Johannes Roth - MTG AG
7 *
8 * Botan is released under the Simplified BSD License (see license.txt)
9 **/
10
11#include <botan/internal/xmss_tree_builder.h>
12
13#include <botan/mem_ops.h>
14#include <botan/internal/xmss_common_ops.h>
15#include <botan/internal/xmss_hash.h>
16#include <algorithm>
17
18namespace Botan {
19
20namespace {
21
22/**
23* Number of leaves whose WOTS+ keys and L-trees are computed at once,
24* so that the hash calls of each step are batched across all of them
25*/
26constexpr size_t LEAF_BATCH = 128;
27
28} // namespace
29
31 size_t target_node_height,
32 const XMSS_Address& adrs_in,
33 XMSS_Hash& hash) const {
34 BOTAN_ASSERT_NOMSG(target_node_height <= 30);
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}.");
37
38 const size_t n = m_wots_params.element_size();
39 const secure_vector<uint8_t>& seed = this->public_seed();
40 const size_t last_idx = (static_cast<size_t>(1) << target_node_height) + start_idx;
41
42 const size_t batch = std::min<size_t>(LEAF_BATCH, last_idx - start_idx);
43 secure_vector<uint8_t> leaves(batch * n);
44
45 // node stack, holds all nodes on stack and one extra "pending" node. This
46 // temporary node referred to as "node" in the XMSS standard document stays
47 // a pending element, meaning it is not regarded as element on the stack
48 // until level is increased.
49 std::vector<secure_vector<uint8_t>> nodes(target_node_height + 1, secure_vector<uint8_t>(n));
50 std::vector<uint8_t> node_levels(target_node_height + 1);
51
52 uint8_t level = 0; // current level on the node stack.
53
54 XMSS_Address adrs(adrs_in);
56
57 for(size_t i = start_idx; i < last_idx; i++) {
58 const size_t b = (i - start_idx) % batch;
59 if(b == 0) {
60 const size_t count = std::min(batch, last_idx - i);
61 compute_leaves(std::span(leaves).first(count * n), i, count, adrs, hash);
62 }
63
64 copy_mem(nodes[level], std::span(leaves).subspan(b * n, n));
65 node_levels[level] = 0;
66
67 adrs.set_tree_height(0);
68 adrs.set_tree_index(static_cast<uint32_t>(i));
69
70 while(level > 0 && node_levels[level] == node_levels[level - 1]) {
71 adrs.set_tree_index(((adrs.get_tree_index() - 1) >> 1));
72 XMSS_Common_Ops::randomize_tree_hash(nodes[level - 1], nodes[level - 1], nodes[level], adrs, seed, hash, n);
73 node_levels[level - 1]++;
74 level--; //Pop stack top element
75 adrs.set_tree_height(adrs.get_tree_height() + 1);
76 }
77 level++; //push temporary node to stack
78 }
79 return nodes[level - 1];
80}
81
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 {
84 const size_t n = m_wots_params.element_size();
85 const size_t len = m_wots_params.len();
86
87 BOTAN_ASSERT_NOMSG(leaves.size() == count * n);
88
89 XMSS_Address ots_adrs(adrs);
90 ots_adrs.set_type(XMSS_Address::Type::OTS_Hash_Address);
91
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));
97 }
98 }
99
100 secure_vector<uint8_t> keys(count * len * n);
101 wots_private_keys(keys, ots_addrs, hash);
102
103 // Algorithm 4: "WOTS_genPK", transforming the private keys in place
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));
106 xmss_wots_chains(m_wots_params, keys, from, to, ots_addrs, public_seed(), hash);
107
108 XMSS_Address ltree_adrs(adrs);
109 ltree_adrs.set_type(XMSS_Address::Type::LTree_Address);
110
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));
114 }
115 XMSS_Common_Ops::create_l_trees(leaves, keys, ltree_addrs, public_seed(), hash, n, len);
116}
117
118void XMSS_Tree_Builder::wots_private_keys(std::span<uint8_t> sks,
119 std::span<const XMSS_Address> addrs,
120 XMSS_Hash& hash) const {
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();
124
125 BOTAN_ASSERT_NOMSG(sks.size() == count * n && count % len == 0);
126
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);
131
132 std::vector<std::span<uint8_t>> outputs(count);
133 std::vector<std::span<const uint8_t>> data(count);
134
135 for(size_t i = 0; i < count; ++i) {
136 const auto slot = std::span(data_arena).subspan(i * data_len, data_len);
137 copy_mem(slot.first(public_seed().size()), public_seed());
138 copy_mem(slot.subspan(public_seed().size()), addrs[i].bytes());
139
140 outputs[i] = sks.subspan(i * n, n);
141 data[i] = slot;
142 }
143
144 hash.prf_keygen_batch(outputs, m_private_seed, data);
145 return;
146 }
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]);
152 }
153 }
154 return;
155 }
156 }
157
158 throw Invalid_State("WOTS derivation method is out of the enum's range");
159}
160
162 switch(m_wots_derivation_method) {
164 return XMSS_WOTS_PrivateKey(m_wots_params, public_seed(), m_private_seed, adrs, hash);
166 return XMSS_WOTS_PrivateKey(m_wots_params, m_private_seed, adrs, hash);
167 }
168
169 throw Invalid_State("WOTS derivation method is out of the enum's range");
170}
171
172} // namespace Botan
#define BOTAN_ASSERT_NOMSG(expr)
Definition assert.h:82
#define BOTAN_ASSERT(expr, assertion_made)
Definition assert.h:69
uint32_t get_tree_index() const
void set_type(Type type)
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
void xmss_wots_chains(const XMSS_WOTS_Parameters &params, 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)
Definition mem_ops.h:144
std::vector< T, secure_allocator< T > > secure_vector
Definition secmem.h:128