Network Working Group D. Benjamin Internet-Draft Google LLC Updates: 5280 (if approved) 28 March 2023 Intended status: Standards Track Expires: 29 September 2023 Updates to X.509 Policy Validation draft-davidben-x509-policy-graph-01 Abstract This document updates RFC 5280 to replace the algorithm for X.509 policy validation with an equivalent, more efficient algorithm. The original algorithm built a structure which scaled exponentially in the worst case, leaving implementations vulnerable to denial-of- service attacks. Status of This Memo This Internet-Draft is submitted in full conformance with the provisions of BCP 78 and BCP 79. Internet-Drafts are working documents of the Internet Engineering Task Force (IETF). Note that other groups may also distribute working documents as Internet-Drafts. The list of current Internet- Drafts is at https://datatracker.ietf.org/drafts/current/. Internet-Drafts are draft documents valid for a maximum of six months and may be updated, replaced, or obsoleted by other documents at any time. It is inappropriate to use Internet-Drafts as reference material or to cite them other than as "work in progress." This Internet-Draft will expire on 29 September 2023. Copyright Notice Copyright (c) 2023 IETF Trust and the persons identified as the document authors. All rights reserved. This document is subject to BCP 78 and the IETF Trust's Legal Provisions Relating to IETF Documents (https://trustee.ietf.org/ license-info) in effect on the date of publication of this document. Please review these documents carefully, as they describe your rights and restrictions with respect to this document. Code Components extracted from this document must include Revised BSD License text as described in Section 4.e of the Trust Legal Provisions and are provided without warranty as described in the Revised BSD License. Benjamin Expires 29 September 2023 [Page 1] Internet-Draft Updates to X.509 Policy Validation March 2023 Table of Contents 1. Introduction . . . . . . . . . . . . . . . . . . . . . . . . 2 1.1. Summary of Changes from RFC 5280 . . . . . . . . . . . . 2 2. Conventions and Definitions . . . . . . . . . . . . . . . . . 3 3. X.509 policy trees . . . . . . . . . . . . . . . . . . . . . 3 3.1. Exponential growth . . . . . . . . . . . . . . . . . . . 4 3.2. Policy graph . . . . . . . . . . . . . . . . . . . . . . 5 3.3. Verification outputs . . . . . . . . . . . . . . . . . . 7 3.4. Other mitigations . . . . . . . . . . . . . . . . . . . . 7 3.4.1. Limit certificate depth . . . . . . . . . . . . . . . 7 3.4.2. Limit policy tree size . . . . . . . . . . . . . . . 7 3.4.3. Inhibit policy mapping . . . . . . . . . . . . . . . 8 3.4.4. Disable policy checking . . . . . . . . . . . . . . . 8 3.4.5. Verify signatures first . . . . . . . . . . . . . . . 8 4. Updates to RFC 5280 . . . . . . . . . . . . . . . . . . . . . 8 4.1. Updates to Section 6.1 . . . . . . . . . . . . . . . . . 8 4.2. Updates to Section 6.1.2 . . . . . . . . . . . . . . . . 9 4.3. Updates to Section 6.1.3 . . . . . . . . . . . . . . . . 11 4.4. Updates to Section 6.1.4 . . . . . . . . . . . . . . . . 15 4.5. Updates to Section 6.1.5 . . . . . . . . . . . . . . . . 16 4.6. Updates to Section 6.1.6 . . . . . . . . . . . . . . . . 17 5. Security Considerations . . . . . . . . . . . . . . . . . . . 18 6. IANA Considerations . . . . . . . . . . . . . . . . . . . . . 18 7. References . . . . . . . . . . . . . . . . . . . . . . . . . 18 7.1. Normative References . . . . . . . . . . . . . . . . . . 18 7.2. Informative References . . . . . . . . . . . . . . . . . 18 Acknowledgements . . . . . . . . . . . . . . . . . . . . . . . . 18 Author's Address . . . . . . . . . . . . . . . . . . . . . . . . 19 1. Introduction [RFC5280] defines a suite of extensions for specifying certificate policies, along with a mechanism for mapping policies between subject and issuer policy domains in cross-certificates. This mechanism, when evaluated according to the algorithm in [RFC5280], Section 6.1 produces a policy tree, describing policies asserted by each certificate, and mappings between them. This tree can grow exponentially in the depth of the certification path. This can lead to a denial-of-service attack in X.509-based applications. 1.1. Summary of Changes from RFC 5280 The algorithm for processing certificate policies and policy mappings is replaced with one which builds an equivalent, but much more efficient structure. This new algorithm does not change the validity status of any certification path, nor which certificate policies are valid for it. Benjamin Expires 29 September 2023 [Page 2] Internet-Draft Updates to X.509 Policy Validation March 2023 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. X.509 policy trees The valid_policy_tree, defined in Section 6.1.2 of [RFC5280], is a tree of certificate policies. The nodes at any given depth in the tree correspond to policies asserted by a certificate in the certificate path. A node's parent policy is the policy in the issuer certificate which was mapped to this policy, and a node's children are the policies it was mapped to in the subject certificate. For example, suppose a certificate chain contains: * An intermediate certificate which asserts policy object identifiers (OIDs) OID1, OID2, and OID5. It contains mappings OID1 to OID3, and OID1 to OID4. * An end-entity certificate which asserts policy OIDs OID2, OID3, and OID6. This would result in the tree shown in Figure 1. +-----------+ Root: | anyPolicy | +-----------+ |{anyPolicy}| +-----------+ / \ / \ v v +------------+ +------------+ Intermediate: | OID1 | | OID2 | +------------+ +------------+ |{OID3, OID4}| | {OID2} | +------------+ +------------+ | | | | v v +------------+ +------------+ End-entity: | OID3 | | OID2 | +------------+ +------------+ Benjamin Expires 29 September 2023 [Page 3] Internet-Draft Updates to X.509 Policy Validation March 2023 Figure 1: An Example X.509 Policy Tree The complete algorithm for building this structure is described in steps (d), (e), and (f) of Section 6.1.3 of [RFC5280], steps (h), (i), (j) of Section 6.1.4 of [RFC5280], and steps (a), (b), and (g) of Section 6.1.5 of [RFC5280]. 3.1. Exponential growth The algorithm described in [RFC5280] grows exponentially in the worst case. In step (d.1) of Section 6.1.3 of [RFC5280], a single policy P can produce multiple child nodes if multiple issuer policies map to P. This can cause the tree size to increase in size multiplicatively at each level. In particular, consider a certificate chain where every intermediate certificate asserts policies OID1 and OID2, and then contains the full Cartesian product of mappings: * OID1 maps to OID1 * OID1 maps to OID2 * OID2 maps to OID1 * OID2 maps to OID2 At each depth, the tree would double in size. For example, if there are two intermediate certificates and one end-entity certificate, the resulting tree would be as depicted in Figure 2. Benjamin Expires 29 September 2023 [Page 4] Internet-Draft Updates to X.509 Policy Validation March 2023 +-----------------------+ | anyPolicy | +-----------------------+ | {anyPolicy} | +-----------------------+ / \ / \ v v +------------+ +------------+ | OID1 | | OID2 | +------------+ +------------+ |{OID1, OID2}| |{OID1, OID2}| +------------+ +------------+ / \ / \ / \ / \ v v v v +------------+ +------------+ +------------+ +------------+ | OID1 | | OID2 | | OID1 | | OID2 | +------------+ +------------+ +------------+ +------------+ |{OID1, OID2}| |{OID1, OID2}| |{OID1, OID2}| |{OID1, OID2}| +------------+ +------------+ +------------+ +------------+ | | | | | | | | v v v v v v v v +------+ +------+ +------+ +------+ +------+ +------+ +------+ +------+ | OID1 | | OID2 | | OID1 | | OID2 | | OID1 | | OID2 | | OID1 | | OID2 | +------+ +------+ +------+ +------+ +------+ +------+ +------+ +------+ Figure 2: An Example X.509 Policy Tree with Exponential Growth 3.2. Policy graph [RFC5280] describes a tree structure, but this is an unnecessarily inefficient representation of this information. A single certificate policy may produce multiple nodes, but each node is identical, with identical children. This document replaces the tree structure with a directed acyclic graph. Where [RFC5280] adds multiple duplicate nodes, this document adds a single node with multiple parents. See Section 4 for the procedure for building this structure. Figure 3 shows the updated representation of the above example. Benjamin Expires 29 September 2023 [Page 5] Internet-Draft Updates to X.509 Policy Validation March 2023 +-----------+ | anyPolicy | +-----------+ |{anyPolicy}| +-----------+ / \ / \ v v +------------+ +------------+ | OID1 | | OID2 | +------------+ +------------+ |{OID1, OID2}| |{OID1, OID2}| +------------+ +------------+ | \ / | | \ / | | \/ | | /\ | | / \ | v v v v +------------+ +------------+ | OID1 | | OID2 | +------------+ +------------+ |{OID1, OID2}| |{OID1, OID2}| +------------+ +------------+ | \ / | | \ / | | \/ | | /\ | | / \ | v v v v +------------+ +------------+ | OID1 | | OID2 | +------------+ +------------+ Figure 3: A More Efficient Representation of an X.509 Policy Tree This graph's size is bounded linearly by the total number of certificate policies (Section 4.2.1.4 of [RFC5280]) and policy mappings (Section 4.2.1.5 of [RFC5280]). The policy tree from [RFC5280] is the tree of all paths from the root to a leaf in the policy graph, so no information is lost in the graph representation. Implementations of X.509 SHOULD implement a policy graph structure instead of a policy tree. Benjamin Expires 29 September 2023 [Page 6] Internet-Draft Updates to X.509 Policy Validation March 2023 3.3. Verification outputs Section 6.1.6 of [RFC5280] describes the entire valid_policy_tree structure as an output of the verification process. Section 12.2 of [X.509] instead only outputs the authorities-constrained policies, the user-constrained policies, and their associated qualifiers. An implementation which outputs the entire tree may be unable switch the format to a more efficient one, as described in Section 3.2. X.509 implementations SHOULD NOT output the entire valid_policy_tree structure and instead SHOULD limit output to just the set of authorities-constrained and/or user-constrained policies, as described in [X.509]. X.509 implementations are additionally RECOMMENDED to omit policy qualifiers from the output, as this simplifies the process. Note Section 4.2.1.4 of [RFC5280] conversely recommends that certificate authorities omit policy qualifiers from policy information terms. This document reiterates this and RECOMMENDS that certificate authorities omit the policyQualifiers field in PolicyInformation structures. 3.4. Other mitigations X.509 implementations that are unable switch to the policy graph structure SHOULD mitigate the denial-of-service attack in other ways. This section describes alternate mitigation and partial mitigation strategies. 3.4.1. Limit certificate depth X.509 validators typically already allow limiting the depth of a certificate chain. This can limit the attack, however a large depth limit may still admit attacks. By modifying the example in Section 3.1 to increase the number of policies asserted in each certificate, an attacker could still achieve O(N^(depth/2)) scaling or higher. 3.4.2. Limit policy tree size If existing stable interfaces force the validator to build a full policy tree (see Section 3.3), the validator SHOULD limit the number of nodes in the policy tree, and reject the certification path if this limit is reached. Benjamin Expires 29 September 2023 [Page 7] Internet-Draft Updates to X.509 Policy Validation March 2023 3.4.3. Inhibit policy mapping If policy mapping is disabled via the initial-policy-mapping-inhibit setting (see Section 6.1.1 of [RFC5280]), the attack is mitigated. This also significantly simplifies the X.509 implementation, which reduces the risk of other security bugs. However, this will break compatibility with any existing certificate paths which rely on policy mapping. To faciliate this mitigation, certificate authorities SHOULD NOT issue certificates with the policy mappings extension (Section 4.2.1.5 of [RFC5280]). Applications maintaining policies for accepted trust anchors are RECOMMENDED to forbid this extension in participating certificate authorities. 3.4.4. Disable policy checking An X.509 validator can mitigate this attack by disabling policy validation entirely. This may be viable for applications which do not require policy validation. In this case, critical policy-related extensions, notably the policy constraints (Section 4.2.1.11 of [RFC5280]), MUST be treated as unrecognized extensions as in Section 4.2 of [RFC5280] and be rejected. 3.4.5. Verify signatures first X.509 validators SHOULD verify signatures in certificate paths before or in conjunction with policy verification. This limits the attack to entities in control of CA certificates. For some applications, this may be sufficient to mitigate the attack. However, other applications may still be impacted. For example: * Any application that evaluates an untrusted PKI, such as a hosting provider that evaluates a customer-supplied PKI * Any application that evaluates an otherwise trusted PKI, but where untrusted entities have technically-constrained intermediate certificates where policy mapping and path length are unconstrained. 4. Updates to RFC 5280 This section provides updates to [RFC5280]. 4.1. Updates to Section 6.1 This update replaces a paragraph of Section 6.1 of [RFC5280] as follows: Benjamin Expires 29 September 2023 [Page 8] Internet-Draft Updates to X.509 Policy Validation March 2023 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. 4.2. Updates to Section 6.1.2 This update replaces entry (a) of Section 6.1.2 of [RFC5280] with the following text: (a) valid_policy_graph: A directed acyclic graph of certificate policies with their optional qualifiers; each of the leaves of the graph represents a valid policy at this stage in the certification path validation. If valid policies exist at this stage in the certification path validation, the depth of the graph is equal to the number of certificates in the chain that have been processed. If valid policies do not exist at this stage in the certification path validation, the graph is set to NULL. Once the graph is set to NULL, policy processing ceases. Implementations MAY omit qualifiers if not returned in the output. Each node in the valid_policy_graph includes three data objects: the valid policy, a set of associated policy qualifiers, and a set of one or more expected policy values. Benjamin Expires 29 September 2023 [Page 9] Internet-Draft Updates to X.509 Policy Validation March 2023 Nodes in the graph can be divided into depths, numbered starting from zero. A node at depth x can have zero or more children at depth x+1, with the exception of depth zero, one or more parents at depth x-1. No other edges between nodes may exist. If the node is at depth x, the components of the node have the following semantics: (1) The valid_policy is a single policy OID representing a valid policy for the path of length x. (2) The qualifier_set is a set of policy qualifiers associated with the valid policy in certificate x. It is only necessary to maintain this field if policy qualifiers are returned to the application. See Section 6.1.5, step (g). (3) The expected_policy_set contains one or more policy OIDs that would satisfy this policy in the certificate x+1. The initial value of the valid_policy_graph is a single node 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. Benjamin Expires 29 September 2023 [Page 10] Internet-Draft Updates to X.509 Policy Validation March 2023 +----------------+ | anyPolicy | <---- valid_policy +----------------+ | {} | <---- qualifier_set +----------------+ | {anyPolicy} | <---- expected_policy_set +----------------+ Figure 4: Initial value of the valid_policy_graph State Variable 4.3. Updates to Section 6.1.3 This update replaces steps (d), (e), and (f) of Section 6.1.3 of [RFC5280] with the following text: (d) If the certificate policies extension is present in the certificate and the valid_policy_graph is not NULL, process the policy information by performing the following steps in order: (1) For each policy P not equal to anyPolicy in the certificate policies extension, let P-OID denote the OID for policy P and P-Q denote the qualifier set for policy P. Perform the following steps in order: (i) Let parent_nodes be the nodes at depth i-1 in 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_tree 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. Benjamin Expires 29 September 2023 [Page 11] Internet-Draft Updates to X.509 Policy Validation March 2023 +-----------------+ +-----------------+ | 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. Benjamin Expires 29 September 2023 [Page 12] Internet-Draft Updates to X.509 Policy Validation March 2023 +-----------------+ | anyPolicy | +-----------------+ | {} | +-----------------+ depth i-1 | {anyPolicy} | +-----------------+ / \ / \ / \ / \ +-----------------+ +-----------------+ | Gold | | Silver | +-----------------+ +-----------------+ | {} | | {Q-Silver} | depth i +-----------------+ +-----------------+ | {Gold} | | {Silver} | +-----------------+ +-----------------+ Figure 6: Processing Unmatched Policies when a Leaf Node Specifies anyPolicy (2) If the certificate policies extension includes the policy anyPolicy with the qualifier set AP-Q and either (a) inhibit_anyPolicy is greater than 0 or (b) i. [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, . 7.2. Informative References [X.509] International Telecommunications Union, "Information technology - Open Systems Interconnection - The Directory: Public-key and attribute certificate frameworks", ITU-T Recommendation X.509, October 2019. Acknowledgements The author thanks Bob Beck, Adam Langley, Matt Mueller, and Ryan Sleevi for many valuable discussions that led to discovering this issue, understanding it, and developing the mitigation. Benjamin Expires 29 September 2023 [Page 18] Internet-Draft Updates to X.509 Policy Validation March 2023 Author's Address David Benjamin Google LLC Email: davidben@google.com Benjamin Expires 29 September 2023 [Page 19]