8.5: Exercises
- Page ID
- 86429
Prove that a block cipher in ECB mode does not provide CPA security. Describe a distinguisher and compute its advantage.
Describe OFB decryption mode.
Describe CTR decryption mode.
CBC mode:
(a) In CBC-mode encryption, if a single bit of the plaintext is changed, which ciphertext blocks are affected (assume the same IV is used)?
(b) In CBC-mode decryption, if a single bit of the ciphertext is changed, which plaintext blocks are affected?
Prove that CPA$ security for variable-length plaintexts implies CPA security for variablelength plaintexts. Where in the proof do you use the fact that \(\left|m_{L}\right|=\left|m_{R}\right|\) ?
Suppose that instead of applying \(C B C\) mode to a block cipher, we apply it to one-time pad. In other words, we replace every occurrence of \(F(k, \star)\) with \(k \oplus \star\) in the code for CBC encryption. Show that the result does not have CPA security. Describe a distinguisher and compute its advantage.
Prove that there is an attacker that runs in time \(O\left(2^{\lambda / 2}\right)\) and that can break CPA security of CBC mode encryption with constant probability.
Below are several block cipher modes for encryption, applied to a PRP \(F\) with blocklength blen \(=\lambda\). For each of the modes:
- Describe the corresponding decryption procedure.
- Show that the mode does not have CPA-security. That means describe a distinguisher and compute its advantage.
Mode (a) is similar to CBC, except the xOR happens after, rather than before, the block cipher application. Mode (c) is essentially the same as CBC decryption.
Suppose you observe a CBC ciphertext and two of its blocks happen to be identical. What can you deduce about the plaintext? State some non-trivial property of the plaintext that doesn’t depend on the encryption key.
The CPA$-security proof for CBC encryption has a slight complication compared to the proof of OFB encryption. Recall that an important part of the proof is arguing that all inputs to the PRF are distinct.
In OFB, outputs of the PRF were fed directly into the PRF as inputs. The adversary had no influence over this process, so it wasn’t so bad to argue that all PRF inputs were distinct (with probability negligibly close to 1 ).
By contrast, CBC mode takes an output block from the PRF, XOR’s it with a plaintext block (which is after all chosen by the adversary), and uses the result as input to the next PRF call. This means we have to be a little more careful when arguing that CBC mode gives distinct inputs to all PRF calls (with probability negligibly close to 1 ).
(a) Prove that the following two libraries are indistinguishable:
Hint:Lemma 4.12 U
(b) Using part (a), and the security of the underlying PRF, prove the CPA$-security of CBC mode.
Hint:correspond to the set of all inputs sent to the PRF. Let R , let right L In , we sample le L (the output of the PRF) uniformly as in r plaintext block. Instead of sampling has never been used as a PRF-input before. This guarantees that the next PRF m⊕r so that r call will be on a “fresh” input.
Note: Appreciate how important it is that the adversary chooses plaintext block \(m\) before "seeing" the output \(r\) from the PRF (which is included in the ciphertext).
Prove that CTR mode achieves CPA$ security.
Hint:to show that there is only negligible probability of chosing the IV so that the block Lemma 4.12 Ucipher gets called on the same value twice.
Let \(F\) be a secure PRF with out \(=\) in \(=\lambda\) and let \(F^{(2)}\) denote the function \(F^{(2)}(k, r)=\) \(F(k, F(k, r))\)
(a) Prove that \(F^{(2)}\) is also a secure PRF.
(b) What if \(F\) is a secure PRP with blocklength blen? Is \(F^{(2)}\) also a secure PRP?
This question refers to the nonce-based notion of CPA security.
(a) Show a definition for CPA$ security that incorporates both the nonce-based syntax of Section \(7.1\) and the variable-length plaintexts of Section 8.2.
(b) Show that CBC mode not secure as a nonce-based scheme (where the IV is used as a nonce).
(c) Show that CTR mode is not secure as a nonce-based scheme (where the IV is used as a nonce). Note that if we restrict (randomized) CTR mode to a single plaintext block, we get the CPA-secure scheme of Construction 7.4, which is is secure as a nonce-based scheme. The attack must therefore use the fact that plaintexts can be longer than one block. (Does the attack in part (b) work with single-block plaintexts?)
One way to convert a randomized-IV-based construction into a nonce-based construction is called the synthetic IV approach.
(a) The synthetic-IV (SIV) approach applied to CBC mode is shown below. Prove that it is CPA/CPA$ secure as a nonce-based scheme (refer to the security definitions from the previous problem):
Instead of chosing a random IV \(c_{0}\), it is generated deterministically from the nonce \(v\) using the block cipher \(F\). In your proof, you can use the fact that randomized CBC mode has CPA$ security, and that \(F\) is also a secure PRF.
(b) It is important that the SIV construction uses two keys for different purposes. Suppose that we instead used the same key throughout:
Show that the resulting scheme does not have CPA$ security (in the nonce-based sense). Ignore the complication of padding, and only consider plaintexts that are a multiple of the blocklength. Describe a successful distinguisher and compute its advantage.
(c) For randomized encryption, it is necessary to include the IV in the ciphertext; otherwise the receiver cannot decrypt. In the nonce-based setting we assume that the receiver knows the correct nonce (e.g., from some out-of-band communication). With that in mind, we could modify the scheme from part (b) to remove \(c_{0}\), since the receiver could reconstruct it anyway from \(v\).
Show that even with this modification, the scheme still fails to be CPA-secure under the nonce-based definition.
Implementers are sometimes cautious about IVs in block cipher modes and may attempt to "protect" them. One idea for protecting an IV is to prevent it from directly appearing in the ciphertext. The modified CBC encryption below sends the IV through the block cipher before including it in the ciphertext:
This ciphertext can be decrypted by first computing \(c_{0}:=F^{-1}\left(k, c_{0}^{\prime}\right)\) and then doing usual CBC decryption on \(c_{0}\|\cdots\| c_{\ell}\).
Show that this new scheme is not CPA-secure (under the traditional definitions for randomized encryption).
Suppose a bad implementation leads to two ciphertexts being encrypted with the same IV, rather than a random IV each time.
(a) Characterize as thoroughly as you can what information is leaked about the plaintexts when CBC mode was used and an IV is repeated.
(b) Characterize as thoroughly as you can what information is leaked about the plaintexts when CTR mode was used and an IV is repeated.
Describe how to extend CTR and OFB modes to deal with plaintexts of arbitrary length (without using padding). Why is it so much simpler than CBC ciphertext stealing?
The following technique for ciphertext stealing in CBC was proposed in the 1980 s and was even adopted into commercial products. Unfortunately, it’s insecure.
Suppose the final plaintext block \(m_{\ell}\) is blen \(-j\) bits long. Rather than padding the final block with zeroes, it is padded with the last \(j\) bits of ciphertext block \(c_{\ell-1}\). Then the padded block \(m_{\ell}\) is sent through the PRP to produce the final ciphertext block \(c_{\ell}\). Since the final \(j\) bits of \(c_{\ell-1}\) are recoverable from \(c_{\ell}\), they can be discarded.
If the final block of plaintext is already blen bits long, then standard CBC mode is used.
Show that the scheme does not satisfy CPA$ security. Describe a distinguisher and compute its advantage.
Hint:Ask for several encryptions of plaintexts whose last block isg. 1 − blen
Prove that any CPA-secure encryption remains CPA-secure when augmented by padding the input.
Prove that \(C B C\) with ciphertext stealing has CPA$ security. You may use the fact that CBC mode has CPA$ security when restricted to plaintexts whose length is an exact multiple of the blocklength (i.e., CBC mode without padding or ciphertext stealing).
Hint: Let blen) ∗ , and let }1, 0{ = M denote CBC mode with ciphertext stealing (so CBC-CTS ∗ ). Observe that it is easy L to implement a call to CBC-CTS cpa$-real L by a related call to CBC cpa$-real plus a small amount of additional processing
Propagating \(\mathrm{CBC}(\mathrm{PCBC})\) mode refers to the following variant of \(\mathrm{CBC}\) mode:
(a) Describe PCBC decryption.
(b) Assuming that standard CBC mode has CPA$-security (for plaintexts that are exact multiple of the block length), prove that PCBC mode also has CPA$-security (for the same plaintext space).
Hint: Write PCBC encryption using plain CBC encryption as a subroutine.
(c) Consider the problem of adapting CBC ciphertext stealing to PCBC mode. Suppose the final plaintext block \(m_{\ell}\) has \(b l e n-j\) bits, and we pad it with the final \(j\) bits of the previous plaintext block \(m_{\ell-1}\). Show that discarding the last \(j\) bits of \(c_{\ell-1}\) still allows for correct decryption and results in CPA$ security.
Hint: See Exercise 8.20
(d) Suppose the final plaintext block is padded using the final \(j\) bits of the previous ciphertext block \(c_{\ell-1}\). Although correct decryption is still possible, the construction is no longer secure. Show an attack violating the CPA$-security of this construction. Why doesn’t the proof approach from part (c) work?
Hint: Ask for several encryptions of plaintexts whose last block is 1 bit long