crypto/openssl/crypto/x509v3/pcy_tree.c

   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
  76 static 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
 241 static 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
 278 static 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
 330 static 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
 372 static 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
 398 static 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
 441 static 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
 500 static 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
 523 static 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
 529 void 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
 566 int 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 }