20-CS-6053 Network Security Spring 2017
Lab 3

Secret Key, Public Key, Hash Algorithms, IPSec, Kerberos, Authentication, more

Authentication via Zero-Knowledge Proofs and RSA

Due: February 27, 2017 (submit instructions: here)

    Continue the development of code started in Lab 1 and continued in Lab 2. Add authentication via Zero-Knowledge proofs and RSA.

Connect to the monitor on port 8180 of helios.ececs.uc.edu for this assignment.
Standings URL is http://gauss.ececs.uc.edu/standings8180.html
Lab Problem:
Write C++ or Java code to support authentication between participants. Participants will be teamed in groups of three or less. The final score of a participant will be the total number of points acquired by all the members of the participant's team by the cutoff date and time. Participants will need to communicate with each other to transfer points from one participant to another. Participants will want to transfer points because if the initiator is the recipient, a bonus of 1% of the amount transferred will be awarded to the initiator. Although all transfers will take place via Monitor directives and commands, the players must talk to each other to authenticate themselves. It is critical that participants know with whom they are transferring points or the points may be stolen. If a participant detects an attack, points may be safely transferred to another team member leaving the red-faced thief empty-handed. This code should be added to the code you wrote for Lab 2.

The following directives and commands are added to the Monitor protocol of Lab 2 which is repeated here for convenience. Most commands and directives support a zero-knowledge Fiege-Fiat-Shamir authentication of the initiator by the sender (recall the public key of such a scheme is a number v and modulus n - click here for a review).

Directive Description
TRANSFER: ARG1 ARG2 FROM ARG3 This Directive is sent by the Monitor to the sender (the identity of the party losing the transferred points), on behalf of the initiator (the identity of the party requesting the transfer). ARG1 is the identity of the recipient (the one receiving the transferred points); ARG2 is the number of points that the initiator would like to transfer; ARG3 is the identity of the sender. The recipient receives a bonus of 10% of the amount transferred.
The following Commands should be used only in transmissions from the Participant to the Monitor:
Command Description Result
TRANSFER_REQUEST ARG1 ARG2 FROM ARG3 This command is executed by the initiator of a transfer to ask the Monitor to confirm the requested transfer by making a request to the party named in ARG3. The arguments to TRANSFER_REQUEST are exactly the same as those to the TRANSFER: directive. The result is
ARG1 is either ACCEPTED, REJECTED, or NOT_ALIVE. All of which refer to the status of the Participant with whom this transfer was requested. If ARG1 is ACCEPTED, then the point totals of recipient and sender are changed accordingly with the recipient getting a 10% bonus.
TRANSFER_RESPONSE ARG1 This command is used by a transfer target to either accept or reject a trade request. This command is most probably used in response to a Message Group that contained the TRANSFER: Directive (and probably a REQUIRE: TRANSFER_RESPONSE Directive as well). ARG1 is either ACCEPT or DECLINE. The result is
Depending on whether the sender accepted or declined the transfer (and, if Monitor approval was given), the sender's point total will be changed.
The following commands support the Fiat-Shamir zero-knowledge protocol. The use of these commands is explained below the table in the Authentication Section.
Command Description Result
PUBLIC_KEY ARG1 ARG2 This command is used by the initiator to respond to the Monitor's request for authentication during the beginning of a transfer request. ARG1 is the initiator's account's public key v value and ARG2 is the n value. The result is forwarded to the sender.
ROUNDS ARG1 This command is sent by the sender after receiving the initiator's public key. ARG1 is the number of rounds to continue the zero-knowledge exchange for authenticating the initiator. The result is forwarded to the initiator.
AUTHORIZE_SET ARG1 ... ARGN This command is sent by the initiator after receiving the sender's number-of-rounds N. The number of arguments must equal N. Each argument is a number that is the square of a random number taken modulo the initiator's public key value n. Observe this is not a set but a list: the order of arguments matters. The set is forwarded to the sender.
SUBSET_A ARG1 ... ARGO This command is sent by the sender after receiving the initiator's authorize list. The number of arguments is no greater than the number of rounds. Each argument is an index into the authorize list. They are expected to be in increasing order and chosen randomly. The set is forwarded to the initiator.
SUBSET_K ARG1 ... ARGO This command is sent by the initiator in response to the sender's authorize list. The initiator multiplies its private key by the random numbers matching indices listed in the authorize list modulo n and returns the results, in proper order, as arguments of this command. The set is forwarded to the sender along with the SUBSET_J set, described next, in the same message group.
SUBSET_J ARG1 ... ARGP This command is sent by the initiator in response to a Monitor directive issued after having sent a K subset. The initiator needs to compute values for random numbers whose indices are not in A. The set is forwarded to the sender in the same message group as the SUBSET_K command described above. The sender will respond by either accepting or declining the transfer request.
Authentication using Fiege-Fiat-Shamir:
A transfer operation is intended to move points from one account, called a sender, to another account, called a recipient. The account from which a transfer request is made is called the initiator. The recipient and sender must be different and the initiator should be different from the sender, although transfers will probably be allowed if they are not different. Since points are intended to be transfered out of the sender, the sender should authenticate the initiator to make sure an adversary is not trying to steal the points. The monitor supports authentication via the Fiat-Feige-Shamir zero-knowledge protocol.

