Public Key Infrastructures (PKI)

PKI Research, Standards & Guidance

PKI Architectures

A Public Key Infrastructure (PKI) is the key management environment for public key information of a public key cryptographic system. In general, there are three basic PKI architectures based on the number of Certificate Authorities (CAs) in the PKI, where users of the PKI place their trust (known as a user’s trust point), and the trust relationships between CAs within a multi-CA PKI.

The most basic PKI architecture is one that contains a single CA that provides the PKI services (certificates, certificate status information, etc.) for all the users of the PKI. Multiple CA PKIs can be constructed using one of two architectures based on the trust relationship between the CAs. A PKI constructed with superior-subordinate CA relationships is called a hierarchical PKI architecture. Alternatively, a PKI constructed of peer-to-peer CA relationships is called a mesh PKI architecture.

Directory Architectures

Early PKI development was conducted under the assumption a directory infrastructure – specifically a global X.500 directory - would be used to distribute certificates and certificate revocation lists (CRL). Unfortunately, the global X.500 directory did not emerge resulting in PKIs being deployed using various directory architectures based on how directory requests are serviced. If the initial directory cannot service a request, the directory can forward the request to other known directories using directory chaining. Another way a directory can resolve an unserviceable request is to return a referral to the initiator of the request indicating a different directory that might be able to service the request. If the directories cannot provide directory chaining or referrals, pointers to directory servers can be embedded in a PKI certificate using the Authority Information Access (AIA) and Subject Information Access (SIA) extensions.

In general, all PKI users interface to the directory infrastructure using the Lightweight Directory Access Protocol (LDAP) irregardless of how the directory infrastructure is navigated.

To help enhance interoperability of the directory infrastructures that support PKI, NIST has help develop the Federal PKI Directory Profile Version 2 and the Shared Service Provider (SSP) Repository Requirements documents.

Bridge CAs

Bridge Certification Authorities (BCAs) provide the means to leverage the capabilities of existing corporate PKIs as well as Federal PKIs. "Bridge Certification Authorities: Connecting B2B Public Key Infrastructures" describes different PKI architectures, difficulties in connecting the architectures, and how a BCA addresses these issues. This article also describes the BCA concept, BCA deployment in the U.S. federal government, and how the BCA enables B2B electronic commerce.

Initially, demonstrated at the Electronic Messaging Association (EMA) Challenge 2000 (see Report of Federal Bridge Certification Authority Initiative and Demonstration), the Federal Bridge CA has been operational since 2001. More information on the Federal Bridge CA is available at http://www.cio.gov/fbca/.

Current NIST research and standardization for BCAs is focused on developing test suites for X.509 certification path building and validation to provide a sanity check for performance and scalability measures.

Certificate Status

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. Ueli Maurer. Modelling a public-key infrastructure. Fourth European Symposium on Research in Computer Security (ESORICS 96), pages 324-350, September 1996. 
4. Silvio Micali. Efficient certificate revocation. Technical Memo MIT/LCS/TM-542b, Massachusetts Institute of Technology, Laboratory for Computer Science, March 1996. 
5. Moni Naor and Kobbi Nissim. Certificate revocation and certificate update. In Proceedings of the 7th USENIX Security Symposium, January 1998