Botan 3.14.1
Crypto and TLS for C&
xmss_wots.cpp
Go to the documentation of this file.
1/*
2 * XMSS WOTS Public and Private Key
3 *
4 * A Winternitz One Time Signature public/private key for use with
5 * Extended Hash-Based Signatures.
6 *
7 * (C) 2016,2017,2018 Matthias Gierlings
8 * 2023 René Meusel - Rohde & Schwarz Cybersecurity
9 * 2026 Jack Lloyd
10 *
11 * Botan is released under the Simplified BSD License (see license.txt)
12 **/
13
14#include <botan/internal/xmss_wots.h>
15
16#include <botan/mem_ops.h>
17#include <botan/internal/xmss_address.h>
18#include <botan/internal/xmss_hash.h>
19#include <botan/internal/xmss_tools.h>
20
21namespace Botan {
22
23namespace {
24
25/**
26* Algorithm 1 (base_w) followed by the WOTS+ checksum, as used by the
27* signing and verification routines in RFC 8391. The result is a single
28* buffer of length params.len() holding the len_1 base-w digits of the
29* message followed by the len_2 base-w digits of the checksum.
30*/
31secure_vector<uint8_t> base_w_with_checksum(const XMSS_WOTS_Parameters& params, std::span<const uint8_t> input) {
32 const size_t len_1 = params.len_1();
33 const size_t len_2 = params.len_2();
34 const size_t lg_w = params.lg_w();
35 const uint8_t mask = static_cast<uint8_t>(params.wots_parameter() - 1);
36
37 BOTAN_ASSERT_NOMSG(input.size() * 8 >= len_1 * lg_w);
38
39 secure_vector<uint8_t> result(len_1 + len_2);
40
41 size_t in = 0;
42 size_t total = 0;
43 size_t bits = 0;
44 for(size_t i = 0; i < len_1; ++i) {
45 if(bits == 0) {
46 total = input[in++];
47 bits = 8;
48 }
49 bits -= lg_w;
50 result[i] = static_cast<uint8_t>((total >> bits) & mask);
51 }
52
53 size_t csum = 0;
54 for(size_t i = 0; i < len_1; ++i) {
55 csum += params.wots_parameter() - 1 - result[i];
56 }
57
58 for(size_t i = 0; i < len_2; ++i) {
59 const size_t shift = lg_w * (len_2 - 1 - i);
60 result[len_1 + i] = static_cast<uint8_t>((csum >> shift) & mask);
61 }
62
63 return result;
64}
65
66/**
67 * Algorithm 2 applied to the chains of a single WOTS+ key
68 *
69 * @param params The WOTS parameters to use
70 * @param[in,out] nodes The chain nodes, transformed in place
71 * @param from Per chain, the first hash address to apply
72 * @param to Per chain, the hash address to stop at (exclusive)
73 * @param adrs The OTS hash address of the key
74 * @param seed A seed.
75 * @param hash Instance of XMSS_Hash, that may only be used by the thread
76 * executing chains.
77 **/
78void chains(const XMSS_WOTS_Parameters& params,
79 wots_keysig_t& nodes,
80 std::span<const uint8_t> from,
81 std::span<const uint8_t> to,
82 const XMSS_Address& adrs,
83 std::span<const uint8_t> seed,
84 XMSS_Hash& hash) {
85 const size_t len = nodes.size();
86 const size_t n = hash.output_length();
87
88 std::vector<XMSS_Address> addrs(len, adrs);
89 secure_vector<uint8_t> flat(len * n);
90 for(size_t i = 0; i < len; ++i) {
91 BOTAN_ASSERT_NOMSG(nodes[i].size() == n);
92 addrs[i].set_chain_address(static_cast<uint32_t>(i));
93 copy_mem(std::span(flat).subspan(i * n, n), nodes[i]);
94 }
95
96 xmss_wots_chains(params, flat, from, to, addrs, seed, hash);
97
98 for(size_t i = 0; i < len; ++i) {
99 copy_mem(nodes[i], std::span(flat).subspan(i * n, n));
100 }
101}
102
103} // namespace
104
105/*
106 * Note that RFC 8391 defines this algorithm recursively (building up the
107 * iterations before any calculation) using 'steps' as the iterator and a
108 * recursion base with 'steps == 0'.
109 * Instead, we implement it iteratively using 's' as iterator. This makes
110 * 'set_hash_address(s)' equivalent to 'ADRS.setHashAddress(i + s - 1)'.
111 */
113 std::span<uint8_t> nodes,
114 std::span<const uint8_t> from,
115 std::span<const uint8_t> to,
116 std::span<XMSS_Address> addrs,
117 std::span<const uint8_t> seed,
118 XMSS_Hash& hash) {
119 const size_t count = addrs.size();
120 const size_t n = hash.output_length();
121
122 BOTAN_ASSERT_NOMSG(nodes.size() == count * n);
123 BOTAN_ASSERT_NOMSG(from.size() == count && to.size() == count);
124
125 for(size_t i = 0; i < count; ++i) {
126 BOTAN_ASSERT_NOMSG(to[i] < params.wots_parameter());
127 }
128
129 // Each step computes the bitmask and the key of every active chain
130 // with a single PRF batch. The addresses differ only in the key/mask
131 // mode, so a second set of addresses in mask mode is kept alongside.
132 std::vector<XMSS_Address> mask_addrs(addrs.begin(), addrs.end());
133 for(size_t i = 0; i < count; ++i) {
134 mask_addrs[i].set_key_mask_mode(XMSS_Address::Key_Mask::Mask_Mode);
135 addrs[i].set_key_mask_mode(XMSS_Address::Key_Mask::Key_Mode);
136 }
137
138 // Lane descriptors for the case that every chain is active; the
139 // bitmasks are lanes [0, count) and the keys lanes [count, 2*count).
140 // The address bytes are updated in place each step so the spans
141 // stay valid throughout. The filtered variants are subsets of these.
142 secure_vector<uint8_t> prf_outputs(2 * count * n);
143 std::vector<std::span<uint8_t>> all_prf_out(2 * count);
144 std::vector<std::span<const uint8_t>> all_prf_in(2 * count);
145 std::vector<std::span<uint8_t>> all_node(count);
146 std::vector<std::span<const uint8_t>> all_key(count);
147 std::vector<std::span<const uint8_t>> all_node_in(count);
148
149 for(size_t i = 0; i < count; ++i) {
150 all_prf_out[i] = std::span(prf_outputs).subspan(i * n, n);
151 all_prf_out[count + i] = std::span(prf_outputs).subspan((count + i) * n, n);
152 all_prf_in[i] = mask_addrs[i].bytes();
153 all_prf_in[count + i] = addrs[i].bytes();
154 all_node[i] = nodes.subspan(i * n, n);
155 all_key[i] = all_prf_out[count + i];
156 all_node_in[i] = all_node[i];
157 }
158
159 std::vector<size_t> active;
160 std::vector<std::span<uint8_t>> prf_out;
161 std::vector<std::span<const uint8_t>> prf_in;
162 std::vector<std::span<uint8_t>> node_out;
163 std::vector<std::span<const uint8_t>> keys;
164 std::vector<std::span<const uint8_t>> node_in;
165
166 for(size_t s = 0; s + 1 < params.wots_parameter(); ++s) {
167 active.clear();
168 for(size_t i = 0; i < count; ++i) {
169 if(from[i] <= s && s < to[i]) {
170 active.push_back(i);
171 }
172 }
173 if(active.empty()) {
174 continue;
175 }
176
177 for(const size_t i : active) {
178 addrs[i].set_hash_address(static_cast<uint32_t>(s));
179 mask_addrs[i].set_hash_address(static_cast<uint32_t>(s));
180 }
181
182 if(active.size() == count) {
183 hash.prf_batch(all_prf_out, seed, all_prf_in);
184
185 // Calculate tmp XOR bitmask, then f(key, tmp XOR bitmask)
186 for(size_t i = 0; i < count; ++i) {
187 xor_buf(all_node[i], all_prf_out[i]);
188 }
189 hash.f_batch(all_node, all_key, all_node_in);
190 } else {
191 prf_out.clear();
192 prf_in.clear();
193 node_out.clear();
194 keys.clear();
195 node_in.clear();
196
197 for(const size_t i : active) {
198 prf_out.push_back(all_prf_out[i]);
199 prf_in.push_back(all_prf_in[i]);
200 }
201 for(const size_t i : active) {
202 prf_out.push_back(all_prf_out[count + i]);
203 prf_in.push_back(all_prf_in[count + i]);
204 }
205 hash.prf_batch(prf_out, seed, prf_in);
206
207 for(const size_t i : active) {
208 xor_buf(all_node[i], all_prf_out[i]);
209 node_out.push_back(all_node[i]);
210 keys.push_back(all_key[i]);
211 node_in.push_back(all_node_in[i]);
212 }
213 hash.f_batch(node_out, keys, node_in);
214 }
215 }
216}
217
219 std::span<const uint8_t> public_seed,
220 wots_keysig_t signature,
221 const secure_vector<uint8_t>& msg,
222 XMSS_Address adrs,
223 XMSS_Hash& hash) :
224 XMSS_WOTS_Base(params, std::move(signature)) {
225 const secure_vector<uint8_t> msg_digest = base_w_with_checksum(m_params, msg);
226 const std::vector<uint8_t> to(m_params.len(), static_cast<uint8_t>(m_params.wots_parameter() - 1));
227
228 chains(m_params, m_key_data, msg_digest, to, adrs, public_seed, hash);
229}
230
232 std::span<const uint8_t> public_seed,
233 XMSS_Address adrs,
234 XMSS_Hash& hash) {
235 const secure_vector<uint8_t> msg_digest = base_w_with_checksum(m_params, msg);
236 auto sig = this->key_data();
237
238 const std::vector<uint8_t> from(m_params.len(), 0);
239 chains(m_params, sig, from, msg_digest, adrs, public_seed, hash);
240
241 return sig;
242}
243
245 std::span<const uint8_t> public_seed,
246 std::span<const uint8_t> private_seed,
247 XMSS_Address adrs,
248 XMSS_Hash& hash) :
249 XMSS_WOTS_Base(params) {
250 const size_t len = m_params.len();
251 const size_t n = hash.output_length();
252
253 m_key_data.resize(len);
254
255 std::vector<XMSS_Address> addrs(len, adrs);
256 const size_t data_len = public_seed.size() + adrs.size();
257 std::vector<uint8_t> data_arena(len * data_len);
258
259 std::vector<std::span<uint8_t>> outputs(len);
260 std::vector<std::span<const uint8_t>> data(len);
261
262 for(size_t i = 0; i < len; ++i) {
263 addrs[i].set_chain_address(static_cast<uint32_t>(i));
264
265 const auto slot = std::span(data_arena).subspan(i * data_len, data_len);
266 copy_mem(slot.first(public_seed.size()), public_seed);
267 copy_mem(slot.subspan(public_seed.size()), addrs[i].bytes());
268
269 m_key_data[i].resize(n);
270 outputs[i] = std::span(m_key_data[i]);
271 data[i] = slot;
272 }
273
274 hash.prf_keygen_batch(outputs, private_seed, data);
275}
276
277// Constructor for legacy XMSS_PrivateKeys
279 std::span<const uint8_t> private_seed,
280 XMSS_Address adrs,
281 XMSS_Hash& hash) :
282 XMSS_WOTS_Base(params) {
283 m_key_data.resize(m_params.len());
284
286 hash.prf(r, private_seed, adrs.bytes());
287
288 for(size_t i = 0; i < m_params.len(); ++i) {
289 xmss_concat<size_t>(m_key_data[i], i, 32);
290 hash.prf(m_key_data[i], r, m_key_data[i]);
291 }
292}
293
294} // namespace Botan
#define BOTAN_ASSERT_NOMSG(expr)
Definition assert.h:82
size_t size() const
std::span< const uint8_t > bytes() const
size_t output_length() const
Definition xmss_hash.h:196
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 prf_keygen_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:162
void f_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:171
const wots_keysig_t & key_data() const
Definition xmss_wots.h:32
XMSS_WOTS_Base(XMSS_WOTS_Parameters params)
Definition xmss_wots.h:27
wots_keysig_t m_key_data
Definition xmss_wots.h:36
XMSS_WOTS_Parameters m_params
Definition xmss_wots.h:35
XMSS_WOTS_PrivateKey(XMSS_WOTS_Parameters params, std::span< const uint8_t > public_seed, std::span< const uint8_t > private_seed, XMSS_Address adrs, XMSS_Hash &hash)
wots_keysig_t sign(const secure_vector< uint8_t > &msg, std::span< const uint8_t > public_seed, XMSS_Address adrs, XMSS_Hash &hash)
XMSS_WOTS_PublicKey(XMSS_WOTS_Parameters params, std::span< const uint8_t > public_seed, wots_keysig_t signature, const secure_vector< uint8_t > &msg, XMSS_Address adrs, XMSS_Hash &hash)
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< secure_vector< uint8_t > > wots_keysig_t
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