9.5: Exercises
- Page ID
- 86462
There is nothing particularly bad about padding schemes. They are only a target because padding is a commonly used structure in plaintexts that is verified at the time of decryption.
A null character is simply the byte 00 . We say that a string is properly null terminated if its last character is null, but no other characters are null. Suppose you have access to the following oracle:
Suppose you are given a CTR-mode encryption of an unknown (but properly null terminated) plaintext \(m^{*}\) under unknown key \(k\). Suppose that plaintexts of arbitrary length are supported by truncating the CTR-stream to the appropriate length before xoring with the plaintext.
Show how to completely recover \(m^{*}\) in the presence of this null-termination oracle.
Show how to completely recover the plaintext of an arbitrary CBC-mode ciphertext in the presence of the following oracle:
Assume that the victim ciphertext encodes a plaintext that does not use any padding (its plaintext is an exact multiple of the blocklength).
Show how to perform a padding oracle attack, to decrypt arbitrary messages that use PKCS#7 padding (where all padded strings end with \(01,0202,030303\), etc.).
Sometimes encryption is as good as decryption, to an adversary.
(a) Suppose you have access to the following encryption oracle, where \(s\) is a secret that is consistent across all calls:
Yes, this question is referring to the awful ECB encryption mode (Construction 8.1). Describe an attack that efficiently recovers all of \(s\) using access to ECBORACLE. Assume that if the length of \(m \| s\) is not a multiple of the blocklength, then ECB mode will pad it with null bytes.
Hint:
(b) Now suppose you have access to a CBC encryption oracle, where you can control the IV that is used:
Describe an attack that efficiently recovers all of \(s\) using access to CBCORACLE. As above, assume that \(m \| s\) is padded to a multiple of the blocklength in some way. It is possible to carry out the attack no matter what the padding method is, as long as the padding method is known to the adversary.
Show how a padding oracle (for CBC-mode encryption with X.923 padding) can be used to generate a valid encryption of any chosen plaintext, under the same (secret) key that the padding oracle uses. In this problem, you are not given access to an encryption subroutine, or any valid ciphertexts - only the padding oracle subroutine.
Prove formally that CCA$ security implies CCA security.
Let \(\Sigma\) be an encryption scheme with message space \(\{0,1\}^{n}\) and define \(\Sigma^{2}\) to be the following encryption scheme with message space \(\{0,1\}^{2 n}\) :
(a) Prove that if \(\sum\) has CPA security, then so does \(\Sigma^{2}\).
(b) Show that even if \(\Sigma\) has CCA security, \(\Sigma^{2}\) does not. Describe a successful distinguisher and compute its distinguishing advantage.
Show that the following block cipher modes do not have CCA security. For each one, describe a successful distinguisher and compute its distinguishing advantage.
(a) OFB mode
(b) CBC mode
(c) CTR mode
Show that none of the schemes in Exercise \(7.7\) have CCA security. For each one, describe a successful distinguisher and compute its distinguishing advantage.
Let \(F\) be a secure block cipher with blocklength \(\lambda\). Below is an encryption scheme for plaintexts \(\mathcal{M}=\{0,1\}^{\lambda}\). Formally describe its decryption algorithm and show that it does not have CCA security.
Let \(F\) be a secure block cipher with blocklength \(\lambda\). Below is an encryption scheme for plaintexts \(\mathcal{M}=\{0,1\}^{\lambda}\). Formally describe its decryption algorithm and show that it does not have CCA security.
Alice has the following idea for a CCA-secure encryption. To encrypt a single plaintext block \(m\), do normal CBC encryption of \(0^{\text {blen }} \| m\). To decrypt, do normal CBC decryption but give an error if the first plaintext block is not all zeroes. Her reasoning is:
- The ciphertext has 3 blocks (including the IV). If an adversary tampers with the IV or the middle block of a ciphertext, then the first plaintext block will no longer be all zeroes and the ciphertext is rejected.
- If an adversary tampers with the last block of a ciphertext, then the CBC decryption results in \(0^{\text {blen }} \| m^{\prime}\) where \(m^{\prime}\) is unpredictable from the adversary’s point of view. Hence the result of decryption \(\left(m^{\prime}\right)\) will leak no information about the original \(m\).
More formally, let \(\mathrm{CBC}\) denote the encryption scheme obtained by using a secure PRF in CBC mode. Below we define an encryption scheme \(\Sigma^{\prime}\) with message space \(\{0,1\}^{\text {blen }}\) and ciphertext space \(\{0,1\}^{3 b l e n}\):
Show that \(\Sigma^{\prime}\) does not have CCA security. Describe a distinguisher and compute its distinguishing advantage. What part of Alice’s reasoning was not quite right?
Hint:
CBC and OFB modes are malleable in very different ways. For that reason, Mallory claims that encrypting a plaintext (independently) with both modes results in CCA security, when the Dec algorithm rejects ciphertexts whose OFB and CBC plaintexts don’t match. The reasoning is that it will be hard to tamper with both ciphertexts in a way that achieves the same effect on the plaintext.
Let \(C B C\) denote the encryption scheme obtained by using a secure PRF in CBC mode. Let OFB denote the encryption scheme obtained by using a secure PRF in OFB mode. Below we define an encryption scheme \(\Sigma^{\prime}\):
Show that \(\Sigma^{\prime}\) does not have CCA security. Describe a distinguisher and compute its distinguishing advantage.
This problem is a generalization of the previous one. Let \(\Sigma_{1}\) and \(\Sigma_{2}\) be two (possibly different) encryption schemes with the same message space \(\mathcal{M}\). Below we define an encryption scheme \(\Sigma^{\prime}\):
Show that \(\Sigma^{\prime}\) does not have CCA security, even if both \(\Sigma_{1}\) and \(\Sigma_{2}\) have CCA (yes, CCA) security. Describe a distinguisher and compute its distinguishing advantage.
Consider any padding scheme consisting of subroutines PAD (which adds valid padding to its argument) and VALIDPAD (which checks its argument for valid padding and returns true/false). Assume that VALIDPAD \((\operatorname{PAD}(x))=\) true for all strings \(x\).
Show that if an encryption scheme \(\Sigma\) has CCA security, then the following two libraries are indistinguishable: That is, a CCA-secure encryption scheme hides underlying plaintexts in the presence of padding-oracle attacks.
That is, a CAA-secure encryption scheme hides underlying plaintexts in the presence of padding-oracle attacks.
Note: The distinguisher can even send a ciphertext \(c\) obtained from EAVESDROP as an argument to PADDINGORACLE. Your proof should somehow account for this when reducing to the CCA security of \(\sum\).
Show that an encryption scheme \(\Sigma\) has CCA$ security if and only if the following two libraries are indistinguishable:
Note: In \(\mathcal{L}_{\text {left }}\), the adversary can obtain the decryption of any ciphertext via DECRYPT. In \(\mathcal{L}_{\text {right }}\), the DECRYPT subroutine is "patched" (via \(D\) ) to give reasonable answers to ciphertexts generated in EAVESDROP.