Internet Engineering Task Force (IETF) D. Benjamin
Request for Comments: 9618 Google LLC
Updates: 5280 August 2024
Category: Standards Track
ISSN: 20701721
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 that scaled exponentially in the
worst case, leaving implementations vulnerable to denialofservice
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 has
received public review and has been approved for publication by the
Internet Engineering Steering Group (IESG). Further information on
Internet Standards is available in Section 2 of RFC 7841.
Information about the current status of this document, any errata,
and how to provide feedback on it may be obtained at
https://www.rfceditor.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/licenseinfo) 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
1.1. Summary of Changes from RFC 5280
2. Conventions and Definitions
3. DenialofService 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 Address
1. Introduction
[RFC5280] defines a suite of extensions for determining the policies
that apply to a certification path. A policy is described by an
object identifier (OID) and a set of optional qualifiers.
Policy validation in [RFC5280] is complex. As an overview, the
certificate policies extension (Section 4.2.1.4 of [RFC5280])
describes the policies, with optional qualifiers, under which an
individual certificate was issued. The policy mappings extension
(Section 4.2.1.5 of [RFC5280]) allows a CA certificate to map its
policy OIDs to other policy OIDs in certificates that it issues.
Subject to these mappings and other extensions, the certification
path's overall policy set is the intersection of policies asserted by
each certificate in the path.
The procedure in Section 6.1 of [RFC5280] determines this set in the
course of certification path validation. It does so by building a
policy tree containing policies asserted by each certificate and the
mappings between them. This tree can grow exponentially in the depth
of the certification path, which means an attacker, with a small
input, can cause a path validator to consume excessive memory and
computational resources. This cost asymmetry can lead to a denial
ofservice vulnerability in X.509based applications, such as
[CVE20230464] and [CVE202323524].
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] that
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 that builds an equivalent but much more
efficient structure. This new algorithm does not change the validity
status of any certification path or which certificate policies are
valid for it.
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. DenialofService Vulnerability
This section discusses how the path validation algorithm defined in
Section 6.1.2 of [RFC5280] can lead to a denialofservice
vulnerability in X.509based 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 that was mapped to this
policy, and a node's children are the policies the node was mapped to
in the subject certificate.
For example, suppose a certification path contains:
* An intermediate certificate that asserts the following policy
OIDs: OID1, OID2, and OID5. It contains mappings from OID1 to
OID3 and from OID1 to OID4.
* An endentity certificate that asserts the following policy OIDs:
OID2, OID3, and OID6.
This would result in the tree shown below. Note that OID5 and OID6
are not included or mapped across the whole path, so they do not
appear in the final structure.
++
Root:  anyPolicy 
++
{anyPolicy}
++
/ \
/ \
v v
++ ++
Intermediate:  OID1   OID2 
(OID5 discarded) ++ ++
{OID3, OID4}  {OID2} 
++ ++
 
 
v v
++ ++
Endentity:  OID3   OID2 
(OID6 discarded) ++ ++
The complete algorithm for building this structure is described in
steps (d), (e), and (f) in Section 6.1.3 of [RFC5280]; steps (h),
(i), and (j) in Section 6.1.4 of [RFC5280]; and steps (a), (b), and
(g) in Section 6.1.5 of [RFC5280].
3.2. Exponential Growth
The valid_policy_tree grows exponentially in the worst case. In step
(d.1) in 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 endentity certificate, the
resulting tree would be as depicted in 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 the exponential growth to mount a denialof
service attack against an X.509based application. The attacker
sends a certificate chain as described in Section 3.2 and triggers
the target application's certificate validation process. For
example, the target application may be a TLS server [RFC8446] that
performs client certificate validation. The target application will
consume far more resources processing the input than the attacker
consumed to send it, which prevents the target application from
servicing other clients.
4. Avoiding Exponential Growth
This document mitigates the denialofservice vulnerability described
in Section 3 by replacing the policy tree with a policy graph
structure, which is 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], 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, exponentialsized
output.
4.1. Policy Graphs
The tree structure in [RFC5280] is an unnecessarily inefficient
representation of a certification path's policy mappings. When
multiple issuer policies map to a single subject policy, the subject
policy will correspond to multiple duplicate nodes in the policy
tree. Children of the subject policy are then duplicated
recursively. This duplication is the source of the exponential
growth described in Section 3.2.
A policy graph represents the same information with a directed
acyclic graph of policy nodes. It eliminates this duplication by
using a single node with multiple parents. See Section 5 for the
procedure for building this structure. Figure 2 shows the updated
representation of the example in Figure 1.
++
 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 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 in
