<?xml version='1.0' encoding='utf-8'?>
<rfc xmlns:xi="http://www.w3.org/2001/XInclude" version="3" ipr="trust200902" docName="draft-ietf-lamps-x509-policy-graph-05" number="9618" category="std" consensus="true" submissionType="IETF" obsoletes="" updates="5280" tocInclude="true" sortRefs="true" symRefs="true" xml:lang="en" prepTime="2024-08-30T15:40:31" indexInclude="true" scripts="Common,Latin" tocDepth="3">
  <link href="https://datatracker.ietf.org/doc/draft-ietf-lamps-x509-policy-graph-05" rel="prev"/>
  <link href="https://dx.doi.org/10.17487/rfc9618" rel="alternate"/>
  <link href="urn:issn:2070-1721" rel="alternate"/>
  <front>
    <title abbrev="Updates to X.509 Policy Validation">Updates to X.509 Policy Validation</title>
    <seriesInfo name="RFC" value="9618" stream="IETF"/>
    <author initials="D." surname="Benjamin" fullname="David Benjamin">
      <organization showOnFrontPage="true">Google LLC</organization>
      <address>
        <email>davidben@google.com</email>
      </address>
    </author>
    <date month="08" year="2024"/>
    <area>sec</area>
    <workgroup>lamps</workgroup>
    <keyword>Certificate</keyword>
    <abstract pn="section-abstract">
      <t indent="0" pn="section-abstract-1">This document updates RFC 5280 to replace the algorithm for
    X.509 policy validation with an equivalent, more efficient algorithm. The
    original algorithm built a structure that scaled exponentially in the
    worst case, leaving implementations vulnerable to denial-of-service
    attacks.</t>
    </abstract>
    <boilerplate>
      <section anchor="status-of-memo" numbered="false" removeInRFC="false" toc="exclude" pn="section-boilerplate.1">
        <name slugifiedName="name-status-of-this-memo">Status of This Memo</name>
        <t indent="0" pn="section-boilerplate.1-1">
            This is an Internet Standards Track document.
        </t>
        <t indent="0" pn="section-boilerplate.1-2">
            This document is a product of the Internet Engineering Task Force
            (IETF).  It represents the consensus of the IETF community.  It has
            received public review and has been approved for publication by
            the Internet Engineering Steering Group (IESG).  Further
            information on Internet Standards is available in Section 2 of 
            RFC 7841.
        </t>
        <t indent="0" pn="section-boilerplate.1-3">
            Information about the current status of this document, any
            errata, and how to provide feedback on it may be obtained at
            <eref target="https://www.rfc-editor.org/info/rfc9618" brackets="none"/>.
        </t>
      </section>
      <section anchor="copyright" numbered="false" removeInRFC="false" toc="exclude" pn="section-boilerplate.2">
        <name slugifiedName="name-copyright-notice">Copyright Notice</name>
        <t indent="0" pn="section-boilerplate.2-1">
            Copyright (c) 2024 IETF Trust and the persons identified as the
            document authors. All rights reserved.
        </t>
        <t indent="0" pn="section-boilerplate.2-2">
            This document is subject to BCP 78 and the IETF Trust's Legal
            Provisions Relating to IETF Documents
            (<eref target="https://trustee.ietf.org/license-info" brackets="none"/>) 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.
        </t>
      </section>
    </boilerplate>
    <toc>
      <section anchor="toc" numbered="false" removeInRFC="false" toc="exclude" pn="section-toc.1">
        <name slugifiedName="name-table-of-contents">Table of Contents</name>
        <ul bare="true" empty="true" indent="2" spacing="compact" pn="section-toc.1-1">
          <li pn="section-toc.1-1.1">
            <t indent="0" keepWithNext="true" pn="section-toc.1-1.1.1"><xref derivedContent="1" format="counter" sectionFormat="of" target="section-1"/>.  <xref derivedContent="" format="title" sectionFormat="of" target="name-introduction">Introduction</xref></t>
            <ul bare="true" empty="true" indent="2" spacing="compact" pn="section-toc.1-1.1.2">
              <li pn="section-toc.1-1.1.2.1">
                <t indent="0" keepWithNext="true" pn="section-toc.1-1.1.2.1.1"><xref derivedContent="1.1" format="counter" sectionFormat="of" target="section-1.1"/>.  <xref derivedContent="" format="title" sectionFormat="of" target="name-summary-of-changes-from-rfc">Summary of Changes from RFC 5280</xref></t>
              </li>
            </ul>
          </li>
          <li pn="section-toc.1-1.2">
            <t indent="0" keepWithNext="true" pn="section-toc.1-1.2.1"><xref derivedContent="2" format="counter" sectionFormat="of" target="section-2"/>.  <xref derivedContent="" format="title" sectionFormat="of" target="name-conventions-and-definitions">Conventions and Definitions</xref></t>
          </li>
          <li pn="section-toc.1-1.3">
            <t indent="0" pn="section-toc.1-1.3.1"><xref derivedContent="3" format="counter" sectionFormat="of" target="section-3"/>.  <xref derivedContent="" format="title" sectionFormat="of" target="name-denial-of-service-vulnerabi">Denial-of-Service Vulnerability</xref></t>
            <ul bare="true" empty="true" indent="2" spacing="compact" pn="section-toc.1-1.3.2">
              <li pn="section-toc.1-1.3.2.1">
                <t indent="0" pn="section-toc.1-1.3.2.1.1"><xref derivedContent="3.1" format="counter" sectionFormat="of" target="section-3.1"/>.  <xref derivedContent="" format="title" sectionFormat="of" target="name-policy-trees">Policy Trees</xref></t>
              </li>
              <li pn="section-toc.1-1.3.2.2">
                <t indent="0" pn="section-toc.1-1.3.2.2.1"><xref derivedContent="3.2" format="counter" sectionFormat="of" target="section-3.2"/>.  <xref derivedContent="" format="title" sectionFormat="of" target="name-exponential-growth">Exponential Growth</xref></t>
              </li>
              <li pn="section-toc.1-1.3.2.3">
                <t indent="0" pn="section-toc.1-1.3.2.3.1"><xref derivedContent="3.3" format="counter" sectionFormat="of" target="section-3.3"/>.  <xref derivedContent="" format="title" sectionFormat="of" target="name-attack-vector">Attack Vector</xref></t>
              </li>
            </ul>
          </li>
          <li pn="section-toc.1-1.4">
            <t indent="0" pn="section-toc.1-1.4.1"><xref derivedContent="4" format="counter" sectionFormat="of" target="section-4"/>.  <xref derivedContent="" format="title" sectionFormat="of" target="name-avoiding-exponential-growth">Avoiding Exponential Growth</xref></t>
            <ul bare="true" empty="true" indent="2" spacing="compact" pn="section-toc.1-1.4.2">
              <li pn="section-toc.1-1.4.2.1">
                <t indent="0" pn="section-toc.1-1.4.2.1.1"><xref derivedContent="4.1" format="counter" sectionFormat="of" target="section-4.1"/>.  <xref derivedContent="" format="title" sectionFormat="of" target="name-policy-graphs">Policy Graphs</xref></t>
              </li>
              <li pn="section-toc.1-1.4.2.2">
                <t indent="0" pn="section-toc.1-1.4.2.2.1"><xref derivedContent="4.2" format="counter" sectionFormat="of" target="section-4.2"/>.  <xref derivedContent="" format="title" sectionFormat="of" target="name-verification-outputs">Verification Outputs</xref></t>
              </li>
            </ul>
          </li>
          <li pn="section-toc.1-1.5">
            <t indent="0" pn="section-toc.1-1.5.1"><xref derivedContent="5" format="counter" sectionFormat="of" target="section-5"/>.  <xref derivedContent="" format="title" sectionFormat="of" target="name-updates-to-rfc-5280">Updates to RFC 5280</xref></t>
            <ul bare="true" empty="true" indent="2" spacing="compact" pn="section-toc.1-1.5.2">
              <li pn="section-toc.1-1.5.2.1">
                <t indent="0" pn="section-toc.1-1.5.2.1.1"><xref derivedContent="5.1" format="counter" sectionFormat="of" target="section-5.1"/>.  <xref derivedContent="" format="title" sectionFormat="of" target="name-updates-to-section-61">Updates to Section 6.1</xref></t>
              </li>
              <li pn="section-toc.1-1.5.2.2">
                <t indent="0" pn="section-toc.1-1.5.2.2.1"><xref derivedContent="5.2" format="counter" sectionFormat="of" target="section-5.2"/>.  <xref derivedContent="" format="title" sectionFormat="of" target="name-updates-to-section-612">Updates to Section 6.1.2</xref></t>
              </li>
              <li pn="section-toc.1-1.5.2.3">
                <t indent="0" pn="section-toc.1-1.5.2.3.1"><xref derivedContent="5.3" format="counter" sectionFormat="of" target="section-5.3"/>.  <xref derivedContent="" format="title" sectionFormat="of" target="name-updates-to-section-613">Updates to Section 6.1.3</xref></t>
              </li>
              <li pn="section-toc.1-1.5.2.4">
                <t indent="0" pn="section-toc.1-1.5.2.4.1"><xref derivedContent="5.4" format="counter" sectionFormat="of" target="section-5.4"/>.  <xref derivedContent="" format="title" sectionFormat="of" target="name-updates-to-section-614">Updates to Section 6.1.4</xref></t>
              </li>
              <li pn="section-toc.1-1.5.2.5">
                <t indent="0" pn="section-toc.1-1.5.2.5.1"><xref derivedContent="5.5" format="counter" sectionFormat="of" target="section-5.5"/>.  <xref derivedContent="" format="title" sectionFormat="of" target="name-updates-to-section-615">Updates to Section 6.1.5</xref></t>
              </li>
              <li pn="section-toc.1-1.5.2.6">
                <t indent="0" pn="section-toc.1-1.5.2.6.1"><xref derivedContent="5.6" format="counter" sectionFormat="of" target="section-5.6"/>.  <xref derivedContent="" format="title" sectionFormat="of" target="name-updates-to-section-616">Updates to Section 6.1.6</xref></t>
              </li>
            </ul>
          </li>
          <li pn="section-toc.1-1.6">
            <t indent="0" pn="section-toc.1-1.6.1"><xref derivedContent="6" format="counter" sectionFormat="of" target="section-6"/>.  <xref derivedContent="" format="title" sectionFormat="of" target="name-other-mitigations">Other Mitigations</xref></t>
            <ul bare="true" empty="true" indent="2" spacing="compact" pn="section-toc.1-1.6.2">
              <li pn="section-toc.1-1.6.2.1">
                <t indent="0" pn="section-toc.1-1.6.2.1.1"><xref derivedContent="6.1" format="counter" sectionFormat="of" target="section-6.1"/>.  <xref derivedContent="" format="title" sectionFormat="of" target="name-verify-signatures-first">Verify Signatures First</xref></t>
              </li>
              <li pn="section-toc.1-1.6.2.2">
                <t indent="0" pn="section-toc.1-1.6.2.2.1"><xref derivedContent="6.2" format="counter" sectionFormat="of" target="section-6.2"/>.  <xref derivedContent="" format="title" sectionFormat="of" target="name-limit-certificate-depth">Limit Certificate Depth</xref></t>
              </li>
              <li pn="section-toc.1-1.6.2.3">
                <t indent="0" pn="section-toc.1-1.6.2.3.1"><xref derivedContent="6.3" format="counter" sectionFormat="of" target="section-6.3"/>.  <xref derivedContent="" format="title" sectionFormat="of" target="name-limit-policy-tree-size">Limit Policy Tree Size</xref></t>
              </li>
              <li pn="section-toc.1-1.6.2.4">
                <t indent="0" pn="section-toc.1-1.6.2.4.1"><xref derivedContent="6.4" format="counter" sectionFormat="of" target="section-6.4"/>.  <xref derivedContent="" format="title" sectionFormat="of" target="name-inhibit-policy-mapping">Inhibit Policy Mapping</xref></t>
              </li>
              <li pn="section-toc.1-1.6.2.5">
                <t indent="0" pn="section-toc.1-1.6.2.5.1"><xref derivedContent="6.5" format="counter" sectionFormat="of" target="section-6.5"/>.  <xref derivedContent="" format="title" sectionFormat="of" target="name-disable-policy-checking">Disable Policy Checking</xref></t>
              </li>
            </ul>
          </li>
          <li pn="section-toc.1-1.7">
            <t indent="0" pn="section-toc.1-1.7.1"><xref derivedContent="7" format="counter" sectionFormat="of" target="section-7"/>.  <xref derivedContent="" format="title" sectionFormat="of" target="name-security-considerations">Security Considerations</xref></t>
          </li>
          <li pn="section-toc.1-1.8">
            <t indent="0" pn="section-toc.1-1.8.1"><xref derivedContent="8" format="counter" sectionFormat="of" target="section-8"/>.  <xref derivedContent="" format="title" sectionFormat="of" target="name-iana-considerations">IANA Considerations</xref></t>
          </li>
          <li pn="section-toc.1-1.9">
            <t indent="0" pn="section-toc.1-1.9.1"><xref derivedContent="9" format="counter" sectionFormat="of" target="section-9"/>.  <xref derivedContent="" format="title" sectionFormat="of" target="name-references">References</xref></t>
            <ul bare="true" empty="true" indent="2" spacing="compact" pn="section-toc.1-1.9.2">
              <li pn="section-toc.1-1.9.2.1">
                <t indent="0" pn="section-toc.1-1.9.2.1.1"><xref derivedContent="9.1" format="counter" sectionFormat="of" target="section-9.1"/>.  <xref derivedContent="" format="title" sectionFormat="of" target="name-normative-references">Normative References</xref></t>
              </li>
              <li pn="section-toc.1-1.9.2.2">
                <t indent="0" pn="section-toc.1-1.9.2.2.1"><xref derivedContent="9.2" format="counter" sectionFormat="of" target="section-9.2"/>.  <xref derivedContent="" format="title" sectionFormat="of" target="name-informative-references">Informative References</xref></t>
              </li>
            </ul>
          </li>
          <li pn="section-toc.1-1.10">
            <t indent="0" pn="section-toc.1-1.10.1"><xref derivedContent="" format="none" sectionFormat="of" target="section-appendix.a"/><xref derivedContent="" format="title" sectionFormat="of" target="name-acknowledgements">Acknowledgements</xref></t>
          </li>
          <li pn="section-toc.1-1.11">
            <t indent="0" pn="section-toc.1-1.11.1"><xref derivedContent="" format="none" sectionFormat="of" target="section-appendix.b"/><xref derivedContent="" format="title" sectionFormat="of" target="name-authors-address">Author's Address</xref></t>
          </li>
        </ul>
      </section>
    </toc>
  </front>
  <middle>
    <section anchor="introduction" numbered="true" removeInRFC="false" toc="include" pn="section-1">
      <name slugifiedName="name-introduction">Introduction</name>
      <t indent="0" pn="section-1-1"><xref target="RFC5280" format="default" sectionFormat="of" derivedContent="RFC5280"/> defines a suite of extensions for
      determining the policies that apply to a certification path. A policy
      is described by an object identifier (OID) and a set of optional
      qualifiers.</t>
      <t indent="0" pn="section-1-2">Policy validation in <xref target="RFC5280" format="default" sectionFormat="of" derivedContent="RFC5280"/> is complex. As an
      overview, the certificate policies extension (<xref section="4.2.1.4" sectionFormat="of" target="RFC5280" format="default" derivedLink="https://rfc-editor.org/rfc/rfc5280#section-4.2.1.4" derivedContent="RFC5280"/>) describes the policies, with
      optional qualifiers, under which an individual certificate was issued.
      The policy mappings extension (<xref section="4.2.1.5" sectionFormat="of" target="RFC5280" format="default" derivedLink="https://rfc-editor.org/rfc/rfc5280#section-4.2.1.5" derivedContent="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.</t>
      <t indent="0" pn="section-1-3">The procedure in <xref section="6.1" sectionFormat="of" target="RFC5280" format="default" derivedLink="https://rfc-editor.org/rfc/rfc5280#section-6.1" derivedContent="RFC5280"/> determines this set in the course of certification
      path validation. It does so by building a policy tree containing
      policies asserted by each certificate and the mappings between
      them. This tree can grow exponentially in the depth of the certification
      path, which means an attacker, with a small input, can cause a path
      validator to consume excessive memory and computational resources. This
      cost asymmetry can lead to a denial-of-service vulnerability in
      X.509-based applications, such as <xref target="CVE-2023-0464" format="default" sectionFormat="of" derivedContent="CVE-2023-0464"/> and
      <xref target="CVE-2023-23524" format="default" sectionFormat="of" derivedContent="CVE-2023-23524"/>.</t>
      <t indent="0" pn="section-1-4"><xref target="dos" format="default" sectionFormat="of" derivedContent="Section 3"/> describes this vulnerability. <xref target="policy-graph" format="default" sectionFormat="of" derivedContent="Section 4.1"/> describes the primary mitigation for this
      vulnerability, a replacement for the policy tree structure.  <xref target="updates" format="default" sectionFormat="of" derivedContent="Section 5"/> provides updates to <xref target="RFC5280" format="default" sectionFormat="of" derivedContent="RFC5280"/> that
      implement this change.  Finally, <xref target="other-mitigations" format="default" sectionFormat="of" derivedContent="Section 6"/>
      discusses alternative mitigation strategies for X.509 applications.</t>
      <section anchor="summary-of-changes-from-rfc-5280" numbered="true" removeInRFC="false" toc="include" pn="section-1.1">
        <name slugifiedName="name-summary-of-changes-from-rfc">Summary of Changes from RFC 5280</name>
        <t indent="0" pn="section-1.1-1">The algorithm for processing certificate policies and policy
        mappings is replaced with one that builds an equivalent but much more
        efficient structure.  This new algorithm does not change the validity
        status of any certification path or which certificate policies are
        valid for it.</t>
      </section>
    </section>
    <section anchor="conventions-and-definitions" numbered="true" removeInRFC="false" toc="include" pn="section-2">
      <name slugifiedName="name-conventions-and-definitions">Conventions and Definitions</name>
      <t indent="0" pn="section-2-1">
    The key words "<bcp14>MUST</bcp14>", "<bcp14>MUST NOT</bcp14>",
    "<bcp14>REQUIRED</bcp14>", "<bcp14>SHALL</bcp14>", "<bcp14>SHALL NOT</bcp14>",
    "<bcp14>SHOULD</bcp14>", "<bcp14>SHOULD NOT</bcp14>",
    "<bcp14>RECOMMENDED</bcp14>", "<bcp14>NOT RECOMMENDED</bcp14>",
    "<bcp14>MAY</bcp14>", and "<bcp14>OPTIONAL</bcp14>" in this document are to be
    interpreted as described in BCP 14 <xref target="RFC2119" format="default" sectionFormat="of" derivedContent="RFC2119"/> <xref target="RFC8174" format="default" sectionFormat="of" derivedContent="RFC8174"/> when, and only when, they appear in all capitals, as
    shown here.
      </t>
    </section>
    <section anchor="dos" numbered="true" removeInRFC="false" toc="include" pn="section-3">
      <name slugifiedName="name-denial-of-service-vulnerabi">Denial-of-Service Vulnerability</name>
      <t indent="0" pn="section-3-1">This section discusses how the path validation algorithm defined in
<xref section="6.1.2" sectionFormat="of" target="RFC5280" format="default" derivedLink="https://rfc-editor.org/rfc/rfc5280#section-6.1.2" derivedContent="RFC5280"/> can lead to a denial-of-service vulnerability in
X.509-based applications.</t>
      <section anchor="policy-trees" numbered="true" removeInRFC="false" toc="include" pn="section-3.1">
        <name slugifiedName="name-policy-trees">Policy Trees</name>
        <t indent="0" pn="section-3.1-1"><xref section="6.1.2" sectionFormat="of" target="RFC5280" format="default" derivedLink="https://rfc-editor.org/rfc/rfc5280#section-6.1.2" derivedContent="RFC5280"/>
        constructs the <tt>valid_policy_tree</tt>, a tree of certificate
        policies, during certification path validation.  The nodes at any
        given depth in the tree correspond to policies asserted by a
        certificate in the certification path.  A node's parent policy is the
        policy in the issuer certificate that was mapped to this policy, and a
        node's children are the policies the node was mapped to in the subject
        certificate.</t>
        <t indent="0" pn="section-3.1-2">For example, suppose a certification path contains:</t>
        <ul spacing="normal" bare="false" empty="false" indent="3" pn="section-3.1-3">
          <li pn="section-3.1-3.1">An intermediate certificate that asserts the following  policy OIDs: OID1, OID2,
          and OID5.  It contains mappings from OID1 to OID3 and from OID1 to OID4.</li>
          <li pn="section-3.1-3.2">An end-entity certificate that asserts the following policy OIDs: OID2, OID3,
          and OID6.</li>
        </ul>
        <t indent="0" pn="section-3.1-4">This would result in the tree shown below.
        Note that OID5 and OID6 are not included or
        mapped across the whole path, so they do not appear in the final
        structure.</t>
        <artset pn="section-3.1-5">
          <artwork type="svg" align="left" pn="section-3.1-5.1"><svg xmlns="http://www.w3.org/2000/svg" version="1.1" height="336" width="424" viewBox="0 0 424 336" class="diagram" text-anchor="middle" font-family="monospace" font-size="13px" stroke-linecap="round">
              <path d="M 152,160 L 152,224" fill="none" stroke="black"/>
              <path d="M 152,288 L 152,320" fill="none" stroke="black"/>
              <path d="M 200,232 L 200,280" fill="none" stroke="black"/>
              <path d="M 232,32 L 232,96" fill="none" stroke="black"/>
              <path d="M 256,160 L 256,224" fill="none" stroke="black"/>
              <path d="M 256,288 L 256,320" fill="none" stroke="black"/>
              <path d="M 312,160 L 312,224" fill="none" stroke="black"/>
              <path d="M 312,288 L 312,320" fill="none" stroke="black"/>
              <path d="M 328,32 L 328,96" fill="none" stroke="black"/>
              <path d="M 360,232 L 360,280" fill="none" stroke="black"/>
              <path d="M 416,160 L 416,224" fill="none" stroke="black"/>
              <path d="M 416,288 L 416,320" fill="none" stroke="black"/>
              <path d="M 232,32 L 328,32" fill="none" stroke="black"/>
              <path d="M 232,64 L 328,64" fill="none" stroke="black"/>
              <path d="M 232,96 L 328,96" fill="none" stroke="black"/>
              <path d="M 152,160 L 256,160" fill="none" stroke="black"/>
              <path d="M 312,160 L 416,160" fill="none" stroke="black"/>
              <path d="M 152,192 L 256,192" fill="none" stroke="black"/>
              <path d="M 312,192 L 416,192" fill="none" stroke="black"/>
              <path d="M 152,224 L 256,224" fill="none" stroke="black"/>
              <path d="M 312,224 L 416,224" fill="none" stroke="black"/>
              <path d="M 152,288 L 256,288" fill="none" stroke="black"/>
              <path d="M 312,288 L 416,288" fill="none" stroke="black"/>
              <path d="M 152,320 L 256,320" fill="none" stroke="black"/>
              <path d="M 312,320 L 416,320" fill="none" stroke="black"/>
              <path d="M 324,104 L 348,152" fill="none" stroke="black"/>
              <path d="M 220,152 L 244,104" fill="none" stroke="black"/>
              <polygon class="arrowhead" points="368,280 356,274.4 356,285.6" fill="black" transform="rotate(90,360,280)"/>
              <polygon class="arrowhead" points="356,152 344,146.4 344,157.6" fill="black" transform="rotate(63.43494882292201,348,152)"/>
              <polygon class="arrowhead" points="228,152 216,146.4 216,157.6" fill="black" transform="rotate(116.56505117707799,220,152)"/>
              <polygon class="arrowhead" points="208,280 196,274.4 196,285.6" fill="black" transform="rotate(90,200,280)"/>
              <g class="text">
                <text x="112" y="52">Root:</text>
                <text x="280" y="52">anyPolicy</text>
                <text x="280" y="84">{anyPolicy}</text>
                <text x="80" y="180">Intermediate:</text>
                <text x="204" y="180">OID1</text>
                <text x="364" y="180">OID2</text>
                <text x="24" y="196">(OID5</text>
                <text x="92" y="196">discarded)</text>
                <text x="180" y="212">{OID3,</text>
                <text x="232" y="212">OID4}</text>
                <text x="364" y="212">{OID2}</text>
                <text x="88" y="308">End-entity:</text>
                <text x="204" y="308">OID3</text>
                <text x="364" y="308">OID2</text>
                <text x="24" y="324">(OID6</text>
                <text x="92" y="324">discarded)</text>
              </g>
            </svg>
          </artwork>
          <artwork type="ascii-art" align="left" pn="section-3.1-5.2">
                            +-----------+
           Root:            | anyPolicy |
                            +-----------+
                            |{anyPolicy}|
                            +-----------+
                             /          \
                            /            \
                           v              v
                  +------------+      +------------+
   Intermediate:  |    OID1    |      |    OID2    |
(OID5 discarded)  +------------+      +------------+
                  |{OID3, OID4}|      |   {OID2}   |
                  +------------+      +------------+
                        |                   |
                        |                   |
                        v                   v
                  +------------+      +------------+
     End-entity:  |    OID3    |      |    OID2    |
(OID6 discarded)  +------------+      +------------+
</artwork>
        </artset>
        <t indent="0" pn="section-3.1-6">The complete algorithm for building this structure is described in
        steps (d), (e), and (f) in <xref section="6.1.3" sectionFormat="of" target="RFC5280" format="default" derivedLink="https://rfc-editor.org/rfc/rfc5280#section-6.1.3" derivedContent="RFC5280"/>; steps (h), (i), and (j) in <xref section="6.1.4" sectionFormat="of" target="RFC5280" format="default" derivedLink="https://rfc-editor.org/rfc/rfc5280#section-6.1.4" derivedContent="RFC5280"/>; and steps (a), (b), and (g) in
        <xref section="6.1.5" sectionFormat="of" target="RFC5280" format="default" derivedLink="https://rfc-editor.org/rfc/rfc5280#section-6.1.5" derivedContent="RFC5280"/>.</t>
      </section>
      <section anchor="exponential-growth" numbered="true" removeInRFC="false" toc="include" pn="section-3.2">
        <name slugifiedName="name-exponential-growth">Exponential Growth</name>
        <t indent="0" pn="section-3.2-1">The <tt>valid_policy_tree</tt> grows exponentially in the worst
        case. In step (d.1) in <xref section="6.1.3" sectionFormat="of" target="RFC5280" format="default" derivedLink="https://rfc-editor.org/rfc/rfc5280#section-6.1.3" derivedContent="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.</t>
        <t indent="0" pn="section-3.2-2">In particular, consider a certificate chain where every
        intermediate certificate asserts policies OID1 and OID2 and then
        contains the full Cartesian product of mappings:</t>
        <ul spacing="normal" bare="false" empty="false" indent="3" pn="section-3.2-3">
          <li pn="section-3.2-3.1">
            <t indent="0" pn="section-3.2-3.1.1">OID1 maps to OID1</t>
          </li>
          <li pn="section-3.2-3.2">
            <t indent="0" pn="section-3.2-3.2.1">OID1 maps to OID2</t>
          </li>
          <li pn="section-3.2-3.3">
            <t indent="0" pn="section-3.2-3.3.1">OID2 maps to OID1</t>
          </li>
          <li pn="section-3.2-3.4">
            <t indent="0" pn="section-3.2-3.4.1">OID2 maps to OID2</t>
          </li>
        </ul>
        <t indent="0" pn="section-3.2-4">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 <xref target="exponential-tree" format="default" sectionFormat="of" derivedContent="Figure 1"/>.</t>
        <figure anchor="exponential-tree" align="left" suppress-title="false" pn="figure-1">
          <name slugifiedName="name-an-example-x509-policy-tree">An Example X.509 Policy Tree with Exponential Growth</name>
          <artset pn="section-3.2-5.1">
            <artwork type="svg" align="left" pn="section-3.2-5.1.1"><svg xmlns="http://www.w3.org/2000/svg" version="1.1" height="448" width="576" viewBox="0 0 576 448" class="diagram" text-anchor="middle" font-family="monospace" font-size="13px" stroke-linecap="round">
                <path d="M 8,400 L 8,432" fill="none" stroke="black"/>
                <path d="M 24,288 L 24,352" fill="none" stroke="black"/>
                <path d="M 40,360 L 40,392" fill="none" stroke="black"/>
                <path d="M 64,400 L 64,432" fill="none" stroke="black"/>
                <path d="M 80,400 L 80,432" fill="none" stroke="black"/>
                <path d="M 104,160 L 104,224" fill="none" stroke="black"/>
                <path d="M 104,360 L 104,392" fill="none" stroke="black"/>
                <path d="M 128,288 L 128,352" fill="none" stroke="black"/>
                <path d="M 136,400 L 136,432" fill="none" stroke="black"/>
                <path d="M 152,400 L 152,432" fill="none" stroke="black"/>
                <path d="M 168,288 L 168,352" fill="none" stroke="black"/>
                <path d="M 184,360 L 184,392" fill="none" stroke="black"/>
                <path d="M 200,32 L 200,96" fill="none" stroke="black"/>
                <path d="M 208,160 L 208,224" fill="none" stroke="black"/>
                <path d="M 208,400 L 208,432" fill="none" stroke="black"/>
                <path d="M 224,400 L 224,432" fill="none" stroke="black"/>
                <path d="M 248,360 L 248,392" fill="none" stroke="black"/>
                <path d="M 272,288 L 272,352" fill="none" stroke="black"/>
                <path d="M 280,400 L 280,432" fill="none" stroke="black"/>
                <path d="M 296,400 L 296,432" fill="none" stroke="black"/>
                <path d="M 312,288 L 312,352" fill="none" stroke="black"/>
                <path d="M 328,360 L 328,392" fill="none" stroke="black"/>
                <path d="M 352,400 L 352,432" fill="none" stroke="black"/>
                <path d="M 368,400 L 368,432" fill="none" stroke="black"/>
                <path d="M 392,32 L 392,96" fill="none" stroke="black"/>
                <path d="M 392,160 L 392,224" fill="none" stroke="black"/>
                <path d="M 392,360 L 392,392" fill="none" stroke="black"/>
                <path d="M 416,288 L 416,352" fill="none" stroke="black"/>
                <path d="M 424,400 L 424,432" fill="none" stroke="black"/>
                <path d="M 440,400 L 440,432" fill="none" stroke="black"/>
                <path d="M 456,288 L 456,352" fill="none" stroke="black"/>
                <path d="M 472,360 L 472,392" fill="none" stroke="black"/>
                <path d="M 496,160 L 496,224" fill="none" stroke="black"/>
                <path d="M 496,400 L 496,432" fill="none" stroke="black"/>
                <path d="M 512,400 L 512,432" fill="none" stroke="black"/>
                <path d="M 536,360 L 536,392" fill="none" stroke="black"/>
                <path d="M 560,288 L 560,352" fill="none" stroke="black"/>
                <path d="M 568,400 L 568,432" fill="none" stroke="black"/>
                <path d="M 200,32 L 392,32" fill="none" stroke="black"/>
                <path d="M 200,64 L 392,64" fill="none" stroke="black"/>
                <path d="M 200,96 L 392,96" fill="none" stroke="black"/>
                <path d="M 104,160 L 208,160" fill="none" stroke="black"/>
                <path d="M 392,160 L 496,160" fill="none" stroke="black"/>
                <path d="M 104,192 L 208,192" fill="none" stroke="black"/>
                <path d="M 392,192 L 496,192" fill="none" stroke="black"/>
                <path d="M 104,224 L 208,224" fill="none" stroke="black"/>
                <path d="M 392,224 L 496,224" fill="none" stroke="black"/>
                <path d="M 24,288 L 128,288" fill="none" stroke="black"/>
                <path d="M 168,288 L 272,288" fill="none" stroke="black"/>
                <path d="M 312,288 L 416,288" fill="none" stroke="black"/>
                <path d="M 456,288 L 560,288" fill="none" stroke="black"/>
                <path d="M 24,320 L 128,320" fill="none" stroke="black"/>
                <path d="M 168,320 L 272,320" fill="none" stroke="black"/>
                <path d="M 312,320 L 416,320" fill="none" stroke="black"/>
                <path d="M 456,320 L 560,320" fill="none" stroke="black"/>
                <path d="M 24,352 L 128,352" fill="none" stroke="black"/>
                <path d="M 168,352 L 272,352" fill="none" stroke="black"/>
                <path d="M 312,352 L 416,352" fill="none" stroke="black"/>
                <path d="M 456,352 L 560,352" fill="none" stroke="black"/>
                <path d="M 8,400 L 64,400" fill="none" stroke="black"/>
                <path d="M 80,400 L 136,400" fill="none" stroke="black"/>
                <path d="M 152,400 L 208,400" fill="none" stroke="black"/>
                <path d="M 224,400 L 280,400" fill="none" stroke="black"/>
                <path d="M 296,400 L 352,400" fill="none" stroke="black"/>
                <path d="M 368,400 L 424,400" fill="none" stroke="black"/>
                <path d="M 440,400 L 496,400" fill="none" stroke="black"/>
                <path d="M 512,400 L 568,400" fill="none" stroke="black"/>
                <path d="M 8,432 L 64,432" fill="none" stroke="black"/>
                <path d="M 80,432 L 136,432" fill="none" stroke="black"/>
                <path d="M 152,432 L 208,432" fill="none" stroke="black"/>
                <path d="M 224,432 L 280,432" fill="none" stroke="black"/>
                <path d="M 296,432 L 352,432" fill="none" stroke="black"/>
                <path d="M 368,432 L 424,432" fill="none" stroke="black"/>
                <path d="M 440,432 L 496,432" fill="none" stroke="black"/>
                <path d="M 512,432 L 568,432" fill="none" stroke="black"/>
                <path d="M 188,232 L 212,280" fill="none" stroke="black"/>
                <path d="M 380,104 L 404,152" fill="none" stroke="black"/>
                <path d="M 484,232 L 508,280" fill="none" stroke="black"/>
                <path d="M 92,280 L 116,232" fill="none" stroke="black"/>
                <path d="M 188,152 L 212,104" fill="none" stroke="black"/>
                <path d="M 388,280 L 412,232" fill="none" stroke="black"/>
                <polygon class="arrowhead" points="544,392 532,386.4 532,397.6" fill="black" transform="rotate(90,536,392)"/>
                <polygon class="arrowhead" points="516,280 504,274.4 504,285.6" fill="black" transform="rotate(63.43494882292201,508,280)"/>
                <polygon class="arrowhead" points="480,392 468,386.4 468,397.6" fill="black" transform="rotate(90,472,392)"/>
                <polygon class="arrowhead" points="412,152 400,146.4 400,157.6" fill="black" transform="rotate(63.43494882292201,404,152)"/>
                <polygon class="arrowhead" points="400,392 388,386.4 388,397.6" fill="black" transform="rotate(90,392,392)"/>
                <polygon class="arrowhead" points="396,280 384,274.4 384,285.6" fill="black" transform="rotate(116.56505117707799,388,280)"/>
                <polygon class="arrowhead" points="336,392 324,386.4 324,397.6" fill="black" transform="rotate(90,328,392)"/>
                <polygon class="arrowhead" points="256,392 244,386.4 244,397.6" fill="black" transform="rotate(90,248,392)"/>
                <polygon class="arrowhead" points="220,280 208,274.4 208,285.6" fill="black" transform="rotate(63.43494882292201,212,280)"/>
                <polygon class="arrowhead" points="196,152 184,146.4 184,157.6" fill="black" transform="rotate(116.56505117707799,188,152)"/>
                <polygon class="arrowhead" points="192,392 180,386.4 180,397.6" fill="black" transform="rotate(90,184,392)"/>
                <polygon class="arrowhead" points="112,392 100,386.4 100,397.6" fill="black" transform="rotate(90,104,392)"/>
                <polygon class="arrowhead" points="100,280 88,274.4 88,285.6" fill="black" transform="rotate(116.56505117707799,92,280)"/>
                <polygon class="arrowhead" points="48,392 36,386.4 36,397.6" fill="black" transform="rotate(90,40,392)"/>
                <g class="text">
                  <text x="304" y="52">anyPolicy</text>
                  <text x="304" y="84">{anyPolicy}</text>
                  <text x="156" y="180">OID1</text>
                  <text x="444" y="180">OID2</text>
                  <text x="132" y="212">{OID1,</text>
                  <text x="184" y="212">OID2}</text>
                  <text x="420" y="212">{OID1,</text>
                  <text x="472" y="212">OID2}</text>
                  <text x="76" y="308">OID1</text>
                  <text x="220" y="308">OID2</text>
                  <text x="364" y="308">OID1</text>
                  <text x="508" y="308">OID2</text>
                  <text x="52" y="340">{OID1,</text>
                  <text x="104" y="340">OID2}</text>
                  <text x="196" y="340">{OID1,</text>
                  <text x="248" y="340">OID2}</text>
                  <text x="340" y="340">{OID1,</text>
                  <text x="392" y="340">OID2}</text>
                  <text x="484" y="340">{OID1,</text>
                  <text x="536" y="340">OID2}</text>
                  <text x="36" y="420">OID1</text>
                  <text x="108" y="420">OID2</text>
                  <text x="180" y="420">OID1</text>
                  <text x="252" y="420">OID2</text>
                  <text x="324" y="420">OID1</text>
                  <text x="396" y="420">OID2</text>
                  <text x="468" y="420">OID1</text>
                  <text x="540" y="420">OID2</text>
                </g>
              </svg>
            </artwork>
            <artwork type="ascii-art" align="left" pn="section-3.2-5.1.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 |
+------+ +------+ +------+ +------+ +------+ +------+ +------+ +------+
</artwork>
          </artset>
        </figure>
      </section>
      <section anchor="attack-vector" numbered="true" removeInRFC="false" toc="include" pn="section-3.3">
        <name slugifiedName="name-attack-vector">Attack Vector</name>
        <t indent="0" pn="section-3.3-1">An attacker can use the exponential growth to mount a
        denial-of-service attack against an X.509-based application. The
        attacker sends a certificate chain as described in <xref target="exponential-growth" format="default" sectionFormat="of" derivedContent="Section 3.2"/> and triggers the target application's
        certificate validation process. For example, the target application
        may be a TLS server <xref target="RFC8446" format="default" sectionFormat="of" derivedContent="RFC8446"/> that performs client
        certificate validation.  The target application will consume far more
        resources processing the input than the attacker consumed to send it,
        which prevents the target application from servicing other
        clients.</t>
      </section>
    </section>
    <section anchor="avoiding-exponential-growth" numbered="true" removeInRFC="false" toc="include" pn="section-4">
      <name slugifiedName="name-avoiding-exponential-growth">Avoiding Exponential Growth</name>
      <t indent="0" pn="section-4-1">This document mitigates the denial-of-service vulnerability 
      described in <xref target="dos" format="default" sectionFormat="of" derivedContent="Section 3"/> by replacing the policy tree with a
      policy graph structure, which is described in this section. The policy graph grows
      linearly instead of exponentially. This removes the asymmetric cost in
      policy validation.</t>
      <t indent="0" pn="section-4-2">X.509 implementations <bcp14>SHOULD</bcp14> perform policy validation
      by building a policy graph, following the procedure described in <xref target="updates" format="default" sectionFormat="of" derivedContent="Section 5"/>. This replacement procedure computes the same
      policies as in <xref target="RFC5280" format="default" sectionFormat="of" derivedContent="RFC5280"/>, but one of the outputs is in a
      different form. See <xref target="outputs" format="default" sectionFormat="of" derivedContent="Section 4.2"/> for details.  <xref target="other-mitigations" format="default" sectionFormat="of" derivedContent="Section 6"/> describes alternative mitigations for
      implementations that depend on the original, exponential-sized
      output.</t>
      <section anchor="policy-graph" numbered="true" removeInRFC="false" toc="include" pn="section-4.1">
        <name slugifiedName="name-policy-graphs">Policy Graphs</name>
        <t indent="0" pn="section-4.1-1">The tree structure in <xref target="RFC5280" format="default" sectionFormat="of" derivedContent="RFC5280"/> is an unnecessarily
   inefficient representation of a certification path's policy mappings.  When
   multiple issuer policies map to a single subject policy, the subject policy
   will correspond to multiple duplicate nodes in the policy tree. Children of
   the subject policy are then duplicated recursively. This duplication is the
   source of the exponential growth described in <xref target="exponential-growth" format="default" sectionFormat="of" derivedContent="Section 3.2"/>.</t>
        <t indent="0" pn="section-4.1-2">A policy graph represents the same information with a directed acyclic
   graph of policy nodes.  It eliminates this duplication by using a single
   node with multiple parents.  See <xref target="updates" format="default" sectionFormat="of" derivedContent="Section 5"/> for the procedure
   for building this structure.  <xref target="exponential-tree-as-graph" format="default" sectionFormat="of" derivedContent="Figure 2"/>
   shows the updated representation of the example in <xref target="exponential-tree" format="default" sectionFormat="of" derivedContent="Figure 1"/>.</t>
        <figure anchor="exponential-tree-as-graph" align="left" suppress-title="false" pn="figure-2">
          <name slugifiedName="name-a-more-efficient-representa">A More Efficient Representation of an X.509 Policy Tree</name>
          <artset pn="section-4.1-3.1">
            <artwork type="svg" align="left" pn="section-4.1-3.1.1"><svg xmlns="http://www.w3.org/2000/svg" version="1.1" height="576" width="248" viewBox="0 0 248 576" class="diagram" text-anchor="middle" font-family="monospace" font-size="13px" stroke-linecap="round">
                <path d="M 8,160 L 8,224" fill="none" stroke="black"/>
                <path d="M 8,336 L 8,400" fill="none" stroke="black"/>
                <path d="M 8,512 L 8,544" fill="none" stroke="black"/>
                <path d="M 48,232 L 48,328" fill="none" stroke="black"/>
                <path d="M 48,408 L 48,504" fill="none" stroke="black"/>
                <path d="M 80,32 L 80,96" fill="none" stroke="black"/>
                <path d="M 112,160 L 112,224" fill="none" stroke="black"/>
                <path d="M 112,336 L 112,400" fill="none" stroke="black"/>
                <path d="M 112,512 L 112,544" fill="none" stroke="black"/>
                <path d="M 136,160 L 136,224" fill="none" stroke="black"/>
                <path d="M 136,336 L 136,400" fill="none" stroke="black"/>
                <path d="M 136,512 L 136,544" fill="none" stroke="black"/>
                <path d="M 176,32 L 176,96" fill="none" stroke="black"/>
                <path d="M 192,232 L 192,328" fill="none" stroke="black"/>
                <path d="M 192,408 L 192,504" fill="none" stroke="black"/>
                <path d="M 240,160 L 240,224" fill="none" stroke="black"/>
                <path d="M 240,336 L 240,400" fill="none" stroke="black"/>
                <path d="M 240,512 L 240,544" fill="none" stroke="black"/>
                <path d="M 80,32 L 176,32" fill="none" stroke="black"/>
                <path d="M 80,64 L 176,64" fill="none" stroke="black"/>
                <path d="M 80,96 L 176,96" fill="none" stroke="black"/>
                <path d="M 8,160 L 112,160" fill="none" stroke="black"/>
                <path d="M 136,160 L 240,160" fill="none" stroke="black"/>
                <path d="M 8,192 L 112,192" fill="none" stroke="black"/>
                <path d="M 136,192 L 240,192" fill="none" stroke="black"/>
                <path d="M 8,224 L 112,224" fill="none" stroke="black"/>
                <path d="M 136,224 L 240,224" fill="none" stroke="black"/>
                <path d="M 8,336 L 112,336" fill="none" stroke="black"/>
                <path d="M 136,336 L 240,336" fill="none" stroke="black"/>
                <path d="M 8,368 L 112,368" fill="none" stroke="black"/>
                <path d="M 136,368 L 240,368" fill="none" stroke="black"/>
                <path d="M 8,400 L 112,400" fill="none" stroke="black"/>
                <path d="M 136,400 L 240,400" fill="none" stroke="black"/>
                <path d="M 8,512 L 112,512" fill="none" stroke="black"/>
                <path d="M 136,512 L 240,512" fill="none" stroke="black"/>
                <path d="M 8,544 L 112,544" fill="none" stroke="black"/>
                <path d="M 136,544 L 240,544" fill="none" stroke="black"/>
                <path d="M 100,408 L 148,504" fill="none" stroke="black"/>
                <path d="M 100,232 L 148,328" fill="none" stroke="black"/>
                <path d="M 172,104 L 196,152" fill="none" stroke="black"/>
                <path d="M 60,152 L 84,104" fill="none" stroke="black"/>
                <path d="M 100,328 L 148,232" fill="none" stroke="black"/>
                <path d="M 100,504 L 148,408" fill="none" stroke="black"/>
                <polygon class="arrowhead" points="200,504 188,498.4 188,509.6" fill="black" transform="rotate(90,192,504)"/>
                <polygon class="arrowhead" points="200,328 188,322.4 188,333.6" fill="black" transform="rotate(90,192,328)"/>
                <polygon class="arrowhead" points="204,152 192,146.4 192,157.6" fill="black" transform="rotate(63.43494882292201,196,152)"/>
                <polygon class="arrowhead" points="156,504 144,498.4 144,509.6" fill="black" transform="rotate(63.43494882292201,148,504)"/>
                <polygon class="arrowhead" points="156,328 144,322.4 144,333.6" fill="black" transform="rotate(63.43494882292201,148,328)"/>
                <polygon class="arrowhead" points="108,504 96,498.4 96,509.6" fill="black" transform="rotate(116.56505117707799,100,504)"/>
                <polygon class="arrowhead" points="108,328 96,322.4 96,333.6" fill="black" transform="rotate(116.56505117707799,100,328)"/>
                <polygon class="arrowhead" points="68,152 56,146.4 56,157.6" fill="black" transform="rotate(116.56505117707799,60,152)"/>
                <polygon class="arrowhead" points="56,504 44,498.4 44,509.6" fill="black" transform="rotate(90,48,504)"/>
                <polygon class="arrowhead" points="56,328 44,322.4 44,333.6" fill="black" transform="rotate(90,48,328)"/>
                <g class="text">
                  <text x="128" y="52">anyPolicy</text>
                  <text x="128" y="84">{anyPolicy}</text>
                  <text x="60" y="180">OID1</text>
                  <text x="188" y="180">OID2</text>
                  <text x="36" y="212">{OID1,</text>
                  <text x="88" y="212">OID2}</text>
                  <text x="164" y="212">{OID1,</text>
                  <text x="216" y="212">OID2}</text>
                  <text x="60" y="356">OID1</text>
                  <text x="188" y="356">OID2</text>
                  <text x="36" y="388">{OID1,</text>
                  <text x="88" y="388">OID2}</text>
                  <text x="164" y="388">{OID1,</text>
                  <text x="216" y="388">OID2}</text>
                  <text x="60" y="532">OID1</text>
                  <text x="188" y="532">OID2</text>
                </g>
              </svg>
            </artwork>
            <artwork type="ascii-art" align="left" pn="section-4.1-3.1.2">
              +-----------+
              | 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    |
     +------------+  +------------+
</artwork>
          </artset>
        </figure>
        <t indent="0" pn="section-4.1-4">This graph's size is bounded linearly by the total number of
        certificate policies (<xref section="4.2.1.4" sectionFormat="of" target="RFC5280" format="default" derivedLink="https://rfc-editor.org/rfc/rfc5280#section-4.2.1.4" derivedContent="RFC5280"/>) and policy mappings (<xref section="4.2.1.5" sectionFormat="of" target="RFC5280" format="default" derivedLink="https://rfc-editor.org/rfc/rfc5280#section-4.2.1.5" derivedContent="RFC5280"/>). The policy tree in <xref target="RFC5280" format="default" sectionFormat="of" derivedContent="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.</t>
      </section>
      <section anchor="outputs" numbered="true" removeInRFC="false" toc="include" pn="section-4.2">
        <name slugifiedName="name-verification-outputs">Verification Outputs</name>
        <t indent="0" pn="section-4.2-1"><xref section="6.1.6" sectionFormat="of" target="RFC5280" format="default" derivedLink="https://rfc-editor.org/rfc/rfc5280#section-6.1.6" derivedContent="RFC5280"/>
        describes the entire <tt>valid_policy_tree</tt> structure as an output
        of the verification process. However, Section 12.2 of <xref target="X.509" format="default" sectionFormat="of" derivedContent="X.509"/> only describes the following as outputs: the
        authorities-constrained policies, the user-constrained policies, and
        their associated qualifiers.</t>
        <t indent="0" pn="section-4.2-2">As the <tt>valid_policy_tree</tt> is the exponential structure,
        computing it reintroduces the denial-of-service vulnerability. X.509
        implementations <bcp14>SHOULD NOT</bcp14> output the entire
        <tt>valid_policy_tree</tt> structure; instead, they
        <bcp14>SHOULD</bcp14> limit output to just the set of
        authorities-constrained and/or user-constrained policies, as described
        in <xref target="X.509" format="default" sectionFormat="of" derivedContent="X.509"/>. Sections <xref target="update-outputs" format="counter" sectionFormat="of" derivedContent="5.6"/> and <xref target="other-mitigations" format="counter" sectionFormat="of" derivedContent="6"/> discuss other mitigations for applications where
        this option is not available.</t>
        <t indent="0" pn="section-4.2-3">X.509 implementations <bcp14>MAY</bcp14> omit policy qualifiers
        from the output to simplify processing. Note that <xref section="4.2.1.4" sectionFormat="of" target="RFC5280" format="default" derivedLink="https://rfc-editor.org/rfc/rfc5280#section-4.2.1.4" derivedContent="RFC5280"/> already recommends that
        certification authorities omit policy qualifiers from policy
        information terms.</t>
      </section>
    </section>
    <section anchor="updates" numbered="true" removeInRFC="false" toc="include" pn="section-5">
      <name slugifiedName="name-updates-to-rfc-5280">Updates to RFC 5280</name>
      <t indent="0" pn="section-5-1">This section provides updates to <xref target="RFC5280" format="default" sectionFormat="of" derivedContent="RFC5280"/>. These updates implement the changes
described in <xref target="avoiding-exponential-growth" format="default" sectionFormat="of" derivedContent="Section 4"/>.</t>
      <section anchor="updates-to-section-61" numbered="true" removeInRFC="false" toc="include" pn="section-5.1">
        <name slugifiedName="name-updates-to-section-61">Updates to Section 6.1</name>
        <t indent="0" pn="section-5.1-1"><xref section="6.1" sectionFormat="of" target="RFC5280" format="default" derivedLink="https://rfc-editor.org/rfc/rfc5280#section-6.1" derivedContent="RFC5280"/> is updated as follows:</t>
        <t indent="0" pn="section-5.1-2">OLD:</t>
        <blockquote pn="section-5.1-3">
          <t indent="0" pn="section-5.1-3.1">A particular certification path may not, however, be
        appropriate for all applications.  Therefore, an application
        <bcp14>MAY</bcp14> 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.</t>
        </blockquote>
        <t indent="0" pn="section-5.1-4">NEW:</t>
        <blockquote pn="section-5.1-5">
          <t indent="0" pn="section-5.1-5.1">A particular certification path may not, however, be
        appropriate for all applications.  Therefore, an application
        <bcp14>MAY</bcp14> 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.</t>
        </blockquote>
      </section>
      <section anchor="updates-to-section-612" numbered="true" removeInRFC="false" toc="include" pn="section-5.2">
        <name slugifiedName="name-updates-to-section-612">Updates to Section 6.1.2</name>
        <t indent="0" pn="section-5.2-1">The following replaces entry (a) in <xref section="6.1.2" sectionFormat="of" target="RFC5280" format="default" derivedLink="https://rfc-editor.org/rfc/rfc5280#section-6.1.2" derivedContent="RFC5280"/>:
        </t>
        <blockquote pn="section-5.2-2">
          <ol spacing="normal" type="(%c)" indent="adaptive" start="1" pn="section-5.2-2.1"><li pn="section-5.2-2.1.1" derivedCounter="(a)">
              <t indent="0" pn="section-5.2-2.1.1.1"><tt>valid_policy_graph</tt>: 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
            <bcp14>MAY</bcp14> omit qualifiers if not returned in the output.
              </t>
              <t indent="0" pn="section-5.2-2.1.1.2">Each node in the <tt>valid_policy_graph</tt> includes three
            data objects: the valid policy, a set of associated policy
            qualifiers, and a set of one or more expected policy values.  </t>
              <t indent="0" pn="section-5.2-2.1.1.3">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.  </t>
              <t indent="0" pn="section-5.2-2.1.1.4">If the node is at depth x, the components of the node have the
            following semantics: </t>
              <ol spacing="normal" type="(%d)" indent="adaptive" start="1" pn="section-5.2-2.1.1.5"><li pn="section-5.2-2.1.1.5.1" derivedCounter="(1)">
                  <t indent="0" pn="section-5.2-2.1.1.5.1.1">The <tt>valid_policy</tt> is a single policy OID
                representing a valid policy for the path of length x.</t>
                </li>
                <li pn="section-5.2-2.1.1.5.2" derivedCounter="(2)">
                  <t indent="0" pn="section-5.2-2.1.1.5.2.1">The <tt>qualifier_set</tt> 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).</t>
                </li>
                <li pn="section-5.2-2.1.1.5.3" derivedCounter="(3)">
                  <t indent="0" pn="section-5.2-2.1.1.5.3.1">The <tt>expected_policy_set</tt> contains one or more
                policy OIDs that would satisfy this policy in the certificate
                x+1.</t>
                </li>
              </ol>
              <t indent="0" pn="section-5.2-2.1.1.6">The initial value of the <tt>valid_policy_graph</tt> is a
            single node with <tt>valid_policy</tt> anyPolicy, an empty
            <tt>qualifier_set</tt>, and an <tt>expected_policy_set</tt> with
            the single value anyPolicy.  This node is considered to be at
            depth zero.  </t>
              <t indent="0" pn="section-5.2-2.1.1.7">The graph additionally satisfies the following invariants:  </t>
              <ul spacing="normal" bare="false" empty="false" indent="3" pn="section-5.2-2.1.1.8">
                <li pn="section-5.2-2.1.1.8.1">
                  <t indent="0" pn="section-5.2-2.1.1.8.1.1">For any depth x and policy OID P-OID, there is at most one
                node at depth x whose <tt>valid_policy</tt> is P-OID.</t>
                </li>
                <li pn="section-5.2-2.1.1.8.2">
                  <t indent="0" pn="section-5.2-2.1.1.8.2.1">The <tt>expected_policy_set</tt> of a node whose
                <tt>valid_policy</tt> is anyPolicy is always {anyPolicy}.</t>
                </li>
                <li pn="section-5.2-2.1.1.8.3">
                  <t indent="0" pn="section-5.2-2.1.1.8.3.1">A node at depth x whose <tt>valid_policy</tt> is anyPolicy,
                except for the one at depth zero, always has exactly one
                parent: a node at depth x-1 whose <tt>valid_policy</tt> is
                also anyPolicy.</t>
                </li>
                <li pn="section-5.2-2.1.1.8.4">
                  <t indent="0" pn="section-5.2-2.1.1.8.4.1">Each node at depth greater than 0 has either one or more
                parent nodes whose <tt>valid_policy</tt> is not anyPolicy or
                a single parent node whose <tt>valid_policy</tt> is anyPolicy.
                That is, a node cannot simultaneously be a child of both
                anyPolicy and some non-anyPolicy OID.</t>
                </li>
              </ul>
              <t indent="0" pn="section-5.2-2.1.1.9"><xref target="graph-initial" format="default" sectionFormat="of" derivedContent="Figure 3"/> is a graphic representation of
            the initial state of the <tt>valid_policy_graph</tt>.  Additional
            figures will use this format to describe changes in the
            <tt>valid_policy_graph</tt> during path processing.  </t>
              <figure anchor="graph-initial" align="left" suppress-title="false" pn="figure-3">
                <name slugifiedName="name-initial-value-of-the-valid_">Initial Value of the <tt>valid_policy_graph</tt> State Variable</name>
                <artset pn="section-5.2-2.1.1.10.1">
                  <artwork type="svg" align="left" pn="section-5.2-2.1.1.10.1.1"><svg xmlns="http://www.w3.org/2000/svg" version="1.1" height="160" width="376" viewBox="0 0 376 160" class="diagram" text-anchor="middle" font-family="monospace" font-size="13px" stroke-linecap="round">
                      <path d="M 8,32 L 8,128" fill="none" stroke="black"/>
                      <path d="M 144,32 L 144,128" fill="none" stroke="black"/>
                      <path d="M 8,32 L 144,32" fill="none" stroke="black"/>
                      <path d="M 176,48 L 208,48" fill="none" stroke="black"/>
                      <path d="M 8,64 L 144,64" fill="none" stroke="black"/>
                      <path d="M 176,80 L 208,80" fill="none" stroke="black"/>
                      <path d="M 8,96 L 144,96" fill="none" stroke="black"/>
                      <path d="M 176,112 L 208,112" fill="none" stroke="black"/>
                      <path d="M 8,128 L 144,128" fill="none" stroke="black"/>
                      <polygon class="arrowhead" points="184,112 172,106.4 172,117.6" fill="black" transform="rotate(180,176,112)"/>
                      <polygon class="arrowhead" points="184,80 172,74.4 172,85.6" fill="black" transform="rotate(180,176,80)"/>
                      <polygon class="arrowhead" points="184,48 172,42.4 172,53.6" fill="black" transform="rotate(180,176,48)"/>
                      <g class="text">
                        <text x="72" y="52">anyPolicy</text>
                        <text x="268" y="52">valid_policy</text>
                        <text x="76" y="84">{}</text>
                        <text x="272" y="84">qualifier_set</text>
                        <text x="72" y="116">{anyPolicy}</text>
                        <text x="296" y="116">expected_policy_set</text>
                      </g>
                    </svg>
                  </artwork>
                  <artwork type="ascii-art" align="left" pn="section-5.2-2.1.1.10.1.2">
    +----------------+
    |   anyPolicy    |   &lt;---- valid_policy
    +----------------+
    |       {}       |   &lt;---- qualifier_set
    +----------------+
    |  {anyPolicy}   |   &lt;---- expected_policy_set
    +----------------+
