Make Karatsuba multiply completely const time

5 files changed, 62 insertions, 36 deletions

diff --git a/doc/manual/side_channels.rst b/doc/manual/side_channels.rst
index cf5f26003..8cb5b1188 100644
--- a/doc/manual/side_channels.rst
+++ b/doc/manual/side_channels.rst
@@ -1,9 +1,9 @@
 Side Channels
 =========================
 
-Many cryptographic systems can be broken by side channels. This document notes
-side channel protections which are currently implemented, as well as areas of
-the code which are known to be vulnerable to side channels. The latter are
+Many cryptographic systems can be easily broken by side channels. This document
+notes side channel protections which are currently implemented, as well as areas
+of the code which are known to be vulnerable to side channels. The latter are
 obviously all open for future improvement.
 
 The following text assumes the reader is already familiar with cryptographic
@@ -20,7 +20,7 @@ inverse with each decryption, both the mask and its inverse are simply squared
 to choose the next blinding factor. This is much faster than computing a fresh
 value each time, and the additional relation is thought to provide only minimal
 useful information for an attacker. Every BOTAN_BLINDING_REINIT_INTERVAL
-(default 32) operations, a new starting point is chosen.
+(default 64) operations, a new starting point is chosen.
 
 Exponent blinding uses new values for each signature.
 
@@ -110,16 +110,14 @@ Modular Exponentiation
 
 Modular exponentiation uses a fixed window algorithm with Montgomery
 representation. A side channel silent table lookup is used to access the
-precomputed powers. See powm_mnt.cpp.
+precomputed powers. See monty_exp.cpp
 
-The Karatsuba multiplication algorithm has some conditional branches that
-probably expose information through the branch predictor, but probably? does not
-expose a timing channel since the same amount of work is done on both sides of
-the conditional. There is certainly room for improvement here. See mp_karat.cpp
-for details.
+Karatsuba multiplication algorithm avoids any conditional branches; in
+cases where different operations must be performed it instead uses masked
+operations. See mp_karat.cpp for details.
 
-The Montgomery reduction is written (and tested) to run in constant time. See
-mp_monty.cpp.
+The Montgomery reduction is written (and tested) to run in constant time.
+The final reduction is handled with a masked subtraction. See mp_monty.cpp.
 
 ECC point decoding
 ----------------------
diff --git a/src/lib/math/mp/mp_core.cpp b/src/lib/math/mp/mp_core.cpp
index b1add33a4..9f2999929 100644
--- a/src/lib/math/mp/mp_core.cpp
+++ b/src/lib/math/mp/mp_core.cpp
@@ -211,18 +211,35 @@ void bigint_sub2_rev(word x[],  const word y[], size_t y_size)
    BOTAN_ASSERT(!borrow, "y must be greater than x");
    }
 
-int32_t bigint_sub_abs(word z[], const word x[], const word y[], size_t sz)
+word bigint_sub_abs(word z[],
+                    const word x[], const word y[], size_t N,
+                    word ws[])
    {
-   word borrow = bigint_sub3(z, x, sz, y, sz);
+   // Subtract in both direction then conditional copy out the result
 
-   CT::unpoison(borrow);
-   if(borrow)
+   word* ws0 = ws;
+   word* ws1 = ws + N;
+
+   word borrow0 = 0;
+   word borrow1 = 0;
+
+   const size_t blocks = N - (N % 8);
+
+   for(size_t i = 0; i != blocks; i += 8)
       {
-      bigint_sub3(z, y, sz, x, sz);
-      return -1;
+      borrow0 = word8_sub3(ws0 + i, x + i, y + i, borrow0);
+      borrow1 = word8_sub3(ws1 + i, y + i, x + i, borrow1);
       }
 
-   return 1;
+   for(size_t i = blocks; i != N; ++i)
+      {
+      ws0[i] = word_sub(x[i], y[i], &borrow0);
+      ws1[i] = word_sub(y[i], x[i], &borrow1);
+      }
+
+   word mask = CT::conditional_copy_mem(borrow1, z, ws0, ws1, N);
+
+   return CT::select<word>(mask, 0, 1);
    }
 
 /*
diff --git a/src/lib/math/mp/mp_core.h b/src/lib/math/mp/mp_core.h
index 4ae28f7bb..9d8ad84db 100644
--- a/src/lib/math/mp/mp_core.h
+++ b/src/lib/math/mp/mp_core.h
@@ -100,9 +100,16 @@ word bigint_sub3(word z[],
 * Otherwise compute z = y - x
 * No borrow is possible since the result is always >= 0
 *
-* Returns 1 if x >= y or -1 if x < y
-*/
-int32_t bigint_sub_abs(word z[], const word x[], const word y[], size_t size);
+* Returns 1 if x >= y or 0 if x < y
+* @param z output array of at least N words
+* @param x input array of N words
+* @param y input array of N words
+* @param N length of x and y
+* @param ws array of at least 2*N words
+*/
+word bigint_sub_abs(word z[],
+                    const word x[], const word y[], size_t N,
+                    word ws[]);
 
 /*
 * Shift Operations
diff --git a/src/lib/math/mp/mp_karat.cpp b/src/lib/math/mp/mp_karat.cpp
index 03a37ed8d..27ae349ef 100644
--- a/src/lib/math/mp/mp_karat.cpp
+++ b/src/lib/math/mp/mp_karat.cpp
@@ -1,6 +1,6 @@
 /*
 * Multiplication and Squaring
-* (C) 1999-2010 Jack Lloyd
+* (C) 1999-2010,2018 Jack Lloyd
 *     2016 Matthias Gierlings
 *
 * Botan is released under the Simplified BSD License (see license.txt)
@@ -8,6 +8,7 @@
 
 #include <botan/internal/mp_core.h>
 #include <botan/internal/mp_asmi.h>
+#include <botan/internal/ct_utils.h>
 #include <botan/mem_ops.h>
 #include <botan/exceptn.h>
 
@@ -120,11 +121,10 @@ void karatsuba_mul(word z[], const word x[], const word y[], size_t N,
    */
 
    // First compute (X_lo - X_hi)*(Y_hi - Y_lo)
