CSL866: Problem Set 2

You will need use the java API for cryptography. Please go through this link and familiarize with the basics.

Problem 1: [30 points]

Mr. Cryptix is a budding cryptographer who has just studied block ciphers. After spending lot of time building and executing attacks on block ciphers like DES and AES, he is now convinced that DES and AES are PRF-secure. Intuitively, this means that the output of these block ciphers appears random. He now has an interesting idea for encrypting jpeg images. He does the following:
  1. First, he converts the given image to a grayscale image. A grayscale image is described by a 2D array of pixels, where each pixel is an integer between 0 and 255 (0 denotes black and 255 denotes white). Let this 2D array be denoted by I.
  2. He then constructs a 1D array A of bytes from this 2D array I of grayscale values in the following manner: A[i] = I[i/width][i%width].
  3. He then considers 8 byte chunks (comprising of 64 bits) of this array A and encrypts these chunks by applying DES (using the 56 bit DES key that it shares with Mr. Receivix to whom Mr. Cryptix wants to send the encrypted image). We know that Mr. Cryptix unknowingly is using ECB mode of operation. Let the encrypted byte array be denoted by B.
  4. He converts this 1D array B to a 2D array EI as follows: EI[i][j] = B[width * i + j].
  5. Finally, he sends a jpeg image by copying the grayscale value to all the RGB components (he ends up getting a grayscale image)
Mr. Cryptix has not yet studied symmetric encryption using block ciphers and its security properties. Hence he does not know that the ECB mode of operation is not very secure. He thinks that since each encoded block appears random the entire image should appear random and hence the sniffing Mr. Evilix will not be able to figure out the secret word that Mr. Cryptix has embedded in the image. However, to make things more interesting, he writes the secret word in funny fonts. He uses his mehtod to encrypt the following jpeg image.

cryptix
Here is the link to the image file.

To his surprise, Mr. Cryptix finds that the encrypted image is not secure at all. This exercise exposes to him the structural weakness of the ECB mode of operation. Mr. Cryptix being still unaware of secure modes of operation such as CBC$ and CTRC, tries a different technique. Just before step 3 above, he adds a randomly chosen 0/1 value to each byte of A. This means that for each index i of the array A, he picks a value b[i] which is 0 with probability 1/2 and 1 with probability 1/2, and then updates A[i] = (A[i] + b[i])%256. He figures that he just needs to send size additional bits to Mr. Receivix, where size is the number of pixels in the image. For the above image this is 786432 bits = 96 KB. Since the image requires 132KB of space anyways this is not going to be a significant overhead.

After encrypting the image with this newly designed technique, he implements it and finds that the encrypted images indeed look extremely random. However, he does not try to formally study the security properties of his scheme but is thinking about deploying his technique. Mr. Cryptix is a bit skeptical about deploying his technique and wants to make sure that there is no easy attack on his scheme. To ensure that there is no easy attack, he devises a challenge. He has created 29 (coincidentally this is the number of students in CSL866) different images with different secret codes embedded in different images. The secret code is a name of a person and a 10 digit number. He is interested in knowing whether someone could figure out these secret codes.

Here is what you have to do for the assignment:
  1. Use a DES key to implement the first technique that Mr. Cryptix came up with. You can pick up your secret key from here. You have to send the encrypted image file corresponding to the image above. (Use transformation "DES/ECB/NoPadding")
  2. Use the same DES key to implement the CBC$ mode of operation. You have to send the encrypted image file corresponding to the image above. Note that you also have to send the Intialization Vector (IV). (Use transformation "DES/CBC/NoPadding")
  3. You are given an encrypted image that is encrypted using Mr. Cryptix's final scheme. You have to figure out the secret name and 10 digit number and send it to me. You may pick up your encrypted image from here. You do not get the random values (b[i]'s) that Mr. Cryptix uses in his scheme.
Here is some code you may use for image manipulation.


Problem 2: [10 Points]

Consider an encryption scheme SE = (K, E, D) that is insecure in the sense that there is an adversary A that is able to guess the 1000th bit of any given message with probability at least (1/2 + δ), where δ = 1/poly(k) (poly denotes some fixed polynomial and k is the size of the key). The probability of success of A is over the random choice of the keys and A's internal randomness. Show that SE is not ind-cpa secure by constructing an adversary B that has the ind-cpa advantage > 9/10. Discuss the running time of the adversary B.

(Hint: You might need to use the Chernoff-Hoeffding Theorem for this problem. Here is a link for a nice writeup that contains this theorem.)

Problem 3: [10 Points]

Assume that DES is PRF-secure. Consider the following modified CBC modes of operation that uses DES as the block cipher. For this problem you may assume that the message length is only 128 bits.
  1. Mode-1: Given a message (x1, x2), where x1 and x2 are 64 bits messages, the encryption algorithm chooses a random 64 bit string r, and returns the following encrypted ciphertext: (y0 | y1 | y2 | y3) where
    1. y0 = 064
    2. y1 = DESK(y0 ⊕ r)
    3. y2 = DESK(y1 ⊕ x1)
    4. y3 = DESK(y2 ⊕ x2)
  2. Mode-2: Given a message (x1, x2), where x1 and x2 are 64 bits messages, the encryption algorithm chooses a random 64 bit string r, and returns the following encrypted ciphertext: (y0 | y1 | y2 | y3) where
Discuss the ind-cpa security of the above two modes of operation.

Problem 4: [10 Points]

Two distributions D1 and D2 over {0,1}n are called computationally indistinguishable if for any polynomial time (polynomial in n) algorithm A, that takes n bit inputs and outputs a single bit, we have:
|Prx ← D1[A(x) = 1] - Prx ← D2[A(x) = 1]| ≤ 1/negl(n), (where 1/negl(n) ≤ 1/poly(n) for any polynomial poly and for all sufficiently large n)
(Note that for any distribution D, x ← D denotes that x is sampled from the distribution D)

Let MA = (K, T, V) be a message authentication scheme such that T generates tags of size n bits. Prove or disprove the following statement:
"If MA is uf-cma secure, then for any pair of messages x1, x2, x1 ≠ x2, the distributions TK(x1) and TK(x2) are always computationally indistinguishable"

(Note that the randomness is over the choice of the keys and internal randomness of the tag generation algorithm T.)