Home About USENIX Events Membership Publications Students
USENIX Technical Program - Paper - Proceedings of the 3rd USENIX Workshop on Electronic Commerce, 1998    [Technical Program]

Electronic Commerce and the Street Performer Protocol

John Kelsey and Bruce Schneier
{kelsey, schneier}@counterpane.com
Counterpane Systems, 101 East Minnehaha Parkway, Minneapolis, MN 55419

ABSTRACT: We present two software-network payment systems, designed so that every user is capable of both buying and selling. One system uses online clearing; the other uses offline clearing.

1. Introduction

Internet commerce requires new payment methods, and several have already been developed [OO90, OO92, FY92, Bra93a, Bra93b, MN93, CR93, Fer94, LMP94, Oka95, MN95, BGH+95, ST95, TMSW95]. This paper describes a specific kind of payment system in which each user can transfer money to each other user: a peer-to-peer payment system. This can be thought of as a credit card account or a checking account. At regular intervals, these electronic payments are translated into real-world payments. Although this step is important to the users of these protocols, it's not a cryptographic operation at all; just a matter of executing EFTs or writing and mailing out checks.

This paper is organized as follows. Section 2 is a discussion of the objectives and design principles for this kind of system. In Section 3 we describe two example systems, one using online clearing, the other, offline clearing with public key signatures. Neither of these is meant as a final system, but both serve as good outlines to build a working system around.

3. Objectives, Design Principles, and Options

The ultimate objective is to have a payment system as handy for doing internet trade as cash, checks, or credit cards are for doing day-to-day trade. Whatever this is, it must meet the following criteria:

  1. Secure. The system must be secure in the sense that it must not be possible to convince someone they have received money when they have not. It must also not be possible to forge a payment from someone else, or to replay payments. Finally, it mustn't be possible to violate other design specifications of the system, for example by tracing other peoples' payments.
  2. Cheap. The system shouldn't require the user to purchase expensive equipment (other than a PC). The operating costs of the system should be low enough that nobody has to pay a large fixed monthly fee. Indeed, a small fixed monthly fee may be all anyone pays, if operation is cheap enough. In a computational sense, nobody should have to do too many complicated computations to pay someone a dime.
  3. Widely Available. For maximum availability, the client (peer) software should be partially or completely available in source-code--participation in the payment system might be the paid for monthly, along with settling of bills as needed.
  4. Peer-to-Peer. Each user should be able to either send or receive payments without complicated registration procedures.

There are several tradeoffs. For example, making a payment protocol computationally light usually means using few or no public key operations. However, this seems to require some kind of interaction with a central server, which drives up communications requirements and operating costs.

In this paper, we attempt to stay within the constraints of what is implementable in software on standard computers of today, using a good cryptographic function library. Individual users (peers) may have secrets, but these secrets have relevance only to those users. Only the bank is allowed to hold any global secrets.

Notation

Notation in the remainder of this document is as follows:

  1. EncKA(X) means that X is encrypted under key KA, using some symmetric encryption algorithm.
  2. AuthKA(X) means that X is authenticated under key KA, using some symmetric message authentication algorithm.
  3. EncAuthKA(X) means that X is authenticated and encrypted, using symmetric algorithms, under keys derived from KA.
  4. PKEncKA(X) means that X is encrypted under public key KA.
  5. SignKA(X) means that X is digitally signed under private key KA.
  6. X, Y means that X is concatenated with Y.

Online Clearing Systems

Online clearing systems are simpler than offline systems, at least in principle, since both users can authenticate themselves to the Bank's trusted server instead of to each other. There are no certificates to worry about, and the most important security operations take place on a secured machine. Also, this system obviates the need for computationally expensive public-key operations (and the associated licensing issues). The cost of this is that the Bank has to maintain a constant online presence, and can easily become the bottleneck of the system.

In this section, we briefly discuss one example of an online system. In this system, we require the person accepting the payment to have a reasonably accurate clock, and to keep some short-term memory about transfers that have been accepted recently, to prevent trivial replay attacks. When Alice wants to transfer money to Carol, she first gets an electronic note of approval from the Bank for this transfer, which includes an expiration time (after which Carol should not accept it). Then, she sends this note to Carol to convince her that the transfer has indeed taken place. This turns out to be very close to the Kerberos protocol [Sch96].

