1160814Ssimon/* pcy_tree.c */ 2194206Ssimon/* Written by Dr Stephen N Henson (steve@openssl.org) for the OpenSSL 3160814Ssimon * project 2004. 4160814Ssimon */ 5160814Ssimon/* ==================================================================== 6160814Ssimon * Copyright (c) 2004 The OpenSSL Project. All rights reserved. 7160814Ssimon * 8160814Ssimon * Redistribution and use in source and binary forms, with or without 9160814Ssimon * modification, are permitted provided that the following conditions 10160814Ssimon * are met: 11160814Ssimon * 12160814Ssimon * 1. Redistributions of source code must retain the above copyright 13160814Ssimon * notice, this list of conditions and the following disclaimer. 14160814Ssimon * 15160814Ssimon * 2. Redistributions in binary form must reproduce the above copyright 16160814Ssimon * notice, this list of conditions and the following disclaimer in 17160814Ssimon * the documentation and/or other materials provided with the 18160814Ssimon * distribution. 19160814Ssimon * 20160814Ssimon * 3. All advertising materials mentioning features or use of this 21160814Ssimon * software must display the following acknowledgment: 22160814Ssimon * "This product includes software developed by the OpenSSL Project 23160814Ssimon * for use in the OpenSSL Toolkit. (http://www.OpenSSL.org/)" 24160814Ssimon * 25160814Ssimon * 4. The names "OpenSSL Toolkit" and "OpenSSL Project" must not be used to 26160814Ssimon * endorse or promote products derived from this software without 27160814Ssimon * prior written permission. For written permission, please contact 28160814Ssimon * licensing@OpenSSL.org. 29160814Ssimon * 30160814Ssimon * 5. Products derived from this software may not be called "OpenSSL" 31160814Ssimon * nor may "OpenSSL" appear in their names without prior written 32160814Ssimon * permission of the OpenSSL Project. 33160814Ssimon * 34160814Ssimon * 6. Redistributions of any form whatsoever must retain the following 35160814Ssimon * acknowledgment: 36160814Ssimon * "This product includes software developed by the OpenSSL Project 37160814Ssimon * for use in the OpenSSL Toolkit (http://www.OpenSSL.org/)" 38160814Ssimon * 39160814Ssimon * THIS SOFTWARE IS PROVIDED BY THE OpenSSL PROJECT ``AS IS'' AND ANY 40160814Ssimon * EXPRESSED OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE 41160814Ssimon * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR 42160814Ssimon * PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE OpenSSL PROJECT OR 43160814Ssimon * ITS CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, 44160814Ssimon * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT 45160814Ssimon * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; 46160814Ssimon * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) 47160814Ssimon * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, 48160814Ssimon * STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) 49160814Ssimon * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED 50160814Ssimon * OF THE POSSIBILITY OF SUCH DAMAGE. 51160814Ssimon * ==================================================================== 52160814Ssimon * 53160814Ssimon * This product includes cryptographic software written by Eric Young 54160814Ssimon * (eay@cryptsoft.com). This product includes software written by Tim 55160814Ssimon * Hudson (tjh@cryptsoft.com). 56160814Ssimon * 57160814Ssimon */ 58160814Ssimon 59160814Ssimon#include "cryptlib.h" 60160814Ssimon#include <openssl/x509.h> 61160814Ssimon#include <openssl/x509v3.h> 62160814Ssimon 63160814Ssimon#include "pcy_int.h" 64160814Ssimon 65238405Sjkim/* Enable this to print out the complete policy tree at various point during 66238405Sjkim * evaluation. 67238405Sjkim */ 68238405Sjkim 69238405Sjkim/*#define OPENSSL_POLICY_DEBUG*/ 70238405Sjkim 71238405Sjkim#ifdef OPENSSL_POLICY_DEBUG 72238405Sjkim 73238405Sjkimstatic void expected_print(BIO *err, X509_POLICY_LEVEL *lev, 74238405Sjkim X509_POLICY_NODE *node, int indent) 75238405Sjkim { 76238405Sjkim if ( (lev->flags & X509_V_FLAG_INHIBIT_MAP) 77238405Sjkim || !(node->data->flags & POLICY_DATA_FLAG_MAP_MASK)) 78238405Sjkim BIO_puts(err, " Not Mapped\n"); 79238405Sjkim else 80238405Sjkim { 81238405Sjkim int i; 82238405Sjkim STACK_OF(ASN1_OBJECT) *pset = node->data->expected_policy_set; 83238405Sjkim ASN1_OBJECT *oid; 84238405Sjkim BIO_puts(err, " Expected: "); 85238405Sjkim for (i = 0; i < sk_ASN1_OBJECT_num(pset); i++) 86238405Sjkim { 87238405Sjkim oid = sk_ASN1_OBJECT_value(pset, i); 88238405Sjkim if (i) 89238405Sjkim BIO_puts(err, ", "); 90238405Sjkim i2a_ASN1_OBJECT(err, oid); 91238405Sjkim } 92238405Sjkim BIO_puts(err, "\n"); 93238405Sjkim } 94238405Sjkim } 95238405Sjkim 96238405Sjkimstatic void tree_print(char *str, X509_POLICY_TREE *tree, 97238405Sjkim X509_POLICY_LEVEL *curr) 98238405Sjkim { 99238405Sjkim X509_POLICY_LEVEL *plev; 100238405Sjkim X509_POLICY_NODE *node; 101238405Sjkim int i; 102238405Sjkim BIO *err; 103238405Sjkim err = BIO_new_fp(stderr, BIO_NOCLOSE); 104238405Sjkim if (!curr) 105238405Sjkim curr = tree->levels + tree->nlevel; 106238405Sjkim else 107238405Sjkim curr++; 108238405Sjkim BIO_printf(err, "Level print after %s\n", str); 109238405Sjkim BIO_printf(err, "Printing Up to Level %ld\n", curr - tree->levels); 110238405Sjkim for (plev = tree->levels; plev != curr; plev++) 111238405Sjkim { 112238405Sjkim BIO_printf(err, "Level %ld, flags = %x\n", 113238405Sjkim plev - tree->levels, plev->flags); 114238405Sjkim for (i = 0; i < sk_X509_POLICY_NODE_num(plev->nodes); i++) 115238405Sjkim { 116238405Sjkim node = sk_X509_POLICY_NODE_value(plev->nodes, i); 117238405Sjkim X509_POLICY_NODE_print(err, node, 2); 118238405Sjkim expected_print(err, plev, node, 2); 119238405Sjkim BIO_printf(err, " Flags: %x\n", node->data->flags); 120238405Sjkim } 121238405Sjkim if (plev->anyPolicy) 122238405Sjkim X509_POLICY_NODE_print(err, plev->anyPolicy, 2); 123238405Sjkim } 124238405Sjkim 125238405Sjkim BIO_free(err); 126238405Sjkim 127238405Sjkim } 128238405Sjkim#else 129238405Sjkim 130238405Sjkim#define tree_print(a,b,c) /* */ 131238405Sjkim 132238405Sjkim#endif 133238405Sjkim 134160814Ssimon/* Initialize policy tree. Return values: 135160814Ssimon * 0 Some internal error occured. 136160814Ssimon * -1 Inconsistent or invalid extensions in certificates. 137160814Ssimon * 1 Tree initialized OK. 138160814Ssimon * 2 Policy tree is empty. 139160814Ssimon * 5 Tree OK and requireExplicitPolicy true. 140160814Ssimon * 6 Tree empty and requireExplicitPolicy true. 141160814Ssimon */ 142160814Ssimon 143160814Ssimonstatic int tree_init(X509_POLICY_TREE **ptree, STACK_OF(X509) *certs, 144160814Ssimon unsigned int flags) 145160814Ssimon { 146160814Ssimon X509_POLICY_TREE *tree; 147160814Ssimon X509_POLICY_LEVEL *level; 148160814Ssimon const X509_POLICY_CACHE *cache; 149160814Ssimon X509_POLICY_DATA *data = NULL; 150160814Ssimon X509 *x; 151160814Ssimon int ret = 1; 152160814Ssimon int i, n; 153160814Ssimon int explicit_policy; 154160814Ssimon int any_skip; 155160814Ssimon int map_skip; 156160814Ssimon *ptree = NULL; 157160814Ssimon n = sk_X509_num(certs); 158160814Ssimon 159238405Sjkim#if 0 160160814Ssimon /* Disable policy mapping for now... */ 161160814Ssimon flags |= X509_V_FLAG_INHIBIT_MAP; 162238405Sjkim#endif 163160814Ssimon 164160814Ssimon if (flags & X509_V_FLAG_EXPLICIT_POLICY) 165160814Ssimon explicit_policy = 0; 166160814Ssimon else 167160814Ssimon explicit_policy = n + 1; 168160814Ssimon 169160814Ssimon if (flags & X509_V_FLAG_INHIBIT_ANY) 170160814Ssimon any_skip = 0; 171160814Ssimon else 172160814Ssimon any_skip = n + 1; 173160814Ssimon 174160814Ssimon if (flags & X509_V_FLAG_INHIBIT_MAP) 175160814Ssimon map_skip = 0; 176160814Ssimon else 177160814Ssimon map_skip = n + 1; 178160814Ssimon 179160814Ssimon /* Can't do anything with just a trust anchor */ 180160814Ssimon if (n == 1) 181160814Ssimon return 1; 182160814Ssimon /* First setup policy cache in all certificates apart from the 183160814Ssimon * trust anchor. Note any bad cache results on the way. Also can 184160814Ssimon * calculate explicit_policy value at this point. 185160814Ssimon */ 186160814Ssimon for (i = n - 2; i >= 0; i--) 187160814Ssimon { 188160814Ssimon x = sk_X509_value(certs, i); 189160814Ssimon X509_check_purpose(x, -1, -1); 190160814Ssimon cache = policy_cache_set(x); 191160814Ssimon /* If cache NULL something bad happened: return immediately */ 192160814Ssimon if (cache == NULL) 193160814Ssimon return 0; 194160814Ssimon /* If inconsistent extensions keep a note of it but continue */ 195160814Ssimon if (x->ex_flags & EXFLAG_INVALID_POLICY) 196160814Ssimon ret = -1; 197160814Ssimon /* Otherwise if we have no data (hence no CertificatePolicies) 198160814Ssimon * and haven't already set an inconsistent code note it. 199160814Ssimon */ 200160814Ssimon else if ((ret == 1) && !cache->data) 201160814Ssimon ret = 2; 202160814Ssimon if (explicit_policy > 0) 203160814Ssimon { 204194206Ssimon if (!(x->ex_flags & EXFLAG_SI)) 205194206Ssimon explicit_policy--; 206194206Ssimon if ((cache->explicit_skip != -1) 207160814Ssimon && (cache->explicit_skip < explicit_policy)) 208160814Ssimon explicit_policy = cache->explicit_skip; 209160814Ssimon } 210160814Ssimon } 211160814Ssimon 212160814Ssimon if (ret != 1) 213160814Ssimon { 214160814Ssimon if (ret == 2 && !explicit_policy) 215160814Ssimon return 6; 216160814Ssimon return ret; 217160814Ssimon } 218160814Ssimon 219160814Ssimon 220160814Ssimon /* If we get this far initialize the tree */ 221160814Ssimon 222160814Ssimon tree = OPENSSL_malloc(sizeof(X509_POLICY_TREE)); 223160814Ssimon 224160814Ssimon if (!tree) 225160814Ssimon return 0; 226160814Ssimon 227160814Ssimon tree->flags = 0; 228160814Ssimon tree->levels = OPENSSL_malloc(sizeof(X509_POLICY_LEVEL) * n); 229160814Ssimon tree->nlevel = 0; 230160814Ssimon tree->extra_data = NULL; 231160814Ssimon tree->auth_policies = NULL; 232160814Ssimon tree->user_policies = NULL; 233160814Ssimon 234205128Ssimon if (!tree->levels) 235160814Ssimon { 236160814Ssimon OPENSSL_free(tree); 237160814Ssimon return 0; 238160814Ssimon } 239160814Ssimon 240160814Ssimon memset(tree->levels, 0, n * sizeof(X509_POLICY_LEVEL)); 241160814Ssimon 242160814Ssimon tree->nlevel = n; 243160814Ssimon 244160814Ssimon level = tree->levels; 245160814Ssimon 246160814Ssimon /* Root data: initialize to anyPolicy */ 247160814Ssimon 248160814Ssimon data = policy_data_new(NULL, OBJ_nid2obj(NID_any_policy), 0); 249160814Ssimon 250160814Ssimon if (!data || !level_add_node(level, data, NULL, tree)) 251160814Ssimon goto bad_tree; 252160814Ssimon 253160814Ssimon for (i = n - 2; i >= 0; i--) 254160814Ssimon { 255160814Ssimon level++; 256160814Ssimon x = sk_X509_value(certs, i); 257160814Ssimon cache = policy_cache_set(x); 258160814Ssimon CRYPTO_add(&x->references, 1, CRYPTO_LOCK_X509); 259160814Ssimon level->cert = x; 260160814Ssimon 261160814Ssimon if (!cache->anyPolicy) 262160814Ssimon level->flags |= X509_V_FLAG_INHIBIT_ANY; 263160814Ssimon 264160814Ssimon /* Determine inhibit any and inhibit map flags */ 265160814Ssimon if (any_skip == 0) 266160814Ssimon { 267160814Ssimon /* Any matching allowed if certificate is self 268160814Ssimon * issued and not the last in the chain. 269160814Ssimon */ 270194206Ssimon if (!(x->ex_flags & EXFLAG_SI) || (i == 0)) 271160814Ssimon level->flags |= X509_V_FLAG_INHIBIT_ANY; 272160814Ssimon } 273160814Ssimon else 274160814Ssimon { 275194206Ssimon if (!(x->ex_flags & EXFLAG_SI)) 276194206Ssimon any_skip--; 277194206Ssimon if ((cache->any_skip >= 0) 278160814Ssimon && (cache->any_skip < any_skip)) 279160814Ssimon any_skip = cache->any_skip; 280160814Ssimon } 281160814Ssimon 282160814Ssimon if (map_skip == 0) 283160814Ssimon level->flags |= X509_V_FLAG_INHIBIT_MAP; 284160814Ssimon else 285160814Ssimon { 286238405Sjkim if (!(x->ex_flags & EXFLAG_SI)) 287238405Sjkim map_skip--; 288194206Ssimon if ((cache->map_skip >= 0) 289160814Ssimon && (cache->map_skip < map_skip)) 290160814Ssimon map_skip = cache->map_skip; 291160814Ssimon } 292160814Ssimon 293160814Ssimon } 294160814Ssimon 295160814Ssimon *ptree = tree; 296160814Ssimon 297160814Ssimon if (explicit_policy) 298160814Ssimon return 1; 299160814Ssimon else 300160814Ssimon return 5; 301160814Ssimon 302160814Ssimon bad_tree: 303160814Ssimon 304160814Ssimon X509_policy_tree_free(tree); 305160814Ssimon 306160814Ssimon return 0; 307160814Ssimon 308160814Ssimon } 309160814Ssimon 310238405Sjkimstatic int tree_link_matching_nodes(X509_POLICY_LEVEL *curr, 311238405Sjkim const X509_POLICY_DATA *data) 312238405Sjkim { 313238405Sjkim X509_POLICY_LEVEL *last = curr - 1; 314238405Sjkim X509_POLICY_NODE *node; 315238405Sjkim int i, matched = 0; 316238405Sjkim /* Iterate through all in nodes linking matches */ 317238405Sjkim for (i = 0; i < sk_X509_POLICY_NODE_num(last->nodes); i++) 318238405Sjkim { 319238405Sjkim node = sk_X509_POLICY_NODE_value(last->nodes, i); 320238405Sjkim if (policy_node_match(last, node, data->valid_policy)) 321238405Sjkim { 322238405Sjkim if (!level_add_node(curr, data, node, NULL)) 323238405Sjkim return 0; 324238405Sjkim matched = 1; 325238405Sjkim } 326238405Sjkim } 327238405Sjkim if (!matched && last->anyPolicy) 328238405Sjkim { 329238405Sjkim if (!level_add_node(curr, data, last->anyPolicy, NULL)) 330238405Sjkim return 0; 331238405Sjkim } 332238405Sjkim return 1; 333238405Sjkim } 334238405Sjkim 335238405Sjkim/* This corresponds to RFC3280 6.1.3(d)(1): 336160814Ssimon * link any data from CertificatePolicies onto matching parent 337160814Ssimon * or anyPolicy if no match. 338160814Ssimon */ 339160814Ssimon 340160814Ssimonstatic int tree_link_nodes(X509_POLICY_LEVEL *curr, 341160814Ssimon const X509_POLICY_CACHE *cache) 342160814Ssimon { 343160814Ssimon int i; 344160814Ssimon X509_POLICY_DATA *data; 345238405Sjkim 346160814Ssimon for (i = 0; i < sk_X509_POLICY_DATA_num(cache->data); i++) 347160814Ssimon { 348160814Ssimon data = sk_X509_POLICY_DATA_value(cache->data, i); 349160814Ssimon /* If a node is mapped any it doesn't have a corresponding 350160814Ssimon * CertificatePolicies entry. 351160814Ssimon * However such an identical node would be created 352160814Ssimon * if anyPolicy matching is enabled because there would be 353160814Ssimon * no match with the parent valid_policy_set. So we create 354160814Ssimon * link because then it will have the mapping flags 355160814Ssimon * right and we can prune it later. 356160814Ssimon */ 357238405Sjkim#if 0 358160814Ssimon if ((data->flags & POLICY_DATA_FLAG_MAPPED_ANY) 359160814Ssimon && !(curr->flags & X509_V_FLAG_INHIBIT_ANY)) 360160814Ssimon continue; 361238405Sjkim#endif 362238405Sjkim /* Look for matching nodes in previous level */ 363238405Sjkim if (!tree_link_matching_nodes(curr, data)) 364160814Ssimon return 0; 365160814Ssimon } 366160814Ssimon return 1; 367160814Ssimon } 368160814Ssimon 369238405Sjkim/* This corresponds to RFC3280 6.1.3(d)(2): 370160814Ssimon * Create new data for any unmatched policies in the parent and link 371160814Ssimon * to anyPolicy. 372160814Ssimon */ 373160814Ssimon 374238405Sjkimstatic int tree_add_unmatched(X509_POLICY_LEVEL *curr, 375238405Sjkim const X509_POLICY_CACHE *cache, 376238405Sjkim const ASN1_OBJECT *id, 377238405Sjkim X509_POLICY_NODE *node, 378238405Sjkim X509_POLICY_TREE *tree) 379238405Sjkim { 380238405Sjkim X509_POLICY_DATA *data; 381238405Sjkim if (id == NULL) 382238405Sjkim id = node->data->valid_policy; 383238405Sjkim /* Create a new node with qualifiers from anyPolicy and 384238405Sjkim * id from unmatched node. 385238405Sjkim */ 386238405Sjkim data = policy_data_new(NULL, id, node_critical(node)); 387238405Sjkim 388238405Sjkim if (data == NULL) 389238405Sjkim return 0; 390238405Sjkim /* Curr may not have anyPolicy */ 391238405Sjkim data->qualifier_set = cache->anyPolicy->qualifier_set; 392238405Sjkim data->flags |= POLICY_DATA_FLAG_SHARED_QUALIFIERS; 393238405Sjkim if (!level_add_node(curr, data, node, tree)) 394238405Sjkim { 395238405Sjkim policy_data_free(data); 396238405Sjkim return 0; 397238405Sjkim } 398238405Sjkim 399238405Sjkim return 1; 400238405Sjkim } 401238405Sjkim 402238405Sjkimstatic int tree_link_unmatched(X509_POLICY_LEVEL *curr, 403238405Sjkim const X509_POLICY_CACHE *cache, 404238405Sjkim X509_POLICY_NODE *node, 405238405Sjkim X509_POLICY_TREE *tree) 406238405Sjkim { 407238405Sjkim const X509_POLICY_LEVEL *last = curr - 1; 408238405Sjkim int i; 409238405Sjkim 410238405Sjkim if ( (last->flags & X509_V_FLAG_INHIBIT_MAP) 411238405Sjkim || !(node->data->flags & POLICY_DATA_FLAG_MAPPED)) 412238405Sjkim { 413238405Sjkim /* If no policy mapping: matched if one child present */ 414238405Sjkim if (node->nchild) 415238405Sjkim return 1; 416238405Sjkim if (!tree_add_unmatched(curr, cache, NULL, node, tree)) 417238405Sjkim return 0; 418238405Sjkim /* Add it */ 419238405Sjkim } 420238405Sjkim else 421238405Sjkim { 422238405Sjkim /* If mapping: matched if one child per expected policy set */ 423238405Sjkim STACK_OF(ASN1_OBJECT) *expset = node->data->expected_policy_set; 424238405Sjkim if (node->nchild == sk_ASN1_OBJECT_num(expset)) 425238405Sjkim return 1; 426238405Sjkim /* Locate unmatched nodes */ 427238405Sjkim for (i = 0; i < sk_ASN1_OBJECT_num(expset); i++) 428238405Sjkim { 429238405Sjkim ASN1_OBJECT *oid = sk_ASN1_OBJECT_value(expset, i); 430238405Sjkim if (level_find_node(curr, node, oid)) 431238405Sjkim continue; 432238405Sjkim if (!tree_add_unmatched(curr, cache, oid, node, tree)) 433238405Sjkim return 0; 434238405Sjkim } 435238405Sjkim 436238405Sjkim } 437238405Sjkim 438238405Sjkim return 1; 439238405Sjkim 440238405Sjkim } 441238405Sjkim 442160814Ssimonstatic int tree_link_any(X509_POLICY_LEVEL *curr, 443160814Ssimon const X509_POLICY_CACHE *cache, 444160814Ssimon X509_POLICY_TREE *tree) 445160814Ssimon { 446160814Ssimon int i; 447238405Sjkim /*X509_POLICY_DATA *data;*/ 448160814Ssimon X509_POLICY_NODE *node; 449238405Sjkim X509_POLICY_LEVEL *last = curr - 1; 450160814Ssimon 451160814Ssimon for (i = 0; i < sk_X509_POLICY_NODE_num(last->nodes); i++) 452160814Ssimon { 453160814Ssimon node = sk_X509_POLICY_NODE_value(last->nodes, i); 454160814Ssimon 455238405Sjkim if (!tree_link_unmatched(curr, cache, node, tree)) 456238405Sjkim return 0; 457238405Sjkim 458238405Sjkim#if 0 459238405Sjkim 460160814Ssimon /* Skip any node with any children: we only want unmathced 461160814Ssimon * nodes. 462160814Ssimon * 463160814Ssimon * Note: need something better for policy mapping 464160814Ssimon * because each node may have multiple children 465160814Ssimon */ 466160814Ssimon if (node->nchild) 467160814Ssimon continue; 468238405Sjkim 469160814Ssimon /* Create a new node with qualifiers from anyPolicy and 470160814Ssimon * id from unmatched node. 471160814Ssimon */ 472160814Ssimon data = policy_data_new(NULL, node->data->valid_policy, 473160814Ssimon node_critical(node)); 474160814Ssimon 475160814Ssimon if (data == NULL) 476160814Ssimon return 0; 477194206Ssimon /* Curr may not have anyPolicy */ 478194206Ssimon data->qualifier_set = cache->anyPolicy->qualifier_set; 479160814Ssimon data->flags |= POLICY_DATA_FLAG_SHARED_QUALIFIERS; 480160814Ssimon if (!level_add_node(curr, data, node, tree)) 481160814Ssimon { 482160814Ssimon policy_data_free(data); 483160814Ssimon return 0; 484160814Ssimon } 485238405Sjkim 486238405Sjkim#endif 487238405Sjkim 488160814Ssimon } 489160814Ssimon /* Finally add link to anyPolicy */ 490160814Ssimon if (last->anyPolicy) 491160814Ssimon { 492160814Ssimon if (!level_add_node(curr, cache->anyPolicy, 493160814Ssimon last->anyPolicy, NULL)) 494160814Ssimon return 0; 495160814Ssimon } 496160814Ssimon return 1; 497160814Ssimon } 498160814Ssimon 499160814Ssimon/* Prune the tree: delete any child mapped child data on the current level 500160814Ssimon * then proceed up the tree deleting any data with no children. If we ever 501160814Ssimon * have no data on a level we can halt because the tree will be empty. 502160814Ssimon */ 503160814Ssimon 504160814Ssimonstatic int tree_prune(X509_POLICY_TREE *tree, X509_POLICY_LEVEL *curr) 505160814Ssimon { 506238405Sjkim STACK_OF(X509_POLICY_NODE) *nodes; 507160814Ssimon X509_POLICY_NODE *node; 508160814Ssimon int i; 509238405Sjkim nodes = curr->nodes; 510238405Sjkim if (curr->flags & X509_V_FLAG_INHIBIT_MAP) 511160814Ssimon { 512238405Sjkim for (i = sk_X509_POLICY_NODE_num(nodes) - 1; i >= 0; i--) 513160814Ssimon { 514238405Sjkim node = sk_X509_POLICY_NODE_value(nodes, i); 515238405Sjkim /* Delete any mapped data: see RFC3280 XXXX */ 516238405Sjkim if (node->data->flags & POLICY_DATA_FLAG_MAP_MASK) 517238405Sjkim { 518238405Sjkim node->parent->nchild--; 519238405Sjkim OPENSSL_free(node); 520238405Sjkim (void)sk_X509_POLICY_NODE_delete(nodes,i); 521238405Sjkim } 522160814Ssimon } 523160814Ssimon } 524160814Ssimon 525160814Ssimon for(;;) { 526160814Ssimon --curr; 527238405Sjkim nodes = curr->nodes; 528238405Sjkim for (i = sk_X509_POLICY_NODE_num(nodes) - 1; i >= 0; i--) 529160814Ssimon { 530238405Sjkim node = sk_X509_POLICY_NODE_value(nodes, i); 531160814Ssimon if (node->nchild == 0) 532160814Ssimon { 533160814Ssimon node->parent->nchild--; 534160814Ssimon OPENSSL_free(node); 535238405Sjkim (void)sk_X509_POLICY_NODE_delete(nodes, i); 536160814Ssimon } 537160814Ssimon } 538160814Ssimon if (curr->anyPolicy && !curr->anyPolicy->nchild) 539160814Ssimon { 540160814Ssimon if (curr->anyPolicy->parent) 541160814Ssimon curr->anyPolicy->parent->nchild--; 542160814Ssimon OPENSSL_free(curr->anyPolicy); 543160814Ssimon curr->anyPolicy = NULL; 544160814Ssimon } 545160814Ssimon if (curr == tree->levels) 546160814Ssimon { 547160814Ssimon /* If we zapped anyPolicy at top then tree is empty */ 548160814Ssimon if (!curr->anyPolicy) 549160814Ssimon return 2; 550160814Ssimon return 1; 551160814Ssimon } 552160814Ssimon } 553160814Ssimon 554160814Ssimon return 1; 555160814Ssimon 556160814Ssimon } 557160814Ssimon 558160814Ssimonstatic int tree_add_auth_node(STACK_OF(X509_POLICY_NODE) **pnodes, 559160814Ssimon X509_POLICY_NODE *pcy) 560160814Ssimon { 561160814Ssimon if (!*pnodes) 562160814Ssimon { 563160814Ssimon *pnodes = policy_node_cmp_new(); 564160814Ssimon if (!*pnodes) 565160814Ssimon return 0; 566160814Ssimon } 567160814Ssimon else if (sk_X509_POLICY_NODE_find(*pnodes, pcy) != -1) 568160814Ssimon return 1; 569160814Ssimon 570160814Ssimon if (!sk_X509_POLICY_NODE_push(*pnodes, pcy)) 571160814Ssimon return 0; 572160814Ssimon 573160814Ssimon return 1; 574160814Ssimon 575160814Ssimon } 576160814Ssimon 577160814Ssimon/* Calculate the authority set based on policy tree. 578160814Ssimon * The 'pnodes' parameter is used as a store for the set of policy nodes 579160814Ssimon * used to calculate the user set. If the authority set is not anyPolicy 580160814Ssimon * then pnodes will just point to the authority set. If however the authority 581160814Ssimon * set is anyPolicy then the set of valid policies (other than anyPolicy) 582160814Ssimon * is store in pnodes. The return value of '2' is used in this case to indicate 583160814Ssimon * that pnodes should be freed. 584160814Ssimon */ 585160814Ssimon 586160814Ssimonstatic int tree_calculate_authority_set(X509_POLICY_TREE *tree, 587160814Ssimon STACK_OF(X509_POLICY_NODE) **pnodes) 588160814Ssimon { 589160814Ssimon X509_POLICY_LEVEL *curr; 590160814Ssimon X509_POLICY_NODE *node, *anyptr; 591160814Ssimon STACK_OF(X509_POLICY_NODE) **addnodes; 592160814Ssimon int i, j; 593160814Ssimon curr = tree->levels + tree->nlevel - 1; 594160814Ssimon 595160814Ssimon /* If last level contains anyPolicy set is anyPolicy */ 596160814Ssimon if (curr->anyPolicy) 597160814Ssimon { 598160814Ssimon if (!tree_add_auth_node(&tree->auth_policies, curr->anyPolicy)) 599160814Ssimon return 0; 600160814Ssimon addnodes = pnodes; 601160814Ssimon } 602160814Ssimon else 603160814Ssimon /* Add policies to authority set */ 604160814Ssimon addnodes = &tree->auth_policies; 605160814Ssimon 606160814Ssimon curr = tree->levels; 607160814Ssimon for (i = 1; i < tree->nlevel; i++) 608160814Ssimon { 609160814Ssimon /* If no anyPolicy node on this this level it can't 610160814Ssimon * appear on lower levels so end search. 611160814Ssimon */ 612160814Ssimon if (!(anyptr = curr->anyPolicy)) 613160814Ssimon break; 614160814Ssimon curr++; 615160814Ssimon for (j = 0; j < sk_X509_POLICY_NODE_num(curr->nodes); j++) 616160814Ssimon { 617160814Ssimon node = sk_X509_POLICY_NODE_value(curr->nodes, j); 618160814Ssimon if ((node->parent == anyptr) 619160814Ssimon && !tree_add_auth_node(addnodes, node)) 620160814Ssimon return 0; 621160814Ssimon } 622160814Ssimon } 623160814Ssimon 624160814Ssimon if (addnodes == pnodes) 625160814Ssimon return 2; 626160814Ssimon 627160814Ssimon *pnodes = tree->auth_policies; 628160814Ssimon 629160814Ssimon return 1; 630160814Ssimon } 631160814Ssimon 632160814Ssimonstatic int tree_calculate_user_set(X509_POLICY_TREE *tree, 633160814Ssimon STACK_OF(ASN1_OBJECT) *policy_oids, 634160814Ssimon STACK_OF(X509_POLICY_NODE) *auth_nodes) 635160814Ssimon { 636160814Ssimon int i; 637160814Ssimon X509_POLICY_NODE *node; 638160814Ssimon ASN1_OBJECT *oid; 639160814Ssimon 640160814Ssimon X509_POLICY_NODE *anyPolicy; 641160814Ssimon X509_POLICY_DATA *extra; 642160814Ssimon 643160814Ssimon /* Check if anyPolicy present in authority constrained policy set: 644160814Ssimon * this will happen if it is a leaf node. 645160814Ssimon */ 646160814Ssimon 647160814Ssimon if (sk_ASN1_OBJECT_num(policy_oids) <= 0) 648160814Ssimon return 1; 649160814Ssimon 650160814Ssimon anyPolicy = tree->levels[tree->nlevel - 1].anyPolicy; 651160814Ssimon 652160814Ssimon for (i = 0; i < sk_ASN1_OBJECT_num(policy_oids); i++) 653160814Ssimon { 654160814Ssimon oid = sk_ASN1_OBJECT_value(policy_oids, i); 655160814Ssimon if (OBJ_obj2nid(oid) == NID_any_policy) 656160814Ssimon { 657160814Ssimon tree->flags |= POLICY_FLAG_ANY_POLICY; 658160814Ssimon return 1; 659160814Ssimon } 660160814Ssimon } 661160814Ssimon 662160814Ssimon for (i = 0; i < sk_ASN1_OBJECT_num(policy_oids); i++) 663160814Ssimon { 664160814Ssimon oid = sk_ASN1_OBJECT_value(policy_oids, i); 665160814Ssimon node = tree_find_sk(auth_nodes, oid); 666160814Ssimon if (!node) 667160814Ssimon { 668160814Ssimon if (!anyPolicy) 669160814Ssimon continue; 670160814Ssimon /* Create a new node with policy ID from user set 671160814Ssimon * and qualifiers from anyPolicy. 672160814Ssimon */ 673160814Ssimon extra = policy_data_new(NULL, oid, 674160814Ssimon node_critical(anyPolicy)); 675160814Ssimon if (!extra) 676160814Ssimon return 0; 677160814Ssimon extra->qualifier_set = anyPolicy->data->qualifier_set; 678160814Ssimon extra->flags = POLICY_DATA_FLAG_SHARED_QUALIFIERS 679160814Ssimon | POLICY_DATA_FLAG_EXTRA_NODE; 680160814Ssimon node = level_add_node(NULL, extra, anyPolicy->parent, 681160814Ssimon tree); 682160814Ssimon } 683160814Ssimon if (!tree->user_policies) 684160814Ssimon { 685160814Ssimon tree->user_policies = sk_X509_POLICY_NODE_new_null(); 686160814Ssimon if (!tree->user_policies) 687160814Ssimon return 1; 688160814Ssimon } 689160814Ssimon if (!sk_X509_POLICY_NODE_push(tree->user_policies, node)) 690160814Ssimon return 0; 691160814Ssimon } 692160814Ssimon return 1; 693160814Ssimon 694160814Ssimon } 695160814Ssimon 696160814Ssimonstatic int tree_evaluate(X509_POLICY_TREE *tree) 697160814Ssimon { 698160814Ssimon int ret, i; 699160814Ssimon X509_POLICY_LEVEL *curr = tree->levels + 1; 700160814Ssimon const X509_POLICY_CACHE *cache; 701160814Ssimon 702160814Ssimon for(i = 1; i < tree->nlevel; i++, curr++) 703160814Ssimon { 704160814Ssimon cache = policy_cache_set(curr->cert); 705160814Ssimon if (!tree_link_nodes(curr, cache)) 706160814Ssimon return 0; 707160814Ssimon 708160814Ssimon if (!(curr->flags & X509_V_FLAG_INHIBIT_ANY) 709160814Ssimon && !tree_link_any(curr, cache, tree)) 710160814Ssimon return 0; 711238405Sjkim tree_print("before tree_prune()", tree, curr); 712160814Ssimon ret = tree_prune(tree, curr); 713160814Ssimon if (ret != 1) 714160814Ssimon return ret; 715160814Ssimon } 716160814Ssimon 717160814Ssimon return 1; 718160814Ssimon 719160814Ssimon } 720160814Ssimon 721160814Ssimonstatic void exnode_free(X509_POLICY_NODE *node) 722160814Ssimon { 723160814Ssimon if (node->data && (node->data->flags & POLICY_DATA_FLAG_EXTRA_NODE)) 724160814Ssimon OPENSSL_free(node); 725160814Ssimon } 726160814Ssimon 727160814Ssimon 728160814Ssimonvoid X509_policy_tree_free(X509_POLICY_TREE *tree) 729160814Ssimon { 730160814Ssimon X509_POLICY_LEVEL *curr; 731160814Ssimon int i; 732160814Ssimon 733160814Ssimon if (!tree) 734160814Ssimon return; 735160814Ssimon 736160814Ssimon sk_X509_POLICY_NODE_free(tree->auth_policies); 737160814Ssimon sk_X509_POLICY_NODE_pop_free(tree->user_policies, exnode_free); 738160814Ssimon 739160814Ssimon for(i = 0, curr = tree->levels; i < tree->nlevel; i++, curr++) 740160814Ssimon { 741160814Ssimon if (curr->cert) 742160814Ssimon X509_free(curr->cert); 743160814Ssimon if (curr->nodes) 744160814Ssimon sk_X509_POLICY_NODE_pop_free(curr->nodes, 745160814Ssimon policy_node_free); 746160814Ssimon if (curr->anyPolicy) 747160814Ssimon policy_node_free(curr->anyPolicy); 748160814Ssimon } 749160814Ssimon 750160814Ssimon if (tree->extra_data) 751160814Ssimon sk_X509_POLICY_DATA_pop_free(tree->extra_data, 752160814Ssimon policy_data_free); 753160814Ssimon 754160814Ssimon OPENSSL_free(tree->levels); 755160814Ssimon OPENSSL_free(tree); 756160814Ssimon 757160814Ssimon } 758160814Ssimon 759160814Ssimon/* Application policy checking function. 760160814Ssimon * Return codes: 761160814Ssimon * 0 Internal Error. 762160814Ssimon * 1 Successful. 763160814Ssimon * -1 One or more certificates contain invalid or inconsistent extensions 764160814Ssimon * -2 User constrained policy set empty and requireExplicit true. 765160814Ssimon */ 766160814Ssimon 767160814Ssimonint X509_policy_check(X509_POLICY_TREE **ptree, int *pexplicit_policy, 768160814Ssimon STACK_OF(X509) *certs, 769160814Ssimon STACK_OF(ASN1_OBJECT) *policy_oids, 770160814Ssimon unsigned int flags) 771160814Ssimon { 772160814Ssimon int ret; 773160814Ssimon X509_POLICY_TREE *tree = NULL; 774160814Ssimon STACK_OF(X509_POLICY_NODE) *nodes, *auth_nodes = NULL; 775160814Ssimon *ptree = NULL; 776160814Ssimon 777160814Ssimon *pexplicit_policy = 0; 778160814Ssimon ret = tree_init(&tree, certs, flags); 779160814Ssimon 780160814Ssimon switch (ret) 781160814Ssimon { 782160814Ssimon 783160814Ssimon /* Tree empty requireExplicit False: OK */ 784160814Ssimon case 2: 785160814Ssimon return 1; 786160814Ssimon 787238405Sjkim /* Some internal error */ 788234954Sbz case -1: 789234954Sbz return -1; 790234954Sbz 791160814Ssimon /* Some internal error */ 792160814Ssimon case 0: 793160814Ssimon return 0; 794160814Ssimon 795160814Ssimon /* Tree empty requireExplicit True: Error */ 796160814Ssimon 797160814Ssimon case 6: 798160814Ssimon *pexplicit_policy = 1; 799160814Ssimon return -2; 800160814Ssimon 801160814Ssimon /* Tree OK requireExplicit True: OK and continue */ 802160814Ssimon case 5: 803160814Ssimon *pexplicit_policy = 1; 804160814Ssimon break; 805160814Ssimon 806160814Ssimon /* Tree OK: continue */ 807160814Ssimon 808160814Ssimon case 1: 809167612Ssimon if (!tree) 810167612Ssimon /* 811167612Ssimon * tree_init() returns success and a null tree 812167612Ssimon * if it's just looking at a trust anchor. 813167612Ssimon * I'm not sure that returning success here is 814167612Ssimon * correct, but I'm sure that reporting this 815167612Ssimon * as an internal error which our caller 816167612Ssimon * interprets as a malloc failure is wrong. 817167612Ssimon */ 818167612Ssimon return 1; 819160814Ssimon break; 820160814Ssimon } 821160814Ssimon 822160814Ssimon if (!tree) goto error; 823160814Ssimon ret = tree_evaluate(tree); 824160814Ssimon 825238405Sjkim tree_print("tree_evaluate()", tree, NULL); 826238405Sjkim 827160814Ssimon if (ret <= 0) 828160814Ssimon goto error; 829160814Ssimon 830160814Ssimon /* Return value 2 means tree empty */ 831160814Ssimon if (ret == 2) 832160814Ssimon { 833160814Ssimon X509_policy_tree_free(tree); 834160814Ssimon if (*pexplicit_policy) 835160814Ssimon return -2; 836160814Ssimon else 837160814Ssimon return 1; 838160814Ssimon } 839160814Ssimon 840160814Ssimon /* Tree is not empty: continue */ 841160814Ssimon 842160814Ssimon ret = tree_calculate_authority_set(tree, &auth_nodes); 843160814Ssimon 844160814Ssimon if (!ret) 845160814Ssimon goto error; 846160814Ssimon 847160814Ssimon if (!tree_calculate_user_set(tree, policy_oids, auth_nodes)) 848160814Ssimon goto error; 849160814Ssimon 850160814Ssimon if (ret == 2) 851160814Ssimon sk_X509_POLICY_NODE_free(auth_nodes); 852160814Ssimon 853160814Ssimon if (tree) 854160814Ssimon *ptree = tree; 855160814Ssimon 856160814Ssimon if (*pexplicit_policy) 857160814Ssimon { 858160814Ssimon nodes = X509_policy_tree_get0_user_policies(tree); 859160814Ssimon if (sk_X509_POLICY_NODE_num(nodes) <= 0) 860160814Ssimon return -2; 861160814Ssimon } 862160814Ssimon 863160814Ssimon return 1; 864160814Ssimon 865160814Ssimon error: 866160814Ssimon 867160814Ssimon X509_policy_tree_free(tree); 868160814Ssimon 869160814Ssimon return 0; 870160814Ssimon 871160814Ssimon } 872238405Sjkim 873