11346280461

Committed 15 Oct 2024 12:42PM UTC coverage: 91.116% (-0.4%) from 91.512%

Build # 11346280461

Build Type

Pull #4291

github

Committed by

web-flow

Commit Message

Merge bfb91307b into 41619a286

Pull Request Pull Request #4291: PQC: SLH-DSA

Run Details

90991 of 99863 relevant lines covered (91.12%)

9298501.65 hits per line

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

95.71

/src/lib/pubkey/sphincsplus/sphincsplus_common/sp_fors.cpp

/*
 * FORS - Forest of Random Subsets (FIPS 205, Section 8)
 * (C) 2023 Jack Lloyd
 *     2023 Fabian Albert, René Meusel, Amos Treiber - Rohde & Schwarz Cybersecurity
 *
 * Parts of this file have been adapted from https://github.com/sphincs/sphincsplus
 *
 * Botan is released under the Simplified BSD License (see license.txt)
 */

#include <botan/internal/sp_fors.h>

#include <botan/assert.h>
#include <botan/hash.h>
#include <botan/sp_parameters.h>

#include <botan/internal/sp_address.h>
#include <botan/internal/sp_hash.h>
#include <botan/internal/sp_treehash.h>
#include <botan/internal/sp_types.h>
#include <botan/internal/stl_util.h>