</artwork>
                </artset>
              </figure>
            </li>
          </ol>
        </blockquote>
      </section>
      <section anchor="updates-to-section-613" numbered="true" removeInRFC="false" toc="include" pn="section-5.3">
        <name slugifiedName="name-updates-to-section-613">Updates to Section 6.1.3</name>
        <t indent="0" pn="section-5.3-1">The following replaces steps (d), (e), and (f) in <xref section="6.1.3" sectionFormat="of" target="RFC5280" format="default" derivedLink="https://rfc-editor.org/rfc/rfc5280#section-6.1.3" derivedContent="RFC5280"/>:
        </t>
        <blockquote pn="section-5.3-2">
          <ol spacing="normal" type="(%c)" start="4" indent="adaptive" pn="section-5.3-2.1"><li pn="section-5.3-2.1.1" derivedCounter="(d)">
              <t indent="0" pn="section-5.3-2.1.1.1">If the certificate policies extension is present in the
            certificate and the <tt>valid_policy_graph</tt> is not NULL,
            process the policy information by performing the following steps
            in order: </t>
              <ol spacing="normal" type="(%d)" indent="adaptive" start="1" pn="section-5.3-2.1.1.2"><li pn="section-5.3-2.1.1.2.1" derivedCounter="(1)">
                  <t indent="0" pn="section-5.3-2.1.1.2.1.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: </t>
                  <ol spacing="normal" type="(%i)" indent="adaptive" start="1" pn="section-5.3-2.1.1.2.1.2"><li pn="section-5.3-2.1.1.2.1.2.1" derivedCounter="(i)">
                      <t indent="0" pn="section-5.3-2.1.1.2.1.2.1.1">Let <tt>parent_nodes</tt> be the nodes at depth i-1 in
                    the <tt>valid_policy_graph</tt> where P-OID is in the
                    <tt>expected_policy_set</tt>.  If <tt>parent_nodes</tt> is
                    not empty, create a child node as follows: set the
                    <tt>valid_policy</tt> to P-OID, set the
                    <tt>qualifier_set</tt> to P-Q, set the
                    <tt>expected_policy_set</tt> to {P-OID}, and set the
                    parent nodes to <tt>parent_nodes</tt>.  </t>
                      <t indent="0" pn="section-5.3-2.1.1.2.1.2.1.2">For example, consider a <tt>valid_policy_graph</tt>
                    with a node of depth i-1 where the
                    <tt>expected_policy_set</tt> is {Gold, White} and a
                    second node where the <tt>expected_policy_set</tt> 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 <xref target="exact-match" format="default" sectionFormat="of" derivedContent="Figure 4"/>.  </t>
                      <figure anchor="exact-match" align="left" suppress-title="false" pn="figure-4">
                        <name slugifiedName="name-processing-an-exact-match">Processing an Exact Match</name>
                        <artset pn="section-5.3-2.1.1.2.1.2.1.3.1">
                          <artwork type="svg" align="left" pn="section-5.3-2.1.1.2.1.2.1.3.1.1"><svg xmlns="http://www.w3.org/2000/svg" version="1.1" height="336" width="456" viewBox="0 0 456 336" class="diagram" text-anchor="middle" font-family="monospace" font-size="13px" stroke-linecap="round">
                              <path d="M 8,32 L 8,128" fill="none" stroke="black"/>
                              <path d="M 112,208 L 112,304" fill="none" stroke="black"/>
                              <path d="M 152,32 L 152,128" fill="none" stroke="black"/>
                              <path d="M 208,32 L 208,128" fill="none" stroke="black"/>
                              <path d="M 256,208 L 256,304" fill="none" stroke="black"/>
                              <path d="M 352,32 L 352,128" fill="none" stroke="black"/>
                              <path d="M 8,32 L 152,32" fill="none" stroke="black"/>
                              <path d="M 208,32 L 352,32" fill="none" stroke="black"/>
                              <path d="M 8,64 L 152,64" fill="none" stroke="black"/>
                              <path d="M 208,64 L 352,64" fill="none" stroke="black"/>
                              <path d="M 8,96 L 152,96" fill="none" stroke="black"/>
                              <path d="M 208,96 L 352,96" fill="none" stroke="black"/>
                              <path d="M 8,128 L 152,128" fill="none" stroke="black"/>
                              <path d="M 208,128 L 352,128" fill="none" stroke="black"/>
                              <path d="M 112,208 L 256,208" fill="none" stroke="black"/>
                              <path d="M 112,240 L 256,240" fill="none" stroke="black"/>
                              <path d="M 112,272 L 256,272" fill="none" stroke="black"/>
                              <path d="M 112,304 L 256,304" fill="none" stroke="black"/>
                              <path d="M 100,136 L 132,200" fill="none" stroke="black"/>
                              <path d="M 236,200 L 268,136" fill="none" stroke="black"/>
                              <polygon class="arrowhead" points="244,200 232,194.4 232,205.6" fill="black" transform="rotate(116.56505117707799,236,200)"/>
                              <polygon class="arrowhead" points="140,200 128,194.4 128,205.6" fill="black" transform="rotate(63.43494882292201,132,200)"/>
                              <g class="text">
                                <text x="80" y="52">Red</text>
                                <text x="284" y="52">Blue</text>
                                <text x="76" y="84">{}</text>
                                <text x="276" y="84">{}</text>
                                <text x="400" y="84">depth</text>
                                <text x="440" y="84">i-1</text>
                                <text x="52" y="116">{Gold,</text>
                                <text x="108" y="116">White}</text>
                                <text x="252" y="116">{Gold,</text>
                                <text x="312" y="116">Yellow}</text>
                                <text x="180" y="228">Gold</text>
                                <text x="180" y="260">{}</text>
                                <text x="304" y="260">depth</text>
                                <text x="336" y="260">i</text>
                                <text x="180" y="292">{Gold}</text>
                              </g>
                            </svg>
                          </artwork>
                          <artwork type="ascii-art" align="left" pn="section-5.3-2.1.1.2.1.2.1.3.1.2">
