/* $OpenBSD: pcy_tree.c,v 1.2 2021/11/01 20:53:08 tb Exp $ */

/* Written by Dr Stephen N Henson (steve@openssl.org) for the OpenSSL

 * project 2004.

 */

/* ====================================================================

 * Copyright (c) 2004 The OpenSSL Project.  All rights reserved.

 *

 * Redistribution and use in source and binary forms, with or without

 * modification, are permitted provided that the following conditions

 * are met:

 *

 * 1. Redistributions of source code must retain the above copyright

 *    notice, this list of conditions and the following disclaimer.

 *

 * 2. Redistributions in binary form must reproduce the above copyright

 *    notice, this list of conditions and the following disclaimer in

 *    the documentation and/or other materials provided with the

 *    distribution.

 *

 * 3. All advertising materials mentioning features or use of this

 *    software must display the following acknowledgment:

 *    "This product includes software developed by the OpenSSL Project

 *    for use in the OpenSSL Toolkit. (http://www.OpenSSL.org/)"

 *

 * 4. The names "OpenSSL Toolkit" and "OpenSSL Project" must not be used to

 *    endorse or promote products derived from this software without

 *    prior written permission. For written permission, please contact

 *    licensing@OpenSSL.org.

 *

 * 5. Products derived from this software may not be called "OpenSSL"

 *    nor may "OpenSSL" appear in their names without prior written

 *    permission of the OpenSSL Project.

 *

 * 6. Redistributions of any form whatsoever must retain the following

 *    acknowledgment:

 *    "This product includes software developed by the OpenSSL Project

 *    for use in the OpenSSL Toolkit (http://www.OpenSSL.org/)"

 *

 * THIS SOFTWARE IS PROVIDED BY THE OpenSSL PROJECT ``AS IS'' AND ANY

 * EXPRESSED OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE

 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR

 * PURPOSE ARE DISCLAIMED.  IN NO EVENT SHALL THE OpenSSL PROJECT OR

 * ITS CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,

 * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT

 * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;

 * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)

 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT,

 * STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)

 * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED

 * OF THE POSSIBILITY OF SUCH DAMAGE.

 * ====================================================================

 *

 * This product includes cryptographic software written by Eric Young

 * (eay@cryptsoft.com).  This product includes software written by Tim

 * Hudson (tjh@cryptsoft.com).

 *

 */

#include <openssl/x509.h>

#include <openssl/x509v3.h>

#include "pcy_int.h"

#include "x509_lcl.h"

/* Enable this to print out the complete policy tree at various point during

 * evaluation.

 */

/*#define OPENSSL_POLICY_DEBUG*/

#ifdef OPENSSL_POLICY_DEBUG

static void

expected_print(BIO *err, X509_POLICY_LEVEL *lev, X509_POLICY_NODE *node,

    int indent)

{

  if ((lev->flags & X509_V_FLAG_INHIBIT_MAP) ||

      !(node->data->flags & POLICY_DATA_FLAG_MAP_MASK))

    BIO_puts(err, "  Not Mapped\n");

  else {

    int i;

    STACK_OF(ASN1_OBJECT) *pset = node->data->expected_policy_set;

    ASN1_OBJECT *oid;

    BIO_puts(err, "  Expected: ");

    for (i = 0; i < sk_ASN1_OBJECT_num(pset); i++) {

      oid = sk_ASN1_OBJECT_value(pset, i);

      if (i)

        BIO_puts(err, ", ");

      i2a_ASN1_OBJECT(err, oid);

    }

    BIO_puts(err, "\n");

  }

}

static void

tree_print(char *str, X509_POLICY_TREE *tree, X509_POLICY_LEVEL *curr)

