Apparatus and method for demonstrating and confirming the status of a digital certificates and other data

• US 6,442,689 B1
• Filed: 07/28/1998
• Issued: 08/27/2002
• Est. Priority Date: 05/14/1996
• Status: Expired due to Term

• Current Assignee: Axway Incorporated (Axway Software SA)
• Original Assignee: Valicert, Inc. (Axway Software SA)
• Inventors: Kocher, Paul Carl
• Primary Examiner(s): Smithers, Matthew
• Application Number:
  US09/123,732
• Time in Patent Office: 1,491 Days
• Field of Search: 713/158, 713/155, 713/156, 713/157, 713/168, 713/175, 713/176, 380/286
• US Class Current: 713/158
• CPC Class Codes: H04L 2209/30 Compression, e.g. Merkle-Damgard construction
• CPC Class Codes: H04L 2209/56 Financial cryptography, e.g. electronic payment or e-cash
• CPC Class Codes: H04L 9/3236 using cryptographic hash functions
• CPC Class Codes: H04L 9/3247 involving digital signatures
• CPC Class Codes: H04L 9/3268 using certificate validation, registration, distribution or revocation, e.g. certificate revocation list [CRL]
• CPC Class Codes: H04L 9/50 using hash chains, e.g. blockchains or hash trees

Abstract

Methods and apparatuses for having a single trusted party collect digitally signed lists (e.g., CRLs) from different trusted data item issuers (e.g., CAs). According to one embodiment, the trusted third party collects the digitally signed lists. The trusted third party then associates with sorted entries from each of the digitally signed lists a representation of the trusted data item issuer that provided the digitally signed list. The trusted third party cryptographically manipulates the sorted entries and associated representations. The trusted party electronically transmits at least one of the entries on one of the digitally signed lists and part of the cryptographically manipulated data onto a network.

Claims

1. A computer implemented method comprising:

a trusted party collecting certificate revocation lists from multiple certificate issuers;

said trusted party forming a single list from the certificate revocation lists;

said trusted party cryptographically manipulating the single list to form a single structure that cryptographically demonstrates whether any given digitally signed data item is identified by any one of said certificate revocation lists and that provides a relative level of assurance to other parties which have a part of said single structure but do not have the entire single structure that said part belongs to said single structure formed by the trusted party; and

electronically transmitting at least part of the single structure onto a network.

2. The method of claim 1, further comprising:

said certificate issuers transmitting said certificate revocation lists to said trusted party.

3. The method of claim 1, wherein:

said method further includes receiving a plurality of request messages from said other parties as to status information regarding specific digital certificates issued by the certificate issuers; and

said electronically transmitting includes transmitting, in response to each of the plurality of request messages, a response message that includes the part of the single structure required to indicate whether the one or more specific digital certificates from said request message are represented on any of said certificate revocation lists.

4. The method of claim 1, wherein a party with a pair of adjacent entries on a sorted version of the single list and only the certain of the single structure that is associated with the pair of entries can verify whether a plurality of digital certificates are identified on any of said certificate revocation lists.

5. The method of claim 1, wherein said trusted party cryptographically manipulating the single list to form the single structure comprises:

deriving from said single list a hash tree having at least one root node; and

digitally signing the at least one root node with a private key.

6. The method of claim 5, wherein said deriving from said single list said tree comprises:

forming leaf nodes of the tree from entries on said single list.

7. The method of claim 1, wherein said trusted party forming said single list comprises:

sorting said single list keeping entries from different ones of said certificate revocation lists in separate regions.

8. The method of claim 7, wherein said trusted party forming comprises:

inserting markers at the beginning and end of each region of the single sorted list corresponding to each certificate issuer.

9. The method of claim 7, wherein said forming comprises:

associating with each region of the single sorted list a representation identifying the certificate issuer.

10. The method of claim 9, wherein said associating includes:

hashing a name of each of said certificate issuers; and

for each region of the single sorted list corresponding to each certificate issuer, concatenating that hashed certificate issuer name with each entry in that region.

11. The method of claim 1, wherein said trusted party forming said single list comprises:

placing a sorted version of the entries from each certificate revocation list in a separate region of said single list.

