Compute ASN.1 BIT STRING sizes more consistently.

OpenSSL's BIT STRING representation has two modes, one where it
implicitly trims trailing zeros and the other where the number of unused
bits is explicitly set. This means logic in ASN1_item_verify, or
elsewhere in callers, that checks flags and ASN1_STRING_length is
inconsistent with i2c_ASN1_BIT_STRING.

Add ASN1_BIT_STRING_num_bytes for code that needs to deal with X.509
using BIT STRING for some fields instead of OCTET STRING. Switch
ASN1_item_verify to it. Some external code does this too, so export it
as public API.

This is mostly a theoretical issue. All parsed BIT STRINGS use explicit
byte strings, and there are no APIs (apart from not-yet-opaquified
structs) to specify the ASN1_STRING in X509, etc., structures. We
intentionally made X509_set1_signature_value, etc., internally construct
the ASN1_STRING. Still having an API is more consistent and helps nudge
callers towards rejecting excess bits when they want bytes.

It may also be worth a public API for consistently accessing the bit
count. I've left it alone for now because I've not seen callers that
need it, and it saves worrying about bytes-to-bits overflows.

This also fixes a bug in the original version of the truncating logic
when the entire string was all zeros, and const-corrects a few
parameters.

Change-Id: I9d29842a3d3264b0cde61ca8cfea07d02177dbc2
Reviewed-on: https://boringssl-review.googlesource.com/c/boringssl/+/48225
Commit-Queue: David Benjamin <davidben@google.com>
Commit-Queue: Adam Langley <agl@google.com>
Reviewed-by: Adam Langley <agl@google.com>
diff --git a/crypto/asn1/a_bitstr.c b/crypto/asn1/a_bitstr.c
index b945cb1..d45a73e 100644
--- a/crypto/asn1/a_bitstr.c
+++ b/crypto/asn1/a_bitstr.c
@@ -65,64 +65,69 @@
 #include "../internal.h"
 
 
-int ASN1_BIT_STRING_set(ASN1_BIT_STRING *x, unsigned char *d, int len)
+int ASN1_BIT_STRING_set(ASN1_BIT_STRING *x, const unsigned char *d, int len)
 {
     return ASN1_STRING_set(x, d, len);
 }
 
+static int asn1_bit_string_length(const ASN1_BIT_STRING *str,
+                                  uint8_t *out_padding_bits) {
+    int len = str->length;
+    if (str->flags & ASN1_STRING_FLAG_BITS_LEFT) {
+        // If the string is already empty, it cannot have padding bits.
+        *out_padding_bits = len == 0 ? 0 : str->flags & 0x07;
+        return len;
+    }
+
+    // TODO(davidben): If we move this logic to |ASN1_BIT_STRING_set_bit|, can
+    // we remove this representation?
+    while (len > 0 && str->data[len - 1] == 0) {
+        len--;
+    }
+    uint8_t padding_bits = 0;
+    if (len > 0) {
+        uint8_t last = str->data[len - 1];
+        assert(last != 0);
+        for (; padding_bits < 7; padding_bits++) {
+            if (last & (1 << padding_bits)) {
+                break;
+            }
+        }
+    }
+    *out_padding_bits = padding_bits;
+    return len;
+}
+
+int ASN1_BIT_STRING_num_bytes(const ASN1_BIT_STRING *str, size_t *out) {
+    uint8_t padding_bits;
+    int len = asn1_bit_string_length(str, &padding_bits);
+    if (padding_bits != 0) {
+        return 0;
+    }
+    *out = len;
+    return 1;
+}
+
 int i2c_ASN1_BIT_STRING(const ASN1_BIT_STRING *a, unsigned char **pp)
 {
-    int ret, j, bits, len;
-    unsigned char *p, *d;
+    if (a == NULL) {
+        return 0;
+    }
 
-    if (a == NULL)
-        return (0);
+    uint8_t bits;
+    int len = asn1_bit_string_length(a, &bits);
+    int ret = 1 + len;
+    if (pp == NULL) {
+        return ret;
+    }
 
-    len = a->length;
-
+    uint8_t *p = *pp;
+    *(p++) = bits;
+    OPENSSL_memcpy(p, a->data, len);
     if (len > 0) {
-        if (a->flags & ASN1_STRING_FLAG_BITS_LEFT) {
-            bits = (int)a->flags & 0x07;
-        } else {
-            for (; len > 0; len--) {
-                if (a->data[len - 1])
-                    break;
-            }
-            j = a->data[len - 1];
-            if (j & 0x01)
-                bits = 0;
-            else if (j & 0x02)
-                bits = 1;
-            else if (j & 0x04)
-                bits = 2;
-            else if (j & 0x08)
-                bits = 3;
-            else if (j & 0x10)
-                bits = 4;
-            else if (j & 0x20)
-                bits = 5;
-            else if (j & 0x40)
-                bits = 6;
-            else if (j & 0x80)
-                bits = 7;
-            else
-                bits = 0;       /* should not happen */
-        }
-    } else
-        bits = 0;
-
-    ret = 1 + len;
-    if (pp == NULL)
-        return (ret);
-
-    p = *pp;
-
-    *(p++) = (unsigned char)bits;
-    d = a->data;
-    OPENSSL_memcpy(p, d, len);
+        p[len - 1] &= (0xff << bits);
+    }
     p += len;
