1.1.Summary of Changes from RFC 5280

The algorithm for processing certificate policies and policy mappings is replaced with one that builds an equivalent but much more efficient structure. This new algorithm does not change the validity status of any certification path or which certificate policies are valid for it.¶

3.1.Policy Trees

Section 6.1.2 of [RFC5280] constructs thevalid_policy_tree, a tree of certificate policies, during certification path validation. The nodes at any given depth in the tree correspond to policies asserted by a certificate in the certification path. A node's parent policy is the policy in the issuer certificate that was mapped to this policy, and a node's children are the policies the node was mapped to in the subject certificate.¶

For example, suppose a certification path contains:¶

• An intermediate certificate that asserts the following policy OIDs: OID1, OID2, and OID5. It contains mappings from OID1 to OID3 and from OID1 to OID4.¶
• An end-entity certificate that asserts the following policy OIDs: OID2, OID3, and OID6.¶

This would result in the tree shown below. Note that OID5 and OID6 are not included or mapped across the whole path, so they do not appear in the final structure.¶

The complete algorithm for building this structure is described in steps (d), (e), and (f) inSection 6.1.3 of [RFC5280]; steps (h), (i), and (j) inSection 6.1.4 of [RFC5280]; and steps (a), (b), and (g) inSection 6.1.5 of [RFC5280].¶

3.2.Exponential Growth

Thevalid_policy_tree grows exponentially in the worst case. In step (d.1) inSection 6.1.3 of [RFC5280], a single policy P can produce multiple child nodes if multiple issuer policies map to P. This can cause the tree size to increase in size multiplicatively at each level.¶

In particular, consider a certificate chain where every intermediate certificate asserts policies OID1 and OID2 and then contains the full Cartesian product of mappings:¶

• OID1 maps to OID1¶

• OID1 maps to OID2¶

• OID2 maps to OID1¶

• OID2 maps to OID2¶

At each depth, the tree would double in size.For example, if there are two intermediate certificates and one end-entity certificate, the resulting tree would be as depicted inFigure 1.¶

3.3.Attack Vector

An attacker can use the exponential growth to mount a denial-of-service attack against an X.509-based application. The attacker sends a certificate chain as described inSection 3.2 and triggers the target application's certificate validation process. For example, the target application may be a TLS server[RFC8446] that performs client certificate validation. The target application will consume far more resources processing the input than the attacker consumed to send it, which prevents the target application from servicing other clients.¶

4.1.Policy Graphs

The tree structure in[RFC5280] is an unnecessarily inefficient representation of a certification path's policy mappings. When multiple issuer policies map to a single subject policy, the subject policy will correspond to multiple duplicate nodes in the policy tree. Children of the subject policy are then duplicated recursively. This duplication is the source of the exponential growth described inSection 3.2.¶

A policy graph represents the same information with a directed acyclic graph of policy nodes. It eliminates this duplication by using a single node with multiple parents. SeeSection 5 for the procedure for building this structure.Figure 2 shows the updated representation of the example inFigure 1.¶

This graph's size is bounded linearly by the total number of certificate policies (Section 4.2.1.4 of [RFC5280]) and policy mappings (Section 4.2.1.5 of [RFC5280]). The policy tree in[RFC5280] is the tree of all paths from the root to a leaf in the policy graph, so no information is lost in the graph representation.¶

4.2.Verification Outputs

Section 6.1.6 of [RFC5280] describes the entirevalid_policy_tree structure as an output of the verification process. However, Section 12.2 of[X.509] only describes the following as outputs: the authorities-constrained policies, the user-constrained policies, and their associated qualifiers.¶

As thevalid_policy_tree is the exponential structure, computing it reintroduces the denial-of-service vulnerability. X.509 implementationsSHOULD NOT output the entirevalid_policy_tree structure; instead, theySHOULD limit output to just the set of authorities-constrained and/or user-constrained policies, as described in[X.509]. Sections5.6 and6 discuss other mitigations for applications where this option is not available.¶

X.509 implementationsMAY omit policy qualifiers from the output to simplify processing. Note thatSection 4.2.1.4 of [RFC5280] already recommends that certification authorities omit policy qualifiers from policy information terms.¶

5.1.Updates to Section 6.1

Section 6.1 of [RFC5280] is updated as follows:¶

OLD:¶

A particular certification path may not, however, be appropriate for all applications. Therefore, an applicationMAY augment this algorithm to further limit the set of valid paths. The path validation process also determines the set of certificate policies that are valid for this path, based on the certificate policies extension, policy mappings extension, policy constraints extension, and inhibit anyPolicy extension. To achieve this, the path validation algorithm constructs a valid policy tree. If the set of certificate policies that are valid for this path is not empty, then the result will be a valid policy tree of depth n, otherwise the result will be a null valid policy tree.¶

