 |
Douglas H. Steves -
dhs@cs.utexas.edu
Chris Edmondson-Yurkanan -
dragon@cs.utexas.edu
Mohamed Gouda -
gouda@cs.utexas.edu
Department of Computer Sciences
The University of
Texas at Austin
Austin, Texas 78712-1188
Existing protocols used for electronic commerce focus primarily on security properties, including message integrity, privacy and non-repudiation, and on basic transaction properties, usually just atomicity; their structural properties are limited to supporting two-party transactions with fixed semantics. We believe that the properties provided by these protocols limit their use to simple forms of commerce.
In this paper we define the properties we believe are necessary for electronic commerce protocols. These include the security properties of existing protocols, and extend the transactional properties to include isolation and causality. Causality is a new property for transactions. It allows the order of the messages in a completed transaction to be independently verified, and thus inferences can be made about causal relationships between messages.
We also extend the structural properties to support scalability, layering and separation of roles. Scalable protocols allow several parties to join each transaction. Protocol layering enables arbitrary transaction semantics and greater system modularity. Separation of roles provides independent adjudication of disputes between transaction participants and allows the use of varied exchange media.
We term a protocol with the above properties a secure transaction protocol.
Lastly, we present a protocol that provides these properties. We believe that this protocol can be used to support more complex and extended forms of electronic commerce than existing protocols.
Protocols with limited properties will have correspondingly limited application in electronic commerce. For instance, a protocol without privacy could not be used for a commercial transaction which must be kept secret. Similarly, a two-party protocol could not be used for a commercial transaction which involves three or more parties.
In this paper we explore the security, transaction and structural properties that can be incorporated into the protocols used for electronic commerce in order to increase the forms of commerce that can be performed electronically. Security properties enable access control and accountability;[4] transaction properties allow the definition and verification of the relationship between messages; structural properties define the relationship between protocols as well as the relationship between the processes executing those protocols.
The initial electronic commerce protocols allowed for the exchange of multiple messages, and so extended these properties to define a session identifier and a session key which are used for all messages in the transaction. Examples of these protocols range from Secure Sockets Layer (SSL)[2] to Secure Electronic Transactions (SET)[16].
Isolation prevents the goods or money exchanged in one transaction from being used in another transaction until and unless the first transaction is successfully concluded. Consider a building contractor who orders cement from a subcontractor for one job and then uses that cement in another job before completing the earlier transaction. If the first transaction is cancelled, it may not be easy for the subcontractor to recover the cement. While it is normally feasible to rollback database transactions, it is not easy to `undo' the foundation of a house.
Note that the relational properties of atomicity and isolation are also familiar from classical database theory [3], where they provide for computational separation of transactions.
Verifiable causality allows the sender or receiver of a message to demonstrate the sequence of messages that could have caused that message. In other words, it allows the order in which messages were sent or received during a transaction to be proven.
If some of these data messages constitute a negotiation between the processes of the transaction, then verifiable causality ensures that each process can prove exactly how the negotiation proceeded. More formally, one of the basic requirements for legal contracts is the demonstration of a causal relationship between the items being exchanged.
Multi-party transactions are common in commerce. Consider the case of the building contractor described above. The contractor would not wish to be responsible for purchasing the cement if the buyer should decide not to build the house, and so would want any commitments made during each subtransaction to be dependent upon the successful conclusion of the entire transaction.
The agreements made between the primary contractor and the subcontractor are part of the same economic transaction, and so need to be part of the same electronic transaction as well. Since the SSL, SET and NetBill protocols are all based upon two primary parties, the customer and the merchant, these protocols could not be used for multi-party electronic commerce.
Note that the transaction properties, such as atomicity, are even more important for multi-party transactions. In two party transactions, either physical proximity or trust based upon long standing relationships can lessen the need for protocol-enforced atomicity. But neither of these are likely to apply in multi-party transactions, where many parties may be unacquainted.
Commercial transactions vary considerably in semantics, and many are unique. Using a layered approach allows the semantics of exchange to be separated from the security and transaction properties, so that these mechanisms can be invoked according to the requirements of each type of commerce. In addition, layering enables these mechanisms to be shared with other distributed applications.[7]
This approach is more general than designing entirely separate protocols for each type of transaction. In SET, for instance, the structure and security properties of the protocol are specific to purchases made with credit cards. Thus, this protocol is not suited to other forms of commerce, which would require their own protocols.
The last structural issue we would like to discuss is separation of roles. This property, common in government and also found in secure computer systems, allows for independent adjudication of disputes.
For example, the building contractor and the cement subcontractor may disagree about the price or deadlines for the foundation work. Without a record of their agreement which can be verified by an independent party, there would be no fair way to resolve the dispute.
For electronic commerce, the party that verifies and enforces agreement on transactions is a commit authority. In NetBill, for example, the commit authority is the bank. But the bank is involved in the transaction since it is supplying one of the exchange media. Moreover, the bank is likely to have different relationships with the parties to the transactions. Thus the bank cannot be an impartial arbitrator.
An additional benefit of the logical separation of transaction commitment and exchange is that the protocol applies to forms of commerce such as barter where the exchange medium is ad hoc or unique. If these functions are not separated, however, the protocol would need to be modified each time the exchange medium changes.
In the second section of this paper we further discuss the protocol transaction and structural properties, and describe how they are supported in our protocol. In the third section, we describe our secure transaction protocol.
In later work we provide a more formal description and an implementation of our protocol. We also expect to explore the layering of specific forms of commerce on top of our protocol.
With secure transaction protocols, of course, we are not concerned with the correctness of data in persistent storage, but rather that data messages are not used or referred to unless their corresponding transaction has been properly committed. This can be accomplished by:
Atomicity is described more fully in [15], where it is incorporated into the NetBill protocol. The approach in this paper is more general, using a separate two-phase commit protocol which does not depend upon the nature of the transaction.
Isolation is only implicitly addressed in NetBill, since nothing of value is exchanged until the transaction is committed by the NetBill server. The validity of this approach depends upon a limited transaction model. For more general forms of commerce, we believe that transaction isolation can only be achieved by a systematic mechanism that effectively limits message propagation until and unless the message's transaction is successfully committed.
The time of a message can be defined by associating a physical or logical timestamp with each message. Physical clocks define a total order, but are problematic due to clock synchronization errors. Logical clocks define a partial order which is sufficient to demonstrate causal relationships.[5]
The context of a message can be defined by including in each message unpredictable and unique elements from earlier messages. These elements could be the message itself[1,6] or a random number bound to the message. The first approach is inefficient and may violate the privacy policy for multi-party transactions, but these issues can be addressed by using message digests[10]. Random numbers, on the other hand, are difficult to generate correctly.
For effective use of causality in electronic commerce where the parties are usually distrustful, the protocol must enable verification of causal claims, both by the receiver, which may wish to reject invalid messages, and by independent arbiters, in order to settle disputes.
There are two types of causal claims: assertion, where a causal link between two messages is claimed, and denial, where a causal link between two messages is disclaimed. Causal assertion may be verified by having the causal information (e.g. logical clock) authenticated by its originator and by having the message sender authenticate the association of this information with the message.
In [12], the authors define a secure causality protocol based upon vector timestamps. When a process sends a message, it updates and signs its component of the vector timestamp that is included in each message. When a process receives a message, it updates any outdated components of its clock from the timestamp included in the message. In [8], the authors define a similar secure causality protocol based upon message contexts. When a process sends a message, it signs the message digest, which is included in the message along with the set of digests the process had previously received. When a process receives a message, it adds the included digests to its own set.
Both of these protocols implement the first requirement for verifying causal assertions, since the causal information is always signed by its originator. They, however, do not do not have the sender authenticate the association between the message and the causal information.
For instance, in the protocol described in [8], the receiver of a message could use the sender's signed message context to prove that the sender did, in fact, send this message. But since the signature does not include the set of other message digests, the causal relationship between the message digests and the message itself cannot be verified by either the receiver or an independent arbiter.
Causal denial is more difficult to verify than causal assertion. In the general case, it would seem to require a protocol in which all messages are delivered by a trusted third party that would safely record the message sequence. This would introduce both performance and reliability problems. We have not, however, found the verification of causal denial to be important for electronic commerce, and thus do not address it in our protocol.
Our protocol is based upon message context, because this allows for the verification of the reception and transmission of specific messages rather than a specific number of messages. Each message includes authenticated context information which meets both of the above requirements for verifiable causal assertions.
At the conclusion of the transaction, the context is used in the commit protocol in order to ensure agreement among all parties. The committed context can then be used later to resolve any disputes that might occur regarding message ordering.
The semantics of a protocol are defined by its allowed sequences and types of messages. Our protocol does not define the type of data that can be transferred - only the messages used for transaction initiation and termination are specifically defined. In addition, data messages are sent and received non-deterministically, so that any sequence of messages is allowable using our protocol. Thus, our protocol is semantically neutral.
When the transaction finishes, the commit authority runs a commit protocol to determine whether the transaction was successful. If the transaction is successfully committed, then the parties can safely exchange the goods, services or money according to the transaction.
By separating the role of commit authority from that of the parties involved in the exchange, arbitration of disputes can be performed by a neutral party. Separation of roles is achieved in our protocol by defining a logically separate commit authority process, which performs only functions relating to transaction initiation and termination.
Each process has a unique identity (UID), a signature key that can be used to sign messages and a verification key that can be used by other processes to verify its message signatures.
An ST process knows its own UID and signature key. It also knows the UID and the verification key for the CA process. ST processes obtain the verification keys for other ST processes from the CA during transaction initialization. Each message is authenticated by the sender by signing the message digest of the message (including message type).
Each transaction in the system has a unique identifier (TID). A transaction contains one or more subtransactions, and may have a separate subtransaction for each process-pair in the system. A subtransaction is identified by its TID and by the unordered UIDs of the two processes in the subtransaction.
Each ST process maintains context for each subtransaction in which it is participating. The context defines the message order in the subtransaction and is computed when a new message is sent or received by taking the message digest of the concatenation of the old context and the new message. The context is included in all data messages so that the data being sent is effectively represented as the result of previous messages.
A transaction begins when one process attempts to begin a subtransaction for an unused TID. If both parties accept, the transaction begins with a single subtransaction. Each party can then have other processes join the transactions by beginning new subtransactions.
For each subtransaction the process stores the current state of that subtransaction, the data messages sent and received, and the other process's verification key.
Within a subtransaction message transfer is half duplex, controlled by a send token. Only the party with the send token can transmit messages or choose to end the subtransaction. This limitation makes it easy to define the total order of messages necessary for correct commitment.
The message sequence as well as the data format and content are not defined or constrained by this protocol. This makes it possible to use STP as the basis for general forms of commerce.
At the end of the subtransaction, each process can choose to commit or abort. An abort will end the whole transaction. Commitment is done on a per subtransaction basis, and is dependent upon both the commitment of the processes and their agreement on the subtransaction context.
These message transfers are depicted in Figure 1.
In this figure, P and Q are ST processes, while CA is the
commit authority.
This protocol assumes that the underlying message transport mechanism will provide reliable, ordered communication except in the presence of severe media failures or in the event of an adversarial attack. If the communication channel cannot confirm the correct delivery of a message, it will return a fault exception to the process.
ST processes communicate with the CA only when they begin or end a subtransaction. At the beginning of a subtransaction, each process must notify the CA whether they wish to accept or reject the subtransaction. Once the CA has heard from both processes, it will notify them of the transaction status and, if both have accepted, pass one of them the send token for the subtransaction.
At the termination of the subtransaction, both ST processes must notify the CA whether they wish to commit or abort the subtransaction. In the commit message, each process must include the final context for that subtransaction, which defines the state of the subtransaction. If both processes commit and both processes report the same context, then the CA will mark that subtransaction as committed.
If any subtransaction is aborted, then the CA will abort the entire transaction. If all subtransactions eventually commit, the CA will commit the transaction.
The CA can also be queried for the status of any transaction. This information can be used by exchange authorities to determine if the exchange of goods, services or money should proceed.
In the following sections, we define STP, in terms of protocol messages, states and and state transitions.
Subtransactions move between states according to messages sent or received.
Invalid messages (those without a verifiable signature or that are not
acceptable in the current state of the subtransaction) are discarded. The
subtransaction state machine for the ST process, excluding certain less
important message types and states, is depicted in Figure 2.
The ST subtransaction states and state transitions are:
Each ST process also maintains state for each transaction. The transaction state changes according to local process subtransaction state changes and global transaction state changes at the CA. The ST transaction states and state transitions are:
Subtransactions move between states according to messages sent or received. Invalid messages (those without a verifiable signature or that are not acceptable in the current state of the subtransaction) are discarded. The CA subtransaction states and state transitions are:
The CA also maintains state for each transaction. The transaction state changes according to subtransaction state changes. The CA transaction states and state transitions are:
In this paper we have presented a protocol for secure transactions that provides the new or extended properties of atomicity, isolation, verifiable causality, scalability, layering and separation of roles, as well as existing properties of integrity, authentication and non-repudiation. This protocol can be used to enable electronic transactions for more complex forms of commerce than are currently supported by existing electronic commerce protocols.
This protocol is complementary to existing secure message protocols, in that existing elements like cryptographic signatures used in a compatible manner, and new elements like context are orthogonal to the other elements in existing protocols. Thus, the properties can also be added easily to these protocols.
Chris Edmondson-Yurkanan is a senior lecturer at the University of Texas. She has a B.A. in Mathematics and Computer Sciences and an M.A. in Computer Sciences from the University of Texas.
Mohamed Gouda is the Mike A. Myers Centennial Professor at the University of Texas. He has a B.S. in Engineering and a B.S. in Mathematics from the University of Cairo, an M.S. in Mathematics from York University (Ontario, Canada), and an M.Math. and a Ph.D. in Computer Science from the University of Waterloo.
This document was generated using the LaTeX2HTML translator Version 98.1p1 release (March 2nd, 1998)
Copyright © 1993, 1994, 1995, 1996, 1997, Nikos Drakos, Computer Based Learning Unit, University of Leeds.
The command line arguments were:
latex2html -split 0
-no_navigation -show_section_numbers -no_auto_link -toc_depth 4 pstp.
The translation was initiated by Douglas H. Steves on 1998-12-17