-    if (len > 0)
-        p[-1] &= (0xff << bits);
     *pp = p;
     return (ret);
 }
@@ -251,7 +256,7 @@
  * 'len' is the length of 'flags'.
  */
 int ASN1_BIT_STRING_check(const ASN1_BIT_STRING *a,
-                          unsigned char *flags, int flags_len)
+                          const unsigned char *flags, int flags_len)
 {
     int i, ok;
     /* Check if there is one bit set at all. */
diff --git a/crypto/asn1/asn1_test.cc b/crypto/asn1/asn1_test.cc
index 30d6091..a14a5cc 100644
--- a/crypto/asn1/asn1_test.cc
+++ b/crypto/asn1/asn1_test.cc
@@ -100,20 +100,23 @@
 template <typename T>
 void TestSerialize(T obj, int (*i2d_func)(T a, uint8_t **pp),
                    bssl::Span<const uint8_t> expected) {
-  int len = static_cast<int>(expected.size());
-  ASSERT_EQ(i2d_func(obj, nullptr), len);
+  // Test the allocating version first. It is easiest to debug.
+  uint8_t *ptr = nullptr;
+  int len = i2d_func(obj, &ptr);
+  ASSERT_GT(len, 0);
+  EXPECT_EQ(Bytes(expected), Bytes(ptr, len));
+  OPENSSL_free(ptr);
 
-  std::vector<uint8_t> buf(expected.size());
-  uint8_t *ptr = buf.data();
-  ASSERT_EQ(i2d_func(obj, &ptr), len);
+  len = i2d_func(obj, nullptr);
+  ASSERT_GT(len, 0);
+  EXPECT_EQ(len, static_cast<int>(expected.size()));
+
+  std::vector<uint8_t> buf(len);
+  ptr = buf.data();
+  len = i2d_func(obj, &ptr);
+  ASSERT_EQ(len, static_cast<int>(expected.size()));
   EXPECT_EQ(ptr, buf.data() + buf.size());
   EXPECT_EQ(Bytes(expected), Bytes(buf));
-
-  // Test the allocating version.
-  ptr = nullptr;
-  ASSERT_EQ(i2d_func(obj, &ptr), len);
-  EXPECT_EQ(Bytes(expected), Bytes(ptr, expected.size()));
-  OPENSSL_free(ptr);
 }
 
 TEST(ASN1Test, SerializeObject) {
@@ -238,6 +241,163 @@
   ASN1_OBJECT_free(obj);
 }
 
+TEST(ASN1Test, BitString) {
+  const size_t kNotWholeBytes = static_cast<size_t>(-1);
+  const struct {
+    std::vector<uint8_t> in;
+    size_t num_bytes;
+  } kValidInputs[] = {
+      // Empty bit string
+      {{0x03, 0x01, 0x00}, 0},
+      // 0b1
+      {{0x03, 0x02, 0x07, 0x80}, kNotWholeBytes},
+      // 0b1010
+      {{0x03, 0x02, 0x04, 0xa0}, kNotWholeBytes},
+      // 0b1010101
+      {{0x03, 0x02, 0x01, 0xaa}, kNotWholeBytes},
+      // 0b10101010
+      {{0x03, 0x02, 0x00, 0xaa}, 1},
+      // Bits 0 and 63 are set
+      {{0x03, 0x09, 0x00, 0x80, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x01}, 8},
+      // 64 zero bits
+      {{0x03, 0x09, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00}, 8},
+  };
+  for (const auto &test : kValidInputs) {
+    SCOPED_TRACE(Bytes(test.in));
+    // The input should parse and round-trip correctly.
+    const uint8_t *ptr = test.in.data();
+    bssl::UniquePtr<ASN1_BIT_STRING> val(
+        d2i_ASN1_BIT_STRING(nullptr, &ptr, test.in.size()));
+    ASSERT_TRUE(val);
+    TestSerialize(val.get(), i2d_ASN1_BIT_STRING, test.in);
+
+    // Check the byte count.
+    size_t num_bytes;
+    if (test.num_bytes == kNotWholeBytes) {
+      EXPECT_FALSE(ASN1_BIT_STRING_num_bytes(val.get(), &num_bytes));
+    } else {
+      ASSERT_TRUE(ASN1_BIT_STRING_num_bytes(val.get(), &num_bytes));
+      EXPECT_EQ(num_bytes, test.num_bytes);
+    }
+  }
+
+  const std::vector<uint8_t> kInvalidInputs[] = {
+      // Wrong tag
+      {0x04, 0x01, 0x00},
+      // Missing leading byte
+      {0x03, 0x00},
+      // Leading byte too high
+      {0x03, 0x02, 0x08, 0x00},
+      {0x03, 0x02, 0xff, 0x00},
+      // TODO(https://crbug.com/boringssl/354): Reject these inputs.
+      // Empty bit strings must have a zero leading byte.
+      // {0x03, 0x01, 0x01},
+      // Unused bits must all be zero.
+      // {0x03, 0x02, 0x06, 0xc1 /* 0b11000001 */},
+  };
+  for (const auto &test : kInvalidInputs) {
+    SCOPED_TRACE(Bytes(test));
+    const uint8_t *ptr = test.data();
+    bssl::UniquePtr<ASN1_BIT_STRING> val(
+        d2i_ASN1_BIT_STRING(nullptr, &ptr, test.size()));
+    EXPECT_FALSE(val);
+  }
+}
+
+TEST(ASN1Test, SetBit) {
+  bssl::UniquePtr<ASN1_BIT_STRING> val(ASN1_BIT_STRING_new());
+  ASSERT_TRUE(val);
+  static const uint8_t kBitStringEmpty[] = {0x03, 0x01, 0x00};
+  TestSerialize(val.get(), i2d_ASN1_BIT_STRING, kBitStringEmpty);
+  EXPECT_EQ(0, ASN1_BIT_STRING_get_bit(val.get(), 0));
+  EXPECT_EQ(0, ASN1_BIT_STRING_get_bit(val.get(), 100));
+
+  // Set a few bits via |ASN1_BIT_STRING_set_bit|.
+  ASSERT_TRUE(ASN1_BIT_STRING_set_bit(val.get(), 0, 1));
+  ASSERT_TRUE(ASN1_BIT_STRING_set_bit(val.get(), 1, 1));
+  ASSERT_TRUE(ASN1_BIT_STRING_set_bit(val.get(), 2, 0));
+  ASSERT_TRUE(ASN1_BIT_STRING_set_bit(val.get(), 3, 1));
+  static const uint8_t kBitString1101[] = {0x03, 0x02, 0x04, 0xd0};
+  TestSerialize(val.get(), i2d_ASN1_BIT_STRING, kBitString1101);
+  EXPECT_EQ(1, ASN1_BIT_STRING_get_bit(val.get(), 0));
+  EXPECT_EQ(1, ASN1_BIT_STRING_get_bit(val.get(), 1));
+  EXPECT_EQ(0, ASN1_BIT_STRING_get_bit(val.get(), 2));
+  EXPECT_EQ(1, ASN1_BIT_STRING_get_bit(val.get(), 3));
+  EXPECT_EQ(0, ASN1_BIT_STRING_get_bit(val.get(), 4));
+
+  // Bits that were set may be cleared.
+  ASSERT_TRUE(ASN1_BIT_STRING_set_bit(val.get(), 1, 0));
+  static const uint8_t kBitString1001[] = {0x03, 0x02, 0x04, 0x90};
+  TestSerialize(val.get(), i2d_ASN1_BIT_STRING, kBitString1001);
+  EXPECT_EQ(1, ASN1_BIT_STRING_get_bit(val.get(), 0));
+  EXPECT_EQ(0, ASN1_BIT_STRING_get_bit(val.get(), 1));
+  EXPECT_EQ(0, ASN1_BIT_STRING_get_bit(val.get(), 2));
+  EXPECT_EQ(1, ASN1_BIT_STRING_get_bit(val.get(), 3));
+  EXPECT_EQ(0, ASN1_BIT_STRING_get_bit(val.get(), 4));
+
+  // Clearing trailing bits truncates the string.
+  ASSERT_TRUE(ASN1_BIT_STRING_set_bit(val.get(), 3, 0));
+  static const uint8_t kBitString1[] = {0x03, 0x02, 0x07, 0x80};
+  TestSerialize(val.get(), i2d_ASN1_BIT_STRING, kBitString1);
+  EXPECT_EQ(1, ASN1_BIT_STRING_get_bit(val.get(), 0));
+  EXPECT_EQ(0, ASN1_BIT_STRING_get_bit(val.get(), 1));
+  EXPECT_EQ(0, ASN1_BIT_STRING_get_bit(val.get(), 2));
+  EXPECT_EQ(0, ASN1_BIT_STRING_get_bit(val.get(), 3));
+  EXPECT_EQ(0, ASN1_BIT_STRING_get_bit(val.get(), 4));
+
+  // Bits may be set beyond the end of the string.
+  ASSERT_TRUE(ASN1_BIT_STRING_set_bit(val.get(), 63, 1));
+  static const uint8_t kBitStringLong[] = {0x03, 0x09, 0x00, 0x80, 0x00, 0x00,
+                                           0x00, 0x00, 0x00, 0x00, 0x01};
+  TestSerialize(val.get(), i2d_ASN1_BIT_STRING, kBitStringLong);
+  EXPECT_EQ(1, ASN1_BIT_STRING_get_bit(val.get(), 0));
+  EXPECT_EQ(0, ASN1_BIT_STRING_get_bit(val.get(), 62));
+  EXPECT_EQ(1, ASN1_BIT_STRING_get_bit(val.get(), 63));
+  EXPECT_EQ(0, ASN1_BIT_STRING_get_bit(val.get(), 64));
+
+  // The string can be truncated back down again.
+  ASSERT_TRUE(ASN1_BIT_STRING_set_bit(val.get(), 63, 0));
+  TestSerialize(val.get(), i2d_ASN1_BIT_STRING, kBitString1);
+  EXPECT_EQ(1, ASN1_BIT_STRING_get_bit(val.get(), 0));
+  EXPECT_EQ(0, ASN1_BIT_STRING_get_bit(val.get(), 62));
+  EXPECT_EQ(0, ASN1_BIT_STRING_get_bit(val.get(), 63));
+  EXPECT_EQ(0, ASN1_BIT_STRING_get_bit(val.get(), 64));
+
+  // |ASN1_BIT_STRING_set_bit| also truncates when starting from a parsed
+  // string.
+  const uint8_t *ptr = kBitStringLong;
+  val.reset(d2i_ASN1_BIT_STRING(nullptr, &ptr, sizeof(kBitStringLong)));
+  ASSERT_TRUE(val);
+  TestSerialize(val.get(), i2d_ASN1_BIT_STRING, kBitStringLong);
+  ASSERT_TRUE(ASN1_BIT_STRING_set_bit(val.get(), 63, 0));
+  TestSerialize(val.get(), i2d_ASN1_BIT_STRING, kBitString1);
+  EXPECT_EQ(1, ASN1_BIT_STRING_get_bit(val.get(), 0));
+  EXPECT_EQ(0, ASN1_BIT_STRING_get_bit(val.get(), 62));
+  EXPECT_EQ(0, ASN1_BIT_STRING_get_bit(val.get(), 63));
+  EXPECT_EQ(0, ASN1_BIT_STRING_get_bit(val.get(), 64));
+
+  // A parsed bit string preserves trailing zero bits.
+  static const uint8_t kBitString10010[] = {0x03, 0x02, 0x03, 0x90};
+  ptr = kBitString10010;
+  val.reset(d2i_ASN1_BIT_STRING(nullptr, &ptr, sizeof(kBitString10010)));
+  ASSERT_TRUE(val);
+  TestSerialize(val.get(), i2d_ASN1_BIT_STRING, kBitString10010);
+  // But |ASN1_BIT_STRING_set_bit| will truncate it even if otherwise a no-op.
+  ASSERT_TRUE(ASN1_BIT_STRING_set_bit(val.get(), 0, 1));
+  TestSerialize(val.get(), i2d_ASN1_BIT_STRING, kBitString1001);
+  EXPECT_EQ(1, ASN1_BIT_STRING_get_bit(val.get(), 0));
+  EXPECT_EQ(0, ASN1_BIT_STRING_get_bit(val.get(), 62));
+  EXPECT_EQ(0, ASN1_BIT_STRING_get_bit(val.get(), 63));
+  EXPECT_EQ(0, ASN1_BIT_STRING_get_bit(val.get(), 64));
+
+  // By default, a BIT STRING implicitly truncates trailing zeros.
+  val.reset(ASN1_BIT_STRING_new());
+  ASSERT_TRUE(val);
+  static const uint8_t kZeros[64] = {0};
+  ASSERT_TRUE(ASN1_STRING_set(val.get(), kZeros, sizeof(kZeros)));
+  TestSerialize(val.get(), i2d_ASN1_BIT_STRING, kBitStringEmpty);
+}
+
 // The ASN.1 macros do not work on Windows shared library builds, where usage of
 // |OPENSSL_EXPORT| is a bit stricter.
 #if !defined(OPENSSL_WINDOWS) || !defined(BORINGSSL_SHARED_LIBRARY)
diff --git a/crypto/x509/a_verify.c b/crypto/x509/a_verify.c
index 8587b59..3cda5d0 100644
--- a/crypto/x509/a_verify.c
+++ b/crypto/x509/a_verify.c
@@ -70,22 +70,26 @@
 #include "internal.h"
 
 int ASN1_item_verify(const ASN1_ITEM *it, X509_ALGOR *a,
-                     ASN1_BIT_STRING *signature, void *asn, EVP_PKEY *pkey)
-{
-    EVP_MD_CTX ctx;
-    uint8_t *buf_in = NULL;
-    int ret = 0, inl = 0;
-
+                     const ASN1_BIT_STRING *signature, void *asn,
+                     EVP_PKEY *pkey) {
     if (!pkey) {
         OPENSSL_PUT_ERROR(X509, ERR_R_PASSED_NULL_PARAMETER);
         return 0;
     }
 
-    if (signature->type == V_ASN1_BIT_STRING && signature->flags & 0x7) {
-        OPENSSL_PUT_ERROR(X509, X509_R_INVALID_BIT_STRING_BITS_LEFT);
-        return 0;
+    size_t sig_len;
+    if (signature->type == V_ASN1_BIT_STRING) {
+        if (!ASN1_BIT_STRING_num_bytes(signature, &sig_len)) {
+            OPENSSL_PUT_ERROR(X509, X509_R_INVALID_BIT_STRING_BITS_LEFT);
+            return 0;
+        }
+    } else {
+        sig_len = (size_t)ASN1_STRING_length(signature);
     }
 
+    EVP_MD_CTX ctx;
+    uint8_t *buf_in = NULL;
+    int ret = 0, inl = 0;
     EVP_MD_CTX_init(&ctx);
 
     if (!x509_digest_verify_init(&ctx, a, pkey)) {
@@ -99,7 +103,7 @@
         goto err;
     }
 
-    if (!EVP_DigestVerify(&ctx, signature->data, (size_t)signature->length,
+    if (!EVP_DigestVerify(&ctx, ASN1_STRING_get0_data(signature), sig_len,
                           buf_in, inl)) {
         OPENSSL_PUT_ERROR(X509, ERR_R_EVP_LIB);
         goto err;
diff --git a/include/openssl/asn1.h b/include/openssl/asn1.h
index 0347d0d..fe2f29d 100644
--- a/include/openssl/asn1.h
+++ b/include/openssl/asn1.h
@@ -177,13 +177,7 @@
 // string.
 //
 // When representing a BIT STRING value, the type field is |V_ASN1_BIT_STRING|.
-// The data contains the encoded form of the BIT STRING, including any padding
-// bits added to round to a whole number of bytes, but excluding the leading
-// byte containing the number of padding bits. The number of padding bits is
-// encoded in the flags field. See |ASN1_STRING_FLAG_BITS_LEFT| for details. For
-// example, DER encodes the BIT STRING {1, 0} as {0x06, 0x80 = 0b10_000000}. The
-// |ASN1_STRING| representation has data of {0x80} and flags of
-// ASN1_STRING_FLAG_BITS_LEFT | 6.
+// See bit string documentation below for how the data and flags are used.
 //
 // When representing an INTEGER or ENUMERATED value, the data contains the
 // big-endian encoding of the absolute value of the integer. The sign bit is
@@ -308,8 +302,83 @@
 // |OPENSSL_malloc|.
 OPENSSL_EXPORT void ASN1_STRING_set0(ASN1_STRING *str, void *data, int len);
 
-// TODO(davidben): Pull up and document functions specific to individual string
-// types.
+// TODO(davidben): Expand and document function prototypes generated in macros.
+
+
+// Bit strings.
+//
+// An ASN.1 BIT STRING type represents a string of bits. The string may not
+// necessarily be a whole number of bytes. BIT STRINGs occur in ASN.1 structures
+// in several forms:
+//
+// Some BIT STRINGs represent a bitmask of named bits, such as the X.509 key
+// usage extension in RFC5280, section 4.2.1.3. For such bit strings, DER
+// imposes an additional restriction that trailing zero bits are removed. Some
+// functions like |ASN1_BIT_STRING_set_bit| help in maintaining this.
+//
+// Other BIT STRINGs are arbitrary strings of bits used as identifiers and do
+// not have this constraint, such as the X.509 issuerUniqueID field.
+//
+// Finally, some structures use BIT STRINGs as a container for byte strings. For
+// example, the signatureValue field in X.509 and the subjectPublicKey field in
+// SubjectPublicKeyInfo are defined as BIT STRINGs with a value specific to the
+// AlgorithmIdentifier. While some unknown algorithm could choose to store
+// arbitrary bit strings, all supported algorithms use a byte string, with bit
+// order matching the DER encoding. Callers interpreting a BIT STRING as a byte
+// string should use |ASN1_BIT_STRING_num_bytes| instead of |ASN1_STRING_length|
+// and reject bit strings that are not a whole number of bytes.
+//
+// This library represents BIT STRINGs as |ASN1_STRING|s with type
+// |V_ASN1_BIT_STRING|. The data contains the encoded form of the BIT STRING,
+// including any padding bits added to round to a whole number of bytes, but
+// excluding the leading byte containing the number of padding bits. If
+// |ASN1_STRING_FLAG_BITS_LEFT| is set, the bottom three bits contains the
+// number of padding bits. For example, DER encodes the BIT STRING {1, 0} as
+// {0x06, 0x80 = 0b10_000000}. The |ASN1_STRING| representation has data of
+// {0x80} and flags of ASN1_STRING_FLAG_BITS_LEFT | 6. If
+// |ASN1_STRING_FLAG_BITS_LEFT| is unset, trailing zero bits are implicitly
+// removed. Callers should not rely this representation when constructing bit
+// strings.
+
+// ASN1_BIT_STRING_num_bytes computes the length of |str| in bytes. If |str|'s
+// bit length is a multiple of 8, it sets |*out| to the byte length and returns
+// one. Otherwise, it returns zero.
+//
+// This function may be used with |ASN1_STRING_get0_data| to interpret |str| as
+// a byte string.
+OPENSSL_EXPORT int ASN1_BIT_STRING_num_bytes(const ASN1_BIT_STRING *str,
+                                             size_t *out);
+
+// ASN1_BIT_STRING_set calls |ASN1_STRING_set|. It leaves flags unchanged, so
+// the caller must set the number of unused bits.
+//
+// TODO(davidben): Maybe it should? Wrapping a byte string in a bit string is a
+// common use case.
+OPENSSL_EXPORT int ASN1_BIT_STRING_set(ASN1_BIT_STRING *str,
+                                       const unsigned char *d, int length);
+
+// ASN1_BIT_STRING_set_bit sets bit |n| of |str| to one if |value| is non-zero
+// and zero if |value| is zero, resizing |str| as needed. It then truncates
+// trailing zeros in |str| to align with the DER represention for a bit string
+// with named bits. It returns one on success and zero on error. |n| is indexed
+// beginning from zero.
+OPENSSL_EXPORT int ASN1_BIT_STRING_set_bit(ASN1_BIT_STRING *str, int n,
+                                           int value);
+
+// ASN1_BIT_STRING_get_bit returns one if bit |n| of |a| is in bounds and set,
+// and zero otherwise. |n| is indexed beginning from zero.
+OPENSSL_EXPORT int ASN1_BIT_STRING_get_bit(const ASN1_BIT_STRING *str, int n);
+
+// ASN1_BIT_STRING_check returns one if |str| only contains bits that are set in
+// the |flags_len| bytes pointed by |flags|. Otherwise it returns zero. Bits in
+// |flags| are arranged according to the DER representation, so bit 0
+// corresponds to the MSB of |flags[0]|.
+OPENSSL_EXPORT int ASN1_BIT_STRING_check(const ASN1_BIT_STRING *str,
+                                         const unsigned char *flags,
+                                         int flags_len);
+
+// TODO(davidben): Expand and document function prototypes generated in macros.
+
 
 
 // Arbitrary elements.
@@ -799,13 +868,6 @@
 OPENSSL_EXPORT ASN1_BIT_STRING *c2i_ASN1_BIT_STRING(ASN1_BIT_STRING **a,
                                                     const unsigned char **pp,
                                                     long length);
-OPENSSL_EXPORT int ASN1_BIT_STRING_set(ASN1_BIT_STRING *a, unsigned char *d,
-                                       int length);
-OPENSSL_EXPORT int ASN1_BIT_STRING_set_bit(ASN1_BIT_STRING *a, int n,
-                                           int value);
-OPENSSL_EXPORT int ASN1_BIT_STRING_get_bit(const ASN1_BIT_STRING *a, int n);
-OPENSSL_EXPORT int ASN1_BIT_STRING_check(const ASN1_BIT_STRING *a,
-                                         unsigned char *flags, int flags_len);
 
 OPENSSL_EXPORT int i2d_ASN1_BOOLEAN(int a, unsigned char **pp);
 OPENSSL_EXPORT int d2i_ASN1_BOOLEAN(int *a, const unsigned char **pp,
diff --git a/include/openssl/x509.h b/include/openssl/x509.h
index d06e1c6..97b3ccb 100644
--- a/include/openssl/x509.h
+++ b/include/openssl/x509.h
@@ -1075,8 +1075,8 @@
                                     unsigned int *len);
 
 OPENSSL_EXPORT int ASN1_item_verify(const ASN1_ITEM *it, X509_ALGOR *algor1,
-                                    ASN1_BIT_STRING *signature, void *data,
-                                    EVP_PKEY *pkey);
+                                    const ASN1_BIT_STRING *signature,
+                                    void *data, EVP_PKEY *pkey);
 
 OPENSSL_EXPORT int ASN1_item_sign(const ASN1_ITEM *it, X509_ALGOR *algor1,
                                   X509_ALGOR *algor2,