NEW:¶

A particular certification path may not, however, be appropriate for all applications. Therefore, an applicationMAY augment this algorithm to further limit the set of valid paths. The path validation process also determines the set of certificate policies that are valid for this path, based on the certificate policies extension, policy mappings extension, policy constraints extension, and inhibit anyPolicy extension. To achieve this, the path validation algorithm constructs a valid policy set, which may be empty if no certificate policies are valid for this path.¶

5.2.Updates to Section 6.1.2

The following replaces entry (a) inSection 6.1.2 of [RFC5280]:¶

(a)

valid_policy_graph: A directed acyclic graph of certificate policies with their optional qualifiers; each of the leaves of the graph represents a valid policy at this stage in the certification path validation. If valid policies exist at this stage in the certification path validation, the depth of the graph is equal to the number of certificates in the chain that have been processed. If valid policies do not exist at this stage in the certification path validation, the graph is set to NULL. Once the graph is set to NULL, policy processing ceases. ImplementationsMAY omit qualifiers if not returned in the output.¶

Each node in thevalid_policy_graph includes three data objects: the valid policy, a set of associated policy qualifiers, and a set of one or more expected policy values.¶

Nodes in the graph can be divided into depths, numbered starting from zero. A node at depth x can have zero or more children at depth x+1 and, with the exception of depth zero, one or more parents at depth x-1. No other edges between nodes may exist.¶

If the node is at depth x, the components of the node have the following semantics:¶

(1)

Thevalid_policy is a single policy OID representing a valid policy for the path of length x.¶

(2)

Thequalifier_set is a set of policy qualifiers associated with the valid policy in certificate x. It is only necessary to maintain this field if policy qualifiers are returned to the application. See Section 6.1.5, step (g).¶

(3)

Theexpected_policy_set contains one or more policy OIDs that would satisfy this policy in the certificate x+1.¶

The initial value of thevalid_policy_graph is a single node withvalid_policy anyPolicy, an emptyqualifier_set, and anexpected_policy_set with the single value anyPolicy. This node is considered to be at depth zero.¶

The graph additionally satisfies the following invariants:¶

• For any depth x and policy OID P-OID, there is at most one node at depth x whosevalid_policy is P-OID.¶

• Theexpected_policy_set of a node whosevalid_policy is anyPolicy is always {anyPolicy}.¶

• A node at depth x whosevalid_policy is anyPolicy, except for the one at depth zero, always has exactly one parent: a node at depth x-1 whosevalid_policy is also anyPolicy.¶

• Each node at depth greater than 0 has either one or more parent nodes whosevalid_policy is not anyPolicy or a single parent node whosevalid_policy is anyPolicy. That is, a node cannot simultaneously be a child of both anyPolicy and some non-anyPolicy OID.¶

Figure 3 is a graphic representation of the initial state of thevalid_policy_graph. Additional figures will use this format to describe changes in thevalid_policy_graph during path processing.¶

¶

5.3.Updates to Section 6.1.3

The following replaces steps (d), (e), and (f) inSection 6.1.3 of [RFC5280]:¶

(d)

If the certificate policies extension is present in the certificate and thevalid_policy_graph is not NULL, process the policy information by performing the following steps in order:¶

(1)

For each policy P not equal to anyPolicy in the certificate policies extension, let P-OID denote the OID for policy P and P-Q denote the qualifier set for policy P. Perform the following steps in order:¶

(i)

Letparent_nodes be the nodes at depth i-1 in thevalid_policy_graph where P-OID is in theexpected_policy_set. Ifparent_nodes is not empty, create a child node as follows: set thevalid_policy to P-OID, set thequalifier_set to P-Q, set theexpected_policy_set to {P-OID}, and set the parent nodes toparent_nodes.¶

For example, consider avalid_policy_graph with a node of depth i-1 where theexpected_policy_set is {Gold, White} and a second node where theexpected_policy_set is {Gold, Yellow}. Assume the certificate policies Gold and Silver appear in the certificate policies extension of certificate i. The Gold policy is matched, but the Silver policy is not. This rule will generate a child node of depth i for the Gold policy. The result is shown asFigure 4.¶

¶

(ii)

If there was no match in step (i) and thevalid_policy_graph includes a node of depth i-1 with thevalid_policy anyPolicy, generate a child node with the following values: set thevalid_policy to P-OID, set thequalifier_set to P-Q, set theexpected_policy_set to {P-OID}, and set the parent node to the anyPolicy node at depth i-1.¶

