/* Copyright (c) 2014, Google Inc. * * Permission to use, copy, modify, and/or distribute this software for any * purpose with or without fee is hereby granted, provided that the above * copyright notice and this permission notice appear in all copies. * * THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES * WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF * MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY * SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES * WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN ACTION * OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF OR IN * CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE. */ #include <openssl/bytestring.h> #include <assert.h> #include <limits.h> #include <string.h> #include <openssl/buf.h> #include <openssl/mem.h> #include "../internal.h" void CBB_zero(CBB *cbb) { OPENSSL_memset(cbb, 0, sizeof(CBB)); } static int cbb_init(CBB *cbb, uint8_t *buf, size_t cap) { // This assumes that |cbb| has already been zeroed. struct cbb_buffer_st *base; base = OPENSSL_malloc(sizeof(struct cbb_buffer_st)); if (base == NULL) { return 0; } base->buf = buf; base->len = 0; base->cap = cap; base->can_resize = 1; base->error = 0; cbb->base = base; cbb->is_top_level = 1; return 1; } int CBB_init(CBB *cbb, size_t initial_capacity) { CBB_zero(cbb); uint8_t *buf = OPENSSL_malloc(initial_capacity); if (initial_capacity > 0 && buf == NULL) { return 0; } if (!cbb_init(cbb, buf, initial_capacity)) { OPENSSL_free(buf); return 0; } return 1; } int CBB_init_fixed(CBB *cbb, uint8_t *buf, size_t len) { CBB_zero(cbb); if (!cbb_init(cbb, buf, len)) { return 0; } cbb->base->can_resize = 0; return 1; } void CBB_cleanup(CBB *cbb) { if (cbb->base) { // Only top-level |CBB|s are cleaned up. Child |CBB|s are non-owning. They // are implicitly discarded when the parent is flushed or cleaned up. assert(cbb->is_top_level); if (cbb->base->can_resize) { OPENSSL_free(cbb->base->buf); } OPENSSL_free(cbb->base); } cbb->base = NULL; } static int cbb_buffer_reserve(struct cbb_buffer_st *base, uint8_t **out, size_t len) { size_t newlen; if (base == NULL) { return 0; } newlen = base->len + len; if (newlen < base->len) { // Overflow goto err; } if (newlen > base->cap) { size_t newcap = base->cap * 2; uint8_t *newbuf; if (!base->can_resize) { goto err; } if (newcap < base->cap || newcap < newlen) { newcap = newlen; } newbuf = OPENSSL_realloc(base->buf, newcap); if (newbuf == NULL) { goto err; } base->buf = newbuf; base->cap = newcap; } if (out) { *out = base->buf + base->len; } return 1; err: base->error = 1; return 0; } static int cbb_buffer_add(struct cbb_buffer_st *base, uint8_t **out, size_t len) { if (!cbb_buffer_reserve(base, out, len)) { return 0; } // This will not overflow or |cbb_buffer_reserve| would have failed. base->len += len; return 1; } static int cbb_buffer_add_u(struct cbb_buffer_st *base, uint64_t v, size_t len_len) { if (len_len == 0) { return 1; } uint8_t *buf; if (!cbb_buffer_add(base, &buf, len_len)) { return 0; } for (size_t i = len_len - 1; i < len_len; i--) { buf[i] = v; v >>= 8; } if (v != 0) { base->error = 1; return 0; } return 1; } int CBB_finish(CBB *cbb, uint8_t **out_data, size_t *out_len) { if (!cbb->is_top_level) { return 0; } if (!CBB_flush(cbb)) { return 0; } if (cbb->base->can_resize && (out_data == NULL || out_len == NULL)) { // |out_data| and |out_len| can only be NULL if the CBB is fixed. return 0; } if (out_data != NULL) { *out_data = cbb->base->buf; } if (out_len != NULL) { *out_len = cbb->base->len; } cbb->base->buf = NULL; CBB_cleanup(cbb); return 1; } // CBB_flush recurses and then writes out any pending length prefix. The // current length of the underlying base is taken to be the length of the // length-prefixed data. int CBB_flush(CBB *cbb) { size_t child_start, i, len; // If |cbb->base| has hit an error, the buffer is in an undefined state, so // fail all following calls. In particular, |cbb->child| may point to invalid // memory. if (cbb->base == NULL || cbb->base->error) { return 0; } if (cbb->child == NULL || cbb->child->pending_len_len == 0) { return 1; } child_start = cbb->child->offset + cbb->child->pending_len_len; if (!CBB_flush(cbb->child) || child_start < cbb->child->offset || cbb->base->len < child_start) { goto err; } len = cbb->base->len - child_start; if (cbb->child->pending_is_asn1) { // For ASN.1 we assume that we'll only need a single byte for the length. // If that turned out to be incorrect, we have to move the contents along // in order to make space. uint8_t len_len; uint8_t initial_length_byte; assert (cbb->child->pending_len_len == 1); if (len > 0xfffffffe) { // Too large. goto err; } else if (len > 0xffffff) { len_len = 5; initial_length_byte = 0x80 | 4; } else if (len > 0xffff) { len_len = 4; initial_length_byte = 0x80 | 3; } else if (len > 0xff) { len_len = 3; initial_length_byte = 0x80 | 2; } else if (len > 0x7f) { len_len = 2; initial_length_byte = 0x80 | 1; } else { len_len = 1; initial_length_byte = (uint8_t)len; len = 0; } if (len_len != 1) { // We need to move the contents along in order to make space. size_t extra_bytes = len_len - 1; if (!cbb_buffer_add(cbb->base, NULL, extra_bytes)) { goto err; } OPENSSL_memmove(cbb->base->buf + child_start + extra_bytes, cbb->base->buf + child_start, len); } cbb->base->buf[cbb->child->offset++] = initial_length_byte; cbb->child->pending_len_len = len_len - 1; } for (i = cbb->child->pending_len_len - 1; i < cbb->child->pending_len_len; i--) { cbb->base->buf[cbb->child->offset + i] = (uint8_t)len; len >>= 8; } if (len != 0) { goto err; } cbb->child->base = NULL; cbb->child = NULL; return 1; err: cbb->base->error = 1; return 0; } const uint8_t *CBB_data(const CBB *cbb) { assert(cbb->child == NULL); return cbb->base->buf + cbb->offset + cbb->pending_len_len; } size_t CBB_len(const CBB *cbb) { assert(cbb->child == NULL); assert(cbb->offset + cbb->pending_len_len <= cbb->base->len); return cbb->base->len - cbb->offset - cbb->pending_len_len; } static int cbb_add_length_prefixed(CBB *cbb, CBB *out_contents, uint8_t len_len) { uint8_t *prefix_bytes; if (!CBB_flush(cbb)) { return 0; } size_t offset = cbb->base->len; if (!cbb_buffer_add(cbb->base, &prefix_bytes, len_len)) { return 0; } OPENSSL_memset(prefix_bytes, 0, len_len); OPENSSL_memset(out_contents, 0, sizeof(CBB)); out_contents->base = cbb->base; cbb->child = out_contents; cbb->child->offset = offset; cbb->child->pending_len_len = len_len; cbb->child->pending_is_asn1 = 0; return 1; } int CBB_add_u8_length_prefixed(CBB *cbb, CBB *out_contents) { return cbb_add_length_prefixed(cbb, out_contents, 1); } int CBB_add_u16_length_prefixed(CBB *cbb, CBB *out_contents) { return cbb_add_length_prefixed(cbb, out_contents, 2); } 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, uint64_t v) { unsigned len_len = 0; uint64_t 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; } // Split the tag into leading bits and tag number. uint8_t tag_bits = (tag >> CBS_ASN1_TAG_SHIFT) & 0xe0; 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) || !add_base128_integer(cbb, tag_number)) { return 0; } } else if (!CBB_add_u8(cbb, tag_bits | tag_number)) { return 0; } size_t offset = cbb->base->len; if (!CBB_add_u8(cbb, 0)) { return 0; } OPENSSL_memset(out_contents, 0, sizeof(CBB)); out_contents->base = cbb->base; cbb->child = out_contents; cbb->child->offset = offset; cbb->child->pending_len_len = 1; cbb->child->pending_is_asn1 = 1; return 1; } int CBB_add_bytes(CBB *cbb, const uint8_t *data, size_t len) { uint8_t *dest; if (!CBB_flush(cbb) || !cbb_buffer_add(cbb->base, &dest, len)) { return 0; } OPENSSL_memcpy(dest, data, len); return 1; } int CBB_add_space(CBB *cbb, uint8_t **out_data, size_t len) { if (!CBB_flush(cbb) || !cbb_buffer_add(cbb->base, out_data, len)) { return 0; } return 1; } int CBB_reserve(CBB *cbb, uint8_t **out_data, size_t len) { if (!CBB_flush(cbb) || !cbb_buffer_reserve(cbb->base, out_data, len)) { return 0; } return 1; } int CBB_did_write(CBB *cbb, size_t len) { size_t newlen = cbb->base->len + len; if (cbb->child != NULL || newlen < cbb->base->len || newlen > cbb->base->cap) { return 0; } cbb->base->len = newlen; return 1; } int CBB_add_u8(CBB *cbb, uint8_t value) { if (!CBB_flush(cbb)) { return 0; } return cbb_buffer_add_u(cbb->base, value, 1); } int CBB_add_u16(CBB *cbb, uint16_t value) { if (!CBB_flush(cbb)) { return 0; } return cbb_buffer_add_u(cbb->base, value, 2); } int CBB_add_u24(CBB *cbb, uint32_t value) { if (!CBB_flush(cbb)) { return 0; } return cbb_buffer_add_u(cbb->base, value, 3); } int CBB_add_u32(CBB *cbb, uint32_t value) { if (!CBB_flush(cbb)) { return 0; } return cbb_buffer_add_u(cbb->base, value, 4); } int CBB_add_u64(CBB *cbb, uint64_t value) { if (!CBB_flush(cbb)) { return 0; } return cbb_buffer_add_u(cbb->base, value, 8); } void CBB_discard_child(CBB *cbb) { if (cbb->child == NULL) { return; } cbb->base->len = cbb->child->offset; cbb->child->base = NULL; cbb->child = NULL; } int CBB_add_asn1_uint64(CBB *cbb, uint64_t value) { CBB child; int started = 0; if (!CBB_add_asn1(cbb, &child, CBS_ASN1_INTEGER)) { return 0; } for (size_t i = 0; i < 8; i++) { uint8_t byte = (value >> 8*(7-i)) & 0xff; if (!started) { if (byte == 0) { // Don't encode leading zeros. continue; } // If the high bit is set, add a padding byte to make it // unsigned. if ((byte & 0x80) && !CBB_add_u8(&child, 0)) { return 0; } started = 1; } if (!CBB_add_u8(&child, byte)) { return 0; } } // 0 is encoded as a single 0, not the empty string. if (!started && !CBB_add_u8(&child, 0)) { return 0; } return CBB_flush(cbb); } int CBB_add_asn1_octet_string(CBB *cbb, const uint8_t *data, size_t data_len) { CBB child; if (!CBB_add_asn1(cbb, &child, CBS_ASN1_OCTETSTRING) || !CBB_add_bytes(&child, data, data_len) || !CBB_flush(cbb)) { return 0; } return 1; } int CBB_add_asn1_bool(CBB *cbb, int value) { CBB child; if (!CBB_add_asn1(cbb, &child, CBS_ASN1_BOOLEAN) || !CBB_add_u8(&child, value != 0 ? 0xff : 0) || !CBB_flush(cbb)) { return 0; } return 1; } // 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, uint64_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 > UINT64_MAX / 10 || *out * 10 > UINT64_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. uint64_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 > UINT64_MAX - 80 || !add_base128_integer(cbb, 40u * 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; } static int compare_set_of_element(const void *a_ptr, const void *b_ptr) { // See X.690, section 11.6 for the ordering. They are sorted in ascending // order by their DER encoding. const CBS *a = a_ptr, *b = b_ptr; size_t a_len = CBS_len(a), b_len = CBS_len(b); size_t min_len = a_len < b_len ? a_len : b_len; int ret = OPENSSL_memcmp(CBS_data(a), CBS_data(b), min_len); if (ret != 0) { return ret; } if (a_len == b_len) { return 0; } // If one is a prefix of the other, the shorter one sorts first. (This is not // actually reachable. No DER encoding is a prefix of another DER encoding.) return a_len < b_len ? -1 : 1; } int CBB_flush_asn1_set_of(CBB *cbb) { if (!CBB_flush(cbb)) { return 0; } CBS cbs; size_t num_children = 0; CBS_init(&cbs, CBB_data(cbb), CBB_len(cbb)); while (CBS_len(&cbs) != 0) { if (!CBS_get_any_asn1_element(&cbs, NULL, NULL, NULL)) { return 0; } num_children++; } if (num_children < 2) { return 1; // Nothing to do. This is the common case for X.509. } if (num_children > ((size_t)-1) / sizeof(CBS)) { return 0; // Overflow. } // Parse out the children and sort. We alias them into a copy of so they // remain valid as we rewrite |cbb|. int ret = 0; size_t buf_len = CBB_len(cbb); uint8_t *buf = BUF_memdup(CBB_data(cbb), buf_len); CBS *children = OPENSSL_malloc(num_children * sizeof(CBS)); if (buf == NULL || children == NULL) { goto err; } CBS_init(&cbs, buf, buf_len); for (size_t i = 0; i < num_children; i++) { if (!CBS_get_any_asn1_element(&cbs, &children[i], NULL, NULL)) { goto err; } } qsort(children, num_children, sizeof(CBS), compare_set_of_element); // Rewind |cbb| and write the contents back in the new order. cbb->base->len = cbb->offset + cbb->pending_len_len; for (size_t i = 0; i < num_children; i++) { if (!CBB_add_bytes(cbb, CBS_data(&children[i]), CBS_len(&children[i]))) { goto err; } } assert(CBB_len(cbb) == buf_len); ret = 1; err: OPENSSL_free(buf); OPENSSL_free(children); return ret; }