 |
Claims  |
|
|
What is claimed is:
1. A method for an authority to provide authenticated information about a
plurality of issued certificates, comprising the steps of:
(a) generating a data string that includes information identifying all the
plurality of issued certificates; and
(b) having the authority authenticate the data string.
2. A method according to claim 1, wherein the data string further includes
information indicating a date of authentication of the data string.
3. A method according to claim 1, wherein the data string further includes
information indicating a date of issuance of at least one of the
certificates.
4. A method according to claim 1, wherein the data string further includes
certificate information about a subset of the issued certificates.
5. A method according to claim 4, wherein the certificate information
includes at least one of: revocation information and validity information
of the subset of the issued certificates.
6. A method for an authority to generate authenticated information about a
plurality of certificates, comprising the steps of:
(a) generating a data string indicating a first set of identifiers, where
identifiers, in the first set correspond to issued certificates, and a
second set of identifiers, wherein identifiers of all issued certificates
are outside the second set; and
(b) having the authority generate the authenticated information by
authenticating the data string.
7. A method according to claim 6, wherein the data string further includes
information indicating a date of authentication of the data string.
8. A method according to claim 6, wherein the data string further includes
certificate information about a subset of the certificates.
9. A method according to claim 8, wherein the certificate information
includes at least one of: revocation information and validity information
of the subset of the certificates.
10. A method according to claim 6, wherein the data string further includes
a date of issuance of at least one of the certificates.
11. A method for an authority to provide authenticated information about
certificate identifiers, comprising, the steps of:
(a) generating data indicating a set of identifiers, wherein an identifier
of each issued certificate is outside the set; and
(b) having the authority authenticate the data.
12. A method according to claim 11, wherein the data further includes
certificate information about issued certificates.
13. A method to provide authenticated information about one or more
unissued certificate identifiers, comprising the steps of:
(a) generating data that includes information identifying the one or more
unissued certificate identifiers; and
(b) authenticating the data.
14. A method for an authority to generate authenticated issuance
information about a plurality of certificate identifiers, comprising the
steps of:
(a) mapping at least two of the plurality of certificate identifiers to
predetermined bit positions in a data string and having a subset of bits
at the bit positions convey issuance information about the at least two
certificates, the issuance information indicating whether each of the
certificate identifiers corresponds to an issued certificate; and
(b) generating authenticated issuance information by having the authority
authenticate the data string.
15. A method according to claim 14, wherein mapping to predetermined bit
positions reduces an amount of bits used to represent certificates that
are mapped.
16. A method according to claim 14, wherein an amount of bits used to
represent the certificates in the authenticated issuance information is
less than a total number of bits contained in serial numbers of the
certificates.
17. A method to generate authenticated issuance information about a
plurality of certificates, comprising the steps of:
(a) generating a data string containing information identifying all issued
certificates among the plurality of certificates that share a given
characteristic; and
(b) generating the authenticated issuance information by authenticating the
data string.
18. A method according to claim 17, wherein each issued certificate has an
identifier belonging to an ordered set and the characteristic includes
having the identifier be between a given lower bound and a given upper
bound in the ordered set.
19. A method according to claim 17, wherein each issued certificate has an
identifier and the characteristic includes having given bits in the
identifier be equal to given values.
20. A method according to claim 17, wherein each issued certificate has an
identifier and the characteristic includes having a hash function applied
to at least a portion of each issued certificate yield a given value.
21. A method according to claim 17, wherein the characteristic includes
having the certificate contain a given value in a given field.
22. A method to generate authenticated issuance information about a
plurality of certificate identifiers, comprising the steps of:
(a) generating a data string containing information identifying all
unissued certificate identifiers that share a given characteristic; and
(b) generating the authenticated information by authenticating the data
string.
23. A method according to claim 22, wherein each unissued certificate
identifier belongs to an ordered set and the characteristic includes
having the identifier be between a given lower bound and a given upper
bound in the ordered set.
24. A method according to claim 22, wherein the characteristic includes
having given bits in the identifier be equal to given values.
25. A method according to claim 22, wherein the characteristic includes
having a hash function applied to at least a portion of the unissued
certificate identifier yield a given value.
26. A method according to claim 22, wherein the characteristic includes
having the certificate contain a given value in a given field.
27. A method for an authority to generate authenticated information about a
plurality of certificate identifiers, comprising the steps of:
(a) generating a data string containing information identifying a set
containing all of the certificate identifiers that share a given
characteristic and correspond to issued certificates, at least one of the
issued certificates not being revoked; and
(b) generating the authenticated information by having the authority
authenticate the data string.
28. A method for an authority to provide authenticated issuance information
about issued certificates, comprising the steps of:
(a) choosing a plurality of characteristics;
(b) for each of the characteristics, generating a data string that contains
information that identifies the characteristic and all the issued
certificates possessing the characteristic, wherein at least one of the
certificates is not revoked and wherein each of the certificates possess
at least one of the characteristics; and
(c) generating the authenticated information having the authority
authenticate each of the data strings.
29. A method according to claim 28, wherein at least one of the data
strings further includes revocation information for a subset of the
certificates.
30. A method according to claim 29, wherein the characteristic includes an
identifier for a subset of the certificates.
31. A method for an authority to provide authenticated issuance information
about certificate identifiers, comprising the steps of:
(a) choosing a plurality of characteristics wherein each of the certificate
identifiers possesses at least one of the characteristics;
(b) for each of the characteristics, generating a data string containing
information that indicates the characteristic and a set of unissued
certificate identifiers possessing the characteristic; and
(c) generating the authenticated information by having the authority
authenticate each of the data strings.
32. A method according to claim 31, wherein at least one of the data
strings includes certificate information for a subset of issued
certificates.
33. A method according to claim 31, wherein at least one of the
characteristics corresponds to an identifier for at least one of the
certificates.
34. A method to provide authenticated issuance information about
certificate identifiers, comprising the steps of:
(a) choosing a plurality of characteristics wherein each of the certificate
identifiers possesses at least one of the characteristics;
(b) for each of the characteristics, generating a data string that
identifies the characteristic, all the identifiers for issued and unissued
certificates possessing the characteristic, and information distinguishing
the issued certificate identifiers from the unissued certificate
identifiers; and
(c) generating the authenticated information by authenticating each of the
data strings.
35. A method according to claim 34, wherein the at least one of the data
strings further includes revocation information for a subset of the
certificates.
36. A method according to claim 34, wherein the characteristic corresponds
to identifiers for a subset of the certificates.
37. A method for providing authenticated information about certificates,
comprising the steps of:
(a) receiving a request for information about a certificate including a
proof that the certificate is issued;
(b) verifying that the proof is valid; and
(c) in response to the proof being valid, providing the requested
information.
38. A method according to claim 37, wherein the proof includes providing an
entire CA-authenticated certificate.
39. A method according to claim 38, wherein verifying includes comparing
the entire CA-authenticated certificate to an on hand copy of a verified
CA-authenticated certificate.
40. A method according to claim 38, wherein verifying includes comparing a
function evaluated at the entire CA-authenticated certificate to the
function evaluated at an on hand copy of a verified CA-authenticated
certificate.
41. A method according to claim 38, wherein a CA digitally signs the
certificate to authenticate the certificate and verifying includes
verifying the signature of the CA.
42. A method according to claim 37, wherein the proof includes a hash of an
entire CA-authenticated certificate.
43. A method according to claim 42, wherein verifying includes comparing
the hash of the CA-signed certificate to an on hand copy of a hash
verified entire CA-signed certificate.
44. A method according to claim 37, wherein the proof includes a given
function of an entire CA-authenticated certificate.
45. A method for providing authenticated information about certificates to
a requestor, comprising the steps of:
(a) receiving a request for a first type of information about at least one
certificate including a proof that the requestor knows at least a second
type of information about the certificate;
(b) verifying that the proof is valid; and
(c) in response to the proof being valid, providing the first type of
information to the requestor.
46. A method according to claim 45, wherein the proof is interactive.
47. A method according to claim 45, wherein the second type of information
is authenticated.
48. A method of providing to a user authenticated information about an
identifier for a certificate, comprising the steps of:
(a) having the user provide the identifier to an intermediary; and
(b) having the intermediary cause the user to receive authenticated
information indicating that the identifier does not correspond to an
issued certificate. |
|
 |
