Meaning

What really matters in a public key certificate? For practitioners looking at this problem for the first time, the answer is obvious: the issuer and subject public keys. But those familiar with X.509-based public key infrastructures could counter that the distinguished names of the issuer and subject alone provide enough information to verify a certificate chain.

The process of certificate path validation from an end-entity certificate of interest to a trusted root is the algorithmic foundation of establishing trust in public key systems. In turn, checking to determine whether a certificate has been revoked is just a function of the underlying algorithm.

The proposed IETF public key infrastructure standard, PKIX Part 1 [4], specifies the algorithm for determining whether a particular certificate chain is valid but does not describe how to discover certificate chains in the first place. Moreover, the semantics of PKIX certificate revocation are also underspecified, which puts crucial issues of meaning in the hands of individual implementations. In every case, the actual process of certificate revocation is deemed the responsibility of the signer even if it is at the request of the subscriber. In theory, the certificate authority has the most to lose with continued circulation of a bad certificate.

Let C = c₀, c₁, ..., c_n be a chain of certificates where c_n is the end-entity certificate of interest, c₀ is a self-signed trusted root certificate, and c_k is signed by the subject of c_k-1 for all k = 1,...,n. By definition, if any certificate c_i in C is revoked then C is not a valid chain. Assume that no c_i in C is revoked, and let $C^{\prime}= c_0^{\prime}, c_1^{\prime}, ..., c_{k-1}^{\prime}, c_k ,..., c_n$ be a second chain of certificates from c_n to a trusted root ( $c_0^{\prime}$), with $c_{k-1}^{\prime}$distinct from c_k-1. Certificates c_k-1 and $c_{k-1}^{\prime}$have the same subject public key (the issuer of the statement in c_k).

Now, because revocation in the PKIX model applies to a particular certificate, it is possible to revoke $c_{k-1}^{\prime}$ without revoking c_k-1. Then chain $C^{\prime}$ is an invalid chain while C is still valid. Is this consistent? It depends on the semantics of the revocation. The certificate $c_{k-1}^{\prime}$ is a statement by an issuer $I_{c_{k-1}^{\prime}}$ that binds together subject name $SN_{c_{k-1}^{\prime}}$ and a subject public key $SPK_{c_{k-1}^{\prime}}$. That is:

$$\begin{eqnarray*}I_{c_{k-1}^{\prime}} : SN_{c_{k-1}^{\prime}} \longleftrightarrow SPK_{c_{k-1}^{\prime}} \end{eqnarray*}$$

where this statement is read, ``Issuer $I_{c_{k-1}^{\prime}}$ states that there is a binding (or relationship) between the public key $SPK_{c_{k-1}^{\prime}}$ and the identity information $SN_{c_{k-1}^{\prime}}$.''

So, revoking $c_{k-1}^{\prime}$ (e.g. adding $c_{k-1}^{\prime}$ to a ``certificate revocation list'' (CRL) signed by $I_{c_{k-1}^{\prime}}$) could mean ``UNDO'' any of the following:

(a)

UNDO $SPK_{c_{k-1}^{\prime}}$, the subject public key (that is, no longer trust the subject public key for anything because it has been compromised),

(b)

UNDO $SN_{c_{k-1}^{\prime }}\longleftrightarrow SPK_{c_{k-1}^{\prime }}$, the relationship between the subject public key and the subject name/identity information, because that binding is no longer valid, or

(c)

UNDO $I_{c_{k-1}^{\prime }}:<$binding>, the relationship between the certificate issuer and the binding between subject public key and identity information, because the issuer is no longer willing to vouch for the binding, although it may still be true.

Each of these cases means something different, and chain processing in the presence of revocation information acts differently in each case.

Consider the first case (a) above, where revocation of $c_{k-1}^{\prime}$ denotes compromise of the subject public key. In this case, the fact that $c_{k-1}^{\prime}$ is revoked should cause all certificate paths that involve the subject public key $SPK_{c_{k-1}^{\prime}}$ to no longer be valid. So, not only is $C^{\prime}$ now invalid, but C itself is now invalid as:

$$SPK_{c_{k-1}}==SPK_{c_{k-1}^{\prime }}==I_{c_{k}}$$

Ideally, if any certificate for a given subject public key is revoked for reasons of key compromise, all such certificates would immediately be revoked, but obviously we cannot guarantee this behavior. Thus, it may be argued that relying parties have a duty to check revocation status on all certificates naming a particular subject public key even if they themselves are not relying on those certificates for chain-building.

Case (b), direct revocation of the subject name-subject public key binding by the issuer, is a fuzzier situation. If the subject names in the two certificates c_k-1 and $c_{k-1}^{\prime}$ are distinct (i.e. $SN_{c_{k-1}} \neq SN_{c_{k-1}^{\prime}}$) then revocation of $c_{k-1}^{\prime}$ should have no impact on acceptance of c_k-1itself. That is, chain $C^{\prime}$ is invalid because of the revocation but C is still a perfectly valid chain. Notice, however, that if the subject names in the two certificates are equal then relying parties could reasonably choose to reject C (or at least suspect it) if the name information $SN_{c_{k-1}} == SN_{c_{k-1}^{\prime}}$ is important to their particular application.

Finally, in case (c) we have revocation of certificate $c_{k-1}^{\prime}$because the issuer of that certificate no longer has a relationship with the subject public key. Revocation here speaks not to the validity of the name-key binding but rather to a lack of contractual obligation. Revocation of $c_{k-1}^{\prime}$ should not in any way impact chain C as there is no authorization statement from the issuer of $c_{k-1}^{\prime}$ concerning the validity of the subject public key $SPK_{c_{k-1}^{\prime}}$ itself (which would make it case (a)) or the name-key binding (case (b)).

The fact that the act of revoking a particular certificate needed to be qualified with intended semantics was recognized by the authors of the X.509 standard. In X.509 Version 2 Certificate Revocation Lists (CRLs), it is possible to include a reason code extension on each and every entry in the CRL. Reason codes are semantics modifiers and can specify situations such as:

• Key compromise
• CA compromise
• Affiliation change (including subject name changes)
• Superseded
• Cessation of operation (the certificate is no longer needed for its original purpose)

Thus, one could conceivably decide whether a particular revocation fell into cases (a)-(c) above based on reason code, assuming one was present in the CRL and that each possible reason code could be assigned to a particular case. (This is not currently true in the PKIX specification as some reason codes have semantics orthogonal to the separation described above. For example, reason code 6, ``certificateHold,'' means that the certificate in question has been ``suspended'' pending the outcome of some process. Clearly the suspended certificate could fall into any of cases (a)-(c).)

Even if reason codes were always present (which is not required by PKIX) and defined to fall into exactly one semantic category for meaning, they only solve the problem if this information is always available to the chain-building algorithm. This is clearly not the case, as any revocation that falls into case (a) (including reason code 1, ``keyCompromise'') may impact certificate chains that do not include the particular revoked certificate. Thus, until we come up with a better mechanism for moving revocation information around, and binding that revocation information to the proper statement being undone by the revocation, use of revocation information can add significant ambiguity to the chain-building process.