RFC 9618
Updates to X.509 Policy Validation
RFC 9618: Updates to X.509 Policy Validation 🎀
Okay bestie, this one is about X.509 policy validation 💅 It's from the IETF, written by D. Benjamin at Google LLC, and published in August 2024 as a Standards Track document, so it's an official Internet standard, not just vibes. It's ISSN 2070-1721. It updates RFC 5280, the big X.509 certificate spec, and the header doesn't list anything it obsoletes 🦋
Abstract ✨
This doc updates RFC 5280 and swaps out the algorithm for X.509 policy validation with one that gives the same results but is way more efficient 🔥 The old algorithm built a structure that could blow up exponentially in the worst case, so implementations were open to denial-of-service attacks 😭
Status of This Memo 🌸
This is an Internet Standards Track document.
This document is a product of the Internet Engineering Task Force (IETF). It represents the consensus of the IETF community. It went through public review and got approved for publication by the Internet Engineering Steering Group (IESG). For more on Internet Standards, check out Section 2 of RFC 7841.
Info about the current status of this document, any errata, and how to send feedback is at https://www.rfc-editor.org/info/rfc9618 🧚
Copyright Notice 💜
Copyright (c) 2024 IETF Trust and the persons identified as the document authors. All rights reserved.
This document is subject to BCP 78 and the IETF Trust's Legal Provisions Relating to IETF Documents (https://trustee.ietf.org/license-info) as they stand on the publication date. Please read these carefully, because they explain your rights and restrictions for this document. Code Components pulled out of this document must include Revised BSD License text as described in Section 4.e of the Trust Legal Provisions, and they come without warranty, as described in the Revised BSD License 🫶
Table of Contents 🍓
1. Introduction
1.1. Summary of Changes from RFC 5280
2. Conventions and Definitions
3. Denial-of-Service Vulnerability
3.1. Policy Trees
3.2. Exponential Growth
3.3. Attack Vector
4. Avoiding Exponential Growth
4.1. Policy Graphs
4.2. Verification Outputs
5. Updates to RFC 5280
5.1. Updates to Section 6.1
5.2. Updates to Section 6.1.2
5.3. Updates to Section 6.1.3
5.4. Updates to Section 6.1.4
5.5. Updates to Section 6.1.5
5.6. Updates to Section 6.1.6
6. Other Mitigations
6.1. Verify Signatures First
6.2. Limit Certificate Depth
6.3. Limit Policy Tree Size
6.4. Inhibit Policy Mapping
6.5. Disable Policy Checking
7. Security Considerations
8. IANA Considerations
9. References
9.1. Normative References
9.2. Informative References
Acknowledgements
Author's Address1. Introduction 💖
[RFC5280] defines a whole suite of extensions for figuring out which policies apply to a certification path. A policy is described by an object identifier (OID) plus a set of optional qualifiers.
Policy validation in [RFC5280] is complicated, so let me give you the tea ☕ The certificate policies extension (Section 4.2.1.4 of [RFC5280]) lists the policies, with optional qualifiers, that an individual certificate was issued under. The policy mappings extension (Section 4.2.1.5 of [RFC5280]) lets a CA certificate map its policy OIDs to other policy OIDs in the certificates it issues. Taking those mappings and other extensions into account, the certification path's overall policy set is the intersection of the policies asserted by each certificate in the path ✨
The procedure in Section 6.1 of [RFC5280] works out that set during certification path validation. It builds a policy tree holding the policies each certificate asserts plus the mappings between them. This tree can grow exponentially with the depth of the certification path, which means an attacker can send a small input and make a path validator burn through excessive memory and computing resources 💀 That cost asymmetry can lead to a denial-of-service vulnerability in X.509-based applications, like [CVE-2023-0464] and [CVE-2023-23524].
Section 3 describes this vulnerability. Section 4.1 describes the main fix, which is replacing the policy tree structure. Section 5 has the updates to [RFC5280] that make that change happen. And finally, Section 6 talks about other mitigation strategies for X.509 applications 🦋
1.1. Summary of Changes from RFC 5280 🌈
The algorithm for processing certificate policies and policy mappings gets replaced with one that builds an equivalent but way more efficient structure. The new algorithm doesn't change whether any certification path is valid or which certificate policies are valid for it 🙌
2. Conventions and Definitions 📝
The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT", "SHOULD", "SHOULD NOT", "RECOMMENDED", "NOT RECOMMENDED", "MAY", and "OPTIONAL" in this document are to be interpreted as described in BCP 14 [RFC2119] [RFC8174] when, and only when, they appear in all capitals, as shown here.
3. Denial-of-Service Vulnerability 😭
This section is about how the path validation algorithm in Section 6.1.2 of [RFC5280] can lead to a denial-of-service vulnerability in X.509-based applications.
3.1. Policy Trees 🌳
Section 6.1.2 of [RFC5280] builds the valid_policy_tree, a tree of certificate policies, during certification path validation. The nodes at any given depth in the tree match up with the policies asserted by a certificate in the certification path. A node's parent policy is the policy in the issuer certificate that got mapped to this policy, and a node's children are the policies that the node got mapped to in the subject certificate.
For example, say a certification path contains:
- An intermediate certificate that asserts these policy OIDs: OID1, OID2, and OID5. It has mappings from OID1 to OID3 and from OID1 to OID4.
- An end-entity certificate that asserts these policy OIDs: OID2, OID3, and OID6.
This gives you the tree below. Notice that OID5 and OID6 aren't included or mapped across the whole path, so they don't show up in the final structure 👀
+-----------+
Root: | anyPolicy |
+-----------+
|{anyPolicy}|
+-----------+
/ \
/ \
v v
+------------+ +------------+
Intermediate: | OID1 | | OID2 |
(OID5 discarded) +------------+ +------------+
|{OID3, OID4}| | {OID2} |
+------------+ +------------+
| |
| |
v v
+------------+ +------------+
End-entity: | OID3 | | OID2 |
(OID6 discarded) +------------+ +------------+The full algorithm for building this structure is in steps (d), (e), and (f) of Section 6.1.3 of [RFC5280], steps (h), (i), and (j) of Section 6.1.4 of [RFC5280], and steps (a), (b), and (g) of Section 6.1.5 of [RFC5280].
3.2. Exponential Growth 📈
The valid_policy_tree grows exponentially in the worst case. In step (d.1) of Section 6.1.3 of [RFC5280], a single policy P can produce multiple child nodes if multiple issuer policies map to P. That means the tree can multiply in size at every level 😱
Here's a specific case: a certificate chain where every intermediate certificate asserts policies OID1 and OID2, 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 looks like Figure 1 🌸
+-----------------------+
| anyPolicy |
+-----------------------+
| {anyPolicy} |
+-----------------------+
/ \
/ \
v v
+------------+ +------------+
| OID1 | | OID2 |
+------------+ +------------+
|{OID1, OID2}| |{OID1, OID2}|
+------------+ +------------+
/ \ / \
/ \ / \
v v v v
+------------+ +------------+ +------------+ +------------+
| OID1 | | OID2 | | OID1 | | OID2 |
+------------+ +------------+ +------------+ +------------+
|{OID1, OID2}| |{OID1, OID2}| |{OID1, OID2}| |{OID1, OID2}|
+------------+ +------------+ +------------+ +------------+
| | | | | | | |
v v v v v v v v
+------+ +------+ +------+ +------+ +------+ +------+ +------+ +------+
| OID1 | | OID2 | | OID1 | | OID2 | | OID1 | | OID2 | | OID1 | | OID2 |
+------+ +------+ +------+ +------+ +------+ +------+ +------+ +------+Figure 1: An Example X.509 Policy Tree with Exponential Growth
3.3. Attack Vector 🏹
An attacker can use that exponential growth to run a denial-of-service attack against an X.509-based application. The attacker sends a certificate chain like the one in Section 3.2 and sets off the target application's certificate validation process. For example, the target application might be a TLS server [RFC8446] that does client certificate validation. The target application ends up using way more resources to process the input than the attacker spent sending it, and that stops it from serving other clients 😤
4. Avoiding Exponential Growth 🦄
This document fixes the denial-of-service vulnerability from Section 3 by replacing the policy tree with a policy graph structure, which is covered in this section. The policy graph grows linearly instead of exponentially, and that removes the lopsided cost in policy validation ✨
X.509 implementations SHOULD perform policy validation by building a policy graph, following the procedure in Section 5. This replacement procedure computes the same policies as [RFC5280], but one of the outputs is in a different form. See Section 4.2 for details. Section 6 describes alternative mitigations for implementations that depend on the original, exponential-sized output 💜
4.1. Policy Graphs 🌳✨
okay so the tree in [RFC5280] is lowkey too much 💀 when a bunch of issuer policies all map to one subject policy, that subject policy shows up as multiple duplicate nodes in the policy tree. And then its children get copied over and over, recursively. That copy-paste situation is literally where the exponential growth from Section 3.2 comes from 😭
a policy graph fixes this with a directed acyclic graph of policy nodes. Instead of duplicating, it uses one node with multiple parents 🦋 Section 5 explains how to build it. Figure 2 shows how the example from Figure 1 looks after the glow-up:
+-----------+
| anyPolicy |
+-----------+
|{anyPolicy}|
+-----------+
/ \
/ \
v v
+------------+ +------------+
| OID1 | | OID2 |
+------------+ +------------+
|{OID1, OID2}| |{OID1, OID2}|
+------------+ +------------+
| \ / |
| \ / |
| \/ |
| /\ |
| / \ |
v v v v
+------------+ +------------+
| OID1 | | OID2 |
+------------+ +------------+
|{OID1, OID2}| |{OID1, OID2}|
+------------+ +------------+
| \ / |
| \ / |
| \/ |
| /\ |
| / \ |
v v v v
+------------+ +------------+
| OID1 | | OID2 |
+------------+ +------------+
Figure 2: A More Efficient Representation of an X.509 Policy Treethe graph's size grows linearly with the total number of certificate policies (Section 4.2.1.4 of [RFC5280]) and policy mappings (Section 4.2.1.5 of [RFC5280]) 📈 and the policy tree from [RFC5280] is just the tree of all paths from the root to a leaf in the policy graph. so nothing gets lost in the graph version, periodt 🫶
4.2. Verification Outputs 🎀
Section 6.1.6 of [RFC5280] describes the whole valid_policy_tree structure as an output of verification. BUT (and this is the tea ☕) Section 12.2 of [X.509] only lists these as outputs: the authorities-constrained policies, the user-constrained policies, and their associated qualifiers.
ngl this matters a LOT. the valid_policy_tree is the exponential structure, so computing it brings the denial-of-service vulnerability right back 😱 X.509 implementations SHOULD NOT output the entire valid_policy_tree structure. instead, they SHOULD limit their output to just the set of authorities-constrained and/or user-constrained policies, as described in [X.509]. Sections 5.6 and 6 cover other mitigations for apps where this option isn't available 🛡️
X.509 implementations MAY omit policy qualifiers from the output to simplify processing. also, Section 4.2.1.4 of [RFC5280] already recommends that certification authorities omit policy qualifiers from policy information terms 💅
5. Updates to RFC 5280 🔥
this section has the actual updates to [RFC5280], and they implement the changes from Section 4. let's gooo 🚀
5.1. Updates to Section 6.1 💖
Section 6.1 of [RFC5280] gets updated like this:
OLD:
| A particular certification path may not, however, be appropriate
| for all applications. Therefore, an application MAY 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 application MAY 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 🦋
this one replaces entry (a) in Section 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. Implementations MAY omit qualifiers if
| not returned in the output.
|
| Each node in the valid_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) The valid_policy is a single policy OID representing a
| valid policy for the path of length x.
|
| (2) The qualifier_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) The expected_policy_set contains one or more policy OIDs
| that would satisfy this policy in the certificate x+1.
|
| The initial value of the valid_policy_graph is a single node
| with valid_policy anyPolicy, an empty qualifier_set, and an
| expected_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 whose valid_policy is P-OID.
|
| * The expected_policy_set of a node whose valid_policy is
| anyPolicy is always {anyPolicy}.
|
| * A node at depth x whose valid_policy is anyPolicy, except
| for the one at depth zero, always has exactly one parent:
| a node at depth x-1 whose valid_policy is also anyPolicy.
|
| * Each node at depth greater than 0 has either one or more
| parent nodes whose valid_policy is not anyPolicy or a
| single parent node whose valid_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
| the valid_policy_graph. Additional figures will use this
| format to describe changes in the valid_policy_graph during
| path processing.
|
| +----------------+
| | anyPolicy | <---- valid_policy
| +----------------+
| | {} | <---- qualifier_set
| +----------------+
| | {anyPolicy} | <---- expected_policy_set
| +----------------+
|
| Figure 3: Initial Value of the valid_policy_graph State
| Variable5.3. Updates to Section 6.1.3 ✨
okay bestie, this one is the big one 💅 we're replacing steps (d), (e), and (f) in Section 6.1.3 of [RFC5280]. so step (d) is where all the policy tree drama happens 🌳
Step (d): if the certificate policies extension is in the certificate AND the valid_policy_graph is not NULL, we process the policy info by doing the following steps in order 🫶
- (1) for each policy
Pthat is notanyPolicyin the certificate policies extension, we letP-OIDbe the OID for policyPandP-Qbe the qualifier set for policyP. then we do these steps in order:- (i) we look at the nodes at depth
i-1in thevalid_policy_graphwhereP-OIDis in theexpected_policy_set. ifparent_nodesisn't empty, we make a child node:valid_policygetsP-OID,qualifier_setgetsP-Q,expected_policy_setgets{P-OID}, andparent nodesgetsparent_nodes. 🎀
- (i) we look at the nodes at depth
picture this: there's a depth i-1 node with expected_policy_set of {Gold, White}, and another one with {Gold, Yellow}. certificate i has the policies Gold and Silver in its certificate policies extension. Gold matches but Silver doesn't, so this rule makes a child node of depth i for Gold. it's giving Figure 4 energy ✨
+-----------------+ +-----------------+
| Red | | Blue |
+-----------------+ +-----------------+
| {} | | {} | depth i-1
+-----------------+ +-----------------+
| {Gold, White} | | {Gold, Yellow} |
+-----------------+ +-----------------+
\ /
\ /
\ /
v v
+-----------------+
| Gold |
+-----------------+
| {} | depth i
+-----------------+
| {Gold} |
+-----------------+
Figure 4: Processing an Exact Match- (ii) if there was no match in step (i) AND the
valid_policy_graphhas a node of depthi-1withvalid_policyanyPolicy, we generate a child node:valid_policygetsP-OID,qualifier_setgetsP-Q,expected_policy_setgets{P-OID}, and the parent node is theanyPolicynode at depthi-1. 🦋
example time: there's a depth i-1 node where valid_policy is anyPolicy. certificate i has Gold and Silver. Gold has no qualifier, but Silver has the qualifier Q-Silver. if neither was matched in (i), this rule makes two child nodes of depth i, one per policy. see Figure 5 👑
+-----------------+
| anyPolicy |
+-----------------+
| {} |
+-----------------+ depth i-1
| {anyPolicy} |
+-----------------+
/ \
/ \
/ \
v v
+-----------------+ +-----------------+
| Gold | | Silver |
+-----------------+ +-----------------+
| {} | | {Q-Silver} | depth i
+-----------------+ +-----------------+
| {Gold} | | {Silver} |
+-----------------+ +-----------------+
Figure 5: Processing Unmatched Policies When a
Leaf Node Specifies anyPolicy- (2) if the certificate policies extension includes the policy
anyPolicywith the qualifier setAP-Q, AND either (a)inhibit_anyPolicyis greater than 0 OR (b)i<nand the certificate is self-issued, then:
for each policy OID P-OID (including anyPolicy) that shows up in the expected_policy_set of some node in the valid_policy_graph for depth i-1, IF P-OID is NOT the valid_policy of any node at depth i, we create a single child node: valid_policy gets P-OID, qualifier_set gets AP-Q, expected_policy_set gets {P-OID}, and the parents are the depth i-1 nodes where P-OID shows up in expected_policy_set. ✨
this is basically the same as running step (1) above as if the certificate policies extension had a policy with OID P-OID and qualifier set AP-Q. 🫶
example: there's a depth i-1 node with expected_policy_set {Gold, Silver} and another depth i-1 node with {Gold}. certificate i has anyPolicy with the qualifiers AP-Q, but Gold and Silver don't show up. this rule makes two child nodes of depth i, one per policy. see Figure 6 below 🌸
+-----------------+ +-----------------+
| Red | | Blue |
+-----------------+ +-----------------+
| {} | | {} | depth i-1
+-----------------+ +-----------------+
| {Gold, Silver} | | {Gold} |
+-----------------+ +-----------------+
| \ |
| \ |
| \ |
| \ |
| \ |
v v v
+-----------------+ +-----------------+
| Silver | | Gold |
+-----------------+ +-----------------+
| {AP-Q} | | {AP-Q} | depth i
+-----------------+ +-----------------+
| {Silver} | | {Gold} |
+-----------------+ +-----------------+
Figure 6: Processing Unmatched Policies When the
Certificate Policies Extension Specifies anyPolicy- (3) if there's a node in the
valid_policy_graphof depthi-1or less with NO child nodes, delete that node. keep repeating this step until there are no nodes of depthi-1or less without children. 🧹
for example, check out the valid_policy_graph in Figure 7 below. the two depth i-1 nodes marked with an 'X' have no children, so they get deleted. then applying this rule to the new graph makes the depth i-2 node marked with a 'Y' get deleted too. after that there are no depth i-1 or less nodes without children, so this step is complete 💀
+-----------+
| | depth i-3
+-----------+
/ | \
/ | \
v v v
+-----------+ +-----------+ +-----------+
| | | | | Y | depth i-2
+-----------+ +-----------+ +-----------+
| \ | |
| \ | |
v v v v
+-----------+ +-----------+ +-----------+
| X | | | | X | depth i-1
+-----------+ +-----------+ +-----------+
/ | \
/ | \
v v v
+-----------+ +-----------+ +-----------+
| | | | | | depth i
+-----------+ +-----------+ +-----------+
Figure 7: Pruning the valid_policy_graphStep (e): if the certificate policies extension is NOT present, set the valid_policy_graph to NULL. 🙈
Step (f): verify that either explicit_policy is greater than 0 OR the valid_policy_graph is not equal to NULL. 🔥
the text after step (f) in Section 6.1.3 of [RFC5280], starting with "If any of steps (a), (b), (c), or (f) fails", stays EXACTLY as it is. no touching it 🙅♀️
5.4. Updates to Section 6.1.4
Okay so this one swaps out step (b) in Section 6.1.4 of [RFC5280] 💅 Here's the new version:
(b) If a policy mappings extension is present, then for each
issuerDomainPolicy ID-P in the policy mappings extension:
(1) If the policy_mapping variable is greater than 0 and
there is a node in the valid_policy_graph of depth i
where ID-P is the valid_policy, set expected_policy_set
to the set of subjectDomainPolicy values that are
specified as equivalent to ID-P by the policy mappings
extension.
(2) If the policy_mapping variable is greater than 0 and no
node of depth i in the valid_policy_graph has a
valid_policy of ID-P but there is a node of depth i with
a valid_policy of anyPolicy, then generate a child node
of the node of depth i-1 that has a valid_policy of
anyPolicy as follows:
(i) set the valid_policy to ID-P;
(ii) set the qualifier_set to the qualifier set of the
policy anyPolicy in the certificate policies
extension of certificate i; and
(iii) set the expected_policy_set to the set of
subjectDomainPolicy values that are specified as
equivalent to ID-P by the policy mappings
extension.
(3) If the policy_mapping variable is equal to 0:
(i) delete the node, if any, of depth i in the
valid_policy_graph where ID-P is the valid_policy.
(ii) If there is a node in the valid_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.5.5. Updates to Section 6.1.5
This replaces step (g) in Section 6.1.5 of [RFC5280], and it's giving very organized ✨
(g) Calculate the user_constrained_policy_set as follows. The
user_constrained_policy_set is a set of policy OIDs, along
with associated policy qualifiers.
(1) If the valid_policy_graph is NULL, set
valid_policy_node_set to the empty set.
(2) If the valid_policy_graph is not NULL, set
valid_policy_node_set to the set of policy nodes whose
valid_policy is not anyPolicy and whose parent list is a
single node with valid_policy of anyPolicy.
(3) If the valid_policy_graph is not NULL and contains a
node of depth n with the valid_policy anyPolicy, add it
to valid_policy_node_set.
(4) Compute authority_constrained_policy_set, a set of
policy OIDs and associated qualifiers as follows. For
each node in valid_policy_node_set:
(i) Add the node's valid_policy to
authority_constrained_policy_set.
(ii) Collect all qualifiers in the node, its ancestors,
and descendants and associate them with
valid_policy. Applications that do not use policy
qualifiers MAY skip this step to simplify
processing.
(5) Set user_constrained_policy_set to
authority_constrained_policy_set.
(6) If the user-initial-policy-set is not anyPolicy:
(i) Remove any elements of user_constrained_policy_set
that do not appear in user-initial-policy-set.
(ii) If anyPolicy appears in
authority_constrained_policy_set with qualifiers
AP-Q, for each OID P-OID in user-initial-policy-
set that does not appear in
user_constrained_policy_set, add P-OID with
qualifiers AP-Q to user_constrained_policy_set.Also, the final paragraph in Section 6.1.5 of [RFC5280] gets a glow-up too 🦋 Here's the before and after:
OLD:
If either (1) the value of explicit_policy variable is greater
than zero or (2) the valid_policy_tree is not NULL, then path
processing has succeeded.
NEW:
If either (1) the value of explicit_policy is greater than zero,
or (2) the user_constrained_policy_set is not empty, then path
processing has succeeded.5.6. Updates to Section 6.1.6
This replaces all of Section 6.1.6 of [RFC5280]. Here's the new version 💖
If path processing succeeds, the procedure terminates, returning a
success indication together with the final value of the
user_constrained_policy_set, the working_public_key, the
working_public_key_algorithm, and the
working_public_key_parameters.
Note that the original procedure described in [RFC5280] included a
valid_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
is NOT RECOMMENDED.
An implementation that requires valid_policy_tree for
compatibility with legacy systems may compute it from
valid_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 implementations SHOULD
mitigate denial-of-service attacks in other ways, such as by
limiting the depth or size of the tree.Quick heads-up: the old valid_policy_tree output is deprecated because it blows up exponentially, which is exactly how we get stuff like [CVE-2023-0464] and [CVE-2023-23524]. Yikes 😭
6. Other Mitigations ✨
X.509 implementations that are unable to switch to the policy graph structure SHOULD mitigate the denial-of-service attack in other ways. This section describes alternate mitigation and partial mitigation strategies 🌸
6.1. Verify Signatures First
X.509 validators SHOULD verify signatures in certification paths before or in conjunction with policy verification. This limits the attack to entities in control of CA certificates. For some applications, this may be sufficient to mitigate the attack. However, other applications may still be impacted, for example:
- 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 in Section 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 (see Section 6.1.1 of [RFC5280]), the attack is mitigated. This also significantly simplifies the X.509 implementation, which reduces the risk of other security bugs. However, this will break compatibility with any existing certification paths that rely on policy mapping.
To facilitate this mitigation, certificate authorities SHOULD NOT issue certificates with the policy mappings extension (Section 4.2.1.5 of [RFC5280]). Applications maintaining policies for accepted trust anchors are RECOMMENDED to forbid this extension in participating certificate authorities 🙈
6.5. Disable Policy Checking
An X.509 validator can mitigate this attack by disabling policy validation entirely. This may be viable for applications that do not require policy validation. In this case, critical policy-related extensions, notably the policy constraints extension (Section 4.2.1.11 of [RFC5280]), MUST be treated as unrecognized extensions as described in Section 4.2 of [RFC5280] and be rejected 💀
7. Security Considerations 🔥
Section 3 discusses how the policy tree algorithm in [RFC5280] can lead to denial-of-service vulnerabilities in X.509-based applications, such as [CVE-2023-0464] and [CVE-2023-23524]. This is a big deal, bestie 😭
Section 5 replaces this algorithm to avoid this issue. As discussed in Section 4.1, the new structure scales linearly with the input. This means input limits in X.509 validators will more naturally bound processing time, thus avoiding these vulnerabilities 👑
8. IANA Considerations
This document has no IANA actions. Nothing to register here, periodt 🎀
9. References
9.1. Normative References
[RFC2119] Bradner, S., "Key words for use in RFCs to Indicate
Requirement Levels", BCP 14, RFC 2119,
DOI 10.17487/RFC2119, March 1997,
<https://www.rfc-editor.org/info/rfc2119>.
[RFC5280] Cooper, D., Santesson, S., Farrell, S., Boeyen, S.,
Housley, R., and W. Polk, "Internet X.509 Public Key
Infrastructure Certificate and Certificate Revocation List
(CRL) Profile", RFC 5280, DOI 10.17487/RFC5280, May 2008,
<https://www.rfc-editor.org/info/rfc5280>.
[RFC8174] Leiba, B., "Ambiguity of Uppercase vs Lowercase in RFC
2119 Key Words", BCP 14, RFC 8174, DOI 10.17487/RFC8174,
May 2017, <https://www.rfc-editor.org/info/rfc8174>.9.2. Informative References
[CVE-2023-0464]
CVE, "Excessive Resource Usage Verifying X.509 Policy
Constraints", CVE-2023-0464, March 2023,
<https://www.cve.org/CVERecord?id=CVE-2023-0464>.
[CVE-2023-23524]
CVE, "Processing a maliciously crafted certificate may
lead to a denial-of-service", CVE-2023-23524, February
2023, <https://www.cve.org/CVERecord?id=CVE-2023-23524>.
[RFC8446] Rescorla, E., "The Transport Layer Security (TLS) Protocol
Version 1.3", RFC 8446, DOI 10.17487/RFC8446, August 2018,
<https://www.rfc-editor.org/info/rfc8446>.
[X.509] ITU-T, "Information technology - Open Systems
Interconnection - The Directory: Public-key and attribute
certificate frameworks", ITU-T Recommendation X.509,
October 2019, <https://www.itu.int/rec/T-REC-X.509>.Acknowledgements
The author thanks Bob Beck, Adam Langley, Matt Mueller, and Ryan Sleevi for many valuable discussions that led to discovering this issue, understanding it, and developing the mitigation. The author also thanks Martin Thomson, Job Snijders, and John Scudder for their review and feedback on this document 🫶
Author's Address
David Benjamin
Google LLC
Email: davidben@google.com📦 where this page comes from
- ietf: rfc9618 2024-08
- 💖 girlified by claude-haiku-5-5 on : a language model's rewrite of the original, under its terms