Assignment Task

1. In triple DES using three keys the encryption is done as follows: C = EK3 (DK2 (EK1 (P). Explain precisely (in terms of K1, K2, K3) how you (as the cryptanalyst) would mount a meet-in-the-middle attack on triple DES with three keys, assuming you had enough known plaintext, ciphertext pairs.

(b) Approximately how many different keys would your attack have to try.

(c) Approximately how much space would your attack require.

A and B are going to communicate via a virtual circuit. A already knows B’s public key KUB, and B already knows A’s public key KUA. After the virtual circuit has been set up, B needs to convince A that he is B, and A needs to convince B that he is A. You have to design a protocol to accomplish this task.

• This protocol should not assume that A and B share some secret information.
• There is no arbitrator or trusted third party i.e. all communication happens directly between A and B.
• After the virtual circuit has been set up (which happens before the protocol starts), this protocol should have only two rounds for authentication purposes, and these two rounds will be as follows:
• Will send a single message to A which will convince A that it is B on the other end of the virtual circuit.
• Will then reply with a single message to B which will convince B that it is A on the other end of the virtual circuit.
• The protocol should be designed so that it can be repeated many times i.e. A might want to communicate with B again in the future, and A, B should be able to prove their identities to each other using the same protocol again without having to change keys.
• The protocol should be resistant to replay attacks i.e. even if the public keys, private keys remain the same, the bad guy BG should not be able to obtain any information he gains from previous iterations of the protocol to masquerade as A or masquerade as B in the future.
• We are only interested in authentication, not confidentiality.

You have to

(a) State any assumptions you are making.

(b) Show precisely what B will transmit to A in round (1) i.e. I don’t need an explanation here, just need you to show me exactly what B is sending to A.

(c) Explain precisely in a step-by-step fashion what is the test A will run to make sure it is B on the other end (and not the BG) i.e. I don’t need an explanation here, just need you to show me exactly what is the test A is running.

(d) Explain clearly why BG cannot do a replay attack.

(e) Show precisely what A will transmit to B in round (1) i.e. I don’t need an explanation here, just need you to show me exactly what A is sending to B. (f) Explain precisely in a step-by-step fashion what is the test B will run to make sure it is A on the other end (and not the BG) i.e. I don’t need an explanation here, just need you to show me exactly what is the test B is running. (g) Explain clearly why BG cannot do a replay attack.

1. Consider the Diffie-Hellman scheme with q = 11 and α = 8.

(a) Show that 8 is a primitive root of 11.

(b) If A has the public key YA = 4, what is the private key XA. Show all calculations.

(c) If B has the public key YB = 5, what is the private key XB. Show all calculations.

(d) Show the calculation done by A to get the shared key KAB.

(e) Show the calculation done by B to get the shared key KAB.

2. Consider the ElGamal scheme (described in section 10.2) with q = 11 and α = 8. A has a private key XA = 5.

(a) Show what will be calculations done by A to get the value of the public key YA.

(b) B choses the random integer k = 3, and the plaintext B wants to encrypt is M = 4. Show what will be calculations done by B to get the value of the ciphertext C1, C2.

(c) Show what will be calculations done by A to recover the plaintext M from C1, C2. Note that you first need to figure out what is the value of K.

3. Give brief and clear explanations for the following by showing in a step-by-step manner how the BG would attack the scheme if we changed things as suggested in the question Consider the key distribution protocol as described in Figure 14.18, page 452 for distributing session keys using secretkey encryption and the Key Distribution Center. Ka is the master key shared between A and the KDC, Kb is the master key shared between B and the KDC, Ks is the session key to be used to encrypt data between A and B, and Na, Nb are nonces. Note that A is the one initiating the request to get a session key.

a. Explain why in the round (3) (KS, IDA, Nb) is encrypted with EKb i.e. i.e. suppose that round (3) consisted of (KS, IDA, Nb) instead of EKb (KS, IDA, Nb), how would the bad guy BG attack the scheme?

b. Explain what role Nb plays in the protocol i.e. assuming that Nb was not there in the protocol, how would the bad guy BG attack the scheme?

c. Explain why in round (3) IDA is included in the encrypted EKb (KS, IDA, Nb) i.e. suppose that round (3) consisted of IDA, EKb (KS, Nb) (so that IDA was being sent in the clear) how would the bad guy BG attack the scheme?

Programming Problem

What you have to turn in and where you have to turn it in is similar to how you needed to turn in stuff for the HW1 programming problem. In this problem, in the HW2 submission, along with the self-critique, the easy to read source code, a printout of the output, you also need to show how much time each of the attacks took for each of the inputs. Please read the programming guidelines (in the course outline on Canvas) before starting to work on the programming problem. You need to read this carefully to understand what has to be turned in and how, including the self-critique. You have to write a program (or if you find it easier, two different programs) to implement two different attacks on RSA and see which works faster. For each attack, your program will take as input the public key e, n, a ciphertext C and produce as output the plaintext M and the total amount of time the attack took to obtain M.

Attack 1

Here you will generate all possible values of M till you find one for which Me = C mod n. You can use the naive and inefficient method for modular exponentiation. Here the output should consist of M.

Attack 2

Here you will factor n to recover the primes p, q such that n = pq. You will then calculate the private key d, n, and then calculate M = C d mod n. You can use the naive and inefficient methods for factoring n, for finding d from e and Φ(n), and for modular exponentiation. Here the output should consist of p, q, d, M.

You have to run your program on three different inputs.

(a) e = 3, n = 15, C = 8. It is possible that this problem gets solved so fast that you do not get very meaningful timing results for this example.

(b) e = 13, n = 527, C = 152. Again, it is possible that this problem gets solved so fast that you do not get very meaningful timing results for this example.

(c) An input generated by you – you should generate the largest values for which you can get results in a “reasonable” amount of time. Here you have to start from scratch in terms of finding p,q,e,d etc i.e. you have to find these values.