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