1 /* pcy_tree.c */ 2 /* Written by Dr Stephen N Henson (steve (at) openssl.org) for the OpenSSL 3 * project 2004. 4 */ 5 /* ==================================================================== 6 * Copyright (c) 2004 The OpenSSL Project. All rights reserved. 7 * 8 * Redistribution and use in source and binary forms, with or without 9 * modification, are permitted provided that the following conditions 10 * are met: 11 * 12 * 1. Redistributions of source code must retain the above copyright 13 * notice, this list of conditions and the following disclaimer. 14 * 15 * 2. Redistributions in binary form must reproduce the above copyright 16 * notice, this list of conditions and the following disclaimer in 17 * the documentation and/or other materials provided with the 18 * distribution. 19 * 20 * 3. All advertising materials mentioning features or use of this 21 * software must display the following acknowledgment: 22 * "This product includes software developed by the OpenSSL Project 23 * for use in the OpenSSL Toolkit. (http://www.OpenSSL.org/)" 24 * 25 * 4. The names "OpenSSL Toolkit" and "OpenSSL Project" must not be used to 26 * endorse or promote products derived from this software without 27 * prior written permission. For written permission, please contact 28 * licensing (at) OpenSSL.org. 29 * 30 * 5. Products derived from this software may not be called "OpenSSL" 31 * nor may "OpenSSL" appear in their names without prior written 32 * permission of the OpenSSL Project. 33 * 34 * 6. Redistributions of any form whatsoever must retain the following 35 * acknowledgment: 36 * "This product includes software developed by the OpenSSL Project 37 * for use in the OpenSSL Toolkit (http://www.OpenSSL.org/)" 38 * 39 * THIS SOFTWARE IS PROVIDED BY THE OpenSSL PROJECT ``AS IS'' AND ANY 40 * EXPRESSED OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE 41 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR 42 * PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE OpenSSL PROJECT OR 43 * ITS CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, 44 * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT 45 * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; 46 * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) 47 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, 48 * STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) 49 * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED 50 * OF THE POSSIBILITY OF SUCH DAMAGE. 51 * ==================================================================== 52 * 53 * This product includes cryptographic software written by Eric Young 54 * (eay (at) cryptsoft.com). This product includes software written by Tim 55 * Hudson (tjh (at) cryptsoft.com). 56 * 57 */ 58 59 #include "cryptlib.h" 60 #include <openssl/x509.h> 61 #include <openssl/x509v3.h> 62 63 #include "pcy_int.h" 64 65 /* Initialize policy tree. Return values: 66 * 0 Some internal error occured. 67 * -1 Inconsistent or invalid extensions in certificates. 68 * 1 Tree initialized OK. 69 * 2 Policy tree is empty. 70 * 5 Tree OK and requireExplicitPolicy true. 71 * 6 Tree empty and requireExplicitPolicy true. 72 */ 73 74 static int tree_init(X509_POLICY_TREE **ptree, STACK_OF(X509) *certs, 75 unsigned int flags) 76 { 77 X509_POLICY_TREE *tree; 78 X509_POLICY_LEVEL *level; 79 const X509_POLICY_CACHE *cache; 80 X509_POLICY_DATA *data = NULL; 81 X509 *x; 82 int ret = 1; 83 int i, n; 84 int explicit_policy; 85 int any_skip; 86 int map_skip; 87 *ptree = NULL; 88 n = sk_X509_num(certs); 89 90 /* Disable policy mapping for now... */ 91 flags |= X509_V_FLAG_INHIBIT_MAP; 92 93 if (flags & X509_V_FLAG_EXPLICIT_POLICY) 94 explicit_policy = 0; 95 else 96 explicit_policy = n + 1; 97 98 if (flags & X509_V_FLAG_INHIBIT_ANY) 99 any_skip = 0; 100 else 101 any_skip = n + 1; 102 103 if (flags & X509_V_FLAG_INHIBIT_MAP) 104 map_skip = 0; 105 else 106 map_skip = n + 1; 107 108 /* Can't do anything with just a trust anchor */ 109 if (n == 1) 110 return 1; 111 /* First setup policy cache in all certificates apart from the 112 * trust anchor. Note any bad cache results on the way. Also can 113 * calculate explicit_policy value at this point. 114 */ 115 for (i = n - 2; i >= 0; i--) 116 { 117 x = sk_X509_value(certs, i); 118 X509_check_purpose(x, -1, -1); 119 cache = policy_cache_set(x); 120 /* If cache NULL something bad happened: return immediately */ 121 if (cache == NULL) 122 return 0; 123 /* If inconsistent extensions keep a note of it but continue */ 124 if (x->ex_flags & EXFLAG_INVALID_POLICY) 125 ret = -1; 126 /* Otherwise if we have no data (hence no CertificatePolicies) 127 * and haven't already set an inconsistent code note it. 128 */ 129 else if ((ret == 1) && !cache->data) 130 ret = 2; 131 if (explicit_policy > 0) 132 { 133 if (!(x->ex_flags & EXFLAG_SI)) 134 explicit_policy--; 135 if ((cache->explicit_skip != -1) 136 && (cache->explicit_skip < explicit_policy)) 137 explicit_policy = cache->explicit_skip; 138 } 139 } 140 141 if (ret != 1) 142 { 143 if (ret == 2 && !explicit_policy) 144 return 6; 145 return ret; 146 } 147 148 149 /* If we get this far initialize the tree */ 150 151 tree = OPENSSL_malloc(sizeof(X509_POLICY_TREE)); 152 153 if (!tree) 154 return 0; 155 156 tree->flags = 0; 157 tree->levels = OPENSSL_malloc(sizeof(X509_POLICY_LEVEL) * n); 158 tree->nlevel = 0; 159 tree->extra_data = NULL; 160 tree->auth_policies = NULL; 161 tree->user_policies = NULL; 162 163 if (!tree->levels) 164 { 165 OPENSSL_free(tree); 166 return 0; 167 } 168 169 memset(tree->levels, 0, n * sizeof(X509_POLICY_LEVEL)); 170 171 tree->nlevel = n; 172 173 level = tree->levels; 174 175 /* Root data: initialize to anyPolicy */ 176 177 data = policy_data_new(NULL, OBJ_nid2obj(NID_any_policy), 0); 178 179 if (!data || !level_add_node(level, data, NULL, tree)) 180 goto bad_tree; 181 182 for (i = n - 2; i >= 0; i--) 183 { 184 level++; 185 x = sk_X509_value(certs, i); 186 cache = policy_cache_set(x); 187 188 CRYPTO_add(&x->references, 1, CRYPTO_LOCK_X509); 189 level->cert = x; 190 191 if (!cache->anyPolicy) 192 level->flags |= X509_V_FLAG_INHIBIT_ANY; 193 194 /* Determine inhibit any and inhibit map flags */ 195 if (any_skip == 0) 196 { 197 /* Any matching allowed if certificate is self 198 * issued and not the last in the chain. 199 */ 200 if (!(x->ex_flags & EXFLAG_SI) || (i == 0)) 201 level->flags |= X509_V_FLAG_INHIBIT_ANY; 202 } 203 else 204 { 205 if (!(x->ex_flags & EXFLAG_SI)) 206 any_skip--; 207 if ((cache->any_skip >= 0) 208 && (cache->any_skip < any_skip)) 209 any_skip = cache->any_skip; 210 } 211 212 if (map_skip == 0) 213 level->flags |= X509_V_FLAG_INHIBIT_MAP; 214 else 215 { 216 map_skip--; 217 if ((cache->map_skip >= 0) 218 && (cache->map_skip < map_skip)) 219 map_skip = cache->map_skip; 220 } 221 222 223 } 224 225 *ptree = tree; 226 227 if (explicit_policy) 228 return 1; 229 else 230 return 5; 231 232 bad_tree: 233 234 X509_policy_tree_free(tree); 235 236 return 0; 237 238 } 239 240 /* This corresponds to RFC3280 XXXX XXXXX: 241 * link any data from CertificatePolicies onto matching parent 242 * or anyPolicy if no match. 243 */ 244 245 static int tree_link_nodes(X509_POLICY_LEVEL *curr, 246 const X509_POLICY_CACHE *cache) 247 { 248 int i; 249 X509_POLICY_LEVEL *last; 250 X509_POLICY_DATA *data; 251 X509_POLICY_NODE *parent; 252 last = curr - 1; 253 for (i = 0; i < sk_X509_POLICY_DATA_num(cache->data); i++) 254 { 255 data = sk_X509_POLICY_DATA_value(cache->data, i); 256 /* If a node is mapped any it doesn't have a corresponding 257 * CertificatePolicies entry. 258 * However such an identical node would be created 259 * if anyPolicy matching is enabled because there would be 260 * no match with the parent valid_policy_set. So we create 261 * link because then it will have the mapping flags 262 * right and we can prune it later. 263 */ 264 if ((data->flags & POLICY_DATA_FLAG_MAPPED_ANY) 265 && !(curr->flags & X509_V_FLAG_INHIBIT_ANY)) 266 continue; 267 /* Look for matching node in parent */ 268 parent = level_find_node(last, data->valid_policy); 269 /* If no match link to anyPolicy */ 270 if (!parent) 271 parent = last->anyPolicy; 272 if (parent && !level_add_node(curr, data, parent, NULL)) 273 return 0; 274 } 275 return 1; 276 } 277 278 /* This corresponds to RFC3280 XXXX XXXXX: 279 * Create new data for any unmatched policies in the parent and link 280 * to anyPolicy. 281 */ 282 283 static int tree_link_any(X509_POLICY_LEVEL *curr, 284 const X509_POLICY_CACHE *cache, 285 X509_POLICY_TREE *tree) 286 { 287 int i; 288 X509_POLICY_DATA *data; 289 X509_POLICY_NODE *node; 290 X509_POLICY_LEVEL *last; 291 292 last = curr - 1; 293 294 for (i = 0; i < sk_X509_POLICY_NODE_num(last->nodes); i++) 295 { 296 node = sk_X509_POLICY_NODE_value(last->nodes, i); 297 298 /* Skip any node with any children: we only want unmathced 299 * nodes. 300 * 301 * Note: need something better for policy mapping 302 * because each node may have multiple children 303 */ 304 if (node->nchild) 305 continue; 306 /* Create a new node with qualifiers from anyPolicy and 307 * id from unmatched node. 308 */ 309 data = policy_data_new(NULL, node->data->valid_policy, 310 node_critical(node)); 311 312 if (data == NULL) 313 return 0; 314 /* Curr may not have anyPolicy */ 315 data->qualifier_set = cache->anyPolicy->qualifier_set; 316 data->flags |= POLICY_DATA_FLAG_SHARED_QUALIFIERS; 317 if (!level_add_node(curr, data, node, tree)) 318 { 319 policy_data_free(data); 320 return 0; 321 } 322 } 323 /* Finally add link to anyPolicy */ 324 if (last->anyPolicy) 325 { 326 if (!level_add_node(curr, cache->anyPolicy, 327 last->anyPolicy, NULL)) 328 return 0; 329 } 330 return 1; 331 } 332 333 /* Prune the tree: delete any child mapped child data on the current level 334 * then proceed up the tree deleting any data with no children. If we ever 335 * have no data on a level we can halt because the tree will be empty. 336 */ 337 338 static int tree_prune(X509_POLICY_TREE *tree, X509_POLICY_LEVEL *curr) 339 { 340 X509_POLICY_NODE *node; 341 int i; 342 for (i = sk_X509_POLICY_NODE_num(curr->nodes) - 1; i >= 0; i--) 343 { 344 node = sk_X509_POLICY_NODE_value(curr->nodes, i); 345 /* Delete any mapped data: see RFC3280 XXXX */ 346 if (node->data->flags & POLICY_DATA_FLAG_MAP_MASK) 347 { 348 node->parent->nchild--; 349 OPENSSL_free(node); 350 (void)sk_X509_POLICY_NODE_delete(curr->nodes, i); 351 } 352 } 353 354 for(;;) { 355 --curr; 356 for (i = sk_X509_POLICY_NODE_num(curr->nodes) - 1; i >= 0; i--) 357 { 358 node = sk_X509_POLICY_NODE_value(curr->nodes, i); 359 if (node->nchild == 0) 360 { 361 node->parent->nchild--; 362 OPENSSL_free(node); 363 (void)sk_X509_POLICY_NODE_delete(curr->nodes, i); 364 } 365 } 366 if (curr->anyPolicy && !curr->anyPolicy->nchild) 367 { 368 if (curr->anyPolicy->parent) 369 curr->anyPolicy->parent->nchild--; 370 OPENSSL_free(curr->anyPolicy); 371 curr->anyPolicy = NULL; 372 } 373 if (curr == tree->levels) 374 { 375 /* If we zapped anyPolicy at top then tree is empty */ 376 if (!curr->anyPolicy) 377 return 2; 378 return 1; 379 } 380 } 381 382 return 1; 383 384 } 385 386 static int tree_add_auth_node(STACK_OF(X509_POLICY_NODE) **pnodes, 387 X509_POLICY_NODE *pcy) 388 { 389 if (!*pnodes) 390 { 391 *pnodes = policy_node_cmp_new(); 392 if (!*pnodes) 393 return 0; 394 } 395 else if (sk_X509_POLICY_NODE_find(*pnodes, pcy) != -1) 396 return 1; 397 398 if (!sk_X509_POLICY_NODE_push(*pnodes, pcy)) 399 return 0; 400 401 return 1; 402 403 } 404 405 /* Calculate the authority set based on policy tree. 406 * The 'pnodes' parameter is used as a store for the set of policy nodes 407 * used to calculate the user set. If the authority set is not anyPolicy 408 * then pnodes will just point to the authority set. If however the authority 409 * set is anyPolicy then the set of valid policies (other than anyPolicy) 410 * is store in pnodes. The return value of '2' is used in this case to indicate 411 * that pnodes should be freed. 412 */ 413 414 static int tree_calculate_authority_set(X509_POLICY_TREE *tree, 415 STACK_OF(X509_POLICY_NODE) **pnodes) 416 { 417 X509_POLICY_LEVEL *curr; 418 X509_POLICY_NODE *node, *anyptr; 419 STACK_OF(X509_POLICY_NODE) **addnodes; 420 int i, j; 421 curr = tree->levels + tree->nlevel - 1; 422 423 /* If last level contains anyPolicy set is anyPolicy */ 424 if (curr->anyPolicy) 425 { 426 if (!tree_add_auth_node(&tree->auth_policies, curr->anyPolicy)) 427 return 0; 428 addnodes = pnodes; 429 } 430 else 431 /* Add policies to authority set */ 432 addnodes = &tree->auth_policies; 433 434 curr = tree->levels; 435 for (i = 1; i < tree->nlevel; i++) 436 { 437 /* If no anyPolicy node on this this level it can't 438 * appear on lower levels so end search. 439 */ 440 if (!(anyptr = curr->anyPolicy)) 441 break; 442 curr++; 443 for (j = 0; j < sk_X509_POLICY_NODE_num(curr->nodes); j++) 444 { 445 node = sk_X509_POLICY_NODE_value(curr->nodes, j); 446 if ((node->parent == anyptr) 447 && !tree_add_auth_node(addnodes, node)) 448 return 0; 449 } 450 } 451 452 if (addnodes == pnodes) 453 return 2; 454 455 *pnodes = tree->auth_policies; 456 457 return 1; 458 } 459 460 static int tree_calculate_user_set(X509_POLICY_TREE *tree, 461 STACK_OF(ASN1_OBJECT) *policy_oids, 462 STACK_OF(X509_POLICY_NODE) *auth_nodes) 463 { 464 int i; 465 X509_POLICY_NODE *node; 466 ASN1_OBJECT *oid; 467 468 X509_POLICY_NODE *anyPolicy; 469 X509_POLICY_DATA *extra; 470 471 /* Check if anyPolicy present in authority constrained policy set: 472 * this will happen if it is a leaf node. 473 */ 474 475 if (sk_ASN1_OBJECT_num(policy_oids) <= 0) 476 return 1; 477 478 anyPolicy = tree->levels[tree->nlevel - 1].anyPolicy; 479 480 for (i = 0; i < sk_ASN1_OBJECT_num(policy_oids); i++) 481 { 482 oid = sk_ASN1_OBJECT_value(policy_oids, i); 483 if (OBJ_obj2nid(oid) == NID_any_policy) 484 { 485 tree->flags |= POLICY_FLAG_ANY_POLICY; 486 return 1; 487 } 488 } 489 490 for (i = 0; i < sk_ASN1_OBJECT_num(policy_oids); i++) 491 { 492 oid = sk_ASN1_OBJECT_value(policy_oids, i); 493 node = tree_find_sk(auth_nodes, oid); 494 if (!node) 495 { 496 if (!anyPolicy) 497 continue; 498 /* Create a new node with policy ID from user set 499 * and qualifiers from anyPolicy. 500 */ 501 extra = policy_data_new(NULL, oid, 502 node_critical(anyPolicy)); 503 if (!extra) 504 return 0; 505 extra->qualifier_set = anyPolicy->data->qualifier_set; 506 extra->flags = POLICY_DATA_FLAG_SHARED_QUALIFIERS 507 | POLICY_DATA_FLAG_EXTRA_NODE; 508 node = level_add_node(NULL, extra, anyPolicy->parent, 509 tree); 510 } 511 if (!tree->user_policies) 512 { 513 tree->user_policies = sk_X509_POLICY_NODE_new_null(); 514 if (!tree->user_policies) 515 return 1; 516 } 517 if (!sk_X509_POLICY_NODE_push(tree->user_policies, node)) 518 return 0; 519 } 520 return 1; 521 522 } 523 524 static int tree_evaluate(X509_POLICY_TREE *tree) 525 { 526 int ret, i; 527 X509_POLICY_LEVEL *curr = tree->levels + 1; 528 const X509_POLICY_CACHE *cache; 529 530 for(i = 1; i < tree->nlevel; i++, curr++) 531 { 532 cache = policy_cache_set(curr->cert); 533 if (!tree_link_nodes(curr, cache)) 534 return 0; 535 536 if (!(curr->flags & X509_V_FLAG_INHIBIT_ANY) 537 && !tree_link_any(curr, cache, tree)) 538 return 0; 539 ret = tree_prune(tree, curr); 540 if (ret != 1) 541 return ret; 542 } 543 544 return 1; 545 546 } 547 548 static void exnode_free(X509_POLICY_NODE *node) 549 { 550 if (node->data && (node->data->flags & POLICY_DATA_FLAG_EXTRA_NODE)) 551 OPENSSL_free(node); 552 } 553 554 555 void X509_policy_tree_free(X509_POLICY_TREE *tree) 556 { 557 X509_POLICY_LEVEL *curr; 558 int i; 559 560 if (!tree) 561 return; 562 563 sk_X509_POLICY_NODE_free(tree->auth_policies); 564 sk_X509_POLICY_NODE_pop_free(tree->user_policies, exnode_free); 565 566 for(i = 0, curr = tree->levels; i < tree->nlevel; i++, curr++) 567 { 568 if (curr->cert) 569 X509_free(curr->cert); 570 if (curr->nodes) 571 sk_X509_POLICY_NODE_pop_free(curr->nodes, 572 policy_node_free); 573 if (curr->anyPolicy) 574 policy_node_free(curr->anyPolicy); 575 } 576 577 if (tree->extra_data) 578 sk_X509_POLICY_DATA_pop_free(tree->extra_data, 579 policy_data_free); 580 581 OPENSSL_free(tree->levels); 582 OPENSSL_free(tree); 583 584 } 585 586 /* Application policy checking function. 587 * Return codes: 588 * 0 Internal Error. 589 * 1 Successful. 590 * -1 One or more certificates contain invalid or inconsistent extensions 591 * -2 User constrained policy set empty and requireExplicit true. 592 */ 593 594 int X509_policy_check(X509_POLICY_TREE **ptree, int *pexplicit_policy, 595 STACK_OF(X509) *certs, 596 STACK_OF(ASN1_OBJECT) *policy_oids, 597 unsigned int flags) 598 { 599 int ret; 600 X509_POLICY_TREE *tree = NULL; 601 STACK_OF(X509_POLICY_NODE) *nodes, *auth_nodes = NULL; 602 *ptree = NULL; 603 604 *pexplicit_policy = 0; 605 ret = tree_init(&tree, certs, flags); 606 607 608 switch (ret) 609 { 610 611 /* Tree empty requireExplicit False: OK */ 612 case 2: 613 return 1; 614 615 /* Some internal error */ 616 case 0: 617 return 0; 618 619 /* Tree empty requireExplicit True: Error */ 620 621 case 6: 622 *pexplicit_policy = 1; 623 return -2; 624 625 /* Tree OK requireExplicit True: OK and continue */ 626 case 5: 627 *pexplicit_policy = 1; 628 break; 629 630 /* Tree OK: continue */ 631 632 case 1: 633 if (!tree) 634 /* 635 * tree_init() returns success and a null tree 636 * if it's just looking at a trust anchor. 637 * I'm not sure that returning success here is 638 * correct, but I'm sure that reporting this 639 * as an internal error which our caller 640 * interprets as a malloc failure is wrong. 641 */ 642 return 1; 643 break; 644 } 645 646 if (!tree) goto error; 647 ret = tree_evaluate(tree); 648 649 if (ret <= 0) 650 goto error; 651 652 /* Return value 2 means tree empty */ 653 if (ret == 2) 654 { 655 X509_policy_tree_free(tree); 656 if (*pexplicit_policy) 657 return -2; 658 else 659 return 1; 660 } 661 662 /* Tree is not empty: continue */ 663 664 ret = tree_calculate_authority_set(tree, &auth_nodes); 665 666 if (!ret) 667 goto error; 668 669 if (!tree_calculate_user_set(tree, policy_oids, auth_nodes)) 670 goto error; 671 672 if (ret == 2) 673 sk_X509_POLICY_NODE_free(auth_nodes); 674 675 if (tree) 676 *ptree = tree; 677 678 if (*pexplicit_policy) 679 { 680 nodes = X509_policy_tree_get0_user_policies(tree); 681 if (sk_X509_POLICY_NODE_num(nodes) <= 0) 682 return -2; 683 } 684 685 return 1; 686 687 error: 688 689 X509_policy_tree_free(tree); 690 691 return 0; 692 693 } 694 695
