/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 | | } |