namespace Botan {

namespace {

/// FIPS 205, Algorithm 4: base_2^b(X,b,out_len) with b = a and out_len = k (for usage in FORS)
std::vector<TreeNodeIndex> fors_message_to_indices(std::span<const uint8_t> message, const Sphincs_Parameters& params) {
   BOTAN_ASSERT_NOMSG((message.size() * 8) >= (params.k() * params.a()));

   std::vector<TreeNodeIndex> indices(params.k());

   uint32_t offset = 0;

   // This is one of the few places where the logic of SPHINCS+ round 3.1 and SLH-DSA differs
   auto update_idx = [&]() -> std::function<void(TreeNodeIndex&, uint32_t)> {
#if defined(BOTAN_HAS_SLH_DSA_WITH_SHA2) || defined(BOTAN_HAS_SLH_DSA_WITH_SHAKE)
      if(params.is_slh_dsa()) {
         return [&](TreeNodeIndex& idx, uint32_t i) {
            idx ^= (((message[offset >> 3] >> (~offset & 0x7)) & 0x1) << (params.a() - 1 - i));
         };
      }
#endif
#if defined(BOTAN_HAS_SPHINCS_PLUS_WITH_SHA2) || defined(BOTAN_HAS_SPHINCS_PLUS_WITH_SHAKE)
      if(!params.is_slh_dsa()) {
         return [&](TreeNodeIndex& idx, uint32_t i) { idx ^= (((message[offset >> 3] >> (offset & 0x7)) & 0x1) << i); };
      }
#endif
      throw Internal_Error("Missing FORS index update logic for SPHINCS+ or SLH-DSA");
   }();

   for(auto& idx : indices) {
      for(uint32_t i = 0; i < params.a(); ++i, ++offset) {
         update_idx(idx, i);
      }
   }

   return indices;
}

}  // namespace

SphincsTreeNode fors_sign_and_pkgen(StrongSpan<ForsSignature> sig_out,
                                    const SphincsHashedMessage& hashed_message,
                                    const SphincsSecretSeed& secret_seed,
                                    const Sphincs_Address& address,
                                    const Sphincs_Parameters& params,
                                    Sphincs_Hash_Functions& hashes) {
   BOTAN_ASSERT_NOMSG(sig_out.size() == params.fors_signature_bytes());

   const auto indices = fors_message_to_indices(hashed_message, params);

   auto fors_tree_addr = Sphincs_Address::as_keypair_from(address);

   auto fors_pk_addr = Sphincs_Address::as_keypair_from(address).set_type(Sphincs_Address::ForsTreeRootsCompression);

   std::vector<uint8_t> roots_buffer(params.k() * params.n());
   BufferStuffer roots(roots_buffer);
   BufferStuffer sig(sig_out);

   // Buffer to hold the FORS leafs during tree traversal
   // (Avoids a secure_vector allocation/deallocation in the hot path)
   ForsLeafSecret fors_leaf_secret(params.n());

   // For each of the k FORS subtrees: Compute the secret leaf, the authentication path
   // and the trees' root and append the signature respectively
   BOTAN_ASSERT_NOMSG(indices.size() == params.k());
   for(uint32_t i = 0; i < params.k(); ++i) {
      uint32_t idx_offset = i * (1 << params.a());

      // Compute the secret leaf given by the chunk of the message and append it to the signature
      fors_tree_addr.set_type(Sphincs_Address_Type::ForsKeyGeneration)
         .set_tree_height(TreeLayerIndex(0))
         .set_tree_index(indices[i] + idx_offset);

      hashes.PRF(sig.next<ForsLeafSecret>(params.n()), secret_seed, fors_tree_addr);

      // Compute the authentication path and root for this leaf node
      fors_tree_addr.set_type(Sphincs_Address_Type::ForsTree);

      GenerateLeafFunction fors_gen_leaf = [&](StrongSpan<SphincsTreeNode> out_root, TreeNodeIndex address_index) {
         fors_tree_addr.set_tree_index(address_index);
         fors_tree_addr.set_type(Sphincs_Address_Type::ForsKeyGeneration);

         hashes.PRF(fors_leaf_secret, secret_seed, fors_tree_addr);

         fors_tree_addr.set_type(Sphincs_Address_Type::ForsTree);
         hashes.T(out_root, fors_tree_addr, fors_leaf_secret);
      };

      treehash(roots.next<SphincsTreeNode>(params.n()),
               sig.next<SphincsAuthenticationPath>(params.a() * params.n()),
               params,
               hashes,
               indices[i],
               idx_offset,
               params.a(),
               fors_gen_leaf,
               fors_tree_addr);
   }

   BOTAN_ASSERT_NOMSG(sig.full());
   BOTAN_ASSERT_NOMSG(roots.full());

   // Compute the public key by the hash of the concatenation of all roots
   return hashes.T<SphincsTreeNode>(fors_pk_addr, roots_buffer);
}

SphincsTreeNode fors_public_key_from_signature(const SphincsHashedMessage& hashed_message,
                                               StrongSpan<const ForsSignature> signature,
                                               const Sphincs_Address& address,
                                               const Sphincs_Parameters& params,
                                               Sphincs_Hash_Functions& hashes) {
   const auto indices = fors_message_to_indices(hashed_message, params);

   auto fors_tree_addr = Sphincs_Address::as_keypair_from(address).set_type(Sphincs_Address::ForsTree);

   auto fors_pk_addr = Sphincs_Address::as_keypair_from(address).set_type(Sphincs_Address::ForsTreeRootsCompression);

   BufferSlicer s(signature);
   std::vector<uint8_t> roots_buffer(params.k() * params.n());
   BufferStuffer roots(roots_buffer);

   // For each of the k FORS subtrees: Reconstruct the subtree's root node by using the
   // leaf and the authentication path offered in the FORS signature.
   BOTAN_ASSERT_NOMSG(indices.size() == params.k());
   for(uint32_t i = 0; i < params.k(); ++i) {
      uint32_t idx_offset = i * (1 << params.a());

      // Compute the FORS leaf by using the secret leaf contained in the signature
      fors_tree_addr.set_tree_height(TreeLayerIndex(0)).set_tree_index(indices[i] + idx_offset);
      auto fors_leaf_secret = s.take<ForsLeafSecret>(params.n());
      auto auth_path = s.take<SphincsAuthenticationPath>(params.n() * params.a());
      auto leaf = hashes.T<SphincsTreeNode>(fors_tree_addr, fors_leaf_secret);

      // Reconstruct the subtree's root using the authentication path
      compute_root(roots.next<SphincsTreeNode>(params.n()),
                   params,
                   hashes,
                   leaf,
                   indices[i],
                   idx_offset,
                   auth_path,
                   params.a(),
                   fors_tree_addr);
   }

   BOTAN_ASSERT_NOMSG(roots.full());

   // Reconstruct the public key the signature creates with the hash of the concatenation of all roots
   // Only if the signature is valid, the pk is the correct FORS pk.
   return hashes.T<SphincsTreeNode>(fors_pk_addr, roots_buffer);
}

}  // namespace Botan