|
 |
Claims |
|
|
|
Description |
|
|
This application is based on U.S. provisional patent application No.
60/025,128 filed on Aug. 29, 1996.
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 useful to certify data, as well as to revoke data
that was previously certified. For instance, in a Public Key
Infrastructure (PKI), it may be useful to certify users' public keys. Such
certification may be provided in the form of a certificate which contains
the certified data and vouches for the authenticity of the certified data.
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
a 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 often
"certified" by a certificate that serves as proof that U is the legitimate
owner of PK.sub.u. At the same time it is also useful to be able to revoke
some of the already-issued certificates when U is no longer the legitimate
owner of PK.sub.u (for whatever reason) and/or when SK.sub.u has been
compromised. Of course, the need for certification and certificate
revocation extends beyond certifying public keys.
In many instances, certificates for users' public keys are produced and
revoked by certifying authorities called CA's. 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 discussion can be easily applied to such other
authorities in a straight-forward manner.
A CA may 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. The CA's signature
of PK.sub.u is then inserted in a Directory and/or given to U himself.
Note that, before certifying U's public key, it is necessary to perform
additional steps, such as properly identifying user U. However, these
additional steps are optional.
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.
In fact, 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 the CA's key may also be obtained.
Certificate retrieval is thus possible, although not necessarily cheap.
Unfortunately, however, this is not the only retrieval that R needs to do.
In addition, it is 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 may be 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 to have each CA periodically issues a Certificate
Revocation List (CRL for short). A CRL may consist of the issuer's digital
signature of 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 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
certificates, a CRL is expected to be quite long. It is envisaged that the
CRL is provided to a Directory who may then distribute the CRL to end
users.
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 the name of the CA.
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.
It is possible for a user to query the Directory with a serial number not
corresponding to any issued certificate. (Indeed, while many times the
user has already seen a certificate and accesses the Directory just to
confirm the current validity of that certificate, at other times the user
wishes to obtain the corresponding certificate from the Directory). If the
corresponding certificate does not exist, the Directory is at a loss as to
how to proceed. If the Directory responds truthfully, it may not be
believed by the user. If the Directory gives the users all the
certificates in its possession (or those relative to a given CA) the user
may suspect that the Directory left out the certificate of interest.
Indeed, even if the Directory gives the user the latest CRL of a given CA,
this does not prove to the user that the certificate in question does not
exist. (In fact, the actions of the Directory may actually be interpreted
as saying that the certificate is valid because it does not appear to have
been revoked.) Thus, in this thorny situation the Directory would have to
be trusted.
SUMMARY OF THE INVENTION
According to the present invention, an authority provides authenticated
information about a plurality of issued certificates by generating a data
string identifying all the plurality of issued certificates and by having
the authority authenticate one or more of the data string alone, the data
string together with date information, or the data string together with
additional information. The date information may include the date of
authentication. The additional information may include a date of issuance
of at least one of the certificates. The additional information may
include certificate information about at least some of the issued
certificates. The certificate information may include one or more of:
revocation information or validity information of at least some of the
issued certificates.
According further to the present invention, an authority generates
authenticated information about a plurality of certificates by generating
a data string identifying which of the plurality of certificates have been
issued and which of the plurality of certificates have not been issued and
by having the authority generate the authenticated information by
authenticating one or more of: the data string alone, the data string
together with date information, or the data string together with
additional information.
According further to the present invention, an authority provides
authenticated information about unissued certificates by generating data
identifying all the unissued certificates and by having the authority
authenticate one or more of: the data alone, the data together with a date
of authentication, or the data together with additional information.
According further to the present invention, an authority provides
authenticated information about one or more unissued certificates by
generating data identifying the one or more unissued certificates and by
having the authority authenticate one or more of: the data alone, the data
together with a date of authentication, or the data together with
additional information.
According further to the present invention, an authority generates
authenticated issuance information about a plurality of certificates by
mapping at least two of the plurality of certificates to predetermined bit
positions in a data string and having at least some bits at the bit
positions convey issuance information about the at least two certificates
and by generating authenticated issuance information by having the
authority authenticate one or more of: the data string alone, the data
string together with date information, or the data string together with
additional information. Mapping to predetermined bit positions may reduce
an amount of bits used to represent certificates that are mapped. The
amount of bits used to represent the certificates in the authenticated
issuance information may be less than the total number of bits contained
in serial numbers of the certificates.
According further to the present invention, an authority generates
authenticated issuance information about a plurality of certificates by
generating a data string identifying all issued certificates among the
plurality of certificates that share a given characteristic and by
generating the authenticated issuance information by having the authority
authenticate one or more of: the data string alone, the data string
together with information identifying the additional characteristic, the
data string together with date information, or the data string together
with additional information. Each issued certificate may have an
identifier belonging to an ordered set and the characteristic may include
having the identifier be between a given lower bound and a given upper
bound in the ordered set. Each issued certificate may have an identifier
and the characteristic may include having given bits in the identifier be
equal to given values or may include having a hash function applied to at
least a portion of the revoked certificate yield a given value. The
characteristic may include having the certificate contain a given value in
a given field.
According further to the present invention, an authority generates
authenticated issuance information about a plurality of certificates by
generating a data string identifying all unissued certificates among the
plurality of certificates that share a given characteristic and by
generating the authenticated information by having the authority
authenticate one or more of: the data string alone, the data string
together with information identifying the additional characteristic, the
data string together with date information, or the data string together
with additional information. Each unissued certificate may have an
identifier belonging to an ordered set and the characteristic may include
having the identifier be between a given lower bound and a given upper
bound in the ordered set. Each unissued certificate may have an identifier
and the characteristic may include having given bits in the identifier be
equal to given values or may include having a hash function applied to at
least a portion of the revoked certificate yield a given value. The
characteristic may include having the certificate contain a given value in
a given field.
According further to the present invention, an authority generates
authenticated information about a plurality of certificates by generating
a data string identifying a subset containing all of the certificates
among the plurality of certificates that share a given characteristic,
indicating the certificates of the subset that have issued and the
certificates of the subset that have not issued, and by generating the
authenticated information by having the authority authenticate at least
one of: the data string alone, the data string together with information
identifying the additional characteristic, the data string together with
date information, or the data string together with additional information.
According further to the present invention, an authority provides
authenticated issuance information about certificates by choosing a
plurality of characteristics such that each of the certificates possesses
at least one of the characteristics, for each of the characteristics,
generating a data string that identifies the characteristic and all the
issued certificates possessing the characteristic, and generating the
authenticated information by, for each data string, having the authority
authenticate at least one of: the data string alone, the data string
together with date information, or the data string together with
additional information. The additional information may include revocation
information for at least some of the certificates. The characteristic may
include an identifier for at least some of the certificates.
According further to the present invention, an authority provides
authenticated issuance information about certificates, by choosing a
plurality of characteristics such that each of the certificates possesses
at least one of the characteristics, for each of the characteristics,
generating a data string that identifies the characteristic and all the
unissued certificates possessing the characteristic, and generating the
authenticated information by, for each data string, having the authority
authenticate at least one of: the data string alone, the data string
together with date information, or the data string together with
additional information. The additional information may include revocation
information for at least some of the certificates. The characteristic may
include an identifier for at least some of the certificates.
According further to the present invention, an authority provides
authenticated issuance information about certificates by choosing a
plurality of characteristics such that each of the certificates possesses
at least one of the characteristics, for each of the characteristics,
generating a data string that identifies the characteristic, all the
issued and unissued certificates possessing the characteristic, and
information distinguishing the issued certificates from the unissued
certificates, and generating the authenticated information by, for each
data string, having the authority authenticate at least one of: the data
string alone, the data string together with date information, or the data
string together with additional information. The additional information
may include revocation information for at least some of the certificates.
The characteristic may include an identifier for at least some of the
certificates.
According further to the present invention, an intermediary proves
certificate information to a user by causing the user to receive
authenticated certificate information that is provided by one or more of
the techniques set forth herein. The intermediary may provide the
authenticated information directly to the user. The intermediary may
receive the authenticated information from one or more of: the authority,
an other intermediary, or a user.
According further to the present invention, a user uses authenticated
certificate information that is generated by one or more of the techniques
set forth herein. The user may receive the authenticated information from
one or more of: an authority, an intermediary, or an other user.
According further to the present invention, providing authenticated
information about certificates includes receiving a request for
information about at least one certificate including a proof that the
certificate is issued, verifying that the proof is valid, and, in response
to the proof being valid, providing the requested information. The proof
may include providing an entire CA-authenticated certificate. Verifying
may include comparing the entire CA-authenticated certificate to an on
hand copy of a verified CA-authenticated certificate and/or may include
comparing a function evaluated at the entire CA-authenticated certificate
to the function evaluated at an on hand copy of a verified
CA-authenticated certificate. The CA may authenticate the CA-authenticated
certificate by digitally signing the certificate and verifying may include
verifying the signature of the CA. The proof may include a suitable hash
of an entire CA-authenticated certificate and/or a suitable function of an
entire CA-authenticated certificate. Verifying may include comparing the
hash of the CA-authenticated certificate to an on hand copy of a hash of a
verified entire CA-authenticated certificate.
According further to the present invention, providing authenticated
information about certificates to a requestor includes receiving a request
for a first type information about at least one certificate including a
proof that the requestor knows at least a portion of a second type of
information, verifying that the proof is valid, and, in response to the
proof being valid, providing the first type of information to the
requestor. The proof may be interactive.
According further to the present invention, providing authenticated
information about certificates to a requestor includes receiving a request
for information about at least one certificate including a proof that the
requestor knows some other suitable amount of authenticated information
about the certificate, verifying that the proof is valid, and, in response
to the proof being valid, providing the requested information to the
requestor.
DETAILED DESCRIPTION OF THE PREFERRED EMBODIMENTS
A user of an electronic communication system may query an intermediary
(such as a Directory) with certificate identification information and
obtain in response the identified certificate. Certificate identification
information may be a serial number, a user name, a CA, etc. For
concreteness, but without limitation, assume that a user may query a
Directory using the serial number and the CA corresponding to the
certificate of interest. The user then obtains in response information
about the certificate issued by the CA having the requested serial number.
The above procedure could present a problem if a user queries the Directory
with a serial number that does not correspond to a certificate issued by
the CA. In that case, the Directory, though possessing the relative
certificate, may deny the user that information. Having the Directory
provide the user with the latest CRL of the CA does not solve the problem
either. In fact, the absence of the queried serial number from the CRL
only proves that the corresponding certificate, if any, is not revoked,
but leaves open the possibility that no certificate corresponding to the
requested serial number (and CA) was ever issued. Since intermediaries may
not be trusted, this is a problem, and may cause serious denial of service
complications or attacks.
Note that, in some sense, every certificate, by definition, is issued,
since certificates include data authenticated by authorities. However,
since it is possible to use identifiers to refer to certificates (e.g.,
use a twenty bit string as a certificate serial number), the set of
possible identifiers may be greater than the set of issued certificates.
For instance, there may be a plurality of twenty bit strings that are not
serial numbers of any certificate issued by a CA. Thus, in order to
simplify the discussion herein, the term "certificate" includes
identifying information that may or may not correspond to an issued
certificate.
The problem of a user querying an intermediary with certificate identifying
information that does not correspond to any issued certificate may be
addressed by means of a new structure, called a Certificate Issue List
(CIL). A CIL may include a (preferably) dated and authenticated (e.g.,
digitally signed) list of all the serial numbers of issued (and preferably
not expired) certificates. A CIL allows a (possibly) untrusted
intermediary to prove whether a given certificate has been issued. A CIL
may also contain additional information. For instance, the CIL may contain
the issue date for each issued certificate and/or the issue date of the
CIL.
Alternatively, a CIL may include authenticated (e.g., digitally signed) and
(preferably) dated information indicating all certificates that have not
yet issued. Alternatively still, a CIL may include authenticated and
(preferably) dated information indicating all issued and unissued
certificates together with information distinguishing which certificates
have been issued and which have not. Of course, when constructing a CIL,
it is possible to include and optionally authenticate any other type of
information, such as issue dates, revocation dates, other revocation
information, validity information, etc. The information may be organized
in a variety of manners (including a list or, more generally, a data
string).
Preferably, a CIL is authenticated (e.g., digitally signed) by a CA. For
instance, the same CA that issues certificates may also authenticate a
corresponding CIL (i.e., a CIL relative to the certificates of the CA).
Alternatively, a CIL may be authenticated by another CA, by a different
type of authority, or by two or more appropriate entities (possibly
machines).
It will be appreciated by one of ordinary skill in the art that the system
described herein may be applied to public key certificates as well as any
other types of certificates. It will also be appreciated by one of
ordinary skill in the art that the system described herein may not only be
used by an authority, but also by any intermediary, such as a directory.
Note that an intermediary includes a directory, an other user, an
authority, a database, a computer file, a read-only file, or any entity
that causes information to be provided to another entity. Indeed, such an
intermediary may receive CIL information and send that information to
other users. More generally, the intermediary may simply cause a user to
receive CIL information from another entity, such as another user, an
other directory, an other intermediary, an other CA, an other database, an
other fie, and so forth. An intermediary may cause users to receive CIL
information by simply storing such information in a file that is
accessible by users. Indeed, the intermediary itself may be such an
accessible file.
It will be appreciated by one of ordinary skill in the | | |
