Skip to main content

Updates to X.509 Policy Validation
draft-ietf-lamps-x509-policy-graph-04

The information below is for an old version of the document.
Document Type
This is an older version of an Internet-Draft whose latest revision state is "Active".
Author David Benjamin
Last updated 2024-02-01 (Latest revision 2024-01-17)
Replaces draft-davidben-x509-policy-graph
RFC stream Internet Engineering Task Force (IETF)
Formats
Reviews
Additional resources Mailing list discussion
Stream WG state Submitted to IESG for Publication
Document shepherd Russ Housley
Shepherd write-up Show Last changed 2023-12-09
IESG IESG state Approved-announcement to be sent::AD Followup
Consensus boilerplate Yes
Telechat date (None)
Responsible AD Roman Danyliw
Send notices to housley@vigilsec.com
IANA IANA review state IANA OK - No Actions Needed
draft-ietf-lamps-x509-policy-graph-04
Limited Additional Mechanisms for PKIX and SMIME             D. Benjamin
Internet-Draft                                                Google LLC
Updates: 5280 (if approved)                              17 January 2024
Intended status: Standards Track                                        
Expires: 20 July 2024

                   Updates to X.509 Policy Validation
                 draft-ietf-lamps-x509-policy-graph-04

Abstract

   This document updates RFC 5280 to replace the algorithm for X.509
   policy validation with an equivalent, more efficient algorithm.  The
   original algorithm built a structure which scaled exponentially in
   the worst case, leaving implementations vulnerable to denial-of-
   service attacks.

Discussion Venues

   This note is to be removed before publishing as an RFC.

   Discussion of this document takes place on the Limited Additional
   Mechanisms for PKIX and SMIME Working Group mailing list
   (spasm@ietf.org), which is archived at
   https://mailarchive.ietf.org/arch/browse/spasm/.

   Source for this draft and an issue tracker can be found at
   https://github.com/davidben/x509-policy-graph.

Status of This Memo

   This Internet-Draft is submitted in full conformance with the
   provisions of BCP 78 and BCP 79.

   Internet-Drafts are working documents of the Internet Engineering
   Task Force (IETF).  Note that other groups may also distribute
   working documents as Internet-Drafts.  The list of current Internet-
   Drafts is at https://datatracker.ietf.org/drafts/current/.

   Internet-Drafts are draft documents valid for a maximum of six months
   and may be updated, replaced, or obsoleted by other documents at any
   time.  It is inappropriate to use Internet-Drafts as reference
   material or to cite them other than as "work in progress."

   This Internet-Draft will expire on 20 July 2024.

Benjamin                  Expires 20 July 2024                  [Page 1]
Internet-Draft     Updates to X.509 Policy Validation       January 2024

Copyright Notice

   Copyright (c) 2024 IETF Trust and the persons identified as the
   document authors.  All rights reserved.

   This document is subject to BCP 78 and the IETF Trust's Legal
   Provisions Relating to IETF Documents (https://trustee.ietf.org/
   license-info) in effect on the date of publication of this document.
   Please review these documents carefully, as they describe your rights
   and restrictions with respect to this document.  Code Components
   extracted from this document must include Revised BSD License text as
   described in Section 4.e of the Trust Legal Provisions and are
   provided without warranty as described in the Revised BSD License.

