Coverage Report

Created: 2021-02-21 07:20

/src/botan/src/lib/pubkey/xmss/xmss_privatekey.cpp
Line
Count
Source (jump to first uncovered line)
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
0
   {
37
0
   secure_vector<uint8_t> raw_key;
38
0
   try
39
0
      {
40
0
      BER_Decoder(key_bits).decode(raw_key, ASN1_Type::OctetString);
41
0
      }
42
0
   catch(Decoding_Error&)
43
0
      {
44
0
      raw_key = key_bits;
45
0
      }
46
0
   return raw_key;
47
0
   }
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
0
   {
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
0
   static_assert(sizeof(size_t) >= 4, "size_t is big enough to support leaf index");
66
67
0
   secure_vector<uint8_t> raw_key = extract_raw_key(key_bits);
68
69
0
   if(raw_key.size() != XMSS_PrivateKey::size())
70
0
      {
71
0
      throw Decoding_Error("Invalid XMSS private key size");
72
0
      }
73
74
   // extract & copy unused leaf index from raw_key
75
0
   uint64_t unused_leaf = 0;
76
0
   auto begin = (raw_key.begin() + XMSS_PublicKey::size());
77
0
   auto end = raw_key.begin() + XMSS_PublicKey::size() + sizeof(uint32_t);
78
79
0
   for(auto& i = begin; i != end; i++)
80
0
      {
81
0
      unused_leaf = ((unused_leaf << 8) | *i);
82
0
      }
83
84
0
   if(unused_leaf >= (1ull << XMSS_PublicKey::m_xmss_params.tree_height()))
85
0
      {
86
0
      throw Decoding_Error("XMSS private key leaf index out of bounds");
87
0
      }
88
89
0
   begin = end;
90
0
   end = begin + XMSS_PublicKey::m_xmss_params.element_size();
91
0
   m_prf.clear();
92
0
   m_prf.reserve(XMSS_PublicKey::m_xmss_params.element_size());
93
0
   std::copy(begin, end, std::back_inserter(m_prf));
94
95
0
   begin = end;
96
0
   end = begin + m_wots_params.element_size();
97
0
   m_wots_priv_key.set_private_seed(secure_vector<uint8_t>(begin, end));
98
0
   set_unused_leaf_index(static_cast<size_t>(unused_leaf));
99
0
   }
Unexecuted instantiation: Botan::XMSS_PrivateKey::XMSS_PrivateKey(std::__1::vector<unsigned char, Botan::secure_allocator<unsigned char> > const&)
Unexecuted instantiation: Botan::XMSS_PrivateKey::XMSS_PrivateKey(std::__1::vector<unsigned char, Botan::secure_allocator<unsigned char> > const&)
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
0
   {
112
0
   XMSS_Address adrs;
113
0
   set_root(tree_hash(0,
114
0
                      XMSS_PublicKey::m_xmss_params.tree_height(),
115
0
                      adrs));
116
0
   }
Unexecuted instantiation: Botan::XMSS_PrivateKey::XMSS_PrivateKey(Botan::XMSS_Parameters::xmss_algorithm_t, Botan::RandomNumberGenerator&)
Unexecuted instantiation: Botan::XMSS_PrivateKey::XMSS_PrivateKey(Botan::XMSS_Parameters::xmss_algorithm_t, Botan::RandomNumberGenerator&)
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
0
   {
133
0
   set_unused_leaf_index(idx_leaf);
134
0
   }
