|
USENIX Symposium on Internet Technologies and Systems, 1997   
[Technical Program]
Lightweight Security Primitives for E-CommerceAbstractEmerging applications in electronic commerce often involve very low-cost transactions, which execute in the context of ongoing, extended client-server relationships. For example, consider a web-site (server) which offers repeated authenticated personalized stock quotes to each of its subscribers (clients). The value of a single transaction (e.g., delivery of a web-page with a customized set of quotes) does not warrant the cost of executing a handshake and key distribution protocol. Also, a client might not always use the same machine during such an extended relationship (e.g., a PC at home, a laptop on a trip). Typical transport/session-layer security mechanisms such as SSL and S-HTTP either require handshake/key distribution for each transaction or do not support client mobility.We propose a new security framework for extended relationships between clients and servers, based on persistent shared keys. We argue that this is a preferred model for inexpensive transactions executing within extended relationships. Our main contribution is the design and implementation of a set of lightweight application-layer primitives, for (1) generating and maintaining persistent shared keys without requiring a client to store any information between transactions and (2) securing a wide range of web-transactions (e.g., subscription, authenticated and/or private delivery of information, receipts) with adequate computational cost. Our protocols require public key infrastructure only for servers/vendors, and its usage only once per client (upon first interaction). IntroductionConsiderable attention has been given recently to transport/session-layer security mechanisms. There are several proposals and implementations available, including SSL [SSL96], S-HTTP [SHTTP95], and SSH [SSH96]. Offering security mechanisms at the transport/session layer has the advantage of obtaining universal security primitives which have wide applicability (e.g., SSL or SSH can be used in conjunction with any TCP connection). However, universality in the proposed schemes comes at the expense of lacking flexibility with respect to complexity and cost of securing transactions, which vary in terms of their monetary value. In particular, web-transactions within the same client-server relationship but executing at different times, either appear unrelated to the transport layer or require the client to store data in secure memory, thus putting additional responsibility on the client and preventing mobility.Emerging applications in electronic commerce often involve very low-cost transactions, which execute in the context of an ongoing, extended client-server relationship. Rivest predicts in [R97] the increase of low-cost transactions and the need for ``low-cost crypto''. For such transactions, general-purpose security mechanisms tend to be prohibitively expensive. In particular, both SSL and S-HTTP involve handshake/key-distribution that consist of a costly public key cryptography. We argue that a framework based on a shared key between a client and a server, persistent for the whole duration of a relationship, is an attractive choice. From a technical point of view, the main challenge is in obtaining low-cost establishment and maintenance of the persistent shared keys, in a transparent and mobility-enabling fashion for clients. We propose a novel mechanism for persistent, shared key generation and management on the client-side. We then leverage this approach to obtain basic security primitives well suited for securing low-cost transactions which repeatedly execute between a client and a server. Such transactions may span a variety of applications, from two party tasks to elaborated micro-payment schemes involving banks, arbiters, vendor, clients, and more. In particular, concrete applications may include (1) delivery of personalized information by a vendor (via web-pages) which ensures privacy, authenticity, and integrity for each client (e.g., authentication of personalized stock quotes which a vendor sends to a client on a daily/hourly basis); (2) support for secure subscription of such services; (3) delivery of receipts to a client which ensures authenticity and integrity, provable to a third party; and (4) support and integration for (micro)payments, such as SET [SET] and PayWord [RS96]. Our approach has the following noteworthy technical aspects:
The client interface is simple. Upon first interaction with the client-proxy (e.g., when starting to run a browser), she provides her identity (e.g., e-mail address) and a secret; she can then reconnect transparently to any server with appropriate session information. Our scheme does not require a client to obtain and maintain her own public and private keys (certificates). The client information (identity, secret) can alternatively be stored on a smart-card, or in a secure file, and be submitted to the client-proxy automatically on the client's behalf. The proposed scheme further gains computational efficiency via minimizing the use of public-key cryptography. Organization of the Paper: Section 2 presents the client-side generation and management of secret shared keys. In Section 3 we introduce our key establishments and data delivery protocols based on the shared key of Section 2. Section 4 extends our protocols to avoid exposure of the shared key. In Section 5 we show how receipts can be generated to help in potential conflicts between clients and vendors. Finally, we discuss implementation issues in Section 6. Client-side key generation and managementIn our scheme, it is up to the client to compute a different secure persistent shared key for each vendor (server) she interacts with. She submits to the vendor an ``identity'' (e.g., email address) and a shared key, which are to be used by both parties during their subsequent interactions. The shared key is private and should be protected during communication; hence, before submitting the shared key, the client uses the vendor's public key to encrypt it. Public-key encryption is used only during the first interaction with a vendor. After this first exchange, both the client and the vendor can use the secret shared key in their subsequent interactions to authenticate and encrypt data with low computational cost. An important aspect of this scheme is the method by which a client computes her shared keys. A shared key is computed as a function of three arguments: the client's unique identity (e.g., e-mail address), a (single) secret provided by the client, and the identity of the vendor (expressed, e.g., as as the domain name in the vendor's URL). The function computes a string with the following properties (with respect to an adversary with polynomially bounded computational power):
For the rest of the paper, we consider the client to be the combination of user, the user-interface (e.g., browser), possibly a user-assisting program (e.g., plug-ins to the browser), and the client-proxy. Whenever we say that a client computes or executes an operation, we mean that the computation or execution is done by the client-proxy. Whenever we say the client supplies input (e.g., id or secret), we mean that the user provides the input through the user interface, or that a user-assisting program does it on the user's behalf. Design of the key generating function To meet the desired properties
listed above, we propose to use the Janus function
In [BGGMM97] it is shown that
the function A vendor stores each client's identity and the shared key (possibly along with some other data, such as a client's preferences) on the very first interaction with a client, so that it can retrieve the corresponding key upon being presented with a client's identity on a repeat visit. Basic protocolsIn this section, we describe the basic protocols used for establishing persistent shared keys, and for subsequent interaction between a client and a server. We also present a model and correctness arguments for our protocols. At the same time, we caution that a careful development of model and correctness proofs (as shown in [BR93] for a simpler, well-known protocol) is beyond the scope of this paper. First, we present the Simple Key Establishment Protocol (SKEP) for establishing relationship between a client and a server, by having the client provide the server with the persistent shared key and some other identifying or payment related information. Then we present the Simple Data Delivery Protocol (SDDP) for the subsequent interactions involving data delivery, and the more robust Extended Data Delivery Protocol (EDDP). In the following, let ModelIn order to interact, a vendor V and a client C form a ``session'' s, during which a single shared key is first established and then used. Let the two threads![]() ![]() We assume the presence of a polynomially bounded adversary E, which is in charge of the communication (e.g., sending, deleting, reordering of messages) and can execute the following actions:
![]() Simple Key Establishment Protocol (SKEP)The SKEP protocol (illustrated in Fig. 1)
is used when a client C requests to register (or subscribe) at a
vendor V for the first time in order to subscribe. First, the client
computes the appropriate persistent shared key Desirable properties of a key establishment protocol include Key Authentication, Entity Authentication, and Key Confirmation, which we now define in turn: We note that the above definition of Entity Authentication is essentially borrowed from [BR93], where a more in-depth discussion and model can be found. Proof: For an unopened session s, adversary E can
only obtain Note that we define entity authentication, in the sense that a client can be assured that it consistently interacts with vendor, and vice versa. In the SKEP protocol, identity information is obtained via a client using a vendor's certified public key and a vendor using a client's payment data, such as credit card or SET data. This is consistent with today's business model of popular web-sites. For instance, on-line subscriptions to the Wall Street Journal and to ESPN Sportzone, and on-line book purchases at amazon.com require only this ``weak authentication'' from their clients. Non-repudiation Key Exchange ProtocolSKEP is lacking the non-repudiation property, i.e., the possibility for a client to obtain a receipt, provable to a third party, for its subscription. SKEP can be extended by one more message exchange to obtain non-repudiation by having the vendor V sign the subscription data of the client; see Fig. 2.Simple Data Delivery Protocol (SDDP)The SDDP protocol (illustrated in Fig. 3) is used when a client C requests from a vendor V some information![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() Desirable properties of a data delivery protocol include Data Privacy, Entity Authentication, and Data Integrity, which we now define in turn: We mention without proof that SDDP fulfills Data Privacy, Entity Authentication for the client and Data Integrity. (The proofs can be derived from the proofs we give in the subsequent section for the EDDP protocol.) However, SDDP provides no Entity Authentication to the vendor. As a consequence E can prompt the vendor via impersonation attacks to send data (even though it might not be readable by E). This might be a problem in terms of chosen message and denial of service attacks. The variant in the next section is more robust in that sense. Extended Data Delivery Protocol (EDDP)The EDDP protocol (illustrated in Fig. 4) requires the client to demonstrate her possession of the appropriate shared key. A request of a client C from a vendor V for information![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]()
Proof:For an unopened session s, E can only obtain
the corresponding encryption EDDP provides Entity Authentication to the vendor, before he sends any data and hence gives better protection against chosen plaintext and denial of service attacks. Furthermore, the exposure of the shared key is better protected, since only the corresponding client can prompt the vendor to use it for encryption/authentication. We note that the state of art in modeling and proof techniques (e.g., see [BR93]) does not consider key exposure. DiscussionThe different applicability of the given protocol-variants can be illustrated by the following examples:Example 1: Free Personalized Stock Quotes.
Example 2: Subscription to Personalized Stock Quotes.
Computational cost and memory requirement of the protocols: The vendor has to sign a single message per client (none with SKEP). All subsequent communication is done via symmetric encryption/MAC. The client has to encrypt (public-key) a single message per vendor upon first interaction, and only MAC in subsequent interactions with that vendor. In addition, the client has to compute one Janus function per browsing-session and vendor. The client does not need any longterm memory. The vendor needs to store a persistent shared key K for each of its clients. Typically, a vendor stores some information about each of its client in any case, so this does not put an extra burden on the vendor. Avoiding exposure of the persistent shared keysIn this section, we show how to extend the protocols presented in Section 3 so that (1) the exposure of the shared key K is minimized and hence cryptanalysis is made more difficult and (2) reuse of compromised keys is prevented. We consider the notion of a session-key Note that the above method has the disadvantage of introducing ``state'' to be kept on both the client and the vendor, namely the counter n. In order to mitigate this drawback, we suggest that the counter be replaced by a strictly monotonic increasing function of the time (standard GMT), with a pre-specified granularity (e.g., day, hour, or minute) that should depend on the accuracy of the time of the client and server. One complication in this approach is that even with high accuracy, there may be discrepancy between two parties (e.g., around midnight when the unit is a day). To alleviate possible conflicts, we let the client determine the time function and notify the server during a first message. The server will accept the time function received from the client if it is the same as computed locally, or if it is within a (pre-determined) reasonable range from its computed time function (e.g., within an hour). Extending the data delivery protocols to enable receiptsConsider the situation, where a client complains that she paid for a subscription of stock quotes, but never got information from the vendor. A third party cannot decide if indeed the vendor is at fault. We propose to adapt a technique used in the micro-payment protocol ``PayWord'' (see [RS96]) to obtain the notion of receipts.Assume for example that a subscription is for a month and that it entitles
a client C to obtain stock quotes once a day. C chooses at
random a value r and sets The vendor can present ImplementationAlmost all cryptographic methods used in our proposed framework are
available in standard cryptographic libraries. The only exception is the
function The LPWA software also forms the starting point for our first (and currently ongoing) implementation of the protocols presented in this paper. The protocols on the client-side are realized by a web-proxy, just as in LPWA. The client identifies herself to the proxy via proxy-authenticate. The web-proxy implements the Janus-function and embeds the client-side protocols into the client's HTTP-requests before forwarding them to the server. In line with our lightweight approach, HTTP headers are authenticated, but never encrypted. Care is taken that the sever can easily retrieve (and verify) the client's identity. The protocols on the server-side are realized via CGI (and FastCGI, see https://www.fastcgi.com/) scripts written in C. The goal of our first implementation is to obtain performance figures on the server-side to shed light on at least the following two issues: (1) Absolute measures of the cryptographic overhead and (2) the cryptographic overhead relative to minimal CGI-scripts (e.g., ``Hello World'' script) and scripts used in actual servers. Another interesting direction is to explore ways to integrate our client-side key management scheme with SSL. This potentially yields a scheme which works works with current Web servers, but allows client mobility and requires no secure client-side long-term memory. AcknowledgmentsWe thank Daniel Bleichenbacher for helpful discussions on secure protocol design and David M. Kristol and Eran Gabber for advice on software design.References
Alain Mayer Wed Oct 22 14:57:26 EDT 1997 |
This paper was originally published in the
Proceedings of the USENIX Symposium on Internet Technologies and Systems,
December 8-11, 1997,
Monterey, California, USA
Last changed: 12 April 2002 aw |
|