17073445006

Committed 19 Aug 2025 01:39AM UTC coverage: 90.654%. Remained the same

Build # 17073445006

Build Type

push

github

Committed by

web-flow

Commit Message

Merge pull request #5067 from randombit/jack/bn-div-neg

Correct bugs handling division by small negative numbers

Run Details

100084 of 110402 relevant lines covered (90.65%)

12161717.57 hits per line

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

98.39

/src/lib/pubkey/classic_mceliece/cmce_encaps.cpp

/*
 * Classic McEliece Encapsulation
 * Based on the public domain reference implementation by the designers
 * (https://classic.mceliece.org/impl.html - released in Oct 2022 for NISTPQC-R4)
 *
 * (C) 2023 Jack Lloyd
 *     2023,2024 Fabian Albert, Amos Treiber - Rohde & Schwarz Cybersecurity
 *
 * Botan is released under the Simplified BSD License (see license.txt)
 **/
#include <botan/internal/cmce_encaps.h>

#include <botan/rng.h>

namespace Botan {

CmceCodeWord Classic_McEliece_Encryptor::encode(const Classic_McEliece_Parameters& params,
                                                const CmceErrorVector& e,
                                                const Classic_McEliece_Matrix& mat) const {
   return mat.mul(params, e);
}

std::optional<CmceErrorVector> Classic_McEliece_Encryptor::fixed_weight_vector_gen(
   const Classic_McEliece_Parameters& params, RandomNumberGenerator& rng) const {
   const auto rand = rng.random_vec((params.sigma1() / 8) * params.tau());
   CT::poison(rand);
   uint16_t mask_m = (uint32_t(1) << params.m()) - 1;  // Only take m least significant bits
   secure_vector<uint16_t> a_values;
   a_values.reserve(params.tau());
   BufferSlicer rand_slicer(rand);

   // Steps 2 & 3: Create d_j from uniform random bits. The first t d_j entries
   //              in range {0,...,n-1} are defined as a_0,...,a_(t-1). ...
   for(size_t j = 0; j < params.tau(); ++j) {
      auto d = load_le<uint16_t>(rand_slicer.take(params.sigma1() / 8).data(), 0);
      // This is not CT, but neither is the reference implementation here.
      // This side channel only leaks which random elements are selected and which are dropped,
      // but no information about their content is leaked.
      d &= mask_m;
      bool d_in_range = d < params.n();
      CT::unpoison(d_in_range);
      if(d_in_range && a_values.size() < params.t()) {
         a_values.push_back(d);
      }
   }
   if(a_values.size() < params.t()) {
      // Step 3: ... If fewer than t of such elements exist restart
      return std::nullopt;
   }

   // Step 4: Restart if not all a_i are distinct
   for(size_t i = 1; i < params.t(); ++i) {
      for(size_t j = 0; j < i; ++j) {
         bool a_i_j_equal = a_values.at(i) == a_values.at(j);
         CT::unpoison(a_i_j_equal);
         if(a_i_j_equal) {
            return std::nullopt;
         }
      }
   }

   secure_vector<uint8_t> a_value_byte(params.t());
   secure_vector<uint8_t> e_bytes(ceil_tobytes(params.n()));

   // Step 5: Set all bits of e at the positions of a_values
   // Prepare the associated byte in e_bytes that is represented by each bit index in a_values
   // if we e is represented as a byte vector
   for(size_t j = 0; j < a_values.size(); ++j) {
      a_value_byte[j] = 1 << (a_values[j] % 8);
   }

   for(size_t i = 0; i < params.n() / 8; ++i) {
      for(size_t j = 0; j < a_values.size(); ++j) {
         // If the current byte is the one that is represented by the current bit index in a_values
         // then set the bit in e_bytes (in-byte position prepared above)
         auto mask = CT::Mask<uint16_t>::is_equal(static_cast<uint16_t>(i), static_cast<uint16_t>(a_values[j] >> 3));
         e_bytes[i] |= mask.if_set_return(a_value_byte[j]);
      }
   }

   return CmceErrorVector(secure_bitvector(e_bytes, params.n()));
}

void Classic_McEliece_Encryptor::raw_kem_encrypt(std::span<uint8_t> out_encapsulated_key,
                                                 std::span<uint8_t> out_shared_key,
                                                 RandomNumberGenerator& rng) {
   BOTAN_ARG_CHECK(out_encapsulated_key.size() == m_key->params().ciphertext_size(),
                   "Incorrect encapsulated key output length");
   BOTAN_ARG_CHECK(out_shared_key.size() == m_key->params().hash_out_bytes(), "Incorrect shared key output length");

   const auto& params = m_key->params();

   // Call fixed_weight until it is successful to
   // create a random error vector e of weight tau
   const CmceErrorVector e = [&] {
      // Emergency abort in case unexpected logical error to prevent endless loops
      //   Success probability: >24% per attempt (25% that elements are distinct * 96% enough elements are in range)
      //   => 647 attempts for 2^(-256) fail probability
      constexpr size_t MAX_ATTEMPTS = 647;
      for(size_t attempt = 0; attempt < MAX_ATTEMPTS; ++attempt) {
         if(auto maybe_e = fixed_weight_vector_gen(params, rng)) {
            return maybe_e.value();
         }
      }
      throw Internal_Error("Cannot created fixed weight vector. Is your RNG broken?");
   }();

   auto hash_func = params.hash_func();

   BufferStuffer big_c_stuf(out_encapsulated_key);
   const auto e_bytes = e.get().to_bytes();
   // Compute and store ciphertext C/C_0 from spec
   const auto big_c_0 = encode(params, e, m_key->matrix());
   big_c_0.to_bytes(big_c_stuf.next(ceil_tobytes(big_c_0.size())));
   if(params.is_pc()) {
      // Compute and store ciphertext C_1 from spec
      hash_func->update(0x02);
      hash_func->update(e_bytes);
      hash_func->final(big_c_stuf.next(hash_func->output_length()));
   }
   BOTAN_ASSERT_NOMSG(big_c_stuf.full());

   // Compute K = Hash(1,e,C) from spec
   hash_func->update(0x01);
   hash_func->update(e_bytes);
   hash_func->update(out_encapsulated_key);
   hash_func->final(out_shared_key);
   CT::unpoison_all(out_encapsulated_key, out_shared_key);
}

}  // namespace Botan