12. The method of claim 11, wherein said trusted party cryptographically manipulating the single list to form the single structure comprises:

deriving a plurality of ranges from adjacent entries in the separate regions of said single list; and

cryptographically manipulating data derived from the plurality of ranges.

13. The method of claim 12, wherein said step of deriving the plurality of ranges comprises:

selecting one of adjacent pairs of entries in the separate regions of said single list as endpoints.

14. The method of claim 13, wherein said cryptographically manipulating data derived from the plurality of ranges comprises:

forming a tree having leaf nodes derived from the plurality of ranges.

15. The method of claim 14, wherein each leaf node specifies one of one range, an endpoint of one range, a hashed range, and a hashed endpoint of one range.

16. The method of claim 12, wherein said plurality of ranges includes a range that spans from the end of one to the beginning of another of said separate regions.

17. The method of claim 12, wherein said trusted part forming said single list further comprises:

inserting markers at the beginning and end of each region of the single sorted list, wherein said plurality of ranges includes a range whose endpoints are two adjacent ones of said markers.

18. A computer implemented method comprising:

a trusted third party collecting a first and second digitally signed lists identifying data items respectively issued from a first and second trusted data item issuer;

said trusted third party associating with sorted entries from each of the digitally signed lists a representation of the identity of the trusted data item issuer which provided the digitally signed list;

said trusted third party forming a combined list from the entries and associated representations;

said trusted third party cryptographically manipulating the entries from the combined list in a manner that provides a relative level of assurance to other parties which do not have the entire combined list that the trusted third party formed the resulting cryptographically manipulated data; and

electronically transmitting at least one of the entries on one of the digitally signed lists and part of the cryptographically manipulated data onto a network.

19. The method of claim 18, further comprising:

said first and second trusted data item issuers respectively transmitting said first and second digitally signed lists to said trusted third party.

20. The method of claim 18, further comprising:

receiving a request message from another party as to status information regarding a particular data item issued by one of the first and second trusted data item issuers; and

said step of electronically transmitting includes transmitting a response message that includes at least one of the entries on one of the digitally signed lists and only part of the cryptographically manipulated data.

21. The method of claim 18, wherein a party with a pair of adjacent entries on the combined list and only certain of the cryptographically manipulated data that is associated with the pair of entries can verify whether a plurality of data items are on any of said first and second digitally signed lists.

22. The method of claim 18, wherein:

said trusted party cryptographically manipulating includes,

said trusted third party deriving a single piece of data from all of the entries on said combined list, and

said trusted third party digitally signing said single piece of data; and

said electronically transmitting comprises transmitting the digitally signed single piece of data onto said network.

23. The method of claim 18, wherein said trusted third party cryptographically manipulating the list comprises:

deriving from said combined list a hash tree having at least one root node; and

digitally signing the at least one root node with a private key.

24. The method of claim 23, wherein said deriving from said combined list said hash tree comprises:

deriving a plurality of ranges from adjacent pairs of entries on said combined list; and

forming leaf nodes of the tree from the plurality of ranges.

25. The method of claim 18, wherein said trusted third party cryptographically manipulating the combined list comprises:

for each of a plurality of adjacent pairs of entries in said combined list, separately signing data derived from that adjacent pair of entries.

26. The method of claim 18, wherein said trusted third party forming comprises:

placing the sorted entries and associated representations from each of the digitally signed lists in a separate region of said combined list; and

inserting markers at the beginning and end of each of said regions of the combined list.

27. The method of claim 26, wherein said trusted third party associating comprises:

hashing a name of each of said trusted data item issuers; and

for each region of the combined list corresponding to each trusted data item issuer, concatenating that hashed trusted data item issuer'"'"'s name with each entry in that region.

28. The method of claim 26, wherein said trusted third party cryptographically manipulating further comprises:

deriving a range from each pair of adjacent entries of said combined list; and

cryptographically manipulating the ranges to form the resulting cryptographically manipulated data.

29. The method of claim 28, wherein said plurality of ranges includes a range whose endpoints are two adjacent ones of said markers.

30. The method of claim 18, wherein said data items identify digital certificates sharing an attribute.

31. The method of claim 30, wherein said attribute is that the digital certificates are one or more of revoked, valid, suspended, and pending.