Variables

  1. SA and SC are Alice and Carol's sequence numbers. These must never repeat or go backwards---instead, they increment one value at a time. Suspicious jumping around by the sequence number must always be noted by the bank, and should initiate corrective action of some kind.
  2. IDA and IDC are Alice and Carol's unique 64-bit ID numbers.
  3. KA and KC are the keys shared between Alice and the Bank, and Carol and the Bank, respectively. The keys are derived based on a master key held by the bank, K*, according to the relation

    Ki = EK*(IDi)

  4. The audit-log is the log of all previous payments, kept by Alice's software. By including this hash, Alice commits to the current entries in the log; if she alters these later, it will be detected by the Bank [SK96].
  5. A Timestamp is a 32-bit representation of a given time and date.

Basic Protocol: Alice Transfers Money to Carol

  1. Alice forms
    • U0 = "Request for Transfer Authorization
    • SA = Current sequence number for Alice--incremented immediately
    • V = hash(Audit Log)
    • W = Amount of Transfer
    • X0 = U0, SA, V, W, IDC
    • K0 = a random message key
    and sends to the Bank
    • M0 = IDA, EncAuthKA (K0), EncAuthK0 (X0)
  2. The Bank receives and decrypts this. If the message doesn't decrypt or authenticate properly, the Bank responds with a simple error message. If the sequence number or hash of the audit log is wrong, then it must begin corrective action. This will be discussed further below. If the amount of the transfer is more than the amount in Alice's account, the ID for Carol is invalid, or anything else is wrong with the message, then a simple error message is sent to Alice. However, if nothing is wrong with M0, then the Bank forms
    • U1a = "Transfer Authorization"
    • TE = Expiration time of authorization
    • Y1 = U1a, hash(M0)IDA, IDC, W, TE
    • K1 = a random message key
    • Z1 = EncAuthKC (K1), EncAuthK1 (Y1)
    • U1b = "Transfer Verification"
    • SC = Carol's current sequence number."
    • IDA, IDC, W (from above step.)
    • X1 = U1b, hash(M0), IDA, IDC, W, SC, TE
    • K2 = a random message key
    and sends back to Alice
    • M1 = EncAuthKA (K2), EncAuthK2 (X1, Z1)
  3. Alice receives this, and verifies everything she can verify. If there are no problems, she forms
    • U2 = "Payment"
    • Z1 from above.
    and sends to Carol
    • M2 = U2, Z1
    At this point, Alice updates her audit log to include this transaction. This is done by appending IDC, W to the previous contents of the audit log. In the event of any trouble verifying that this payment arrived, Alice and/or Carol contact the Bank.
  4. Carol appends IDA, W to her audit log, and adjusts her internally-carried balance by the amount of the transfer.

Security of the Protocol

  1. Replays
    1. The Bank would recognize any replay attempts immediately because of Alice's sequence number. Only an attacker that could alter or forge messages from Alice could replay a message with a new sequence number, without being caught at it.
    2. Alice would recognize any replay attempts because the hash of her previous message is embedded inside the second protocol message.
    3. Carol would recognize replay attempts directed at her by the replayed timestamp and incorrect sequence number. Note that there needs to be some room for error in both these values for Carol, because messages may not always arrive in the order they were sent, and because most computer clocks aren't highly accurate.
    4. It's not possible to alter individual parts of transmitted messages because of the authentication being used. It's not possible to alter individual messages in a protocol because they typically contain the hash of the prior message.
  2. Forgeries Forgeries should be very difficult to carry out, if the symmetric authentication scheme is acceptably strong.
  3. Information Leaks Because of the use of a new message key for each message, it should be very hard for any information to leak. Within the message formats, only the ID of the person transferring money to someone else is leaked in any message.
  4. Other Attacks There is a trivial attack in which Carol simply discards a payment to her by Alice, which means that Alice and the Bank will eventually need to resolve this. This is fundamentally a nuisance attack.

