The first example of CCA insecurity in the book played games with the length of the ciphertext. This problem generalizes that idea.
Call an encryption scheme “online complete” if it satisfies the following property: Given an \(\ell\)-block plaintext, \((m_1,m_2,\ldots,m_{\ell})\), after receiving some number \(k<\ell\) of full plaintext blocks (\(m_1\) through \(m_k\)) the encryption scheme outputs ciphertext blocks \((c_0,c_1,\ldots,c_k)\) such that this sequence of ciphertext blocks form a valid encryption of the blocks that have been processed. In other words, \((c_0,c_1,\ldots,c_k)\) can be decrypted to get \((m_1,\ldots,m_k)\). This does imply that no special “termination”, such as proper padding, needs to exist in the plaintext.
All of the CPA-secure block cipher modes from Chapter 8 are online complete. Pick any of these modes and explain why this is the case.
Prove that if an encryption scheme is online complete, then it is not CCA secure.
The insecurity of the standard block cipher modes goes further than just attacks that play games with the length however. This problem explores attacks in which all library calls are done when the plaintext and ciphertext lengths are fixed.
Recall my informal description of a “malleable” encryption scheme: An encryption scheme is malleable if an attacker can tamper with the ciphertext in such a way that the plaintext decrypted from the modified ciphertext is meaningful or predictable in some way. In this problem we’ll formalize this for a specific form of tampering.
Let \(\Sigma\) be an encryption scheme with \({\mathcal M}=\{0,1\}^{\lambda}\) and \({\mathcal C}=\{0,1\}^{2\lambda}\), so we can write \((c_0,c_1)=\Sigma.\textsf{Enc}(k,m)\). Note that all of the CPA-secure block cipher modes satisfy this definition with \(blen=\lambda\).
Consider a function TAMPER that takes an encryption of a plaintext message \(m\), say with ciphertext \(c=(c_0,c_1)\), and modifies the ciphertext to produce a different ciphertext \(c'\). TAMPER succeeds if decrypting the tampered-with ciphertext produces the complement of \(m\) – in other words, if \(\Sigma.\textsf{Dec}(k,TAMPER(\Sigma.\textsf{Enc}(k,m)))=\overline{m}\).
Show that any encryption scheme for which there is a successful TAMPER function is not CCA secure.
Define a TAMPER function that succeeds with CBC mode (and show that it succeeds).
Define a TAMPER function that succeeds with CTR mode (and show that it succeeds).
Define a TAMPER function that succeeds with OFB mode (and show that it succeeds).
Textbook, Exercise 9.12 (Hint: The problem statement is long, but the solution isn’t super-hard — the hint given in the book is very helpful!)
Textbook, Exercise 10.2
Textbook, Exercise 10.4
Textbook, Exercise 10.7