CMU 15-827

Security and Cryptography

Fall 1998


Symmetric and Public Key Cryptography



Homework 3

Due: 2 November 1998

  1. Security Models (10)
  2. Can you think of a situation where it makes sense to have a combination of the Bell-LaPadula and Biba mandatory integrity models?

  3. Credit Cards (10)
  4. Look at several Visa and Mastercard numbers and infer a simple algorithm for checking whether a credit card number could be valid.

  5. Digital Cash (10)
  6. Give a "black box" description (not tied to any specific cryptographic representation) of Chaumís electronic token blinding operation. Use it to give a black box description of Chaumís digital cash protocol.

  7. Anonymous Purchases (15)
  8. In electronic commerce, one might want to make a purchase anonymously. One may also want to complain if one receives poor service (or the wrong goods). Can you think of some ways to reconcile these properties? What additional information is needed from the purchase protocol to accomplish this?

  9. Wallets with Observers (15)
  10. In Section 6 of Brandís paper he extends the basic cash system to restrain double-spending.

    1. Explain in English (not math!) what the role of O is. What roles do o1 and o2 play in the protocol?
    2. Explain in English the payment (sub)protocol. What is the purpose of each step and what is the purpose of each part of each message?
    3. How are double-spenders traced in case the tamper resistant card is broken?
    4. Is anonymity preserved? Can the observer leak information? How or why not?

  11. IKP (10)
  12. In the iKP paper the authors say that they require encryption to provide not only confidentiality, but also integrity. Decryption of a ciphertext results either in a message or in a flag indicating non-validity. Correct decryption convinces the receiver that the sender knows the plaintext that was encrypted.

    Definition 1: We say that an encryption scheme is plaintext-aware if it is impossible to produce a valid ciphertext without knowing the corresponding plaintext.

    1. Why is plaintext-awareness needed in iKP? Explain one possible problem if a regular (non-plaintext-aware) encryption function (such as RSA) is used.
    2. Definition 2: We say that an encryption scheme E is non-malleable if given a ciphertext c = E(m) it is impossible to produce a valid ciphertext cí of a related message mí.

    3. Compare Definitions 1 and 2. Does one imply the other? Explain your reasoning.

  13. Atomicity of Withdrawal Protocol (15)
  14. Hereís a protocol that allows a Customer to withdraw a coin of $1 from the Bank. Let (n, 3) be the RSA public key of the Bank.

    1. The Customer prepares 100 messages m1, Ö, m100 which are all $1 coins. The Customer blinds them; i.e., she chooses random r1, Ö, r100 and computes wi = ri3mi. The Customer sends w1, Ö, w100 to the Bank.
    2. The Bank chooses at random 99 of the blindings and asks the Customer to open them. That is, the Bank chooses i1, Ö, i99 and sends it to the Customer.
    3. The Customer opens the required blindings by revealing ri1, Ö, ri99.
    4. The Bank checks that the blindings are constructed correctly and then finally signs the unopened blinding. W.l.o.g. assume this to be the first one. So the Bank signs w1 by sending to the Customer w11/3 = r1m11/3.
    5. The Customer divides this signature by r1 and gets a signature on m1 which is a valid coin.

    Notice that the Customer has a probability of 1/100 to cheat successfully.

    Suppose now that the protocol is not atomic. That is, the communication line may go down at the end of each step between the Customer and the Bank. What protocol should be followed for each step if the line goes down at the end of that step in order to prevent abuse or fraud by either party?

    8. Transferable Electronic Cash (15)

    Real-life cash has two main properties:

    The electronic cash proposals we saw in class are all "non-transferable," that is the customer gets a coin from the bank, spends it, and the vendor must return the coin to the bank in order to get credit. As such they really behave as anonymous non-transferable checks. In this problem we are going to modify such proposals in order to achieve transferability.

    Consider the following abstraction of a protocol similar to what we saw in class. We have three agents: the Bank, the Customer, and the Merchant.

    The Bank has a pair of keys (S, P). A signature with S is a coin worth a fixed amount (say $1). It is possible to make blind signatures, meaning the Customer gets a signature S(m) on a message m, but the Bank gets no information about m.

    Withdrawal protocol

      1. The Customer chooses a message m.
      2. The Bank blindly signs m and withdraws $1 from Customerís account.
      3. The Customer recovers S(m). The coin is the pair (m, S(m)).

    Payment Protocol

      1. The Customer gives the coin (m, S(m)) to the Merchant.
      2. The Merchant verifies the Bank signature and sends a random challenge c to the Customer.
      3. The Customer replies with an answer r.
      4. The Merchant verifies that the answer is correct.

    The challenge-response protocol is needed in order to detect double-spending. Indeed the system is constructed in such a way that if the Customer answers two different challenges on the same coin (meaning heís trying to spend the coin twice) his identity will be revealed to the Bank when the two coins return to the bank. This is why the whole history of the payment protocol must be presented to the Bank when the Merchant deposits the coin.

    Deposit protocol

      1. The Merchant sends m, S(m), c, r to the Bank
      2. The Bank verifies it and add $1 to the Merchantís account.
      3. The Bank searches its database to see if the coin was deposited already and if it was reconstructs the identity of the double-spender Customer.

    In order to make the whole scheme transferable we give the bank a different pair of keys (S, P). It is still possible to make blind signatures with S. However messages signed with S have no value. We will call them pseudo-coins. When people open an account with the Bank, they get a lot of these anonymous pseudo-coins by running the withdrawal protocol with S as the signature key.

    Suppose now the Merchant received a paid coin m, S(m), c, r and instead of depositing it wants to use it to buy something from OtherMerchant. What she could do is the following:

    Transfer protocol

      1. The Merchant sends m, S(m), c, r and a pseudo-coin m¢ , S(m¢ ) to OtherMerchant.
      2. OtherMerchant verifies all signatures and the pair (c,r). Then sends a random challenge c¢ for the pseudo-coin.
      3. Merchant replies with r¢
      4. OtherMerchant checks the answer.

    Notice however that Merchant can still double-spend the coin m, S(m), c, r if she uses two different pseudo-coins to transfer it to two different people. Indeed since she will never answer two different challenges on the same pseudo-coin, her identity will never be revealed. The problem is that there is no link between the real coin and the pseudo-coin used during the transfer protocol. If we could force the Merchant to use only one pseudo-coin for each real coin she wants to transfer then the problem would be solved.

    Show how to achieve the above goal. You will need to modify both the payment and the transfer protocols.