1	/*
2	* Classic McEliece Encapsulation
3	* Based on the public domain reference implementation by the designers
4	* (https://classic.mceliece.org/impl.html - released in Oct 2022 for NISTPQC-R4)
5	*
6	* (C) 2023 Jack Lloyd
7	* 2023,2024 Fabian Albert, Amos Treiber - Rohde & Schwarz Cybersecurity
8	*
9	* Botan is released under the Simplified BSD License (see license.txt)
10	**/
11	#include <botan/internal/cmce_encaps.h>
12
13	#include <botan/rng.h>
14
15	namespace Botan {
16
17	CmceCodeWord Classic_McEliece_Encryptor::encode(const Classic_McEliece_Parameters& params,	48✔
18	const CmceErrorVector& e,
19	const Classic_McEliece_Matrix& mat) const {
20	return mat.mul(params, e);	48✔
21	}
22
23	std::optional<CmceErrorVector> Classic_McEliece_Encryptor::fixed_weight_vector_gen(	769✔
24	const Classic_McEliece_Parameters& params, RandomNumberGenerator& rng) const {
25	const auto rand = rng.random_vec((params.sigma1() / 8) * params.tau());	769✔
26	CT::poison(rand);	769✔
27	uint16_t mask_m = (uint32_t(1) << params.m()) - 1; // Only take m least significant bits	769✔
28	secure_vector<uint16_t> a_values;	769✔
29	a_values.reserve(params.tau());	769✔
30	BufferSlicer rand_slicer(rand);	769✔
31
32	// Steps 2 & 3: Create d_j from uniform random bits. The first t d_j entries
33	// in range {0,...,n-1} are defined as a_0,...,a_(t-1). ...
34	for(size_t j = 0; j < params.tau(); ++j) {	106,311✔
35	auto d = load_le<uint16_t>(rand_slicer.take(params.sigma1() / 8).data(), 0);	105,542✔
36	// This is not CT, but neither is the reference implementation here.
37	// This side channel only leaks which random elements are selected and which are dropped,
38	// but no information about their content is leaked.
39	d &= mask_m;	105,542✔
40	bool d_in_range = d < params.n();	105,542✔
41	CT::unpoison(d_in_range);	105,542✔
42	if(d_in_range && a_values.size() < params.t()) {	105,542✔
43	a_values.push_back(d);	55,971✔
44	}
45	}
46	if(a_values.size() < params.t()) {	769✔
47	// Step 3: ... If fewer than t of such elements exist restart
48	return std::nullopt;	×
49	}
50
51	// Step 4: Restart if not all a_i are distinct
52	for(size_t i = 1; i < params.t(); ++i) {	11,789✔
53	for(size_t j = 0; j < i; ++j) {	582,443✔
54	bool a_i_j_equal = a_values.at(i) == a_values.at(j);	571,423✔
55	CT::unpoison(a_i_j_equal);	571,423✔
56	if(a_i_j_equal) {	571,423✔
57	return std::nullopt;	721✔
58	}
59	}
60	}
61
62	secure_vector<uint8_t> a_value_byte(params.t());	48✔
63	secure_vector<uint8_t> e_bytes(ceil_tobytes(params.n()));	48✔
64
65	// Step 5: Set all bits of e at the positions of a_values
66	// Prepare the associated byte in e_bytes that is represented by each bit index in a_values
67	// if we e is represented as a byte vector
68	for(size_t j = 0; j < a_values.size(); ++j) {	5,508✔
69	a_value_byte[j] = 1 << (a_values[j] % 8);	5,460✔
70	}
71
72	for(size_t i = 0; i < params.n() / 8; ++i) {	38,880✔
73	for(size_t j = 0; j < a_values.size(); ++j) {	4,637,352✔
74	// If the current byte is the one that is represented by the current bit index in a_values
75	// then set the bit in e_bytes (in-byte position prepared above)
76	auto mask = CT::Mask<uint16_t>::is_equal(static_cast<uint16_t>(i), static_cast<uint16_t>(a_values[j] >> 3));	4,598,520✔
77	e_bytes[i] \|= mask.if_set_return(a_value_byte[j]);	4,598,520✔
78	}
79	}
80
81	return CmceErrorVector(secure_bitvector(e_bytes, params.n()));	48✔
82	}	1,634✔
83
84	void Classic_McEliece_Encryptor::raw_kem_encrypt(std::span<uint8_t> out_encapsulated_key,	49✔
85	std::span<uint8_t> out_shared_key,
86	RandomNumberGenerator& rng) {
87	BOTAN_ARG_CHECK(out_encapsulated_key.size() == m_key->params().ciphertext_size(),	49✔
88	"Incorrect encapsulated key output length");
89	BOTAN_ARG_CHECK(out_shared_key.size() == m_key->params().hash_out_bytes(), "Incorrect shared key output length");	49✔
90
91	const auto& params = m_key->params();	49✔
92
93	// Call fixed_weight until it is successful to
94	// create a random error vector e of weight tau
95	const CmceErrorVector e = [&] {	146✔
96	// Emergency abort in case unexpected logical error to prevent endless loops
97	// Success probability: >24% per attempt (25% that elements are distinct * 96% enough elements are in range)
98	// => 647 attempts for 2^(-256) fail probability
99	constexpr size_t MAX_ATTEMPTS = 647;	49✔
100	for(size_t attempt = 0; attempt < MAX_ATTEMPTS; ++attempt) {	770✔
101	if(auto maybe_e = fixed_weight_vector_gen(params, rng)) {	769✔
102	return maybe_e.value();	96✔
103	}	769✔
104	}
105	throw Internal_Error("Cannot created fixed weight vector. Is your RNG broken?");	1✔
106	}();	49✔
107
108	auto hash_func = params.hash_func();	48✔
109
110	BufferStuffer big_c_stuf(out_encapsulated_key);	48✔
111	const auto e_bytes = e.get().to_bytes();	48✔
112	// Compute and store ciphertext C/C_0 from spec
113	const auto big_c_0 = encode(params, e, m_key->matrix());	48✔
114	big_c_0.to_bytes(big_c_stuf.next(ceil_tobytes(big_c_0.size())));	48✔
115	if(params.is_pc()) {	48✔
116	// Compute and store ciphertext C_1 from spec
117	hash_func->update(0x02);	18✔
118	hash_func->update(e_bytes);	18✔
119	hash_func->final(big_c_stuf.next(hash_func->output_length()));	18✔
120	}
121	BOTAN_ASSERT_NOMSG(big_c_stuf.full());	48✔
122
123	// Compute K = Hash(1,e,C) from spec
124	hash_func->update(0x01);	48✔
125	hash_func->update(e_bytes);	48✔
126	hash_func->update(out_encapsulated_key);	48✔
127	hash_func->final(out_shared_key);	48✔
128	CT::unpoison_all(out_encapsulated_key, out_shared_key);	48✔
129	}	192✔
130
131	} // namespace Botan

randombit / botan / 17073445006

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