Method and system for authenticating digital certificates issued by an authentication hierarchy

• US 6,301,658 B1
• Filed: 09/09/1998
• Issued: 10/09/2001
• Est. Priority Date: 09/09/1998
• Status: Expired due to Term

• Current Assignee: McAfee, LLC
• Original Assignee: Secure Computing Corporation (McAfee, LLC)
• Inventors: Koehler, Stephen C.
• Primary Examiner(s): Peeso, Thomas R.
• Application Number:
  US09/150,260
• Time in Patent Office: 1,126 Days
• Field of Search: 380/255, 380/277, 380/278, 380/279, 713/155, 713/156, 713/158, 713/169, 713/175
• US Class Current: 713/155
• CPC Class Codes: G06F 21/33 using certificates
• CPC Class Codes: G06F 2221/2151 Time stamp

Abstract

A method and system for efficiently authenticating digital certificates issued by an organization'"'"'s authentication hierarchy. The system includes a verification server that manages a certificate repository and a verification cache having entries for verified digital certificates and certification revocation lists. Each cache entry includes a corresponding timestamp that indicates when the item was last authenticated. The verification server incrementally updates the verification cache using a recursive procedure to traverse the hierarchy'"'"'s chain of authority signatures. The procedure performs costly verifications of digital signatures and scans of certification revocation lists only when an item'"'"'s timestamp is out of date with respect to its issuer'"'"'s digital certificate, certification revocation list or other security information.

Claims

