CS 257 - Problem Set 2

Assigned:Wednesday September 9
Deadline:Thursday September 24th, 11:59pm

Reading

Mark Stamp, “Information Security: Principles and Practice”, Chapter 3.

Available at Yale as a licensed online book.

Deliverable

Create a pdf file yournetid.cs257hw2.pdf with your answers to the following questions. DO NOT include your name and netid in the file. You will submit the file through gradescope.

Problem 1: (10 points) [Chapter 3, problem 4, page 79]

This problem deals with the A5/1 cipher. For each part, justify your answer.
  1. On average, how often does the X register step?
  2. On average, how often does the Y register step?
  3. On average, how often does the Z register step?
  4. On average, how often do all three registers step?
  5. On average, how often do exactly two registers step?
  6. On average, how often does exactly one register step?

Problem 2: (10 points) [Chapter 3, problem 5, page 80]

Implement (or simulate) the A5/1 algorithm. Suppose that, after a particular step, the values in the registers are 
X = (x0, x1,..., x18) = (1010101010101010101)
Y = (y0, y1,..., y21) = (1100110011001100110011)
Z = {z0, z1,..., z22) = (11100001111000011110000)
List the next 32 keystream bits and give the contents of X, Y, and Z after these 32 bits have been generated.

Problem 3: (10 points) [Chapter 3, problem 7, page 80]

The RC4 cipher consists of a lookup table S, which contains 256 byte values, and two indices, i and j .
  1. The lookup table S is initialized to contain the identity permutation 0,1,2,..., 255 and at each step of the algorithm, S contains a permutation. How is this achieved? That is, why does S always contain a permutation?
  2. Where is RC4 used in the real world?

Problem 4: (10 points) [Chapter 3, problem 8, page 80]

This problem deals with the RC4 stream cipher.
  1. Find a reasonable upper bound on the size of the RC4 state space. That is, find an upper bound for the number of different states that are possible for the RC4 cipher. Hint: The RC4 cipher consists of a lookup table S, and two indices i and j . Count the number of possible distinct tables S and the number of distinct indices i and j , then compute the product of these numbers.
  2. Why is the size of the state space relevant when analyzing a stream cipher?

Problem 5: (10 points) [Chapter 3, problem 14, page 82]

This problem deals with the DES cipher.
  1. How many bits in each plaintext block?
  2. How many bits in each ciphertext block?
  3. How many bits in the key?
  4. How many bits in each subkey?
  5. How many rounds?
  6. How many S-boxes?
  7. An S-box requires how many bits of input?
  8. An S-box generates how many bits of output?

Problem 6: (10 points) [Chapter 3, problem 19, page 82]

AES consists of four functions in three layers.
  1. Which of the four functions are primarily for confusion and which are primarily for diffusion? Justify your answer.
  2. Which of the three layers are for confusion and which are for diffusion? Justify your answer.

Problem 7: (10 points) [Chapter 3, problem 20, part (a) only, page 83]

Implement the Tiny Encryption Algorithm (TEA).
  1. Use your TEA algorithm to encrypt the 64-bit plaintext block 
    0x0123456789ABCDEF
    using the 128-bit key 
    0xA56BABCD00000000FFFFFFFFABCDEF01.
    Decrypt the resulting ciphertext and verify that you obtain the original plaintext. We provide a python file to get you started: teahelp.py teahelp3.py (python 3)

Problem 8: (10 points) [Chapter 3, problem 35, page 85]

Suppose Alice uses DES to compute a MAC. She then sends the plaintext, the IV, and the corresponding MAC to Bob. If Trudy alters one block of plaintext before Bob receives it, what is the probability that Bob will not detect the change? Extra: What if more than one block is changed?

Problem 9: (10 points) [Chapter 3, problem 37, page 85]

Using CBC mode, Alice encrypts four blocks of plaintext, P0, P1, P2, P3 and she sends the resulting ciphertext blocks, C0, C1, C2, C3, and the IV to Bob. Suppose that Trudy is able to change any of the ciphertext blocks before they are received by Bob. If Trudy knows P1, show that she can replace P1 with X. Hint: Determine C so that if Trudy replaces C0 with C', when Bob decrypts C1, he will obtain X instead of P1.

Problem 10: (10 points) openssl script

The following file has been encrypted with openssl using a standard cipher: hw2file. The password is one of the 14 Yale residential college names, lowercase, and last name only. For example, Ezra Stiles => stiles.

Your job is to decode the file. We suggest that you write a script, e.g., using bash or python, that performs an exhaustive search. That is, it tries all specified ciphers with all possible passwords. Here is a list of the possible ciphers: ciphers.txt. Note that openssl sets the status bit upon return. Following the UNIX convention, if it succeeds, the bit is 0, else 1. Your script should avail itself of this bit of information.