diff options
Diffstat (limited to 'libder/libder_obj.c')
| -rw-r--r-- | libder/libder_obj.c | 1192 |
1 files changed, 1192 insertions, 0 deletions
diff --git a/libder/libder_obj.c b/libder/libder_obj.c new file mode 100644 index 000000000000..21d39e01fc17 --- /dev/null +++ b/libder/libder_obj.c @@ -0,0 +1,1192 @@ +/*- + * Copyright (c) 2024 Kyle Evans <kevans@FreeBSD.org> + * + * SPDX-License-Identifier: BSD-2-Clause + */ + +#include <assert.h> +#include <stdlib.h> +#include <string.h> + +#include "libder_private.h" + +#undef DER_CHILDREN +#undef DER_NEXT + +#define DER_CHILDREN(obj) ((obj)->children) +#define DER_NEXT(obj) ((obj)->next) + +static uint8_t * +libder_obj_alloc_copy_payload(struct libder_ctx *ctx, const uint8_t *payload_in, + size_t length) +{ + uint8_t *payload; + + if ((length == 0 && payload_in != NULL) || + (length != 0 && payload_in == NULL)) { + libder_set_error(ctx, LDE_INVAL); + return (NULL); + } + + if (length > 0) { + payload = malloc(length); + if (payload == NULL) { + libder_set_error(ctx, LDE_NOMEM); + return (NULL); + } + + memcpy(payload, payload_in, length); + } else { + payload = NULL; + } + + return (payload); +} + +static bool +libder_obj_alloc_check(struct libder_ctx *ctx, struct libder_tag *type, + const uint8_t *payload_in, size_t length) +{ + /* + * In addition to our normal constraints, constructed objects coming in + * from lib users should not have payloads. + */ + if (!libder_is_valid_obj(ctx, type, payload_in, length, false) || + (type->tag_constructed && length != 0)) { + libder_set_error(ctx, LDE_BADOBJECT); + return (false); + } + + return (true); +} + +struct libder_object * +libder_obj_alloc(struct libder_ctx *ctx, struct libder_tag *type, + const uint8_t *payload_in, size_t length) +{ + struct libder_object *obj; + uint8_t *payload; + + if (!libder_obj_alloc_check(ctx, type, payload_in, length)) + return (NULL); + + payload = libder_obj_alloc_copy_payload(ctx, payload_in, length); + + obj = libder_obj_alloc_internal(ctx, type, payload, length, 0); + if (obj == NULL) { + if (length != 0) { + libder_bzero(payload, length); + free(payload); + } + + libder_set_error(ctx, LDE_NOMEM); + } + + return (obj); +} + +struct libder_object * +libder_obj_alloc_simple(struct libder_ctx *ctx, uint8_t stype, + const uint8_t *payload_in, size_t length) +{ + struct libder_object *obj; + struct libder_tag *type; + uint8_t *payload; + + type = libder_type_alloc_simple(ctx, stype); + if (type == NULL) + return (NULL); + + if (!libder_obj_alloc_check(ctx, type, payload_in, length)) { + libder_type_free(type); + return (NULL); + } + + payload = libder_obj_alloc_copy_payload(ctx, payload_in, length); + + obj = libder_obj_alloc_internal(ctx, type, payload, length, LDO_OWNTAG); + if (obj == NULL) { + if (length != 0) { + libder_bzero(payload, length); + free(payload); + } + + libder_type_free(type); + libder_set_error(ctx, LDE_NOMEM); + } + + return (obj); +} + +/* + * Returns an obj on success, NULL if out of memory. `obj` takes ownership of + * the payload on success. + */ +LIBDER_PRIVATE struct libder_object * +libder_obj_alloc_internal(struct libder_ctx *ctx, struct libder_tag *type, + uint8_t *payload, size_t length, uint32_t flags) +{ + struct libder_object *obj; + + assert((flags & ~(LDO_OWNTAG)) == 0); + + if (length != 0) + assert(payload != NULL); + else + assert(payload == NULL); + + obj = malloc(sizeof(*obj)); + if (obj == NULL) + return (NULL); + + if ((flags & LDO_OWNTAG) != 0) { + obj->type = type; + } else { + /* + * Deep copies the tag data, so that the caller can predict what + * it can do with the buffer. + */ + obj->type = libder_type_dup(ctx, type); + if (obj->type == NULL) { + free(obj); + return (NULL); + } + } + + obj->length = length; + obj->payload = payload; + obj->children = obj->next = obj->parent = NULL; + obj->nchildren = 0; + + return (obj); +} + +LIBDER_PRIVATE size_t +libder_size_length(size_t sz) +{ + size_t nbytes; + + /* + * With DER, we use the smallest encoding necessary: less than 0x80 + * can be encoded in one byte. + */ + if (sz < 0x80) + return (1); + + /* + * We can support up to 0x7f size bytes, but we don't really have a way + * to represent that right now. It's a good thing this function only + * takes a size_t, otherwise this would be a bit wrong. + */ + for (nbytes = 1; nbytes < sizeof(size_t); nbytes++) { + if ((sz & ~((1ULL << 8 * nbytes) - 1)) == 0) + break; + } + + /* Add one for the lead byte describing the length of the length. */ + return (nbytes + 1); +} + +/* + * Returns the size on-disk. If an object has children, we encode the size as + * the sum of their lengths recursively. Otherwise, we use the object's size. + * + * Returns 0 if the object size would overflow a size_t... perhaps we could + * lift this restriction later. + * + * Note that the size of the object will be set/updated to simplify later write + * calculations. + */ +LIBDER_PRIVATE size_t +libder_obj_disk_size(struct libder_object *obj, bool include_header) +{ + struct libder_object *walker; + size_t disk_size, header_size; + + disk_size = obj->length; + if (obj->children != NULL) { + /* We should have rejected these. */ + assert(obj->length == 0); + + DER_FOREACH_CHILD(walker, obj) { + size_t child_size; + + child_size = libder_obj_disk_size(walker, true); + if (SIZE_MAX - child_size < disk_size) + return (0); /* Overflow */ + disk_size += child_size; + } + } + + obj->disk_size = disk_size; + + /* + * Children always include the header above, we only include the header + * at the root if we're calculating how much space we need in total. + */ + if (include_header) { + /* Size of the length + the tag (arbitrary length) */ + header_size = libder_size_length(disk_size) + obj->type->tag_size; + if (obj->type->tag_encoded) + header_size++; /* Lead byte */ + if (SIZE_MAX - header_size < disk_size) + return (0); + + disk_size += header_size; + } + + return (disk_size); +} + +void +libder_obj_free(struct libder_object *obj) +{ + struct libder_object *child, *tmp; + + if (obj == NULL) + return; + + DER_FOREACH_CHILD_SAFE(child, obj, tmp) + libder_obj_free(child); + + if (obj->payload != NULL) { + libder_bzero(obj->payload, obj->length); + free(obj->payload); + } + + libder_type_free(obj->type); + free(obj); +} + +static void +libder_obj_unlink(struct libder_object *obj) +{ + struct libder_object *child, *parent, *prev; + + parent = obj->parent; + if (parent == NULL) + return; + + prev = NULL; + assert(parent->nchildren > 0); + DER_FOREACH_CHILD(child, parent) { + if (child == obj) { + if (prev == NULL) + parent->children = child->next; + else + prev->next = child->next; + parent->nchildren--; + child->parent = NULL; + return; + } + + prev = child; + } + + assert(0 && "Internal inconsistency: parent set, but child not found"); +} + +bool +libder_obj_append(struct libder_object *parent, struct libder_object *child) +{ + struct libder_object *end, *walker; + + if (!parent->type->tag_constructed) + return (false); + + /* XXX Type check */ + + if (child->parent != NULL) + libder_obj_unlink(child); + + if (parent->nchildren == 0) { + parent->children = child; + parent->nchildren++; + return (true); + } + + /* Walk the chain */ + DER_FOREACH_CHILD(walker, parent) { + end = walker; + } + + assert(end != NULL); + end->next = child; + parent->nchildren++; + child->parent = parent; + return (true); +} + +struct libder_object * +libder_obj_child(const struct libder_object *obj, size_t idx) +{ + struct libder_object *cur; + + DER_FOREACH_CHILD(cur, obj) { + if (idx-- == 0) + return (cur); + } + + return (NULL); +} + +struct libder_object * +libder_obj_children(const struct libder_object *obj) +{ + + return (obj->children); +} + +struct libder_object * +libder_obj_next(const struct libder_object *obj) +{ + + return (obj->next); +} + +struct libder_tag * +libder_obj_type(const struct libder_object *obj) +{ + + return (obj->type); +} + +uint8_t +libder_obj_type_simple(const struct libder_object *obj) +{ + struct libder_tag *type = obj->type; + uint8_t simple = type->tag_class << 6; + + if (type->tag_constructed) + simple |= BER_TYPE_CONSTRUCTED_MASK; + + if (type->tag_encoded) + simple |= 0x1f; /* Encode the "long tag" tag. */ + else + simple |= type->tag_short; + return (simple); +} + +const uint8_t * +libder_obj_data(const struct libder_object *obj, size_t *osz) +{ + + if (obj->type->tag_constructed) + return (NULL); + + *osz = obj->length; + return (obj->payload); +} + +static const char * +libder_type_name(const struct libder_tag *type) +{ + static char namebuf[128]; + + if (type->tag_encoded) { + return ("{ ... }"); + } + + if (type->tag_class != BC_UNIVERSAL) + goto fallback; + +#define UTYPE(val) case val: return (&(#val)[3]) + switch (type->tag_short) { + UTYPE(BT_RESERVED); + UTYPE(BT_BOOLEAN); + UTYPE(BT_INTEGER); + UTYPE(BT_BITSTRING); + UTYPE(BT_OCTETSTRING); + UTYPE(BT_NULL); + UTYPE(BT_OID); + UTYPE(BT_OBJDESC); + UTYPE(BT_EXTERNAL); + UTYPE(BT_REAL); + UTYPE(BT_ENUMERATED); + UTYPE(BT_PDV); + UTYPE(BT_UTF8STRING); + UTYPE(BT_RELOID); + UTYPE(BT_NUMERICSTRING); + UTYPE(BT_STRING); + UTYPE(BT_TELEXSTRING); + UTYPE(BT_VIDEOTEXSTRING); + UTYPE(BT_IA5STRING); + UTYPE(BT_UTCTIME); + UTYPE(BT_GENTIME); + UTYPE(BT_GFXSTRING); + UTYPE(BT_VISSTRING); + UTYPE(BT_GENSTRING); + UTYPE(BT_UNIVSTRING); + UTYPE(BT_CHARSTRING); + UTYPE(BT_BMPSTRING); + case BT_SEQUENCE & ~BER_TYPE_CONSTRUCTED_MASK: + case BT_SEQUENCE: return "SEQUENCE"; + case BT_SET & ~BER_TYPE_CONSTRUCTED_MASK: + case BT_SET: return "SET"; + } + +fallback: + snprintf(namebuf, sizeof(namebuf), "%.02x", libder_type_simple(type)); + return (&namebuf[0]); +} + +static void +libder_obj_dump_internal(const struct libder_object *obj, FILE *fp, int lvl) +{ + static char spacer[4096]; + const struct libder_object *child; + + /* Primitive, goofy, but functional. */ + if (spacer[0] == '\0') + memset(spacer, '\t', sizeof(spacer)); + + if (lvl >= (int)sizeof(spacer)) { + /* Too large, truncate the display. */ + fprintf(fp, "%.*s...\n", (int)sizeof(spacer), spacer); + return; + } + + if (obj->children == NULL) { + size_t col = lvl * 8; + + col += fprintf(fp, "%.*sOBJECT[type=%s, size=%zx]%s", + lvl, spacer, libder_type_name(obj->type), + obj->length, obj->length != 0 ? ": " : ""); + + if (obj->length != 0) { + uint8_t printb; + +#define LIBDER_CONTENTS_WRAP 80 + for (size_t i = 0; i < obj->length; i++) { + if (col + 3 >= LIBDER_CONTENTS_WRAP) { + fprintf(fp, "\n%.*s ", lvl, spacer); + col = (lvl * 8) + 4; + } + + if (obj->payload == NULL) + printb = 0; + else + printb = obj->payload[i]; + + col += fprintf(fp, "%.02x ", printb); + } + } + + fprintf(fp, "\n"); + + return; + } + + fprintf(fp, "%.*sOBJECT[type=%s]\n", lvl, spacer, + libder_type_name(obj->type)); + DER_FOREACH_CHILD(child, obj) + libder_obj_dump_internal(child, fp, lvl + 1); +} + +void +libder_obj_dump(const struct libder_object *root, FILE *fp) +{ + + libder_obj_dump_internal(root, fp, 0); +} + +LIBDER_PRIVATE bool +libder_is_valid_obj(struct libder_ctx *ctx, const struct libder_tag *type, + const uint8_t *payload, size_t payloadsz, bool varlen) +{ + + if (payload != NULL) { + assert(payloadsz > 0); + assert(!varlen); + } else { + assert(payloadsz == 0); + } + + /* No rules for non-universal types. */ + if (type->tag_class != BC_UNIVERSAL || type->tag_encoded) + return (true); + + if (ctx->strict && type->tag_constructed) { + /* Types that don't allow constructed */ + switch (libder_type_simple(type) & ~BER_TYPE_CONSTRUCTED_MASK) { + case BT_BOOLEAN: + case BT_INTEGER: + case BT_REAL: + case BT_NULL: + libder_set_error(ctx, LDE_STRICT_PRIMITIVE); + return (false); + default: + break; + } + } else if (ctx->strict) { + /* Types that cannot be primitive */ + switch (libder_type_simple(type) | BER_TYPE_CONSTRUCTED_MASK) { + case BT_SEQUENCE: + case BT_SET: + libder_set_error(ctx, LDE_STRICT_CONSTRUCTED); + return (false); + default: + break; + } + } + + /* Further validation */ + switch (libder_type_simple(type)) { + case BT_BOOLEAN: + if (ctx->strict && payloadsz != 1) { + libder_set_error(ctx, LDE_STRICT_BOOLEAN); + return (false); + } + break; + case BT_NULL: + if (ctx->strict && (payloadsz != 0 || varlen)) { + libder_set_error(ctx, LDE_STRICT_NULL); + return (false); + } + break; + case BT_BITSTRING: /* Primitive */ + /* + * Bit strings require more invasive parsing later during child + * coalescing or normalization, so we alway strictly enforce + * their form. + */ + if (payloadsz == 1 && payload[0] != 0) + return (false); + + /* We can't have more than seven unused bits. */ + return (payloadsz < 2 || payload[0] < 8); + case BT_RESERVED: + if (payloadsz != 0) { + libder_set_error(ctx, LDE_STRICT_EOC); + return (false); + } + break; + default: + break; + } + + return (true); +} + +LIBDER_PRIVATE bool +libder_obj_may_coalesce_children(const struct libder_object *obj) +{ + + /* No clue about non-universal types. */ + if (obj->type->tag_class != BC_UNIVERSAL || obj->type->tag_encoded) + return (false); + + /* Constructed types don't have children. */ + if (!obj->type->tag_constructed) + return (false); + + /* Strip the constructed bit off. */ + switch (libder_type_simple(obj->type)) { + case BT_OCTETSTRING: /* Raw data types */ + case BT_BITSTRING: + return (true); + case BT_UTF8STRING: /* String types */ + case BT_NUMERICSTRING: + case BT_STRING: + case BT_TELEXSTRING: + case BT_VIDEOTEXSTRING: + case BT_IA5STRING: + case BT_GFXSTRING: + case BT_VISSTRING: + case BT_GENSTRING: + case BT_UNIVSTRING: + case BT_CHARSTRING: + case BT_BMPSTRING: + return (true); + case BT_UTCTIME: /* Time types */ + case BT_GENTIME: + return (true); + default: + return (false); + } +} + +static size_t +libder_merge_bitstrings(uint8_t *buf, size_t offset, size_t bufsz, + const struct libder_object *child) +{ + const uint8_t *rhs = child->payload; + size_t rsz = child->disk_size, startoff = offset; + uint8_t rhsunused, unused; + + rhsunused = (rhs != NULL ? rhs[0] : 0); + + /* We have no unused bits if the buffer's empty as of yet. */ + if (offset == 0) + unused = 0; + else + unused = buf[0]; + + /* Shave the lead byte off if we have one. */ + if (rsz > 1) { + if (rhs != NULL) + rhs++; + rsz--; + } + + if (unused == 0) { + size_t extra = 0; + + /* + * In all cases we'll just write the unused byte separately, + * since we're copying way past it in the common case and can't + * just overwrite it as part of the memcpy(). + */ + if (offset == 0) { + offset = 1; + extra++; + } + + assert(rhsunused < 8); + assert(offset + rsz <= bufsz); + + buf[0] = rhsunused; + if (rhs == NULL) + memset(&buf[offset], 0, rsz); + else + memcpy(&buf[offset], rhs, rsz); + + return (rsz + extra); + } + + for (size_t i = 0; i < rsz; i++) { + uint8_t bits, next; + + if (rhs == NULL) + next = 0; + else + next = rhs[i]; + + /* Rotate the leading bits into the byte before it. */ + assert(unused < 8); + bits = next >> (8 - unused); + buf[offset - 1] |= bits; + + next <<= unused; + + /* + * Copy the new valid bits in; we shift over the old unused + * amount up until the very last bit, then we have to recalculate + * because we may be dropping it entirely. + */ + if (i == rsz - 1) { + assert(rhsunused < 8); + + /* + * Figure out how many unused bits we have between the two + * buffers, sum % 8 is the new # unused bits. It will be + * somewhere in the range of [0, 14], and if it's at or + * higher than a single byte then that's a clear indicator + * that we shifted some unused bits into the previous byte and + * can just halt here. + */ + unused += rhsunused; + buf[0] = unused % 8; + if (unused >= 8) + break; + } + + assert(offset < bufsz); + buf[offset++] = next; + } + + return (offset - startoff); +} + +LIBDER_PRIVATE bool +libder_obj_coalesce_children(struct libder_object *obj, struct libder_ctx *ctx) +{ + struct libder_object *child, *last_child, *tmp; + size_t new_size = 0, offset = 0; + uint8_t *coalesced_data; + uint8_t type; + bool need_payload = false, strict_violation = false; + + if (obj->nchildren == 0 || !libder_obj_may_coalesce_children(obj)) + return (true); + + assert(obj->type->tag_class == BC_UNIVERSAL); + assert(obj->type->tag_constructed); + assert(!obj->type->tag_encoded); + type = obj->type->tag_short; + + last_child = NULL; + DER_FOREACH_CHILD(child, obj) { + /* Sanity check and coalesce our children. */ + if (child->type->tag_class != BC_UNIVERSAL || + child->type->tag_short != obj->type->tag_short) { + libder_set_error(ctx, LDE_COALESCE_BADCHILD); + return (false); + } + + /* Recursively coalesce everything. */ + if (!libder_obj_coalesce_children(child, ctx)) + return (false); + + /* + * The child node will be disappearing anyways, so we stash the + * disk size sans header in its disk_size to reuse in the later + * loop. + */ + child->disk_size = libder_obj_disk_size(child, false); + + /* + * We strip the lead byte off of every element, and add it back + * in pre-allocation. + */ + if (type == BT_BITSTRING && child->disk_size > 1) + child->disk_size--; + if (child->disk_size > 0) + last_child = child; + + new_size += child->disk_size; + + if (child->payload != NULL) + need_payload = true; + } + + if (new_size != 0 && need_payload) { + if (type == BT_BITSTRING) + new_size++; + coalesced_data = malloc(new_size); + if (coalesced_data == NULL) { + libder_set_error(ctx, LDE_NOMEM); + return (false); + } + } else { + /* + * This would perhaps be a bit weird, but that's normalization + * for you. We shouldn't really have a UTF-8 string that's + * composed of a series of zero-length UTF-8 strings, but + * weirder things have happened. + */ + coalesced_data = NULL; + } + + /* Avoid leaking any children as we coalesce. */ + DER_FOREACH_CHILD_SAFE(child, obj, tmp) { + if (child->disk_size != 0) + assert(coalesced_data != NULL || !need_payload); + + /* + * Just free everything when we violate strict rules. + */ + if (strict_violation) + goto violated; + + if (child->disk_size != 0 && need_payload) { + assert(coalesced_data != NULL); + assert(offset + child->disk_size <= new_size); + + /* + * Bit strings are special, in that the first byte + * contains the number of unused bits at the end. We + * need to trim that off when concatenating bit strings + */ + if (type == BT_BITSTRING) { + if (ctx->strict && child != last_child && + child->disk_size > 1 && child->payload != NULL) { + /* + * Each child must have a multiple of 8, + * up until the final one. + */ + if (child->payload[0] != 0) { + libder_set_error(ctx, LDE_STRICT_BITSTRING); + strict_violation = true; + goto violated; + } + } + + offset += libder_merge_bitstrings(coalesced_data, + offset, new_size, child); + } else { + /* + * Write zeroes out if we don't have a payload. + */ + if (child->payload == NULL) { + memset(&coalesced_data[offset], 0, child->disk_size); + offset += child->disk_size; + } else { + memcpy(&coalesced_data[offset], child->payload, + child->disk_size); + offset += child->disk_size; + } + } + } + +violated: + libder_obj_free(child); + } + + assert(offset <= new_size); + + /* Zap the children, we've absorbed their bodies. */ + obj->children = NULL; + + if (strict_violation) { + if (coalesced_data != NULL) { + libder_bzero(coalesced_data, offset); + free(coalesced_data); + } + + return (false); + } + + /* Finally, swap out the payload. */ + if (obj->payload != NULL) { + libder_bzero(obj->payload, obj->length); + free(obj->payload); + } + + obj->length = offset; + obj->payload = coalesced_data; + obj->type->tag_constructed = false; + + return (true); +} + +static bool +libder_obj_normalize_bitstring(struct libder_object *obj) +{ + uint8_t *payload = obj->payload; + size_t length = obj->length; + uint8_t unused; + + if (payload == NULL || length < 2) + return (true); + + unused = payload[0]; + if (unused == 0) + return (true); + + /* Clear the unused bits completely. */ + payload[length - 1] &= ~((1 << unused) - 1); + return (true); +} + +static bool +libder_obj_normalize_boolean(struct libder_object *obj) +{ + uint8_t *payload = obj->payload; + size_t length = obj->length; + int sense = 0; + + assert(length > 0); + + /* + * Booleans must be collapsed down to a single byte, 0x00 or 0xff, + * indicating false or true respectively. + */ + if (length == 1 && (payload[0] == 0x00 || payload[0] == 0xff)) + return (true); + + for (size_t bpos = 0; bpos < length; bpos++) { + sense |= payload[bpos]; + if (sense != 0) + break; + } + + payload[0] = sense != 0 ? 0xff : 0x00; + obj->length = 1; + return (true); +} + +static bool +libder_obj_normalize_integer(struct libder_object *obj) +{ + uint8_t *payload = obj->payload; + size_t length = obj->length; + size_t strip = 0; + + /* + * Strip any leading sign-extended looking bytes, but note that + * we can't strip a leading byte unless it matches the sign bit + * on the next byte. + */ + for (size_t bpos = 0; bpos < length - 1; bpos++) { + if (payload[bpos] != 0 && payload[bpos] != 0xff) + break; + + if (payload[bpos] == 0xff) { + /* Only if next byte indicates signed. */ + if ((payload[bpos + 1] & 0x80) == 0) + break; + } else { + /* Only if next byte indicates unsigned. */ + if ((payload[bpos + 1] & 0x80) != 0) + break; + } + + strip++; + } + + if (strip != 0) { + payload += strip; + length -= strip; + + memmove(&obj->payload[0], payload, length); + obj->length = length; + } + + return (true); +} + +static int +libder_obj_tag_compare(const struct libder_tag *lhs, const struct libder_tag *rhs) +{ + const uint8_t *lbits, *rbits; + size_t delta, end, lsz, rsz; + uint8_t lbyte, rbyte; + + /* Highest bits: tag class, libder_ber_class has the same bit ordering. */ + if (lhs->tag_class < rhs->tag_class) + return (-1); + if (lhs->tag_class > rhs->tag_class) + return (1); + + /* Next bit: constructed vs. primitive */ + if (!lhs->tag_constructed && rhs->tag_constructed) + return (-1); + if (lhs->tag_constructed && rhs->tag_constructed) + return (1); + + /* + * Finally: tag data; we can use the size as a first-order heuristic + * because we store tags in the shortest possible representation. + */ + if (lhs->tag_size < rhs->tag_size) + return (-1); + else if (lhs->tag_size > rhs->tag_size) + return (1); + + if (!lhs->tag_encoded) { + lbits = (const void *)&lhs->tag_short; + lsz = sizeof(uint64_t); + } else { + lbits = lhs->tag_long; + lsz = lhs->tag_size; + } + + if (!rhs->tag_encoded) { + rbits = (const void *)&rhs->tag_short; + rsz = sizeof(uint64_t); + } else { + rbits = rhs->tag_long; + rsz = rhs->tag_size; + } + + delta = 0; + end = MAX(lsz, rsz); + if (lsz > rsz) + delta = lsz - rsz; + else if (lsz < rsz) + delta = rsz - lsz; + for (size_t i = 0; i < end; i++) { + /* Zero-extend the short one the difference. */ + if (lsz < rsz && i < delta) + lbyte = 0; + else + lbyte = lbits[i - delta]; + + if (lsz > rsz && i < delta) + rbyte = 0; + else + rbyte = rbits[i - delta]; + + if (lbyte < rbyte) + return (-1); + else if (lbyte > rbyte) + return (-1); + } + + return (0); +} + +/* + * Similar to strcmp(), returns -1, 0, or 1. + */ +static int +libder_obj_compare(const struct libder_object *lhs, const struct libder_object *rhs) +{ + size_t end; + int cmp; + uint8_t lbyte, rbyte; + + cmp = libder_obj_tag_compare(lhs->type, rhs->type); + if (cmp != 0) + return (cmp); + + /* + * We'll compare up to the longer of the two; the shorter payload is + * zero-extended at the end for comparison purposes. + */ + end = MAX(lhs->length, rhs->length); + for (size_t pos = 0; pos < end; pos++) { + if (lhs->payload != NULL && pos < lhs->length) + lbyte = lhs->payload[pos]; + else + lbyte = 0; + if (rhs->payload != NULL && pos < rhs->length) + rbyte = rhs->payload[pos]; + else + rbyte = 0; + + if (lbyte < rbyte) + return (-1); + else if (lbyte > rbyte) + return (1); + } + + return (0); +} + +static int +libder_obj_normalize_set_cmp(const void *lhs_entry, const void *rhs_entry) +{ + const struct libder_object *lhs = + *__DECONST(const struct libder_object **, lhs_entry); + const struct libder_object *rhs = + *__DECONST(const struct libder_object **, rhs_entry); + + return (libder_obj_compare(lhs, rhs)); +} + +static bool +libder_obj_normalize_set(struct libder_object *obj, struct libder_ctx *ctx) +{ + struct libder_object **sorting; + struct libder_object *child; + size_t offset = 0; + + if (obj->nchildren < 2) + return (true); + + /* + * Kind of goofy, but we'll just take advantage of a standardized + * qsort() rather than rolling our own sort -- we have no idea how large + * of a dataset we're working with. + */ + sorting = calloc(obj->nchildren, sizeof(*sorting)); + if (sorting == NULL) { + libder_set_error(ctx, LDE_NOMEM); + return (false); + } + + DER_FOREACH_CHILD(child, obj) { + sorting[offset++] = child; + } + + assert(offset == obj->nchildren); + qsort(sorting, offset, sizeof(*sorting), libder_obj_normalize_set_cmp); + + obj->children = sorting[0]; + sorting[offset - 1]->next = NULL; + for (size_t i = 0; i < offset - 1; i++) { + sorting[i]->next = sorting[i + 1]; + } + + free(sorting); + + return (true); +} + +LIBDER_PRIVATE bool +libder_obj_normalize(struct libder_object *obj, struct libder_ctx *ctx) +{ + uint8_t *payload = obj->payload; + size_t length = obj->length; + + if (obj->type->tag_constructed) { + /* + * For constructed types, we'll see if we can coalesce their + * children into them, then we'll proceed with whatever normalization + * rules we can apply to the children. + */ + if (DER_NORMALIZING(ctx, CONSTRUCTED) && !libder_obj_coalesce_children(obj, ctx)) + return (false); + + /* + * We may not be a constructed object anymore after the above coalescing + * happened, so we check it again here. Constructed objects need not go + * any further, but the now-primitive coalesced types still need to be + * normalized. + */ + if (obj->type->tag_constructed) { + struct libder_object *child; + + DER_FOREACH_CHILD(child, obj) { + if (!libder_obj_normalize(child, ctx)) + return (false); + } + + /* Sets must be sorted. */ + if (obj->type->tag_short != BT_SET) + return (true); + + return (libder_obj_normalize_set(obj, ctx)); + } + } + + /* We only have normalization rules for universal types. */ + if (obj->type->tag_class != BC_UNIVERSAL || obj->type->tag_encoded) + return (true); + + if (!libder_normalizing_type(ctx, obj->type)) + return (true); + + /* + * We are clear to normalize this object, check for some easy cases that + * don't need normalization. + */ + switch (libder_type_simple(obj->type)) { + case BT_BITSTRING: + case BT_BOOLEAN: + case BT_INTEGER: + /* + * If we have a zero payload, then we need to encode them as a + * single zero byte. + */ + if (payload == NULL) { + if (length != 1) + obj->length = 1; + + return (true); + } + + break; + case BT_NULL: + if (payload != NULL) { + free(payload); + + obj->payload = NULL; + obj->length = 0; + } + + return (true); + default: + /* + * If we don't have a payload, we'll just leave it alone. + */ + if (payload == NULL) + return (true); + break; + } + + switch (libder_type_simple(obj->type)) { + case BT_BITSTRING: + return (libder_obj_normalize_bitstring(obj)); + case BT_BOOLEAN: + return (libder_obj_normalize_boolean(obj)); + case BT_INTEGER: + return (libder_obj_normalize_integer(obj)); + default: + break; + } + + return (true); +} |