11346962432

Committed 15 Oct 2024 01:20PM UTC coverage: 91.112% (-0.4%) from 91.512%

Build # 11346962432

Build Type

push

github

Committed by

web-flow

Commit Message

Merge pull request #4291 from Rohde-Schwarz/feature/slh-dsa

PQC: SLH-DSA

Run Details

90987 of 99863 relevant lines covered (91.11%)

9307997.46 hits per line

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

98.73

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

/*
* WOTS+ - Winternitz One Time Signature Plus Scheme (FIPS 205, Section 5)
* (C) 2023 Jack Lloyd
*     2023 Fabian Albert, René Meusel, Amos Treiber - Rohde & Schwarz Cybersecurity
*
* Botan is released under the Simplified BSD License (see license.txt)
**/

#include <botan/internal/sp_wots.h>

#include <botan/internal/sp_hash.h>
#include <botan/internal/stl_util.h>

namespace Botan {
namespace {

/**
 * @brief FIPS 205, Algorithm 5: chain
 *
 * Computes a WOTS+ hash chain for @p steps steps beginning with value
 * @p wots_chain_key at index @p start.
 */
void chain(StrongSpan<WotsPublicKeyNode> out,
           StrongSpan<const WotsNode> wots_chain_key,
           WotsHashIndex start,
           uint8_t steps,
           Sphincs_Address& addr,
           Sphincs_Hash_Functions& hashes,
           const Sphincs_Parameters& params) {
   // Initialize out with the value at position 'start'.
   std::copy(wots_chain_key.begin(), wots_chain_key.end(), out.begin());

   // Iterate 'steps' calls to the hash function.
   for(WotsHashIndex i = start; i < (start + steps) && i < params.w(); i++) {
      addr.set_hash_address(i);
      hashes.T(out, addr, out);
   }
}

/**
 * FIPS 205, Algorithm 4: base_2^b for WOTS+
 *
 * Interprets an array of bytes as integers in base w = 2^b.
 * This only works when lg_w is a divisor of 8.
 */
void base_2_b(std::span<WotsHashIndex> output, std::span<const uint8_t> input, const Sphincs_Parameters& params) {
   BOTAN_ASSERT_NOMSG(output.size() <= 8 * input.size() / params.log_w());

   size_t input_offset = 0;
   uint8_t current_byte = 0;
   uint32_t remaining_bits_in_current_byte = 0;

   for(auto& out : output) {
      if(remaining_bits_in_current_byte == 0) {
         current_byte = input[input_offset];
         ++input_offset;
         remaining_bits_in_current_byte = 8;
      }
      remaining_bits_in_current_byte -= params.log_w();
      out = WotsHashIndex((current_byte >> remaining_bits_in_current_byte) & (params.w() - 1));
   }
}

/**
 * Computes the WOTS+ checksum over a message (in base_2^b).
 * Corresponds to FIPS 205, Algorithm 7 or 8, Step 7.
 */
void wots_checksum(std::span<WotsHashIndex> output,
                   std::span<const WotsHashIndex> msg_base_w,
                   const Sphincs_Parameters& params) {
   uint32_t csum = 0;

   // Compute checksum.
   for(auto wots_hash_index : msg_base_w) {
      csum += params.w() - 1 - wots_hash_index.get();
   }

   // Convert checksum to base_w.
   csum = csum << ((8 - ((params.wots_len_2() * params.log_w()) % 8)) % 8);

   std::array<uint8_t, 4> csum_bytes;
   store_be(csum, csum_bytes.data());

   const size_t csum_bytes_size = params.wots_checksum_bytes();
   BOTAN_ASSERT_NOMSG(csum_bytes.size() >= csum_bytes_size);
   base_2_b(output, std::span(csum_bytes).last(csum_bytes_size), params);
}

}  // namespace

std::vector<WotsHashIndex> chain_lengths(const SphincsTreeNode& msg, const Sphincs_Parameters& params) {
   std::vector<WotsHashIndex> result(params.wots_len_1() + params.wots_len_2());

   auto msg_base_w = std::span(result).first(params.wots_len_1());
   auto checksum_base_w = std::span(result).last(params.wots_len_2());

   base_2_b(msg_base_w, msg.get(), params);
   wots_checksum(checksum_base_w, msg_base_w, params);

   return result;
}

WotsPublicKey wots_public_key_from_signature(const SphincsTreeNode& hashed_message,
                                             StrongSpan<const WotsSignature> signature,
                                             Sphincs_Address& address,
                                             const Sphincs_Parameters& params,
                                             Sphincs_Hash_Functions& hashes) {
   const std::vector<WotsHashIndex> lengths = chain_lengths(hashed_message, params);
   WotsPublicKey pk_buffer(params.wots_len() * params.n());
   BufferSlicer sig(signature);
   BufferStuffer pk(pk_buffer);

   for(WotsChainIndex i(0); i < params.wots_len(); i++) {
      address.set_chain_address(i);

      // params.w() can be one of {4, 8, 256}
      const WotsHashIndex start_index = lengths[i.get()];
      const uint8_t steps_to_take = static_cast<uint8_t>(params.w() - 1) - start_index.get();

      chain(pk.next<WotsPublicKeyNode>(params.n()),
            sig.take<WotsNode>(params.n()),
            start_index,
            steps_to_take,
            address,
            hashes,
            params);
   }

   return pk_buffer;
}

void wots_sign_and_pkgen(StrongSpan<WotsSignature> sig_out,
                         StrongSpan<SphincsTreeNode> leaf_out,
                         const SphincsSecretSeed& secret_seed,
                         TreeNodeIndex leaf_idx,
                         std::optional<TreeNodeIndex> sign_leaf_idx,
                         const std::vector<WotsHashIndex>& wots_steps,
                         Sphincs_Address& leaf_addr,
                         Sphincs_Address& pk_addr,
                         const Sphincs_Parameters& params,
                         Sphincs_Hash_Functions& hashes) {
   // `wots_steps` are needed only if `sign_leaf_idx` is set
   BOTAN_ASSERT_NOMSG(!sign_leaf_idx.has_value() || wots_steps.size() == params.wots_len());
   BOTAN_ASSERT_NOMSG(pk_addr.get_type() == Sphincs_Address_Type::WotsPublicKeyCompression);

   secure_vector<uint8_t> wots_sig;
   WotsPublicKey wots_pk_buffer(params.wots_bytes());

   BufferStuffer wots_pk(wots_pk_buffer);
   BufferStuffer sig(sig_out);

   leaf_addr.set_keypair_address(leaf_idx);
   pk_addr.set_keypair_address(leaf_idx);

   for(WotsChainIndex i(0); i < params.wots_len(); i++) {
      // If the current leaf is part of the signature wots_k stores the chain index
      //   of the value neccessary for the signature. Otherwise: nullopt (no signature)
      const auto wots_k = [&]() -> std::optional<WotsHashIndex> {
         if(sign_leaf_idx.has_value() && leaf_idx == sign_leaf_idx.value()) {
            return wots_steps[i.get()];
         } else {
            return std::nullopt;
         }
      }();

      // Start with the secret seed
      leaf_addr.set_chain_address(i);
      leaf_addr.set_hash_address(WotsHashIndex(0));
      leaf_addr.set_type(Sphincs_Address_Type::WotsKeyGeneration);

      auto buffer_s = wots_pk.next<WotsNode>(params.n());

      hashes.PRF(buffer_s, secret_seed, leaf_addr);

      leaf_addr.set_type(Sphincs_Address_Type::WotsHash);

      // Iterates down the WOTS chain
      for(WotsHashIndex k(0);; k++) {
         // Check if this is the value that needs to be saved as a part of the WOTS signature
         if(wots_k.has_value() && k == wots_k.value()) {
            std::copy(buffer_s.begin(), buffer_s.end(), sig.next<WotsNode>(params.n()).begin());
         }

         // Check if the top of the chain was hit
         if(k == params.w() - 1) {
            break;
         }

         // Iterate one step on the chain
         leaf_addr.set_hash_address(k);

         hashes.T(buffer_s, leaf_addr, buffer_s);
      }
   }

   // Do the final thash to generate the public keys
   hashes.T(leaf_out, pk_addr, wots_pk_buffer);
}

}  // namespace Botan

