 |
Description  |
|
|
CROSS-REFERENCE TO RELATED APPLICATION
This application is based on Provisional application Ser. No. 60/006,038
filed Oct. 24, 1995.
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.sub.U
and a matching verification key, PK.sub.U. User U uses SK.sub.U to compute
easily his digital signature of a message m, SIG.sub.U (m), while anyone
knowing that PK.sub.U is U's public key can verify that SIG.sub.U (m) is
U's signature of m. Finding SIG.sub.U (m) without knowing SK.sub.U is
practically impossible. On the other hand, knowledge of PK.sub.U does not
give any practical advantage in computing SK.sub.U. For this reason, it is
in U's interest to keep SK.sub.U secret (so that only he can digitally
sign for U) and to make PK.sub.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.sub.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..sup.1 A CA can be considered to be a trusted agent having an
already certified (or universally known) public key. To certify that
PK.sub.U is U's public key, a CA typically digitally signs PK.sub.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..sup.2 The CA's signature of PK.sub.U is then inserted in
a Directory and/or given to U himself.
.sup.1 A complete public-key infrastructure may involved 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.
.sup.2 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.
Upon receiving the (alleged) digital signature of user U of a message M,
SIG.sub.U (M), a recipient R needs to obtain a certificate for PK.sub.U.
(Indeed, SIG.sub.U (M) may be a correct digital signature of M with
respect to some public key PK.sub.U, but R has no guarantee that PK.sub.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.sub.U with respect to the CA's public key, and (2)
the correctness of SIG.sub.U (M) with respect to PK.sub.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.sub.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,.sup.3 CRLs are sent out bi-weekly, and, finally, the recipient of
a digital signature requests certificate information 20% of the
time..sup.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.
.sup.3 5% because of key compromise and 5% because of change in affiliation
with the organization connected to a given CA.
.sup.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 a positive
and explicit statement about the validity status of each not-yet-expired
certificate.
It is another object of the invention to allow certifying authorities to
provide certificate validity information without requiring a trusted
Directory.
It is a further object of the invention to provide a certificate management
scheme wherein it is possible to prove that a given certificate was never
issued or even existed.
The foregoing has outlined some of the more pertinent objects of the
present invention. These objects should be construed to be merely
illustrative of some of the more prominent features and applications of
the invention. Many other beneficial results can be attained by applying
the disclosed invention in a different manner or modifying the invention
as will be described. Accordingly, other objects and a fuller
understanding of the invention may be had by referring to the following
Detailed Description of the preferred embodiment.
BRIEF DESCRIPTION OF THE DRAWINGS
For a more complete understanding of the present invention and the
advantages thereof, reference should be made to the following Detailed
Description taken in connection with the accompanying drawings in which:
The FIGURE is a secure communications environment according to the
invention including at least one user, one certifying authority and a
directory wherein a certificate management scheme of the present invention
is implemented.
DETAILED DESCRIPTION AND PREFERRED EMBODIMENT
By way of brief background, assume that each user U of a digital signature
scheme has a signing key SK.sub.U and a matching verification key,
PK.sub.U. User U uses SK.sub.U to compute easily his digital signature of
a message m, SIG.sub.U (m), while anyone knowing that PK.sub.U is U's
public key can verify that SIG.sub.U (m) is U's signature of m. PK.sub.U
must be the legitimate key of user U, and thus it is known to certify
users' public keys are certified. This process is now described.
Assume there are one or more certification authorities A, also known
collectively as CA's. When U goes to A to have his public key PK.sub.U
certified, she identifies him, makes sure that PK.sub.U is his public key,
and then digitally signs the pair (U, PK.sub.U), indicating that PK.sub.U
is U's legitimate public key. This signature, SIG.sub.A (U,PK.sub.U), is
verifiable by anyone, because A's public verification key, PK.sub.A, is
assumed to be universally known or otherwise, for instance, properly
certified. The string SIG.sub.A (U,PK.sub.U) constitutes a simple
certificate for PK.sub.U. Indeed, additional information can be included
in PK.sub.U 's certificate. The present invention, as will be seen, works
for any type of certificate for PKU as well as whenever certificates
concern objects other than users' public keys.
Such a certificate can be stored in a secure database or given to the user
himself. Indeed, in order to enable a recipient of the signature SIG.sub.U
(m) to verify it, U may also given the recipient PK.sub.U together with
its certificate SIG.sub.A (U,PK.sub.U). In this way, the recipient may
first verify that SIG.sub.U (m) is a legitimate digital signature of m
relative to the public key PK.sub.U (no matter to whom this key may
belong), and then check that PK.sub.U is U's legitimate public key by
verifying its certificate (i.e., by verifying A's digital signature
SIG(U,PK) with the help of the well-known public key of A).
In the above system, U may be a buyer, the recipient a vendor, and m a
payment for the purchase of a given good. The system is very convenient,
but the possibility that public key certificates have been revoked must be
addressed. If, for instance, U abuses of his digital signature power
(e.g., he stops honoring the contracts or payments he signs), then his
certificate SIG.sub.A (PK.sub.U) must, somehow, be invalidated. This is
the problem addressed by the present invention.
The preferred embodiment of the new certification/revocation system is now
described. For simplicity of presentation, it is envisioned that a
certificate revocation status is updated daily, although this is not a
requirement of the present invention. According to the present invention,
the CA has the responsibility of making and updating certificates. This is
preferably accomplished in the following manner, although as will be seen
other techniques may used as well.
As seen in the FIGURE, the certifying authority CA sends to the Directory
individual certificate revocation status information CRS.sub.i about each
of its issued, but not-yet expired certificates C.sub.1 . . . C.sub.k. The
Directory sends CRS.sub.i to a requesting user who has inquired about
certificate serial number "i" of that certifying authority.
CA OPERATIONS (Making a Certificate.) A CA produces the certificate of a
user's public key by digitally signing together traditional quantities
(e.g., the user's public key, the user name, the certificate serial
number, the type of signature algorithm of the issuer, the certification
or issue date, and the expiration date) plus two new quantities: a
(preferably 100-bit) value Y--for "YES"--and a (preferably 100-bit) value
N--for "NO". These values are, at least with very high probability, unique
to the certificate. The CA preferably generates Y and N by selecting two
secret preferably 100-bit values, respectively Y.sub.0 and N.sub.0, and
then evaluating on them a given one-way function F 365 times (i.e., as
many days in a year). Thus, Y=Y.sub.365 =F.sup.365 (Y.sub.0) and
N=N.sub.365 =F.sup.365 (N.sub.0).
The CA may select Y.sub.0 and N.sub.0 at random (in which case she must
separately store them) or pseudo-randomly (e.g., she computes them from a
secret master key--which she keeps in storage--and other inputs such as
the string YES--respectively, NO,--the certificate serial number, and the
issue date) in which case she can recompute them when needed rather than
storing them at all times.
(Updating the CRS.) Daily (but not by way of limitation), a CA sends the
Directory the following information:
(a) Preferably, a digitally signed list of the serial numbers of all
not-yet-expired certificates issued by her together with the current day;
(b) Preferably, the new certificates made that day; and
(c) For each not-yet-expired certificate made by her, she sends a
preferably 100-bit value computed as follows. Assume that the current day
is the ith date in some standard reference (e.g., the ith day of the year,
the ith date after the issue date of the certificate, and so on). Then, if
the certificate was valid and continues to be valid, she sends the value
Y.sub.365-i (which she may easily compute by evaluating F 365-i times on
input Y.sub.0). If the certificate ceases to be valid that very day, she
sends the value N.sub.364 (which she can easily compute starting with
N.sub.0). If the certificate was valid for the first j days after
issuance, but has been invalid for the latest i-j-1 days, then preferably
she sends the value N.sub.365-(i-j) (which she can also easily compute
from N.sub.0).
Note 1: Since there are one-way functions that are extremely easy to
evaluate, updating a given CRS is very efficient, and at most 120 bits
about it are preferably sent to the Directory; e.g., the certificate
serial number (i.e., 20 bits) and a 100-bit (YES/NO) value. Alternatively,
rather than sending a YES-value, a CA can sign the certificate's serial
number together with the new date i and YES (if the certificate continues
to be valid). Also, rather than sending a NO-value if the certificate is
no longer valid, the CA can directly sign that the certificate has been
revoked together with additional information (e.g., it may sign the
certificate serial number together with the string NO and the revocation
date, and/or additional information). In this case, such a revocation
signature need not be sent at every subsequent CRS update.
Note 2: Handling the Y/N values can be done in several ways; for instance,
but without limitation, by using just one or more values rather two
YES-NO-values, or by using trap-door functions, etc. Also, rather than
just a one-way function, a CA C may use a one-way hash function H. For
instance, she may choose Y.sub.1 =H(Y.sub.0,C,1), Y.sub.2 =H(Y.sub.1,C,2),
and so on. If desired, the hash function may have less or additional
inputs, such as the issue date of the certificate.
Note 3: The amount of information sent by a CA to the Directory at each
update is roughly twenty times as long as a CRL. Indeed, in a CRL update,
the CA sends, on average, 9 bytes (72 bits) for 10% of the certificates.
For a CRS update, the CA preferably sends 120 bits for each certificate in
Step (c), and just 20 bits per certificate in Step (a). The number of bits
transmissed in Step (b) is roughly the same for both systems.
Note 4: Calling the Y.sub.i and N.sub.j respectively YES- and NO-values,
one may ensure that no YES-value coincides with a NO-value. In practice,
however, this is unnecessary, because the probability of this happening if
the function F is well-chosen is miniscule. (Indeed, for suitable choice
of the parameters, it can be made much less than the probability that the
digital signature algorithm of a CA is broken.)
DIRECTORY OPERATIONS.
(Response to CRS Update). For every CA, the Directory preferably stores all
not-yet-expired certificates issued by her, organized by serial number,
and for each of them it also stores its latest YES-value and NO-value (or
the revocation signature described above). The Directory preferably
performs the following verification steps.
The Directory checks that each newly received certificate is well-formed
and properly signed. (In particular, it checks that the
certification/issue date coincides with the current day.)
The Directory checks that the latest list of not-yet-expired certificates
of every CA is fine. (In particular, it checks that its date coincides
with the current one, that the list is complete, and that no certificate
declared invalid in the previous list is declared valid now.)
For every certificate, the Directory, upon receiving its latest 100-bit
value V, performs the following check. Assume that the current day is i
days after the certification date, and that the stored YES- and NO-values
of the certificate are, respectively, Y' and N'..sup.5 Then, the Directory
verifies whether F(V)=Y', if V is a YES value, and whether F(V)=N',
otherwise.
.sup.5 If all was done properly, these values should, according to our
conventions, be Y'=Y.sub.365-i-j and N'=N.sub.365-i-j respectively.
(Response to Users' Inquiries.) Assume, for simplicity, that recipient
users receive the certificates of their sending signers from the senders
themselves. Thus, users make Directory queries just for determining the
validity status of certificates already known to them.
When a user U inquires about the status of a given certificate (e.g., by
specifying its CA and its serial number), the Directory retrieves and
sends to U the latest YES-value and the latest NO-value of that
certificate.
Should U inquire about a serial number that does not correspond to any
not-yet-expired certificate issued by the CA, then the Directory sends U
the latest, digitally signed, serial-number list of that CA or any other
proof that the inquired-about certificate "does not exist."
Note 5: If a CRL-based system was adopted instead, when a query about a
"non-existing" certificate is made, it is proposed herein that the
Directory should provide U with a digital signature indicating that the
certificate "does not exist."
Note 6: The Directory is not trusted very much, because it cannot "make
valid" a revoked certificate, nor can it "make revoked" a valid one.
Assume the i is the current date, and that a certificate has expired at
some date j.ltoreq.i. Then, the CA has provided so far the Directory with
at most j-1 F-inverses of Y.sub.365, that is, with the Y-values Y.sub.365,
. . . , Y.sub.365-(j-1). Thus, if the Directory wishes to make the
certificate look valid at date i, it must invert F (at least once) on
Y.sub.365-(j-1), which it cannot do because F is a one-way function.sup.6
.sup.6 The CA does not know how to invert F in general. She only knows how
to invert it on the Y.sub.i, for i>0, because she chose Y.sub.0 and
N.sub.0, and constructed the YES and NO values by evaluating F, on the
easy direction, starting from Y.sub.0 and N.sub.0. Thus the CA can invert
F on on Y.sub.365 by either storing all intermediate Y-values, or quickly
recomputing them from Y.sub.0.
Assume now that a certificate is valid at date i, and the Directory wishes
to convince a user that it has been revoked at a date lesser than or equal
to i. In order to do so, it must invert F at least once on the
certificate's N.sub.365 value, which again it cannot do because F is a
one-way function.
Assume now that the current date is i, and that the certificate ceased to
be valid at date j<i, but the Directory wishes to convince a user that the
certificate was actually revoked at a different date..sup.7 Notice that,
at the current date k, the total number of "F-inversions" divulged by the
CA for a certificate revoked at time j<i, is still j Y-values (Y.sub.365,
. . . , Y.sub.365-j) and i-j N-values (i.e., N.sub.365, . . . ,
N.sub.365-(i-j)). If received at the current date i, this information
specifies that the revocation date is j+1, that is, 1 plus the number of
divulged Y-inversions. Indeed, if at current date i the Directory wished
to pretend convincingly that the certificate was revoked at a date earlier
than j, it should release at least one less Y-inverse and at least one
more N-inverse, which it cannot do. Similarly, it at current date i the
Directory wishes to fake that the certificate was revoked after date i, it
should produce at least one more Y-inverse, which it cannot do
either..sup.8
.sup.6 For instance, it may try to make trouble for someone who has
accepted a signature relative to a public key that was valid at data d<j,
by convincing someone else that the certificate of that public key was
already revoked by date d.
.sup.7 For instance, it may try to make trouble for someone who has
accepted a signature relative to a public key that was valid at data d<j,
by convincing someone else that the certificate of that public key was
already revoked by date d.
.sup.8 This information, however, does not prove the revocation date if
examined at a later date, D>i. Indeed, the revocation date could be any
date d between j and j+(D-i). Assume therefore that a malicious person has
received at date D from the Directory Y.sub.365-d and N.sub.365-(D-d).
Then, he may evaluate F on the received YES-value so as to obtain the jth
inverse of Y.sub.365, end may evaluate F on the received NO-value so as to
compute the (i-j)th F-inverse of N.sub.365. To prove what the revocation
date is in a way that is verifiable at any point in time, see the
discussion below.
For this reason it is not recommended that the CA signs the YES- and
NO-values of every CRS update. Indeed, Y and N are signed within the
certificate, and only the CA may easily invert F on them a few times. Thus
any value V on which the one-way function F, evaluated at most 365 times,
yields Y, must have been computed by the CA.
The latest YES or NO-values may however be digitally signed if desired.
USER OPERATIONS.
Let Y and N be, respectively, the YES-value and the NO-value of the
certificate the inquiring user U is interested in, and let the current
date be i days after the certificate's issue date.
If the Director sends him Y' and N' (the alleged latest YES- and NO-value
of the certificate), preferably then user U performs the following check.
First he verifies that by evaluating F on Y' and N' he obtains,
respectively, Y and N within a total of i F-evaluations. (As usual, we let
F.sup.0 denote the identity function.)
Then, letting a and b be the number of F-evaluations needed to obtain,
respectively, Y from Y' and N from N', he verifies that a+b=i.
If the Directory claims that the certificate "does not exist" by sending
him the CA's signed list of serial numbers of not-yet-expired
certificates, or an alternative proof, then U checks the CA's digital
signatures, and that the serial number of interest to him does not appear
in the list or checks the alternative proof.
BENEFITS AND ANALYSIS
The novel system enjoys three main advantages over the traditional CRL.
First, it saves dramatically on bit transmissions and costs. In this
regard, recall that there are few CRS/CRL updates. Indeed, they typically
occur bi-weekly and are performed by the CAs which are few in numbers. By
contrast, there are very many | | |
