Reimplement OBJ_txt2obj and add a lower-level function.

OBJ_txt2obj is currently implemented using BIGNUMs which is absurd. It
also depends on the giant OID table, which is undesirable. Write a new
one and expose the low-level function so Chromium can use it without the
OID table.

Bug: chromium:706445
Change-Id: I61ff750a914194f8776cb8d81ba5d3eb5eaa3c3d
Reviewed-on: https://boringssl-review.googlesource.com/23364
Commit-Queue: David Benjamin <davidben@google.com>
CQ-Verified: CQ bot account: commit-bot@chromium.org <commit-bot@chromium.org>
Reviewed-by: Steven Valdez <svaldez@google.com>

8 files changed, 191 insertions, 216 deletions

diff --git a/crypto/asn1/a_object.c b/crypto/asn1/a_object.c
index a710add..005e37d 100644
--- a/crypto/asn1/a_object.c
+++ b/crypto/asn1/a_object.c
@@ -87,134 +87,6 @@ int i2d_ASN1_OBJECT(ASN1_OBJECT *a, unsigned char **pp)
     return (objsize);
 }
 
-int a2d_ASN1_OBJECT(unsigned char *out, int olen, const char *buf, int num)
-{
-    int i, first, len = 0, c, use_bn;
-    char ftmp[24], *tmp = ftmp;
-    int tmpsize = sizeof ftmp;
-    const char *p;
-    unsigned long l;
-    BIGNUM *bl = NULL;
-
-    if (num == 0)
-        return (0);
-    else if (num == -1)
-        num = strlen(buf);
-
-    p = buf;
-    c = *(p++);
-    num--;
-    if ((c >= '0') && (c <= '2')) {
-        first = c - '0';
-    } else {
-        OPENSSL_PUT_ERROR(ASN1, ASN1_R_FIRST_NUM_TOO_LARGE);
-        goto err;
-    }
-
-    if (num <= 0) {
-        OPENSSL_PUT_ERROR(ASN1, ASN1_R_MISSING_SECOND_NUMBER);
-        goto err;
-    }
-    c = *(p++);
-    num--;
-    for (;;) {
-        if (num <= 0)
-            break;
-        if ((c != '.') && (c != ' ')) {
-            OPENSSL_PUT_ERROR(ASN1, ASN1_R_INVALID_SEPARATOR);
-            goto err;
-        }
-        l = 0;
-        use_bn = 0;
-        for (;;) {
-            if (num <= 0)
-                break;
-            num--;
-            c = *(p++);
-            if ((c == ' ') || (c == '.'))
-                break;
-            if ((c < '0') || (c > '9')) {
-                OPENSSL_PUT_ERROR(ASN1, ASN1_R_INVALID_DIGIT);
-                goto err;
-            }
-            if (!use_bn && l >= ((ULONG_MAX - 80) / 10L)) {
-                use_bn = 1;
-                if (!bl)
-                    bl = BN_new();
-                if (!bl || !BN_set_word(bl, l))
-                    goto err;
-            }
-            if (use_bn) {
-                if (!BN_mul_word(bl, 10L)
-                    || !BN_add_word(bl, c - '0'))
-                    goto err;
-            } else
-                l = l * 10L + (long)(c - '0');
-        }
-        if (len == 0) {
-            if ((first < 2) && (l >= 40)) {
-                OPENSSL_PUT_ERROR(ASN1, ASN1_R_SECOND_NUMBER_TOO_LARGE);
-                goto err;
-            }
-            if (use_bn) {
-                if (!BN_add_word(bl, first * 40))
-                    goto err;
-            } else
-                l += (long)first *40;
-        }
-        i = 0;
-        if (use_bn) {
-            int blsize;
-            blsize = BN_num_bits(bl);
-            blsize = (blsize + 6) / 7;
-            if (blsize > tmpsize) {
-                if (tmp != ftmp)
-                    OPENSSL_free(tmp);
-                tmpsize = blsize + 32;
-                tmp = OPENSSL_malloc(tmpsize);
-                if (!tmp)
-                    goto err;
-            }
-            while (blsize--) {
-                BN_ULONG t = BN_div_word(bl, 0x80L);
-                if (t == (BN_ULONG)-1)
-                    goto err;
-                tmp[i++] = (unsigned char)t;
-            }
-        } else {
-
-            for (;;) {
-                tmp[i++] = (unsigned char)l & 0x7f;
-                l >>= 7L;
-                if (l == 0L)
-                    break;
-            }
-
-        }
-        if (out != NULL) {
-            if (len + i > olen) {
-                OPENSSL_PUT_ERROR(ASN1, ASN1_R_BUFFER_TOO_SMALL);
-                goto err;
-            }
-            while (--i > 0)
-                out[len++] = tmp[i] | 0x80;
-            out[len++] = tmp[0];
-        } else
-            len += i;
-    }
-    if (tmp != ftmp)
-        OPENSSL_free(tmp);
-    if (bl)
-        BN_free(bl);
-    return (len);
- err:
-    if (tmp != ftmp)
-        OPENSSL_free(tmp);
-    if (bl)
-        BN_free(bl);
-    return (0);
-}
-
 int i2t_ASN1_OBJECT(char *buf, int buf_len, ASN1_OBJECT *a)
 {
     return OBJ_obj2txt(buf, buf_len, a, 0);
diff --git a/crypto/bytestring/bytestring_test.cc b/crypto/bytestring/bytestring_test.cc
index 7e3d453..6ce7035 100644
--- a/crypto/bytestring/bytestring_test.cc
+++ b/crypto/bytestring/bytestring_test.cc
@@ -886,3 +886,57 @@ TEST(CBSTest, BitString) {
               CBS_asn1_bitstring_has_bit(&cbs, test.bit));
   }
 }