{

  X509_POLICY_LEVEL *plev;

  X509_POLICY_NODE *node;

  int i;

  BIO *err;

  if ((err = BIO_new_fp(stderr, BIO_NOCLOSE)) == NULL)

    return;

  if (!curr)

    curr = tree->levels + tree->nlevel;

  else

    curr++;

  BIO_printf(err, "Level print after %s\n", str);

  BIO_printf(err, "Printing Up to Level %ld\n", curr - tree->levels);

  for (plev = tree->levels; plev != curr; plev++) {

    BIO_printf(err, "Level %ld, flags = %x\n",

        plev - tree->levels, plev->flags);

    for (i = 0; i < sk_X509_POLICY_NODE_num(plev->nodes); i++) {

      node = sk_X509_POLICY_NODE_value(plev->nodes, i);

      X509_POLICY_NODE_print(err, node, 2);

      expected_print(err, plev, node, 2);

      BIO_printf(err, "  Flags: %x\n", node->data->flags);

    }

    if (plev->anyPolicy)

      X509_POLICY_NODE_print(err, plev->anyPolicy, 2);

  }

  BIO_free(err);

}

#else

#define tree_print(a,b,c) /* */

#endif

/* Initialize policy tree. Return values:

 *  0 Some internal error occured.

 * -1 Inconsistent or invalid extensions in certificates.

 *  1 Tree initialized OK.

 *  2 Policy tree is empty.

 *  5 Tree OK and requireExplicitPolicy true.

 *  6 Tree empty and requireExplicitPolicy true.

 */

static int

tree_init(X509_POLICY_TREE **ptree, STACK_OF(X509) *certs, unsigned int flags)

{

  X509_POLICY_TREE *tree;

  X509_POLICY_LEVEL *level;

  const X509_POLICY_CACHE *cache;

  X509_POLICY_DATA *data = NULL;

  X509 *x;

  int ret = 1;

  int i, n;

  int explicit_policy;

  int any_skip;

  int map_skip;

  *ptree = NULL;

  n = sk_X509_num(certs);

  if (flags & X509_V_FLAG_EXPLICIT_POLICY)

    explicit_policy = 0;

  else

    explicit_policy = n + 1;

  if (flags & X509_V_FLAG_INHIBIT_ANY)

    any_skip = 0;

  else

    any_skip = n + 1;

  if (flags & X509_V_FLAG_INHIBIT_MAP)

    map_skip = 0;

  else

    map_skip = n + 1;

  /* Can't do anything with just a trust anchor */

  if (n == 1)

    return 1;

  /* First setup policy cache in all certificates apart from the

   * trust anchor. Note any bad cache results on the way. Also can

   * calculate explicit_policy value at this point.

   */

  for (i = n - 2; i >= 0; i--) {

    x = sk_X509_value(certs, i);

    X509_check_purpose(x, -1, -1);

    cache = policy_cache_set(x);

    /* If cache NULL something bad happened: return immediately */

    if (cache == NULL)

      return 0;

    /* If inconsistent extensions keep a note of it but continue */

    if (x->ex_flags & EXFLAG_INVALID_POLICY)

      ret = -1;

    /* Otherwise if we have no data (hence no CertificatePolicies)

     * and haven't already set an inconsistent code note it.

     */

    else if ((ret == 1) && !cache->data)

      ret = 2;

    if (explicit_policy > 0) {

      if (!(x->ex_flags & EXFLAG_SI))

        explicit_policy--;

      if ((cache->explicit_skip != -1) &&

          (cache->explicit_skip < explicit_policy))

        explicit_policy = cache->explicit_skip;

    }

  }

  if (ret != 1) {

    if (ret == 2 && !explicit_policy)

      return 6;

    return ret;

  }

  /* If we get this far initialize the tree */

  tree = malloc(sizeof(X509_POLICY_TREE));

  if (!tree)

    return 0;

  tree->flags = 0;

  tree->levels = calloc(n, sizeof(X509_POLICY_LEVEL));

  tree->nlevel = 0;

  tree->extra_data = NULL;

  tree->auth_policies = NULL;

  tree->user_policies = NULL;

  if (!tree->levels) {

    free(tree);

    return 0;

  }

  tree->nlevel = n;

  level = tree->levels;

  /* Root data: initialize to anyPolicy */

  data = policy_data_new(NULL, OBJ_nid2obj(NID_any_policy), 0);

  if (!data || !level_add_node(level, data, NULL, tree, NULL))

    goto bad_tree;

  for (i = n - 2; i >= 0; i--) {

    level++;

    x = sk_X509_value(certs, i);

    cache = policy_cache_set(x);

    CRYPTO_add(&x->references, 1, CRYPTO_LOCK_X509);

    level->cert = x;

    if (!cache->anyPolicy)

      level->flags |= X509_V_FLAG_INHIBIT_ANY;

    /* Determine inhibit any and inhibit map flags */

    if (any_skip == 0) {

      /* Any matching allowed if certificate is self

       * issued and not the last in the chain.

       */

      if (!(x->ex_flags & EXFLAG_SI) || (i == 0))

        level->flags |= X509_V_FLAG_INHIBIT_ANY;

    } else {

      if (!(x->ex_flags & EXFLAG_SI))

        any_skip--;

      if ((cache->any_skip >= 0) &&

          (cache->any_skip < any_skip))

        any_skip = cache->any_skip;

    }

    if (map_skip == 0)

      level->flags |= X509_V_FLAG_INHIBIT_MAP;

    else {

      if (!(x->ex_flags & EXFLAG_SI))

        map_skip--;

      if ((cache->map_skip >= 0) &&

          (cache->map_skip < map_skip))

        map_skip = cache->map_skip;

    }

  }

  *ptree = tree;

  if (explicit_policy)

    return 1;

  else

    return 5;

bad_tree:

  X509_policy_tree_free(tree);

  return 0;

}

