Various crypto libraries have various ways to represent and store information about which Certificate Authorities are to be used as trust anchors. They also have different ways to represent certificates that are blacklisted.
This has led to a poor experience and a lack of coherency on Linux when it comes to validating certificates.
In this document we examine a general purpose method for storing anchor certificates, and representing policy about them. We also look at blacklists and their peculiarities. We see how we can represent these in a coherent and future-proof manner. In addition to being extensible, the proposed concept is relatively easy to implement and retrofit into existing code.
By using consistent anchors and other trust information, crypto libraries can make consistent decisions about X.509 certificates.
We are dealing here with the anchors and other trust policy information used by a key or certificate validation algorithm. The algorithm itself lives inside of a crypto library implementation. This trust policy information can be viewed as input to the certificate validation algorithms. We are not dealing with the validation algorithms themselves. These are dealt in sufficient detail in the relevant RFCs . While in theory it could be nice to have all implementations share common code for verification of certificates, imagining such an effort is outside the scope of this document. This document does not conflict with such a theoretical effort.
This document attempts to represent basic local trust policy information for X.509 certificate validation. It does not attempt to tackle the theoretical problem of representing all possible forms of digital trust. There are many possible flags, profiles and inputs to certificate validation which are not represented. Instead this is a common base of information to share, which augmented by other application specific information.
This document currently limits itself to treatment of anchors and blacklisted certificates. Later companion documents will deal with pinned keys and shared state/storage needed by alternative trust validation implementations.
Since the words used with these topics are often heavily overloaded and some concepts are discussed here.
A word on terminology. The word trust is used quite a bit in this document. This is a highly overloaded and subjective term, and its use in this specification is unfortunate. An unambiguous term is desirable. The author cringes every time the word trust is used. The author cringed a lot while writing this document.
X.509 is structured around the concept of having a chain of certificates, each of which is signed and therefore trusted by the previous certificate in the chain: a certificate authority. These chains are built by crypto libraries when validating certificates. They are built in various ways, several of which are outlined in RFC 5280.
At one end of a certificate chain is the end entity certificate, which is the certificate that is being validated. At the other end the certificate chain is anchored by a trust anchor. This is a public key that is explicitly trusted by the local system, either by default or by a deliberate configuration choice. Usually this public key is represented as a certificate. The anchor is usually, but not always, a root self-signed certificate authority.
Anchors can have trust policy  attached to them which define the situations they can be used as anchors. This policy takes on many forms. A given anchor might be only be relevant when verifying an end entity certificate used for email. Another anchor might be relevant only for an end entity certificate that has a Common Name under a certain domain. There are many such policies and combinations of them.
When the anchor public key is represented by a certificate, this trust policy is often included in the certificate itself. This is done by use of X.509 certificate extensions. The email anchor above would have an ExtendedKeyUsage  certificate extension included in it. The second anchor above would have a NameConstraints  certificate extension included in it.
But it very often occurs that the trust policy included with the anchor is not present or is not enough. System builders, administrators, and others wish to override or adjust the trust policy for a given certificate authority especially when used as an anchor. This overridden out-of-band trust policy is not included in the anchor itself.
On Linux there has been no standard way to represent this additional trust policy. Various crypto libraries have various of representing this out-of-band trust policy, as examined elsewhere. This document wishes to define such a standard.
X.509 certificate extensions usually define the ways that a certificate can be used to represent trust policy. Usually these certificate extensions are internal to the certificate, and are signed by the issuer of the certificate.
By associating additional certificate extensions to a public key or X.509 certificate we can represent out-of-band trust policy, as defined by a system builder, administrator or user.
We will refer to these additional extensions as Attached Extensions.
When both standard X.509 certificate extensions and attached extensions are present, the attached extension is to be used instead of the certificate extension with the same OID in the certificate itself. In this way attached certificate extensions override policy defined in the certificate, if any.
This has the implication that if only one portion of a certificate extension needs to be adjusted by a attached certificate extension, that entire extension will be overridden for that certificate. This is intentional. Each extension that contains trust policy should be treated as a whole unit of trust policy. This includes changing the critical field of an extension. This is part of the whole.
For each certificate, there may not be more than one attached certificate extension of a given identifier or type. There is no way to automatically merge certificate extensions. It may be possible for applications which store attached certificate extensions (such as a management interface) to merge certain extensions in some way. However that is out of the scope of this document.
Attached certificate extensions are associated with the subject public key info of the anchor or certificate.
A blacklisted key or certificate is one that should be rejected outright when it is encountered in a validation algorithm.
As designed, when an X.509 certificate is compromised, either through malice or accident, it is supposed to be revoked. Verification algorithms check against lists of revoked certificates published by certificate authorities in standard ways.
When an anchor certificate is revoked, or revocation needs to take place independent of the certificate authority, such a certificate is added to a blacklist. This is a separate mechanism from the certificate revocation lists outlined in X.509.
Blacklists are distributed by system builders or administrators. They are used as a supplement to retrieved revocation lists, and dynamic protocols such as OCSP and OCSP Stapling.
On Linux there has been no standard way to represent blacklists. Various crypto libraries have various means of representing them, and we examine them elsewhere. This document wishes to define a such a standard.
Over the years there have been many ways that anchors and blacklists have been represented. It is clear that none of the examined representations serve to comprehensively model the necessary trust information.
Here we discuss a stored model which can be used to store, lookup, and share (between implementations) anchors and blacklists. The model is generic in nature and defines the characteristics that actual APIs and formats should have.
Actual APIs for accessing this model are defined in companion documents.
In its general form the store has the following characteristics. It is a subset of the behavior and characteritsics used by many other object stores or relational models.
The store contains various data sets used for various various purposes.
Each set contains multiple items.
Each item has fields. Fields have an identifier, and contain byte data as their value.
Certain fields are used to lookup items in a set. These lookup fields are not necessarily unique among all items in a set. Multiple items may match a given lookup field value.
Certain fields are optional, and may be missing from an item.
A lookup operation takes as input: the set, the lookup fields/values, and the identifiers of the fields to return.
The returned values and fields are returned for all items matching the lookup fields.
No particular order is defined for the returned items.
It is possible to do a lookup without specifying any fields to return, merely to check if matching items are in the set.
It is not an error for a lookup operation to return no items.
A remove operation takes as input: the set, and the lookup fields/values.
All items matching the input are removed from the set.
The remove operation is not supported by read-only sets.
It is not an error for a remove operation to remove no items.
A store operation takes as input: the set, and the fields/values to store.
If an item matching all the fields/values already exists in the set, then the item is not added, although this is not an error.
The store operation is not supported by read-only sets.
Implementations of the store may have additional capabilities, but must implement the above characteristics and behavior.
This is a known set containing anchors to be used in certificate chain validation. The presence of a public key in this data set makes it an anchor.
Items in the set of anchors contain the following fields:
The public key of the anchor. A DER encoded SubjectPublicKeyInfo sequence as defined in X.509.
The subject DN of the anchor. A DER encoded Name sequence defined in X.509.
A certificate associated with the anchor. The DER encoded Certificate sequence defined in X.509.
Given the above fields and their flags, this set has the following characteristics:
Anchors are defined as a public key.
Some, but not all anchors have an associated certificate.
Some, but not all anchors have an associated subject.
A single anchor public key can be stored multiple times with different subjects and certificates.
To determine whether a given public key is an anchor callers should perform a lookup operation on this set using the public key info as the lookup field.
To determine whether a given certificate is an anchor callers should extract the subjectPublicKeyInfo field of that certificate. Then perform a lookup operation on this set using the public key info as the lookup field.
If a caller is building a certificate chain, and wishes to find a possible anchor: Perform a lookup operation on this set using the issuer field of the last certificate in the chain as the subject lookup field.
Callers looking up anchors in the store which are unable to handle anchors that are not certificates, should ignore anchors that do not contain certificates. If multiple results are returned for a lookup, such callers should prefer the result which contains a certificate field.
Anchors without a subject field are not able to be used when building a certificate chain.
To change whether a public key or certificate is an anchor or not, it is added or removed from the list of anchors.
Callers storing anchors in the store, should be aware that certificate and subject fields are desired by many callers, and should store those fields with the anchor if possible.
In order to be a certificate authority anchor (that is an anchor in a certificate chain with a length longer than one) the BasicConstraints extension must be present with a isCa field set to TRUE. This extension can be present either in the certificate or attached to it.
This is a known set containing public keys that should never be treated as valid. Items in the blacklist set contain the following fields:
The public key that is blacklisted. A DER encoded SubjectPublicKeyInfo sequence as defined in X.509.
The issuer DN of the authority that issued or previously validated the key or a certificate containing the key. A DER encoded Name sequence defined in X.509.
The serial number given by the authority issued or previously validated the key or a certificate containing the key. The DER encoded CertificateSerialNumber field defined in X.509.
Given the above fields and their flags, this set has the following characteristics:
Keys may be black listed by their public key.
Certificates may be black listed by issuer and serial number.
A single public key may be blacklisted with different issuer and serial number fields.
To determine whether a given public key is black listed callers should perform a lookup operation on this set using the public key info as the lookup field.
Callers which are validating certificate chains should, for all non-root certificates in the chain, perform a lookup on this set using the issuer and serialNumber as lookup fields.
Callers storing blacklists in the store, should store as much information as is available. If a certificate is available then store all three of the public key info, issuer, and serial number fields. If only issuer and serial number information is available (such as would come from a CRL list) then store those.
Additionally it is possible to blacklist a certificate by constraining its trust policy with certificate extensions like ExtendedKeyUsage so that it will not validate for any purpose or use case. This is not the recommended approach. Implementors should instead place the certificates on an explicit blacklist.
This is a known set of certificate extensions that should be applied to a public key, which define or adjust trust policy for it. Items in the attached extensions set contain the following fields:
The public key with which the extension is to be used. A DER encoded SubjectPublicKeyInfo sequence as defined in X.509.
The extension to define for the public key. A DER encoded Extension sequence defined in X.509.
Given the above fields and their flags, this set has the following characteristics:
Attached extensions are associated with a public key.
Multiple attached extensions may be present for a given public key.
To lookup all attached extensions for a given certificate or public key, callers should perform a lookup operation on this set using the public key info as the lookup field.
Callers which are validating certificate chains should, retrieve all attached extensions for each certificate in the chain and use those attached extensions as if they had been present in the respective certificate. If an attached extension has the same extnID value as one present in the certificate, the attached certificate extension should be used instead.
Callers storing attached extensions in the store, should never store duplicate extensions in the set that contain the same extnID value, just as you would not place multiple extensions in a certificate with the same extnID.
To change whether a certificate is an authority or not, an attached BasicConstraints extension is added with the relevant isCa and pathlen fields.
An ExtendedKeyUsage or KeyUsage attached extension may be added to a certificate when the system builder or administrator wishes to define or override which purposes a certificate can be used for (eg: server authentication, email, etc.)
In combination with having a certificate an anchor, these attached extensions may be used to constrain for what purposes anchors can be used.
A NameConstraints attached certificate extension may be added to a certificate when the system builder or administrator wishes to define which end entity names can be signed by a given certificate.
Implementations may have multiple stores, each containing the above sets. For example one store may be a read-only system store, and another store may be one editable by the user. Implementations should have a defined order of lookup priority for these multiple stores.
Callers performing a lookup operation should perform the lookup against each store in turn, using the defined order. Once the lookup operation returns results against a store, it should not continue to on to lower priority stores. In this way items in higher priority stores override information in lower priority stores.
If a public key or certificate is both in the set of anchors and the blacklist set, then the caller should treat it as black listed. This means that both the anchors and blacklist sets in a given store should be consulted when validating certificates or keys. However again, as noted above, once a store returns results for a key, stores with a lower priority should not be consulted for trust information about that key.
 Note we use the term policy here rather broadly, and is not limited to the PolicyConstraints certificate extension. Rather it includes such concepts as ExtendedKeyUsage, NameConstraints, PolicyConstraints, and so on.
 See RFC 5280 section 126.96.36.199
 See RFC 5280 section 188.8.131.52