Make X509_PUBKEY opaque
[openssl.git] / 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 }