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