Table of Contents

   1.  Introduction  . . . . . . . . . . . . . . . . . . . . . . . .   3
     1.1.  Summary of Changes from RFC 5280  . . . . . . . . . . . .   3
   2.  Conventions and Definitions . . . . . . . . . . . . . . . . .   4
   3.  Denial of Service Vulnerability . . . . . . . . . . . . . . .   4
     3.1.  Policy Trees  . . . . . . . . . . . . . . . . . . . . . .   4
     3.2.  Exponential Growth  . . . . . . . . . . . . . . . . . . .   5
     3.3.  Attack Vector . . . . . . . . . . . . . . . . . . . . . .   6
   4.  Avoiding Exponential Growth . . . . . . . . . . . . . . . . .   7
     4.1.  Policy Graphs . . . . . . . . . . . . . . . . . . . . . .   7
     4.2.  Verification Outputs  . . . . . . . . . . . . . . . . . .   8
   5.  Updates to RFC 5280 . . . . . . . . . . . . . . . . . . . . .   9
     5.1.  Updates to Section 6.1  . . . . . . . . . . . . . . . . .   9
     5.2.  Updates to Section 6.1.2  . . . . . . . . . . . . . . . .  10
     5.3.  Updates to Section 6.1.3  . . . . . . . . . . . . . . . .  11
     5.4.  Updates to Section 6.1.4  . . . . . . . . . . . . . . . .  15
     5.5.  Updates to Section 6.1.5  . . . . . . . . . . . . . . . .  16
     5.6.  Updates to Section 6.1.6  . . . . . . . . . . . . . . . .  17
   6.  Other Mitigations . . . . . . . . . . . . . . . . . . . . . .  18
     6.1.  Limit Certificate Depth . . . . . . . . . . . . . . . . .  18
     6.2.  Limit Policy Tree Size  . . . . . . . . . . . . . . . . .  19
     6.3.  Inhibit Policy Mapping  . . . . . . . . . . . . . . . . .  19
     6.4.  Disable Policy Checking . . . . . . . . . . . . . . . . .  19
     6.5.  Verify Signatures First . . . . . . . . . . . . . . . . .  19
   7.  Implementation Status . . . . . . . . . . . . . . . . . . . .  20
   8.  Security Considerations . . . . . . . . . . . . . . . . . . .  20
   9.  IANA Considerations . . . . . . . . . . . . . . . . . . . . .  20
   10. References  . . . . . . . . . . . . . . . . . . . . . . . . .  20
     10.1.  Normative References . . . . . . . . . . . . . . . . . .  20
     10.2.  Informative References . . . . . . . . . . . . . . . . .  21
   Acknowledgements  . . . . . . . . . . . . . . . . . . . . . . . .  22
   Author's Address  . . . . . . . . . . . . . . . . . . . . . . . .  22

Benjamin                  Expires 20 July 2024                  [Page 2]
Internet-Draft     Updates to X.509 Policy Validation       January 2024

1.  Introduction

   [RFC5280] defines a suite of extensions for determining the
   "policies" which apply to a certification path.  A policy is
   described by an object identifier (OID), and a set of optional
   qualifiers.

   Policy validation in [RFC5280] is complex.  As an overview, the
   certificate policies extension (Section 4.2.1.4 of [RFC5280])
   describes the policies, with optional qualifiers, under which an
   individual certificate was issued.  The policy mappings extension
   (Section 4.2.1.5 of [RFC5280]) allows a CA certificate to map its
   policy OIDs to other policy OIDs in certificates that it issues.
   Subject to these mappings and other extensions, the certification
   path's overall policy set is the intersection of policies asserted by
   each certificate in the path, collecting the corresponding
   qualifiers.

   The procedure in Section 6.1 of [RFC5280] determines this set in the
   course of certification path validation.  It does so by building a
   policy tree, containing policies asserted by each certificate and
   mappings between them.  This tree can grow exponentially in the depth
   of the certification path, which means an attacker, with a small
   input, can cause a path validator to consume excessive memory and
   computational resources.  This cost asymmetry can lead to a denial-
   of-service vulnerability in X.509-based applications, such as
   [CVE-2023-0464] and [CVE-2023-23524].

   Section 3 describes this vulnerability.  Section 4.1 describes the
   primary mitigation for this vulnerability, a replacement for the
   policy tree structure.  Section 5 provides updates to [RFC5280] which
   implement this change.  Finally, Section 6 discusses alternative
   mitigation strategies for X.509 applications.