1	/*
2	* WOTS+ - Winternitz One Time Signature Plus Scheme (FIPS 205, Section 5)
3	* (C) 2023 Jack Lloyd
4	* 2023 Fabian Albert, René Meusel, Amos Treiber - Rohde & Schwarz Cybersecurity
5	*
6	* Botan is released under the Simplified BSD License (see license.txt)
7	**/
8
9	#include <botan/internal/sp_wots.h>
10
11	#include <botan/internal/sp_hash.h>
12	#include <botan/internal/stl_util.h>
13
14	namespace Botan {
15	namespace {
16
17	/**
18	* @brief FIPS 205, Algorithm 5: chain
19	*
20	* Computes a WOTS+ hash chain for @p steps steps beginning with value
21	* @p wots_chain_key at index @p start.
22	*/
23	void chain(StrongSpan<WotsPublicKeyNode> out,	86,173✔
24	StrongSpan<const WotsNode> wots_chain_key,
25	WotsHashIndex start,
26	uint8_t steps,
27	Sphincs_Address& addr,
28	Sphincs_Hash_Functions& hashes,
29	const Sphincs_Parameters& params) {
30	// Initialize out with the value at position 'start'.
31	std::copy(wots_chain_key.begin(), wots_chain_key.end(), out.begin());	86,173✔
32
33	// Iterate 'steps' calls to the hash function.
34	for(WotsHashIndex i = start; i < (start + steps) && i < params.w(); i++) {	741,853✔
35	addr.set_hash_address(i);	655,680✔
36	hashes.T(out, addr, out);	655,680✔
37	}
38	}	86,173✔
39
40	/**
41	* FIPS 205, Algorithm 4: base_2^b for WOTS+
42	*
43	* Interprets an array of bytes as integers in base w = 2^b.
44	* This only works when lg_w is a divisor of 8.
45	*/
46	void base_2_b(std::span<WotsHashIndex> output, std::span<const uint8_t> input, const Sphincs_Parameters& params) {	7,120✔
47	BOTAN_ASSERT_NOMSG(output.size() <= 8 * input.size() / params.log_w());	7,120✔
48
49	size_t input_offset = 0;	7,120✔
50	uint8_t current_byte = 0;	7,120✔
51	uint32_t remaining_bits_in_current_byte = 0;	7,120✔
52
53	for(auto& out : output) {	164,968✔
54	if(remaining_bits_in_current_byte == 0) {	157,848✔
55	current_byte = input[input_offset];	80,704✔
56	++input_offset;	80,704✔
57	remaining_bits_in_current_byte = 8;	80,704✔
58	}
59	remaining_bits_in_current_byte -= params.log_w();	157,848✔
60	out = WotsHashIndex((current_byte >> remaining_bits_in_current_byte) & (params.w() - 1));	157,848✔
61	}
62	}	7,120✔
63
64	/**
65	* Computes the WOTS+ checksum over a message (in base_2^b).
66	* Corresponds to FIPS 205, Algorithm 7 or 8, Step 7.
67	*/
68	void wots_checksum(std::span<WotsHashIndex> output,	3,560✔
69	std::span<const WotsHashIndex> msg_base_w,
70	const Sphincs_Parameters& params) {
71	uint32_t csum = 0;	3,560✔
72
73	// Compute checksum.
74	for(auto wots_hash_index : msg_base_w) {	150,728✔
75	csum += params.w() - 1 - wots_hash_index.get();	147,168✔
76	}
77
78	// Convert checksum to base_w.
79	csum = csum << ((8 - ((params.wots_len_2() * params.log_w()) % 8)) % 8);	3,560✔
80
81	std::array<uint8_t, 4> csum_bytes;	3,560✔
82	store_be(csum, csum_bytes.data());	3,560✔
83
84	const size_t csum_bytes_size = params.wots_checksum_bytes();	3,560✔
85	BOTAN_ASSERT_NOMSG(csum_bytes.size() >= csum_bytes_size);	3,560✔
86	base_2_b(output, std::span(csum_bytes).last(csum_bytes_size), params);	3,560✔
87	}	3,560✔
88
89	} // namespace
90
91	std::vector<WotsHashIndex> chain_lengths(const SphincsTreeNode& msg, const Sphincs_Parameters& params) {	3,560✔
92	std::vector<WotsHashIndex> result(params.wots_len_1() + params.wots_len_2());	3,560✔
93
94	auto msg_base_w = std::span(result).first(params.wots_len_1());	3,560✔
95	auto checksum_base_w = std::span(result).last(params.wots_len_2());	3,560✔
96
97	base_2_b(msg_base_w, msg.get(), params);	3,560✔
98	wots_checksum(checksum_base_w, msg_base_w, params);	3,560✔
99
100	return result;	3,560✔
101	}	×
102
103	WotsPublicKey wots_public_key_from_signature(const SphincsTreeNode& hashed_message,	1,951✔
104	StrongSpan<const WotsSignature> signature,
105	Sphincs_Address& address,
106	const Sphincs_Parameters& params,
107	Sphincs_Hash_Functions& hashes) {
108	const std::vector<WotsHashIndex> lengths = chain_lengths(hashed_message, params);	1,951✔
109	WotsPublicKey pk_buffer(params.wots_len() * params.n());	1,951✔
110	BufferSlicer sig(signature);	1,951✔
111	BufferStuffer pk(pk_buffer);	1,951✔
112
113	for(WotsChainIndex i(0); i < params.wots_len(); i++) {	88,124✔
114	address.set_chain_address(i);	86,173✔
115
116	// params.w() can be one of {4, 8, 256}
117	const WotsHashIndex start_index = lengths[i.get()];	86,173✔
118	const uint8_t steps_to_take = static_cast<uint8_t>(params.w() - 1) - start_index.get();	86,173✔
119
120	chain(pk.next<WotsPublicKeyNode>(params.n()),	86,173✔
121	sig.take<WotsNode>(params.n()),
122	start_index,
123	steps_to_take,
124	address,
125	hashes,
126	params);
127	}
128
129	return pk_buffer;	1,951✔
130	}	1,951✔
131
132	void wots_sign_and_pkgen(StrongSpan<WotsSignature> sig_out,	147,452✔
133	StrongSpan<SphincsTreeNode> leaf_out,
134	const SphincsSecretSeed& secret_seed,
135	TreeNodeIndex leaf_idx,
136	std::optional<TreeNodeIndex> sign_leaf_idx,
137	const std::vector<WotsHashIndex>& wots_steps,
138	Sphincs_Address& leaf_addr,
139	Sphincs_Address& pk_addr,
140	const Sphincs_Parameters& params,
141	Sphincs_Hash_Functions& hashes) {
142	// `wots_steps` are needed only if `sign_leaf_idx` is set
143	BOTAN_ASSERT_NOMSG(!sign_leaf_idx.has_value() \|\| wots_steps.size() == params.wots_len());	147,452✔
144	BOTAN_ASSERT_NOMSG(pk_addr.get_type() == Sphincs_Address_Type::WotsPublicKeyCompression);	147,452✔
145
146	secure_vector<uint8_t> wots_sig;	147,452✔
147	WotsPublicKey wots_pk_buffer(params.wots_bytes());	147,452✔
148
149	BufferStuffer wots_pk(wots_pk_buffer);	147,452✔
150	BufferStuffer sig(sig_out);	147,452✔
151
152	leaf_addr.set_keypair_address(leaf_idx);	147,452✔
153	pk_addr.set_keypair_address(leaf_idx);	147,452✔
154
155	for(WotsChainIndex i(0); i < params.wots_len(); i++) {	7,193,648✔
156	// If the current leaf is part of the signature wots_k stores the chain index
157	// of the value neccessary for the signature. Otherwise: nullopt (no signature)
158	const auto wots_k = [&]() -> std::optional<WotsHashIndex> {	14,092,392✔
159	if(sign_leaf_idx.has_value() && leaf_idx == sign_leaf_idx.value()) {	7,046,196✔
160	return wots_steps[i.get()];	71,675✔
161	} else {
162	return std::nullopt;	6,974,521✔
163	}
164	}();	7,046,196✔
165
166	// Start with the secret seed
167	leaf_addr.set_chain_address(i);	7,046,196✔
168	leaf_addr.set_hash_address(WotsHashIndex(0));	7,046,196✔
169	leaf_addr.set_type(Sphincs_Address_Type::WotsKeyGeneration);	7,046,196✔
170
171	auto buffer_s = wots_pk.next<WotsNode>(params.n());	7,046,196✔
172
173	hashes.PRF(buffer_s, secret_seed, leaf_addr);	7,046,196✔
174
175	leaf_addr.set_type(Sphincs_Address_Type::WotsHash);	7,046,196✔
176
177	// Iterates down the WOTS chain
178	for(WotsHashIndex k(0);; k++) {	7,046,196✔
179	// Check if this is the value that needs to be saved as a part of the WOTS signature
180	if(wots_k.has_value() && k == wots_k.value()) {	112,739,136✔
181	std::copy(buffer_s.begin(), buffer_s.end(), sig.next<WotsNode>(params.n()).begin());	71,675✔
182	}
183
184	// Check if the top of the chain was hit
185	if(k == params.w() - 1) {	112,739,136✔
186	break;
187	}
188
189	// Iterate one step on the chain
190	leaf_addr.set_hash_address(k);	105,692,940✔
191
192	hashes.T(buffer_s, leaf_addr, buffer_s);	105,692,940✔
193	}
194	}
195
196	// Do the final thash to generate the public keys
197	hashes.T(leaf_out, pk_addr, wots_pk_buffer);	147,452✔
198	}	147,452✔
199
200	} // namespace Botan

randombit / botan / 11346962432

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