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