+-----------------+      +-----------------+
|       Red       |      |       Blue      |
+-----------------+      +-----------------+
|       {}        |      |       {}        |   depth i-1
+-----------------+      +-----------------+
|  {Gold, White}  |      |  {Gold, Yellow} |
+-----------------+      +-----------------+
            \                   /
             \                 /
              \               /
               v             v
             +-----------------+
             |      Gold       |
             +-----------------+
             |       {}        |   depth i
             +-----------------+
             |     {Gold}      |
             +-----------------+
</artwork>
                        </artset>
                      </figure>
                    </li>
                    <li pn="section-5.3-2.1.1.2.1.2.2" derivedCounter="(ii)">
                      <t indent="0" pn="section-5.3-2.1.1.2.1.2.2.1">If there was no match in step (i) and the
                    <tt>valid_policy_graph</tt> includes a node of depth i-1
                    with the <tt>valid_policy</tt> anyPolicy, generate a child
                    node with the following values: set the
                    <tt>valid_policy</tt> to P-OID, set the
                    <tt>qualifier_set</tt> to P-Q, set the
                    <tt>expected_policy_set</tt> to {P-OID}, and set the
                    parent node to the anyPolicy node at depth i-1.  </t>
                      <t indent="0" pn="section-5.3-2.1.1.2.1.2.2.2">For example, consider a <tt>valid_policy_graph</tt>
                    with a node of depth i-1 where the <tt>valid_policy</tt>
                    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 <xref target="unmatched-anypolicy" format="default" sectionFormat="of" derivedContent="Figure 5"/>.  </t>
                      <figure anchor="unmatched-anypolicy" align="left" suppress-title="false" pn="figure-5">
                        <name slugifiedName="name-processing-unmatched-polici">Processing Unmatched Policies When a Leaf Node Specifies anyPolicy</name>
                        <artset pn="section-5.3-2.1.1.2.1.2.2.3.1">
                          <artwork type="svg" align="left" pn="section-5.3-2.1.1.2.1.2.2.3.1.1"><svg xmlns="http://www.w3.org/2000/svg" version="1.1" height="336" width="472" viewBox="0 0 472 336" class="diagram" text-anchor="middle" font-family="monospace" font-size="13px" stroke-linecap="round">
                              <path d="M 8,208 L 8,304" fill="none" stroke="black"/>
                              <path d="M 120,32 L 120,128" fill="none" stroke="black"/>
                              <path d="M 152,208 L 152,304" fill="none" stroke="black"/>
                              <path d="M 240,208 L 240,304" fill="none" stroke="black"/>
                              <path d="M 264,32 L 264,128" fill="none" stroke="black"/>
                              <path d="M 384,208 L 384,304" fill="none" stroke="black"/>
                              <path d="M 120,32 L 264,32" fill="none" stroke="black"/>
                              <path d="M 120,64 L 264,64" fill="none" stroke="black"/>
                              <path d="M 120,96 L 264,96" fill="none" stroke="black"/>
                              <path d="M 120,128 L 264,128" fill="none" stroke="black"/>
                              <path d="M 8,208 L 152,208" fill="none" stroke="black"/>
                              <path d="M 240,208 L 384,208" fill="none" stroke="black"/>
                              <path d="M 8,240 L 152,240" fill="none" stroke="black"/>
                              <path d="M 240,240 L 384,240" fill="none" stroke="black"/>
                              <path d="M 8,272 L 152,272" fill="none" stroke="black"/>
                              <path d="M 240,272 L 384,272" fill="none" stroke="black"/>
                              <path d="M 8,304 L 152,304" fill="none" stroke="black"/>
                              <path d="M 240,304 L 384,304" fill="none" stroke="black"/>
                              <path d="M 236,136 L 268,200" fill="none" stroke="black"/>
                              <path d="M 116,200 L 148,136" fill="none" stroke="black"/>
                              <polygon class="arrowhead" points="276,200 264,194.4 264,205.6" fill="black" transform="rotate(63.43494882292201,268,200)"/>
                              <polygon class="arrowhead" points="124,200 112,194.4 112,205.6" fill="black" transform="rotate(116.56505117707799,116,200)"/>
                              <g class="text">
                                <text x="192" y="52">anyPolicy</text>
                                <text x="188" y="84">{}</text>
                                <text x="312" y="100">depth</text>
                                <text x="352" y="100">i-1</text>
                                <text x="192" y="116">{anyPolicy}</text>
                                <text x="76" y="228">Gold</text>
                                <text x="308" y="228">Silver</text>
                                <text x="76" y="260">{}</text>
                                <text x="308" y="260">{Q-Silver}</text>
                                <text x="432" y="260">depth</text>
                                <text x="464" y="260">i</text>
                                <text x="76" y="292">{Gold}</text>
                                <text x="308" y="292">{Silver}</text>
                              </g>
                            </svg>
                          </artwork>
                          <artwork type="ascii-art" align="left" pn="section-5.3-2.1.1.2.1.2.2.3.1.2">
              +-----------------+
              |    anyPolicy    |
              +-----------------+
              |       {}        |
              +-----------------+   depth i-1
              |   {anyPolicy}   |
              +-----------------+
                 /           \
                /             \
               /               \
              v                 v
