Windowed revocation is a technique for the revocation of the digital certificates that provide assurance of the auth- enticity and integrity of public encryption keys and associated private decryption keys. These keys are used to protect the privacy of communications via the Internet. The need for revocation of certificates arises in cases in which private keys are lost or compromised, rights of access are changed, or it is desired to change keys as a precaution against cryptanalysis. Windowed revocation satisfies the security requirements and conforms to the policies of publickey systems now in use, while imposing less (relative to prior certificate-revocation techniques) of a burden on certificate server computers and communication networks.

This Time Line illustrates an example of windowed revocation. Once certificates C1 and C2 are revoked, they are mentioned in CRLs that occur during their revocation windows.
Heretofore, the acceptance of certificate- distribution services has been inhibited by the lack of a certificate-revocation technique that is scalable in the sense that the cost associated with the management, retrieval, and verification of certificates would increase at a rate less than the rate of growth of the community served. There are two fundamental approaches to the dis- tribution of information about revocation of certificates: explicit and implicit.

  • In certificate-distribution architectures that employ explicit revocation, each issuer explicitly states which certificates are revoked, and indirectly which are not revoked. In systems based on the X.500 standard, each issuer periodically generates a list of certificates that have been revoked but have not yet expired. The presence of the certificate in the list, called a certificate revocation list (CRL), explicitly states revocation. The performances of such systems are largely limited by the cost of bandwidth: the transmission of large CRLs to potentially many clients can be prohibitively expensive.
  • In certificate-distribution architectures that employ implicit revocation, lack of revocation is asserted implicitly through the verifier’s ability to retrieve the certificate. Any certificate retrieved from the issuer is guaranteed to be valid at or near the time of retrieval. Associated with each certificate is a time to live (TTL), which represents the maximum time the certificate may be cached. Thus, in implicit revocation, the window of vulnerability is the TTL. The performance of a system that uses implicit revocation is limited by the cost of acquiring certificates: supplying real-time information on revocation status during each acquisition is computationally expensive.

Windowed revocation involves a hybrid of explicit and implicit revocation that affords the desired scalability. In windowed revocation, the issuer asserts revocation in two different ways at two different times: (1) implicitly during initial acquisition of a certificate, and thereafter (2) explicitly through periodically published CRLs. Verifiers acquire CRLs from issuers directly. Retrieved certificates are guaranteed to be nonrevoked, fresh, and authentic. Subsequent validation of the revocation statuses of certificates is effected primarily through CRLs.

CRLs are generated at uniform time intervals, each interval being denoted a CRL publication period. Revoked certificates are mentioned in the CRLs that occur during possibly longer intervals denoted revocation windows (see figure). A revocation window is the time during which a certificate may be cached without further validation. The revocation window is specified by the issuer and documented in each certificate. By bounding the times during which each revoked certificate must be included in the periodic CRLs, revocation windows limit the sizes of CRLs and thus the costs of distributing them.

Windowed revocation is secure, and its correctness has been rigorously mathematically proved. In worst-case situations, it requires no more network bandwidth than do prior CRL-based techniques and no more central-processing-unit resources than do prior implicit techniques. Moreover, the tradeoffs between consumption of resources and security can be managed through the parameters of windowed-revocation protocols.