22022566023

Committed 14 Feb 2026 06:55PM UTC coverage: 90.067%. Remained the same

Build # 22022566023

Build Type

push

github

Committed by

web-flow

Commit Message

Merge pull request #5334 from randombit/jack/test-h-remove-confirm

Remove confirm test helper, use test_is_true or test_is_false instead

Run Details

102260 of 113538 relevant lines covered (90.07%)

11510296.11 hits per line

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

96.83

/src/lib/pubkey/mce/gf2m_rootfind_dcmp.cpp

/*
 * (C) 2014 cryptosource GmbH
 * (C) 2014 Falko Strenzke fstrenzke@cryptosource.de
 *
 * Botan is released under the Simplified BSD License (see license.txt)
 *
 */

#include <botan/internal/polyn_gf2m.h>

#include <botan/assert.h>
#include <botan/exceptn.h>
#include <botan/internal/code_based_util.h>

namespace Botan {

namespace {

void patch_root_array(gf2m res_root_arr[], size_t res_root_arr_len, size_t root_pos) {
   volatile gf2m patch_elem = 0x01;
   volatile gf2m cond_mask = static_cast<gf2m>(root_pos == res_root_arr_len);
   cond_mask = expand_mask_16bit(cond_mask);
   cond_mask = ~cond_mask; /* now cond = 1 if not enough roots */
   patch_elem = patch_elem & cond_mask;
   for(size_t i = 0; i < res_root_arr_len; i++) {
      patch_elem = patch_elem + 1;
      gf2m masked_patch_elem = patch_elem & cond_mask;
      res_root_arr[i] ^= masked_patch_elem++;
   }
}

class gf2m_decomp_rootfind_state {
   public:
      gf2m_decomp_rootfind_state(const polyn_gf2m& p_polyn, size_t code_length);

      void calc_LiK(const polyn_gf2m& sigma);
      gf2m calc_Fxj_j_neq_0(const polyn_gf2m& sigma, gf2m j_gray);
      void calc_next_Aij();
      void calc_Ai_zero(const polyn_gf2m& sigma);
      secure_vector<gf2m> find_roots(const polyn_gf2m& sigma);