For example, consider avalid_policy_graph with a node of depth i-1 where thevalid_policy is anyPolicy. Assume the certificate policies Gold and Silver appear in the certificate policies extension of certificate i. The Gold policy does not have a qualifier, but the Silver policy has the qualifier Q-Silver. If Gold and Silver were not matched in (i) above, this rule will generate two child nodes of depth i, one for each policy. The result is shown asFigure 5.¶

¶

(2)

If the certificate policies extension includes the policy anyPolicy with the qualifier set AP-Q and either (a)inhibit_anyPolicy is greater than 0 or (b) i<n and the certificate is self-issued, then:¶

For each policy OID P-OID (including anyPolicy) that appears in theexpected_policy_set of some node in thevalid_policy_graph for depth i-1, if P-OID does not appear as thevalid_policy of some node at depth i, create a single child node with the following values: set thevalid_policy to P-OID, set thequalifier_set to AP-Q, set theexpected_policy_set to {P-OID}, and set the parents to the nodes at depth i-1 where P-OID appears inexpected_policy_set.¶

This is equivalent to running step (1) above as if the certificate policies extension contained a policy with OID P-OID and qualifier set AP-Q.¶

For example, consider avalid_policy_graph with a node of depth i-1 where theexpected_policy_set is {Gold, Silver} and a second node of depth i-1 where theexpected_policy_set is {Gold}. Assume anyPolicy appears in the certificate policies extension of certificate i with policy qualifiers AP-Q, but Gold and Silver do not appear. This rule will generate two child nodes of depth i, one for each policy. The result is shown below asFigure 6.¶

¶

(3)

If there is a node in thevalid_policy_graph of depth i-1 or less without any child nodes, delete that node.Repeat this step until there are no nodes of depth i-1 or less without children.¶

For example, consider thevalid_policy_graph shown inFigure 7 below.The two nodes at depth i-1 that are marked with an 'X' have no children, and they are deleted.Applying this rule to the resulting graph will cause the nodes at depth i-2 that is marked with a 'Y' to be deleted.In the resulting graph, there are no nodes of depth i-1 or less without children, and this step is complete.¶

¶

(e)

If the certificate policies extension is not present, set thevalid_policy_graph to NULL.¶

(f)

Verify that eitherexplicit_policy is greater than 0 or thevalid_policy_graph is not equal to NULL.¶

The text following step (f) inSection 6.1.3 of [RFC5280], beginning with "If any of steps (a), (b), (c), or (f) fails", is left unmodified.¶

5.4.Updates to Section 6.1.4

The following replaces step (b) inSection 6.1.4 of [RFC5280]:¶

(b)

If a policy mappings extension is present, then for each issuerDomainPolicy ID-P in the policy mappings extension:¶

(1)

If thepolicy_mapping variable is greater than 0 and there is anode in thevalid_policy_graph of depth i where ID-P is thevalid_policy, setexpected_policy_set to the set ofsubjectDomainPolicy values that are specified asequivalent to ID-P by the policy mappings extension.¶

(2)

If thepolicy_mapping variable is greater than 0 and no node of depth i in thevalid_policy_graph has avalid_policy of ID-P but there is a node of depth i with avalid_policy of anyPolicy, then generate a child node ofthe node of depth i-1 that has avalid_policy of anyPolicyas follows:¶

(i)

set thevalid_policy to ID-P;¶

(ii)

set thequalifier_set to the qualifier set of thepolicy anyPolicy in the certificate policiesextension of certificate i; and¶

(iii)

set theexpected_policy_set to the set ofsubjectDomainPolicy values that are specified asequivalent to ID-P by the policy mappings extension.¶

(3)

If thepolicy_mapping variable is equal to 0:¶

(i)

delete the node, if any, of depth i in thevalid_policy_graph where ID-P is thevalid_policy.¶

(ii)

If there is a node in thevalid_policy_graph of depthi-1 or less without any child nodes, delete thatnode. Repeat this step until there are no nodes ofdepth i-1 or less without children.¶

5.5.Updates to Section 6.1.5

The following replaces step (g) inSection 6.1.5 of [RFC5280]:¶

(g)

Calculate theuser_constrained_policy_set as follows.Theuser_constrained_policy_set is a set of policy OIDs, along with associated policy qualifiers.¶

(1)

If thevalid_policy_graph is NULL, setvalid_policy_node_set to the empty set.¶

(2)

If thevalid_policy_graph is not NULL, setvalid_policy_node_set to the set of policy nodeswhosevalid_policy is not anyPolicy andwhose parent list is a single node withvalid_policy of anyPolicy.¶

(3)

If thevalid_policy_graph is not NULL and contains a node of depth n with thevalid_policy anyPolicy, add it tovalid_policy_node_set.¶

