libder_obj.c
1 /*- 2 * Copyright (c) 2024 Kyle Evans <kevans@FreeBSD.org> 3 * 4 * SPDX-License-Identifier: BSD-2-Clause 5 */ 6 7 #include <assert.h> 8 #include <stdlib.h> 9 #include <string.h> 10 11 #include "libder_private.h" 12 13 #undef DER_CHILDREN 14 #undef DER_NEXT 15 16 #define DER_CHILDREN(obj) ((obj)->children) 17 #define DER_NEXT(obj) ((obj)->next) 18 19 static uint8_t * 20 libder_obj_alloc_copy_payload(struct libder_ctx *ctx, const uint8_t *payload_in, 21 size_t length) 22 { 23 uint8_t *payload; 24 25 if ((length == 0 && payload_in != NULL) || 26 (length != 0 && payload_in == NULL)) { 27 libder_set_error(ctx, LDE_INVAL); 28 return (NULL); 29 } 30 31 if (length > 0) { 32 payload = malloc(length); 33 if (payload == NULL) { 34 libder_set_error(ctx, LDE_NOMEM); 35 return (NULL); 36 } 37 38 memcpy(payload, payload_in, length); 39 } else { 40 payload = NULL; 41 } 42 43 return (payload); 44 } 45 46 static bool 47 libder_obj_alloc_check(struct libder_ctx *ctx, struct libder_tag *type, 48 const uint8_t *payload_in, size_t length) 49 { 50 /* 51 * In addition to our normal constraints, constructed objects coming in 52 * from lib users should not have payloads. 53 */ 54 if (!libder_is_valid_obj(ctx, type, payload_in, length, false) || 55 (type->tag_constructed && length != 0)) { 56 libder_set_error(ctx, LDE_BADOBJECT); 57 return (false); 58 } 59 60 return (true); 61 } 62 63 struct libder_object * 64 libder_obj_alloc(struct libder_ctx *ctx, struct libder_tag *type, 65 const uint8_t *payload_in, size_t length) 66 { 67 struct libder_object *obj; 68 uint8_t *payload; 69 70 if (!libder_obj_alloc_check(ctx, type, payload_in, length)) 71 return (NULL); 72 73 payload = libder_obj_alloc_copy_payload(ctx, payload_in, length); 74 75 obj = libder_obj_alloc_internal(ctx, type, payload, length, 0); 76 if (obj == NULL) { 77 if (length != 0) { 78 libder_bzero(payload, length); 79 free(payload); 80 } 81 82 libder_set_error(ctx, LDE_NOMEM); 83 } 84 85 return (obj); 86 } 87 88 struct libder_object * 89 libder_obj_alloc_simple(struct libder_ctx *ctx, uint8_t stype, 90 const uint8_t *payload_in, size_t length) 91 { 92 struct libder_object *obj; 93 struct libder_tag *type; 94 uint8_t *payload; 95 96 type = libder_type_alloc_simple(ctx, stype); 97 if (type == NULL) 98 return (NULL); 99 100 if (!libder_obj_alloc_check(ctx, type, payload_in, length)) { 101 libder_type_free(type); 102 return (NULL); 103 } 104 105 payload = libder_obj_alloc_copy_payload(ctx, payload_in, length); 106 107 obj = libder_obj_alloc_internal(ctx, type, payload, length, LDO_OWNTAG); 108 if (obj == NULL) { 109 if (length != 0) { 110 libder_bzero(payload, length); 111 free(payload); 112 } 113 114 libder_type_free(type); 115 libder_set_error(ctx, LDE_NOMEM); 116 } 117 118 return (obj); 119 } 120 121 /* 122 * Returns an obj on success, NULL if out of memory. `obj` takes ownership of 123 * the payload on success. 124 */ 125 LIBDER_PRIVATE struct libder_object * 126 libder_obj_alloc_internal(struct libder_ctx *ctx, struct libder_tag *type, 127 uint8_t *payload, size_t length, uint32_t flags) 128 { 129 struct libder_object *obj; 130 131 assert((flags & ~(LDO_OWNTAG)) == 0); 132 133 if (length != 0) 134 assert(payload != NULL); 135 else 136 assert(payload == NULL); 137 138 obj = malloc(sizeof(*obj)); 139 if (obj == NULL) 140 return (NULL); 141 142 if ((flags & LDO_OWNTAG) != 0) { 143 obj->type = type; 144 } else { 145 /* 146 * Deep copies the tag data, so that the caller can predict what 147 * it can do with the buffer. 148 */ 149 obj->type = libder_type_dup(ctx, type); 150 if (obj->type == NULL) { 151 free(obj); 152 return (NULL); 153 } 154 } 155 156 obj->length = length; 157 obj->payload = payload; 158 obj->children = obj->next = obj->parent = NULL; 159 obj->nchildren = 0; 160 161 return (obj); 162 } 163 164 LIBDER_PRIVATE size_t 165 libder_size_length(size_t sz) 166 { 167 size_t nbytes; 168 169 /* 170 * With DER, we use the smallest encoding necessary: less than 0x80 171 * can be encoded in one byte. 172 */ 173 if (sz < 0x80) 174 return (1); 175 176 /* 177 * We can support up to 0x7f size bytes, but we don't really have a way 178 * to represent that right now. It's a good thing this function only 179 * takes a size_t, otherwise this would be a bit wrong. 180 */ 181 for (nbytes = 1; nbytes < sizeof(size_t); nbytes++) { 182 if ((sz & ~((1ULL << 8 * nbytes) - 1)) == 0) 183 break; 184 } 185 186 /* Add one for the lead byte describing the length of the length. */ 187 return (nbytes + 1); 188 } 189 190 /* 191 * Returns the size on-disk. If an object has children, we encode the size as 192 * the sum of their lengths recursively. Otherwise, we use the object's size. 193 * 194 * Returns 0 if the object size would overflow a size_t... perhaps we could 195 * lift this restriction later. 196 * 197 * Note that the size of the object will be set/updated to simplify later write 198 * calculations. 199 */ 200 LIBDER_PRIVATE size_t 201 libder_obj_disk_size(struct libder_object *obj, bool include_header) 202 { 203 struct libder_object *walker; 204 size_t disk_size, header_size; 205 206 disk_size = obj->length; 207 if (obj->children != NULL) { 208 /* We should have rejected these. */ 209 assert(obj->length == 0); 210 211 DER_FOREACH_CHILD(walker, obj) { 212 size_t child_size; 213 214 child_size = libder_obj_disk_size(walker, true); 215 if (SIZE_MAX - child_size < disk_size) 216 return (0); /* Overflow */ 217 disk_size += child_size; 218 } 219 } 220 221 obj->disk_size = disk_size; 222 223 /* 224 * Children always include the header above, we only include the header 225 * at the root if we're calculating how much space we need in total. 226 */ 227 if (include_header) { 228 /* Size of the length + the tag (arbitrary length) */ 229 header_size = libder_size_length(disk_size) + obj->type->tag_size; 230 if (obj->type->tag_encoded) 231 header_size++; /* Lead byte */ 232 if (SIZE_MAX - header_size < disk_size) 233 return (0); 234 235 disk_size += header_size; 236 } 237 238 return (disk_size); 239 } 240 241 void 242 libder_obj_free(struct libder_object *obj) 243 { 244 struct libder_object *child, *tmp; 245 246 if (obj == NULL) 247 return; 248 249 DER_FOREACH_CHILD_SAFE(child, obj, tmp) 250 libder_obj_free(child); 251 252 if (obj->payload != NULL) { 253 libder_bzero(obj->payload, obj->length); 254 free(obj->payload); 255 } 256 257 libder_type_free(obj->type); 258 free(obj); 259 } 260 261 static void 262 libder_obj_unlink(struct libder_object *obj) 263 { 264 struct libder_object *child, *parent, *prev; 265 266 parent = obj->parent; 267 if (parent == NULL) 268 return; 269 270 prev = NULL; 271 assert(parent->nchildren > 0); 272 DER_FOREACH_CHILD(child, parent) { 273 if (child == obj) { 274 if (prev == NULL) 275 parent->children = child->next; 276 else 277 prev->next = child->next; 278 parent->nchildren--; 279 child->parent = NULL; 280 return; 281 } 282 283 prev = child; 284 } 285 286 assert(0 && "Internal inconsistency: parent set, but child not found"); 287 } 288 289 bool 290 libder_obj_append(struct libder_object *parent, struct libder_object *child) 291 { 292 struct libder_object *end, *walker; 293 294 if (!parent->type->tag_constructed) 295 return (false); 296 297 /* XXX Type check */ 298 299 if (child->parent != NULL) 300 libder_obj_unlink(child); 301 302 if (parent->nchildren == 0) { 303 parent->children = child; 304 parent->nchildren++; 305 return (true); 306 } 307 308 /* Walk the chain */ 309 DER_FOREACH_CHILD(walker, parent) { 310 end = walker; 311 } 312 313 assert(end != NULL); 314 end->next = child; 315 parent->nchildren++; 316 child->parent = parent; 317 return (true); 318 } 319 320 struct libder_object * 321 libder_obj_child(const struct libder_object *obj, size_t idx) 322 { 323 struct libder_object *cur; 324 325 DER_FOREACH_CHILD(cur, obj) { 326 if (idx-- == 0) 327 return (cur); 328 } 329 330 return (NULL); 331 } 332 333 struct libder_object * 334 libder_obj_children(const struct libder_object *obj) 335 { 336 337 return (obj->children); 338 } 339 340 struct libder_object * 341 libder_obj_next(const struct libder_object *obj) 342 { 343 344 return (obj->next); 345 } 346 347 struct libder_tag * 348 libder_obj_type(const struct libder_object *obj) 349 { 350 351 return (obj->type); 352 } 353 354 uint8_t 355 libder_obj_type_simple(const struct libder_object *obj) 356 { 357 struct libder_tag *type = obj->type; 358 uint8_t simple = type->tag_class << 6; 359 360 if (type->tag_constructed) 361 simple |= BER_TYPE_CONSTRUCTED_MASK; 362 363 if (type->tag_encoded) 364 simple |= 0x1f; /* Encode the "long tag" tag. */ 365 else 366 simple |= type->tag_short; 367 return (simple); 368 } 369 370 const uint8_t * 371 libder_obj_data(const struct libder_object *obj, size_t *osz) 372 { 373 374 if (obj->type->tag_constructed) 375 return (NULL); 376 377 *osz = obj->length; 378 return (obj->payload); 379 } 380 381 static const char * 382 libder_type_name(const struct libder_tag *type) 383 { 384 static char namebuf[128]; 385 386 if (type->tag_encoded) { 387 return ("{ ... }"); 388 } 389 390 if (type->tag_class != BC_UNIVERSAL) 391 goto fallback; 392 393 #define UTYPE(val) case val: return (&(#val)[3]) 394 switch (type->tag_short) { 395 UTYPE(BT_RESERVED); 396 UTYPE(BT_BOOLEAN); 397 UTYPE(BT_INTEGER); 398 UTYPE(BT_BITSTRING); 399 UTYPE(BT_OCTETSTRING); 400 UTYPE(BT_NULL); 401 UTYPE(BT_OID); 402 UTYPE(BT_OBJDESC); 403 UTYPE(BT_EXTERNAL); 404 UTYPE(BT_REAL); 405 UTYPE(BT_ENUMERATED); 406 UTYPE(BT_PDV); 407 UTYPE(BT_UTF8STRING); 408 UTYPE(BT_RELOID); 409 UTYPE(BT_NUMERICSTRING); 410 UTYPE(BT_STRING); 411 UTYPE(BT_TELEXSTRING); 412 UTYPE(BT_VIDEOTEXSTRING); 413 UTYPE(BT_IA5STRING); 414 UTYPE(BT_UTCTIME); 415 UTYPE(BT_GENTIME); 416 UTYPE(BT_GFXSTRING); 417 UTYPE(BT_VISSTRING); 418 UTYPE(BT_GENSTRING); 419 UTYPE(BT_UNIVSTRING); 420 UTYPE(BT_CHARSTRING); 421 UTYPE(BT_BMPSTRING); 422 case BT_SEQUENCE & ~BER_TYPE_CONSTRUCTED_MASK: 423 case BT_SEQUENCE: return "SEQUENCE"; 424 case BT_SET & ~BER_TYPE_CONSTRUCTED_MASK: 425 case BT_SET: return "SET"; 426 } 427 428 fallback: 429 snprintf(namebuf, sizeof(namebuf), "%.02x", libder_type_simple(type)); 430 return (&namebuf[0]); 431 } 432 433 static void 434 libder_obj_dump_internal(const struct libder_object *obj, FILE *fp, int lvl) 435 { 436 static char spacer[4096]; 437 const struct libder_object *child; 438 439 /* Primitive, goofy, but functional. */ 440 if (spacer[0] == '\0') 441 memset(spacer, '\t', sizeof(spacer)); 442 443 if (lvl >= (int)sizeof(spacer)) { 444 /* Too large, truncate the display. */ 445 fprintf(fp, "%.*s...\n", (int)sizeof(spacer), spacer); 446 return; 447 } 448 449 if (obj->children == NULL) { 450 size_t col = lvl * 8; 451 452 col += fprintf(fp, "%.*sOBJECT[type=%s, size=%zx]%s", 453 lvl, spacer, libder_type_name(obj->type), 454 obj->length, obj->length != 0 ? ": " : ""); 455 456 if (obj->length != 0) { 457 uint8_t printb; 458 459 #define LIBDER_CONTENTS_WRAP 80 460 for (size_t i = 0; i < obj->length; i++) { 461 if (col + 3 >= LIBDER_CONTENTS_WRAP) { 462 fprintf(fp, "\n%.*s ", lvl, spacer); 463 col = (lvl * 8) + 4; 464 } 465 466 if (obj->payload == NULL) 467 printb = 0; 468 else 469 printb = obj->payload[i]; 470 471 col += fprintf(fp, "%.02x ", printb); 472 } 473 } 474 475 fprintf(fp, "\n"); 476 477 return; 478 } 479 480 fprintf(fp, "%.*sOBJECT[type=%s]\n", lvl, spacer, 481 libder_type_name(obj->type)); 482 DER_FOREACH_CHILD(child, obj) 483 libder_obj_dump_internal(child, fp, lvl + 1); 484 } 485 486 void 487 libder_obj_dump(const struct libder_object *root, FILE *fp) 488 { 489 490 libder_obj_dump_internal(root, fp, 0); 491 } 492 493 LIBDER_PRIVATE bool 494 libder_is_valid_obj(struct libder_ctx *ctx, const struct libder_tag *type, 495 const uint8_t *payload, size_t payloadsz, bool varlen) 496 { 497 498 if (payload != NULL) { 499 assert(payloadsz > 0); 500 assert(!varlen); 501 } else { 502 assert(payloadsz == 0); 503 } 504 505 /* No rules for non-universal types. */ 506 if (type->tag_class != BC_UNIVERSAL || type->tag_encoded) 507 return (true); 508 509 if (ctx->strict && type->tag_constructed) { 510 /* Types that don't allow constructed */ 511 switch (libder_type_simple(type) & ~BER_TYPE_CONSTRUCTED_MASK) { 512 case BT_BOOLEAN: 513 case BT_INTEGER: 514 case BT_REAL: 515 case BT_NULL: 516 libder_set_error(ctx, LDE_STRICT_PRIMITIVE); 517 return (false); 518 default: 519 break; 520 } 521 } else if (ctx->strict) { 522 /* Types that cannot be primitive */ 523 switch (libder_type_simple(type) | BER_TYPE_CONSTRUCTED_MASK) { 524 case BT_SEQUENCE: 525 case BT_SET: 526 libder_set_error(ctx, LDE_STRICT_CONSTRUCTED); 527 return (false); 528 default: 529 break; 530 } 531 } 532 533 /* Further validation */ 534 switch (libder_type_simple(type)) { 535 case BT_BOOLEAN: 536 if (ctx->strict && payloadsz != 1) { 537 libder_set_error(ctx, LDE_STRICT_BOOLEAN); 538 return (false); 539 } 540 break; 541 case BT_NULL: 542 if (ctx->strict && (payloadsz != 0 || varlen)) { 543 libder_set_error(ctx, LDE_STRICT_NULL); 544 return (false); 545 } 546 break; 547 case BT_BITSTRING: /* Primitive */ 548 /* 549 * Bit strings require more invasive parsing later during child 550 * coalescing or normalization, so we alway strictly enforce 551 * their form. 552 */ 553 if (payloadsz == 1 && payload[0] != 0) 554 return (false); 555 556 /* We can't have more than seven unused bits. */ 557 return (payloadsz < 2 || payload[0] < 8); 558 case BT_RESERVED: 559 if (payloadsz != 0) { 560 libder_set_error(ctx, LDE_STRICT_EOC); 561 return (false); 562 } 563 break; 564 default: 565 break; 566 } 567 568 return (true); 569 } 570 571 LIBDER_PRIVATE bool 572 libder_obj_may_coalesce_children(const struct libder_object *obj) 573 { 574 575 /* No clue about non-universal types. */ 576 if (obj->type->tag_class != BC_UNIVERSAL || obj->type->tag_encoded) 577 return (false); 578 579 /* Constructed types don't have children. */ 580 if (!obj->type->tag_constructed) 581 return (false); 582 583 /* Strip the constructed bit off. */ 584 switch (libder_type_simple(obj->type)) { 585 case BT_OCTETSTRING: /* Raw data types */ 586 case BT_BITSTRING: 587 return (true); 588 case BT_UTF8STRING: /* String types */ 589 case BT_NUMERICSTRING: 590 case BT_STRING: 591 case BT_TELEXSTRING: 592 case BT_VIDEOTEXSTRING: 593 case BT_IA5STRING: 594 case BT_GFXSTRING: 595 case BT_VISSTRING: 596 case BT_GENSTRING: 597 case BT_UNIVSTRING: 598 case BT_CHARSTRING: 599 case BT_BMPSTRING: 600 return (true); 601 case BT_UTCTIME: /* Time types */ 602 case BT_GENTIME: 603 return (true); 604 default: 605 return (false); 606 } 607 } 608 609 static size_t 610 libder_merge_bitstrings(uint8_t *buf, size_t offset, size_t bufsz, 611 const struct libder_object *child) 612 { 613 const uint8_t *rhs = child->payload; 614 size_t rsz = child->disk_size, startoff = offset; 615 uint8_t rhsunused, unused; 616 617 rhsunused = (rhs != NULL ? rhs[0] : 0); 618 619 /* We have no unused bits if the buffer's empty as of yet. */ 620 if (offset == 0) 621 unused = 0; 622 else 623 unused = buf[0]; 624 625 /* Shave the lead byte off if we have one. */ 626 if (rsz > 1) { 627 if (rhs != NULL) 628 rhs++; 629 rsz--; 630 } 631 632 if (unused == 0) { 633 size_t extra = 0; 634 635 /* 636 * In all cases we'll just write the unused byte separately, 637 * since we're copying way past it in the common case and can't 638 * just overwrite it as part of the memcpy(). 639 */ 640 if (offset == 0) { 641 offset = 1; 642 extra++; 643 } 644 645 assert(rhsunused < 8); 646 assert(offset + rsz <= bufsz); 647 648 buf[0] = rhsunused; 649 if (rhs == NULL) 650 memset(&buf[offset], 0, rsz); 651 else 652 memcpy(&buf[offset], rhs, rsz); 653 654 return (rsz + extra); 655 } 656 657 for (size_t i = 0; i < rsz; i++) { 658 uint8_t bits, next; 659 660 if (rhs == NULL) 661 next = 0; 662 else 663 next = rhs[i]; 664 665 /* Rotate the leading bits into the byte before it. */ 666 assert(unused < 8); 667 bits = next >> (8 - unused); 668 buf[offset - 1] |= bits; 669 670 next <<= unused; 671 672 /* 673 * Copy the new valid bits in; we shift over the old unused 674 * amount up until the very last bit, then we have to recalculate 675 * because we may be dropping it entirely. 676 */ 677 if (i == rsz - 1) { 678 assert(rhsunused < 8); 679 680 /* 681 * Figure out how many unused bits we have between the two 682 * buffers, sum % 8 is the new # unused bits. It will be 683 * somewhere in the range of [0, 14], and if it's at or 684 * higher than a single byte then that's a clear indicator 685 * that we shifted some unused bits into the previous byte and 686 * can just halt here. 687 */ 688 unused += rhsunused; 689 buf[0] = unused % 8; 690 if (unused >= 8) 691 break; 692 } 693 694 assert(offset < bufsz); 695 buf[offset++] = next; 696 } 697 698 return (offset - startoff); 699 } 700 701 LIBDER_PRIVATE bool 702 libder_obj_coalesce_children(struct libder_object *obj, struct libder_ctx *ctx) 703 { 704 struct libder_object *child, *last_child, *tmp; 705 size_t new_size = 0, offset = 0; 706 uint8_t *coalesced_data; 707 uint8_t type; 708 bool need_payload = false, strict_violation = false; 709 710 if (obj->nchildren == 0 || !libder_obj_may_coalesce_children(obj)) 711 return (true); 712 713 assert(obj->type->tag_class == BC_UNIVERSAL); 714 assert(obj->type->tag_constructed); 715 assert(!obj->type->tag_encoded); 716 type = obj->type->tag_short; 717 718 last_child = NULL; 719 DER_FOREACH_CHILD(child, obj) { 720 /* Sanity check and coalesce our children. */ 721 if (child->type->tag_class != BC_UNIVERSAL || 722 child->type->tag_short != obj->type->tag_short) { 723 libder_set_error(ctx, LDE_COALESCE_BADCHILD); 724 return (false); 725 } 726 727 /* Recursively coalesce everything. */ 728 if (!libder_obj_coalesce_children(child, ctx)) 729 return (false); 730 731 /* 732 * The child node will be disappearing anyways, so we stash the 733 * disk size sans header in its disk_size to reuse in the later 734 * loop. 735 */ 736 child->disk_size = libder_obj_disk_size(child, false); 737 738 /* 739 * We strip the lead byte off of every element, and add it back 740 * in pre-allocation. 741 */ 742 if (type == BT_BITSTRING && child->disk_size > 1) 743 child->disk_size--; 744 if (child->disk_size > 0) 745 last_child = child; 746 747 new_size += child->disk_size; 748 749 if (child->payload != NULL) 750 need_payload = true; 751 } 752 753 if (new_size != 0 && need_payload) { 754 if (type == BT_BITSTRING) 755 new_size++; 756 coalesced_data = malloc(new_size); 757 if (coalesced_data == NULL) { 758 libder_set_error(ctx, LDE_NOMEM); 759 return (false); 760 } 761 } else { 762 /* 763 * This would perhaps be a bit weird, but that's normalization 764 * for you. We shouldn't really have a UTF-8 string that's 765 * composed of a series of zero-length UTF-8 strings, but 766 * weirder things have happened. 767 */ 768 coalesced_data = NULL; 769 } 770 771 /* Avoid leaking any children as we coalesce. */ 772 DER_FOREACH_CHILD_SAFE(child, obj, tmp) { 773 if (child->disk_size != 0) 774 assert(coalesced_data != NULL || !need_payload); 775 776 /* 777 * Just free everything when we violate strict rules. 778 */ 779 if (strict_violation) 780 goto violated; 781 782 if (child->disk_size != 0 && need_payload) { 783 assert(coalesced_data != NULL); 784 assert(offset + child->disk_size <= new_size); 785 786 /* 787 * Bit strings are special, in that the first byte 788 * contains the number of unused bits at the end. We 789 * need to trim that off when concatenating bit strings 790 */ 791 if (type == BT_BITSTRING) { 792 if (ctx->strict && child != last_child && 793 child->disk_size > 1 && child->payload != NULL) { 794 /* 795 * Each child must have a multiple of 8, 796 * up until the final one. 797 */ 798 if (child->payload[0] != 0) { 799 libder_set_error(ctx, LDE_STRICT_BITSTRING); 800 strict_violation = true; 801 goto violated; 802 } 803 } 804 805 offset += libder_merge_bitstrings(coalesced_data, 806 offset, new_size, child); 807 } else { 808 /* 809 * Write zeroes out if we don't have a payload. 810 */ 811 if (child->payload == NULL) { 812 memset(&coalesced_data[offset], 0, child->disk_size); 813 offset += child->disk_size; 814 } else { 815 memcpy(&coalesced_data[offset], child->payload, 816 child->disk_size); 817 offset += child->disk_size; 818 } 819 } 820 } 821 822 violated: 823 libder_obj_free(child); 824 } 825 826 assert(offset <= new_size); 827 828 /* Zap the children, we've absorbed their bodies. */ 829 obj->children = NULL; 830 831 if (strict_violation) { 832 if (coalesced_data != NULL) { 833 libder_bzero(coalesced_data, offset); 834 free(coalesced_data); 835 } 836 837 return (false); 838 } 839 840 /* Finally, swap out the payload. */ 841 if (obj->payload != NULL) { 842 libder_bzero(obj->payload, obj->length); 843 free(obj->payload); 844 } 845 846 obj->length = offset; 847 obj->payload = coalesced_data; 848 obj->type->tag_constructed = false; 849 850 return (true); 851 } 852 853 static bool 854 libder_obj_normalize_bitstring(struct libder_object *obj) 855 { 856 uint8_t *payload = obj->payload; 857 size_t length = obj->length; 858 uint8_t unused; 859 860 if (payload == NULL || length < 2) 861 return (true); 862 863 unused = payload[0]; 864 if (unused == 0) 865 return (true); 866 867 /* Clear the unused bits completely. */ 868 payload[length - 1] &= ~((1 << unused) - 1); 869 return (true); 870 } 871 872 static bool 873 libder_obj_normalize_boolean(struct libder_object *obj) 874 { 875 uint8_t *payload = obj->payload; 876 size_t length = obj->length; 877 int sense = 0; 878 879 assert(length > 0); 880 881 /* 882 * Booleans must be collapsed down to a single byte, 0x00 or 0xff, 883 * indicating false or true respectively. 884 */ 885 if (length == 1 && (payload[0] == 0x00 || payload[0] == 0xff)) 886 return (true); 887 888 for (size_t bpos = 0; bpos < length; bpos++) { 889 sense |= payload[bpos]; 890 if (sense != 0) 891 break; 892 } 893 894 payload[0] = sense != 0 ? 0xff : 0x00; 895 obj->length = 1; 896 return (true); 897 } 898 899 static bool 900 libder_obj_normalize_integer(struct libder_object *obj) 901 { 902 uint8_t *payload = obj->payload; 903 size_t length = obj->length; 904 size_t strip = 0; 905 906 /* 907 * Strip any leading sign-extended looking bytes, but note that 908 * we can't strip a leading byte unless it matches the sign bit 909 * on the next byte. 910 */ 911 for (size_t bpos = 0; bpos < length - 1; bpos++) { 912 if (payload[bpos] != 0 && payload[bpos] != 0xff) 913 break; 914 915 if (payload[bpos] == 0xff) { 916 /* Only if next byte indicates signed. */ 917 if ((payload[bpos + 1] & 0x80) == 0) 918 break; 919 } else { 920 /* Only if next byte indicates unsigned. */ 921 if ((payload[bpos + 1] & 0x80) != 0) 922 break; 923 } 924 925 strip++; 926 } 927 928 if (strip != 0) { 929 payload += strip; 930 length -= strip; 931 932 memmove(&obj->payload[0], payload, length); 933 obj->length = length; 934 } 935 936 return (true); 937 } 938 939 static int 940 libder_obj_tag_compare(const struct libder_tag *lhs, const struct libder_tag *rhs) 941 { 942 const uint8_t *lbits, *rbits; 943 size_t delta, end, lsz, rsz; 944 uint8_t lbyte, rbyte; 945 946 /* Highest bits: tag class, libder_ber_class has the same bit ordering. */ 947 if (lhs->tag_class < rhs->tag_class) 948 return (-1); 949 if (lhs->tag_class > rhs->tag_class) 950 return (1); 951 952 /* Next bit: constructed vs. primitive */ 953 if (!lhs->tag_constructed && rhs->tag_constructed) 954 return (-1); 955 if (lhs->tag_constructed && rhs->tag_constructed) 956 return (1); 957 958 /* 959 * Finally: tag data; we can use the size as a first-order heuristic 960 * because we store tags in the shortest possible representation. 961 */ 962 if (lhs->tag_size < rhs->tag_size) 963 return (-1); 964 else if (lhs->tag_size > rhs->tag_size) 965 return (1); 966 967 if (!lhs->tag_encoded) { 968 lbits = (const void *)&lhs->tag_short; 969 lsz = sizeof(uint64_t); 970 } else { 971 lbits = lhs->tag_long; 972 lsz = lhs->tag_size; 973 } 974 975 if (!rhs->tag_encoded) { 976 rbits = (const void *)&rhs->tag_short; 977 rsz = sizeof(uint64_t); 978 } else { 979 rbits = rhs->tag_long; 980 rsz = rhs->tag_size; 981 } 982 983 delta = 0; 984 end = MAX(lsz, rsz); 985 if (lsz > rsz) 986 delta = lsz - rsz; 987 else if (lsz < rsz) 988 delta = rsz - lsz; 989 for (size_t i = 0; i < end; i++) { 990 /* Zero-extend the short one the difference. */ 991 if (lsz < rsz && i < delta) 992 lbyte = 0; 993 else 994 lbyte = lbits[i - delta]; 995 996 if (lsz > rsz && i < delta) 997 rbyte = 0; 998 else 999 rbyte = rbits[i - delta]; 1000 1001 if (lbyte < rbyte) 1002 return (-1); 1003 else if (lbyte > rbyte) 1004 return (-1); 1005 } 1006 1007 return (0); 1008 } 1009 1010 /* 1011 * Similar to strcmp(), returns -1, 0, or 1. 1012 */ 1013 static int 1014 libder_obj_compare(const struct libder_object *lhs, const struct libder_object *rhs) 1015 { 1016 size_t end; 1017 int cmp; 1018 uint8_t lbyte, rbyte; 1019 1020 cmp = libder_obj_tag_compare(lhs->type, rhs->type); 1021 if (cmp != 0) 1022 return (cmp); 1023 1024 /* 1025 * We'll compare up to the longer of the two; the shorter payload is 1026 * zero-extended at the end for comparison purposes. 1027 */ 1028 end = MAX(lhs->length, rhs->length); 1029 for (size_t pos = 0; pos < end; pos++) { 1030 if (lhs->payload != NULL && pos < lhs->length) 1031 lbyte = lhs->payload[pos]; 1032 else 1033 lbyte = 0; 1034 if (rhs->payload != NULL && pos < rhs->length) 1035 rbyte = rhs->payload[pos]; 1036 else 1037 rbyte = 0; 1038 1039 if (lbyte < rbyte) 1040 return (-1); 1041 else if (lbyte > rbyte) 1042 return (1); 1043 } 1044 1045 return (0); 1046 } 1047 1048 static int 1049 libder_obj_normalize_set_cmp(const void *lhs_entry, const void *rhs_entry) 1050 { 1051 const struct libder_object *lhs = 1052 *__DECONST(const struct libder_object **, lhs_entry); 1053 const struct libder_object *rhs = 1054 *__DECONST(const struct libder_object **, rhs_entry); 1055 1056 return (libder_obj_compare(lhs, rhs)); 1057 } 1058 1059 static bool 1060 libder_obj_normalize_set(struct libder_object *obj, struct libder_ctx *ctx) 1061 { 1062 struct libder_object **sorting; 1063 struct libder_object *child; 1064 size_t offset = 0; 1065 1066 if (obj->nchildren < 2) 1067 return (true); 1068 1069 /* 1070 * Kind of goofy, but we'll just take advantage of a standardized 1071 * qsort() rather than rolling our own sort -- we have no idea how large 1072 * of a dataset we're working with. 1073 */ 1074 sorting = calloc(obj->nchildren, sizeof(*sorting)); 1075 if (sorting == NULL) { 1076 libder_set_error(ctx, LDE_NOMEM); 1077 return (false); 1078 } 1079 1080 DER_FOREACH_CHILD(child, obj) { 1081 sorting[offset++] = child; 1082 } 1083 1084 assert(offset == obj->nchildren); 1085 qsort(sorting, offset, sizeof(*sorting), libder_obj_normalize_set_cmp); 1086 1087 obj->children = sorting[0]; 1088 sorting[offset - 1]->next = NULL; 1089 for (size_t i = 0; i < offset - 1; i++) { 1090 sorting[i]->next = sorting[i + 1]; 1091 } 1092 1093 free(sorting); 1094 1095 return (true); 1096 } 1097 1098 LIBDER_PRIVATE bool 1099 libder_obj_normalize(struct libder_object *obj, struct libder_ctx *ctx) 1100 { 1101 uint8_t *payload = obj->payload; 1102 size_t length = obj->length; 1103 1104 if (obj->type->tag_constructed) { 1105 /* 1106 * For constructed types, we'll see if we can coalesce their 1107 * children into them, then we'll proceed with whatever normalization 1108 * rules we can apply to the children. 1109 */ 1110 if (DER_NORMALIZING(ctx, CONSTRUCTED) && !libder_obj_coalesce_children(obj, ctx)) 1111 return (false); 1112 1113 /* 1114 * We may not be a constructed object anymore after the above coalescing 1115 * happened, so we check it again here. Constructed objects need not go 1116 * any further, but the now-primitive coalesced types still need to be 1117 * normalized. 1118 */ 1119 if (obj->type->tag_constructed) { 1120 struct libder_object *child; 1121 1122 DER_FOREACH_CHILD(child, obj) { 1123 if (!libder_obj_normalize(child, ctx)) 1124 return (false); 1125 } 1126 1127 /* Sets must be sorted. */ 1128 if (obj->type->tag_short != BT_SET) 1129 return (true); 1130 1131 return (libder_obj_normalize_set(obj, ctx)); 1132 } 1133 } 1134 1135 /* We only have normalization rules for universal types. */ 1136 if (obj->type->tag_class != BC_UNIVERSAL || obj->type->tag_encoded) 1137 return (true); 1138 1139 if (!libder_normalizing_type(ctx, obj->type)) 1140 return (true); 1141 1142 /* 1143 * We are clear to normalize this object, check for some easy cases that 1144 * don't need normalization. 1145 */ 1146 switch (libder_type_simple(obj->type)) { 1147 case BT_BITSTRING: 1148 case BT_BOOLEAN: 1149 case BT_INTEGER: 1150 /* 1151 * If we have a zero payload, then we need to encode them as a 1152 * single zero byte. 1153 */ 1154 if (payload == NULL) { 1155 if (length != 1) 1156 obj->length = 1; 1157 1158 return (true); 1159 } 1160 1161 break; 1162 case BT_NULL: 1163 if (payload != NULL) { 1164 free(payload); 1165 1166 obj->payload = NULL; 1167 obj->length = 0; 1168 } 1169 1170 return (true); 1171 default: 1172 /* 1173 * If we don't have a payload, we'll just leave it alone. 1174 */ 1175 if (payload == NULL) 1176 return (true); 1177 break; 1178 } 1179 1180 switch (libder_type_simple(obj->type)) { 1181 case BT_BITSTRING: 1182 return (libder_obj_normalize_bitstring(obj)); 1183 case BT_BOOLEAN: 1184 return (libder_obj_normalize_boolean(obj)); 1185 case BT_INTEGER: 1186 return (libder_obj_normalize_integer(obj)); 1187 default: 1188 break; 1189 } 1190 1191 return (true); 1192 }