Botan  1.11.15
src/lib/pubkey/mce/gf2m_rootfind_dcmp.cpp
Go to the documentation of this file.
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