Fix BIT STRING comparison in ASN1_STRING_cmp.
The comparison should notice differences in bit count.
Update-Note: ASN1_STRING_cmp no longer incorrectly treats BIT STRINGs
with different padding bits as equal.
Bug: 446
Change-Id: I22b3fcc5d369540d029ca234e9b3b02402cec4c3
Reviewed-on: https://boringssl-review.googlesource.com/c/boringssl/+/49928
Reviewed-by: Adam Langley <agl@google.com>
Commit-Queue: David Benjamin <davidben@google.com>
diff --git a/crypto/asn1/a_bitstr.c b/crypto/asn1/a_bitstr.c
index d45a73e..7ce8cca 100644
--- a/crypto/asn1/a_bitstr.c
+++ b/crypto/asn1/a_bitstr.c
@@ -63,6 +63,7 @@
#include <openssl/mem.h>
#include "../internal.h"
+#include "internal.h"
int ASN1_BIT_STRING_set(ASN1_BIT_STRING *x, const unsigned char *d, int len)
@@ -70,8 +71,8 @@
return ASN1_STRING_set(x, d, len);
}
-static int asn1_bit_string_length(const ASN1_BIT_STRING *str,
- uint8_t *out_padding_bits) {
+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.
@@ -79,8 +80,8 @@
return len;
}
- // TODO(davidben): If we move this logic to |ASN1_BIT_STRING_set_bit|, can
- // we remove this representation?
+ // TODO(https://crbug.com/boringssl/447): 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--;
}
diff --git a/crypto/asn1/asn1_lib.c b/crypto/asn1/asn1_lib.c
index b13a82a..9def017 100644
--- a/crypto/asn1/asn1_lib.c
+++ b/crypto/asn1/asn1_lib.c
@@ -64,6 +64,7 @@
#include <openssl/mem.h>
#include "../internal.h"
+#include "internal.h"
/* Cross-module errors from crypto/x509/i2d_pr.c. */
@@ -406,17 +407,44 @@
int ASN1_STRING_cmp(const ASN1_STRING *a, const ASN1_STRING *b)
{
- int i;
+ /* Capture padding bits and implicit truncation in BIT STRINGs. */
+ int a_length = a->length, b_length = b->length;
+ uint8_t a_padding = 0, b_padding = 0;
+ if (a->type == V_ASN1_BIT_STRING) {
+ a_length = asn1_bit_string_length(a, &a_padding);
+ }
+ if (b->type == V_ASN1_BIT_STRING) {
+ b_length = asn1_bit_string_length(b, &b_padding);
+ }
- i = (a->length - b->length);
- if (i == 0) {
- i = OPENSSL_memcmp(a->data, b->data, a->length);
- if (i == 0)
- return (a->type - b->type);
- else
- return (i);
- } else
- return (i);
+ if (a_length < b_length) {
+ return -1;
+ }
+ if (a_length > b_length) {
+ return 1;
+ }
+ /* In a BIT STRING, the number of bits is 8 * length - padding. Invert this
+ * comparison so we compare by lengths. */
+ if (a_padding > b_padding) {
+ return -1;
+ }
+ if (a_padding < b_padding) {
+ return 1;
+ }
+
+ int ret = OPENSSL_memcmp(a->data, b->data, a_length);
+ if (ret != 0) {
+ return ret;
+ }
+
+ /* Comparing the type first is more natural, but this matches OpenSSL. */
+ if (a->type < b->type) {
+ return -1;
+ }
+ if (a->type > b->type) {
+ return 1;
+ }
+ return 0;
}
int ASN1_STRING_length(const ASN1_STRING *str)
diff --git a/crypto/asn1/asn1_test.cc b/crypto/asn1/asn1_test.cc
index cd47d2b..bb2b0a8 100644
--- a/crypto/asn1/asn1_test.cc
+++ b/crypto/asn1/asn1_test.cc
@@ -1478,6 +1478,115 @@
EXPECT_FALSE(val);
}
+TEST(ASN1Test, StringCmp) {
+ struct Input {
+ int type;
+ std::vector<uint8_t> data;
+ int flags;
+ bool equals_previous;
+ };
+ // kInputs is a list of |ASN1_STRING| parameters, in sorted order. The input
+ // should be sorted by bit length, then data, then type.
+ const Input kInputs[] = {
+ {V_ASN1_BIT_STRING, {}, ASN1_STRING_FLAG_BITS_LEFT | 0, false},
+ {V_ASN1_BIT_STRING, {}, 0, true},
+ // When |ASN1_STRING_FLAG_BITS_LEFT| is unset, BIT STRINGs implicitly
+ // drop trailing zeros.
+ {V_ASN1_BIT_STRING, {0x00, 0x00, 0x00, 0x00}, 0, true},
+
+ {V_ASN1_OCTET_STRING, {}, 0, false},
+ {V_ASN1_UTF8STRING, {}, 0, false},
+
+ // BIT STRINGs with padding bits (i.e. not part of the actual value) are
+ // shorter and thus sort earlier:
+ // 1-bit inputs.
+ {V_ASN1_BIT_STRING, {0x00}, ASN1_STRING_FLAG_BITS_LEFT | 7, false},
+ {V_ASN1_BIT_STRING, {0x80}, ASN1_STRING_FLAG_BITS_LEFT | 7, false},
+ // 2-bit inputs.
+ {V_ASN1_BIT_STRING, {0x00}, ASN1_STRING_FLAG_BITS_LEFT | 6, false},
+ {V_ASN1_BIT_STRING, {0xc0}, ASN1_STRING_FLAG_BITS_LEFT | 6, false},
+ // 3-bit inputs.
+ {V_ASN1_BIT_STRING, {0x00}, ASN1_STRING_FLAG_BITS_LEFT | 5, false},
+ {V_ASN1_BIT_STRING, {0xe0}, ASN1_STRING_FLAG_BITS_LEFT | 5, false},
+ // 4-bit inputs.
+ {V_ASN1_BIT_STRING, {0xf0}, ASN1_STRING_FLAG_BITS_LEFT | 4, false},
+ {V_ASN1_BIT_STRING, {0xf0}, 0, true}, // 4 trailing zeros dropped.
+ {V_ASN1_BIT_STRING, {0xf0, 0x00}, 0, true}, // 12 trailing zeros dropped.
+ // 5-bit inputs.
+ {V_ASN1_BIT_STRING, {0x00}, ASN1_STRING_FLAG_BITS_LEFT | 3, false},
+ {V_ASN1_BIT_STRING, {0xf0}, ASN1_STRING_FLAG_BITS_LEFT | 3, false},
+ {V_ASN1_BIT_STRING, {0xf8}, ASN1_STRING_FLAG_BITS_LEFT | 3, false},
+ // 6-bit inputs.
+ {V_ASN1_BIT_STRING, {0x00}, ASN1_STRING_FLAG_BITS_LEFT | 2, false},
+ {V_ASN1_BIT_STRING, {0xf0}, ASN1_STRING_FLAG_BITS_LEFT | 2, false},
+ {V_ASN1_BIT_STRING, {0xfc}, ASN1_STRING_FLAG_BITS_LEFT | 2, false},
+ // 7-bit inputs.
+ {V_ASN1_BIT_STRING, {0x00}, ASN1_STRING_FLAG_BITS_LEFT | 1, false},
+ {V_ASN1_BIT_STRING, {0xf0}, ASN1_STRING_FLAG_BITS_LEFT | 1, false},
+ {V_ASN1_BIT_STRING, {0xfe}, ASN1_STRING_FLAG_BITS_LEFT | 1, false},
+
+ // 8-bit inputs.
+ {V_ASN1_BIT_STRING, {0x00}, ASN1_STRING_FLAG_BITS_LEFT | 0, false},
+ {V_ASN1_OCTET_STRING, {0x00}, 0, false},
+ {V_ASN1_UTF8STRING, {0x00}, 0, false},
+
+ {V_ASN1_BIT_STRING, {0x80}, ASN1_STRING_FLAG_BITS_LEFT | 0, false},
+ {V_ASN1_OCTET_STRING, {0x80}, 0, false},
+ {V_ASN1_UTF8STRING, {0x80}, 0, false},
+
+ {V_ASN1_BIT_STRING, {0xff}, ASN1_STRING_FLAG_BITS_LEFT | 0, false},
+ {V_ASN1_BIT_STRING, {0xff}, 0, true}, // No trailing zeros to drop.
+ {V_ASN1_OCTET_STRING, {0xff}, 0, false},
+ {V_ASN1_UTF8STRING, {0xff}, 0, false},
+
+ // Bytes are compared lexicographically.
+ {V_ASN1_BIT_STRING, {0x00, 0x00}, ASN1_STRING_FLAG_BITS_LEFT | 0, false},
+ {V_ASN1_OCTET_STRING, {0x00, 0x00}, 0, false},
+ {V_ASN1_UTF8STRING, {0x00, 0x00}, 0, false},
+
+ {V_ASN1_BIT_STRING, {0x00, 0xff}, ASN1_STRING_FLAG_BITS_LEFT | 0, false},
+ {V_ASN1_OCTET_STRING, {0x00, 0xff}, 0, false},
+ {V_ASN1_UTF8STRING, {0x00, 0xff}, 0, false},
+
+ {V_ASN1_BIT_STRING, {0xff, 0x00}, ASN1_STRING_FLAG_BITS_LEFT | 0, false},
+ {V_ASN1_OCTET_STRING, {0xff, 0x00}, 0, false},
+ {V_ASN1_UTF8STRING, {0xff, 0x00}, 0, false},
+ };
+ std::vector<bssl::UniquePtr<ASN1_STRING>> strs;
+ strs.reserve(OPENSSL_ARRAY_SIZE(kInputs));
+ for (const auto &input : kInputs) {
+ strs.emplace_back(ASN1_STRING_type_new(input.type));
+ ASSERT_TRUE(strs.back());
+ ASSERT_TRUE(ASN1_STRING_set(strs.back().get(), input.data.data(),
+ input.data.size()));
+ strs.back()->flags = input.flags;
+ }
+
+ for (size_t i = 0; i < strs.size(); i++) {
+ SCOPED_TRACE(i);
+ bool expect_equal = true;
+ for (size_t j = i; j < strs.size(); j++) {
+ SCOPED_TRACE(j);
+ if (j > i && !kInputs[j].equals_previous) {
+ expect_equal = false;
+ }
+
+ const int cmp_i_j = ASN1_STRING_cmp(strs[i].get(), strs[j].get());
+ const int cmp_j_i = ASN1_STRING_cmp(strs[j].get(), strs[i].get());
+ if (expect_equal) {
+ EXPECT_EQ(cmp_i_j, 0);
+ EXPECT_EQ(cmp_j_i, 0);
+ } else if (i < j) {
+ EXPECT_LT(cmp_i_j, 0);
+ EXPECT_GT(cmp_j_i, 0);
+ } else {
+ EXPECT_GT(cmp_i_j, 0);
+ EXPECT_LT(cmp_j_i, 0);
+ }
+ }
+ }
+}
+
// 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/asn1/internal.h b/crypto/asn1/internal.h
index dcb6fcf..5731499 100644
--- a/crypto/asn1/internal.h
+++ b/crypto/asn1/internal.h
@@ -175,6 +175,14 @@
* ASN.1 PrintableString, and zero otherwise. */
int asn1_is_printable(uint32_t value);
+/* asn1_bit_string_length returns the number of bytes in |str| and sets
+ * |*out_padding_bits| to the number of padding bits.
+ *
+ * This function should be used instead of |ASN1_STRING_length| to correctly
+ * handle the non-|ASN1_STRING_FLAG_BITS_LEFT| case. */
+int asn1_bit_string_length(const ASN1_BIT_STRING *str,
+ uint8_t *out_padding_bits);
+
typedef struct {
int nid;
long minsize;
diff --git a/include/openssl/asn1.h b/include/openssl/asn1.h
index 0f12a5b..8e8fa9d 100644
--- a/include/openssl/asn1.h
+++ b/include/openssl/asn1.h
@@ -503,13 +503,8 @@
// suitable for sorting, callers should not rely on the exact order when |a|
// and |b| are different types.
//
-// If |a| or |b| are BIT STRINGs, this function does not compare the
-// |ASN1_STRING_FLAG_BITS_LEFT| flags. Additionally, if |a| and |b| are
-// INTEGERs, this comparison does not order the values numerically. For a
-// numerical comparison, use |ASN1_INTEGER_cmp|.
-//
-// TODO(https://crbug.com/boringssl/446): The BIT STRING comparison seems like a
-// bug. Fix it?
+// Note that, if |a| and |b| are INTEGERs, this comparison does not order the
+// values numerically. For a numerical comparison, use |ASN1_INTEGER_cmp|.
OPENSSL_EXPORT int ASN1_STRING_cmp(const ASN1_STRING *a, const ASN1_STRING *b);
// ASN1_STRING_set sets the contents of |str| to a copy of |len| bytes from
@@ -735,7 +730,7 @@
// {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.
+// strings. The padding bits in the |ASN1_STRING| data must be zero.
// ASN1_BIT_STRING_new calls |ASN1_STRING_type_new| with |V_ASN1_BIT_STRING|.
OPENSSL_EXPORT ASN1_BIT_STRING *ASN1_BIT_STRING_new(void);