+
+TEST(CBBTest, AddOIDFromText) {
+  const struct {
+    const char *in;
+    bool ok;
+    std::vector<uint8_t> out;
+  } kTests[] = {
+      // Some valid values.
+      {"1.2.3.4", true, {0x2a, 0x3, 0x4}},
+      {"1.2.840.113554.4.1.72585",
+       true,
+       {0x2a, 0x86, 0x48, 0x86, 0xf7, 0x12, 0x04, 0x01, 0x84, 0xb7, 0x09}},
+      // Test edge cases around the first component.
+      {"0.39", true, {0x27}},
+      {"0.40", false, {}},
+      {"1.0", true, {0x28}},
+      {"1.39", true, {0x4f}},
+      {"1.40", false, {}},
+      {"2.0", true, {0x50}},
+      {"2.1", true, {0x51}},
+      {"2.40", true, {0x78}},
+      // The empty string is not an OID.
+      {"", false, {}},
+      // No empty components.
+      {".1.2.3.4.5", false, {}},
+      {"1..2.3.4.5", false, {}},
+      {"1.2.3.4.5.", false, {}},
+      // There must be at least two components.
+      {"1", false, {}},
+      // No extra leading zeros.
+      {"00.1.2.3.4", false, {}},
+      {"01.1.2.3.4", false, {}},
+      // Check for overflow.
+      {"1.2.4294967295", true, {0x2a, 0x8f, 0xff, 0xff, 0xff, 0x7f}},
+      {"1.2.4294967296", false, {}},
+      // 40*A + B overflows.
+      {"2.4294967215", true, {0x8f, 0xff, 0xff, 0xff, 0x7f}},
+      {"2.4294967216", false, {}},
+  };
+  for (const auto &t : kTests) {
+    SCOPED_TRACE(t.in);
+    bssl::ScopedCBB cbb;
+    ASSERT_TRUE(CBB_init(cbb.get(), 0));
+    int ok = CBB_add_asn1_oid_from_text(cbb.get(), t.in, strlen(t.in));
+    EXPECT_EQ(t.ok, static_cast<bool>(ok));
+    if (ok) {
+      uint8_t *out;
+      size_t len;
+      ASSERT_TRUE(CBB_finish(cbb.get(), &out, &len));
+      bssl::UniquePtr<uint8_t> free_out(out);
+      EXPECT_EQ(Bytes(t.out), Bytes(out, len));
+    }
+  }
+}
diff --git a/crypto/bytestring/cbb.c b/crypto/bytestring/cbb.c
index b1afe7d..5a1c45b 100644
--- a/crypto/bytestring/cbb.c
+++ b/crypto/bytestring/cbb.c
@@ -15,6 +15,7 @@
 #include <openssl/bytestring.h>
 
 #include <assert.h>
