##### # # # # # ## #### #### # # ### # # # # # # # # # # # # # #### #### # # # # ###### # # ####### # # # # # # # # # # # ### ##### ###### # # #### #### # # ####### # # ###### #### ##### ##### #### # # # #### # # # # # # # # # # ## # # # # ##### # ##### # # # # # # # # # # # # # # # # ##### # # # # # # # # # # # # # # # # # # ## # # # ####### ###### ###### #### # # # #### # # # #### ###### # # ## # # # # ###### # # ##### #### # # # # # # ## ## # ## # # # ###### # # # # ## # ##### # # # # #### # ###### # # # # # # # # # # # # # # # # # ## # # # # # # # # # ###### # # # #### 4.1 Gerard's Brief History of Money 4.1.1 Money in prehistoric times. 4.1.2 Money in the Twentieth Century. 4.1.3 The Payment Methods in the Netherlands. 4.2 Issues in Electronic Payments 4.2.1 Identification 4.2.2 Anonimity. 4.2.3 Software or Hardware solution. 4.2.4 On-line or Off-line 4.2.5 Double Spender problem 4.3 An Elementary Payment System 4.4 Adding Anonimity: Ecash 4.4.1 Blind signatures. 4.5 The Off-line Anonymous Protocol 4.5.1 Blobs 4.5.2 Certificate format. 4.5.3 Cut-and-Choose 4.6 The Current Dutch Treat (Thread) 4.6.1 Payment functions. 4.6.2 Identification. Today's lecture discusses electronic means of payment. The discussion opens with a short history of Money, and then discusses cryptographic implementation of money. 4.1 Gerard's Brief History of Money --------------------------------------- History has shown different ideas of what money is. 4.1.1 Money in prehistoric times. Long ago, people had no money; a situation currently persisting only in certain central- and east European countries. The economy was based on direct exchange of goods. This means that the fisherman in need of a haircut would search for a hairdresser who likes fish, and pay a meal for a cut. Around 2500BC this situation made way for a system based on exchange against objects of `universal' value, usually small discs of precious metals called coins. The coins served three crucial functions in the economic life for several millenia: 1. Value exchange: any good or service was payable in coins, eliminating search for an economic partner with exactly complementary needs. 2. Value standard: the PRICE of a good could be stated as the number of coins that should be exchanged for it. 3. Value storage: the fisherman could now catch a fish on Monday, exchange for coins, and have his hair cut on Friday and pay with these coins. So in those times, real money was a gold (or silver) coin; genarally called commodity money, because the money actually consisted of a precious commodity. Carrying large amounts of gold was a burden, and large amounts were a dangerous possession because of their attractiveness for thieves. So new institutions called banks came into view, they would preserve your gold and give you a a gold-certificate as a proof. These certificates appeared for the first time in China, around 1300BC. If you wanted to pay you `simply' would go and get your real money back, hand it to the payee, who would bring it to the bank and receive a certificate for it... To save trouble, the banks invented that the certificate itself could be used for the payment, that is, the certificate could be transferred by a protocol (initially involving signatures written on it), which would tranfer the ownership of the gold stored in the bank. As a result, the gold certificates became `real' money, but they were not precious themselves; they are called representative money because each note represents a certain amount of precious commodity. 4.1.2 Money in the Twentieth Century. Thus we enter the current century in a situation where REAL MONEY is a bank note, representing a certain amount of gold stored in a central bank. The possibility of exchange into gold was rarely used, however, because the paper was so convenient. In the first half of this century the central banks decided that it was no longer necessary to keep all the gold in store, and even the possibility of exchange for gold was abandoned in the various countries. Instead of being representative for gold, the notes had become something valuable by themselves. We call this fiat money because the notes in fact ARE nothing, but get their value by the trust everybody puts in them. A next revolution appeared during the sixties and seventies, when almost everybody got a paymant account with a bank, and all the importent payments received the form of bank transfers. The current state of affairs is that REAL MONEY means having a positive balance on the bank account; consequenly, a payment in the twenty first century is a method to transfer some balance from the account of a payer (called Alice, of course) to that of a payee (Bob). Reduction of Alice's balance is called debiting, increase of Bob's account is called crediting. 4.1.3 The Payment Methods in the Netherlands. Until about five years ago, a payment in the Netherlands was made using either of the following two models: 1. The Credit-Debit model: The bank is given instruction to transfer the desired amount directly from Alice' to Bob's account. 2. The Token model: Some of Alice' balance is converted into transferable object, handed to Bob, and converted back. 1. The Credit-Debit model: One can send a written instruction by mail, and this is useful to buy something big like a car or a house, but it is not suitable for daily shopping. A second implementation is that Alice writes a check when buying something, and Bob gives the check to the bank to effectuate the transfer. Thus, Bob receives the money a few days after giving Alice the goods, which is usually not a problem. In our country, it was decided in the sixties that bank cheques are GUARANTEED: this means that if Bob accepts the check according to the protocol (including that Alice waves an identity card and signs) Bob WILL receive his money, even if Alice has no balance. This decision a definite, but manageable risk to the banks, but caused the checks to become widely accepted! The third implementation is an on-line transaction, where Bob has a small terminal connected to the bank. Alice identifies herself by showing a bank card and typing a PIN (Personal Identification Number), and the bank transfers the amount at the same moment. 2. The token model. Alice identifies herself at the bank and desires to receive a few balance certificates; of course in return for a debit of her account. She pays by transfering the certificates to Bob, who can convert them back to real money by handing them to the bank, at which moment he will be credited. The certificates are so portable, that Bob might use them for other payments instead of cashing them for real money. The certificates come in two forms currently: small metal discs called coins and rectangular printed paper called notes. AMERICAN SITUATION: CREDIT CARDS Checks with guaranteed value regardless of sufficient balance of the payer are unthinkable in the American situation. Even to the present day it is very difficult to just explain to American people how they work and the Yanks usually don't believe that the bank would accept any agreement under which it would be forced to pay to Bob and be unable to trace Alice and sue her for the money and the damage. Consequently, checks didn't make it in the American society and a third payment model came up: the credit card. Under a credit card payment, Bob receives his money first from a fourth party (credit card company), and later the CCC will get this money back from Alice. In this way the CCC carries the risk of non-payment by Alice, but there is more: the CCC also advances the money temporarily, which is the cause for the name credit card, but also makes the system very expensive: the CCC charges Bob 2 to 6 percent of the payed amount. Needless to say, we in Europe don't need such a system! It will be excluded from today's discussion, as will be the credit-debit system: we shall concentrate on token systems. 4.2 Issues in Electronic Payments ------------------------------------- Electronic money is not the same as the historic stuff: it is not a value standard, nor a vehicle for value preservation, but only a means to effectuate payments. In the payment protocols we consider three parties: Alice, Bob, and the bank because for simplicity we assume that Alice and Bob have their account at one bank. We now discuss several important issues in payments systems. 4.2.1 Identification This is important for withdrawals and for other protocols as we shall see later; we have already seen how this problem can be solved. 4.2.2 Anonimity. Current balance certificates are almost anonymous: if you pay in a shop you cannot be traced by your payment with a coin. You can by payment with a banknote as they are numbered, but only if the number were registered beforehand and this is not regularly done. Some systems offer the same degree of anonimity, while others reveal the identity of the payer to the payee or the bank. 4.2.3 Software or Hardware solution. Some systems offer full protection through the protocols and the crypto graphic functions used, while for others the data in possession of the clients must be protected from being tampered with. In the latter case the client receives a smartcard holding his data and protocols, and the banks trust the tamper-resistance of this device. As no device is really tamper-proof, the software-only solutions are preferred. Of course, the banks will give smartcards to their customers to help them execute the cryptographic protocols; but the security of the system does not depend critically on their use. 4.2.4 On-line or Off-line We call a system on-line if cooperation of the bank is necessary during payments. The current payments with PIN-protected bank cards are on line. 4.2.5 Double Spender problem The metal and paper certificates in use nowadays are difficult to generate or reproduce; cryptography will ensure nobody can generate certificates, but copying them will be easy. So any system will have to deal with the possibility of doubly spending a certificate. 4.3 An Elementary Payment System ------------------------------------ The first payment system is non-anonymous, software-only, and off-line. A rudimentary system has certificates of the form where b is the amount and r a unique series number; the certificate is signed by the bank. To discourage double spending, upon spending the certificate one signs a transfer certificate of the form , where r is the series number, u a uniqueness tag, and X the payee; here are the protocols. PHASE ONE: Withdrawal. 11. Alice identifies herself and requests a b certificatte 12. The bank chooses random r and signs . 13. Alice is debited amount b and receives the signature y. 14. Alice verifies that y^e is of the form . PHASE TWO: Payment. 21. Alice picks an article with price b from Bob's shop. 22. Alice identifies herself and pays with y. 23. Bob verifies that the certificate is real and generates u. 24. Alice signs to transfer the note y to Bob. 25. Bob verifies the signature and accepts the payment. PHASE THREE: Deposit. 31. Bob gives y to the bank. 32. The bank verifies the validity and checks if r was deposited before. 33. If everything is fine, Bob is credited amount b. The protocol has the possibility of double spending, but the signed transfer certificates allow to trace the culprit and are the proof of the crime. Assume the same note is deposited twice, by Bob and Carol; the bank asks to see the transfer certificates of Bob and Carol. If they differ, Alice has signed two of them and is prosecuted. If they are equal, Bob and Carol will be prosecuted because they have attempted to cheat. 4.4 Adding Anonimity: Ecash ------------------------------- Alternatively, double spending can be prevented completely by making the payments on-line: Bob verifies during payment with the bank if note r was already deposited. This would give a non-anonymous on-line system, so besides the extra security not much would be gained over the current Debit-credit payments using bank cards. The Dutch company Digicash has implemented an anonymous payment system for use over the Internet, and because in an anonymous system payers cannot be traced, double spending MUST be prevented. 4.4.1 Blind signatures. Crucial in the protocol is that Alice can generate a banknote herself and have it signed by the bank without the bank seeing the series number. The bank doesn't really care about the sequence number, as long as they are sure that Alice receives just one note. Suppose Alice wants the bank to sign the number z. Step 1. Alice selects random k and computes z' = k^e.z. Step 2. The bank signs z' by computing y' = z'^d for Alice. Step 3. Alice divides y = y'/k. The signature is valid because y^e = z, but the bank has never seen z because it was blinded by k^e. As the bank does not know k, they cannot tell the real z. Actually, the bank has absolutely no idea what it was signing for Alice, so they better use this key ONLY for bank notes of value b and for nothing else. Though the signature can be nbblinded to ANY note as far as the bank can tell, Alice can only unblind it to her original note, because she has no other unblinder than k. In this system, the withdrawal simply means the bank signs one number for Alice against payment of b: 11. Alice forms a banknote z = and blinds it to z' = k^e.z. 12. Alice has z' signed by the bank against a debit of b. 13. Alice divides the signature by k and obtains the bank's signature under . The bank knowns it has validated a bank note for Alice, but it does not know the number; of course, bank notes are signed for many clients. PHASE TWO/THREE: 11. A lady shops at Bob's and wants an object priced b. 12. She pays with a number y for which y^e = for some r. 13. Bob sends the number to the bank. 14. The banks didn't see the series number, nor created it, but sees the valid signature. 15. They check that no such number was deposited before and credit Bob. 16. Bob is informed and accepts the payment. 17. The unknown lady leaves the shop with the object. Almost everybody is happy. The bank because the signature proves that the note has been (though blinded) signed by the bank, for which an amount b was debited. Bob because he has received payment for the object. The lady because she has paid but nobody knows who she was. Except we: because we have seen off-line protocols, and we want to have this property in an anonymous protocol as well. 4.5 The Off-line Anonymous Protocol --------------------------------------- The protocol is off-line, so double spending cannot be prevented by a direct check as in the previous protocol. So we must ensure that double spenders are caught after the fact. But how is this done if the system is anonymous? The solution is that single spending of a certificate does NOT reveal the identity of the spender, however, if somebody spends a certificate twice, his identity is revealed. To this end, the identity is hidden in a certificate in shares, and each time a certificate is spent, a share of the identity is revealed. Revealing two shares will disclose the identity to the bank. The shares will consist of X0 and X1, both random strings, but X0 XOR X1 reads "Alice". 4.5.1 Blobs To hide shares of the identity in the bank note, the payer puts them into Blobs: a blob is like a cryptographic envelope in which some value can be hidden. Then the value cannot be observed, but the envelope can be opened to reveal the content. There is no way to open the blob except by showing the value that was put in it. The blob mechanism makes use of a strongly collision-free hash function f and to blob value x, Alice announces the value b = f(x). This really conceals the input, because the function is one-way: it is not possible to compute x from b. To open the blob b, Alice gives x, and it can then be verified that f(x) = b. There is no way for Alice to produce a blob that she can open in two ways, because she cannot produce different x and y with f(x) equal to f(y). 4.5.2 Certificate format. The certificate contains the following information: 1. The value b. 2. A random series number r. 3. Ten pairs of blobs B0i & B1i for i = 1..10, such that X0 XOR X1 reads the identity of the payer. This is how to form a certificate: 1. r <-- random string ; b <-- amount ; 2. for i <-- 1 to 10 do 3. y <-- random string 4. X0i <-- y ; X1i <-- "Alice" XOR y 5. B0i <-- f(X0i) ; B1i <-- f(X1i) When Alice pays with the certificate, Bob asks her to open one blob of each pair randomly. Thus, when Alice uses the same certificate a second time, the odds are only 1 to 1024 that the same blobs will be asked, and with high probability she will have to open the complement of at least one of the blobs she already opened, giving away her id. Here is the transfer protocol: 21. A lady shops at Bob's and pays with a certificate C carrying the bank's signature. Bob sees all the blobs containing the shares of the identity of the lady, but he cannot see the shares inside the blobs. 22. Bob chooses 10 random bits y1 ... y10 and asks the lady to open the 10 blobs Byi,i, and obtains x{yi,i}. Of course he verifies their f-images. The X are random strings, and reveal nothing to Bob about the identity of the lady; you need two matching X to see the name. 23. Bob accepts the payment, the lady leaves the shop. Fase 3: Deposit. 31. Bob gives the certificate, the signature, the yi and the X{yi,i} to the bank. 32. Bank verifies the signature and checks the f-images of the X. If Bob has correctly accepted the certificate, he gets credited. 33. Now the bank checks the records to see if certificate number r was deposited before. 34. If not: everything is fine, and the data is stored. 35. If yes: somebody is going to have a problem. But who? We retrieve the certificate C with yi' and X{yi',i}. 36. If all yi = yi', Bob will be accused of attempting to deposit the certificate twice. 37. If at least one yi != yi' we XOR the two strings X{yi,i} and X{yi',i}; the strings are random, but XORing them reveals the name of a lady... 4.5.3 Cut-and-Choose Because the certificates are signed blind, the bank must somehow obtain certainty that the certificate signed for Alice has the correct amount (b) and that the blobs have the desired property. To this end, the withdrawal makes use of a technique called cut-and-choose: 11. Alice makes 20 certificates C1 ... C20 and blinds them to B1 ... B20, where Bi = Ci. ki^e. 12. The bank asks Alice to reveal 19 of the blinding roots bi. For each of these bi, the bank computes Zi = Bi/ki^e. They verify the format: the amount b and the presence of ten blob pairs. 13. The bank asks Alice to open each of the twenty blobs and verifies that their XOR really reads "Alice". 14. If everything is fine, Alice didn't cheat with the 19 certificates, so the bank will trust the 20th blinded certificate also and signs it. 15. The bank does NOT know its series number, nor the blobs inside it. 4.6 The Current Dutch Treat (Thread) ---------------------------------------- The Dutch banks are currently introducing payment smart cards, known as Chippers and Chipknips. I will review the system briefly and explain why it will be an (expensive) fiasco. The main reason is that implementation had to be cheap: 5 milion cards are being handed out, and the banks rather pay 10 then 20 guilders for each card. The cards have only 8K of memory and are not capable of performing RSA functions. 4.6.1 Payment functions. The `money' in the card is not present in the form of discrete objects like electronic coins, but in the form of a counter giving the `balance' on the card. The cards are under control of the customers, so this is very much like a small bank where you maintain your own balance. When you pay, your card identifies with the termrinal and the balance is transferred from the card to the terminal. When you load the card, the card is given permission from a terminal to increase the balance on the card. The terminal must identify to the card as being a real one, otherwise the card will refuse. The banks trust that the cards are physically safe against tampering, but this isn't true. It is possible to open the card and apply some brain surgery to it, for example to modify the operation of the register holding the balance. Thus you create a chipknip that pays forever without bothering about loading. By checking all payment transcripts (I don't know if this is routinely done) the banks may notice that this card spends more than it withdraws and request the card back. 4.6.2 Identification. It would be better to have the card impersonate another card so you will remain unknown while leading your life in luxury. To make this possible, the banks have chosen an identification procedure on the basis of symmetric cryptography: the protocol in Section 3.5. Of course, this requires that the card and the payment terminal share a `secret' key k. This secret is the encryption of the card number x under a Master Key M known to the terminals! The card does NOT know M, but M was used during production of any real card. The card gives its identitiy number x to the terminal, and the terminal computes k = E_M(x). Terminal and Card then enroll in the symmetric identification. The terminal gets convinced that the card knows k, hence is real, while the card gets convinced that the terminal known M, thus is real. The real gangsters steal a terminal (or have them in their own shops) and read the secrets M from them. It is then possible to produce new cards, numbered y, and load them with the corresponding secret k = E_M(y) so as to fool all other terminals. The encryption used is really strong: 3DES, but is of no help here.