Secondary Protocol: Alice Reconciles

Occasionally, communications failures, implementation errors, or fraudulent transfers may leave Alice and the Bank unsynchronized. The solution is to go through a more complicated protocol to verify that all is well. This is also done from time to time to verify that Alice has received all the deposits that she should have received by now. During the ordinary transfer protocol, the Bank can require a reconciliation protocol before it will allow Alice to carry out any transfers, or Carol to receive any. This protocol is always required before depositing or withdrawing any money from the bank.
  1. Alice forms
    • U0 = "Request for Reconciliation"
    • R0 = a random challenge
    • SA = Alice's current internal sequence number
    • X0 = U0, SA
    • K0 = A random message key
    she then sends to the Bank
    • M0 = IDA, EncAuthKA (K0), EncAuthK0 (X0).
  2. The Bank verifies the authentication, and then forms
    • U1 = "Reconciliation Challenge"
    • SA ^* = Bank's current idea about what SA should be.
    • K1 = A random message key
    • X1 = U1, hash(M0), SA ^*
    it then sends to Alice
    • M1 = EncAuthKA (K1), EncAuthK1 (X1).
  3. Alice verifies the authentication, and that the hash of the previous message is included. She then forms
    • U2 = "Reconciliation Response"
    • X2 = U2, hash(M1), Full Authentication Log
    • K2 = a random message key
    • SA = max(SA, SA ^*)+1
    she then sends to the Bank
    • M2 = EncAuthKA (K2), EncAuthK2 (X2).
  4. The Bank, after verifying all this information, either is or is not willing to let Alice start transferring money again. Thus, it forms
    • U3a = "Reconciliation Success Message"
    • U3b = "Reconcilliation Failure Message"
    • K3 = a random message key
    • X3a = U3a, hash(M_2), SA, Account Balance
    • X3b = U+3b, hash(M2), Problem Description
    and sends to Alice, depending on the circumstances, one of the following:
    • M3a = EncAuthKA (K3), EncAuthK3 (X3a).
    • M3b = EncAuthKA (K3), EncAuthK3 (X3b).

At the end of this protocol, Alice and the Bank should have some common new sequence number, and either they should agree on what has happened, or there will be some kind of investigation going on, and Alice should know the basic kind of problem and what to do next.

What Can Go Wrong?

The most dire failure would involve a security breach at the Bank. Maintaining an authenticated, physically secure and separate log would be one way to ensure that a bank could recover from this kind of failure. Note that each payment from a user contains a current hash of her log.

The user's PC can lose security, in almost the same sense that someone can lose a credit card or checkbook. This should be rare, but it will generally have to be dealt with by humans. The software maintains a log, authenticated by chained hashes. Each payment commits to the current value of the log; that is, the hash of the log up until now.

The authentication and/or encryption functions can be broken. If this happens, the system must be recalled and fixed, and lots of money will be lost. This gives us a lot of incentive to choose our authentication and encryption functions well. For example, Triple-DES [NBS77] or Blowfish [Sch94] in CBC-mode might be used to encrypt, and a keyed hash might be made from SHA1 [NIST93], using a well-thought-out construction such as [PvO95].

An Off-line Payment System

The offline system can be imagined as a checking account: users are allowed to write checks for whatever's in their accounts. The software will not allow them to overdraw, but it is assumed that fraudulent users can change their software to allow this. We assume that we know how to deal with people who don't pay their bills: they can overdraw for a limited span of time, and the bank's collections department will wind up trying to get the money back from them. The offline system uses some public key operations instead of interactions with the Bank. Although certificates are used, there is no CRL. Instead, certificates have a very short lifetime, perhaps a week. After that time, the user must connect to the bank to get a new certificate.

There are two routine operations: Payment and Reconciliation. In payment, one user (Alice) will pay $X to another user (Carol). In reconciliation, a user (Alice) will interact with the Bank to allow her to continue using the system. The system assumes that both Alice and Carol have reasonably accurate clocks.

Payment

In this protocol, Alice makes a payment to Carol by sending Carol a "draft." That is, a timestamped, digitally signed authorization for the bank to move $X from Alice's account into Carol's. Each draft has a unique identifying number, which prevents the bank from ever accepting replays, and gives Alice a way to refer to disputed payments.