(4)

Computeauthority_constrained_policy_set, a set of policy OIDs and associated qualifiers as follows. For each node invalid_policy_node_set:¶

(i)

Add the node'svalid_policy toauthority_constrained_policy_set.¶

(ii)

Collect all qualifiers in the node, its ancestors, and descendants and associate them withvalid_policy. Applications that do not use policy qualifiersMAY skip this step to simplify processing.¶

(5)

Setuser_constrained_policy_set toauthority_constrained_policy_set.¶

(6)

If the user-initial-policy-set is not anyPolicy:¶

(i)

Remove any elements ofuser_constrained_policy_set that do not appear in user-initial-policy-set.¶

(ii)

If anyPolicy appears inauthority_constrained_policy_set with qualifiers AP-Q, for each OID P-OID in user-initial-policy-set that does not appear inuser_constrained_policy_set, add P-OID with qualifiers AP-Q touser_constrained_policy_set.¶

In addition, the final paragraph inSection 6.1.5 of [RFC5280] is updated as follows:¶

OLD:¶

If either (1) the value ofexplicit_policy variable is greater than zero or (2) thevalid_policy_tree is not NULL, then path processing has succeeded.¶

NEW:¶

If either (1) the value ofexplicit_policy is greater than zero, or (2) theuser_constrained_policy_set is not empty, then path processing has succeeded.¶

5.6.Updates to Section 6.1.6

The following replacesSection 6.1.6 of [RFC5280]:¶

If path processing succeeds, the procedure terminates, returning a success indication together with the final value of theuser_constrained_policy_set, theworking_public_key, theworking_public_key_algorithm, and theworking_public_key_parameters.¶

Note that the original procedure described in[RFC5280] included avalid_policy_tree structure as part of the output. This structure grows exponentially in the size of the input, so computing it risks denial-of-service vulnerabilities in X.509-based applications, such as[CVE-2023-0464] and[CVE-2023-23524]. Accordingly, this output is deprecated. Computing this structure isNOT RECOMMENDED.¶

An implementation that requiresvalid_policy_tree for compatibility with legacy systems may compute it fromvalid_policy_graph by recursively duplicating every multi-parent node. This may be done on-demand when the calling application first requests this output. However, this computation may consume exponential time and memory, so such implementationsSHOULD mitigate denial-of-service attacks in other ways, such as by limiting the depth or size of the tree.¶

6.1.Verify Signatures First

X.509 validatorsSHOULD verify signatures in certification paths before or inconjunction with policy verification. This limits the attack to entities incontrol of CA certificates. For some applications, this may be sufficient tomitigate the attack. However, other applications may still be impacted, forexample:¶

• Any application that evaluates an untrusted PKI, such as a hosting provider that evaluates a customer-supplied PKI¶

• Any application that evaluates an otherwise trusted PKI that includes untrusted entities with technically constrained intermediate certificates. If the intermediates do not constrain policy mapping or path length, those entities may be able to perform this attack.¶

6.2.Limit Certificate Depth

The policy tree grows exponentially in the depth of a certification path, so limiting the depth and certificate size can mitigate the attack.¶

However, this option may not be viable for all applications. Too low of a limit may reject existing paths that the application wishes to accept. Too high of a limit may still admit a denial-of-service attack for the application. By modifying the example inSection 3.2 to increase the number of policies asserted in each certificate, an attacker could still achieve O(N^(depth/2)) scaling.¶

6.3.Limit Policy Tree Size

The attack can be mitigated by limiting the number of nodes in the policy tree and rejecting the certification path if this limit is reached. This limit should be set high enough to still admit existing valid certification paths for the application but low enough to no longer admit a denial-of-service attack.¶

6.4.Inhibit Policy Mapping

If policy mapping is disabled via the initial-policy-mapping-inhibit setting(seeSection 6.1.1 of [RFC5280]), the attack is mitigated. This alsosignificantly simplifies the X.509 implementation, which reduces the risk ofother security bugs. However, this will break compatibility with any existingcertification paths that rely on policy mapping.¶

To facilitate this mitigation, certificate authoritiesSHOULD NOT issuecertificates with the policy mappings extension (Section 4.2.1.5 of [RFC5280]). Applications maintaining policies for accepted trust anchors areRECOMMENDED to forbid this extension in participating certificate authorities.¶

6.5.Disable Policy Checking

An X.509 validator can mitigate this attack by disabling policy validationentirely. This may be viable for applications that do not require policyvalidation. In this case, critical policy-related extensions, notably the policyconstraints extension (Section 4.2.1.11 of [RFC5280]),MUST be treated as unrecognizedextensions as described inSection 4.2 of [RFC5280] and be rejected.¶