Botan  2.6.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  * draft-itrf-cfrg-xmss-hash-based-signatures-06
9  * Release: July 2016.
10  * https://datatracker.ietf.org/doc/
11  * draft-irtf-cfrg-xmss-hash-based-signatures/?include_text=1
12  *
13  * (C) 2016,2017 Matthias Gierlings
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 <cmath>
21 #if defined(BOTAN_TARGET_OS_HAS_THREADS)
22  #include <thread>
23 #endif
24 
25 namespace Botan {
26 
28  : XMSS_PublicKey(unlock(raw_key)),
29  XMSS_Common_Ops(XMSS_PublicKey::m_xmss_params.oid()),
30  m_wots_priv_key(m_wots_params.oid(), m_public_seed),
31  m_index_reg(XMSS_Index_Registry::get_instance())
32  {
33  BOTAN_ASSERT(sizeof(size_t) >= std::ceil(
34  static_cast<float>(XMSS_PublicKey::m_xmss_params.tree_height()) / 8.f),
35  "System type \"size_t\" not big enough to support"
36  " leaf index.");
37 
38  if(raw_key.size() != size())
39  {
40  throw Integrity_Failure("Invalid XMSS private key size detected.");
41  }
42 
43  // extract & copy unused leaf index from raw_key.
44  uint64_t unused_leaf = 0;
45  auto begin = (raw_key.begin() + XMSS_PublicKey::size());
46  auto end = raw_key.begin() + XMSS_PublicKey::size() + sizeof(uint64_t);
47 
48  for(auto& i = begin; i != end; i++)
49  {
50  unused_leaf = ((unused_leaf << 8) | *i);
51  }
52 
53  if(unused_leaf >= (1ull << (XMSS_PublicKey::m_xmss_params.tree_height() -
54  1)))
55  {
56  throw Integrity_Failure("XMSS private key leaf index out of "
57  "bounds.");
58  }
59 
60  begin = end;
62  m_prf.clear();
63  m_prf.reserve(XMSS_PublicKey::m_xmss_params.element_size());
64  std::copy(begin, end, std::back_inserter(m_prf));
65 
66  begin = end;
67  end = begin + m_wots_params.element_size();
68  m_wots_priv_key.set_private_seed(secure_vector<uint8_t>(begin, end));
69  set_unused_leaf_index(static_cast<size_t>(unused_leaf));
70  }
71 
75  : XMSS_PublicKey(xmss_algo_id, rng),
76  XMSS_Common_Ops(xmss_algo_id),
77  m_wots_priv_key(XMSS_PublicKey::m_xmss_params.ots_oid(),
78  public_seed(),
79  rng),
80  m_prf(rng.random_vec(XMSS_PublicKey::m_xmss_params.element_size())),
81  m_index_reg(XMSS_Index_Registry::get_instance())
82  {
83  XMSS_Address adrs;
85  XMSS_PublicKey::m_xmss_params.tree_height(),
86  adrs));
87  }
88 
90 XMSS_PrivateKey::tree_hash(size_t start_idx,
91  size_t target_node_height,
92  XMSS_Address& adrs)
93  {
94  BOTAN_ASSERT((start_idx % (1 << target_node_height)) == 0,
95  "Start index must be divisible by 2^{target node height}.");
96 
97 #if defined(BOTAN_TARGET_OS_HAS_THREADS)
98  // dertermine number of parallel tasks to split the tree_hashing into.
99  size_t split_level = std::min(
100  {
101  target_node_height,
102  static_cast<size_t>(
103  std::ceil(std::log2(XMSS_Tools::max_threads())))
104  });
105 
106  // skip parallelization overhead for leaf nodes.
107  if(split_level == 0)
108  {
109 #endif
110  secure_vector<uint8_t> result;
111  tree_hash_subtree(result, start_idx, target_node_height, adrs);
112  return result;
113 #if defined(BOTAN_TARGET_OS_HAS_THREADS)
114  }
115 
116  size_t subtrees = 1 << split_level;
117  size_t last_idx = static_cast<size_t>(1 << (target_node_height)) + start_idx;
118  size_t offs = (last_idx - start_idx) / subtrees;
119  uint8_t level = split_level; // current level in the tree
120 
121  BOTAN_ASSERT((last_idx - start_idx) % subtrees == 0,
122  "Number of worker threads in tree_hash need to divide range "
123  "of calculated nodes.");
124 
125  std::vector<secure_vector<uint8_t>> nodes(
126  subtrees,
128  std::vector<XMSS_Address> node_addresses(subtrees, adrs);
129  std::vector<XMSS_Hash> xmss_hash(subtrees, m_hash);
130  std::vector<std::thread> threads;
131  threads.reserve(subtrees);
132 
133  // Calculate multiple subtrees in parallel.
134  for(size_t i = 0; i < subtrees; i++)
135  {
136  using tree_hash_subtree_fn_t =
138  size_t,
139  size_t,
140  XMSS_Address&,
141  XMSS_Hash&);
142 
143  threads.emplace_back(
144  std::thread(
145  static_cast<tree_hash_subtree_fn_t>(
146  &XMSS_PrivateKey::tree_hash_subtree),
147  this,
148  std::ref(nodes[i]),
149  start_idx + i * offs,
150  target_node_height - split_level,
151  std::ref(node_addresses[i]),
152  std::ref(xmss_hash[i])));
153  }
154 
155  for(auto& t : threads)
156  {
157  t.join();
158  }
159 
160  threads.clear();
161 
162  // Parallelize the top tree levels horizontally
163  while(level-- > 1)
164  {
165  std::vector<secure_vector<uint8_t>> ro_nodes(
166  nodes.begin(), nodes.begin() + (1 << (level+1)));
167 
168  for(size_t i = 0; i < (1U << level); i++)
169  {
170  node_addresses[i].set_tree_height(target_node_height - (level + 1));
171  node_addresses[i].set_tree_index(
172  (node_addresses[2 * i + 1].get_tree_index() - 1) >> 1);
173  using rnd_tree_hash_fn_t =
175  const secure_vector<uint8_t>&,
176  const secure_vector<uint8_t>&,
177  XMSS_Address& adrs,
178  const secure_vector<uint8_t>&,
179  XMSS_Hash&);
180 
181  threads.emplace_back(
182  std::thread(
183  static_cast<rnd_tree_hash_fn_t>(
185  this,
186  std::ref(nodes[i]),
187  std::ref(ro_nodes[2 * i]),
188  std::ref(ro_nodes[2 * i + 1]),
189  std::ref(node_addresses[i]),
190  std::ref(this->public_seed()),
191  std::ref(xmss_hash[i])));
192  }
193  for(auto &t : threads)
194  {
195  t.join();
196  }
197  threads.clear();
198  }
199 
200  // Avoid creation an extra thread to calculate root node.
201  node_addresses[0].set_tree_height(target_node_height - 1);
202  node_addresses[0].set_tree_index(
203  (node_addresses[1].get_tree_index() - 1) >> 1);
204  randomize_tree_hash(nodes[0],
205  nodes[0],
206  nodes[1],
207  node_addresses[0],
208  this->public_seed());
209  return nodes[0];
210 #endif
211  }
212 
213 void
214 XMSS_PrivateKey::tree_hash_subtree(secure_vector<uint8_t>& result,
215  size_t start_idx,
216  size_t target_node_height,
217  XMSS_Address& adrs,
218  XMSS_Hash& hash)
219  {
220  const secure_vector<uint8_t>& seed = this->public_seed();
221 
222  std::vector<secure_vector<uint8_t>> nodes(
223  target_node_height + 1,
225 
226  // node stack, holds all nodes on stack and one extra "pending" node. This
227  // temporary node referred to as "node" in the XMSS standard document stays
228  // a pending element, meaning it is not regarded as element on the stack
229  // until level is increased.
230  std::vector<uint8_t> node_levels(target_node_height + 1);
231 
232  uint8_t level = 0; // current level on the node stack.
233  XMSS_WOTS_PublicKey pk(m_wots_priv_key.wots_parameters().oid(), seed);
234  size_t last_idx = static_cast<size_t>(1 << target_node_height) + start_idx;
235 
236  for(size_t i = start_idx; i < last_idx; i++)
237  {
239  adrs.set_ots_address(i);
241  pk,
242  // getWOTS_SK(SK, s + i), reference implementation uses adrs
243  // instead of zero padded index s + i.
244  this->wots_private_key().at(adrs, hash),
245  adrs,
246  hash);
248  adrs.set_ltree_address(i);
249  create_l_tree(nodes[level], pk, adrs, seed, hash);
250  node_levels[level] = 0;
251 
253  adrs.set_tree_height(0);
254  adrs.set_tree_index(i);
255 
256  while(level > 0 && node_levels[level] ==
257  node_levels[level - 1])
258  {
259  adrs.set_tree_index(((adrs.get_tree_index() - 1) >> 1));
260  randomize_tree_hash(nodes[level - 1],
261  nodes[level - 1],
262  nodes[level],
263  adrs,
264  seed,
265  hash);
266  node_levels[level - 1]++;
267  level--; //Pop stack top element
268  adrs.set_tree_height(adrs.get_tree_height() + 1);
269  }
270  level++; //push temporary node to stack
271  }
272  result = nodes[level - 1];
273  }
274 
275 std::shared_ptr<Atomic<size_t>>
276 XMSS_PrivateKey::recover_global_leaf_index() const
277  {
278  BOTAN_ASSERT(m_wots_priv_key.private_seed().size() ==
281  "Trying to retrieve index for partially initialized "
282  "key.");
283  return m_index_reg.get(m_wots_priv_key.private_seed(),
284  m_prf);
285  }
286 
288  {
289  std::vector<uint8_t> pk { raw_public_key() };
290  secure_vector<uint8_t> result(pk.begin(), pk.end());
291  result.reserve(size());
292 
293  for(int i = 7; i >= 0; i--)
294  {
295  result.push_back(
296  static_cast<uint8_t>(
297  static_cast<uint64_t>(unused_leaf_index()) >> 8 * i));
298  }
299 
300  std::copy(m_prf.begin(), m_prf.end(), std::back_inserter(result));
301  std::copy(m_wots_priv_key.private_seed().begin(),
302  m_wots_priv_key.private_seed().end(),
303  std::back_inserter(result));
304 
305  return result;
306  }
307 
308 std::unique_ptr<PK_Ops::Signature>
310  const std::string&,
311  const std::string& provider) const
312  {
313  if(provider == "base" || provider.empty())
314  return std::unique_ptr<PK_Ops::Signature>(
315  new XMSS_Signature_Operation(*this));
316 
317  throw Provider_Not_Found(algo_name(), provider);
318  }
319 
320 }
const secure_vector< uint8_t > & public_seed() const override
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
static size_t max_threads()
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)
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:30
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:95
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
std::vector< T, secure_allocator< T > > secure_vector
Definition: secmem.h:88
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