1.1.  Summary of Changes from RFC 5280

   The algorithm for processing certificate policies and policy mappings
   is replaced with one which builds an equivalent, but much more
   efficient structure.  This new algorithm does not change the validity
   status of any certification path, nor which certificate policies are
   valid for it.

Benjamin                  Expires 20 July 2024                  [Page 3]
Internet-Draft     Updates to X.509 Policy Validation       January 2024

2.  Conventions and Definitions

   The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT",
   "SHOULD", "SHOULD NOT", "RECOMMENDED", "NOT RECOMMENDED", "MAY", and
   "OPTIONAL" in this document are to be interpreted as described in BCP
   14 [RFC2119] [RFC8174] when, and only when, they appear in all
   capitals, as shown here.

3.  Denial of Service Vulnerability

   This section discusses how the path validation algorithm defined in
   Section 6.1.2 of [RFC5280] can lead to a denial-of-service
   vulnerability in X.509-based applications.

3.1.  Policy Trees

   Section 6.1.2 of [RFC5280] constructs the valid_policy_tree, a tree
   of certificate policies, during certification path validation.  The
   nodes at any given depth in the tree correspond to policies asserted
   by a certificate in the certification path.  A node's parent policy
   is the policy in the issuer certificate which was mapped to this
   policy, and a node's children are the policies it was mapped to in
   the subject certificate.

   For example, suppose a certification path contains:

   *  An intermediate certificate which asserts policy OIDs OID1, OID2,
      and OID5.  It contains mappings OID1 to OID3, and OID1 to OID4.

   *  An end-entity certificate which asserts policy OIDs OID2, OID3,
      and OID6.

   This would result in the tree shown in Figure 1.  Note that OID5 and
   OID6 are not included or mapped across the whole path, so they do not
   appear in the final structure.

Benjamin                  Expires 20 July 2024                  [Page 4]
Internet-Draft     Updates to X.509 Policy Validation       January 2024

                               +-----------+
              Root:            | anyPolicy |
                               +-----------+
                               |{anyPolicy}|
                               +-----------+
                                /          \
                               /            \
                              v              v
                     +------------+      +------------+
      Intermediate:  |    OID1    |      |    OID2    |
   (OID5 discarded)  +------------+      +------------+
                     |{OID3, OID4}|      |   {OID2}   |
                     +------------+      +------------+
                           |                   |
                           |                   |
                           v                   v
                     +------------+      +------------+
        End-entity:  |    OID3    |      |    OID2    |
   (OID6 discarded)  +------------+      +------------+

                   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.2.  Exponential Growth

   The valid_policy_tree grows exponentially in the worst case.  In step
   (d.1) of Section 6.1.3 of [RFC5280], a single policy P can produce
   multiple child nodes if multiple issuer policies map to P.  This can
   cause the tree size to increase in size multiplicatively at each
   level.

   In particular, consider a certificate chain where every intermediate
   certificate asserts policies OID1 and OID2, and then contains the
   full Cartesian product of mappings:

   *  OID1 maps to OID1

   *  OID1 maps to OID2

   *  OID2 maps to OID1

   *  OID2 maps to OID2

Benjamin                  Expires 20 July 2024                  [Page 5]
Internet-Draft     Updates to X.509 Policy Validation       January 2024

   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.

                         +-----------------------+
                         |        anyPolicy      |
                         +-----------------------+
                         |       {anyPolicy}     |
                         +-----------------------+
                          /                     \
                         /                       \
                        v                         v
             +------------+                      +------------+
             |    OID1    |                      |    OID2    |
             +------------+                      +------------+
             |{OID1, OID2}|                      |{OID1, OID2}|
             +------------+                      +------------+
              /         \                          /         \
             /           \                        /           \
            v             v                      v             v
   +------------+    +------------+    +------------+    +------------+
   |    OID1    |    |    OID2    |    |    OID1    |    |    OID2    |
   +------------+    +------------+    +------------+    +------------+
   |{OID1, OID2}|    |{OID1, OID2}|    |{OID1, OID2}|    |{OID1, OID2}|
   +------------+    +------------+    +------------+    +------------+
     |       |         |       |         |       |         |       |
     v       v         v       v         v       v         v       v
 +------+ +------+ +------+ +------+ +------+ +------+ +------+ +------+
 | OID1 | | OID2 | | OID1 | | OID2 | | OID1 | | OID2 | | OID1 | | OID2 |
 +------+ +------+ +------+ +------+ +------+ +------+ +------+ +------+

     Figure 2: An Example X.509 Policy Tree with Exponential Growth

