| /* 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, uint32_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); |
| } |
| |
| 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; |
| } |