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);