3.3.  Attack Vector

   An attacker can use the exponential growth to mount a denial-of-
   service attack against an X.509-based application.  The attacker
   sends certificate chain as in Section 3.2 and triggers the target
   application's certificate validation process.  For example, the
   target application may be a TLS [RFC8446] server that performs client
   certificate validation.  The target application will consume far more
   resources processing the input than the attacker consumed to send it,
   preventing it from servicing other clients.

Benjamin                  Expires 20 July 2024                  [Page 6]
Internet-Draft     Updates to X.509 Policy Validation       January 2024

4.  Avoiding Exponential Growth

   This document mitigates the denial-of-service vulnerability described
   in Section 3 by replacing the policy tree with a policy graph
   structure, described in this section.  The policy graph grows
   linearly instead of exponentially.  This removes the asymmetric cost
   in policy validation.

   X.509 implementations SHOULD perform policy validation by building a
   policy graph, following the procedure described in Section 5.  This
   replacement procedure computes the same policies as in [RFC5280],
   however one of the outputs is in a different form.  See Section 4.2
   for details.  Section 6 describes alternative mitigations for
   implementations that depend on the original, exponential-sized
   output.

4.1.  Policy Graphs

   The tree structure from [RFC5280] is an unnecessarily inefficient
   representation of a certification path's policy mappings.  A single
   certificate policy may correspond to multiple nodes, but each node is
   identical, with identical children.  This redundancy is the source of
   the exponential growth described in Section 3.2.

   A policy graph is a directed acyclic graph of policy nodes.  Where
   [RFC5280] adds multiple duplicate nodes, a policy graph adds a single
   node with multiple parents.  See Section 5 for the procedure for
   building this structure.  Figure 3 shows the updated representation
   of the example in Figure 2.

Benjamin                  Expires 20 July 2024                  [Page 7]
Internet-Draft     Updates to X.509 Policy Validation       January 2024

                 +-----------+
                 | anyPolicy |
                 +-----------+
                 |{anyPolicy}|
                 +-----------+
                 /           \
                /             \
               v               v
        +------------+  +------------+
        |    OID1    |  |    OID2    |
        +------------+  +------------+
        |{OID1, OID2}|  |{OID1, OID2}|
        +------------+  +------------+
             |      \    /     |
             |       \  /      |
             |        \/       |
             |        /\       |
             |       /  \      |
             v      v    v     v
        +------------+  +------------+
        |    OID1    |  |    OID2    |
        +------------+  +------------+
        |{OID1, OID2}|  |{OID1, OID2}|
        +------------+  +------------+
             |      \    /     |
             |       \  /      |
             |        \/       |
             |        /\       |
             |       /  \      |
             v      v    v     v
        +------------+  +------------+
        |    OID1    |  |    OID2    |
        +------------+  +------------+

     Figure 3: A More Efficient Representation of an X.509 Policy Tree

   This graph's size is bounded linearly by the total number of
   certificate policies (Section 4.2.1.4 of [RFC5280]) and policy
   mappings (Section 4.2.1.5 of [RFC5280]).  The policy tree from
   [RFC5280] is the tree of all paths from the root to a leaf in the
   policy graph, so no information is lost in the graph representation.

4.2.  Verification Outputs

   Section 6.1.6 of [RFC5280] describes the entire valid_policy_tree
   structure as an output of the verification process.  Section 12.2 of
   [X.509] instead only outputs the authorities-constrained policies,
   the user-constrained policies, and their associated qualifiers.

