Botan 3.14.1
Crypto and TLS for C&
xmss_common_ops.cpp
Go to the documentation of this file.
1/*
2 * XMSS Common Ops
3 * Operations shared by XMSS signature generation and verification operations.
4 * (C) 2016,2017 Matthias Gierlings
5 *
6 * Botan is released under the Simplified BSD License (see license.txt)
7 **/
8
9#include <botan/internal/xmss_common_ops.h>
10
11#include <botan/mem_ops.h>
12#include <botan/internal/xmss_hash.h>
13#include <botan/internal/xmss_wots.h>
14#include <array>
15
16namespace Botan {
17
19 const secure_vector<uint8_t>& left,
20 const secure_vector<uint8_t>& right,
21 XMSS_Address adrs,
22 const secure_vector<uint8_t>& seed,
23 XMSS_Hash& hash,
24 size_t element_size) {
27 hash.prf(key, seed, adrs.bytes());
28
30 secure_vector<uint8_t> bitmask_l;
31 hash.prf(bitmask_l, seed, adrs.bytes());
32
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}
48
50 const wots_keysig_t& pk,
51 XMSS_Address adrs,
52 const secure_vector<uint8_t>& seed,
53 XMSS_Hash& hash,
54 size_t element_size,
55 size_t wots_len) {
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}
68
69void XMSS_Common_Ops::create_l_trees(std::span<uint8_t> leaves,
70 std::span<uint8_t> pks,
71 std::span<XMSS_Address> addrs,
72 std::span<const uint8_t> seed,
73 XMSS_Hash& hash,
74 size_t element_size,
75 size_t wots_len) {
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}
166
168 const XMSS_TreeSignature& tree_sig,
169 const secure_vector<uint8_t>& msg,
170 XMSS_Address adrs,
171 const secure_vector<uint8_t>& seed,
172 XMSS_Hash& hash,
173 const XMSS_WOTS_Parameters& wots_params,
174 size_t tree_height) {
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}
207
208} // namespace Botan
#define BOTAN_ASSERT_NOMSG(expr)
Definition assert.h:82
#define BOTAN_ASSERT(expr, assertion_made)
Definition assert.h:69
void set_key_mask_mode(Key_Mask value)
void set_ots_address(uint32_t value)
uint32_t get_tree_index() const
void set_type(Type type)
void set_tree_height(uint32_t value)
void set_tree_index(uint32_t value)
std::span< const uint8_t > bytes() const
void set_ltree_address(uint32_t value)
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 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)
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)
void prf(secure_vector< uint8_t > &result, std::span< const uint8_t > key, std::span< const uint8_t > data)
Definition xmss_hash.h:60
void prf_batch(std::span< std::span< uint8_t > > outputs, std::span< const uint8_t > key, std::span< std::span< const uint8_t > > data)
Definition xmss_hash.h:153
void h_batch(std::span< std::span< uint8_t > > outputs, std::span< std::span< const uint8_t > > keys, std::span< std::span< const uint8_t > > data)
Definition xmss_hash.h:185
void h(secure_vector< uint8_t > &result, std::span< const uint8_t > key, std::span< const uint8_t > data)
Definition xmss_hash.h:100
const wots_keysig_t & key_data() const
Definition xmss_wots.h:32
constexpr void copy_mem(T *out, const T *in, size_t n)
Definition mem_ops.h:144
std::vector< secure_vector< uint8_t > > wots_keysig_t
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
std::vector< T, secure_allocator< T > > secure_vector
Definition secmem.h:128
wots_keysig_t authentication_path