1	/*
2	* FORS - Forest of Random Subsets (FIPS 205, Section 8)
3	* (C) 2023 Jack Lloyd
4	* 2023 Fabian Albert, René Meusel, Amos Treiber - Rohde & Schwarz Cybersecurity
5	*
6	* Parts of this file have been adapted from https://github.com/sphincs/sphincsplus
7	*
8	* Botan is released under the Simplified BSD License (see license.txt)
9	*/
10
11	#include <botan/internal/sp_fors.h>
12
13	#include <botan/assert.h>
14	#include <botan/hash.h>
15	#include <botan/sp_parameters.h>
16
17	#include <botan/internal/sp_address.h>
18	#include <botan/internal/sp_hash.h>
19	#include <botan/internal/sp_treehash.h>
20	#include <botan/internal/sp_types.h>
21	#include <botan/internal/stl_util.h>
22
23	namespace Botan {
24
25	namespace {
26
27	/// FIPS 205, Algorithm 4: base_2^b(X,b,out_len) with b = a and out_len = k (for usage in FORS)
28	std::vector<TreeNodeIndex> fors_message_to_indices(std::span<const uint8_t> message, const Sphincs_Parameters& params) {	274✔
29	BOTAN_ASSERT_NOMSG((message.size() * 8) >= (params.k() * params.a()));	274✔
30
31	std::vector<TreeNodeIndex> indices(params.k());	274✔
32
33	uint32_t offset = 0;	274✔
34
35	// This is one of the few places where the logic of SPHINCS+ round 3.1 and SLH-DSA differs
36	auto update_idx = [&]() -> std::function<void(TreeNodeIndex&, uint32_t)> {	×
37	#if defined(BOTAN_HAS_SLH_DSA_WITH_SHA2) \|\| defined(BOTAN_HAS_SLH_DSA_WITH_SHAKE)
38	if(params.is_slh_dsa()) {	274✔
39	return [&](TreeNodeIndex& idx, uint32_t i) {	218✔
40	idx ^= (((message[offset >> 3] >> (~offset & 0x7)) & 0x1) << (params.a() - 1 - i));	48,450✔
41	};	218✔
42	}
43	#endif
44	#if defined(BOTAN_HAS_SPHINCS_PLUS_WITH_SHA2) \|\| defined(BOTAN_HAS_SPHINCS_PLUS_WITH_SHAKE)
45	if(!params.is_slh_dsa()) {	56✔
46	return [&](TreeNodeIndex& idx, uint32_t i) { idx ^= (((message[offset >> 3] >> (offset & 0x7)) & 0x1) << i); };	56✔
47	}
48	#endif
49	throw Internal_Error("Missing FORS index update logic for SPHINCS+ or SLH-DSA");	×
50	}();	274✔
51
52	for(auto& idx : indices) {	7,122✔
53	for(uint32_t i = 0; i < params.a(); ++i, ++offset) {	68,810✔
54	update_idx(idx, i);	123,924✔
55	}
56	}
57
58	return indices;	274✔
59	}	274✔
60
61	} // namespace
62
63	SphincsTreeNode fors_sign_and_pkgen(StrongSpan<ForsSignature> sig_out,	112✔
64	const SphincsHashedMessage& hashed_message,
65	const SphincsSecretSeed& secret_seed,
66	const Sphincs_Address& address,
67	const Sphincs_Parameters& params,
68	Sphincs_Hash_Functions& hashes) {
69	BOTAN_ASSERT_NOMSG(sig_out.size() == params.fors_signature_bytes());	112✔
70
71	const auto indices = fors_message_to_indices(hashed_message, params);	112✔
72
73	auto fors_tree_addr = Sphincs_Address::as_keypair_from(address);	112✔
74
75	auto fors_pk_addr = Sphincs_Address::as_keypair_from(address).set_type(Sphincs_Address::ForsTreeRootsCompression);	224✔
76
77	std::vector<uint8_t> roots_buffer(params.k() * params.n());	112✔
78	BufferStuffer roots(roots_buffer);	112✔
79	BufferStuffer sig(sig_out);	112✔
80
81	// Buffer to hold the FORS leafs during tree traversal
82	// (Avoids a secure_vector allocation/deallocation in the hot path)
83	ForsLeafSecret fors_leaf_secret(params.n());	112✔
84
85	// For each of the k FORS subtrees: Compute the secret leaf, the authentication path
86	// and the trees' root and append the signature respectively
87	BOTAN_ASSERT_NOMSG(indices.size() == params.k());	112✔
88	for(uint32_t i = 0; i < params.k(); ++i) {	3,173✔
89	uint32_t idx_offset = i * (1 << params.a());	3,061✔
90
91	// Compute the secret leaf given by the chunk of the message and append it to the signature
92	fors_tree_addr.set_type(Sphincs_Address_Type::ForsKeyGeneration)	3,061✔
93	.set_tree_height(TreeLayerIndex(0))	3,061✔
94	.set_tree_index(indices[i] + idx_offset);	3,061✔
95
96	hashes.PRF(sig.next<ForsLeafSecret>(params.n()), secret_seed, fors_tree_addr);	6,122✔
97
98	// Compute the authentication path and root for this leaf node
99	fors_tree_addr.set_type(Sphincs_Address_Type::ForsTree);	3,061✔
100
101	GenerateLeafFunction fors_gen_leaf = [&](StrongSpan<SphincsTreeNode> out_root, TreeNodeIndex address_index) {	×
102	fors_tree_addr.set_tree_index(address_index);	10,261,568✔
103	fors_tree_addr.set_type(Sphincs_Address_Type::ForsKeyGeneration);	10,261,568✔
104
105	hashes.PRF(fors_leaf_secret, secret_seed, fors_tree_addr);	10,261,568✔
106
107	fors_tree_addr.set_type(Sphincs_Address_Type::ForsTree);	10,261,568✔
108	hashes.T(out_root, fors_tree_addr, fors_leaf_secret);	10,261,568✔
109	};	3,061✔
110
111	treehash(roots.next<SphincsTreeNode>(params.n()),	3,061✔
112	sig.next<SphincsAuthenticationPath>(params.a() * params.n()),	3,061✔
113	params,
114	hashes,
115	indices[i],	3,061✔
116	idx_offset,
117	params.a(),
118	fors_gen_leaf,
119	fors_tree_addr);
120	}	3,061✔
121
122	BOTAN_ASSERT_NOMSG(sig.full());	112✔
123	BOTAN_ASSERT_NOMSG(roots.full());	112✔
124
125	// Compute the public key by the hash of the concatenation of all roots
126	return hashes.T<SphincsTreeNode>(fors_pk_addr, roots_buffer);	112✔
127	}	336✔
128
129	SphincsTreeNode fors_public_key_from_signature(const SphincsHashedMessage& hashed_message,	162✔
130	StrongSpan<const ForsSignature> signature,
131	const Sphincs_Address& address,
132	const Sphincs_Parameters& params,
133	Sphincs_Hash_Functions& hashes) {
134	const auto indices = fors_message_to_indices(hashed_message, params);	162✔
135
136	auto fors_tree_addr = Sphincs_Address::as_keypair_from(address).set_type(Sphincs_Address::ForsTree);	162✔
137
138	auto fors_pk_addr = Sphincs_Address::as_keypair_from(address).set_type(Sphincs_Address::ForsTreeRootsCompression);	162✔
139
140	BufferSlicer s(signature);	162✔
141	std::vector<uint8_t> roots_buffer(params.k() * params.n());	162✔
142	BufferStuffer roots(roots_buffer);	162✔
143
144	// For each of the k FORS subtrees: Reconstruct the subtree's root node by using the
145	// leaf and the authentication path offered in the FORS signature.
146	BOTAN_ASSERT_NOMSG(indices.size() == params.k());	162✔
147	for(uint32_t i = 0; i < params.k(); ++i) {	3,949✔
148	uint32_t idx_offset = i * (1 << params.a());	3,787✔
149
150	// Compute the FORS leaf by using the secret leaf contained in the signature
151	fors_tree_addr.set_tree_height(TreeLayerIndex(0)).set_tree_index(indices[i] + idx_offset);	3,787✔
152	auto fors_leaf_secret = s.take<ForsLeafSecret>(params.n());	3,787✔
153	auto auth_path = s.take<SphincsAuthenticationPath>(params.n() * params.a());	3,787✔
154	auto leaf = hashes.T<SphincsTreeNode>(fors_tree_addr, fors_leaf_secret);	3,787✔
155
156	// Reconstruct the subtree's root using the authentication path
157	compute_root(roots.next<SphincsTreeNode>(params.n()),	3,787✔
158	params,
159	hashes,
160	leaf,
161	indices[i],	3,787✔
162	idx_offset,
163	auth_path,
164	params.a(),
165	fors_tree_addr);
166	}	3,787✔
167
168	BOTAN_ASSERT_NOMSG(roots.full());	162✔
169
170	// Reconstruct the public key the signature creates with the hash of the concatenation of all roots
171	// Only if the signature is valid, the pk is the correct FORS pk.
172	return hashes.T<SphincsTreeNode>(fors_pk_addr, roots_buffer);	162✔
173	}	324✔
174
175	} // namespace Botan

randombit / botan / 11346280461

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