crypto/x509v3/pcy_tree.c

   1 /*
   2  * Written by Dr Stephen N Henson (steve@openssl.org) for the OpenSSL project
   3  * 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 "internal/cryptlib.h"
  60 #include <openssl/x509.h>
  61 #include <openssl/x509v3.h>
  62
  63 #include "pcy_int.h"
  64
  65 /*
  66  * Enable this to print out the complete policy tree at various point during
  67  * evaluation.
  68  */
  69
  70 /*
  71  * #define OPENSSL_POLICY_DEBUG
  72  */
  73
  74 #ifdef OPENSSL_POLICY_DEBUG
  75
  76 static void expected_print(BIO *err, X509_POLICY_LEVEL *lev,
  77                            X509_POLICY_NODE *node, int indent)
  78 {
  79     if ((lev->flags & X509_V_FLAG_INHIBIT_MAP)
  80         || !(node->data->flags & POLICY_DATA_FLAG_MAP_MASK))
  81         BIO_puts(err, "  Not Mapped\n");
  82     else {
  83         int i;
  84         STACK_OF(ASN1_OBJECT) *pset = node->data->expected_policy_set;
  85         ASN1_OBJECT *oid;
  86         BIO_puts(err, "  Expected: ");
  87         for (i = 0; i < sk_ASN1_OBJECT_num(pset); i++) {
  88             oid = sk_ASN1_OBJECT_value(pset, i);
  89             if (i)
  90                 BIO_puts(err, ", ");
  91             i2a_ASN1_OBJECT(err, oid);
  92         }
  93         BIO_puts(err, "\n");
  94     }
  95 }
  96
  97 static void tree_print(char *str, X509_POLICY_TREE *tree,
  98                        X509_POLICY_LEVEL *curr)
  99 {
 100     BIO *err = BIO_new_fp(stderr, BIO_NOCLOSE);
 101     X509_POLICY_LEVEL *plev;
 102
 103     if (err == NULL)
 104         return;
 105     if (!curr)
 106         curr = tree->levels + tree->nlevel;
 107     else
 108         curr++;
 109
 110     BIO_printf(err, "Level print after %s\n", str);
 111     BIO_printf(err, "Printing Up to Level %ld\n", curr - tree->levels);
 112     for (plev = tree->levels; plev != curr; plev++) {
 113         int i;
 114
 115         BIO_printf(err, "Level %ld, flags = %x\n",
 116                    (long)(plev - tree->levels), plev->flags);
 117         for (i = 0; i < sk_X509_POLICY_NODE_num(plev->nodes); i++) {
 118             X509_POLICY_NODE *node = sk_X509_POLICY_NODE_value(plev->nodes, i);
 119
 120             X509_POLICY_NODE_print(err, node, 2);
 121             expected_print(err, plev, node, 2);
 122             BIO_printf(err, "  Flags: %x\n", node->data->flags);
 123         }
 124         if (plev->anyPolicy)
 125             X509_POLICY_NODE_print(err, plev->anyPolicy, 2);
 126     }
 127     BIO_free(err);
 128 }
 129 #endif
 130
 131 /*-
 132  * Return value: <= 0 on error, or positive bit mask:
 133  *
 134  * X509_PCY_TREE_VALID: valid tree
 135  * X509_PCY_TREE_EMPTY: empty tree (including bare TA case)
 136  * X509_PCY_TREE_EXPLICIT: explicit policy required
 137  */
 138 static int tree_init(X509_POLICY_TREE **ptree, STACK_OF(X509) *certs,
 139                      unsigned int flags)
 140 {
 141     X509_POLICY_TREE *tree;
 142     X509_POLICY_LEVEL *level;
 143     const X509_POLICY_CACHE *cache;
 144     X509_POLICY_DATA *data = NULL;
 145     int ret = X509_PCY_TREE_VALID;
 146     int n = sk_X509_num(certs) - 1; /* RFC5280 paths omit the TA */
 147     int explicit_policy = (flags & X509_V_FLAG_EXPLICIT_POLICY) ? 0 : n+1;
 148     int any_skip = (flags & X509_V_FLAG_INHIBIT_ANY) ? 0 : n+1;
 149     int map_skip = (flags & X509_V_FLAG_INHIBIT_MAP) ? 0 : n+1;
 150     int i;
 151
 152     *ptree = NULL;
 153
 154     /* Can't do anything with just a trust anchor */
 155     if (n == 0)
 156         return X509_PCY_TREE_EMPTY;
 157
 158     /*
 159      * First setup the policy cache in all n non-TA certificates, this will be
 160      * used in X509_verify_cert() which will invoke the verify callback for all
 161      * certificates with invalid policy extensions.
 162      */
 163     for (i = n - 1; i >= 0; i--) {
 164         X509 *x = sk_X509_value(certs, i);
 165
 166         /* Call for side-effect of computing hash and caching extensions */
 167         X509_check_purpose(x, -1, 0);
 168
 169         /* If cache is NULL, likely ENOMEM: return immediately */
 170         if ((cache = policy_cache_set(x)) == NULL)
 171             return X509_PCY_TREE_INTERNAL;
 172     }
 173
 174     /*
 175      * At this point check for invalid policies and required explicit policy.
 176      * Note that the explicit_policy counter is a count-down to zero, with the
 177      * requirement kicking in if and once it does that.  The counter is
 178      * decremented for every non-self-issued certificate in the path, but may
 179      * be further reduced by policy constraints in a non-leaf certificate.
 180      *
 181      * The ultimate policy set is the interesection of all the policies along
 182      * the path, if we hit a certificate with an empty policy set, and explicit
 183      * policy is required we're done.
 184      */
 185     for (i = n - 1;
 186          i >= 0 && (explicit_policy > 0 || (ret & X509_PCY_TREE_EMPTY) == 0);
 187          i--) {
 188         X509 *x = sk_X509_value(certs, i);
 189         uint32_t ex_flags = X509_get_extension_flags(x);
 190
 191         /* All the policies are already cached, we can return early */
 192         if (ex_flags & EXFLAG_INVALID_POLICY)
 193             return X509_PCY_TREE_INVALID;
 194
 195         /* Access the cache which we now know exists */
 196         cache = policy_cache_set(x);
 197
 198         if ((ret & X509_PCY_TREE_VALID) && cache->data == NULL)
 199             ret = X509_PCY_TREE_EMPTY;
 200         if (explicit_policy > 0) {
 201             if (!(ex_flags & EXFLAG_SI))
 202                 explicit_policy--;
 203             if ((cache->explicit_skip >= 0)
 204                 && (cache->explicit_skip < explicit_policy))
 205                 explicit_policy = cache->explicit_skip;
 206         }
 207     }
 208
 209     if (explicit_policy == 0)
 210         ret |= X509_PCY_TREE_EXPLICIT;
 211     if ((ret & X509_PCY_TREE_VALID) == 0)
 212         return ret;
 213
 214     /* If we get this far initialize the tree */
 215     if ((tree = OPENSSL_zalloc(sizeof(*tree))) == NULL)
 216         return X509_PCY_TREE_INTERNAL;
 217
 218     /*
 219      * http://tools.ietf.org/html/rfc5280#section-6.1.2, figure 3.
 220      *
 221      * The top level is implicitly for the trust anchor with valid expected
 222      * policies of anyPolicy.  (RFC 5280 has the TA at depth 0 and the leaf at
 223      * depth n, we have the leaf at depth 0 and the TA at depth n).
 224      */
 225     if ((tree->levels = OPENSSL_zalloc(sizeof(*tree->levels)*(n+1))) == NULL) {
 226         OPENSSL_free(tree);
 227         return X509_PCY_TREE_INTERNAL;
 228     }
 229     tree->nlevel = n+1;
 230     level = tree->levels;
 231     if ((data = policy_data_new(NULL, OBJ_nid2obj(NID_any_policy), 0)) == NULL)
 232         goto bad_tree;
 233     if (level_add_node(level, data, NULL, tree) == NULL) {
 234         policy_data_free(data);
 235         goto bad_tree;
 236     }
 237
 238     /*
 239      * In this pass initialize all the tree levels and whether anyPolicy and
 240      * policy mapping are inhibited at each level.
 241      */
 242     for (i = n - 1; i >= 0; i--) {
 243         X509 *x = sk_X509_value(certs, i);
 244         uint32_t ex_flags = X509_get_extension_flags(x);
 245
 246         /* Access the cache which we now know exists */
 247         cache = policy_cache_set(x);
 248
 249         X509_up_ref(x);
 250         (++level)->cert = x;
 251
 252         if (!cache->anyPolicy)
 253             level->flags |= X509_V_FLAG_INHIBIT_ANY;
 254
 255         /* Determine inhibit any and inhibit map flags */
 256         if (any_skip == 0) {
 257             /*
 258              * Any matching allowed only if certificate is self issued and not
 259              * the last in the chain.
 260              */
 261             if (!(ex_flags & EXFLAG_SI) || (i == 0))
 262                 level->flags |= X509_V_FLAG_INHIBIT_ANY;
 263         } else {
 264             if (!(ex_flags & EXFLAG_SI))
 265                 any_skip--;
 266             if ((cache->any_skip >= 0) && (cache->any_skip < any_skip))
 267                 any_skip = cache->any_skip;
 268         }
 269
 270         if (map_skip == 0)
 271             level->flags |= X509_V_FLAG_INHIBIT_MAP;
 272         else {
 273             if (!(ex_flags & EXFLAG_SI))
 274                 map_skip--;
 275             if ((cache->map_skip >= 0) && (cache->map_skip < map_skip))
 276                 map_skip = cache->map_skip;
 277         }
 278     }
 279
 280     *ptree = tree;
 281     return ret;
 282
 283  bad_tree:
 284     X509_policy_tree_free(tree);
 285     return X509_PCY_TREE_INTERNAL;
 286 }
 287
 288 /*
 289  * Return value: 1 on success, 0 otherwise
 290  */
 291 static int tree_link_matching_nodes(X509_POLICY_LEVEL *curr,
 292                                     X509_POLICY_DATA *data)
 293 {
 294     X509_POLICY_LEVEL *last = curr - 1;
 295     int i, matched = 0;
 296
 297     /* Iterate through all in nodes linking matches */
 298     for (i = 0; i < sk_X509_POLICY_NODE_num(last->nodes); i++) {
 299         X509_POLICY_NODE *node = sk_X509_POLICY_NODE_value(last->nodes, i);
 300
 301         if (policy_node_match(last, node, data->valid_policy)) {
 302             if (level_add_node(curr, data, node, NULL) == NULL)
 303                 return 0;
 304             matched = 1;
 305         }
 306     }
 307     if (!matched && last->anyPolicy) {
 308         if (level_add_node(curr, data, last->anyPolicy, NULL) == NULL)
 309             return 0;
 310     }
 311     return 1;
 312 }
 313
 314 /*
 315  * This corresponds to RFC3280 6.1.3(d)(1): link any data from
 316  * CertificatePolicies onto matching parent or anyPolicy if no match.
 317  *
 318  * Return value: 1 on success, 0 otherwise.
 319  */
 320 static int tree_link_nodes(X509_POLICY_LEVEL *curr,
 321                            const X509_POLICY_CACHE *cache)
 322 {
 323     int i;
 324
 325     for (i = 0; i < sk_X509_POLICY_DATA_num(cache->data); i++) {
 326         X509_POLICY_DATA *data = sk_X509_POLICY_DATA_value(cache->data, i);
 327
 328         /* Look for matching nodes in previous level */
 329         if (!tree_link_matching_nodes(curr, data))
 330             return 0;
 331     }
 332     return 1;
 333 }
 334
 335 /*
 336  * This corresponds to RFC3280 6.1.3(d)(2): Create new data for any unmatched
 337  * policies in the parent and link to anyPolicy.
 338  *
 339  * Return value: 1 on success, 0 otherwise.
 340  */
 341 static int tree_add_unmatched(X509_POLICY_LEVEL *curr,
 342                               const X509_POLICY_CACHE *cache,
 343                               const ASN1_OBJECT *id,
 344                               X509_POLICY_NODE *node, X509_POLICY_TREE *tree)
 345 {
 346     X509_POLICY_DATA *data;
 347
 348     if (id == NULL)
 349         id = node->data->valid_policy;
 350     /*
 351      * Create a new node with qualifiers from anyPolicy and id from unmatched
 352      * node.
 353      */
 354     if ((data = policy_data_new(NULL, id, node_critical(node))) == NULL)
 355         return 0;
 356
 357     /* Curr may not have anyPolicy */
 358     data->qualifier_set = cache->anyPolicy->qualifier_set;
 359     data->flags |= POLICY_DATA_FLAG_SHARED_QUALIFIERS;
 360     if (level_add_node(curr, data, node, tree) == NULL) {
 361         policy_data_free(data);
 362         return 0;
 363     }
 364     return 1;
 365 }
 366
 367 /*
 368  * Return value: 1 on success, 0 otherwise.
 369  */
 370 static int tree_link_unmatched(X509_POLICY_LEVEL *curr,
 371                                const X509_POLICY_CACHE *cache,
 372                                X509_POLICY_NODE *node, X509_POLICY_TREE *tree)
 373 {
 374     const X509_POLICY_LEVEL *last = curr - 1;
 375     int i;
 376
 377     if ((last->flags & X509_V_FLAG_INHIBIT_MAP)
 378         || !(node->data->flags & POLICY_DATA_FLAG_MAPPED)) {
 379         /* If no policy mapping: matched if one child present */
 380         if (node->nchild)
 381             return 1;
 382         if (!tree_add_unmatched(curr, cache, NULL, node, tree))
 383             return 0;
 384         /* Add it */
 385     } else {
 386         /* If mapping: matched if one child per expected policy set */
 387         STACK_OF(ASN1_OBJECT) *expset = node->data->expected_policy_set;
 388         if (node->nchild == sk_ASN1_OBJECT_num(expset))
 389             return 1;
 390         /* Locate unmatched nodes */
 391         for (i = 0; i < sk_ASN1_OBJECT_num(expset); i++) {
 392             ASN1_OBJECT *oid = sk_ASN1_OBJECT_value(expset, i);
 393             if (level_find_node(curr, node, oid))
 394                 continue;
 395             if (!tree_add_unmatched(curr, cache, oid, node, tree))
 396                 return 0;
 397         }
 398
 399     }
 400     return 1;
 401 }
 402
 403 /*
 404  * Return value: 1 on success, 0 otherwise
 405  */
 406 static int tree_link_any(X509_POLICY_LEVEL *curr,
 407                          const X509_POLICY_CACHE *cache,
 408                          X509_POLICY_TREE *tree)
 409 {
 410     int i;
 411     X509_POLICY_NODE *node;
 412     X509_POLICY_LEVEL *last = curr - 1;
 413
 414     for (i = 0; i < sk_X509_POLICY_NODE_num(last->nodes); i++) {
 415         node = sk_X509_POLICY_NODE_value(last->nodes, i);
 416
 417         if (!tree_link_unmatched(curr, cache, node, tree))
 418             return 0;
 419     }
 420     /* Finally add link to anyPolicy */
 421     if (last->anyPolicy &&
 422         level_add_node(curr, cache->anyPolicy, last->anyPolicy, NULL) == NULL)
 423         return 0;
 424     return 1;
 425 }
 426
 427 /*-
 428  * Prune the tree: delete any child mapped child data on the current level then
 429  * proceed up the tree deleting any data with no children. If we ever have no
 430  * data on a level we can halt because the tree will be empty.
 431  *
 432  * Return value: <= 0 error, otherwise one of:
 433  *
 434  * X509_PCY_TREE_VALID: valid tree
 435  * X509_PCY_TREE_EMPTY: empty tree
 436  */
 437 static int tree_prune(X509_POLICY_TREE *tree, X509_POLICY_LEVEL *curr)
 438 {
 439     STACK_OF(X509_POLICY_NODE) *nodes;
 440     X509_POLICY_NODE *node;
 441     int i;
 442     nodes = curr->nodes;
 443     if (curr->flags & X509_V_FLAG_INHIBIT_MAP) {
 444         for (i = sk_X509_POLICY_NODE_num(nodes) - 1; i >= 0; i--) {
 445             node = sk_X509_POLICY_NODE_value(nodes, i);
 446             /* Delete any mapped data: see RFC3280 XXXX */
 447             if (node->data->flags & POLICY_DATA_FLAG_MAP_MASK) {
 448                 node->parent->nchild--;
 449                 OPENSSL_free(node);
 450                 (void)sk_X509_POLICY_NODE_delete(nodes, i);
 451             }
 452         }
 453     }
 454
 455     for (;;) {
 456         --curr;
 457         nodes = curr->nodes;
 458         for (i = sk_X509_POLICY_NODE_num(nodes) - 1; i >= 0; i--) {
 459             node = sk_X509_POLICY_NODE_value(nodes, i);
 460             if (node->nchild == 0) {
 461                 node->parent->nchild--;
 462                 OPENSSL_free(node);
 463                 (void)sk_X509_POLICY_NODE_delete(nodes, i);
 464             }
 465         }
 466         if (curr->anyPolicy && !curr->anyPolicy->nchild) {
 467             if (curr->anyPolicy->parent)
 468                 curr->anyPolicy->parent->nchild--;
 469             OPENSSL_free(curr->anyPolicy);
 470             curr->anyPolicy = NULL;
 471         }
 472         if (curr == tree->levels) {
 473             /* If we zapped anyPolicy at top then tree is empty */
 474             if (!curr->anyPolicy)
 475                 return X509_PCY_TREE_EMPTY;
 476             break;
 477         }
 478     }
 479     return X509_PCY_TREE_VALID;
 480 }
 481
 482 /*
 483  * Return value: 1 on success, 0 otherwise.
 484  */
 485 static int tree_add_auth_node(STACK_OF(X509_POLICY_NODE) **pnodes,
 486                               X509_POLICY_NODE *pcy)
 487 {
 488     if (*pnodes == NULL &&
 489         (*pnodes = policy_node_cmp_new()) == NULL)
 490         return 0;
 491     if (sk_X509_POLICY_NODE_find(*pnodes, pcy) != -1)
 492         return 1;
 493     return sk_X509_POLICY_NODE_push(*pnodes, pcy) != 0;
 494 }
 495
 496 #define TREE_CALC_FAILURE 0
 497 #define TREE_CALC_OK_NOFREE 1
 498 #define TREE_CALC_OK_DOFREE 2
 499
 500 /*-
 501  * Calculate the authority set based on policy tree. The 'pnodes' parameter is
 502  * used as a store for the set of policy nodes used to calculate the user set.
 503  * If the authority set is not anyPolicy then pnodes will just point to the
 504  * authority set. If however the authority set is anyPolicy then the set of
 505  * valid policies (other than anyPolicy) is store in pnodes.
 506  *
 507  * Return value:
 508  *  TREE_CALC_FAILURE on failure,
 509  *  TREE_CALC_OK_NOFREE on success and pnodes need not be freed,
 510  *  TREE_CALC_OK_DOFREE on success and pnodes needs to be freed
 511  */
 512 static int tree_calculate_authority_set(X509_POLICY_TREE *tree,
 513                                         STACK_OF(X509_POLICY_NODE) **pnodes)
 514 {
 515     X509_POLICY_LEVEL *curr;
 516     X509_POLICY_NODE *node, *anyptr;
 517     STACK_OF(X509_POLICY_NODE) **addnodes;
 518     int i, j;
 519     curr = tree->levels + tree->nlevel - 1;
 520
 521     /* If last level contains anyPolicy set is anyPolicy */
 522     if (curr->anyPolicy) {
 523         if (!tree_add_auth_node(&tree->auth_policies, curr->anyPolicy))
 524             return TREE_CALC_FAILURE;
 525         addnodes = pnodes;
 526     } else
 527         /* Add policies to authority set */
 528         addnodes = &tree->auth_policies;
 529
 530     curr = tree->levels;
 531     for (i = 1; i < tree->nlevel; i++) {
 532         /*
 533          * If no anyPolicy node on this this level it can't appear on lower
 534          * levels so end search.
 535          */
 536         if ((anyptr = curr->anyPolicy) == NULL)
 537             break;
 538         curr++;
 539         for (j = 0; j < sk_X509_POLICY_NODE_num(curr->nodes); j++) {
 540             node = sk_X509_POLICY_NODE_value(curr->nodes, j);
 541             if ((node->parent == anyptr)
 542                 && !tree_add_auth_node(addnodes, node)) {
 543                 if (addnodes == pnodes) {
 544                     sk_X509_POLICY_NODE_free(*pnodes);
 545                     *pnodes = NULL;
 546                 }
 547                 return TREE_CALC_FAILURE;
 548             }
 549         }
 550     }
 551     if (addnodes == pnodes)
 552         return TREE_CALC_OK_DOFREE;
 553
 554     *pnodes = tree->auth_policies;
 555     return TREE_CALC_OK_NOFREE;
 556 }
 557
 558 /*
 559  * Return value: 1 on success, 0 otherwise.
 560  */
 561 static int tree_calculate_user_set(X509_POLICY_TREE *tree,
 562                                    STACK_OF(ASN1_OBJECT) *policy_oids,
 563                                    STACK_OF(X509_POLICY_NODE) *auth_nodes)
 564 {
 565     int i;
 566     X509_POLICY_NODE *node;
 567     ASN1_OBJECT *oid;
 568     X509_POLICY_NODE *anyPolicy;
 569     X509_POLICY_DATA *extra;
 570
 571     /*
 572      * Check if anyPolicy present in authority constrained policy set: this
 573      * will happen if it is a leaf node.
 574      */
 575     if (sk_ASN1_OBJECT_num(policy_oids) <= 0)
 576         return 1;
 577
 578     anyPolicy = tree->levels[tree->nlevel - 1].anyPolicy;
 579
 580     for (i = 0; i < sk_ASN1_OBJECT_num(policy_oids); i++) {
 581         oid = sk_ASN1_OBJECT_value(policy_oids, i);
 582         if (OBJ_obj2nid(oid) == NID_any_policy) {
 583             tree->flags |= POLICY_FLAG_ANY_POLICY;
 584             return 1;
 585         }
 586     }
 587
 588     for (i = 0; i < sk_ASN1_OBJECT_num(policy_oids); i++) {
 589         oid = sk_ASN1_OBJECT_value(policy_oids, i);
 590         node = tree_find_sk(auth_nodes, oid);
 591         if (!node) {
 592             if (!anyPolicy)
 593                 continue;
 594             /*
 595              * Create a new node with policy ID from user set and qualifiers
 596              * from anyPolicy.
 597              */
 598             extra = policy_data_new(NULL, oid, node_critical(anyPolicy));
 599             if (extra == NULL)
 600                 return 0;
 601             extra->qualifier_set = anyPolicy->data->qualifier_set;
 602             extra->flags = POLICY_DATA_FLAG_SHARED_QUALIFIERS
 603                 | POLICY_DATA_FLAG_EXTRA_NODE;
 604             node = level_add_node(NULL, extra, anyPolicy->parent, tree);
 605         }
 606         if (!tree->user_policies) {
 607             tree->user_policies = sk_X509_POLICY_NODE_new_null();
 608             if (!tree->user_policies)
 609                 return 1;
 610         }
 611         if (!sk_X509_POLICY_NODE_push(tree->user_policies, node))
 612             return 0;
 613     }
 614     return 1;
 615 }
 616
 617 /*-
 618  * Return value: <= 0 error, otherwise one of:
 619  *  X509_PCY_TREE_VALID: valid tree
 620  *  X509_PCY_TREE_EMPTY: empty tree
 621  * (see tree_prune()).
 622  */
 623 static int tree_evaluate(X509_POLICY_TREE *tree)
 624 {
 625     int ret, i;
 626     X509_POLICY_LEVEL *curr = tree->levels + 1;
 627     const X509_POLICY_CACHE *cache;
 628
 629     for (i = 1; i < tree->nlevel; i++, curr++) {
 630         cache = policy_cache_set(curr->cert);
 631         if (!tree_link_nodes(curr, cache))
 632             return X509_PCY_TREE_INTERNAL;
 633
 634         if (!(curr->flags & X509_V_FLAG_INHIBIT_ANY)
 635             && !tree_link_any(curr, cache, tree))
 636             return X509_PCY_TREE_INTERNAL;
 637 #ifdef OPENSSL_POLICY_DEBUG
 638         tree_print("before tree_prune()", tree, curr);
 639 #endif
 640         ret = tree_prune(tree, curr);
 641         if (ret != X509_PCY_TREE_VALID)
 642             return ret;
 643     }
 644     return X509_PCY_TREE_VALID;
 645 }
 646
 647 static void exnode_free(X509_POLICY_NODE *node)
 648 {
 649     if (node->data && (node->data->flags & POLICY_DATA_FLAG_EXTRA_NODE))
 650         OPENSSL_free(node);
 651 }
 652
 653 void X509_policy_tree_free(X509_POLICY_TREE *tree)
 654 {
 655     X509_POLICY_LEVEL *curr;
 656     int i;
 657
 658     if (!tree)
 659         return;
 660
 661     sk_X509_POLICY_NODE_free(tree->auth_policies);
 662     sk_X509_POLICY_NODE_pop_free(tree->user_policies, exnode_free);
 663
 664     for (i = 0, curr = tree->levels; i < tree->nlevel; i++, curr++) {
 665         X509_free(curr->cert);
 666         sk_X509_POLICY_NODE_pop_free(curr->nodes, policy_node_free);
 667         policy_node_free(curr->anyPolicy);
 668     }
 669
 670     sk_X509_POLICY_DATA_pop_free(tree->extra_data, policy_data_free);
 671     OPENSSL_free(tree->levels);
 672     OPENSSL_free(tree);
 673
 674 }
 675
 676 /*-
 677  * Application policy checking function.
 678  * Return codes:
 679  *  X509_PCY_TREE_FAILURE:  Failure to satisfy explicit policy
 680  *  X509_PCY_TREE_INVALID:  Inconsistent or invalid extensions
 681  *  X509_PCY_TREE_INTERNAL: Internal error, most likely malloc
 682  *  X509_PCY_TREE_VALID:    Success (null tree if empty or bare TA)
 683  */
 684 int X509_policy_check(X509_POLICY_TREE **ptree, int *pexplicit_policy,
 685                       STACK_OF(X509) *certs,
 686                       STACK_OF(ASN1_OBJECT) *policy_oids, unsigned int flags)
 687 {
 688     int init_ret;
 689     int ret;
 690     X509_POLICY_TREE *tree = NULL;
 691     STACK_OF(X509_POLICY_NODE) *nodes, *auth_nodes = NULL;
 692
 693     *ptree = NULL;
 694     *pexplicit_policy = 0;
 695     init_ret = tree_init(&tree, certs, flags);
 696
 697     if (init_ret <= 0)
 698         return init_ret;
 699
 700     if ((init_ret & X509_PCY_TREE_EXPLICIT) == 0) {
 701         if (init_ret & X509_PCY_TREE_EMPTY) {
 702             X509_policy_tree_free(tree);
 703             return X509_PCY_TREE_VALID;
 704         }
 705     } else {
 706         *pexplicit_policy = 1;
 707         /* Tree empty and requireExplicit True: Error */
 708         if (init_ret & X509_PCY_TREE_EMPTY)
 709             return X509_PCY_TREE_FAILURE;
 710     }
 711
 712     ret = tree_evaluate(tree);
 713 #ifdef OPENSSL_POLICY_DEBUG
 714     tree_print("tree_evaluate()", tree, NULL);
 715 #endif
 716     if (ret <= 0)
 717         goto error;
 718
 719     if (ret == X509_PCY_TREE_EMPTY) {
 720         X509_policy_tree_free(tree);
 721         if (init_ret & X509_PCY_TREE_EXPLICIT)
 722             return X509_PCY_TREE_FAILURE;
 723         return X509_PCY_TREE_VALID;
 724     }
 725
 726     /* Tree is not empty: continue */
 727     if ((ret = tree_calculate_authority_set(tree, &auth_nodes)) == 0 ||
 728         !tree_calculate_user_set(tree, policy_oids, auth_nodes))
 729         goto error;
 730     if (ret == TREE_CALC_OK_DOFREE)
 731         sk_X509_POLICY_NODE_free(auth_nodes);
 732
 733     *ptree = tree;
 734
 735     if (init_ret & X509_PCY_TREE_EXPLICIT) {
 736         nodes = X509_policy_tree_get0_user_policies(tree);
 737         if (sk_X509_POLICY_NODE_num(nodes) <= 0)
 738             return X509_PCY_TREE_FAILURE;
 739     }
 740     return X509_PCY_TREE_VALID;
 741
 742  error:
 743     X509_policy_tree_free(tree);
 744     return X509_PCY_TREE_INTERNAL;
 745 }