Updates to X.509 Policy Validation
draft-ietf-lamps-x509-policy-graph-02
The information below is for an old version of the document.
| Document | Type |
This is an older version of an Internet-Draft that was ultimately published as RFC 9618.
|
|
|---|---|---|---|
| Author | David Benjamin | ||
| Last updated | 2024-01-05 (Latest revision 2023-11-21) | ||
| Replaces | draft-davidben-x509-policy-graph | ||
| RFC stream | Internet Engineering Task Force (IETF) | ||
| Formats | |||
| Reviews |
ARTART Last Call review
(of
-03)
by Martin Thomson
Ready w/nits
|
||
| Additional resources | Mailing list discussion | ||
| Stream | WG state | Submitted to IESG for Publication | |
| Document shepherd | Russ Housley | ||
| Shepherd write-up | Show Last changed 2023-12-09 | ||
| IESG | IESG state | Became RFC 9618 (Proposed Standard) | |
| Consensus boilerplate | Yes | ||
| Telechat date | (None) | ||
| Responsible AD | Roman Danyliw | ||
| Send notices to | housley@vigilsec.com |
draft-ietf-lamps-x509-policy-graph-02
Limited Additional Mechanisms for PKIX and SMIME D. Benjamin
Internet-Draft Google LLC
Updates: 5280 (if approved) 21 November 2023
Intended status: Standards Track
Expires: 24 May 2024
Updates to X.509 Policy Validation
draft-ietf-lamps-x509-policy-graph-02
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 24 May 2024.
Benjamin Expires 24 May 2024 [Page 1]
Internet-Draft Updates to X.509 Policy Validation November 2023
Copyright Notice
Copyright (c) 2023 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.
Table of Contents
1. Introduction . . . . . . . . . . . . . . . . . . . . . . . . 3
1.1. Summary of Changes from RFC 5280 . . . . . . . . . . . . 3
2. Conventions and Definitions . . . . . . . . . . . . . . . . . 3
3. Denial of Service Vulnerability . . . . . . . . . . . . . . . 3
3.1. Policy Trees . . . . . . . . . . . . . . . . . . . . . . 4
3.2. Exponential Growth . . . . . . . . . . . . . . . . . . . 5
3.3. Attack Vector . . . . . . . . . . . . . . . . . . . . . . 6
4. Avoiding Exponential Growth . . . . . . . . . . . . . . . . . 6
4.1. Policy Graphs . . . . . . . . . . . . . . . . . . . . . . 7
4.2. Verification Outputs . . . . . . . . . . . . . . . . . . 8
5. Updates to RFC 5280 . . . . . . . . . . . . . . . . . . . . . 9
5.1. Updates to Section 6.1 . . . . . . . . . . . . . . . . . 9
5.2. Updates to Section 6.1.2 . . . . . . . . . . . . . . . . 10
5.3. Updates to Section 6.1.3 . . . . . . . . . . . . . . . . 11
5.4. Updates to Section 6.1.4 . . . . . . . . . . . . . . . . 15
5.5. Updates to Section 6.1.5 . . . . . . . . . . . . . . . . 16
5.6. Updates to Section 6.1.6 . . . . . . . . . . . . . . . . 18
6. Other Mitigations . . . . . . . . . . . . . . . . . . . . . . 18
6.1. Limit Certificate Depth . . . . . . . . . . . . . . . . . 18
6.2. Limit Policy Tree Size . . . . . . . . . . . . . . . . . 18
6.3. Inhibit Policy Mapping . . . . . . . . . . . . . . . . . 18
6.4. Disable Policy Checking . . . . . . . . . . . . . . . . . 19
6.5. Verify Signatures First . . . . . . . . . . . . . . . . . 19
7. Security Considerations . . . . . . . . . . . . . . . . . . . 19
8. IANA Considerations . . . . . . . . . . . . . . . . . . . . . 19
9. References . . . . . . . . . . . . . . . . . . . . . . . . . 19
9.1. Normative References . . . . . . . . . . . . . . . . . . 20
9.2. Informative References . . . . . . . . . . . . . . . . . 20
Acknowledgements . . . . . . . . . . . . . . . . . . . . . . . . 20
Author's Address . . . . . . . . . . . . . . . . . . . . . . . . 20
Benjamin Expires 24 May 2024 [Page 2]
Internet-Draft Updates to X.509 Policy Validation November 2023
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.
Benjamin Expires 24 May 2024 [Page 3]
Internet-Draft Updates to X.509 Policy Validation November 2023
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.
+-----------+
Root: | anyPolicy |
+-----------+
|{anyPolicy}|
+-----------+
/ \
/ \
v v
+------------+ +------------+
Intermediate: | OID1 | | OID2 |
+------------+ +------------+
|{OID3, OID4}| | {OID2} |
+------------+ +------------+
| |
| |
v v
+------------+ +------------+
End-entity: | OID3 | | OID2 |
+------------+ +------------+
Figure 1: An Example X.509 Policy Tree
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].
Benjamin Expires 24 May 2024 [Page 4]
Internet-Draft Updates to X.509 Policy Validation November 2023
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:
* 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 in Figure 2.
Benjamin Expires 24 May 2024 [Page 5]
Internet-Draft Updates to X.509 Policy Validation November 2023
+-----------------------+
| 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 2: An Example X.509 Policy Tree with Exponential Growth
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
The denial-of-service vulnerability described in Section 3 can be
mitigated by implementing a policy graph structure, described in this
section.
Benjamin Expires 24 May 2024 [Page 6]
Internet-Draft Updates to X.509 Policy Validation November 2023
Compared the original policy tree structure described in [RFC5280],
the policy graph grows linearly instead of exponentially. This
document deprecates the original policy tree structure. X.509
implementations SHOULD instead perform policy validation by building
a policy graph. This mitigates the denial-of-service attack by
removing the asymmetric cost in policy validation.
While this replacement process computes the same policies as in
[RFC5280], one of the outputs is in a different form. See
Section 4.2 for details.
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.
Benjamin Expires 24 May 2024 [Page 7]
Internet-Draft Updates to X.509 Policy Validation November 2023
+-----------+
| 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 3: A More Efficient Representation of an X.509 Policy Tree
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.
Benjamin Expires 24 May 2024 [Page 8]
Internet-Draft Updates to X.509 Policy Validation November 2023
An implementation which outputs the entire tree may be unable switch
the format to a more efficient one, as described in Section 4.1.
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].
X.509 implementations are additionally RECOMMENDED to omit policy
qualifiers from the output, as this simplifies the process. Note
Section 4.2.1.4 of [RFC5280] conversely recommends that certificate
authorities omit policy qualifiers from policy information terms.
This document reiterates this and RECOMMENDS that certificate
authorities omit the policyQualifiers field in PolicyInformation
structures.
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:
Benjamin Expires 24 May 2024 [Page 9]
Internet-Draft Updates to X.509 Policy Validation November 2023
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).
Benjamin Expires 24 May 2024 [Page 10]
Internet-Draft Updates to X.509 Policy Validation November 2023
(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 4 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 4: Initial value of the valid_policy_graph State Variable
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:
Benjamin Expires 24 May 2024 [Page 11]
Internet-Draft Updates to X.509 Policy Validation November 2023
(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 the
valid_policy_graph where P-OID is in the
expected_policy_set. If parent_nodes is not empty,
create a child node as follows: set the valid_policy
to P-OID, set the qualifier_set to P-Q, set the
expected_policy_set to {P-OID}, and set the parent
nodes to parent_nodes.
For example, consider a valid_policy_graph with a
node of depth i-1 where the expected_policy_set is
{Gold, White}, and a second node where the
expected_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.
+-----------------+ +-----------------+
| Red | | Blue |
+-----------------+ +-----------------+
| {} | | {} | depth i-1
+-----------------+ +-----------------+
| {Gold, White} | | {Gold, Yellow} |
+-----------------+ +-----------------+
\ /
\ /
\ /
v v
+-----------------+
| Gold |
+-----------------+
| {} | depth i
+-----------------+
| {Gold} |
+-----------------+
Figure 5: Processing an Exact Match
Benjamin Expires 24 May 2024 [Page 12]
Internet-Draft Updates to X.509 Policy Validation November 2023
(ii) If there was no match in step (i) and the
valid_policy_graph includes a node of depth i-1 with
the valid_policy anyPolicy, generate a child node
with the following values: set the valid_policy to
P-OID, set the qualifier_set to P-Q, set the
expected_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 the valid_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.
+-----------------+
| anyPolicy |
+-----------------+
| {} |
+-----------------+ depth i-1
| {anyPolicy} |
+-----------------+
/ \
/ \
/ \
/ \
+-----------------+ +-----------------+
| Gold | | Silver |
+-----------------+ +-----------------+
| {} | | {Q-Silver} | depth i
+-----------------+ +-----------------+
| {Gold} | | {Silver} |
+-----------------+ +-----------------+
Figure 6: Processing Unmatched Policies when a
Leaf Node Specifies anyPolicy
(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:
Benjamin Expires 24 May 2024 [Page 13]
Internet-Draft Updates to X.509 Policy Validation November 2023
For each policy OID P-OID (including anyPolicy) which
appears in the expected_policy_set of some node in the
valid_policy_graph for depth i-1, if P-OID does not appear
as the valid_policy of some node at depth i, create a
single child node with the following values: set the
valid_policy to P-OID, set the qualifier_set to AP-Q, set
the expected_policy_set to {P-OID}, and set the parents to
the nodes at depth i-1 where P-OID appears in
expected_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 the expected_policy_set is {Gold, Silver},
and a second node of depth i-1 where the
expected_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.
+-----------------+ +-----------------+
| Red | | Blue |
+-----------------+ +-----------------+
| {} | | {} | depth i-1
+-----------------+ +-----------------+
| {Gold, Silver} | | {Gold, Bronze} |
+-----------------+ +-----------------+
| \ |
| \ |
| \ |
| \ |
| \ |
v v v
+-----------------+ +-----------------+
| Silver | | Gold |
+-----------------+ +-----------------+
| {AP-Q} | | {AP-Q} | depth i
+-----------------+ +-----------------+
| {Silver} | | {Gold} |
+-----------------+ +-----------------+
Figure 7: Processing Unmatched Policies When the
Certificate Policies Extension Specifies anyPolicy
Benjamin Expires 24 May 2024 [Page 14]
Internet-Draft Updates to X.509 Policy Validation November 2023
(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.
+-----------+
| | depth i-3
+-----------+
/ | \
/ | \
/ | \
+-----------+ +-----------+ +-----------+
| | | | | Y | depth i-2
+-----------+ +-----------+ +-----------+
| \ | |
| \ | |
| \ | |
+-----------+ +-----------+ +-----------+
| X | | | | X | depth i-1
+-----------+ +-----------+ +-----------+
/ | \
/ | \
/ | \
+-----------+ +-----------+ +-----------+
| | | | | | depth i
+-----------+ +-----------+ +-----------+
Figure 8: Pruning the valid_policy_graph
(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 the
valid_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:
Benjamin Expires 24 May 2024 [Page 15]
Internet-Draft Updates to X.509 Policy Validation November 2023
(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, 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 update replaces step (g) of Section 6.1.5 of [RFC5280] with the
following text:
(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.
Benjamin Expires 24 May 2024 [Page 16]
Internet-Draft Updates to X.509 Policy Validation November 2023
(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) If returning policy qualifiers in the output, collect
all qualifiers in the node, its ancestors, and
descendants and associate them with valid_policy.
Returning policy qualifiers in the output is NOT
RECOMMENDED.
(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
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 in user_constrained_policy_set,
add P-OID with qualifiers AP-Q to
user_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) the valid_policy_tree is not NULL, then path
processing has succeeded.
NEW:
Benjamin Expires 24 May 2024 [Page 17]
Internet-Draft Updates to X.509 Policy Validation November 2023
If either (1) the value of explicit_policy variable 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 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, the working_public_key, the
working_public_key_algorithm, and the
working_public_key_parameters.
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
X.509 validators typically already allow limiting the depth of a
certificate chain. This can limit the attack, however a large depth
limit may still admit attacks. 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
or higher.
6.2. Limit Policy Tree Size
If existing stable interfaces force the validator to build a full
policy tree (see Section 4.2), the validator SHOULD limit the number
of nodes in the policy tree, and reject the certification path if
this limit is reached.
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.
Benjamin Expires 24 May 2024 [Page 18]
Internet-Draft Updates to X.509 Policy Validation November 2023
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
Benjamin Expires 24 May 2024 [Page 19]
Internet-Draft Updates to X.509 Policy Validation November 2023
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/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, May 2008,
<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,
May 2017, <https://www.rfc-editor.org/rfc/rfc8174>.
9.2. Informative References
[CVE-2023-0464]
"Excessive Resource Usage Verifying X.509 Policy
Constraints", March 2023,
<https://www.cve.org/CVERecord?id=CVE-2023-0464>.
[CVE-2023-23524]
"Processing a maliciously crafted certificate may lead to
a denial-of-service", 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/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, October 2019.
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.
Author's Address
David Benjamin
Google LLC
Benjamin Expires 24 May 2024 [Page 20]
Internet-Draft Updates to X.509 Policy Validation November 2023
Email: davidben@google.com
Benjamin Expires 24 May 2024 [Page 21]