Rewrite the X509_NAME parser The old parser was a mess. It has to deal with X509_NAME using a slightly different in-memory represtation than tasn_dec expects, and it has to populate cached fields. On top of that, the handling of the cache was not thread-safe. It previously worked by first using the tasn_dec machinery to parse a STACK_OF(STACK_OF(X509_NAME_ENTRY)), and then flattening it. Then it makes a *new* STACK_OF(STACK_OF(X509_NAME_ENTRY)) with canonicalized fields. Then it re-encodes that with tasn_enc to save the canonicalized form. Instead of all that, parse with CBS so we don't need an allocated intermediate representation. We can just write it out into the X509_NAME representation as we parse it. For the two cached fields, fix the thread-safety issue by wrapping it in a struct and managing it with an atomic pointer. I had vaguely hoped we could avoid this, but that seems too complicated with the API we've got. When computing the cached encodings, rather than making a new allocated intermediate representation, we can just write a canonicalized encoder and write it straight into a single CBB, so we only have one growable array's worth of buffer. It's faster too! Before: Did 1319499 Parse X.509 certificate operations in 5001015us (263846.2 ops/sec) After: Did 1794529 Parse X.509 certificate operations in 5000632us (358860.4 ops/sec) Subsequent CLs will make the API const-correct, test threading, and embed the X509_NAMEs into the X509 struct. One nuisance: it's hard for an infallible x509_name_init to initialize a STACK_OF(X509_NAME_ENTRY). For now I just made the zero state legal and the add function materializes the STACK_OF on demand. We don't expose the underlying object, so it doesn't matter much. Really we should stop believing in fallible mallocs. Bug: 42290417, 42290269 Change-Id: I0081c75dc06c76c3863eb9418e61262953c9179f Reviewed-on: https://boringssl-review.googlesource.com/c/boringssl/+/81891 Auto-Submit: David Benjamin <davidben@google.com> Commit-Queue: David Benjamin <davidben@google.com> Reviewed-by: Adam Langley <agl@google.com>
diff --git a/crypto/asn1/a_type.cc b/crypto/asn1/a_type.cc index de888f1..b714340 100644 --- a/crypto/asn1/a_type.cc +++ b/crypto/asn1/a_type.cc
@@ -356,10 +356,7 @@ return CBB_add_asn1_bool(out, in->value.boolean != ASN1_BOOLEAN_FALSE); case V_ASN1_INTEGER: case V_ASN1_ENUMERATED: - return asn1_marshal_integer(out, in->value.integer, - static_cast<CBS_ASN1_TAG>(in->type)); case V_ASN1_BIT_STRING: - return asn1_marshal_bit_string(out, in->value.bit_string, /*tag=*/0); case V_ASN1_OCTET_STRING: case V_ASN1_NUMERICSTRING: case V_ASN1_PRINTABLESTRING: @@ -374,14 +371,49 @@ case V_ASN1_UNIVERSALSTRING: case V_ASN1_BMPSTRING: case V_ASN1_UTF8STRING: - return asn1_marshal_octet_string(out, in->value.asn1_string, + case V_ASN1_SEQUENCE: + case V_ASN1_SET: + case V_ASN1_OTHER: + return asn1_marshal_any_string(out, in->value.asn1_string); + default: + // |ASN1_TYPE|s can have type -1 when default-constructed. + OPENSSL_PUT_ERROR(ASN1, ASN1_R_WRONG_TYPE); + return 0; + } +} + +int asn1_marshal_any_string(CBB *out, const ASN1_STRING *in) { + switch (in->type) { + case V_ASN1_INTEGER: + case V_ASN1_NEG_INTEGER: + return asn1_marshal_integer(out, in, CBS_ASN1_INTEGER); + case V_ASN1_ENUMERATED: + case V_ASN1_NEG_ENUMERATED: + return asn1_marshal_integer(out, in, CBS_ASN1_ENUMERATED); + case V_ASN1_BIT_STRING: + return asn1_marshal_bit_string(out, in, /*tag=*/0); + case V_ASN1_OCTET_STRING: + case V_ASN1_NUMERICSTRING: + case V_ASN1_PRINTABLESTRING: + case V_ASN1_T61STRING: + case V_ASN1_VIDEOTEXSTRING: + case V_ASN1_IA5STRING: + case V_ASN1_UTCTIME: + case V_ASN1_GENERALIZEDTIME: + case V_ASN1_GRAPHICSTRING: + case V_ASN1_VISIBLESTRING: + case V_ASN1_GENERALSTRING: + case V_ASN1_UNIVERSALSTRING: + case V_ASN1_BMPSTRING: + case V_ASN1_UTF8STRING: + return asn1_marshal_octet_string(out, in, static_cast<CBS_ASN1_TAG>(in->type)); case V_ASN1_SEQUENCE: case V_ASN1_SET: case V_ASN1_OTHER: // These three types store the whole TLV as contents. - return CBB_add_bytes(out, ASN1_STRING_get0_data(in->value.asn1_string), - ASN1_STRING_length(in->value.asn1_string)); + return CBB_add_bytes(out, ASN1_STRING_get0_data(in), + ASN1_STRING_length(in)); default: // |ASN1_TYPE|s can have type -1 when default-constructed. OPENSSL_PUT_ERROR(ASN1, ASN1_R_WRONG_TYPE);
diff --git a/crypto/asn1/internal.h b/crypto/asn1/internal.h index 2ddabc8..1ab7fa5 100644 --- a/crypto/asn1/internal.h +++ b/crypto/asn1/internal.h
@@ -194,6 +194,10 @@ // result to |out|. It returns one on success and zeron on error. int asn1_marshal_any(CBB *out, const ASN1_TYPE *in); +// asn1_marshal_any_string marshals |in| as a DER-encoded ASN.1 value and writes +// the result to |out|. It returns one on success and zeron on error. +int asn1_marshal_any_string(CBB *out, const ASN1_STRING *in); + // Support structures for the template-based encoder.
diff --git a/crypto/x509/internal.h b/crypto/x509/internal.h index b4d48ca..3bee7cd 100644 --- a/crypto/x509/internal.h +++ b/crypto/x509/internal.h
@@ -52,7 +52,7 @@ struct X509_name_entry_st { ASN1_OBJECT *object; - ASN1_STRING *value; + ASN1_STRING value; int set; } /* X509_NAME_ENTRY */; @@ -60,13 +60,19 @@ // (RFC 5280) and C type is |X509_NAME_ENTRY*|. DECLARE_ASN1_ITEM(X509_NAME_ENTRY) -// we always keep X509_NAMEs in 2 forms. +struct X509_NAME_CACHE { + // canon contains the DER-encoded canonicalized X.509 Name, not including the + // outermost TLV. + uint8_t *canon; + size_t canon_len; + // der contains the DER-encoded X.509 Name, including the outermost TLV. + uint8_t *der; + size_t der_len; +}; + struct X509_name_st { STACK_OF(X509_NAME_ENTRY) *entries; - int modified; // true if 'bytes' needs to be built - BUF_MEM *bytes; - unsigned char *canon_enc; - int canon_enclen; + mutable bssl::Atomic<X509_NAME_CACHE *> cache; } /* X509_NAME */; struct x509_attributes_st { @@ -567,13 +573,19 @@ // TODO(https://crbug.com/boringssl/695): Remove this. int DIST_POINT_set_dpname(DIST_POINT_NAME *dpn, X509_NAME *iname); +void x509_name_init(X509_NAME *name); +void x509_name_cleanup(X509_NAME *name); + +// x509_parse_name parses a DER-encoded, X.509 Name from |cbs| and writes the +// result to |*out|. It returns one on success and zero on error. +int x509_parse_name(CBS *cbs, X509_NAME *out); + // x509_marshal_name marshals |in| as a DER-encoded, X.509 Name and writes the // result to |out|. It returns one on success and zero on error. -// -// TODO(https://crbug.com/boringssl/407): This function should be const and -// thread-safe but is currently neither in some cases, notably if |in| was -// mutated. -int x509_marshal_name(CBB *out, X509_NAME *in); +int x509_marshal_name(CBB *out, const X509_NAME *in); + +const X509_NAME_CACHE *x509_name_get_cache(const X509_NAME *name); +void x509_name_invalidate_cache(X509_NAME *name); void x509_algor_init(X509_ALGOR *alg); void x509_algor_cleanup(X509_ALGOR *alg);
diff --git a/crypto/x509/v3_ncons.cc b/crypto/x509/v3_ncons.cc index 7661ea8..c94bb20 100644 --- a/crypto/x509/v3_ncons.cc +++ b/crypto/x509/v3_ncons.cc
@@ -340,17 +340,19 @@ // subset of the name. static int nc_dn(X509_NAME *nm, X509_NAME *base) { - // Ensure canonical encodings are up to date. - if (nm->modified && i2d_X509_NAME(nm, NULL) < 0) { + const X509_NAME_CACHE *nm_cache = x509_name_get_cache(nm); + if (nm_cache == nullptr) { return X509_V_ERR_OUT_OF_MEM; } - if (base->modified && i2d_X509_NAME(base, NULL) < 0) { + const X509_NAME_CACHE *base_cache = x509_name_get_cache(base); + if (base_cache == nullptr) { return X509_V_ERR_OUT_OF_MEM; } - if (base->canon_enclen > nm->canon_enclen) { + if (base_cache->canon_len > nm_cache->canon_len) { return X509_V_ERR_PERMITTED_VIOLATION; } - if (OPENSSL_memcmp(base->canon_enc, nm->canon_enc, base->canon_enclen)) { + if (OPENSSL_memcmp(base_cache->canon, nm_cache->canon, + base_cache->canon_len)) { return X509_V_ERR_PERMITTED_VIOLATION; } return X509_V_OK;
diff --git a/crypto/x509/x509_cmp.cc b/crypto/x509/x509_cmp.cc index be08ec8..3e5a784 100644 --- a/crypto/x509/x509_cmp.cc +++ b/crypto/x509/x509_cmp.cc
@@ -94,41 +94,39 @@ } int X509_NAME_cmp(const X509_NAME *a, const X509_NAME *b) { - int ret; - - // Ensure canonical encoding is present and up to date - - if (!a->canon_enc || a->modified) { - ret = i2d_X509_NAME((X509_NAME *)a, NULL); - if (ret < 0) { - return -2; - } + const X509_NAME_CACHE *a_cache = x509_name_get_cache(a); + if (a_cache == nullptr) { + return -2; } - - if (!b->canon_enc || b->modified) { - ret = i2d_X509_NAME((X509_NAME *)b, NULL); - if (ret < 0) { - return -2; - } + const X509_NAME_CACHE *b_cache = x509_name_get_cache(b); + if (b_cache == nullptr) { + return -2; } - - ret = a->canon_enclen - b->canon_enclen; - - if (ret) { - return ret; + if (a_cache->canon_len < b_cache->canon_len) { + return -1; } - - return OPENSSL_memcmp(a->canon_enc, b->canon_enc, a->canon_enclen); + if (a_cache->canon_len > b_cache->canon_len) { + return 1; + } + int ret = OPENSSL_memcmp(a_cache->canon, b_cache->canon, a_cache->canon_len); + // Canonicalize the return value so it is even possible to distinguish the + // error case from a < b, though ideally we would not have an error case. + if (ret < 0) { + return -1; + } + if (ret > 0) { + return 1; + } + return 0; } uint32_t X509_NAME_hash(X509_NAME *x) { - // Make sure the X509_NAME structure contains a valid cached encoding. - if (i2d_X509_NAME(x, NULL) < 0) { + const X509_NAME_CACHE *cache = x509_name_get_cache(x); + if (cache == nullptr) { return 0; } - uint8_t md[SHA_DIGEST_LENGTH]; - SHA1(x->canon_enc, x->canon_enclen, md); + SHA1(cache->canon, cache->canon_len, md); return CRYPTO_load_u32_le(md); } @@ -136,13 +134,12 @@ // this is reasonably efficient. uint32_t X509_NAME_hash_old(X509_NAME *x) { - // Make sure the X509_NAME structure contains a valid cached encoding. - if (i2d_X509_NAME(x, NULL) < 0) { + const X509_NAME_CACHE *cache = x509_name_get_cache(x); + if (cache == nullptr) { return 0; } - - uint8_t md[SHA_DIGEST_LENGTH]; - MD5((const uint8_t *)x->bytes->data, x->bytes->length, md); + uint8_t md[MD5_DIGEST_LENGTH]; + MD5(cache->der, cache->der_len, md); return CRYPTO_load_u32_le(md); }
diff --git a/crypto/x509/x509_obj.cc b/crypto/x509/x509_obj.cc index 6eb5df9..66ef386 100644 --- a/crypto/x509/x509_obj.cc +++ b/crypto/x509/x509_obj.cc
@@ -73,13 +73,13 @@ } l1 = strlen(s); - type = ne->value->type; - num = ne->value->length; + type = ne->value.type; + num = ne->value.length; if (num > NAME_ONELINE_MAX) { OPENSSL_PUT_ERROR(X509, X509_R_NAME_TOO_LONG); goto err; } - q = ne->value->data; + q = ne->value.data; if ((type == V_ASN1_GENERALSTRING) && ((num % 4) == 0)) { gs_doit[0] = gs_doit[1] = gs_doit[2] = gs_doit[3] = 0; @@ -130,7 +130,7 @@ p += l1; *(p++) = '='; - q = ne->value->data; + q = ne->value.data; for (j = 0; j < num; j++) { if (!gs_doit[j & 3]) {
diff --git a/crypto/x509/x509name.cc b/crypto/x509/x509name.cc index 8f9792c..72c8883 100644 --- a/crypto/x509/x509name.cc +++ b/crypto/x509/x509name.cc
@@ -130,7 +130,7 @@ STACK_OF(X509_NAME_ENTRY) *sk = name->entries; X509_NAME_ENTRY *ret = sk_X509_NAME_ENTRY_delete(sk, loc); size_t n = sk_X509_NAME_ENTRY_num(sk); - name->modified = 1; + x509_name_invalidate_cache(name); if ((size_t)loc == n) { return ret; } @@ -196,14 +196,17 @@ // guy we are about to stomp on. int X509_NAME_add_entry(X509_NAME *name, const X509_NAME_ENTRY *entry, int loc, int set) { - X509_NAME_ENTRY *new_name = NULL; - int i, inc; - STACK_OF(X509_NAME_ENTRY) *sk; - - if (name == NULL) { + if (name == nullptr) { return 0; } - sk = name->entries; + if (name->entries == nullptr) { + name->entries = sk_X509_NAME_ENTRY_new_null(); + if (name->entries == nullptr) { + return 0; + } + } + + STACK_OF(X509_NAME_ENTRY) *sk = name->entries; int n = (int)sk_X509_NAME_ENTRY_num(sk); if (loc > n) { loc = n; @@ -211,8 +214,8 @@ loc = n; } - inc = (set == 0); - name->modified = 1; + bool inc = set == 0; + x509_name_invalidate_cache(name); if (set == -1) { if (loc == 0) { @@ -222,7 +225,6 @@ set = sk_X509_NAME_ENTRY_value(sk, loc - 1)->set; } } else { // if (set >= 0) - if (loc >= n) { if (loc != 0) { set = sk_X509_NAME_ENTRY_value(sk, loc - 1)->set + 1; @@ -234,25 +236,22 @@ } } - if ((new_name = X509_NAME_ENTRY_dup(entry)) == NULL) { - goto err; + bssl::UniquePtr<X509_NAME_ENTRY> new_entry(X509_NAME_ENTRY_dup(entry)); + if (new_entry == nullptr) { + return 0; } - new_name->set = set; - if (!sk_X509_NAME_ENTRY_insert(sk, new_name, loc)) { - goto err; + new_entry->set = set; + if (!sk_X509_NAME_ENTRY_insert(sk, new_entry.get(), loc)) { + return 0; } + new_entry.release(); // |sk| took ownership. if (inc) { n = (int)sk_X509_NAME_ENTRY_num(sk); - for (i = loc + 1; i < n; i++) { + for (int i = loc + 1; i < n; i++) { sk_X509_NAME_ENTRY_value(sk, i)->set += 1; } } return 1; -err: - if (new_name != NULL) { - X509_NAME_ENTRY_free(new_name); - } - return 0; } X509_NAME_ENTRY *X509_NAME_ENTRY_create_by_txt(X509_NAME_ENTRY **ne, @@ -333,19 +332,18 @@ return 0; } if ((type > 0) && (type & MBSTRING_FLAG)) { - return ASN1_STRING_set_by_NID(&ne->value, bytes, len, type, - OBJ_obj2nid(ne->object)) - ? 1 - : 0; + ASN1_STRING *dst = &ne->value; + return ASN1_STRING_set_by_NID(&dst, bytes, len, type, + OBJ_obj2nid(ne->object)) != nullptr; } if (len < 0) { len = strlen((const char *)bytes); } - if (!ASN1_STRING_set(ne->value, bytes, len)) { + if (!ASN1_STRING_set(&ne->value, bytes, len)) { return 0; } if (type != V_ASN1_UNDEF) { - ne->value->type = type; + ne->value.type = type; } return 1; } @@ -361,5 +359,6 @@ if (ne == NULL) { return NULL; } - return ne->value; + // This function is not const-correct for OpenSSL compatibility. + return const_cast<ASN1_STRING*>(&ne->value); }
diff --git a/crypto/x509/x_name.cc b/crypto/x509/x_name.cc index 7ec83f6..0e80ab4 100644 --- a/crypto/x509/x_name.cc +++ b/crypto/x509/x_name.cc
@@ -13,8 +13,11 @@ // limitations under the License. #include <ctype.h> +#include <limits.h> #include <string.h> +#include <utility> + #include <openssl/asn1.h> #include <openssl/asn1t.h> #include <openssl/buf.h> @@ -23,440 +26,364 @@ #include <openssl/obj.h> #include <openssl/stack.h> #include <openssl/x509.h> -#include <cstdint> #include "../asn1/internal.h" +#include "../bytestring/internal.h" #include "../internal.h" +#include "../mem_internal.h" #include "internal.h" -typedef STACK_OF(X509_NAME_ENTRY) STACK_OF_X509_NAME_ENTRY; -DEFINE_STACK_OF(STACK_OF_X509_NAME_ENTRY) - -// Maximum length of X509_NAME: much larger than anything we should -// ever see in practice. - +// X509_NAME_MAX is the length of the maximum encoded |X509_NAME| we accept. #define X509_NAME_MAX (1024 * 1024) -static int x509_name_encode(X509_NAME *a); -static int x509_name_canon(X509_NAME *a); -static int asn1_string_canon(ASN1_STRING *out, ASN1_STRING *in); -static int i2d_name_canon(STACK_OF(STACK_OF_X509_NAME_ENTRY) *intname, - unsigned char **in); +static int asn1_marshal_string_canon(CBB *cbb, const ASN1_STRING *in); -ASN1_SEQUENCE(X509_NAME_ENTRY) = { - ASN1_SIMPLE(X509_NAME_ENTRY, object, ASN1_OBJECT), - ASN1_SIMPLE(X509_NAME_ENTRY, value, ASN1_ANY_AS_STRING), -} ASN1_SEQUENCE_END(X509_NAME_ENTRY) - -IMPLEMENT_ASN1_ALLOC_FUNCTIONS(X509_NAME_ENTRY) -IMPLEMENT_ASN1_DUP_FUNCTION_const(X509_NAME_ENTRY) - -// For the "Name" type we need a SEQUENCE OF { SET OF X509_NAME_ENTRY } so -// declare two template wrappers for this - -ASN1_ITEM_TEMPLATE(X509_NAME_ENTRIES) = ASN1_EX_TEMPLATE_TYPE(ASN1_TFLG_SET_OF, - 0, RDNS, - X509_NAME_ENTRY) -ASN1_ITEM_TEMPLATE_END(X509_NAME_ENTRIES) - -ASN1_ITEM_TEMPLATE(X509_NAME_INTERNAL) = - ASN1_EX_TEMPLATE_TYPE(ASN1_TFLG_SEQUENCE_OF, 0, Name, X509_NAME_ENTRIES) -ASN1_ITEM_TEMPLATE_END(X509_NAME_INTERNAL) - -// Normally that's where it would end: we'd have two nested STACK structures -// representing the ASN1. Unfortunately X509_NAME uses a completely different -// form and caches encodings so we have to process the internal form and -// convert to the external form. -// -// TODO(crbug.com/42290417): Rewrite all this with |CBS| and |CBB|. - -static int x509_name_ex_new(ASN1_VALUE **val, const ASN1_ITEM *it) { - X509_NAME *ret = NULL; - ret = reinterpret_cast<X509_NAME *>(OPENSSL_malloc(sizeof(X509_NAME))); - if (!ret) { - goto memerr; +X509_NAME_ENTRY *X509_NAME_ENTRY_new(void) { + bssl::UniquePtr<X509_NAME_ENTRY> ret = bssl::MakeUnique<X509_NAME_ENTRY>(); + if (ret == nullptr) { + return nullptr; } - if ((ret->entries = sk_X509_NAME_ENTRY_new_null()) == NULL) { - goto memerr; - } - if ((ret->bytes = BUF_MEM_new()) == NULL) { - goto memerr; - } - ret->canon_enc = NULL; - ret->canon_enclen = 0; - ret->modified = 1; - *val = (ASN1_VALUE *)ret; - return 1; - -memerr: - if (ret) { - if (ret->entries) { - sk_X509_NAME_ENTRY_free(ret->entries); - } - OPENSSL_free(ret); - } - return 0; + ret->object = const_cast<ASN1_OBJECT *>(OBJ_get_undef()); + asn1_string_init(&ret->value, -1); + ret->set = 0; + return ret.release(); } -static void x509_name_ex_free(ASN1_VALUE **pval, const ASN1_ITEM *it) { - X509_NAME *a; - if (!pval || !*pval) { - return; +void X509_NAME_ENTRY_free(X509_NAME_ENTRY *entry) { + if (entry != nullptr) { + ASN1_OBJECT_free(entry->object); + asn1_string_cleanup(&entry->value); + OPENSSL_free(entry); } - a = (X509_NAME *)*pval; - - BUF_MEM_free(a->bytes); - sk_X509_NAME_ENTRY_pop_free(a->entries, X509_NAME_ENTRY_free); - if (a->canon_enc) { - OPENSSL_free(a->canon_enc); - } - OPENSSL_free(a); - *pval = NULL; } -static void local_sk_X509_NAME_ENTRY_free(STACK_OF(X509_NAME_ENTRY) *ne) { - sk_X509_NAME_ENTRY_free(ne); -} - -static void local_sk_X509_NAME_ENTRY_pop_free(STACK_OF(X509_NAME_ENTRY) *ne) { - sk_X509_NAME_ENTRY_pop_free(ne, X509_NAME_ENTRY_free); -} - -static int x509_name_ex_parse(ASN1_VALUE **val, CBS *cbs, const ASN1_ITEM *it, - int opt) { - if (opt && !CBS_peek_asn1_tag(cbs, CBS_ASN1_SEQUENCE)) { - return 1; - } - - CBS elem; - if (!CBS_get_asn1_element(cbs, &elem, CBS_ASN1_SEQUENCE) || - // Bound the size of an X509_NAME we are willing to parse. - CBS_len(&elem) > X509_NAME_MAX) { +static int x509_parse_name_entry(CBS *cbs, X509_NAME_ENTRY *out) { + CBS seq; + if (!CBS_get_asn1(cbs, &seq, CBS_ASN1_SEQUENCE)) { OPENSSL_PUT_ERROR(ASN1, ASN1_R_DECODE_ERROR); return 0; } - - // TODO(crbug.com/42290417): Rewrite the parser and canonicalization code with - // CBS and CBB. For now this calls into the original two-layer d2i code. - long len = static_cast<long>(CBS_len(&elem)); - const unsigned char *p = CBS_data(&elem), *q; - STACK_OF(STACK_OF_X509_NAME_ENTRY) *intname = NULL; - X509_NAME *nm = NULL; - size_t i, j; - STACK_OF(X509_NAME_ENTRY) *entries; - X509_NAME_ENTRY *entry; - q = p; - - // Get internal representation of Name - ASN1_VALUE *intname_val = NULL; - if (ASN1_item_ex_d2i(&intname_val, &p, len, - ASN1_ITEM_rptr(X509_NAME_INTERNAL), /*tag=*/-1, - /*aclass=*/0, /*opt=*/0) <= 0) { + ASN1_OBJECT_free(out->object); + out->object = asn1_parse_object(&seq, /*tag=*/0); + if (out->object == nullptr || // + !asn1_parse_any_as_string(&seq, &out->value) || // + CBS_len(&seq) != 0) { + OPENSSL_PUT_ERROR(ASN1, ASN1_R_DECODE_ERROR); return 0; } - intname = (STACK_OF(STACK_OF_X509_NAME_ENTRY) *)intname_val; - - if (*val) { - x509_name_ex_free(val, NULL); - } - ASN1_VALUE *nm_val = NULL; - if (!x509_name_ex_new(&nm_val, NULL)) { - goto err; - } - nm = (X509_NAME *)nm_val; - // We've decoded it: now cache encoding - if (!BUF_MEM_grow(nm->bytes, p - q)) { - goto err; - } - OPENSSL_memcpy(nm->bytes->data, q, p - q); - - // Convert internal representation to X509_NAME structure - for (i = 0; i < sk_STACK_OF_X509_NAME_ENTRY_num(intname); i++) { - entries = sk_STACK_OF_X509_NAME_ENTRY_value(intname, i); - for (j = 0; j < sk_X509_NAME_ENTRY_num(entries); j++) { - entry = sk_X509_NAME_ENTRY_value(entries, j); - entry->set = (int)i; - if (!sk_X509_NAME_ENTRY_push(nm->entries, entry)) { - goto err; - } - (void)sk_X509_NAME_ENTRY_set(entries, j, NULL); - } - } - if (!x509_name_canon(nm)) { - goto err; - } - sk_STACK_OF_X509_NAME_ENTRY_pop_free(intname, local_sk_X509_NAME_ENTRY_free); - nm->modified = 0; - *val = (ASN1_VALUE *)nm; return 1; -err: - X509_NAME_free(nm); - sk_STACK_OF_X509_NAME_ENTRY_pop_free(intname, - local_sk_X509_NAME_ENTRY_pop_free); - OPENSSL_PUT_ERROR(X509, ERR_R_ASN1_LIB); - return 0; } -static int x509_name_ex_i2d(ASN1_VALUE **val, unsigned char **out, - const ASN1_ITEM *it) { - X509_NAME *a = (X509_NAME *)*val; - if (a->modified && (!x509_name_encode(a) || !x509_name_canon(a))) { - return -1; +static int x509_marshal_name_entry(CBB *cbb, const X509_NAME_ENTRY *entry, + int canonicalize) { + CBB seq; + if (!CBB_add_asn1(cbb, &seq, CBS_ASN1_SEQUENCE) || + !asn1_marshal_object(&seq, entry->object, /*tag=*/0)) { + return 0; } - int ret = a->bytes->length; - if (out != NULL) { - OPENSSL_memcpy(*out, a->bytes->data, ret); - *out += ret; + int ok = canonicalize ? asn1_marshal_string_canon(&seq, &entry->value) + : asn1_marshal_any_string(&seq, &entry->value); + if (!ok) { + return 0; } - return ret; + return CBB_flush(cbb); } -static const ASN1_EXTERN_FUNCS x509_name_ff = { - x509_name_ex_new, x509_name_ex_free, x509_name_ex_parse, x509_name_ex_i2d}; -IMPLEMENT_EXTERN_ASN1(X509_NAME, x509_name_ff) -IMPLEMENT_ASN1_FUNCTIONS(X509_NAME) -IMPLEMENT_ASN1_DUP_FUNCTION(X509_NAME) +static int i2d_x509_name_entry(const X509_NAME_ENTRY *entry, uint8_t **out) { + return bssl::I2DFromCBB(/*initial_capacity=*/16, out, [&](CBB *cbb) -> bool { + return x509_marshal_name_entry(cbb, entry, /*canonicalize=*/0); + }); +} -static int x509_name_encode(X509_NAME *a) { - int len; - unsigned char *p; - STACK_OF(X509_NAME_ENTRY) *entries = NULL; - X509_NAME_ENTRY *entry; - int set = -1; - size_t i; - STACK_OF(STACK_OF_X509_NAME_ENTRY) *intname = - sk_STACK_OF_X509_NAME_ENTRY_new_null(); +IMPLEMENT_EXTERN_ASN1_SIMPLE(X509_NAME_ENTRY, X509_NAME_ENTRY_new, + X509_NAME_ENTRY_free, CBS_ASN1_SEQUENCE, + x509_parse_name_entry, i2d_x509_name_entry) - { - if (!intname) { - goto err; +X509_NAME_ENTRY *X509_NAME_ENTRY_dup(const X509_NAME_ENTRY *entry) { + bssl::ScopedCBB cbb; + if (!CBB_init(cbb.get(), 16) || + !x509_marshal_name_entry(cbb.get(), entry, /*canonicalize=*/0)) { + return nullptr; + } + CBS cbs; + CBS_init(&cbs, CBB_data(cbb.get()), CBB_len(cbb.get())); + bssl::UniquePtr<X509_NAME_ENTRY> copy(X509_NAME_ENTRY_new()); + if (copy == nullptr || !x509_parse_name_entry(&cbs, copy.get())) { + return nullptr; + } + return copy.release(); +} + +static void x509_name_cache_free(X509_NAME_CACHE *cache) { + if (cache != nullptr) { + OPENSSL_free(cache->canon); + OPENSSL_free(cache->der); + OPENSSL_free(cache); + } +} + +void x509_name_init(X509_NAME *name) { + OPENSSL_memset(name, 0, sizeof(X509_NAME)); +} + +void x509_name_cleanup(X509_NAME *name) { + sk_X509_NAME_ENTRY_pop_free(name->entries, X509_NAME_ENTRY_free); + x509_name_cache_free(name->cache.exchange(nullptr)); +} + +X509_NAME *X509_NAME_new(void) { + return static_cast<X509_NAME *>(OPENSSL_zalloc(sizeof(X509_NAME))); +} + +void X509_NAME_free(X509_NAME *name) { + if (name != nullptr) { + x509_name_cleanup(name); + OPENSSL_free(name); + } +} + +int x509_parse_name(CBS *cbs, X509_NAME *out) { + // Reset the old state. + x509_name_cleanup(out); + x509_name_init(out); + + out->entries = sk_X509_NAME_ENTRY_new_null(); + if (out->entries == nullptr) { + return 0; + } + CBS seq, rdn; + if (!CBS_get_asn1(cbs, &seq, CBS_ASN1_SEQUENCE) || + // Bound the size of an X509_NAME we are willing to parse. + CBS_len(&seq) > X509_NAME_MAX) { + OPENSSL_PUT_ERROR(ASN1, ASN1_R_DECODE_ERROR); + return 0; + } + static_assert(X509_NAME_MAX <= INT_MAX, "set may overflow"); + for (int set = 0; CBS_len(&seq) > 0; set++) { + if (!CBS_get_asn1(&seq, &rdn, CBS_ASN1_SET) || // + CBS_len(&rdn) == 0) { + OPENSSL_PUT_ERROR(ASN1, ASN1_R_DECODE_ERROR); + return 0; } - for (i = 0; i < sk_X509_NAME_ENTRY_num(a->entries); i++) { - entry = sk_X509_NAME_ENTRY_value(a->entries, i); - if (entry->set != set) { - entries = sk_X509_NAME_ENTRY_new_null(); - if (!entries) { - goto err; - } - if (!sk_STACK_OF_X509_NAME_ENTRY_push(intname, entries)) { - sk_X509_NAME_ENTRY_free(entries); - goto err; - } - set = entry->set; + while (CBS_len(&rdn) != 0) { + bssl::UniquePtr<X509_NAME_ENTRY> entry(X509_NAME_ENTRY_new()); + if (entry == nullptr || !x509_parse_name_entry(&rdn, entry.get())) { + return 0; } - if (!sk_X509_NAME_ENTRY_push(entries, entry)) { - goto err; + entry->set = set; + if (!bssl::PushToStack(out->entries, std::move(entry))) { + return 0; } } - ASN1_VALUE *intname_val = (ASN1_VALUE *)intname; - len = - ASN1_item_ex_i2d(&intname_val, NULL, ASN1_ITEM_rptr(X509_NAME_INTERNAL), - /*tag=*/-1, /*aclass=*/0); - if (len <= 0) { - goto err; - } - if (!BUF_MEM_grow(a->bytes, len)) { - goto err; - } - p = (unsigned char *)a->bytes->data; - if (ASN1_item_ex_i2d(&intname_val, &p, ASN1_ITEM_rptr(X509_NAME_INTERNAL), - /*tag=*/-1, /*aclass=*/0) <= 0) { - goto err; - } - sk_STACK_OF_X509_NAME_ENTRY_pop_free(intname, - local_sk_X509_NAME_ENTRY_free); - a->modified = 0; + } + + // While we are single-threaded, also fill in the cached state. + return x509_name_get_cache(out) != nullptr; +} + +static int x509_marshal_name_entries(CBB *out, const X509_NAME *name, + int canonicalize) { + if (sk_X509_NAME_ENTRY_num(name->entries) == 0) { return 1; } -err: - sk_STACK_OF_X509_NAME_ENTRY_pop_free(intname, local_sk_X509_NAME_ENTRY_free); - return 0; -} - -// This function generates the canonical encoding of the Name structure. In -// it all strings are converted to UTF8, leading, trailing and multiple -// spaces collapsed, converted to lower case and the leading SEQUENCE header -// removed. In future we could also normalize the UTF8 too. By doing this -// comparison of Name structures can be rapidly perfomed by just using -// OPENSSL_memcmp() of the canonical encoding. By omitting the leading SEQUENCE -// name constraints of type dirName can also be checked with a simple -// OPENSSL_memcmp(). - -static int x509_name_canon(X509_NAME *a) { - unsigned char *p; - STACK_OF(STACK_OF_X509_NAME_ENTRY) *intname = NULL; - STACK_OF(X509_NAME_ENTRY) *entries = NULL; - X509_NAME_ENTRY *entry, *tmpentry = NULL; - int set = -1, ret = 0, len; - size_t i; - - if (a->canon_enc) { - OPENSSL_free(a->canon_enc); - a->canon_enc = NULL; + // Bootstrap the first RDN. + int set = sk_X509_NAME_ENTRY_value(name->entries, 0)->set; + CBB rdn; + if (!CBB_add_asn1(out, &rdn, CBS_ASN1_SET)) { + return 0; } - // Special case: empty X509_NAME => null encoding - if (sk_X509_NAME_ENTRY_num(a->entries) == 0) { - a->canon_enclen = 0; - return 1; - } - intname = sk_STACK_OF_X509_NAME_ENTRY_new_null(); - if (!intname) { - goto err; - } - for (i = 0; i < sk_X509_NAME_ENTRY_num(a->entries); i++) { - entry = sk_X509_NAME_ENTRY_value(a->entries, i); + + for (const X509_NAME_ENTRY *entry : name->entries) { if (entry->set != set) { - entries = sk_X509_NAME_ENTRY_new_null(); - if (!entries) { - goto err; - } - if (!sk_STACK_OF_X509_NAME_ENTRY_push(intname, entries)) { - sk_X509_NAME_ENTRY_free(entries); - goto err; + // Flush the previous RDN and start a new one. + if (!CBB_flush_asn1_set_of(&rdn) || + !CBB_add_asn1(out, &rdn, CBS_ASN1_SET)) { + return 0; } set = entry->set; } - tmpentry = X509_NAME_ENTRY_new(); - if (tmpentry == NULL) { - goto err; - } - tmpentry->object = OBJ_dup(entry->object); - if (!asn1_string_canon(tmpentry->value, entry->value)) { - goto err; - } - if (!sk_X509_NAME_ENTRY_push(entries, tmpentry)) { - goto err; - } - tmpentry = NULL; - } - - // Finally generate encoding - - len = i2d_name_canon(intname, NULL); - if (len < 0) { - goto err; - } - a->canon_enclen = len; - - p = reinterpret_cast<uint8_t *>(OPENSSL_malloc(a->canon_enclen)); - - if (!p) { - goto err; - } - - a->canon_enc = p; - - i2d_name_canon(intname, &p); - - ret = 1; - -err: - - if (tmpentry) { - X509_NAME_ENTRY_free(tmpentry); - } - if (intname) { - sk_STACK_OF_X509_NAME_ENTRY_pop_free(intname, - local_sk_X509_NAME_ENTRY_pop_free); - } - return ret; -} - -// Bitmap of all the types of string that will be canonicalized. - -#define ASN1_MASK_CANON \ - (B_ASN1_UTF8STRING | B_ASN1_BMPSTRING | B_ASN1_UNIVERSALSTRING | \ - B_ASN1_PRINTABLESTRING | B_ASN1_T61STRING | B_ASN1_IA5STRING | \ - B_ASN1_VISIBLESTRING) - -static int asn1_string_canon(ASN1_STRING *out, ASN1_STRING *in) { - unsigned char *to, *from; - int len, i; - - // If type not in bitmask just copy string across - if (!(ASN1_tag2bit(in->type) & ASN1_MASK_CANON)) { - if (!ASN1_STRING_copy(out, in)) { + if (!x509_marshal_name_entry(&rdn, entry, canonicalize)) { return 0; } - return 1; } - out->type = V_ASN1_UTF8STRING; - out->length = ASN1_STRING_to_UTF8(&out->data, in); - if (out->length == -1) { + return CBB_flush_asn1_set_of(&rdn) && CBB_flush(out); +} + +const X509_NAME_CACHE *x509_name_get_cache(const X509_NAME *name) { + const X509_NAME_CACHE *cache = name->cache.load(); + if (cache != nullptr) { + return cache; + } + + X509_NAME_CACHE *new_cache = + static_cast<X509_NAME_CACHE *>(OPENSSL_zalloc(sizeof(X509_NAME_CACHE))); + // Cache the DER encoding, including the outer TLV. + bssl::ScopedCBB cbb; + CBB seq; + if (!CBB_init(cbb.get(), 16) || + !CBB_add_asn1(cbb.get(), &seq, CBS_ASN1_SEQUENCE) || + !x509_marshal_name_entries(&seq, name, /*canonicalize=*/0) || + !CBB_finish(cbb.get(), &new_cache->der, &new_cache->der_len)) { + x509_name_cache_free(new_cache); + return 0; + } + // Cache the canonicalized form, without the outer TLV. + if (!CBB_init(cbb.get(), 16) || + !x509_marshal_name_entries(cbb.get(), name, /*canonicalize=*/1) || + !CBB_finish(cbb.get(), &new_cache->canon, &new_cache->canon_len)) { + x509_name_cache_free(new_cache); return 0; } - to = out->data; - from = to; - - len = out->length; - - // Convert string in place to canonical form. - - // Ignore leading spaces - while ((len > 0) && OPENSSL_isspace(*from)) { - from++; - len--; + X509_NAME_CACHE *expected = nullptr; + if (name->cache.compare_exchange_strong(expected, new_cache)) { + // We won the race. |name| now owns |new_cache|. + return new_cache; } - to = from + len; - - // Ignore trailing spaces - while ((len > 0) && OPENSSL_isspace(to[-1])) { - to--; - len--; - } - - to = out->data; - - i = 0; - while (i < len) { - // Collapse multiple spaces - if (OPENSSL_isspace(*from)) { - // Copy one space across - *to++ = ' '; - // Ignore subsequent spaces. Note: don't need to check len here - // because we know the last character is a non-space so we can't - // overflow. - do { - from++; - i++; - } while (OPENSSL_isspace(*from)); - } else { - *to++ = OPENSSL_tolower(*from); - from++; - i++; - } - } - - out->length = to - out->data; - - return 1; + // Some other thread installed a (presumably identical) cache. Release the one + // we made and return the winning one. + assert(expected != nullptr); + x509_name_cache_free(new_cache); + return expected; } -static int i2d_name_canon(STACK_OF(STACK_OF_X509_NAME_ENTRY) *_intname, - unsigned char **in) { - int len, ltmp; - size_t i; - ASN1_VALUE *v; - STACK_OF(ASN1_VALUE) *intname = (STACK_OF(ASN1_VALUE) *)_intname; +void x509_name_invalidate_cache(X509_NAME *name) { + x509_name_cache_free(name->cache.exchange(nullptr)); +} - len = 0; - for (i = 0; i < sk_ASN1_VALUE_num(intname); i++) { - v = sk_ASN1_VALUE_value(intname, i); - ltmp = ASN1_item_ex_i2d(&v, in, ASN1_ITEM_rptr(X509_NAME_ENTRIES), - /*tag=*/-1, /*aclass=*/0); - if (ltmp < 0) { - return ltmp; - } - len += ltmp; +int x509_marshal_name(CBB *out, const X509_NAME *in) { + const X509_NAME_CACHE *cache = x509_name_get_cache(in); + if (cache == nullptr) { + return 0; } + return CBB_add_bytes(out, cache->der, cache->der_len); +} + +X509_NAME *X509_NAME_dup(X509_NAME *name) { + const X509_NAME_CACHE *cache = x509_name_get_cache(name); + if (cache == nullptr) { + return nullptr; + } + CBS cbs; + CBS_init(&cbs, cache->der, cache->der_len); + bssl::UniquePtr<X509_NAME> copy(X509_NAME_new()); + if (copy == nullptr || !x509_parse_name(&cbs, copy.get())) { + return nullptr; + } + assert(CBS_len(&cbs) == 0); + return copy.release(); +} + +X509_NAME *d2i_X509_NAME(X509_NAME **out, const uint8_t **inp, long len) { + return bssl::D2IFromCBS( + out, inp, len, [](CBS *cbs) -> bssl::UniquePtr<X509_NAME> { + bssl::UniquePtr<X509_NAME> name(X509_NAME_new()); + if (name == nullptr || !x509_parse_name(cbs, name.get())) { + return nullptr; + } + return name; + }); +} + +int i2d_X509_NAME(X509_NAME *in, uint8_t **outp) { + const X509_NAME_CACHE *cache = x509_name_get_cache(in); + if (cache == nullptr) { + return -1; + } + if (cache->der_len > INT_MAX) { + OPENSSL_PUT_ERROR(X509, ERR_R_OVERFLOW); + return -1; + } + int len = static_cast<int>(cache->der_len); + if (outp == nullptr) { + return len; + } + if (*outp == nullptr) { + *outp = static_cast<uint8_t*>(OPENSSL_memdup(cache->der, cache->der_len)); + return *outp != nullptr ? len : -1; + } + OPENSSL_memcpy(*outp, cache->der, cache->der_len); + *outp += cache->der_len; return len; } +IMPLEMENT_EXTERN_ASN1_SIMPLE(X509_NAME, X509_NAME_new, X509_NAME_free, + CBS_ASN1_SEQUENCE, x509_parse_name, i2d_X509_NAME) + +static int asn1_marshal_string_canon(CBB *cbb, const ASN1_STRING *in) { + int (*decode_func)(CBS *, uint32_t *); + int error; + switch (in->type) { + case V_ASN1_UTF8STRING: + decode_func = CBS_get_utf8; + error = ASN1_R_INVALID_UTF8STRING; + break; + case V_ASN1_BMPSTRING: + decode_func = CBS_get_ucs2_be; + error = ASN1_R_INVALID_BMPSTRING; + break; + case V_ASN1_UNIVERSALSTRING: + decode_func = CBS_get_utf32_be; + error = ASN1_R_INVALID_UNIVERSALSTRING; + break; + case V_ASN1_PRINTABLESTRING: + case V_ASN1_T61STRING: + case V_ASN1_IA5STRING: + case V_ASN1_VISIBLESTRING: + decode_func = CBS_get_latin1; + error = ERR_R_INTERNAL_ERROR; // Latin-1 inputs are never invalid. + break; + default: + // Other string types are not canonicalized. + return asn1_marshal_any_string(cbb, in); + } + + CBB child; + if (!CBB_add_asn1(cbb, &child, CBS_ASN1_UTF8STRING)) { + return 0; + } + + bool empty = true; + bool in_whitespace = false; + CBS cbs; + CBS_init(&cbs, in->data, in->length); + while (CBS_len(&cbs) != 0) { + uint32_t c; + if (!decode_func(&cbs, &c)) { + OPENSSL_PUT_ERROR(ASN1, error); + return 0; + } + if (OPENSSL_isspace(c)) { + if (empty) { + continue; // Trim leading whitespace. + } + in_whitespace = true; + } else { + if (in_whitespace) { + // Collapse the previous run of whitespace into one space. + if (!CBB_add_u8(&child, ' ')) { + return 0; + } + } + in_whitespace = false; + // Lowecase ASCII codepoints. + if (c <= 0x7f) { + c = OPENSSL_tolower(c); + } + if (!CBB_add_utf8(&child, c)) { + return 0; + } + empty = false; + } + } + + return CBB_flush(cbb); +} + int X509_NAME_set(X509_NAME **xn, X509_NAME *name) { if ((name = X509_NAME_dup(name)) == NULL) { return 0; @@ -470,24 +397,15 @@ int X509_NAME_get0_der(X509_NAME *nm, const unsigned char **out_der, size_t *out_der_len) { - // Make sure encoding is valid - if (i2d_X509_NAME(nm, NULL) <= 0) { + const X509_NAME_CACHE *cache = x509_name_get_cache(nm); + if (cache == nullptr) { return 0; } - if (out_der != NULL) { - *out_der = (unsigned char *)nm->bytes->data; + if (out_der != nullptr) { + *out_der = cache->der; } - if (out_der_len != NULL) { - *out_der_len = nm->bytes->length; + if (out_der_len != nullptr) { + *out_der_len = cache->der_len; } return 1; } - -int x509_marshal_name(CBB *out, X509_NAME *in) { - int len = i2d_X509_NAME(in, nullptr); - if (len <= 0) { - return 0; - } - uint8_t *ptr; - return CBB_add_space(out, &ptr, len) && i2d_X509_NAME(in, &ptr) == len; -}
diff --git a/include/openssl/x509.h b/include/openssl/x509.h index 667eede5..e490931 100644 --- a/include/openssl/x509.h +++ b/include/openssl/x509.h
@@ -1370,9 +1370,6 @@ // they are equal, one if |a| sorts after |b|, -1 if |b| sorts after |a|, and -2 // on error. // -// TODO(crbug.com/42290269): This function is const, but it is not always -// thread-safe, notably if |name| was mutated. -// // TODO(https://crbug.com/boringssl/355): The -2 return is very inconvenient to // pass to a sorting function. Can we make this infallible? In the meantime, // prefer to use this function only for equality checks rather than comparisons.