Botan 2.1.0 Crypto and TLS for C++11

- Main Page
- Namespaces
- Classes
- Files

- File List
- File Members

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 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
m_Aij
secure_vector< gf2m > m_Aij
Definition: gf2m_rootfind_dcmp.cpp:50
m_Lik
secure_vector< gf2m > m_Lik
Definition: gf2m_rootfind_dcmp.cpp:49
BOTAN_ASSERT
#define BOTAN_ASSERT(expr, assertion_made)
Definition: assert.h:27
Botan::secure_vector
std::vector< T, secure_allocator< T >> secure_vector
Definition: secmem.h:121
Botan::lex_to_gray
gf2m lex_to_gray(gf2m lex)
Definition: code_based_util.h:40
Botan::expand_mask_16bit
uint16_t expand_mask_16bit(T tst)
Definition: code_based_util.h:25
Botan::gf2m
uint16_t gf2m
Definition: gf2m_small_m.h:20
Botan::find_roots_gf2m_decomp
secure_vector< gf2m > find_roots_gf2m_decomp(const polyn_gf2m &polyn, uint32_t code_length)
Definition: gf2m_rootfind_dcmp.cpp:311
Botan
Definition: alg_id.cpp:13
m_j
gf2m m_j
Definition: gf2m_rootfind_dcmp.cpp:52
Botan::polyn_gf2m
Definition: polyn_gf2m.h:24
m_sigma_3_neq_0_mask
gf2m m_sigma_3_neq_0_mask
Definition: gf2m_rootfind_dcmp.cpp:55
m_j_gray
gf2m m_j_gray
Definition: gf2m_rootfind_dcmp.cpp:53
code_length
uint32_t code_length
Definition: gf2m_rootfind_dcmp.cpp:48
m_sigma_3_l
gf2m m_sigma_3_l
Definition: gf2m_rootfind_dcmp.cpp:54
m_outer_summands
uint32_t m_outer_summands
Definition: gf2m_rootfind_dcmp.cpp:51