Certificate Path Validation in Bridge CA and Cross-Certification Environments

Recently, we’ve had a deluge of questions regarding chain building and selection, especially in the presence of cross-certified certificates. Hopefully, this post will make Crypto API 2 (CAPI2) chaining logic clearer and help enterprise admins design and troubleshoot their public key infrastructure.
 
While trying to validate an end entity, CAPI2 tries to select the best quality chain leading up to a certificate that the user trusts. Where multiple valid chains exist, this may not be the shortest chain found. It is also possible that CAPI2 could not construct complete chains – this can happen when intermediate CAs are not available on the client, and the client could not retrieve the certificates (due to server issues, proxy authentication failures, insufficient rights to access the network, and other issues).
 
Consider the following chain: the Contoso Root CA has issued an intermediate CA, Contoso InterCA, which in turn issues a signing cert to Bob. Now, another root CA, Super Root has issued an intermediate CA called Bridge CA, which cross certifies the Contoso Root CA.

Contoso Root CA ->
             Contoso InterCA ->
                                     Bob

Bridge CA cross certifies Contoso Root CA, resulting in

Super Root ->
             Bridge CA ->
                    X-Cert Contoso Root CA->
                                           Contoso InterCA ->
                                                                   Bob

There are two possible valid chains here – the original chain Contoso Root CA -> Contoso InterCA -> Bob, and the cross certified chain Super Root -> Bridge CA -> X-Cert Contoso Root CA -> Contoso InterCA -> Bob. Which chain will CAPI2 return? This isn’t as simple as returning the shortest chain. It is also affected by certificate discovery – can the client access all certificates in the chain?

Consider the simple case, in which the client has all certificates available. This means that it either performed a network retrieval to get the certificates, or they were already installed into the relevant certificate stores, or were available in the cache. Since the client now has two valid chains, CAPI2 need to select and return the “best” chain. Simply returning the shortest chain isn’t an option – the longer chain can be a “better” chain. The process of selecting a chain can be explained as follows.
 
CAPI2 starts by calculating the “quality” of each chain. The quality of the chain is derived from a number of factors, including:
         1. Certificate signatures are valid
         2. Certificate chain ends at a trusted root
         3. Chain has valid basic constraints
         4. Successful revocation check / not revoked
         5. Chain has name constraint policies
         6. Chain has certificate policies
         7. Chain has extended key usages
         8. Chain has SubjectKeyIdentifier / AuthorityKeyIdentifier match

In a nutshell, if a chain provides more information (i.e. valid policy constraints, revocation check succeeded) its quality increases; conversely, if it encounters errors (certificate is revoked / revocation status unknown, invalid name constraints) its quality decreases.
 
If there are multiple chains with the same quality score, CAPI2 uses the following tie breakers:
         1. Starting with the certificate of the end entity’s issuer on both chains, compare the NotBefore dates and NotAfter dates of certificates in the same position in the chain. The first chain with a later NotBefore date, or if the NotBefore dates are identical, the chain with the later NotAfter date is selected.
         2. If both chains have identical validity periods, then the shorter chain is selected.

When there are multiple valid chains possible, the above heuristics are used only when CAPI2 can successfully build the various valid chains. However, due to various issues during path discovery, CAPI2 may not even be able to build a certificate chain up to a particular root. For example, if the intermediate certificates or cross-certificates cannot be discovered, CAPI2 may only completely build one of the two valid chains in the example above. There are however some general guidelines which are recommended for a majority of PKI scenarios commonly encountered in the enterprise.

In order to facilitate a successful path discovery, you should use group policies to deploy cross-certificates and intermediate CA certificates in your environment. This would eliminate the need to perform network retrievals during path discovery (and potentially result in performance improvements).
 
Selection of particular chains can be forced by correct management of trusted roots and certificate policies. If you want a chain up to a particular root be always picked, you need to make sure that is the only trusted valid chain that can be built and remove the ambiguity. In the example above, if you want the chain up to the Contoso Root to be built, then it needs to be only valid chain possible.  If Super Root is distributed through automatic root update service, then you can either disable the Auto Root Update program in clients and push the selected third party roots via Group Policy, or place Super Root in the “Untrusted Certificates” store.
 
What if you can’t do either, because Super Root is required to be trusted for a different application? That’s where policy and name constraints come into play. By specifying these on the CA certificates, you can provide additional context for the chain validation client, thereby making a stronger case to restrict to a particular chain (assuming, of course, the constraints are valid throughout the chain). In our example, this could mean specifying a nameConstraint on the Contoso Root CA, which is satisfied by all certificates in the chain. The additional context provided by the shorter chain would cause CAPI2 to return the more restrictive chain.

-----

Siddarth Adukia
Windows Core Security Team