Benjamin                  Expires 20 July 2024                  [Page 8]
Internet-Draft     Updates to X.509 Policy Validation       January 2024

   As the valid_policy_tree is the exponential structure, computing it
   reintroduces the denial-of-service vulnerability.  X.509
   implementations SHOULD NOT output the entire valid_policy_tree
   structure and instead SHOULD limit output to just the set of
   authorities-constrained and/or user-constrained policies, as
   described in [X.509].  Section 5.6 and Section 6 discuss other
   mitigations for applications where this option is not available.

   X.509 implementations MAY omit policy qualifiers from the output to
   simplify processing.  Note Section 4.2.1.4 of [RFC5280] already
   recommends that certification authorities omit policy qualifiers from
   policy information terms.

5.  Updates to RFC 5280

   This section provides updates to [RFC5280].  This implements the
   changes described in Section 4.

5.1.  Updates to Section 6.1

   This update replaces a paragraph of Section 6.1 of [RFC5280] as
   follows:

   OLD:

      A particular certification path may not, however, be appropriate
      for all applications.  Therefore, an application MAY augment this
      algorithm to further limit the set of valid paths.  The path
      validation process also determines the set of certificate policies
      that are valid for this path, based on the certificate policies
      extension, policy mappings extension, policy constraints
      extension, and inhibit anyPolicy extension.  To achieve this, the
      path validation algorithm constructs a valid policy tree.  If the
      set of certificate policies that are valid for this path is not
      empty, then the result will be a valid policy tree of depth n,
      otherwise the result will be a null valid policy tree.

   NEW:

      A particular certification path may not, however, be appropriate
      for all applications.  Therefore, an application MAY augment this
      algorithm to further limit the set of valid paths.  The path
      validation process also determines the set of certificate policies
      that are valid for this path, based on the certificate policies
      extension, policy mappings extension, policy constraints
      extension, and inhibit anyPolicy extension.  To achieve this, the
      path validation algorithm constructs a valid policy set, which may
      be empty if no certificate policies are valid for this path.

Benjamin                  Expires 20 July 2024                  [Page 9]
Internet-Draft     Updates to X.509 Policy Validation       January 2024

5.2.  Updates to Section 6.1.2

   This update replaces entry (a) of Section 6.1.2 of [RFC5280] with the
   following text:

   (a)  valid_policy_graph: A directed acyclic graph of certificate
        policies with their optional qualifiers; each of the leaves of
        the graph represents a valid policy at this stage in the
        certification path validation.  If valid policies exist at this
        stage in the certification path validation, the depth of the
        graph is equal to the number of certificates in the chain that
        have been processed.  If valid policies do not exist at this
        stage in the certification path validation, the graph is set to
        NULL.  Once the graph is set to NULL, policy processing ceases.
        Implementations MAY omit qualifiers if not returned in the
        output.

        Each node in the valid_policy_graph includes three data objects:
        the valid policy, a set of associated policy qualifiers, and a
        set of one or more expected policy values.

        Nodes in the graph can be divided into depths, numbered starting
        from zero.  A node at depth x can have zero or more children at
        depth x+1 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:

Benjamin                  Expires 20 July 2024                 [Page 10]
Internet-Draft     Updates to X.509 Policy Validation       January 2024

        *  For any depth x and policy OID P-OID, there is at most one
           node at depth x whose valid_policy is P-OID.

        *  The expected_policy_set of a node whose valid_policy is
           anyPolicy is always {anyPolicy}.

        *  A node at depth x whose valid_policy is anyPolicy, except for
           the one at depth zero, always has exactly one parent: a node
           at depth x-1 whose valid_policy is also anyPolicy.

        *  Each node at depth greater than 0 has either one or more
           parent nodes whose valid_policy is not anyPolicy, or a single
           parent node whose valid_policy is anyPolicy.  That is, a node
           cannot simultaneously be a child of both anyPolicy and some
           non-anyPolicy OID.

        Figure 4 is a graphic representation of the initial state of the
        valid_policy_graph.  Additional figures will use this format to
        describe changes in the valid_policy_graph during path
        processing.

            +----------------+
            |   anyPolicy    |   <---- valid_policy
            +----------------+
            |       {}       |   <---- qualifier_set
            +----------------+
            |  {anyPolicy}   |   <---- expected_policy_set
            +----------------+

        Figure 4: Initial value of the valid_policy_graph State Variable

