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