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