Botan 3.5.0
Crypto and TLS for C&
xmss_privatekey.cpp
Go to the documentation of this file.
1/*
2 * XMSS Private Key
3 * An XMSS: Extended Hash-Based Siganture private key.
4 * The XMSS private key does not support the X509 and PKCS7 standard. Instead
5 * the raw format described in [1] is used.
6 *
7 * [1] XMSS: Extended Hash-Based Signatures,
8 * Request for Comments: 8391
9 * Release: May 2018.
10 * https://datatracker.ietf.org/doc/rfc8391/
11 *
12 * (C) 2016,2017,2018 Matthias Gierlings
13 * (C) 2019 Jack Lloyd
14 * (C) 2023 René Meusel - Rohde & Schwarz Cybersecurity
15 *
16 * Botan is released under the Simplified BSD License (see license.txt)
17 **/
18
19#include <botan/xmss.h>
20
21#include <botan/ber_dec.h>
22#include <botan/der_enc.h>
23#include <botan/internal/loadstor.h>
24#include <botan/internal/stl_util.h>
25#include <botan/internal/xmss_common_ops.h>
26#include <botan/internal/xmss_index_registry.h>
27#include <botan/internal/xmss_signature_operation.h>
28#include <iterator>
29
30#if defined(BOTAN_HAS_THREAD_UTILS)
31 #include <botan/internal/thread_pool.h>
32#endif
33
34namespace Botan {
35
36namespace {
37
38// fall back to raw decoding for previous versions, which did not encode an OCTET STRING
39secure_vector<uint8_t> extract_raw_private_key(std::span<const uint8_t> key_bits, const XMSS_Parameters& xmss_params) {
41
42 // The public part of the input key bits was already parsed, so we can
43 // decide depending on the buffer length whether this must be BER decoded.
44 if(key_bits.size() == xmss_params.raw_private_key_size() ||
45 key_bits.size() == xmss_params.raw_legacy_private_key_size()) {
46 raw_key.assign(key_bits.begin(), key_bits.end());
47 } else {
48 DataSource_Memory src(key_bits);
49 BER_Decoder(src).decode(raw_key, ASN1_Type::OctetString).verify_end();
50 }
51
52 return raw_key;
53}
54
55} // namespace
56
57class XMSS_PrivateKey_Internal {
58 public:
59 XMSS_PrivateKey_Internal(const XMSS_Parameters& xmss_params,
60 const XMSS_WOTS_Parameters& wots_params,
61 WOTS_Derivation_Method wots_derivation_method,
62 RandomNumberGenerator& rng) :
63 m_xmss_params(xmss_params),
64 m_wots_params(wots_params),
65 m_wots_derivation_method(wots_derivation_method),
66 m_hash(xmss_params),
67 m_prf(rng.random_vec(xmss_params.element_size())),
68 m_private_seed(rng.random_vec(xmss_params.element_size())),
69 m_index_reg(XMSS_Index_Registry::get_instance()) {}
70
71 XMSS_PrivateKey_Internal(const XMSS_Parameters& xmss_params,
72 const XMSS_WOTS_Parameters& wots_params,
73 WOTS_Derivation_Method wots_derivation_method,
74 secure_vector<uint8_t> private_seed,
76 m_xmss_params(xmss_params),
77 m_wots_params(wots_params),
78 m_wots_derivation_method(wots_derivation_method),
79 m_hash(m_xmss_params),
80 m_prf(std::move(prf)),
81 m_private_seed(std::move(private_seed)),
82 m_index_reg(XMSS_Index_Registry::get_instance()) {}
83
84 XMSS_PrivateKey_Internal(const XMSS_Parameters& xmss_params,
85 const XMSS_WOTS_Parameters& wots_params,
86 std::span<const uint8_t> key_bits) :
87 m_xmss_params(xmss_params),
88 m_wots_params(wots_params),
89 m_hash(m_xmss_params),
90 m_index_reg(XMSS_Index_Registry::get_instance()) {
91 /*
92 The code requires sizeof(size_t) >= ceil(tree_height / 8)
93
94 Maximum supported tree height is 20, ceil(20/8) == 3, so 4 byte
95 size_t is sufficient for all defined parameters, or even a
96 (hypothetical) tree height 32, which would be extremely slow to
97 compute.
98 */
99 static_assert(sizeof(size_t) >= 4, "size_t is big enough to support leaf index");
100
101 const secure_vector<uint8_t> raw_key = extract_raw_private_key(key_bits, xmss_params);
102
103 if(raw_key.size() != m_xmss_params.raw_private_key_size() &&
104 raw_key.size() != m_xmss_params.raw_legacy_private_key_size()) {
105 throw Decoding_Error("Invalid XMSS private key size");
106 }
107
108 BufferSlicer s(raw_key);
109
110 // We're not interested in the public key here
111 s.skip(m_xmss_params.raw_public_key_size());
112
113 auto unused_leaf_bytes = s.take(sizeof(uint32_t));
114 size_t unused_leaf = load_be<uint32_t>(unused_leaf_bytes.data(), 0);
115 if(unused_leaf >= (1ULL << m_xmss_params.tree_height())) {
116 throw Decoding_Error("XMSS private key leaf index out of bounds");
117 }
118
119 m_prf = s.copy_as_secure_vector(m_xmss_params.element_size());
120 m_private_seed = s.copy_as_secure_vector(m_xmss_params.element_size());
121 set_unused_leaf_index(unused_leaf);
122
123 // Legacy keys generated prior to Botan 3.x don't feature a
124 // WOTS+ key derivation method encoded in their private key.
125 m_wots_derivation_method =
126 (s.empty()) ? WOTS_Derivation_Method::Botan2x : static_cast<WOTS_Derivation_Method>(s.take(1).front());
127
128 BOTAN_ASSERT_NOMSG(s.empty());
129 }
130
131 secure_vector<uint8_t> serialize(std::vector<uint8_t> raw_public_key) const {
132 std::vector<uint8_t> unused_index(4);
133 store_be(static_cast<uint32_t>(unused_leaf_index()), unused_index.data());
134
135 std::vector<uint8_t> wots_derivation_method;
136 wots_derivation_method.push_back(static_cast<uint8_t>(m_wots_derivation_method));
137
139 raw_public_key, unused_index, m_prf, m_private_seed, wots_derivation_method);
140 }
141
142 XMSS_Hash& hash() { return m_hash; }
143
144 const secure_vector<uint8_t>& prf_value() const { return m_prf; }
145
146 const secure_vector<uint8_t>& private_seed() { return m_private_seed; }
147
148 const XMSS_WOTS_Parameters& wots_parameters() { return m_wots_params; }
149
150 WOTS_Derivation_Method wots_derivation_method() const { return m_wots_derivation_method; }
151
152 XMSS_Index_Registry& index_registry() { return m_index_reg; }
153
154 std::shared_ptr<Atomic<size_t>> recover_global_leaf_index() const {
156 m_private_seed.size() == m_xmss_params.element_size() && m_prf.size() == m_xmss_params.element_size(),
157 "Trying to retrieve index for partially initialized key");
158 return m_index_reg.get(m_private_seed, m_prf);
159 }
160
161 void set_unused_leaf_index(size_t idx) {
162 if(idx >= (1ULL << m_xmss_params.tree_height())) {
163 throw Decoding_Error("XMSS private key leaf index out of bounds");
164 } else {
165 std::atomic<size_t>& index = static_cast<std::atomic<size_t>&>(*recover_global_leaf_index());
166 size_t current = 0;
167
168 do {
169 current = index.load();
170 if(current > idx) {
171 return;
172 }
173 } while(!index.compare_exchange_strong(current, idx));
174 }
175 }
176
177 size_t reserve_unused_leaf_index() {
178 size_t idx = (static_cast<std::atomic<size_t>&>(*recover_global_leaf_index())).fetch_add(1);
179 if(idx >= m_xmss_params.total_number_of_signatures()) {
180 throw Decoding_Error("XMSS private key, one time signatures exhaused");
181 }
182 return idx;
183 }
184
185 size_t unused_leaf_index() const { return *recover_global_leaf_index(); }
186
187 size_t remaining_signatures() const {
188 return m_xmss_params.total_number_of_signatures() - *recover_global_leaf_index();
189 }
190
191 private:
192 XMSS_Parameters m_xmss_params;
193 XMSS_WOTS_Parameters m_wots_params;
194 WOTS_Derivation_Method m_wots_derivation_method;
195
196 XMSS_Hash m_hash;
198 secure_vector<uint8_t> m_private_seed;
199 XMSS_Index_Registry& m_index_reg;
200};
201
202XMSS_PrivateKey::XMSS_PrivateKey(std::span<const uint8_t> key_bits) :
203 XMSS_PublicKey(key_bits),
204 m_private(std::make_shared<XMSS_PrivateKey_Internal>(m_xmss_params, m_wots_params, key_bits)) {}
205
208 WOTS_Derivation_Method wots_derivation_method) :
209 XMSS_PublicKey(xmss_algo_id, rng),
210 m_private(std::make_shared<XMSS_PrivateKey_Internal>(m_xmss_params, m_wots_params, wots_derivation_method, rng)) {
211 XMSS_Address adrs;
212 m_root = tree_hash(0, XMSS_PublicKey::m_xmss_params.tree_height(), adrs);
213}
214
216 size_t idx_leaf,
217 secure_vector<uint8_t> wots_priv_seed,
220 secure_vector<uint8_t> public_seed,
221 WOTS_Derivation_Method wots_derivation_method) :
222 XMSS_PublicKey(xmss_algo_id, std::move(root), std::move(public_seed)),
223 m_private(std::make_shared<XMSS_PrivateKey_Internal>(
224 m_xmss_params, m_wots_params, wots_derivation_method, std::move(wots_priv_seed), std::move(prf))) {
225 m_private->set_unused_leaf_index(idx_leaf);
226 BOTAN_ARG_CHECK(m_private->prf_value().size() == m_xmss_params.element_size(),
227 "XMSS: unexpected byte length of PRF value");
228 BOTAN_ARG_CHECK(m_private->private_seed().size() == m_xmss_params.element_size(),
229 "XMSS: unexpected byte length of private seed");
230}
231
232secure_vector<uint8_t> XMSS_PrivateKey::tree_hash(size_t start_idx, size_t target_node_height, XMSS_Address& adrs) {
233 BOTAN_ASSERT_NOMSG(target_node_height <= 30);
234 BOTAN_ASSERT((start_idx % (static_cast<size_t>(1) << target_node_height)) == 0,
235 "Start index must be divisible by 2^{target node height}.");
236
237#if defined(BOTAN_HAS_THREAD_UTILS)
238 // dertermine number of parallel tasks to split the tree_hashing into.
239
241
242 const size_t split_level = std::min(target_node_height, thread_pool.worker_count());
243
244 // skip parallelization overhead for leaf nodes.
245 if(split_level == 0) {
247 tree_hash_subtree(result, start_idx, target_node_height, adrs);
248 return result;
249 }
250
251 const size_t subtrees = static_cast<size_t>(1) << split_level;
252 const size_t last_idx = (static_cast<size_t>(1) << (target_node_height)) + start_idx;
253 const size_t offs = (last_idx - start_idx) / subtrees;
254 // this cast cannot overflow because target_node_height is limited
255 uint8_t level = static_cast<uint8_t>(split_level); // current level in the tree
256
257 BOTAN_ASSERT((last_idx - start_idx) % subtrees == 0,
258 "Number of worker threads in tree_hash need to divide range "
259 "of calculated nodes.");
260
261 std::vector<secure_vector<uint8_t>> nodes(subtrees,
263 std::vector<XMSS_Address> node_addresses(subtrees, adrs);
264 std::vector<XMSS_Hash> xmss_hash(subtrees, m_private->hash());
265 std::vector<std::future<void>> work;
266
267 // Calculate multiple subtrees in parallel.
268 for(size_t i = 0; i < subtrees; i++) {
269 using tree_hash_subtree_fn_t =
270 void (XMSS_PrivateKey::*)(secure_vector<uint8_t>&, size_t, size_t, XMSS_Address&, XMSS_Hash&);
271
272 tree_hash_subtree_fn_t work_fn = &XMSS_PrivateKey::tree_hash_subtree;
273
274 work.push_back(thread_pool.run(work_fn,
275 this,
276 std::ref(nodes[i]),
277 start_idx + i * offs,
278 target_node_height - split_level,
279 std::ref(node_addresses[i]),
280 std::ref(xmss_hash[i])));
281 }
282
283 for(auto& w : work) {
284 w.get();
285 }
286 work.clear();
287
288 // Parallelize the top tree levels horizontally
289 while(level-- > 1) {
290 std::vector<secure_vector<uint8_t>> ro_nodes(nodes.begin(),
291 nodes.begin() + (static_cast<size_t>(1) << (level + 1)));
292
293 for(size_t i = 0; i < (static_cast<size_t>(1) << level); i++) {
294 BOTAN_ASSERT_NOMSG(xmss_hash.size() > i);
295
296 node_addresses[i].set_tree_height(static_cast<uint32_t>(target_node_height - (level + 1)));
297 node_addresses[i].set_tree_index((node_addresses[2 * i + 1].get_tree_index() - 1) >> 1);
298
299 work.push_back(thread_pool.run(&XMSS_Common_Ops::randomize_tree_hash,
300 std::ref(nodes[i]),
301 std::cref(ro_nodes[2 * i]),
302 std::cref(ro_nodes[2 * i + 1]),
303 std::ref(node_addresses[i]),
304 std::cref(this->public_seed()),
305 std::ref(xmss_hash[i]),
306 std::cref(m_xmss_params)));
307 }
308
309 for(auto& w : work) {
310 w.get();
311 }
312 work.clear();
313 }
314
315 // Avoid creation an extra thread to calculate root node.
316 node_addresses[0].set_tree_height(static_cast<uint32_t>(target_node_height - 1));
317 node_addresses[0].set_tree_index((node_addresses[1].get_tree_index() - 1) >> 1);
319 nodes[0], nodes[0], nodes[1], node_addresses[0], this->public_seed(), m_private->hash(), m_xmss_params);
320 return nodes[0];
321#else
323 tree_hash_subtree(result, start_idx, target_node_height, adrs, m_private->hash());
324 return result;
325#endif
326}
327
328void XMSS_PrivateKey::tree_hash_subtree(secure_vector<uint8_t>& result,
329 size_t start_idx,
330 size_t target_node_height,
331 XMSS_Address& adrs) {
332 return tree_hash_subtree(result, start_idx, target_node_height, adrs, m_private->hash());
333}
334
335void XMSS_PrivateKey::tree_hash_subtree(
336 secure_vector<uint8_t>& result, size_t start_idx, size_t target_node_height, XMSS_Address& adrs, XMSS_Hash& hash) {
337 const secure_vector<uint8_t>& seed = this->public_seed();
338
339 std::vector<secure_vector<uint8_t>> nodes(target_node_height + 1,
341
342 // node stack, holds all nodes on stack and one extra "pending" node. This
343 // temporary node referred to as "node" in the XMSS standard document stays
344 // a pending element, meaning it is not regarded as element on the stack
345 // until level is increased.
346 std::vector<uint8_t> node_levels(target_node_height + 1);
347
348 uint8_t level = 0; // current level on the node stack.
349 const size_t last_idx = (static_cast<size_t>(1) << target_node_height) + start_idx;
350
351 for(size_t i = start_idx; i < last_idx; i++) {
353 adrs.set_ots_address(static_cast<uint32_t>(i));
354
355 XMSS_WOTS_PublicKey pk = this->wots_public_key_for(adrs, hash);
356
358 adrs.set_ltree_address(static_cast<uint32_t>(i));
359 XMSS_Common_Ops::create_l_tree(nodes[level], pk.key_data(), adrs, seed, hash, m_xmss_params);
360 node_levels[level] = 0;
361
363 adrs.set_tree_height(0);
364 adrs.set_tree_index(static_cast<uint32_t>(i));
365
366 while(level > 0 && node_levels[level] == node_levels[level - 1]) {
367 adrs.set_tree_index(((adrs.get_tree_index() - 1) >> 1));
369 nodes[level - 1], nodes[level - 1], nodes[level], adrs, seed, hash, m_xmss_params);
370 node_levels[level - 1]++;
371 level--; //Pop stack top element
372 adrs.set_tree_height(adrs.get_tree_height() + 1);
373 }
374 level++; //push temporary node to stack
375 }
376 result = nodes[level - 1];
377}
378
379XMSS_WOTS_PublicKey XMSS_PrivateKey::wots_public_key_for(XMSS_Address& adrs, XMSS_Hash& hash) const {
380 const auto private_key = wots_private_key_for(adrs, hash);
381 return XMSS_WOTS_PublicKey(m_private->wots_parameters(), m_public_seed, private_key, adrs, hash);
382}
383
384XMSS_WOTS_PrivateKey XMSS_PrivateKey::wots_private_key_for(XMSS_Address& adrs, XMSS_Hash& hash) const {
385 switch(wots_derivation_method()) {
387 return XMSS_WOTS_PrivateKey(
388 m_private->wots_parameters(), m_public_seed, m_private->private_seed(), adrs, hash);
390 return XMSS_WOTS_PrivateKey(m_private->wots_parameters(), m_private->private_seed(), adrs, hash);
391 }
392
393 throw Invalid_State("WOTS derivation method is out of the enum's range");
394}
395
399
400size_t XMSS_PrivateKey::reserve_unused_leaf_index() {
401 return m_private->reserve_unused_leaf_index();
402}
403
405 return m_private->unused_leaf_index();
406}
407
409 return m_private->remaining_signatures();
410}
411
412std::optional<uint64_t> XMSS_PrivateKey::remaining_operations() const {
413 return m_private->remaining_signatures();
414}
415
416const secure_vector<uint8_t>& XMSS_PrivateKey::prf_value() const {
417 return m_private->prf_value();
418}
419
421 return m_private->serialize(raw_public_key());
422}
423
425 return m_private->wots_derivation_method();
426}
427
428std::unique_ptr<Public_Key> XMSS_PrivateKey::public_key() const {
429 return std::make_unique<XMSS_PublicKey>(xmss_parameters().oid(), root(), public_seed());
430}
431
432std::unique_ptr<PK_Ops::Signature> XMSS_PrivateKey::create_signature_op(RandomNumberGenerator& /*rng*/,
433 std::string_view /*params*/,
434 std::string_view provider) const {
435 if(provider == "base" || provider.empty()) {
436 return std::make_unique<XMSS_Signature_Operation>(*this);
437 }
438
439 throw Provider_Not_Found(algo_name(), provider);
440}
441
442} // namespace Botan
#define BOTAN_ASSERT_NOMSG(expr)
Definition assert.h:59
#define BOTAN_ARG_CHECK(expr, msg)
Definition assert.h:29
#define BOTAN_ASSERT(expr, assertion_made)
Definition assert.h:50
secure_vector< uint8_t > get_contents()
Definition der_enc.cpp:132
DER_Encoder & encode(bool b)
Definition der_enc.cpp:250
size_t worker_count() const
Definition thread_pool.h:52
auto run(F &&f, Args &&... args) -> std::future< typename std::invoke_result< F, Args... >::type >
Definition thread_pool.h:66
static Thread_Pool & global_instance()
static void create_l_tree(secure_vector< uint8_t > &result, wots_keysig_t pk, XMSS_Address &adrs, const secure_vector< uint8_t > &seed, XMSS_Hash &hash, const XMSS_Parameters &params)
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, const XMSS_Parameters &params)
std::shared_ptr< Atomic< size_t > > get(const secure_vector< uint8_t > &private_seed, const secure_vector< uint8_t > &prf)
size_t total_number_of_signatures() const
size_t raw_private_key_size() const
size_t raw_public_key_size() const
size_t raw_legacy_private_key_size() const
size_t element_size() const
std::unique_ptr< Public_Key > public_key() const override
size_t remaining_signatures() const
size_t unused_leaf_index() const
std::optional< uint64_t > remaining_operations() const override
Retrieves the number of remaining operations if this is a stateful private key.
WOTS_Derivation_Method wots_derivation_method() const
secure_vector< uint8_t > raw_private_key() const
secure_vector< uint8_t > private_key_bits() const override
XMSS_PrivateKey(XMSS_Parameters::xmss_algorithm_t xmss_algo_id, RandomNumberGenerator &rng, WOTS_Derivation_Method wots_derivation_method=WOTS_Derivation_Method::NIST_SP800_208)
std::unique_ptr< PK_Ops::Signature > create_signature_op(RandomNumberGenerator &, std::string_view, std::string_view provider) const override
const secure_vector< uint8_t > & root() const
Definition xmss.h:118
secure_vector< uint8_t > m_root
Definition xmss.h:126
const secure_vector< uint8_t > & public_seed() const
Definition xmss.h:116
secure_vector< uint8_t > m_public_seed
Definition xmss.h:127
const XMSS_Parameters & xmss_parameters() const
Definition xmss.h:120
XMSS_Parameters m_xmss_params
Definition xmss.h:124
std::vector< uint8_t > raw_public_key() const
std::string algo_name() const override
Definition xmss.h:72
Gf448Elem root(const Gf448Elem &elem)
Compute the root of elem in the field.
constexpr auto concat(Rs &&... ranges)
Definition stl_util.h:262
std::vector< T, secure_allocator< T > > secure_vector
Definition secmem.h:61
WOTS_Derivation_Method
Definition xmss.h:138
constexpr auto store_be(ParamTs &&... params)
Definition loadstor.h:707
constexpr auto load_be(ParamTs &&... params)
Definition loadstor.h:467