32. The method of claim 18, wherein said data items identify one of revoked digital certificate chains, digital signatures, signatures on binary code, and revoked credit cards.

33. A computer implemented method comprising:

a trusted third party collecting a first and second digitally signed lists identifying data items respectively issued from a first and second trusted data item issuer;

said trusted third party associating with sorted entries from each of the digitally signed lists a representation of the identity of the trusted data item issuer which provided the digitally signed list;

said trusted third party forming a single list from the entries and associated representations;

said trusted party cryptographically manipulating the single list to form a tree with at least one digitally signed root node that provides a relative level of assurance to other parties which do not have the entire single list that the trusted third party formed the single list; and

electronically transmitting at least said digitally signed root node and a part of said tree required to generate said root node onto a network.

34. The method of claim 33, further comprising:

said first and second trusted data items issuers respectively transmitting said first and

second digitally signed lists to said trusted third party.

35. The method of claim 33, further comprising:

receiving a request message from another party as to status information regarding a particular data item issued by one of the first and second trusted data item issuers; and

said step of electronically transmitting includes transmitting a response message that includes at least one of the entries on one of the digitally signed lists and only part of the cryptographically manipulated data.

36. The method of claim 33, wherein a party with a pair of adjacent entries on the single list and only certain of the cryptographically manipulated data that is associated with the pair of entries can verify the trusted third party generated said single list and whether a plurality of data items are on any of said first and second digitally signed lists.

37. The method of claim 33, wherein said digitally signed lists are certificate revocation lists and said first and second trusted data item issuers are certificate issuers.

38. The method of claim 33, wherein said trusted third party cryptographically manipulating the single list to form said tree comprises:

deriving a plurality of ranges from adjacent pairs of entries on said single list; and

forming leaf nodes of the tree from the plurality of ranges.

39. The method of claim 38, wherein each leaf node specifies one of one range, an endpoint of one range, a hashed range, and a hashed endpoint of one range.

40. The method of claim 33, wherein said trusted third party forming the single list comprises:

placing the sorted entries and associated representations from each of the digitally signed lists in a separate region of said single list; and

inserting markers at the beginning and end of each of said regions.

41. The method of claim 40, wherein said trusted third party associating comprises:

hashing a name of each of said trusted data item issuers; and

for each region of the single sorted list corresponding to each trusted data item issuer, concatenating that hashed trusted data item issuer'"'"'s name with each entry in that region.

42. The method of claim 40, wherein said trusted third party cryptographically manipulating further comprises:

deriving a range from each pair of adjacent entries of said combined list; and

cryptographically manipulating the ranges to form the resulting cryptographically manipulated data.

43. The method of claim 42, wherein said ranges includes a range whose endpoints are two adjacent ones of said markers.

44. The method of claim 33, wherein said data items identify digital certificates sharing an attribute.

45. The method of claim 44, wherein said attribute is that the digital certificates are one or more of revoked, valid, suspended, and pending.

46. The method of claim 33, wherein said data items identify one of revoked digital certificate chains, digital signatures, signatures on binary code, and revoked credit cards.

47. A computer implemented method comprising:

a trusted third party collecting a first and second certificate revocation list identifying digital certificates that were respectively issued from a first and second certificate issuer and that have been revoked;

said trusted third party associating with sorted entries from each of the certificate revocation lists a representation of the identity of the certificate issuer which provided the certificate revocation list, wherein adjacent pairs of sorted entries identify whether any given digital certificate is on any one of said lists;

said trusted third party cryptographically manipulating the sorted entries and associated data to form cryptographically manipulated data that provides a relative level of assurance to other parties which do not have all the sorted entries that the trusted third party formed the cryptographically manipulated data; and

electronically transmitting a representative of at least one of the entries and the part of the cryptographically manipulated data associated with that entry onto a network.

48. The method of claim 47, further comprising:

said certificate issuers transmitting said certificate revocation lists to said trusted third party.

49. The method of claim 47, wherein:

said method further includes receiving a plurality of request messages from other parties as to status information regarding digital certificates issued by the certificate issuers; and

