 |
Description  |
|
|
The invention relates to a protocol for one party to an electronic
transaction, as for example a client in a client-server transaction, to
prove its authenticity to the other party of the transaction.
BACKGROUND OF THE INVENTION
Client-server systems provide electronic access by the client to data,
information, accounts and other material stored at the server. In
financial transactions, the system provides a client electronic access to
accounts and financial resources.
In a client-server transaction, the client is required to prove to the
server that it is an authentic client, and not some impersonator or other
unauthorized party. Protocols are known by which a client proves to a
server its authenticity, while at the same time it does not reveal
information that could be misused by a third party.
A standard well known protocol for proving authenticity involves public-key
cryptography. The client establishes a public key/private key pair and
provides the public key to the server. In a transaction, to prove its
authenticity to the server, the client forms a digital signature with its
private key on a time-varying message, and the server verifies the digital
signature with the client's public key. The time-varying message, which
may be a timestamp or a challenge supplied by the server, is different in
each instance. This message, when checked by the server, provides
safeguards against a third party impersonating the client by simply
replaying copies of previous signatures of the client that the third party
has intercepted or otherwise acquired.
In the standard protocol described above, the server trusts that the public
key belongs to the client, i.e., that the client is in fact actively
involved in the transaction because it is presumed that only the client
knows the private key and can form valid digital signatures. A convenient
way to establish trust in a public key is to use a certificate. This is
accomplished by a certification authority issuing public-key certificates
signed with the certification authority's private key, which thereby
asserts to the server that the client's public key is a valid public key
issued by or registered with the certification authority. Assuming the
server trusts the certification authority's public key, then it trusts the
client's certificate, the client's public key and ultimately the client's
authenticity.
With typical public-key cryptosystems, it is computationally expensive to
form digital signatures because of the need to perform an exponentiation
operation. In some electronic transactions, for example, those involving a
smart card client where the computational capacity is limited, the
standard protocol using a digital signature is computationally expensive
and is therefore a significant burden.
Beller and Yacobi, in an article entitled "Fully-Fledged Two-Way Public Key
Authentication and Key Agreement for Low-Cost Terminals" ELECTRONICS
LETTERS, May 27, 1993, Vol. 29, No. 11, at pages 999-1000, describe a
protocol that provides for less on-line computation on one side of the
protocol. In this protocol authentication of the server by the client is
carried out by the server sending a random challenge with an expected
"colour", structure or format, to the client for verification by the
client. Authentication of the client by the server is achieved by the
client sending to the server its identity, public key, certificate and a
signature on the random challenge for verification of the certificate and
the signature by the server. The protocol is described as being useful
where one side of the interaction is a low-cost customer device such as
portable telephones, home banking terminals, smart cards and notebook
computers.
Other protocols are known for establishing the authenticity of a client to
a server. Client authentication protocols such as those based on
secret-key cryptography exist, but often have the limitation that the
server must be on-line, or the server must store a key which can be used
to impersonate arbitrary clients. In Cellular Digital Packet Data systems,
a client authenticates itself to a server by sending a one time password
encrypted with a Diffie-Hellman shared key, and the server returns a new
password for the next session. Again, the server must be on-line or the
client must share a different password with each server, which can be
inconvenient.
BRIEF DESCRIPTION OF THE INVENTION
A protocol that is less computationally expensive for a client but achieves
similar goals as the standard protocol is used to develop a server's trust
in the client. In this protocol, a certificate provided by a trusted
certification authority to the client is encrypted with a key known only
to the client and the server or the public key of the server. The client
forms no digital signature. Since only the client and the server it trusts
have access to the certificate, the certificate itself is proof of the
authenticity of the client. This protocol is particularly useful in client
devices having small computational capacity, e.g., a smart card.
Additional interactive protocols are disclosed whereby messages are
exchanged between client and server to establish authenticity of both the
client and the server as well as protocols wherein only a portion of the
client's certificate is encrypted. Moreover, the certificate can include a
one way function, such as a cryptographic hash function of a secret value
or a root of a hash tree of secret values for protection against the
certification authority or unauthorized servers, respectively.
A still further more general protocol involves a user, which may be an
individual, a computer or some other entity, connected to a verifier by
way of an encrypted communications channel such that the user can
confidentially deliver to the verifier information essential to verify the
message.
DESCRIPTION OF THE DRAWINGS
FIG. 1 schematically illustrates the components of a smart card;
FIG. 2 illustrates the components of a server;
FIG. 3A is a flow diagram showing the procedure for generating messages by
a client to prove its authenticity to a server;
FIG. 3B is a flow diagram showing the processing at the server of messages
sent by a client to authenticate the client;
FIG. 4A is a flow diagram illustrating an interactive embodiment of the
invention where the server sends a copy of its certificate to a client;
FIG. 4B is a flow diagram illustrating an interactive embodiment of the
invention where the server sends a copy of its certificate and a
time-varying value to the client;
FIG. 4C is a flow diagram illustrating an interactive embodiment of the
invention where the server sends a time-varying value to the client;
FIG. 5 is a flow diagram illustrating an interactive embodiment of the
invention where a client is sent a message signed by the server;
FIG. 6 is a partial flow diagram illustrating a variation in the messages
generated by the client;
FIG. 7 is a partial flow diagram illustrating a version of the invention
where a client's certificate is sent directly to a server;
FIG. 8 is a partial flow diagram of FIG. 5 modified so that only part of
the client's certificate is encrypted;
FIG. 9 is a partial flow diagram of FIG. 6 modified so that only part of
the client's certificate is encrypted;
FIG. 10 is a partial flow diagram of FIG. 7 modified so that only part of
the client's certificate is encrypted;
FIG. 11 is an illustration of a hash tree which may be used to prevent
misuse by a server; and
FIG. 12 illustrates a still further flow diagram of essential elements of a
system having a more general protocol but which may have features of other
embodiments disclosed herein added thereto.
DESCRIPTION OF THE PREFERRED EMBODIMENTS
The specific description of the invention is set forth in the environment
of a smart card client. However, the invention is not limited to a smart
card client since the disclosed protocols are applicable to client/server
systems in general, and in particular clients having low computational
capacity such as portable telephones, notebook computers and home banking
terminals. In an even more general manner the disclosed exemplary
embodiments as described later can involve a user, which can be an
individual, a computer or some other entity, which is connected to a
verifier, which can be a client, a server or some other entity, via an
encrypted communications channel whereby the user can confidentially
deliver to the verifier information essential to verify the message.
A smart card includes a microchip containing a processor and memories to
hold programs and data. FIG. 1 illustrates a smart card 1 comprising a
processor 2, an erasable programmable read only memory (EPROM) 3,
programmable read only memory (PROM) 4, random access memory (RAM) 5,
input/output (I/O) port 6, number generator 7, clock 8 and power source 9.
PROM 4 holds the card operating system and RAM 5 holds temporary results
of calculations. EPROM 3 holds the certificate for the card. This
certificate for the card, unlike the usual public key certificate, need
not include the public key of the client since authentication of the
client by the server does not rely on the public key of the client. A
cache of public keys of one or more servers may also be stored in PROM 4
or EPROM 3. Number generator 7 provides random seed numbers to the
processor for generating secret session keys. Clock 8, conventional and
well known in the art, is used for generating a timestamp and for
verifying a received timestamp. Clock 8 is optional where the server's
timestamp or time-varying value is used by the client to provide a
time-varying value or where a challenge procedure is followed. Power
source 9 is a battery when a card has a clock. Otherwise, power may be
supplied by an external source or a server. I/O terminals 6 provide a
means for external communications.
The public key of a trusted certification authority may be stored in PROM 4
or EPROM 3. PROM 4, or the RAM 5 if non-volatile, may have a section for
storing certificate revocation lists (CRLs). Such a list would include a
list of servers whose certificates have expired or been revoked. This list
would be provided by signed and dated messages from the trusted
certification authority either directly or indirectly while in a
communicating relationship with a server. Reference to the list during the
initial stages of the protocol will indicate whether the transaction being
initiated is with a valid server or with one holding a revoked
certificate, and thereby whether a received server's certificate is to be
verified.
The card manufacturer initializes the smart card using conventional
techniques. PROM 4 is loaded with an operating program to be executed by
processor 2, clock 8 is set (or an initial time-varying value, e.g., a
sequence number or a timestamp is set in one of the memories when a clock
is not used) and the certificate associated with the card and the trusted
certification authority's public key are loaded into the memories.
Optionally, server public keys and CRLs are also loaded into the memories.
A server 40 as illustrated in FIG. 2 includes a processor 60, a facility
for generating a time-varying value or timestamp 42, input/output port 63,
and a memory 61 for holding the operating program for the processor, the
private key PRIV.sub.SERV associated with the server's public key
PUB.sub.SERV and the public key PUB.sub.TCA of the trusted certification
authority that signed the client's certificate. In addition, memory 61 may
hold a certificate revocation list (CRL) and a certificate (CERT-S) for
its public key. The facility for generating a time-varying value 42 may
comprise a clock for generating a timestamp or other means for generating
a time-varying value. The I/O port 63 provides an interface between the
processor of the server and external entities.
FIG. 3A illustrates the processing by a client for generating and sending
messages to a server for use by the server to prove the client's
authenticity. A client at 101 generates or provides a time-varying value
(TS). This may be a timestamp or other value which changes with time. The
client also generates a random secret session key (KSS) at 102 employing a
number generator or other means to provide a random seed number. At step
103, the time-varying value TS and the secret session key KSS are
concatenated and at 104 the result is encrypted with the server's public
key PUB.sub.SERV which has been retrieved from memory 4 or 5. The
encrypted message {KSS.vertline.TS}PUB.sub.SERV is sent to the server at
107. The client's certificate (CERT-C) is retrieved from memory, EPROM 3,
at 105, encrypted with the secret session key KSS at 106 to form message
{CER-TC}KSS which is sent to the server at 108. The sending operations 107
and 108 may be combined into one operation.
FIG. 3B illustrates the processing at a server 40 of messages received from
a client via I/O port 63 for the purpose of ensuring the authenticity of
the client. Initially, the server decrypts at 201 the message
{KSS.vertline.TS}PUB.sub.SERV using its private key PRIV.sub.SERV
recovered from memory 61. At 202 the received time-varying value TS is
compared with a reference value obtained from the server's facility for
generating a time-varying value 42. Where the values do not compare an
error signal is generated at 207 and the process is terminated. Where the
time-varying values compare, the processing continues at 203 with recovery
of the secret session key KSS and at 204 by decrypting of the message
{CERT-C}KSS using the secret session key. This provides the server with
the client's certificate (CERT-C) which is then at 205 subjected to a
public key operation using the trusted certification authority's public
key PUB.sub.TCA retrieved from memory 61. At 206 a verification of the
certificate (CERT-C) is performed with the subsequent generation at 208 of
an error signal where the certificate cannot be verified or the generating
of an authentic signal at 209 where the certificate is found to be
authentic. The verification procedure at 206 may include the use of the
CRL stored in memory 61.
One embodiment of the invention is a non-interactive version where the
protocol requires only the sending of messages over a communications
channel by a client to the server with which it is seeking to execute a
transaction. In other interactive embodiments (FIGS. 4A, 4B and 4C), a
message, designated 11 in the drawing figures, containing information
needed by the client to produce authenticating messages for the server,
e.g., the public key of the server and/or a time-varying value provided by
the server, is sent by the server to the client. In a further interactive
embodiment (FIG. 5), the client has need of assurance of the server's
presence in the transaction and therefore requires a message signed by the
server. FIG. 6 represents a modification of the embodiments of the
invention due to the message generated by the client having the
time-varying value combined with the certificate of the client. FIG. 7
shows a version of the invention where a session key is not used.
Moreover, FIGS. 8 to 10 illustrate modifications to the embodiments of
FIGS. 5 to 7 wherein only a part of the client's certificate is encrypted.
Additionally, FIG. 12 illustrates a fundamental protocol whereby a user
can confidentially deliver to a verifier information which is essential to
verify a message signed by a credential issuing authority, but which may
be modified to include one or more features of other disclosed
embodiments.
In the non-interactive embodiment, there is no message 11 sent from server
40 to a client in the authentication protocol. The protocol is essentially
as shown in FIGS. 3A and 3B with a client configuration as in FIG. 1 and a
server configuration as in FIG. 2. The client upon gaining access to a
server 40 obtains the server's public key from a local storage, generates
a random secret session key KSS (102), concatenates (103) it with an
internally generated time-varying value, encrypts (104) the result with
the server's public key and sends the result to server 40 (107). The
client concurrently or subsequently retrieves its certificate (CERT-C)
from storage (105) encrypts (106) the certificate with the secret session
key and sends the result to server 40 (108). In the non-interactive
embodiment, there is no signing by the server or even the generation and
sending of a message by the server. The client's confidence in the server
is assured by the use of the server's public key, since only the server
can decrypt a message encrypted with its public key. The authenticity of
the client is established to the satisfaction of the server by its receipt
and verification of the time-varying value and the client's certificate by
processing the received messages in accordance with the procedure shown in
FIG. 3B.
In the interactive embodiments of FIGS. 4A, 4B and 4C, message 11 consists
of a certificate (CERT-S), a time-varying value, or a combination of a
certificate (CERT-S) and a time-varying value. These informational items
are provided to a client so that the client may properly form
authenticating message 12. FIG. 5 shows an interactive embodiment where
the server provides a signed message 11. Since FIG. 5 is the most
comprehensive, it will be described first, and the embodiments of FIGS.
4A, 4B and 4C described primarily with respect to differentiating features
caused by the differences in the content of message 11.
In FIG. 5, the parties to the electronic transaction are the client 20 and
the server 40. Messages 11, 12 and 13 are generated and exchanged between
the client 20 and the server 40 over a communications channel 15.
Successful exchanges of the messages establish the trust of the client 20
in the server 40 and the authenticity of the client 20 to the server 40.
Communications channel 15 may simply be electrical connections between a
card reader and the terminal equipment at a server or may be in the form
of a telephone or other communications link established between a client
and a remote server, or other conventional communications medium.
Client 20 includes a certificate (CERT-C) 21 stored in EPROM 3, a key
generator (KEY) 22, a facility for generating a time-varying value (TS) 23
which may include the clock 8, when used, and the public key (PUB.sub.TCA)
24 of the trusted certification authority which may be stored in EPROM 3
or PROM 4. Certificate 21 comprises a message provided and signed by the
trusted certification authority with its private key in the standard
manner. The message in this instance need not be the client's public key
because this key is not involved in the protocol. Any message is
sufficient and may be certain well structured information about the
client, e.g., account number and expiration date of the account. The
message may also indicate the types of transactions for which the client
20 is authorized and the period of time during which the certificate may
be considered valid. The key generator 22 is comprised of any conventional
means of generating an encryption key. It may comprise a subroutine in the
processor and use a number supplied by a number generator 7. The facility
23 may comprise conventional clock 8 that provides a current date and time
or may be one that operates on a received timestamp or time-varying value.
Key 24, the public key of the trusted certification authority, is used to
verify a certificate sent by the server and signed by the trusted
certification authority.
Key storage unit 25 represents an optional memory or memory section for
storage of keys of one or more frequently used servers. These are the
public keys of servers and are made available to clients by the servers.
Storing the public key of server 40 and other selected servers at the
client avoids the need to process the certificate from a server to recover
the key, or provides a source for the key where the certificate does not
contain the public key or an easily recoverable copy of the public key of
the server. CRL storage unit 26, also an optional memory or memory
section, stores a list of certificates that have been revoked.
Elements 30 through 35 illustrate the functional processes of the protocol
performed by the client to establish trust in the server. Public key
operations are conventional well known processes in the art. Recovering
the public key of the server from the server's certificate for the key and
storing it in a memory, as illustrated in block 30, is a certificate
processing within the skill of art.
Functional element 32 represents a public key operation performed with the
trusted certification authority's public key 24 on the certificate portion
of the message 11 received from the server 40. Functional element 31
represents a public key operation performed on the timestamp or other
time-varying value received from a server with the server's public key
obtained from processing the certificate at read and store element 30 or
from key storage unit 25. At functional block 33 a standard verification
procedure, as those skilled in the art appreciate, is used to verify the
certificate. A certificate revocation list supplied from memory 26 may
optionally be used in verifying the certificate.
Functional element 34 represents a comparison and verification of the
timestamp or time-varying value received from the server 40 to verify that
it is proper. Where the smart card or client has a clock, a simple
comparison (allowing for small time differences) of the time at clock 8
with the time of the received timestamp suffices to verify a received
timestamp. Where the smart card does not include a clock, the stored time
of a last received valid timestamp can be compared with the time of the
currently received timestamp to verify that the currently received
timestamp is later in time. Any time-varying value may be received and
processed to verify that it is of recent origin or in a proper time
sequence.
Failure to verify the server's certificate or time-varying value
(illustrated by the NO outputs of elements 33 and 34) results in an error
and termination of the transaction. Symbol 35 is a representation that
permits further processing, i.e. the generation of the secret session key,
when both the received certificate and time-varying have been verified
(indicated by YES outputs of elements 33 and 34).
Elements 36, 37 and 38 illustrate the functional processes performed by the
client 20 to generate messages 12 and 13. Message 12 is generated by
concatenating the session key 22 and the time-varying value from facility
23 at element 36 and performing a public key encryption on the combination
in public key operation 37 with the public key of server 40 retrieved from
read and store element 30 or key storage unit 25. Message 13 is generated
by performing an encryption at element 38 on the certificate 21 with the
session key 22.
The functional elements and blocks of client 20 define operational steps
performed by a processor, e.g., processor 2 of FIG. 1. Similarly, the
functional elements and blocks of server 40 illustrate operational steps
performed by the server's processor 60.
Server 40 of FIG. 5 includes a certificate (CERT-S) 41 provided by the
trusted certification authority, a facility for generating time-varying
values (TS) 42, the private key of the server (PRIV.sub.SERV) 43 and the
public key of the trusted certification authority (PUB.sub.TCA) 44.
Certificate 41 is a certificate for the server's 40 public key, and
contains a message which includes the server's public key and that
identifies the server as a valid and authorized holder of the public key.
Facility 42 may be provided by a clock. The key 43 is the server's private
key of the public key/private key pair used in standard public key
cryptography. Key 44 is the public key of the trusted certification
authority. CRL 45 is an optional element that stores certificate
revocation lists for both server's and client's certificates. These lists
are signed, dated messages received from the trusted certification
authority. The server CRL is for forwarding to a client during the herein
described protocol or ancillary to the protocol. The client CRL would
serve, for example, as a list of revoked smart cards, i.e., cards that
have been lost, stolen, destroyed or that have expired.
The server's certificate and private key, the public key of the
certification authority and the CRL are stored in memories of the server.
These memories are accessed by a processor of the server in accordance
with an operating procedure for executing the authentication protocol.
Elements 17 and 18 illustrate the functional process for generating message
11. The time-varying value from facility 42 is signed with the private key
43 of the server 40 in private key operation 17. The signed time-varying
value is then concatenated with the certificate 41 in the concatenate
operation 18 to thereby form message 11.
Blocks and elements 51 through 56 represent functional processes of the
protocol performed by the server 40. Functional element 51 performs a
private key operation with the private key 43 on the received message 12.
A comparison at 52 provides verification of the time-varying value
received from the client 20. This may be done by comparing a timestamp
received with the current timestamp of a clock from facility 42, or by
storing a time-varying value sent to the client and comparing the stored
time-varying value with the time-varying value returned by the client to
see that they are in correspondence. Gate symbol 53 represents the
permissive continuation of the processing upon the verification of the
receipt of a proper time-varying value. Functional element 54 performs a
decryption of the message 13 using a key 22 received from the client 20.
Functional element 55 performs a public key operation on the certificate
with the public key 44 of the trusted certification authority. Block 56
provides for the verification of the certificate with or without the CRL
of clients in a manner well understood by those skilled in the art.
Initially, the client 20 may have to gain the trust of the server 40 before
it will reveal its certificate 21. This protects against revealing the
certificate to unauthorized third parties who could then use the
certificate to impersonate client 20. Client 20 gains the trust of the
server 40 through a public key protocol.
Considering the FIG. 5 illustration, so that client 20 may gain its trust,
upon a request for access the server 40 reveals its certificate 41 by
combining the certificate 41 with the signed time-varying value from
facility 42 to form message 11 CERT-S{TS}PRIV.sub.SERV. Client 20 receives
the message 11 sent over the communications channel 15, verifies the
signature on the certificate with the trusted certification authority's
public key 24 in public key operation 32 and verification process 33, and
processes the certificate in operation 30 to read and store the public key
of the server. Client 20 then uses the public key of the server in public
key operation 31 to obtain the time-varying value. As indicated above, the
public key of server 40 alternatively may be retrieved from public key
storage unit 25 where used. Checking of the time-varying value to see that
it is valid is done in comparison unit 34. A failure to verify the
server's certificate or validate the received time-varying value
terminates the transaction. Signature verification, particularly for RSA,
is computationally inexpensive, so the computational burden on the client
20 is minimal. As an additional step in certificate verification, the
client 20 may check the values of one or more fields of the certificate 41
to determine whether the server 40 is authorized for transactions with the
client 20. It is presumed that the trusted certification authority of
interest issues authorized certificates only to trusted servers, so the
pair of signature verifications is sufficient for the client 20 to gain
trust in the server 40.
Once client 20 verifies the time-varying value from 42 and the certificate
41 of server 40, trust of the server 40 is established. Thereafter, client
20 generates a random secret session key (KSS) at 22, combines this key
with its time-varying value (TS) generated by a clock at 23, or where no
clock is present replicates the time-varying value received from the
server, to form a message and encrypts the message with the public key
(PUB.sub.SERV) of server 40 obtained from storage at element 30 or 25 to
form the encrypted message 12. Again, for RSA, encrypting with the
server's public key is computationally inexpensive so this is not a burden
on the client.
The encrypted message 12, {KSS.vertline.TS}PUB.sub.SERV, is sent to the
server 40 where it is received and processed for recovery of the secret
session key KSS by decrypting the message 12 with private key 43 in
private key operation 51. A checking of the time-varying value TS
demonstrates to the server 40 that a client is active in the transaction,
not an impersonator replaying a recorded message.
Client 20 then encrypts its certificate 21 using the secret session key to
produce encrypted message 13, {CERT-C}KSS, and sends it to server 40.
Messages 12 and 13 may be combined as one message
{KSS.vertline.TS}PUB.sub.SERV {CERT-C} KSS. Server 40 receives the
encrypted message 13 and decrypts it in decryption operation 54 to gain
the client's 20 certificate 21. Certificate 21 is processed in public key
operation 55 with the trusted certification authority's public key stored
at 44. After verification at 56, with or without the optional CRL in unit
45, the authenticity of client 20 is accepted by server 40 and the
transaction can be undertaken.
When clocks are used for both timestamp facilities, the client and the
server need to account for variations in their clocks when checking that
the timestamp received is current. One procedure is to determine the
difference between the two clock timestamps, for example, the client
determines the difference between the received timestamp and its own clock
generated timestamp, and compares that difference to a pre-set reference
value to see that it is less than the reference value. Other techniques
known to those skilled in the art may be used to account for the clock
variations. See, for example, Weiss, U.S. Pat. No. 4,885,778, entitled
"Method and Apparatus for Synchronizing Generation of Separate Free
Running, Time Dependent Equipment," which describes a technique for
synchronizing client and server clocks in an authorization protocol.
In place of a timestamp a challenge may be used. A challenge may comprise
any-time varying message that can be processed and verified.
The client may also store a CRL of servers. Either as a part of the
authentication protocol or subsequent thereto, the server and the client
may exchange lists of revoked certificates.
In the embodiment illustrated in FIG. 4A, message 11 consists of the public
key certificate 41 of server 40. Here, client 20 does not have or need to
have prior possession of the server's public key. Possession of the
server's public key is acquired by the client receiving and reading the
public key certificate 41. The signature on the certificate is verified
with the Trusted Certification Authority's public key 24 and the
certificate is verified by conventional verification procedures as
discussed in the description of FIG. 5. This public key of the server is
then used in public key operation 37. The time-varying value is generated
locally at facility 23. As seen from FIG. 4A, client 20 comprises only the
elements, e.g., 24, 32, 33 and 26 to verify the certificate and its
signature and a functional element 30 to read the received certificate 41
and store the public key PUB.sub.SERV. The server's processing to form
message 11 involves only the sending of its certificate 41. The remainder
of the components, functional elements and operations of FIG. 4A
correspond with those in FIG. 5.
In the embodiment of FIG. 4B, the message 11 consists of certificate 41 and
a time-varying value TS. The time-varying value TS is needed where a
client 20 does not have a facility for generating its own time-varying
value. Thus, as shown, server 40 forms message 11 by concatenating at
element 18 the certificate 41 with the time-varying va | | |
