Botan  2.12.1
Crypto and TLS for C++11
gf2m_rootfind_dcmp.cpp
Go to the documentation of this file.
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/polyn_gf2m.h>
10 #include <botan/internal/bit_ops.h>
11 #include <botan/internal/code_based_util.h>
12 #include <botan/exceptn.h>
13 
14 namespace Botan {
15 
16 namespace {
17 
18 uint32_t patch_root_array(gf2m* res_root_arr,
19  uint32_t res_root_arr_len,
20  uint32_t root_pos)
21  {
22  volatile gf2m patch_elem = 0x01;
23  volatile gf2m cond_mask = (root_pos == res_root_arr_len);
24  cond_mask = expand_mask_16bit(cond_mask);
25  cond_mask = ~cond_mask; /* now cond = 1 if not enough roots */
26  patch_elem &= cond_mask;
27  for(size_t i = 0; i < res_root_arr_len; i++)
28  {
29  gf2m masked_patch_elem = (patch_elem++) & cond_mask;
30  res_root_arr[i] ^= masked_patch_elem++;
31  }
32  return res_root_arr_len;
33  }
34 
35 class gf2m_decomp_rootfind_state
36  {
37  public:
38  gf2m_decomp_rootfind_state(const polyn_gf2m & p_polyn, uint32_t code_length);
39 
40  void calc_LiK(const polyn_gf2m & sigma);
41  gf2m calc_Fxj_j_neq_0( const polyn_gf2m & sigma, gf2m j_gray);
42  void calc_next_Aij();
43  void calc_Ai_zero(const polyn_gf2m & sigma);
44  secure_vector<gf2m> find_roots(const polyn_gf2m & sigma);
45  uint32_t get_code_length() const { return code_length; }
46  uint32_t code_length;
47  secure_vector<gf2m> m_Lik; // size is outer_summands * m
48  secure_vector<gf2m> m_Aij; // ...
49  uint32_t m_outer_summands;
54  };
55 
56 /*
57 * !! Attention: assumes gf2m is 16bit !!
58 */
59 #if 0
60 gf2m brootf_decomp_gray_to_lex(gf2m gray)
61  {
62  static_assert(sizeof(gf2m) == 2, "Expected size");
63  gf2m result = gray ^ (gray>>8);
64  result ^= (result >> 4);
65  result ^= (result >> 2);
66  result ^= (result >> 1);
67  return result;
68  }
69 #endif
70 
71 /**
72 * calculates ceil((t-4)/5) = outer_summands - 1
73 */
74 uint32_t brootf_decomp_calc_sum_limit(uint32_t t)
75  {
76  uint32_t result;
77  if(t < 4)
78  {
79  return 0;
80  }
81  result = t - 4;
82  result += 4;
83  result /= 5;
84  return result;
85  }
86 
87 gf2m_decomp_rootfind_state::gf2m_decomp_rootfind_state(const polyn_gf2m & polyn, uint32_t the_code_length) :
88  code_length(the_code_length), m_j(0), m_j_gray(0)
89  {
90  gf2m coeff_3;
91  gf2m coeff_head;
92  std::shared_ptr<GF2m_Field> sp_field = polyn.get_sp_field();
93  int deg_sigma = polyn.get_degree();
94  if(deg_sigma <= 3)
95  {
96  throw Internal_Error("Unexpected degree in gf2m_decomp_rootfind_state");
97  }
98 
99  coeff_3 = polyn.get_coef( 3);
100  coeff_head = polyn.get_coef( deg_sigma); /* dummy value for SCA CM */
101  if(coeff_3 != 0)
102  {
103  this->m_sigma_3_l = sp_field->gf_l_from_n(coeff_3);
104  this->m_sigma_3_neq_0_mask = 0xFFFF;
105  }
106  else
107  {
108  // dummy value needed for timing countermeasure
109  this->m_sigma_3_l = sp_field->gf_l_from_n(coeff_head);
110  this->m_sigma_3_neq_0_mask = 0 ;
111  }
112 
113  this->m_outer_summands = 1 + brootf_decomp_calc_sum_limit(deg_sigma);
114  this->m_Lik.resize(this->m_outer_summands * sp_field->get_extension_degree());
115  this->m_Aij.resize(this->m_outer_summands);
116  }
117 
118 void gf2m_decomp_rootfind_state::calc_Ai_zero(const polyn_gf2m & sigma)
119  {
120  uint32_t i;
121  /*
122  * this function assumes this the first gray code element is zero
123  */
124  for(i = 0; i < this->m_outer_summands; i++)
125  {
126  this->m_Aij[i] = sigma.get_coef(5*i);
127  }
128  this->m_j = 0;
129  this->m_j_gray = 0;
130  }
131 
132 void gf2m_decomp_rootfind_state::calc_next_Aij()
133  {
134  /*
135  * upon function entry, we have in the state j, Aij.
136  * first thing, we declare Aij Aij_minusone and increase j.
137  * Case j=0 upon function entry also included, then Aij contains A_{i,j=0}.
138  */
139  uint32_t i;
140  gf2m diff, new_j_gray;
141  uint32_t Lik_pos_base;
142 
143  this->m_j++;
144 
145  new_j_gray = lex_to_gray(this->m_j);
146 
147  if(this->m_j & 1) /* half of the times */
148  {
149  Lik_pos_base = 0;
150  }
151  else if(this->m_j & 2) /* one quarter of the times */
152  {
153  Lik_pos_base = this->m_outer_summands;
154  }
155  else if( this->m_j & 4) /* one eighth of the times */
156  {
157  Lik_pos_base = this->m_outer_summands * 2;
158  }
159  else if( this->m_j & 8) /* one sixteenth of the times */
160  {
161  Lik_pos_base = this->m_outer_summands * 3;
162  }
163  else if( this->m_j & 16) /* ... */
164  {
165  Lik_pos_base = this->m_outer_summands * 4;
166  }
167  else
168  {
169  gf2m delta_offs = 5;
170  diff = this->m_j_gray ^ new_j_gray;
171  while(((static_cast<gf2m>(1) << delta_offs) & diff) == 0)
172  {
173  delta_offs++;
174 
175  }
176  Lik_pos_base = delta_offs * this->m_outer_summands;
177  }
178  this->m_j_gray = new_j_gray;
179 
180  i = 0;
181  for(; i < this->m_outer_summands; i++)
182  {
183  this->m_Aij[i] ^= this->m_Lik[Lik_pos_base + i];
184  }
185 
186  }
187 
188 void gf2m_decomp_rootfind_state::calc_LiK(const polyn_gf2m & sigma)
189  {
190  std::shared_ptr<GF2m_Field> sp_field = sigma.get_sp_field();
191  uint32_t i, k, d;
192  d = sigma.get_degree();
193  for(k = 0; k < sp_field->get_extension_degree(); k++)
194  {
195  uint32_t Lik_pos_base = k * this->m_outer_summands;
196  gf2m alpha_l_k_tt2_ttj[4];
197  alpha_l_k_tt2_ttj[0] = sp_field->gf_l_from_n(static_cast<gf2m>(1) << k);
198  alpha_l_k_tt2_ttj[1] = sp_field->gf_mul_rrr(alpha_l_k_tt2_ttj[0], alpha_l_k_tt2_ttj[0]);
199  alpha_l_k_tt2_ttj[2] = sp_field->gf_mul_rrr(alpha_l_k_tt2_ttj[1],alpha_l_k_tt2_ttj[1] );
200 
201  alpha_l_k_tt2_ttj[3] = sp_field->gf_mul_rrr(alpha_l_k_tt2_ttj[2], alpha_l_k_tt2_ttj[2]);
202  for(i = 0; i < this->m_outer_summands; i++)
203  {
204  uint32_t j;
205  uint32_t five_i = 5*i;
206  uint32_t Lik_pos = Lik_pos_base + i;
207  this->m_Lik[Lik_pos] = 0;
208  for(j = 0; j <= 3; j++)
209  {
210  gf2m f, x;
211  uint32_t f_ind = five_i + (static_cast<uint32_t>(1) << j);
212  if(f_ind > d)
213  {
214  break;
215  }
216  f = sigma.get_coef( f_ind);
217 
218  x = sp_field->gf_mul_zrz(alpha_l_k_tt2_ttj[j], f);
219  this->m_Lik[Lik_pos] ^= x;
220  }
221  }
222  }
223  }
224 
225 gf2m gf2m_decomp_rootfind_state::calc_Fxj_j_neq_0( const polyn_gf2m & sigma, gf2m j_gray)
226  {
227  //needs the A_{ij} to compute F(x)_j
228  gf2m sum = 0;
229  uint32_t i;
230  std::shared_ptr<GF2m_Field> sp_field = sigma.get_sp_field();
231  const gf2m jl_gray = sp_field->gf_l_from_n(j_gray);
232  gf2m xl_j_tt_5 = sp_field->gf_square_rr(jl_gray);
233  gf2m xl_gray_tt_3 = sp_field->gf_mul_rrr(xl_j_tt_5, jl_gray);
234  xl_j_tt_5 = sp_field->gf_mul_rrr(xl_j_tt_5, xl_gray_tt_3);
235 
236 
237  sum = sp_field->gf_mul_nrr(xl_gray_tt_3, this->m_sigma_3_l);
238  sum &= this->m_sigma_3_neq_0_mask;
239  /* here, we rely on compiler to be unable to optimize
240  * for the state->sigma_3_neq_0_mask value
241  */
242  /* treat i = 0 special: */
243  sum ^= this->m_Aij[0];
244  /* treat i = 1 special also */
245 
246  if(this->m_outer_summands > 1)
247  {
248  gf2m x;
249  x = sp_field->gf_mul_zrz(xl_j_tt_5, this->m_Aij[1]); /* x_j^{5i} A_i^j */
250  sum ^= x;
251  }
252 
253  gf2m xl_j_tt_5i = xl_j_tt_5;
254 
255  for(i = 2; i < this->m_outer_summands; i++)
256  {
257  gf2m x;
258  xl_j_tt_5i = sp_field->gf_mul_rrr(xl_j_tt_5i, xl_j_tt_5);
259  // now x_j_tt_5i lives up to its name
260  x = sp_field->gf_mul_zrz(xl_j_tt_5i, this->m_Aij[i]); /* x_j^{5i} A_i^(j) */
261  sum ^= x;
262  }
263  return sum;
264  }
265 
266 secure_vector<gf2m> gf2m_decomp_rootfind_state::find_roots(const polyn_gf2m & sigma)
267  {
268  const int sigma_degree = sigma.get_degree();
269  BOTAN_ASSERT(sigma_degree > 0, "Valid sigma");
270  secure_vector<gf2m> result(sigma_degree);
271  uint32_t root_pos = 0;
272 
273  this->calc_Ai_zero(sigma);
274  this->calc_LiK(sigma);
275  do
276  {
277  gf2m eval_result;
278  if(this->m_j_gray == 0)
279  {
280  eval_result = sigma.get_coef( 0);
281  }
282  else
283  {
284  eval_result = this->calc_Fxj_j_neq_0(sigma, this->m_j_gray);
285  }
286 
287  if(eval_result == 0)
288  {
289 
290  result[root_pos] = this->m_j_gray;
291  root_pos++;
292 
293  }
294  if(this->m_j + static_cast<uint32_t>(1) == this->get_code_length())
295  {
296  break;
297  }
298  this->calc_next_Aij();
299  }while(1);
300 
301  // side channel / fault attack countermeasure:
302  root_pos = patch_root_array(result.data(), result.size(), root_pos);
303  result.resize(root_pos);
304  return result;
305  }
306 
307 } // end anonymous namespace
308 
310  {
311  gf2m_decomp_rootfind_state state(polyn, code_length);
312  return state.find_roots(polyn);
313  }
314 
315 } // end namespace Botan
secure_vector< gf2m > m_Aij
secure_vector< gf2m > m_Lik
#define BOTAN_ASSERT(expr, assertion_made)
Definition: assert.h:55
gf2m lex_to_gray(gf2m lex)
uint16_t expand_mask_16bit(T tst)
uint16_t gf2m
Definition: gf2m_small_m.h:23
secure_vector< gf2m > find_roots_gf2m_decomp(const polyn_gf2m &polyn, uint32_t code_length)
Definition: alg_id.cpp:13
gf2m m_j
gf2m m_sigma_3_neq_0_mask
gf2m m_j_gray
uint32_t code_length
gf2m m_sigma_3_l
std::vector< T, secure_allocator< T > > secure_vector
Definition: secmem.h:65
uint32_t m_outer_summands