Repository: randombit/botan
Pull request #3924 (2024-02-27 14:57:49)

Backport/FIX: Access Violation in OCB
This is a back port of #3814, in response to [the reminder](https://github.com/randombit/botan/issues/3812#issuecomment-1966248869) by @ni4. Sorry, again, for that.

Anyway, it turns out, that this bug was actually exposed by [this patch during the 3.x development](https://github.com/randombit/botan/commit/510a8318e9596b795700681dcd9828f03c5e3265#diff-6b0a60b5ffc4d50b4acf24238f3502c6d6d2d31a6f2bf42b29f4be11178ce413). It reduced the allowed update granularity of the OCB mode, making it much easier to provoke a bogus state of OCB.

Albeit more contrived, its still possible to create an example to hit the access violation in 2.19.4.


Patch:
diff --git a/src/lib/modes/aead/ocb/ocb.cpp b/src/lib/modes/aead/ocb/ocb.cpp
index 6c1620329..9270f119c 100644
--- a/src/lib/modes/aead/ocb/ocb.cpp
+++ b/src/lib/modes/aead/ocb/ocb.cpp
@@ -24,6 +24,17 @@ class L_computer final
          m_L_star.resize(m_BS);
          cipher.encrypt(m_L_star);
          m_L_dollar = poly_double(star());
+
+         // Preallocate the m_L vector to the maximum expected size to avoid
+         // re-allocations during runtime. This had caused a use-after-free in
+         // earlier versions, due to references into this buffer becoming stale
+         // in `compute_offset()`, after calling `get()` in the hot path.
+         //
+         // Note, that the list member won't be pre-allocated, so the expected
+         // memory overhead is negligible.
+         //
+         // See also https://github.com/randombit/botan/issues/3812
+         m_L.reserve(31);
          m_L.push_back(poly_double(dollar()));
 
          while(m_L.size() < 8)


Test patch:
diff --git a/src/tests/test_ocb.cpp b/src/tests/test_ocb.cpp
index e2a564a04..9f1691ef1 100644
--- a/src/tests/test_ocb.cpp
+++ b/src/tests/test_ocb.cpp
@@ -13,6 +13,8 @@
    #include <botan/internal/poly_dbl.h>
 #endif
 
+#include <array>
+
 namespace Botan_Tests {
 
 namespace {
@@ -360,6 +362,95 @@ class OCB_Long_KAT_Tests final : public Text_Based_Test
 
 BOTAN_REGISTER_TEST("modes", "ocb_long", OCB_Long_KAT_Tests);
 
+/**
+ * Extremely cheap toy cipher for the OCB regression test for
+ * the issue explained in GitHub #3812.
+ */
+class OCB_Null_Cipher final : public Botan::BlockCipher
+   {
+   public:
+      explicit OCB_Null_Cipher(size_t bs, size_t parallelism) :
+            m_bs(bs), m_parallelism(parallelism) {}
+
+      std::string name() const override { return "OCB_Null_Cipher"; }
+
+      size_t block_size() const override { return m_bs; }
+
+      void clear() override {}
+
+      Botan::BlockCipher* clone() const override { return new OCB_Null_Cipher(m_bs, m_parallelism); }
+
+      void key_schedule(const uint8_t[], size_t) override {}
+
+      Botan::Key_Length_Specification key_spec() const override { return Botan::Key_Length_Specification(m_bs); }
+
+      void encrypt_n(const uint8_t in[], uint8_t out[], size_t blocks) const override
+         {
+         if(in != out)
+            {
+            Botan::copy_mem(out, in, blocks * m_bs);
+            }
+         }
+
+      void decrypt_n(const uint8_t in[], uint8_t out[], size_t blocks) const override
+         {
+         if(in != out)
+            {
+            Botan::copy_mem(out, in, blocks * m_bs); 
+            }
+         }
+
+      size_t parallelism() const override { return m_parallelism; }
+
+   private:
+      size_t m_bs;
+      size_t m_parallelism;
+   };
+
+/**
+ * A regression test for a crash found in OCB in November 2023.
+ * See here for details: https://github.com/randombit/botan/issues/3812
+ */
+Test::Result test_ocb_crash_regression()
+   {
+   Test::Result result("OCB crash regression");
+
+   constexpr size_t cipherparallelism = 12;
+   constexpr size_t blocksize = 16;
+   constexpr size_t tagsize = 8;
+
+   std::array<uint8_t, 8> iv = {0};
+   std::array<uint8_t, 16> key = {0};
+
+   Botan::OCB_Encryption enc(new OCB_Null_Cipher(blocksize, cipherparallelism), tagsize);
+   enc.set_key(key.data(), key.size());
+   enc.start(iv.data(), iv.size());
+
+   // Assumption: L_computer pre-allocates the first 8 buffers and std::vector<>
+   //             has a matching actual capacity of 8.
+   // Assumption: L_computer::compute_offsets() does some loop unrolling if the
+   //             starting block_index is divisible by 4.
+   // Assumption: L_computer::compute_offsets() computes ciph->parallelism() * 4
+   //             blocks at most (48 blocks in our case).
+   //
+   // L_computer::compute_offsets() ran into an access violation when ::get()
+   // had to re-allocate m_L before the last iteration of the unrolled loop.
+   //
+   // We recreate such a situation here:
+   Botan::secure_vector<uint8_t> preamble(blocksize * 240);
+   enc.update(preamble, 0);
+
+   // block_index is now at 240 (which is divisible by 4). When passed another
+   // chunk of 48 blocks, get() would re-allocate m_L after 4 of 12 iterations.
+   // This would have caused the access violation.
+   Botan::secure_vector<uint8_t> killpacket(blocksize * 48);
+   enc.update(killpacket, 0);
+
+   return result;
+   }
+
+BOTAN_REGISTER_TEST_FN("modes", "ocb_lazy_alloc", test_ocb_crash_regression);
+
 #endif
 
 }