1/* pcy_tree.c */ 2/* Written by Dr Stephen N Henson (shenson@bigfoot.com) 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@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@cryptsoft.com). This product includes software written by Tim 55 * Hudson (tjh@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 74static 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 explicit_policy--; 134 if (!(x->ex_flags & EXFLAG_SS) 135 && (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) 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_SS) || (i == 0)) 201 level->flags |= X509_V_FLAG_INHIBIT_ANY; 202 } 203 else 204 { 205 any_skip--; 206 if ((cache->any_skip > 0) 207 && (cache->any_skip < any_skip)) 208 any_skip = cache->any_skip; 209 } 210 211 if (map_skip == 0) 212 level->flags |= X509_V_FLAG_INHIBIT_MAP; 213 else 214 { 215 map_skip--; 216 if ((cache->map_skip > 0) 217 && (cache->map_skip < map_skip)) 218 map_skip = cache->map_skip; 219 } 220 221 222 } 223 224 *ptree = tree; 225 226 if (explicit_policy) 227 return 1; 228 else 229 return 5; 230 231 bad_tree: 232 233 X509_policy_tree_free(tree); 234 235 return 0; 236 237 } 238 239/* This corresponds to RFC3280 XXXX XXXXX: 240 * link any data from CertificatePolicies onto matching parent 241 * or anyPolicy if no match. 242 */ 243 244static int tree_link_nodes(X509_POLICY_LEVEL *curr, 245 const X509_POLICY_CACHE *cache) 246 { 247 int i; 248 X509_POLICY_LEVEL *last; 249 X509_POLICY_DATA *data; 250 X509_POLICY_NODE *parent; 251 last = curr - 1; 252 for (i = 0; i < sk_X509_POLICY_DATA_num(cache->data); i++) 253 { 254 data = sk_X509_POLICY_DATA_value(cache->data, i); 255 /* If a node is mapped any it doesn't have a corresponding 256 * CertificatePolicies entry. 257 * However such an identical node would be created 258 * if anyPolicy matching is enabled because there would be 259 * no match with the parent valid_policy_set. So we create 260 * link because then it will have the mapping flags 261 * right and we can prune it later. 262 */ 263 if ((data->flags & POLICY_DATA_FLAG_MAPPED_ANY) 264 && !(curr->flags & X509_V_FLAG_INHIBIT_ANY)) 265 continue; 266 /* Look for matching node in parent */ 267 parent = level_find_node(last, data->valid_policy); 268 /* If no match link to anyPolicy */ 269 if (!parent) 270 parent = last->anyPolicy; 271 if (parent && !level_add_node(curr, data, parent, NULL)) 272 return 0; 273 } 274 return 1; 275 } 276 277/* This corresponds to RFC3280 XXXX XXXXX: 278 * Create new data for any unmatched policies in the parent and link 279 * to anyPolicy. 280 */ 281 282static int tree_link_any(X509_POLICY_LEVEL *curr, 283 const X509_POLICY_CACHE *cache, 284 X509_POLICY_TREE *tree) 285 { 286 int i; 287 X509_POLICY_DATA *data; 288 X509_POLICY_NODE *node; 289 X509_POLICY_LEVEL *last; 290 291 last = curr - 1; 292 293 for (i = 0; i < sk_X509_POLICY_NODE_num(last->nodes); i++) 294 { 295 node = sk_X509_POLICY_NODE_value(last->nodes, i); 296 297 /* Skip any node with any children: we only want unmathced 298 * nodes. 299 * 300 * Note: need something better for policy mapping 301 * because each node may have multiple children 302 */ 303 if (node->nchild) 304 continue; 305 /* Create a new node with qualifiers from anyPolicy and 306 * id from unmatched node. 307 */ 308 data = policy_data_new(NULL, node->data->valid_policy, 309 node_critical(node)); 310 311 if (data == NULL) 312 return 0; 313 data->qualifier_set = curr->anyPolicy->data->qualifier_set; 314 data->flags |= POLICY_DATA_FLAG_SHARED_QUALIFIERS; 315 if (!level_add_node(curr, data, node, tree)) 316 { 317 policy_data_free(data); 318 return 0; 319 } 320 } 321 /* Finally add link to anyPolicy */ 322 if (last->anyPolicy) 323 { 324 if (!level_add_node(curr, cache->anyPolicy, 325 last->anyPolicy, NULL)) 326 return 0; 327 } 328 return 1; 329 } 330 331/* Prune the tree: delete any child mapped child data on the current level 332 * then proceed up the tree deleting any data with no children. If we ever 333 * have no data on a level we can halt because the tree will be empty. 334 */ 335 336static int tree_prune(X509_POLICY_TREE *tree, X509_POLICY_LEVEL *curr) 337 { 338 X509_POLICY_NODE *node; 339 int i; 340 for (i = sk_X509_POLICY_NODE_num(curr->nodes) - 1; i >= 0; i--) 341 { 342 node = sk_X509_POLICY_NODE_value(curr->nodes, i); 343 /* Delete any mapped data: see RFC3280 XXXX */ 344 if (node->data->flags & POLICY_DATA_FLAG_MAP_MASK) 345 { 346 node->parent->nchild--; 347 OPENSSL_free(node); 348 sk_X509_POLICY_NODE_delete(curr->nodes, i); 349 } 350 } 351 352 for(;;) { 353 --curr; 354 for (i = sk_X509_POLICY_NODE_num(curr->nodes) - 1; i >= 0; i--) 355 { 356 node = sk_X509_POLICY_NODE_value(curr->nodes, i); 357 if (node->nchild == 0) 358 { 359 node->parent->nchild--; 360 OPENSSL_free(node); 361 sk_X509_POLICY_NODE_delete(curr->nodes, i); 362 } 363 } 364 if (curr->anyPolicy && !curr->anyPolicy->nchild) 365 { 366 if (curr->anyPolicy->parent) 367 curr->anyPolicy->parent->nchild--; 368 OPENSSL_free(curr->anyPolicy); 369 curr->anyPolicy = NULL; 370 } 371 if (curr == tree->levels) 372 { 373 /* If we zapped anyPolicy at top then tree is empty */ 374 if (!curr->anyPolicy) 375 return 2; 376 return 1; 377 } 378 } 379 380 return 1; 381 382 } 383 384static int tree_add_auth_node(STACK_OF(X509_POLICY_NODE) **pnodes, 385 X509_POLICY_NODE *pcy) 386 { 387 if (!*pnodes) 388 { 389 *pnodes = policy_node_cmp_new(); 390 if (!*pnodes) 391 return 0; 392 } 393 else if (sk_X509_POLICY_NODE_find(*pnodes, pcy) != -1) 394 return 1; 395 396 if (!sk_X509_POLICY_NODE_push(*pnodes, pcy)) 397 return 0; 398 399 return 1; 400 401 } 402 403/* Calculate the authority set based on policy tree. 404 * The 'pnodes' parameter is used as a store for the set of policy nodes 405 * used to calculate the user set. If the authority set is not anyPolicy 406 * then pnodes will just point to the authority set. If however the authority 407 * set is anyPolicy then the set of valid policies (other than anyPolicy) 408 * is store in pnodes. The return value of '2' is used in this case to indicate 409 * that pnodes should be freed. 410 */ 411 412static int tree_calculate_authority_set(X509_POLICY_TREE *tree, 413 STACK_OF(X509_POLICY_NODE) **pnodes) 414 { 415 X509_POLICY_LEVEL *curr; 416 X509_POLICY_NODE *node, *anyptr; 417 STACK_OF(X509_POLICY_NODE) **addnodes; 418 int i, j; 419 curr = tree->levels + tree->nlevel - 1; 420 421 /* If last level contains anyPolicy set is anyPolicy */ 422 if (curr->anyPolicy) 423 { 424 if (!tree_add_auth_node(&tree->auth_policies, curr->anyPolicy)) 425 return 0; 426 addnodes = pnodes; 427 } 428 else 429 /* Add policies to authority set */ 430 addnodes = &tree->auth_policies; 431 432 curr = tree->levels; 433 for (i = 1; i < tree->nlevel; i++) 434 { 435 /* If no anyPolicy node on this this level it can't 436 * appear on lower levels so end search. 437 */ 438 if (!(anyptr = curr->anyPolicy)) 439 break; 440 curr++; 441 for (j = 0; j < sk_X509_POLICY_NODE_num(curr->nodes); j++) 442 { 443 node = sk_X509_POLICY_NODE_value(curr->nodes, j); 444 if ((node->parent == anyptr) 445 && !tree_add_auth_node(addnodes, node)) 446 return 0; 447 } 448 } 449 450 if (addnodes == pnodes) 451 return 2; 452 453 *pnodes = tree->auth_policies; 454 455 return 1; 456 } 457 458static int tree_calculate_user_set(X509_POLICY_TREE *tree, 459 STACK_OF(ASN1_OBJECT) *policy_oids, 460 STACK_OF(X509_POLICY_NODE) *auth_nodes) 461 { 462 int i; 463 X509_POLICY_NODE *node; 464 ASN1_OBJECT *oid; 465 466 X509_POLICY_NODE *anyPolicy; 467 X509_POLICY_DATA *extra; 468 469 /* Check if anyPolicy present in authority constrained policy set: 470 * this will happen if it is a leaf node. 471 */ 472 473 if (sk_ASN1_OBJECT_num(policy_oids) <= 0) 474 return 1; 475 476 anyPolicy = tree->levels[tree->nlevel - 1].anyPolicy; 477 478 for (i = 0; i < sk_ASN1_OBJECT_num(policy_oids); i++) 479 { 480 oid = sk_ASN1_OBJECT_value(policy_oids, i); 481 if (OBJ_obj2nid(oid) == NID_any_policy) 482 { 483 tree->flags |= POLICY_FLAG_ANY_POLICY; 484 return 1; 485 } 486 } 487 488 for (i = 0; i < sk_ASN1_OBJECT_num(policy_oids); i++) 489 { 490 oid = sk_ASN1_OBJECT_value(policy_oids, i); 491 node = tree_find_sk(auth_nodes, oid); 492 if (!node) 493 { 494 if (!anyPolicy) 495 continue; 496 /* Create a new node with policy ID from user set 497 * and qualifiers from anyPolicy. 498 */ 499 extra = policy_data_new(NULL, oid, 500 node_critical(anyPolicy)); 501 if (!extra) 502 return 0; 503 extra->qualifier_set = anyPolicy->data->qualifier_set; 504 extra->flags = POLICY_DATA_FLAG_SHARED_QUALIFIERS 505 | POLICY_DATA_FLAG_EXTRA_NODE; 506 node = level_add_node(NULL, extra, anyPolicy->parent, 507 tree); 508 } 509 if (!tree->user_policies) 510 { 511 tree->user_policies = sk_X509_POLICY_NODE_new_null(); 512 if (!tree->user_policies) 513 return 1; 514 } 515 if (!sk_X509_POLICY_NODE_push(tree->user_policies, node)) 516 return 0; 517 } 518 return 1; 519 520 } 521 522static int tree_evaluate(X509_POLICY_TREE *tree) 523 { 524 int ret, i; 525 X509_POLICY_LEVEL *curr = tree->levels + 1; 526 const X509_POLICY_CACHE *cache; 527 528 for(i = 1; i < tree->nlevel; i++, curr++) 529 { 530 cache = policy_cache_set(curr->cert); 531 if (!tree_link_nodes(curr, cache)) 532 return 0; 533 534 if (!(curr->flags & X509_V_FLAG_INHIBIT_ANY) 535 && !tree_link_any(curr, cache, tree)) 536 return 0; 537 ret = tree_prune(tree, curr); 538 if (ret != 1) 539 return ret; 540 } 541 542 return 1; 543 544 } 545 546static void exnode_free(X509_POLICY_NODE *node) 547 { 548 if (node->data && (node->data->flags & POLICY_DATA_FLAG_EXTRA_NODE)) 549 OPENSSL_free(node); 550 } 551 552 553void X509_policy_tree_free(X509_POLICY_TREE *tree) 554 { 555 X509_POLICY_LEVEL *curr; 556 int i; 557 558 if (!tree) 559 return; 560 561 sk_X509_POLICY_NODE_free(tree->auth_policies); 562 sk_X509_POLICY_NODE_pop_free(tree->user_policies, exnode_free); 563 564 for(i = 0, curr = tree->levels; i < tree->nlevel; i++, curr++) 565 { 566 if (curr->cert) 567 X509_free(curr->cert); 568 if (curr->nodes) 569 sk_X509_POLICY_NODE_pop_free(curr->nodes, 570 policy_node_free); 571 if (curr->anyPolicy) 572 policy_node_free(curr->anyPolicy); 573 } 574 575 if (tree->extra_data) 576 sk_X509_POLICY_DATA_pop_free(tree->extra_data, 577 policy_data_free); 578 579 OPENSSL_free(tree->levels); 580 OPENSSL_free(tree); 581 582 } 583 584/* Application policy checking function. 585 * Return codes: 586 * 0 Internal Error. 587 * 1 Successful. 588 * -1 One or more certificates contain invalid or inconsistent extensions 589 * -2 User constrained policy set empty and requireExplicit true. 590 */ 591 592int X509_policy_check(X509_POLICY_TREE **ptree, int *pexplicit_policy, 593 STACK_OF(X509) *certs, 594 STACK_OF(ASN1_OBJECT) *policy_oids, 595 unsigned int flags) 596 { 597 int ret; 598 X509_POLICY_TREE *tree = NULL; 599 STACK_OF(X509_POLICY_NODE) *nodes, *auth_nodes = NULL; 600 *ptree = NULL; 601 602 *pexplicit_policy = 0; 603 ret = tree_init(&tree, certs, flags); 604 605 606 switch (ret) 607 { 608 609 /* Tree empty requireExplicit False: OK */ 610 case 2: 611 return 1; 612 613 /* Some internal error */ 614 case 0: 615 return 0; 616 617 /* Tree empty requireExplicit True: Error */ 618 619 case 6: 620 *pexplicit_policy = 1; 621 return -2; 622 623 /* Tree OK requireExplicit True: OK and continue */ 624 case 5: 625 *pexplicit_policy = 1; 626 break; 627 628 /* Tree OK: continue */ 629 630 case 1: 631 if (!tree) 632 /* 633 * tree_init() returns success and a null tree 634 * if it's just looking at a trust anchor. 635 * I'm not sure that returning success here is 636 * correct, but I'm sure that reporting this 637 * as an internal error which our caller 638 * interprets as a malloc failure is wrong. 639 */ 640 return 1; 641 break; 642 } 643 644 if (!tree) goto error; 645 ret = tree_evaluate(tree); 646 647 if (ret <= 0) 648 goto error; 649 650 /* Return value 2 means tree empty */ 651 if (ret == 2) 652 { 653 X509_policy_tree_free(tree); 654 if (*pexplicit_policy) 655 return -2; 656 else 657 return 1; 658 } 659 660 /* Tree is not empty: continue */ 661 662 ret = tree_calculate_authority_set(tree, &auth_nodes); 663 664 if (!ret) 665 goto error; 666 667 if (!tree_calculate_user_set(tree, policy_oids, auth_nodes)) 668 goto error; 669 670 if (ret == 2) 671 sk_X509_POLICY_NODE_free(auth_nodes); 672 673 if (tree) 674 *ptree = tree; 675 676 if (*pexplicit_policy) 677 { 678 nodes = X509_policy_tree_get0_user_policies(tree); 679 if (sk_X509_POLICY_NODE_num(nodes) <= 0) 680 return -2; 681 } 682 683 return 1; 684 685 error: 686 687 X509_policy_tree_free(tree); 688 689 return 0; 690 691 } 692 693