1. A method for authenticating a user digital certificate issued by a certification authority (CA) belonging to a hierarchy of certification authorities (CA'"'"'s) having a root CA, wherein each CA of the hierarchy except the root CA has a corresponding digital certificate from a parent CA of the hierarchy, the method comprising the steps of:

providing a cache having entries for previously authenticated digital certificates, wherein each entry has a timestamp;

traversing the hierarchy of CA'"'"'s to determine a chain of parent CA'"'"'s from the CA that issued the user digital certificate to the root CA; and

marking the user digital certificate as authentic as a function of timestamp of a cache entry for the user digital certificate and the timestamps of cache entries for digital certificates of each CA of the determined chain.

2. The method of claim 1, wherein the marking step includes the steps of:

authenticating the digital signature of the user digital certificate when a timestamp of the respective cache entry is older than a timestamp of the issuing CA; and

updating the timestamp of the cache entry for the user digital certificate when the digital signature of the user digital certificate is authenticated.

3. The method of claim 2, wherein the marking step includes the steps of:

authenticating the digital signature of the digital certificate of each CA of the determined chain when a timestamp of the corresponding cache entry is older than a timestamp of the cache entry for the corresponding parent CA; and

updating the timestamp of the corresponding cache entry of each CA of the determined chain when the digital signature of the digital certificate of each CA is authenticated.

4. The method of claim 2, wherein the authenticating step includes the step of verifying the digital signature of the user digital certificate using a corresponding public key.

5. The method of claim 3, wherein the authenticating step includes verifying the digital signature of each CA of the determined chain using a corresponding public key.

6. The method of claim 1, wherein the verification cache has entries for certificate revocation lists (CRL'"'"'s), and further wherein the marking step includes searching a CRL published by the CA issuing the user digital certificate when a timestamp of a cache entry for the CRL of the issuing CA is more recent than the timestamp of the cache entry for the user digital certificate.

7. The method of claim 1, wherein the verification cache has entries for certificate revocation lists (CRL'"'"'s), and further wherein the marking step includes searching a CRL published by the corresponding parent CA of each CA of the determined chain when a timestamp of a cache entry for the CRL is more recent than the timestamp of the cached entry for the digital certificate of the CA.

8. A system for authenticating a user digital certificate issued by a certification authority (CA) belonging to a hierarchy of certification authorities (CA'"'"'s) having a root CA, wherein each CA of the hierarchy except the root CA has a corresponding digital certificate from a parent CA of the hierarchy, the system comprising:

a verification cache having a plurality of cache entries, wherein each cache entry corresponds to a digital certificate, and further wherein each cache entry has a timestamp indicating when a digital signature of the corresponding digital certificate was authenticated; and

a verification server for authenticating the user digital certificate based on a comparison of the timestamp of a cache entry for the user digital certificate with timestamps of cache entries for each CA of a chain of parent CA'"'"'s linking the issuing CA to the root CA.

9. The system of claim 8, wherein the verification server authenticates the digital signature of the user digital certificate when a timestamp of the respective cache entry is older than a timestamp of the issuing CA.

10. The system of claim 9, wherein the verification server authenticates the digital signature of the digital certificate of each CA of the chain when a timestamp of the corresponding cache entry is older than a timestamp of the cache entry for the corresponding parent CA.

11. The system of claim 9, wherein the verification server verifies the digital signature of the user digital certificate using a corresponding public key.

12. The system of claim 10, wherein the verification server verifies the digital signature of each CA of the determined chain using a corresponding public key.

13. The system of claim 8, wherein the verification cache has entries for certificate revocation lists (CRL'"'"'s), and further wherein the verification server searches a CRL published by the CA issuing the user digital certificate when a timestamp of a cache entry for the CRL is more recent than the timestamp of the cache entry for the user digital certificate.

14. The system of claim 8, wherein the cache has entries for certificate revocation lists (CRL'"'"'s), and further wherein the verification server searches a CRL published by the corresponding parent CA of each CA of the chain when a timestamp of a cache entry for the CRL is more recent than the timestamp of the cached entry for the digital certificate of the CA of the chain.

15. A system for processing client requests to authenticate user digital certificates issued by a certification authority (CA) of a hierarchy of certification authorities (CA'"'"'s) having a root CA, wherein each CA of the hierarchy except the root CA has a corresponding digital certificate from a parent CA of the hierarchy, the system comprising:

a verification cache having a plurality of cache entries, wherein each cache entry corresponds to a verified digital certificate, and further wherein each cache entry has a timestamp indicating when a digital signature of the corresponding digital certificate was authenticated; and

a verification server executing a software program for performing the steps of;

accessing the verification cache to retrieve a cache entry for a digital certificate of the CA issuing the user digital certificate;

authenticating the digital certificate of the issuing CA as a function of cache entries for each CA of a chain of parent CA'"'"'s from the issuing CA to the root CA;

updating the timestamp of the cache entry for the digital certificate of the issuing CA when the digital certificate of the issuing CA is authenticated; and

responding that the user digital certificate is authentic when the timestamp of the cache entry for the user digital certificate is more recent than the timestamp of the cache entry corresponding to the digital certificate of the issuing CA.

16. The system of claim 15, wherein the software program invokes a recursive subroutine to authenticate the digital certificate of each CA of the chain of CA'"'"'s.

17. The system of claim 15 wherein the responding step of the software program includes:

validating the digital signature of the user digital certificate when a timestamp of the respective cache entry is older than a timestamp of the issuing CA; and

updating the timestamp of the cache entry for the user digital certificate when the digital signature of the user digital certificate is authenticated.

18. The system of claim 15, wherein the of the software program authenticates the issuing CA by:

validating the digital signature of the digital certificate of each CA of the chain when a timestamp of the corresponding cache entry is older than a timestamp of the cache entry for the corresponding parent CA; and

updating the timestamp of the corresponding cache entry when the digital signature of the digital certificate of each CA of the chain is authenticated.

19. The system of claim 17, wherein the validating step of the software program includes verifying the digital signature of the user digital certificate using a corresponding public key.

20. The system of claim 18, wherein the authenticating step of the software program includes verifying the digital signature of each CA of the chain using a corresponding public key.

21. The system of claim 15, wherein the verification cache has entries for certificate revocation lists (CRL'"'"'s), and further wherein the responding step of the software program includes searching a CRL published by the issuing CA when a timestamp of a cache entry for the CRL is more recent than the timestamp of the cache entry for the user digital certificate.

22. A method for maintaining a cache having entries for previously authenticated digital certificates issued by a certification authority (CA) belonging to a hierarchy of CA'"'"'s, wherein each CA of the hierarchy except a root CA has a corresponding digital certificate issued by a parent CA of the hierarchy, the method comprising the steps of:

authenticating a digital signature of the digital certificate of one of the CA'"'"'s when a timestamp of the corresponding cache entry is older than a timestamp of the cache entry for the digital certificate of the corresponding parent CA; and

updating the timestamp of the cache entry for the authenticated digital certificate when the digital signature is authenticated.

23. The method of claim 22, wherein the cache has cache entries for certificate revocation lists (CRL'"'"'s) and the authenticating step includes searching a CRL published by the corresponding parent CA when a timestamp of a cache entry for the CRL is more recent than the timestamp of the cache entry for the digital certificate of the CA to be authenticated.