1 files changed, 317 insertions, 0 deletions
diff --git a/src/lib/pubkey/mce/gf2m_rootfind_dcmp.cpp b/src/lib/pubkey/mce/gf2m_rootfind_dcmp.cpp
new file mode 100644
index 000000000..f6ff8e498
--- /dev/null
+++ b/src/lib/pubkey/mce/gf2m_rootfind_dcmp.cpp
@@ -0,0 +1,317 @@
+/**
+ * (C) 2014 cryptosource GmbH
+ * (C) 2014 Falko Strenzke [email protected]
+ *
+ * Distributed under the terms of the Botan license
+ *
+ */
+
+#include <botan/gf2m_rootfind_dcmp.h>
+#include <botan/gf2m_small_m.h>
+#include <botan/internal/bit_ops.h>
+#include <botan/code_based_util.h>
+
+namespace Botan
+{
+
+namespace {
+
+  u32bit patch_root_array(
+    gf2m* res_root_arr,
+    u32bit res_root_arr_len,
+    u32bit root_pos)
+  {
+    volatile u32bit i;
+    volatile gf2m patch_elem = 0x01;
+    volatile gf2m cond_mask = (root_pos == res_root_arr_len);
+    cond_mask = expand_mask_16bit(cond_mask);
+    cond_mask = ~cond_mask; /* now cond = 1 if not enough roots */
+    patch_elem &= cond_mask;
+    for(i = 0; i < res_root_arr_len; i++)
+    {
+
+      gf2m masked_patch_elem = (patch_elem++) & cond_mask;
+      res_root_arr[i] ^= masked_patch_elem++;
+    }
+    return res_root_arr_len;
+  }
+
+struct gf2m_decomp_rootfind_state
+{
+    gf2m_decomp_rootfind_state(const polyn_gf2m & p_polyn, u32bit code_length);
+
+  void calc_LiK(const polyn_gf2m & sigma);
+  gf2m calc_Fxj_j_neq_0( const polyn_gf2m & sigma, gf2m j_gray);
+  void calc_next_Aij();
+  void calc_Ai_zero(const polyn_gf2m & sigma);
+  secure_vector<gf2m> find_roots(const polyn_gf2m & sigma);
+   u32bit get_code_length() const { return code_length; };
+    u32bit code_length;
+  secure_vector<gf2m> m_Lik; // size is outer_summands * m
+  secure_vector<gf2m> m_Aij; // ...
+  u32bit m_outer_summands;
+  gf2m m_j;
+  gf2m m_j_gray;
+  gf2m m_sigma_3_l;
+  gf2m m_sigma_3_neq_0_mask;
+} ;
+
+
+/*
+ * !! Attention: assumes gf2m is 16bit !!
+ */
+gf2m brootf_decomp__gray_to_lex(gf2m gray)
+{
+  static_assert(sizeof(gf2m) == 2, "Expected size");
+  gf2m result = gray ^ (gray>>8);
+  result ^= (result >> 4);
+  result ^= (result >> 2);
+  result ^= (result >> 1);
+  return result;
+}
+
+/**
+ * calculates ceil((t-4)/5) = outer_summands - 1
+ */
+u32bit brootf_decomp__calc_sum_limit(u32bit t)
+{
+  u32bit result;
+  if(t < 4)
+  {
+    return 0;
+  }
+  result = t - 4;
+  result += 4;
+  result /= 5;
+  return result;
+}
+}
+
+secure_vector<gf2m> find_roots_gf2m_decomp(const polyn_gf2m & polyn, u32bit code_length)
+{
+  gf2m_decomp_rootfind_state state(polyn, code_length);
+  return state.find_roots(polyn);
+
+}
+
+gf2m_decomp_rootfind_state::gf2m_decomp_rootfind_state(const polyn_gf2m & polyn, u32bit the_code_length)
+  :code_length(the_code_length)
+{
+
+  gf2m coeff_3;
+  gf2m coeff_head;
+  std::shared_ptr<gf2m_small_m::Gf2m_Field> sp_field = polyn.get_sp_field();
+  int deg_sigma = polyn.get_degree();
+  if(deg_sigma <= 3)
+  {
+    throw std::exception();
+  }
+  this->m_j = 0;
+  coeff_3 = polyn.get_coef( 3);
+  coeff_head = polyn.get_coef( deg_sigma); /* dummy value for SCA CM */
+  if(coeff_3 != 0)
+  {
+    this->m_sigma_3_l = sp_field->gf_l_from_n(coeff_3);
+    this->m_sigma_3_neq_0_mask = 0xFFFF;
+  }
+  else
+  {
+    // dummy value needed for timing countermeasure
+    this->m_sigma_3_l = sp_field->gf_l_from_n(coeff_head);
+    this->m_sigma_3_neq_0_mask = 0 ;
+  }
+
+  this->m_outer_summands =  1 + brootf_decomp__calc_sum_limit(deg_sigma);
+  this->m_Lik.resize(this->m_outer_summands * sp_field->get_extension_degree());
+  this->m_Aij.resize(this->m_outer_summands);
+}
+
+void gf2m_decomp_rootfind_state::calc_Ai_zero(const polyn_gf2m & sigma)
+{
+  u32bit i;
+  /*
+   * this function assumes this the first gray code element is zero
+   */
+  for(i = 0; i < this->m_outer_summands; i++)
+  {
+    this->m_Aij[i] = sigma.get_coef(5*i);
+  }
+  this->m_j = 0;
+  this->m_j_gray = 0;
+}
+
+void gf2m_decomp_rootfind_state::calc_next_Aij()
+{
+  /*
+   * upon function entry, we have in the state j, Aij.
+   * first thing, we declare Aij Aij_minusone and increase j.
+   * Case j=0 upon function entry also included, then Aij contains A_{i,j=0}.
+   */
+  u32bit i;
+  gf2m diff, new_j_gray;
+  u32bit Lik_pos_base;
+
+  this->m_j++;
+
+  new_j_gray =  lex_to_gray(this->m_j);
+
+  if(this->m_j & 1)  /* half of the times */
+  {
+    Lik_pos_base = 0;
+  }
+  else if(this->m_j & 2) /* one quarter of the times */
+  {
+    Lik_pos_base = this->m_outer_summands;
+  }
+  else if( this->m_j & 4) /* one eighth of the times */
+  {
+    Lik_pos_base = this->m_outer_summands * 2;
+  }
+  else if( this->m_j & 8) /* one sixteenth of the times */
+  {
+    Lik_pos_base = this->m_outer_summands * 3;
+  }
+  else if( this->m_j & 16) /* ... */
+  {
+    Lik_pos_base = this->m_outer_summands * 4;
+  }
+  else
+  {
+    gf2m delta_offs = 5;
+    diff = this->m_j_gray ^ new_j_gray;
+    while(((((gf2m)1) << delta_offs) & diff) == 0)
+    {
+      delta_offs++;
+
+    }
+    Lik_pos_base = delta_offs * this->m_outer_summands;
+  }
+  this->m_j_gray = new_j_gray;
+
+  i = 0;
+  for(; i < this->m_outer_summands; i++)
+  {
+    this->m_Aij[i] ^= this->m_Lik[Lik_pos_base + i];
+  }
+
+}
+void gf2m_decomp_rootfind_state::calc_LiK(const polyn_gf2m & sigma)
+{
+  std::shared_ptr<gf2m_small_m::Gf2m_Field> sp_field = sigma.get_sp_field();
+  u32bit i, k, d;
+  d = sigma.get_degree();
+  for(k = 0; k < sp_field->get_extension_degree(); k++)
+  {
+    u32bit Lik_pos_base = k * this->m_outer_summands;
+    gf2m alpha_l_k_tt2_ttj[4];
+    alpha_l_k_tt2_ttj[0] = sp_field->gf_l_from_n( ((gf2m)1) << k);
+    alpha_l_k_tt2_ttj[1] = sp_field->gf_mul_rrr(alpha_l_k_tt2_ttj[0], alpha_l_k_tt2_ttj[0]);
+    alpha_l_k_tt2_ttj[2] = sp_field->gf_mul_rrr(alpha_l_k_tt2_ttj[1],alpha_l_k_tt2_ttj[1] );
+
+    alpha_l_k_tt2_ttj[3] = sp_field->gf_mul_rrr(alpha_l_k_tt2_ttj[2], alpha_l_k_tt2_ttj[2]);
+    for(i = 0; i < this->m_outer_summands; i++)
+    {
+      u32bit j;
+      u32bit five_i = 5*i;
+      u32bit Lik_pos = Lik_pos_base + i;
+      this->m_Lik[Lik_pos] = 0;
+      for(j = 0; j <= 3; j++)
+      {
+        gf2m f, x;
+        u32bit f_ind = five_i + ((u32bit)1<<j);
+        if(f_ind > d)
+        {
+          break;
+        }
+        f = sigma.get_coef( f_ind);
+
+        x = sp_field->gf_mul_zrz(alpha_l_k_tt2_ttj[j], f);
+        this->m_Lik[Lik_pos] ^= x;
+      }
+    }
+  }
+}
+
+gf2m gf2m_decomp_rootfind_state::calc_Fxj_j_neq_0( const polyn_gf2m & sigma, gf2m j_gray)
+{
+  //needs the A_{ij} to compute F(x)_j
+  gf2m sum = 0;
+  u32bit i;
+  std::shared_ptr<gf2m_small_m::Gf2m_Field> sp_field = sigma.get_sp_field();
+  gf2m xl_j_tt_5i, xl_j_tt_5,  xl_gray_tt_3;
+  gf2m jl_gray;
+  jl_gray = sp_field->gf_l_from_n(j_gray);
+  xl_j_tt_5 = sp_field->gf_square_rr(jl_gray);
+  xl_gray_tt_3 = sp_field->gf_mul_rrr(xl_j_tt_5, jl_gray);
+  xl_j_tt_5 = sp_field->gf_mul_rrr(xl_j_tt_5, xl_gray_tt_3);
+
+
+  sum = sp_field->gf_mul_nrr(xl_gray_tt_3, this->m_sigma_3_l);
+  sum &= this->m_sigma_3_neq_0_mask;
+  /* here, we rely on compiler to be unable to optimize
+   * for the state->sigma_3_neq_0_mask value
+   */
+  /* treat i = 0 special: */
+  sum ^= this->m_Aij[0];
+  /* treat i = 1 special also */
+  if(this->m_outer_summands > 1)
+  {
+    gf2m x;
+    xl_j_tt_5i = xl_j_tt_5;
+    x = sp_field->gf_mul_zrz(xl_j_tt_5, this->m_Aij[1]); /* x_j^{5i} A_i^j */
+    sum ^= x;
+  }
+  for(i = 2; i < this->m_outer_summands; i++)
+  {
+    gf2m x;
+    xl_j_tt_5i = sp_field->gf_mul_rrr(xl_j_tt_5i, xl_j_tt_5);
+    // now x_j_tt_5i lives up to its name
+    x = sp_field->gf_mul_zrz(xl_j_tt_5i, this->m_Aij[i]); /* x_j^{5i} A_i^(j) */
+    sum ^= x;
+  }
+  return sum;
+}
+
+
+
+
+secure_vector<gf2m> gf2m_decomp_rootfind_state::find_roots(const polyn_gf2m & sigma)
+{
+
+  secure_vector<gf2m> result(sigma.get_degree());
+  u32bit root_pos = 0;
+
+  this->calc_Ai_zero(sigma);
+  this->calc_LiK(sigma);
+  do
+  {
+    gf2m eval_result;
+    if(this->m_j_gray == 0)
+    {
+      eval_result = sigma.get_coef( 0);
+    }
+    else
+    {
+      eval_result = this->calc_Fxj_j_neq_0(sigma, this->m_j_gray);
+    }
+
+    if(eval_result == 0)
+    {
+
+      result[root_pos] = this->m_j_gray;
+      root_pos++;
+
+    }
+    if(this->m_j + static_cast<u32bit>(1) == this->get_code_length())
+    {
+      break;
+    }
+    this->calc_next_Aij();
+  }while(1);
+
+  // side channel / fault attack countermeasure:
+  root_pos = patch_root_array(&result[0], result.size(), root_pos);
+  result.resize(root_pos);
+ return result;
+}
+} // end namespace Botan