1 /* $OpenBSD: x509_policy.c,v 1.29 2025/01/06 17:42:39 tb Exp $ */ 2 /* 3 * Copyright (c) 2022, Google Inc. 4 * 5 * Permission to use, copy, modify, and/or distribute this software for any 6 * purpose with or without fee is hereby granted, provided that the above 7 * copyright notice and this permission notice appear in all copies. 8 * 9 * THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES 10 * WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF 11 * MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY 12 * SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES 13 * WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN ACTION 14 * OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF OR IN 15 * CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE. 16 */ 17 18 #include <string.h> 19 20 #include <openssl/err.h> 21 #include <openssl/objects.h> 22 #include <openssl/stack.h> 23 #include <openssl/x509.h> 24 #include <openssl/x509v3.h> 25 26 #include "stack_local.h" 27 #include "x509_internal.h" 28 #include "x509_local.h" 29 30 /* XXX move to proper place */ 31 #define X509_R_INVALID_POLICY_EXTENSION 201 32 33 /* 34 * This file computes the X.509 policy tree, as described in RFC 5280, 35 * section 6.1 and RFC 9618. It differs in that: 36 * 37 * (1) It does not track "qualifier_set". This is not needed as it is not 38 * output by this implementation. 39 * 40 * (2) It builds a directed acyclic graph, rather than a tree. When a given 41 * policy matches multiple parents, RFC 5280 makes a separate node for 42 * each parent. This representation condenses them into one node with 43 * multiple parents. Thus we refer to this structure as a "policy graph", 44 * rather than a "policy tree". 45 * 46 * (3) "expected_policy_set" is not tracked explicitly and built temporarily 47 * as part of building the graph. 48 * 49 * (4) anyPolicy nodes are not tracked explicitly. 50 * 51 * (5) Some pruning steps are deferred to when policies are evaluated, as a 52 * reachability pass. 53 */ 54 55 /* 56 * An X509_POLICY_NODE is a node in the policy graph. It corresponds to a node 57 * from RFC 5280, section 6.1.2, step (a), but we store some fields differently. 58 */ 59 typedef struct x509_policy_node_st { 60 /* policy is the "valid_policy" field from RFC 5280. */ 61 ASN1_OBJECT *policy; 62 63 /* 64 * parent_policies, if non-empty, is the list of "valid_policy" values 65 * for all nodes which are a parent of this node. In this case, no entry 66 * in this list will be anyPolicy. This list is in no particular order 67 * and may contain duplicates if the corresponding certificate had 68 * duplicate mappings. 69 * 70 * If empty, this node has a single parent, anyPolicy. The node is then 71 * a root policies, and is in authorities-constrained-policy-set if it 72 * has a path to a leaf node. 73 * 74 * Note it is not possible for a policy to have both anyPolicy and a 75 * concrete policy as a parent. Section 6.1.3, step (d.1.ii) only runs 76 * if there was no match in step (d.1.i). We do not need to represent a 77 * parent list of, say, {anyPolicy, OID1, OID2}. 78 */ 79 STACK_OF(ASN1_OBJECT) *parent_policies; 80 81 /* 82 * mapped is one if this node matches a policy mapping in the 83 * certificate and zero otherwise. 84 */ 85 int mapped; 86 87 /* 88 * reachable is one if this node is reachable from some valid policy in 89 * the end-entity certificate. It is computed during |has_explicit_policy|. 90 */ 91 int reachable; 92 } X509_POLICY_NODE; 93 94 DECLARE_STACK_OF(X509_POLICY_NODE) 95 96 #define sk_X509_POLICY_NODE_new(cmp) SKM_sk_new(X509_POLICY_NODE, (cmp)) 97 #define sk_X509_POLICY_NODE_new_null() SKM_sk_new_null(X509_POLICY_NODE) 98 #define sk_X509_POLICY_NODE_free(st) SKM_sk_free(X509_POLICY_NODE, (st)) 99 #define sk_X509_POLICY_NODE_num(st) SKM_sk_num(X509_POLICY_NODE, (st)) 100 #define sk_X509_POLICY_NODE_value(st, i) SKM_sk_value(X509_POLICY_NODE, (st), (i)) 101 #define sk_X509_POLICY_NODE_set(st, i, val) SKM_sk_set(X509_POLICY_NODE, (st), (i), (val)) 102 #define sk_X509_POLICY_NODE_zero(st) SKM_sk_zero(X509_POLICY_NODE, (st)) 103 #define sk_X509_POLICY_NODE_push(st, val) SKM_sk_push(X509_POLICY_NODE, (st), (val)) 104 #define sk_X509_POLICY_NODE_unshift(st, val) SKM_sk_unshift(X509_POLICY_NODE, (st), (val)) 105 #define sk_X509_POLICY_NODE_find(st, val) SKM_sk_find(X509_POLICY_NODE, (st), (val)) 106 #define sk_X509_POLICY_NODE_delete(st, i) SKM_sk_delete(X509_POLICY_NODE, (st), (i)) 107 #define sk_X509_POLICY_NODE_delete_ptr(st, ptr) SKM_sk_delete_ptr(X509_POLICY_NODE, (st), (ptr)) 108 #define sk_X509_POLICY_NODE_insert(st, val, i) SKM_sk_insert(X509_POLICY_NODE, (st), (val), (i)) 109 #define sk_X509_POLICY_NODE_set_cmp_func(st, cmp) SKM_sk_set_cmp_func(X509_POLICY_NODE, (st), (cmp)) 110 #define sk_X509_POLICY_NODE_dup(st) SKM_sk_dup(X509_POLICY_NODE, st) 111 #define sk_X509_POLICY_NODE_pop_free(st, free_func) SKM_sk_pop_free(X509_POLICY_NODE, (st), (free_func)) 112 #define sk_X509_POLICY_NODE_shift(st) SKM_sk_shift(X509_POLICY_NODE, (st)) 113 #define sk_X509_POLICY_NODE_pop(st) SKM_sk_pop(X509_POLICY_NODE, (st)) 114 #define sk_X509_POLICY_NODE_sort(st) SKM_sk_sort(X509_POLICY_NODE, (st)) 115 #define sk_X509_POLICY_NODE_is_sorted(st) SKM_sk_is_sorted(X509_POLICY_NODE, (st)) 116 117 /* 118 * An X509_POLICY_LEVEL is the collection of nodes at the same depth in the 119 * policy graph. This structure can also be used to represent a level's 120 * "expected_policy_set" values. See |process_policy_mappings|. 121 */ 122 typedef struct x509_policy_level_st { 123 /* 124 * nodes is the list of nodes at this depth, except for the anyPolicy 125 * node, if any. This list is sorted by policy OID for efficient lookup. 126 */ 127 STACK_OF(X509_POLICY_NODE) *nodes; 128 129 /* 130 * has_any_policy is one if there is an anyPolicy node at this depth, 131 * and zero otherwise. 132 */ 133 int has_any_policy; 134 } X509_POLICY_LEVEL; 135 136 DECLARE_STACK_OF(X509_POLICY_LEVEL) 137 138 #define sk_X509_POLICY_LEVEL_new(cmp) SKM_sk_new(X509_POLICY_LEVEL, (cmp)) 139 #define sk_X509_POLICY_LEVEL_new_null() SKM_sk_new_null(X509_POLICY_LEVEL) 140 #define sk_X509_POLICY_LEVEL_free(st) SKM_sk_free(X509_POLICY_LEVEL, (st)) 141 #define sk_X509_POLICY_LEVEL_num(st) SKM_sk_num(X509_POLICY_LEVEL, (st)) 142 #define sk_X509_POLICY_LEVEL_value(st, i) SKM_sk_value(X509_POLICY_LEVEL, (st), (i)) 143 #define sk_X509_POLICY_LEVEL_set(st, i, val) SKM_sk_set(X509_POLICY_LEVEL, (st), (i), (val)) 144 #define sk_X509_POLICY_LEVEL_zero(st) SKM_sk_zero(X509_POLICY_LEVEL, (st)) 145 #define sk_X509_POLICY_LEVEL_push(st, val) SKM_sk_push(X509_POLICY_LEVEL, (st), (val)) 146 #define sk_X509_POLICY_LEVEL_unshift(st, val) SKM_sk_unshift(X509_POLICY_LEVEL, (st), (val)) 147 #define sk_X509_POLICY_LEVEL_find(st, val) SKM_sk_find(X509_POLICY_LEVEL, (st), (val)) 148 #define sk_X509_POLICY_LEVEL_delete(st, i) SKM_sk_delete(X509_POLICY_LEVEL, (st), (i)) 149 #define sk_X509_POLICY_LEVEL_delete_ptr(st, ptr) SKM_sk_delete_ptr(X509_POLICY_LEVEL, (st), (ptr)) 150 #define sk_X509_POLICY_LEVEL_insert(st, val, i) SKM_sk_insert(X509_POLICY_LEVEL, (st), (val), (i)) 151 #define sk_X509_POLICY_LEVEL_set_cmp_func(st, cmp) SKM_sk_set_cmp_func(X509_POLICY_LEVEL, (st), (cmp)) 152 #define sk_X509_POLICY_LEVEL_dup(st) SKM_sk_dup(X509_POLICY_LEVEL, st) 153 #define sk_X509_POLICY_LEVEL_pop_free(st, free_func) SKM_sk_pop_free(X509_POLICY_LEVEL, (st), (free_func)) 154 #define sk_X509_POLICY_LEVEL_shift(st) SKM_sk_shift(X509_POLICY_LEVEL, (st)) 155 #define sk_X509_POLICY_LEVEL_pop(st) SKM_sk_pop(X509_POLICY_LEVEL, (st)) 156 #define sk_X509_POLICY_LEVEL_sort(st) SKM_sk_sort(X509_POLICY_LEVEL, (st)) 157 #define sk_X509_POLICY_LEVEL_is_sorted(st) SKM_sk_is_sorted(X509_POLICY_LEVEL, (st)) 158 159 /* 160 * Don't look Ethel, but you would really not want to look if we did 161 * this the OpenSSL way either, and we are not using this boringsslism 162 * anywhere else. Callers should ensure that the stack in data is sorted. 163 */ 164 void 165 sk_X509_POLICY_NODE_delete_if(STACK_OF(X509_POLICY_NODE) *nodes, 166 int (*delete_if)(X509_POLICY_NODE *, void *), void *data) 167 { 168 _STACK *sk = (_STACK *)nodes; 169 X509_POLICY_NODE *node; 170 int new_num = 0; 171 int i; 172 173 for (i = 0; i < sk_X509_POLICY_NODE_num(nodes); i++) { 174 node = sk_X509_POLICY_NODE_value(nodes, i); 175 if (!delete_if(node, data)) 176 sk->data[new_num++] = (char *)node; 177 } 178 sk->num = new_num; 179 } 180 181 static int 182 is_any_policy(const ASN1_OBJECT *obj) 183 { 184 return OBJ_obj2nid(obj) == NID_any_policy; 185 } 186 187 static void 188 x509_policy_node_free(X509_POLICY_NODE *node) 189 { 190 if (node == NULL) 191 return; 192 193 ASN1_OBJECT_free(node->policy); 194 sk_ASN1_OBJECT_pop_free(node->parent_policies, ASN1_OBJECT_free); 195 free(node); 196 } 197 198 static X509_POLICY_NODE * 199 x509_policy_node_new(const ASN1_OBJECT *policy) 200 { 201 X509_POLICY_NODE *node = NULL; 202 203 if (is_any_policy(policy)) 204 goto err; 205 if ((node = calloc(1, sizeof(*node))) == NULL) 206 goto err; 207 if ((node->policy = OBJ_dup(policy)) == NULL) 208 goto err; 209 if ((node->parent_policies = sk_ASN1_OBJECT_new_null()) == NULL) 210 goto err; 211 212 return node; 213 214 err: 215 x509_policy_node_free(node); 216 return NULL; 217 } 218 219 static int 220 x509_policy_node_cmp(const X509_POLICY_NODE *const *a, 221 const X509_POLICY_NODE *const *b) 222 { 223 return OBJ_cmp((*a)->policy, (*b)->policy); 224 } 225 226 static void 227 x509_policy_level_free(X509_POLICY_LEVEL *level) 228 { 229 if (level == NULL) 230 return; 231 232 sk_X509_POLICY_NODE_pop_free(level->nodes, x509_policy_node_free); 233 free(level); 234 } 235 236 static X509_POLICY_LEVEL * 237 x509_policy_level_new(void) 238 { 239 X509_POLICY_LEVEL *level; 240 241 if ((level = calloc(1, sizeof(*level))) == NULL) 242 goto err; 243 level->nodes = sk_X509_POLICY_NODE_new(x509_policy_node_cmp); 244 if (level->nodes == NULL) 245 goto err; 246 247 return level; 248 249 err: 250 x509_policy_level_free(level); 251 return NULL; 252 } 253 254 static int 255 x509_policy_level_is_empty(const X509_POLICY_LEVEL *level) 256 { 257 if (level->has_any_policy) 258 return 0; 259 260 return sk_X509_POLICY_NODE_num(level->nodes) == 0; 261 } 262 263 static void 264 x509_policy_level_clear(X509_POLICY_LEVEL *level) 265 { 266 X509_POLICY_NODE *node; 267 int i; 268 269 level->has_any_policy = 0; 270 for (i = 0; i < sk_X509_POLICY_NODE_num(level->nodes); i++) { 271 node = sk_X509_POLICY_NODE_value(level->nodes, i); 272 x509_policy_node_free(node); 273 } 274 sk_X509_POLICY_NODE_zero(level->nodes); 275 } 276 277 /* 278 * x509_policy_level_find returns the node in |level| corresponding to |policy|, 279 * or NULL if none exists. Callers should ensure that level->nodes is sorted 280 * to avoid the cost of sorting it in sk_find(). 281 */ 282 static X509_POLICY_NODE * 283 x509_policy_level_find(X509_POLICY_LEVEL *level, const ASN1_OBJECT *policy) 284 { 285 X509_POLICY_NODE node; 286 node.policy = (ASN1_OBJECT *)policy; 287 int idx; 288 289 if ((idx = sk_X509_POLICY_NODE_find(level->nodes, &node)) < 0) 290 return NULL; 291 return sk_X509_POLICY_NODE_value(level->nodes, idx); 292 } 293 294 /* 295 * x509_policy_level_add_nodes adds the nodes in |nodes| to |level|. It returns 296 * one on success and zero on error. No policy in |nodes| may already be present 297 * in |level|. This function modifies |nodes| to avoid making a copy, but the 298 * caller is still responsible for releasing |nodes| itself. 299 * 300 * This function is used to add nodes to |level| in bulk, and avoid resorting 301 * |level| after each addition. 302 */ 303 static int 304 x509_policy_level_add_nodes(X509_POLICY_LEVEL *level, 305 STACK_OF(X509_POLICY_NODE) *nodes) 306 { 307 int i; 308 309 for (i = 0; i < sk_X509_POLICY_NODE_num(nodes); i++) { 310 X509_POLICY_NODE *node = sk_X509_POLICY_NODE_value(nodes, i); 311 if (!sk_X509_POLICY_NODE_push(level->nodes, node)) 312 return 0; 313 sk_X509_POLICY_NODE_set(nodes, i, NULL); 314 } 315 sk_X509_POLICY_NODE_sort(level->nodes); 316 317 return 1; 318 } 319 320 static int 321 policyinfo_cmp(const POLICYINFO *const *a, 322 const POLICYINFO *const *b) 323 { 324 return OBJ_cmp((*a)->policyid, (*b)->policyid); 325 } 326 327 static int 328 delete_if_not_in_policies(X509_POLICY_NODE *node, void *data) 329 { 330 const CERTIFICATEPOLICIES *policies = data; 331 POLICYINFO info; 332 info.policyid = node->policy; 333 334 if (sk_POLICYINFO_find(policies, &info) >= 0) 335 return 0; 336 x509_policy_node_free(node); 337 return 1; 338 } 339 340 /* 341 * process_certificate_policies updates |level| to incorporate |x509|'s 342 * certificate policies extension. This implements steps (d) and (e) of RFC 343 * 5280, section 6.1.3. |level| must contain the previous level's 344 * "expected_policy_set" information. For all but the top-most level, this is 345 * the output of |process_policy_mappings|. |any_policy_allowed| specifies 346 * whether anyPolicy is allowed or inhibited, taking into account the exception 347 * for self-issued certificates. 348 */ 349 static int 350 process_certificate_policies(const X509 *x509, X509_POLICY_LEVEL *level, 351 int any_policy_allowed) 352 { 353 STACK_OF(X509_POLICY_NODE) *new_nodes = NULL; 354 CERTIFICATEPOLICIES *policies; 355 const POLICYINFO *policy; 356 X509_POLICY_NODE *node; 357 int cert_has_any_policy, critical, i, previous_level_has_any_policy; 358 int ret = 0; 359 360 policies = X509_get_ext_d2i(x509, NID_certificate_policies, &critical, 361 NULL); 362 if (policies == NULL) { 363 if (critical != -1) 364 return 0; /* Syntax error in the extension. */ 365 366 /* RFC 5280, section 6.1.3, step (e). */ 367 x509_policy_level_clear(level); 368 return 1; 369 } 370 371 /* 372 * certificatePolicies may not be empty. See RFC 5280, section 4.2.1.4. 373 * TODO(https://crbug.com/boringssl/443): Move this check into the parser. 374 */ 375 if (sk_POLICYINFO_num(policies) == 0) { 376 X509error(X509_R_INVALID_POLICY_EXTENSION); 377 goto err; 378 } 379 380 (void)sk_POLICYINFO_set_cmp_func(policies, policyinfo_cmp); 381 sk_POLICYINFO_sort(policies); 382 cert_has_any_policy = 0; 383 for (i = 0; i < sk_POLICYINFO_num(policies); i++) { 384 policy = sk_POLICYINFO_value(policies, i); 385 if (is_any_policy(policy->policyid)) 386 cert_has_any_policy = 1; 387 if (i > 0 && 388 OBJ_cmp(sk_POLICYINFO_value(policies, i - 1)->policyid, 389 policy->policyid) == 0) { 390 /* 391 * Per RFC 5280, section 4.2.1.4, |policies| may not 392 * have duplicates. 393 */ 394 X509error(X509_R_INVALID_POLICY_EXTENSION); 395 goto err; 396 } 397 } 398 399 /* 400 * This does the same thing as RFC 5280, section 6.1.3, step (d), 401 * though in a slightly different order. |level| currently contains 402 * "expected_policy_set" values of the previous level. 403 * See |process_policy_mappings| for details. 404 */ 405 previous_level_has_any_policy = level->has_any_policy; 406 407 /* 408 * First, we handle steps (d.1.i) and (d.2). The net effect of these 409 * two steps is to intersect |level| with |policies|, ignoring 410 * anyPolicy if it is inhibited. 411 */ 412 if (!cert_has_any_policy || !any_policy_allowed) { 413 if (!sk_POLICYINFO_is_sorted(policies)) 414 goto err; 415 sk_X509_POLICY_NODE_delete_if(level->nodes, 416 delete_if_not_in_policies, policies); 417 level->has_any_policy = 0; 418 } 419 420 /* 421 * Step (d.1.ii) may attach new nodes to the previous level's anyPolicy 422 * node. 423 */ 424 if (previous_level_has_any_policy) { 425 new_nodes = sk_X509_POLICY_NODE_new_null(); 426 if (new_nodes == NULL) 427 goto err; 428 for (i = 0; i < sk_POLICYINFO_num(policies); i++) { 429 policy = sk_POLICYINFO_value(policies, i); 430 /* 431 * Though we've reordered the steps slightly, |policy| 432 * is in |level| if and only if it would have been a 433 * match in step (d.1.ii). 434 */ 435 if (is_any_policy(policy->policyid)) 436 continue; 437 if (!sk_X509_POLICY_NODE_is_sorted(level->nodes)) 438 goto err; 439 if (x509_policy_level_find(level, policy->policyid) != NULL) 440 continue; 441 node = x509_policy_node_new(policy->policyid); 442 if (node == NULL || 443 !sk_X509_POLICY_NODE_push(new_nodes, node)) { 444 x509_policy_node_free(node); 445 goto err; 446 } 447 } 448 if (!x509_policy_level_add_nodes(level, new_nodes)) 449 goto err; 450 } 451 452 ret = 1; 453 454 err: 455 sk_X509_POLICY_NODE_pop_free(new_nodes, x509_policy_node_free); 456 CERTIFICATEPOLICIES_free(policies); 457 return ret; 458 } 459 460 static int 461 compare_issuer_policy(const POLICY_MAPPING *const *a, 462 const POLICY_MAPPING *const *b) 463 { 464 return OBJ_cmp((*a)->issuerDomainPolicy, (*b)->issuerDomainPolicy); 465 } 466 467 static int 468 compare_subject_policy(const POLICY_MAPPING *const *a, 469 const POLICY_MAPPING *const *b) 470 { 471 return OBJ_cmp((*a)->subjectDomainPolicy, (*b)->subjectDomainPolicy); 472 } 473 474 static int 475 delete_if_mapped(X509_POLICY_NODE *node, void *data) 476 { 477 const POLICY_MAPPINGS *mappings = data; 478 POLICY_MAPPING mapping; 479 mapping.issuerDomainPolicy = node->policy; 480 if (sk_POLICY_MAPPING_find(mappings, &mapping) < 0) 481 return 0; 482 x509_policy_node_free(node); 483 return 1; 484 } 485 486 /* 487 * process_policy_mappings processes the policy mappings extension of |cert|, 488 * whose corresponding graph level is |level|. |mapping_allowed| specifies 489 * whether policy mapping is inhibited at this point. On success, it returns an 490 * |X509_POLICY_LEVEL| containing the "expected_policy_set" for |level|. On 491 * error, it returns NULL. This implements steps (a) and (b) of RFC 5280, 492 * section 6.1.4. 493 * 494 * We represent the "expected_policy_set" as an |X509_POLICY_LEVEL|. 495 * |has_any_policy| indicates whether there is an anyPolicy node with 496 * "expected_policy_set" of {anyPolicy}. If a node with policy oid P1 contains 497 * P2 in its "expected_policy_set", the level will contain a node of policy P2 498 * with P1 in |parent_policies|. 499 * 500 * This is equivalent to the |X509_POLICY_LEVEL| that would result if the next 501 * certificats contained anyPolicy. |process_certificate_policies| will filter 502 * this result down to compute the actual level. 503 */ 504 static X509_POLICY_LEVEL * 505 process_policy_mappings(const X509 *cert, 506 X509_POLICY_LEVEL *level, 507 int mapping_allowed) 508 { 509 STACK_OF(X509_POLICY_NODE) *new_nodes = NULL; 510 POLICY_MAPPINGS *mappings; 511 const ASN1_OBJECT *last_policy; 512 POLICY_MAPPING *mapping; 513 X509_POLICY_LEVEL *next = NULL; 514 X509_POLICY_NODE *node; 515 int critical, i; 516 int ok = 0; 517 518 mappings = X509_get_ext_d2i(cert, NID_policy_mappings, &critical, NULL); 519 if (mappings == NULL && critical != -1) { 520 /* Syntax error in the policy mappings extension. */ 521 goto err; 522 } 523 524 if (mappings != NULL) { 525 /* 526 * PolicyMappings may not be empty. See RFC 5280, section 4.2.1.5. 527 * TODO(https://crbug.com/boringssl/443): Move this check into 528 * the parser. 529 */ 530 if (sk_POLICY_MAPPING_num(mappings) == 0) { 531 X509error(X509_R_INVALID_POLICY_EXTENSION); 532 goto err; 533 } 534 535 /* RFC 5280, section 6.1.4, step (a). */ 536 for (i = 0; i < sk_POLICY_MAPPING_num(mappings); i++) { 537 mapping = sk_POLICY_MAPPING_value(mappings, i); 538 if (is_any_policy(mapping->issuerDomainPolicy) || 539 is_any_policy(mapping->subjectDomainPolicy)) 540 goto err; 541 } 542 543 /* Sort to group by issuerDomainPolicy. */ 544 (void)sk_POLICY_MAPPING_set_cmp_func(mappings, 545 compare_issuer_policy); 546 sk_POLICY_MAPPING_sort(mappings); 547 548 if (mapping_allowed) { 549 /* 550 * Mark nodes as mapped, and add any nodes to |level| 551 * which may be needed as part of RFC 5280, 552 * section 6.1.4, step (b.1). 553 */ 554 new_nodes = sk_X509_POLICY_NODE_new_null(); 555 if (new_nodes == NULL) 556 goto err; 557 last_policy = NULL; 558 for (i = 0; i < sk_POLICY_MAPPING_num(mappings); i++) { 559 mapping = sk_POLICY_MAPPING_value(mappings, i); 560 /* 561 * There may be multiple mappings with the same 562 * |issuerDomainPolicy|. 563 */ 564 if (last_policy != NULL && 565 OBJ_cmp(mapping->issuerDomainPolicy, 566 last_policy) == 0) 567 continue; 568 last_policy = mapping->issuerDomainPolicy; 569 570 if (!sk_X509_POLICY_NODE_is_sorted(level->nodes)) 571 goto err; 572 node = x509_policy_level_find(level, 573 mapping->issuerDomainPolicy); 574 if (node == NULL) { 575 if (!level->has_any_policy) 576 continue; 577 node = x509_policy_node_new( 578 mapping->issuerDomainPolicy); 579 if (node == NULL || 580 !sk_X509_POLICY_NODE_push(new_nodes, 581 node)) { 582 x509_policy_node_free(node); 583 goto err; 584 } 585 } 586 node->mapped = 1; 587 } 588 if (!x509_policy_level_add_nodes(level, new_nodes)) 589 goto err; 590 } else { 591 /* 592 * RFC 5280, section 6.1.4, step (b.2). If mapping is 593 * inhibited, delete all mapped nodes. 594 */ 595 if (!sk_POLICY_MAPPING_is_sorted(mappings)) 596 goto err; 597 sk_X509_POLICY_NODE_delete_if(level->nodes, 598 delete_if_mapped, mappings); 599 sk_POLICY_MAPPING_pop_free(mappings, 600 POLICY_MAPPING_free); 601 mappings = NULL; 602 } 603 } 604 605 /* 606 * If a node was not mapped, it retains the original "explicit_policy_set" 607 * value, itself. Add those to |mappings|. 608 */ 609 if (mappings == NULL) { 610 mappings = sk_POLICY_MAPPING_new_null(); 611 if (mappings == NULL) 612 goto err; 613 } 614 for (i = 0; i < sk_X509_POLICY_NODE_num(level->nodes); i++) { 615 node = sk_X509_POLICY_NODE_value(level->nodes, i); 616 if (!node->mapped) { 617 mapping = POLICY_MAPPING_new(); 618 if (mapping == NULL) 619 goto err; 620 mapping->issuerDomainPolicy = OBJ_dup(node->policy); 621 mapping->subjectDomainPolicy = OBJ_dup(node->policy); 622 if (mapping->issuerDomainPolicy == NULL || 623 mapping->subjectDomainPolicy == NULL || 624 !sk_POLICY_MAPPING_push(mappings, mapping)) { 625 POLICY_MAPPING_free(mapping); 626 goto err; 627 } 628 } 629 } 630 631 /* Sort to group by subjectDomainPolicy. */ 632 (void)sk_POLICY_MAPPING_set_cmp_func(mappings, compare_subject_policy); 633 sk_POLICY_MAPPING_sort(mappings); 634 635 /* Convert |mappings| to our "expected_policy_set" representation. */ 636 next = x509_policy_level_new(); 637 if (next == NULL) 638 goto err; 639 next->has_any_policy = level->has_any_policy; 640 641 X509_POLICY_NODE *last_node = NULL; 642 for (i = 0; i < sk_POLICY_MAPPING_num(mappings); i++) { 643 mapping = sk_POLICY_MAPPING_value(mappings, i); 644 /* 645 * Skip mappings where |issuerDomainPolicy| does not appear in 646 * the graph. 647 */ 648 if (!level->has_any_policy) { 649 if (!sk_X509_POLICY_NODE_is_sorted(level->nodes)) 650 goto err; 651 if (x509_policy_level_find(level, 652 mapping->issuerDomainPolicy) == NULL) 653 continue; 654 } 655 656 if (last_node == NULL || 657 OBJ_cmp(last_node->policy, mapping->subjectDomainPolicy) != 658 0) { 659 last_node = x509_policy_node_new( 660 mapping->subjectDomainPolicy); 661 if (last_node == NULL || 662 !sk_X509_POLICY_NODE_push(next->nodes, last_node)) { 663 x509_policy_node_free(last_node); 664 goto err; 665 } 666 } 667 668 if (!sk_ASN1_OBJECT_push(last_node->parent_policies, 669 mapping->issuerDomainPolicy)) 670 goto err; 671 mapping->issuerDomainPolicy = NULL; 672 } 673 674 sk_X509_POLICY_NODE_sort(next->nodes); 675 ok = 1; 676 677 err: 678 if (!ok) { 679 x509_policy_level_free(next); 680 next = NULL; 681 } 682 683 sk_POLICY_MAPPING_pop_free(mappings, POLICY_MAPPING_free); 684 sk_X509_POLICY_NODE_pop_free(new_nodes, x509_policy_node_free); 685 return next; 686 } 687 688 /* 689 * apply_skip_certs, if |skip_certs| is non-NULL, sets |*value| to the minimum 690 * of its current value and |skip_certs|. It returns one on success and zero if 691 * |skip_certs| is negative. 692 */ 693 static int 694 apply_skip_certs(const ASN1_INTEGER *skip_certs, size_t *value) 695 { 696 if (skip_certs == NULL) 697 return 1; 698 699 /* TODO(https://crbug.com/boringssl/443): Move this check into the parser. */ 700 if (skip_certs->type & V_ASN1_NEG) { 701 X509error(X509_R_INVALID_POLICY_EXTENSION); 702 return 0; 703 } 704 705 /* If |skip_certs| does not fit in |uint64_t|, it must exceed |*value|. */ 706 uint64_t u64; 707 if (ASN1_INTEGER_get_uint64(&u64, skip_certs) && u64 < *value) 708 *value = (size_t)u64; 709 ERR_clear_error(); 710 return 1; 711 } 712 713 /* 714 * process_policy_constraints updates |*explicit_policy|, |*policy_mapping|, and 715 * |*inhibit_any_policy| according to |x509|'s policy constraints and inhibit 716 * anyPolicy extensions. It returns one on success and zero on error. This 717 * implements steps (i) and (j) of RFC 5280, section 6.1.4. 718 */ 719 static int 720 process_policy_constraints(const X509 *x509, size_t *explicit_policy, 721 size_t *policy_mapping, 722 size_t *inhibit_any_policy) 723 { 724 ASN1_INTEGER *inhibit_any_policy_ext; 725 POLICY_CONSTRAINTS *constraints; 726 int critical; 727 int ok = 0; 728 729 constraints = X509_get_ext_d2i(x509, NID_policy_constraints, &critical, 730 NULL); 731 if (constraints == NULL && critical != -1) 732 return 0; 733 if (constraints != NULL) { 734 if (constraints->requireExplicitPolicy == NULL && 735 constraints->inhibitPolicyMapping == NULL) { 736 /* 737 * Per RFC 5280, section 4.2.1.11, at least one of the 738 * fields must be 739 */ 740 X509error(X509_R_INVALID_POLICY_EXTENSION); 741 POLICY_CONSTRAINTS_free(constraints); 742 return 0; 743 } 744 ok = apply_skip_certs(constraints->requireExplicitPolicy, 745 explicit_policy) && 746 apply_skip_certs(constraints->inhibitPolicyMapping, 747 policy_mapping); 748 POLICY_CONSTRAINTS_free(constraints); 749 if (!ok) 750 return 0; 751 } 752 753 inhibit_any_policy_ext = X509_get_ext_d2i(x509, NID_inhibit_any_policy, 754 &critical, NULL); 755 if (inhibit_any_policy_ext == NULL && critical != -1) 756 return 0; 757 ok = apply_skip_certs(inhibit_any_policy_ext, inhibit_any_policy); 758 ASN1_INTEGER_free(inhibit_any_policy_ext); 759 return ok; 760 } 761 762 /* 763 * has_explicit_policy returns one if the set of authority-space policy OIDs 764 * |levels| has some non-empty intersection with |user_policies|, and zero 765 * otherwise. This mirrors the logic in RFC 5280, section 6.1.5, step (g). This 766 * function modifies |levels| and should only be called at the end of policy 767 * evaluation. 768 */ 769 static int 770 has_explicit_policy(STACK_OF(X509_POLICY_LEVEL) *levels, 771 const STACK_OF(ASN1_OBJECT) *user_policies) 772 { 773 X509_POLICY_LEVEL *level, *prev; 774 X509_POLICY_NODE *node, *parent; 775 int num_levels, user_has_any_policy; 776 int i, j, k; 777 778 if (!sk_ASN1_OBJECT_is_sorted(user_policies)) 779 return 0; 780 781 /* Step (g.i). If the policy graph is empty, the intersection is empty. */ 782 num_levels = sk_X509_POLICY_LEVEL_num(levels); 783 level = sk_X509_POLICY_LEVEL_value(levels, num_levels - 1); 784 if (x509_policy_level_is_empty(level)) 785 return 0; 786 787 /* 788 * If |user_policies| is empty, we interpret it as having a single 789 * anyPolicy value. The caller may also have supplied anyPolicy 790 * explicitly. 791 */ 792 user_has_any_policy = sk_ASN1_OBJECT_num(user_policies) <= 0; 793 for (i = 0; i < sk_ASN1_OBJECT_num(user_policies); i++) { 794 if (is_any_policy(sk_ASN1_OBJECT_value(user_policies, i))) { 795 user_has_any_policy = 1; 796 break; 797 } 798 } 799 800 /* 801 * Step (g.ii). If the policy graph is not empty and the user set 802 * contains anyPolicy, the intersection is the entire (non-empty) graph. 803 */ 804 if (user_has_any_policy) 805 return 1; 806 807 /* 808 * Step (g.iii) does not delete anyPolicy nodes, so if the graph has 809 * anyPolicy, some explicit policy will survive. The actual intersection 810 * may synthesize some nodes in step (g.iii.3), but we do not return the 811 * policy list itself, so we skip actually computing this. 812 */ 813 if (level->has_any_policy) 814 return 1; 815 816 /* 817 * We defer pruning the tree, so as we look for nodes with parent 818 * anyPolicy, step (g.iii.1), we must limit to nodes reachable from the 819 * bottommost level. Start by marking each of those nodes as reachable. 820 */ 821 for (i = 0; i < sk_X509_POLICY_NODE_num(level->nodes); i++) 822 sk_X509_POLICY_NODE_value(level->nodes, i)->reachable = 1; 823 824 for (i = num_levels - 1; i >= 0; i--) { 825 level = sk_X509_POLICY_LEVEL_value(levels, i); 826 for (j = 0; j < sk_X509_POLICY_NODE_num(level->nodes); j++) { 827 node = sk_X509_POLICY_NODE_value(level->nodes, j); 828 if (!node->reachable) 829 continue; 830 if (sk_ASN1_OBJECT_num(node->parent_policies) == 0) { 831 /* 832 * |node|'s parent is anyPolicy and is part of 833 * "valid_policy_node_set". If it exists in 834 * |user_policies|, the intersection is 835 * non-empty and we * can return immediately. 836 */ 837 if (sk_ASN1_OBJECT_find(user_policies, 838 node->policy) >= 0) 839 return 1; 840 } else if (i > 0) { 841 int num_parent_policies = 842 sk_ASN1_OBJECT_num(node->parent_policies); 843 /* 844 * |node|'s parents are concrete policies. Mark 845 * the parents reachable, to be inspected by the 846 * next loop iteration. 847 */ 848 prev = sk_X509_POLICY_LEVEL_value(levels, i - 1); 849 for (k = 0; k < num_parent_policies; k++) { 850 if (!sk_X509_POLICY_NODE_is_sorted(prev->nodes)) 851 return 0; 852 parent = x509_policy_level_find(prev, 853 sk_ASN1_OBJECT_value(node->parent_policies, 854 k)); 855 if (parent != NULL) 856 parent->reachable = 1; 857 } 858 } 859 } 860 } 861 862 return 0; 863 } 864 865 static int 866 asn1_object_cmp(const ASN1_OBJECT *const *a, const ASN1_OBJECT *const *b) 867 { 868 return OBJ_cmp(*a, *b); 869 } 870 871 int 872 X509_policy_check(const STACK_OF(X509) *certs, 873 const STACK_OF(ASN1_OBJECT) *user_policies, 874 unsigned long flags, X509 **out_current_cert) 875 { 876 *out_current_cert = NULL; 877 int ret = X509_V_ERR_OUT_OF_MEM; 878 X509 *cert; 879 X509_POLICY_LEVEL *level = NULL; 880 X509_POLICY_LEVEL *current_level; 881 STACK_OF(X509_POLICY_LEVEL) *levels = NULL; 882 STACK_OF(ASN1_OBJECT) *user_policies_sorted = NULL; 883 int num_certs = sk_X509_num(certs); 884 int is_self_issued, any_policy_allowed; 885 int i; 886 887 /* Skip policy checking if the chain is just the trust anchor. */ 888 if (num_certs <= 1) 889 return X509_V_OK; 890 891 /* See RFC 5280, section 6.1.2, steps (d) through (f). */ 892 size_t explicit_policy = 893 (flags & X509_V_FLAG_EXPLICIT_POLICY) ? 0 : num_certs + 1; 894 size_t inhibit_any_policy = 895 (flags & X509_V_FLAG_INHIBIT_ANY) ? 0 : num_certs + 1; 896 size_t policy_mapping = 897 (flags & X509_V_FLAG_INHIBIT_MAP) ? 0 : num_certs + 1; 898 899 levels = sk_X509_POLICY_LEVEL_new_null(); 900 if (levels == NULL) 901 goto err; 902 903 for (i = num_certs - 2; i >= 0; i--) { 904 cert = sk_X509_value(certs, i); 905 if (!x509v3_cache_extensions(cert)) 906 goto err; 907 is_self_issued = (cert->ex_flags & EXFLAG_SI) != 0; 908 909 if (level == NULL) { 910 if (i != num_certs - 2) 911 goto err; 912 level = x509_policy_level_new(); 913 if (level == NULL) 914 goto err; 915 level->has_any_policy = 1; 916 } 917 918 /* 919 * RFC 5280, section 6.1.3, steps (d) and (e). |any_policy_allowed| 920 * is computed as in step (d.2). 921 */ 922 any_policy_allowed = 923 inhibit_any_policy > 0 || (i > 0 && is_self_issued); 924 if (!process_certificate_policies(cert, level, 925 any_policy_allowed)) { 926 ret = X509_V_ERR_INVALID_POLICY_EXTENSION; 927 *out_current_cert = cert; 928 goto err; 929 } 930 931 /* RFC 5280, section 6.1.3, step (f). */ 932 if (explicit_policy == 0 && x509_policy_level_is_empty(level)) { 933 ret = X509_V_ERR_NO_EXPLICIT_POLICY; 934 goto err; 935 } 936 937 /* Insert into the list. */ 938 if (!sk_X509_POLICY_LEVEL_push(levels, level)) 939 goto err; 940 current_level = level; 941 level = NULL; 942 943 /* 944 * If this is not the leaf certificate, we go to section 6.1.4. 945 * If it is the leaf certificate, we go to section 6.1.5 instead. 946 */ 947 if (i != 0) { 948 /* RFC 5280, section 6.1.4, steps (a) and (b). */ 949 level = process_policy_mappings(cert, current_level, 950 policy_mapping > 0); 951 if (level == NULL) { 952 ret = X509_V_ERR_INVALID_POLICY_EXTENSION; 953 *out_current_cert = cert; 954 goto err; 955 } 956 } 957 958 /* 959 * RFC 5280, section 6.1.4, step (h-j) for non-leaves, and 960 * section 6.1.5, step (a-b) for leaves. In the leaf case, 961 * RFC 5280 says only to update |explicit_policy|, but 962 * |policy_mapping| and |inhibit_any_policy| are no 963 * longer read at this point, so we use the same process. 964 */ 965 if (i == 0 || !is_self_issued) { 966 if (explicit_policy > 0) 967 explicit_policy--; 968 if (policy_mapping > 0) 969 policy_mapping--; 970 if (inhibit_any_policy > 0) 971 inhibit_any_policy--; 972 } 973 if (!process_policy_constraints(cert, &explicit_policy, 974 &policy_mapping, &inhibit_any_policy)) { 975 ret = X509_V_ERR_INVALID_POLICY_EXTENSION; 976 *out_current_cert = cert; 977 goto err; 978 } 979 } 980 981 /* 982 * RFC 5280, section 6.1.5, step (g). We do not output the policy set, 983 * so it is only necessary to check if the user-constrained-policy-set 984 * is not empty. 985 */ 986 if (explicit_policy == 0) { 987 /* 988 * Build a sorted copy of |user_policies| for more efficient 989 * lookup. 990 */ 991 if (user_policies != NULL) { 992 user_policies_sorted = sk_ASN1_OBJECT_dup( 993 user_policies); 994 if (user_policies_sorted == NULL) 995 goto err; 996 (void)sk_ASN1_OBJECT_set_cmp_func(user_policies_sorted, 997 asn1_object_cmp); 998 sk_ASN1_OBJECT_sort(user_policies_sorted); 999 } 1000 1001 if (!has_explicit_policy(levels, user_policies_sorted)) { 1002 ret = X509_V_ERR_NO_EXPLICIT_POLICY; 1003 goto err; 1004 } 1005 } 1006 1007 ret = X509_V_OK; 1008 1009 err: 1010 x509_policy_level_free(level); 1011 /* 1012 * |user_policies_sorted|'s contents are owned by |user_policies|, so 1013 * we do not use |sk_ASN1_OBJECT_pop_free|. 1014 */ 1015 sk_ASN1_OBJECT_free(user_policies_sorted); 1016 sk_X509_POLICY_LEVEL_pop_free(levels, x509_policy_level_free); 1017 return ret; 1018 } 1019