Variables:

  1. Timestamp is the current timestamp, in some standard format. The timestamp must never repeat, so it should include everything from centuries to seconds. An example might be "19951225010000".
  2. The audit-log is the log of all previous payments. By including this, Alice commits to the current contents of her log each time she makes a payment. Later changes are detected by the Bank during reconciliation.
  3. The Draft is the order specifying a draft sequence number, the account number of the payor, and the account number of the payee.
  4. CertA is Alice's certificate, attesting to the current valid linkage between her public signing key and her ability to write drafts on a given account id.
  5. PKA is Alice's public signing key.

This is the protocol by which Alice pays Carol:

  1. Alice forms
    • U0 = "Check Transmission"
    • T0 = timestamp
    • V0 = hash(audit-log)
    • X0 = U0, V0, T0, Draft
    • S0 = SignSKA (X0)
    • K0 = a random message key
and sends to Carol
    • M1 = CertA, PKEPKC (K0), EncK0 (X0, S0)
  1. Carol verifies Alice's certificate and timestamp. She then verifies the signature on Alice's draft. If all is well, she knows that the payment has occurred.

This protocol is somewhat computationally expensive. Alice must perform a signature, and Carol must perform two verifications (though she may want to maintain lists of valid certificates, so she doesn't perform the certificate verification more often than necessary). Note that all payments from Alice to Carol appear in the clear; if a secure connection has already been made, then this will work well. If not, it may be necessary in some cases to establish a secure connection; this implies more public key operations for a strong key exchange. Also note that nothing keeps Carol from refusing to acknowledge Alice's payment; Alice can contact the bank and send a signed request to have a stop-payment put on that draft.

Deposit

Deposit simply consists of Carol sending to the Bank (perhaps by e-mail) the digitally signed draft from Alice. Since the draft names Carol, there is no risk of redirection. An active attack can prevent the bank from receiving the deposit. The Bank returns a receipt, also digitally signed. Because each draft must be different, there is no risk of replay attack, if things are done properly.

This is the protocol by which Carol deposits a draft:

  1. Carol forms
    • U1 = "Deposit Request"
    • T = Timestamp
    • V1 = X0, S0 from the previous protocol
    • X1 = U1, T, V1.
    • S1 = SignSKC (X1)
    • K1 = a random message key
    and sends to the Bank
    • M1 = PKEPKC (K1), EncK1 (X1, S1)
  2. The Bank verifies that all is well. If so, it forms
    • U2 = ("Deposit Receipt")
    • R = Receipt
    • X2 = U2, R, hash(M1)
    • S2 = SignSKB (X2)
    • K2 = (a random message key)
    and sends to Carol
    • M2 = PKEPKC (K2), EncK2 (X2, S2)

If Carol never receives M1, she restarts the protocol later, or eventually notes it when she reconciles.

Reconciliation

Reconciliation occurs when Alice connects with the Bank to send in her logs, including copies of all drafts she has written, and to receive a new certificate. User certificates expire often.

  1. The Bank forms
    • U3 = ("Reconcilliation Request")
    • R3 = (a random 64-bit value)
    • X3 = U3, R3
    • S3 = SignSKB (X3)
    • K3 = (a random message key)
    and sends to Alice
    • M3 = PKEPKA (K3), EncK3 (X3, S3)
  2. Alice forms
    • R4 = (a random 64-bit value)
    • U4 = ("Reconcilliation Response")
    • L = the log of payments and deposits since last reconciliation, noting any for which she received no receipt, and any for which she wishes to dispute payment.
    • X4 = U4, hash(M3), R4, L
    • S4 = SignSKA (X4)
    • K4 = (a random message key)
    and sends to the Bank
    • M4 = PKEPKB (K4), EncK4 (X4, S4).
  3. The Bank verifies that all is well. If so, it responds by forming
    • U5 = ("Reconciliation Receipt")
    • CA = New Certificate for Alice with a new timestamp
    • X5 = U5, hash(M4), CA, Ending Balance, Timestamp
    • S5 = SignSKB (X5)
    • K5 = (a random message key)
    and sends to Alice
    • M5 = PKEPKA (K5), EK5 (X5, S5)

If there are disputed payments or other problems, there will be a request for more information sent. This should lead to an online session, telephone call, or face-to-face discussion of the user's complaint. Dispute resolution falls outside of the scope of the payment system.

Error Recovery, Fraud Detection, and Auditing

A continual audit trail is kept in the user's PC, and its current value is committed to each time a payment is made. Forged transactions will be caught during reconciliation, as will almost all other problems. People who overdraw their accounts, exceed their credit lines, or fail to pay their bills have either had a software flaw, or hacked their software to do these things. They will not be issued a new certificate until they resolve the problem. This limits damage from individual security failures to a small period of time, perhaps no more than a week.

What Can Go Wrong?

Compromise of the private signing key used to create certificates is probably the most catastrophic thing that could happen. This must be guarded against strongly, perhaps maintaining the key in a tamper-resistant token under good physical security. Compromise of this key would allow an attacker to write an endless stream of bad checks on anyone's account.

The user's PC can lose security, in almost the same sense that someone can lose a credit card or checkbook. This should be rare, but it will generally have to be dealt with by humans. The software maintains a log, authenticated by chained hashes. Each payment commits to the current value of the log: i.e., the hash of the log up until now. Since certificates expire often, this will be dealt with soon after it's discovered by freezing the account that has been compromised until the problem can be dealt with. In this system, another thing that can happen is that a user's clock can be fouled up, to trick him into accepting a stale certificate. Such attacks must be guarded against.

The authentication, signing, and/or encryption functions can be broken. If this happens, the system must be recalled and fixed, and lots of money will be lost. This gives us a lot of incentive to choose our functions well. For example, we might use 1280-bit RSA [RSA78] SHA1 [NIST93] for our signatures.

Additional Comments and Extensions

Note that it is possible to give the payor anonymity from the payee. This is done by giving each user a large number of IDs, each with a different public signing key and certificate. This gives no anonymity from the bank.

Retrofitting Existing Systems

There are several reasonably good methods of paying for things available now. Small variations in these could be adapted to this kind of an applications. The advantages of using an already fielded system are that there is no need to build the system's infrastructure, and that a fielded system may already have had many of its flaws worked out. Among the possible disadvantages are that many currently-fielded payments systems don't meet the specific needs of this application, and that there are often hardware requirements and licensing fees.

  • Digicash is payer-anonymous electronic cash. It is currently available. The cost per transaction appears to be too high, and there are some practical security problems with any payer-anonymous system that need to be worked out, but this kind of system might be worth using for this application at some point.
  • Some schemes simply transfer users' credit card numbers around. These have obvious security problems involving replay and forgery attacks. However, one way to implement any of the systems discussed above would be for the bank to bill users' credit card for any money owed. To avoid high transaction costs, the bank would bundle many small transactions per month before billing them---perhaps only in $50 increments---from the user's card. The advantage of this would be in low start-up costs. Ideally, the system would also be able to credit money to their credit cards, or transfer it into their bank accounts. This would simplify the mechanics of running this kind of system.
  • There are micropayment schemes, such as Millicent, Payword, and Micromint, that allow for small monetary values to be transferred among parties. However, micropayment schemes generally have to solve somewhat different problems than a peer-to-peer metering system, so they make somewhat different tradeoffs.

Conclusion

The future of the Internet is one where many people are both producers and consumers of information. Any payment system needs to reflect this. This work, while no means complete, shows the kind of directions necessary for peer-to-peer payment systems.

Bibliography

[BGH+95] M. Bellare, J.A. Garay, R. Hauser, A. Herzberg, H, Krawczyk, M. Steiner, G. Tsudik, and M. Waidner, "iKP - A Family of Secure Electronic Payment Protocols", The First USENIX Workshop on Electronic Commerce, USENIX Association, 1995, pp. 89--106.

[Bra93a] S. Brands, "Untraceable Off-line Cash in Wallets with Observers, " Advances in Cryptology---CRYPTO '93 Proceedings, Springer-Verlag, 1994 pp. 302--318.

[Bra93b] S. Brands, "An Efficient Off-line Electronic Cash Systems Based on the Representation Problem, " C.W.I. Technical Report CS-T9323, 1993.

[CR93] CitiBank and S. S. Rosen, "Electronic-Monetary System, " International Publication Number WO 93/10503; May 27 1993.

[Fer94] N. Ferguson, "Extensions of Single-Term Coins, " Advances in Cryptology--CRYPTO '93 Proceedings, Springer-Verlag, 1994, pp. 292--301.

[FY92] M. Franklin and M. Yung, "Towards Provably Secure Efficient Electronic Cash, " Columbia Univ. Dept of C.S. TR CUCS-018-92, April 24, 1992. (Also in Icalp-93, July 93, Lund Sweden, LNCS Springer-Verlag).

[LMP94] S. H. Low, N. F. Maxemchuk and S. Paul, "Anonymous Credit Cards, " The Second ACM Conference on Computer and Communications Security, ACM Press, 1994, pp. 108--117.

[MN93] G. Medvinsky and B. C. Neuman, "Netcash: A Design for Practical Electronic Currency on the Internet, " The First ACM Conference on Computer and Communications Security, ACM Press, 1993, pp. 102--106.

[NBS77] National Bureau of Standards, NBS FIPS PUB 46, "Data Encryption Standard, " National Bureau of Standards, U.S. Department of Commerce, Jan 1977.

[MN95] B. C. Neuman and G. Medvinsky, "Requirements for Network Payment: The NetChequeTM Perspective, " Compcon '95, pp. 32--36

[NIST93] National Institute of Standards and Technology, NIST FIPS PUB 180, "Secure Hash Standard, " U.S. Department of Commerce, May 93.

[Oka95] T Okamoto, "An Efficient Divisible Electronic Cash Scheme, " Advances in Cryptology---CRYPTO '95 Proceedings, Springer-Verlag, 1995, pp. 438--451.

[OO90] T. Okamoto and K. Ohta, "Disposable Zero-Knowledge Authentication and Their Applications to Untraceable Electronic Cash, " Advances in Cryptology---CRYPTO '89 Proceedings, Springer-Verlag, 1990, pp. 481--496

[OO92] T. Okamoto and K. Ohta, "Universal Electronic Cash, " Advances in Cryptology---CRYPTO '91 Proceedings, Springer-Verlag, 1992, pp. 324--337.

[PvO95] B. Preneel and P.C. van Oorschot, "MD$X$-MAC and Building Fast MACs from Hash Functions, " Advances in Cryptology---CRYPTO '95 Proceedings, Springer-Verlag, 1995, pp. 1--14.

[RSA78] R. Rivest, A. Shamir, and L. Adleman, "A Method for Obtaining Digital Signatures and Public-Key Cryptosystems, " Communications of the ACM, v. 21, n. 2, Feb 1978, pp. 120-126.

[Sch94] B. Schneier, "Description of a New Variable-Length Key, 64-Bit Block Cipher (Blowfish), " Fast Software Encryption, Cambridge Security Workshop Proceedings, Springer-Verlag, 1994, pp. 191--204.

[Sch96] B. Schneier, Applied Cryptography, Second Edition, John Wiley & Sons, 1996.

[SK96] B. Schneier, J. Kelsey, "Automatic Event-Stream Notarization Using Digital Signatures, " in Advances in Cryptology, Proceedings of the Cambridge Protocols Workshop 96, Springer-Verlag, 1996, pp. in preparation.

[ST95] M. Sirbu and J. D. Tygar, "NetBill: An Internet Commerce System Optimized for Network Delivered Services, " Compcon '95, pp. 20--25.

[TMSW95] J. M. Tenenbaum, C. Medich, A. M. Schiffman, and W. T. Wong, "CommerceNet: Spontaneous Electronic Commerce on the Internet, " Compcon '95, pp. 38--43

This paper was originally published in the 3rd USENIX Workshop on Electronic Commerce, 1998
Last changed: 8 April 2002 ml
Technical Program
Workshop Index
USENIX home