Repository: randombit/botan (cpp)

Issue:
Invalid BER decoding of OIDs
Hi, we've found an issue with Botan's BER decoding of OIDs.

The byte sequence `0x06 0x02 0x79 0x01` should yield the OID `2.41.1`. However, Botan decodes it as `3.1.1`. _Please note_ that `3.1.1` is explicitly forbidden by the standard (see [ITU-T X.660 Annex A.2](https://www.itu.int/rec/T-REC-X.660/en)). 

According to the standard, the first "byte" is encoded by multiplying the first _object identifier component_ by 40 and adding the second _object identifier component_: `2 * 40 + 41 = 121 (0x79)` (see [ITU-T X.690 Section 8.19.4](https://www.itu.int/ITU-T/studygroups/com17/languages/X.690-0207.pdf)). When decoding this byte, Botan interprets this as `3 * 40 + 1`. For arc `0` and `1` only subidentifiers up to `39` are allowed (they couldn't be distinguished otherwise) (see [ITU-T X.660 Section 7.6](https://www.itu.int/rec/T-REC-X.660/en)). For arc `2`, there's no such limitation.

Furthermore, Botan does treat the first byte as a single byte. That is another issuer: The valid OID [`2.999.1234`](http://oid-info.com/get/2.999) cannot be encoded/decoded by Botan. For this to work, Botan must use the same _variable length encoding_ (bit 8 set to 1) for the first "byte" (see [ITU-T X.690 Section 8.19.2](https://www.itu.int/ITU-T/studygroups/com17/languages/X.690-0207.pdf)).

Helpful Links:
- https://misc.daniel-marschall.de/asn.1/oid-converter/online.php
- https://misc.daniel-marschall.de/asn.1/oid_facts.html

Pull request description:
Fix several bugs relating to OID encoding and decoding
The handling for OID encoding did not correctly handle OIDs that begin with 2.x where x >= 40.

Fixes #4023

Patch:
diff --git a/src/cli/asn1.cpp b/src/cli/asn1.cpp
index 1b9154844..e72b35548 100644
--- a/src/cli/asn1.cpp
+++ b/src/cli/asn1.cpp
@@ -102,7 +102,7 @@ class OID_Info final : public Command {
             }
 
             return;
-         } catch(Botan::Decoding_Error&) {}
+         } catch(Botan::Exception&) {}
 
          // This throws if the string is not known
          Botan::OID oid = Botan::OID::from_string(oid_str);
diff --git a/src/lib/asn1/asn1_obj.h b/src/lib/asn1/asn1_obj.h
index 8a5b70bd3..889b88226 100644
--- a/src/lib/asn1/asn1_obj.h
+++ b/src/lib/asn1/asn1_obj.h
@@ -12,6 +12,7 @@
 #include <chrono>
 #include <iosfwd>
 #include <optional>
+#include <span>
 #include <string>
 #include <string_view>
 #include <unordered_map>
@@ -151,6 +152,8 @@ class BOTAN_PUBLIC_API(2, 0) BER_Object final {
 
       size_t length() const { return m_value.size(); }
 
+      std::span<const uint8_t> data() const { return std::span{m_value}; }
+
       void assert_is_a(ASN1_Type type_tag, ASN1_Class class_tag, std::string_view descr = "object") const;
 
       bool is_a(ASN1_Type type_tag, ASN1_Class class_tag) const;
@@ -219,23 +222,21 @@ class BOTAN_PUBLIC_API(2, 0) OID final : public ASN1_Object {
 
       /**
       * Construct an OID from a string.
-      * @param str a string in the form "a.b.c" etc., where a,b,c are numbers
+      * @param str a string in the form "a.b.c" etc., where a,b,c are integers
+      *
+      * Note: it is currently required that each integer fit into 32 bits
       */
       explicit OID(std::string_view str);
 
       /**
       * Initialize an OID from a sequence of integer values
       */
-      explicit OID(std::initializer_list<uint32_t> init) : m_id(init) {
-         BOTAN_ARG_CHECK(m_id.size() > 2 && m_id[0] <= 2 && (m_id[0] != 2 || m_id[1] <= 39), "Invalid OID");
-      }
+      explicit OID(std::initializer_list<uint32_t> init);
 
       /**
       * Initialize an OID from a vector of integer values
       */
-      explicit OID(std::vector<uint32_t>&& init) : m_id(init) {
-         BOTAN_ARG_CHECK(m_id.size() > 2 && m_id[0] <= 2 && (m_id[0] != 2 || m_id[1] <= 39), "Invalid OID");
-      }
+      BOTAN_DEPRECATED("Use another contructor") explicit OID(std::vector<uint32_t>&& init);
 
       /**
       * Construct an OID from a string.
@@ -268,15 +269,7 @@ class BOTAN_PUBLIC_API(2, 0) OID final : public ASN1_Object {
       * Find out whether this OID has a value
       * @return true is this OID has a value
       */
-      bool has_value() const { return (m_id.empty() == false); }
-
-      /**
-      * Get this OID as list (vector) of its components.
-      * @return vector representing this OID
-      */
-      const std::vector<uint32_t>& get_components() const { return m_id; }
-
-      const std::vector<uint32_t>& get_id() const { return get_components(); }
+      bool has_value() const { return !empty(); }
 
       /**
       * Get this OID as a dotted-decimal string
@@ -308,14 +301,28 @@ class BOTAN_PUBLIC_API(2, 0) OID final : public ASN1_Object {
       */
       bool operator==(const OID& other) const { return m_id == other.m_id; }
 
-   private:
-      std::unordered_map<std::string, std::string> load_oid2str_map();
-      std::unordered_map<std::string, OID> load_str2oid_map();
+      /**
+      * Get this OID as list (vector) of its components.
+      * @return vector representing this OID
+      */
+      BOTAN_DEPRECATED("Do not access the integer values, use eg to_string")
+      const std::vector<uint32_t>& get_components() const {
+         return m_id;
+      }
+
+      BOTAN_DEPRECATED("Do not access the integer values, use eg to_string")
+      const std::vector<uint32_t>& get_id() const {
+         return m_id;
+      }
 
+   private:
       std::vector<uint32_t> m_id;
 };
 
-std::ostream& operator<<(std::ostream& out, const OID& oid);
+inline std::ostream& operator<<(std::ostream& out, const OID& oid) {
+   out << oid.to_string();
+   return out;
+}
 
 /**
 * Compare two OIDs.
diff --git a/src/lib/asn1/asn1_oid.cpp b/src/lib/asn1/asn1_oid.cpp
index 4b0d0dbd5..56f10d29b 100644
--- a/src/lib/asn1/asn1_oid.cpp
+++ b/src/lib/asn1/asn1_oid.cpp
@@ -1,6 +1,6 @@
 /*
 * ASN.1 OID
-* (C) 1999-2007 Jack Lloyd
+* (C) 1999-2007,2024 Jack Lloyd
 *
 * Botan is released under the Simplified BSD License (see license.txt)
 */
@@ -11,15 +11,27 @@
 #include <botan/der_enc.h>
 #include <botan/internal/bit_ops.h>
 #include <botan/internal/fmt.h>
+#include <botan/internal/int_utils.h>
 #include <botan/internal/oid_map.h>
 #include <botan/internal/parsing.h>
+#include <botan/internal/stl_util.h>
 #include <algorithm>
+#include <span>
 #include <sstream>
 
 namespace Botan {
 
 namespace {
 
+void oid_valid_check(std::span<const uint32_t> oid) {
+   BOTAN_ARG_CHECK(oid.size() >= 2, "OID too short to be valid");
+   BOTAN_ARG_CHECK(oid[0] <= 2, "OID root out of range");
+   BOTAN_ARG_CHECK(oid[1] <= 39 || oid[0] == 2, "OID second arc too large");
+   // This last is a limitation of using 32 bit integers when decoding
+   // not a limitation of ASN.1 object identifiers in general
+   BOTAN_ARG_CHECK(oid[1] <= 0xFFFFFFAF, "OID second arc too large");
+}
+
 // returns empty on invalid
 std::vector<uint32_t> parse_oid_str(std::string_view oid) {
    try {
@@ -43,8 +55,8 @@ std::vector<uint32_t> parse_oid_str(std::string_view oid) {
       }
 
       return oid_elems;
-   } catch(Invalid_Argument&)  // thrown by to_u32bit
-   {
+   } catch(Invalid_Argument&) {
+      // thrown by to_u32bit
       return std::vector<uint32_t>();
    }
 }
@@ -81,24 +93,29 @@ OID OID::from_string(std::string_view str) {
       return o;
    }
 
-   std::vector<uint32_t> raw = parse_oid_str(str);
-
-   if(!raw.empty()) {
-      return OID(std::move(raw));
-   }
+   // Try to parse as a dotted decimal
+   try {
+      return OID(str);
+   } catch(...) {}
 
    throw Lookup_Error(fmt("No OID associated with name '{}'", str));
 }
 
+OID::OID(std::initializer_list<uint32_t> init) : m_id(init) {
+   oid_valid_check(m_id);
+}
+
+OID::OID(std::vector<uint32_t>&& init) : m_id(std::move(init)) {
+   oid_valid_check(m_id);
+}
+
 /*
 * ASN.1 OID Constructor
 */
 OID::OID(std::string_view oid_str) {
    if(!oid_str.empty()) {
       m_id = parse_oid_str(oid_str);
-      if(m_id.size() < 2 || m_id[0] > 2 || (m_id[0] < 2 && m_id[1] > 39)) {
-         throw Decoding_Error(fmt("Invalid OID '{}'", oid_str));
-      }
+      oid_valid_check(m_id);
    }
 }
 
@@ -107,7 +124,15 @@ OID::OID(std::string_view oid_str) {
 */
 std::string OID::to_string() const {
    std::ostringstream out;
-   out << (*this);
+
+   for(size_t i = 0; i != m_id.size(); ++i) {
+      // avoid locale issues with integer formatting
+      out << std::to_string(m_id[i]);
+      if(i != m_id.size() - 1) {
+         out << ".";
+      }
+   }
+
    return out.str();
 }
 
@@ -137,20 +162,6 @@ bool operator<(const OID& a, const OID& b) {
    return std::lexicographical_compare(oid1.begin(), oid1.end(), oid2.begin(), oid2.end());
 }
 
-std::ostream& operator<<(std::ostream& out, const OID& oid) {
-   const auto& val = oid.get_components();
-
-   for(size_t i = 0; i != val.size(); ++i) {
-      // avoid locale issues with integer formatting
-      out << std::to_string(val[i]);
-      if(i != val.size() - 1) {
-         out << ".";
-      }
-   }
-
-   return out;
-}
-
 /*
 * DER encode an OBJECT IDENTIFIER
 */
@@ -159,28 +170,33 @@ void OID::encode_into(DER_Encoder& der) const {
       throw Invalid_Argument("OID::encode_into: OID is invalid");
    }
 
-   std::vector<uint8_t> encoding;
-
-   if(m_id[0] > 2 || m_id[1] >= 40) {
-      throw Encoding_Error("Invalid OID prefix, cannot encode");
-   }
-
-   encoding.push_back(static_cast<uint8_t>(40 * m_id[0] + m_id[1]));
-
-   for(size_t i = 2; i != m_id.size(); ++i) {
-      if(m_id[i] == 0) {
-         encoding.push_back(0);
+   auto append = [](std::vector<uint8_t>& encoding, uint32_t z) {
+      if(z <= 0x7F) {
+         encoding.push_back(static_cast<uint8_t>(z));
       } else {
-         size_t blocks = high_bit(m_id[i]) + 6;
-         blocks = (blocks - (blocks % 7)) / 7;
+         size_t z7 = (high_bit(z) + 7 - 1) / 7;
 
-         BOTAN_ASSERT(blocks > 0, "Math works");
+         for(size_t j = 0; j != z7; ++j) {
+            uint8_t zp = static_cast<uint8_t>(z >> (7 * (z7 - j - 1)) & 0x7F);
 
-         for(size_t j = 0; j != blocks - 1; ++j) {
-            encoding.push_back(0x80 | ((m_id[i] >> 7 * (blocks - j - 1)) & 0x7F));
+            if(j != z7 - 1) {
+               zp |= 0x80;
+            }
+
+            encoding.push_back(zp);
          }
-         encoding.push_back(m_id[i] & 0x7F);
       }
+   };
+
+   std::vector<uint8_t> encoding;
+
+   // We know 40 * root can't overflow because root is between 0 and 2
+   auto first = BOTAN_ASSERT_IS_SOME(checked_add(40 * m_id[0], m_id[1]));
+
+   append(encoding, first);
+
+   for(size_t i = 2; i != m_id.size(); ++i) {
+      append(encoding, m_id[i]);
    }
    der.add_object(ASN1_Type::ObjectId, ASN1_Class::Universal, encoding);
 }
@@ -194,35 +210,75 @@ void OID::decode_from(BER_Decoder& decoder) {
       throw BER_Bad_Tag("Error decoding OID, unknown tag", obj.tagging());
    }
 
-   const size_t length = obj.length();
-   const uint8_t* bits = obj.bits();
-
-   if(length < 2 && !(length == 1 && bits[0] == 0)) {
+   if(obj.length() == 0) {
       throw BER_Decoding_Error("OID encoding is too short");
    }
 
-   m_id.clear();
-   m_id.push_back(bits[0] / 40);
-   m_id.push_back(bits[0] % 40);
+   auto consume = [](BufferSlicer& data) -> uint32_t {
+      BOTAN_ASSERT_NOMSG(!data.empty());
+      uint32_t b = data.take_byte();
 
-   size_t i = 0;
-   while(i != length - 1) {
-      uint32_t component = 0;
-      while(i != length - 1) {
-         ++i;
+      if(b > 0x7F) {
+         b &= 0x7F;
 
-         if(component >> (32 - 7)) {
-            throw Decoding_Error("OID component overflow");
+         // Even BER requires that the OID have minimal length, ie that
+         // the first byte of a multibyte encoding cannot be zero
+         // See X.690 section 8.19.2
+         if(b == 0) {
+            throw Decoding_Error("Leading zero byte in multibyte OID encoding");
          }
 
-         component = (component << 7) + (bits[i] & 0x7F);
+         while(true) {
+            if(data.empty()) {
+               throw Decoding_Error("Truncated OID value");
+            }
+
+            const uint8_t next = data.take_byte();
+            const bool more = (next & 0x80);
+            const uint8_t value = next & 0x7F;
 
-         if(!(bits[i] & 0x80)) {
-            break;
+            if((b >> (32 - 7)) != 0) {
+               throw Decoding_Error("OID component overflow");
+            }
+
+            b = (b << 7) | value;
+
+            if(!more) {
+               break;
+            }
          }
       }
-      m_id.push_back(component);
+
+      return b;
+   };
+
+   BufferSlicer data(obj.data());
+   std::vector<uint32_t> parts;
+   while(!data.empty()) {
+      const uint32_t comp = consume(data);
+
+      if(parts.empty()) {
+         // divide into root and second arc
+
+         const uint32_t root_arc = [](uint32_t b0) -> uint32_t {
+            if(b0 < 40) {
+               return 0;
+            } else if(b0 < 80) {
+               return 1;
+            } else {
+               return 2;
+            }
+         }(comp);
+
+         parts.push_back(root_arc);
+         BOTAN_ASSERT_NOMSG(comp >= 40 * root_arc);
+         parts.push_back(comp - 40 * root_arc);
+      } else {
+         parts.push_back(comp);
+      }
    }
+
+   m_id = parts;
 }
 
 }  // namespace Botan


Test patch:
diff --git a/src/tests/data/asn1_oid.vec b/src/tests/data/asn1_oid.vec
new file mode 100644
index 000000000..c997c4369
--- /dev/null
+++ b/src/tests/data/asn1_oid.vec
@@ -0,0 +1,62 @@
+
+# Generated using OpenSSL
+
+[Valid]
+OID = 1.2.3.4
+DER = 06032A0304
+
+OID = 1.39.0.0.0.1
+DER = 06054F00000001
+
+OID = 1.39.0.0.0.1.20000000
+DER = 06094F0000000189C4DA00
+
+OID = 1.39.0.0.0.1.4294967295.1.4294967295
+DER = 06104F000000018FFFFFFF7F018FFFFFFF7F
+
+OID = 1.2
+DER = 06012A
+
+OID = 0.9.0.0
+DER = 0603090000
+
+OID = 1.37.1.0
+DER = 06034D0100
+
+OID = 1.39
+DER = 06014F
+
+OID = 0.1
+DER = 060101
+
+OID = 0.1.0
+DER = 06020100
+
+OID = 0.0.0
+DER = 06020000
+
+OID = 2.40.0
+DER = 06027800
+
+# GH 4023
+OID = 2.41.1
+DER = 06027901
+
+OID = 2.999.1234
+DER = 060488378952
+
+OID = 2.168.0
+DER = 0603817800
+
+OID = 2.48.0
+DER = 0603810000
+
+OID = 2.127.128.129.255
+DER = 0608814F81008101817F
+
+# Maximum 2.<x> we can accept while decoding
+OID = 2.4294967215.0.4294967215
+DER = 060B8FFFFFFF7F008FFFFFFF2F
+
+OID = 2.4294967215.0.4294967295
+DER = 060B8FFFFFFF7F008FFFFFFF7F
diff --git a/src/tests/data/asn1_oid_invalid.vec b/src/tests/data/asn1_oid_invalid.vec
new file mode 100644
index 000000000..8a28850b9
--- /dev/null
+++ b/src/tests/data/asn1_oid_invalid.vec
@@ -0,0 +1,34 @@
+
+# Wrong tag
+DER = 050100
+
+# Empty OID
+DER = 0600
+
+# Leading zero byte in multibyte encoding
+DER = 0603500180
+
+# Truncated
+DER = 060350018101
+
+# Multibyte encoding that doesn't end with high bit cleared
+DER = 060450018181
+
+# 2.1.4294967296 - this is valid, we just can't decode it due to 32 bit limbs
+DER = 0606519080808000
+
+# 2.4294967216 - this is valid, we just can't decode it due to 32 bit limbs
+DER = 06059080808000
+
+# From https://misc.daniel-marschall.de/asn.1/oid_facts.html
+
+DER = 060000
+DER = 068000
+DER = 06FF00
+DER = 080100
+DER = 06070180808080807F
+DER = 06028001
+DER = 0602807F
+
+# BUG: we accept constructed encoding of an OID, but should not
+#DER = 06800000
diff --git a/src/tests/test_oid.cpp b/src/tests/test_oid.cpp
index a08676272..ad6bfb69d 100644
--- a/src/tests/test_oid.cpp
+++ b/src/tests/test_oid.cpp
@@ -1,6 +1,6 @@
 /*
 * (C) 2016 Daniel Neus, Rohde & Schwarz Cybersecurity
-*     2023 Jack Lloyd
+*     2023,2024 Jack Lloyd
 *
 * Botan is released under the Simplified BSD License (see license.txt)
 */
@@ -9,6 +9,8 @@
 
 #if defined(BOTAN_HAS_ASN1)
    #include <botan/asn1_obj.h>
+   #include <botan/ber_dec.h>
+   #include <botan/der_enc.h>
    #include <botan/oids.h>
 #endif
 
@@ -135,6 +137,68 @@ class OID_Tests final : public Test {
 
 BOTAN_REGISTER_TEST("asn1", "oid", OID_Tests);
 
+class OID_Encoding_Tests : public Text_Based_Test {
+   public:
+      OID_Encoding_Tests() : Text_Based_Test("asn1_oid.vec", "OID,DER") {}
+
+      Test::Result run_one_test(const std::string&, const VarMap& vars) override {
+         const auto oid_str = vars.get_req_str("OID");
+         const auto expected_der = vars.get_req_bin("DER");
+
+         Test::Result result("OID DER encode/decode");
+
+         const Botan::OID oid(oid_str);
+
+         try {
+            std::vector<uint8_t> der;
+            Botan::DER_Encoder enc(der);
+            enc.encode(oid);
+            result.test_eq("Encoding correct", der, expected_der);
+         } catch(std::exception& e) {
+            result.test_failure("Encoding OID failed", e.what());
+         }
+
+         try {
+            Botan::BER_Decoder dec(expected_der);
+            Botan::OID dec_oid;
+            dec.decode(dec_oid);
+            dec.verify_end();
+            result.test_eq("Decoding OID correct", dec_oid.to_string(), oid_str);
+         } catch(std::exception& e) {
+            result.test_failure("Decoding OID failed", e.what());
+         }
+
+         return result;
+      }
+};
+
+BOTAN_REGISTER_TEST("asn1", "oid_enc", OID_Encoding_Tests);
+
+class OID_Invalid_Encoding_Tests : public Text_Based_Test {
+   public:
+      OID_Invalid_Encoding_Tests() : Text_Based_Test("asn1_oid_invalid.vec", "DER") {}
+
+      Test::Result run_one_test(const std::string&, const VarMap& vars) override {
+         const auto test_der = vars.get_req_bin("DER");
+
+         Test::Result result("OID DER decode invalid");
+
+         try {
+            Botan::BER_Decoder dec(test_der);
+            Botan::OID oid;
+            dec.decode(oid);
+            dec.verify_end();
+            result.test_failure("Accepted invalid OID encoding", oid.to_string());
+         } catch(Botan::Decoding_Error&) {
+            result.test_success("Rejected invalid OID with Decoding_Error");
+         }
+
+         return result;
+      }
+};
+
+BOTAN_REGISTER_TEST("asn1", "oid_dec_invalid", OID_Invalid_Encoding_Tests);
+
 #endif
 
 }  // namespace