Intro to network security homework 2

3. (15 points) (How much padding?) Imagine you posses an PKCS #7 encode message encrypted using CBC mode. Further imagine you have access to a machine that will take a ciphertext as input and return to you either success (decryption worked) or failure (there was a padding error) but, not the plaintext. Using just this machine, it is known that one can recover the underlying plaintext message without possessing the key. The attack works in two phases:
   1. Determine the number of bytes of padding, b.
   2. Use the number of padding bytes to aid in recovering the bytes of the plaintext bydoing 32n` decryption queries, where n is the number of blocks in the ciphertext and ` is the block size in bits.

Your goal is to devise an algorithm to handle step (1), determine the number of bytes of padding given only the ciphertext and access to the decryption oracle. How many decryption queries do you need to make in the worst case? Note: You should not worry about step (2) at all.

4. (15 points) (CPA Security) In class we discussed a desirable property of cryptosystem which was resistance to Chosen-Plaintext Attacks (CPA). The CPA property is generally discussed as a game between a defender and an adversary. The adversary’s goal is to break the encryption or learn some non- trivial property of the cipher text. The game is as follows:
   1. The adversary selects two random messages m₀ and m₁ from M and sends them to the defender.
   2. The defender selects a key k ∈K uniformly at random. Additionally, the defender selects a b ∈ {0,1} uniformly at random. The defender sends E_k (m_b) to the adversary.
   3. The adversary is then allowed to make a polynomial number of encryption queriesto the defender. In other words, the adversary selects any message m ∈M, sends it to the defender, and the defender will return to the adversary E_k (m).
   4. The adversary makes a guess b⁰ ∈{0,1} and wins the game if b = b⁰. In other words the adversary selected m_b0 in step 2.

Construct an adversary that wins the game (be sure to specify what they do at each step of the game) when the encryption is performed using AES-128. Hint: You will not need to understand the inner workings of AES-128 to answer this question.

5. (10 points) (Substitution-Permutation Networks) A derangement is a permutation where no element is mapped to itself. For example, the permutation π defined as: π (1) = 2,π (2) = 3,π (3) = 1 is a derangement on digits 1 through 3. I claim that the permutation phase of a substitution-permutation network should be a derangement. Why is this a good idea? Please defend your answer. Hint: Think about what the purpose of the permutation step.