static int

tree_link_matching_nodes(X509_POLICY_LEVEL *curr, const X509_POLICY_DATA *data)

{

  X509_POLICY_LEVEL *last = curr - 1;

  X509_POLICY_NODE *node;

  int i, matched = 0;

  /* Iterate through all in nodes linking matches */

  for (i = 0; i < sk_X509_POLICY_NODE_num(last->nodes); i++) {

    node = sk_X509_POLICY_NODE_value(last->nodes, i);

    if (policy_node_match(last, node, data->valid_policy)) {

      if (!level_add_node(curr, data, node, NULL, NULL))

        return 0;

      matched = 1;

    }

  }

  if (!matched && last->anyPolicy) {

    if (!level_add_node(curr, data, last->anyPolicy, NULL, NULL))

      return 0;

  }

  return 1;

}

/* This corresponds to RFC3280 6.1.3(d)(1):

 * link any data from CertificatePolicies onto matching parent

 * or anyPolicy if no match.

 */

static int

tree_link_nodes(X509_POLICY_LEVEL *curr, const X509_POLICY_CACHE *cache)

{

  int i;

  X509_POLICY_DATA *data;

  for (i = 0; i < sk_X509_POLICY_DATA_num(cache->data); i++) {

    data = sk_X509_POLICY_DATA_value(cache->data, i);

    /* Look for matching nodes in previous level */

    if (!tree_link_matching_nodes(curr, data))

      return 0;

  }

  return 1;

}

/* This corresponds to RFC3280 6.1.3(d)(2):

 * Create new data for any unmatched policies in the parent and link

 * to anyPolicy.

 */

static int

tree_add_unmatched(X509_POLICY_LEVEL *curr, const X509_POLICY_CACHE *cache,

    const ASN1_OBJECT *id, X509_POLICY_NODE *node, X509_POLICY_TREE *tree)

{

  X509_POLICY_DATA *data;

  if (id == NULL)

    id = node->data->valid_policy;

  /* Create a new node with qualifiers from anyPolicy and

   * id from unmatched node.

   */

  data = policy_data_new(NULL, id, node_critical(node));

  if (data == NULL)

    return 0;

  /* Curr may not have anyPolicy */

  data->qualifier_set = cache->anyPolicy->qualifier_set;

  data->flags |= POLICY_DATA_FLAG_SHARED_QUALIFIERS;

  if (!level_add_node(curr, data, node, tree, NULL)) {

    policy_data_free(data);

    return 0;

  }

  return 1;

}

static int

tree_link_unmatched(X509_POLICY_LEVEL *curr, const X509_POLICY_CACHE *cache,

    X509_POLICY_NODE *node, X509_POLICY_TREE *tree)

