rfc9618.original | rfc9618.txt | |||
---|---|---|---|---|
Limited Additional Mechanisms for PKIX and SMIME D. Benjamin | Internet Engineering Task Force (IETF) D. Benjamin | |||
Internet-Draft Google LLC | Request for Comments: 9618 Google LLC | |||
Updates: 5280 (if approved) 1 February 2024 | Updates: 5280 July 2024 | |||
Intended status: Standards Track | Category: Standards Track | |||
Expires: 4 August 2024 | ISSN: 2070-1721 | |||
Updates to X.509 Policy Validation | Updates to X.509 Policy Validation | |||
draft-ietf-lamps-x509-policy-graph-05 | ||||
Abstract | Abstract | |||
This document updates RFC 5280 to replace the algorithm for X.509 | This document updates RFC 5280 to replace the algorithm for X.509 | |||
policy validation with an equivalent, more efficient algorithm. The | policy validation with an equivalent, more efficient algorithm. The | |||
original algorithm built a structure which scaled exponentially in | original algorithm built a structure that scaled exponentially in the | |||
the worst case, leaving implementations vulnerable to denial-of- | worst case, leaving implementations vulnerable to denial-of-service | |||
service attacks. | 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 | Status of This Memo | |||
This Internet-Draft is submitted in full conformance with the | This is an Internet Standards Track document. | |||
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 | This document is a product of the Internet Engineering Task Force | |||
and may be updated, replaced, or obsoleted by other documents at any | (IETF). It represents the consensus of the IETF community. It has | |||
time. It is inappropriate to use Internet-Drafts as reference | received public review and has been approved for publication by the | |||
material or to cite them other than as "work in progress." | Internet Engineering Steering Group (IESG). Further information on | |||
Internet Standards is available in Section 2 of RFC 7841. | ||||
This Internet-Draft will expire on 4 August 2024. | Information about the current status of this document, any errata, | |||
and how to provide feedback on it may be obtained at | ||||
https://www.rfc-editor.org/info/rfc9618. | ||||
Copyright Notice | Copyright Notice | |||
Copyright (c) 2024 IETF Trust and the persons identified as the | Copyright (c) 2024 IETF Trust and the persons identified as the | |||
document authors. All rights reserved. | document authors. All rights reserved. | |||
This document is subject to BCP 78 and the IETF Trust's Legal | This document is subject to BCP 78 and the IETF Trust's Legal | |||
Provisions Relating to IETF Documents (https://trustee.ietf.org/ | Provisions Relating to IETF Documents | |||
license-info) in effect on the date of publication of this document. | (https://trustee.ietf.org/license-info) in effect on the date of | |||
Please review these documents carefully, as they describe your rights | publication of this document. Please review these documents | |||
and restrictions with respect to this document. Code Components | carefully, as they describe your rights and restrictions with respect | |||
extracted from this document must include Revised BSD License text as | to this document. Code Components extracted from this document must | |||
described in Section 4.e of the Trust Legal Provisions and are | include Revised BSD License text as described in Section 4.e of the | |||
provided without warranty as described in the Revised BSD License. | Trust Legal Provisions and are provided without warranty as described | |||
in the Revised BSD License. | ||||
Table of Contents | Table of Contents | |||
1. Introduction . . . . . . . . . . . . . . . . . . . . . . . . 3 | 1. Introduction | |||
1.1. Summary of Changes from RFC 5280 . . . . . . . . . . . . 3 | 1.1. Summary of Changes from RFC 5280 | |||
2. Conventions and Definitions . . . . . . . . . . . . . . . . . 4 | 2. Conventions and Definitions | |||
3. Denial of Service Vulnerability . . . . . . . . . . . . . . . 4 | 3. Denial-of-Service Vulnerability | |||
3.1. Policy Trees . . . . . . . . . . . . . . . . . . . . . . 4 | 3.1. Policy Trees | |||
3.2. Exponential Growth . . . . . . . . . . . . . . . . . . . 5 | 3.2. Exponential Growth | |||
3.3. Attack Vector . . . . . . . . . . . . . . . . . . . . . . 6 | 3.3. Attack Vector | |||
4. Avoiding Exponential Growth . . . . . . . . . . . . . . . . . 7 | 4. Avoiding Exponential Growth | |||
4.1. Policy Graphs . . . . . . . . . . . . . . . . . . . . . . 7 | 4.1. Policy Graphs | |||
4.2. Verification Outputs . . . . . . . . . . . . . . . . . . 8 | 4.2. Verification Outputs | |||
5. Updates to RFC 5280 . . . . . . . . . . . . . . . . . . . . . 9 | 5. Updates to RFC 5280 | |||
5.1. Updates to Section 6.1 . . . . . . . . . . . . . . . . . 9 | 5.1. Updates to Section 6.1 | |||
5.2. Updates to Section 6.1.2 . . . . . . . . . . . . . . . . 10 | 5.2. Updates to Section 6.1.2 | |||
5.3. Updates to Section 6.1.3 . . . . . . . . . . . . . . . . 11 | 5.3. Updates to Section 6.1.3 | |||
5.4. Updates to Section 6.1.4 . . . . . . . . . . . . . . . . 15 | 5.4. Updates to Section 6.1.4 | |||
5.5. Updates to Section 6.1.5 . . . . . . . . . . . . . . . . 16 | 5.5. Updates to Section 6.1.5 | |||
5.6. Updates to Section 6.1.6 . . . . . . . . . . . . . . . . 17 | 5.6. Updates to Section 6.1.6 | |||
6. Other Mitigations . . . . . . . . . . . . . . . . . . . . . . 18 | 6. Other Mitigations | |||
6.1. Verify Signatures First . . . . . . . . . . . . . . . . . 18 | 6.1. Verify Signatures First | |||
6.2. Limit Certificate Depth . . . . . . . . . . . . . . . . . 19 | 6.2. Limit Certificate Depth | |||
6.3. Limit Policy Tree Size . . . . . . . . . . . . . . . . . 19 | 6.3. Limit Policy Tree Size | |||
6.4. Inhibit Policy Mapping . . . . . . . . . . . . . . . . . 19 | 6.4. Inhibit Policy Mapping | |||
6.5. Disable Policy Checking . . . . . . . . . . . . . . . . . 19 | 6.5. Disable Policy Checking | |||
7. Implementation Status . . . . . . . . . . . . . . . . . . . . 20 | 7. Security Considerations | |||
8. Security Considerations . . . . . . . . . . . . . . . . . . . 20 | 8. IANA Considerations | |||
9. IANA Considerations . . . . . . . . . . . . . . . . . . . . . 20 | 9. References | |||
10. References . . . . . . . . . . . . . . . . . . . . . . . . . 20 | 9.1. Normative References | |||
10.1. Normative References . . . . . . . . . . . . . . . . . . 20 | 9.2. Informative References | |||
10.2. Informative References . . . . . . . . . . . . . . . . . 21 | Acknowledgements | |||
Acknowledgements . . . . . . . . . . . . . . . . . . . . . . . . 22 | Author's Address | |||
Author's Address . . . . . . . . . . . . . . . . . . . . . . . . 22 | ||||
1. Introduction | 1. Introduction | |||
[RFC5280] defines a suite of extensions for determining the | [RFC5280] defines a suite of extensions for determining the policies | |||
"policies" which apply to a certification path. A policy is | that apply to a certification path. A policy is described by an | |||
described by an object identifier (OID), and a set of optional | object identifier (OID) and a set of optional qualifiers. | |||
qualifiers. | ||||
Policy validation in [RFC5280] is complex. As an overview, the | Policy validation in [RFC5280] is complex. As an overview, the | |||
certificate policies extension (Section 4.2.1.4 of [RFC5280]) | certificate policies extension (Section 4.2.1.4 of [RFC5280]) | |||
describes the policies, with optional qualifiers, under which an | describes the policies, with optional qualifiers, under which an | |||
individual certificate was issued. The policy mappings extension | individual certificate was issued. The policy mappings extension | |||
(Section 4.2.1.5 of [RFC5280]) allows a CA certificate to map its | (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. | policy OIDs to other policy OIDs in certificates that it issues. | |||
Subject to these mappings and other extensions, the certification | Subject to these mappings and other extensions, the certification | |||
path's overall policy set is the intersection of policies asserted by | path's overall policy set is the intersection of policies asserted by | |||
each certificate in the path, collecting the corresponding | each certificate in the path, collecting the corresponding | |||
qualifiers. | qualifiers. | |||
The procedure in Section 6.1 of [RFC5280] determines this set in the | The procedure in Section 6.1 of [RFC5280] determines this set in the | |||
course of certification path validation. It does so by building a | course of certification path validation. It does so by building a | |||
policy tree, containing policies asserted by each certificate and | policy tree containing policies asserted by each certificate and the | |||
mappings between them. This tree can grow exponentially in the depth | mappings between them. This tree can grow exponentially in the depth | |||
of the certification path, which means an attacker, with a small | of the certification path, which means an attacker, with a small | |||
input, can cause a path validator to consume excessive memory and | input, can cause a path validator to consume excessive memory and | |||
computational resources. This cost asymmetry can lead to a denial- | computational resources. This cost asymmetry can lead to a denial- | |||
of-service vulnerability in X.509-based applications, such as | of-service vulnerability in X.509-based applications, such as | |||
[CVE-2023-0464] and [CVE-2023-23524]. | [CVE-2023-0464] and [CVE-2023-23524]. | |||
Section 3 describes this vulnerability. Section 4.1 describes the | Section 3 describes this vulnerability. Section 4.1 describes the | |||
primary mitigation for this vulnerability, a replacement for the | primary mitigation for this vulnerability, a replacement for the | |||
policy tree structure. Section 5 provides updates to [RFC5280] which | policy tree structure. Section 5 provides updates to [RFC5280] that | |||
implement this change. Finally, Section 6 discusses alternative | implement this change. Finally, Section 6 discusses alternative | |||
mitigation strategies for X.509 applications. | mitigation strategies for X.509 applications. | |||
1.1. Summary of Changes from RFC 5280 | 1.1. Summary of Changes from RFC 5280 | |||
The algorithm for processing certificate policies and policy mappings | The algorithm for processing certificate policies and policy mappings | |||
is replaced with one which builds an equivalent, but much more | is replaced with one that builds an equivalent but much more | |||
efficient structure. This new algorithm does not change the validity | efficient structure. This new algorithm does not change the validity | |||
status of any certification path, nor which certificate policies are | status of any certification path or which certificate policies are | |||
valid for it. | valid for it. | |||
2. Conventions and Definitions | 2. Conventions and Definitions | |||
The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT", | The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT", | |||
"SHOULD", "SHOULD NOT", "RECOMMENDED", "NOT RECOMMENDED", "MAY", and | "SHOULD", "SHOULD NOT", "RECOMMENDED", "NOT RECOMMENDED", "MAY", and | |||
"OPTIONAL" in this document are to be interpreted as described in BCP | "OPTIONAL" in this document are to be interpreted as described in | |||
14 [RFC2119] [RFC8174] when, and only when, they appear in all | BCP 14 [RFC2119] [RFC8174] when, and only when, they appear in all | |||
capitals, as shown here. | capitals, as shown here. | |||
3. Denial of Service Vulnerability | 3. Denial-of-Service Vulnerability | |||
This section discusses how the path validation algorithm defined in | This section discusses how the path validation algorithm defined in | |||
Section 6.1.2 of [RFC5280] can lead to a denial-of-service | Section 6.1.2 of [RFC5280] can lead to a denial-of-service | |||
vulnerability in X.509-based applications. | vulnerability in X.509-based applications. | |||
3.1. Policy Trees | 3.1. Policy Trees | |||
Section 6.1.2 of [RFC5280] constructs the valid_policy_tree, a tree | Section 6.1.2 of [RFC5280] constructs the valid_policy_tree, a tree | |||
of certificate policies, during certification path validation. The | of certificate policies, during certification path validation. The | |||
nodes at any given depth in the tree correspond to policies asserted | nodes at any given depth in the tree correspond to policies asserted | |||
by a certificate in the certification path. A node's parent policy | by a certificate in the certification path. A node's parent policy | |||
is the policy in the issuer certificate which was mapped to this | is the policy in the issuer certificate that was mapped to this | |||
policy, and a node's children are the policies it was mapped to in | policy, and a node's children are the policies it was mapped to in | |||
the subject certificate. | the subject certificate. | |||
For example, suppose a certification path contains: | For example, suppose a certification path contains: | |||
* An intermediate certificate which asserts policy OIDs OID1, OID2, | * An intermediate certificate that asserts the following policy | |||
and OID5. It contains mappings OID1 to OID3, and OID1 to OID4. | 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, | * An end-entity certificate that asserts the following policy OIDs: | |||
and OID6. | OID2, OID3, and OID6. | |||
This would result in the tree shown in Figure 1. Note that OID5 and | This would result in the tree shown below. Note that OID5 and OID6 | |||
OID6 are not included or mapped across the whole path, so they do not | are not included or mapped across the whole path, so they do not | |||
appear in the final structure. | appear in the final structure. | |||
+-----------+ | +-----------+ | |||
Root: | anyPolicy | | Root: | anyPolicy | | |||
+-----------+ | +-----------+ | |||
|{anyPolicy}| | |{anyPolicy}| | |||
+-----------+ | +-----------+ | |||
/ \ | / \ | |||
/ \ | / \ | |||
v v | v v | |||
skipping to change at page 5, line 25 ¶ | skipping to change at line 178 ¶ | |||
(OID5 discarded) +------------+ +------------+ | (OID5 discarded) +------------+ +------------+ | |||
|{OID3, OID4}| | {OID2} | | |{OID3, OID4}| | {OID2} | | |||
+------------+ +------------+ | +------------+ +------------+ | |||
| | | | | | |||
| | | | | | |||
v v | v v | |||
+------------+ +------------+ | +------------+ +------------+ | |||
End-entity: | OID3 | | OID2 | | End-entity: | OID3 | | OID2 | | |||
(OID6 discarded) +------------+ +------------+ | (OID6 discarded) +------------+ +------------+ | |||
Figure 1: An Example X.509 Policy Tree | ||||
The complete algorithm for building this structure is described in | The complete algorithm for building this structure is described in | |||
steps (d), (e), and (f) of Section 6.1.3 of [RFC5280], steps (h), | steps (d), (e), and (f) in Section 6.1.3 of [RFC5280]; steps (h), | |||
(i), (j) of Section 6.1.4 of [RFC5280], and steps (a), (b), and (g) | (i), and (j) in Section 6.1.4 of [RFC5280]; and steps (a), (b), and | |||
of Section 6.1.5 of [RFC5280]. | (g) in Section 6.1.5 of [RFC5280]. | |||
3.2. Exponential Growth | 3.2. Exponential Growth | |||
The valid_policy_tree grows exponentially in the worst case. In step | 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 | (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 | multiple child nodes if multiple issuer policies map to P. This can | |||
cause the tree size to increase in size multiplicatively at each | cause the tree size to increase in size multiplicatively at each | |||
level. | level. | |||
In particular, consider a certificate chain where every intermediate | In particular, consider a certificate chain where every intermediate | |||
certificate asserts policies OID1 and OID2, and then contains the | certificate asserts policies OID1 and OID2 and then contains the full | |||
full Cartesian product of mappings: | Cartesian product of mappings: | |||
* OID1 maps to OID1 | * OID1 maps to OID1 | |||
* OID1 maps to OID2 | * OID1 maps to OID2 | |||
* OID2 maps to OID1 | * OID2 maps to OID1 | |||
* OID2 maps to OID2 | * OID2 maps to OID2 | |||
At each depth, the tree would double in size. For example, if there | At each depth, the tree would double in size. For example, if there | |||
are two intermediate certificates and one end-entity certificate, the | are two intermediate certificates and one end-entity certificate, the | |||
resulting tree would be as depicted in Figure 2. | resulting tree would be as depicted in Figure 1. | |||
+-----------------------+ | +-----------------------+ | |||
| anyPolicy | | | anyPolicy | | |||
+-----------------------+ | +-----------------------+ | |||
| {anyPolicy} | | | {anyPolicy} | | |||
+-----------------------+ | +-----------------------+ | |||
/ \ | / \ | |||
/ \ | / \ | |||
v v | v v | |||
+------------+ +------------+ | +------------+ +------------+ | |||
skipping to change at page 6, line 35 ¶ | skipping to change at line 234 ¶ | |||
| OID1 | | OID2 | | OID1 | | OID2 | | | OID1 | | OID2 | | OID1 | | OID2 | | |||
+------------+ +------------+ +------------+ +------------+ | +------------+ +------------+ +------------+ +------------+ | |||
|{OID1, OID2}| |{OID1, OID2}| |{OID1, OID2}| |{OID1, OID2}| | |{OID1, OID2}| |{OID1, OID2}| |{OID1, OID2}| |{OID1, OID2}| | |||
+------------+ +------------+ +------------+ +------------+ | +------------+ +------------+ +------------+ +------------+ | |||
| | | | | | | | | | | | | | | | | | |||
v v v v v v v v | v v v v v v v v | |||
+------+ +------+ +------+ +------+ +------+ +------+ +------+ +------+ | +------+ +------+ +------+ +------+ +------+ +------+ +------+ +------+ | |||
| OID1 | | OID2 | | OID1 | | OID2 | | OID1 | | OID2 | | OID1 | | OID2 | | | OID1 | | OID2 | | OID1 | | OID2 | | OID1 | | OID2 | | OID1 | | OID2 | | |||
+------+ +------+ +------+ +------+ +------+ +------+ +------+ +------+ | +------+ +------+ +------+ +------+ +------+ +------+ +------+ +------+ | |||
Figure 2: An Example X.509 Policy Tree with Exponential Growth | Figure 1: An Example X.509 Policy Tree with Exponential Growth | |||
3.3. Attack Vector | 3.3. Attack Vector | |||
An attacker can use the exponential growth to mount a denial-of- | An attacker can use the exponential growth to mount a denial-of- | |||
service attack against an X.509-based application. The attacker | service attack against an X.509-based application. The attacker | |||
sends certificate chain as in Section 3.2 and triggers the target | sends a certificate chain as described in Section 3.2 and triggers | |||
application's certificate validation process. For example, the | the target application's certificate validation process. For | |||
target application may be a TLS [RFC8446] server that performs client | example, the target application may be a TLS server [RFC8446] that | |||
certificate validation. The target application will consume far more | performs client certificate validation. The target application will | |||
resources processing the input than the attacker consumed to send it, | consume far more resources processing the input than the attacker | |||
preventing it from servicing other clients. | consumed to send it, preventing it from servicing other clients. | |||
4. Avoiding Exponential Growth | 4. Avoiding Exponential Growth | |||
This document mitigates the denial-of-service vulnerability described | This document mitigates the denial-of-service vulnerability described | |||
in Section 3 by replacing the policy tree with a policy graph | in Section 3 by replacing the policy tree with a policy graph | |||
structure, described in this section. The policy graph grows | structure, which is described in this section. The policy graph | |||
linearly instead of exponentially. This removes the asymmetric cost | grows linearly instead of exponentially. This removes the asymmetric | |||
in policy validation. | cost in policy validation. | |||
X.509 implementations SHOULD perform policy validation by building a | X.509 implementations SHOULD perform policy validation by building a | |||
policy graph, following the procedure described in Section 5. This | policy graph, following the procedure described in Section 5. This | |||
replacement procedure computes the same policies as in [RFC5280], | replacement procedure computes the same policies as in [RFC5280], but | |||
however one of the outputs is in a different form. See Section 4.2 | one of the outputs is in a different form. See Section 4.2 for | |||
for details. Section 6 describes alternative mitigations for | details. Section 6 describes alternative mitigations for | |||
implementations that depend on the original, exponential-sized | implementations that depend on the original, exponential-sized | |||
output. | output. | |||
4.1. Policy Graphs | 4.1. Policy Graphs | |||
The tree structure from [RFC5280] is an unnecessarily inefficient | The tree structure in [RFC5280] is an unnecessarily inefficient | |||
representation of a certification path's policy mappings. A single | representation of a certification path's policy mappings. A single | |||
certificate policy may correspond to multiple nodes, but each node is | certificate policy may correspond to multiple nodes, but each node is | |||
identical, with identical children. This redundancy is the source of | identical, with identical children. This redundancy is the source of | |||
the exponential growth described in Section 3.2. | the exponential growth described in Section 3.2. | |||
A policy graph is a directed acyclic graph of policy nodes. Where | A policy graph is a directed acyclic graph of policy nodes. The | |||
[RFC5280] adds multiple duplicate nodes, a policy graph adds a single | policy tree in [RFC5280] adds multiple duplicate nodes, but a policy | |||
node with multiple parents. See Section 5 for the procedure for | graph adds a single node with multiple parents. See Section 5 for | |||
building this structure. Figure 3 shows the updated representation | the procedure for building this structure. Figure 2 shows the | |||
of the example in Figure 2. | updated representation of the example in Figure 1. | |||
+-----------+ | +-----------+ | |||
| anyPolicy | | | anyPolicy | | |||
+-----------+ | +-----------+ | |||
|{anyPolicy}| | |{anyPolicy}| | |||
+-----------+ | +-----------+ | |||
/ \ | / \ | |||
/ \ | / \ | |||
v v | v v | |||
+------------+ +------------+ | +------------+ +------------+ | |||
skipping to change at page 8, line 39 ¶ | skipping to change at line 311 ¶ | |||
| \ / | | | \ / | | |||
| \ / | | | \ / | | |||
| \/ | | | \/ | | |||
| /\ | | | /\ | | |||
| / \ | | | / \ | | |||
v v v v | v v v v | |||
+------------+ +------------+ | +------------+ +------------+ | |||
| OID1 | | OID2 | | | OID1 | | OID2 | | |||
+------------+ +------------+ | +------------+ +------------+ | |||
Figure 3: A More Efficient Representation of an X.509 Policy Tree | Figure 2: A More Efficient Representation of an X.509 Policy Tree | |||
This graph's size is bounded linearly by the total number of | This graph's size is bounded linearly by the total number of | |||
certificate policies (Section 4.2.1.4 of [RFC5280]) and policy | certificate policies (Section 4.2.1.4 of [RFC5280]) and policy | |||
mappings (Section 4.2.1.5 of [RFC5280]). The policy tree from | 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 | [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. | policy graph, so no information is lost in the graph representation. | |||
4.2. Verification Outputs | 4.2. Verification Outputs | |||
Section 6.1.6 of [RFC5280] describes the entire valid_policy_tree | Section 6.1.6 of [RFC5280] describes the entire valid_policy_tree | |||
structure as an output of the verification process. Section 12.2 of | structure as an output of the verification process. Section 12.2 of | |||
[X.509] instead only outputs the authorities-constrained policies, | [X.509] instead only outputs the authorities-constrained policies, | |||
the user-constrained policies, and their associated qualifiers. | the user-constrained policies, and their associated qualifiers. | |||
As the valid_policy_tree is the exponential structure, computing it | As the valid_policy_tree is the exponential structure, computing it | |||
reintroduces the denial-of-service vulnerability. X.509 | reintroduces the denial-of-service vulnerability. X.509 | |||
implementations SHOULD NOT output the entire valid_policy_tree | implementations SHOULD NOT output the entire valid_policy_tree | |||
structure and instead SHOULD limit output to just the set of | structure; instead, they SHOULD limit output to just the set of | |||
authorities-constrained and/or user-constrained policies, as | authorities-constrained and/or user-constrained policies, as | |||
described in [X.509]. Section 5.6 and Section 6 discuss other | described in [X.509]. Sections 5.6 and 6 discuss other mitigations | |||
mitigations for applications where this option is not available. | for applications where this option is not available. | |||
X.509 implementations MAY omit policy qualifiers from the output to | X.509 implementations MAY omit policy qualifiers from the output to | |||
simplify processing. Note Section 4.2.1.4 of [RFC5280] already | simplify processing. Note that Section 4.2.1.4 of [RFC5280] already | |||
recommends that certification authorities omit policy qualifiers from | recommends that certification authorities omit policy qualifiers from | |||
policy information terms. | policy information terms. | |||
5. Updates to RFC 5280 | 5. Updates to RFC 5280 | |||
This section provides updates to [RFC5280]. This implements the | This section provides updates to [RFC5280]. These updates implement | |||
changes described in Section 4. | the changes described in Section 4. | |||
5.1. Updates to Section 6.1 | 5.1. Updates to Section 6.1 | |||
This update replaces a paragraph of Section 6.1 of [RFC5280] as | Section 6.1 of [RFC5280] is updated as follows: | |||
follows: | ||||
OLD: | OLD: | |||
A particular certification path may not, however, be appropriate | | A particular certification path may not, however, be appropriate | |||
for all applications. Therefore, an application MAY augment this | | for all applications. Therefore, an application MAY augment this | |||
algorithm to further limit the set of valid paths. The path | | algorithm to further limit the set of valid paths. The path | |||
validation process also determines the set of certificate policies | | validation process also determines the set of certificate policies | |||
that are valid for this path, based on the certificate policies | | that are valid for this path, based on the certificate policies | |||
extension, policy mappings extension, policy constraints | | extension, policy mappings extension, policy constraints | |||
extension, and inhibit anyPolicy extension. To achieve this, the | | extension, and inhibit anyPolicy extension. To achieve this, the | |||
path validation algorithm constructs a valid policy tree. If the | | path validation algorithm constructs a valid policy tree. If the | |||
set of certificate policies that are valid for this path is not | | 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, | | empty, then the result will be a valid policy tree of depth n, | |||
otherwise the result will be a null valid policy tree. | | otherwise the result will be a null valid policy tree. | |||
NEW: | NEW: | |||
A particular certification path may not, however, be appropriate | | A particular certification path may not, however, be appropriate | |||
for all applications. Therefore, an application MAY augment this | | for all applications. Therefore, an application MAY augment this | |||
algorithm to further limit the set of valid paths. The path | | algorithm to further limit the set of valid paths. The path | |||
validation process also determines the set of certificate policies | | validation process also determines the set of certificate policies | |||
that are valid for this path, based on the certificate policies | | that are valid for this path, based on the certificate policies | |||
extension, policy mappings extension, policy constraints | | extension, policy mappings extension, policy constraints | |||
extension, and inhibit anyPolicy extension. To achieve this, the | | extension, and inhibit anyPolicy extension. To achieve this, the | |||
path validation algorithm constructs a valid policy set, which may | | path validation algorithm constructs a valid policy set, which may | |||
be empty if no certificate policies are valid for this path. | | be empty if no certificate policies are valid for this path. | |||
5.2. Updates to Section 6.1.2 | 5.2. Updates to Section 6.1.2 | |||
This update replaces entry (a) of Section 6.1.2 of [RFC5280] with the | The following replaces entry (a) in Section 6.1.2 of [RFC5280]: | |||
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 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 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 | | (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 | ||||
| Variable | ||||
5.3. Updates to Section 6.1.3 | 5.3. Updates to Section 6.1.3 | |||
This update replaces steps (d), (e), and (f) of Section 6.1.3 of | The following replaces steps (d), (e), and (f) in Section 6.1.3 of | |||
[RFC5280] with the following text: | [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 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 | ||||
(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} | | ||||
+-----------------+ | ||||
/ \ | ||||
/ \ | ||||
/ \ | ||||
v v | ||||
+-----------------+ +-----------------+ | ||||
| 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: | ||||
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}. 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} | | ||||
+-----------------+ +-----------------+ | ||||
| \ | | ||||
| \ | | ||||
| \ | | ||||
| \ | | ||||
| \ | | ||||
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 | ||||
(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 | ||||
+-----------+ | ||||
/ | \ | ||||
/ | \ | ||||
v v v | ||||
+-----------+ +-----------+ +-----------+ | ||||
| | | | | Y | depth i-2 | ||||
+-----------+ +-----------+ +-----------+ | ||||
| \ | | | ||||
| \ | | | ||||
v v v v | ||||
+-----------+ +-----------+ +-----------+ | ||||
| X | | | | X | depth i-1 | ||||
+-----------+ +-----------+ +-----------+ | ||||
/ | \ | ||||
/ | \ | ||||
v v v | ||||
+-----------+ +-----------+ +-----------+ | ||||
| | | | | | 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 | | (d) If the certificate policies extension is present in the | |||
valid_policy_graph is not equal to NULL; | | 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 4. | ||||
| | ||||
| +-----------------+ +-----------------+ | ||||
| | 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_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 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 | ||||
| anyPolicy with the qualifier set AP-Q and either (a) | ||||
| inhibit_anyPolicy is greater than 0 or (b) i<n and the | ||||
| certificate is self-issued, then: | ||||
| | ||||
| For each policy OID P-OID (including anyPolicy) that appears | ||||
| in 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}. 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 6. | ||||
| | ||||
| +-----------------+ +-----------------+ | ||||
| | 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 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 7 below. The two nodes at depth i-1 that are marked | ||||
| with an 'X' have no children, and they are deleted. Applying | ||||
| this rule to the resulting graph will cause the nodes at | ||||
| depth i-2 that is marked with a 'Y' to be deleted. In the | ||||
| resulting graph, there are no nodes of depth i-1 or less | ||||
| without children, and this step is complete. | ||||
| | ||||
| +-----------+ | ||||
| | | 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_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 | 5.4. Updates to Section 6.1.4 | |||
This update replaces step (b) of Section 6.1.4 of [RFC5280] with the | The following replaces step (b) in Section 6.1.4 of [RFC5280]: | |||
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, 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 | | (b) If a policy mappings extension is present, then for each | |||
i-1 or less without any child nodes, delete that | | issuerDomainPolicy ID-P in the policy mappings extension: | |||
node. Repeat this step until there are no nodes of | | | |||
depth i-1 or less without children. | | (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 | 5.5. Updates to Section 6.1.5 | |||
This update replaces step (g) of Section 6.1.5 of [RFC5280] with the | The following replaces step (g) in Section 6.1.5 of [RFC5280]: | |||
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. | ||||
(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 | ||||
which do not appear in user-initial-policy-set. | ||||
(ii) If anyPolicy appears in | | (g) Calculate the user_constrained_policy_set as follows. The | |||
authority_constrained_policy_set with qualifiers AP- | | user_constrained_policy_set is a set of policy OIDs, along | |||
Q, for each OID P-OID in user-initial-policy-set | | with associated policy qualifiers. | |||
which does not appear in user_constrained_policy_set, | | | |||
add P-OID with qualifiers AP-Q to | | (1) If the valid_policy_graph is NULL, set valid_policy_node_set | |||
user_constrained_policy_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. | ||||
Additionally, this update replaces the final paragraph as follows: | In addition, the final paragraph in Section 6.1.5 of [RFC5280] is | |||
updated as follows: | ||||
OLD: | OLD: | |||
If either (1) the value of explicit_policy variable is greater | | If either (1) the value of explicit_policy variable is greater | |||
than zero or (2) the valid_policy_tree is not NULL, then path | | than zero or (2) the valid_policy_tree is not NULL, then path | |||
processing has succeeded. | | processing has succeeded. | |||
NEW: | NEW: | |||
If either (1) the value of explicit_policy is greater than zero or | | If either (1) the value of explicit_policy is greater than zero, | |||
(2) the user_constrained_policy_set is not empty, then path | | or (2) the user_constrained_policy_set is not empty, then path | |||
processing has succeeded. | | processing has succeeded. | |||
5.6. Updates to Section 6.1.6 | 5.6. Updates to Section 6.1.6 | |||
This update replaces Section 6.1.6 of [RFC5280] with the following | The following replaces Section 6.1.6 of [RFC5280]: | |||
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. | ||||
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 | | If path processing succeeds, the procedure terminates, returning a | |||
compatibility with legacy systems may compute it from | | success indication together with the final value of the | |||
valid_policy_graph by recursively duplicating every multi-parent | | user_constrained_policy_set, the working_public_key, the | |||
node. This may be done on-demand when the calling application | | working_public_key_algorithm, and the | |||
first requests this output. However, this computation may consume | | working_public_key_parameters. | |||
exponential time and memory, so such implementations SHOULD | | | |||
mitigate denial-of-service in other ways, such as limiting the | | Note that the original procedure described in [RFC5280] included a | |||
depth or size of the tree. | | 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 in other ways, such as by limiting the | ||||
| depth or size of the tree. | ||||
6. Other Mitigations | 6. Other Mitigations | |||
X.509 implementations that are unable switch to the policy graph | X.509 implementations that are unable to switch to the policy graph | |||
structure SHOULD mitigate the denial-of-service attack in other ways. | structure SHOULD mitigate the denial-of-service attack in other ways. | |||
This section describes alternate mitigation and partial mitigation | This section describes alternate mitigation and partial mitigation | |||
strategies. | strategies. | |||
6.1. Verify Signatures First | 6.1. Verify Signatures First | |||
X.509 validators SHOULD verify signatures in certification paths | X.509 validators SHOULD verify signatures in certification paths | |||
before or in conjunction with policy verification. This limits the | before or in conjunction with policy verification. This limits the | |||
attack to entities in control of CA certificates. For some | attack to entities in control of CA certificates. For some | |||
applications, this may be sufficient to mitigate the attack. | applications, this may be sufficient to mitigate the attack. | |||
However, other applications may still be impacted. For example: | However, other applications may still be impacted, for example: | |||
* Any application that evaluates an untrusted PKI, such as a hosting | * Any application that evaluates an untrusted PKI, such as a hosting | |||
provider that evaluates a customer-supplied PKI | provider that evaluates a customer-supplied PKI | |||
* Any application that evaluates an otherwise trusted PKI, but where | * Any application that evaluates an otherwise trusted PKI, but where | |||
untrusted entities have technically-constrained intermediate | untrusted entities have technically constrained intermediate | |||
certificates where policy mapping and path length are | certificates where policy mapping and path length are | |||
unconstrained. | unconstrained. | |||
6.2. Limit Certificate Depth | 6.2. Limit Certificate Depth | |||
The policy tree grows exponentially in the depth of a certification | The policy tree grows exponentially in the depth of a certification | |||
path, so limiting the depth and certificate size can mitigate the | path, so limiting the depth and certificate size can mitigate the | |||
attack. | attack. | |||
However, this option may not be viable for all applications. Too low | However, this option may not be viable for all applications. Too low | |||
of a limit may reject existing paths which the application wishes to | of a limit may reject existing paths that the application wishes to | |||
accept. Too high of a limit may still admit a DoS attack for the | accept. Too high of a limit may still admit a denial-of-service | |||
application. By modifying the example in Section 3.2 to increase the | attack for the application. By modifying the example in Section 3.2 | |||
number of policies asserted in each certificate, an attacker could | to increase the number of policies asserted in each certificate, an | |||
still achieve O(N^(depth/2)) scaling. | attacker could still achieve O(N^(depth/2)) scaling. | |||
6.3. Limit Policy Tree Size | 6.3. Limit Policy Tree Size | |||
The attack can be mitigated by limiting the number of nodes in the | The attack can be mitigated by limiting the number of nodes in the | |||
policy tree, and rejecting the certification path if this limit is | policy tree and rejecting the certification path if this limit is | |||
reached. This limit should be set high enough to still admit | reached. This limit should be set high enough to still admit | |||
existing valid certification paths for the application, but low | existing valid certification paths for the application but low enough | |||
enough to no longer admit a DoS attack. | to no longer admit a denial-of-service attack. | |||
6.4. Inhibit Policy Mapping | 6.4. Inhibit Policy Mapping | |||
If policy mapping is disabled via the initial-policy-mapping-inhibit | If policy mapping is disabled via the initial-policy-mapping-inhibit | |||
setting (see Section 6.1.1 of [RFC5280]), the attack is mitigated. | setting (see Section 6.1.1 of [RFC5280]), the attack is mitigated. | |||
This also significantly simplifies the X.509 implementation, which | This also significantly simplifies the X.509 implementation, which | |||
reduces the risk of other security bugs. However, this will break | reduces the risk of other security bugs. However, this will break | |||
compatibility with any existing certification paths which rely on | compatibility with any existing certification paths that rely on | |||
policy mapping. | policy mapping. | |||
To facilitate this mitigation, certificate authorities SHOULD NOT | To facilitate this mitigation, certificate authorities SHOULD NOT | |||
issue certificates with the policy mappings extension | issue certificates with the policy mappings extension | |||
(Section 4.2.1.5 of [RFC5280]). Applications maintaining policies | (Section 4.2.1.5 of [RFC5280]). Applications maintaining policies | |||
for accepted trust anchors are RECOMMENDED to forbid this extension | for accepted trust anchors are RECOMMENDED to forbid this extension | |||
in participating certificate authorities. | in participating certificate authorities. | |||
6.5. Disable Policy Checking | 6.5. Disable Policy Checking | |||
An X.509 validator can mitigate this attack by disabling policy | An X.509 validator can mitigate this attack by disabling policy | |||
validation entirely. This may be viable for applications which do | validation entirely. This may be viable for applications that do not | |||
not require policy validation. In this case, critical policy-related | require policy validation. In this case, critical policy-related | |||
extensions, notably the policy constraints (Section 4.2.1.11 of | extensions, notably the policy constraints extension | |||
[RFC5280]), MUST be treated as unrecognized extensions as in | (Section 4.2.1.11 of [RFC5280]), MUST be treated as unrecognized | |||
Section 4.2 of [RFC5280] and be rejected. | extensions as described in Section 4.2 of [RFC5280] and be rejected. | |||
7. Implementation Status | ||||
This section is to be removed before publishing as an RFC. | ||||
This section records the status of known implementations of the | ||||
protocol defined by this specification at the time of posting of this | ||||
Internet-Draft, and is based on a proposal described in RFC 7942. | ||||
The description of implementations in this section is intended to | ||||
assist the IETF in its decision processes in progressing drafts to | ||||
RFCs. Please note that the listing of any individual implementation | ||||
here does not imply endorsement by the IETF. Furthermore, no effort | ||||
has been spent to verify the information presented here that was | ||||
supplied by IETF contributors. This is not intended as, and must not | ||||
be construed to be, a catalog of available implementations or their | ||||
features. Readers are advised to note that other implementations may | ||||
exist. | ||||
According to RFC 7942, "this will allow reviewers and working groups | ||||
to assign due consideration to documents that have the benefit of | ||||
running code, which may serve as evidence of valuable experimentation | ||||
and feedback that have made the implemented protocols more mature. | ||||
It is up to the individual working groups to use this information as | ||||
they see fit". | ||||
The following projects adopted the concept outlined in this document: | ||||
* [BoringSSL] | ||||
* [LibreSSL] | ||||
8. Security Considerations | 7. Security Considerations | |||
Section 3 discusses how [RFC5280]'s policy tree algorithm can lead to | Section 3 discusses how the policy tree algorithm in [RFC5280] can | |||
denial-of-service vulnerabilities in X.509-based applications, such | lead to denial-of-service vulnerabilities in X.509-based | |||
as [CVE-2023-0464] and [CVE-2023-23524]. | applications, such as [CVE-2023-0464] and [CVE-2023-23524]. | |||
Section 5 replaces this algorithm to avoid this issue. As discussed | Section 5 replaces this algorithm to avoid this issue. As discussed | |||
in Section 4.1, the new structure scales linearly with the input. | in Section 4.1, the new structure scales linearly with the input. | |||
This means input limits in X.509 validators will more naturally bound | This means input limits in X.509 validators will more naturally bound | |||
processing time, thus avoiding these vulnerabilities. | processing time, thus avoiding these vulnerabilities. | |||
9. IANA Considerations | 8. IANA Considerations | |||
This document has no IANA actions. | This document has no IANA actions. | |||
10. References | 9. References | |||
10.1. Normative References | 9.1. Normative References | |||
[RFC2119] Bradner, S., "Key words for use in RFCs to Indicate | [RFC2119] Bradner, S., "Key words for use in RFCs to Indicate | |||
Requirement Levels", BCP 14, RFC 2119, | Requirement Levels", BCP 14, RFC 2119, | |||
DOI 10.17487/RFC2119, March 1997, | DOI 10.17487/RFC2119, March 1997, | |||
<https://www.rfc-editor.org/rfc/rfc2119>. | <https://www.rfc-editor.org/info/rfc2119>. | |||
[RFC5280] Cooper, D., Santesson, S., Farrell, S., Boeyen, S., | [RFC5280] Cooper, D., Santesson, S., Farrell, S., Boeyen, S., | |||
Housley, R., and W. Polk, "Internet X.509 Public Key | Housley, R., and W. Polk, "Internet X.509 Public Key | |||
Infrastructure Certificate and Certificate Revocation List | Infrastructure Certificate and Certificate Revocation List | |||
(CRL) Profile", RFC 5280, DOI 10.17487/RFC5280, May 2008, | (CRL) Profile", RFC 5280, DOI 10.17487/RFC5280, May 2008, | |||
<https://www.rfc-editor.org/rfc/rfc5280>. | <https://www.rfc-editor.org/info/rfc5280>. | |||
[RFC8174] Leiba, B., "Ambiguity of Uppercase vs Lowercase in RFC | [RFC8174] Leiba, B., "Ambiguity of Uppercase vs Lowercase in RFC | |||
2119 Key Words", BCP 14, RFC 8174, DOI 10.17487/RFC8174, | 2119 Key Words", BCP 14, RFC 8174, DOI 10.17487/RFC8174, | |||
May 2017, <https://www.rfc-editor.org/rfc/rfc8174>. | May 2017, <https://www.rfc-editor.org/info/rfc8174>. | |||
10.2. Informative References | ||||
[BoringSSL] | 9.2. Informative References | |||
"BoringSSL", January 2024, | ||||
<https://boringssl.googlesource.com/boringssl>. | ||||
[CVE-2023-0464] | [CVE-2023-0464] | |||
"Excessive Resource Usage Verifying X.509 Policy | CVE, "Excessive Resource Usage Verifying X.509 Policy | |||
Constraints", March 2023, | Constraints", CVE-2023-0464, March 2023, | |||
<https://www.cve.org/CVERecord?id=CVE-2023-0464>. | <https://www.cve.org/CVERecord?id=CVE-2023-0464>. | |||
[CVE-2023-23524] | [CVE-2023-23524] | |||
"Processing a maliciously crafted certificate may lead to | CVE, "Processing a maliciously crafted certificate may | |||
a denial-of-service", February 2023, | lead to a denial-of-service", CVE-2023-23524, February | |||
<https://www.cve.org/CVERecord?id=CVE-2023-23524>. | 2023, <https://www.cve.org/CVERecord?id=CVE-2023-23524>. | |||
[LibreSSL] "LibreSSL", January 2024, <https://www.libressl.org/>. | ||||
[RFC8446] Rescorla, E., "The Transport Layer Security (TLS) Protocol | [RFC8446] Rescorla, E., "The Transport Layer Security (TLS) Protocol | |||
Version 1.3", RFC 8446, DOI 10.17487/RFC8446, August 2018, | Version 1.3", RFC 8446, DOI 10.17487/RFC8446, August 2018, | |||
<https://www.rfc-editor.org/rfc/rfc8446>. | <https://www.rfc-editor.org/info/rfc8446>. | |||
[X.509] International Telecommunications Union, "Information | [X.509] ITU-T, "Information technology - Open Systems | |||
technology - Open Systems Interconnection - The Directory: | Interconnection - The Directory: Public-key and attribute | |||
Public-key and attribute certificate frameworks", | certificate frameworks", ITU-T Recommendation X.509, | |||
ITU-T Recommendation X.509, October 2019. | October 2019, <https://www.itu.int/rec/T-REC-X.509>. | |||
Acknowledgements | Acknowledgements | |||
The author thanks Bob Beck, Adam Langley, Matt Mueller, and Ryan | The author thanks Bob Beck, Adam Langley, Matt Mueller, and Ryan | |||
Sleevi for many valuable discussions that led to discovering this | Sleevi for many valuable discussions that led to discovering this | |||
issue, understanding it, and developing the mitigation. The author | issue, understanding it, and developing the mitigation. The author | |||
also thanks Martin Thomson and Job Snijders for feedback on this | also thanks Martin Thomson, Job Snijders, and John Scudder for their | |||
document. | review and feedback on this document. | |||
Author's Address | Author's Address | |||
David Benjamin | David Benjamin | |||
Google LLC | Google LLC | |||
Email: davidben@google.com | Email: davidben@google.com | |||
End of changes. 75 change blocks. | ||||
593 lines changed or deleted | 534 lines changed or added | |||
This html diff was produced by rfcdiff 1.48. |