Tradeoffs in certificate revocation schemes

ABSTRACT

Cryptographic certificates are a powerful tool for security concerned applications where the participants must be authenticated in order to access some resources or commit a transaction. However, due to various reasons, the validity of such certificates can change over time, introducing the risk of an invalid certificate being used to authenticate an entity. Various methods of mitigating this risk have been devised, known broadly as "certificate revocation" schemes. In this paper, we categorize and analyze them based on our identified characteristics. We further discuss tradeoffs among them and suggest how system designers might apply the analyses.

REFERENCES

• 1: The SSL V3.0 Protocol. http://wp.netscape.com/eng/ssl3/draft302.txt.
• 2: ValiCert: Secure solution for paperless e-business. http://www.valicert.com.
• 3: Secure Hash Standard. U.S. National Institute for Standards and Technology (NIST), 1994.
• 4: Carlisle Adams and Robert Zuccherato. A General, Flexible Approach to Certificate Revocation, June 1998. Entrust White Paper.
• 5: William Aiello , Sachin Lodha , Rafail Ostrovsky, Fast Digital Identity Revocation (Extended Abstract), Proceedings of the 18th Annual International Cryptology Conference on Advances in Cryptology, p.137-152, August 23-27, 1998
• 6: André Årnes. Public Key Certificate Revocation Schemes. PhD thesis, Norwegian University of Science and Technology, February 2000.
• 7: Josh Cohen Benaloh and Michael de Mare. One-Way Accumulators: A Decentralized Alternative to Digital Signatures. Lecture Notes in Computer Science, 765:274--285, 1994.
• 8: Dan Boneh, Xuhua Ding, Gene Tsudik, and Chi Ming Wong. A Method for Fast Revocation of Public Key Certificates and Security Capabilites. In The 10th USENIX Security Symposium, 2001.
• 9: Ahto Buldas , Peeter Laud , Helger Lipmaa, Accountable certificate management using undeniable attestations, Proceedings of the 7th ACM conference on Computer and communications security, p.9-17, November 01-04, 2000, Athens, Greece [doi>10.1145/352600.352604]
• 10: David A. Cooper, A Model of Certificate Revocation, Proceedings of the 15th Annual Computer Security Applications Conference, p.256, December 06-10, 1999
• 11: David A. Cooper, A More Efficient Use of Delta-CRLs, Proceedings of the 2000 IEEE Symposium on Security and Privacy, p.190, May 14-17, 2000
• 12: E. Faldella , M. Prandini, A novel approach to on-line status authentication of public-key certificates, Proceedings of the 16th Annual Computer Security Applications Conference, p.270, December 11-15, 2000
• 13: Irene Gassko , Peter Gemmell , Philip D. MacKenzie, Efficient and Fresh Cerification, Proceedings of the Third International Workshop on Practice and Theory in Public Key Cryptography: Public Key Cryptography, p.342-353, January 18-20, 2000
• 14: Michael Goodrich, Robert Tamassia, and Andrew Schwerin. Implementation of an Authenticated Dictionary with Skip Lists and Commutative Hashing.
• 15: R. Housley, W. Ford, W. Polk, and D. Solo. Internet X.509 Public Key Infrastructure Certificate and CRL Profile, Jan 1999. RFC 2459.
• 16: Stephen T. Kent, Internet Privacy Enhanced Mail, Communications of the ACM, v.36 n.8, p.48-60, Aug. 1993 [doi>10.1145/163381.163390]
• 17: Stephen T. Kent. Privacy Enhancement for Internet Electronic Mail: Part II: Certificate-Based Key Management, Feburary 1993. RFC 1422.
• 18: Angelos Dennis Keromytis , Jonathan M. Smith, Strongman: a scalable solution to trust management in networks, 2001
• 19: Paul C. Kocher, On Certificate Revocation and Validation, Proceedings of the Second International Conference on Financial Cryptography, p.172-177, February 23-25, 1998
• 20: Y. Kortesniemi, T. Hasu, and J. Srs. A Revocation, Validation and Authentication Protocol for SPKI Based Delegation Systems. In Network and Distributed System Security Symposium, February 2000.
• 21: Patrick McDaniel and Sugih Jamin. Windowed Certificate Revocation. In INFOCOM(3), pages 1406--1414, 2000.
• 22: Patrick McDaniel , Aviel D. Rubin, A Response to ''Can We Eliminate Certificate Revocation Lists?'', Proceedings of the 4th International Conference on Financial Cryptography, p.245-258, February 20-24, 2000
• 23: Ralph C. Merkle, A certified digital signature, Proceedings on Advances in cryptology, p.218-238, July 1989, Santa Barbara, California, United States
• 24: S. Micali, Enhanced Certificate Revocation System, Massachusetts Institute of Technology, Cambridge, MA, 1995
• 25: S. Micali, Efficient Certificate Revocation, Massachusetts Institute of Technology, Cambridge, MA, 1996
• 26: Silvio Micali. NOVOMODO: Scalable Certificate Validation and Simplified PKI Management. In 1st Annual PKI Research Workshop - Proceeding, April 2002.
• 27: Michael Myers, Revocation: Options and Challenges, Proceedings of the Second International Conference on Financial Cryptography, p.165-171, February 23-25, 1998
• 28: Michael Myers, Rich Ankney, Ambarish Malpani, Slava Galperin, and Carlisle Adams. X.509 Internet Public Key Infrastructure Online Certificate Status Protocol-OCSP, June 1999. RFC 2560.
• 29: Moni Naor and Kobbi Nissim. Certificate Revocation and Certificate Update. In Proceedings 7th USENIX Security Symposium (San Antonio, Texas), Jan 1998.
• 30: CCITT (Consultative Committee on International Telegraphy and Telephony). Recommendation X.509: The Directory---Authentication Framework, 1988.
• 31: R. Perlman and C. Kaufman. Method of Issuance and Revocation of Certificates of Authenticity Used in Public Key Networks and Other Systems. United State Patent 5,261,002, November 1993.
• 32: Ronald L. Rivest, Can We Eliminate Certificate Revocations Lists?, Proceedings of the Second International Conference on Financial Cryptography, p.178-183, February 23-25, 1998
• 33: Petra Wohlmacher, Digital certificates: a survey of revocation methods, Proceedings of the 2000 ACM workshops on Multimedia, p.111-114, October 30-November 03, 2000, Los Angeles, California, United States [doi>10.1145/357744.357892]
• 34: Rebecca N. Wright , Patrick D. Lincoln , Jonathan K. Millen, Efficient fault-tolerant certificate revocation, Proceedings of the 7th ACM conference on Computer and communications security, p.19-24, November 01-04, 2000, Athens, Greece [doi>10.1145/352600.352605]
• 35: ITU-T Recommendation X.509. Information Technology - Open Systems Interconnection - The Directory: Authentication Framework, August 1997.