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/buf.h>
16#include <openssl/mem.h>
17#include <openssl/bytestring.h>
18
19#include <assert.h>
20#include <inttypes.h>
21#include <string.h>
22
23#include "internal.h"
24#include "../internal.h"
25
26
27void CBS_init(CBS *cbs, const uint8_t *data, size_t len) {
28 cbs->data = data;
29 cbs->len = len;
30}
31
32static int cbs_get(CBS *cbs, const uint8_t **p, size_t n) {
33 if (cbs->len < n) {
34 return 0;
35 }
36
37 *p = cbs->data;
38 cbs->data += n;
39 cbs->len -= n;
40 return 1;
41}
42
43int CBS_skip(CBS *cbs, size_t len) {
44 const uint8_t *dummy;
45 return cbs_get(cbs, &dummy, len);
46}
47
48const uint8_t *CBS_data(const CBS *cbs) {
49 return cbs->data;
50}
51
52size_t CBS_len(const CBS *cbs) {
53 return cbs->len;
54}
55
56int CBS_stow(const CBS *cbs, uint8_t **out_ptr, size_t *out_len) {
57 OPENSSL_free(*out_ptr);
58 *out_ptr = NULL;
59 *out_len = 0;
60
61 if (cbs->len == 0) {
62 return 1;
63 }
64 *out_ptr = BUF_memdup(cbs->data, cbs->len);
65 if (*out_ptr == NULL) {
66 return 0;
67 }
68 *out_len = cbs->len;
69 return 1;
70}
71
72int CBS_strdup(const CBS *cbs, char **out_ptr) {
73 if (*out_ptr != NULL) {
74 OPENSSL_free(*out_ptr);
75 }
76 *out_ptr = BUF_strndup((const char*)cbs->data, cbs->len);
77 return (*out_ptr != NULL);
78}
79
80int CBS_contains_zero_byte(const CBS *cbs) {
81 return OPENSSL_memchr(cbs->data, 0, cbs->len) != NULL;
82}
83
84int CBS_mem_equal(const CBS *cbs, const uint8_t *data, size_t len) {
85 if (len != cbs->len) {
86 return 0;
87 }
88 return CRYPTO_memcmp(cbs->data, data, len) == 0;
89}
90
91static int cbs_get_u(CBS *cbs, uint64_t *out, size_t len) {
92 uint64_t result = 0;
93 const uint8_t *data;
94
95 if (!cbs_get(cbs, &data, len)) {
96 return 0;
97 }
98 for (size_t i = 0; i < len; i++) {
99 result <<= 8;
100 result |= data[i];
101 }
102 *out = result;
103 return 1;
104}
105
106int CBS_get_u8(CBS *cbs, uint8_t *out) {
107 const uint8_t *v;
108 if (!cbs_get(cbs, &v, 1)) {
109 return 0;
110 }
111 *out = *v;
112 return 1;
113}
114
115int CBS_get_u16(CBS *cbs, uint16_t *out) {
116 uint64_t v;
117 if (!cbs_get_u(cbs, &v, 2)) {
118 return 0;
119 }
120 *out = v;
121 return 1;
122}
123
124int CBS_get_u24(CBS *cbs, uint32_t *out) {
125 uint64_t v;
126 if (!cbs_get_u(cbs, &v, 3)) {
127 return 0;
128 }
129 *out = v;
130 return 1;
131}
132
133int CBS_get_u32(CBS *cbs, uint32_t *out) {
134 uint64_t v;
135 if (!cbs_get_u(cbs, &v, 4)) {
136 return 0;
137 }
138 *out = v;
139 return 1;
140}
141
142int CBS_get_u64(CBS *cbs, uint64_t *out) {
143 return cbs_get_u(cbs, out, 8);
144}
145
146int CBS_get_last_u8(CBS *cbs, uint8_t *out) {
147 if (cbs->len == 0) {
148 return 0;
149 }
150 *out = cbs->data[cbs->len - 1];
151 cbs->len--;
152 return 1;
153}
154
155int CBS_get_bytes(CBS *cbs, CBS *out, size_t len) {
156 const uint8_t *v;
157 if (!cbs_get(cbs, &v, len)) {
158 return 0;
159 }
160 CBS_init(out, v, len);
161 return 1;
162}
163
164int CBS_copy_bytes(CBS *cbs, uint8_t *out, size_t len) {
165 const uint8_t *v;
166 if (!cbs_get(cbs, &v, len)) {
167 return 0;
168 }
169 OPENSSL_memcpy(out, v, len);
170 return 1;
171}
172
173static int cbs_get_length_prefixed(CBS *cbs, CBS *out, size_t len_len) {
174 uint64_t len;
175 if (!cbs_get_u(cbs, &len, len_len)) {
176 return 0;
177 }
178 // If |len_len| <= 3 then we know that |len| will fit into a |size_t|, even on
179 // 32-bit systems.
180 assert(len_len <= 3);
181 return CBS_get_bytes(cbs, out, len);
182}
183
184int CBS_get_u8_length_prefixed(CBS *cbs, CBS *out) {
185 return cbs_get_length_prefixed(cbs, out, 1);
186}
187
188int CBS_get_u16_length_prefixed(CBS *cbs, CBS *out) {
189 return cbs_get_length_prefixed(cbs, out, 2);
190}
191
192int CBS_get_u24_length_prefixed(CBS *cbs, CBS *out) {
193 return cbs_get_length_prefixed(cbs, out, 3);
194}
195
196// parse_base128_integer reads a big-endian base-128 integer from |cbs| and sets
197// |*out| to the result. This is the encoding used in DER for both high tag
198// number form and OID components.
199static int parse_base128_integer(CBS *cbs, uint64_t *out) {
200 uint64_t v = 0;
201 uint8_t b;
202 do {
203 if (!CBS_get_u8(cbs, &b)) {
204 return 0;
205 }
206 if ((v >> (64 - 7)) != 0) {
207 // The value is too large.
208 return 0;
209 }
210 if (v == 0 && b == 0x80) {
211 // The value must be minimally encoded.
212 return 0;
213 }
214 v = (v << 7) | (b & 0x7f);
215
216 // Values end at an octet with the high bit cleared.
217 } while (b & 0x80);
218
219 *out = v;
220 return 1;
221}
222
223static int parse_asn1_tag(CBS *cbs, unsigned *out) {
224 uint8_t tag_byte;
225 if (!CBS_get_u8(cbs, &tag_byte)) {
226 return 0;
227 }
228
229 // ITU-T X.690 section 8.1.2.3 specifies the format for identifiers with a tag
230 // number no greater than 30.
231 //
232 // If the number portion is 31 (0x1f, the largest value that fits in the
233 // allotted bits), then the tag is more than one byte long and the
234 // continuation bytes contain the tag number. This parser only supports tag
235 // numbers less than 31 (and thus single-byte tags).
236 unsigned tag = ((unsigned)tag_byte & 0xe0) << CBS_ASN1_TAG_SHIFT;
237 unsigned tag_number = tag_byte & 0x1f;
238 if (tag_number == 0x1f) {
239 uint64_t v;
240 if (!parse_base128_integer(cbs, &v) ||
241 // Check the tag number is within our supported bounds.
242 v > CBS_ASN1_TAG_NUMBER_MASK ||
243 // Small tag numbers should have used low tag number form.
244 v < 0x1f) {
245 return 0;
246 }
247 tag_number = (unsigned)v;
248 }
249
250 tag |= tag_number;
251
252 *out = tag;
253 return 1;
254}
255
256static int cbs_get_any_asn1_element(CBS *cbs, CBS *out, unsigned *out_tag,
257 size_t *out_header_len, int ber_ok) {
258 CBS header = *cbs;
259 CBS throwaway;
260
261 if (out == NULL) {
262 out = &throwaway;
263 }
264
265 unsigned tag;
266 if (!parse_asn1_tag(&header, &tag)) {
267 return 0;
268 }
269 if (out_tag != NULL) {
270 *out_tag = tag;
271 }
272
273 uint8_t length_byte;
274 if (!CBS_get_u8(&header, &length_byte)) {
275 return 0;
276 }
277
278 size_t header_len = CBS_len(cbs) - CBS_len(&header);
279
280 size_t len;
281 // The format for the length encoding is specified in ITU-T X.690 section
282 // 8.1.3.
283 if ((length_byte & 0x80) == 0) {
284 // Short form length.
285 len = ((size_t) length_byte) + header_len;
286 if (out_header_len != NULL) {
287 *out_header_len = header_len;
288 }
289 } else {
290 // The high bit indicate that this is the long form, while the next 7 bits
291 // encode the number of subsequent octets used to encode the length (ITU-T
292 // X.690 clause 8.1.3.5.b).
293 const size_t num_bytes = length_byte & 0x7f;
294 uint64_t len64;
295
296 if (ber_ok && (tag & CBS_ASN1_CONSTRUCTED) != 0 && num_bytes == 0) {
297 // indefinite length
298 if (out_header_len != NULL) {
299 *out_header_len = header_len;
300 }
301 return CBS_get_bytes(cbs, out, header_len);
302 }
303
304 // ITU-T X.690 clause 8.1.3.5.c specifies that the value 0xff shall not be
305 // used as the first byte of the length. If this parser encounters that
306 // value, num_bytes will be parsed as 127, which will fail the check below.
307 if (num_bytes == 0 || num_bytes > 4) {
308 return 0;
309 }
310 if (!cbs_get_u(&header, &len64, num_bytes)) {
311 return 0;
312 }
313 // ITU-T X.690 section 10.1 (DER length forms) requires encoding the length
314 // with the minimum number of octets.
315 if (len64 < 128) {
316 // Length should have used short-form encoding.
317 return 0;
318 }
319 if ((len64 >> ((num_bytes-1)*8)) == 0) {
320 // Length should have been at least one byte shorter.
321 return 0;
322 }
323 len = len64;
324 if (len + header_len + num_bytes < len) {
325 // Overflow.
326 return 0;
327 }
328 len += header_len + num_bytes;
329 if (out_header_len != NULL) {
330 *out_header_len = header_len + num_bytes;
331 }
332 }
333
334 return CBS_get_bytes(cbs, out, len);
335}
336
337int CBS_get_any_asn1(CBS *cbs, CBS *out, unsigned *out_tag) {
338 size_t header_len;
339 if (!CBS_get_any_asn1_element(cbs, out, out_tag, &header_len)) {
340 return 0;
341 }
342
343 if (!CBS_skip(out, header_len)) {
344 assert(0);
345 return 0;
346 }
347
348 return 1;
349}
350
351int CBS_get_any_asn1_element(CBS *cbs, CBS *out, unsigned *out_tag,
352 size_t *out_header_len) {
353 return cbs_get_any_asn1_element(cbs, out, out_tag, out_header_len,
354 0 /* DER only */);
355}
356
357int CBS_get_any_ber_asn1_element(CBS *cbs, CBS *out, unsigned *out_tag,
358 size_t *out_header_len) {
359 return cbs_get_any_asn1_element(cbs, out, out_tag, out_header_len,
360 1 /* BER allowed */);
361}
362
363static int cbs_get_asn1(CBS *cbs, CBS *out, unsigned tag_value,
364 int skip_header) {
365 size_t header_len;
366 unsigned tag;
367 CBS throwaway;
368
369 if (out == NULL) {
370 out = &throwaway;
371 }
372
373 if (!CBS_get_any_asn1_element(cbs, out, &tag, &header_len) ||
374 tag != tag_value) {
375 return 0;
376 }
377
378 if (skip_header && !CBS_skip(out, header_len)) {
379 assert(0);
380 return 0;
381 }
382
383 return 1;
384}
385
386int CBS_get_asn1(CBS *cbs, CBS *out, unsigned tag_value) {
387 return cbs_get_asn1(cbs, out, tag_value, 1 /* skip header */);
388}
389
390int CBS_get_asn1_element(CBS *cbs, CBS *out, unsigned tag_value) {
391 return cbs_get_asn1(cbs, out, tag_value, 0 /* include header */);
392}
393
394int CBS_peek_asn1_tag(const CBS *cbs, unsigned tag_value) {
395 if (CBS_len(cbs) < 1) {
396 return 0;
397 }
398
399 CBS copy = *cbs;
400 unsigned actual_tag;
401 return parse_asn1_tag(&copy, &actual_tag) && tag_value == actual_tag;
402}
403
404int CBS_get_asn1_uint64(CBS *cbs, uint64_t *out) {
405 CBS bytes;
406 if (!CBS_get_asn1(cbs, &bytes, CBS_ASN1_INTEGER)) {
407 return 0;
408 }
409
410 *out = 0;
411 const uint8_t *data = CBS_data(&bytes);
412 size_t len = CBS_len(&bytes);
413
414 if (len == 0) {
415 // An INTEGER is encoded with at least one octet.
416 return 0;
417 }
418
419 if ((data[0] & 0x80) != 0) {
420 // Negative number.
421 return 0;
422 }
423
424 if (data[0] == 0 && len > 1 && (data[1] & 0x80) == 0) {
425 // Extra leading zeros.
426 return 0;
427 }
428
429 for (size_t i = 0; i < len; i++) {
430 if ((*out >> 56) != 0) {
431 // Too large to represent as a uint64_t.
432 return 0;
433 }
434 *out <<= 8;
435 *out |= data[i];
436 }
437
438 return 1;
439}
440
441int CBS_get_asn1_bool(CBS *cbs, int *out) {
442 CBS bytes;
443 if (!CBS_get_asn1(cbs, &bytes, CBS_ASN1_BOOLEAN) ||
444 CBS_len(&bytes) != 1) {
445 return 0;
446 }
447
448 const uint8_t value = *CBS_data(&bytes);
449 if (value != 0 && value != 0xff) {
450 return 0;
451 }
452
453 *out = !!value;
454 return 1;
455}
456
457int CBS_get_optional_asn1(CBS *cbs, CBS *out, int *out_present, unsigned tag) {
458 int present = 0;
459
460 if (CBS_peek_asn1_tag(cbs, tag)) {
461 if (!CBS_get_asn1(cbs, out, tag)) {
462 return 0;
463 }
464 present = 1;
465 }
466
467 if (out_present != NULL) {
468 *out_present = present;
469 }
470
471 return 1;
472}
473
474int CBS_get_optional_asn1_octet_string(CBS *cbs, CBS *out, int *out_present,
475 unsigned tag) {
476 CBS child;
477 int present;
478 if (!CBS_get_optional_asn1(cbs, &child, &present, tag)) {
479 return 0;
480 }
481 if (present) {
482 assert(out);
483 if (!CBS_get_asn1(&child, out, CBS_ASN1_OCTETSTRING) ||
484 CBS_len(&child) != 0) {
485 return 0;
486 }
487 } else {
488 CBS_init(out, NULL, 0);
489 }
490 if (out_present) {
491 *out_present = present;
492 }
493 return 1;
494}
495
496int CBS_get_optional_asn1_uint64(CBS *cbs, uint64_t *out, unsigned tag,
497 uint64_t default_value) {
498 CBS child;
499 int present;
500 if (!CBS_get_optional_asn1(cbs, &child, &present, tag)) {
501 return 0;
502 }
503 if (present) {
504 if (!CBS_get_asn1_uint64(&child, out) ||
505 CBS_len(&child) != 0) {
506 return 0;
507 }
508 } else {
509 *out = default_value;
510 }
511 return 1;
512}
513
514int CBS_get_optional_asn1_bool(CBS *cbs, int *out, unsigned tag,
515 int default_value) {
516 CBS child, child2;
517 int present;
518 if (!CBS_get_optional_asn1(cbs, &child, &present, tag)) {
519 return 0;
520 }
521 if (present) {
522 uint8_t boolean;
523
524 if (!CBS_get_asn1(&child, &child2, CBS_ASN1_BOOLEAN) ||
525 CBS_len(&child2) != 1 ||
526 CBS_len(&child) != 0) {
527 return 0;
528 }
529
530 boolean = CBS_data(&child2)[0];
531 if (boolean == 0) {
532 *out = 0;
533 } else if (boolean == 0xff) {
534 *out = 1;
535 } else {
536 return 0;
537 }
538 } else {
539 *out = default_value;
540 }
541 return 1;
542}
543
544int CBS_is_valid_asn1_bitstring(const CBS *cbs) {
545 CBS in = *cbs;
546 uint8_t num_unused_bits;
547 if (!CBS_get_u8(&in, &num_unused_bits) ||
548 num_unused_bits > 7) {
549 return 0;
550 }
551
552 if (num_unused_bits == 0) {
553 return 1;
554 }
555
556 // All num_unused_bits bits must exist and be zeros.
557 uint8_t last;
558 if (!CBS_get_last_u8(&in, &last) ||
559 (last & ((1 << num_unused_bits) - 1)) != 0) {
560 return 0;
561 }
562
563 return 1;
564}
565
566int CBS_asn1_bitstring_has_bit(const CBS *cbs, unsigned bit) {
567 if (!CBS_is_valid_asn1_bitstring(cbs)) {
568 return 0;
569 }
570
571 const unsigned byte_num = (bit >> 3) + 1;
572 const unsigned bit_num = 7 - (bit & 7);
573
574 // Unused bits are zero, and this function does not distinguish between
575 // missing and unset bits. Thus it is sufficient to do a byte-level length
576 // check.
577 return byte_num < CBS_len(cbs) &&
578 (CBS_data(cbs)[byte_num] & (1 << bit_num)) != 0;
579}
580
581static int add_decimal(CBB *out, uint64_t v) {
582 char buf[DECIMAL_SIZE(uint64_t) + 1];
583 BIO_snprintf(buf, sizeof(buf), "%" PRIu64, v);
584 return CBB_add_bytes(out, (const uint8_t *)buf, strlen(buf));
585}
586
587char *CBS_asn1_oid_to_text(const CBS *cbs) {
588 CBB cbb;
589 if (!CBB_init(&cbb, 32)) {
590 goto err;
591 }
592
593 CBS copy = *cbs;
594 // The first component is 40 * value1 + value2, where value1 is 0, 1, or 2.
595 uint64_t v;
596 if (!parse_base128_integer(&copy, &v)) {
597 goto err;
598 }
599
600 if (v >= 80) {
601 if (!CBB_add_bytes(&cbb, (const uint8_t *)"2.", 2) ||
602 !add_decimal(&cbb, v - 80)) {
603 goto err;
604 }
605 } else if (!add_decimal(&cbb, v / 40) ||
606 !CBB_add_u8(&cbb, '.') ||
607 !add_decimal(&cbb, v % 40)) {
608 goto err;
609 }
610
611 while (CBS_len(&copy) != 0) {
612 if (!parse_base128_integer(&copy, &v) ||
613 !CBB_add_u8(&cbb, '.') ||
614 !add_decimal(&cbb, v)) {
615 goto err;
616 }
617 }
618
619 uint8_t *txt;
620 size_t txt_len;
621 if (!CBB_add_u8(&cbb, '\0') ||
622 !CBB_finish(&cbb, &txt, &txt_len)) {
623 goto err;
624 }
625
626 return (char *)txt;
627
628err:
629 CBB_cleanup(&cbb);
630 return NULL;
631}
632