1 /* Copyright (c) 2014, Google Inc. 2 * 3 * Permission to use, copy, modify, and/or distribute this software for any 4 * purpose with or without fee is hereby granted, provided that the above 5 * copyright notice and this permission notice appear in all copies. 6 * 7 * THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES 8 * WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF 9 * MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY 10 * SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES 11 * WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN ACTION 12 * OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF OR IN 13 * CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE. */ 14 15 #include <openssl/bytestring.h> 16 17 #include <assert.h> 18 #include <limits.h> 19 #include <string.h> 20 21 #include <openssl/buf.h> 22 #include <openssl/mem.h> 23 24 #include "../internal.h" 25 26 27 void CBB_zero(CBB *cbb) { 28 OPENSSL_memset(cbb, 0, sizeof(CBB)); 29 } 30 31 static int cbb_init(CBB *cbb, uint8_t *buf, size_t cap) { 32 // This assumes that |cbb| has already been zeroed. 33 struct cbb_buffer_st *base; 34 35 base = OPENSSL_malloc(sizeof(struct cbb_buffer_st)); 36 if (base == NULL) { 37 return 0; 38 } 39 40 base->buf = buf; 41 base->len = 0; 42 base->cap = cap; 43 base->can_resize = 1; 44 base->error = 0; 45 46 cbb->base = base; 47 cbb->is_top_level = 1; 48 return 1; 49 } 50 51 int CBB_init(CBB *cbb, size_t initial_capacity) { 52 CBB_zero(cbb); 53 54 uint8_t *buf = OPENSSL_malloc(initial_capacity); 55 if (initial_capacity > 0 && buf == NULL) { 56 return 0; 57 } 58 59 if (!cbb_init(cbb, buf, initial_capacity)) { 60 OPENSSL_free(buf); 61 return 0; 62 } 63 64 return 1; 65 } 66 67 int CBB_init_fixed(CBB *cbb, uint8_t *buf, size_t len) { 68 CBB_zero(cbb); 69 70 if (!cbb_init(cbb, buf, len)) { 71 return 0; 72 } 73 74 cbb->base->can_resize = 0; 75 return 1; 76 } 77 78 void CBB_cleanup(CBB *cbb) { 79 if (cbb->base) { 80 // Only top-level |CBB|s are cleaned up. Child |CBB|s are non-owning. They 81 // are implicitly discarded when the parent is flushed or cleaned up. 82 assert(cbb->is_top_level); 83 84 if (cbb->base->can_resize) { 85 OPENSSL_free(cbb->base->buf); 86 } 87 OPENSSL_free(cbb->base); 88 } 89 cbb->base = NULL; 90 } 91 92 static int cbb_buffer_reserve(struct cbb_buffer_st *base, uint8_t **out, 93 size_t len) { 94 size_t newlen; 95 96 if (base == NULL) { 97 return 0; 98 } 99 100 newlen = base->len + len; 101 if (newlen < base->len) { 102 // Overflow 103 goto err; 104 } 105 106 if (newlen > base->cap) { 107 size_t newcap = base->cap * 2; 108 uint8_t *newbuf; 109 110 if (!base->can_resize) { 111 goto err; 112 } 113 114 if (newcap < base->cap || newcap < newlen) { 115 newcap = newlen; 116 } 117 newbuf = OPENSSL_realloc(base->buf, newcap); 118 if (newbuf == NULL) { 119 goto err; 120 } 121 122 base->buf = newbuf; 123 base->cap = newcap; 124 } 125 126 if (out) { 127 *out = base->buf + base->len; 128 } 129 130 return 1; 131 132 err: 133 base->error = 1; 134 return 0; 135 } 136 137 static int cbb_buffer_add(struct cbb_buffer_st *base, uint8_t **out, 138 size_t len) { 139 if (!cbb_buffer_reserve(base, out, len)) { 140 return 0; 141 } 142 // This will not overflow or |cbb_buffer_reserve| would have failed. 143 base->len += len; 144 return 1; 145 } 146 147 static int cbb_buffer_add_u(struct cbb_buffer_st *base, uint32_t v, 148 size_t len_len) { 149 if (len_len == 0) { 150 return 1; 151 } 152 153 uint8_t *buf; 154 if (!cbb_buffer_add(base, &buf, len_len)) { 155 return 0; 156 } 157 158 for (size_t i = len_len - 1; i < len_len; i--) { 159 buf[i] = v; 160 v >>= 8; 161 } 162 163 if (v != 0) { 164 base->error = 1; 165 return 0; 166 } 167 168 return 1; 169 } 170 171 int CBB_finish(CBB *cbb, uint8_t **out_data, size_t *out_len) { 172 if (!cbb->is_top_level) { 173 return 0; 174 } 175 176 if (!CBB_flush(cbb)) { 177 return 0; 178 } 179 180 if (cbb->base->can_resize && (out_data == NULL || out_len == NULL)) { 181 // |out_data| and |out_len| can only be NULL if the CBB is fixed. 182 return 0; 183 } 184 185 if (out_data != NULL) { 186 *out_data = cbb->base->buf; 187 } 188 if (out_len != NULL) { 189 *out_len = cbb->base->len; 190 } 191 cbb->base->buf = NULL; 192 CBB_cleanup(cbb); 193 return 1; 194 } 195 196 // CBB_flush recurses and then writes out any pending length prefix. The 197 // current length of the underlying base is taken to be the length of the 198 // length-prefixed data. 199 int CBB_flush(CBB *cbb) { 200 size_t child_start, i, len; 201 202 // If |cbb->base| has hit an error, the buffer is in an undefined state, so 203 // fail all following calls. In particular, |cbb->child| may point to invalid 204 // memory. 205 if (cbb->base == NULL || cbb->base->error) { 206 return 0; 207 } 208 209 if (cbb->child == NULL || cbb->child->pending_len_len == 0) { 210 return 1; 211 } 212 213 child_start = cbb->child->offset + cbb->child->pending_len_len; 214 215 if (!CBB_flush(cbb->child) || 216 child_start < cbb->child->offset || 217 cbb->base->len < child_start) { 218 goto err; 219 } 220 221 len = cbb->base->len - child_start; 222 223 if (cbb->child->pending_is_asn1) { 224 // For ASN.1 we assume that we'll only need a single byte for the length. 225 // If that turned out to be incorrect, we have to move the contents along 226 // in order to make space. 227 uint8_t len_len; 228 uint8_t initial_length_byte; 229 230 assert (cbb->child->pending_len_len == 1); 231 232 if (len > 0xfffffffe) { 233 // Too large. 234 goto err; 235 } else if (len > 0xffffff) { 236 len_len = 5; 237 initial_length_byte = 0x80 | 4; 238 } else if (len > 0xffff) { 239 len_len = 4; 240 initial_length_byte = 0x80 | 3; 241 } else if (len > 0xff) { 242 len_len = 3; 243 initial_length_byte = 0x80 | 2; 244 } else if (len > 0x7f) { 245 len_len = 2; 246 initial_length_byte = 0x80 | 1; 247 } else { 248 len_len = 1; 249 initial_length_byte = (uint8_t)len; 250 len = 0; 251 } 252 253 if (len_len != 1) { 254 // We need to move the contents along in order to make space. 255 size_t extra_bytes = len_len - 1; 256 if (!cbb_buffer_add(cbb->base, NULL, extra_bytes)) { 257 goto err; 258 } 259 OPENSSL_memmove(cbb->base->buf + child_start + extra_bytes, 260 cbb->base->buf + child_start, len); 261 } 262 cbb->base->buf[cbb->child->offset++] = initial_length_byte; 263 cbb->child->pending_len_len = len_len - 1; 264 } 265 266 for (i = cbb->child->pending_len_len - 1; i < cbb->child->pending_len_len; 267 i--) { 268 cbb->base->buf[cbb->child->offset + i] = (uint8_t)len; 269 len >>= 8; 270 } 271 if (len != 0) { 272 goto err; 273 } 274 275 cbb->child->base = NULL; 276 cbb->child = NULL; 277 278 return 1; 279 280 err: 281 cbb->base->error = 1; 282 return 0; 283 } 284 285 const uint8_t *CBB_data(const CBB *cbb) { 286 assert(cbb->child == NULL); 287 return cbb->base->buf + cbb->offset + cbb->pending_len_len; 288 } 289 290 size_t CBB_len(const CBB *cbb) { 291 assert(cbb->child == NULL); 292 assert(cbb->offset + cbb->pending_len_len <= cbb->base->len); 293 294 return cbb->base->len - cbb->offset - cbb->pending_len_len; 295 } 296 297 static int cbb_add_length_prefixed(CBB *cbb, CBB *out_contents, 298 uint8_t len_len) { 299 uint8_t *prefix_bytes; 300 301 if (!CBB_flush(cbb)) { 302 return 0; 303 } 304 305 size_t offset = cbb->base->len; 306 if (!cbb_buffer_add(cbb->base, &prefix_bytes, len_len)) { 307 return 0; 308 } 309 310 OPENSSL_memset(prefix_bytes, 0, len_len); 311 OPENSSL_memset(out_contents, 0, sizeof(CBB)); 312 out_contents->base = cbb->base; 313 cbb->child = out_contents; 314 cbb->child->offset = offset; 315 cbb->child->pending_len_len = len_len; 316 cbb->child->pending_is_asn1 = 0; 317 318 return 1; 319 } 320 321 int CBB_add_u8_length_prefixed(CBB *cbb, CBB *out_contents) { 322 return cbb_add_length_prefixed(cbb, out_contents, 1); 323 } 324 325 int CBB_add_u16_length_prefixed(CBB *cbb, CBB *out_contents) { 326 return cbb_add_length_prefixed(cbb, out_contents, 2); 327 } 328 329 int CBB_add_u24_length_prefixed(CBB *cbb, CBB *out_contents) { 330 return cbb_add_length_prefixed(cbb, out_contents, 3); 331 } 332 333 // add_base128_integer encodes |v| as a big-endian base-128 integer where the 334 // high bit of each byte indicates where there is more data. This is the 335 // encoding used in DER for both high tag number form and OID components. 336 static int add_base128_integer(CBB *cbb, uint64_t v) { 337 unsigned len_len = 0; 338 uint64_t copy = v; 339 while (copy > 0) { 340 len_len++; 341 copy >>= 7; 342 } 343 if (len_len == 0) { 344 len_len = 1; // Zero is encoded with one byte. 345 } 346 for (unsigned i = len_len - 1; i < len_len; i--) { 347 uint8_t byte = (v >> (7 * i)) & 0x7f; 348 if (i != 0) { 349 // The high bit denotes whether there is more data. 350 byte |= 0x80; 351 } 352 if (!CBB_add_u8(cbb, byte)) { 353 return 0; 354 } 355 } 356 return 1; 357 } 358 359 int CBB_add_asn1(CBB *cbb, CBB *out_contents, unsigned tag) { 360 if (!CBB_flush(cbb)) { 361 return 0; 362 } 363 364 // Split the tag into leading bits and tag number. 365 uint8_t tag_bits = (tag >> CBS_ASN1_TAG_SHIFT) & 0xe0; 366 unsigned tag_number = tag & CBS_ASN1_TAG_NUMBER_MASK; 367 if (tag_number >= 0x1f) { 368 // Set all the bits in the tag number to signal high tag number form. 369 if (!CBB_add_u8(cbb, tag_bits | 0x1f) || 370 !add_base128_integer(cbb, tag_number)) { 371 return 0; 372 } 373 } else if (!CBB_add_u8(cbb, tag_bits | tag_number)) { 374 return 0; 375 } 376 377 size_t offset = cbb->base->len; 378 if (!CBB_add_u8(cbb, 0)) { 379 return 0; 380 } 381 382 OPENSSL_memset(out_contents, 0, sizeof(CBB)); 383 out_contents->base = cbb->base; 384 cbb->child = out_contents; 385 cbb->child->offset = offset; 386 cbb->child->pending_len_len = 1; 387 cbb->child->pending_is_asn1 = 1; 388 389 return 1; 390 } 391 392 int CBB_add_bytes(CBB *cbb, const uint8_t *data, size_t len) { 393 uint8_t *dest; 394 395 if (!CBB_flush(cbb) || 396 !cbb_buffer_add(cbb->base, &dest, len)) { 397 return 0; 398 } 399 OPENSSL_memcpy(dest, data, len); 400 return 1; 401 } 402 403 int CBB_add_space(CBB *cbb, uint8_t **out_data, size_t len) { 404 if (!CBB_flush(cbb) || 405 !cbb_buffer_add(cbb->base, out_data, len)) { 406 return 0; 407 } 408 return 1; 409 } 410 411 int CBB_reserve(CBB *cbb, uint8_t **out_data, size_t len) { 412 if (!CBB_flush(cbb) || 413 !cbb_buffer_reserve(cbb->base, out_data, len)) { 414 return 0; 415 } 416 return 1; 417 } 418 419 int CBB_did_write(CBB *cbb, size_t len) { 420 size_t newlen = cbb->base->len + len; 421 if (cbb->child != NULL || 422 newlen < cbb->base->len || 423 newlen > cbb->base->cap) { 424 return 0; 425 } 426 cbb->base->len = newlen; 427 return 1; 428 } 429 430 int CBB_add_u8(CBB *cbb, uint8_t value) { 431 if (!CBB_flush(cbb)) { 432 return 0; 433 } 434 435 return cbb_buffer_add_u(cbb->base, value, 1); 436 } 437 438 int CBB_add_u16(CBB *cbb, uint16_t value) { 439 if (!CBB_flush(cbb)) { 440 return 0; 441 } 442 443 return cbb_buffer_add_u(cbb->base, value, 2); 444 } 445 446 int CBB_add_u24(CBB *cbb, uint32_t value) { 447 if (!CBB_flush(cbb)) { 448 return 0; 449 } 450 451 return cbb_buffer_add_u(cbb->base, value, 3); 452 } 453 454 int CBB_add_u32(CBB *cbb, uint32_t value) { 455 if (!CBB_flush(cbb)) { 456 return 0; 457 } 458 459 return cbb_buffer_add_u(cbb->base, value, 4); 460 } 461 462 void CBB_discard_child(CBB *cbb) { 463 if (cbb->child == NULL) { 464 return; 465 } 466 467 cbb->base->len = cbb->child->offset; 468 469 cbb->child->base = NULL; 470 cbb->child = NULL; 471 } 472 473 int CBB_add_asn1_uint64(CBB *cbb, uint64_t value) { 474 CBB child; 475 int started = 0; 476 477 if (!CBB_add_asn1(cbb, &child, CBS_ASN1_INTEGER)) { 478 return 0; 479 } 480 481 for (size_t i = 0; i < 8; i++) { 482 uint8_t byte = (value >> 8*(7-i)) & 0xff; 483 if (!started) { 484 if (byte == 0) { 485 // Don't encode leading zeros. 486 continue; 487 } 488 // If the high bit is set, add a padding byte to make it 489 // unsigned. 490 if ((byte & 0x80) && !CBB_add_u8(&child, 0)) { 491 return 0; 492 } 493 started = 1; 494 } 495 if (!CBB_add_u8(&child, byte)) { 496 return 0; 497 } 498 } 499 500 // 0 is encoded as a single 0, not the empty string. 501 if (!started && !CBB_add_u8(&child, 0)) { 502 return 0; 503 } 504 505 return CBB_flush(cbb); 506 } 507 508 int CBB_add_asn1_octet_string(CBB *cbb, const uint8_t *data, size_t data_len) { 509 CBB child; 510 if (!CBB_add_asn1(cbb, &child, CBS_ASN1_OCTETSTRING) || 511 !CBB_add_bytes(&child, data, data_len) || 512 !CBB_flush(cbb)) { 513 return 0; 514 } 515 516 return 1; 517 } 518 519 int CBB_add_asn1_bool(CBB *cbb, int value) { 520 CBB child; 521 if (!CBB_add_asn1(cbb, &child, CBS_ASN1_BOOLEAN) || 522 !CBB_add_u8(&child, value != 0 ? 0xff : 0) || 523 !CBB_flush(cbb)) { 524 return 0; 525 } 526 527 return 1; 528 } 529 530 // parse_dotted_decimal parses one decimal component from |cbs|, where |cbs| is 531 // an OID literal, e.g., "1.2.840.113554.4.1.72585". It consumes both the 532 // component and the dot, so |cbs| may be passed into the function again for the 533 // next value. 534 static int parse_dotted_decimal(CBS *cbs, uint64_t *out) { 535 *out = 0; 536 int seen_digit = 0; 537 for (;;) { 538 // Valid terminators for a component are the end of the string or a 539 // non-terminal dot. If the string ends with a dot, this is not a valid OID 540 // string. 541 uint8_t u; 542 if (!CBS_get_u8(cbs, &u) || 543 (u == '.' && CBS_len(cbs) > 0)) { 544 break; 545 } 546 if (u < '0' || u > '9' || 547 // Forbid stray leading zeros. 548 (seen_digit && *out == 0) || 549 // Check for overflow. 550 *out > UINT64_MAX / 10 || 551 *out * 10 > UINT64_MAX - (u - '0')) { 552 return 0; 553 } 554 *out = *out * 10 + (u - '0'); 555 seen_digit = 1; 556 } 557 // The empty string is not a legal OID component. 558 return seen_digit; 559 } 560 561 int CBB_add_asn1_oid_from_text(CBB *cbb, const char *text, size_t len) { 562 if (!CBB_flush(cbb)) { 563 return 0; 564 } 565 566 CBS cbs; 567 CBS_init(&cbs, (const uint8_t *)text, len); 568 569 // OIDs must have at least two components. 570 uint64_t a, b; 571 if (!parse_dotted_decimal(&cbs, &a) || 572 !parse_dotted_decimal(&cbs, &b)) { 573 return 0; 574 } 575 576 // The first component is encoded as 40 * |a| + |b|. This assumes that |a| is 577 // 0, 1, or 2 and that, when it is 0 or 1, |b| is at most 39. 578 if (a > 2 || 579 (a < 2 && b > 39) || 580 b > UINT64_MAX - 80 || 581 !add_base128_integer(cbb, 40u * a + b)) { 582 return 0; 583 } 584 585 // The remaining components are encoded unmodified. 586 while (CBS_len(&cbs) > 0) { 587 if (!parse_dotted_decimal(&cbs, &a) || 588 !add_base128_integer(cbb, a)) { 589 return 0; 590 } 591 } 592 593 return 1; 594 } 595 596 static int compare_set_of_element(const void *a_ptr, const void *b_ptr) { 597 // See X.690, section 11.6 for the ordering. They are sorted in ascending 598 // order by their DER encoding. 599 const CBS *a = a_ptr, *b = b_ptr; 600 size_t a_len = CBS_len(a), b_len = CBS_len(b); 601 size_t min_len = a_len < b_len ? a_len : b_len; 602 int ret = OPENSSL_memcmp(CBS_data(a), CBS_data(b), min_len); 603 if (ret != 0) { 604 return ret; 605 } 606 if (a_len == b_len) { 607 return 0; 608 } 609 // If one is a prefix of the other, the shorter one sorts first. (This is not 610 // actually reachable. No DER encoding is a prefix of another DER encoding.) 611 return a_len < b_len ? -1 : 1; 612 } 613 614 int CBB_flush_asn1_set_of(CBB *cbb) { 615 if (!CBB_flush(cbb)) { 616 return 0; 617 } 618 619 CBS cbs; 620 size_t num_children = 0; 621 CBS_init(&cbs, CBB_data(cbb), CBB_len(cbb)); 622 while (CBS_len(&cbs) != 0) { 623 if (!CBS_get_any_asn1_element(&cbs, NULL, NULL, NULL)) { 624 return 0; 625 } 626 num_children++; 627 } 628 629 if (num_children < 2) { 630 return 1; // Nothing to do. This is the common case for X.509. 631 } 632 if (num_children > ((size_t)-1) / sizeof(CBS)) { 633 return 0; // Overflow. 634 } 635 636 // Parse out the children and sort. We alias them into a copy of so they 637 // remain valid as we rewrite |cbb|. 638 int ret = 0; 639 size_t buf_len = CBB_len(cbb); 640 uint8_t *buf = BUF_memdup(CBB_data(cbb), buf_len); 641 CBS *children = OPENSSL_malloc(num_children * sizeof(CBS)); 642 if (buf == NULL || children == NULL) { 643 goto err; 644 } 645 CBS_init(&cbs, buf, buf_len); 646 for (size_t i = 0; i < num_children; i++) { 647 if (!CBS_get_any_asn1_element(&cbs, &children[i], NULL, NULL)) { 648 goto err; 649 } 650 } 651 qsort(children, num_children, sizeof(CBS), compare_set_of_element); 652 653 // Rewind |cbb| and write the contents back in the new order. 654 cbb->base->len = cbb->offset + cbb->pending_len_len; 655 for (size_t i = 0; i < num_children; i++) { 656 if (!CBB_add_bytes(cbb, CBS_data(&children[i]), CBS_len(&children[i]))) { 657 goto err; 658 } 659 } 660 assert(CBB_len(cbb) == buf_len); 661 662 ret = 1; 663 664 err: 665 OPENSSL_free(buf); 666 OPENSSL_free(children); 667 return ret; 668 } 669