5111374265

Committed 29 May 2023 11:19AM UTC coverage: 92.227% (+0.5%) from 91.723%

Build # 5111374265

Build Type

push

github

Committed by

randombit

Commit Message

Next release will be 3.1.0. Update release notes

Run Details

75588 of 81959 relevant lines covered (92.23%)

11886470.91 hits per line

Source File
Press 'n' to go to next uncovered line, 'b' for previous

88.53

/src/lib/pubkey/xmss/xmss_privatekey.cpp

/*
 * XMSS Private Key
 * An XMSS: Extended Hash-Based Siganture private key.
 * The XMSS private key does not support the X509 and PKCS7 standard. Instead
 * the raw format described in [1] is used.
 *
 * [1] XMSS: Extended Hash-Based Signatures,
 *     Request for Comments: 8391
 *     Release: May 2018.
 *     https://datatracker.ietf.org/doc/rfc8391/
 *
 * (C) 2016,2017,2018 Matthias Gierlings
 * (C) 2019 Jack Lloyd
 * (C) 2023 René Meusel - Rohde & Schwarz Cybersecurity
 *
 * Botan is released under the Simplified BSD License (see license.txt)
 **/

#include <botan/xmss.h>

#include <botan/ber_dec.h>
#include <botan/der_enc.h>
#include <botan/internal/loadstor.h>
#include <botan/internal/stl_util.h>
#include <botan/internal/xmss_common_ops.h>
#include <botan/internal/xmss_index_registry.h>
#include <botan/internal/xmss_signature_operation.h>
#include <iterator>

#if defined(BOTAN_HAS_THREAD_UTILS)
   #include <botan/internal/thread_pool.h>
#endif

namespace Botan {

namespace {

// fall back to raw decoding for previous versions, which did not encode an OCTET STRING
secure_vector<uint8_t> extract_raw_private_key(std::span<const uint8_t> key_bits, const XMSS_Parameters& xmss_params) {
   secure_vector<uint8_t> raw_key;

   // The public part of the input key bits was already parsed, so we can
   // decide depending on the buffer length whether this must be BER decoded.
   if(key_bits.size() == xmss_params.raw_private_key_size() ||
      key_bits.size() == xmss_params.raw_legacy_private_key_size()) {
      raw_key.assign(key_bits.begin(), key_bits.end());
   } else {
      DataSource_Memory src(key_bits);
      BER_Decoder(src).decode(raw_key, ASN1_Type::OctetString).verify_end();
   }

   return raw_key;
}

}  // namespace

class XMSS_PrivateKey_Internal {
   public:
      XMSS_PrivateKey_Internal(const XMSS_Parameters& xmss_params,
                               const XMSS_WOTS_Parameters& wots_params,
                               WOTS_Derivation_Method wots_derivation_method,
                               RandomNumberGenerator& rng) :
            m_xmss_params(xmss_params),
            m_wots_params(wots_params),
            m_wots_derivation_method(wots_derivation_method),
            m_hash(xmss_params),
            m_prf(rng.random_vec(xmss_params.element_size())),
            m_private_seed(rng.random_vec(xmss_params.element_size())),
            m_index_reg(XMSS_Index_Registry::get_instance()) {}

      XMSS_PrivateKey_Internal(const XMSS_Parameters& xmss_params,
                               const XMSS_WOTS_Parameters& wots_params,
                               WOTS_Derivation_Method wots_derivation_method,
                               secure_vector<uint8_t> private_seed,
                               secure_vector<uint8_t> prf) :
            m_xmss_params(xmss_params),
            m_wots_params(wots_params),
            m_wots_derivation_method(wots_derivation_method),
            m_hash(m_xmss_params),
            m_prf(std::move(prf)),
            m_private_seed(std::move(private_seed)),
            m_index_reg(XMSS_Index_Registry::get_instance()) {}

      XMSS_PrivateKey_Internal(const XMSS_Parameters& xmss_params,
                               const XMSS_WOTS_Parameters& wots_params,
                               std::span<const uint8_t> key_bits) :
            m_xmss_params(xmss_params),
            m_wots_params(wots_params),
            m_hash(m_xmss_params),
            m_index_reg(XMSS_Index_Registry::get_instance()) {
         /*
         The code requires sizeof(size_t) >= ceil(tree_height / 8)

         Maximum supported tree height is 20, ceil(20/8) == 3, so 4 byte
         size_t is sufficient for all defined parameters, or even a
         (hypothetical) tree height 32, which would be extremely slow to
         compute.
         */
         static_assert(sizeof(size_t) >= 4, "size_t is big enough to support leaf index");

         const secure_vector<uint8_t> raw_key = extract_raw_private_key(key_bits, xmss_params);

         if(raw_key.size() != m_xmss_params.raw_private_key_size() &&
            raw_key.size() != m_xmss_params.raw_legacy_private_key_size()) {
            throw Decoding_Error("Invalid XMSS private key size");
         }

         BufferSlicer s(raw_key);

         // We're not interested in the public key here
         s.skip(m_xmss_params.raw_public_key_size());

         auto unused_leaf_bytes = s.take(sizeof(uint32_t));
         size_t unused_leaf = load_be<uint32_t>(unused_leaf_bytes.data(), 0);
         if(unused_leaf >= (1ULL << m_xmss_params.tree_height())) {
            throw Decoding_Error("XMSS private key leaf index out of bounds");
         }

         m_prf = s.take_secure_vector(m_xmss_params.element_size());
         m_private_seed = s.take_secure_vector(m_xmss_params.element_size());
         set_unused_leaf_index(unused_leaf);

         // Legacy keys generated prior to Botan 3.x don't feature a
         // WOTS+ key derivation method encoded in their private key.
         m_wots_derivation_method =
            (s.empty()) ? WOTS_Derivation_Method::Botan2x : static_cast<WOTS_Derivation_Method>(s.take(1).front());

         BOTAN_ASSERT_NOMSG(s.empty());
      }

