Botan 2.19.3
Crypto and TLS for C&
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
14namespace Botan {
15
16namespace {
17
18void patch_root_array(gf2m res_root_arr[],
19 size_t res_root_arr_len,
20 size_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 }
33
34class gf2m_decomp_rootfind_state
35 {
36 public:
37 gf2m_decomp_rootfind_state(const polyn_gf2m & p_polyn, size_t code_length);
38
39 void calc_LiK(const polyn_gf2m & sigma);
40 gf2m calc_Fxj_j_neq_0( const polyn_gf2m & sigma, gf2m j_gray);
41 void calc_next_Aij();
42 void calc_Ai_zero(const polyn_gf2m & sigma);
43 secure_vector<gf2m> find_roots(const polyn_gf2m & sigma);
44
45 private:
46 size_t m_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;
50 gf2m m_j;
51 gf2m m_j_gray;
52 gf2m m_sigma_3_l;
53 gf2m m_sigma_3_neq_0_mask;
54 };
55
56/*
57* !! Attention: assumes gf2m is 16bit !!
58*/
59#if 0
60gf2m 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*/
74uint32_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
87gf2m_decomp_rootfind_state::gf2m_decomp_rootfind_state(const polyn_gf2m & polyn, size_t code_length) :
88 m_code_length(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
118void 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
132void 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
188void 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
225gf2m 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
266secure_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 for(;;)
276 {
277 gf2m eval_result;
278
279 if(this->m_j_gray == 0)
280 {
281 eval_result = sigma.get_coef(0);
282 }
283 else
284 {
285 eval_result = this->calc_Fxj_j_neq_0(sigma, this->m_j_gray);
286 }
287
288 if(eval_result == 0)
289 {
290 result[root_pos] = this->m_j_gray;
291 root_pos++;
292 }
293
294 if(this->m_j + static_cast<uint32_t>(1) == m_code_length)
295 {
296 break;
297 }
298 this->calc_next_Aij();
299 }
300
301 // side channel / fault attack countermeasure:
302 patch_root_array(result.data(), result.size(), root_pos);
303 return result;
304 }
305
306} // end anonymous namespace
307
308secure_vector<gf2m> find_roots_gf2m_decomp(const polyn_gf2m & polyn, size_t code_length)
309 {
310 gf2m_decomp_rootfind_state state(polyn, code_length);
311 return state.find_roots(polyn);
312 }
313
314} // end namespace Botan
#define BOTAN_ASSERT(expr, assertion_made)
Definition assert.h:55
gf2m lex_to_gray(gf2m lex)
uint16_t expand_mask_16bit(T tst)
secure_vector< gf2m > find_roots_gf2m_decomp(const polyn_gf2m &polyn, size_t code_length)
std::vector< T, secure_allocator< T > > secure_vector
Definition secmem.h:65
uint16_t gf2m