11972552403

Committed 22 Nov 2024 12:26PM UTC coverage: 91.244% (+0.004%) from 91.24%

Build # 11972552403

Build Type

push

github

Committed by

web-flow

Commit Message

Merge pull request #4436 from randombit/jack/cleanup-curvegfp

Cleanups relating to CurveGFp

Run Details

93250 of 102198 relevant lines covered (91.24%)

11237819.31 hits per line

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

92.59

/src/lib/pubkey/classic_mceliece/cmce_keys_internal.cpp

/*
 * Classic McEliece key generation with Internal Private and Public Key classes
 * (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_keys_internal.h>

namespace Botan {

namespace {

/**
 * @brief Try to generate a Classic McEliece keypair for a given seed.
 *
 * @param[out] out_next_seed The next seed to use for key generation, if this iteration fails
 * @param params Classic McEliece parameters
 * @param seed The seed to used for this key generation iteration
 * @return a keypair on success, std::nullopt otherwise
 */
std::optional<Classic_McEliece_KeyPair_Internal> try_generate_keypair(std::span<uint8_t> out_next_seed,
                                                                      const Classic_McEliece_Parameters& params,
                                                                      CmceKeyGenSeed seed) {
   BOTAN_ASSERT_EQUAL(seed.size(), 32, "Valid seed length");
   BOTAN_ASSERT_EQUAL(out_next_seed.size(), 32, "Valid output seed length");

   auto big_e_xof = params.prg(seed);

   auto s = big_e_xof->output<CmceRejectionSeed>(params.n() / 8);
   auto ordering_bits = big_e_xof->output<CmceOrderingBits>((params.sigma2() * params.q()) / 8);
   auto irreducible_bits = big_e_xof->output<CmceIrreducibleBits>((params.sigma1() * params.t()) / 8);
   big_e_xof->output(out_next_seed);

   // Field-ordering generation - Classic McEliece ISO 8.2
   auto field_ordering = Classic_McEliece_Field_Ordering::create_field_ordering(params, ordering_bits);
   if(!field_ordering) {
      return std::nullopt;
   }

   // Irreducible-polynomial generation - Classic McEliece ISO 8.1
   auto g = params.poly_ring().compute_minimal_polynomial(irreducible_bits);
   if(!g) {
      return std::nullopt;
   }

   // Matrix generation for Goppa codes - Classic McEliece ISO 7.2
   auto pk_matrix_and_pivots =
      Classic_McEliece_Matrix::create_matrix_and_apply_pivots(params, field_ordering.value(), g.value());
   if(!pk_matrix_and_pivots) {
      return std::nullopt;
   }
   auto& [pk_matrix, pivots] = pk_matrix_and_pivots.value();

   // Key generation was successful - Create and return keys
   return Classic_McEliece_KeyPair_Internal{
      .private_key = std::make_shared<Classic_McEliece_PrivateKeyInternal>(
         params, std::move(seed), pivots, std::move(g.value()), std::move(field_ordering.value()), std::move(s)),
      .public_key = std::make_shared<Classic_McEliece_PublicKeyInternal>(params, std::move(pk_matrix))};
}

}  // namespace

Classic_McEliece_PrivateKeyInternal Classic_McEliece_PrivateKeyInternal::from_bytes(
   const Classic_McEliece_Parameters& params, std::span<const uint8_t> sk_bytes) {
   BOTAN_ASSERT(sk_bytes.size() == params.sk_size_bytes(), "Valid private key size");
   BufferSlicer sk_slicer(sk_bytes);

   auto delta = sk_slicer.copy<CmceKeyGenSeed>(params.seed_len());
   auto c = CmceColumnSelection(sk_slicer.take(params.sk_c_bytes()));
   auto g = Classic_McEliece_Minimal_Polynomial::from_bytes(sk_slicer.take(params.sk_poly_g_bytes()), params.poly_f());
   auto field_ordering = Classic_McEliece_Field_Ordering::create_from_control_bits(
      params, secure_bitvector(sk_slicer.take(params.sk_alpha_control_bytes())));
   auto s = sk_slicer.copy<CmceRejectionSeed>(params.sk_s_bytes());
   BOTAN_ASSERT_NOMSG(sk_slicer.empty());

   return Classic_McEliece_PrivateKeyInternal(
      params, std::move(delta), std::move(c), std::move(g), std::move(field_ordering), std::move(s));
}

