10.4: Encrypt-Then-MAC
- Page ID
- 7365
\( \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}}\)
\( \newcommand{\vectorA}[1]{\vec{#1}} % arrow\)
\( \newcommand{\vectorAt}[1]{\vec{\text{#1}}} % arrow\)
\( \newcommand{\vectorB}[1]{\overset { \scriptstyle \rightharpoonup} {\mathbf{#1}} } \)
\( \newcommand{\vectorC}[1]{\textbf{#1}} \)
\( \newcommand{\vectorD}[1]{\overrightarrow{#1}} \)
\( \newcommand{\vectorDt}[1]{\overrightarrow{\text{#1}}} \)
\( \newcommand{\vectE}[1]{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash{\mathbf {#1}}}} \)
\( \newcommand{\vecs}[1]{\overset { \scriptstyle \rightharpoonup} {\mathbf{#1}} } \)
\( \newcommand{\vecd}[1]{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash {#1}}} \)
\(\newcommand{\avec}{\mathbf a}\) \(\newcommand{\bvec}{\mathbf b}\) \(\newcommand{\cvec}{\mathbf c}\) \(\newcommand{\dvec}{\mathbf d}\) \(\newcommand{\dtil}{\widetilde{\mathbf d}}\) \(\newcommand{\evec}{\mathbf e}\) \(\newcommand{\fvec}{\mathbf f}\) \(\newcommand{\nvec}{\mathbf n}\) \(\newcommand{\pvec}{\mathbf p}\) \(\newcommand{\qvec}{\mathbf q}\) \(\newcommand{\svec}{\mathbf s}\) \(\newcommand{\tvec}{\mathbf t}\) \(\newcommand{\uvec}{\mathbf u}\) \(\newcommand{\vvec}{\mathbf v}\) \(\newcommand{\wvec}{\mathbf w}\) \(\newcommand{\xvec}{\mathbf x}\) \(\newcommand{\yvec}{\mathbf y}\) \(\newcommand{\zvec}{\mathbf z}\) \(\newcommand{\rvec}{\mathbf r}\) \(\newcommand{\mvec}{\mathbf m}\) \(\newcommand{\zerovec}{\mathbf 0}\) \(\newcommand{\onevec}{\mathbf 1}\) \(\newcommand{\real}{\mathbb R}\) \(\newcommand{\twovec}[2]{\left[\begin{array}{r}#1 \\ #2 \end{array}\right]}\) \(\newcommand{\ctwovec}[2]{\left[\begin{array}{c}#1 \\ #2 \end{array}\right]}\) \(\newcommand{\threevec}[3]{\left[\begin{array}{r}#1 \\ #2 \\ #3 \end{array}\right]}\) \(\newcommand{\cthreevec}[3]{\left[\begin{array}{c}#1 \\ #2 \\ #3 \end{array}\right]}\) \(\newcommand{\fourvec}[4]{\left[\begin{array}{r}#1 \\ #2 \\ #3 \\ #4 \end{array}\right]}\) \(\newcommand{\cfourvec}[4]{\left[\begin{array}{c}#1 \\ #2 \\ #3 \\ #4 \end{array}\right]}\) \(\newcommand{\fivevec}[5]{\left[\begin{array}{r}#1 \\ #2 \\ #3 \\ #4 \\ #5 \\ \end{array}\right]}\) \(\newcommand{\cfivevec}[5]{\left[\begin{array}{c}#1 \\ #2 \\ #3 \\ #4 \\ #5 \\ \end{array}\right]}\) \(\newcommand{\mattwo}[4]{\left[\begin{array}{rr}#1 \amp #2 \\ #3 \amp #4 \\ \end{array}\right]}\) \(\newcommand{\laspan}[1]{\text{Span}\{#1\}}\) \(\newcommand{\bcal}{\cal B}\) \(\newcommand{\ccal}{\cal C}\) \(\newcommand{\scal}{\cal S}\) \(\newcommand{\wcal}{\cal W}\) \(\newcommand{\ecal}{\cal E}\) \(\newcommand{\coords}[2]{\left\{#1\right\}_{#2}}\) \(\newcommand{\gray}[1]{\color{gray}{#1}}\) \(\newcommand{\lgray}[1]{\color{lightgray}{#1}}\) \(\newcommand{\rank}{\operatorname{rank}}\) \(\newcommand{\row}{\text{Row}}\) \(\newcommand{\col}{\text{Col}}\) \(\renewcommand{\row}{\text{Row}}\) \(\newcommand{\nul}{\text{Nul}}\) \(\newcommand{\var}{\text{Var}}\) \(\newcommand{\corr}{\text{corr}}\) \(\newcommand{\len}[1]{\left|#1\right|}\) \(\newcommand{\bbar}{\overline{\bvec}}\) \(\newcommand{\bhat}{\widehat{\bvec}}\) \(\newcommand{\bperp}{\bvec^\perp}\) \(\newcommand{\xhat}{\widehat{\xvec}}\) \(\newcommand{\vhat}{\widehat{\vvec}}\) \(\newcommand{\uhat}{\widehat{\uvec}}\) \(\newcommand{\what}{\widehat{\wvec}}\) \(\newcommand{\Sighat}{\widehat{\Sigma}}\) \(\newcommand{\lt}{<}\) \(\newcommand{\gt}{>}\) \(\newcommand{\amp}{&}\) \(\definecolor{fillinmathshade}{gray}{0.9}\)Our motivation for studying \(\mathrm{MACs}\) is that they seem useful in constructing a CCA-secure encryption scheme. The idea is to add a MAC to a CPA-secure encryption scheme. The decryption algorithm can raise an error if the MAC is invalid, thereby ensuring that adversarially-generated (or adversarially-modified) ciphertexts are not accepted. There are several natural ways to combine a MAC and encryption scheme, but not all are secure! (See the exercises.) The safest way is known as encrypt-then-MAC:
Let \(E\) denote an encryption scheme, and \(M\) denote a \(M A C\) scheme where E.C \(\subseteq M . M\) (i.e., the MAC scheme is capable of generating MACs of ciphertexts in the E scheme). Then let EtM denote the encrypt-then-MAC construction given below:
Importantly, the scheme computes a MAC of the CPA ciphertext, and not of the plaintext! The result is a CCA-secure encryption scheme:
If E has CPA security and \(M\) is a secure \(M A C\), then Et \(M\) (Construction 10.9) has \(C C A\) security.
Proof
As usual, we prove the claim with a sequence of hybrid libraries:
The starting point is \(\mathcal{L}_{\mathrm{cca}-L}^{E t M}\), shown here with the details of the encrypt-then-MAC construction highlighted. Our goal is to eventually swap \(m_{L}\) with \(m_{R}\). But the CPA security of \(E\) should allow us to do just that, so what’s the catch? To apply the CPA-security of \(E\), we must factor out the relevant call to \(E\).Enc in terms of the CPA library \(\mathcal{L}_{\text {cpa-L }}^{E}\). This means that \(k_{\mathrm{e}}\) becomes private to the \(\mathcal{L}_{\mathrm{cpa}-\mathrm{L}}\) library. But \(k_{\mathrm{e}}\) is also used in the last line of the library as \(E\). \(\operatorname{Dec}\left(k_{\mathrm{e}}, c\right)\). The \(C P A\) security library for \(E\) provides no way to carry out such E.Dec statements! |
|
The operations of the MAC scheme have been factored out in terms of \(\mathcal{L}_{\mathrm{mac}-real}^{M}\). Notably, in the DEC subroutine the condition \("t\neq M.\textrm{MAC}\left ( k_{M},c \right )"'\) has been replaced with “not CHECKTAG\((c,t)\).” | |
We have applied the security of the MAC scheme, and replaced \(\mathcal{L}_{\text {mac-real}}\) with \(\mathcal{L}_{\text {mac-fake}}\). | |
We have inlined the \(\mathcal{L}_{\text {mac-fake }}\) library. This library keeps track of a set \(\mathcal{S}\) of values for the purpose of the CCA interface, but also a set \(\mathcal{T}\) of values for the purposes of the MAC. However, it is clear from the code of this library that \(\mathcal{S}\) and \(\mathcal{T}\) always have the same contents. Therefore, the two conditions " \((c, t) \in \mathcal{S}\) " and " \((c, t) \notin \mathcal{T}\) " in the DEC subroutine are exhaustive! The final line of DEC is unreachable. This hybrid highlights the intuitive idea that an adversary can either query DEC with a ciphertext generated by EAVESDROP (the \((c, t) \in \mathcal{S}\) case) - in which case the response is null \(-\) or with a different ciphertext \(-\) in which case the response will be err since the MAC will not verify. |
|
The unreachable statement has been removed and the redundant variables \(\mathcal{S}\) and \(\mathcal{T}\) have been unified. Note that this hybrid li- brary never uses \(E\).Dec, making it possible to express its use of \(\mathcal{S}:=\mathcal{S} \cup\{(c, t)\}\) the \(E\) encryption scheme in terms of \(\mathcal{L}_{\text {cpa-L}}\). | |
The statement involving the encryption scheme \(E\) have been factored out in terms of \(\mathcal{L}_{\text {cpa-L}}\). |
We have now reached the half-way point of the proof. The proof proceeds by replacing \(\mathcal{L}_{\text {cpa-L}}\) with \(\mathcal{L}_{\text {cpa-R}}\) (so that \(m_R\) rather than \(m_L\) is encrypted), applying the same modifications as before (but in reverse order), to finally arrive at \(\mathcal{L}_{\text {cca-R}}\). The repetitive details have been omitted, but we mention that when listing the same steps in reverse, the changes appear very bizarre indeed. For instance, we add an unreachable statement to the DEC subroutine; we create a redundant variable \(\mathcal{T}\) whose contents are the same as \(\mathcal{S}\); we mysteriously change one instance of \(\mathcal{S}\) (the condition of the second if-statement in DEC) to refer to the other variable \(\mathcal{T}\). Of course, all of this is so that we can factor out the statements referring to the MAC scheme (along with \(\mathcal{T}\)) in terms of \(\mathcal{L}_{\text {mac-fake}}\) and finally replace \(\mathcal{L}_{\text {mac-fake}}\) with \(\mathcal{L}_{\text {mac-real}}\).