+#include <limits.h>
 #include <string.h>
 
 #include <openssl/mem.h>
@@ -328,6 +329,32 @@ int CBB_add_u24_length_prefixed(CBB *cbb, CBB *out_contents) {
   return cbb_add_length_prefixed(cbb, out_contents, 3);
 }
 
+// add_base128_integer encodes |v| as a big-endian base-128 integer where the
+// high bit of each byte indicates where there is more data. This is the
+// encoding used in DER for both high tag number form and OID components.
+static int add_base128_integer(CBB *cbb, uint32_t v) {
+  unsigned len_len = 0;
+  unsigned copy = v;
+  while (copy > 0) {
+    len_len++;
+    copy >>= 7;
+  }
+  if (len_len == 0) {
+    len_len = 1;  // Zero is encoded with one byte.
+  }
+  for (unsigned i = len_len - 1; i < len_len; i--) {
+    uint8_t byte = (v >> (7 * i)) & 0x7f;
+    if (i != 0) {
+      // The high bit denotes whether there is more data.
+      byte |= 0x80;
+    }
+    if (!CBB_add_u8(cbb, byte)) {
+      return 0;
+    }
+  }
+  return 1;
+}
+
 int CBB_add_asn1(CBB *cbb, CBB *out_contents, unsigned tag) {
   if (!CBB_flush(cbb)) {
     return 0;
@@ -338,26 +365,10 @@ int CBB_add_asn1(CBB *cbb, CBB *out_contents, unsigned tag) {
   unsigned tag_number = tag & CBS_ASN1_TAG_NUMBER_MASK;
   if (tag_number >= 0x1f) {
     // Set all the bits in the tag number to signal high tag number form.
-    if (!CBB_add_u8(cbb, tag_bits | 0x1f)) {
+    if (!CBB_add_u8(cbb, tag_bits | 0x1f) ||
+        !add_base128_integer(cbb, tag_number)) {
       return 0;
     }
-
-    unsigned len_len = 0;
-    unsigned copy = tag_number;
-    while (copy > 0) {
-      len_len++;
-      copy >>= 7;
-    }
-    for (unsigned i = len_len - 1; i < len_len; i--) {
-      uint8_t byte = (tag_number >> (7 * i)) & 0x7f;
-      if (i != 0) {
-        // The high bit denotes whether there is more data.
-        byte |= 0x80;
-      }
-      if (!CBB_add_u8(cbb, byte)) {
-        return 0;
-      }
-    }
   } else if (!CBB_add_u8(cbb, tag_bits | tag_number)) {
     return 0;
   }
@@ -492,3 +503,69 @@ int CBB_add_asn1_uint64(CBB *cbb, uint64_t value) {
 
   return CBB_flush(cbb);
 }
+
+// parse_dotted_decimal parses one decimal component from |cbs|, where |cbs| is
+// an OID literal, e.g., "1.2.840.113554.4.1.72585". It consumes both the
+// component and the dot, so |cbs| may be passed into the function again for the
+// next value.
+static int parse_dotted_decimal(CBS *cbs, uint32_t *out) {
+  *out = 0;
+  int seen_digit = 0;
+  for (;;) {
+    // Valid terminators for a component are the end of the string or a
+    // non-terminal dot. If the string ends with a dot, this is not a valid OID
+    // string.
+    uint8_t u;
+    if (!CBS_get_u8(cbs, &u) ||
+        (u == '.' && CBS_len(cbs) > 0)) {
+      break;
+    }
+    if (u < '0' || u > '9' ||
+        // Forbid stray leading zeros.
+        (seen_digit && *out == 0) ||
+        // Check for overflow.
+        *out > UINT32_MAX / 10 ||
+        *out * 10 > UINT32_MAX - (u - '0')) {
+      return 0;
+    }
+    *out = *out * 10 + (u - '0');
+    seen_digit = 1;
+  }
+  // The empty string is not a legal OID component.
+  return seen_digit;
+}
+
+int CBB_add_asn1_oid_from_text(CBB *cbb, const char *text, size_t len) {
+  if (!CBB_flush(cbb)) {
+    return 0;
+  }
+
+  CBS cbs;
+  CBS_init(&cbs, (const uint8_t *)text, len);
+
+  // OIDs must have at least two components.
+  uint32_t a, b;
+  if (!parse_dotted_decimal(&cbs, &a) ||
+      !parse_dotted_decimal(&cbs, &b)) {
+    return 0;
+  }
+
+  // The first component is encoded as 40 * |a| + |b|. This assumes that |a| is
+  // 0, 1, or 2 and that, when it is 0 or 1, |b| is at most 39.
+  if (a > 2 ||
+      (a < 2 && b > 39) ||
+      b > UINT32_MAX - 80 ||
+      !add_base128_integer(cbb, 40 * a + b)) {
+    return 0;
+  }
+
+  // The remaining components are encoded unmodified.
+  while (CBS_len(&cbs) > 0) {
+    if (!parse_dotted_decimal(&cbs, &a) ||
+        !add_base128_integer(cbb, a)) {
+      return 0;
+    }
+  }
+
+  return 1;
+}
diff --git a/crypto/err/obj.errordata b/crypto/err/obj.errordata
index c54435e..be13451 100644
--- a/crypto/err/obj.errordata
+++ b/crypto/err/obj.errordata
@@ -1 +1,2 @@
+OBJ,101,INVALID_OID_STRING
 OBJ,100,UNKNOWN_NID
diff --git a/crypto/obj/obj.c b/crypto/obj/obj.c
index 52e265b..8e1e6b1 100644
--- a/crypto/obj/obj.c
+++ b/crypto/obj/obj.c
@@ -389,16 +389,30 @@ const char *OBJ_nid2ln(int nid) {
   return obj->ln;
 }
 
-ASN1_OBJECT *OBJ_txt2obj(const char *s, int dont_search_names) {
-  int nid = NID_undef;
-  ASN1_OBJECT *op = NULL;
-  unsigned char *buf;
-  unsigned char *p;
-  const unsigned char *bufp;
-  int contents_len, total_len;
+static ASN1_OBJECT *create_object_with_text_oid(int (*get_nid)(void),
+                                                const char *oid,
+                                                const char *short_name,
+                                                const char *long_name) {
+  uint8_t *buf;
+  size_t len;
+  CBB cbb;
+  if (!CBB_init(&cbb, 32) ||
+      !CBB_add_asn1_oid_from_text(&cbb, oid, strlen(oid)) ||
+      !CBB_finish(&cbb, &buf, &len)) {
+    OPENSSL_PUT_ERROR(OBJ, OBJ_R_INVALID_OID_STRING);
+    CBB_cleanup(&cbb);
+    return NULL;
+  }
+
+  ASN1_OBJECT *ret = ASN1_OBJECT_create(get_nid ? get_nid() : NID_undef, buf,
+                                        len, short_name, long_name);
+  OPENSSL_free(buf);
+  return ret;
+}
 
+ASN1_OBJECT *OBJ_txt2obj(const char *s, int dont_search_names) {
   if (!dont_search_names) {
-    nid = OBJ_sn2nid(s);
+    int nid = OBJ_sn2nid(s);
     if (nid == NID_undef) {
       nid = OBJ_ln2nid(s);
     }
@@ -408,31 +422,7 @@ ASN1_OBJECT *OBJ_txt2obj(const char *s, int dont_search_names) {
     }
   }
 
-  // Work out size of content octets
-  contents_len = a2d_ASN1_OBJECT(NULL, 0, s, -1);
-  if (contents_len <= 0) {
-    return NULL;
-  }
-  // Work out total size
-  total_len = ASN1_object_size(0, contents_len, V_ASN1_OBJECT);
-
-  buf = OPENSSL_malloc(total_len);
-  if (buf == NULL) {
-    OPENSSL_PUT_ERROR(OBJ, ERR_R_MALLOC_FAILURE);
-    return NULL;
-  }
-
-  p = buf;
-  // Write out tag+length
-  ASN1_put_object(&p, 0, contents_len, V_ASN1_OBJECT, V_ASN1_UNIVERSAL);
-  // Write out contents
-  a2d_ASN1_OBJECT(p, contents_len, s, -1);
-
-  bufp = buf;
-  op = d2i_ASN1_OBJECT(NULL, &bufp, total_len);
-  OPENSSL_free(buf);
-
-  return op;
+  return create_object_with_text_oid(NULL, s, NULL, NULL);
 }
 
 static int strlcpy_int(char *dst, const char *src, int dst_size) {
@@ -621,41 +611,11 @@ static int obj_add_object(ASN1_OBJECT *obj) {
 }
 
 int OBJ_create(const char *oid, const char *short_name, const char *long_name) {
-  int ret = NID_undef;
-  ASN1_OBJECT *op = NULL;
-  unsigned char *buf = NULL;
-  int len;
-
-  len = a2d_ASN1_OBJECT(NULL, 0, oid, -1);
-  if (len <= 0) {
-    goto err;
-  }
-
-  buf = OPENSSL_malloc(len);
-  if (buf == NULL) {
-    OPENSSL_PUT_ERROR(OBJ, ERR_R_MALLOC_FAILURE);
-    goto err;
-  }
-
-  len = a2d_ASN1_OBJECT(buf, len, oid, -1);
-  if (len == 0) {
-    goto err;
-  }
-
-  op = (ASN1_OBJECT *)ASN1_OBJECT_create(obj_next_nid(), buf, len, short_name,
-                                         long_name);
-  if (op == NULL) {
-    goto err;
-  }
-
-  if (obj_add_object(op)) {
-    ret = op->nid;
+  ASN1_OBJECT *op =
+      create_object_with_text_oid(obj_next_nid, oid, short_name, long_name);
+  if (op == NULL ||
+      !obj_add_object(op)) {
+    return NID_undef;
   }
-  op = NULL;
-
-err:
-  ASN1_OBJECT_free(op);
-  OPENSSL_free(buf);
-
-  return ret;
+  return op->nid;
 }
diff --git a/include/openssl/asn1.h b/include/openssl/asn1.h
index 2ef4c97..5c8bf4c 100644
--- a/include/openssl/asn1.h
+++ b/include/openssl/asn1.h
@@ -737,7 +737,6 @@ OPENSSL_EXPORT int i2a_ASN1_OBJECT(BIO *bp,ASN1_OBJECT *a);
 OPENSSL_EXPORT int i2a_ASN1_STRING(BIO *bp, ASN1_STRING *a, int type);
 OPENSSL_EXPORT int i2t_ASN1_OBJECT(char *buf,int buf_len,ASN1_OBJECT *a);
 
-OPENSSL_EXPORT int a2d_ASN1_OBJECT(unsigned char *out,int olen, const char *buf, int num);
 OPENSSL_EXPORT ASN1_OBJECT *ASN1_OBJECT_create(int nid, unsigned char *data,int len, const char *sn, const char *ln);
 
 OPENSSL_EXPORT int ASN1_INTEGER_set(ASN1_INTEGER *a, long v);
diff --git a/include/openssl/bytestring.h b/include/openssl/bytestring.h
index 3906809..abf8885 100644
--- a/include/openssl/bytestring.h
+++ b/include/openssl/bytestring.h
@@ -443,6 +443,17 @@ OPENSSL_EXPORT void CBB_discard_child(CBB *cbb);
 // error.
 OPENSSL_EXPORT int CBB_add_asn1_uint64(CBB *cbb, uint64_t value);
 
+// CBB_add_asn1_oid_from_text decodes |len| bytes from |text| as an ASCII OID
+// representation, e.g. "1.2.840.113554.4.1.72585", and writes the DER-encoded
+// contents to |cbb|. It returns one on success and zero on malloc failure or if
+// |text| was invalid. It does not include the OBJECT IDENTIFER framing, only
+// the element's contents.
+//
+// This function considers OID strings with components which do not fit in a
+// |uint32_t| to be invalid.
+OPENSSL_EXPORT int CBB_add_asn1_oid_from_text(CBB *cbb, const char *text,
+                                              size_t len);
+
 
 #if defined(__cplusplus)
 }  // extern C
diff --git a/include/openssl/obj.h b/include/openssl/obj.h
index 2bdc3b7..374658e 100644
--- a/include/openssl/obj.h
+++ b/include/openssl/obj.h
@@ -228,5 +228,6 @@ OPENSSL_EXPORT void OBJ_NAME_do_all(int type, void (*callback)(const OBJ_NAME *,
 #endif
 
 #define OBJ_R_UNKNOWN_NID 100
+#define OBJ_R_INVALID_OID_STRING 101
 
 #endif  // OPENSSL_HEADER_OBJ_H