← Back to branch summary

~ubuntu-branches/debian/sid/botan/sid

« back to all changes in this revision

Viewing changes to src/lib/pubkey/mce/gf2m_rootfind_dcmp.cpp

  • Committer: Package Import Robot
  • Author(s): Laszlo Boszormenyi (GCS)
  • Date: 2018-03-01 22:23:25 UTC
  • mfrom: (1.2.2)
  • Revision ID: package-import@ubuntu.com-20180301222325-7p7vc45gu3hta34d
Tags: 2.4.0-2
* Don't remove .doctrees from the manual if it doesn't exist.
* Don't specify parallel to debhelper.

Show diffs side-by-side

added added

removed removed

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