Avoid branching in the NIST prime reduction code

This is still vulnerable to a cache-based side channel since the
multiple chosen leaks the final carry.

2 files changed, 58 insertions, 59 deletions

diff --git a/src/lib/math/mp/mp_core.h b/src/lib/math/mp/mp_core.h
index 5244261d7..40ff5fadd 100644
--- a/src/lib/math/mp/mp_core.h
+++ b/src/lib/math/mp/mp_core.h
@@ -40,17 +40,16 @@ inline void bigint_cnd_swap(word cnd, word x[], word y[], size_t size)
       }
    }
 
-/*
-* If cond > 0 adds x[0:size] and y[0:size] and returns carry
-* Runs in constant time
-*/
-inline word bigint_cnd_add(word cnd, word x[], const word y[], size_t size)
+inline word bigint_cnd_add(word cnd, word x[], word x_size,
+                           const word y[], size_t y_size)
    {
+   BOTAN_ASSERT(x_size >= y_size, "Expected sizes");
+
    const word mask = CT::expand_mask(cnd);
 
    word carry = 0;
 
-   const size_t blocks = size - (size % 8);
+   const size_t blocks = y_size - (y_size % 8);
    word z[8] = { 0 };
 
    for(size_t i = 0; i != blocks; i += 8)
@@ -61,26 +60,45 @@ inline word bigint_cnd_add(word cnd, word x[], const word y[], size_t size)
          x[i+j] = CT::select(mask, z[j], x[i+j]);
       }
 
-   for(size_t i = blocks; i != size; ++i)
+   for(size_t i = blocks; i != y_size; ++i)
       {
       z[0] = word_add(x[i], y[i], &carry);
       x[i] = CT::select(mask, z[0], x[i]);
       }
 
+   for(size_t i = y_size; i != x_size; ++i)
+      {
+      z[0] = word_add(x[i], 0, &carry);
+      x[i] = CT::select(mask, z[0], x[i]);
+      }
+
    return carry & mask;
    }
 
 /*
+* If cond > 0 adds x[0:size] and y[0:size] and returns carry
+* Runs in constant time
+*/
+inline word bigint_cnd_add(word cnd, word x[], const word y[], size_t size)
+   {
+   return bigint_cnd_add(cnd, x, size, y, size);
+   }
+
+/*
 * If cond > 0 subtracts x[0:size] and y[0:size] and returns borrow
 * Runs in constant time
 */
-inline word bigint_cnd_sub(word cnd, word x[], const word y[], size_t size)
+inline word bigint_cnd_sub(word cnd,
+                           word x[], size_t x_size,
+                           const word y[], size_t y_size)
    {
+   BOTAN_ASSERT(x_size >= y_size, "Expected sizes");
+
    const word mask = CT::expand_mask(cnd);
 
    word carry = 0;
 
-   const size_t blocks = size - (size % 8);
+   const size_t blocks = y_size - (y_size % 8);
    word z[8] = { 0 };
 
    for(size_t i = 0; i != blocks; i += 8)
@@ -91,16 +109,32 @@ inline word bigint_cnd_sub(word cnd, word x[], const word y[], size_t size)
          x[i+j] = CT::select(mask, z[j], x[i+j]);
       }
 
-   for(size_t i = blocks; i != size; ++i)
+   for(size_t i = blocks; i != y_size; ++i)
       {
       z[0] = word_sub(x[i], y[i], &carry);
       x[i] = CT::select(mask, z[0], x[i]);
       }
 
+   for(size_t i = y_size; i != x_size; ++i)
+      {
+      z[0] = word_sub(x[i], 0, &carry);
+      x[i] = CT::select(mask, z[0], x[i]);
+      }
+
    return carry & mask;
    }
 
 /*
+* If cond > 0 adds x[0:size] and y[0:size] and returns carry
+* Runs in constant time
+*/
+inline word bigint_cnd_sub(word cnd, word x[], const word y[], size_t size)
+   {
+   return bigint_cnd_sub(cnd, x, size, y, size);
+   }
+
+
+/*
 * Equivalent to
 *   bigint_cnd_add( mask, x, y, size);
 *   bigint_cnd_sub(~mask, x, y, size);
@@ -478,7 +512,10 @@ void bigint_monty_redc(word z[],
                        size_t ws_size);
 
 /**
-* Compare x and y returning early
+* Compare x and y
+* Return -1 if x < y
+* Return 0 if x == y
+* Return 1 if x > y
 */
 inline int32_t bigint_cmp(const word x[], size_t x_size,
                           const word y[], size_t y_size)