+-----------------+          +-----------------+
|      Gold       |          |     Silver      |
+-----------------+          +-----------------+
|       {}        |          |   {Q-Silver}    |   depth i
+-----------------+          +-----------------+
|     {Gold}      |          |    {Silver}     |
+-----------------+          +-----------------+
</artwork>
                        </artset>
                      </figure>
                    </li>
                  </ol>
                </li>
                <li pn="section-5.3-2.1.1.2.2" derivedCounter="(2)">
                  <t indent="0" pn="section-5.3-2.1.1.2.2.1">If the certificate policies extension includes the policy
                anyPolicy with the qualifier set AP-Q and either (a)
                <tt>inhibit_anyPolicy</tt> is greater than 0 or (b) i&lt;n and
                the certificate is self-issued, then: </t>
                  <t indent="0" pn="section-5.3-2.1.1.2.2.2">For each policy OID P-OID (including anyPolicy) that
                appears in the <tt>expected_policy_set</tt> of some node in
                the <tt>valid_policy_graph</tt> for depth i-1, if P-OID does
                not appear as the <tt>valid_policy</tt> of some node at depth
                i, create a single child node with the following values: set
                the <tt>valid_policy</tt> to P-OID, set the
                <tt>qualifier_set</tt> to AP-Q, set the
                <tt>expected_policy_set</tt> to {P-OID}, and set the parents
                to the nodes at depth i-1 where P-OID appears in
                <tt>expected_policy_set</tt>.  </t>
                  <t indent="0" pn="section-5.3-2.1.1.2.2.3">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.  </t>
                  <t indent="0" pn="section-5.3-2.1.1.2.2.4">For example, consider a <tt>valid_policy_graph</tt> with a
                node of depth i-1 where the <tt>expected_policy_set</tt> is
                {Gold, Silver} and a second node of depth i-1 where the
                <tt>expected_policy_set</tt> 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 <xref target="anypolicy-in-extension" format="default" sectionFormat="of" derivedContent="Figure 6"/>.  </t>
                  <figure anchor="anypolicy-in-extension" align="left" suppress-title="false" pn="figure-6">
                    <name slugifiedName="name-processing-unmatched-policie">Processing Unmatched Policies When the Certificate Policies Extension Specifies anyPolicy</name>
                    <artset pn="section-5.3-2.1.1.2.2.5.1">
                      <artwork type="svg" align="left" pn="section-5.3-2.1.1.2.2.5.1.1"><svg xmlns="http://www.w3.org/2000/svg" version="1.1" height="368" width="432" viewBox="0 0 432 368" class="diagram" text-anchor="middle" font-family="monospace" font-size="13px" stroke-linecap="round">
                          <path d="M 8,32 L 8,128" fill="none" stroke="black"/>
                          <path d="M 8,240 L 8,336" fill="none" stroke="black"/>
                          <path d="M 72,136 L 72,232" fill="none" stroke="black"/>
                          <path d="M 152,32 L 152,128" fill="none" stroke="black"/>
                          <path d="M 152,240 L 152,336" fill="none" stroke="black"/>
                          <path d="M 184,32 L 184,128" fill="none" stroke="black"/>
                          <path d="M 184,240 L 184,336" fill="none" stroke="black"/>
                          <path d="M 256,136 L 256,232" fill="none" stroke="black"/>
                          <path d="M 328,32 L 328,128" fill="none" stroke="black"/>
                          <path d="M 328,240 L 328,336" fill="none" stroke="black"/>
                          <path d="M 8,32 L 152,32" fill="none" stroke="black"/>
                          <path d="M 184,32 L 328,32" fill="none" stroke="black"/>
                          <path d="M 8,64 L 152,64" fill="none" stroke="black"/>
                          <path d="M 184,64 L 328,64" fill="none" stroke="black"/>
                          <path d="M 8,96 L 152,96" fill="none" stroke="black"/>
                          <path d="M 184,96 L 328,96" fill="none" stroke="black"/>
                          <path d="M 8,128 L 152,128" fill="none" stroke="black"/>
                          <path d="M 184,128 L 328,128" fill="none" stroke="black"/>
                          <path d="M 8,240 L 152,240" fill="none" stroke="black"/>
                          <path d="M 184,240 L 328,240" fill="none" stroke="black"/>
                          <path d="M 8,272 L 152,272" fill="none" stroke="black"/>
                          <path d="M 184,272 L 328,272" fill="none" stroke="black"/>
                          <path d="M 8,304 L 152,304" fill="none" stroke="black"/>
                          <path d="M 184,304 L 328,304" fill="none" stroke="black"/>
                          <path d="M 8,336 L 152,336" fill="none" stroke="black"/>
                          <path d="M 184,336 L 328,336" fill="none" stroke="black"/>
                          <path d="M 148,136 L 196,232" fill="none" stroke="black"/>
                          <polygon class="arrowhead" points="264,232 252,226.4 252,237.6" fill="black" transform="rotate(90,256,232)"/>
                          <polygon class="arrowhead" points="204,232 192,226.4 192,237.6" fill="black" transform="rotate(63.43494882292201,196,232)"/>
                          <polygon class="arrowhead" points="80,232 68,226.4 68,237.6" fill="black" transform="rotate(90,72,232)"/>
                          <g class="text">
                            <text x="80" y="52">Red</text>
                            <text x="260" y="52">Blue</text>
                            <text x="76" y="84">{}</text>
                            <text x="252" y="84">{}</text>
                            <text x="376" y="84">depth</text>
                            <text x="416" y="84">i-1</text>
                            <text x="52" y="116">{Gold,</text>
                            <text x="112" y="116">Silver}</text>
                            <text x="260" y="116">{Gold}</text>
                            <text x="76" y="260">Silver</text>
                            <text x="260" y="260">Gold</text>
                            <text x="76" y="292">{AP-Q}</text>
                            <text x="260" y="292">{AP-Q}</text>
                            <text x="376" y="292">depth</text>
                            <text x="408" y="292">i</text>
                            <text x="76" y="324">{Silver}</text>
                            <text x="260" y="324">{Gold}</text>
                          </g>
                        </svg>
                      </artwork>
                      <artwork type="ascii-art" align="left" pn="section-5.3-2.1.1.2.2.5.1.2">
    +-----------------+   +-----------------+
    |       Red       |   |       Blue      |
    +-----------------+   +-----------------+
    |       {}        |   |       {}        |   depth i-1
    +-----------------+   +-----------------+
    |  {Gold, Silver} |   |      {Gold}     |
    +-----------------+   +-----------------+
            |         \            |
            |          \           |
            |           \          |
            |            \         |
            |             \        |
            v              v       v
    +-----------------+   +-----------------+
    |     Silver      |   |       Gold      |
    +-----------------+   +-----------------+
    |     {AP-Q}      |   |      {AP-Q}     |   depth i
    +-----------------+   +-----------------+
    |    {Silver}     |   |      {Gold}     |
    +-----------------+   +-----------------+