[RFC5280] is the tree of all paths from the root to a leaf in the
policy graph, so no information is lost in the graph representation.
4.2. Verification Outputs
Section 6.1.6 of [RFC5280] describes the entire valid_policy_tree
structure as an output of the verification process. However,
Section 12.2 of [X.509] only describes the following as outputs: the
authoritiesconstrained policies, the userconstrained policies, and
their associated qualifiers.
As the valid_policy_tree is the exponential structure, computing it
reintroduces the denialofservice vulnerability. X.509
implementations SHOULD NOT output the entire valid_policy_tree
structure; instead, they SHOULD limit output to just the set of
authoritiesconstrained and/or userconstrained policies, as
described in [X.509]. Sections 5.6 and 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 that 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]. These updates implement
the changes described in Section 4.
5.1. Updates to Section 6.1
Section 6.1 of [RFC5280] is updated as follows:
OLD:
 A particular certification path may not, however, be appropriate
 for all applications. Therefore, an 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
The following 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 x1. 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 POID, there is at most one
 node at depth x whose valid_policy is POID.

 * 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 x1 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 nonanyPolicy 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
 Variable
5.3. Updates to Section 6.1.3
The following replaces steps (d), (e), and (f) in Section 6.1.3 of
[RFC5280]:
 (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 POID denote the OID
 for policy P and PQ denote the qualifier set for policy
 P. Perform the following steps in order:

 (i) Let parent_nodes be the nodes at depth i1 in the
 valid_policy_graph where POID is in the
 expected_policy_set. If parent_nodes is not
 empty, create a child node as follows: set the
 valid_policy to POID, set the qualifier_set to
 PQ, set the expected_policy_set to {POID}, and
 set the parent nodes to parent_nodes.

 For example, consider a valid_policy_graph with a
 node of depth i1 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 4.

 ++ ++
  Red   Blue 
 ++ ++
  {}   {}  depth i1
 ++ ++
  {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_graph includes a node of depth i1
 with the valid_policy anyPolicy, generate a child
 node with the following values: set the
 valid_policy to POID, set the qualifier_set to
 PQ, set the expected_policy_set to {POID}, and
 set the parent node to the anyPolicy node at depth
 i1.

 For example, consider a valid_policy_graph with a
 node of depth i1 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 QSilver. 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 5.

 ++
  anyPolicy 
 ++
  {} 
 ++ depth i1
  {anyPolicy} 
 ++
 / \
 / \
 / \
 v v
 ++ ++
  Gold   Silver 
 ++ ++
  {}   {QSilver}  depth i
 ++ ++
  {Gold}   {Silver} 
 ++ ++

 Figure 5: Processing Unmatched Policies When a
 Leaf Node Specifies anyPolicy

 (2) If the certificate policies extension includes the
 policy anyPolicy with the qualifier set APQ and either
 (a) inhibit_anyPolicy is greater than 0 or (b) i.
[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,
.
[RFC8174] Leiba, B., "Ambiguity of Uppercase vs Lowercase in RFC
2119 Key Words", BCP 14, RFC 8174, DOI 10.17487/RFC8174,
May 2017, .
9.2. Informative References
[CVE20230464]
CVE, "Excessive Resource Usage Verifying X.509 Policy
Constraints", CVE20230464, March 2023,
.
[CVE202323524]
CVE, "Processing a maliciously crafted certificate may
lead to a denialofservice", CVE202323524, February
2023, .
[RFC8446] Rescorla, E., "The Transport Layer Security (TLS) Protocol
Version 1.3", RFC 8446, DOI 10.17487/RFC8446, August 2018,
.
[X.509] ITUT, "Information technology  Open Systems
Interconnection  The Directory: Publickey and attribute
certificate frameworks", ITUT 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. 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