crypto/x509/pcy_tree.c

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