Petra Wohlmacher
University of Klagenfurt
Villacherstrasse 161
9020 Klagenfurt, Austria
+43 463 2700854
petra.wohlmacher@uni-klu.ac.at
Keywords
Digital certificate, public-key certificate, attribute certificate, X.509, revocation, CRL, CRS, CRT, OCSP.
Certificates are generated and issued by a trustworthy authority named certification authority (CA). The security policy of a CA describes the lifecycle of key pairs or attributes, respectively, and thus, the validity period of a certificate. Within this period, its reliability can be assured. The validity of the public key or attribute is specified in the certificate and signed together with other data by the CA. Therefore, certificates are unforgeable and usually securely submitted to an authority that provides certificates. The authority is mostly called directory. Typically, the validity period of a certificate is between several months and two years. But in some circumstances, a certificate must to be revoked, i.e. its validity must be terminated sooner than assigned.
The revocation management needs to be clearly defined for CAs, directories, and users: CAs must provide a revocation service in a trustworthy manner and therefore, publish a proper security policy. A user needs to know how and when a revocation must be initiated and also gets informed. The revocation is initiated by the owner of the certificate (subject), by an authorized representative which is already mentioned in the certificate or by a CA. Only the CA revokes certificates and complies with a revocation request since the initiator is able to prove his authorization. Usually, the status of all certificates is submitted to the directory that answers users requests concerning the validity of certificates. Due to the security policy, this service might also be provided by another authority.
Additionally, revocation methods must fulfill other requirements, too. A revocation needs to be fast, efficient, timely and particularly appropriated for large infrastructures. Due to that, it is necessary e.g. to reduce the number of time-consuming calculations like verification processes of a digital signature and to apply other mechanisms, or to minimize the amount of data transmitted. It is also desirable that a method provides suspending a certificate temporarily (placed onhold) and also a reuse.
To prove the validity of a certificate, a user has to perform different tests, where some of them are really critical. One of the most critical ones is to determine whether a certificate has been revoked or not. Usually, a user determining whether a specific certificate has been revoked sends a request to a directory. The request contains at least a serial number which represents a unique identifier for each certificate. The response includes the serial number, status, date and reason of revocation, and is then analyzed by the user.
In the following, the paper gives an overview of different kinds of revocation methods. They all have in common that an authentic verification key of the (Root-)CA is required. Initially, we give a short classification and point out main reasons for the revocation of certificates. Traditionally, revoked certificates are stored in certificate revocation lists (CRL) which are described in section 4. Section 5 gives an introduction to certificate revocation systems (CRS). In section 6 we present the idea of a certificate revocation tree (CRT) and in section 7 we point out the online certificate revocation protocol (OCSP). Finally we give some conclusions.
A CRL contains a list of serial numbers of revoked certificates together with their date of revocation, and also a date of its generation and a latest date of the next issue. Optional more information e.g. reasons of revocation can be added. Finally, the CRL is digitally signed by the issuing CA. Thus, its freshness and authenticity can be checked. CRLs are periodically sent to a directory.
Users requesting the validity of a certificate receive a full CRL. Then they check the actuality and verify the signature of the CRL. If this succeeds, they determine whether the certificate queried is included in the CRL or not. If the serial number can not be found, the certificate is supposed to be still valid.
Because CRLs are straightforward, they are easy to understand and thus, widespreadly used. Since the validity period of certificates is long and the number of users is immens, CRLs can grow extremely large. Therefore, a great amount of data needs to be transmitted. The fact that a CRL is only up-to-date at their point of issuing led to the definition of so called delta-CRLs. A delta-CRL is issued between two CRL updates. It includes only changes since the last issued CRL and so enhances the efficiency. Delta-CRLs contain sequence numbers that allow to verify the completeness of CRL information.
The system is set up as follows: The CA defines n time intervals i (e.g., with respect to a year, daily: n = 365 and i represents a day), within the CRS is periodically updated. Using X.509 certificates, the number of extension fields needs to be extended by two 100-bit fields called Y (for "yes") and N (for "no"). Because of CA's signature, the authenticity of both values is guarantied. The CA constitutes a proper hash function H and chooses (pseudo-)randomly two 100-bit values Y0 and N0, where both Y0 and N0 are kept secret by the CA. Then the CA calculates (see Figure 1): Y : = Yn = Hn(Y0) and N : = H(N0). Value Y0 is used within n computations but N0 only once.
To keep the CRS up-to-date the CA submits the following information to a directory: a fresh and timestamped list L containing all serial numbers of issued and not-yet-expired certificates, where L is signed by the CA. Also further information are transmitted: new certificates issued within interval i; a 100-bit value V for each certificate determined either by V : = Yn - i = Hn - i(Y0) if the certificate is neither expired nor revoked, or by V : = N0 if the certificate has been revoked within interval i. For revoked certificates the CA may also provide a signed template including additional data like time and reason of revocation. Now, the directory stores the serial numbers of each certificate together with its dedicated value V.
A user asking for the validity of a certificate first gains list L. Then he checks the soundness and correctness of the whole list L by verifying the signature. If this succeeds, he determines whether L contains the requested serial number. Further tests are performed by using Y or N (see Figure 1): He calculates Hi(V) and examines whether Hi(V) equals Y. If this is true, the certificate is valid within the interval i. Otherwise, he computes H(V) and verifies whether H(V) is equal to N. If any verification succeeds, the status of the certificate can determined. This works because: Y = Hi(Hn - i(Y0)) = Hn(Y0) and N = H(N0).
All other occurrences come from problems concerning e.g. data transmission, data authenticity or even denial of services.
A CRS provides the following advantages: The signed list L is offered off-line. Because a hash function is used and both Y and N are represented by a string of 100 bits, the verification process of V is efficient and therefore, can be calculated online. The directory is not able to forge neither L nor V since Y0 and N0 is only known by the CA. Nevertheless, the security of CRS depends also on the secrecy of Y0 and N0, and also on their generation process.
The system is initialized as follows: Let low resp. high, where
low < i < high,
determine the lower resp. upper bound of the range of all serial numbers i. A
certificate with serial number i is named Ci. Revoked certificates Cj and Ck
form a pair (j, k), where no certificate Cm with a serial number in the range j < m < k
is revoked. Let N be the number of revoked certificates, then the ranges are identified
by data structures
L0,..., LN, where each of them may contain additional
information about reason and date of revocation. Now, each
Ln(0 n
N) is
used as a leaf node N0, n of a binary tree to build a hash tree by use of a hash
function H:
N0, n = H(Ln). (Remark: To simplify matters, we assume that N + 1 is a
power of 2, where the binary tree is complete and has height
log2(N + 1). Otherwise,
Li is placed to lower levels of the tree.)
Each node Ni, j of the next level (descendant) is computed by hashing the concatenation of its left ancestor Ni - 1, l and its right ancestor Ni - 1, r: Ni, j = H(Ni - 1, l|| N i - 1, r), where H denotes a hash function. All other values of the nodes are computed in the same manner up to the root N r, 0 where r : = log2(N + 1). Subsequently, the root of the tree together with other information like issuing and expiration date of the CRT is digitally signed by the CA. Finally, tree and signature are made available for users by a directory.
A user sends a request containing the serial number of the certificate to a directory. The response consist of the following data: the data structure Lk which includes the inquired serial number, if k is even: the value N0, k + 1 otherwise N 0, k - 1, additionally, the smallest number of other hash values representing nodes which are needed to compute the root and finally, the root and its signature. Now, the user needs to hash the data in the right manner and checks whether the computed value of the root equals its submitted value. If so, the validation succeeds and regarding Li either the certificate is valid or revoked.
Figure 2 shows an example for a CRT, where N = 7 and the serial numbers of revoked certificates are given by 4, 8, 15, 16, 28, 34, 48. For example, N 1, 2 is computed by N1, 2 = H(N0, 4|| N 0, 5) where N0, 4 = H(L4) and N0, 5 = H(L5) . The validity of certificate with serial number 14 can be checked using L2, N0, 3, N1, 0, N2, 1 , and the signed root.
CRTs are efficient, because of the use of hash functions and the amount of data increases only as the logarithm of the number of tree leafs. Furthermore, values of the nodes can be precomputed. The signing of the root can also be performed off-line, but since it is an off-line system, issuing dates need to be defined and also up-to-date problems occure.The protocol is applied between a client (OCSP requester, acting for the user) and a server (OCSP responder, representing a directory). The client generates a so called OCSP request that primary contains one ore even more identifiers of certificates queried, i.e. their serial number together with other data. Then, the (optionally signed) request is send to the server. The server receiving the OCSP request creates an OCSP response: Since all syntactical and content checks succeed, the response mainly includes a timestamp representing the time when the actual request is generated, furthermore, the identifiers and status values of the requested certificates together with a validity interval. A certificate status value is either set to good, revoked or unknown. Be aware that "good" implies three meanings: firstly, the certificate is not revoked, but secondly, it may also not be issued yet or even thirdly, the time at which the response is produced is not within the validity of the certificate. Status "revoked" stands for a revocation or onhold of the certificate. If the answer is "unknown" the server has no information available about the required certificate. The validity interval specifies the time at which the status being indicated is known to be correct and optional the time at or before newer information will be available about the status of the certificate. The OCSP response should be digitally signed either by the server or by the CA. In case of any error the OCSP response contains an error message. The OCSP response is send to the requesting client of the user who then analyzes the data.
Extensions like time and reason for revocation may be used in addition, further OCSP extensions are handled in a separate Internet-Draft [2]. Formats of request and response are due to the transmission protocol e.g. HTTP or LDAP.
Depending on proper defined time schedules, OCSP provides more timely status information than any other method. A preproducing of signed responses is currently optional. OCSP is especially appropiated for attribute certificates where status information always need to be up-to-date. In the practice, the caching of HTTP-browsers must be handled carefully.
The knowledge about different revocation methods is not very widely spread. Efficient and practicable methods are still needed and a topic of today's research. A main requirement for new developments and new ideas is that they can easily be integrated in widespreadly used X.509 certificates.