{

  const X509_POLICY_LEVEL *last = curr - 1;

  int i;

  if ((last->flags & X509_V_FLAG_INHIBIT_MAP) ||

      !(node->data->flags & POLICY_DATA_FLAG_MAPPED)) {

    /* If no policy mapping: matched if one child present */

    if (node->nchild)

      return 1;

    if (!tree_add_unmatched(curr, cache, NULL, node, tree))

      return 0;

    /* Add it */

  } else {

    /* If mapping: matched if one child per expected policy set */

    STACK_OF(ASN1_OBJECT) *expset = node->data->expected_policy_set;

    if (node->nchild == sk_ASN1_OBJECT_num(expset))

      return 1;

    /* Locate unmatched nodes */

    for (i = 0; i < sk_ASN1_OBJECT_num(expset); i++) {

      ASN1_OBJECT *oid = sk_ASN1_OBJECT_value(expset, i);

      if (level_find_node(curr, node, oid))

        continue;

      if (!tree_add_unmatched(curr, cache, oid, node, tree))

        return 0;

    }

  }

  return 1;

}

static int

tree_link_any(X509_POLICY_LEVEL *curr, const X509_POLICY_CACHE *cache,

    X509_POLICY_TREE *tree)

{

  int i;

  X509_POLICY_NODE *node;

  X509_POLICY_LEVEL *last = curr - 1;

  for (i = 0; i < sk_X509_POLICY_NODE_num(last->nodes); i++) {

    node = sk_X509_POLICY_NODE_value(last->nodes, i);

    if (!tree_link_unmatched(curr, cache, node, tree))

      return 0;

  }

  /* Finally add link to anyPolicy */

  if (last->anyPolicy) {

    if (!level_add_node(curr, cache->anyPolicy,

        last->anyPolicy, NULL, NULL))

      return 0;

  }

  return 1;

}

/* Prune the tree: delete any child mapped child data on the current level

 * then proceed up the tree deleting any data with no children. If we ever

 * have no data on a level we can halt because the tree will be empty.

 */

static int

tree_prune(X509_POLICY_TREE *tree, X509_POLICY_LEVEL *curr)

{

  STACK_OF(X509_POLICY_NODE) *nodes;

  X509_POLICY_NODE *node;

  int i;

  nodes = curr->nodes;

  if (curr->flags & X509_V_FLAG_INHIBIT_MAP) {

    for (i = sk_X509_POLICY_NODE_num(nodes) - 1; i >= 0; i--) {

      node = sk_X509_POLICY_NODE_value(nodes, i);

      /* Delete any mapped data: see RFC3280 XXXX */

      if (node->data->flags & POLICY_DATA_FLAG_MAP_MASK) {

        node->parent->nchild--;

        free(node);

        (void)sk_X509_POLICY_NODE_delete(nodes, i);

      }

    }

  }

  for (;;) {

    --curr;

    nodes = curr->nodes;

    for (i = sk_X509_POLICY_NODE_num(nodes) - 1; i >= 0; i--) {

      node = sk_X509_POLICY_NODE_value(nodes, i);

      if (node->nchild == 0) {

        node->parent->nchild--;

        free(node);

        (void)sk_X509_POLICY_NODE_delete(nodes, i);

      }

    }

    if (curr->anyPolicy && !curr->anyPolicy->nchild) {

      if (curr->anyPolicy->parent)

        curr->anyPolicy->parent->nchild--;

      free(curr->anyPolicy);

      curr->anyPolicy = NULL;

    }

    if (curr == tree->levels) {

      /* If we zapped anyPolicy at top then tree is empty */

      if (!curr->anyPolicy)

        return 2;

      return 1;

    }

  }

  return 1;

}

static int

tree_add_auth_node(STACK_OF(X509_POLICY_NODE) **pnodes, X509_POLICY_NODE *pcy)

{

  if (!*pnodes) {

    *pnodes = policy_node_cmp_new();

    if (!*pnodes)

      return 0;

  } else if (sk_X509_POLICY_NODE_find(*pnodes, pcy) != -1)

    return 1;

  if (!sk_X509_POLICY_NODE_push(*pnodes, pcy))

    return 0;

  return 1;

}