secure_vector<uint8_t> Classic_McEliece_PrivateKeyInternal::serialize() const {
   auto control_bits = m_field_ordering.alphas_control_bits();

   /* NIST Impl. guide 6.1 Control-Bit Gen:
    *     As low-cost protection against faults in the control-bit computation, implementors are advised
    *     to check after the computation that applying the Benes network produces pi, and to
    *     restart key generation if this test fails; applying the Benes network is very fast.
    *
    * Here, we just assert that applying the Benes network produces pi.
    */
   BOTAN_ASSERT(Classic_McEliece_Field_Ordering::create_from_control_bits(m_params, control_bits)
                   .ct_is_equal(m_field_ordering)
                   .as_bool(),
                "Control Bit Computation Check");

   return concat(m_delta.get(), m_c.get().to_bytes(), m_g.serialize(), control_bits.to_bytes(), m_s);
}

bool Classic_McEliece_PrivateKeyInternal::check_key() const {
   auto prg = m_params.prg(m_delta);

   const auto s = prg->output<CmceRejectionSeed>(m_params.n() / 8);
   const auto ordering_bits = prg->output<CmceOrderingBits>((m_params.sigma2() * m_params.q()) / 8);
   const auto irreducible_bits = prg->output<CmceIrreducibleBits>((m_params.sigma1() * m_params.t()) / 8);

   // Recomputing s as hash of delta
   auto ret = CT::Mask<size_t>::expand(CT::is_equal<uint8_t>(s.data(), m_s.data(), m_params.n() / 8));

   // Checking weight of c
   ret &= CT::Mask<size_t>::is_equal(c().hamming_weight(), 32);

   if(auto g = m_params.poly_ring().compute_minimal_polynomial(irreducible_bits)) {
      for(size_t i = 0; i < g->degree() - 1; ++i) {
         ret &= CT::Mask<size_t>::expand(GF_Mask::is_equal(g->coef_at(i), m_g.coef_at(i)).elem_mask());
      }
   } else {
      ret = CT::Mask<size_t>::cleared();
   }

   // Check alpha control bits
   if(auto field_ord_from_seed = Classic_McEliece_Field_Ordering::create_field_ordering(m_params, ordering_bits)) {
      field_ord_from_seed->permute_with_pivots(m_params, c());
      ret &= CT::Mask<size_t>::expand(field_ord_from_seed->ct_is_equal(field_ordering()));
   } else {
      ret = CT::Mask<size_t>::cleared();
   }

   return ret.as_bool();
}

std::shared_ptr<Classic_McEliece_PublicKeyInternal> Classic_McEliece_PublicKeyInternal::create_from_private_key(
   const Classic_McEliece_PrivateKeyInternal& sk) {
   auto pk_matrix_and_pivot = Classic_McEliece_Matrix::create_matrix(sk.params(), sk.field_ordering(), sk.g());
   if(!pk_matrix_and_pivot.has_value()) {
      throw Decoding_Error("Cannot create public key from private key. Private key is invalid.");
   }
   auto& [pk_matrix, pivot] = pk_matrix_and_pivot.value();

   // There should not be a pivot other than 0xff ff ff ff 00 00 00 00.
   // Otherwise the gauss algorithm failed effectively.
   const auto pivot_is_valid = (CT::Mask<uint8_t>::expand(pivot.subvector(0, pivot.size() / 2).all()) &
                                CT::Mask<uint8_t>::expand(pivot.subvector(pivot.size() / 2).none()))
                                  .as_choice();
   if(!pivot_is_valid.as_bool()) {
      throw Decoding_Error("Cannot create public key from private key. Private key is invalid.");
   }

   auto pk = std::make_shared<Classic_McEliece_PublicKeyInternal>(sk.params(), std::move(pk_matrix));

   return pk;
}

Classic_McEliece_KeyPair_Internal Classic_McEliece_KeyPair_Internal::generate(const Classic_McEliece_Parameters& params,
                                                                              StrongSpan<const CmceInitialSeed> seed) {
   BOTAN_ASSERT_EQUAL(seed.size(), params.seed_len(), "Valid seed length");

   CmceKeyGenSeed next_seed(seed.size());
   CmceKeyGenSeed current_seed(seed.begin(), seed.end());

   while(true) {
      if(auto keypair = try_generate_keypair(next_seed, params, std::move(current_seed))) {
         return keypair.value();
      }
      current_seed = next_seed;
   }
}

}  // namespace Botan

