LimitedKnowledgePurchasing

MeatballWiki | RecentChanges | Random Page | Indices | Categories

The text below comes from my report for my LimitedKnowledgePurchasing final project. I think it's a decent case to demonstrate how various HardSecurity methods interact with each other to build a complete system. It's probably not a very good solution to the fundamental problem, though. -- SunirShah

I suppose now that it's been a long time, I can admit that I secretly thought this was only useful for buying porn. I coulda made a fortune. ;) -- SunirShah

Did a quick scan of this, not a deep read. You need to read up on DavidChaum?'s DigitalCash proposals. There's some discussion of Chaum in AppliedCryptography, but I don't believe digital cash itself is mentioned. There is some good discussion of Chaum's quest in StephenLevy?'s Crypto. -- KarstenSelf

CategoryCryptography

Introduction

When purchasing digital content from the Internet, it is often unnecessary to reveal the customer's identity, location, and other identifying information. Also, as with any purchasing system, it is undesirable to allow third parties to discover the identity of the customer, the item being purchased, the amount it was purchased for, or any other information about the transaction. These properties are part of our common everyday experience with physical money. Cash is anonymous. When I walk into a store to buy a pack of gum, no one needs to know who I am. Nor does an authority need to know what I spent my money on. Further, for those who weren't watching me (or couldn't see), no one needs to know what I purchased.

One model to migrate these properties to the Internet is to invent some sort of digital cash. However, digital cash requires a lot of infrastructure and guarantees that are expensive to construct (as expensive as it was to construct the modern unified currency system that we use today). Furthermore, digital cash can be perfectly traceable, much like a more stringent, systemic version of [Where's George] [Eskin, 1998]

Thus, it will be faster and cheaper to use the existing virtual currency systems in use today; i.e. the credit and debit card systems. Unfortunately these systems are anything but anonymous or secure. Banks can see a person's entire transaction history. Only "soft" privacy polices restrict a bank's ability to sell this information to third parties like targeted advertising agencies. Also, with credit cards, the retailer is given too much information about the customer, such as her credit card number, her name, her bank, etc.

Nonetheless, it is possible to construct a purchasing system that protects the customer's, the retailer's, and the bank's interests during the transaction. That is the focus of this project.

Concepts

Goals.

To succeed, the project must ultimately allow some end user to purchase something from some retailer. However, that something is of limited class. Realistically, a cryptographically-secured, limited knowledge transaction system can only succeed if it transferred digital content. Physical goods cannot be shipped without revealing important information, like a street address. While it is true that consumers can use anonymous post office boxes or drop off points, that will not occur in the normal case. Most end users will not be making a premeditated attempt to shirk identification, and if they were, there is only a limited number of anonymous post drops. Furthermore, post drops aren't completely anonymous. They give away your city for instance.

Ultimately, the best candidate for a digital limited knowledge purchasing environment is digital content. Digital content lends itself to well to this environment because the merchandise can be secured cryptographically, which is much more reliable any identity masking in a physical environment. Thus, the first goal:

: Goal 1. The system will allow an end user to purchase digital content from a retailer.

However, we can already accomplish this goal under the current system on the web. What we need in addition is privacy. For the user, we do not want the retailer to know who he is through any identifying information. What this really means is we want to ensure the retailer does not need to know anything about us. This gives us our next goals, the separate parts of the transaction.

: Goal 2. The retailer can be paid securely without knowing who the user is.
: Goal 3. The user can receive the merchandise (content) without identifying herself.
: Goal 4. No third party, including those involved in the transaction, should have enough information to record a connection between the end user and the retailer.

In any system of financial transactions, we need further economic guarantees that the transaction is valid. For instance, we need to prove that all parties are who they say they are.

: Goal 5. All parties must have some means of proving their identity.

Note that this goal is particularly difficult in the face of the previous goals. Proving one's identity without identifying oneself will require transitive trust.

Because a financial transaction is a short-term contract, the parties should also be prevented from repudiating the transactions.

: Goal 6. Non-repudiation.

Finally, the exchange of merchandise for money should happen simultaneously so one party cannot renege the agreement halfway through. Thus, we have:

: Goal 7. The retailer will not be paid until the user verifies and validates the transaction.

: Goal 8. The user will not receive merchandise until the retailer receives payment.

Trust.

All financial transactions involve some sort of trust. All parties before entering in the agreement believe they will be getting something of greater value as part of the exchange. In order to allow them to believe this, the parties must have trust that the transaction will go through.

In practice, the most common way of achieving this is by GoodFaith by all parties involved. When purchasing merchandise from a store, if that merchandise is defective, the usual case is that the customer will no longer return to that store. Market forces keep the retailers in line. If this proves ineffective or the cost of the transaction makes bad faith a serious risk, citizens can also turn to the civil law to enforce good faith. Contract law, for instance, allows citizens to sue each other when they breach contract. Criminal law also prevents people from stealing from a retailer, counterfeiting bills, or extorting retailers. Criminal law also protects the consumer by enforcing community standards on retailers, such as by forcing sanitary conditions on restaurants. In our society, financial institutions are given power through all three. The market gives power to the banks by giving them control of its money, and in order to allow those banks to act effectively in our capitalistic economy, legislation has been enacted to give them the power of the courts and enforcement. In short, we have chosen to trust banks to run our economy.

But in all cases, trust only comes from accountability. With nothing to force people to act in good faith, opportunists can profit greatly. Cryptography and information theory helps by limiting the extent of damage, or by outright refuting some attacks, but it isn't sufficient. In a financial transaction, the parties have identities that need protection. In an online financial transaction, audit trails and traceability confounds privacy concerns. The disreputable can abuse this to gain traction against people, and thus undeserved economic advantage.

As Vividence has discovered, people do not trust the retailers online with their personal information. "People get intimidated by a zillion questions," says Vicky Valandra of Vividence. "And they feel like it's intrusive if someone wants their address right off the bat." [Poole, 2000] As Lawrence Lessig argues so effectively, the online world can become the perfect Big Brother. [Lessig, 2000]

But people do trust their banks. As Lessig further argues, banks are easy to regulate because they are relatively few. They are also heavily regulated by the government, especially through the Bank Act [Bank Act, 1991]. Banks also have the advantage of implementing many of the digital payment systems already available, including the credit and debit card systems, as well as the important wire transfer system.

It seems plausible, then, to use a bank as a proxy agent in the transaction. While the user and the retailer may not be able to trust each other, especially since the retailer does not know who the user is and the user may not even know who the retailer is, they both trust the bank system enough to carry the transaction. Moreover, each party's bank already has his or her personal information stored, so it will not leak information further. Therefore, the limited knowledge purchasing system will rely heavily on the bank as the go between. The parties can trust the bank to faithfully carry out the transaction without causing security breaches.

On the other hand, the user would not want to let the bank store information that could be potentially damaging were a subpoena be served to the bank. Consequently, the user will be careful not to provide any information that will directly identify the retailer. Only the credentials necessary to authenticate the retailer will be provided; the bank can trust the user will not provide bad credentials, as it is the user's money in question. Similarly, the merchandise itself, even in encrypted form, will not be transmitted through the bank.

Protocol

Implementation issues.

The Internet today is dominated by the World Wide Web. The dominant protocol is the Hypertext Transfer Protocol (HTTP). [HTTP, 1999] Most firewalls and proxies leave port 80 open, and this has lead to a number of protocols tunneling over HTTP. This makes HTTP a good candidate on the surface. But HTTP also has additional benefits.

With the Internet developing as it is today, many people are acquiring IP addresses for their personal computers. When you open a socket connection to another device, the foreign server will be able to track your identity by looking up your IP address. This is not acceptable. Fortunately, supply has kept up with demand. The web is full of anonymous proxies that will redirect your HTTP requests appropriately and anonymously. For instance, there is A4Proxy [A4Proxy, 2001] which will sit on your local machine and transparently anonymize your HTTP sessions. Thus, for end users with extreme privacy concerns, HTTP is a good answer. The best answer for using HTTP is via the Common Gateway Interface (CGI) [CGI, 1995] as it is ubiquitous, easy to proxy, and easy to implement. A message send is merely an HTTP POST, and a message reply is simply POST-formatted text/plaintext returned from the HTTP server.

HTTP and CGI are not secure in and of themselves. Some form of protocol level encryption is needed. While HTTPS [HTTPS, 2000] has been drafted, and could likely be very useful for this application, it was too complicated to use for demonstration purposes. Consequently, I implemented my own protocol encryption based on the RSA public key encryption algorithm. [Rivest, et. al, 1978] In my protocol, I assume there is some certificate authority where the bank and retailer public keys are available (actually, I hard code the keys directly.) On the other hand, since the retailer cannot ask a certificate authority for the user's keys (as the retailer does not know who the user is), the user has to give her keys directly to the retailer during handshaking. Extending this, all connections begin by sending the initiator's keys to the target. All traffic is also encrypted using RSA. Thus, for the message M being sent from Alice with public key a to the Bob with public key b, sending a message is defined as

    send( Bob, M ) := HTTP-POST( url(Bob), PEb(a, M) )

Similarly, replying with message N from Bob to Alice in the same transaction is defined as

    reply( N ) := HTTP-PRINT( "text/plaintext", POST-FORMAT(PEa(N)) )

I also used SHA-1 hashing [SHA, 1995] to implement digital signatures and the Rijndael symmetric key encryption algorithm, more commonly known as the Advanced Encryption Standard (AES) [AES, 2000], in the protocol. For a message M <= (m1, m2, ... ) with a private signing key and public verification key pair known as a, signing and authenticating a message are defined as

    M' := (signature, m1, m2, ...) 
       := sign( M <= (m1, m2, ... ), a ) 
       := ( PEa( SHA-1(M) ), m1, m2, ... )

    passed := verify( M', a ) 
           := verify( (signature, m1, m2, ...), a )
           := PDa(signature) <=> SHA-1( m1, m2, ... )

And for a given symmetric key, k, encryption and decryption of a message M and ciphertext, C, are defined as

    C := encrypt( k, M ) := AES( k, M )
    M := decrypt( k, C ) := AES( k, C  )

I also used a high-quality random number generator (randlib) to generate nonces and symmetric keys. For instance, nonces are generated randomly from the uniform interval [0,7FFF7FFFFh]. To generate the RSA keys, I used a separate program. See Dependencies below.

Protocol Description.

In the description below, error responses are implicitly defined as non-normative cases. For instance, an invalid signature or insufficient funds are error conditions that will return error results. Instead of describing each possible way the protocol may fail, only the means by which an error condition is flagged will be defined. Throwing an exception, E, is defined as

    error( E ) := reply( Error <= (E) )

Signatures are always verified whenever possible. If it is not possible, as you will see, it will be made possible.

The user has the public-private key pair known collectively as u, and the signing key pair known as su. Similarly, the retailer has r and sr, and the bank has b and sb.

The initiating action is a user who, after browsing a catalog from a retailer, decides to purchase an item with a given catalog number, Item#. She will begin by creating a signed quote for the price. This will prevent the retailer from later denying it offered the item at the price at the given time.

    Quote-request <= ( Item# )
    send( retailer, Quote-request )

The retailer then responds with

    Quote <= sign( (Item#, Amount, CurrentTime, ExpiryTime), sr )
    reply( Quote )

Where Amount is the cost of Item#, CurrentTime is a timestamp of the current time from the retailer's perspective, and expiry time is the lifetime of Quote. The lifetime must be no longer than the lifetime of sr, but it may be much shorter for wildly fluctuating prices. Of course, the purpose of Quote is more than just returning the price of the item. Because it is signed, it represents a binding agreement between the retailer and the user that the retailer will sell Item# to the user at the given price.

Armed with the price, the user then asks the bank to make a Cheque on a given Account. A Cheque acts much like a cheque in the traditional sense--that is, it's a contract for a person A to pay a given amount to a person B--except that person B does not need to know who person A is.

    StartTime := CurrentTime
    Cheque-request <= sign( 
        (user, Account, Amount, StartTime, ExpiryTime, nonce1, sr),   
         su 
    )
    send( bank, Cheque-request )

Notice in the above that the user sends a nonce to the bank. This is to prevent replays of this message. If anytime before ExpiryTime the same nonce is used twice, the bank will deny the cheque. It also ensures that the user will get the right cheque back. Otherwise, a malicious retailer might intercept two purchase requests and reply the higher of the two in order to get more money. Notice also that the user sends the retailer's signing key to the bank. This is because the bank does not know who the retailer is and thus cannot look up its keys. Later on, we will see the bank will need to verify the retailer's signature.

If this succeeds, the bank will create an timestamped entry for the Cheque in its database. Each cheque has a unique Cheque#.

    Cheque <= sign( (bank, Cheque#, Amount, Timestamp), sb )
    Cheque-entry <= ( Cheque#, user, Account, Amount, StartTime, 
                            ExpiryTime, nonce2, status, Timestamp, sr )
    status := Live Î { Live, PendingActivation, Expired, Used, 
                             Retracted } 
    Cheque-wrapper <= sign( (Cheque, nonce1, nonce2), sb )
    reply( Cheque-wrapper )

Because we can trust the bank, it can act as a timestamping authority to demonstrate that the user in fact created the cheque at the given time. This will prevent the user from repudiating the cheque in the future. The second nonce is to prevent others from verifying the cheque later on. Now with a token that represents cash, if the quote hasn't expired, the user can now begin the purchase transaction with the retailer.

    Purchase-request <= sign( (Quote, Cheque, nonce3), su )
    send( retailer, Purchase-request )

The user resends the entire Quote just to prove to the retailer that this is in fact what they agreed upon. The third nonce is to ensure that the transaction isn't meddled with by attacking parties. It will be returned with the Receipt.

The retailer at this point records the purchase request for bookkeeping purposes. Unfortunately, it doesn't know if the request is valid. It doesn't have the user's signing key. It does know who the bank is from the Cheque, and the bank knows who the user is. So, the retailer asks the bank for the signing keys.

 
    SigningKey-request <= sign( (Cheque#), sr )
    send( bank, SigningKey-request )

Here, we see the first merits of storing the retailer's signing key in the Cheque-entry. The bank will only hand out the user's signing key to the people who have legitimate need for it. This means someone can't just ask the bank for the user signing keys attached to all cheques in the database; they will have to know the recipient keys as well.

Nonetheless, this is easy enough for the bank to respond to.

    reply( SigningKey <= sign(su, sb) )

Given the user's signing keys, the retailer now verifies that the purchase request is valid. Given that's the case, the retailer will now attempt the cash the Cheque. First, the retailer generates a key, k, that it will use to encrypt the item and another nonce, nonce4, that the user will need to get k from the bank. Strictly, nonce4 isn't necessary but it makes it a lot harder to break the system as an attacker will need to intercept communications between more parties.

    Cash-cheque <= sign( 
          ( RetailerBank, RetailerAccount, k, Cheque#, nonce4 ),
          sr
    )
    send( bank, Cash-cheque )

Provided the Cheque hasn't expired and it is still live (i.e. not retracted), the Cheque-entry is updated as follows

    status := PendingActivation
    Cheque-entry := ( Cheque#, ..., k, nonce4, RetailerBank, RetailerAccount )
    reply( sign(success, sb) )

Noting that the bank will not give k to the user unless the money transfer succeeds, the retailer is confident enough to send the encrypted item to the user.

    Purchase <= sign( (encrypt(k,Item), nonce3, nonce4, sr )
    reply( Purchase )

The user, if she is happy with the transaction. A new nonce is created for good measure.

    Key-request <= sign( (Cheque#, nonce2, nonce4, nonce5), su )
    send( bank, Key-request )

Upon receiving the key request, if there is enough money in the user' s account, the bank transfers funds from the user to the retailer and then sends the key back to the user, thus closing the transaction.

    Key <= sign( (k, nonce5), sb )
    reply( Key )

If in this last leg, the nonce fails, the user can go physically to a bank branch with a diskette to retrieve the key. Given the key, the user merely

   
 decrypt( k, Item )

to get the content.

Conclusion

As you can see from the above, at no time does any party have enough information to connect the user to the retailer, nor to discern the content that the user is buying. Furthermore, the protocol is sufficiently capable that it can exist in modern environments to greater or lesser degrees of security. It certainly accomplishes all the goals listed above (see Goals.).

One thing the protocol does not address is the quality of the Item once purchased. If the retailer cheats, and the item is either fake or damaged, the user is left with no suitable recourse if she wants to maintain her privacy. Certainly the retailer can include a Receipt of purchase with the Item, e.g.

    Receipt <= sign( (Quote, Item), sr )

Whereby the retailer sends Receipt encrypted, not Item. The bank will also timestamp the date the funds transfer occurred, which can prevent the retailer from repudiating the transaction after its signing keys have expired. But, still, the user will have to then defeat the system by identifying that she purchased content from the retailer. Moreover, she will likely have to describe the nature of the content to prove that it was damaged. Thus, it's really caveat emptor.

The other thing that the protocol does not address is the case when the retailer's bank and the user's bank are the same. In that case, it's trivial for the bank to make the connection between the user and the retailer. The protocol can be extended during the initial handshaking by having the retailer send the user a list of banks that the retailer has accounts at. Then the user can choose between her banks and the retailer's banks to pick a pair that is unlikely to cause privacy concerns.

References

[A4Proxy, 2001] "Anonymity 4 Proxy," iNetPrivacy. http://www.inetprivacy.com/a4proxy/ (2001)

[AES, 2000] Daemon, J. and Rijnmen, V., ``The Block Cipher Rijndael,'' Smart Card Research and Applications, LNCS 1820, J.-J. Quisquater and B. Schneier, Eds., Springer-Verlag, 2000, pp. 288-296.

[Bank Act, 1991] Bank Act. 1991, c. 46.

[CGI, 1995] "The Common Gateway Interface Specification" (aka CGI/1.1) National Center for Supercomputing Applications. http://hoohoo.ncsa.uiuc.edu/cgi/interface.html. (1995)

[Eskin, 1998] Eskin, H. Where's George. http://wheresgeorge.com (1998)

[HTTP, 1999] Fielding, R., et. al. "Hypertext Transfer Protocol -- HTTP/1.1." Internet Engineering Task Force. RFC 2616. (1999)

[HTTPS, 2000] Rescorla, E. "HTTP Over TLS" The Internet Society. RFC 2818. (2000)

[Lessig, 2000] Lessig, L. Code: And the Other Laws of Cyberspace. Bantam Books. (2000)

[Poole, 2000] Poole, G. A. "The Riddle of the Abandoned Shopping Cart," The Industry Standard: Grok. Dec 2000-Jan 2001, p.76

[Rivest, et.al. 2001] Rivest, Shamir, and Adleman, "A Method for Obtaining Digital Signatures and Public-key Cryptosystems", Communications of the ACM. (Volume 21. Feb 1978)

[SHA, 1995] Brown, R. and Prabhakar, A. "Secure Hash Standard." Federal Information Processing Standards Publication Series. National Institute of Standards and Technology. (1995)

LimitedKnowledgePurchasing

Discussion