      secure_vector<uint8_t> serialize(std::vector<uint8_t> raw_public_key) const {
         std::vector<uint8_t> unused_index(4);
         store_be(static_cast<uint32_t>(unused_leaf_index()), unused_index.data());

         std::vector<uint8_t> wots_derivation_method;
         wots_derivation_method.push_back(static_cast<uint8_t>(m_wots_derivation_method));

         return concat_as<secure_vector<uint8_t>>(
            raw_public_key, unused_index, m_prf, m_private_seed, wots_derivation_method);
      }

      XMSS_Hash& hash() { return m_hash; }

      const secure_vector<uint8_t>& prf_value() const { return m_prf; }

      const secure_vector<uint8_t>& private_seed() { return m_private_seed; }

      const XMSS_WOTS_Parameters& wots_parameters() { return m_wots_params; }

      WOTS_Derivation_Method wots_derivation_method() const { return m_wots_derivation_method; }

      XMSS_Index_Registry& index_registry() { return m_index_reg; }

      std::shared_ptr<Atomic<size_t>> recover_global_leaf_index() const {
         BOTAN_ASSERT(
            m_private_seed.size() == m_xmss_params.element_size() && m_prf.size() == m_xmss_params.element_size(),
            "Trying to retrieve index for partially initialized key");
         return m_index_reg.get(m_private_seed, m_prf);
      }

      void set_unused_leaf_index(size_t idx) {
         if(idx >= (1ULL << m_xmss_params.tree_height())) {
            throw Decoding_Error("XMSS private key leaf index out of bounds");
         } else {
            std::atomic<size_t>& index = static_cast<std::atomic<size_t>&>(*recover_global_leaf_index());
            size_t current = 0;

            do {
               current = index.load();
               if(current > idx) {
                  return;
               }
            } while(!index.compare_exchange_strong(current, idx));
         }
      }

      size_t reserve_unused_leaf_index() {
         size_t idx = (static_cast<std::atomic<size_t>&>(*recover_global_leaf_index())).fetch_add(1);
         if(idx >= m_xmss_params.total_number_of_signatures()) {
            throw Decoding_Error("XMSS private key, one time signatures exhaused");
         }
         return idx;
      }

      size_t unused_leaf_index() const { return *recover_global_leaf_index(); }

      size_t remaining_signatures() const {
         return m_xmss_params.total_number_of_signatures() - *recover_global_leaf_index();
      }

   private:
      const XMSS_Parameters& m_xmss_params;
      const XMSS_WOTS_Parameters& m_wots_params;
      WOTS_Derivation_Method m_wots_derivation_method;

