Coverage Report

Created: 2020-02-14 15:38

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