Merge GH #2312 Make CBC padding constant time

6 files changed, 197 insertions, 52 deletions

diff --git a/doc/security.rst b/doc/security.rst
index b606e57f6..e2e736a91 100644
--- a/doc/security.rst
+++ b/doc/security.rst
@@ -15,6 +15,23 @@ mail please use::
 This key can be found in the file ``doc/pgpkey.txt`` or online at
 https://keybase.io/jacklloyd and on most PGP keyservers.
 
+2020
+^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
+
+* 2020-03-24: Side channel during CBC padding
+
+  The CBC padding operations were not constant time and as a result would leak
+  the length of the plaintext values which were being padded to an attacker
+  running a side channel attack via shared resources such as cache or branch
+  predictor. No information about the contents was leaked, but the length alone
+  might be used to make inferences about the contents. This issue affects TLS
+  CBC ciphersuites as well as CBC encryption using PKCS7 or other similar padding
+  mechanisms. In all cases, the unpadding operations were already constant time
+  and are not affected. Reported by Maximilian Blochberger of Universität
+  Hamburg.
+
+  Fixed in 2.14.0, all prior versions affected.
+
 2018
 ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
 
diff --git a/src/lib/modes/cbc/cbc.cpp b/src/lib/modes/cbc/cbc.cpp
index a4af7f0bf..cde08f64a 100644
--- a/src/lib/modes/cbc/cbc.cpp
+++ b/src/lib/modes/cbc/cbc.cpp
@@ -135,8 +135,7 @@ void CBC_Encryption::finish(secure_vector<uint8_t>& buffer, size_t offset)
 
    padding().add_padding(buffer, bytes_in_final_block, BS);
 
-   if((buffer.size()-offset) % BS)
-      throw Internal_Error("Did not pad to full block size in " + name());
+   BOTAN_ASSERT_EQUAL(buffer.size() % BS, offset % BS, "Padded to block boundary");
 
    update(buffer, offset);
    }