said electronically transmitting includes transmitting, in response to each of the plurality of request messages, a response message that includes at least one of the entries on one of the certificate revocation list and part of the cryptographically manipulated data required to respond to that request message.

50. The method of claim 47, wherein a party with one of the adjacent pairs of sorted entries and only certain of the cryptographically manipulated data that is associated with that adjacent pair of entries can verify whether a plurality of digital certificates are on any of said certificate revocation lists.

51. The method of claim 47, wherein:

said cryptographically manipulating includes,

said trusted third party deriving a single piece of data from all of the sorted entries, and

digitally signing said single piece of data; and

said electronically transmitting comprises transmitting the digitally signed single piece of data onto the network.

52. The method of claim 47, wherein said trusted third party cryptographically manipulating comprises:

deriving from said sorted entries and associated representations a hash tree having at least one root node; and

digitally signing the at least one root node with a private key.

53. The method of claim 52, wherein said deriving from said single list said hash tree comprises:

forming leaf nodes of the tree from the sorted entries.

54. The method of claim 52, wherein said deriving from said single list said tree comprises:

deriving a plurality of ranges from adjacent pairs of sorted entries; and

forming leaf nodes of the tree from the plurality of ranges.

55. The method of claim 47, wherein said trusted third party cryptographically manipulating comprises:

for each of a plurality of adjacent pairs of sorted entries, separately signing data derived from that adjacent pair of entries.

56. The method of claim 47, wherein said trusted third party forming said single list comprises:

inserting markers at the beginning and end of the set of sorted entries corresponding to each certificate issuer to form a single list.

57. The method of claim 56, wherein said trusted third party cryptographically manipulating further comprises:

deriving a range from each pair of adjacent entries of said single list; and

cryptographically manipulating the ranges to form the resulting cryptographically manipulated data.

58. The method of claim 57, wherein said ranges includes a range whose endpoints are two adjacent ones of said markers.

59. The method of claim 47, wherein said trusted third party associating includes:

hashing each certificate issuer name; and

for each certificate issuer, concatenating that hashed certificate issuer name with each entry from that certificate issuer.

60. A machine-readable medium that provides instructions which, when executed by a machine, cause said machine to perform operations comprising:

a trusted party collecting certificate revocation lists from multiple certificate issuers;

said trusted party forming a single list from the certificate revocation lists;

said trusted party cryptographically manipulating the single list to form a single structure that cryptographically demonstrates whether any given digitally signed data item is identified by any one of said certificate revocation lists and that provides a relative level of assurance to other parties which have a part of said single structure but do not have the entire single structure that said part belongs to said single structure formed by the trusted party; and

electronically transmitting at least part of the single structure onto a network.

61. The machine-readable medium of claim 60, further comprising:

said certificate issuers transmitting said certificate revocation lists to said trusted party.

62. The machine-readable medium of claim 60, wherein:

said operations further include receiving a plurality of request messages from said other parties as to status information regarding specific digital certificates issued by the certificate issuers; and

said electronically transmitting includes transmitting, in response to each of the plurality of request messages, a response message that includes the part of the single structure required to indicate whether the one or more specific digital certificates from said request message are represented on any of said certificate revocation lists.

63. The machine-readable medium of claim 60, wherein a party with a pair of adjacent entries on a sorted version of the single list and only the certain of the single structure that is associated with the pair of entries can verify whether a plurality of digital certificates are identified on any of said certificate revocation lists.

64. The machine-readable medium of claim 60, wherein said trusted party cryptographically manipulating the single list to form the single structure comprises:

deriving from said single list a hash tree having at least one root node; and

digitally signing the at least one root node with a private key.

65. The machine-readable medium of claim 64, wherein said deriving from said single list said tree comprises:

forming leaf nodes of the tree from entries on said single list.

66. The machine-readable medium of claim 60, wherein said trusted party forming said single list comprises:

sorting said single list keeping entries from different ones of said certificate revocation lists in separate regions.

67. The machine-readable medium of claim 66, wherein said trusted party forming comprises:

inserting markers at the beginning and end of each region of the single sorted list corresponding to each certificate issuer.

68. The machine-readable medium of claim 66, wherein said forming comprises:

associating with each region of the single sorted list a representation identifying the certificate issuer.

