Use consistent logic for OAEP and PKCS1v15 decoding

The decoding leaked some information about the delimiter index
due to copying only exactly input_len - delim_idx bytes. I can't
articulate a specific attack that would work here, but it is easy
enough to fix this to run in const time instead, where all bytes
are accessed regardless of the length of the padding.

CT::copy_out is O(n^2) and thus terrible, but in practice it is only
used with RSA decryption, and multiplication is also O(n^2) with the
modulus size, so a few extra cycles here doesn't matter much.

9 files changed, 171 insertions, 92 deletions

diff --git a/src/lib/math/bigint/big_ops2.cpp b/src/lib/math/bigint/big_ops2.cpp
index c42bf16e9..e758089cd 100644
--- a/src/lib/math/bigint/big_ops2.cpp
+++ b/src/lib/math/bigint/big_ops2.cpp
@@ -76,8 +76,7 @@ BigInt& BigInt::mod_add(const BigInt& s, const BigInt& mod, secure_vector<word>&
       ws.resize(3*mod_sw);
 
    word borrow = bigint_sub3(&ws[0], mod.data(), mod_sw, s.data(), mod_sw);
-   CT::unpoison(borrow);
-   BOTAN_ASSERT_NOMSG(borrow == 0);
+   BOTAN_DEBUG_ASSERT(borrow == 0);
 
    // Compute t - ws
    borrow = bigint_sub3(&ws[mod_sw], this->data(), mod_sw, &ws[0], mod_sw);
diff --git a/src/lib/math/mp/mp_monty.cpp b/src/lib/math/mp/mp_monty.cpp
index e5dda705c..433d3ff35 100644
--- a/src/lib/math/mp/mp_monty.cpp
+++ b/src/lib/math/mp/mp_monty.cpp
@@ -98,12 +98,10 @@ void bigint_monty_redc_generic(word z[], size_t z_size,
       ws[p_size + 1 + i] = word_sub(ws[i], p[i], &borrow);
    ws[2*p_size+1] = word_sub(ws[p_size], 0, &borrow);
 
+   BOTAN_DEBUG_ASSERT(borrow == 0 || borrow == 1);
+
    CT::conditional_copy_mem(borrow, z, ws, ws + (p_size + 1), (p_size + 1));
    clear_mem(z + p_size, z_size - p_size - 2);
-
-   // This check comes after we've used it but that's ok here
-   CT::unpoison(&borrow, 1);
-   BOTAN_ASSERT(borrow == 0 || borrow == 1, "Expected borrow");
    }
 
 }