/* Calculate the authority set based on policy tree.

 * The 'pnodes' parameter is used as a store for the set of policy nodes

 * used to calculate the user set. If the authority set is not anyPolicy

 * then pnodes will just point to the authority set. If however the authority

 * set is anyPolicy then the set of valid policies (other than anyPolicy)

 * is store in pnodes. The return value of '2' is used in this case to indicate

 * that pnodes should be freed.

 */

static int

tree_calculate_authority_set(X509_POLICY_TREE *tree,

    STACK_OF(X509_POLICY_NODE) **pnodes)

{

  X509_POLICY_LEVEL *curr;

  X509_POLICY_NODE *node, *anyptr;

  STACK_OF(X509_POLICY_NODE) **addnodes;

  int i, j;

  curr = tree->levels + tree->nlevel - 1;

  /* If last level contains anyPolicy set is anyPolicy */

  if (curr->anyPolicy) {

    if (!tree_add_auth_node(&tree->auth_policies, curr->anyPolicy))

      return 0;

    addnodes = pnodes;

  } else

    /* Add policies to authority set */

    addnodes = &tree->auth_policies;

  curr = tree->levels;

  for (i = 1; i < tree->nlevel; i++) {

    /* If no anyPolicy node on this this level it can't

     * appear on lower levels so end search.

     */

    if (!(anyptr = curr->anyPolicy))

      break;

    curr++;

    for (j = 0; j < sk_X509_POLICY_NODE_num(curr->nodes); j++) {

      node = sk_X509_POLICY_NODE_value(curr->nodes, j);

      if ((node->parent == anyptr) &&

          !tree_add_auth_node(addnodes, node))

        return 0;

    }

  }

  if (addnodes == pnodes)

    return 2;

  *pnodes = tree->auth_policies;

  return 1;

}

static int

tree_calculate_user_set(X509_POLICY_TREE *tree,

    STACK_OF(ASN1_OBJECT) *policy_oids, STACK_OF(X509_POLICY_NODE) *auth_nodes)

{

  int i;

  X509_POLICY_NODE *node;

  ASN1_OBJECT *oid;

  X509_POLICY_NODE *anyPolicy;

  X509_POLICY_DATA *extra;

  /* Check if anyPolicy present in authority constrained policy set:

   * this will happen if it is a leaf node.

   */

  if (sk_ASN1_OBJECT_num(policy_oids) <= 0)

    return 1;

  anyPolicy = tree->levels[tree->nlevel - 1].anyPolicy;

  for (i = 0; i < sk_ASN1_OBJECT_num(policy_oids); i++) {

    oid = sk_ASN1_OBJECT_value(policy_oids, i);

    if (OBJ_obj2nid(oid) == NID_any_policy) {

      tree->flags |= POLICY_FLAG_ANY_POLICY;

      return 1;

    }

  }

  for (i = 0; i < sk_ASN1_OBJECT_num(policy_oids); i++) {

    oid = sk_ASN1_OBJECT_value(policy_oids, i);

    node = tree_find_sk(auth_nodes, oid);

    if (!node) {

      if (!anyPolicy)

        continue;

      /* Create a new node with policy ID from user set

       * and qualifiers from anyPolicy.

       */

      extra = policy_data_new(NULL, oid,

          node_critical(anyPolicy));

      if (!extra)

        return 0;

      extra->qualifier_set = anyPolicy->data->qualifier_set;

      extra->flags = POLICY_DATA_FLAG_SHARED_QUALIFIERS |

          POLICY_DATA_FLAG_EXTRA_NODE;

      (void) level_add_node(NULL, extra, anyPolicy->parent,

          tree, &node);

    }

    if (!tree->user_policies) {

      tree->user_policies = sk_X509_POLICY_NODE_new_null();

      if (!tree->user_policies)

        return 1;

    }

    if (!sk_X509_POLICY_NODE_push(tree->user_policies, node))

      return 0;

  }

  return 1;

}

static int

tree_evaluate(X509_POLICY_TREE *tree)

