Electrical computers and digital processing systems: support – Multiple computer communication using cryptography – Central trusted authority provides computer authentication
Reexamination Certificate
1998-07-28
2002-08-27
Smithers, Matthew (Department: 2131)
Electrical computers and digital processing systems: support
Multiple computer communication using cryptography
Central trusted authority provides computer authentication
Reexamination Certificate
active
06442689
ABSTRACT:
FIELD OF THE INVENTION
This invention relates generally to data security, information security, and cryptography, and specifically to systems for constructing digitally-signed lists and determining whether particular values.are present on such lists. The invention has specific application to revocation of digital certificates or other types of digital data items and for determining whether such data items have been revoked.
DESCRIPTION OF THE BACKGROUND ART
Asymmetric (public key) cryptologic techniques are widely used in security protocols for applications such as secure e-mail, electronic commerce, encrypted voice and video communications, and security on the World Wide Web. The RSA cryptosystem, described in U.S. Pat. No. 4,405,829 to Rivest et al (1983), and the Digital Signature Algorithm (DSA), described in U.S. Pat. No. 5,231,668, to Kravitz, are examples of asymmetric functions. Asymmetric cryptosystems systems typically involve a secret private key, which is used for digital signing or decryption, and a non-confidential public key derived from the private key, which is used for signature verification or encryption. For general information about RSA, DSA, and other asymmetric cryptosystems, the reader is referred to Applied Cryptography.
Before using a public key to encrypt a confidential message or verify a signature, a party in an electronic communications protocol generally must confirm the identity of the party holding the private key. An electronic communications protocol defines conventions allowing two or more computers or other electronic devices to exchange digital data or messages via a communications channel. Without such confirmation, an attacker could substitute a legitimate public key with another for which the attacker knows the private key. Digital certificates are the most common solution to this problem. The holder of the private key provides its corresponding public key to a widely-trusted Certificate Authority (CA) along with acceptable identification. The CA then issues a certificate, which typically consists of a digital signature on a specially-formatted block of data containing the user's name, the user's public key, the certificate issuance and expiration dates, and the certificate serial number. The recipient of a digital certificate who trusts the issuing CA can use the CA's (already trusted) public key to verify the signature. If the signature is valid and if the CA is trustworthy, the recipient can trust that the person identified in the certificate holds the private key corresponding to the public key in the certificate. The ISO 9594-8 standard defines techniques and data formats for computing and verifying digital signatures and certificates.
Certificates often need to be revoked due to unexpected events such as compromise, theft, or loss of the device containing the private key. A certificate might also need to be revoked if a user has lost the privileges granted by the certificate. In general, a certificate's status might be good, revoked, or pending, as well as other possibilities that will be appreciated by those skilled in the art.
In large open networks such as the Internet, certificate status determination, specifically certificate revocation, presents enormous challenges. The Internet is expected to have hundreds of millions of users worldwide soon. It is desirable that certificate revocation messages propagate as quickly as possible to all users who might otherwise accept the invalid certificate. Thus, there are difficult design constraints which a successful system must satisfy:
1. Network applications are sensitive to latency. A good solution should minimize the number of additional network connections and data exchanges required.
2. The system must work on a global scale and work on a broad range of systems with different levels of connectivity.
3. The system must be distributable so that critical information can be cached in many locations at once to minimize the number of long-distance network connections.
4. The system must be cryptographically secure.
Previous certificate revocation mechanisms, such as ISO 9594-8, use a type of digitally-signed structure called a Certificate Revocation List (CRL) which is issued periodically by the CA and lists the serial numbers of certificates issued by the CA which have been revoked.
FIG. 1
shows the structure of a typical CRL
101
, which consists of the issuer's name, a field identifying the signature algorithm, the date and time of issuance, and a list of revoked certificates, followed by a digital signature of the above information. To determine if a particular certificate is revoked, one obtains an up-to-date CRL from the appropriate CA, verifies that the digital signature in the CRL is valid, then searches the list of revoked certificates to determine whether the certificate in question.is revoked. If the certificate is not on the list, it is assumed to be valid.
Because the complete CRL must be obtained and verified to determine the revocation status of a single certificate, CRLs do not scale well to large networks. In particular, existing certificate revocation mechanisms suffer from a number of disadvantages:
(a) CRLs can become extremely large, making them inefficient to transmit or process. For example, a very large system might have several million revoked certificates, resulting in CRLs which are many megabytes in size. To determine whether a particular certificate is valid, one must download a recent CRL in its entirety and process the entire list to verify the digital signature. For a large network, the required network bandwidth can be prohibitively large, especially if every user needs to download new CRLs often. The time required to process a large list can also be an issue.
(b) Only mechanisms recognized and supported by the certificate recipient can be used to revoke certificates. In most cases, only revocations issued by the CA are accepted. Additional revocation mechanisms cannot be added easily.
(c) Because CAs are entrusted with both certificate issuance and revocation, physical destruction of a CA's private key could result in a situation where certificates could no longer be revoked without revoking the CA's public key.
(d) Verifiers must be able to obtain up-to-date CRLs from every supported CA. Certificate chaining makes this particularly difficult since there can easily be an extremely large number of CAs and multiple CAs per certificate chain.
Present techniques for determining whether types of data other than certificates are present on digitally-signed lists suffer from the same scalability problems. On large networks such as the Internet such systems will typically suffer from poor latency and extremely large bandwidth requirements. These limitations arise because existing techniques either require active network connections to a trusted server at transaction time or require replication of CRLs or other digitally-signed lists containing all elements of the list.
SUMMARY OF THE INVENTION
Accordingly, it is an object of the invention to greatly reduced the processing effort, network bandwidth, network latency, data storage, and data replication requirements needed to determine whether a particular certificate has been revoked. In particular, the invention allows certificate status to be determined without knowledge of the entire list of revoked certificates and without having to search the entire list of revoked certificates.
Another object of the invention is to simplify the addition of new revocation mechanisms, such as revocation by certificate holders, without altering existing revocation mechanisms.
Another object of the invention is to allow revocations from many CAs to be included efficiently in a single database, thereby allowing a single trusted source for certificate revocation messages.
Another object of the invention is to provide a certificate revocation system whose operation is open to public scrutiny to ensure that certificates are not maliciously revoked and that revoked certificates are not marked as
Smithers Matthew
ValiCert, Inc.
LandOfFree
Apparatus and method for demonstrating and confirming the... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Apparatus and method for demonstrating and confirming the..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Apparatus and method for demonstrating and confirming the... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2968017