Certificate revocation system

Details Certificate revocation system Certificate revocation system

2001-07-25

2004-07-20

Morse, Gregory (Department: 2134)

Electrical computers and digital processing systems: support

Multiple computer communication using cryptography

Central trusted authority provides computer authentication

C713S156000

Reexamination Certificate

active

06766450

ABSTRACT:

TECHNICAL FIELD
The present invention relates generally to secure communications and more particularly to schemes for certificate management.
BACKGROUND OF THE INVENTION
In many settings, it is necessary to certify certain data, as well as to revoke already issued certificates. For instance, in a Public-Key Infrastructure, (PKI) it is necessary to certify users' public keys.
In a digital signature scheme, each user U chooses a signing key SK
U
and a matching verification key, PK
U
. User U uses SK
U
to compute easily his digital signature of a message m, SIG
U
(m), while anyone knowing that PK
U
is U's public key can verify that SIG
U
(m) is U's signature of m. Finding SIG
U
(m) without knowing SK
U
is practically impossible. On the other hand, knowledge of PK
U
does not give any practical advantage in computing SK
U
. For this reason, it is in U's interest to keep SK
U
secret (so that only he can digitally sign for U) and to make PK
U
as public as possible (so that everyone dealing with U can verify U's digital signatures). At the same time, in a world with millions of users, it is essential in the smooth flow of business and communications to be certain that PK
U
really is the legitimate key of user U. To this end, users' public keys are “certified.” At the same time it is also necessary to revoke some of the already-issued certificates.
Certification and Revocation of Public Keys
Typically, certificates for users' public keys are produced and revoked by certifying authorities called CA's.
1
A CA can be considered to be a trusted agent having an already certified (or universally known) public key. To certify that PK
U
is U's public key, a CA typically digitally signs PK
U
together with (e.g., concatenating it with) U's name, a certificate serial number, the current date (i.e., the certification or issue date), and an expiration date.
2
The CA's signature of PK
U
is then inserted in a Directory and/or given to U himself.
1
A complete public-key infrastructure may involved other authorities (e.g., PCAs) who may also provide similiar services (e.g., they may certify the public keys to their CA's). The present inventions can be easily applied to such other authorities.
2
Before certifying U's public key, it is neccesary to preform additional steps, such as properly identifying user U. The present invention, however, does not depend on these additional steps.
Upon receiving the (alleged) digital signature of user U of a message M, SIG
U
(M), a recipient R needs to obtain a certificate for PK
U
. (indeed, SIG
U
(M) may be a correct digital signature of M with respect to some public key PK
U
, but R has no guarantee that PK
U
is indeed U's public key). Recipient R may obtain this certificate from the Directory, or from his own memory (if he has previously cached it), or from U himself. Having done this, R verifies (1) the correctness of the CA's certificate for PK
U
with respect to the CA's public key, and (2) the correctness of SIG
U
(M) with respect to PK
U
. (If the CA's public key is not universally known, or cached with R, then a certificate for this key too must be obtained.)
Certificate retrieval is thus possible, although not necessarily cheap. Unfortunately, however, this is not the only retrieval that R needs to do. Indeed, it is crucially important that R makes sure that the certificate for PK
U
has not been revoked. This check, of course, may not be needed after the certificate's expiration date, but is needed during the certificate's alleged lifetime. A user's certificate can be revoked for a variety of reasons, including key compromise and the fact that the user is no longer associated with a particular CA.
To enable a recipient to establish whether a given certificate has been revoked, it is known that each CA periodically issues and gives the Directory a Certificate Revocation List (CRL for short), in general containing an indication of all the (not yet expired) certificates originally issued by it. A CRL typically consists of the issuer's digital signature of (1) a header comprising the issuer's name (as well as the type of his signature algorithm), the current date, the date of the last update, and the date of the next update, together with (2) a complete list of revoked certificates (whose date has not yet expired), each with its serial number and revocation date. Since it is expected that a CA revokes many of her certificates, a CRL is expected to be quite long.
After performing some checks on the CA's CRL (e.g., checking the CA's digital signature, checking that the CRL has arrived at the expected time, that a certificate declared revoked in the previous CRL of that CA—and not yet expired—still is revoked in the current CRL, etc.), the Directory stores it under its CA name.
When a user queries the Directory about the revocation of a certificate issued by a given CA, the Directory responds by sending to the user the latest CRL of that CA. The user can then check the CRL signature, the CRL dates (so as to receive a reasonable assurance that he is dealing with the latest one), and whether or not the certificate of interest to him belongs to it.
While CRLs are quite effective in helping users establishing which certificates are no longer deemed valid, they are also extremely expensive, because they tend to be very long and need to be transmitted very often.
The National Institute of Standard and Technology has tasked the MITRE Corporation to study the organization and cost of a PKI for the Federal Government. This study estimates that CRLs constitute by far the largest entry in the Federal PKI's cost list. According to MITRE's estimates/assumptions, in the Federal PKI there are about three million users, each CA serves 30,000 users, 10% of the certificates are revoked,
3
CRLs are sent out bi-weekly, and, finally, the recipient of a digital signature requests certificate information 20% of the time.
4
The study envisages that each revoked certificate is specified in a CRL by means of about 9 bytes: 20 bits of serial number and 48 bits of revocation date. Thus, in the Federal PKI, each CRL is expected to comprise thousands of certificate serial numbers and their revocation dates; the header, however, has a fixed length, consisting of just 51 bytes.
3
5% because of key compromise and 5% because of change in affiliation with an organization connected to a given CA.
4
The remaining 80% of the time he will be dealing with public keys in his cache.
At 2 cents per kilobyte, the impact of CRL transmission on the estimated yearly costs of running the Federal PKI is stunning: if each federal employee verifies 100 digital signatures per day on average, then the total PKI yearly costs are $10,848 Millions, of which 10,237 Millions are due to CRL transmission. If each employee is assumed to verify just 5 digital signatures a day on average, then the total PKI yearly costs are $732 Millions, of which 563 Millions are due to CRL transmission.
The MITRE study thus suggests that any effort should be made to find alternative and cheaper CRL designs. This is indeed the goal of the present invention.
BRIEF SUMMARY OF THE INVENTION
It is thus a primary object of the present invention to facilitate management of public key certificate revocation without providing users with lists of revoked certificates.
It is another primary object of the invention to provide certificate revocation information to users of a public key communications system wherein a user can receive an individual piece of information about any public key certificate instead of a large list of revoked certificates.
It is still another object of the invention to reduce dramatically the cost of managing public key certificates in part by reducing the size and number of transmissions by and among participants in the management scheme.
It is a still further object of the invention to provide novel certificate revocation schemes wherein a certifying authority can provide

Affiliated with

Also associated with

Rating

Certificate revocation system does not yet have a rating. At this time, there are no reviews or comments for this patent.

If you have personal experience with Certificate revocation system, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Certificate revocation system will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-3222150