diff --git a/src/lib/pk_pad/eme_oaep/oaep.cpp b/src/lib/pk_pad/eme_oaep/oaep.cpp
index 9a8676ab9..163efbfef 100644
--- a/src/lib/pk_pad/eme_oaep/oaep.cpp
+++ b/src/lib/pk_pad/eme_oaep/oaep.cpp
@@ -106,7 +106,7 @@ oaep_find_delim(uint8_t& valid_mask,
 
    size_t delim_idx = 2 * hlen;
    CT::Mask<uint8_t> waiting_for_delim = CT::Mask<uint8_t>::set();
-   CT::Mask<uint8_t> bad_input = CT::Mask<uint8_t>::cleared();
+   CT::Mask<uint8_t> bad_input_m = CT::Mask<uint8_t>::cleared();
 
    for(size_t i = delim_idx; i < input_len; ++i)
       {
@@ -115,7 +115,7 @@ oaep_find_delim(uint8_t& valid_mask,
 
       const auto add_m = waiting_for_delim & zero_m;
 
-      bad_input |= waiting_for_delim & ~(zero_m | one_m);
+      bad_input_m |= waiting_for_delim & ~(zero_m | one_m);
 
       delim_idx += add_m.if_set_return(1);
 
@@ -123,19 +123,15 @@ oaep_find_delim(uint8_t& valid_mask,
       }
 
    // If we never saw any non-zero byte, then it's not valid input
-   bad_input |= waiting_for_delim;
-   bad_input |= CT::Mask<uint8_t>::is_zero(ct_compare_u8(&input[hlen], Phash.data(), hlen));
+   bad_input_m |= waiting_for_delim;
+   bad_input_m |= CT::Mask<uint8_t>::is_zero(ct_compare_u8(&input[hlen], Phash.data(), hlen));
 
-   delim_idx = CT::Mask<size_t>::expand(bad_input.value()).if_not_set_return(delim_idx);
+   delim_idx += 1;
 
-   CT::unpoison(input, input_len);
-   CT::unpoison(&bad_input, 1);
-   CT::unpoison(&delim_idx, 1);
-
-   valid_mask = (~bad_input).value();
+   valid_mask = (~bad_input_m).unpoisoned_value();
+   const secure_vector<uint8_t> output = CT::copy_output(bad_input_m, input, input_len, delim_idx);
 
-   secure_vector<uint8_t> output(input + delim_idx + 1, input + input_len);
-   bad_input.if_set_zero_out(output.data(), output.size());
+   CT::unpoison(input, input_len);
 
    return output;
    }
diff --git a/src/lib/pk_pad/eme_pkcs1/eme_pkcs.cpp b/src/lib/pk_pad/eme_pkcs1/eme_pkcs.cpp
index 597b7c26a..eac3da5d9 100644
--- a/src/lib/pk_pad/eme_pkcs1/eme_pkcs.cpp
+++ b/src/lib/pk_pad/eme_pkcs1/eme_pkcs.cpp
@@ -50,7 +50,13 @@ secure_vector<uint8_t> EME_PKCS1v15::pad(const uint8_t in[], size_t inlen,
 secure_vector<uint8_t> EME_PKCS1v15::unpad(uint8_t& valid_mask,
                                         const uint8_t in[], size_t inlen) const
    {
-   if(inlen < 2)
+   /*
+   * RSA decryption pads the ciphertext up to the modulus size, so this only
+   * occurs with very (!) small keys, or when fuzzing.
+   *
+   * 11 bytes == 00,02 + 8 bytes mandatory padding + 00
+   */
+   if(inlen < 11)
       {
       valid_mask = false;
       return secure_vector<uint8_t>();
@@ -60,7 +66,7 @@ secure_vector<uint8_t> EME_PKCS1v15::unpad(uint8_t& valid_mask,
 
    CT::Mask<uint8_t> bad_input_m = CT::Mask<uint8_t>::cleared();
    CT::Mask<uint8_t> seen_zero_m = CT::Mask<uint8_t>::cleared();
-   size_t delim_idx = 0;
+   size_t delim_idx = 2; // initial 0002
 
    bad_input_m |= ~CT::Mask<uint8_t>::is_equal(in[0], 0);
    bad_input_m |= ~CT::Mask<uint8_t>::is_equal(in[1], 2);
@@ -68,23 +74,24 @@ secure_vector<uint8_t> EME_PKCS1v15::unpad(uint8_t& valid_mask,
    for(size_t i = 2; i < inlen; ++i)
       {
       const auto is_zero_m = CT::Mask<uint8_t>::is_zero(in[i]);
-
       delim_idx += seen_zero_m.if_not_set_return(1);
-
-      bad_input_m |= is_zero_m & CT::Mask<uint8_t>(CT::Mask<size_t>::is_lt(i, 10));
       seen_zero_m |= is_zero_m;
       }
 
+   // no zero delim -> bad padding
    bad_input_m |= ~seen_zero_m;
-   bad_input_m |= CT::Mask<uint8_t>(CT::Mask<size_t>::is_lt(delim_idx, 8));
+   /*
+   delim indicates < 8 bytes padding -> bad padding
+
+   We require 11 here because we are counting also the 00 delim byte
+   */
+   bad_input_m |= CT::Mask<uint8_t>(CT::Mask<size_t>::is_lt(delim_idx, 11));
+
+   valid_mask = (~bad_input_m).unpoisoned_value();
+   const secure_vector<uint8_t> output = CT::copy_output(bad_input_m, in, inlen, delim_idx);
 
    CT::unpoison(in, inlen);
-   CT::unpoison(bad_input_m);
-   CT::unpoison(delim_idx);
 
-   secure_vector<uint8_t> output(&in[delim_idx + 2], &in[inlen]);
-   bad_input_m.if_set_zero_out(output.data(), output.size());
-   valid_mask = ~bad_input_m.value();
    return output;
    }
 
diff --git a/src/lib/pk_pad/eme_pkcs1/eme_pkcs.h b/src/lib/pk_pad/eme_pkcs1/eme_pkcs.h
index a77e0141b..26b03e47a 100644
--- a/src/lib/pk_pad/eme_pkcs1/eme_pkcs.h
+++ b/src/lib/pk_pad/eme_pkcs1/eme_pkcs.h
@@ -19,7 +19,7 @@ class BOTAN_PUBLIC_API(2,0) EME_PKCS1v15 final : public EME
    {
    public:
       size_t maximum_input_size(size_t) const override;
-   private:
+
       secure_vector<uint8_t> pad(const uint8_t[], size_t, size_t,
                              RandomNumberGenerator&) const override;
 
diff --git a/src/lib/utils/ct_utils.cpp b/src/lib/utils/ct_utils.cpp
new file mode 100644
index 000000000..029c54065
--- /dev/null
+++ b/src/lib/utils/ct_utils.cpp
@@ -0,0 +1,82 @@
+/*
+* (C) 2018 Jack Lloyd
+*
+* Botan is released under the Simplified BSD License (see license.txt)
+*/
+
+#include <botan/internal/ct_utils.h>
+
+namespace Botan {
+
+namespace CT {
+
+secure_vector<uint8_t> copy_output(CT::Mask<uint8_t> bad_input,
+                                   const uint8_t input[],
+                                   size_t input_length,
+                                   size_t offset)
+   {
+   if(input_length == 0)
+      return secure_vector<uint8_t>();
+
+   /*
+   * Ensure at runtime that offset <= input_length. This is an invalid input,
+   * but we can't throw without using the poisoned value. Instead, if it happens,
+   * set offset to be equal to the input length (so output_bytes becomes 0 and
+   * the returned vector is empty)
+   */
+   const auto valid_offset = CT::Mask<size_t>::is_lte(offset, input_length);
+   offset = valid_offset.select(offset, input_length);
+
+   const size_t output_bytes = input_length - offset;
+
+   secure_vector<uint8_t> output(input_length);
+
+   /*
+   Move the desired output bytes to the front using a slow (O^n)
+   but constant time loop that does not leak the value of the offset
+   */
+   for(size_t i = 0; i != input_length; ++i)
+      {
+      /*
+      start index from i rather than 0 since we know j must be >= i + offset
+      to have any effect, and starting from i does not reveal information
+      */
+      for(size_t j = i; j != input_length; ++j)
+         {
+         const uint8_t b = input[j];
+         const auto is_eq = CT::Mask<size_t>::is_equal(j, offset + i);
+         output[i] |= is_eq.if_set_return(b);
+         }
+      }
+
+   bad_input.if_set_zero_out(output.data(), output.size());
+
+   /*
+   This is potentially not const time, depending on how std::vector is
+   implemented. But since we are always reducing length, it should
+   just amount to setting the member var holding the length.
+   */
+   CT::unpoison(output.data(), output.size());
+   CT::unpoison(output_bytes);
+   output.resize(output_bytes);
+   return output;
+   }
+
+secure_vector<uint8_t> strip_leading_zeros(const uint8_t in[], size_t length)
+   {
+   size_t leading_zeros = 0;
+
+   auto only_zeros = Mask<uint8_t>::set();
+
+   for(size_t i = 0; i != length; ++i)
+      {
+      only_zeros &= CT::Mask<uint8_t>::is_zero(in[i]);
+      leading_zeros += only_zeros.if_set_return(1);
+      }
+
+   return copy_output(CT::Mask<uint8_t>::cleared(), in, length, leading_zeros);
+   }
+
+}
+
+}
diff --git a/src/lib/utils/ct_utils.h b/src/lib/utils/ct_utils.h
index 63583460f..72be79114 100644
--- a/src/lib/utils/ct_utils.h
+++ b/src/lib/utils/ct_utils.h
@@ -354,20 +354,17 @@ inline Mask<T> conditional_copy_mem(T cnd,
    return mask;
    }
 
-inline secure_vector<uint8_t> strip_leading_zeros(const uint8_t in[], size_t length)
-   {
-   size_t leading_zeros = 0;
-
-   auto only_zeros = Mask<uint8_t>::set();
-
-   for(size_t i = 0; i != length; ++i)
-      {
-      only_zeros &= CT::Mask<uint8_t>::is_zero(in[i]);
-      leading_zeros += only_zeros.if_set_return(1);
-      }
+/**
+* If bad_mask is unset, return in[delim_idx:input_length] copied to
+* new buffer. If bad_mask is set, return an all zero vector of
+* unspecified length.
+*/
+secure_vector<uint8_t> copy_output(CT::Mask<uint8_t> bad_input,
+                                   const uint8_t input[],
+                                   size_t input_length,
+                                   size_t delim_idx);
 
-   return secure_vector<uint8_t>(in + leading_zeros, in + length);
-   }
+secure_vector<uint8_t> strip_leading_zeros(const uint8_t in[], size_t length);
 
 inline secure_vector<uint8_t> strip_leading_zeros(const secure_vector<uint8_t>& in)
    {
diff --git a/src/tests/data/pk_pad_eme/pkcs1.vec b/src/tests/data/pk_pad_eme/pkcs1.vec
index 48b732d95..55eae75bc 100644
--- a/src/tests/data/pk_pad_eme/pkcs1.vec
+++ b/src/tests/data/pk_pad_eme/pkcs1.vec
@@ -1,46 +1,43 @@
-[PKCS1v15]
+[invalid]
 RawCiphertext =
-ValidInput = false
 
 RawCiphertext = 00
-ValidInput = false
-
-RawCiphertext = 0000
-ValidInput = false
 
 RawCiphertext = FF
-ValidInput = false
 
-RawCiphertext = FF02
-ValidInput = false
+RawCiphertext = 0000
 
-RawCiphertext = 0002DEDE24212121DEDEDE5EDEDEDEDE0A5EDE00000000DEDEDE010000000000
-Plaintext = 000000DEDEDE010000000000
-ValidInput = true
+RawCiphertext = FF02
 
 RawCiphertext = 022C2C4018181818181818181818183A18181818181818180000002C022C00010A2C2C2C2C2C022C
-ValidInput = false
 
-RawCiphertext = 00022C2C4018181818181818181818183A18181818181818180000002C022C00010A2C2C2C2C2C022C
+# Short padding strings
+RawCiphertext = 0002FFFFFFFFFFFFFF000113131313131388
+RawCiphertext = 0002FFFFFFFFFFFF000113131313131388
+RawCiphertext = 0002FFFFFFFFFF000113131313131388
+RawCiphertext = 0002FFFFFFFF000113131313131388
+RawCiphertext = 0002FFFFFF000113131313131388
+
+[valid]
+
+Plaintext = 0113131313131388
+RawCiphertext = 0002FFFFFFFFFFFFFFFF000113131313131388
+
+Plaintext = 000000DEDEDE010000000000
+RawCiphertext = 0002DEDE24212121DEDEDE5EDEDEDEDE0A5EDE00000000DEDEDE010000000000
+
 Plaintext = 00002C022C00010A2C2C2C2C2C022C
-ValidInput = true
+RawCiphertext = 00022C2C4018181818181818181818183A18181818181818180000002C022C00010A2C2C2C2C2C022C
 
-RawCiphertext = 0002FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF010100000021FFFFFFFFFFFFBC
 Plaintext = 000021FFFFFFFFFFFFBC
-ValidInput = true
+RawCiphertext = 0002FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF010100000021FFFFFFFFFFFFBC
 
-RawCiphertext = 0002F9CCFFFFCCCCCCCCCCCCCCCC4E0000CCFFFFCCCCCCCCCCCCCCCCCCCCCCCCCC06
 Plaintext = 00CCFFFFCCCCCCCCCCCCCCCCCCCCCCCCCC06
-ValidInput = true
+RawCiphertext = 0002F9CCFFFFCCCCCCCCCCCCCCCC4E0000CCFFFFCCCCCCCCCCCCCCCCCCCCCCCCCC06
 
-RawCiphertext = 000253FFC43B5253FF0A53DE0000FD
 Plaintext = 00FD
-ValidInput = true
+RawCiphertext = 000253FFC43B5253FF0A53DE0000FD
 
-RawCiphertext = 0002FFFF06FFFFFFFFFF00000000000000000000000000000000000000000000000000000000FF0A
 Plaintext = 000000000000000000000000000000000000000000000000000000FF0A
-ValidInput = true
+RawCiphertext = 0002FFFF06FFFFFFFFFF00000000000000000000000000000000000000000000000000000000FF0A
 
-# Padding only 7 bytes
-RawCiphertext = 0002FFFFFFFFFFFFFF000113131313131388
-ValidInput = false
diff --git a/src/tests/test_pk_pad.cpp b/src/tests/test_pk_pad.cpp
index babe5242d..5d56acbc8 100644
--- a/src/tests/test_pk_pad.cpp
+++ b/src/tests/test_pk_pad.cpp
@@ -8,58 +8,61 @@
 
 #if defined(BOTAN_HAS_PK_PADDING)
    #include <botan/emsa.h>
-   #include <botan/eme.h>
+#endif
+
+#if defined(BOTAN_HAS_EME_PKCS1v15)
+   #include <botan/eme_pkcs.h>
 #endif
 
 namespace Botan_Tests {
 
-#if defined(BOTAN_HAS_PK_PADDING)
+#if defined(BOTAN_HAS_EME_PKCS1v15)
 
-class EME_Decoding_Tests final : public Text_Based_Test
+class EME_PKCS1v15_Decoding_Tests final : public Text_Based_Test
    {
    public:
-      EME_Decoding_Tests()
+      EME_PKCS1v15_Decoding_Tests()
          : Text_Based_Test(
-              "pk_pad_eme",
-              "RawCiphertext,ValidInput",
+              "pk_pad_eme/pkcs1.vec",
+              "RawCiphertext",
               "Plaintext") {}
 
-      Test::Result run_one_test(const std::string& algo, const VarMap& vars) override
+      Test::Result run_one_test(const std::string& hdr, const VarMap& vars) override
          {
-         Test::Result result(algo + " Decoding");
+         const bool is_valid = (hdr == "valid");
 
-         std::unique_ptr<Botan::EME> eme;
+         Test::Result result("PKCSv15 Decoding");
 
-         try
-            {
-            eme.reset(Botan::get_eme(algo));
-            }
-         catch(Botan::Lookup_Error&)
-            {
-            result.note_missing(algo);
-            return result;
-            }
+         Botan::EME_PKCS1v15 pkcs;
 
          const std::vector<uint8_t> ciphertext = vars.get_req_bin("RawCiphertext");
          const std::vector<uint8_t> plaintext = vars.get_opt_bin("Plaintext");
-         const bool is_valid = vars.get_req_bool("ValidInput");
 
          if(is_valid == false)
             {
-            result.test_eq("Plaintext value is empty for invalid EME inputs", plaintext.size(), 0);
+            result.test_eq("Plaintext value should be empty for invalid EME inputs", plaintext.size(), 0);
             }
 
          uint8_t valid_mask = 0;
          Botan::secure_vector<uint8_t> decoded =
-            eme->unpad(valid_mask, ciphertext.data(), ciphertext.size());
+            pkcs.unpad(valid_mask, ciphertext.data(), ciphertext.size());
 
          result.confirm("EME valid_mask has expected value", valid_mask == 0x00 || valid_mask == 0xFF);
          result.test_eq("EME decoding valid/invalid matches", valid_mask == 0xFF, is_valid);
 
-         if(is_valid && valid_mask == 0xFF)
+         if(valid_mask == 0xFF)
             {
             result.test_eq("EME decoded plaintext correct", decoded, plaintext);
             }
+         else
+            {
+            bool all_zeros = true;
+            for(size_t i = 0; i != decoded.size(); ++i)
+               if(decoded[i] != 0)
+                  all_zeros = false;
+
+            result.confirm("On invalid padding output is all zero", all_zeros);
+            }
 
          // TODO: also test that encoding is accepted
 
@@ -67,7 +70,7 @@ class EME_Decoding_Tests final : public Text_Based_Test
          }
    };
 
-BOTAN_REGISTER_TEST("pk_pad_eme", EME_Decoding_Tests);
+BOTAN_REGISTER_TEST("eme_pkcs1v15", EME_PKCS1v15_Decoding_Tests);
 
 class EMSA_unit_tests final : public Test
    {