Internet-Draft | Updates to X.509 Policy Validation | January 2024 |
Benjamin | Expires 8 July 2024 | [Page] |
- Workgroup:
- Limited Additional Mechanisms for PKIX and SMIME
- Internet-Draft:
- draft-ietf-lamps-x509-policy-graph-03
- Updates:
- 5280 (if approved)
- Published:
- Intended Status:
- Standards Track
- Expires:
Updates to X.509 Policy Validation
Abstract
This document updates RFC 5280 to replace the algorithm for X.509 policy validation with an equivalent, more efficient algorithm. The original algorithm built a structure which scaled exponentially in the worst case, leaving implementations vulnerable to denial-of-service attacks.¶
Discussion Venues
This note is to be removed before publishing as an RFC.¶
Discussion of this document takes place on the Limited Additional Mechanisms for PKIX and SMIME Working Group mailing list (spasm@ietf.org), which is archived at https://mailarchive.ietf.org/arch/browse/spasm/.¶
Source for this draft and an issue tracker can be found at https://github.com/davidben/x509-policy-graph.¶
Status of This Memo
This Internet-Draft is submitted in full conformance with the provisions of BCP 78 and BCP 79.¶
Internet-Drafts are working documents of the Internet Engineering Task Force (IETF). Note that other groups may also distribute working documents as Internet-Drafts. The list of current Internet-Drafts is at https://datatracker.ietf.org/drafts/current/.¶
Internet-Drafts are draft documents valid for a maximum of six months and may be updated, replaced, or obsoleted by other documents at any time. It is inappropriate to use Internet-Drafts as reference material or to cite them other than as "work in progress."¶
This Internet-Draft will expire on 8 July 2024.¶
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) in effect on the date of publication of this document. Please review these documents carefully, as they describe your rights and restrictions with respect to this document. Code Components extracted from this document must include Revised BSD License text as described in Section 4.e of the Trust Legal Provisions and are provided without warranty as described in the Revised BSD License.¶
1. Introduction
[RFC5280] defines a suite of extensions for specifying certificate policies, along with a mechanism for mapping policies between subject and issuer policy domains in cross-certificates. This mechanism, when evaluated according to the algorithm in [RFC5280], Section 6.1 produces a policy tree, describing policies asserted by each certificate, and mappings between them. This tree can grow exponentially in the depth of the certification path. This cost asymmetry can lead to a denial-of-service vulnerability in X.509-based applications, such as [CVE-2023-0464] and [CVE-2023-23524].¶
Section 3 describes this vulnerability. Section 4.1 describes the primary mitigation for this vulnerability, a replacement for the policy tree structure. Section 5 provides updates to [RFC5280] which implement this change. Finally, Section 6 discusses alternative mitigation strategies for X.509 applications.¶
1.1. Summary of Changes from RFC 5280
The algorithm for processing certificate policies and policy mappings is replaced with one which builds an equivalent, but much more efficient structure. This new algorithm does not change the validity status of any certification path, nor 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 discusses how the path validation algorithm defined 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] constructs the valid_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 which was mapped to this
policy, and a node's children are the policies it was mapped to in the subject
certificate.¶
For example, suppose a certification path contains:¶
-
An intermediate certificate which asserts policy object identifiers (OIDs) OID1, OID2, and OID5. It contains mappings OID1 to OID3, and OID1 to OID4.¶
-
An end-entity certificate which asserts policy OIDs OID2, OID3, and OID6.¶
This would result in the tree shown in Figure 1. 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) of Section 6.1.3 of [RFC5280], steps (h), (i), (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. 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:¶
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 in Figure 2.¶
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 certificate chain as in Section 3.2 and triggers the target application's certificate validation process. For example, the target application may be a TLS [RFC8446] server that performs client certificate validation. The target application will consume far more resources processing the input than the attacker consumed to send it, preventing it from servicing other clients.¶
4. Avoiding Exponential Growth
This document mitigates the denial-of-service vulnerability described in Section 3 by replacing the policy tree with a policy graph structure, described in this section. The policy graph grows linearly instead of exponentially. This removes the asymmetric cost in policy validation.¶
X.509 implementations SHOULD perform policy validation by building a policy graph, following the procedure described in Section 5. This replacement procedure computes the same policies as in [RFC5280], however 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
The tree structure from [RFC5280] is an unnecessarily inefficient representation of a certification path's policy mappings. A single certificate policy may correspond to multiple nodes, but each node is identical, with identical children. This redundancy is the source of the exponential growth described in Section 3.2.¶
A policy graph is a directed acyclic graph of policy nodes. Where [RFC5280] adds multiple duplicate nodes, a policy graph adds a single node with multiple parents. See Section 5 for the procedure for building this structure. Figure 3 shows the updated representation of the example in Figure 2.¶
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 from [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 entire valid_policy_tree
structure as
an output of the verification process. Section 12.2 of [X.509] instead only
outputs the authorities-constrained policies, the user-constrained policies,
and their associated qualifiers.¶
As the valid_policy_tree
is the exponential structure, computing it
reintroduces the denial-of-service vulnerability. X.509 implementations
SHOULD NOT output the entire valid_policy_tree
structure and instead SHOULD
limit output to just the set of authorities-constrained and/or user-constrained
policies, as described in [X.509]. Section 5.6 and
Section 6 discuss other mitigations for applications where this
option is not available.¶
X.509 implementations MAY omit policy qualifiers from the output to simplify processing. Note 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 provides updates to [RFC5280]. This implements the changes described in Section 4.¶
5.1. Updates to Section 6.1
This update replaces a paragraph of Section 6.1 of [RFC5280] as follows:¶
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 update replaces entry (a) of Section 6.1.2 of [RFC5280] with the following text:¶
- (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, 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 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 whose
valid_policy
is P-OID.¶ -
The
expected_policy_set
of a node whosevalid_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 whosevalid_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 whosevalid_policy
is anyPolicy. That is, a node cannot simultaneously be a child of both anyPolicy and some non-anyPolicy OID.¶
Figure 4 is a graphic representation of the initial state of the
valid_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
This update replaces steps (d), (e), and (f) of Section 6.1.3 of [RFC5280] with the following text:¶
- (d)
-
If the certificate policies extension is present in the certificate and the
valid_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)
-
Let
parent_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 a
valid_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 as Figure 5.¶ - (ii)
-
If there was no match in step (i) and the
valid_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 a
valid_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 as Figure 6.¶
- (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) which appears in the
expected_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 a
valid_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, Bronze}. 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 as Figure 7.¶ - (3)
-
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.¶For example, consider the valid_policy_graph shown in Figure 8 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 the
valid_policy_graph
to NULL.¶ - (f)
-
Verify that either
explicit_policy
is greater than 0 or thevalid_policy_graph
is not equal to NULL;¶
5.4. Updates to Section 6.1.4
This update replaces step (b) of Section 6.1.4 of [RFC5280] with the following text:¶
- (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, setexpected_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, no node of depth i in the
valid_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 of the node of depth i-1 that has avalid_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:¶
5.5. Updates to Section 6.1.5
This update replaces step (g) of Section 6.1.5 of [RFC5280] with the following text:¶
- (g)
-
Calculate the
user_constrained_policy_set
as follows. Theuser_constrained_policy_set
is a set of policy OIDs, along with associated policy qualifiers.¶- (1)
-
If the
valid_policy_graph
is NULL, setvalid_policy_node_set
to the empty set.¶ - (2)
-
If the
valid_policy_graph
is not NULL, setvalid_policy_node_set
to the set of policy nodes whosevalid_policy
is not anyPolicy and whose parent list is a single node withvalid_policy
of anyPolicy.¶ - (3)
-
If the
valid_policy_graph
is not NULL and contains a node of depth n with thevalid_policy
anyPolicy, add it tovalid_policy_node_set
.¶ - (4)
-
Compute
authority_constrained_policy_set
, a set of policy OIDs and associated qualifiers as follows. For each node invalid_policy_node_set
:¶ - (5)
-
Set
user_constrained_policy_set
toauthority_constrained_policy_set
.¶ - (6)
-
If the user-initial-policy-set is not anyPolicy:¶
- (i)
-
Remove any elements of
user_constrained_policy_set
which 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 which does not appear inuser_constrained_policy_set
, add P-OID with qualifiers AP-Q touser_constrained_policy_set
.¶
Additionally, this update replaces the final paragraph as follows:¶
OLD:¶
-
If either (1) the value of
explicit_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 of
explicit_policy
variable 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
This update replaces Section 6.1.6 of [RFC5280] with the following text:¶
-
If path processing succeeds, the procedure terminates, returning a success indication together with final value of the
user_constrained_policy_set
, theworking_public_key
, theworking_public_key_algorithm
, and theworking_public_key_parameters
.¶Note 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 which requires
valid_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 implementations SHOULD mitigate denial-of-service in other ways, such as limiting the depth or size of the tree.¶
6. Other Mitigations
X.509 implementations that are unable 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. 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 which the application wishes to accept. Too high of a limit may still admit a DoS attack for the application. By modifying the example in Section 3.2 to increase the number of policies asserted in each ertificate, an attacker could still achieve O(N^(depth/2)) scaling.¶
6.2. 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 DoS attack.¶
6.3. 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 which 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.4. Disable Policy Checking
An X.509 validator can mitigate this attack by disabling policy validation entirely. This may be viable for applications which do not require policy validation. In this case, critical policy-related extensions, notably the policy constraints (Section 4.2.1.11 of [RFC5280]), MUST be treated as unrecognized extensions as in Section 4.2 of [RFC5280] and be rejected.¶
6.5. 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, but where untrusted entities have technically-constrained intermediate certificates where policy mapping and path length are unconstrained.¶
7. Security Considerations
Section 3 discusses how [RFC5280]'s policy tree algorithm can lead to denial-of-service vulnerabilities in X.509-based applications, such as [CVE-2023-0464] and [CVE-2023-23524].¶
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.¶
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, , <https://www.rfc-editor.org/rfc/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, , <https://www.rfc-editor.org/rfc/rfc5280>.
- [RFC8174]
- Leiba, B., "Ambiguity of Uppercase vs Lowercase in RFC 2119 Key Words", BCP 14, RFC 8174, DOI 10.17487/RFC8174, , <https://www.rfc-editor.org/rfc/rfc8174>.
9.2. Informative References
- [CVE-2023-0464]
- "Excessive Resource Usage Verifying X.509 Policy Constraints", , <https://www.cve.org/CVERecord?id=CVE-2023-0464>.
- [CVE-2023-23524]
- "Processing a maliciously crafted certificate may lead to a denial-of-service", , <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, , <https://www.rfc-editor.org/rfc/rfc8446>.
- [X.509]
- International Telecommunications Union, "Information technology - Open Systems Interconnection - The Directory: Public-key and attribute certificate frameworks", ITU-T Recommendation 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.¶