Textbook, Exercise 6.8 parts a-c. You don’t need to go into a lot of detail with these – just give a simple distinguisher, and analyze the probabilities/advantage. They should all be (hopefully!) pretty obvious, but it’s good practice.
Construction 6.10 gives the formula for a one-round keyed Feistel network.
Write this out using \(k_1\) as the key variable instead of just \(k\), and then apply \(F^{*}\) again to this output using key \(k_2\). The formulas get messy, so it’s perfectly ok to write one formula for the first half of the bits and a different formula for the second half (rather than concatenating two formulas together). This is then the formula for a two-round keyed Feistel network with round keys \(k_1\) and \(k_2\) (assume they are separate and independent).
Use your formula(s) to prove that this is not a secure PRP (hint: only half of the output bits, or one of the formulas, is important to the distinguisher, so you can ignore the other half – can you make two different queries that will recognize when this formula is applied?) [A side note on the importance of this – one and two round Feistel networks are not secure PRPs, but a three round Feistel network with a secure PRF is a secure PRP – this is stated as Theorem 6.12 in the textbook.]
Textbook, Exercise 7.1 (note that this is very similar to Exercise 6.1 from the previous assignment – to make notation concrete, let the plaintext space be \(\{0,1\}^{in}\) and the ciphertext space be \(\{0,1\}^{out}\)).
Textbook, Exercise 7.5 (“nonce-based CPA security” is defined in Exercise 7.4).
Textbook, Exercise 7.11 (the key point here is that any scheme that preserves length – where the ciphertext is the same length as the plaintext – cannot be CPA secure)
Textbook, Exercise 8.1.
Constructions 8.1 and 8.2 give algorithms and diagrams for the decryption of ECB and CBC mode; however, Construction 8.3 does not give the same for CTR mode. For this question, write out both the algorithm and draw a diagram for CTR-mode decryption.
Consider a simple function inspired by the one-time pad: \(F(k,x)=k\oplus x\).
Prove that for any key \(k\), \(F(k,\cdot)\) is a permutation, and give \(F^{-1}(k,x)\).
Prove that \(F\) is not a secure PRP by giving a distinguisher and analyzing the advantage (hint: remember that the distinguisher can call LOOKUP more than once!).
Since \(F\) is a permutation, it can be used in the CBC construction as defined in Construction 8.2. Write out the formula for \(c_1\) using this \(F\) function and a randomly chosen \(c_0\).
Give an algorithm that an adversary could use to compute the secret key with a single call to CHALLENGE (from the \(\textsf{cpa\$-real}\) library on page 148 of Chapter 8).