Before any transfers take place, all player accounts should have chosen a secret number s and a modulus n, and should have computed a public key v which is s2 mod n. Be advised that all player accounts should have different s, v, and n. The running example below will use s=5, n=16, and therefore v=9. Typical values for s and n will be numbers consisting of several hundred decimal digits.

Authentication proceeds as follows. The initiator passes its public key pair <v,n> to the sender. The sender verifies that this public key belongs to the initiator. The project page describes how this can be done using certificates. An adversary can spoof the initiator's public key but will not know the initiator's secret s and therefore will be unsuccessful in some round of the authentication protocol. Next, the number of rounds for this particular transfer is passed by the sender to the initiator. On each round, the initiator (the prover) chooses a random number R and passes F=R2 mod n to the sender (the verifier). The sender randomly chooses 0 or 1 and passes its choice to the initiator. The initiator receives the number from the sender. If the number is 0, the initiator computes E=s*R mod n and passes it to the sender, otherwise the initiator computes and passes E=R mod n. The sender computes G=E2 mod n. If the sender had passed a 1 to the initiator in the previous transmission, the initiator compares G with F*v mod n where F and v have been obtained from earlier transmissions. If they do not agree, the initiator is bogus. If the sender had passed a 0, the initiator compares G with F. If they do not agree, the initiator is bogus. If the initiator is not deemed bogus on any round, the sender accepts the transfer.

Rather than complete rounds sequentially, each transaction in the authentication process carries information for all rounds simultaneously. Details of this process follow.

The initiator connects to the Monitor and issues a TRANSFER_REQUEST, for example like this:

Note: RECIPIENT and SENDER will be actual contest account names.

The sender named in that request alives itself and receives notification that the transfer is requested by the initiator.

To the sender:
COMMENT: Monitor Version 2.2
PARTICIPANT_PASSWORD_CHECKSUM: cb1f3f077473c05a81ba6dc0db4195fd8d03af55

From the sender:
IDENT SENDER 1vgn90d0crurg6rjblr0osn8rqahi5qopvinaodn34ba7...

To the sender:
RESULT: IDENT v0a08dief488kd769aa6dokdgp8gblt87ai7taib49tr...

From the sender:

To the sender:
RESULT: ALIVE Identity has been verified.

When the sender verifies that it is alive the Monitor requests that the initiator submit its public key for authentication to the sender. This is done as follows:

To the initiator:

From the initiator:

where v and n are (rather large) numbers expressing the Fiat-Feige-Shamir public key of the initiator,

