diff options
Diffstat (limited to 'src/lib/pubkey/mce/gf2m_rootfind_dcmp.cpp')
| -rw-r--r-- | src/lib/pubkey/mce/gf2m_rootfind_dcmp.cpp | 531 |
1 files changed, 262 insertions, 269 deletions
diff --git a/src/lib/pubkey/mce/gf2m_rootfind_dcmp.cpp b/src/lib/pubkey/mce/gf2m_rootfind_dcmp.cpp index 2d4f06130..d23d05172 100644 --- a/src/lib/pubkey/mce/gf2m_rootfind_dcmp.cpp +++ b/src/lib/pubkey/mce/gf2m_rootfind_dcmp.cpp @@ -6,314 +6,307 @@ * */ -#include <botan/gf2m_rootfind_dcmp.h> -#include <botan/gf2m_small_m.h> +#include <botan/polyn_gf2m.h> #include <botan/internal/bit_ops.h> -#include <botan/code_based_util.h> +#include <botan/internal/code_based_util.h> -namespace Botan -{ +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++) - { +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; -} ; - + } + return res_root_arr_len; + } + +class gf2m_decomp_rootfind_state + { + public: + 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 !! - */ +* !! Attention: assumes gf2m is 16bit !! +*/ #if 0 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; -} + { + static_assert(sizeof(gf2m) == 2, "Expected size"); + gf2m result = gray ^ (gray>>8); + result ^= (result >> 4); + result ^= (result >> 2); + result ^= (result >> 1); + return result; + } #endif /** - * calculates ceil((t-4)/5) = outer_summands - 1 - */ +* 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; -} + { + 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 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_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 ; + } -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); -} + 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; - /* + { + 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; -} + 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(((static_cast<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]; - } + 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(((static_cast<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(static_cast<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++) + { + std::shared_ptr<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++) { - gf2m f, x; - u32bit f_ind = five_i + (static_cast<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; + 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(static_cast<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 + (static_cast<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 + { + //needs the A_{ij} to compute F(x)_j + gf2m sum = 0; + u32bit i; + std::shared_ptr<GF2m_Field> sp_field = sigma.get_sp_field(); + gf2m xl_j_tt_5i, xl_j_tt_5, xl_gray_tt_3; + const gf2m 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; -} - + /* 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.data(), result.size(), root_pos); + result.resize(root_pos); + return result; + } -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.data(), result.size(), root_pos); - result.resize(root_pos); - return result; -} } // end namespace Botan |