</artwork>
                    </artset>
                  </figure>
                </li>
                <li pn="section-5.3-2.1.1.2.3" derivedCounter="(3)">
                  <t indent="0" pn="section-5.3-2.1.1.2.3.1">If there is a node in the <tt>valid_policy_graph</tt> 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.      </t>
                  <t indent="0" pn="section-5.3-2.1.1.2.3.2">
For example, consider the <tt>valid_policy_graph</tt> shown in <xref target="pruning" format="default" sectionFormat="of" derivedContent="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.      </t>
                  <figure anchor="pruning" align="left" suppress-title="false" pn="figure-7">
                    <name slugifiedName="name-pruning-the-valid_policy_gr">Pruning the valid_policy_graph</name>
                    <artset pn="section-5.3-2.1.1.2.3.3.1">
                      <artwork type="svg" align="left" pn="section-5.3-2.1.1.2.3.3.1.1"><svg xmlns="http://www.w3.org/2000/svg" version="1.1" height="384" width="416" viewBox="0 0 416 384" class="diagram" text-anchor="middle" font-family="monospace" font-size="13px" stroke-linecap="round">
                          <path d="M 8,128 L 8,160" fill="none" stroke="black"/>
                          <path d="M 8,224 L 8,256" fill="none" stroke="black"/>
                          <path d="M 8,320 L 8,352" fill="none" stroke="black"/>
                          <path d="M 56,168 L 56,216" fill="none" stroke="black"/>
                          <path d="M 104,128 L 104,160" fill="none" stroke="black"/>
                          <path d="M 104,224 L 104,256" fill="none" stroke="black"/>
                          <path d="M 104,320 L 104,352" fill="none" stroke="black"/>
                          <path d="M 120,32 L 120,64" fill="none" stroke="black"/>
                          <path d="M 120,128 L 120,160" fill="none" stroke="black"/>
                          <path d="M 120,224 L 120,256" fill="none" stroke="black"/>
                          <path d="M 120,320 L 120,352" fill="none" stroke="black"/>
                          <path d="M 168,72 L 168,120" fill="none" stroke="black"/>
                          <path d="M 168,168 L 168,216" fill="none" stroke="black"/>
                          <path d="M 168,264 L 168,312" fill="none" stroke="black"/>
                          <path d="M 216,32 L 216,64" fill="none" stroke="black"/>
                          <path d="M 216,128 L 216,160" fill="none" stroke="black"/>
                          <path d="M 216,224 L 216,256" fill="none" stroke="black"/>
                          <path d="M 216,320 L 216,352" fill="none" stroke="black"/>
                          <path d="M 232,128 L 232,160" fill="none" stroke="black"/>
                          <path d="M 232,224 L 232,256" fill="none" stroke="black"/>
                          <path d="M 232,320 L 232,352" fill="none" stroke="black"/>
                          <path d="M 280,168 L 280,216" fill="none" stroke="black"/>
                          <path d="M 328,128 L 328,160" fill="none" stroke="black"/>
                          <path d="M 328,224 L 328,256" fill="none" stroke="black"/>
                          <path d="M 328,320 L 328,352" fill="none" stroke="black"/>
                          <path d="M 120,32 L 216,32" fill="none" stroke="black"/>
                          <path d="M 120,64 L 216,64" fill="none" stroke="black"/>
                          <path d="M 8,128 L 104,128" fill="none" stroke="black"/>
                          <path d="M 120,128 L 216,128" fill="none" stroke="black"/>
                          <path d="M 232,128 L 328,128" fill="none" stroke="black"/>
                          <path d="M 8,160 L 104,160" fill="none" stroke="black"/>
                          <path d="M 120,160 L 216,160" fill="none" stroke="black"/>
                          <path d="M 232,160 L 328,160" fill="none" stroke="black"/>
                          <path d="M 8,224 L 104,224" fill="none" stroke="black"/>
                          <path d="M 120,224 L 216,224" fill="none" stroke="black"/>
                          <path d="M 232,224 L 328,224" fill="none" stroke="black"/>
                          <path d="M 8,256 L 104,256" fill="none" stroke="black"/>
                          <path d="M 120,256 L 216,256" fill="none" stroke="black"/>
                          <path d="M 232,256 L 328,256" fill="none" stroke="black"/>
                          <path d="M 8,320 L 104,320" fill="none" stroke="black"/>
                          <path d="M 120,320 L 216,320" fill="none" stroke="black"/>
                          <path d="M 232,320 L 328,320" fill="none" stroke="black"/>
                          <path d="M 8,352 L 104,352" fill="none" stroke="black"/>
                          <path d="M 120,352 L 216,352" fill="none" stroke="black"/>
                          <path d="M 232,352 L 328,352" fill="none" stroke="black"/>
                          <path d="M 100,168 L 124,216" fill="none" stroke="black"/>
                          <path d="M 212,264 L 236,312" fill="none" stroke="black"/>
                          <path d="M 212,72 L 236,120" fill="none" stroke="black"/>
                          <path d="M 100,120 L 124,72" fill="none" stroke="black"/>
                          <path d="M 100,312 L 124,264" fill="none" stroke="black"/>
                          <polygon class="arrowhead" points="288,216 276,210.4 276,221.6" fill="black" transform="rotate(90,280,216)"/>
                          <polygon class="arrowhead" points="244,312 232,306.4 232,317.6" fill="black" transform="rotate(63.43494882292201,236,312)"/>
                          <polygon class="arrowhead" points="244,120 232,114.4 232,125.6" fill="black" transform="rotate(63.43494882292201,236,120)"/>
                          <polygon class="arrowhead" points="176,312 164,306.4 164,317.6" fill="black" transform="rotate(90,168,312)"/>
                          <polygon class="arrowhead" points="176,216 164,210.4 164,221.6" fill="black" transform="rotate(90,168,216)"/>
                          <polygon class="arrowhead" points="176,120 164,114.4 164,125.6" fill="black" transform="rotate(90,168,120)"/>
                          <polygon class="arrowhead" points="132,216 120,210.4 120,221.6" fill="black" transform="rotate(63.43494882292201,124,216)"/>
                          <polygon class="arrowhead" points="108,312 96,306.4 96,317.6" fill="black" transform="rotate(116.56505117707799,100,312)"/>
                          <polygon class="arrowhead" points="108,120 96,114.4 96,125.6" fill="black" transform="rotate(116.56505117707799,100,120)"/>
                          <polygon class="arrowhead" points="64,216 52,210.4 52,221.6" fill="black" transform="rotate(90,56,216)"/>
                          <g class="text">
                            <text x="248" y="52">depth</text>
                            <text x="288" y="52">i-3</text>
                            <text x="280" y="148">Y</text>
                            <text x="360" y="148">depth</text>
                            <text x="400" y="148">i-2</text>
                            <text x="56" y="244">X</text>
                            <text x="280" y="244">X</text>
                            <text x="360" y="244">depth</text>
                            <text x="400" y="244">i-1</text>
                            <text x="360" y="340">depth</text>
                            <text x="392" y="340">i</text>
                          </g>
                        </svg>
                      </artwork>
                      <artwork type="ascii-art" align="left" pn="section-5.3-2.1.1.2.3.3.1.2">
                  +-----------+
                  |           | depth i-3
                  +-----------+
                  /     |     \
                 /      |      \
                v       v       v
    +-----------+ +-----------+ +-----------+
    |           | |           | |     Y     | depth i-2
    +-----------+ +-----------+ +-----------+
          |     \       |             |
          |      \      |             |
          v       v     v             v
    +-----------+ +-----------+ +-----------+
    |     X     | |           | |     X     | depth i-1
    +-----------+ +-----------+ +-----------+
                  /     |     \
                 /      |      \
                v       v       v
    +-----------+ +-----------+ +-----------+
    |           | |           | |           | depth i
    +-----------+ +-----------+ +-----------+
