legacy-libs/grpc/deps/grpc/third_party/boringssl/crypto/bytestring/cbb.c

   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 }