CSRC   nistlogo
Home Library Services Events Advisories Contact Site Map  
SEARCH

PKI Home

Application Programming Interface (API)

Computer Security Objects Register (CSOR)

Documents

Federal Bridge Certification Authority (FBCA)

Interoperability Testbed

MISPC

Program Overview

Security Requirements

Secure Mail

Testing PKI Components

TWG

NIST Cryptographic Standards

 
 
 
Modeling of PKI Architectures

Certificate Revocation Modeling

Public key infrastructures (PKIs) are being fielded in increasing size and numbers, but our operational experience to date has been limited to a relatively small number of environments. As a result, there are still many unanswered questions about the ways in which PKIs will be organized and operated in large scale systems. Some of these questions involve the ways in which individual certification authorities (CAs) will be interconnected. Others involve the ways in which revocation information will be distributed. In a 1994 report, the MITRE Corporation suggested that the distribution of revocation information has the potential to be the most costly aspect of running a large scale PKI [2].

The MITRE report assumed that each CA would periodically issue a certificate revocation list (CRL) that listed all of the unexpired certificates that it had revoked. Since the MITRE report was published, several alternative revocation distribution mechanisms have been proposed. Each of these mechanisms has its own relative advantages and disadvantages in comparison to the other schemes. The National Institute of Standards and Technology (NIST) has created mathematical models of some of the proposed revocation distribution mechanisms. These models were used in order to determine under what circumstances each of the mechanisms is most efficient.

Most of the proposed revocation distribution mechanisms have involved variations of the original CRL scheme. Examples include the use of segmented CRLs and delta-CRLs. However, some schemes do not involve the use of any type of CRL (e.g., on-line certificate status protocols and hash chains [5]).

"A model of certificate revocation" presents a mathematical model for describing the timings of validations by relying parties. The model is used to determine how request rates for traditional CRLs change over time. This model is then extended to show how request rates are affected when CRLs are segmented. This paper also presents a new technique for distributing revocation information, over-issued CRLs. Over-issued CRLs are identical to traditional CRLs but are issued more frequently. The result of over-issuing CRLs is to spread out requests from relying parties and thus to reduce the peak load on the repository.

"A more efficient use of delta-CRLs" uses the model described in "A model of certificate revocation" to analyze various methods of issuing delta-CRLs. It begins with an analysis of the "traditional" method of issuing delta-CRLs and shows that, in some circumstances, issuing delta-CRLs in this manner fails to provide the efficiency gains for which delta-CRLs were designed. A new method of issuing delta-CRLs, sliding window delta-CRLs, is then presented. Sliding window delta-CRLs are similar to traditional delta-CRLs but provide a constant amount of historical information. While this does not affect the request rate for delta-CRLs, it can significantly reduce the peak request rate for base CRLs. The paper provides an analysis of sliding window delta-CRLs along with advice on how to select the optimal window size to use when issuing delta-CRLs.
 

Papers

David A. Cooper. A model of certificate revocation. In Proceedings of the Fifteenth Annual Computer Security Applications Conference, pages 256-264, December 1999.

David A. Cooper. A more efficient use of delta-CRLs. In Proceedings of the 2000 IEEE Symposium on Security and Privacy, pages 190-202, May 2000.
 

References

  1. Carlisle Adams and Robert Zuccherato. A general, flexible approach to certificate revocation. Entrust Technologies White Paper, June 10, 1998.
  2. Shimshon Berkovits, Santosh Chokhani, Judith A. Furlong, Jisoo A. Geiter, and Jonathan C. Guild. Public Key Infrastructure Study: Final Report. Produced by the MITRE Corporation for NIST, April 1994.
  3. Paul Kocher. A Quick Introduction to Certificate Revocation Trees. ValiCert, Inc. White Paper.
  4. Ueli Maurer. Modelling a public-key infrastructure. Fourth European Symposium on Research in Computer Security (ESORICS 96), pages 324-350, September 1996. 
  5. Silvio Micali. Efficient certificate revocation. Technical Memo MIT/LCS/TM-542b, Massachusetts Institute of Technology, Laboratory for Computer Science, March 1996. 
  6. Moni Naor and Kobbi Nissim. Certificate revocation and certificate update. In Proceedings of the 7th USENIX Security Symposium, January 1998
 


Please read our NIST disclaimer and privacy policy.
The Computer Security Resource Center is in the Computer Security Division of the Information Technology Laboratory at the National Institute of Standards and Technology .
NIST is an agency of the U.S. Commerce Department's Technology Administration.
Please send comments or suggestions to david.cooper@nist.gov
Last Modified: February 20, 2002.