</artwork>
                    </artset>
                  </figure>
                </li>
              </ol>
            </li>
            <li pn="section-5.3-2.1.2" derivedCounter="(e)">
              <t indent="0" pn="section-5.3-2.1.2.1">If the certificate policies extension is not present, set the
            <tt>valid_policy_graph</tt> to NULL.</t>
            </li>
            <li pn="section-5.3-2.1.3" derivedCounter="(f)">
              <t indent="0" pn="section-5.3-2.1.3.1">Verify that either <tt>explicit_policy</tt> is greater than 0
            or the <tt>valid_policy_graph</tt> is not equal to NULL.</t>
            </li>
          </ol>
        </blockquote>
        <t indent="0" pn="section-5.3-3">The text following step (f) in <xref section="6.1.3" sectionFormat="of" target="RFC5280" format="default" derivedLink="https://rfc-editor.org/rfc/rfc5280#section-6.1.3" derivedContent="RFC5280"/>, beginning with "If any of steps (a), (b), (c), or (f) fails", is left unmodified.</t>
      </section>
      <section anchor="updates-to-section-614" numbered="true" removeInRFC="false" toc="include" pn="section-5.4">
        <name slugifiedName="name-updates-to-section-614">Updates to Section 6.1.4</name>
        <t indent="0" pn="section-5.4-1">The following replaces step (b) in <xref section="6.1.4" sectionFormat="of" target="RFC5280" format="default" derivedLink="https://rfc-editor.org/rfc/rfc5280#section-6.1.4" derivedContent="RFC5280"/>:</t>
        <blockquote pn="section-5.4-2">
          <ol spacing="normal" type="(%c)" start="2" indent="adaptive" pn="section-5.4-2.1"><li pn="section-5.4-2.1.1" derivedCounter="(b)">
              <t indent="0" pn="section-5.4-2.1.1.1">If a policy mappings extension is present, then for each issuerDomainPolicy ID-P in the policy mappings extension:  </t>
              <ol spacing="normal" type="(%d)" indent="adaptive" start="1" pn="section-5.4-2.1.1.2"><li pn="section-5.4-2.1.1.2.1" derivedCounter="(1)">
                  <t indent="0" pn="section-5.4-2.1.1.2.1.1">If the <tt>policy_mapping</tt> variable is greater than 0 and there is a
