xref: /openbsd-src/lib/libcrypto/x509/x509_asid.c (revision 5a38ef86d0b61900239c7913d24a05e7b88a58f0) 
1 /*	$OpenBSD: x509_asid.c,v 1.19 2021/11/01 20:53:08 tb Exp $ */
2 /*
3  * Copyright 2006-2018 The OpenSSL Project Authors. All Rights Reserved.
4  *
5  * Licensed under the OpenSSL license (the "License").  You may not use
6  * this file except in compliance with the License.  You can obtain a copy
7  * in the file LICENSE in the source distribution or at
8  * https://www.openssl.org/source/license.html
9  */
10 
11 /*
12  * Implementation of RFC 3779 section 3.2.
13  */
14 
15 #include <assert.h>
16 #include <stdio.h>
17 #include <stdlib.h>
18 #include <string.h>
19 
20 #include <openssl/asn1.h>
21 #include <openssl/asn1t.h>
22 #include <openssl/bn.h>
23 #include <openssl/conf.h>
24 #include <openssl/err.h>
25 #include <openssl/x509.h>
26 #include <openssl/x509.h>
27 #include <openssl/x509v3.h>
28 
29 #include "x509_lcl.h"
30 
31 #ifndef OPENSSL_NO_RFC3779
32 
33 static const ASN1_TEMPLATE ASRange_seq_tt[] = {
34 	{
35 		.flags = 0,
36 		.tag = 0,
37 		.offset = offsetof(ASRange, min),
38 		.field_name = "min",
39 		.item = &ASN1_INTEGER_it,
40 	},
41 	{
42 		.flags = 0,
43 		.tag = 0,
44 		.offset = offsetof(ASRange, max),
45 		.field_name = "max",
46 		.item = &ASN1_INTEGER_it,
47 	},
48 };
49 
50 const ASN1_ITEM ASRange_it = {
51 	.itype = ASN1_ITYPE_SEQUENCE,
52 	.utype = V_ASN1_SEQUENCE,
53 	.templates = ASRange_seq_tt,
54 	.tcount = sizeof(ASRange_seq_tt) / sizeof(ASN1_TEMPLATE),
55 	.funcs = NULL,
56 	.size = sizeof(ASRange),
57 	.sname = "ASRange",
58 };
59 
60 static const ASN1_TEMPLATE ASIdOrRange_ch_tt[] = {
61 	{
62 		.flags = 0,
63 		.tag = 0,
64 		.offset = offsetof(ASIdOrRange, u.id),
65 		.field_name = "u.id",
66 		.item = &ASN1_INTEGER_it,
67 	},
68 	{
69 		.flags = 0,
70 		.tag = 0,
71 		.offset = offsetof(ASIdOrRange, u.range),
72 		.field_name = "u.range",
73 		.item = &ASRange_it,
74 	},
75 };
76 
77 const ASN1_ITEM ASIdOrRange_it = {
78 	.itype = ASN1_ITYPE_CHOICE,
79 	.utype = offsetof(ASIdOrRange, type),
80 	.templates = ASIdOrRange_ch_tt,
81 	.tcount = sizeof(ASIdOrRange_ch_tt) / sizeof(ASN1_TEMPLATE),
82 	.funcs = NULL,
83 	.size = sizeof(ASIdOrRange),
84 	.sname = "ASIdOrRange",
85 };
86 
87 static const ASN1_TEMPLATE ASIdentifierChoice_ch_tt[] = {
88 	{
89 		.flags = 0,
90 		.tag = 0,
91 		.offset = offsetof(ASIdentifierChoice, u.inherit),
92 		.field_name = "u.inherit",
93 		.item = &ASN1_NULL_it,
94 	},
95 	{
96 		.flags = ASN1_TFLG_SEQUENCE_OF,
97 		.tag = 0,
98 		.offset = offsetof(ASIdentifierChoice, u.asIdsOrRanges),
99 		.field_name = "u.asIdsOrRanges",
100 		.item = &ASIdOrRange_it,
101 	},
102 };
103 
104 const ASN1_ITEM ASIdentifierChoice_it = {
105 	.itype = ASN1_ITYPE_CHOICE,
106 	.utype = offsetof(ASIdentifierChoice, type),
107 	.templates = ASIdentifierChoice_ch_tt,
108 	.tcount = sizeof(ASIdentifierChoice_ch_tt) / sizeof(ASN1_TEMPLATE),
109 	.funcs = NULL,
110 	.size = sizeof(ASIdentifierChoice),
111 	.sname = "ASIdentifierChoice",
112 };
113 
114 static const ASN1_TEMPLATE ASIdentifiers_seq_tt[] = {
115 	{
116 		.flags = ASN1_TFLG_EXPLICIT | ASN1_TFLG_OPTIONAL,
117 		.tag = 0,
118 		.offset = offsetof(ASIdentifiers, asnum),
119 		.field_name = "asnum",
120 		.item = &ASIdentifierChoice_it,
121 	},
122 	{
123 		.flags = ASN1_TFLG_EXPLICIT | ASN1_TFLG_OPTIONAL,
124 		.tag = 1,
125 		.offset = offsetof(ASIdentifiers, rdi),
126 		.field_name = "rdi",
127 		.item = &ASIdentifierChoice_it,
128 	},
129 };
130 
131 const ASN1_ITEM ASIdentifiers_it = {
132 	.itype = ASN1_ITYPE_SEQUENCE,
133 	.utype = V_ASN1_SEQUENCE,
134 	.templates = ASIdentifiers_seq_tt,
135 	.tcount = sizeof(ASIdentifiers_seq_tt) / sizeof(ASN1_TEMPLATE),
136 	.funcs = NULL,
137 	.size = sizeof(ASIdentifiers),
138 	.sname = "ASIdentifiers",
139 };
140 
141 ASRange *
142 d2i_ASRange(ASRange **a, const unsigned char **in, long len)
143 {
144 	return (ASRange *)ASN1_item_d2i((ASN1_VALUE **)a, in, len,
145 	    &ASRange_it);
146 }
147 
148 int
149 i2d_ASRange(ASRange *a, unsigned char **out)
150 {
151 	return ASN1_item_i2d((ASN1_VALUE *)a, out, &ASRange_it);
152 }
153 
154 ASRange *
155 ASRange_new(void)
156 {
157 	return (ASRange *)ASN1_item_new(&ASRange_it);
158 }
159 
160 void
161 ASRange_free(ASRange *a)
162 {
163 	ASN1_item_free((ASN1_VALUE *)a, &ASRange_it);
164 }
165 
166 ASIdOrRange *
167 d2i_ASIdOrRange(ASIdOrRange **a, const unsigned char **in, long len)
168 {
169 	return (ASIdOrRange *)ASN1_item_d2i((ASN1_VALUE **)a, in, len,
170 	    &ASIdOrRange_it);
171 }
172 
173 int
174 i2d_ASIdOrRange(ASIdOrRange *a, unsigned char **out)
175 {
176 	return ASN1_item_i2d((ASN1_VALUE *)a, out, &ASIdOrRange_it);
177 }
178 
179 ASIdOrRange *
180 ASIdOrRange_new(void)
181 {
182 	return (ASIdOrRange *)ASN1_item_new(&ASIdOrRange_it);
183 }
184 
185 void
186 ASIdOrRange_free(ASIdOrRange *a)
187 {
188 	ASN1_item_free((ASN1_VALUE *)a, &ASIdOrRange_it);
189 }
190 
191 ASIdentifierChoice *
192 d2i_ASIdentifierChoice(ASIdentifierChoice **a, const unsigned char **in,
193     long len)
194 {
195 	return (ASIdentifierChoice *)ASN1_item_d2i((ASN1_VALUE **)a, in, len,
196 	    &ASIdentifierChoice_it);
197 }
198 
199 int
200 i2d_ASIdentifierChoice(ASIdentifierChoice *a, unsigned char **out)
201 {
202 	return ASN1_item_i2d((ASN1_VALUE *)a, out, &ASIdentifierChoice_it);
203 }
204 
205 ASIdentifierChoice *
206 ASIdentifierChoice_new(void)
207 {
208 	return (ASIdentifierChoice *)ASN1_item_new(&ASIdentifierChoice_it);
209 }
210 
211 void
212 ASIdentifierChoice_free(ASIdentifierChoice *a)
213 {
214 	ASN1_item_free((ASN1_VALUE *)a, &ASIdentifierChoice_it);
215 }
216 
217 ASIdentifiers *
218 d2i_ASIdentifiers(ASIdentifiers **a, const unsigned char **in, long len)
219 {
220 	return (ASIdentifiers *)ASN1_item_d2i((ASN1_VALUE **)a, in, len,
221 	    &ASIdentifiers_it);
222 }
223 
224 int
225 i2d_ASIdentifiers(ASIdentifiers *a, unsigned char **out)
226 {
227 	return ASN1_item_i2d((ASN1_VALUE *)a, out, &ASIdentifiers_it);
228 }
229 
230 ASIdentifiers *
231 ASIdentifiers_new(void)
232 {
233 	return (ASIdentifiers *)ASN1_item_new(&ASIdentifiers_it);
234 }
235 
236 void
237 ASIdentifiers_free(ASIdentifiers *a)
238 {
239 	ASN1_item_free((ASN1_VALUE *)a, &ASIdentifiers_it);
240 }
241 
242 /*
243  * i2r method for an ASIdentifierChoice.
244  */
245 static int
246 i2r_ASIdentifierChoice(BIO *out, ASIdentifierChoice *choice, int indent,
247     const char *msg)
248 {
249 	int i;
250 	char *s;
251 	if (choice == NULL)
252 		return 1;
253 	BIO_printf(out, "%*s%s:\n", indent, "", msg);
254 	switch (choice->type) {
255 	case ASIdentifierChoice_inherit:
256 		BIO_printf(out, "%*sinherit\n", indent + 2, "");
257 		break;
258 	case ASIdentifierChoice_asIdsOrRanges:
259 		for (i = 0; i < sk_ASIdOrRange_num(choice->u.asIdsOrRanges);
260 		    i++) {
261 			ASIdOrRange *aor =
262 			    sk_ASIdOrRange_value(choice->u.asIdsOrRanges, i);
263 			switch (aor->type) {
264 			case ASIdOrRange_id:
265 				if ((s = i2s_ASN1_INTEGER(NULL, aor->u.id)) ==
266 				    NULL)
267 					return 0;
268 				BIO_printf(out, "%*s%s\n", indent + 2, "", s);
269 				free(s);
270 				break;
271 			case ASIdOrRange_range:
272 				if ((s = i2s_ASN1_INTEGER(NULL,
273 				    aor->u.range->min)) == NULL)
274 					return 0;
275 				BIO_printf(out, "%*s%s-", indent + 2, "", s);
276 				free(s);
277 				if ((s = i2s_ASN1_INTEGER(NULL,
278 				    aor->u.range->max)) == NULL)
279 					return 0;
280 				BIO_printf(out, "%s\n", s);
281 				free(s);
282 				break;
283 			default:
284 				return 0;
285 			}
286 		}
287 		break;
288 	default:
289 		return 0;
290 	}
291 	return 1;
292 }
293 
294 /*
295  * i2r method for an ASIdentifier extension.
296  */
297 static int
298 i2r_ASIdentifiers(const X509V3_EXT_METHOD *method, void *ext, BIO *out,
299     int indent)
300 {
301 	ASIdentifiers *asid = ext;
302 	return (i2r_ASIdentifierChoice(out, asid->asnum, indent,
303 	    "Autonomous System Numbers") &&
304 	    i2r_ASIdentifierChoice(out, asid->rdi, indent,
305 	    "Routing Domain Identifiers"));
306 }
307 
308 /*
309  * Sort comparison function for a sequence of ASIdOrRange elements.
310  */
311 static int
312 ASIdOrRange_cmp(const ASIdOrRange *const *a_, const ASIdOrRange *const *b_)
313 {
314 	const ASIdOrRange *a = *a_, *b = *b_;
315 
316     /* XXX: these asserts need to be replaced */
317 	OPENSSL_assert((a->type == ASIdOrRange_id && a->u.id != NULL) ||
318 	    (a->type == ASIdOrRange_range && a->u.range != NULL &&
319 	     a->u.range->min != NULL && a->u.range->max != NULL));
320 
321 	OPENSSL_assert((b->type == ASIdOrRange_id && b->u.id != NULL) ||
322 	    (b->type == ASIdOrRange_range && b->u.range != NULL &&
323 	     b->u.range->min != NULL && b->u.range->max != NULL));
324 
325 	if (a->type == ASIdOrRange_id && b->type == ASIdOrRange_id)
326 		return ASN1_INTEGER_cmp(a->u.id, b->u.id);
327 
328 	if (a->type == ASIdOrRange_range && b->type == ASIdOrRange_range) {
329 		int r = ASN1_INTEGER_cmp(a->u.range->min, b->u.range->min);
330 		return r != 0 ? r : ASN1_INTEGER_cmp(a->u.range->max,
331 		    b->u.range->max);
332 	}
333 
334 	if (a->type == ASIdOrRange_id)
335 		return ASN1_INTEGER_cmp(a->u.id, b->u.range->min);
336 	else
337 		return ASN1_INTEGER_cmp(a->u.range->min, b->u.id);
338 }
339 
340 /*
341  * Add an inherit element.
342  */
343 int
344 X509v3_asid_add_inherit(ASIdentifiers *asid, int which)
345 {
346 	ASIdentifierChoice **choice;
347 	if (asid == NULL)
348 		return 0;
349 	switch (which) {
350 	case V3_ASID_ASNUM:
351 		choice = &asid->asnum;
352 		break;
353 	case V3_ASID_RDI:
354 		choice = &asid->rdi;
355 		break;
356 	default:
357 		return 0;
358 	}
359 	if (*choice == NULL) {
360 		if ((*choice = ASIdentifierChoice_new()) == NULL)
361 			return 0;
362 		if (((*choice)->u.inherit = ASN1_NULL_new()) == NULL)
363 			return 0;
364 		(*choice)->type = ASIdentifierChoice_inherit;
365 	}
366 	return (*choice)->type == ASIdentifierChoice_inherit;
367 }
368 
369 /*
370  * Add an ID or range to an ASIdentifierChoice.
371  */
372 int
373 X509v3_asid_add_id_or_range(ASIdentifiers *asid, int which, ASN1_INTEGER *min,
374     ASN1_INTEGER *max)
375 {
376 	ASIdentifierChoice **choice;
377 	ASIdOrRange *aor;
378 	if (asid == NULL)
379 		return 0;
380 	switch (which) {
381 	case V3_ASID_ASNUM:
382 		choice = &asid->asnum;
383 		break;
384 	case V3_ASID_RDI:
385 		choice = &asid->rdi;
386 		break;
387 	default:
388 		return 0;
389 	}
390 	if (*choice != NULL && (*choice)->type == ASIdentifierChoice_inherit)
391 		return 0;
392 	if (*choice == NULL) {
393 		if ((*choice = ASIdentifierChoice_new()) == NULL)
394 			return 0;
395 		(*choice)->u.asIdsOrRanges = sk_ASIdOrRange_new(ASIdOrRange_cmp);
396 		if ((*choice)->u.asIdsOrRanges == NULL)
397 			return 0;
398 		(*choice)->type = ASIdentifierChoice_asIdsOrRanges;
399 	}
400 	if ((aor = ASIdOrRange_new()) == NULL)
401 		return 0;
402 	if (max == NULL) {
403 		aor->type = ASIdOrRange_id;
404 		aor->u.id = min;
405 	} else {
406 		aor->type = ASIdOrRange_range;
407 		if ((aor->u.range = ASRange_new()) == NULL)
408 			goto err;
409 		ASN1_INTEGER_free(aor->u.range->min);
410 		aor->u.range->min = min;
411 		ASN1_INTEGER_free(aor->u.range->max);
412 		aor->u.range->max = max;
413 	}
414 	if (!(sk_ASIdOrRange_push((*choice)->u.asIdsOrRanges, aor)))
415 		goto err;
416 	return 1;
417 
418  err:
419 	ASIdOrRange_free(aor);
420 	return 0;
421 }
422 
423 /*
424  * Extract min and max values from an ASIdOrRange.
425  */
426 static int
427 extract_min_max(ASIdOrRange *aor, ASN1_INTEGER **min, ASN1_INTEGER **max)
428 {
429 	OPENSSL_assert(aor != NULL);
430 
431 	switch (aor->type) {
432 	case ASIdOrRange_id:
433 		*min = aor->u.id;
434 		*max = aor->u.id;
435 		return 1;
436 	case ASIdOrRange_range:
437 		*min = aor->u.range->min;
438 		*max = aor->u.range->max;
439 		return 1;
440 	}
441 
442 	return 0;
443 }
444 
445 /*
446  * Check whether an ASIdentifierChoice is in canonical form.
447  */
448 static int
449 ASIdentifierChoice_is_canonical(ASIdentifierChoice *choice)
450 {
451 	ASN1_INTEGER *a_max_plus_one = NULL;
452 	ASN1_INTEGER *orig;
453 	BIGNUM *bn = NULL;
454 	int i, ret = 0;
455 
456 	/*
457 	 * Empty element or inheritance is canonical.
458 	 */
459 	if (choice == NULL || choice->type == ASIdentifierChoice_inherit)
460 		return 1;
461 
462 	/*
463 	 * If not a list, or if empty list, it's broken.
464 	 */
465 	if (choice->type != ASIdentifierChoice_asIdsOrRanges ||
466 	    sk_ASIdOrRange_num(choice->u.asIdsOrRanges) == 0)
467 		return 0;
468 
469 	/*
470 	 * It's a list, check it.
471 	 */
472 	for (i = 0; i < sk_ASIdOrRange_num(choice->u.asIdsOrRanges) - 1; i++) {
473 		ASIdOrRange *a = sk_ASIdOrRange_value(choice->u.asIdsOrRanges,
474 		    i);
475 		ASIdOrRange *b = sk_ASIdOrRange_value(choice->u.asIdsOrRanges,
476 		    i + 1);
477 		ASN1_INTEGER *a_min = NULL,
478 		*a_max = NULL,
479 		*b_min = NULL,
480 		*b_max =
481 		    NULL;
482 
483 		if (!extract_min_max(a, &a_min, &a_max) ||
484 		    !extract_min_max(b, &b_min, &b_max))
485 			goto done;
486 
487 		/*
488 		 * Punt misordered list, overlapping start, or inverted range.
489 		 */
490 		if (ASN1_INTEGER_cmp(a_min, b_min) >= 0 ||
491 		    ASN1_INTEGER_cmp(a_min, a_max) > 0 ||
492 		    ASN1_INTEGER_cmp(b_min, b_max) > 0)
493 			goto done;
494 
495 		/*
496 		 * Calculate a_max + 1 to check for adjacency.
497 		 */
498 		if ((bn == NULL && (bn = BN_new()) == NULL) ||
499 		    ASN1_INTEGER_to_BN(a_max, bn) == NULL ||
500 		    !BN_add_word(bn, 1)) {
501 			X509V3error(ERR_R_MALLOC_FAILURE);
502 			goto done;
503 		}
504 
505 		if ((a_max_plus_one =
506 		    BN_to_ASN1_INTEGER(bn, orig = a_max_plus_one)) == NULL) {
507 			a_max_plus_one = orig;
508 			X509V3error(ERR_R_MALLOC_FAILURE);
509 			goto done;
510 		}
511 
512 		/*
513 		 * Punt if adjacent or overlapping.
514 		 */
515 		if (ASN1_INTEGER_cmp(a_max_plus_one, b_min) >= 0)
516 			goto done;
517 	}
518 
519 	/*
520 	* Check for inverted range.
521 	*/
522 	i = sk_ASIdOrRange_num(choice->u.asIdsOrRanges) - 1;
523 	{
524 		ASIdOrRange *a = sk_ASIdOrRange_value(choice->u.asIdsOrRanges,
525 		    i);
526 		ASN1_INTEGER *a_min, *a_max;
527 		if (a != NULL && a->type == ASIdOrRange_range) {
528 			if (!extract_min_max(a, &a_min, &a_max) ||
529 			    ASN1_INTEGER_cmp(a_min, a_max) > 0)
530 				goto done;
531 		}
532 	}
533 
534 	ret = 1;
535 
536  done:
537 	ASN1_INTEGER_free(a_max_plus_one);
538 	BN_free(bn);
539 	return ret;
540 }
541 
542 /*
543  * Check whether an ASIdentifier extension is in canonical form.
544  */
545 int
546 X509v3_asid_is_canonical(ASIdentifiers *asid)
547 {
548 	return (asid == NULL ||
549 	    (ASIdentifierChoice_is_canonical(asid->asnum) &&
550 	     ASIdentifierChoice_is_canonical(asid->rdi)));
551 }
552 
553 /*
554  * Whack an ASIdentifierChoice into canonical form.
555  */
556 static int
557 ASIdentifierChoice_canonize(ASIdentifierChoice *choice)
558 {
559 	ASN1_INTEGER *a_max_plus_one = NULL;
560 	ASN1_INTEGER *orig;
561 	BIGNUM *bn = NULL;
562 	int i, ret = 0;
563 
564 	/*
565 	 * Nothing to do for empty element or inheritance.
566 	 */
567 	if (choice == NULL || choice->type == ASIdentifierChoice_inherit)
568 		return 1;
569 
570 	/*
571 	 * If not a list, or if empty list, it's broken.
572 	 */
573 	if (choice->type != ASIdentifierChoice_asIdsOrRanges ||
574 	    sk_ASIdOrRange_num(choice->u.asIdsOrRanges) == 0) {
575 		X509V3error(X509V3_R_EXTENSION_VALUE_ERROR);
576 		return 0;
577 	}
578 
579 	/*
580 	 * We have a non-empty list.  Sort it.
581 	 */
582 	sk_ASIdOrRange_sort(choice->u.asIdsOrRanges);
583 
584 	/*
585 	 * Now check for errors and suboptimal encoding, rejecting the
586 	 * former and fixing the latter.
587 	 */
588 	for (i = 0; i < sk_ASIdOrRange_num(choice->u.asIdsOrRanges) - 1; i++) {
589 		ASIdOrRange *a = sk_ASIdOrRange_value(choice->u.asIdsOrRanges,
590 		    i);
591 		ASIdOrRange *b = sk_ASIdOrRange_value(choice->u.asIdsOrRanges,
592 		    i + 1);
593 		ASN1_INTEGER *a_min = NULL,
594 		*a_max = NULL,
595 		*b_min = NULL,
596 		*b_max =
597 		    NULL;
598 
599 		if (!extract_min_max(a, &a_min, &a_max) ||
600 		    !extract_min_max(b, &b_min, &b_max))
601 			goto done;
602 
603 		/*
604 		 * Make sure we're properly sorted (paranoia).
605 		 */
606 		OPENSSL_assert(ASN1_INTEGER_cmp(a_min, b_min) <= 0);
607 
608 		/*
609 		 * Punt inverted ranges.
610 		 */
611 		if (ASN1_INTEGER_cmp(a_min, a_max) > 0 ||
612 		    ASN1_INTEGER_cmp(b_min, b_max) > 0)
613 			goto done;
614 
615 		/*
616 		 * Check for overlaps.
617 		 */
618 		if (ASN1_INTEGER_cmp(a_max, b_min) >= 0) {
619 			X509V3error(X509V3_R_EXTENSION_VALUE_ERROR);
620 			goto done;
621 		}
622 
623 		/*
624 		 * Calculate a_max + 1 to check for adjacency.
625 		 */
626 		if ((bn == NULL && (bn = BN_new()) == NULL) ||
627 		    ASN1_INTEGER_to_BN(a_max, bn) == NULL ||
628 		    !BN_add_word(bn, 1)) {
629 			X509V3error(ERR_R_MALLOC_FAILURE);
630 			goto done;
631 		}
632 
633 		if ((a_max_plus_one =
634 		    BN_to_ASN1_INTEGER(bn, orig = a_max_plus_one)) == NULL) {
635 			a_max_plus_one = orig;
636 			X509V3error(ERR_R_MALLOC_FAILURE);
637 			goto done;
638 		}
639 
640 		/*
641 		 * If a and b are adjacent, merge them.
642 		 */
643 		if (ASN1_INTEGER_cmp(a_max_plus_one, b_min) == 0) {
644 			ASRange *r;
645 			switch (a->type) {
646 			case ASIdOrRange_id:
647 				if ((r = calloc(1, sizeof(*r))) == NULL) {
648 					X509V3error(ERR_R_MALLOC_FAILURE);
649 					goto done;
650 				}
651 				r->min = a_min;
652 				r->max = b_max;
653 				a->type = ASIdOrRange_range;
654 				a->u.range = r;
655 				break;
656 			case ASIdOrRange_range:
657 				ASN1_INTEGER_free(a->u.range->max);
658 				a->u.range->max = b_max;
659 				break;
660 			}
661 			switch (b->type) {
662 			case ASIdOrRange_id:
663 				b->u.id = NULL;
664 				break;
665 			case ASIdOrRange_range:
666 				b->u.range->max = NULL;
667 				break;
668 			}
669 			ASIdOrRange_free(b);
670 			(void)sk_ASIdOrRange_delete(choice->u.asIdsOrRanges,
671 			    i + 1);
672 			i--;
673 			continue;
674 		}
675 	}
676 
677 	/*
678 	 * Check for final inverted range.
679 	 */
680 	i = sk_ASIdOrRange_num(choice->u.asIdsOrRanges) - 1;
681 	{
682 		ASIdOrRange *a = sk_ASIdOrRange_value(choice->u.asIdsOrRanges,
683 		    i);
684 		ASN1_INTEGER *a_min, *a_max;
685 		if (a != NULL && a->type == ASIdOrRange_range) {
686 			if (!extract_min_max(a, &a_min, &a_max) ||
687 			    ASN1_INTEGER_cmp(a_min, a_max) > 0)
688 				goto done;
689 		}
690 	}
691 
692 	/* Paranoia */
693 	OPENSSL_assert(ASIdentifierChoice_is_canonical(choice));
694 
695 	ret = 1;
696 
697  done:
698 	ASN1_INTEGER_free(a_max_plus_one);
699 	BN_free(bn);
700 	return ret;
701 }
702 
703 /*
704  * Whack an ASIdentifier extension into canonical form.
705  */
706 int
707 X509v3_asid_canonize(ASIdentifiers *asid)
708 {
709 	return (asid == NULL ||
710 	    (ASIdentifierChoice_canonize(asid->asnum) &&
711 	     ASIdentifierChoice_canonize(asid->rdi)));
712 }
713 
714 /*
715  * v2i method for an ASIdentifier extension.
716  */
717 static void *
718 v2i_ASIdentifiers(const struct v3_ext_method *method, struct v3_ext_ctx *ctx,
719     STACK_OF(CONF_VALUE)*values)
720 {
721 	ASN1_INTEGER *min = NULL, *max = NULL;
722 	ASIdentifiers *asid = NULL;
723 	int i;
724 
725 	if ((asid = ASIdentifiers_new()) == NULL) {
726 		X509V3error(ERR_R_MALLOC_FAILURE);
727 		return NULL;
728 	}
729 
730 	for (i = 0; i < sk_CONF_VALUE_num(values); i++) {
731 		CONF_VALUE *val = sk_CONF_VALUE_value(values, i);
732 		int i1 = 0, i2 = 0, i3 = 0, is_range = 0, which = 0;
733 
734 		/*
735 		 * Figure out whether this is an AS or an RDI.
736 		 */
737 		if (!name_cmp(val->name, "AS")) {
738 			which = V3_ASID_ASNUM;
739 		} else if (!name_cmp(val->name, "RDI")) {
740 			which = V3_ASID_RDI;
741 		} else {
742 			X509V3error(X509V3_R_EXTENSION_NAME_ERROR);
743 			X509V3_conf_err(val);
744 			goto err;
745 		}
746 
747 		/*
748 		 * Handle inheritance.
749 		 */
750 		if (strcmp(val->value, "inherit") == 0) {
751 			if (X509v3_asid_add_inherit(asid, which))
752 				continue;
753 			X509V3error(X509V3_R_INVALID_INHERITANCE);
754 			X509V3_conf_err(val);
755 			goto err;
756 		}
757 
758 		/*
759 		 * Number, range, or mistake, pick it apart and figure out which
760 		 */
761 		i1 = strspn(val->value, "0123456789");
762 		if (val->value[i1] == '\0') {
763 			is_range = 0;
764 		} else {
765 			is_range = 1;
766 			i2 = i1 + strspn(val->value + i1, " \t");
767 			if (val->value[i2] != '-') {
768 				X509V3error(X509V3_R_INVALID_ASNUMBER);
769 				X509V3_conf_err(val);
770 				goto err;
771 			}
772 			i2++;
773 			i2 = i2 + strspn(val->value + i2, " \t");
774 			i3 = i2 + strspn(val->value + i2, "0123456789");
775 			if (val->value[i3] != '\0') {
776 				X509V3error(X509V3_R_INVALID_ASRANGE);
777 				X509V3_conf_err(val);
778 				goto err;
779 			}
780 		}
781 
782 		/*
783 		 * Syntax is ok, read and add it.
784 		 */
785 		if (!is_range) {
786 			if (!X509V3_get_value_int(val, &min)) {
787 				X509V3error(ERR_R_MALLOC_FAILURE);
788 				goto err;
789 			}
790 		} else {
791 			char *s = strdup(val->value);
792 			if (s == NULL) {
793 				X509V3error(ERR_R_MALLOC_FAILURE);
794 				goto err;
795 			}
796 			s[i1] = '\0';
797 			min = s2i_ASN1_INTEGER(NULL, s);
798 			max = s2i_ASN1_INTEGER(NULL, s + i2);
799 			free(s);
800 			if (min == NULL || max == NULL) {
801 				X509V3error(ERR_R_MALLOC_FAILURE);
802 				goto err;
803 			}
804 			if (ASN1_INTEGER_cmp(min, max) > 0) {
805 				X509V3error(X509V3_R_EXTENSION_VALUE_ERROR);
806 				goto err;
807 			}
808 		}
809 		if (!X509v3_asid_add_id_or_range(asid, which, min, max)) {
810 			X509V3error(ERR_R_MALLOC_FAILURE);
811 			goto err;
812 		}
813 		min = max = NULL;
814 	}
815 
816 	/*
817 	 * Canonize the result, then we're done.
818 	 */
819 	if (!X509v3_asid_canonize(asid))
820 		goto err;
821 	return asid;
822 
823  err:
824 	ASIdentifiers_free(asid);
825 	ASN1_INTEGER_free(min);
826 	ASN1_INTEGER_free(max);
827 	return NULL;
828 }
829 
830 /*
831  * OpenSSL dispatch.
832  */
833 const X509V3_EXT_METHOD v3_asid = {
834 	NID_sbgp_autonomousSysNum,  /* nid */
835 	0,                          /* flags */
836 	&ASIdentifiers_it,          /* template */
837 	0, 0, 0, 0,                 /* old functions, ignored */
838 	0,                          /* i2s */
839 	0,                          /* s2i */
840 	0,                          /* i2v */
841 	v2i_ASIdentifiers,          /* v2i */
842 	i2r_ASIdentifiers,          /* i2r */
843 	0,                          /* r2i */
844 	NULL                        /* extension-specific data */
845 };
846 
847 /*
848  * Figure out whether extension uses inheritance.
849  */
850 int
851 X509v3_asid_inherits(ASIdentifiers *asid)
852 {
853 	return (asid != NULL &&
854 	    ((asid->asnum != NULL &&
855 	      asid->asnum->type == ASIdentifierChoice_inherit) ||
856 	     (asid->rdi != NULL &&
857 	      asid->rdi->type == ASIdentifierChoice_inherit)));
858 }
859 
860 /*
861  * Figure out whether parent contains child.
862  */
863 static int
864 asid_contains(ASIdOrRanges *parent, ASIdOrRanges *child)
865 {
866 	ASN1_INTEGER *p_min = NULL, *p_max = NULL, *c_min = NULL, *c_max = NULL;
867 	int p, c;
868 
869 	if (child == NULL || parent == child)
870 		return 1;
871 	if (parent == NULL)
872 		return 0;
873 
874 	p = 0;
875 	for (c = 0; c < sk_ASIdOrRange_num(child); c++) {
876 		if (!extract_min_max(sk_ASIdOrRange_value(child, c), &c_min,
877 		    &c_max))
878 			return 0;
879 		for (;; p++) {
880 			if (p >= sk_ASIdOrRange_num(parent))
881 				return 0;
882 			if (!extract_min_max(sk_ASIdOrRange_value(parent, p),
883 			    &p_min, &p_max))
884 				return 0;
885 			if (ASN1_INTEGER_cmp(p_max, c_max) < 0)
886 				continue;
887 			if (ASN1_INTEGER_cmp(p_min, c_min) > 0)
888 				return 0;
889 			break;
890 		}
891 	}
892 
893 	return 1;
894 }
895 
896 /*
897  * Test whether a is a subset of b.
898  */
899 int
900 X509v3_asid_subset(ASIdentifiers *a, ASIdentifiers *b)
901 {
902 	return (a == NULL ||
903 	    a == b ||
904 	    (b != NULL &&
905 	     !X509v3_asid_inherits(a) &&
906 	     !X509v3_asid_inherits(b) &&
907 	     asid_contains(b->asnum->u.asIdsOrRanges,
908 	     a->asnum->u.asIdsOrRanges) &&
909 	     asid_contains(b->rdi->u.asIdsOrRanges,
910 	     a->rdi->u.asIdsOrRanges)));
911 }
912 
913 /*
914  * Validation error handling via callback.
915  */
916 #define validation_err(_err_)           \
917   do {                                  \
918     if (ctx != NULL) {                  \
919       ctx->error = _err_;               \
920       ctx->error_depth = i;             \
921       ctx->current_cert = x;            \
922       ret = ctx->verify_cb(0, ctx);     \
923     } else {                            \
924       ret = 0;                          \
925     }                                   \
926     if (!ret)                           \
927       goto done;                        \
928   } while (0)
929 
930 /*
931  * Core code for RFC 3779 3.3 path validation.
932  */
933 static int
934 asid_validate_path_internal(X509_STORE_CTX *ctx, STACK_OF(X509)*chain,
935     ASIdentifiers *ext)
936 {
937 	ASIdOrRanges *child_as = NULL, *child_rdi = NULL;
938 	int i, ret = 1, inherit_as = 0, inherit_rdi = 0;
939 	X509 *x;
940 
941 	OPENSSL_assert(chain != NULL && sk_X509_num(chain) > 0);
942 	OPENSSL_assert(ctx != NULL || ext != NULL);
943 	OPENSSL_assert(ctx == NULL || ctx->verify_cb != NULL);
944 
945 	/*
946 	 * Figure out where to start.  If we don't have an extension to
947 	 * check, we're done.  Otherwise, check canonical form and
948 	 * set up for walking up the chain.
949 	 */
950 	if (ext != NULL) {
951 		i = -1;
952 		x = NULL;
953 	} else {
954 		i = 0;
955 		x = sk_X509_value(chain, i);
956 		if ((ext = x->rfc3779_asid) == NULL)
957 			goto done;
958 	}
959 	if (!X509v3_asid_is_canonical(ext))
960 		validation_err(X509_V_ERR_INVALID_EXTENSION);
961 	if (ext->asnum != NULL) {
962 		switch (ext->asnum->type) {
963 		case ASIdentifierChoice_inherit:
964 			inherit_as = 1;
965 			break;
966 		case ASIdentifierChoice_asIdsOrRanges:
967 			child_as = ext->asnum->u.asIdsOrRanges;
968 			break;
969 		}
970 	}
971 	if (ext->rdi != NULL) {
972 		switch (ext->rdi->type) {
973 		case ASIdentifierChoice_inherit:
974 			inherit_rdi = 1;
975 			break;
976 		case ASIdentifierChoice_asIdsOrRanges:
977 			child_rdi = ext->rdi->u.asIdsOrRanges;
978 			break;
979 		}
980 	}
981 
982 	/*
983 	 * Now walk up the chain.  Extensions must be in canonical form, no
984 	 * cert may list resources that its parent doesn't list.
985 	 */
986 	for (i++; i < sk_X509_num(chain); i++) {
987 		x = sk_X509_value(chain, i);
988 		OPENSSL_assert(x != NULL);
989 
990 		if (x->rfc3779_asid == NULL) {
991 			if (child_as != NULL || child_rdi != NULL)
992 				validation_err(X509_V_ERR_UNNESTED_RESOURCE);
993 			continue;
994 		}
995 		if (!X509v3_asid_is_canonical(x->rfc3779_asid))
996 			validation_err(X509_V_ERR_INVALID_EXTENSION);
997 		if (x->rfc3779_asid->asnum == NULL && child_as != NULL) {
998 			validation_err(X509_V_ERR_UNNESTED_RESOURCE);
999 			child_as = NULL;
1000 			inherit_as = 0;
1001 		}
1002 		if (x->rfc3779_asid->asnum != NULL &&
1003 		    x->rfc3779_asid->asnum->type ==
1004 		    ASIdentifierChoice_asIdsOrRanges) {
1005 			if (inherit_as ||
1006 			    asid_contains(x->rfc3779_asid->asnum->u.asIdsOrRanges,
1007 			    child_as)) {
1008 				child_as = x->rfc3779_asid->asnum->u.asIdsOrRanges;
1009 				inherit_as = 0;
1010 			} else {
1011 				validation_err(X509_V_ERR_UNNESTED_RESOURCE);
1012 			}
1013 		}
1014 		if (x->rfc3779_asid->rdi == NULL && child_rdi != NULL) {
1015 			validation_err(X509_V_ERR_UNNESTED_RESOURCE);
1016 			child_rdi = NULL;
1017 			inherit_rdi = 0;
1018 		}
1019 		if (x->rfc3779_asid->rdi != NULL &&
1020 		    x->rfc3779_asid->rdi->type == ASIdentifierChoice_asIdsOrRanges) {
1021 			if (inherit_rdi ||
1022 			    asid_contains(x->rfc3779_asid->rdi->u.asIdsOrRanges,
1023 			    child_rdi)) {
1024 				child_rdi = x->rfc3779_asid->rdi->u.asIdsOrRanges;
1025 				inherit_rdi = 0;
1026 			} else {
1027 				validation_err(X509_V_ERR_UNNESTED_RESOURCE);
1028 			}
1029 		}
1030 	}
1031 
1032 	/*
1033 	 * Trust anchor can't inherit.
1034 	 */
1035 	OPENSSL_assert(x != NULL);
1036 
1037 	if (x->rfc3779_asid != NULL) {
1038 		if (x->rfc3779_asid->asnum != NULL &&
1039 		    x->rfc3779_asid->asnum->type == ASIdentifierChoice_inherit)
1040 			validation_err(X509_V_ERR_UNNESTED_RESOURCE);
1041 		if (x->rfc3779_asid->rdi != NULL &&
1042 		    x->rfc3779_asid->rdi->type == ASIdentifierChoice_inherit)
1043 			validation_err(X509_V_ERR_UNNESTED_RESOURCE);
1044 	}
1045 
1046  done:
1047 	return ret;
1048 }
1049 
1050 #undef validation_err
1051 
1052 /*
1053  * RFC 3779 3.3 path validation -- called from X509_verify_cert().
1054  */
1055 int
1056 X509v3_asid_validate_path(X509_STORE_CTX *ctx)
1057 {
1058 	if (ctx->chain == NULL ||
1059 	    sk_X509_num(ctx->chain) == 0 ||
1060 	    ctx->verify_cb == NULL) {
1061 		ctx->error = X509_V_ERR_UNSPECIFIED;
1062 		return 0;
1063 	}
1064 	return asid_validate_path_internal(ctx, ctx->chain, NULL);
1065 }
1066 
1067 /*
1068  * RFC 3779 3.3 path validation of an extension.
1069  * Test whether chain covers extension.
1070  */
1071 int
1072 X509v3_asid_validate_resource_set(STACK_OF(X509)*chain, ASIdentifiers *ext,
1073     int allow_inheritance)
1074 {
1075 	if (ext == NULL)
1076 		return 1;
1077 	if (chain == NULL || sk_X509_num(chain) == 0)
1078 		return 0;
1079 	if (!allow_inheritance && X509v3_asid_inherits(ext))
1080 		return 0;
1081 	return asid_validate_path_internal(NULL, chain, ext);
1082 }
1083 
1084 #endif                          /* OPENSSL_NO_RFC3779 */
1085