Note: Descriptions are shown in the official language in which they were submitted.
CA 02374195 2002-03-O1
SYSTEM AND METHOD OF LOOKING UP AND
VALIDATING A DIGITAL CERTIFICATE IN ONE
PASS
FIELD OF THE INVENTION
[00001] This invention relates to the field of digital certificates. More
specifically, it
is directed to an improved scheme for validating digital certificates.
BACKGROUND OF THE INVENTION
[00002] In asymmetric encryption technology, each user generates a pair of
keys
known as a public key and a private key. The public key is widely disseminated
and used by
others to encrypt communications intended for the owner of the public key.
Once the
message has been encrypted with the public key, it can only be decrypted with
the
corresponding private key. This is the basis of public key encryption.
[00003] The problem with this technology is that the sender needs to have a
way of
guaranteeing that the public key used for encryption does indeed belong to the
recipient.
Otherwise, the sender could unintentionally encrypt a message that could only
be decrypted
by some mischievous third party. A method was therefore needed for users to be
able to
have a high degree of assurance that the owner of a public key was indeed the
intended
recipient.
[00004] Digital certificates were invented to solve this problem. A recognized
2 0 certificate authority issues a certificate binding the public key of a
subscriber to his real
world identity. The certificate is digitally signed by the recognized issuing
authority. A
message is digitally signed in effect by encrypting it with a private key. The
message can
then only be decrypted with the corresponding public key, and provided the
user has a high
t
CA 02374195 2002-03-O1
degree of trust in the certifying authority, he will then have assurance that
the public key
contained in the certificate does indeed belong to the user to whom it is
bound.
[00005] Digital certificates generally follow the X.509 standard, developed by
the
International Standards Organization (ISO) and the Comity Consultatif
Internationale
Telegraphique et Telephonique (CCIT'I~. These certificates create a binding
between an
entity's public key and its identity. Obtaining authentic copies of public key
certificates is
critical in deploying secure public key systems. Often a digital certificate
is stored in a
publicly accessible repository such as an LDAP or X.500 directory.
[00006) In practice, implementers of certificate revocation lists have
discovered that
they are di~cult to manage because they can become very large and not usable
by some
certificate verifiers such as smartcards or mobile phones. Further, since
these lists are issued
only periodically,'there is a time gap between when a certificate is revoked
by its issuer and
when it appears on a publicly available list of revoked certificates. Methods
such as the
online certificate status protocol have been developed as a means to make
requests to
validation services to determine whether a particular certificate is cun:ently
valid, however,
this requires that a certificate verifier make at least two requests, one to
obtain a copy of the
certificate and another to obtain the current validity status of the
certificate. Further requests
may be required to obtain all certificates needed to construct a certificate
chain that can be
validated up to a tn>sted root held by the verifier. In many applications, in
particular those
2 0 where the verifier is a mobile phone, smartcard or other client devices
that are relatively
constrained with respect to storage capacity, Processing power and
coaununication
bandwidth, the current solutions are not practical.
[00007] It will be apparent finm the foregoing that prior certificate issuance
and
validation systems and methods are generally designed to allow a user to
obtain a validated
2 5 digital certificate, but are slow and cumbersome to the user under various
circumstances.
2
CA 02374195 2002-03-O1
SUMMARY OF THE INVENTION
[00008) It is an object of the present invention to provide a system for
accessing and
validating a digital certificate, comprising a first set of certificate
authorities connected to a
communication network and able to receive and respond to requests for
certificates; the first
set of certificate authorities having a set of hierarchical trust relationship
among them, the
set of hierarchical trust relationships being verified by a set of digital
certificates; a certificate
holder having a digital certificate issued by one of the first set of
certificate authorities; a
certificate verifier connected to the communication network and having a mist
relationship
with a second set of certificate authorities; and a certificate distribution
cetrter connected to
the communication network and operable to receive a request finm the
certificate verifier for
a validated copy of the digital certificate, obtain the digital certificate
fi~om said one of the
first set of certificate authorities, obtain a subset of digital certificates
of the set of digital
certificates necessary to validate the digital certificate, and return to the
certificate verifier a
validated copy of the digital certificate, wherein the certificate
distribution server determines
the subset of digital certificates of the set of digital certificates based on
the second set of
certificate authorities.
[00009] Preferably, the certificate distribution center is operable to
indicate to the
certificate verifier that the digital certificate has a status of invalid,
revoked, expired or non-
existent.
2 0 [00010] Also preferably, there is at least one revocation list server
having a list of
digital certificates that have been revoked; and a certificate cache, wherein
the certificate
distribution center additionally obtains from the certificate cache a cached
copy of one of the
digital certificate and the set of digital certificates and verifies with the
at least one
revocation server the validity thereof prior to contacting the set of
certificate authorities.
2 5 [00011 ] The certificate cache preferably resides at the certificate
distribution center
and serves a plurality of certificate verifiers.
3
CA 02374195 2002-03-O1
[00012] Also preferably, the certificate distribution center deposits a subset
of the
digital certificate and the subset of digital certificates obtained from the
first set of certificate
authorities in the certificate cache.
[00013] The request finm the certificate verifier can indicate a desired level
of
confidence for the digital certificate's validity or can directs the
certificate distribution center
to ignore the certificate cache.
[00014] Preferably, the reply to the certificate verifier additionally
comprises a
formatted first certificate chain summary.
[00015] Also preferably, the certificate distribution center additionally
constructs and
returns a second certificate chain, based on the second set of certificate
authorities, to the
certificate verifier permitting the certificate verifier to validate the
digital certificate of the
certificate distribution center.
[00016] The certificate distribution center preferably has prior knowledge of
the
second set of certificate authorities trusted by the certificate verifier.
[00017] In addition, the request finm the certificate verifier includes a
requested
certificate identifier fibm which each of the first set of certificate
authorities in parent
relationship to the certificate holder can be identified.
[00018] In another aspect of the invention, there is provided a method of
validating
and serving a digital certificate, comprising the steps of receiving a first
request from a
2 0 certificate verifier for a digital certificate; sending a second request
to a first certificate
authority having issued the digital certificate requested by the certificate
verifier; receiving
the digital certificate from the first certificate authority; if the first
certificate authority is not
twisted by the certificate verifier, requesting an additional digital
certificate from a
subsequent parent certificate authority, receiving the additional digital
certificate from the
2 5 subsequent parent certificate authority, validating a previous digital
certificate with the
additional digital certificate, and, in the event that said subsequent parent
certificate authority
4
CA 02374195 2002-03-O1
is not trusted by the certificate verifier, repeating these steps; and
rettuning the digital
certificate to the certificate verifier.
[00019] Preferably, the step of receiving the digital certificate or
additional digital
certificate from the certificate authority can alternatively comprise
receiving an indication
that the digital certificate or the additional digital certificate is invalid,
the steps of obtaining
additional digital certificates are repeated also conditionally on the
validity of the previous
digital certificate and the existence of the additional digital certificate
and its unrevoked
status, and the step of returning the digital certificate to the certificate
verifier can
alternatively comprise returning a notification that the digital certificate
is invalid.
[00020] Also preferably, the method additionally comprises the step of
obtaining the
digital certificate or the additional digital certificate from a certificate
cache and validating
the digital certificate or the additional digital certificate using a
revocation list in place of
obtaining the digital certificate or the additional digital certificate from
the first or
subsequent parent certificate authorities, in the event that the digital
certificate or the
additional digital certificate is available from the certificate cache.
[00021] Further, the method preferably additionally comprises the step of
placing at
least one of the digital certificate and the additional digital certificates
in the certificate cache
once received from the first or subsequent parent certificate authority.
[00022] The step of receiving a first request from a certificate verifier can
additionally
2 0 comprise receiving a desired level of confidence from the certificate
verifier, and the step of
validating the digital certificate and the additional digital certificates
reflects the desired level
of confidence.
[00023] Alternatively, the step of receiving a first request from a
certificate verifier
comprises receiving from the certificate verifier a direction to ignore the
certificate cache.
2 5 [00024] Further, the step of returning the digital certificate to the
certificate verifier
preferably additionally comprises constmcting a first certificate chain from
the digital
s
CA 02374195 2002-03-O1
certificate and the additional digital certificates, if any, and returning the
first certificate
chain, along with the digital certificate, to the certificate verifier.
[00025] Preferably, the step of returning the certificate chain comprises
formatting the
first certificate chain and the digital certificate prior to returning the
first certificate chain to
the certificate verifier.
[00026] The steps of obtaining additional digital certificates are preferably
followed
by the step of constructing a second certificate chain, based on the second
set of certificate
authorities, to the certificate verifier permitting the certificate verifier
to validate the
certificate distribution cecrter, and returning the second certificate chain
to the certificate
verifier.
[00027] Preferably, the step of constructing a second certificate chain
additionally
comprises the step of formatting the second certificate chain prior to
returning the second
certificate chain to the certificate verifier.
[00028] Also preferably, the step of receiving a first request from a
certificate verifier
for a digital certificate additionally includes the step of identifying the
first certificate
authority and each of the subsequent parent certificate authorities solely
from the
information presented in the first request, and the steps of obtaining the
additional digital
certificates is performed prior to receiving the digital certificate from the
first certificate
authority.
2 0 BRIEF DESCRI>fTION OF TIIE DRAWINGS
[00029] The present invention will now be described, by way of example only,
with
reference to certain embodiments shown in the attached Figures in which:
[00030] FIG. 1 is a block diagram of the prior art method of authenticating
the public
key of an entity;
6
CA 02374195 2002-03-O1
[00031] FIG. 2 is a block diagram of the method in an embodirrient in the
present
invention for authenticating the public key of an entity;
[00032] FIG. 3 is a block diagram of the request data structure sent by the
certificate
verifier to a certificate distribution center in a present embodiment of the
invention;
[00033] FIG. 4 is a block diagram of the response data st<ucttue sent by the
certificate
distribution cert~er to the certificate verifier in a present embodiment of
the invention; and
[00034] FIG. 5 is a flow chart of an embodiment of the method of looking up
and
validating a digital signat<ue in one pass.
DETAILED DESCRIPTION OF THE INVENTION
[00035] The general method of certificate authentication as taught under the
aforementioned standards is shown in FIG. 1. In order to obtain a validated
certificate, a
verifier may be required to make numerous requests to various authorities and
verify the
authenticity of each certificate received individually.
[00036] Referring now to FIGS. 2 to 5, the system and method of looking up and
validating a digital certificate in one pass in accordance with a first
embodiment of the
present invention is indicated generally at 20. A certificate verifier 24 is
provisioned with at
least one certificate of a trusted root certificate authority and means to
locate and contact a
certificate distribution center (CDC) 28. Certificate verifier 24 may be a
desktop or server
computer that has a pernianent connection or establishes a temporary
connection to a
2 0 communication network, such as the Internet. Certificate verifier 24 may
know the physical
address of CDC 28 or may know its virtual address that will resolve to CDC 28
by means of
a resolution system, such as DNS.
[00037] When certificate verifier 24 needs to obtain a copy of a public key
contained
in a certificate, and wants assurances that the certificate is currently
valid, in order to verify a
CA 02374195 2002-03-O1
digital signature of or encrypt a message to a certificate holder 32, it
transmits a certificate
request 36 to CDC 28.
[00038] Certificate request 36 contains a requested certificate identifier 40
that
provides sufficient information for CDC 28 to retrieve the certificate for
certificate holder 32
from the appropriate CA. Requested certificate identifier 40 may be
information that
directly or indirectly identifies certificate holder 32.
[00039] Certificate request 36 can also contain tn,LSted certificate
information 44,
indicating trust relationships with at least one CA. Trusted certificate
information 44 defines
the gap in trust that CDC 28 must try to bridge with a chain of certificates.
Trusted
certificate information 44 can be a list of the CAs for which tn~sted
certificates are held, a
reference to a list of CAs known or available to CDC 28, or any other
information allowing
CDC 28 to detenTiirte what CAs are tn~ by certificate verifier 24.
[00040] Additionally, validated certificate request 36 can optionally contain
a CDC
credentials request field 48 that allows certificate verifier 24 to demand a
copy of the
certificate of CDC 28 and, additionally, any certificates required to
construct a chain to a CA
trusted by certificate verifier 24.
[00041] Further, a set of ayptogcaphic security information 52 can be included
in
validated certificate request 36 to prevent a replay attack such as a time
code or a nonce.
[00042] CDC 28 receives validated certificate request 36 and parses it. The
initial
2 0 task of CDC 28 is to use cryptographic security information 52 to verify
whether the request
was tampered with.
[00043] Once verified, CDC 28 commences acquiring and validating the
appropriate
certificates. The greatest resources used in constructing a response are in
looking up the
certificate chain of certificate holder 32 and validity thereof. CDC 28 may
need to lookup
2 5 these certificates in public directories such as LDAP or X.500
directories. CDC 28 looks up
the certificate of certificate holder 32, the certificates of the CA that
issued the certificate of
8
CA 02374195 2002-03-O1
certificate holder 32 and the certificates of the subsequent parent CAs that
demonstrate the
hierarchical twist relationships, up to the certificate issued by the CA
trusted by certificate
verifier 24. If the CAs tntsted by certificate verifier 24 are not a direct or
indirect parent of
the CA that issued the certificate to certificate holder 32, then CDC 28 can
continue to look
up certificates until that of the root CA has been obtained.
[00044] CDC 28 can maintain a certificate cache 56 to cache certificates
retrieved in
response to certificate requests 36. In this case, CDC 28 preferably serves
multiple
certificate verifiers. Alternatively, certificate cache 56 may be eactaztally
located.
[00045] For each certificate required, CDC 28 checks to see if a cached copy
exists in
certificate cache 56. If it does, CA checks with a revocation list server 60
maintaining a last
of revoked certificates that is updated periodically. Revocation list server
60 can be located
at CDC 28, such'as a process on the same computer making the request or on a
separate
computer cooperatively comprising CDC 28, or can alternatively be located
externally.
Alternatively, Cl7C 28 checks with the CA that issued the certificate to
confirm the validity
1 S of the certificate.
[00046] If C1JC 28 does not have access to a cached copy of a required
certificate,
CDC 28 contacts the CA that issued the certificate for a copy, if available.
[0004'7] CIaC 28 can thus conswct a chain of certificates fibm certificate
holder 32 to
a CA trusted by certificate verifier 24, or to a root CA if no CA in the
hierarchy is misted by
2 0 certificate verifier 24.
[00048] Where CDC credentials request field 48 is employed and certificate
verifier
24 has requested such credentials, CDC 28 can construct a chain of
certificates from CDC 28
to a CA muted by certificate verifier 24, or to a root CA if no CA in the
hierarchy is trusted
by certificate verifier 24.
9
CA 02374195 2002-03-O1
[00049] CDC 28 then forms and transmits a certificate response 64 to
certificate
verifier 24. Certificate response 64 can include a cryptographic hash of the
original request
for proposes of verifying secure receipt of certificate request 36 of
certificate verifier 24.
[00050] If C17C 28 was able to find a valid certificate matching the requested
parameters, it can include in certificate response 64 the certificate and
certificate chain
information up to, but not including, the certificate of a trusted certificate
authority specified
in the request 36, or the root CA where no CA trusted by certificate verifier
24 was in the
chain. Alternatively, CDC 28 can provide a confirmation of the credentials of
certificate
holder 32 in some other format, such as a Boolean response.
[00051 ] If no certificate matches the requested parameters or if the
requested
certificate is revoked, has expired or is invalid because of an incomplete
certificate chain to a
tnrsted certificate authority, CDC 28 sends a response indicating that no such
valid
certificate was found.
[00052] Where certificate verifier 24 requests the credentials of CI7C 28, CDC
28 can
provide its certificate and certificate chain information up to, but not
including, the certificate
of a trusted root specified in the request.
[00053] If certificate verifier does not have a frosted root that is in a
chain containing
the requested certificate or a chain containing the certificate distribution
center's certificate,
CDC 28 may include this tn~sted root but the response may be less meaningful
to the
2 0 certificate verifier.
[00054] The time at which CDC 28 determined the validity of the requested
certificate can be optionally included in the response.
[00055] Finally, CIx 28 includes its digital signature on the response
covering the
entire contents of the response.
2 5 [00056] CDC 28 sends signed certificate response 64 to certificate
verifier 24.
1o
CA 02374195 2002-03-O1
[00057] Certificate verifier 24 uses the public key of CDC 28 to verify the
signatm~e
on certificate response 64. This key is obtained either from certificate
response 64 itself or
by some other method Certificate verifier 24, if it does not trust this key
directly, also
verifies the certificate chain containing this certificate, and resultantly
this key, up to a
tn~sted certificate. Certificate verifier 24 also verifies that the identity
in the certificate
returned in certificate response 64 containing the public key of CDC 28
matches the identity
of CDC 28.
[00058] Certificate verifier 24 also verifies that the cryptographic hash 52
of
certificate request 64 it sent to CDC 28 matches the cryptographic hash 68 in
the response.
This prevents replay attacks and prevents an adversary finm changing the
information in the
original request
[00059] Once certificate verifier 24 has determined that certificate response
64 is
authentic and is a response to the request it made, it can proceed to extract
the requested
certificate and certificate chain information with the confidence that each
certificate in the
chain is currently valid and not revoked.
[00060] While the foregoing description refers to a system whereby the
response
includes the certificate chain and validation thereof, it is contemplated that
CDC 28 returns a
response indicating that the certificate chain has been validated, but does
not include the
certificate chain itself.
2 0 [00061 ] Other variations are within the scope of the invention.
[00062] For example, CDC 28 can have a certificate issued by a CA trusted
directly
or indirectly by certificate verifier 24; for example, the CA whose root
certificate is held by
certificate verifier 24. This enables certificate verifier 24 to trust Cl7C
28.
[00063] Further, the certificate of CDC 28 can indicate that CDC 28 is
permitted to
2 5 act in its capacity.
11
CA 02374195 2002-03-O1
[00064] CDC 28 can maintain state information about which certificate
authorities are
trusted by certificate verifier 24.
[00065] Certificate verifier 24 can specify a desired level of confidence to
be satisfied
in determining the validity of a requested digital certificate. For example,
certificate verifier
may specify that a certificate obtained from a source other than the issuing
certificate
authority only need have been validated within the last month; that is, if the
certificate was
placed in the cache in the last month or was determined not to have been on a
revocation list
in the last month, then the certificate can be retied on. Further, certificate
verifier 24 can
specify for CDC 28 to obtain fresh copies of certificates from the appropriate
issuing
certificate authorities.
[00066] Requested certificate identifier 40 can disclose not only the name and
location of the digital certificate of certificate holder 32, but may also
specify those of each
subsequent parent certificate authority including the root certificate
authority, such as by
using the method of pseudonyms for identifying certificate chains, as
disclosed, in co-
pending Canadian patent application 2,365,441. If the method described in co-
pending
Canadian patent application 2,365,441. is used, then inforniation contained in
the response
may contain a certificate sequence number.
[00067] Further, where the complete hierarchy can be immediately identified
from
requested certificate identifier 40 of certificate request 36, CDC 28 can
perform the
2 0 necessary procedures to validate each of the certificate in the
certificate chain
simultaneously, thus improving response times.
[00068] The present invention provides a novel system and method for looking
up
and validating a digital certificate that is generally less cumbersome and
more rapid for the
certificate verifier.
2 5 [00069] The invention enables client software to have a smaller size
because
certificate validation information is gathered and consolidated by the
certificate distribution
center. The set up of this software is easier because it needs to be
configured to
12
CA 02374195 2002-03-O1
communicate only with the certificate distribution center. Network
communications are
more efficient because the certificate verifier does not need to establish
sessions with
different validation authorities or directories.
[00070] The above-described embodiments of the invention are intended to be
examples of the present invention and alterations and modifications may be
effected thereto,
by those of skill in the art.
[00071] This concludes the description of the preferned embodiment of the
invention.
The foregoing description has been presented for the purpose of illustration
and is not
intended to be exhaustive or to limit the invention to the precise form
disclosed. Many
modifications and variations are possible in light of the above teaching and
will be apparent
to those skilled in the art. It is intended the scope of the invention be
limited not by this
description but by the claims that follow.
13