-   const int32_t cmp0 = bigint_sub_abs(z0, x0, x1, N2);
-   const int32_t cmp1 = bigint_sub_abs(z1, y1, y0, N2);
+   const word cmp0 = bigint_sub_abs(z0, x0, x1, N2, workspace);
+   const word cmp1 = bigint_sub_abs(z1, y1, y0, N2, workspace);
 
    karatsuba_mul(ws0, z0, z1, N2, ws1);
-   const bool is_negative = cmp0 != cmp1;
 
    // Compute X_lo * Y_lo
    karatsuba_mul(z0, x0, y0, N2, ws1);
@@ -138,10 +138,12 @@ void karatsuba_mul(word z[], const word x[], const word y[], size_t N,
    z_carry += bigint_add2_nc(z + N + N2, N2, &ws_carry, 1);
    bigint_add2_nc(z + N + N2, N2, &z_carry, 1);
 
-   if(is_negative)
-      bigint_sub2(z + N2, 2*N-N2, ws0, N);
-   else
-      bigint_add2_nc(z + N2, 2*N-N2, ws0, N);
+   clear_mem(workspace + N, N2);
+
+   const word is_negative = CT::expand_mask<word>(cmp0 != cmp1);
+
+   bigint_cnd_sub(is_negative,  z + N2, workspace, 2*N-N2);
+   bigint_cnd_add(~is_negative, z + N2, workspace, 2*N-N2);
    }
 
 /*
@@ -178,7 +180,7 @@ void karatsuba_sqr(word z[], const word x[], size_t N, word workspace[])
    clear_mem(workspace, 2*N);
 
    // See comment in karatsuba_mul
-   bigint_sub_abs(z0, x0, x1, N2);
+   bigint_sub_abs(z0, x0, x1, N2, workspace);
    karatsuba_sqr(ws0, z0, N2, ws1);
 
    karatsuba_sqr(z0, x0, N2, ws1);
diff --git a/src/lib/utils/ct_utils.h b/src/lib/utils/ct_utils.h
index 0356f9b39..f67fb8f10 100644
--- a/src/lib/utils/ct_utils.h
+++ b/src/lib/utils/ct_utils.h
@@ -139,11 +139,11 @@ inline T is_lte(T a, T b)
    }
 
 template<typename T>
-inline void conditional_copy_mem(T value,
-                                 T* to,
-                                 const T* from0,
-                                 const T* from1,
-                                 size_t elems)
+inline T conditional_copy_mem(T value,
+                              T* to,
+                              const T* from0,
+                              const T* from1,
+                              size_t elems)
    {
    const T mask = CT::expand_mask(value);
 
@@ -151,6 +151,8 @@ inline void conditional_copy_mem(T value,
       {
       to[i] = CT::select(mask, from0[i], from1[i]);
       }
+
+   return mask;
    }
 
 template<typename T>