From 1d0eb1afd390b3b7e2719f6d80e9964a618a26b8 Mon Sep 17 00:00:00 2001 From: Jack Lloyd Date: Wed, 20 Jun 2018 15:30:55 -0400 Subject: Perform ECC mult starting from top bit of the exponent Since we know the top bit is 1, then R will always be a point other than point at infinity after the very first addition regardless of the scalar or mask, so then coordinate randomization is guaranteed to work. --- src/lib/pubkey/ec_group/point_mul.cpp | 33 ++++++++++++++++----------------- 1 file changed, 16 insertions(+), 17 deletions(-) (limited to 'src/lib') diff --git a/src/lib/pubkey/ec_group/point_mul.cpp b/src/lib/pubkey/ec_group/point_mul.cpp index 60e72d3ac..f393c2ea4 100644 --- a/src/lib/pubkey/ec_group/point_mul.cpp +++ b/src/lib/pubkey/ec_group/point_mul.cpp @@ -100,12 +100,12 @@ PointGFp PointGFp_Base_Point_Precompute::mul(const BigInt& k, throw Invalid_Argument("PointGFp_Base_Point_Precompute scalar must be positive"); // Choose a small mask m and use k' = k + m*order (Coron's 1st countermeasure) - const BigInt mask(rng, PointGFp_SCALAR_BLINDING_BITS, false); + const BigInt mask(rng, PointGFp_SCALAR_BLINDING_BITS); // Instead of reducing k mod group order should we alter the mask size?? const BigInt scalar = m_mod_order.reduce(k) + group_order * mask; - size_t windows = round_up(scalar.bits(), 2) / 2; + const size_t windows = round_up(scalar.bits(), 2) / 2; const size_t elem_size = 2*m_p_words; @@ -122,22 +122,10 @@ PointGFp PointGFp_Base_Point_Precompute::mul(const BigInt& k, for(size_t i = 0; i != windows; ++i) { - const size_t base_addr = (3*i)*elem_size; - - if(i == 5) - { - /* - * There is a small (1/1024) chance that the bottom 10 bits of the - * (randomized) scalar are all zero, in which case R is zero and so this - * randomization is ineffective. Instead we could randomize after the - * first non-zero exponent bits are processed, but that unfortunately - * introduces a side channel on the exponent, albeit likely not - * exploitable. - */ - R.randomize_repr(rng, ws[0].get_word_vector()); - } + const size_t window = windows - i - 1; + const size_t base_addr = (3*window)*elem_size; - const word w = scalar.get_substring(2*i, 2); + const word w = scalar.get_substring(2*window, 2); const word w_is_1 = CT::is_equal(w, 1); const word w_is_2 = CT::is_equal(w, 2); @@ -153,6 +141,17 @@ PointGFp PointGFp_Base_Point_Precompute::mul(const BigInt& k, } R.add_affine(&Wt[0], m_p_words, &Wt[m_p_words], m_p_words, ws); + + if(i == 0) + { + /* + * Since we start with the top bit of the exponent we know the + * first window must have a non-zero element, and thus R is + * now a point other than the point at infinity. + */ + BOTAN_DEBUG_ASSERT(w != 0); + R.randomize_repr(rng, ws[0].get_word_vector()); + } } BOTAN_DEBUG_ASSERT(R.on_the_curve()); -- cgit v1.2.3