1	/*
2	* Classic McEliece key generation with Internal Private and Public Key classes
3	* (C) 2023 Jack Lloyd
4	* 2023,2024 Fabian Albert, Amos Treiber - Rohde & Schwarz Cybersecurity
5	*
6	* Botan is released under the Simplified BSD License (see license.txt)
7	**/
8
9	#include <botan/internal/cmce_keys_internal.h>
10
11	namespace Botan {
12
13	namespace {
14
15	/**
16	* @brief Try to generate a Classic McEliece keypair for a given seed.
17	*
18	* @param[out] out_next_seed The next seed to use for key generation, if this iteration fails
19	* @param params Classic McEliece parameters
20	* @param seed The seed to used for this key generation iteration
21	* @return a keypair on success, std::nullopt otherwise
22	*/
23	std::optional<Classic_McEliece_KeyPair_Internal> try_generate_keypair(std::span<uint8_t> out_next_seed,	76✔
24	const Classic_McEliece_Parameters& params,
25	CmceKeyGenSeed seed) {
26	BOTAN_ASSERT_EQUAL(seed.size(), 32, "Valid seed length");	76✔
27	BOTAN_ASSERT_EQUAL(out_next_seed.size(), 32, "Valid output seed length");	76✔
28
29	auto big_e_xof = params.prg(seed);	76✔
30
31	auto s = big_e_xof->output<CmceRejectionSeed>(params.n() / 8);	76✔
32	auto ordering_bits = big_e_xof->output<CmceOrderingBits>((params.sigma2() * params.q()) / 8);	76✔
33	auto irreducible_bits = big_e_xof->output<CmceIrreducibleBits>((params.sigma1() * params.t()) / 8);	76✔
34	big_e_xof->output(out_next_seed);	76✔
35
36	// Field-ordering generation - Classic McEliece ISO 8.2
37	auto field_ordering = Classic_McEliece_Field_Ordering::create_field_ordering(params, ordering_bits);	76✔
38	if(!field_ordering) {	76✔
39	return std::nullopt;	×
40	}
41
42	// Irreducible-polynomial generation - Classic McEliece ISO 8.1
43	auto g = params.poly_ring().compute_minimal_polynomial(irreducible_bits);	76✔
44	if(!g) {	76✔
45	return std::nullopt;	×
46	}
47
48	// Matrix generation for Goppa codes - Classic McEliece ISO 7.2
49	auto pk_matrix_and_pivots =	76✔
50	Classic_McEliece_Matrix::create_matrix_and_apply_pivots(params, field_ordering.value(), g.value());	76✔
51	if(!pk_matrix_and_pivots) {	76✔
52	return std::nullopt;	35✔
53	}
54	auto& [pk_matrix, pivots] = pk_matrix_and_pivots.value();	41✔
55
56	// Key generation was successful - Create and return keys
57	return Classic_McEliece_KeyPair_Internal{	82✔
58	.private_key = std::make_shared<Classic_McEliece_PrivateKeyInternal>(
59	params, std::move(seed), pivots, std::move(g.value()), std::move(field_ordering.value()), std::move(s)),	41✔
60	.public_key = std::make_shared<Classic_McEliece_PublicKeyInternal>(params, std::move(pk_matrix))};	41✔
61	}	491✔
62
63	} // namespace
64
65	Classic_McEliece_PrivateKeyInternal Classic_McEliece_PrivateKeyInternal::from_bytes(	45✔
66	const Classic_McEliece_Parameters& params, std::span<const uint8_t> sk_bytes) {
67	BOTAN_ASSERT(sk_bytes.size() == params.sk_size_bytes(), "Valid private key size");	45✔
68	BufferSlicer sk_slicer(sk_bytes);	45✔
69
70	auto delta = sk_slicer.copy<CmceKeyGenSeed>(params.seed_len());	45✔
71	auto c = CmceColumnSelection(sk_slicer.take(params.sk_c_bytes()));	45✔
72	auto g = Classic_McEliece_Minimal_Polynomial::from_bytes(sk_slicer.take(params.sk_poly_g_bytes()), params.poly_f());	45✔
73	auto field_ordering = Classic_McEliece_Field_Ordering::create_from_control_bits(	45✔
74	params, secure_bitvector(sk_slicer.take(params.sk_alpha_control_bytes())));	45✔
75	auto s = sk_slicer.copy<CmceRejectionSeed>(params.sk_s_bytes());	45✔
76	BOTAN_ASSERT_NOMSG(sk_slicer.empty());	45✔
77
78	return Classic_McEliece_PrivateKeyInternal(	45✔
79	params, std::move(delta), std::move(c), std::move(g), std::move(field_ordering), std::move(s));	135✔
80	}	45✔
81
82	secure_vector<uint8_t> Classic_McEliece_PrivateKeyInternal::serialize() const {	96✔
83	auto control_bits = m_field_ordering.alphas_control_bits();	96✔
84
85	/* NIST Impl. guide 6.1 Control-Bit Gen:
86	* As low-cost protection against faults in the control-bit computation, implementors are advised
87	* to check after the computation that applying the Benes network produces pi, and to
88	* restart key generation if this test fails; applying the Benes network is very fast.
89	*
90	* Here, we just assert that applying the Benes network produces pi.
91	*/
92	BOTAN_ASSERT(Classic_McEliece_Field_Ordering::create_from_control_bits(m_params, control_bits)	192✔
93	.ct_is_equal(m_field_ordering)
94	.as_bool(),
95	"Control Bit Computation Check");
96
97	return concat(m_delta.get(), m_c.get().to_bytes(), m_g.serialize(), control_bits.to_bytes(), m_s);	384✔
98	}	96✔
99
100	bool Classic_McEliece_PrivateKeyInternal::check_key() const {	2✔
101	auto prg = m_params.prg(m_delta);	2✔
102
103	const auto s = prg->output<CmceRejectionSeed>(m_params.n() / 8);	2✔
104	const auto ordering_bits = prg->output<CmceOrderingBits>((m_params.sigma2() * m_params.q()) / 8);	2✔
105	const auto irreducible_bits = prg->output<CmceIrreducibleBits>((m_params.sigma1() * m_params.t()) / 8);	2✔
106
107	// Recomputing s as hash of delta
108	auto ret = CT::Mask<size_t>::expand(CT::is_equal<uint8_t>(s.data(), m_s.data(), m_params.n() / 8));	4✔
109
110	// Checking weight of c
111	ret &= CT::Mask<size_t>::is_equal(c().hamming_weight(), 32);	2✔
112
113	if(auto g = m_params.poly_ring().compute_minimal_polynomial(irreducible_bits)) {	2✔
114	for(size_t i = 0; i < g->degree() - 1; ++i) {	187✔
115	ret &= CT::Mask<size_t>::expand(GF_Mask::is_equal(g->coef_at(i), m_g.coef_at(i)).elem_mask());	185✔
116	}
117	} else {
118	ret = CT::Mask<size_t>::cleared();
119	}	×
120
121	// Check alpha control bits
122	if(auto field_ord_from_seed = Classic_McEliece_Field_Ordering::create_field_ordering(m_params, ordering_bits)) {	2✔
123	field_ord_from_seed->permute_with_pivots(m_params, c());	2✔
124	ret &= CT::Mask<size_t>::expand(field_ord_from_seed->ct_is_equal(field_ordering()));	2✔
125	} else {
126	ret = CT::Mask<size_t>::cleared();
127	}	×
128
129	return ret.as_bool();	2✔
130	}	8✔
131
132	std::shared_ptr<Classic_McEliece_PublicKeyInternal> Classic_McEliece_PublicKeyInternal::create_from_private_key(	45✔
133	const Classic_McEliece_PrivateKeyInternal& sk) {
134	auto pk_matrix_and_pivot = Classic_McEliece_Matrix::create_matrix(sk.params(), sk.field_ordering(), sk.g());	45✔
135	if(!pk_matrix_and_pivot.has_value()) {	45✔
136	throw Decoding_Error("Cannot create public key from private key. Private key is invalid.");	×
137	}
138	auto& [pk_matrix, pivot] = pk_matrix_and_pivot.value();	45✔
139
140	// There should not be a pivot other than 0xff ff ff ff 00 00 00 00.
141	// Otherwise the gauss algorithm failed effectively.
142	const auto pivot_is_valid = (CT::Mask<uint8_t>::expand(pivot.subvector(0, pivot.size() / 2).all()) &	90✔
143	CT::Mask<uint8_t>::expand(pivot.subvector(pivot.size() / 2).none()))	90✔
144	.as_choice();	45✔
145	if(!pivot_is_valid.as_bool()) {	45✔
146	throw Decoding_Error("Cannot create public key from private key. Private key is invalid.");	×
147	}
148
149	auto pk = std::make_shared<Classic_McEliece_PublicKeyInternal>(sk.params(), std::move(pk_matrix));	45✔
150
151	return pk;	45✔
152	}	45✔
153
154	Classic_McEliece_KeyPair_Internal Classic_McEliece_KeyPair_Internal::generate(const Classic_McEliece_Parameters& params,	41✔
155	StrongSpan<const CmceInitialSeed> seed) {
156	BOTAN_ASSERT_EQUAL(seed.size(), params.seed_len(), "Valid seed length");	41✔
157
158	CmceKeyGenSeed next_seed(seed.size());	41✔
159	CmceKeyGenSeed current_seed(seed.begin(), seed.end());	41✔
160
161	while(true) {	76✔
162	if(auto keypair = try_generate_keypair(next_seed, params, std::move(current_seed))) {	111✔
163	return keypair.value();	41✔
164	}	41✔
165	current_seed = next_seed;	111✔
166	}
167	}	82✔
168
169	} // namespace Botan

randombit / botan / 11972552403

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