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