5.3.  Updates to Section 6.1.3

   This update replaces steps (d), (e), and (f) of Section 6.1.3 of
   [RFC5280] with the following text:

   (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,

Benjamin                  Expires 20 July 2024                 [Page 11]
Internet-Draft     Updates to X.509 Policy Validation       January 2024

                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

Benjamin                  Expires 20 July 2024                 [Page 12]
Internet-Draft     Updates to X.509 Policy Validation       January 2024

                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.

Benjamin                  Expires 20 July 2024                 [Page 13]
Internet-Draft     Updates to X.509 Policy Validation       January 2024

             For example, consider a valid_policy_graph with a node of
             depth i-1 where the expected_policy_set is {Gold, Silver},
             and a second node of depth i-1 where the
             expected_policy_set is {Gold, Bronze}. Assume anyPolicy
             appears in the certificate policies extension of
             certificate i with policy qualifiers AP-Q, but Gold and
             Silver do not appear.  This rule will generate two child
             nodes of depth i, one for each policy.  The result is shown
             below as Figure 7.

                 +-----------------+   +-----------------+
                 |       Red       |   |       Blue      |
                 +-----------------+   +-----------------+
                 |       {}        |   |       {}        |   depth i-1
                 +-----------------+   +-----------------+
                 |  {Gold, Silver} |   |  {Gold, Bronze} |
                 +-----------------+   +-----------------+
                         |         \            |
                         |          \           |
                         |           \          |
                         |            \         |
                         |             \        |
                         v              v       v
                 +-----------------+   +-----------------+
                 |     Silver      |   |       Gold      |
                 +-----------------+   +-----------------+
                 |     {AP-Q}      |   |      {AP-Q}     |   depth i
                 +-----------------+   +-----------------+
                 |    {Silver}     |   |      {Gold}     |
                 +-----------------+   +-----------------+

                   Figure 7: Processing Unmatched Policies When the
                  Certificate Policies Extension Specifies anyPolicy

        (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.

Benjamin                  Expires 20 July 2024                 [Page 14]
Internet-Draft     Updates to X.509 Policy Validation       January 2024

                               +-----------+
                               |           | 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
        valid_policy_graph is not equal to NULL;

5.4.  Updates to Section 6.1.4

   This update replaces step (b) of Section 6.1.4 of [RFC5280] with the
   following text:

   (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.

Benjamin                  Expires 20 July 2024                 [Page 15]
Internet-Draft     Updates to X.509 Policy Validation       January 2024

        (2)  If the policy_mapping variable is greater than 0, no node
             of depth i in the valid_policy_graph has a valid_policy of
             ID-P, but there is a node of depth i with a valid_policy of
             anyPolicy, then generate a child node of the node of depth
             i-1 that has a valid_policy of anyPolicy as follows:

             (i)    set the valid_policy to ID-P;

             (ii)   set the qualifier_set to the qualifier set of the
                    policy anyPolicy in the certificate policies
                    extension of certificate i; and

             (iii)  set the expected_policy_set to the set of
                    subjectDomainPolicy values that are specified as
                    equivalent to ID-P by the policy mappings extension.

        (3)  If the policy_mapping variable is equal to 0:

             (i)   delete the node, if any, of depth i in the
                   valid_policy_graph where ID-P is the valid_policy.

             (ii)  If there is a node in the valid_policy_graph of depth
                   i-1 or less without any child nodes, delete that
                   node.  Repeat this step until there are no nodes of
                   depth i-1 or less without children.

5.5.  Updates to Section 6.1.5

   This update replaces step (g) of Section 6.1.5 of [RFC5280] with the
   following text:

   (g)  Calculate the user_constrained_policy_set as follows.  The
        user_constrained_policy_set is a set of policy OIDs, along with
        associated policy qualifiers.

        (1)  If the valid_policy_graph is NULL, set
             valid_policy_node_set to the empty set.

        (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.

Benjamin                  Expires 20 July 2024                 [Page 16]
Internet-Draft     Updates to X.509 Policy Validation       January 2024

        (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
                   authority_constrained_policy_set with qualifiers AP-
                   Q, for each OID P-OID in user-initial-policy-set
                   which does not appear in user_constrained_policy_set,
                   add P-OID with qualifiers AP-Q to
                   user_constrained_policy_set.

   Additionally, this update replaces the final paragraph as follows:

   OLD:

      If either (1) the value of explicit_policy variable is greater
      than zero or (2) the valid_policy_tree is not NULL, then path
      processing has succeeded.

   NEW:

      If either (1) the value of explicit_policy variable is greater
      than zero or (2) the user_constrained_policy_set is not empty,
      then path processing has succeeded.

5.6.  Updates to Section 6.1.6

   This update replaces Section 6.1.6 of [RFC5280] with the following
   text:

Benjamin                  Expires 20 July 2024                 [Page 17]
Internet-Draft     Updates to X.509 Policy Validation       January 2024

      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
      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 limiting the
      depth or size of the tree.

6.  Other Mitigations

   X.509 implementations that are unable switch to the policy graph
   structure SHOULD mitigate the denial-of-service attack in other ways.
   This section describes alternate mitigation and partial mitigation
   strategies.

6.1.  Limit Certificate Depth

   The policy tree grows exponentially in the depth of a certification
   path, so limiting the depth and certificate size can mitigate the
   attack.

   However, this option may not be viable for all applications.  Too low
   of a limit may reject existing paths which the application wishes to
   accept.  Too high of a limit may still admit a DoS attack for the
   application.  By modifying the example in Section 3.2 to increase the
   number of policies asserted in each ertificate, an attacker could
   still achieve O(N^(depth/2)) scaling.

Benjamin                  Expires 20 July 2024                 [Page 18]
Internet-Draft     Updates to X.509 Policy Validation       January 2024

6.2.  Limit Policy Tree Size

   The attack can be mitigated by limiting the number of nodes in the
   policy tree, and rejecting the certification path if this limit is
   reached.  This limit should be set high enough to still admit
   existing valid certification paths for the application, but low
   enough to no longer admit a DoS attack.

6.3.  Inhibit Policy Mapping

   If policy mapping is disabled via the initial-policy-mapping-inhibit
   setting (see Section 6.1.1 of [RFC5280]), the attack is mitigated.
   This also significantly simplifies the X.509 implementation, which
   reduces the risk of other security bugs.  However, this will break
   compatibility with any existing certification paths which rely on
   policy mapping.

   To facilitate this mitigation, certificate authorities SHOULD NOT
   issue certificates with the policy mappings extension
   (Section 4.2.1.5 of [RFC5280]).  Applications maintaining policies
   for accepted trust anchors are RECOMMENDED to forbid this extension
   in participating certificate authorities.

6.4.  Disable Policy Checking

   An X.509 validator can mitigate this attack by disabling policy
   validation entirely.  This may be viable for applications which do
   not require policy validation.  In this case, critical policy-related
   extensions, notably the policy constraints (Section 4.2.1.11 of
   [RFC5280]), MUST be treated as unrecognized extensions as in
   Section 4.2 of [RFC5280] and be rejected.

6.5.  Verify Signatures First

   X.509 validators SHOULD verify signatures in certification paths
   before or in conjunction with policy verification.  This limits the
   attack to entities in control of CA certificates.  For some
   applications, this may be sufficient to mitigate the attack.
   However, other applications may still be impacted.  For example:

   *  Any application that evaluates an untrusted PKI, such as a hosting
      provider that evaluates a customer-supplied PKI

   *  Any application that evaluates an otherwise trusted PKI, but where
      untrusted entities have technically-constrained intermediate
      certificates where policy mapping and path length are
      unconstrained.

Benjamin                  Expires 20 July 2024                 [Page 19]
Internet-Draft     Updates to X.509 Policy Validation       January 2024

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

   Section 3 discusses how [RFC5280]'s policy tree algorithm can lead to
   denial-of-service vulnerabilities in X.509-based applications, such
   as [CVE-2023-0464] and [CVE-2023-23524].

   Section 5 replaces this algorithm to avoid this issue.  As discussed
   in Section 4.1, the new structure scales linearly with the input.
   This means input limits in X.509 validators will more naturally bound
   processing time, thus avoiding these vulnerabilities.

9.  IANA Considerations

   This document has no IANA actions.

10.  References

10.1.  Normative References

Benjamin                  Expires 20 July 2024                 [Page 20]
Internet-Draft     Updates to X.509 Policy Validation       January 2024

   [RFC2119]  Bradner, S., "Key words for use in RFCs to Indicate
              Requirement Levels", BCP 14, RFC 2119,
              DOI 10.17487/RFC2119, March 1997,
              <https://www.rfc-editor.org/rfc/rfc2119>.

   [RFC5280]  Cooper, D., Santesson, S., Farrell, S., Boeyen, S.,
              Housley, R., and W. Polk, "Internet X.509 Public Key
              Infrastructure Certificate and Certificate Revocation List
              (CRL) Profile", RFC 5280, DOI 10.17487/RFC5280, May 2008,
              <https://www.rfc-editor.org/rfc/rfc5280>.

   [RFC8174]  Leiba, B., "Ambiguity of Uppercase vs Lowercase in RFC
              2119 Key Words", BCP 14, RFC 8174, DOI 10.17487/RFC8174,
              May 2017, <https://www.rfc-editor.org/rfc/rfc8174>.

10.2.  Informative References

   [BoringSSL]
              "BoringSSL", January 2024,
              <https://boringssl.googlesource.com/boringssl>.

   [CVE-2023-0464]
              "Excessive Resource Usage Verifying X.509 Policy
              Constraints", March 2023,
              <https://www.cve.org/CVERecord?id=CVE-2023-0464>.

   [CVE-2023-23524]
              "Processing a maliciously crafted certificate may lead to
              a denial-of-service", February 2023,
              <https://www.cve.org/CVERecord?id=CVE-2023-23524>.

   [LibreSSL] "LibreSSL", January 2024, <https://www.libressl.org/>.

   [RFC8446]  Rescorla, E., "The Transport Layer Security (TLS) Protocol
              Version 1.3", RFC 8446, DOI 10.17487/RFC8446, August 2018,
              <https://www.rfc-editor.org/rfc/rfc8446>.

   [X.509]    International Telecommunications Union, "Information
              technology - Open Systems Interconnection - The Directory:
              Public-key and attribute certificate frameworks",
              ITU-T Recommendation X.509, October 2019.

Benjamin                  Expires 20 July 2024                 [Page 21]
Internet-Draft     Updates to X.509 Policy Validation       January 2024

Acknowledgements

   The author thanks Bob Beck, Adam Langley, Matt Mueller, and Ryan
   Sleevi for many valuable discussions that led to discovering this
   issue, understanding it, and developing the mitigation.  The author
   also thanks Martin Thomson and Job Snijders for feedback on this
   document.

Author's Address

   David Benjamin
   Google LLC
   Email: davidben@google.com

Benjamin                  Expires 20 July 2024                 [Page 22]