Tree-based certificate revocation system

Details Tree-based certificate revocation system Tree-based certificate revocation system

1997-11-26

2001-10-09

Barron, Jr., Gilberto (Department: 2132)

Electrical computers and digital processing systems: support

Multiple computer communication using cryptography

Central trusted authority provides computer authentication

C713S157000

Reexamination Certificate

active

06301659

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.
C
ERTIFICATION AND
R
EVOCATION OF
P
UBLIC
K
EYS
.
Typically, certificates for users' public keys are produced and revoked by certifying authorities called CA's. A complete public-key infrastructure may involve other authorities (e.g., PCAS) who may also provide similar services (e.g., they may certify the public keys of their CA's). The present inventions can be easily applied to such other authorities. 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. (Before certifying U's public key, it is necessary to perform additional steps, such as properly identifying user U. The present invention, however, does not depend on these additional steps). The CA's signature of PK
u
is then inserted in a Directory and/or given to U himself.
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 Standards 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 MITRES'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 (5% because of key compromise and 5% because of change in affiliation with the organization connected to a given CA). CRLs are sent out bi-weekly, and, finally, the recipient of a digital signature requests certificate information 20% of the time. (The remaining 80% of the time he will be dealing with public keys in his cache). 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.
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
To avoid the dramatic CRL costs, a novel Certification Revocation System is described, where requesting users no longer receive the latest list of revoked certificates (of a given CA). The scheme utilizes a known tree-based authentication technique in a novel way to overcome the problems associated with the prior art.
It is thus a primary object of this invention to provide certificate management without providing CRL's to a user requesting information about the certificate (e.g, its validity). Although special CRL's still may be used between CA's and the Directory in this scheme, the tree-based technique allows the Directory to convince users of whether or not a given certificate is still valid in a way that is essentially individualized, and thus quite convenient.


REFERENCES:
patent: Re. 34954 (199

Affiliated with

Also associated with

Rating

Tree-based 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 Tree-based certificate revocation system, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Tree-based certificate revocation system will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-2558025