69. The machine-readable medium of claim 68, wherein said associating includes:

hashing a name of each of said certificate issuers; and

for each region of the single sorted list corresponding to each certificate issuer, concatenating that hashed certificate issuer name with each entry in that region.

70. The machine-readable medium of claim 60, wherein said trusted party forming said single list comprises:

placing a sorted version of the entries from each certificate revocation list in a separate region of said single list.

71. The machine-readable medium of claim 70, wherein said trusted party cryptographically manipulating the single list to form the single structure comprises:

deriving a plurality of ranges from adjacent entries in the separate regions of said single list; and

cryptographically manipulating data derived from the plurality of ranges.

72. The machine-readable medium of claim 71, wherein said step of deriving the plurality of ranges comprises:

selecting one of adjacent pairs of entries in the separate regions of said single list as endpoints.

73. The machine-readable medium of claim 71, wherein said cryptographically manipulating data derived from the plurality of ranges comprises:

forming a tree having leaf nodes derived from the plurality of ranges.

74. The machine-readable medium of claim 73, wherein each leaf node specifies one of one range, an endpoint of one range, a hashed range, and a hashed endpoint of one range.

75. A machine-readable medium that provides instructions which, when executed by a machine, cause said machine to perform operations comprising:

a trusted third party collecting a first and second certificate revocation list identifying digital certificates that were respectively issued from a first and second certificate issuer and that have been revoked;

said trusted third party associating with sorted entries from each of the certificate revocation lists a representation of the identity of the certificate issuer which provided the certificate revocation list, wherein adjacent pairs of sorted entries identify whether any given digital certificate is on any one of said lists;

said trusted third party cryptographically manipulating the sorted entries and associated data to form cryptographically manipulated data that provides a relative level of assurance to other parties which do not have all the sorted entries that the trusted third party formed the cryptographically manipulated data; and

electronically transmitting a representative of at least one of the entries and the part of the cryptographically manipulated data associated with that entry onto a network.

76. The machine-readable medium of claim 75, further comprising:

said certificate issuers transmitting said certificate revocation lists to said trusted third party.

77. The machine-readable medium of claim 75, wherein:

said operations further include receiving a plurality of request messages from other parties as to status information regarding digital certificates issued by the certificate issuers; and

said electronically transmitting includes transmitting, in response to each of the plurality of request messages, a response message that includes at least one of the entries on one of the certificate revocation list and part of the cryptographically manipulated data required to respond to that request message.

78. The machine-readable medium of claim 75, wherein a party with one of the adjacent pairs of sorted entries and only certain of the cryptographically manipulated data that is associated with that adjacent pair of entries can verify whether a plurality of digital certificates are on any of said certificate revocation lists.

79. The machine-readable medium of claim 75, wherein:

said cryptographically manipulating includes,

said trusted third party deriving a single piece of data from all of the sorted entries, and

digitally signing said single piece of data; and

said electronically transmitting comprises transmitting the digitally signed single piece of data onto the network.

80. The machine-readable medium of claim 75, wherein said trusted third party cryptographically manipulating comprises:

deriving from said sorted entries and associated representations a hash tree having at least one root node; and

digitally signing the at least one root node with a private key.

81. The machine-readable medium of claim 80, wherein said deriving from said single list said hash tree comprises:

forming leaf nodes of the tree from the sorted entries.

82. The machine-readable medium of claim 80, wherein said deriving from said single list said tree comprises:

deriving a plurality of ranges from adjacent pairs of sorted entries; and

forming leaf nodes of the tree from the plurality of ranges.

83. The machine-readable medium of claim 75, wherein said trusted third party cryptographically manipulating comprises:

for each of a plurality of adjacent pairs of sorted entries, separately signing data derived from that adjacent pair of entries.

84. The machine-readable medium of claim 75, wherein said trusted third party forming said single list comprises:

inserting markers at the beginning and end of the set of sorted entries corresponding to each certificate issuer to form a single list.

85. The machine-readable medium of claim 75, wherein said trusted third party associating includes:

hashing each certificate issuer name; and

for each certificate issuer, concatenating that hashed certificate issuer name with each entry from that certificate issuer.