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
27void CBB_zero(CBB *cbb) {
28 OPENSSL_memset(cbb, 0, sizeof(CBB));
29}
30
31static 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
51int 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
67int 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
78void 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
95static 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
135err:
136 base->error = 1;
137 return 0;
138}
139
140static 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
150static 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
174int 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.
202int 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
283err:
284 cbb->base->error = 1;
285 return 0;
286}
287
288const 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
293size_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
300static 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
325int CBB_add_u8_length_prefixed(CBB *cbb, CBB *out_contents) {
326 return cbb_add_length_prefixed(cbb, out_contents, 1);
327}
328
329int CBB_add_u16_length_prefixed(CBB *cbb, CBB *out_contents) {
330 return cbb_add_length_prefixed(cbb, out_contents, 2);
331}
332
333int 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.
340static 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
363int 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
397int 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
408int 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
416int 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
424int 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
435int 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
443int 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
451int 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
459int 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
467int 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
474void 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
485int 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
520int 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
531int 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.
546static 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
573int 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
608static 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
626int 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
676err:
677 OPENSSL_free(buf);
678 OPENSSL_free(children);
679 return ret;
680}
681