node in the <tt>valid_policy_graph</tt> of depth i where ID-P is the
<tt>valid_policy</tt>, set <tt>expected_policy_set</tt> to the set of
subjectDomainPolicy values that are specified as
equivalent to ID-P by the policy mappings extension.</t>
                </li>
                <li pn="section-5.4-2.1.1.2.2" derivedCounter="(2)">
                  <t indent="0" pn="section-5.4-2.1.1.2.2.1">If the <tt>policy_mapping</tt> variable is greater than 0 and 
no node of depth i in the <tt>valid_policy_graph</tt> has a
<tt>valid_policy</tt> of ID-P but there is a node of depth i with a
<tt>valid_policy</tt> of anyPolicy, then generate a child node of
the node of depth i-1 that has a <tt>valid_policy</tt> of anyPolicy
as follows:      </t>
                  <ol spacing="normal" type="(%i)" indent="adaptive" start="1" pn="section-5.4-2.1.1.2.2.2"><li pn="section-5.4-2.1.1.2.2.2.1" derivedCounter="(i)">
                      <t indent="0" pn="section-5.4-2.1.1.2.2.2.1.1">set the <tt>valid_policy</tt> to ID-P;</t>
                    </li>
                    <li pn="section-5.4-2.1.1.2.2.2.2" derivedCounter="(ii)">
                      <t indent="0" pn="section-5.4-2.1.1.2.2.2.2.1">set the <tt>qualifier_set</tt> to the qualifier set of the
policy anyPolicy in the certificate policies
extension of certificate i; and</t>
                    </li>
                    <li pn="section-5.4-2.1.1.2.2.2.3" derivedCounter="(iii)">
                      <t indent="0" pn="section-5.4-2.1.1.2.2.2.3.1">set the <tt>expected_policy_set</tt> to the set of
subjectDomainPolicy values that are specified as
equivalent to ID-P by the policy mappings extension.</t>
                    </li>
                  </ol>
                </li>
                <li pn="section-5.4-2.1.1.2.3" derivedCounter="(3)">
                  <t indent="0" pn="section-5.4-2.1.1.2.3.1">If the <tt>policy_mapping</tt> variable is equal to 0:      </t>
                  <ol spacing="normal" type="(%i)" indent="adaptive" start="1" pn="section-5.4-2.1.1.2.3.2"><li pn="section-5.4-2.1.1.2.3.2.1" derivedCounter="(i)">
                      <t indent="0" pn="section-5.4-2.1.1.2.3.2.1.1">delete the node, if any, of depth i in the <tt>valid_policy_graph</tt> where ID-P is the <tt>valid_policy</tt>.</t>
                    </li>
                    <li pn="section-5.4-2.1.1.2.3.2.2" derivedCounter="(ii)">
                      <t indent="0" pn="section-5.4-2.1.1.2.3.2.2.1">If there is a node in the <tt>valid_policy_graph</tt> 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.</t>
                    </li>
                  </ol>
                </li>
              </ol>
            </li>
          </ol>
        </blockquote>
      </section>
      <section anchor="updates-to-section-615" numbered="true" removeInRFC="false" toc="include" pn="section-5.5">
        <name slugifiedName="name-updates-to-section-615">Updates to Section 6.1.5</name>
        <t indent="0" pn="section-5.5-1">The following replaces step (g) in <xref section="6.1.5" sectionFormat="of" target="RFC5280" format="default" derivedLink="https://rfc-editor.org/rfc/rfc5280#section-6.1.5" derivedContent="RFC5280"/>:</t>
        <blockquote pn="section-5.5-2">
          <ol spacing="normal" type="(%c)" start="7" indent="adaptive" pn="section-5.5-2.1"><li pn="section-5.5-2.1.1" derivedCounter="(g)">
              <t indent="0" pn="section-5.5-2.1.1.1">Calculate the <tt>user_constrained_policy_set</tt> as follows.
The <tt>user_constrained_policy_set</tt> is a set of policy OIDs, along with associated policy qualifiers.  </t>
              <ol spacing="normal" type="(%d)" indent="adaptive" start="1" pn="section-5.5-2.1.1.2"><li pn="section-5.5-2.1.1.2.1" derivedCounter="(1)">
                  <t indent="0" pn="section-5.5-2.1.1.2.1.1">If the <tt>valid_policy_graph</tt> is NULL, set <tt>valid_policy_node_set</tt> to the empty set.</t>
                </li>
                <li pn="section-5.5-2.1.1.2.2" derivedCounter="(2)">
                  <t indent="0" pn="section-5.5-2.1.1.2.2.1">If the <tt>valid_policy_graph</tt> is not NULL, set <tt>valid_policy_node_set</tt> to the set of policy nodes
whose <tt>valid_policy</tt> is not anyPolicy and
whose parent list is a single node with <tt>valid_policy</tt> of anyPolicy.</t>
                </li>
                <li pn="section-5.5-2.1.1.2.3" derivedCounter="(3)">
                  <t indent="0" pn="section-5.5-2.1.1.2.3.1">If the <tt>valid_policy_graph</tt> is not NULL and contains a node of depth n with the <tt>valid_policy</tt> anyPolicy, add it to <tt>valid_policy_node_set</tt>.</t>
                </li>
                <li pn="section-5.5-2.1.1.2.4" derivedCounter="(4)">
                  <t indent="0" pn="section-5.5-2.1.1.2.4.1">Compute <tt>authority_constrained_policy_set</tt>, a set of policy OIDs and associated qualifiers as follows. For each node in <tt>valid_policy_node_set</tt>:      </t>
                  <ol spacing="normal" type="(%i)" indent="adaptive" start="1" pn="section-5.5-2.1.1.2.4.2"><li pn="section-5.5-2.1.1.2.4.2.1" derivedCounter="(i)">
                      <t indent="0" pn="section-5.5-2.1.1.2.4.2.1.1">Add the node's <tt>valid_policy</tt> to <tt>authority_constrained_policy_set</tt>.</t>
                    </li>
                    <li pn="section-5.5-2.1.1.2.4.2.2" derivedCounter="(ii)">
                      <t indent="0" pn="section-5.5-2.1.1.2.4.2.2.1">Collect all qualifiers in the node, its ancestors, and descendants and associate them with <tt>valid_policy</tt>. Applications that do not use policy qualifiers <bcp14>MAY</bcp14> skip this step to simplify processing.</t>
                    </li>
                  </ol>
                </li>
                <li pn="section-5.5-2.1.1.2.5" derivedCounter="(5)">
                  <t indent="0" pn="section-5.5-2.1.1.2.5.1">Set <tt>user_constrained_policy_set</tt> to <tt>authority_constrained_policy_set</tt>.</t>
                </li>
                <li pn="section-5.5-2.1.1.2.6" derivedCounter="(6)">
                  <t indent="0" pn="section-5.5-2.1.1.2.6.1">If the user-initial-policy-set is not anyPolicy:      </t>
                  <ol spacing="normal" type="(%i)" indent="adaptive" start="1" pn="section-5.5-2.1.1.2.6.2"><li pn="section-5.5-2.1.1.2.6.2.1" derivedCounter="(i)">
                      <t indent="0" pn="section-5.5-2.1.1.2.6.2.1.1">Remove any elements of <tt>user_constrained_policy_set</tt> that do not appear in user-initial-policy-set.</t>
                    </li>
                    <li pn="section-5.5-2.1.1.2.6.2.2" derivedCounter="(ii)">
                      <t indent="0" pn="section-5.5-2.1.1.2.6.2.2.1">If anyPolicy appears in <tt>authority_constrained_policy_set</tt> with qualifiers AP-Q, for each OID P-OID in user-initial-policy-set that does not appear in <tt>user_constrained_policy_set</tt>, add P-OID with qualifiers AP-Q to <tt>user_constrained_policy_set</tt>.</t>
                    </li>
                  </ol>
                </li>
              </ol>
            </li>
          </ol>
        </blockquote>
        <t indent="0" pn="section-5.5-3">In addition, the final paragraph in <xref section="6.1.5" sectionFormat="of" target="RFC5280" format="default" derivedLink="https://rfc-editor.org/rfc/rfc5280#section-6.1.5" derivedContent="RFC5280"/> is updated as follows:</t>
        <t indent="0" pn="section-5.5-4">OLD:</t>
        <blockquote pn="section-5.5-5">
          <t indent="0" pn="section-5.5-5.1">If either (1) the value of <tt>explicit_policy</tt>
        variable is greater than zero or (2) the <tt>valid_policy_tree</tt> is
        not NULL, then path processing has succeeded.</t>
        </blockquote>
        <t indent="0" pn="section-5.5-6">NEW:</t>
        <blockquote pn="section-5.5-7">
          <t indent="0" pn="section-5.5-7.1">If either (1) the value of <tt>explicit_policy</tt> is
        greater than zero, or (2) the <tt>user_constrained_policy_set</tt> is
        not empty, then path processing has succeeded.</t>
        </blockquote>
      </section>
      <section anchor="update-outputs" numbered="true" removeInRFC="false" toc="include" pn="section-5.6">
        <name slugifiedName="name-updates-to-section-616">Updates to Section 6.1.6</name>
        <t indent="0" pn="section-5.6-1">The following replaces <xref section="6.1.6" sectionFormat="of" target="RFC5280" format="default" derivedLink="https://rfc-editor.org/rfc/rfc5280#section-6.1.6" derivedContent="RFC5280"/>:</t>
        <blockquote pn="section-5.6-2">
          <t indent="0" pn="section-5.6-2.1">If path processing succeeds, the procedure terminates, returning
          a success indication together with the final value of the
          <tt>user_constrained_policy_set</tt>, the
          <tt>working_public_key</tt>, the
          <tt>working_public_key_algorithm</tt>, and the
          <tt>working_public_key_parameters</tt>.</t>
          <t indent="0" pn="section-5.6-2.2">Note that the original procedure described in <xref target="RFC5280" format="default" sectionFormat="of" derivedContent="RFC5280"/> included a <tt>valid_policy_tree</tt> 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 <xref target="CVE-2023-0464" format="default" sectionFormat="of" derivedContent="CVE-2023-0464"/> and <xref target="CVE-2023-23524" format="default" sectionFormat="of" derivedContent="CVE-2023-23524"/>. Accordingly, this output is
          deprecated. Computing this structure is <bcp14>NOT RECOMMENDED</bcp14>.</t>
          <t indent="0" pn="section-5.6-2.3">An implementation that requires <tt>valid_policy_tree</tt> for
          compatibility with legacy systems may compute it from
          <tt>valid_policy_graph</tt> 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
          <bcp14>SHOULD</bcp14> mitigate denial-of-service attacks in other ways, such
          as by limiting the depth or size of the tree.</t>
        </blockquote>
      </section>
    </section>
    <section anchor="other-mitigations" numbered="true" removeInRFC="false" toc="include" pn="section-6">
      <name slugifiedName="name-other-mitigations">Other Mitigations</name>
      <t indent="0" pn="section-6-1">X.509 implementations that are unable to switch to the policy graph structure