{

  int ret, i;

  X509_POLICY_LEVEL *curr = tree->levels + 1;

  const X509_POLICY_CACHE *cache;

  for (i = 1; i < tree->nlevel; i++, curr++) {

    cache = policy_cache_set(curr->cert);

    if (!tree_link_nodes(curr, cache))

      return 0;

    if (!(curr->flags & X509_V_FLAG_INHIBIT_ANY) &&

        !tree_link_any(curr, cache, tree))

      return 0;

    tree_print("before tree_prune()", tree, curr);

    ret = tree_prune(tree, curr);

    if (ret != 1)

      return ret;

  }

  return 1;

}

static void

exnode_free(X509_POLICY_NODE *node)

{

  if (node->data && (node->data->flags & POLICY_DATA_FLAG_EXTRA_NODE))

    free(node);

}

void

X509_policy_tree_free(X509_POLICY_TREE *tree)

{

  X509_POLICY_LEVEL *curr;

  int i;

  if (!tree)

    return;

  sk_X509_POLICY_NODE_free(tree->auth_policies);

  sk_X509_POLICY_NODE_pop_free(tree->user_policies, exnode_free);

  for (i = 0, curr = tree->levels; i < tree->nlevel; i++, curr++) {

    X509_free(curr->cert);

    if (curr->nodes)

      sk_X509_POLICY_NODE_pop_free(curr->nodes,

        policy_node_free);

    if (curr->anyPolicy)

      policy_node_free(curr->anyPolicy);

  }

  if (tree->extra_data)

    sk_X509_POLICY_DATA_pop_free(tree->extra_data,

        policy_data_free);

  free(tree->levels);

  free(tree);

}

/* Application policy checking function.

 * Return codes:

 *  0   Internal Error.

 *  1   Successful.

 * -1   One or more certificates contain invalid or inconsistent extensions

 * -2 User constrained policy set empty and requireExplicit true.

 */

int

X509_policy_check(X509_POLICY_TREE **ptree, int *pexplicit_policy,

    STACK_OF(X509) *certs, STACK_OF(ASN1_OBJECT) *policy_oids,

    unsigned int flags)

{

  int ret, ret2;

  X509_POLICY_TREE *tree = NULL;

  STACK_OF(X509_POLICY_NODE) *nodes, *auth_nodes = NULL;

  *ptree = NULL;

  *pexplicit_policy = 0;

  ret = tree_init(&tree, certs, flags);

  switch (ret) {

    /* Tree empty requireExplicit False: OK */

  case 2:

    return 1;

    /* Some internal error */

  case -1:

    return -1;

    /* Some internal error */

  case 0:

    return 0;

    /* Tree empty requireExplicit True: Error */

  case 6:

    *pexplicit_policy = 1;

    return -2;

    /* Tree OK requireExplicit True: OK and continue */

  case 5:

    *pexplicit_policy = 1;

    break;

    /* Tree OK: continue */

  case 1:

    if (!tree)

      /*

       * tree_init() returns success and a null tree

       * if it's just looking at a trust anchor.

       * I'm not sure that returning success here is

       * correct, but I'm sure that reporting this

       * as an internal error which our caller

       * interprets as a malloc failure is wrong.

       */

      return 1;

    break;

  }

  if (!tree)

    goto error;

  ret = tree_evaluate(tree);

  tree_print("tree_evaluate()", tree, NULL);

  if (ret <= 0)

    goto error;

  /* Return value 2 means tree empty */

  if (ret == 2) {

    X509_policy_tree_free(tree);

    if (*pexplicit_policy)

      return -2;

    else

      return 1;

  }

  /* Tree is not empty: continue */

  ret = tree_calculate_authority_set(tree, &auth_nodes);

  if (ret == 0)

    goto error;

  ret2 = tree_calculate_user_set(tree, policy_oids, auth_nodes);

  /* Return value 2 means auth_nodes needs to be freed */

  if (ret == 2)

    sk_X509_POLICY_NODE_free(auth_nodes);

  if (ret2 == 0)

    goto error;

  if (tree)

    *ptree = tree;

  if (*pexplicit_policy) {

    nodes = X509_policy_tree_get0_user_policies(tree);

    if (sk_X509_POLICY_NODE_num(nodes) <= 0)

      return -2;

  }

  return 1;

error:

  X509_policy_tree_free(tree);

  return 0;

}