Botan  2.18.1
Crypto and TLS for C++11
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
35 secure_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 
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;
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 
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;
114  XMSS_PublicKey::m_xmss_params.tree_height(),
115  adrs));
116  }
117 
118 
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 
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,
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 =
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(
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);
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
257 XMSS_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,
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  {
282  adrs.set_ots_address(static_cast<uint32_t>(i));
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);
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 
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 
320  {
322  }
323 
324 std::shared_ptr<Atomic<size_t>>
325 XMSS_PrivateKey::recover_global_leaf_index() const
326  {
327  BOTAN_ASSERT(m_wots_priv_key.private_seed().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 
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 
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 
368  {
369  return *recover_global_leaf_index();
370  }
371 
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 
393 std::unique_ptr<PK_Ops::Signature>
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 }
const secure_vector< uint8_t > & public_seed() const override
Definition: xmss.h:382
size_t worker_count() const
Definition: thread_pool.h:43
const XMSS_WOTS_PrivateKey & wots_private_key() const
Definition: xmss.h:343
secure_vector< uint8_t > tree_hash(size_t start_idx, size_t target_node_height, XMSS_Address &adrs)
uint32_t get_tree_index() const
Definition: xmss_address.h:297
void set_ots_address(uint32_t value)
Definition: xmss_address.h:164
void set_tree_height(uint32_t value)
Definition: xmss_address.h:251
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)
void set_ltree_address(uint32_t value)
Definition: xmss_address.h:194
secure_vector< uint8_t > get_contents()
Definition: der_enc.cpp:152
void set_root(const secure_vector< uint8_t > &root)
Definition: xmss.h:151
void set_unused_leaf_index(size_t idx)
#define BOTAN_ASSERT_NOMSG(expr)
Definition: assert.h:68
virtual std::vector< uint8_t > raw_public_key() const
virtual size_t size() const
Definition: xmss.h:229
#define BOTAN_ASSERT(expr, assertion_made)
Definition: assert.h:55
auto run(F &&f, Args &&... args) -> std::future< typename std::result_of< F(Args...)>::type >
Definition: thread_pool.h:57
DER_Encoder & encode(bool b)
Definition: der_enc.cpp:285
size_t unused_leaf_index() const
XMSS_PrivateKey(XMSS_Parameters::xmss_algorithm_t xmss_algo_id, RandomNumberGenerator &rng)
size_t size() const override
Definition: xmss.h:394
uint32_t get_tree_height() const
Definition: xmss_address.h:235
void set_type(Type type)
Definition: xmss_address.h:111
std::shared_ptr< Atomic< size_t > > get(const secure_vector< uint8_t > &private_seed, const secure_vector< uint8_t > &prf)
XMSS_WOTS_PublicKey generate_public_key(XMSS_Address &adrs)
Definition: alg_id.cpp:13
secure_vector< uint8_t > private_key_bits() const override
const XMSS_WOTS_Parameters & wots_parameters() const
Definition: xmss_wots.h:331
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::vector< T > unlock(const secure_vector< T > &in)
Definition: secmem.h:72
std::unique_ptr< PK_Ops::Signature > create_signature_op(RandomNumberGenerator &, const std::string &, const std::string &provider) const override
const secure_vector< uint8_t > & private_seed() const
Definition: xmss_wots.h:686
std::string algo_name() const override
Definition: xmss.h:186
secure_vector< uint8_t > raw_private_key() const
size_t element_size() const
XMSS_WOTS_Parameters m_wots_params
Definition: xmss.h:246
static Thread_Pool & global_instance()
Definition: thread_pool.cpp:15
std::vector< T, secure_allocator< T > > secure_vector
Definition: secmem.h:65
void set_tree_index(uint32_t value)
Definition: xmss_address.h:313
void set_private_seed(const secure_vector< uint8_t > &private_seed)
Definition: xmss_wots.h:697
XMSS_Parameters m_xmss_params
Definition: xmss.h:245
size_t element_size() const
Definition: xmss_wots.h:85
MechanismType hash
ots_algorithm_t oid() const
Definition: xmss_wots.h:103