Use masked table lookup in ECC base point multiplication

2 files changed, 42 insertions, 9 deletions

diff --git a/src/lib/pubkey/ec_group/point_mul.cpp b/src/lib/pubkey/ec_group/point_mul.cpp
index 0a8f76d58..60e72d3ac 100644
--- a/src/lib/pubkey/ec_group/point_mul.cpp
+++ b/src/lib/pubkey/ec_group/point_mul.cpp
@@ -8,6 +8,7 @@
 #include <botan/rng.h>
 #include <botan/reducer.h>
 #include <botan/internal/rounding.h>
+#include <botan/internal/ct_utils.h>
 
 namespace Botan {
 
@@ -106,7 +107,9 @@ PointGFp PointGFp_Base_Point_Precompute::mul(const BigInt& k,
 
    size_t windows = round_up(scalar.bits(), 2) / 2;
 
-   BOTAN_ASSERT(windows <= m_W.size() / (3*2*m_p_words),
+   const size_t elem_size = 2*m_p_words;
+
+   BOTAN_ASSERT(windows <= m_W.size() / (3*elem_size),
                 "Precomputed sufficient values for scalar mult");
 
    PointGFp R = m_base_point.zero();
@@ -114,24 +117,42 @@ PointGFp PointGFp_Base_Point_Precompute::mul(const BigInt& k,
    if(ws.size() < PointGFp::WORKSPACE_SIZE)
       ws.resize(PointGFp::WORKSPACE_SIZE);
 
+   // the precomputed multiples are not secret so use std::vector
+   std::vector<word> Wt(elem_size);
+
    for(size_t i = 0; i != windows; ++i)
       {
-      if(i == 4)
+      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 uint32_t w = scalar.get_substring(2*i, 2);
+      const word w = scalar.get_substring(2*i, 2);
 
-      // side channel here, we are relying on scalar blinding
-      // TODO use masked lookup
+      const word w_is_1 = CT::is_equal<word>(w, 1);
+      const word w_is_2 = CT::is_equal<word>(w, 2);
+      const word w_is_3 = CT::is_equal<word>(w, 3);
 
-      if(w > 0)
+      for(size_t j = 0; j != elem_size; ++j)
          {
-         const size_t idx = (3*i + w - 1)*2*m_p_words;
-         R.add_affine(&m_W[idx], m_p_words,
-                      &m_W[idx + m_p_words], m_p_words, ws);
+         const word w1 = m_W[base_addr + 0*elem_size + j];
+         const word w2 = m_W[base_addr + 1*elem_size + j];
+         const word w3 = m_W[base_addr + 2*elem_size + j];
+
+         Wt[j] = CT::select3<word>(w_is_1, w1, w_is_2, w2, w_is_3, w3, 0);
          }
+
+      R.add_affine(&Wt[0], m_p_words, &Wt[m_p_words], m_p_words, ws);
       }
 
    BOTAN_DEBUG_ASSERT(R.on_the_curve());
diff --git a/src/lib/utils/ct_utils.h b/src/lib/utils/ct_utils.h
index f67fb8f10..013267874 100644
--- a/src/lib/utils/ct_utils.h
+++ b/src/lib/utils/ct_utils.h
@@ -108,6 +108,18 @@ inline T select(T mask, T from0, T from1)
    return static_cast<T>((from0 & mask) | (from1 & ~mask));
    }
 
+template<typename T>
+inline T select2(T mask0, T val0, T mask1, T val1, T val2)
+   {
+   return select<T>(mask0, val0, select<T>(mask1, val1, val2));
+   }
+
+template<typename T>
+inline T select3(T mask0, T val0, T mask1, T val1, T mask2, T val2, T val3)
+   {
+   return select2<T>(mask0, val0, mask1, val1, select<T>(mask2, val2, val3));
+   }
+
 template<typename PredT, typename ValT>
 inline ValT val_or_zero(PredT pred_val, ValT val)
    {