10.5: Exercises

Last updated
Save as PDF

Page ID: 86431

\( \newcommand{\vecs}[1]{\overset { \scriptstyle \rightharpoonup} {\mathbf{#1}} } \) \( \newcommand{\vecd}[1]{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash {#1}}} \)\(\newcommand{\id}{\mathrm{id}}\) \( \newcommand{\Span}{\mathrm{span}}\) \( \newcommand{\kernel}{\mathrm{null}\,}\) \( \newcommand{\range}{\mathrm{range}\,}\) \( \newcommand{\RealPart}{\mathrm{Re}}\) \( \newcommand{\ImaginaryPart}{\mathrm{Im}}\) \( \newcommand{\Argument}{\mathrm{Arg}}\) \( \newcommand{\norm}[1]{\| #1 \|}\) \( \newcommand{\inner}[2]{\langle #1, #2 \rangle}\) \( \newcommand{\Span}{\mathrm{span}}\) \(\newcommand{\id}{\mathrm{id}}\) \( \newcommand{\Span}{\mathrm{span}}\) \( \newcommand{\kernel}{\mathrm{null}\,}\) \( \newcommand{\range}{\mathrm{range}\,}\) \( \newcommand{\RealPart}{\mathrm{Re}}\) \( \newcommand{\ImaginaryPart}{\mathrm{Im}}\) \( \newcommand{\Argument}{\mathrm{Arg}}\) \( \newcommand{\norm}[1]{\| #1 \|}\) \( \newcommand{\inner}[2]{\langle #1, #2 \rangle}\) \( \newcommand{\Span}{\mathrm{span}}\)\(\newcommand{\AA}{\unicode[.8,0]{x212B}}\)

Exercise \(10.1\)

Consider the following MAC scheme, where \(F\) is a secure PRF with in \(=\) out \(=\lambda\) :

Show that the scheme is not a secure MAC. Describe a distinguisher and compute its advantage.

Exercise \(10.2\)

Consider the following MAC scheme, where \(F\) is a secure PRF with in \(=\) out \(=\lambda\) :

Show that the scheme is not a secure MAC. Describe a distinguisher and compute its advantage.

Exercise \(10.3\)

Suppose MAC is a secure MAC algorithm. Define a new algorithm \(M_{A C}(k, m)=\) \(\operatorname{MAC}(k, m) \| M A C(k, m)\). Prove that \(\mathrm{MAC}^{\prime}\) is also a secure \(\mathrm{MAC}\) algorithm.

Note: MAC’ cannot be a secure PRF. This shows that MAC security is different than PRF security.

Exercise \(10.4\)

Suppose MAC is a secure MAC scheme, whose outputs are \(\ell\) bits long. Show that there is an efficient adversary that breaks MAC security (i.e., distinguishes the relevant libraries) with advantage \(\Theta\left(1 / 2^{\ell}\right)\). This implies that MAC tags must be reasonably long in order to be secure.

Exercise \(10.5\)

Suppose we use CBC-MAC with message space \(\mathcal{M}=\left(\{0,1\}^{\lambda}\right)^{*}\). In other words, a single MAC key will be used on messages of any length that is an exact multiple of the block length. Show that the result is not a secure MAC. Construct a distinguisher and compute its advantage.

Hint:

Exercise \(\star 10.6\)

Here is a different way to extend CBC-MAC for mixed-length messages, when the length of each message is known in advance. Assume that \(F\) is a secure PRF with in out \(=\lambda\).

Prove that this scheme is a secure MAC for message space \(\mathcal{M}=\left(\{\theta, 1\}^{\lambda}\right)^{*}\). You can use the fact that CBC-MAC is secure for messages of fixed-length.

Exercise \(10.7\)

Let \(E\) be a CPA-secure encryption scheme and \(M\) be a secure MAC. Show that the following encryption scheme (called encrypt & MAC) is not CCA-secure:

Describe a distinguisher and compute its advantage.

Exercise \(10.8\)

Let \(E\) be a CPA-secure encryption scheme and \(M\) be a secure MAC. Show that the following encryption scheme \(\Sigma\) (which I call encrypt-and-encrypted-MAC) is not CCA-secure:

Describe a distinguisher and compute its advantage.

Exercise \(\star 10.9\)

In Construction \(7.4\), we encrypt one plaintext block into two ciphertext blocks. Imagine applying the Encrypt-then-MAC paradigm to this encryption scheme, but (erroneously) computing a MAC of only the second ciphertext block.

In other words, let \(F\) be a PRF with in \(=\) out \(=\lambda\), and let \(M\) be a MAC scheme for message space \(\{0,1\}^{\lambda}\). Define the following encryption scheme:

Show that the scheme does not have CCA security. Describe a successful attack and compute its advantage.

Hint:\(\)

Exercise \(10.10\)

When we combine different cryptographic ingredients (e.g., combining a CPA-secure encryption scheme with a MAC to obtain a CCA-secure scheme) we generally require the two ingredients to use separate, independent keys. It would be more convenient if the entire scheme just used a single \(\lambda\)-bit key.

(a) Suppose we are using Encrypt-then-MAC, where both the encryption scheme and MAC have keys that are \(\lambda\) bits long. Refer to the proof of security of Claim \(12.5\) and describe where it breaks down when we modify Encrypt-then-MAC to use the same key for both the encryption & MAC components:

(b) While Encrypt-then-MAC requires independent keys \(k_{\mathrm{e}}\) and \(k_{\mathrm{m}}\) for the two components, show that they can both be derived from a single key using a PRF.

In more detail, let \(F\) be a PRF with in \(=1\) and out \(=\lambda\). Prove that the following modified Encrypt-then-MAC construction is CCA-secure:

You should not have to re-prove all the tedious steps of the Encrypt-then-MAC security proof. Rather, you should apply the security of the PRF in order to reach the original Encrypt-then-MAC construction, whose security we already proved (so you don’t have to repeat)