diff --git a/src/lib/modes/mode_pad/mode_pad.cpp b/src/lib/modes/mode_pad/mode_pad.cpp
index 1df6abfeb..18bb71af5 100644
--- a/src/lib/modes/mode_pad/mode_pad.cpp
+++ b/src/lib/modes/mode_pad/mode_pad.cpp
@@ -1,6 +1,6 @@
 /*
 * CBC Padding Methods
-* (C) 1999-2007,2013,2018 Jack Lloyd
+* (C) 1999-2007,2013,2018,2020 Jack Lloyd
 * (C) 2016 René Korthaus, Rohde & Schwarz Cybersecurity
 *
 * Botan is released under the Simplified BSD License (see license.txt)
@@ -40,12 +40,39 @@ BlockCipherModePaddingMethod* get_bc_pad(const std::string& algo_spec)
 */
 void PKCS7_Padding::add_padding(secure_vector<uint8_t>& buffer,
                                 size_t last_byte_pos,
-                                size_t block_size) const
+                                size_t BS) const
    {
-   const uint8_t pad_value = static_cast<uint8_t>(block_size - last_byte_pos);
+   /*
+   Padding format is
+   01
+   0202
+   030303
+   ...
+   */
+   BOTAN_DEBUG_ASSERT(last_byte_pos < BS);
+
+   const uint8_t padding_len = static_cast<uint8_t>(BS - last_byte_pos);
+
+   buffer.resize(buffer.size() + padding_len);
+
+   CT::poison(&last_byte_pos, 1);
+   CT::poison(buffer.data(), buffer.size());
+
+   BOTAN_DEBUG_ASSERT(buffer.size() % BS == 0);
+   BOTAN_DEBUG_ASSERT(buffer.size() >= BS);
+
+   const size_t start_of_last_block = buffer.size() - BS;
+   const size_t end_of_last_block = buffer.size();
+   const size_t start_of_padding = buffer.size() - padding_len;
+
+   for(size_t i = start_of_last_block; i != end_of_last_block; ++i)
+      {
+      auto needs_padding = CT::Mask<uint8_t>(CT::Mask<size_t>::is_gte(i, start_of_padding));
+      buffer[i] = needs_padding.select(padding_len, buffer[i]);
+      }
 
-   for(size_t i = 0; i != pad_value; ++i)
-      buffer.push_back(pad_value);
+   CT::unpoison(buffer.data(), buffer.size());
+   CT::unpoison(last_byte_pos);
    }
 
 /*
@@ -88,15 +115,40 @@ size_t PKCS7_Padding::unpad(const uint8_t input[], size_t input_length) const
 */
 void ANSI_X923_Padding::add_padding(secure_vector<uint8_t>& buffer,
                                     size_t last_byte_pos,
-                                    size_t block_size) const
+                                    size_t BS) const
    {
-   const uint8_t pad_value = static_cast<uint8_t>(block_size - last_byte_pos);
+   /*
+   Padding format is
+   01
+   0002
+   000003
+   ...
+   */
+   BOTAN_DEBUG_ASSERT(last_byte_pos < BS);
+
+   const uint8_t padding_len = static_cast<uint8_t>(BS - last_byte_pos);
+
+   buffer.resize(buffer.size() + padding_len);
+
+   CT::poison(&last_byte_pos, 1);
+   CT::poison(buffer.data(), buffer.size());
 
-   for(size_t i = last_byte_pos; i < block_size-1; ++i)
+   BOTAN_DEBUG_ASSERT(buffer.size() % BS == 0);
+   BOTAN_DEBUG_ASSERT(buffer.size() >= BS);
+
+   const size_t start_of_last_block = buffer.size() - BS;
+   const size_t end_of_zero_padding = buffer.size() - 1;
+   const size_t start_of_padding = buffer.size() - padding_len;
+
+   for(size_t i = start_of_last_block; i != end_of_zero_padding; ++i)
       {
-      buffer.push_back(0);
+      auto needs_padding = CT::Mask<uint8_t>(CT::Mask<size_t>::is_gte(i, start_of_padding));
+      buffer[i] = needs_padding.select(0, buffer[i]);
       }
-   buffer.push_back(pad_value);
+
+   buffer[buffer.size()-1] = padding_len;
+   CT::unpoison(buffer.data(), buffer.size());
+   CT::unpoison(last_byte_pos);
    }
 
 /*
@@ -133,12 +185,41 @@ size_t ANSI_X923_Padding::unpad(const uint8_t input[], size_t input_length) cons
 */
 void OneAndZeros_Padding::add_padding(secure_vector<uint8_t>& buffer,
                                       size_t last_byte_pos,
-                                      size_t block_size) const
+                                      size_t BS) const
    {
-   buffer.push_back(0x80);
+   /*
+   Padding format is
+   80
+   8000
+   800000
+   ...
+   */
+
+   BOTAN_DEBUG_ASSERT(last_byte_pos < BS);
+
+   const uint8_t padding_len = static_cast<uint8_t>(BS - last_byte_pos);
+
+   buffer.resize(buffer.size() + padding_len);
+
+   CT::poison(&last_byte_pos, 1);
+   CT::poison(buffer.data(), buffer.size());
+
+   BOTAN_DEBUG_ASSERT(buffer.size() % BS == 0);
+   BOTAN_DEBUG_ASSERT(buffer.size() >= BS);
+
+   const size_t start_of_last_block = buffer.size() - BS;
+   const size_t end_of_last_block = buffer.size();
+   const size_t start_of_padding = buffer.size() - padding_len;
+
+   for(size_t i = start_of_last_block; i != end_of_last_block; ++i)
+      {
+      auto needs_80 = CT::Mask<uint8_t>(CT::Mask<size_t>::is_equal(i, start_of_padding));
+      auto needs_00 = CT::Mask<uint8_t>(CT::Mask<size_t>::is_gt(i, start_of_padding));
+      buffer[i] = needs_00.select(0x00, needs_80.select(0x80, buffer[i]));
+      }
 
-   for(size_t i = last_byte_pos + 1; i % block_size; ++i)
-      buffer.push_back(0x00);
+   CT::unpoison(buffer.data(), buffer.size());
+   CT::unpoison(last_byte_pos);
    }
 
 /*
@@ -179,14 +260,42 @@ size_t OneAndZeros_Padding::unpad(const uint8_t input[], size_t input_length) co
 */
 void ESP_Padding::add_padding(secure_vector<uint8_t>& buffer,
                               size_t last_byte_pos,
-                              size_t block_size) const
+                              size_t BS) const
    {
-   uint8_t pad_value = 0x01;
+   /*
+   Padding format is
+   01
+   0102
+   010203
+   ...
+   */
+   BOTAN_DEBUG_ASSERT(last_byte_pos < BS);
+
+   const uint8_t padding_len = static_cast<uint8_t>(BS - last_byte_pos);
+
+   buffer.resize(buffer.size() + padding_len);
+
+   CT::poison(&last_byte_pos, 1);
+   CT::poison(buffer.data(), buffer.size());
 
-   for(size_t i = last_byte_pos; i < block_size; ++i)
+   BOTAN_DEBUG_ASSERT(buffer.size() % BS == 0);
+   BOTAN_DEBUG_ASSERT(buffer.size() >= BS);
+
+   const size_t start_of_last_block = buffer.size() - BS;
+   const size_t end_of_last_block = buffer.size();
+   const size_t start_of_padding = buffer.size() - padding_len;
+
+   uint8_t pad_ctr = 0x01;
+
+   for(size_t i = start_of_last_block; i != end_of_last_block; ++i)
       {
-      buffer.push_back(pad_value++);
+      auto needs_padding = CT::Mask<uint8_t>(CT::Mask<size_t>::is_gte(i, start_of_padding));
+      buffer[i] = needs_padding.select(pad_ctr, buffer[i]);
+      pad_ctr = needs_padding.select(pad_ctr + 1, pad_ctr);
       }
+
+   CT::unpoison(buffer.data(), buffer.size());
+   CT::unpoison(last_byte_pos);
    }
 
 /*
diff --git a/src/lib/tls/tls_cbc/tls_cbc.cpp b/src/lib/tls/tls_cbc/tls_cbc.cpp
index a23fa8595..3e3e4c2df 100644
--- a/src/lib/tls/tls_cbc/tls_cbc.cpp
+++ b/src/lib/tls/tls_cbc/tls_cbc.cpp
@@ -1,6 +1,6 @@
 /*
 * TLS CBC Record Handling
-* (C) 2012,2013,2014,2015,2016 Jack Lloyd
+* (C) 2012,2013,2014,2015,2016,2020 Jack Lloyd
 * (C) 2016 Juraj Somorovsky
 * (C) 2016 Matthias Gierlings
 * (C) 2016 Daniel Neus, Rohde & Schwarz Cybersecurity
@@ -143,6 +143,7 @@ void TLS_CBC_HMAC_AEAD_Encryption::set_associated_data(const uint8_t ad[], size_
    if(use_encrypt_then_mac())
       {
       // AAD hack for EtM
+      // EtM uses ciphertext size instead of plaintext size for AEAD input
       const uint16_t pt_size = make_uint16(assoc_data()[11], assoc_data()[12]);
       const uint16_t enc_size = static_cast<uint16_t>(round_up(iv_size() + pt_size + 1, block_size()));
       assoc_data()[11] = get_byte<uint16_t>(0, enc_size);
@@ -150,12 +151,36 @@ void TLS_CBC_HMAC_AEAD_Encryption::set_associated_data(const uint8_t ad[], size_
       }
    }
 
-void TLS_CBC_HMAC_AEAD_Encryption::cbc_encrypt_record(uint8_t buf[], size_t buf_size)
+void TLS_CBC_HMAC_AEAD_Encryption::cbc_encrypt_record(
+   secure_vector<uint8_t>& buffer, size_t offset, size_t padding_length)
    {
+   // We always do short padding:
+   BOTAN_ASSERT_NOMSG(padding_length <= 16);
+
+   buffer.resize(buffer.size() + padding_length);
+
+   const uint8_t padding_val = static_cast<uint8_t>(padding_length - 1);
+
+   CT::poison(&padding_val, 1);
+   CT::poison(&padding_length, 1);
+   CT::poison(buffer.data(), buffer.size());
+
+   const size_t last_block_starts = buffer.size() - block_size();
+   const size_t padding_starts = buffer.size() - padding_length;
+   for(size_t i = last_block_starts; i != buffer.size(); ++i)
+      {
+      auto add_padding = CT::Mask<uint8_t>(CT::Mask<size_t>::is_gte(i, padding_starts));
+      buffer[i] = add_padding.select(padding_val, buffer[i]);
+      }
+
+   CT::unpoison(padding_val);
+   CT::unpoison(padding_length);
+   CT::unpoison(buffer.data(), buffer.size());
+
    cbc().start(cbc_state());
-   cbc().process(buf, buf_size);
+   cbc().process(&buffer[offset], buffer.size() - offset);
 
-   cbc_state().assign(buf + buf_size - block_size(), buf + buf_size);
+   cbc_state().assign(buffer.data() + (buffer.size() - block_size()), buffer.data() + buffer.size());
    }
 
 size_t TLS_CBC_HMAC_AEAD_Encryption::output_length(size_t input_length) const
@@ -167,18 +192,19 @@ size_t TLS_CBC_HMAC_AEAD_Encryption::output_length(size_t input_length) const
 void TLS_CBC_HMAC_AEAD_Encryption::finish(secure_vector<uint8_t>& buffer, size_t offset)
    {
    update(buffer, offset);
-   buffer.resize(offset); // truncate, leaving just header
-   const size_t header_size = offset;
 
-   buffer.insert(buffer.end(), msg().begin(), msg().end());
+   const size_t msg_size = msg().size();
 
-   const size_t input_size = msg().size() + 1 + (use_encrypt_then_mac() ? 0 : tag_size());
+   const size_t input_size = msg_size + 1 + (use_encrypt_then_mac() ? 0 : tag_size());
    const size_t enc_size = round_up(input_size, block_size());
-   const size_t pad_val = enc_size - input_size;
-   const size_t buf_size = enc_size + (use_encrypt_then_mac() ? tag_size() : 0);
+   BOTAN_DEBUG_ASSERT(enc_size % block_size() == 0);
+
+   const uint8_t padding_val = static_cast<uint8_t>(enc_size - input_size);
+   const size_t padding_length = static_cast<size_t>(padding_val) + 1;
 
-   BOTAN_ASSERT(enc_size % block_size() == 0,
-                "Buffer is an even multiple of block size");
+   buffer.reserve(offset + msg_size + padding_length + tag_size());
+   buffer.resize(offset + msg_size);
+   copy_mem(&buffer[offset], msg().data(), msg_size);
 
    mac().update(assoc_data());
 
@@ -189,25 +215,17 @@ void TLS_CBC_HMAC_AEAD_Encryption::finish(secure_vector<uint8_t>& buffer, size_t
          mac().update(cbc_state());
          }
 
-      for(size_t i = 0; i != pad_val + 1; ++i)
-         buffer.push_back(static_cast<uint8_t>(pad_val));
-      cbc_encrypt_record(&buffer[header_size], enc_size);
+      cbc_encrypt_record(buffer, offset, padding_length);
+      mac().update(&buffer[offset], enc_size);
+      buffer.resize(buffer.size() + tag_size());
+      mac().final(&buffer[buffer.size() - tag_size()]);
       }
-
-   // EtM also uses ciphertext size instead of plaintext size for AEAD input
-   const uint8_t* mac_input = (use_encrypt_then_mac() ? &buffer[header_size] : msg().data());
-   const size_t mac_input_len = (use_encrypt_then_mac() ? enc_size : msg().size());
-
-   mac().update(mac_input, mac_input_len);
-
-   buffer.resize(buffer.size() + tag_size());
-   mac().final(&buffer[buffer.size() - tag_size()]);
-
-   if(use_encrypt_then_mac() == false)
+   else
       {
-      for(size_t i = 0; i != pad_val + 1; ++i)
-         buffer.push_back(static_cast<uint8_t>(pad_val));
-      cbc_encrypt_record(&buffer[header_size], buf_size);
+      mac().update(&buffer[offset], msg_size);
+      buffer.resize(buffer.size() + tag_size());
+      mac().final(&buffer[buffer.size() - tag_size()]);
+      cbc_encrypt_record(buffer, offset, padding_length);
       }
    }
 
diff --git a/src/lib/tls/tls_cbc/tls_cbc.h b/src/lib/tls/tls_cbc/tls_cbc.h
index 284a51391..938714218 100644
--- a/src/lib/tls/tls_cbc/tls_cbc.h
+++ b/src/lib/tls/tls_cbc/tls_cbc.h
@@ -132,7 +132,8 @@ class BOTAN_TEST_API TLS_CBC_HMAC_AEAD_Encryption final : public TLS_CBC_HMAC_AE
 
       void finish(secure_vector<uint8_t>& final_block, size_t offset = 0) override;
    private:
-      void cbc_encrypt_record(uint8_t record_contents[], size_t record_len);
+      void cbc_encrypt_record(secure_vector<uint8_t>& buffer, size_t offset,
+                              size_t padding_length);
    };
 
 /**
diff --git a/src/lib/utils/ct_utils.cpp b/src/lib/utils/ct_utils.cpp
index 029c54065..cbcecfc28 100644
--- a/src/lib/utils/ct_utils.cpp
+++ b/src/lib/utils/ct_utils.cpp
@@ -51,13 +51,14 @@ secure_vector<uint8_t> copy_output(CT::Mask<uint8_t> bad_input,
 
    bad_input.if_set_zero_out(output.data(), output.size());
 
+   CT::unpoison(output.data(), output.size());
+   CT::unpoison(output_bytes);
+
    /*
    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;
    }