Updates to X.509 Policy Validation
updates
- rfc-5280 — Internet X.509 Public Key Infrastructure Certificate and Certificate Revocation List (CRL) Profile
Extracted elements (20)
Limiting certificate chain depth can mitigate the exponential growth attack since the tree size is exponential in depth, but depth limits may reject legitimate paths if set too low and may still admit O(N^(depth/2)) attacks if the attacker increases the number of policies per certificate.
The new algorithm's validity semantics are identical to RFC 5280: no certification path changes validity status, and no valid policy set changes. The only difference is that one output (valid_policy_tree) is replaced by a different-form output (user_constrained_policy_set), consistent with X.509's own described outputs.
The policy tree in RFC 5280 is exponential because when multiple issuer policies map to a single subject policy, the subject policy produces multiple duplicate nodes whose children are recursively duplicated. Replacing the tree with a directed acyclic graph (policy graph) eliminates duplicates by using a single node with multiple parents, bounding size linearly by the total number of certificate policies and policy mappings.
X.509's own specification (X.509 Section 12.2) only requires authorities-constrained policies, user-constrained policies, and their qualifiers as outputs—not the full valid_policy_tree. RFC 5280's inclusion of the tree as output was therefore beyond what X.509 required and is the proximate cause of the DoS exposure.
Section 6.1.6 of RFC 5280 described the valid_policy_tree as an output of verification, but this document deprecates that output. Implementations needing it for legacy compatibility may reconstruct it from valid_policy_graph on demand by recursively duplicating multi-parent nodes, but must accept the exponential cost and apply additional mitigations.
Verifying signatures first does not fully mitigate the attack for applications that evaluate untrusted PKIs (e.g., hosting providers accepting customer-supplied PKIs) or trusted PKIs containing technically constrained intermediates that do not constrain policy mapping or path length.
Certificate authorities SHOULD NOT issue certificates with the policy mappings extension. Applications maintaining policies for accepted trust anchors are RECOMMENDED to forbid this extension in participating CAs, as inhibiting policy mapping mitigates the attack and simplifies implementations.
Computing the valid_policy_tree from valid_policy_graph (by recursively duplicating every multi-parent node) is NOT RECOMMENDED because this computation may consume exponential time and memory. Implementations that require it for legacy compatibility SHOULD mitigate DoS attacks by other means such as limiting tree depth or size.
If policy checking is disabled entirely as a mitigation, critical policy-related extensions—notably the policy constraints extension (RFC 5280 Section 4.2.1.11)—MUST be treated as unrecognized extensions per RFC 5280 Section 4.2 and the certificate MUST be rejected.
Path processing succeeds if either explicit_policy is greater than zero or the user_constrained_policy_set is not empty. This replaces the RFC 5280 condition that checked valid_policy_tree for non-NULL.
X.509 implementations MAY omit policy qualifiers from the output to simplify processing, consistent with RFC 5280's existing recommendation that CAs omit qualifiers from policy information terms.
X.509 implementations SHOULD NOT output the entire valid_policy_tree structure; instead they SHOULD limit output to just the set of authorities-constrained and/or user-constrained policies as described in X.509, because computing the full tree reintroduces the denial-of-service vulnerability.
X.509 implementations SHOULD perform policy validation by building a policy graph following the procedure described in Section 5 rather than the policy tree defined in RFC 5280. This replacement computes the same valid policies but avoids exponential resource consumption.
X.509 validators SHOULD verify signatures in certification paths before or in conjunction with policy verification. This limits exploitability of the exponential-growth attack to entities controlling CA certificates.
The user_constrained_policy_set replaces valid_policy_tree as a primary output. It is computed from valid_policy_node_set (leaf nodes not under anyPolicy plus any depth-n anyPolicy node), producing authority_constrained_policy_set, then filtered by user-initial-policy-set and augmented with anyPolicy-qualified entries if needed.
The valid_policy_graph is a directed acyclic graph replacing the valid_policy_tree. Each node contains a valid_policy OID, a qualifier_set, and an expected_policy_set. Nodes at depth x have zero or more children at depth x+1 and one or more parents at depth x-1 (except depth zero). The initial state is a single anyPolicy node at depth zero.
The valid_policy_graph satisfies four invariants: (1) at most one node per depth per policy OID; (2) a node with valid_policy anyPolicy always has expected_policy_set {anyPolicy}; (3) a non-root anyPolicy node has exactly one parent whose valid_policy is also anyPolicy; (4) a node cannot simultaneously be a child of both anyPolicy and a non-anyPolicy OID.
The valid_policy_tree algorithm in RFC 5280 Section 6.1 can grow exponentially in the depth of the certification path. An attacker can craft a certificate chain where every intermediate asserts two policies with full Cartesian-product mappings, causing the tree to double at each depth level, enabling denial-of-service attacks such as CVE-2023-0464 and CVE-2023-23524.
Step (b) of Section 6.1.4 processes policy mappings: (1) if policy_mapping > 0 and ID-P has a node at depth i, update its expected_policy_set to the subjectDomainPolicy values; (2) if policy_mapping > 0 and no node for ID-P but anyPolicy node exists, generate a child; (3) if policy_mapping == 0, delete the ID-P node and prune childless ancestors.
Step (d) of Section 6.1.3 processing: for each non-anyPolicy certificate policy P, find parent_nodes at depth i-1 whose expected_policy_set contains P-OID and create a single merged child node; if no match, fall back to anyPolicy parent if present. Step (d)(2) handles anyPolicy in the certificate policies extension. Step (d)(3) prunes nodes at depth i-1 or less that have no children by repeated deletion.