   private:
      size_t m_code_length;
      secure_vector<gf2m> m_Lik;  // size is outer_summands * m
      secure_vector<gf2m> m_Aij;  // ...
      uint32_t m_outer_summands;
      gf2m m_j;
      gf2m m_j_gray;
      gf2m m_sigma_3_l;
      gf2m m_sigma_3_neq_0_mask;
};

/**
* calculates ceil((t-4)/5) = outer_summands - 1
*/
uint32_t brootf_decomp_calc_sum_limit(uint32_t t) {
   if(t < 4) {
      return 0;
   }
   uint32_t result = t - 4;
   result += 4;
   result /= 5;
   return result;
}

gf2m_decomp_rootfind_state::gf2m_decomp_rootfind_state(const polyn_gf2m& polyn, size_t code_length) :
      m_code_length(code_length), m_j(0), m_j_gray(0) {
   const std::shared_ptr<GF2m_Field> sp_field = polyn.get_sp_field();
   const int deg_sigma = polyn.get_degree();
   if(deg_sigma <= 3) {
      throw Internal_Error("Unexpected degree in gf2m_decomp_rootfind_state");
   }

   const gf2m coeff_3 = polyn.get_coef(3);
   const gf2m coeff_head = polyn.get_coef(deg_sigma); /* dummy value for SCA CM */
   if(coeff_3 != 0) {
      this->m_sigma_3_l = sp_field->gf_l_from_n(coeff_3);
      this->m_sigma_3_neq_0_mask = 0xFFFF;
   } else {
      // dummy value needed for timing countermeasure
      this->m_sigma_3_l = sp_field->gf_l_from_n(coeff_head);
      this->m_sigma_3_neq_0_mask = 0;
   }

   this->m_outer_summands = 1 + brootf_decomp_calc_sum_limit(deg_sigma);
   this->m_Lik.resize(this->m_outer_summands * sp_field->get_extension_degree());
   this->m_Aij.resize(this->m_outer_summands);
}

void gf2m_decomp_rootfind_state::calc_Ai_zero(const polyn_gf2m& sigma) {
   /*
   * this function assumes this the first gray code element is zero
   */
   for(uint32_t i = 0; i < this->m_outer_summands; i++) {
      this->m_Aij[i] = sigma.get_coef(5 * i);
   }
   this->m_j = 0;
   this->m_j_gray = 0;
}

void gf2m_decomp_rootfind_state::calc_next_Aij() {
   /*
   * upon function entry, we have in the state j, Aij.
   * first thing, we declare Aij Aij_minusone and increase j.
   * Case j=0 upon function entry also included, then Aij contains A_{i,j=0}.
   */
   uint32_t Lik_pos_base = 0;

   this->m_j++;

   const gf2m new_j_gray = lex_to_gray(this->m_j);

   if((this->m_j & 1) != 0) {
      /* half of the times */
      Lik_pos_base = 0;
   } else if((this->m_j & 2) != 0) {
      /* one quarter of the times */
      Lik_pos_base = this->m_outer_summands;
   } else if((this->m_j & 4) != 0) {
      /* one eighth of the times */
      Lik_pos_base = this->m_outer_summands * 2;
   } else if((this->m_j & 8) != 0) {
      /* one sixteenth of the times */
      Lik_pos_base = this->m_outer_summands * 3;
   } else if((this->m_j & 16) != 0) {
      Lik_pos_base = this->m_outer_summands * 4;
   } else {
      gf2m delta_offs = 5;
      const gf2m diff = this->m_j_gray ^ new_j_gray;
      while(((static_cast<gf2m>(1) << delta_offs) & diff) == 0) {
         delta_offs++;
      }
      Lik_pos_base = delta_offs * this->m_outer_summands;
   }
   this->m_j_gray = new_j_gray;

   for(uint32_t i = 0; i < this->m_outer_summands; i++) {
      this->m_Aij[i] ^= this->m_Lik[Lik_pos_base + i];
   }
}

void gf2m_decomp_rootfind_state::calc_LiK(const polyn_gf2m& sigma) {
   const std::shared_ptr<GF2m_Field> sp_field = sigma.get_sp_field();
   const uint32_t d = sigma.get_degree();
   for(uint32_t k = 0; k < sp_field->get_extension_degree(); k++) {
      const uint32_t Lik_pos_base = k * this->m_outer_summands;
      gf2m alpha_l_k_tt2_ttj[4];
      alpha_l_k_tt2_ttj[0] = sp_field->gf_l_from_n(static_cast<gf2m>(1) << k);
      alpha_l_k_tt2_ttj[1] = sp_field->gf_mul_rrr(alpha_l_k_tt2_ttj[0], alpha_l_k_tt2_ttj[0]);
      alpha_l_k_tt2_ttj[2] = sp_field->gf_mul_rrr(alpha_l_k_tt2_ttj[1], alpha_l_k_tt2_ttj[1]);

      alpha_l_k_tt2_ttj[3] = sp_field->gf_mul_rrr(alpha_l_k_tt2_ttj[2], alpha_l_k_tt2_ttj[2]);
      for(uint32_t i = 0; i < this->m_outer_summands; i++) {
         const uint32_t five_i = 5 * i;
         const uint32_t Lik_pos = Lik_pos_base + i;
         this->m_Lik[Lik_pos] = 0;
         for(size_t j = 0; j <= 3; j++) {
            const uint32_t f_ind = five_i + (static_cast<uint32_t>(1) << j);
            if(f_ind > d) {
               break;
            }
            const gf2m f = sigma.get_coef(f_ind);

            const gf2m x = sp_field->gf_mul_zrz(alpha_l_k_tt2_ttj[j], f);
            this->m_Lik[Lik_pos] ^= x;
         }
      }
   }
}

gf2m gf2m_decomp_rootfind_state::calc_Fxj_j_neq_0(const polyn_gf2m& sigma, gf2m j_gray) {
   //needs the A_{ij} to compute F(x)_j
   gf2m sum = 0;
   const std::shared_ptr<GF2m_Field> sp_field = sigma.get_sp_field();
   const gf2m jl_gray = sp_field->gf_l_from_n(j_gray);
   gf2m xl_j_tt_5 = sp_field->gf_square_rr(jl_gray);
   const gf2m xl_gray_tt_3 = sp_field->gf_mul_rrr(xl_j_tt_5, jl_gray);
   xl_j_tt_5 = sp_field->gf_mul_rrr(xl_j_tt_5, xl_gray_tt_3);

   sum = sp_field->gf_mul_nrr(xl_gray_tt_3, this->m_sigma_3_l);
   sum &= this->m_sigma_3_neq_0_mask;
   /* here, we rely on compiler to be unable to optimize
   * for the state->sigma_3_neq_0_mask value
   */
   /* treat i = 0 special: */
   sum ^= this->m_Aij[0];
   /* treat i = 1 special also */

   if(this->m_outer_summands > 1) {
      const gf2m x = sp_field->gf_mul_zrz(xl_j_tt_5, this->m_Aij[1]); /* x_j^{5i} A_i^j */
      sum ^= x;
   }

   gf2m xl_j_tt_5i = xl_j_tt_5;

   for(uint32_t i = 2; i < this->m_outer_summands; i++) {
      xl_j_tt_5i = sp_field->gf_mul_rrr(xl_j_tt_5i, xl_j_tt_5);
      // now x_j_tt_5i lives up to its name
      const gf2m x = sp_field->gf_mul_zrz(xl_j_tt_5i, this->m_Aij[i]); /* x_j^{5i} A_i^(j) */
      sum ^= x;
   }
   return sum;
}

secure_vector<gf2m> gf2m_decomp_rootfind_state::find_roots(const polyn_gf2m& sigma) {
   const int sigma_degree = sigma.get_degree();
   BOTAN_ASSERT(sigma_degree > 0, "Valid sigma");
   secure_vector<gf2m> result(sigma_degree);
   uint32_t root_pos = 0;

   this->calc_Ai_zero(sigma);
   this->calc_LiK(sigma);
   for(;;) {
      gf2m eval_result = 0;

      if(this->m_j_gray == 0) {
         eval_result = sigma.get_coef(0);
      } else {
         eval_result = this->calc_Fxj_j_neq_0(sigma, this->m_j_gray);
      }

      if(eval_result == 0) {
         result[root_pos] = this->m_j_gray;
         root_pos++;
      }

      if(this->m_j + static_cast<uint32_t>(1) == m_code_length) {
         break;
      }
      this->calc_next_Aij();
   }

   // side channel / fault attack countermeasure:
   patch_root_array(result.data(), result.size(), root_pos);
   return result;
}

}  // end anonymous namespace

secure_vector<gf2m> find_roots_gf2m_decomp(const polyn_gf2m& polyn, size_t code_length) {
   gf2m_decomp_rootfind_state state(polyn, code_length);
   return state.find_roots(polyn);
}

}  // end namespace Botan

