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