Botan
1.11.15
|
00001 /** 00002 * (C) 2014 cryptosource GmbH 00003 * (C) 2014 Falko Strenzke fstrenzke@cryptosource.de 00004 * 00005 * Botan is released under the Simplified BSD License (see license.txt) 00006 * 00007 */ 00008 00009 #include <botan/gf2m_rootfind_dcmp.h> 00010 #include <botan/gf2m_small_m.h> 00011 #include <botan/internal/bit_ops.h> 00012 #include <botan/code_based_util.h> 00013 00014 namespace Botan 00015 { 00016 00017 namespace { 00018 00019 u32bit patch_root_array( 00020 gf2m* res_root_arr, 00021 u32bit res_root_arr_len, 00022 u32bit root_pos) 00023 { 00024 volatile u32bit i; 00025 volatile gf2m patch_elem = 0x01; 00026 volatile gf2m cond_mask = (root_pos == res_root_arr_len); 00027 cond_mask = expand_mask_16bit(cond_mask); 00028 cond_mask = ~cond_mask; /* now cond = 1 if not enough roots */ 00029 patch_elem &= cond_mask; 00030 for(i = 0; i < res_root_arr_len; i++) 00031 { 00032 00033 gf2m masked_patch_elem = (patch_elem++) & cond_mask; 00034 res_root_arr[i] ^= masked_patch_elem++; 00035 } 00036 return res_root_arr_len; 00037 } 00038 00039 struct gf2m_decomp_rootfind_state 00040 { 00041 gf2m_decomp_rootfind_state(const polyn_gf2m & p_polyn, u32bit code_length); 00042 00043 void calc_LiK(const polyn_gf2m & sigma); 00044 gf2m calc_Fxj_j_neq_0( const polyn_gf2m & sigma, gf2m j_gray); 00045 void calc_next_Aij(); 00046 void calc_Ai_zero(const polyn_gf2m & sigma); 00047 secure_vector<gf2m> find_roots(const polyn_gf2m & sigma); 00048 u32bit get_code_length() const { return code_length; }; 00049 u32bit code_length; 00050 secure_vector<gf2m> m_Lik; // size is outer_summands * m 00051 secure_vector<gf2m> m_Aij; // ... 00052 u32bit m_outer_summands; 00053 gf2m m_j; 00054 gf2m m_j_gray; 00055 gf2m m_sigma_3_l; 00056 gf2m m_sigma_3_neq_0_mask; 00057 } ; 00058 00059 00060 /* 00061 * !! Attention: assumes gf2m is 16bit !! 00062 */ 00063 #if 0 00064 gf2m brootf_decomp__gray_to_lex(gf2m gray) 00065 { 00066 static_assert(sizeof(gf2m) == 2, "Expected size"); 00067 gf2m result = gray ^ (gray>>8); 00068 result ^= (result >> 4); 00069 result ^= (result >> 2); 00070 result ^= (result >> 1); 00071 return result; 00072 } 00073 #endif 00074 00075 /** 00076 * calculates ceil((t-4)/5) = outer_summands - 1 00077 */ 00078 u32bit brootf_decomp__calc_sum_limit(u32bit t) 00079 { 00080 u32bit result; 00081 if(t < 4) 00082 { 00083 return 0; 00084 } 00085 result = t - 4; 00086 result += 4; 00087 result /= 5; 00088 return result; 00089 } 00090 } 00091 00092 secure_vector<gf2m> find_roots_gf2m_decomp(const polyn_gf2m & polyn, u32bit code_length) 00093 { 00094 gf2m_decomp_rootfind_state state(polyn, code_length); 00095 return state.find_roots(polyn); 00096 00097 } 00098 00099 gf2m_decomp_rootfind_state::gf2m_decomp_rootfind_state(const polyn_gf2m & polyn, u32bit the_code_length) 00100 :code_length(the_code_length) 00101 { 00102 00103 gf2m coeff_3; 00104 gf2m coeff_head; 00105 std::shared_ptr<gf2m_small_m::Gf2m_Field> sp_field = polyn.get_sp_field(); 00106 int deg_sigma = polyn.get_degree(); 00107 if(deg_sigma <= 3) 00108 { 00109 throw std::exception(); 00110 } 00111 this->m_j = 0; 00112 coeff_3 = polyn.get_coef( 3); 00113 coeff_head = polyn.get_coef( deg_sigma); /* dummy value for SCA CM */ 00114 if(coeff_3 != 0) 00115 { 00116 this->m_sigma_3_l = sp_field->gf_l_from_n(coeff_3); 00117 this->m_sigma_3_neq_0_mask = 0xFFFF; 00118 } 00119 else 00120 { 00121 // dummy value needed for timing countermeasure 00122 this->m_sigma_3_l = sp_field->gf_l_from_n(coeff_head); 00123 this->m_sigma_3_neq_0_mask = 0 ; 00124 } 00125 00126 this->m_outer_summands = 1 + brootf_decomp__calc_sum_limit(deg_sigma); 00127 this->m_Lik.resize(this->m_outer_summands * sp_field->get_extension_degree()); 00128 this->m_Aij.resize(this->m_outer_summands); 00129 } 00130 00131 void gf2m_decomp_rootfind_state::calc_Ai_zero(const polyn_gf2m & sigma) 00132 { 00133 u32bit i; 00134 /* 00135 * this function assumes this the first gray code element is zero 00136 */ 00137 for(i = 0; i < this->m_outer_summands; i++) 00138 { 00139 this->m_Aij[i] = sigma.get_coef(5*i); 00140 } 00141 this->m_j = 0; 00142 this->m_j_gray = 0; 00143 } 00144 00145 void gf2m_decomp_rootfind_state::calc_next_Aij() 00146 { 00147 /* 00148 * upon function entry, we have in the state j, Aij. 00149 * first thing, we declare Aij Aij_minusone and increase j. 00150 * Case j=0 upon function entry also included, then Aij contains A_{i,j=0}. 00151 */ 00152 u32bit i; 00153 gf2m diff, new_j_gray; 00154 u32bit Lik_pos_base; 00155 00156 this->m_j++; 00157 00158 new_j_gray = lex_to_gray(this->m_j); 00159 00160 if(this->m_j & 1) /* half of the times */ 00161 { 00162 Lik_pos_base = 0; 00163 } 00164 else if(this->m_j & 2) /* one quarter of the times */ 00165 { 00166 Lik_pos_base = this->m_outer_summands; 00167 } 00168 else if( this->m_j & 4) /* one eighth of the times */ 00169 { 00170 Lik_pos_base = this->m_outer_summands * 2; 00171 } 00172 else if( this->m_j & 8) /* one sixteenth of the times */ 00173 { 00174 Lik_pos_base = this->m_outer_summands * 3; 00175 } 00176 else if( this->m_j & 16) /* ... */ 00177 { 00178 Lik_pos_base = this->m_outer_summands * 4; 00179 } 00180 else 00181 { 00182 gf2m delta_offs = 5; 00183 diff = this->m_j_gray ^ new_j_gray; 00184 while(((static_cast<gf2m>(1) << delta_offs) & diff) == 0) 00185 { 00186 delta_offs++; 00187 00188 } 00189 Lik_pos_base = delta_offs * this->m_outer_summands; 00190 } 00191 this->m_j_gray = new_j_gray; 00192 00193 i = 0; 00194 for(; i < this->m_outer_summands; i++) 00195 { 00196 this->m_Aij[i] ^= this->m_Lik[Lik_pos_base + i]; 00197 } 00198 00199 } 00200 void gf2m_decomp_rootfind_state::calc_LiK(const polyn_gf2m & sigma) 00201 { 00202 std::shared_ptr<gf2m_small_m::Gf2m_Field> sp_field = sigma.get_sp_field(); 00203 u32bit i, k, d; 00204 d = sigma.get_degree(); 00205 for(k = 0; k < sp_field->get_extension_degree(); k++) 00206 { 00207 u32bit Lik_pos_base = k * this->m_outer_summands; 00208 gf2m alpha_l_k_tt2_ttj[4]; 00209 alpha_l_k_tt2_ttj[0] = sp_field->gf_l_from_n(static_cast<gf2m>(1) << k); 00210 alpha_l_k_tt2_ttj[1] = sp_field->gf_mul_rrr(alpha_l_k_tt2_ttj[0], alpha_l_k_tt2_ttj[0]); 00211 alpha_l_k_tt2_ttj[2] = sp_field->gf_mul_rrr(alpha_l_k_tt2_ttj[1],alpha_l_k_tt2_ttj[1] ); 00212 00213 alpha_l_k_tt2_ttj[3] = sp_field->gf_mul_rrr(alpha_l_k_tt2_ttj[2], alpha_l_k_tt2_ttj[2]); 00214 for(i = 0; i < this->m_outer_summands; i++) 00215 { 00216 u32bit j; 00217 u32bit five_i = 5*i; 00218 u32bit Lik_pos = Lik_pos_base + i; 00219 this->m_Lik[Lik_pos] = 0; 00220 for(j = 0; j <= 3; j++) 00221 { 00222 gf2m f, x; 00223 u32bit f_ind = five_i + (static_cast<u32bit>(1) << j); 00224 if(f_ind > d) 00225 { 00226 break; 00227 } 00228 f = sigma.get_coef( f_ind); 00229 00230 x = sp_field->gf_mul_zrz(alpha_l_k_tt2_ttj[j], f); 00231 this->m_Lik[Lik_pos] ^= x; 00232 } 00233 } 00234 } 00235 } 00236 00237 gf2m gf2m_decomp_rootfind_state::calc_Fxj_j_neq_0( const polyn_gf2m & sigma, gf2m j_gray) 00238 { 00239 //needs the A_{ij} to compute F(x)_j 00240 gf2m sum = 0; 00241 u32bit i; 00242 std::shared_ptr<gf2m_small_m::Gf2m_Field> sp_field = sigma.get_sp_field(); 00243 gf2m xl_j_tt_5i, xl_j_tt_5, xl_gray_tt_3; 00244 gf2m jl_gray; 00245 jl_gray = sp_field->gf_l_from_n(j_gray); 00246 xl_j_tt_5 = sp_field->gf_square_rr(jl_gray); 00247 xl_gray_tt_3 = sp_field->gf_mul_rrr(xl_j_tt_5, jl_gray); 00248 xl_j_tt_5 = sp_field->gf_mul_rrr(xl_j_tt_5, xl_gray_tt_3); 00249 00250 00251 sum = sp_field->gf_mul_nrr(xl_gray_tt_3, this->m_sigma_3_l); 00252 sum &= this->m_sigma_3_neq_0_mask; 00253 /* here, we rely on compiler to be unable to optimize 00254 * for the state->sigma_3_neq_0_mask value 00255 */ 00256 /* treat i = 0 special: */ 00257 sum ^= this->m_Aij[0]; 00258 /* treat i = 1 special also */ 00259 if(this->m_outer_summands > 1) 00260 { 00261 gf2m x; 00262 xl_j_tt_5i = xl_j_tt_5; 00263 x = sp_field->gf_mul_zrz(xl_j_tt_5, this->m_Aij[1]); /* x_j^{5i} A_i^j */ 00264 sum ^= x; 00265 } 00266 for(i = 2; i < this->m_outer_summands; i++) 00267 { 00268 gf2m x; 00269 xl_j_tt_5i = sp_field->gf_mul_rrr(xl_j_tt_5i, xl_j_tt_5); 00270 // now x_j_tt_5i lives up to its name 00271 x = sp_field->gf_mul_zrz(xl_j_tt_5i, this->m_Aij[i]); /* x_j^{5i} A_i^(j) */ 00272 sum ^= x; 00273 } 00274 return sum; 00275 } 00276 00277 00278 00279 00280 secure_vector<gf2m> gf2m_decomp_rootfind_state::find_roots(const polyn_gf2m & sigma) 00281 { 00282 00283 secure_vector<gf2m> result(sigma.get_degree()); 00284 u32bit root_pos = 0; 00285 00286 this->calc_Ai_zero(sigma); 00287 this->calc_LiK(sigma); 00288 do 00289 { 00290 gf2m eval_result; 00291 if(this->m_j_gray == 0) 00292 { 00293 eval_result = sigma.get_coef( 0); 00294 } 00295 else 00296 { 00297 eval_result = this->calc_Fxj_j_neq_0(sigma, this->m_j_gray); 00298 } 00299 00300 if(eval_result == 0) 00301 { 00302 00303 result[root_pos] = this->m_j_gray; 00304 root_pos++; 00305 00306 } 00307 if(this->m_j + static_cast<u32bit>(1) == this->get_code_length()) 00308 { 00309 break; 00310 } 00311 this->calc_next_Aij(); 00312 }while(1); 00313 00314 // side channel / fault attack countermeasure: 00315 root_pos = patch_root_array(&result[0], result.size(), root_pos); 00316 result.resize(root_pos); 00317 return result; 00318 } 00319 } // end namespace Botan