Botan 2.19.5 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 *
15 * Botan is released under the Simplified BSD License (see license.txt)
16 **/
17
18#include <botan/xmss.h>
19#include <botan/internal/xmss_signature_operation.h>
20#include <botan/internal/xmss_index_registry.h>
21#include <botan/internal/xmss_common_ops.h>
22#include <botan/ber_dec.h>
23#include <botan/der_enc.h>
24#include <iterator>
25
26#if defined(BOTAN_HAS_THREAD_UTILS)
27 #include <botan/internal/thread_pool.h>
28#endif
29
30 namespace Botan {
31
32 namespace {
33
34// fall back to raw decoding for previous versions, which did not encode an OCTET STRING
35secure_vector<uint8_t> extract_raw_key(const secure_vector<uint8_t>& key_bits)
36 {
37 secure_vector<uint8_t> raw_key;
38 try
39 {
40 BER_Decoder(key_bits).decode(raw_key, OCTET_STRING);
41 }
42 catch(Decoding_Error&)
43 {
44 raw_key = key_bits;
45 }
46 return raw_key;
47 }
48
49}
50
51 XMSS_PrivateKey::XMSS_PrivateKey(const secure_vector<uint8_t>& key_bits)
52 : XMSS_PublicKey(unlock(key_bits)),
53 m_wots_priv_key(m_wots_params.oid(), m_public_seed),
54 m_hash(xmss_hash_function()),
55 m_index_reg(XMSS_Index_Registry::get_instance())
56 {
57 /*
58 The code requires sizeof(size_t) >= ceil(tree_height / 8)
59
60 Maximum supported tree height is 20, ceil(20/8) == 3, so 4 byte
61 size_t is sufficient for all defined parameters, or even a
62 (hypothetical) tree height 32, which would be extremely slow to
63 compute.
64 */
65 static_assert(sizeof(size_t) >= 4, "size_t is big enough to support leaf index");
66
67 secure_vector<uint8_t> raw_key = extract_raw_key(key_bits);
68
69 if(raw_key.size() != XMSS_PrivateKey::size())
70 {
71 throw Decoding_Error("Invalid XMSS private key size");
72 }
73
74 // extract & copy unused leaf index from raw_key
75 uint64_t unused_leaf = 0;
76 auto begin = (raw_key.begin() + XMSS_PublicKey::size());
77 auto end = raw_key.begin() + XMSS_PublicKey::size() + sizeof(uint32_t);
78
79 for(auto& i = begin; i != end; i++)
80 {
81 unused_leaf = ((unused_leaf << 8) | *i);
82 }
83
84 if(unused_leaf >= (1ull << XMSS_PublicKey::m_xmss_params.tree_height()))
85 {
86 throw Decoding_Error("XMSS private key leaf index out of bounds");
87 }
88
89 begin = end;
90 end = begin + XMSS_PublicKey::m_xmss_params.element_size();
91 m_prf.clear();
92 m_prf.reserve(XMSS_PublicKey::m_xmss_params.element_size());
93 std::copy(begin, end, std::back_inserter(m_prf));
94
95 begin = end;
96 end = begin + m_wots_params.element_size();
97 m_wots_priv_key.set_private_seed(secure_vector<uint8_t>(begin, end));
98 set_unused_leaf_index(static_cast<size_t>(unused_leaf));
99 }
100
101 XMSS_PrivateKey::XMSS_PrivateKey(
102 XMSS_Parameters::xmss_algorithm_t xmss_algo_id,
103 RandomNumberGenerator& rng)
104 : XMSS_PublicKey(xmss_algo_id, rng),
105 m_wots_priv_key(XMSS_PublicKey::m_xmss_params.ots_oid(),
106 public_seed(),
107 rng),
108 m_hash(xmss_hash_function()),
109 m_prf(rng.random_vec(XMSS_PublicKey::m_xmss_params.element_size())),
110 m_index_reg(XMSS_Index_Registry::get_instance())
111 {
112 XMSS_Address adrs;
113 set_root(tree_hash(0,
114 XMSS_PublicKey::m_xmss_params.tree_height(),
115 adrs));
116 }
117
118
119 XMSS_PrivateKey::XMSS_PrivateKey(XMSS_Parameters::xmss_algorithm_t xmss_algo_id,
120 size_t idx_leaf,
121 const secure_vector<uint8_t>& wots_priv_seed,
122 const secure_vector<uint8_t>& prf,
123 const secure_vector<uint8_t>& root,
124 const secure_vector<uint8_t>& public_seed)
125 : XMSS_PublicKey(xmss_algo_id, root, public_seed),
126 m_wots_priv_key(XMSS_PublicKey::m_xmss_params.ots_oid(),
127 public_seed,
128 wots_priv_seed),
129 m_hash(XMSS_PublicKey::m_xmss_params.hash_function_name()),
130 m_prf(prf),
131 m_index_reg(XMSS_Index_Registry::get_instance())
132 {
133 set_unused_leaf_index(idx_leaf);
134 }
135
136 secure_vector<uint8_t>
137 XMSS_PrivateKey::tree_hash(size_t start_idx,
138 size_t target_node_height,
139 XMSS_Address& adrs)
140 {
141 BOTAN_ASSERT_NOMSG(target_node_height <= 30);
142 BOTAN_ASSERT((start_idx % (static_cast<size_t>(1) << target_node_height)) == 0,
143 "Start index must be divisible by 2^{target node height}.");
144
145#if defined(BOTAN_HAS_THREAD_UTILS)
146 // dertermine number of parallel tasks to split the tree_hashing into.
147
148 Thread_Pool& thread_pool = Thread_Pool::global_instance();
149
150 const size_t split_level = std::min(target_node_height, thread_pool.worker_count());
151
152 // skip parallelization overhead for leaf nodes.
153 if(split_level == 0)
154 {
155 secure_vector<uint8_t> result;
156 tree_hash_subtree(result, start_idx, target_node_height, adrs);
157 return result;
158 }
159
160 const size_t subtrees = static_cast<size_t>(1) << split_level;
161 const size_t last_idx = (static_cast<size_t>(1) << (target_node_height)) + start_idx;
162 const size_t offs = (last_idx - start_idx) / subtrees;
163 // this cast cannot overflow because target_node_height is limited
164 uint8_t level = static_cast<uint8_t>(split_level); // current level in the tree
165
166 BOTAN_ASSERT((last_idx - start_idx) % subtrees == 0,
167 "Number of worker threads in tree_hash need to divide range "
168 "of calculated nodes.");
169
170 std::vector<secure_vector<uint8_t>> nodes(
171 subtrees,
172 secure_vector<uint8_t>(XMSS_PublicKey::m_xmss_params.element_size()));
173 std::vector<XMSS_Address> node_addresses(subtrees, adrs);
174 std::vector<XMSS_Hash> xmss_hash(subtrees, m_hash);
175 std::vector<std::future<void>> work;
176
177 // Calculate multiple subtrees in parallel.
178 for(size_t i = 0; i < subtrees; i++)
179 {
180 using tree_hash_subtree_fn_t =
181 void (XMSS_PrivateKey::*)(secure_vector<uint8_t>&,
182 size_t,
183 size_t,
184 XMSS_Address&,
185 XMSS_Hash&);
186
187 tree_hash_subtree_fn_t work_fn = &XMSS_PrivateKey::tree_hash_subtree;
188
189 work.push_back(thread_pool.run(
190 work_fn,
191 this,
192 std::ref(nodes[i]),
193 start_idx + i * offs,
194 target_node_height - split_level,
195 std::ref(node_addresses[i]),
196 std::ref(xmss_hash[i])));
197 }
198
199 for(auto& w : work)
200 {
201 w.get();
202 }
203 work.clear();
204
205 // Parallelize the top tree levels horizontally
206 while(level-- > 1)
207 {
208 std::vector<secure_vector<uint8_t>> ro_nodes(
209 nodes.begin(), nodes.begin() + (static_cast<size_t>(1) << (level+1)));
210
211 for(size_t i = 0; i < (static_cast<size_t>(1) << level); i++)
212 {
213 BOTAN_ASSERT_NOMSG(xmss_hash.size() > i);
214
215 node_addresses[i].set_tree_height(static_cast<uint32_t>(target_node_height - (level + 1)));
216 node_addresses[i].set_tree_index(
217 (node_addresses[2 * i + 1].get_tree_index() - 1) >> 1);
218
219 work.push_back(thread_pool.run(
220 &XMSS_Common_Ops::randomize_tree_hash,
221 std::ref(nodes[i]),
222 std::cref(ro_nodes[2 * i]),
223 std::cref(ro_nodes[2 * i + 1]),
224 std::ref(node_addresses[i]),
225 std::cref(this->public_seed()),
226 std::ref(xmss_hash[i]),
227 std::cref(m_xmss_params)));
228 }
229
230 for(auto &w : work)
231 {
232 w.get();
233 }
234 work.clear();
235 }
236
237 // Avoid creation an extra thread to calculate root node.
238 node_addresses[0].set_tree_height(static_cast<uint32_t>(target_node_height - 1));
239 node_addresses[0].set_tree_index(
240 (node_addresses[1].get_tree_index() - 1) >> 1);
241 XMSS_Common_Ops::randomize_tree_hash(nodes[0],
242 nodes[0],
243 nodes[1],
244 node_addresses[0],
245 this->public_seed(),
246 m_hash,
247 m_xmss_params);
248 return nodes[0];
249#else
250 secure_vector<uint8_t> result;
251 tree_hash_subtree(result, start_idx, target_node_height, adrs, m_hash);
252 return result;
253#endif
254 }
255
256 void
257XMSS_PrivateKey::tree_hash_subtree(secure_vector<uint8_t>& result,
258 size_t start_idx,
259 size_t target_node_height,
260 XMSS_Address& adrs,
261 XMSS_Hash& hash)
262 {
263 const secure_vector<uint8_t>& seed = this->public_seed();
264
265 std::vector<secure_vector<uint8_t>> nodes(
266 target_node_height + 1,
267 secure_vector<uint8_t>(XMSS_PublicKey::m_xmss_params.element_size()));
268
269 // node stack, holds all nodes on stack and one extra "pending" node. This
270 // temporary node referred to as "node" in the XMSS standard document stays
271 // a pending element, meaning it is not regarded as element on the stack
272 // until level is increased.
273 std::vector<uint8_t> node_levels(target_node_height + 1);
274
275 uint8_t level = 0; // current level on the node stack.
276 XMSS_WOTS_PublicKey pk(m_wots_priv_key.wots_parameters().oid(), seed);
277 const size_t last_idx = (static_cast<size_t>(1) << target_node_height) + start_idx;
278
279 for(size_t i = start_idx; i < last_idx; i++)
280 {
281 adrs.set_type(XMSS_Address::Type::OTS_Hash_Address);
282 adrs.set_ots_address(static_cast<uint32_t>(i));
283 this->wots_private_key().generate_public_key(
284 pk,
285 // getWOTS_SK(SK, s + i), reference implementation uses adrs
286 // instead of zero padded index s + i.
287 this->wots_private_key().at(adrs, hash),
288 adrs,
289 hash);
290 adrs.set_type(XMSS_Address::Type::LTree_Address);
291 adrs.set_ltree_address(static_cast<uint32_t>(i));
292 XMSS_Common_Ops::create_l_tree(nodes[level], pk, adrs, seed, hash, m_xmss_params);
293 node_levels[level] = 0;
294
295 adrs.set_type(XMSS_Address::Type::Hash_Tree_Address);
296 adrs.set_tree_height(0);
297 adrs.set_tree_index(static_cast<uint32_t>(i));
298
299 while(level > 0 && node_levels[level] ==
300 node_levels[level - 1])
301 {
302 adrs.set_tree_index(((adrs.get_tree_index() - 1) >> 1));
303 XMSS_Common_Ops::randomize_tree_hash(nodes[level - 1],
304 nodes[level - 1],
305 nodes[level],
306 adrs,
307 seed,
308 hash,
309 m_xmss_params);
310 node_levels[level - 1]++;
311 level--; //Pop stack top element
312 adrs.set_tree_height(adrs.get_tree_height() + 1);
313 }
314 level++; //push temporary node to stack
315 }
316 result = nodes[level - 1];
317 }
318
319 secure_vector<uint8_t> XMSS_PrivateKey::private_key_bits() const
320 {
321 return DER_Encoder().encode(raw_private_key(), OCTET_STRING).get_contents();
322 }
323
324std::shared_ptr<Atomic<size_t>>
325XMSS_PrivateKey::recover_global_leaf_index() const
326 {
327 BOTAN_ASSERT(m_wots_priv_key.private_seed().size() ==
328 XMSS_PublicKey::m_xmss_params.element_size() &&
329 m_prf.size() == XMSS_PublicKey::m_xmss_params.element_size(),
330 "Trying to retrieve index for partially initialized key");
331 return m_index_reg.get(m_wots_priv_key.private_seed(), m_prf);
332 }
333
334 void XMSS_PrivateKey::set_unused_leaf_index(size_t idx)
335 {
336 if(idx >= (1ull << XMSS_PublicKey::m_xmss_params.tree_height()))
337 {
338 throw Decoding_Error("XMSS private key leaf index out of bounds");
339 }
340 else
341 {
342 std::atomic<size_t>& index =
343 static_cast<std::atomic<size_t>&>(*recover_global_leaf_index());
344 size_t current = 0;
345
346 do
347 {
348 current = index.load();
349 if(current > idx)
350 { return; }
351 }
352 while(!index.compare_exchange_strong(current, idx));
353 }
354 }
355
356 size_t XMSS_PrivateKey::reserve_unused_leaf_index()
357 {
358 size_t idx = (static_cast<std::atomic<size_t>&>(
359 *recover_global_leaf_index())).fetch_add(1);
360 if(idx >= (1ull << XMSS_PublicKey::m_xmss_params.tree_height()))
361 {
362 throw Decoding_Error("XMSS private key, one time signatures exhaused");
363 }
364 return idx;
365 }
366
367 size_t XMSS_PrivateKey::unused_leaf_index() const
368 {
369 return *recover_global_leaf_index();
370 }
371
372 secure_vector<uint8_t> XMSS_PrivateKey::raw_private_key() const
373 {
374 std::vector<uint8_t> pk { raw_public_key() };
375 secure_vector<uint8_t> result(pk.begin(), pk.end());
376 result.reserve(size());
377
378 for(int i = 3; i >= 0; i--)
379 {
380 result.push_back(
381 static_cast<uint8_t>(
382 static_cast<uint64_t>(unused_leaf_index()) >> 8 * i));
383 }
384
385 std::copy(m_prf.begin(), m_prf.end(), std::back_inserter(result));
386 std::copy(m_wots_priv_key.private_seed().begin(),
387 m_wots_priv_key.private_seed().end(),
388 std::back_inserter(result));
389
390 return result;
391 }
392
393std::unique_ptr<PK_Ops::Signature>
394 XMSS_PrivateKey::create_signature_op(RandomNumberGenerator&,
395 const std::string&,
396 const std::string& provider) const
397 {
398 if(provider == "base" || provider.empty())
399 return std::unique_ptr<PK_Ops::Signature>(
400 new XMSS_Signature_Operation(*this));
401
402 throw Provider_Not_Found(algo_name(), provider);
403 }
404
405}
BOTAN_ASSERT_NOMSG
#define BOTAN_ASSERT_NOMSG(expr)
Definition: assert.h:68
BOTAN_ASSERT
#define BOTAN_ASSERT(expr, assertion_made)
Definition: assert.h:55
Botan::DER_Encoder
Definition: der_enc.h:23
Botan::DER_Encoder::get_contents
secure_vector< uint8_t > get_contents()
Definition: der_enc.cpp:152
Botan::DER_Encoder::encode
DER_Encoder & encode(bool b)
Definition: der_enc.cpp:285
Botan::Decoding_Error
Definition: exceptn.h:200
Botan::Provider_Not_Found
Definition: exceptn.h:279
Botan::RandomNumberGenerator
Definition: rng.h:26
Botan::Thread_Pool
Definition: thread_pool.h:25
Botan::Thread_Pool::worker_count
size_t worker_count() const
Definition: thread_pool.h:43
Botan::Thread_Pool::run
auto run(F &&f, Args &&... args) -> std::future< typename std::result_of< F(Args...)>::type >
Definition: thread_pool.h:57
Botan::Thread_Pool::global_instance
static Thread_Pool & global_instance()
Definition: thread_pool.cpp:15
Botan::XMSS_Address
Definition: xmss_address.h:22
Botan::XMSS_Address::Type::OTS_Hash_Address
@ OTS_Hash_Address
Botan::XMSS_Address::Type::LTree_Address
@ LTree_Address
Botan::XMSS_Address::Type::Hash_Tree_Address
@ Hash_Tree_Address
Botan::XMSS_Address::set_ots_address
void set_ots_address(uint32_t value)
Definition: xmss_address.h:164
Botan::XMSS_Address::get_tree_index
uint32_t get_tree_index() const
Definition: xmss_address.h:297
Botan::XMSS_Address::set_type
void set_type(Type type)
Definition: xmss_address.h:111
Botan::XMSS_Address::get_tree_height
uint32_t get_tree_height() const
Definition: xmss_address.h:235
Botan::XMSS_Address::set_tree_height
void set_tree_height(uint32_t value)
Definition: xmss_address.h:251
Botan::XMSS_Address::set_tree_index
void set_tree_index(uint32_t value)
Definition: xmss_address.h:313
Botan::XMSS_Address::set_ltree_address
void set_ltree_address(uint32_t value)
Definition: xmss_address.h:194
Botan::XMSS_Common_Ops::create_l_tree
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)
Definition: xmss_common_ops.cpp:47
Botan::XMSS_Common_Ops::randomize_tree_hash
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)
Definition: xmss_common_ops.cpp:14
Botan::XMSS_Hash
Definition: xmss_hash.h:22
Botan::XMSS_Index_Registry
Definition: xmss_index_registry.h:26
Botan::XMSS_Index_Registry::get
std::shared_ptr< Atomic< size_t > > get(const secure_vector< uint8_t > &private_seed, const secure_vector< uint8_t > &prf)
Definition: xmss_index_registry.cpp:38
Botan::XMSS_Parameters::element_size
size_t element_size() const
Definition: xmss_parameters.h:67
Botan::XMSS_Parameters::xmss_algorithm_t
xmss_algorithm_t
Definition: xmss_parameters.h:27
Botan::XMSS_PrivateKey
Definition: xmss.h:271
Botan::XMSS_PrivateKey::public_seed
const secure_vector< uint8_t > & public_seed() const override
Definition: xmss.h:382
Botan::XMSS_PrivateKey::set_unused_leaf_index
void set_unused_leaf_index(size_t idx)
Definition: xmss_privatekey.cpp:334
Botan::XMSS_PrivateKey::tree_hash
secure_vector< uint8_t > tree_hash(size_t start_idx, size_t target_node_height, XMSS_Address &adrs)
Definition: xmss_privatekey.cpp:137
Botan::XMSS_PrivateKey::unused_leaf_index
size_t unused_leaf_index() const
Definition: xmss_privatekey.cpp:367
Botan::XMSS_PrivateKey::size
size_t size() const override
Definition: xmss.h:394
Botan::XMSS_PrivateKey::wots_private_key
const XMSS_WOTS_PrivateKey & wots_private_key() const
Definition: xmss.h:343
Botan::XMSS_PrivateKey::reserve_unused_leaf_index
size_t reserve_unused_leaf_index()
Definition: xmss_privatekey.cpp:356
Botan::XMSS_PrivateKey::create_signature_op
std::unique_ptr< PK_Ops::Signature > create_signature_op(RandomNumberGenerator &, const std::string &, const std::string &provider) const override
Definition: xmss_privatekey.cpp:394
Botan::XMSS_PrivateKey::XMSS_PrivateKey
XMSS_PrivateKey(XMSS_Parameters::xmss_algorithm_t xmss_algo_id, RandomNumberGenerator &rng)
Definition: xmss_privatekey.cpp:101
Botan::XMSS_PrivateKey::raw_private_key
secure_vector< uint8_t > raw_private_key() const
Definition: xmss_privatekey.cpp:372
Botan::XMSS_PrivateKey::private_key_bits
secure_vector< uint8_t > private_key_bits() const override
Definition: xmss_privatekey.cpp:319
Botan::XMSS_PublicKey
Definition: xmss.h:31
Botan::XMSS_PublicKey::set_root
void set_root(const secure_vector< uint8_t > &root)
Definition: xmss.h:151
Botan::XMSS_PublicKey::m_xmss_params
XMSS_Parameters m_xmss_params
Definition: xmss.h:245
Botan::XMSS_PublicKey::raw_public_key
virtual std::vector< uint8_t > raw_public_key() const
Definition: xmss_publickey.cpp:104
Botan::XMSS_PublicKey::m_wots_params
XMSS_WOTS_Parameters m_wots_params
Definition: xmss.h:246
Botan::XMSS_PublicKey::algo_name
std::string algo_name() const override
Definition: xmss.h:186
Botan::XMSS_PublicKey::size
virtual size_t size() const
Definition: xmss.h:229
Botan::XMSS_Signature_Operation
Definition: xmss_signature_operation.h:29
Botan::XMSS_WOTS_Parameters::element_size
size_t element_size() const
Definition: xmss_wots.h:85
Botan::XMSS_WOTS_Parameters::oid
ots_algorithm_t oid() const
Definition: xmss_wots.h:103
Botan::XMSS_WOTS_PrivateKey::private_seed
const secure_vector< uint8_t > & private_seed() const
Definition: xmss_wots.h:686
Botan::XMSS_WOTS_PrivateKey::generate_public_key
XMSS_WOTS_PublicKey generate_public_key(XMSS_Address &adrs)
Definition: xmss_wots_privatekey.cpp:34
Botan::XMSS_WOTS_PrivateKey::set_private_seed
void set_private_seed(const secure_vector< uint8_t > &private_seed)
Definition: xmss_wots.h:697
Botan::XMSS_WOTS_PublicKey
Definition: xmss_wots.h:135
Botan::XMSS_WOTS_PublicKey::wots_parameters
const XMSS_WOTS_Parameters & wots_parameters() const
Definition: xmss_wots.h:331
Botan
Definition: alg_id.cpp:13
Botan::unlock
std::vector< T > unlock(const secure_vector< T > &in)
Definition: secmem.h:72
Botan::OCTET_STRING
@ OCTET_STRING
Definition: asn1_obj.h:38
Botan::secure_vector
std::vector< T, secure_allocator< T > > secure_vector
Definition: secmem.h:65
hash
MechanismType hash
Definition: p11_mechanism.cpp:64