/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 |