To the sender:

The sender responds with the number of rounds of tests that it wants:

From the sender:

Any number of rounds could have been used here - we illustrate the protocol with a running example consisting of seven rounds. The initiator gets this request and chooses, in this example 7, random numbers which we will call R[0], R[1], R[2], R[3], R[4], R[5], R[6], then passes the squares of those numbers mod n (RR[i] = R[i]2 mod n), for 0 <= i < 7, as an AUTHORIZE_SET via the Monitor to the sender as follows:

To the initiator:

From the initiator:

For our (impractical) running example,
let s=5, n=16, v=9, R[0]=1, R[1]=2, R[2]=3, R[3]=4, R[4]=5, R[5]=6, R[6]=7.
Hence, for the running example, the initiator responds with
AUTHORIZE_SET 1 4 9 0 9 4 1

The AUTHORIZE_SET is passed to the sender who replies with a sublist of array indices A to the initiator to put into SUBSET_A (A is a set of indices into array RR):

To the sender:

From the sender:
SUBSET_A: A[0] A[1] ... A[o]

In our running example we choose o=2, A[0]=2, A[1]=4, and A[2]=5
Hence, for the running example, the sender replies with
SUBSET_A: 2 4 5

The initiator receives the SUBSET_A subset and responds by computing each element of SUBSET_K, such that K[i] = s*R[A[i]] mod n for all i from 0 to o. The elements in SUBSET_K must be in the same order as the corresponding elements of SUBSET_A:

To the initiator:
RESULT: SUBSET_A A[0] A[1] ... A[o]

From the initiator:
SUBSET_K K[0] K[1] ... K[o]

For the running example this will be
SUBSET_K 15 9 14

The initiator then must produce SUBSET_J, which operates on all indices of R[.] not contained in SUBSET_A, according to
J[i] = R[i] mod n for all 0 <= i < ROUNDS such that i is not in {A[0], A[1], ..., A[o]}:

To the initiator:

From the initiator:
SUBSET_J J[0] J[1] ... J[m]

For the running example this will be
SUBSET_J 1 2 4 7

The monitor passes SUBSET_J and SUBSET_K to the sender and expects a response to the transaction:

To the sender:
RESULT: SUBSET_K K[0] K[1] ... K[o]
RESULT: SUBSET_J J[0] J[1] ... J[m]

The sender tests the values in SUBSET_K and SUBSET_J in the following manner: using the initiator's v,n, for all K[.], J[.], the sender squares the results mod n, and checks
   K[i]2 mod n == v*R[A[i]]2 mod n,     0 <= i <= o
   J[i]2 mod n == RR[B[i]],
       where B[i] is the ith element of {0,1,...,Rounds-1} - {A[0],A[1],...,A[o]}.

For the running example,
   K[0]2 mod 16 == 1 == 9*32 mod 16 == v*RR[2] mod n,
   K[1]2 mod 16 == 1 == 9*52 mod 16 == v*RR[4] mod n,
   K[2]2 mod 16 == 4 == 9*62 mod 16 == v*RR[5] mod n,
   J[0]2 mod 16 == 1 == RR[0],
   J[1]2 mod 16 == 4 == RR[1],
   J[2]2 mod 16 == 0 == RR[3],
   J[3]2 mod 16 == 1 == RR[6].

Then the sender responds with one of the following:

From the sender:

For the running example, the sender responds with

The sender is then asked to QUIT and after that happens the transfer is completed with the initiator receiving a WAITING: directive.

It is possible for the sender to use dummy values throughout and accept or decline however it pleases. But, a policy of declining nearly all transfers will be frowned upon by the management.

You must watch out! If someone steals the identity of one of your group, all members of the group are vulnerable!! You cannot blindly accept transfers from any group member.

Authentication of Certificate by RSA Signing:
See monitor key help for advice on this. This section will be made self contained pretty soon.