Secure Inter-Domain Routing M. Reynolds Internet-Draft S. Kent Intended status: Standards Track BBN Expires: May 13, 2011 November 9, 2010 Local Trust Anchor Management for the Resource Public Key Infrastructure Status of this Memo This Internet-Draft is submitted to IETF in full conformance with the provisions of BCP 78 and BCP 79. Internet-Drafts are working documents of the Internet Engineering Task Force (IETF), its areas, and its working groups. Note that other groups may also distribute working documents as Internet-Drafts. Internet-Drafts are draft documents valid for a maximum of six months and may be updated, replaced, or obsoleted by other documents at any time. It is inappropriate to use Internet-Drafts as reference material or to cite them other than as "work in progress." The list of current Internet-Drafts can be accessed at http://www.ietf.org/1id-abstracts.html The list of Internet-Draft Shadow Directories can be accessed at http://www.ietf.org/shadow.html This Internet-Draft will expire on May 13, 2011. Copyright and License Notice Copyright (c) 2010 IETF Trust and the persons identified as the document authors. All rights reserved. This document is subject to BCP 78 and the IETF Trust's Legal Provisions Relating to IETF Documents (http://trustee.ietf.org/license-info) in effect on the date of publication of this document. Please review these documents carefully, as they describe your rights and restrictions with respect to this document. Code Components extracted from this document must include Simplified BSD License text as described in Section 4.e of the Trust Legal Provisions and are provided without warranty as described in the Simplified BSD License. Reynolds, et al Expires May 13, 2011 [Page 1] Internet-Draft RPKI Local TA Management November 2010 Abstract This document describes a facility to enable a relying party (RP) to manage trust anchors (TAs) in the context of the Resource Public Key Infrastructure (RPKI). It is common to allow an RP to import TA material in the form of self-signed certificates. The facility described in this document allows an RP to impose constraints on such TAs. Because this mechanism is designed to operate in the RPKI context, the relevant constraints are the RFC 3779 extensions that bind address spaces and/or autonomous system (AS) numbers to entities. The primary motivation for this facility is to enable an RP to ensure that resource allocation information that it has acquired via some trusted channel is not overridden by the information acquired from the RPKI repository system or by the putative TAs that the RP imports. Specifically, the mechanism allows an RP to specify a set of bindings between public key identifiers and RFC 3779 extension data and will override any conflicting bindings expressed via the putative TAs and the certificates downloaded from the RPKI repository system. Although this mechanism is designed for local use by an RP, an entity that is accorded administrative control over a set of RPs may use this mechanism to convey its view of the RPKI to a set of RPs within its jurisdiction. The means by which this latter use case is effected is outside the scope of this document. Table of Contents 1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . 4 1.1 Terminology . . . . . . . . . . . . . . . . . . . . . . . . 5 2 Overview of Certificate Processing . . . . . . . . . . . . . . . 5 2.1 Target Certificate Processing . . . . . . . . . . . . . . . 5 2.2 Perforation . . . . . . . . . . . . . . . . . . . . . . . . 5 2.3 TA Re-parenting . . . . . . . . . . . . . . . . . . . . . . 6 2.4 Paracertificates . . . . . . . . . . . . . . . . . . . . . 6 3 Format of the constraints file . . . . . . . . . . . . . . . . . 8 3.1 Relying party subsection . . . . . . . . . . . . . . . . . 8 3.2 Flags subsection . . . . . . . . . . . . . . . . . . . . . 8 3.3 Tags subsection . . . . . . . . . . . . . . . . . . . . . . 9 3.3.1 Xvalidity_dates tag . . . . . . . . . . . . . . . . 10 3.3.2 Xcrldp tag . . . . . . . . . . . . . . . . . . . . . 10 3.3.3 Xcp tag . . . . . . . . . . . . . . . . . . . . . . 11 3.3.4 Xaia tag . . . . . . . . . . . . . . . . . . . . . . 11 3.4 Blocks subsection . . . . . . . . . . . . . . . . . . . . 12 4 Certificate Processing Algorithm . . . . . . . . . . . . . . . 13 4.1 Proofreading algorithm . . . . . . . . . . . . . . . . . 14 4.2 TA processing algorithm . . . . . . . . . . . . . . . . . 15 4.2.1 Preparatory processing (stage 0) . . . . . . . . . . 16 Reynolds, et al Expires May 13, 2011 [Page 2] Internet-Draft RPKI Local TA Management November 2010 4.2.2 Target processing (stage 1) . . . . . . . . . . . . 17 4.2.3 Ancestor processing (stage 2) . . . . . . . . . . . 18 4.2.4 Tree processing (stage 3) . . . . . . . . . . . . . 19 4.2.5 TA re-parenting (stage 4) . . . . . . . . . . . . . 20 4.3 Discussion . . . . . . . . . . . . . . . . . . . . . . . 21 5 Implications for Path Discovery . . . . . . . . . . . . . . . 21 5.1 Two answers . . . . . . . . . . . . . . . . . . . . . . . 21 5.2 One answer . . . . . . . . . . . . . . . . . . . . . . . 22 5.3 No answer . . . . . . . . . . . . . . . . . . . . . . . . 22 6 Implications for Revocation . . . . . . . . . . . . . . . . . 22 6.1 No state bits set . . . . . . . . . . . . . . . . . . . . 22 6.2 ORIGINAL state bit set . . . . . . . . . . . . . . . . . 23 6.3 PARA state bit set . . . . . . . . . . . . . . . . . . . 23 6.4 Both ORIGINAL and PARA state bits set . . . . . . . . . . 23 7 Security Considerations . . . . . . . . . . . . . . . . . . . 24 8 IANA Considerations . . . . . . . . . . . . . . . . . . . . . 24 9 Acknowledgements . . . . . . . . . . . . . . . . . . . . . . . 24 10 References . . . . . . . . . . . . . . . . . . . . . . . . . 24 10.1 Normative References . . . . . . . . . . . . . . . . . . 24 10.2 Informative References . . . . . . . . . . . . . . . . . 25 Authors' Addresses . . . . . . . . . . . . . . . . . . . . . . . 25 Appendix A: Sample Constraints File . . . . . . . . . . . . . . . 26 Appendix B: Optional Sorting Algorithm for Ancestor Processing . 27 Reynolds, et al Expires May 13, 2011 [Page 3] Internet-Draft RPKI Local TA Management November 2010 1 Introduction The Resource Public Key Infrastructure (RPKI) [I-D.sidr-arch] is a PKI in which certificates are issued to facilitate management of IP addresses and autonomous system number resources. Such resources are expressed in the form of X.509v3 "resource" certificates with extensions as defined by RFC 3779 [I-D.sidr-res-cert-prof]. Validation of a resource certificate is preceded by path discovery. Path discovery is effected by constructing a certificate path (upward) from a target certificate to a trust anchor. Path validation proceeds from the TA in question to the target certificate, using the public key from each certificate along the path to verify the signature of its subordinate certificate. In the RPKI it is anticipated that one or more putative TAs, aligned with the resource allocation hierarchy, will be available in the form of self-signed certificates configured by an RP. There are circumstances under which an RP may wish to override the resource specifications obtained through the RPKI distributed repository system [I-D.sidr-repos- struct]. This document describes a mechanism by which an RP may override any conflicting information expressed via the putative TAs and the certificates downloaded from the RPKI repository system. To effect this local control, this document calls for a relying party to specify a set of bindings between public key identifiers and resources (IP resources and/or AS number resources) through a text file known as a constraints file. The constraints expressed in this file then take precedence over any competing claims expressed by resource certificates acquired from the distributed repository system. (The means by which a relying party acquires the key identifier and the RFC 3779 extension data used to populate the constraints file is outside the scope of this document.) The relying party also may use a local publication point (the root of a local directory tree that is made available as if it were a remote repository) as a source of certificates and CRLs (and other RPKI signed objects, e.g. ROAs and manifests) that do not appear in the RPKI repository system. In order to allow reuse of existing, standard path validation mechanisms, the RP-imposed constraints are realized by having the RP itself represented as the only TA known in the local certificate validation context. To ensure that all RPKI certificates can be validated relative to this TA, this RP TA certificate must contain all-encompassing resource allocations, i.e. 0/0 for IPv4, 0::/0 for IPv6 and 0-4294967295 for AS numbers. Thus, a conforming implementation of this mechanism must be able to cause a self-signed certification authority (CA) certificate to be created with a locally generated key pair. It also must be able to issue CA certificates subordinate to this TA. Finally, a conforming implementation of this Reynolds, et al Expires May 13, 2011 [Page 4] Internet-Draft RPKI Local TA Management November 2010 mechanism must process the constraints file and modify certificates as needed in order to enforce the constraints asserted in the file. The remainder of this document describes in detail the types of certificate modification that may occur, the semantics of the constraints file, and the implications of certificate modification on path discovery and revocation. 1.1 Terminology It is assumed that the reader is familiar with the terms and concepts described in "Internet X.509 Public Key Infrastructure Certificate and Certificate Revocation List (CRL) Profile" [RFC5280] and "X.509 Extensions for IP Addresses and AS Identifiers" [RFC3779]. The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT", "SHOULD", "SHOULD NOT", "RECOMMENDED", "MAY", and "OPTIONAL" in this document are to be interpreted as described in RFC 2119. 2 Overview of Certificate Processing The fundamental aspect of the facility described in this document is one of certificate modification. The constraints file, described in more detail in the next section, contains assertions about resources that are to be specially processed. As a result of this processing, certificates in the local copy of the RPKI repository are transformed into new certificates satisfying the resource constraints so specified. This enables the RP to override conflicting assertions about resource holdings as acquired from the RPKI repository system. Three forms of certificate modification can occur. 2.1 Target Certificate Processing If a certificate is acquired from the RPKI repository system and it's SKI is listed in the constraints file, it will be reissued directly under the RP TA certificate, with (possibly) modified RFC 3779 extensions. The modified extensions will include any RFC 3779 data expressed in the constraints file. In Section 4.2, target certificate processing corresponds to stage one of the algorithm. 2.2 Perforation Any certificate acquired from the RPKI repository that contains an RFC 3779 extension that intersects the resource data in the constraints file will be reissued directly under the RP TA, with modified RFC 3779 extensions. We refer to the process of modifying the RFC 3779 extension in an affected certificate as "perforation" (because the process will create "holes" in these extensions). The Reynolds, et al Expires May 13, 2011 [Page 5] Internet-Draft RPKI Local TA Management November 2010 modified extensions will exclude any RFC 3779 data expressed in the constraints file. In the certificate processing algorithm described in Section 4.2, perforation corresponds to stage two of the algorithm ("ancestor processing") and also to stage three of the algorithm ("tree processing"). 2.3 TA Re-parenting For consistency, all valid, self-signed certificates that would have been regarded as TAs in the public RPKI certificate hierarchy, e.g. self-signed certificates issued by IANA or the RIRs, will be re- issued under the RP TA certificate. This processing is done even though all but one of these certificates might not intersect any resources specified in the constraints file. We refer to this reissuance as "re-parenting" since the Issuer (parent) of the certificate has been changed. In the certificate processing algorithm described in Section 4.2, TA re-parenting corresponds to stage four of the algorithm. 2.4 Paracertificates If a certificate is subject to any of the three forms of processing just described, that certificate will be referred to as an "original" certificate and the processed (output) certificate will be referred to as a paracertificate. When an original certificate is transformed into a paracertificate all the fields and extensions from the original certificate will be retained, except as indicated in Table 1, below. Reynolds, et al Expires May 13, 2011 [Page 6] Internet-Draft RPKI Local TA Management November 2010 Original Certificate Field Action Version unchanged Serial number created per note A Signature replaced if needed with RP's signing alg Issuer replaced with RP's name Validity dates replaced per note B Subject unchanged Subject public key info unchanged Extensions Subject key identifier unchanged Key usage unchanged Basic constraints unchanged CRL distribution points replaced per note B Certificate policy replaced per note B Authority info access replaced per note B Authority key ident replaced with RP's IP address block modified as described AS number block modified as described Subject info access unchanged All other extensions unchanged Signature Algorithm same as above Signature value new Table 1 Certificate Field Modifications Note A. The serial number will be created by concatenating the current time (the number of seconds since Jan 1, 1970) with a count of the certificates created in the current run. Note B. These fields are derived (as described in section 3.3 below) from parameters in the constraints file (if present); otherwise, they take on values from the certificates from which the paracertificates are derived. Reynolds, et al Expires May 13, 2011 [Page 7] Internet-Draft RPKI Local TA Management November 2010 3 Format of the constraints file This section describes a general model for the syntax of the constraints file. The model described below is nominal; implementations need not match details of this model as presented, but the external behavior of implementations MUST correspond to the externally observable characteristics of this model in order to be compliant. The constraints file consists of four logical subsections: the replying party subsection, the flags subsection, the tags subsection and the blocks subsection. The relying party subsection and the blocks subsection are REQUIRED and MUST be present; the flags and tags subsections are OPTIONAL. Each subsection is described in more detail below. Note that the semicolon (;) character acts as the comment character, to enable annotating constraints files. All characters from a semicolon to the end of that line are ignored. In addition, lines consisting only of whitespace are ignored. The subsections MUST occur in the order indicated. An example constraints file is given in Appendix A. 3.1 Relying party subsection The relying party subsection is a REQUIRED subsection of the constraints file. It MUST be the first subsection of the constraints file, and it MUST consist of two lines of the form: PRIVATEKEYMETHOD value [ ... value ] TOPLEVELCERTIFICATE value The first line provides guidance to the certificate processing algorithm on the method that will be used to gain access to the RP's private key. This line consists of the string literal PRIVATEKEYMETHOD, followed by one or more whitespace delimited string values. These values are passed to the certificate processing algorithm as described below. Note that this entry, as for all entries in the constraints file, is case sensitive. The second line of this subsection consists of the string literal TOPLEVELCERTIFICATE, followed by exactly one string value. This value is the name of a file containing the relying party's TA certificate. The file name is passed to the certificate processing algorithm as described below. 3.2 Flags subsection The flags subsection of the constraints file is an OPTIONAL subsection. If present it MUST immediately follow the relying party Reynolds, et al Expires May 13, 2011 [Page 8] Internet-Draft RPKI Local TA Management November 2010 subsection. The flags subsection consists of one or more lines of the form CONTROL flagname booleanvalue Each such line is referred to as a control line. Each control line MUST contain exactly three whitespace delimited strings. The first string MUST be the literal CONTROL. The second string MUST be one of the following three literals: resource_nounion intersection_always treegrowth The third string denotes a boolean value, and MUST be one of the literals TRUE or FALSE. Control flags influence the global operation of the certificate processing algorithm; the semantics of the flags is described in detail in Section 4.2. Note that each flag has a default value, so that if the corresponding CONTROL line does not appear in the constraints file, the algorithm flag is considered to take the corresponding default value. The default value for each flag is FALSE. Thus, if any flag is not named in a control line it takes the value FALSE. Further, if the flags subsection is absent, all three flags take the value FALSE. 3.3 Tags subsection The tags subsection is an OPTIONAL subsection in the constraints file. If present it MUST immediately follow the relying party subsection (if the flags subsection is absent) or the flags subsection (if it is present). The tags subsection consists of one or more lines of the form TAG tagname tagvalue [ ... tagvalue ] Each such line is referred to as a tag line. Each tag line MUST consist of at least three whitespace delimited string values, the first of which must be the literal TAG. The second string value gives the name of the tag, and subsequent string(s) give the value(s) of the tag. The tag name MUST be one of the following four string literals: Xvalidity_dates Xcrldp Xcp Xaia The purpose of the tag lines is to provide an indication of the means Reynolds, et al Expires May 13, 2011 [Page 9] Internet-Draft RPKI Local TA Management November 2010 by which paracertificate fields, specifically those indicated above under "Note B", are constructed. Each tag has a default, so that if the corresponding tag line is not present in the constraints file, the default behavior is used when constructing the paracertificates. The syntax and semantics of each tag line is described next. Note that the tag lines are considered to be global; the action of each tag line (or the default action, if that tag line is not present) applies to all paracertificates that are created as part of the certificate processing algorithm. 3.3.1 Xvalidity_dates tag This tag line is used to control the value of the notBefore and notAfter fields in paracertificates. If this tag line is specified and there is a single tagvalue which is the literal string C, the paracertificate validity interval is copied from the original certificate validity interval from which it is derived. If this tag is specified and there is a single tagvalue which is the literal string R, the paracertificate validity interval is copied from the validity interval of the relying party's top level (TA) certificate. If this tag is specified and the tagvalue is neither of these literals, then exactly two tagvalues MUST be specified. Each must be a Generalized Time string of the form YYYYMMDDHHMMSSZ. The first tagvalue is assigned to the notBefore field and the second tagvalue is assigned to the notAfter field. It MUST be the case that the tagvalues may be parsed as valid Generalized Time strings such that notBefore is less than notAfter, and also such that notAfter represents a time in the future (i.e., the paracertificate has not already expired). If this tag line is not present in the constraints file the default behavior is to copy the validity interval from the original certificate to the corresponding paracertificate. 3.3.2 Xcrldp tag This tag line is used to control the value of the CRL distribution point extension in paracertificates. If this tag line is specified and there is a single tagvalue that is the string literal C, the CRLDP of the paracertificate is copied from the CRLDP of the original certificate from which it is derived. If this tag line is specified and there is a single tagvalue that is the string literal R, the CRLDP of the paracertificate is copied from the CRLDP of the RP's top level certificate. If this tag line is specified and there is a single tagvalue that is not one of these two reserved literals, or if there is more than one tagvalue, then each tagvalue is interpreted as a URL that will be placed in the CRLDP sequence in the Reynolds, et al Expires May 13, 2011 [Page 10] Internet-Draft RPKI Local TA Management November 2010 paracertificate. If this tag line is not present in the constraints file the default behavior is to copy the CRLDP from the original certificate to the corresponding paracertificate. 3.3.3 Xcp tag This tag line is used to control the value of the policyQualifierId field in paracertificates. If this tag line is specified there MUST be exactly one tagvalue. If the tagvalue is the string literal C, the paracertificate value is copied from the value in the corresponding original certificate. If the tagvalue is the string literal R, the paracertificate value is copied from the value in the RP's top level TA certificate. If the tagvalue is the string literal D, the paracertificate value is set to the default OID. If the tagvalue is not one of these reserved string literals, then the tagvalue MUST be an OID specified using the standard dotted notation. The value in the paracertificate's policyQualifierId field is set to this OID. Note the RFC 5280 specifies that only a single policy may be specified in a certificate, so only a single tagvalue is permitted in this tag line, even though the CertificatePolicy field is an ASN.1 sequence. If this tag line is not specified the default behavior is to use the default OID in creating the paracertificate. This option permits the RP to convert a value of the policyQualifierId field in a certificate (that would not be in conformance with the RPKI CP) to a conforming value in the paracertificate. This conversion enables use of RPKI validation software that checks the policy field against that specified in the RPKI CP [ID.sidr-res-cert-prof]. 3.3.4 Xaia tag This tag line is used to control the value of the Authority Information Access (AIA) extension in the paracertificate. If this tag line is present then it MUST have exactly one tagvalue. If this tagvalue is the string literal C, then the AIA field in the paracertificate is copied from the AIA field in the original certificate from which it is derived. If this tag line is present and the tagvalue is not the reserved string literal, then the tagvalue MUST be a URL. This URL is set as the AIA extension of the paracertificates that are created. If this tag line is not specified the default behavior is to use copy the AIA field from the original certificate to the AIA field of the paracertificate. Reynolds, et al Expires May 13, 2011 [Page 11] Internet-Draft RPKI Local TA Management November 2010 3.4 Blocks subsection The blocks subsection is a REQUIRED subsection of the constraints file. If the tags subsection is present, the blocks subsection MUST appear immediately after it. If the tags subsection is absent, but the flags subsection is present, the block subsection MUST appear immediately after it. Otherwise, the blocks subsection MUST appear immediately after the relying party subsection. The blocks subsection consists of one or more blocks, known as target blocks. A target block is used to specify an association between a certificate (given by a hash of its public key information) and a set of resource assertions. Each target block contains four regions, an SKI region, an IPv4 region, an IPv6 region and an AS number region. All regions are REQUIRED to be present in a target block. The SKI region contains a single line beginning with the string literal SKI and followed by forty hexadecimal characters giving the subject key identifier of a certificate, known as the target certificate. The hex character string MAY contain embedded whitespace or colon characters (included to improve readability), which are ignored. The IPv4 region consists of a line containing only the string literal IPv4. This line is followed by zero or more lines containing IPv4 prefixes in the format described in RFC 3779. The IPv6 region consists of a line containing only the string literal IPv6, followed by zero or more lines containing IPv6 prefixes using the format described in RFC 3513. (The presence of the IPv4 and IPv6 literals is to simplify parsing of the constraints file.) Finally, the AS number region consists of a line containing only the string literal AS#, followed by zero or more lines containing AS numbers (one per line). The AS numbers are specified in decimal notation as recommended in RFC 5396. A target block is terminated by either the end of the constraints file, or by the beginning of the next target block, as signaled by its opening SKI region line. An example target block is shown below. See also the complete constraints file example given in Appendix A. Note that whitespace, as always, is ignored. SKI 00:12:33:44:00:BA:BA:DE:EB:EE:00:99:88:77:66:55:44:33:22:11 IPv4 10.2.3/24 10.8/16 IPv6 1:2:3:4:5:6/112 AS# 123 567 The blocks subsection MUST contain at least one target block. Note that it is OPTIONAL that the SKI refer to a certificate that is known Reynolds, et al Expires May 13, 2011 [Page 12] Internet-Draft RPKI Local TA Management November 2010 or resolvable within the context of the local RPKI repository. Also, there is no REQUIRED or implied ordering of target blocks within the block subsection. As a result of the fact that blocks may occur in any order, it MAY result that the outcome of processing a constraints file depends on the order in which target blocks occur within the constraints file. The next section of this document contains a detailed description of the certificate processing algorithm. 4 Certificate Processing Algorithm The section describes the certificate processing algorithm through which paracertificates are created from original certificates in the local RPKI repository. For the purposes of describing this algorithm, it will be assumed that certificates may be persistently associated with state (or metadata) information. This state information will be further construed as having the form of any array of named bits that are associated with each certificate. No specific implementation of this functionality is mandated by this document. Any implementation that provides the indicated functionality is acceptable, and need not actually consist of a bit field associated with each certificate. The state bits used in certificate processing are NOCHAIN ORIGINAL PARA TARGET If the NOCHAIN bit is set, this indicates that a full path between the given certificate and a TA has not yet been discovered. If the ORIGINAL bit is set, this indicates that the certificate is question has been processed by some part of the processing algorithm described in Section 4.2. If it was processed as part of stage one processing, as described in section 4.2.2, the TARGET bit will also be set. Finally, any paracertificate will have the PARA bit set. At the beginning of algorithm processing each certificate in the local RPKI repository has the ORIGINAL, PARA and TARGET bits clear. If a certificate has a complete, validated path to a TA, or is itself a TA, then that certificate will have the NOCHAIN bit clear, otherwise it will have the NOCHAIN bit set. As the certificate processing algorithm is executed, the bit state of original certificates may changed. In addition, since the certificate processing algorithm may also be creating paracertificates, it is responsible for actively setting or clearing the state of these four bits on those paracertificates. The certificate processing algorithm consists of two sub-algorithms: Reynolds, et al Expires May 13, 2011 [Page 13] Internet-Draft RPKI Local TA Management November 2010 "proofreading" and "TA processing". Conceptually, the proofreading sub-algorithm performs syntactic checks on the constraints file, while the TA processing sub-algorithm performs the actual certificate transformation processing. If the proofreading sub-algorithm does not succeed in parsing the constraints file, the TA processing sub- algorithm is not executed. Note also that if the constraints file is not present, neither sub-algorithm is executed and the local RPKI repository is not modified. Each of the constituent algorithms will now be described in detail. 4.1 Proofreading algorithm The goal of the proofreading algorithm is to check the constraints file for syntactic errors, such as missing REQUIRED subsections, or malformed addresses such as 1.2.300/24. It also performs a set of heuristic checks, such as checking for prefixes that are too large (larger than /8). The proofreading algorithm SHOULD also examine resource regions (IPv4, IPv6 and AS# regions) within the blocks subsection, and reorder such resources within a region in ascending numeric order. On encountering any error the proofreading algorithm SHOULD provide an error message indicating the line on which the error occurred as well as informative text that is sufficiently descriptive as to allow the user to identify and correct the error. An implementation of the proofreading algorithm MUST NOT assume that is has access to the local RPKI repository (even read-only access). An implementation of the proofreading algorithm MUST NOT alter the local RPKI repository in any way; it also MUST NOT change any of the state/metadata information associated with certificates in that repository. (Recall that the processing described here is creating a copy of that local repository.) Finally, the proofreading algorithm MAY produce a transformed output file containing the same syntactic information as in the text version of the constraints file, so long as the format of the transformed file is understood by the TA processing algorithm. The proofreading algorithm performs the following syntactic checks on the constraints file. It checks for the presence of the REQUIRED relying party subsection and the REQUIRED blocks subsection. It checks that the order of the two, three or four subsections is as stated above. It checks that the relying party subsection conforms to the specification given in section 3.1 above. If present, it checks that the tags and flags subsections conform to the specifications in sections 3.2 and 3.3 above. It then checks the blocks subsection. It splits the blocks subsection into constituent target blocks, as delimited by the SKI region line(s), and verifies that at least one target block is present. It verifies that each SKI region line contains exactly forty hexadecimal digits and contains no additional characters other than whitespace or colon characters. For each target Reynolds, et al Expires May 13, 2011 [Page 14] Internet-Draft RPKI Local TA Management November 2010 block, it then verifies the presence of the IPv4, IPv6 and AS# regions, and also verifies that at least one such resource is present. For each IPv4 prefix, IPv6 prefix and autonomous system number given, it checks that the indicated resource is syntactically valid according to the appropriate RFC definition, as described in section 3.4. It also verifies that no IPv4 resource has a prefix larger than /8. The proofreading algorithm SHOULD performing reordering within each of the three resource regions so that stated resource occur in ascending numerical order. If the proofreading algorithm has performed any reordering of information it MAY overwrite the constraints file. If it does so, however, it MUST preserve all information contained within the file, including information that is not parsed (such as comments). If the proofreading algorithm has performed any reordering of information but has not overwritten the constraints file, it MAY produce a transformed output file, as described above. If the proofreading algorithm has performed any reordering of information, but has neither overwritten the constraints file nor produced a transformed output file, it MUST provide an error message to the user indicating what reordering was performed. 4.2 TA processing algorithm The TA processing algorithm acts on the constraints file (or the output file produced by the proofreading algorithm) and the contents of the local RPKI repository to produce paracertificates for the purpose of enforcing the resource allocations as expressed in the constraints file. The TA processing algorithm operates in five stages, a preparatory stage (stage 0), target processing (stage 1), ancestor processing (stage 2), tree processing (state 3) and TA re- parenting (stage 4). Conceptually, during the preparatory stage the constraints (or proofreader output) file is read and a set of internal RP, tag and flag variables are set based on the contents of that file. (If the constraint file has not specified one or more of the tags and/or flags, those tags and flags are set to default values). During target processing all certificates specified by a target block are processed, and the resources for those certificates are (potentially) expanded; for each target found a new paracertificate is manufactured with its various fields set, as shown in Table 1, using the values of the internal variables set in the preparatory stage and also, of course, the fields of the original certificate (and, potentially, fields of the RP's TA certificate). In stage 2 (ancestor) processing, all ancestors of the each target certificate are found, and the claimed resources are then removed (perforated). A new paracertificate with these diminished resources is crafted, with its fields generated based on internal variable settings, original certificate field values, and, potentially, the fields of the RP's TA certificate. In tree processing (stage 3), the Reynolds, et al Expires May 13, 2011 [Page 15] Internet-Draft RPKI Local TA Management November 2010 entire local RPKI repository is searching for any other certificates that have resources that intersect a target resource, and that were not otherwise processed during a preceding stage. Perforation is again performed for any such intersecting certificates, and paracertificates created as in stage 2. Finally, in the fourth and last stage, TA re-parenting, any TA certificates in the local RPKI repository that have not already been processed are now re-parented under the RP's TA certificate. This transformation will create paracertificates; however, these paracertificates may have RFC 3779 resources that were not altered during algorithm processing. The final output of algorithm processing will be threefold. First, the state/metadata information on some (original) certificates in the repository MAY be altered. Second, paracertificates will be created, with the appropriate metadata, and entered into the repository. Finally, the TA processing algorithm SHOULD produce a human readable log of its actions, indicating which paracertificates were created and why. The remainder of this section describes the processing stages of the algorithm in detail. 4.2.1 Preparatory processing (stage 0) During preparatory processing, the constraints file, or the corresponding output file of the proofreader algorithm, is read. Internal variables are set corresponding to each tag and flag, if present, or to their defaults, if absent. Internal variables are also set corresponding to the PRIVATEKEYMETHOD value string(s) and the TOPLEVELCERTIFICATE string. The TA processing algorithm is queried to determine if it supports the indicated private key access methodology. This query is performed in an implementation-specific manner. In particular, an implementation is free to vacuously return success to this query. The TA processing algorithm next uses the value string for the TOPLEVELCERTIFICATE to locate this certificate, again in an implementation=specific manner. The certificate in question may already be present in the local RPKI repository, or it may be located elsewhere. The implementation is also free to create the top level certificate at this time, and then assign to this newly-created certificate the name indicated. It is necessary only that, at the conclusion of this processing, a valid trust anchor certificate for the relying party has been created or otherwise obtained. Some form of access to the RP's private key and top level certificate are required for subsequent correct operation of the algorithm. Therefore, stage 0 processing MUST terminate if one or both conditions are not satisfied. In the error case, the implementation SHOULD provide an error message of sufficient detail that the user can correct the error(s). If stage 0 processing does not succeed, no further stages of TA processing are executed. Reynolds, et al Expires May 13, 2011 [Page 16] Internet-Draft RPKI Local TA Management November 2010 4.2.2 Target processing (stage 1) During target processing, the TA processing algorithm reads all target blocks in the constraints file or corresponding proofreader output file. It then processes each target block in the order specified in the file. In the description that follows, except where noted, the operation of the algorithm on a single target block will be described. Note, however, that all stage 1 processing is executed before any processing in subsequent stages is performed. The algorithm first obtains the SKI region of the target block. It then locates, in an implementation-dependent manner, the certificate the SKI extension field of which contains that value. Note that if paracertificates have been created by virtue of previous target blocks being processed, those paracertificates are not searched in attempting to locate a certificate with a matching SKI; only original certificates are searched. If more than one original certificate is found matching this SKI, there are two possible scenarios. If a resource holder has two certificates issued by the same CA, with overlapping validity intervals and the same key, but distinct subject names (typically, by virtue of the SerialNumber parts being different), then these two certificates are both consider to be (distinct) targets, and are both processed. If, however, a resource holder has certificates issued by two different CAs, containing different resources, but using the same key, there is no unambiguous method to decide which of the certificates is intended as the target. In this latter case the algorithm MUST issue a warning to that effect, mark the target block in question as unavailable for processing by subsequent stages and proceed to the next target block. If no certificate is found then the algorithm SHOULD issue a warning to that effect and proceed to process the next target block. If a single original certificate is found matching the indicated SKI, then the algorithm takes the following actions. First, it sets the ORIGINAL state bit for the certificate found. Second, it sets the TARGET state bit for the certificate found. Third, it extracts the RFC 3779 resources from the certificate. If the global resource_nounion flag is TRUE, it compares the extracted certificate resources with the resources specified in the constraints file. If the two resource sets are different, the algorithm SHOULD issue a warning noting the difference. An output resource set is then formed that is identical to the resource set extracted from the certificate. If, however, the resource_nounion flag is FALSE, then the output resource set is calculated by forming the union of the resources extracted from the certificate and the resources specified for this target block in the constraints file. A paracertificate is then constructed according to Table 1, using fields from the original certificate, the tags that had been set during stage 0, and, if Reynolds, et al Expires May 13, 2011 [Page 17] Internet-Draft RPKI Local TA Management November 2010 necessary, fields from the RP's TA certificate. The RFC 3779 resources of the paracertificate are equated to the derived output resource set. The PARA state bit is set for the newly created paracertificate. 4.2.3 Ancestor processing (stage 2) The goal of ancestor processing is to discover all ancestors of target certificates and remove from those ancestors the resources specified in the target blocks corresponding to the targets being processed. Note that it is possible that, for a given chain from a target certificate to a trust anchor, another target might be encountered. This is handled by removing all the target resources of all descendents. The set of all targets that are descendants of the given certificate is formed. The union of all the target resources of the corresponding target blocks is computed, and this union in then removed from the shared ancestor. In detail, the algorithm is as follows. First, all original target certificates processed during stage 1 processing are collected. Second, any such certificates that have the NOCHAIN state bit set are eliminated from the collection. (Note that, as a result of eliminating such certificates, the resulting collection may be empty, in which case this stage of algorithm processing terminates, and processing advances to stage 3.) Next, an implementation MAY sort the collection. The optional sorting algorithm is described in Appendix B. Note that all stage 2 processing is completed before any stage 3 processing. Two levels of nested iteration are performed. The outer iteration is effected over all certificates in the collection; the inner iteration is over all ancestors of the designated certificate being processed. The first certificate in the collection is chosen, and a resource set R is initialized based on the resources of the target block for that certificate (since the certificate is in collection, it must be a target certificate, and thus correspond to a target block). The parent of the certificate is then located using ordinary path discovery over original certificates only. The ancestor's certificate resources A are then extracted. These resources are then perforated with respect to R. That is, an output set of resources is created by forming the intersection I of A and R, and then taking the set difference A - I as the output resources. A paracertificate is then created containing resources tat are these output resources, and containing other fields and extensions from the original certificate (and possibly the RP's TA certificate) according to the procedure given in Table 1. The PARA state bit is set on this paracertificate and the ORIGINAL state bit is set on A. If A is also a target certificate, as indicated by its TARGET state bit being set, then Reynolds, et al Expires May 13, 2011 [Page 18] Internet-Draft RPKI Local TA Management November 2010 there will already have been a paracertificate created for it. This previous paracertificate is destroyed in favor of the newly created paracertificate. In this case also, the set R is augmented by adding into it the set of resources of the target block for A. The algorithm then proceeds to process the parent of A. This inner iteration continues until the self-signed certificate at the root of the path is encountered and processed. The outer iteration then continues by clearing R and proceeding to the next certificate in the target collection. Note that ancestor processing has the potential for order dependency as mentioned earlier in this document. If sorting is not implemented, or if the sorting algorithm fails to completely process the collection of target certificates because the allotted maximum number of iterations has been realized, it may be the case that an ancestor of a certificate logically occurs before that certificate in the collection. Whenever an existing paracertificate is replaced by a newly created paracertificate during ancestor processing, the algorithm SHOULD alert the user, and SHOULD log sufficient detail such that the user is able to determine which resources were perforated from the original certificate in order to create the (new) paracertificate. In addition, implementations MUST provide for conflict detection and notification during ancestor processing. In particular, if a certificate is encountered two or more times during any part of the ancestor processing algorithm, and the modifications dictated by the ancestor processing algorithm are in conflict, the implementation MUST refrain from processing that certificate. Further, the implementation MUST present the user with an error message that contains enough detail that the user can locate those directives in the constraints file that are creating the conflict. For example, during one stage of the processing algorithm it may be directed that resources R1 be added to a certificate C, while during a different stage of the processing algorithm it may be directed that resources R2 be removed from certificate C. If the resource sets R1 and R2 have a non-empty intersection, that is a conflict. 4.2.4 Tree processing (stage 3) The goal of tree processing is to locate other certificates the resources of which might conflict with the resources allocated to a target by virtue of their being mentioned in the constraints file. In this stage of processing, certificates that are not ancestors of any target are considered. In detail, the algorithm used is as follows. First, all target certificates are again collected. Second, all target certificates that have the NOCHAIN state bit set are eliminated from this collection. Third, if the intersection_always Reynolds, et al Expires May 13, 2011 [Page 19] Internet-Draft RPKI Local TA Management November 2010 global flag is set, those target blocks that occur in the constraints file, but that did not correspond to a certificate in the local repository, are also added to the collection. In tree processing, unlike ancestor processing, this collection is not sorted. An iteration is now performed over each certificate (or set of target block resources) in the collection. Note that the collection may be empty, in which case this stage of algorithm processing terminates, and processing advances to stage 4. Note also that all stage 3 processing is performed before any stage 4 processing. Given a certificate or target resource block, each top level original TA certificate is examined. If that TA certificate has an intersection with the target block resources, then the certificate is perforated with respect to those resources. A paracertificate is created based on the contents of the original certificate (and possibly the RP's TA certificate, as indicated in Table 1) using the perforated resources. The ORIGINAL state bit is set on the original certificate processed in this manner, and the PARA state bit is set on the paracertificate just created. An inner iteration then begins on the descendants of the original certificate just processed. There are two ways in which this iteration may proceed. If the treegrowth global flag is clear, then examination of the children proceeds until all children are exhausted, or until one child is found with intersecting resources. If the treegrowth global flag is set, all children are examined. Since a transfer of resources may be in process such that more than one child possesses intersecting resources, it is RECOMMENDED that the treegrowth flag be set. The inner iteration proceeds until all descendants have been examined and no further intersecting resources are found. The outer iteration then continues with the next certificate or target resource block in the collection. Note that unlike ancestor processing, there is no concept of a potentially cumulating resource collection R; only the resources in the target block are used for perforation. 4.2.5 TA re-parenting (stage 4) In the final stage of TA algorithm processing, all TA certificates (other than the RP's TA certificate) that have not already been processed in a previous stage are now processed. It will be the case that all such unprocessed TA certificates have no intersection with any target resource blocks. As such, in creating the corresponding paracertificates, the output resource set is identical to the input resource set. Other transformations as described in Table 1 are performed. The original TA certificates have the ORIGINAL state bit set; the newly created paracertificates have the PARA state bit set. Note that once stage four processing is completely, only a single TA certificate will remain in an unprocessed state, namely the relying party's own TA certificate. Reynolds, et al Expires May 13, 2011 [Page 20] Internet-Draft RPKI Local TA Management November 2010 4.3 Discussion The algorithm described in this document effectively creates two coexisting certificate hierarchies: the original certificate hierarchy and the paracertificate hierarchy. Note that original certificates are not removed during any of the processing described in the previous section. Some original certificates may move from having no state bits set (or only the NOCHAIN state bit set) to having one or both of the ORIGINAL and TARGET state bits set. In addition, the NOCHAIN state bit will still be set if it was set before any processing. The paracertificate hierarchy, however, is intended to supersede the original hierarchy for the purposes of ROA validation. The presence of two hierarchies has implications for the handling of path discovery, and also for the handling of revocation. If one thinks of a certificate as being "named" by its SKI, then there can now be two certificates with the same name, one an original certificate and the other a paracertificate. The next two sections discuss the implications of this duality in detail. Before proceeding, it is worth noting that even without the existence of the paracertificate hierarchy, cases may exist in which two or more original certificates have the same SKI. As noted earlier, in Section 4.2.2, these cases may be subdivided into the case in which such certificates are distinguishable by virtue of having different subject names, but identical issuers and resource sets, versus all other cases. In the distinguishable case, the path discovery algorithm treats the original certificates as separate certificates, and processes them separately. In all other cases, the original certificates should be treated as indistinguishable, and path validation should fail. 5 Implications for Path Discovery Path discovery proceeds from a child certificate C by asking for a parent certificate P such that the AKI of C is equal to the SKI of P. With one hierarchy this question would produce at most one answer. With two hierarchies, the original certificate hierarchy and the paracertificate hierarchy, the question may produce two answers, one answer, or no answer. Each of these cases is considered in turn. 5.1 Two answers In this case, it SHOULD be the case that one of the matches is a certificate with the ORIGINAL state bit set and the PARA state bit clear, while the other match inversely has the ORIGINAL state bit clear and the PARA state bit set. If any other combination of ORIGINAL and PARA state bits obtains, the path discovery algorithm MUST alert the user. In addition, the path discovery algorithm SHOULD refrain from attempting to make a choice as to which of the two Reynolds, et al Expires May 13, 2011 [Page 21] Internet-Draft RPKI Local TA Management November 2010 certificates is the putative parent. In the no-error case, with the state bits are as indicated, the certificate with the PARA state bit set is chosen as the parent P. Note this means, in effect, that all children of the original certificate have been re-parented under the paracertificate. 5.2 One answer If the matching certificate has neither the ORIGINAL state bit set nor the PARA state bit set, this certificate is the parent. If the matching certificate has the PARA state bit set but the ORIGINAL state bit not set, this certificate is the parent. (This situation would arise, for example, if the original certificate had been revoked by its issuer but the paracertificate had not been revoked by the RP.) If the matching certificate has the ORIGINAL state bit set but the PARA state bit not set, this is not an error but it is a situation in which path discovery MUST be forced to fail. The parent P MUST be set to NULL, and the NOCHAIN state bit must be set on C and all its descendants; the user SHOULD be warned. Even if the RP has revoked the paracertificate, the original certificate MAY persist. Forcing path discovery to unsuccessfully terminate is a reflection of the RP's preference for path discovery to fail as opposed to using the original hierarchy. Finally, if the matching certificate has both the ORIGINAL and PARA state bits set, this is an error. The parent P MUST be set to NULL, and the user MUST be warned. 5.3 No answer This situation occurs when C has no parent in either the original hierarchy or the paracertificate hierarchy. In this case the parent P is NULL and path discovery terminates unsuccessfully. The NOCHAIN state bit must be set on C and all its descendants. 6 Implications for Revocation In a standard implementation of revocation in a PKI, a valid CRL names a (sibling) certificate by serial number. That certificate is revoked and is purged from the local RPKI repository. In the mechanism described in this document, the original certificate hierarchy and the paracertificate hierarchy are closely related. It can thus be asked how revocation is handled in the presence of these two hierarchies, in particular with regard to whether changes in one of the hierarchies triggers corresponding changes in the other hierarchy. There are four cases. 6.1 No state bits set If the CRL names a certificate that has neither the ORIGINAL state Reynolds, et al Expires May 13, 2011 [Page 22] Internet-Draft RPKI Local TA Management November 2010 bit set nor the PARA state bit set, revocation proceeds normally. All children of the revoked certificate have their state modified so that the NOCHAIN state bit is set. 6.2 ORIGINAL state bit set If the CRL names a certificate with the ORIGINAL state bit set and the PARA state bit clear, then this certificate is revoked as usual. If this original certificate also has the TARGET state bit set, then the corresponding paracertificate (if it exists) is not revoked; if this original certificate has the TARGET state bit clear, then the corresponding paracertificate is revoked as well. Note that since all the children of the original certificate have been re-parented to be children of the corresponding paracertificate, as described above, the revocation algorithm MUST NOT set the NOCHAIN state bit on these children unless the paracertificate is also revoked. Note also that if the original certificate is revoked but the paracertificate is not revoked, the paracertificate retains its PARA state bit. This is to ensure that path discovery proceeds preferentially through the paracertificate hierarchy, as described above. 6.3 PARA state bit set If the CRL names a certificate with the PARA state bit set and the ORIGINAL state bit clear, this CRL must have been issued, perforce, by the RP itself. This is because all the paracertificates are children of the RP's TA certificate. (Recall that a TA is not revoked via a CRL; it is merely removed from the repository.) The paracertificate is revoked and all children of the paracertificate have the NOCHAIN state bit set. No action is taken on the corresponding original certificate; in particular, its ORIGINAL state bit is not cleared. Note that the serial numbers of paracertificates are synthesized according to the procedure given in Table 1, rather than being assigned by an algorithm under the control of the (original) issuer. 6.4 Both ORIGINAL and PARA state bits set This is an error. The revocation algorithm MUST alert the user and take no further action. Reynolds, et al Expires May 13, 2011 [Page 23] Internet-Draft RPKI Local TA Management November 2010 7 Security Considerations The goal of the algorithm described in this document is to enable an RP to impose its own constraints on its view of the RPKI, which itself is a security function. An RP using a constraints file is trusting the assertions made in that file. Errors in the constraints file used by an RP can undermine the security offered by the RPKI, to that RP. In particular, since the paracertificate hierarchy is intended to trump the original certificate hierarchy for the purposes of path discovery, an improperly constructed paracertificate hierarchy could validate origin attestations that would otherwise be invalid, or could declare as invalid origin attestations that would otherwise be valid. As a result, an RP must carefully consider the security implications of the constraints file being used. 8 IANA Considerations [Note to IANA, to be removed prior to publication: there are no IANA considerations stated in this version of the document.] 9 Acknowledgements The authors would like to acknowledge the significant contributions of Charles Gardiner, who was the original author of an internal version of this document, and who contributed significantly to its evolution into the current version. 10 References 10.1 Normative References [RFC2119] Bradner, S., "Key words for use in RFCs to Indicate Requirement Levels", BCP 14, RFC 2119, March 1997. [RFC3513] Hinden, R., and S. Deering, "Internet Protocol Version 6 (IPv6) Addressing Architecture", RFC 3513, April 2003. [RFC3779] Lynn, C., Kent, S., and K. Seo, "X.509 Extensions for IP Addresses and AS Identifiers", RFC 3779, June 2004. [RFC5280] Cooper, D., Santesson, S., Farrell, S., Boeyen, S., Housley, R., and W. Polk, "Internet X.509 Public Key Infrastructure Certificate and Certificate Revocation List (CRL) Profile", RFC 5280, May 2008. [RFC5396] Huston, G., and G. Michaelson, "Textual Representation of Autonomous System (AS) Numbers", RFC 5396, December 2008. Reynolds, et al Expires May 13, 2011 [Page 24] Internet-Draft RPKI Local TA Management November 2010 [I-D. sidr-arch] Lepinski, M. and S. Kent, "An Infrastructure to Support Secure Internet Routing", draft-ietf-sidr-arch-11.txt (work in progress), September 2010. [I-D. sidr-repos-struct] Huston, G., Loomans, R., and G. Michaelson, "A Profile for Resource Certificate Policy Structure", draft-ietf- sidr-repos-struct-05.txt (work in progress), October 2010. [I-D. sidr-res-cert-prof] Huston, G., Michaelson, G., and R. Loomans, "A Profile for X.509 PKIX Resource Certificates", draft-ietf-sidr- res-certs-19.txt (work in progress), October 2010. 10.2 Informative References None. Authors' Addresses Stephen Kent BBN Technologies 10 Moulton St. Cambridge, MA 02138 Email: kent@bbn.com Mark Reynolds BBN Technologies 10 Moulton St. Cambridge, MA 02138 Email: mreynold@bbn.com Reynolds, et al Expires May 13, 2011 [Page 25] Internet-Draft RPKI Local TA Management November 2010 Appendix A: Sample Constraints File ; ; Sample constraints file for TBO LTA Test Corporation. ; ; TBO manages its own local (10.x.x.x) address space ; via the target blocks in this file. ; ; ; Relying party subsection. TBO uses ssh-agent as ; a software cryptographic agent. ; PRIVATEKEYMETHOD OBO(ssh-agent) TOPLEVELCERTIFICATE tbomaster.cer ; ; Flags subsection ; ; Always use the resources in this file to augment ; certificate resources. ; Always process resource conflicts in the tree, even ; if the target certificate is missing. ; Always search the entire tree. ; CONTROL resource_nounion FALSE CONTROL intersection_always TRUE CONTROL treegrowth TRUE ; ; Tags subsection ; ; Copy the original cert's validity dates. ; Use the default policy OID. ; Use our own CRLDP. ; Use our own AIA. ; TAG Xvalidity_dates C TAG Xcp D TAG Xcrldp rsync://tbo_lta_test.com/pub/CRLs TAG Xaia rsync://tbo_lta_test.com/pub/repos ; ; Block subsection Reynolds, et al Expires May 13, 2011 [Page 26] Internet-Draft RPKI Local TA Management November 2010 ; ; ; First block: TBO corporate ; SKI 00112233445566778899998877665544332211 IPv4 10.2.3/24 10.8/16 IPv6 2000:2:3:4:5:6/112 AS# 60123 5507 ; ; Second block: TBO LTA Test enforcement division ; SKI 653420AF758421CF600029FF857422AA6833299F IPv4 10.2.8/24 10.47/16 IPv6 AS# 60124 ; ; Third block: TBO LTA Test Acceptance Corporation ; Quality financial services since sometime ; late yesterday. ; SKI 19:82:34:90:8b:a0:9c:ef:00:af:a0:98:23:09:82:4b:ef:ab:98:09 IPv4 10.3.3/24 IPv6 AS# 60125 ; End of TBO constraints file Appendix B: Optional Sorting Algorithm for Ancestor Processing Sorting is performed in an effort to eliminate any order dependencies in ancestor processing, as described in section 4.2.3 of this Reynolds, et al Expires May 13, 2011 [Page 27] Internet-Draft RPKI Local TA Management November 2010 document. The sorting algorithm does this by rearranging the processing of certificates such that if A is an ancestor of B, B is processed before A. The sorting algorithm is an OPTIONAL part of ancestor processing. Sorting proceeds as follows. The collection created at the beginning of ancestor processing is traversed and any certificate in the collection that is visited as a result of path discovery is temporarily marked. After the traversal, all unmarked certificates are moved to the beginning of the collection. The remaining marked certificates are unmarked, and a traversal again performed through this sub-collection of previously marked certificates. The sorting algorithm proceeds iteratively until all certificates have been sorted or until a predetermined fixed number of iterations has been performed. (Eight is suggested as a munificent value for the upper bound, since the number of sorting steps need should be no greater than the maximum depth of the tree). Finally, the ancestor processing algorithm is applied in turn to each certificate in the remaining sorted collection. If the sorting algorithm fails to converge, that is if the maximum number of iterations has been reached and unsorted certificates remain, the implementation SHOULD warn the user. Reynolds, et al Expires May 13, 2011 [Page 28]