Certification path validation algorithm
Encyclopedia
The certification path validation algorithm is the algorithm
which verifies that a given certificate path is valid under a given public key infrastructure
(PKI). A path starts with the Subject certificate and proceeds through a number of intermediate certificates up to a trusted root certificate
, typically issued by a trusted Certification Authority (CA).
Path validation is necessary for a relying party to make an informed trust decision when presented with any certificate that is not already explicitly trusted. For example, in a hierarchical PKI, a certificate chain starting with a web server certificate might lead to a small CA, then to an intermediate CA, then to a large CA whose trust anchor is present in the relying party's web browser. In a bridged PKI, a certificate chain starting with a user at Company A might lead to Company A's CA certificate, then to a bridge CA, then to company B's CA certificate, then to company B's trust anchor, which a relying party at company B could trust.
RFC 3280 defines a standardized path validation algorithm for X.509
certificates, given a certificate path. (Path discovery, the actual construction of a path, is not covered.) The algorithm takes the following inputs:
In the standardized algorithm, the following steps are performed for each certificate in the path, starting from the trust anchor. If any check fails on any certificate, the algorithm terminates and path validation fails. (This is an explanatory summary of the scope of the algorithm, not a rigorous reproduction of the detailed steps.)
If this procedure reaches the last certificate in the chain, with no name constraint or policy violations or any other error condition, then the certificate path validation algorithm terminates successfully.
Algorithm
In mathematics and computer science, an algorithm is an effective method expressed as a finite list of well-defined instructions for calculating a function. Algorithms are used for calculation, data processing, and automated reasoning...
which verifies that a given certificate path is valid under a given public key infrastructure
Public key infrastructure
Public Key Infrastructure is a set of hardware, software, people, policies, and procedures needed to create, manage, distribute, use, store, and revoke digital certificates. In cryptography, a PKI is an arrangement that binds public keys with respective user identities by means of a certificate...
(PKI). A path starts with the Subject certificate and proceeds through a number of intermediate certificates up to a trusted root certificate
Root certificate
In cryptography and computer security, a root certificate is either an unsigned public key certificate or a self-signed certificate that identifies the Root Certificate Authority . A root certificate is part of a public key infrastructure scheme...
, typically issued by a trusted Certification Authority (CA).
Path validation is necessary for a relying party to make an informed trust decision when presented with any certificate that is not already explicitly trusted. For example, in a hierarchical PKI, a certificate chain starting with a web server certificate might lead to a small CA, then to an intermediate CA, then to a large CA whose trust anchor is present in the relying party's web browser. In a bridged PKI, a certificate chain starting with a user at Company A might lead to Company A's CA certificate, then to a bridge CA, then to company B's CA certificate, then to company B's trust anchor, which a relying party at company B could trust.
RFC 3280 defines a standardized path validation algorithm for X.509
X.509
In cryptography, X.509 is an ITU-T standard for a public key infrastructure and Privilege Management Infrastructure . X.509 specifies, amongst other things, standard formats for public key certificates, certificate revocation lists, attribute certificates, and a certification path validation...
certificates, given a certificate path. (Path discovery, the actual construction of a path, is not covered.) The algorithm takes the following inputs:
- The certificate path to be evaluated;
- The current date/time;
- The list of Certificate PolicyCertificate policyA certificate policy is a document which aims to state what are the different actors of a public key infrastructure , their roles and their duties. This document is published in the PKI perimeter....
OIDsObject identifierIn computing, an object identifier or OID is an identifier used to name an object . Structurally, an OID consists of a node in a hierarchically-assigned namespace, formally defined using the ITU-T's ASN.1 standard. Successive numbers of the nodes, starting at the root of the tree, identify each...
acceptable to the relying party (or any); - The trust anchor of the certificate path; and
- Indicators whether policy mapping is allowed and how/when/whether the "any" policy OIDObject identifierIn computing, an object identifier or OID is an identifier used to name an object . Structurally, an OID consists of a node in a hierarchically-assigned namespace, formally defined using the ITU-T's ASN.1 standard. Successive numbers of the nodes, starting at the root of the tree, identify each...
is to be tolerated.
In the standardized algorithm, the following steps are performed for each certificate in the path, starting from the trust anchor. If any check fails on any certificate, the algorithm terminates and path validation fails. (This is an explanatory summary of the scope of the algorithm, not a rigorous reproduction of the detailed steps.)
- The public key algorithm and parameters are checked;
- The current date/time is checked against the validity period of the certificate;
- The revocation status is checked, whether by CRLCertificate revocation listIn the operation of some cryptosystems, usually public key infrastructures , a certificate revocation list is a list of certificates that have been revoked, and therefore should not be relied upon.-Revocation States:There are two different states of revocation defined in RFC 3280:* Revoked: A...
, OCSPOnline Certificate Status ProtocolThe Online Certificate Status Protocol is an Internet protocol used for obtaining the revocation status of an X.509 digital certificate. It is described in RFC 2560 and is on the Internet standards track...
, or some other mechanism, to ensure the certificate is not revoked; - The issuer name is checked to ensure that it equals the subject name of the previous certificate in the path;
- Name constraints are checked, to make sure the subject name is within the permitted subtrees list of all previous CA certificates and not within the excluded subtrees list of any previous CA certificate;
- The asserted Certificate PolicyCertificate policyA certificate policy is a document which aims to state what are the different actors of a public key infrastructure , their roles and their duties. This document is published in the PKI perimeter....
OIDsObject identifierIn computing, an object identifier or OID is an identifier used to name an object . Structurally, an OID consists of a node in a hierarchically-assigned namespace, formally defined using the ITU-T's ASN.1 standard. Successive numbers of the nodes, starting at the root of the tree, identify each...
are checked against the permissible OIDs as of the previous certificate, including any policy mapping equivalencies asserted by the previous certificate; - Policy constraints and basic constraints are checked, to ensure that any explicit policy requirements are not violated and that the certificate is a CA certificate, respectively. This step is crucial in preventing some man in the middle attacks ;
- The path length is checked to ensure that it does not exceed any maximum path length asserted in this or a previous certificate;
- The key usage extension is checked to ensure that is allowed to sign certificates; and
- Any other critical extensions are recognized and processed.
If this procedure reaches the last certificate in the chain, with no name constraint or policy violations or any other error condition, then the certificate path validation algorithm terminates successfully.
Implementations
- Pathfinder is an open-source implementation of the algorithm in RFC 3280.