      XMSS_Hash m_hash;
      secure_vector<uint8_t> m_prf;
      secure_vector<uint8_t> m_private_seed;
      XMSS_Index_Registry& m_index_reg;
};

XMSS_PrivateKey::XMSS_PrivateKey(std::span<const uint8_t> key_bits) :
      XMSS_PublicKey(key_bits),
      m_private(std::make_shared<XMSS_PrivateKey_Internal>(m_xmss_params, m_wots_params, key_bits)) {}

XMSS_PrivateKey::XMSS_PrivateKey(XMSS_Parameters::xmss_algorithm_t xmss_algo_id,
                                 RandomNumberGenerator& rng,
                                 WOTS_Derivation_Method wots_derivation_method) :
      XMSS_PublicKey(xmss_algo_id, rng),
      m_private(std::make_shared<XMSS_PrivateKey_Internal>(m_xmss_params, m_wots_params, wots_derivation_method, rng)) {
   XMSS_Address adrs;
   m_root = tree_hash(0, XMSS_PublicKey::m_xmss_params.tree_height(), adrs);
}

XMSS_PrivateKey::XMSS_PrivateKey(XMSS_Parameters::xmss_algorithm_t xmss_algo_id,
                                 size_t idx_leaf,
                                 secure_vector<uint8_t> wots_priv_seed,
                                 secure_vector<uint8_t> prf,
                                 secure_vector<uint8_t> root,
                                 secure_vector<uint8_t> public_seed,
                                 WOTS_Derivation_Method wots_derivation_method) :
      XMSS_PublicKey(xmss_algo_id, std::move(root), std::move(public_seed)),
      m_private(std::make_shared<XMSS_PrivateKey_Internal>(
         m_xmss_params, m_wots_params, wots_derivation_method, std::move(wots_priv_seed), std::move(prf))) {
   m_private->set_unused_leaf_index(idx_leaf);
   BOTAN_ARG_CHECK(m_private->prf_value().size() == m_xmss_params.element_size(),
                   "XMSS: unexpected byte length of PRF value");
   BOTAN_ARG_CHECK(m_private->private_seed().size() == m_xmss_params.element_size(),
                   "XMSS: unexpected byte length of private seed");
}

secure_vector<uint8_t> XMSS_PrivateKey::tree_hash(size_t start_idx, size_t target_node_height, XMSS_Address& adrs) {
   BOTAN_ASSERT_NOMSG(target_node_height <= 30);
   BOTAN_ASSERT((start_idx % (static_cast<size_t>(1) << target_node_height)) == 0,
                "Start index must be divisible by 2^{target node height}.");

#if defined(BOTAN_HAS_THREAD_UTILS)
   // dertermine number of parallel tasks to split the tree_hashing into.

   Thread_Pool& thread_pool = Thread_Pool::global_instance();

   const size_t split_level = std::min(target_node_height, thread_pool.worker_count());

   // skip parallelization overhead for leaf nodes.
   if(split_level == 0) {
      secure_vector<uint8_t> result;
      tree_hash_subtree(result, start_idx, target_node_height, adrs);
      return result;
   }

   const size_t subtrees = static_cast<size_t>(1) << split_level;
   const size_t last_idx = (static_cast<size_t>(1) << (target_node_height)) + start_idx;
   const size_t offs = (last_idx - start_idx) / subtrees;
   // this cast cannot overflow because target_node_height is limited
   uint8_t level = static_cast<uint8_t>(split_level);  // current level in the tree

   BOTAN_ASSERT((last_idx - start_idx) % subtrees == 0,
                "Number of worker threads in tree_hash need to divide range "
                "of calculated nodes.");

   std::vector<secure_vector<uint8_t>> nodes(subtrees,
                                             secure_vector<uint8_t>(XMSS_PublicKey::m_xmss_params.element_size()));
   std::vector<XMSS_Address> node_addresses(subtrees, adrs);
   std::vector<XMSS_Hash> xmss_hash(subtrees, m_private->hash());
   std::vector<std::future<void>> work;

   // Calculate multiple subtrees in parallel.
   for(size_t i = 0; i < subtrees; i++) {
      using tree_hash_subtree_fn_t =
         void (XMSS_PrivateKey::*)(secure_vector<uint8_t>&, size_t, size_t, XMSS_Address&, XMSS_Hash&);

      tree_hash_subtree_fn_t work_fn = &XMSS_PrivateKey::tree_hash_subtree;

      work.push_back(thread_pool.run(work_fn,
                                     this,
                                     std::ref(nodes[i]),
                                     start_idx + i * offs,
                                     target_node_height - split_level,
                                     std::ref(node_addresses[i]),
                                     std::ref(xmss_hash[i])));
   }

   for(auto& w : work) {
      w.get();
   }
   work.clear();

   // Parallelize the top tree levels horizontally
   while(level-- > 1) {
      std::vector<secure_vector<uint8_t>> ro_nodes(nodes.begin(),
                                                   nodes.begin() + (static_cast<size_t>(1) << (level + 1)));

      for(size_t i = 0; i < (static_cast<size_t>(1) << level); i++) {
         BOTAN_ASSERT_NOMSG(xmss_hash.size() > i);

         node_addresses[i].set_tree_height(static_cast<uint32_t>(target_node_height - (level + 1)));
         node_addresses[i].set_tree_index((node_addresses[2 * i + 1].get_tree_index() - 1) >> 1);

         work.push_back(thread_pool.run(&XMSS_Common_Ops::randomize_tree_hash,
                                        std::ref(nodes[i]),
                                        std::cref(ro_nodes[2 * i]),
                                        std::cref(ro_nodes[2 * i + 1]),
                                        std::ref(node_addresses[i]),
                                        std::cref(this->public_seed()),
                                        std::ref(xmss_hash[i]),
                                        std::cref(m_xmss_params)));
      }

      for(auto& w : work) {
         w.get();
      }
      work.clear();
   }

   // Avoid creation an extra thread to calculate root node.
   node_addresses[0].set_tree_height(static_cast<uint32_t>(target_node_height - 1));
   node_addresses[0].set_tree_index((node_addresses[1].get_tree_index() - 1) >> 1);
   XMSS_Common_Ops::randomize_tree_hash(
      nodes[0], nodes[0], nodes[1], node_addresses[0], this->public_seed(), m_private->hash(), m_xmss_params);
   return nodes[0];
#else
   secure_vector<uint8_t> result;
   tree_hash_subtree(result, start_idx, target_node_height, adrs, m_private->hash());
   return result;
#endif
}

void XMSS_PrivateKey::tree_hash_subtree(secure_vector<uint8_t>& result,
                                        size_t start_idx,
                                        size_t target_node_height,
                                        XMSS_Address& adrs) {
   return tree_hash_subtree(result, start_idx, target_node_height, adrs, m_private->hash());
}

void XMSS_PrivateKey::tree_hash_subtree(
   secure_vector<uint8_t>& result, size_t start_idx, size_t target_node_height, XMSS_Address& adrs, XMSS_Hash& hash) {
   const secure_vector<uint8_t>& seed = this->public_seed();

   std::vector<secure_vector<uint8_t>> nodes(target_node_height + 1,
                                             secure_vector<uint8_t>(XMSS_PublicKey::m_xmss_params.element_size()));

   // node stack, holds all nodes on stack and one extra "pending" node. This
   // temporary node referred to as "node" in the XMSS standard document stays
   // a pending element, meaning it is not regarded as element on the stack
   // until level is increased.
   std::vector<uint8_t> node_levels(target_node_height + 1);

   uint8_t level = 0;  // current level on the node stack.
   const size_t last_idx = (static_cast<size_t>(1) << target_node_height) + start_idx;

   for(size_t i = start_idx; i < last_idx; i++) {
      adrs.set_type(XMSS_Address::Type::OTS_Hash_Address);
      adrs.set_ots_address(static_cast<uint32_t>(i));

      XMSS_WOTS_PublicKey pk = this->wots_public_key_for(adrs, hash);

      adrs.set_type(XMSS_Address::Type::LTree_Address);
      adrs.set_ltree_address(static_cast<uint32_t>(i));
      XMSS_Common_Ops::create_l_tree(nodes[level], pk.key_data(), adrs, seed, hash, m_xmss_params);
      node_levels[level] = 0;

      adrs.set_type(XMSS_Address::Type::Hash_Tree_Address);
      adrs.set_tree_height(0);
      adrs.set_tree_index(static_cast<uint32_t>(i));

      while(level > 0 && node_levels[level] == node_levels[level - 1]) {
         adrs.set_tree_index(((adrs.get_tree_index() - 1) >> 1));
         XMSS_Common_Ops::randomize_tree_hash(
            nodes[level - 1], nodes[level - 1], nodes[level], adrs, seed, hash, m_xmss_params);
         node_levels[level - 1]++;
         level--;  //Pop stack top element
         adrs.set_tree_height(adrs.get_tree_height() + 1);
      }
      level++;  //push temporary node to stack
   }
   result = nodes[level - 1];
}

XMSS_WOTS_PublicKey XMSS_PrivateKey::wots_public_key_for(XMSS_Address& adrs, XMSS_Hash& hash) const {
   const auto private_key = wots_private_key_for(adrs, hash);
   return XMSS_WOTS_PublicKey(m_private->wots_parameters(), m_public_seed, private_key, adrs, hash);
}

XMSS_WOTS_PrivateKey XMSS_PrivateKey::wots_private_key_for(XMSS_Address& adrs, XMSS_Hash& hash) const {
   switch(wots_derivation_method()) {
      case WOTS_Derivation_Method::NIST_SP800_208:
         return XMSS_WOTS_PrivateKey(
            m_private->wots_parameters(), m_public_seed, m_private->private_seed(), adrs, hash);
      case WOTS_Derivation_Method::Botan2x:
         return XMSS_WOTS_PrivateKey(m_private->wots_parameters(), m_private->private_seed(), adrs, hash);
   }

   throw Invalid_State("WOTS derivation method is out of the enum's range");
}

secure_vector<uint8_t> XMSS_PrivateKey::private_key_bits() const {
   return DER_Encoder().encode(raw_private_key(), ASN1_Type::OctetString).get_contents();
}

size_t XMSS_PrivateKey::reserve_unused_leaf_index() { return m_private->reserve_unused_leaf_index(); }

size_t XMSS_PrivateKey::unused_leaf_index() const { return m_private->unused_leaf_index(); }

size_t XMSS_PrivateKey::remaining_signatures() const { return m_private->remaining_signatures(); }

const secure_vector<uint8_t>& XMSS_PrivateKey::prf_value() const { return m_private->prf_value(); }

secure_vector<uint8_t> XMSS_PrivateKey::raw_private_key() const { return m_private->serialize(raw_public_key()); }

WOTS_Derivation_Method XMSS_PrivateKey::wots_derivation_method() const { return m_private->wots_derivation_method(); }

std::unique_ptr<Public_Key> XMSS_PrivateKey::public_key() const {
   return std::make_unique<XMSS_PublicKey>(xmss_parameters().oid(), root(), public_seed());
}

std::unique_ptr<PK_Ops::Signature> XMSS_PrivateKey::create_signature_op(RandomNumberGenerator& /*rng*/,
                                                                        std::string_view /*params*/,
                                                                        std::string_view provider) const {
   if(provider == "base" || provider.empty())
      return std::make_unique<XMSS_Signature_Operation>(*this);

   throw Provider_Not_Found(algo_name(), provider);
}

}  // namespace Botan

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	* (C) 2023 René Meusel - Rohde & Schwarz Cybersecurity
15	*
16	* Botan is released under the Simplified BSD License (see license.txt)
17	**/
18
19	#include <botan/xmss.h>
20
21	#include <botan/ber_dec.h>
22	#include <botan/der_enc.h>
23	#include <botan/internal/loadstor.h>
24	#include <botan/internal/stl_util.h>
25	#include <botan/internal/xmss_common_ops.h>
26	#include <botan/internal/xmss_index_registry.h>
27	#include <botan/internal/xmss_signature_operation.h>
28	#include <iterator>
29
30	#if defined(BOTAN_HAS_THREAD_UTILS)
31	#include <botan/internal/thread_pool.h>
32	#endif
33
34	namespace Botan {
35
36	namespace {
37
38	// fall back to raw decoding for previous versions, which did not encode an OCTET STRING
39	secure_vector<uint8_t> extract_raw_private_key(std::span<const uint8_t> key_bits, const XMSS_Parameters& xmss_params) {	45✔
40	secure_vector<uint8_t> raw_key;	45✔
41
42	// The public part of the input key bits was already parsed, so we can
43	// decide depending on the buffer length whether this must be BER decoded.
44	if(key_bits.size() == xmss_params.raw_private_key_size() \|\|	45✔
45	key_bits.size() == xmss_params.raw_legacy_private_key_size()) {	22✔
46	raw_key.assign(key_bits.begin(), key_bits.end());	28✔
47	} else {
48	DataSource_Memory src(key_bits);	17✔
49	BER_Decoder(src).decode(raw_key, ASN1_Type::OctetString).verify_end();	34✔
50	}	17✔
51
52	return raw_key;	45✔
53	}	×
54
55	} // namespace
56
57	class XMSS_PrivateKey_Internal {
58	public:
59	XMSS_PrivateKey_Internal(const XMSS_Parameters& xmss_params,	12✔
60	const XMSS_WOTS_Parameters& wots_params,
61	WOTS_Derivation_Method wots_derivation_method,
62	RandomNumberGenerator& rng) :	12✔
63	m_xmss_params(xmss_params),	12✔
64	m_wots_params(wots_params),	12✔
65	m_wots_derivation_method(wots_derivation_method),	12✔
66	m_hash(xmss_params),	12✔
67	m_prf(rng.random_vec(xmss_params.element_size())),	12✔
68	m_private_seed(rng.random_vec(xmss_params.element_size())),	12✔
69	m_index_reg(XMSS_Index_Registry::get_instance()) {}	12✔
70
71	XMSS_PrivateKey_Internal(const XMSS_Parameters& xmss_params,	×
72	const XMSS_WOTS_Parameters& wots_params,
73	WOTS_Derivation_Method wots_derivation_method,
74	secure_vector<uint8_t> private_seed,
75	secure_vector<uint8_t> prf) :	×
76	m_xmss_params(xmss_params),	×
77	m_wots_params(wots_params),	×
78	m_wots_derivation_method(wots_derivation_method),	×
79	m_hash(m_xmss_params),	×
80	m_prf(std::move(prf)),	×
81	m_private_seed(std::move(private_seed)),	×
82	m_index_reg(XMSS_Index_Registry::get_instance()) {}	×
83
84	XMSS_PrivateKey_Internal(const XMSS_Parameters& xmss_params,	45✔
85	const XMSS_WOTS_Parameters& wots_params,
86	std::span<const uint8_t> key_bits) :	45✔
87	m_xmss_params(xmss_params),	45✔
88	m_wots_params(wots_params),	45✔
89	m_hash(m_xmss_params),	45✔
90	m_index_reg(XMSS_Index_Registry::get_instance()) {	45✔
91	/*
92	The code requires sizeof(size_t) >= ceil(tree_height / 8)
93
94	Maximum supported tree height is 20, ceil(20/8) == 3, so 4 byte
95	size_t is sufficient for all defined parameters, or even a
96	(hypothetical) tree height 32, which would be extremely slow to
97	compute.
98	*/
99	static_assert(sizeof(size_t) >= 4, "size_t is big enough to support leaf index");	45✔
100
101	const secure_vector<uint8_t> raw_key = extract_raw_private_key(key_bits, xmss_params);	45✔
102
103	if(raw_key.size() != m_xmss_params.raw_private_key_size() &&	45✔
104	raw_key.size() != m_xmss_params.raw_legacy_private_key_size()) {	6✔
105	throw Decoding_Error("Invalid XMSS private key size");	×
106	}
107
108	BufferSlicer s(raw_key);	45✔
109
110	// We're not interested in the public key here
111	s.skip(m_xmss_params.raw_public_key_size());	45✔
112
113	auto unused_leaf_bytes = s.take(sizeof(uint32_t));	45✔
114	size_t unused_leaf = load_be<uint32_t>(unused_leaf_bytes.data(), 0);	45✔
115	if(unused_leaf >= (1ULL << m_xmss_params.tree_height())) {	45✔
116	throw Decoding_Error("XMSS private key leaf index out of bounds");	×
117	}
118
119	m_prf = s.take_secure_vector(m_xmss_params.element_size());	45✔
120	m_private_seed = s.take_secure_vector(m_xmss_params.element_size());	45✔
121	set_unused_leaf_index(unused_leaf);	45✔
122
123	// Legacy keys generated prior to Botan 3.x don't feature a
124	// WOTS+ key derivation method encoded in their private key.
125	m_wots_derivation_method =	45✔
126	(s.empty()) ? WOTS_Derivation_Method::Botan2x : static_cast<WOTS_Derivation_Method>(s.take(1).front());	45✔
127
128	BOTAN_ASSERT_NOMSG(s.empty());	45✔
129	}	45✔
130
131	secure_vector<uint8_t> serialize(std::vector<uint8_t> raw_public_key) const {	36✔
132	std::vector<uint8_t> unused_index(4);	36✔
133	store_be(static_cast<uint32_t>(unused_leaf_index()), unused_index.data());	36✔
134
135	std::vector<uint8_t> wots_derivation_method;	36✔
136	wots_derivation_method.push_back(static_cast<uint8_t>(m_wots_derivation_method));	36✔
137
138	return concat_as<secure_vector<uint8_t>>(	36✔
139	raw_public_key, unused_index, m_prf, m_private_seed, wots_derivation_method);	36✔
140	}	72✔
141
142	XMSS_Hash& hash() { return m_hash; }	670✔
143
144	const secure_vector<uint8_t>& prf_value() const { return m_prf; }	×
145
146	const secure_vector<uint8_t>& private_seed() { return m_private_seed; }	47,104✔
147
148	const XMSS_WOTS_Parameters& wots_parameters() { return m_wots_params; }	94,174✔
149
150	WOTS_Derivation_Method wots_derivation_method() const { return m_wots_derivation_method; }	47,104✔
151
152	XMSS_Index_Registry& index_registry() { return m_index_reg; }
153
154	std::shared_ptr<Atomic<size_t>> recover_global_leaf_index() const {	120✔
155	BOTAN_ASSERT(	120✔
156	m_private_seed.size() == m_xmss_params.element_size() && m_prf.size() == m_xmss_params.element_size(),
157	"Trying to retrieve index for partially initialized key");
158	return m_index_reg.get(m_private_seed, m_prf);	120✔
159	}
160
161	void set_unused_leaf_index(size_t idx) {	45✔
162	if(idx >= (1ULL << m_xmss_params.tree_height())) {	45✔
163	throw Decoding_Error("XMSS private key leaf index out of bounds");	×
164	} else {
165	std::atomic<size_t>& index = static_cast<std::atomic<size_t>&>(*recover_global_leaf_index());	45✔
166	size_t current = 0;	45✔
167
168	do {	45✔
169	current = index.load();	45✔
170	if(current > idx) {	45✔
171	return;	45✔
172	}
173	} while(!index.compare_exchange_strong(current, idx));	45✔
174	}
175	}
176
177	size_t reserve_unused_leaf_index() {	35✔
178	size_t idx = (static_cast<std::atomic<size_t>&>(*recover_global_leaf_index())).fetch_add(1);	35✔
179	if(idx >= m_xmss_params.total_number_of_signatures()) {	35✔
180	throw Decoding_Error("XMSS private key, one time signatures exhaused");	1✔
181	}
182	return idx;	34✔
183	}
184
185	size_t unused_leaf_index() const { return *recover_global_leaf_index(); }	36✔
186
187	size_t remaining_signatures() const {	4✔
188	return m_xmss_params.total_number_of_signatures() - *recover_global_leaf_index();	4✔
189	}
190
191	private:
192	const XMSS_Parameters& m_xmss_params;
193	const XMSS_WOTS_Parameters& m_wots_params;
194	WOTS_Derivation_Method m_wots_derivation_method;
195
196	XMSS_Hash m_hash;
197	secure_vector<uint8_t> m_prf;
198	secure_vector<uint8_t> m_private_seed;
199	XMSS_Index_Registry& m_index_reg;
200	};
201
202	XMSS_PrivateKey::XMSS_PrivateKey(std::span<const uint8_t> key_bits) :	45✔
203	XMSS_PublicKey(key_bits),
204	m_private(std::make_shared<XMSS_PrivateKey_Internal>(m_xmss_params, m_wots_params, key_bits)) {}	45✔
205
206	XMSS_PrivateKey::XMSS_PrivateKey(XMSS_Parameters::xmss_algorithm_t xmss_algo_id,	12✔
207	RandomNumberGenerator& rng,
208	WOTS_Derivation_Method wots_derivation_method) :	12✔
209	XMSS_PublicKey(xmss_algo_id, rng),
210	m_private(std::make_shared<XMSS_PrivateKey_Internal>(m_xmss_params, m_wots_params, wots_derivation_method, rng)) {	12✔
211	XMSS_Address adrs;	12✔
212	m_root = tree_hash(0, XMSS_PublicKey::m_xmss_params.tree_height(), adrs);	12✔
213	}	12✔
214
215	XMSS_PrivateKey::XMSS_PrivateKey(XMSS_Parameters::xmss_algorithm_t xmss_algo_id,	×
216	size_t idx_leaf,
217	secure_vector<uint8_t> wots_priv_seed,
218	secure_vector<uint8_t> prf,
219	secure_vector<uint8_t> root,
220	secure_vector<uint8_t> public_seed,
221	WOTS_Derivation_Method wots_derivation_method) :	×
222	XMSS_PublicKey(xmss_algo_id, std::move(root), std::move(public_seed)),	×
223	m_private(std::make_shared<XMSS_PrivateKey_Internal>(	×
224	m_xmss_params, m_wots_params, wots_derivation_method, std::move(wots_priv_seed), std::move(prf))) {	×
225	m_private->set_unused_leaf_index(idx_leaf);	×
226	BOTAN_ARG_CHECK(m_private->prf_value().size() == m_xmss_params.element_size(),	×
227	"XMSS: unexpected byte length of PRF value");
228	BOTAN_ARG_CHECK(m_private->private_seed().size() == m_xmss_params.element_size(),	×
229	"XMSS: unexpected byte length of private seed");
230	}	×
231
232	secure_vector<uint8_t> XMSS_PrivateKey::tree_hash(size_t start_idx, size_t target_node_height, XMSS_Address& adrs) {	352✔
233	BOTAN_ASSERT_NOMSG(target_node_height <= 30);	352✔
234	BOTAN_ASSERT((start_idx % (static_cast<size_t>(1) << target_node_height)) == 0,	352✔
235	"Start index must be divisible by 2^{target node height}.");
236
237	#if defined(BOTAN_HAS_THREAD_UTILS)
238	// dertermine number of parallel tasks to split the tree_hashing into.
239
240	Thread_Pool& thread_pool = Thread_Pool::global_instance();	352✔
241
242	const size_t split_level = std::min(target_node_height, thread_pool.worker_count());	352✔
243
244	// skip parallelization overhead for leaf nodes.
245	if(split_level == 0) {	352✔
246	secure_vector<uint8_t> result;	34✔
247	tree_hash_subtree(result, start_idx, target_node_height, adrs);	34✔
248	return result;	34✔
249	}	34✔
250
251	const size_t subtrees = static_cast<size_t>(1) << split_level;	318✔
252	const size_t last_idx = (static_cast<size_t>(1) << (target_node_height)) + start_idx;	318✔
253	const size_t offs = (last_idx - start_idx) / subtrees;	318✔
254	// this cast cannot overflow because target_node_height is limited
255	uint8_t level = static_cast<uint8_t>(split_level); // current level in the tree	318✔
256
257	BOTAN_ASSERT((last_idx - start_idx) % subtrees == 0,	318✔
258	"Number of worker threads in tree_hash need to divide range "
259	"of calculated nodes.");
260
261	std::vector<secure_vector<uint8_t>> nodes(subtrees,	318✔
262	secure_vector<uint8_t>(XMSS_PublicKey::m_xmss_params.element_size()));	636✔
263	std::vector<XMSS_Address> node_addresses(subtrees, adrs);	318✔
264	std::vector<XMSS_Hash> xmss_hash(subtrees, m_private->hash());	318✔
265	std::vector<std::future<void>> work;	318✔
266
267	// Calculate multiple subtrees in parallel.
268	for(size_t i = 0; i < subtrees; i++) {	1,522✔
269	using tree_hash_subtree_fn_t =	1,204✔
270	void (XMSS_PrivateKey::*)(secure_vector<uint8_t>&, size_t, size_t, XMSS_Address&, XMSS_Hash&);
271
272	tree_hash_subtree_fn_t work_fn = &XMSS_PrivateKey::tree_hash_subtree;	1,204✔
273
274	work.push_back(thread_pool.run(work_fn,	2,408✔
275	this,	2,408✔
276	std::ref(nodes[i]),	2,408✔
277	start_idx + i * offs,	2,408✔
278	target_node_height - split_level,	2,408✔
279	std::ref(node_addresses[i]),	1,204✔
280	std::ref(xmss_hash[i])));	2,408✔
281	}
282
283	for(auto& w : work) {	1,522✔
284	w.get();	1,204✔
285	}
286	work.clear();	318✔
287
288	// Parallelize the top tree levels horizontally
289	while(level-- > 1) {	602✔
290	std::vector<secure_vector<uint8_t>> ro_nodes(nodes.begin(),	284✔
291	nodes.begin() + (static_cast<size_t>(1) << (level + 1)));	284✔
292
293	for(size_t i = 0; i < (static_cast<size_t>(1) << level); i++) {	852✔
294	BOTAN_ASSERT_NOMSG(xmss_hash.size() > i);	568✔
295
296	node_addresses[i].set_tree_height(static_cast<uint32_t>(target_node_height - (level + 1)));	568✔
297	node_addresses[i].set_tree_index((node_addresses[2 * i + 1].get_tree_index() - 1) >> 1);	568✔
298
299	work.push_back(thread_pool.run(&XMSS_Common_Ops::randomize_tree_hash,	568✔
300	std::ref(nodes[i]),	1,136✔
301	std::cref(ro_nodes[2 * i]),	1,136✔
302	std::cref(ro_nodes[2 * i + 1]),	1,136✔
303	std::ref(node_addresses[i]),	568✔
304	std::cref(this->public_seed()),	568✔
305	std::ref(xmss_hash[i]),	568✔
306	std::cref(m_xmss_params)));	1,136✔
307	}
308
309	for(auto& w : work) {	852✔
310	w.get();	568✔
311	}
312	work.clear();	284✔
313	}	284✔
314
315	// Avoid creation an extra thread to calculate root node.
316	node_addresses[0].set_tree_height(static_cast<uint32_t>(target_node_height - 1));	318✔
317	node_addresses[0].set_tree_index((node_addresses[1].get_tree_index() - 1) >> 1);	318✔
318	XMSS_Common_Ops::randomize_tree_hash(	318✔
319	nodes[0], nodes[0], nodes[1], node_addresses[0], this->public_seed(), m_private->hash(), m_xmss_params);	318✔
320	return nodes[0];	318✔
321	#else
322	secure_vector<uint8_t> result;
323	tree_hash_subtree(result, start_idx, target_node_height, adrs, m_private->hash());
324	return result;
325	#endif
326	}	318✔
327
328	void XMSS_PrivateKey::tree_hash_subtree(secure_vector<uint8_t>& result,	34✔
329	size_t start_idx,
330	size_t target_node_height,
331	XMSS_Address& adrs) {
332	return tree_hash_subtree(result, start_idx, target_node_height, adrs, m_private->hash());	34✔
333	}
334
335	void XMSS_PrivateKey::tree_hash_subtree(	1,238✔
336	secure_vector<uint8_t>& result, size_t start_idx, size_t target_node_height, XMSS_Address& adrs, XMSS_Hash& hash) {
337	const secure_vector<uint8_t>& seed = this->public_seed();	1,238✔
338
339	std::vector<secure_vector<uint8_t>> nodes(target_node_height + 1,	1,238✔
340	secure_vector<uint8_t>(XMSS_PublicKey::m_xmss_params.element_size()));	2,476✔
341
342	// node stack, holds all nodes on stack and one extra "pending" node. This
343	// temporary node referred to as "node" in the XMSS standard document stays
344	// a pending element, meaning it is not regarded as element on the stack
345	// until level is increased.
346	std::vector<uint8_t> node_levels(target_node_height + 1);	1,238✔
347
348	uint8_t level = 0; // current level on the node stack.	1,238✔
349	const size_t last_idx = (static_cast<size_t>(1) << target_node_height) + start_idx;	1,238✔
350
351	for(size_t i = start_idx; i < last_idx; i++) {	48,308✔
352	adrs.set_type(XMSS_Address::Type::OTS_Hash_Address);	47,070✔
353	adrs.set_ots_address(static_cast<uint32_t>(i));	47,070✔
354
355	XMSS_WOTS_PublicKey pk = this->wots_public_key_for(adrs, hash);	47,070✔
356
357	adrs.set_type(XMSS_Address::Type::LTree_Address);	47,070✔
358	adrs.set_ltree_address(static_cast<uint32_t>(i));	47,070✔
359	XMSS_Common_Ops::create_l_tree(nodes[level], pk.key_data(), adrs, seed, hash, m_xmss_params);	47,070✔
360	node_levels[level] = 0;	47,070✔
361
362	adrs.set_type(XMSS_Address::Type::Hash_Tree_Address);	47,070✔
363	adrs.set_tree_height(0);	47,070✔
364	adrs.set_tree_index(static_cast<uint32_t>(i));	47,070✔
365
366	while(level > 0 && node_levels[level] == node_levels[level - 1]) {	92,902✔
367	adrs.set_tree_index(((adrs.get_tree_index() - 1) >> 1));	45,832✔
368	XMSS_Common_Ops::randomize_tree_hash(	45,832✔
369	nodes[level - 1], nodes[level - 1], nodes[level], adrs, seed, hash, m_xmss_params);	45,832✔
370	node_levels[level - 1]++;	45,832✔
371	level--; //Pop stack top element	45,832✔
372	adrs.set_tree_height(adrs.get_tree_height() + 1);	45,832✔
373	}
374	level++; //push temporary node to stack	47,070✔
375	}	47,070✔
376	result = nodes[level - 1];	1,238✔
377	}	1,238✔
378
379	XMSS_WOTS_PublicKey XMSS_PrivateKey::wots_public_key_for(XMSS_Address& adrs, XMSS_Hash& hash) const {	47,070✔
380	const auto private_key = wots_private_key_for(adrs, hash);	47,070✔
381	return XMSS_WOTS_PublicKey(m_private->wots_parameters(), m_public_seed, private_key, adrs, hash);	47,070✔
382	}	47,070✔
383
384	XMSS_WOTS_PrivateKey XMSS_PrivateKey::wots_private_key_for(XMSS_Address& adrs, XMSS_Hash& hash) const {	47,104✔
385	switch(wots_derivation_method()) {	47,104✔
386	case WOTS_Derivation_Method::NIST_SP800_208:	37,888✔
387	return XMSS_WOTS_PrivateKey(	37,888✔
388	m_private->wots_parameters(), m_public_seed, m_private->private_seed(), adrs, hash);	75,776✔
389	case WOTS_Derivation_Method::Botan2x:	9,216✔
390	return XMSS_WOTS_PrivateKey(m_private->wots_parameters(), m_private->private_seed(), adrs, hash);	18,432✔
391	}
392
393	throw Invalid_State("WOTS derivation method is out of the enum's range");	×
394	}
395
396	secure_vector<uint8_t> XMSS_PrivateKey::private_key_bits() const {	29✔
397	return DER_Encoder().encode(raw_private_key(), ASN1_Type::OctetString).get_contents();	87✔
398	}
399
400	size_t XMSS_PrivateKey::reserve_unused_leaf_index() { return m_private->reserve_unused_leaf_index(); }	35✔
401
402	size_t XMSS_PrivateKey::unused_leaf_index() const { return m_private->unused_leaf_index(); }	×
403
404	size_t XMSS_PrivateKey::remaining_signatures() const { return m_private->remaining_signatures(); }	4✔
405
406	const secure_vector<uint8_t>& XMSS_PrivateKey::prf_value() const { return m_private->prf_value(); }	34✔
407
408	secure_vector<uint8_t> XMSS_PrivateKey::raw_private_key() const { return m_private->serialize(raw_public_key()); }	72✔
409
410	WOTS_Derivation_Method XMSS_PrivateKey::wots_derivation_method() const { return m_private->wots_derivation_method(); }	47,104✔
411
412	std::unique_ptr<Public_Key> XMSS_PrivateKey::public_key() const {	2✔
413	return std::make_unique<XMSS_PublicKey>(xmss_parameters().oid(), root(), public_seed());	2✔
414	}
415
416	std::unique_ptr<PK_Ops::Signature> XMSS_PrivateKey::create_signature_op(RandomNumberGenerator& /rng/,	116✔
417	std::string_view /params/,
418	std::string_view provider) const {
419	if(provider == "base" \|\| provider.empty())	143✔
420	return std::make_unique<XMSS_Signature_Operation>(*this);	35✔
421
422	throw Provider_Not_Found(algo_name(), provider);	162✔
423	}
424
425	} // namespace Botan

randombit / botan / 5111374265

Source File Press 'n' to go to next uncovered line, 'b' for previous

Source File
Press 'n' to go to next uncovered line, 'b' for previous