Coverage Report

Created: 2022-06-23 06:44

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