CSci 4554 Lab 5. Zero-knowledge protocols; Digital Cash

Due Friday, May 7th at 11:59pm (by e-mail)

50 points total

Description

This lab is done in groups of 2. The goal of the lab is to implement implement a zero-knowledge identity proof and digital cash. You will also get practice detecting dishonest participants.

Tasks for the lab:

Problem 1: Feige-Fiat-Shamir authentication zero-knowledge protocol

Implement the Feige-Fiat-Shamir authentication zero-knowledge protocol as described in the handout given in class and also here. Alternatively you can try to cheat, i.e. prepare responses without generating a key. In addition you will have to verify another group's responses and decide if they are cheating. I will distribute roles so that there are enough "honest" and "dishonest" groups.

Record and briefly explain all your computations.

Tasks for problem 1

All groups:

1. Generate a large integer N which is a product of two large primes. For simplicity choose a Blum integer because you will need to find a square root mod N. As in the previous lab, use at least 15 as the bit length when generating primes.
2. Post N and keep the primes private. Here is the wiki page for the lab: https://wiki.umn.edu/view/UMMCSci4554Spring10/ZeroKnowledgeLab

"Honest" groups:

1. Choose a random number u in the field generated by N and compute its square v.
2. Find the inverse of v.
3. Find the smallest square root of the inverse of v (compute all four roots and take the smallest one).
4. Post v.

"Dishonest" groups:

1. Publish a randomly chosen quadratic residue as v. Do not store or otherwise record its square root.

All groups

1. Choose a group with which you are going to exchange challenges and responses.
2. Request m < 20 test numbers from the other group. Choose m so that you are confident that you can catch a cheater. Write down your reasoning.
3. In response to a request generate m responses. An "honest" group has to generate responses r according to the protocol. A "dishonest" group needs to compute responses so that each can satisfy one of the challenge questions (i.e. those that will be requested by chosing 0 or 1). Record which of the two challenges they satisfy. CC your e-mail to me.
4. When the m responses arrive, randomly generate m bits 0/1 and send them to the other group. CC your e-mail to me.
5. Once the 0/1 are received, calculate and send the responses. An "honest" group follows the protocol. A "dishonest" group sends pre-computed responses to the challenges it can meet and any number (random works) for challenges you cannot meet. CC your e-mail to me.
6. Once the responses are in, verify the result. If you discover "fake" responses, identify the group as "dishonest". If all responses verify correctly, calculate the probability that the group is "dishonest". This probability should be very small.

Digital cash

Your task is to implement digital cash, as described in this overview. Different groups will be assigned different roles. The goal is to be able to distinguish a legitimate transaction from an attempt to cheat. The roles and tasks will be as follows:

• The bank: blind-sign customers' money while checking that the customers follow the protocol. When the money is deposited after the transaction, check for double-spending. If double-spending is detected, open up the two bills to find out who double-spent.
• Customers ("Alice" group): generate money for digital signatures, unblind money, pay "Bob" (the merchant). Customers group creates 5 "customers" (give them names, create accounts for them at the bank). Once all the customers get money, each customer must pay a merchant. Important: some of the "bills" paid to the mercants must be illegitimate copies of bills spent elsewhere, and some must be legitimate. Also, at least one bill must be fake, i.e. not signed properly by the bank.
• Merchants ("Bob" group): accept money from Alice, verify its legitimacy (find the fake bill(s)). Then deposit money to the bank.

More specifically:

1. The bank generates RSA modulus in which p, q are at least 100 bits (note that we will use it to encrypt the result of SHA-1 which is 160 bits). As always, Blum integers preferred. To follow the the suggested scheme, use e = 3. Note that 1/3 in the description refers to d (the inverse of e mod (p-1)(q-1)).
2. All parties need to use a seeded random number generator. Each group needs to pick a large (at least 5 digits) seed. This guarantees (hopefully) that all the seeds are different.
3. Account numbers for customers are 10-digit binary numbers. They are set by the bank.
4. The customer group creates digital cash (say, in $100 bills) for each customer as defined in the protocol. Assume k = 40. The parameters are as follows:
   • A randomly generated 10-digit binary serial number for the bill.
   • a_i are random 20-digit binary numbers
   • y_i is the SHA-1 of the following: XOR of a_i and the concatenation of the account number and the bill serial number. It needs to be stored as a hexadecimal string. Here are some helpful links: an example of a message digest, how to convert from a byte array to a string of hexadecimals.
   • x_i = SHA-1 (a_i) as a hexadecimal string. Corrected at 4:10pm Wedn 5/5, was incorrect: SHA-1 (y_i)
5. Keep a_i, y_i, and x_i and the blinding factor for each element of each bill. Keep track of which elements have been opened by the bank and discarded.
6. After all a_i, x_i, and y_i are created, "Alice" (the customer) concatenates x_i and y_i and computes SHA-1 of the result (this is the g(x_i, y_i) part of the protocol). The concatenation is treated as a string. Then follow the example on how to pass it to SHA-1. The result of SHA-1 is represented as a BigInteger created by passing the result of SHA-1 (the byte array) to BigInteger constructor.
7. Then she generates a "blinding factor" r_i for each g(x_i, y_i) and sends all of them (blinded) to the bank for a blind signature. Note that at least one of the customers is expected to be cheating at this point.
8. The bank send each customer ("Alice") a request to open randomly chosen 20 bills. The customer sends the blinding factor to unblind those. If the bank detects cheating, the customer repeats the procedure.
9. After the bank verifies the bills, it signs the product of the remaining k/2 numbers mod N (as an RSA signature).
10. The customer unblinds the signed cash by dividing it by the product of the unblinding factors of the 20 remaining elements.
11. The customer pays some of the merchants with the signed bills by sending the bill (the product) and its signature. The merchant verifies the bank signature (if it's not a proper signature, the transaction gets canceled). In the process he sends the customer a randomly chosen sequence of k/2 numbers and the customer sends the corresponding elements:
    • a_i and y_i for 1
    • a_i xor < info> and x_1 for 0.
    Then for each i "Bob" can find x_i and y_i, compute SHA-1 of their concatenation, and verify the bank's signature on their product. "Alice" has to try to cheat at this point by providing a bill that hasn't been properly signed.
12. When the money is deposited (with the customer responses to 0/1 challenges), the bank checks the cash value and verifies that the cash has not been double-spent. If it has been, the bank uses the 0/1 challengers to find out who is the cheater. "Alice" group has to double-spend at least one bill, the bank has to detect it.

What to submit (by e-mail to me, CC your partner)

1. All your program code (well-documented) and instructions for running it.
2. All your computations with explanations.
3. Detailed explanations of what you were doing and why.

CSci 4554 course web site.