<bcp14>SHOULD</bcp14> mitigate the denial-of-service attack in other ways. This section
describes alternate mitigation and partial mitigation strategies.</t>
      <section anchor="verify-signatures-first" numbered="true" removeInRFC="false" toc="include" pn="section-6.1">
        <name slugifiedName="name-verify-signatures-first">Verify Signatures First</name>
        <t indent="0" pn="section-6.1-1">X.509 validators <bcp14>SHOULD</bcp14> 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:</t>
        <ul spacing="normal" bare="false" empty="false" indent="3" pn="section-6.1-2">
          <li pn="section-6.1-2.1">
            <t indent="0" pn="section-6.1-2.1.1">Any application that evaluates an untrusted PKI, such as a
            hosting provider that evaluates a customer-supplied PKI</t>
          </li>
          <li pn="section-6.1-2.2">
            <t indent="0" pn="section-6.1-2.2.1">Any application that evaluates an otherwise trusted PKI that
            includes untrusted entities with technically constrained
            intermediate certificates. If the intermediates do not constrain
            policy mapping or path length, those entities may be able to
            perform this attack.</t>
          </li>
        </ul>
      </section>
      <section anchor="limit-certificate-depth" numbered="true" removeInRFC="false" toc="include" pn="section-6.2">
        <name slugifiedName="name-limit-certificate-depth">Limit Certificate Depth</name>
        <t indent="0" pn="section-6.2-1">The policy tree grows exponentially in the depth of a certification
        path, so limiting the depth and certificate size can mitigate the
        attack.</t>
        <t indent="0" pn="section-6.2-2">However, this option may not be viable for all applications. Too
        low of a limit may reject existing paths that the application wishes
        to accept. Too high of a limit may still admit a denial-of-service attack for the
        application. By modifying the example in <xref target="exponential-growth" format="default" sectionFormat="of" derivedContent="Section 3.2"/> to increase the number of policies
        asserted in each certificate, an attacker could still achieve
        O(N<sup>(depth/2)</sup>) scaling.</t>
      </section>
      <section anchor="limit-policy-tree-size" numbered="true" removeInRFC="false" toc="include" pn="section-6.3">
        <name slugifiedName="name-limit-policy-tree-size">Limit Policy Tree Size</name>
        <t indent="0" pn="section-6.3-1">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 denial-of-service attack.</t>
      </section>
      <section anchor="inhibit-policy-mapping" numbered="true" removeInRFC="false" toc="include" pn="section-6.4">
        <name slugifiedName="name-inhibit-policy-mapping">Inhibit Policy Mapping</name>
        <t indent="0" pn="section-6.4-1">If policy mapping is disabled via the initial-policy-mapping-inhibit setting
(see <xref section="6.1.1" sectionFormat="of" target="RFC5280" format="default" derivedLink="https://rfc-editor.org/rfc/rfc5280#section-6.1.1" derivedContent="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 that rely on policy mapping.</t>
        <t indent="0" pn="section-6.4-2">To facilitate this mitigation, certificate authorities <bcp14>SHOULD NOT</bcp14> issue
certificates with the policy mappings extension (<xref section="4.2.1.5" sectionFormat="of" target="RFC5280" format="default" derivedLink="https://rfc-editor.org/rfc/rfc5280#section-4.2.1.5" derivedContent="RFC5280"/>). Applications maintaining policies for accepted trust anchors are
<bcp14>RECOMMENDED</bcp14> to forbid this extension in participating certificate authorities.</t>
      </section>
      <section anchor="disable-policy-checking" numbered="true" removeInRFC="false" toc="include" pn="section-6.5">
        <name slugifiedName="name-disable-policy-checking">Disable Policy Checking</name>
        <t indent="0" pn="section-6.5-1">An X.509 validator can mitigate this attack by disabling policy validation
entirely. This may be viable for applications that do not require policy
validation. In this case, critical policy-related extensions, notably the policy
constraints extension (<xref section="4.2.1.11" sectionFormat="of" target="RFC5280" format="default" derivedLink="https://rfc-editor.org/rfc/rfc5280#section-4.2.1.11" derivedContent="RFC5280"/>), <bcp14>MUST</bcp14> be treated as unrecognized
extensions as described in <xref section="4.2" sectionFormat="of" target="RFC5280" format="default" derivedLink="https://rfc-editor.org/rfc/rfc5280#section-4.2" derivedContent="RFC5280"/> and be rejected.</t>
      </section>
    </section>
    <section anchor="security-considerations" numbered="true" removeInRFC="false" toc="include" pn="section-7">
      <name slugifiedName="name-security-considerations">Security Considerations</name>
      <t indent="0" pn="section-7-1"><xref target="dos" format="default" sectionFormat="of" derivedContent="Section 3"/> discusses how the policy
      tree algorithm in <xref target="RFC5280" format="default" sectionFormat="of" derivedContent="RFC5280"/> can lead to denial-of-service vulnerabilities in
      X.509-based applications, such as <xref target="CVE-2023-0464" format="default" sectionFormat="of" derivedContent="CVE-2023-0464"/> and
      <xref target="CVE-2023-23524" format="default" sectionFormat="of" derivedContent="CVE-2023-23524"/>.</t>
      <t indent="0" pn="section-7-2"><xref target="updates" format="default" sectionFormat="of" derivedContent="Section 5"/> replaces this algorithm to avoid this
      issue. As discussed in <xref target="policy-graph" format="default" sectionFormat="of" derivedContent="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.</t>
    </section>
    <section anchor="iana-considerations" numbered="true" removeInRFC="false" toc="include" pn="section-8">
      <name slugifiedName="name-iana-considerations">IANA Considerations</name>
      <t indent="0" pn="section-8-1">This document has no IANA actions.</t>
    </section>
  </middle>
  <back>
    <references pn="section-9">
      <name slugifiedName="name-references">References</name>
      <references anchor="sec-normative-references" pn="section-9.1">
        <name slugifiedName="name-normative-references">Normative References</name>
        <reference anchor="RFC2119" target="https://www.rfc-editor.org/info/rfc2119" quoteTitle="true" derivedAnchor="RFC2119">
          <front>
            <title>Key words for use in RFCs to Indicate Requirement Levels</title>
            <author fullname="S. Bradner" initials="S." surname="Bradner"/>
            <date month="March" year="1997"/>
            <abstract>
              <t indent="0">In many standards track documents several words are used to signify the requirements in the specification. These words are often capitalized. This document defines these words as they should be interpreted in IETF documents. This document specifies an Internet Best Current Practices for the Internet Community, and requests discussion and suggestions for improvements.</t>
            </abstract>
          </front>
          <seriesInfo name="BCP" value="14"/>
          <seriesInfo name="RFC" value="2119"/>
          <seriesInfo name="DOI" value="10.17487/RFC2119"/>
        </reference>
        <reference anchor="RFC5280" target="https://www.rfc-editor.org/info/rfc5280" quoteTitle="true" derivedAnchor="RFC5280">
          <front>
            <title>Internet X.509 Public Key Infrastructure Certificate and Certificate Revocation List (CRL) Profile</title>
            <author fullname="D. Cooper" initials="D." surname="Cooper"/>
            <author fullname="S. Santesson" initials="S." surname="Santesson"/>
            <author fullname="S. Farrell" initials="S." surname="Farrell"/>
            <author fullname="S. Boeyen" initials="S." surname="Boeyen"/>
            <author fullname="R. Housley" initials="R." surname="Housley"/>
            <author fullname="W. Polk" initials="W." surname="Polk"/>
            <date month="May" year="2008"/>
            <abstract>
              <t indent="0">This memo profiles the X.509 v3 certificate and X.509 v2 certificate revocation list (CRL) for use in the Internet. An overview of this approach and model is provided as an introduction. The X.509 v3 certificate format is described in detail, with additional information regarding the format and semantics of Internet name forms. Standard certificate extensions are described and two Internet-specific extensions are defined. A set of required certificate extensions is specified. The X.509 v2 CRL format is described in detail along with standard and Internet-specific extensions. An algorithm for X.509 certification path validation is described. An ASN.1 module and examples are provided in the appendices. [STANDARDS-TRACK]</t>
            </abstract>
          </front>
          <seriesInfo name="RFC" value="5280"/>
          <seriesInfo name="DOI" value="10.17487/RFC5280"/>
        </reference>
        <reference anchor="RFC8174" target="https://www.rfc-editor.org/info/rfc8174" quoteTitle="true" derivedAnchor="RFC8174">
          <front>
            <title>Ambiguity of Uppercase vs Lowercase in RFC 2119 Key Words</title>
            <author fullname="B. Leiba" initials="B." surname="Leiba"/>
            <date month="May" year="2017"/>
            <abstract>
              <t indent="0">RFC 2119 specifies common key words that may be used in protocol specifications. This document aims to reduce the ambiguity by clarifying that only UPPERCASE usage of the key words have the defined special meanings.</t>
            </abstract>
          </front>
          <seriesInfo name="BCP" value="14"/>
          <seriesInfo name="RFC" value="8174"/>
          <seriesInfo name="DOI" value="10.17487/RFC8174"/>
        </reference>
      </references>
      <references anchor="sec-informative-references" pn="section-9.2">
        <name slugifiedName="name-informative-references">Informative References</name>
        <reference anchor="CVE-2023-0464" target="https://www.cve.org/CVERecord?id=CVE-2023-0464" quoteTitle="true" derivedAnchor="CVE-2023-0464">
          <front>
            <title>Excessive Resource Usage Verifying X.509 Policy Constraints</title>
            <author>
              <organization showOnFrontPage="true">CVE</organization>
            </author>
            <date year="2023" month="March"/>
          </front>
          <refcontent>CVE-2023-0464</refcontent>
        </reference>
        <reference anchor="CVE-2023-23524" target="https://www.cve.org/CVERecord?id=CVE-2023-23524" quoteTitle="true" derivedAnchor="CVE-2023-23524">
          <front>
            <title>Processing a maliciously crafted certificate may lead to a denial-of-service</title>
            <author>
              <organization showOnFrontPage="true">CVE</organization>
            </author>
            <date year="2023" month="February"/>
          </front>
          <refcontent>CVE-2023-23524</refcontent>
        </reference>
        <reference anchor="RFC8446" target="https://www.rfc-editor.org/info/rfc8446" quoteTitle="true" derivedAnchor="RFC8446">
          <front>
            <title>The Transport Layer Security (TLS) Protocol Version 1.3</title>
            <author fullname="E. Rescorla" initials="E." surname="Rescorla"/>
            <date month="August" year="2018"/>
            <abstract>
              <t indent="0">This document specifies version 1.3 of the Transport Layer Security (TLS) protocol. TLS allows client/server applications to communicate over the Internet in a way that is designed to prevent eavesdropping, tampering, and message forgery.</t>
              <t indent="0">This document updates RFCs 5705 and 6066, and obsoletes RFCs 5077, 5246, and 6961. This document also specifies new requirements for TLS 1.2 implementations.</t>
            </abstract>
          </front>
          <seriesInfo name="RFC" value="8446"/>
          <seriesInfo name="DOI" value="10.17487/RFC8446"/>
        </reference>
        <reference anchor="X.509" target="https://www.itu.int/rec/T-REC-X.509" quoteTitle="true" derivedAnchor="X.509">
          <front>
            <title>Information technology - Open Systems Interconnection - The Directory: Public-key and attribute certificate frameworks</title>
            <author>
              <organization showOnFrontPage="true">ITU-T</organization>
            </author>
            <date year="2019" month="October"/>
          </front>
          <seriesInfo name="ITU-T Recommendation" value="X.509"/>
        </reference>
      </references>
    </references>
    <section numbered="false" anchor="acknowledgements" removeInRFC="false" toc="include" pn="section-appendix.a">
      <name slugifiedName="name-acknowledgements">Acknowledgements</name>
      <t indent="0" pn="section-appendix.a-1">The author thanks <contact fullname="Bob Beck"/>, <contact fullname="Adam Langley"/>, <contact fullname="Matt Mueller"/>, and
      <contact fullname="Ryan Sleevi"/> for many valuable discussions that led
      to discovering this issue, understanding it, and developing the
      mitigation. The author also thanks <contact fullname="Martin Thomson"/>,
      <contact fullname="Job Snijders"/>, and <contact fullname="John       Scudder"/> for their review and feedback on this document.</t>
    </section>
    <section anchor="authors-addresses" numbered="false" removeInRFC="false" toc="include" pn="section-appendix.b">
      <name slugifiedName="name-authors-address">Author's Address</name>
      <author initials="D." surname="Benjamin" fullname="David Benjamin">
        <organization showOnFrontPage="true">Google LLC</organization>
        <address>
          <email>davidben@google.com</email>
        </address>
      </author>
    </section>
  </back>
</rfc>