1	/*
2	* (C) 2014 cryptosource GmbH
3	* (C) 2014 Falko Strenzke fstrenzke@cryptosource.de
4	*
5	* Botan is released under the Simplified BSD License (see license.txt)
6	*
7	*/
8
9	#include <botan/internal/polyn_gf2m.h>
10
11	#include <botan/assert.h>
12	#include <botan/exceptn.h>
13	#include <botan/internal/code_based_util.h>
14
15	namespace Botan {
16
17	namespace {
18
19	void patch_root_array(gf2m res_root_arr[], size_t res_root_arr_len, size_t root_pos) {	2,641✔
20	volatile gf2m patch_elem = 0x01;	2,641✔
21	volatile gf2m cond_mask = static_cast<gf2m>(root_pos == res_root_arr_len);	2,641✔
22	cond_mask = expand_mask_16bit(cond_mask);	2,641✔
23	cond_mask = ~cond_mask; /* now cond = 1 if not enough roots */	2,641✔
24	patch_elem = patch_elem & cond_mask;	2,641✔
25	for(size_t i = 0; i < res_root_arr_len; i++) {	83,901✔
26	patch_elem = patch_elem + 1;	81,260✔
27	gf2m masked_patch_elem = patch_elem & cond_mask;	81,260✔
28	res_root_arr[i] ^= masked_patch_elem++;	81,260✔
29	}
30	}	2,641✔
31
32	class gf2m_decomp_rootfind_state {
33	public:
34	gf2m_decomp_rootfind_state(const polyn_gf2m& p_polyn, size_t code_length);
35
36	void calc_LiK(const polyn_gf2m& sigma);
37	gf2m calc_Fxj_j_neq_0(const polyn_gf2m& sigma, gf2m j_gray);
38	void calc_next_Aij();
39	void calc_Ai_zero(const polyn_gf2m& sigma);
40	secure_vector<gf2m> find_roots(const polyn_gf2m& sigma);
41
42	private:
43	size_t m_code_length;
44	secure_vector<gf2m> m_Lik; // size is outer_summands * m
45	secure_vector<gf2m> m_Aij; // ...
46	uint32_t m_outer_summands;
47	gf2m m_j;
48	gf2m m_j_gray;
49	gf2m m_sigma_3_l;
50	gf2m m_sigma_3_neq_0_mask;
51	};
52
53	/**
54	* calculates ceil((t-4)/5) = outer_summands - 1
55	*/
56	uint32_t brootf_decomp_calc_sum_limit(uint32_t t) {	2,641✔
57	if(t < 4) {	2,641✔
58	return 0;
59	}
60	uint32_t result = t - 4;	2,641✔
61	result += 4;	2,641✔
62	result /= 5;	2,641✔
63	return result;	2,641✔
64	}
65
66	gf2m_decomp_rootfind_state::gf2m_decomp_rootfind_state(const polyn_gf2m& polyn, size_t code_length) :	2,641✔
67	m_code_length(code_length), m_j(0), m_j_gray(0) {	2,641✔
68	const std::shared_ptr<GF2m_Field> sp_field = polyn.get_sp_field();	2,641✔
69	const int deg_sigma = polyn.get_degree();	2,641✔
70	if(deg_sigma <= 3) {	2,641✔
71	throw Internal_Error("Unexpected degree in gf2m_decomp_rootfind_state");	×
72	}
73
74	const gf2m coeff_3 = polyn.get_coef(3);	2,641✔
75	const gf2m coeff_head = polyn.get_coef(deg_sigma); /* dummy value for SCA CM */	2,641✔
76	if(coeff_3 != 0) {	2,641✔
77	this->m_sigma_3_l = sp_field->gf_l_from_n(coeff_3);	2,641✔
78	this->m_sigma_3_neq_0_mask = 0xFFFF;	2,641✔
79	} else {
80	// dummy value needed for timing countermeasure
81	this->m_sigma_3_l = sp_field->gf_l_from_n(coeff_head);	×
82	this->m_sigma_3_neq_0_mask = 0;	×
83	}
84
85	this->m_outer_summands = 1 + brootf_decomp_calc_sum_limit(deg_sigma);	2,641✔
86	this->m_Lik.resize(this->m_outer_summands * sp_field->get_extension_degree());	2,641✔
87	this->m_Aij.resize(this->m_outer_summands);	2,641✔
88	}	2,641✔
89
90	void gf2m_decomp_rootfind_state::calc_Ai_zero(const polyn_gf2m& sigma) {	2,641✔
91	/*
92	* this function assumes this the first gray code element is zero
93	*/
94	for(uint32_t i = 0; i < this->m_outer_summands; i++) {	20,522✔
95	this->m_Aij[i] = sigma.get_coef(5 * i);	17,881✔
96	}
97	this->m_j = 0;	2,641✔
98	this->m_j_gray = 0;	2,641✔
99	}
100
101	void gf2m_decomp_rootfind_state::calc_next_Aij() {	3,608,143✔
102	/*
103	* upon function entry, we have in the state j, Aij.
104	* first thing, we declare Aij Aij_minusone and increase j.
105	* Case j=0 upon function entry also included, then Aij contains A_{i,j=0}.
106	*/
107	uint32_t Lik_pos_base = 0;	3,608,143✔
108
109	this->m_j++;	3,608,143✔
110
111	const gf2m new_j_gray = lex_to_gray(this->m_j);	3,608,143✔
112
113	if((this->m_j & 1) != 0) {	3,608,143✔
114	/* half of the times */
115	Lik_pos_base = 0;
116	} else if((this->m_j & 2) != 0) {	1,802,751✔
117	/* one quarter of the times */
118	Lik_pos_base = this->m_outer_summands;	902,696✔
119	} else if((this->m_j & 4) != 0) {	900,055✔
120	/* one eighth of the times */
121	Lik_pos_base = this->m_outer_summands * 2;	451,348✔
122	} else if((this->m_j & 8) != 0) {	448,707✔
123	/* one sixteenth of the times */
124	Lik_pos_base = this->m_outer_summands * 3;	225,674✔
125	} else if((this->m_j & 16) != 0) {	223,033✔
126	Lik_pos_base = this->m_outer_summands * 4;	112,835✔
127	} else {
128	gf2m delta_offs = 5;	110,198✔
129	const gf2m diff = this->m_j_gray ^ new_j_gray;	110,198✔
130	while(((static_cast<gf2m>(1) << delta_offs) & diff) == 0) {	208,222✔
131	delta_offs++;	98,024✔
132	}
133	Lik_pos_base = delta_offs * this->m_outer_summands;	110,198✔
134	}
135	this->m_j_gray = new_j_gray;	3,608,143✔
136
137	for(uint32_t i = 0; i < this->m_outer_summands; i++) {	48,669,622✔
138	this->m_Aij[i] ^= this->m_Lik[Lik_pos_base + i];	45,061,479✔
139	}
140	}	3,608,143✔
141
142	void gf2m_decomp_rootfind_state::calc_LiK(const polyn_gf2m& sigma) {	2,641✔
143	const std::shared_ptr<GF2m_Field> sp_field = sigma.get_sp_field();	2,641✔
144	const uint32_t d = sigma.get_degree();	2,641✔
145	for(uint32_t k = 0; k < sp_field->get_extension_degree(); k++) {	28,599✔
146	const uint32_t Lik_pos_base = k * this->m_outer_summands;	25,958✔
147	gf2m alpha_l_k_tt2_ttj[4];	25,958✔
148	alpha_l_k_tt2_ttj[0] = sp_field->gf_l_from_n(static_cast<gf2m>(1) << k);	25,958✔
149	alpha_l_k_tt2_ttj[1] = sp_field->gf_mul_rrr(alpha_l_k_tt2_ttj[0], alpha_l_k_tt2_ttj[0]);	25,958✔
150	alpha_l_k_tt2_ttj[2] = sp_field->gf_mul_rrr(alpha_l_k_tt2_ttj[1], alpha_l_k_tt2_ttj[1]);	25,958✔
151
152	alpha_l_k_tt2_ttj[3] = sp_field->gf_mul_rrr(alpha_l_k_tt2_ttj[2], alpha_l_k_tt2_ttj[2]);	25,958✔
153	for(uint32_t i = 0; i < this->m_outer_summands; i++) {	217,100✔
154	const uint32_t five_i = 5 * i;	191,142✔
155	const uint32_t Lik_pos = Lik_pos_base + i;	191,142✔
156	this->m_Lik[Lik_pos] = 0;	191,142✔
157	for(size_t j = 0; j <= 3; j++) {	875,632✔
158	const uint32_t f_ind = five_i + (static_cast<uint32_t>(1) << j);	726,320✔
159	if(f_ind > d) {	726,320✔
160	break;
161	}
162	const gf2m f = sigma.get_coef(f_ind);	684,490✔
163
164	const gf2m x = sp_field->gf_mul_zrz(alpha_l_k_tt2_ttj[j], f);	684,490✔
165	this->m_Lik[Lik_pos] ^= x;	684,490✔
166	}
167	}
168	}
169	}	2,641✔
170
171	gf2m gf2m_decomp_rootfind_state::calc_Fxj_j_neq_0(const polyn_gf2m& sigma, gf2m j_gray) {	3,608,143✔
172	//needs the A_{ij} to compute F(x)_j
173	gf2m sum = 0;	3,608,143✔
174	const std::shared_ptr<GF2m_Field> sp_field = sigma.get_sp_field();	3,608,143✔
175	const gf2m jl_gray = sp_field->gf_l_from_n(j_gray);	3,608,143✔
176	gf2m xl_j_tt_5 = sp_field->gf_square_rr(jl_gray);	3,608,143✔
177	const gf2m xl_gray_tt_3 = sp_field->gf_mul_rrr(xl_j_tt_5, jl_gray);	3,608,143✔
178	xl_j_tt_5 = sp_field->gf_mul_rrr(xl_j_tt_5, xl_gray_tt_3);	3,608,143✔
179
180	sum = sp_field->gf_mul_nrr(xl_gray_tt_3, this->m_sigma_3_l);	3,608,143✔
181	sum &= this->m_sigma_3_neq_0_mask;	3,608,143✔
182	/* here, we rely on compiler to be unable to optimize
183	* for the state->sigma_3_neq_0_mask value
184	*/
185	/* treat i = 0 special: */
186	sum ^= this->m_Aij[0];	3,608,143✔
187	/* treat i = 1 special also */
188
189	if(this->m_outer_summands > 1) {	3,608,143✔
190	const gf2m x = sp_field->gf_mul_zrz(xl_j_tt_5, this->m_Aij[1]); /* x_j^{5i} A_i^j */	3,608,143✔
191	sum ^= x;	3,608,143✔
192	}
193
194	gf2m xl_j_tt_5i = xl_j_tt_5;
195
196	for(uint32_t i = 2; i < this->m_outer_summands; i++) {	41,453,336✔
197	xl_j_tt_5i = sp_field->gf_mul_rrr(xl_j_tt_5i, xl_j_tt_5);	37,845,193✔
198	// now x_j_tt_5i lives up to its name
199	const gf2m x = sp_field->gf_mul_zrz(xl_j_tt_5i, this->m_Aij[i]); /* x_j^{5i} A_i^(j) */	37,845,193✔
200	sum ^= x;	37,845,193✔
201	}
202	return sum;	3,608,143✔
203	}	3,608,143✔
204
205	secure_vector<gf2m> gf2m_decomp_rootfind_state::find_roots(const polyn_gf2m& sigma) {	2,641✔
206	const int sigma_degree = sigma.get_degree();	2,641✔
207	BOTAN_ASSERT(sigma_degree > 0, "Valid sigma");	2,641✔
208	secure_vector<gf2m> result(sigma_degree);	2,641✔
209	uint32_t root_pos = 0;	2,641✔
210
211	this->calc_Ai_zero(sigma);	2,641✔
212	this->calc_LiK(sigma);	2,641✔
213	for(;;) {	7,218,927✔
214	gf2m eval_result = 0;	3,610,784✔
215
216	if(this->m_j_gray == 0) {	3,610,784✔
217	eval_result = sigma.get_coef(0);	2,641✔
218	} else {
219	eval_result = this->calc_Fxj_j_neq_0(sigma, this->m_j_gray);	3,608,143✔
220	}
221
222	if(eval_result == 0) {	3,610,784✔
223	result[root_pos] = this->m_j_gray;	81,260✔
224	root_pos++;	81,260✔
225	}
226
227	if(this->m_j + static_cast<uint32_t>(1) == m_code_length) {	3,610,784✔
228	break;
229	}
230	this->calc_next_Aij();	3,608,143✔
231	}	3,608,143✔
232
233	// side channel / fault attack countermeasure:
234	patch_root_array(result.data(), result.size(), root_pos);	2,641✔
235	return result;	2,641✔
236	}	×
237
238	} // end anonymous namespace
239
240	secure_vector<gf2m> find_roots_gf2m_decomp(const polyn_gf2m& polyn, size_t code_length) {	2,641✔
241	gf2m_decomp_rootfind_state state(polyn, code_length);	2,641✔
242	return state.find_roots(polyn);	5,282✔
243	}	2,641✔
244
245	} // end namespace Botan

randombit / botan / 22022566023

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