|
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
- Carlisle Adams and Robert Zuccherato.
A
general, flexible approach to certificate revocation. Entrust
Technologies White Paper, June 10, 1998.
- 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.
- Paul Kocher. A
Quick Introduction to Certificate Revocation Trees. ValiCert,
Inc. White Paper.
- Ueli Maurer. Modelling
a public-key infrastructure. Fourth European Symposium
on Research in Computer Security (ESORICS 96), pages 324-350,
September 1996.
- Silvio Micali. Efficient
certificate revocation. Technical Memo MIT/LCS/TM-542b, Massachusetts
Institute of Technology, Laboratory for Computer Science, March
1996.
- Moni Naor and Kobbi Nissim. Certificate
revocation and certificate update. In Proceedings of the
7th USENIX Security Symposium, January 1998
|
|