Distributed delegated path discovery and validation

• US 8,707,030 B2
• Filed: 11/19/2004
• Issued: 04/22/2014
• Est. Priority Date: 11/19/2003
• Status: Active Grant

• Current Assignee: Assa Abloy AB
• Original Assignee: Corestreet, Ltd. (Assa Abloy AB)
• Inventors: Engberg, David
• Primary Examiner(s): Chea, Philip
• Assistant Examiner(s): HOANG, DANIEL L
• Application Number:
  US10/993,131
• Publication Number:
  US 20050154918A1
• Time in Patent Office: 3,441 Days
• Field of Search: 713/157
• US Class Current: 713/157
• CPC Class Codes: H04L 9/3265 using certificate chains, trees or paths; Hierarchical trust model
• CPC Class Codes: H04L 9/3268 using certificate validation, registration, distribution or revocation, e.g. certificate revocation list [CRL]

Abstract

Providing path validation information for a system includes determining paths between a subset of certificate of the system and at least one trust root, storing each of the paths in a table prior to a request for path validation information, and fetching the validation information stored in the table in response to a request for path validation information. Providing path validation information may also include digitally signing the validation information. Providing path validation information may also include applying constraints to the validation information and only providing validation information that is consistent with the constraints. Determining paths may include constructing a directed graph of trusted roots and the subset of certificates and performing a depth-first acyclic search of the graph.

Claims

1. A method of providing path validation information for a system, comprising:

determining, using at least one processor, paths between each of a plurality of certificates of the system and at least one trust root;

storing, in a non-transitory computer readable medium, validation information prior to a request for path validation information for a trust path from a target certificate to the at least one trust root, the trust path including a chain of certificates from the target certificate to the at least one trust root, wherein the validation information identifies a particular trust path from a particular one of the plurality of certificates to the at least one trust root, wherein the validation information for each particular trust path includes a proof for each of the plurality of certificates along the particular trust path indicating that each of the plurality of certificates has not been revoked, and wherein the proofs for the plurality of certificates are stored for each of the plurality of certificates of the particular trust path, are digitally signed, and are pre-generated prior to receiving the request for path validation information;

in response to the request for path validation information, determining, using at least one processor, the trust path from the target certificate to the at least one trust root that satisfies the request, fetching the validation information for the trust path, and providing to a relying party the validation information for the trust path in response to the request without performing real-time certificate status validation of the trust path; and

applying name or policy constraints to the validation information and only providing validation information that is consistent with the constraints.

2. The method, according to claim 1, wherein determining paths includes constructing a directed graph of trusted roots and the plurality of certificates and performing a depth-first acyclic search of the graph.

3. The method, according to claim 1, wherein validation information for all of the trusted paths is stored in a table and wherein the table is indexed using the trusted roots.

4. The method, according to claim 1, wherein validation information for all of the trusted paths is stored in a table and wherein the table is indexed using the certificates.

5. The method, according to claim 1, further comprising:

receiving and storing the proofs for the plurality of certificates at regular intervals prior to receiving the request for path validation information.

6. The method, according to claim 5, further comprising:

digitally signing the proofs.

7. The method, according to claim 1, wherein the plurality of certificates includes trusted roots, authorities that issue end user certificates, and authorities that vouch for other authorities.

8. The method, according to claim 7, wherein the plurality of certificates further includes end user certificates.

9. A computer program product, stored on a non-transitory computer-readable storage medium, that provides path validation information for a system, comprising:

a storage medium that contains executable code for the computer program product;

executable code that determines paths between each of a plurality of certificates of the system and at least one trust root;

executable code that stores validation information prior to a request for path validation information for a trust path from a target certificate to the at least one trust root, the trust path including a chain of certificates from the target certificate to the at least one trust root, wherein the validation information identifies a particular trust path from a particular one of the plurality of certificates to the at least one trust root, wherein the validation information for each particular trust path includes a proof for each of the plurality of certificates along the particular trust path indicating that each of the plurality of certificates has not been revoked, and wherein the proofs for the plurality of certificates are stored for each of the plurality of certificates of the particular trust path, are digitally signed, and are pre-generated prior to receiving the request for path validation information;

executable code that, in response to the request for path validation information, determines the trust path from the target certificate to the at least one trust root that satisfies the request, fetches the validation information for the trust path, and provides to a relying party the validation information for the trust path in response to the request without performing real-time certificate status validation of the trust path; and

executable code that applies name or policy constraints to the validation information and that only provides validation information that is consistent with the constraints.

10. The computer program product, according to claim 9, further comprising:

executable code that digitally signs the validation information.

11. The computer program product, according to claim 9, wherein executable code that determines paths constructs a directed graph of trusted roots and the plurality of certificates and performs a depth-first acyclic search of the graph.

12. The computer program product, according to claim 9, wherein validation information for all of the trusted paths is stored in a table and wherein the table is indexed using the trusted roots.

13. The computer program product, according to claim 9, wherein validation information for all of the trusted paths is stored in a table and wherein the table is indexed using the certificates.

14. The computer program product, according to claim 9, further comprising:

executable code that receives and stores the proofs for the plurality of certificates at regular intervals prior to receiving the request for path validation information.

15. The computer program product, according to claim 9, wherein the subset of certificates includes trusted roots, authorities that issue end user certificates, and authorities that vouch for other authorities.

16. The computer program product, according to claim 15, wherein the plurality of certificates further includes end user certificates.

17. A server, comprising:

a processor;

internal storage coupled to the processor;

executable code, provided on the internal storage, that determines paths between each of a plurality of certificates of the system and at least one trust root;

executable code, provided on the internal storage, that stores validation information prior to a request for path validation information for a trust path from a target certificate to the at least one trust root, the trust path including a chain of certificates from the target certificate to the at least one trust root, wherein the validation information identifies a particular trust path from a particular one of the plurality of certificates to the at least one trust root, wherein the validation information for each particular trust path includes a proof for each of the plurality of certificates along the particular trust path indicating that each of the plurality of certificates has not been revoked, and wherein the proofs for the plurality of certificates are stored for each of the plurality of certificates of the particular trust path, are digitally signed, and are pre-generated prior to receiving the request for path validation information; and

executable code, provided on the internal storage, that, in response to the request for path validation information, determines the trust path from the target certificate to the at least one trust root that satisfies the request, fetches the validation information for the trust path, and provides to a relying party the validation information for the trust path in response to the request without performing real-time certificate status validation of the trust path; and

executable code, provided on the internal storage, that applies name or policy constraints to the validation information and that only provides validation information that is consistent with the constraints.

18. The server, according to claim 17, further comprising:

executable code, provided on the internal storage, that digitally signs the validation information.

19. The server, according to claim 17, wherein executable code that determines paths constructs a directed graph of trusted roots and the plurality of certificates and performs a depth-first acyclic search of the graph.

20. The server, according to claim 17, wherein validation information for all of the trusted paths is stored in a table and wherein the table is indexed using the trusted roots.

21. The server, according to claim 17, wherein validation information for all of the trusted paths is stored in a table and wherein the table is indexed using the certificates.

22. The server, according to claim 17, further comprising:

executable code, provided on the internal storage, that receives and stores the proofs for the plurality of certificates at regular intervals prior to receiving the request for path validation information.

23. The server, according to claim 17, wherein the subset of certificates includes trusted roots, authorities that issue end user certificates, and authorities that vouch for other authorities.

24. The server, according to claim 23, wherein the plurality of certificates further includes end user certificates.