diff --git a/src/lib/math/numbertheory/nistp_redc.cpp b/src/lib/math/numbertheory/nistp_redc.cpp
index 5ad4515b4..a005e1abb 100644
--- a/src/lib/math/numbertheory/nistp_redc.cpp
+++ b/src/lib/math/numbertheory/nistp_redc.cpp
@@ -194,19 +194,9 @@ void redc_p192(BigInt& x, secure_vector<word>& ws)
 #endif
    };
 
-   if(S == 0 && x.word_at(p192_limbs-1) < p192_mults[0][p192_limbs-1])
-      {
-      return;
-      }
-
    word borrow = bigint_sub2(x.mutable_data(), x.size(), p192_mults[S], p192_limbs);
-
-   BOTAN_ASSERT(borrow == 0 || borrow == 1, "Expected borrow during P-192 reduction");
-
-   if(borrow)
-      {
-      bigint_add2(x.mutable_data(), x.size() - 1, p192_mults[0], p192_limbs);
-      }
+   BOTAN_DEBUG_ASSERT(borrow == 0 || borrow == 1);
+   bigint_cnd_add(borrow, x.mutable_data(), x.size(), p192_mults[0], p192_limbs);
    }
 
 const BigInt& prime_p224()
@@ -303,19 +293,9 @@ void redc_p224(BigInt& x, secure_vector<word>& ws)
 
    };
 
-   if(S == 0 && x.word_at(p224_limbs-1) < p224_mults[0][p224_limbs-1])
-      {
-      return;
-      }
-
    word borrow = bigint_sub2(x.mutable_data(), x.size(), p224_mults[S], p224_limbs);
-
-   BOTAN_ASSERT(borrow == 0 || borrow == 1, "Expected borrow during P-224 reduction");
-
-   if(borrow)
-      {
-      bigint_add2(x.mutable_data(), x.size() - 1, p224_mults[0], p224_limbs);
-      }
+   BOTAN_DEBUG_ASSERT(borrow == 0 || borrow == 1);
+   bigint_cnd_add(borrow, x.mutable_data(), x.size(), p224_mults[0], p224_limbs);
    }
 
 const BigInt& prime_p256()
@@ -405,7 +385,7 @@ void redc_p256(BigInt& x, secure_vector<word>& ws)
 
    S += 5; // the top digits of 6*P-256
 
-   BOTAN_ASSERT(S >= 0 && S <= 10, "Expected overflow");
+   BOTAN_DEBUG_ASSERT(S >= 0 && S <= 10);
 
    /*
    This is a table of (i*P-256) % 2**256 for i in 1...10
@@ -438,19 +418,11 @@ void redc_p256(BigInt& x, secure_vector<word>& ws)
 #endif
    };
 
-   if(S == 0 && x.word_at(p256_limbs-1) < p256_mults[0][p256_limbs-1])
-      {
-      return;
-      }
+   CT::unpoison(S);
 
    word borrow = bigint_sub2(x.mutable_data(), x.size(), p256_mults[S], p256_limbs);
-
-   BOTAN_ASSERT(borrow == 0 || borrow == 1, "Expected borrow during P-256 reduction");
-
-   if(borrow)
-      {
-      bigint_add2(x.mutable_data(), x.size() - 1, p256_mults[0], p256_limbs);
-      }
+   BOTAN_DEBUG_ASSERT(borrow == 0 || borrow == 1);
+   bigint_cnd_add(borrow, x.mutable_data(), x.size(), p256_mults[0], p256_limbs);
    }
 
 const BigInt& prime_p384()
@@ -598,19 +570,9 @@ void redc_p384(BigInt& x, secure_vector<word>& ws)
 #endif
    };
 
-   if(S == 0 && x.word_at(p384_limbs-1) < p384_mults[0][p384_limbs-1])
-      {
-      return;
-      }
-
    word borrow = bigint_sub2(x.mutable_data(), x.size(), p384_mults[S], p384_limbs);
-
-   BOTAN_ASSERT(borrow == 0 || borrow == 1, "Expected borrow during P-384 reduction");
-
-   if(borrow)
-      {
-      bigint_add2(x.mutable_data(), x.size() - 1, p384_mults[0], p384_limbs);
-      }
+   BOTAN_DEBUG_ASSERT(borrow == 0 || borrow == 1);
+   bigint_cnd_add(borrow, x.mutable_data(), x.size(), p384_mults[0], p384_limbs);
    }
 
 #endif