Repository: randombit/botan
Pull request #3999 (2024-04-10 11:25:54)

Move checked integer arithmetic to int_utils.h

coveralls: 
[![Coverage Status](https://coveralls.io/builds/66826214/badge)](https://coveralls.io/builds/66826214)

coverage: 92.027% (+0.007%) from 92.02%
when pulling **f1e8048fb1af07ef60a4955832cb046c283b9688 on jack/int-utils**
into **846a6aedc9bdfbf1cff043f1cd32c3c261407669 on master**.


Patch:
diff --git a/src/lib/asn1/ber_dec.cpp b/src/lib/asn1/ber_dec.cpp
index f77eecf4d..1b92fc037 100644
--- a/src/lib/asn1/ber_dec.cpp
+++ b/src/lib/asn1/ber_dec.cpp
@@ -8,8 +8,8 @@
 #include <botan/ber_dec.h>
 
 #include <botan/bigint.h>
+#include <botan/internal/int_utils.h>
 #include <botan/internal/loadstor.h>
-#include <botan/internal/safeint.h>
 #include <memory>
 
 namespace Botan {
@@ -128,18 +128,20 @@ size_t find_eoc(DataSource* ber, size_t allow_indef) {
    while(true) {
       ASN1_Type type_tag;
       ASN1_Class class_tag;
-      size_t tag_size = decode_tag(&source, type_tag, class_tag);
+      const size_t tag_size = decode_tag(&source, type_tag, class_tag);
       if(type_tag == ASN1_Type::NoObject) {
          break;
       }
 
       size_t length_size = 0;
-      size_t item_size = decode_length(&source, length_size, allow_indef);
+      const size_t item_size = decode_length(&source, length_size, allow_indef);
       source.discard_next(item_size);
 
-      length = BOTAN_CHECKED_ADD(length, item_size);
-      length = BOTAN_CHECKED_ADD(length, tag_size);
-      length = BOTAN_CHECKED_ADD(length, length_size);
+      if(auto new_len = checked_add(length, item_size, tag_size, length_size)) {
+         length = new_len.value();
+      } else {
+         throw Decoding_Error("Integer overflow while decoding DER");
+      }
 
       if(type_tag == ASN1_Type::Eoc && class_tag == ASN1_Class::Universal) {
          break;
diff --git a/src/lib/compression/compress_utils.cpp b/src/lib/compression/compress_utils.cpp
index eac5add84..cc89beb8c 100644
--- a/src/lib/compression/compress_utils.cpp
+++ b/src/lib/compression/compress_utils.cpp
@@ -10,7 +10,7 @@
 #include <botan/exceptn.h>
 #include <botan/mem_ops.h>
 #include <botan/internal/fmt.h>
-#include <botan/internal/safeint.h>
+#include <botan/internal/int_utils.h>
 #include <cstdlib>
 
 namespace Botan {
@@ -19,7 +19,9 @@ Compression_Error::Compression_Error(const char* func_name, ErrorType type, int
       Exception(fmt("Compression API {} failed with return code {}", func_name, rc)), m_type(type), m_rc(rc) {}
 
 void* Compression_Alloc_Info::do_malloc(size_t n, size_t size) {
-   if(!BOTAN_CHECKED_MUL(n, size).has_value()) [[unlikely]] {
+   // Precheck for integer overflow in the multiplication
+   // before passing to calloc, which may or may not check.
+   if(!checked_mul(n, size)) {
       return nullptr;
    }
 
diff --git a/src/lib/utils/allocator.cpp b/src/lib/utils/allocator.cpp
index 512e830a3..8f624896b 100644
--- a/src/lib/utils/allocator.cpp
+++ b/src/lib/utils/allocator.cpp
@@ -7,7 +7,7 @@
 #include <botan/allocator.h>
 
 #include <botan/mem_ops.h>
-#include <botan/internal/safeint.h>
+#include <botan/internal/int_utils.h>
 #include <cstdlib>
 #include <new>
 
@@ -23,8 +23,7 @@ BOTAN_MALLOC_FN void* allocate_memory(size_t elems, size_t elem_size) {
    }
 
    // Some calloc implementations do not check for overflow (?!?)
-
-   if(!BOTAN_CHECKED_MUL(elems, elem_size).has_value()) {
+   if(!checked_mul(elems, elem_size).has_value()) {
       throw std::bad_alloc();
    }
 
diff --git a/src/lib/utils/info.txt b/src/lib/utils/info.txt
index 11374c0c8..4c4fcc733 100644
--- a/src/lib/utils/info.txt
+++ b/src/lib/utils/info.txt
@@ -35,6 +35,7 @@ ct_utils.h
 donna128.h
 filesystem.h
 fmt.h
+int_utils.h
 loadstor.h
 mul128.h
 os_utils.h
@@ -42,7 +43,6 @@ parsing.h
 prefetch.h
 rotate.h
 rounding.h
-safeint.h
 scan_name.h
 stl_util.h
 timer.h
diff --git a/src/lib/utils/int_utils.h b/src/lib/utils/int_utils.h
new file mode 100644
index 000000000..76e42a881
--- /dev/null
+++ b/src/lib/utils/int_utils.h
@@ -0,0 +1,60 @@
+/*
+* (C) 2024 Jack Lloyd
+*
+* Botan is released under the Simplified BSD License (see license.txt)
+*/
+
+#ifndef BOTAN_INT_UTILS_H_
+#define BOTAN_INT_UTILS_H_
+
+#include <botan/concepts.h>
+#include <botan/types.h>
+#include <limits>
+#include <optional>
+
+namespace Botan {
+
+template <std::unsigned_integral T>
+constexpr inline std::optional<T> checked_add(T a, T b) {
+   const T r = a + b;
+   if(r < a || r < b) {
+      return {};
+   }
+   return r;
+}
+
+template <std::unsigned_integral T, std::unsigned_integral... Ts>
+   requires all_same_v<T, Ts...>
+constexpr inline std::optional<T> checked_add(T a, T b, Ts... rest) {
+   if(auto r = checked_add(a, b)) {
+      return checked_add(r.value(), rest...);
+   } else {
+      return {};
+   }
+}
+
+template <std::unsigned_integral T>
+constexpr inline std::optional<T> checked_mul(T a, T b) {
+   // Multiplication by 1U is a hack to work around C's insane
+   // integer promotion rules.
+   // https://stackoverflow.com/questions/24795651
+   const T r = (1U * a) * b;
+   // If a == 0 then the multiply certainly did not overflow
+   // Otherwise r / a == b unless overflow occured
+   if(a != 0 && r / a != b) {
+      return {};
+   }
+   return r;
+}
+
+template <std::unsigned_integral ReturnT>
+constexpr inline std::optional<ReturnT> checked_cast(std::unsigned_integral auto input) {
+   if(std::numeric_limits<ReturnT>::max() < input) {
+      return {};
+   }
+   return static_cast<ReturnT>(input);
+}
+
+}  // namespace Botan
+
+#endif
diff --git a/src/lib/utils/locking_allocator/locking_allocator.cpp b/src/lib/utils/locking_allocator/locking_allocator.cpp
index 93342f079..ad95547fd 100644
--- a/src/lib/utils/locking_allocator/locking_allocator.cpp
+++ b/src/lib/utils/locking_allocator/locking_allocator.cpp
@@ -7,9 +7,9 @@
 
 #include <botan/internal/locking_allocator.h>
 
+#include <botan/internal/int_utils.h>
 #include <botan/internal/mem_pool.h>
 #include <botan/internal/os_utils.h>
-#include <botan/internal/safeint.h>
 
 namespace Botan {
 
@@ -18,12 +18,12 @@ void* mlock_allocator::allocate(size_t num_elems, size_t elem_size) {
       return nullptr;
    }
 
-   const auto n = BOTAN_CHECKED_MUL(num_elems, elem_size);
-   if(!n.has_value()) {
-      return nullptr;  // overflow!
+   if(auto n = checked_mul(num_elems, elem_size)) {
+      return m_pool->allocate(n.value());
+   } else {
+      // overflow!
+      return nullptr;
    }
-
-   return m_pool->allocate(n.value());
 }
 
 bool mlock_allocator::deallocate(void* p, size_t num_elems, size_t elem_size) noexcept {
@@ -31,16 +31,15 @@ bool mlock_allocator::deallocate(void* p, size_t num_elems, size_t elem_size) no
       return false;
    }
 
-   /*
-   We return nullptr in allocate if there was an overflow, so if an
-   overflow occurs here we know the pointer was not allocated by this pool.
-   */
-   const auto n = BOTAN_CHECKED_MUL(num_elems, elem_size);
-   if(!n.has_value()) {
+   if(auto n = checked_mul(num_elems, elem_size)) {
+      return m_pool->deallocate(p, n.value());
+   } else {
+      /*
+      We return nullptr in allocate if there was an overflow, so if an
+      overflow occurs here we know the pointer was not allocated by this pool.
+      */
       return false;
    }
-
-   return m_pool->deallocate(p, n.value());
 }
 
 mlock_allocator::mlock_allocator() {
diff --git a/src/lib/utils/safeint.h b/src/lib/utils/safeint.h
deleted file mode 100644
index 3fa7547cc..000000000
--- a/src/lib/utils/safeint.h
+++ /dev/null
@@ -1,78 +0,0 @@
-/*
-* Safe(r) Integer Handling
-* (C) 2016 Jack Lloyd
-*
-* Botan is released under the Simplified BSD License (see license.txt)
-*/
-
-#ifndef BOTAN_UTILS_SAFE_INT_H_
-#define BOTAN_UTILS_SAFE_INT_H_
-
-#include <botan/exceptn.h>
-#include <botan/internal/fmt.h>
-#include <optional>
-#include <string_view>
-
-#if defined(_MSC_VER)
-   #include <intsafe.h>
-#endif
-
-namespace Botan {
-
-class Integer_Overflow_Detected final : public Exception {
-   public:
-      Integer_Overflow_Detected(std::string_view file, int line) :
-            Exception(fmt("Integer overflow detected at {}:{}", file, line)) {}
-
-      ErrorType error_type() const noexcept override { return ErrorType::InternalError; }
-};
-
-inline size_t checked_add(size_t x, size_t y, const char* file, int line) {
-#if BOTAN_COMPILER_HAS_BUILTIN(__builtin_add_overflow)
-   size_t z;
-   if(__builtin_add_overflow(x, y, &z)) [[unlikely]]
-#elif defined(_MSC_VER)
-   size_t z;
-   if(SizeTAdd(x, y, &z) != S_OK) [[unlikely]]
-#else
-   size_t z = x + y;
-   if(z < x) [[unlikely]]
-#endif
-   {
-      throw Integer_Overflow_Detected(file, line);
-   }
-   return z;
-}
-
-inline std::optional<size_t> checked_mul(size_t x, size_t y) {
-#if BOTAN_COMPILER_HAS_BUILTIN(__builtin_add_overflow)
-   size_t z;
-   if(__builtin_mul_overflow(x, y, &z)) [[unlikely]]
-#elif defined(_MSC_VER)
-   size_t z;
-   if(SizeTMult(x, y, &z) != S_OK) [[unlikely]]
-#else
-   size_t z = x * y;
-   if(y && z / y != x) [[unlikely]]
-#endif
-   {
-      return std::nullopt;
-   }
-   return z;
-}
-
-template <typename RT, typename AT>
-RT checked_cast_to(AT i) {
-   RT c = static_cast<RT>(i);
-   if(i != static_cast<AT>(c)) {
-      throw Internal_Error("Error during integer conversion");
-   }
-   return c;
-}
-
-#define BOTAN_CHECKED_ADD(x, y) checked_add(x, y, __FILE__, __LINE__)
-#define BOTAN_CHECKED_MUL(x, y) checked_mul(x, y)
-
-}  // namespace Botan
-
-#endif


Test patch:
diff --git a/src/tests/test_utils.cpp b/src/tests/test_utils.cpp
index d3917852f..e82c384d1 100644
--- a/src/tests/test_utils.cpp
+++ b/src/tests/test_utils.cpp
@@ -14,6 +14,7 @@
 #include <botan/internal/cpuid.h>
 #include <botan/internal/ct_utils.h>
 #include <botan/internal/fmt.h>
+#include <botan/internal/int_utils.h>
 #include <botan/internal/loadstor.h>
 #include <botan/internal/parsing.h>
 #include <botan/internal/rounding.h>
@@ -38,6 +39,9 @@ class Utility_Function_Tests final : public Test {
       std::vector<Test::Result> run() override {
          std::vector<Test::Result> results;
 
+         results.push_back(test_checked_add());
+         results.push_back(test_checked_mul());
+         results.push_back(test_checked_cast());
          results.push_back(test_round_up());
          results.push_back(test_loadstore());
          results.push_back(test_loadstore_fallback());
@@ -47,6 +51,82 @@ class Utility_Function_Tests final : public Test {
       }
 
    private:
+      Test::Result test_checked_add() {
+         Test::Result result("checked_add");
+
+         const size_t large = static_cast<size_t>(-5);
+         const size_t zero = 0;
+
+         for(int si = -15; si != 15; ++si) {
+            const size_t i = static_cast<size_t>(si);
+            auto sum1 = Botan::checked_add<size_t>(i, zero, zero, zero, large);
+            auto sum2 = Botan::checked_add<size_t>(large, zero, zero, zero, i);
+
+            result.confirm("checked_add looks at all args", sum1 == sum2);
+
+            if(i < 5) {
+               result.test_eq("checked_add worked", sum1.value(), i + large);
+            } else {
+               result.confirm("checked_add did not return a result", !sum1.has_value());
+            }
+         }
+
+         auto& rng = Test::rng();
+
+         for(size_t i = 0; i != 100; ++i) {
+            const uint16_t x = Botan::make_uint16(rng.next_byte(), rng.next_byte());
+            const uint16_t y = Botan::make_uint16(rng.next_byte(), rng.next_byte());
+
+            const uint32_t ref = static_cast<uint32_t>(x) + y;
+
+            if(auto z = Botan::checked_add(x, y)) {
+               result.test_int_eq("checked_add adds", z.value(), ref);
+            } else {
+               result.confirm("checked_add checks", (ref >> 16) > 0);
+            }
+         }
+
+         return result;
+      }
+
+      Test::Result test_checked_mul() {
+         Test::Result result("checked_mul");
+
+         auto& rng = Test::rng();
+
+         for(size_t i = 0; i != 100; ++i) {
+            const uint16_t x = Botan::make_uint16(rng.next_byte(), rng.next_byte());
+            const uint16_t y = Botan::make_uint16(rng.next_byte(), rng.next_byte());
+
+            const uint32_t ref = static_cast<uint32_t>(x) * y;
+
+            if(auto z = Botan::checked_mul(x, y)) {
+               result.test_int_eq("checked_mul multiplies", z.value(), ref);
+            } else {
+               result.confirm("checked_mul checks", (ref >> 16) > 0);
+            }
+         }
+
+         return result;
+      }
+
+      Test::Result test_checked_cast() {
+         Test::Result result("checked_cast");
+
+         const uint32_t large = static_cast<uint32_t>(-1);
+         const uint32_t is_16_bits = 0x8123;
+         const uint32_t is_8_bits = 0x89;
+
+         result.confirm("checked_cast checks", !Botan::checked_cast<uint16_t>(large).has_value());
+         result.confirm("checked_cast checks", !Botan::checked_cast<uint8_t>(large).has_value());
+
+         result.test_int_eq("checked_cast converts", Botan::checked_cast<uint32_t>(large).value(), large);
+         result.test_int_eq("checked_cast converts", Botan::checked_cast<uint16_t>(is_16_bits).value(), 0x8123);
+         result.test_int_eq("checked_cast converts", Botan::checked_cast<uint8_t>(is_8_bits).value(), 0x89);
+
+         return result;
+      }
+
       Test::Result test_round_up() {
          Test::Result result("Util round_up");