Unexecuted instantiation: Botan::XMSS_PrivateKey::XMSS_PrivateKey(Botan::XMSS_Parameters::xmss_algorithm_t, unsigned long, std::__1::vector<unsigned char, Botan::secure_allocator<unsigned char> > const&, std::__1::vector<unsigned char, Botan::secure_allocator<unsigned char> > const&, std::__1::vector<unsigned char, Botan::secure_allocator<unsigned char> > const&, std::__1::vector<unsigned char, Botan::secure_allocator<unsigned char> > const&)
Unexecuted instantiation: Botan::XMSS_PrivateKey::XMSS_PrivateKey(Botan::XMSS_Parameters::xmss_algorithm_t, unsigned long, std::__1::vector<unsigned char, Botan::secure_allocator<unsigned char> > const&, std::__1::vector<unsigned char, Botan::secure_allocator<unsigned char> > const&, std::__1::vector<unsigned char, Botan::secure_allocator<unsigned char> > const&, std::__1::vector<unsigned char, Botan::secure_allocator<unsigned char> > const&)
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
0
   {
141
0
   BOTAN_ASSERT_NOMSG(target_node_height <= 30);
142
0
   BOTAN_ASSERT((start_idx % (static_cast<size_t>(1) << target_node_height)) == 0,
143
0
                "Start index must be divisible by 2^{target node height}.");
144
145
0
#if defined(BOTAN_HAS_THREAD_UTILS)
146
   // dertermine number of parallel tasks to split the tree_hashing into.
147
148
0
   Thread_Pool& thread_pool = Thread_Pool::global_instance();
149
150
0
   const size_t split_level = std::min(target_node_height, thread_pool.worker_count());
151
152
   // skip parallelization overhead for leaf nodes.
153
0
   if(split_level == 0)
154
0
      {
155
0
      secure_vector<uint8_t> result;
156
0
      tree_hash_subtree(result, start_idx, target_node_height, adrs);
157
0
      return result;
158
0
      }
159
160
0
   const size_t subtrees = static_cast<size_t>(1) << split_level;
161
0
   const size_t last_idx = (static_cast<size_t>(1) << (target_node_height)) + start_idx;
162
0
   const size_t offs = (last_idx - start_idx) / subtrees;
163
   // this cast cannot overflow because target_node_height is limited
164
0
   uint8_t level = static_cast<uint8_t>(split_level); // current level in the tree
165
166
0
   BOTAN_ASSERT((last_idx - start_idx) % subtrees == 0,
167
0
                "Number of worker threads in tree_hash need to divide range "
168
0
                "of calculated nodes.");
169
170
0
   std::vector<secure_vector<uint8_t>> nodes(
171
0
       subtrees,
172
0
       secure_vector<uint8_t>(XMSS_PublicKey::m_xmss_params.element_size()));
173
0
   std::vector<XMSS_Address> node_addresses(subtrees, adrs);
174
0
   std::vector<XMSS_Hash> xmss_hash(subtrees, m_hash);
175
0
   std::vector<std::future<void>> work;
176
177
   // Calculate multiple subtrees in parallel.
178
0
   for(size_t i = 0; i < subtrees; i++)
179
0
      {
180
0
      using tree_hash_subtree_fn_t =
181
0
         void (XMSS_PrivateKey::*)(secure_vector<uint8_t>&,
182
0
                                   size_t,
183
0
                                   size_t,
184
0
                                   XMSS_Address&,
185
0
                                   XMSS_Hash&);
186
187
0
      tree_hash_subtree_fn_t work_fn = &XMSS_PrivateKey::tree_hash_subtree;
188
189
0
      work.push_back(thread_pool.run(
190
0
                        work_fn,
191
0
                        this,
192
0
                        std::ref(nodes[i]),
193
0
                        start_idx + i * offs,
194
0
                        target_node_height - split_level,
195
0
                        std::ref(node_addresses[i]),
196
0
                        std::ref(xmss_hash[i])));
197
0
      }
198
199
0
   for(auto& w : work)
200
0
      {
201
0
      w.get();
202
0
      }
203
0
   work.clear();
204
205
   // Parallelize the top tree levels horizontally
206
0
   while(level-- > 1)
207
0
      {
208
0
      std::vector<secure_vector<uint8_t>> ro_nodes(
209
0
         nodes.begin(), nodes.begin() + (static_cast<size_t>(1) << (level+1)));
210
211
0
      for(size_t i = 0; i < (static_cast<size_t>(1) << level); i++)
212
0
         {
213
0
         BOTAN_ASSERT_NOMSG(xmss_hash.size() > i);
214
215
0
         node_addresses[i].set_tree_height(static_cast<uint32_t>(target_node_height - (level + 1)));
216
0
         node_addresses[i].set_tree_index(
217
0
            (node_addresses[2 * i + 1].get_tree_index() - 1) >> 1);
218
219
0
         work.push_back(thread_pool.run(
220
0
               &XMSS_Common_Ops::randomize_tree_hash,
221
0
               std::ref(nodes[i]),
222
0
               std::cref(ro_nodes[2 * i]),
223
0
               std::cref(ro_nodes[2 * i + 1]),
224
0
               std::ref(node_addresses[i]),
225
0
               std::cref(this->public_seed()),
226
0
               std::ref(xmss_hash[i]),
227
0
               std::cref(m_xmss_params)));
228
0
         }
229
230
0
      for(auto &w : work)
231
0
         {
232
0
         w.get();
233
0
         }
234
0
      work.clear();
235
0
      }
236
237
   // Avoid creation an extra thread to calculate root node.
238
0
   node_addresses[0].set_tree_height(static_cast<uint32_t>(target_node_height - 1));
239
0
   node_addresses[0].set_tree_index(
240
0
      (node_addresses[1].get_tree_index() - 1) >> 1);
241
0
   XMSS_Common_Ops::randomize_tree_hash(nodes[0],
242
0
                                        nodes[0],
243
0
                                        nodes[1],
244
0
                                        node_addresses[0],
245
0
                                        this->public_seed(),
246
0
                                        m_hash,
247
0
                                        m_xmss_params);
248
0
   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
0
   }
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
0
   {
263
0
   const secure_vector<uint8_t>& seed = this->public_seed();
264
265
0
   std::vector<secure_vector<uint8_t>> nodes(
266
0
      target_node_height + 1,
267
0
      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
0
   std::vector<uint8_t> node_levels(target_node_height + 1);
274
275
0
   uint8_t level = 0; // current level on the node stack.
276
0
   XMSS_WOTS_PublicKey pk(m_wots_priv_key.wots_parameters().oid(), seed);
277
0
   const size_t last_idx = (static_cast<size_t>(1) << target_node_height) + start_idx;
278
279
0
   for(size_t i = start_idx; i < last_idx; i++)
280
0
      {
281
0
      adrs.set_type(XMSS_Address::Type::OTS_Hash_Address);
282
0
      adrs.set_ots_address(static_cast<uint32_t>(i));
283
0
      this->wots_private_key().generate_public_key(
284
0
         pk,
285
         // getWOTS_SK(SK, s + i), reference implementation uses adrs
286
         // instead of zero padded index s + i.
287
0
         this->wots_private_key().at(adrs, hash),
288
0
         adrs,
289
0
         hash);
290
0
      adrs.set_type(XMSS_Address::Type::LTree_Address);
291
0
      adrs.set_ltree_address(static_cast<uint32_t>(i));
292
0
      XMSS_Common_Ops::create_l_tree(nodes[level], pk, adrs, seed, hash, m_xmss_params);
293
0
      node_levels[level] = 0;
294
295
0
      adrs.set_type(XMSS_Address::Type::Hash_Tree_Address);
296
0
      adrs.set_tree_height(0);
297
0
      adrs.set_tree_index(static_cast<uint32_t>(i));
298
299
0
      while(level > 0 && node_levels[level] ==
300
0
            node_levels[level - 1])
301
0
         {
302
0
         adrs.set_tree_index(((adrs.get_tree_index() - 1) >> 1));
303
0
         XMSS_Common_Ops::randomize_tree_hash(nodes[level - 1],
304
0
                                              nodes[level - 1],
305
0
                                              nodes[level],
306
0
                                              adrs,
307
0
                                              seed,
308
0
                                              hash,
309
0
                                              m_xmss_params);
310
0
         node_levels[level - 1]++;
311
0
         level--; //Pop stack top element
312
0
         adrs.set_tree_height(adrs.get_tree_height() + 1);
313
0
         }
314
0
      level++; //push temporary node to stack
315
0
      }
316
0
   result = nodes[level - 1];
317
0
   }
318
319
secure_vector<uint8_t> XMSS_PrivateKey::private_key_bits() const
320
0
   {
321
0
   return DER_Encoder().encode(raw_private_key(), ASN1_Type::OctetString).get_contents();
322
0
   }
323
324
std::shared_ptr<Atomic<size_t>>
325
XMSS_PrivateKey::recover_global_leaf_index() const
326
0
   {
327
0
   BOTAN_ASSERT(m_wots_priv_key.private_seed().size() ==
328
0
                XMSS_PublicKey::m_xmss_params.element_size() &&
329
0
                m_prf.size() == XMSS_PublicKey::m_xmss_params.element_size(),
330
0
                "Trying to retrieve index for partially initialized key");
331
0
   return m_index_reg.get(m_wots_priv_key.private_seed(), m_prf);
332
0
   }
333
334
void XMSS_PrivateKey::set_unused_leaf_index(size_t idx)
335
0
   {
336
0
   if(idx >= (1ull << XMSS_PublicKey::m_xmss_params.tree_height()))
337
0
      {
338
0
      throw Decoding_Error("XMSS private key leaf index out of bounds");
339
0
      }
340
0
   else
341
0
      {
342
0
      std::atomic<size_t>& index =
343
0
         static_cast<std::atomic<size_t>&>(*recover_global_leaf_index());
344
0
      size_t current = 0;
345
346
0
      do
347
0
         {
348
0
         current = index.load();
349
0
         if(current > idx)
350
0
            { return; }
351
0
         }
352
0
      while(!index.compare_exchange_strong(current, idx));
353
0
      }
354
0
   }
355
356
size_t XMSS_PrivateKey::reserve_unused_leaf_index()
357
0
   {
358
0
   size_t idx = (static_cast<std::atomic<size_t>&>(
359
0
                    *recover_global_leaf_index())).fetch_add(1);
360
0
   if(idx >= (1ull << XMSS_PublicKey::m_xmss_params.tree_height()))
361
0
      {
362
0
      throw Decoding_Error("XMSS private key, one time signatures exhaused");
363
0
      }
364
0
   return idx;
365
0
   }
366
367
size_t XMSS_PrivateKey::unused_leaf_index() const
368
0
   {
369
0
   return *recover_global_leaf_index();
370
0
   }
371
372
secure_vector<uint8_t> XMSS_PrivateKey::raw_private_key() const
373
0
   {
374
0
   std::vector<uint8_t> pk { raw_public_key() };
375
0
   secure_vector<uint8_t> result(pk.begin(), pk.end());
376
0
   result.reserve(size());
377
378
0
   for(int i = 3; i >= 0; i--)
379
0
      {
380
0
      result.push_back(
381
0
         static_cast<uint8_t>(
382
0
            static_cast<uint64_t>(unused_leaf_index()) >> 8 * i));
383
0
      }
384
385
0
   std::copy(m_prf.begin(), m_prf.end(), std::back_inserter(result));
386
0
   std::copy(m_wots_priv_key.private_seed().begin(),
387
0
             m_wots_priv_key.private_seed().end(),
388
0
             std::back_inserter(result));
389
390
0
   return result;
391
0
   }
392
393
std::unique_ptr<Public_Key> XMSS_PrivateKey::public_key() const
394
0
   {
395
0
   return std::unique_ptr<Public_Key>(
396
0
      new XMSS_PublicKey(xmss_oid(), root(), public_seed()));
397
0
   }
398
399
std::unique_ptr<PK_Ops::Signature>
400
XMSS_PrivateKey::create_signature_op(RandomNumberGenerator&,
401
                                     const std::string&,
402
                                     const std::string& provider) const
403
0
   {
404
0
   if(provider == "base" || provider.empty())
405
0
      return std::unique_ptr<PK_Ops::Signature>(
406
0
         new XMSS_Signature_Operation(*this));
407
408
0
   throw Provider_Not_Found(algo_name(), provider);
409
0
   }
410
411
}