Miscellaneous rewordings and fixings.

[doc/ips] / enc-symm.tex

\xcalways\section{Symmetric encryption}\x

\xcalways\subsection{Syntax}\x

\begin{slide}
  \head{Symmetric encryption syntax}
  
  A \emph{symmetric encryption scheme} $\mathcal{E} = (E, D)$ is a set of
  keys $\keys\mathcal{E}$ (usually $\{0, 1\}^k$ for some integer $k$) and
  pair of algorithms:
  \begin{itemize}
  \item an \emph{encryption} algorithm $E\colon \keys\mathcal{E} \times \{0,
    1\}^* \to \{0, 1\}^*$; and
  \item a \emph{decryption} algorithm $D\colon \keys\mathcal{E} \times \{0,
    1\}^* \to \{0, 1\}^*$.
  \end{itemize}
  We also have a \emph{correctness} requirement: for any $K \in
  \keys\mathcal{E}$, and any plaintext $x$, if $E(K, x)$ returns $y$ then
  $D(K, y)$ returns $x$.

  We write $E_K(\cdot)$ rather than $E(K, \cdot)$, and $D_K(\cdot)$ rather
  than $D(K, \cdot)$.
\end{slide}

\xcalways\subsection{Security notions}\x

\begin{slide}
  \head{Symmetric encryption security notions}
  
  In symmetric scheme, an adversary who doesn't know the key can't encrypt
  data for itself.  To modify our security notions by providing the adversary
  with an encryption oracle.
  
  We consider semantic security, indistinguishability and non-malleability,
  against chosen-plaintext and chosen-ciphertext attacks.  To make life more
  complicated, we have three different indistinguishability notions.

  We use the same notation to describe the decryption oracles provided in
  various types of attacks:
  \begin{tabular}[C]{l Mc Mc }
                                \hlx*{hv}
    Attack & D_0(c) & D_1(c) \\ \hlx{vhv}
    CPA    & \bot   & \bot   \\  
    CCA1   & D_K(c) & \bot   \\  
    CCA2   & D_K(c) & D_K(c) \\ \hlx*{vh}
  \end{tabular}
\end{slide}

\begin{slide}
  \topic{semantic security}
  \head{Semantic security}

  The semantic security game is as for the asymmetric case, except for the
  presence of encryption oracles.

  \begin{program}
    Experiment $\Expt{sem-\id{atk}-$b$}{\mathcal{E}}(A)$: \+ \\
      $K \getsr \keys\mathcal{E}$; \\
      $(\mathcal{M}, s) \gets A^{E_K(\cdot), D_0(\cdot)}
        (\cookie{select})$; \\
      $x_0 \getsr \mathcal{M}$; $x_1 \getsr \mathcal{M}$; \\
      $y \gets E_K(x_1)$; \\
      $(f, \alpha) \gets A^{E_K(\cdot), D_1(\cdot)}
        (\cookie{predict}, y, s)$; \\
      \IF $f(x_b) = \alpha$ \THEN \RETURN $1$; \\
      \ELSE \RETURN $0$;
  \end{program}
  The distribution $\mathcal{M}$ must be \emph{valid}: all strings in
  $\supp\mathcal{M}$ must have the same length.
\end{slide}

\begin{slide}
  \topic{find-then-guess}
  \head{Find-then-guess indistinguishability}
  
  The `find-then-guess' (FTG) game corresponds to the standard public-key
  indistinguishability notion.
  \begin{program}
    Experiment $\Expt{ftg-\id{atk}-$b$}{\mathcal{E}}(A)$: \+ \\
      $K \getsr \keys\mathcal{E}$; \\
      $(x_0, x_1, s) \gets A^{E_K(\cdot), D_0(\cdot)}(\cookie{find})$; \\
      \IF $|x_0| \ne |x_1|$ \THEN \RETURN $0$; \\
      $y \gets E_K(x_b)$; \\
      $b' \gets A^{E_K(\cdot), D_1(\cdot)}(\cookie{guess}, y, s)$; \\
      \RETURN $b'$;
  \end{program}
\end{slide}

\begin{slide}
  \topic{left-or-right}
  \head{Left-or-right indistinguishability}
  
  The `left-or-right' (LOR) notion is a natural extension of find-then-guess.
  Rather than having to guess the hidden bit using a single challenge
  ciphertext, the adversary is allowed to request more as it likes.  It is
  given an encryption oracle which accepts two arguments: it selects either
  the left or the right plaintext, according to the hidden bit, and returns
  the ciphertext.
  \begin{program}
    Experiment $\Expt{lor-\id{atk}-$b$}{\mathcal{E}}(A)$; \+ \\
      $K \getsr \keys\mathcal{E}$; \\
      $b' \gets A^{E_K(\id{lr}_b(\cdot, \cdot)), D_1(\cdot)}$; \\
      \RETURN $b'$; \- \\[\smallskipamount]
    Function $\id{lr}_b(x_0, x_1)$: \+ \\
      \RETURN $x_b$;
  \end{program}
  Note that, because the adversary only runs in one stage, we can only
  consider chosen-plaintext and adaptive chosen-ciphertext attacks.
\end{slide}

\begin{slide}
  \topic{real-or-random}
  \head{Real-or-random indistinguishability}

  The `real-or-random' (ROR) notion is somewhat less natural, but turns out
  to be useful for analysing block cipher encryption modes.

  The adversary is given an oracle which, when given a plaintext $x$, either
  returns an encryption of $x$ or an encryption of a random string with the
  same length as $x$.
  \begin{program}
    Experiment $\Expt{ror-\id{atk}-$0$}{\mathcal{E}}(A)$; \+ \\
      $K \getsr \keys\mathcal{E}$; \\
      $b' \gets A^{E_K(\id{rand}(\cdot)), D_1(\cdot)}$; \\
      \RETURN $b'$; \- \\[\smallskipamount]
    Function $\id{rand}(x)$: \+ \\
      $x' \getsr \{0, 1\}^{|x|}$; \\
      \RETURN $x'$;
  \next
    Experiment $\Expt{ror-\id{atk}-$1$}{\mathcal{E}}(A)$; \+ \\
      $K \getsr \keys\mathcal{E}$; \\
      $b' \gets A^{E_K(\cdot), D_1(\cdot)}$; \\
      \RETURN $b'$;
  \end{program}
  Again, only chosen-plaintext and adaptive chosen-ciphertext attacks are
  applicable.
\end{slide}

\begin{slide}
  \topic{relations between notions}
  \head{Relations between notions \cite{Bellare:2000:CST}}

  \[ \xymatrix @=2cm {
    \txt{LOR} \ar@<0.5ex>[r]^1 \ar@<-0.5ex>[d]_3 &
    \txt{ROR} \ar@<0.5ex>[l]^2 \\
    \txt{FTG} \ar@{-->}@<-0.5ex>[u]_4 \ar@<0.5ex>[r] &
    \txt{SEM} \ar@<0.5ex>[l]
  } \]
  \begin{list}{}{
      \settowidth{\labelwidth}{\textbf{Key}}
      \leftmargin\labelwidth\advance\leftmargin\labelsep
      \itemindent0pt\let\makelabel\textbf}
  \item[Key] \begin{itemize}
    \item A solid arrow $\xy\ar*+{A};<1.5cm, 0cm>*+{B}\endxy$ indicates an
      \emph{security-preserving} reduction: if a scheme is secure in notion
      $A$ then it is as secure in notion $B$, to within a small constant
      factor.
    \item A broken arrow $\xy\ar@{-->}*+{A};<1.5cm, 0cm>*+{B}\endxy$
      indicates a non-security-preserving reduction.
    \item The numbers refer to sections of the proof provided in the notes.
    \end{itemize}
  \end{list}  
\end{slide}

\begin{proof}
  We deal with the propositions one at a time.  Most of them are pretty easy,
  with the exception of the security-losing reduction from FTG to LOR.
  \begin{enumerate}

  \item We show that $\text{LOR-\id{atk}} \implies \text{ROR-\id{atk}}$.
    Suppose $A'$ attacks $\mathcal{E}$ in the real-or-random sense.
    \begin{program}
      Adversary $A^{E(\cdot, \cdot), D(\cdot)}$: \+ \\
        \RETURN $A'^{\id{ror-hack}(\cdot), D(\cdot)}$; \-\\[\smallskipamount]
      Oracle $\id{ror-hack}(x)$: \+ \\
        $x' \getsr \{0, 1\}^{|x|}$; \\
        \RETURN $E(x', x)$;
    \end{program}
    Since this provides a perfect simulation of the ROR game,
    \[ \Adv{lor-\id{atk}}{\mathcal{E}}(A) =
         \Adv{ror-\id{atk}}{\mathcal{E}}(A'), \]%
    and hence
    \[ \InSec{ror-\id{atk}}(\mathcal{E}; t, q_E, q_D) \le
         \InSec{lor-\id{atk}}(\mathcal{E}; t, q_E, q_D). \]%

  \item We show that $\text{ROR-\id{atk}} \implies \text{LOR-\id{atk}}$.
    Suppose $A'$ attacks $\mathcal{E}$ in the left-or-right sense.
    \begin{program}
      Adversary $A^{E(\cdot), D(\cdot)}$: \+ \\
        $\hat{b} \gets \{0, 1\}$; \\
        $b' \gets A'^{\id{lor-hack}(\cdot, \cdot), D(\cdot)}$; \\
        \IF $b' = \hat{b}$ \THEN \RETURN $1$; \\
        \ELSE \RETURN $0$; \- \\[\smallskipamount]
      Oracle $\id{lor-hack}(x_0, x_1)$: \+ \\
        \RETURN $E(x_{\hat{b}})$;
    \end{program}
    If the ROR oracle is returning correct encryptions, then $A'$ will return
    the correct bit $\hat{b}$ with probability
    \[ \frac{\Adv{lor-\id{atk}}{\mathcal{E}}(A')}{2} + \frac{1}{2}; \]
    if the ROR oracle is returning ciphertexts for random plaintexts, then
    $A'$ is being given no information about $\hat{b}$, and hence guesses
    correctly with probability exactly $\frac{1}{2}$.  We conclude that
    \[ \Adv{ror-\id{atk}}{\mathcal{E}}(A) =
         \frac{1}{2}\Adv{lor-\id{atk}}{\mathcal{E}}(A'), \]%
    and hence
    \[ \InSec{lor-\id{atk}}(\mathcal{E}; t, q_E, q_D) \le
         2 \cdot \InSec{ror-\id{atk}}(\mathcal{E}; t, q_E, q_D). \]%

  \item We show that $\text{LOR-\id{atk}} \implies \text{FTG-\id{atk}}$.
    Suppose $A'$ attacks $\mathcal{E}$ in the find-then-guess sense.  We
    assume, without loss of generality, that $A'$ never queries its
    decryption oracle on ciphertexts it obtained from its encryption oracle.
    \begin{program}
      Adversary $A^{E(\cdot, \cdot), D(\cdot)}$: \+ \\
        $(x_0, x_1, s) \gets A'^{\id{encrypt}(\cdot), D(\cdot)}
          (\cookie{find})$; \\
        $y \gets E(x_0, x_1)$; \\
        $b' \gets A'^{\id{encrypt}(\cdot), D(\cdot)}
          (\cookie{guess}, y, s);$ \\
        \RETURN $b'$; \- \\[\smallskipamount]
      Oracle $\id{encrypt}(x)$: \+ \\
        \RETURN $E(x, x)$;
    \end{program}
    Since this provides a perfect simulation of the FTG game,
    \[ \Adv{lor-\id{atk}}{\mathcal{E}}(A) =
         \Adv{ftg-\id{atk}}{\mathcal{E}}(A'), \]%
    and hence
    \[ \InSec{ftg-\id{atk}}(\mathcal{E}; t, q_E, q_D) \le
         \InSec{lor-\id{atk}}(\mathcal{E}; t, q_E + 1, q_D). \]%
    
  \item We show that $\text{FTG-\id{atk}} \implies \text{LOR-\id{atk}}$,
    though with a factor of $q_E$ loss of security.

    This proof is slightly more tricky than the others.  Consider the
    following `hybrid' games, defined for $0 \le i \le q_E$:
    \begin{program}
      Experiment $\Expt{hyb-$i$-\id{atk}-$b$}{\mathcal{E}}$: \+ \\
        $K \getsr \keys\mathcal{E}$; \\
        $j \gets 0$; \\
        $b' \gets A^{E(\id{lr-hack}_b(\cdot, \cdot)), D_1(\cdot)}$; \\
        \RETURN $b'$; \- \\[\smallskipamount]
    \next
      Function $\id{lr-hack}_b(x_0, x_1)$: \+ \\
        \IF $j < i$ \THEN $x \gets x_0$; \\
        \ELSE \IF $j > i$ \THEN $x \gets x_1$; \\
        \ELSE $x \gets x_b$; \\
        $j \gets j + 1$; \\
        \RETURN $E_K(x_b)$;
    \end{program}
    As usual, we define
    \[ \Adv{hyb-$i$-\id{atk}}{\mathcal{E}}(A) =
          \Pr[\Expt{hyb-$i$-\id{atk}-$1$}{\mathcal{E}} = 1] -
          \Pr[\Expt{hyb-$i$-\id{atk}-$0$}{\mathcal{E}} = 1]. \]%

    Observe that we have the identities
    \begin{eqnarray*}[rl]
       \Expt{lor-\id{atk}-$0$}{\mathcal{E}} &\equiv
       \Expt{hyb-$(q_E{-}1)$-\id{atk}-$0$}{\mathcal{E}}
       \\
       \Expt{lor-\id{atk}-$1$}{\mathcal{E}} &\equiv
       \Expt{hyb-$0$-\id{atk}-$1$}{\mathcal{E}}
       \\
    \tabpause{and, for $0 \le i < q_E$,}
       \Expt{hyb-$i$-\id{atk}-$0$}{\mathcal{E}} &\equiv
       \Expt{hyb-$(i{+}1)$-\id{atk}-$1$}{\mathcal{E}}.
    \end{eqnarray*}
    Thus,
    \begin{eqnarray*}[rclclc]
       \Adv{lor-\id{atk}}{\mathcal{E}}(A)
       &=& \Pr[\Expt{lor-\id{atk}-$1$}{\mathcal{E}}(A) = 1] &-&
           \Pr[\Expt{lor-\id{atk}-$0$}{\mathcal{E}}(A) = 1]
       \\*
       &=& \Pr[\Expt{hyb-$0$-\id{atk}-$1$}{\mathcal{E}}(A) = 1] &-&
           \Pr[\Expt{hyb-$(q_E{-}1)$-\id{atk}-$0$}{\mathcal{E}}(A) = 1]
       \\
       &=& \Pr[\Expt{hyb-$0$-\id{atk}-$1$}{\mathcal{E}}(A) = 1] &-&
           \Pr[\Expt{hyb-$0$-\id{atk}-$0$}{\mathcal{E}}(A) = 1] &+ \\*
       & & \Pr[\Expt{hyb-$1$-\id{atk}-$1$}{\mathcal{E}}(A) = 1] &-&
           \Pr[\Expt{hyb-$1$-\id{atk}-$0$}{\mathcal{E}}(A) = 1] &+ \\*
       & & \multicolumn{1}{c}{\smash\vdots} &-&
           \multicolumn{1}{c}{\smash\vdots} &+ \\*
       & & \Pr[\Expt{hyb-$(q_E{-}1)$-\id{atk}-$1$}{\mathcal{E}}(A) = 1] &-&
           \Pr[\Expt{hyb-$(q_E{-}1)$-\id{atk}-$0$}{\mathcal{E}}(A) = 1]
       \\*
       &=& \sum_{0\le i<q_E} \Adv{hyb-$i$-\id{atk}}{\mathcal{E}}(A)
     \end{eqnarray*}
     Now, there must be at least one $i$ for which
     \[ \Adv{hyb-$i$-\id{atk}}{\mathcal{E}}(A) \ge
        \frac{1}{q_E} \Adv{lor-\id{atk}}{\mathcal{E}}(A). \]%
     
     Suppose that $A'$ is an adversary attacking $\mathcal{E}$ in the LOR
     sense.  We can construct an FTG adversary $A$ for which
     \[ \Adv{ftg-\id{atk}}{\mathcal{E}}(A) \ge
        \frac{1}{q_E} \Adv{lor-\id{atk}}{\mathcal{E}}(A') \]%
     as follows:\footnote{%
       The expression of the FTG adversary requires control flow operations
       which aren't easily expressed in the pseudocode language we've used so
       far, hence the cop-out into English.}
     \begin{enumerate}
     \item When invoked in the $\cookie{find}$ stage, run the LOR adversary,
       passing it $A$'s decryption oracle.
     \item Respond to its first $i$ left-or-right queries $(x_0, x_1)$ with
       $E(x_0)$.
     \item On the $(i + 1)$-th left-or-right query, $(x_0, x_1)$, package up
       all of $A'$'s state, and return that, together with the pair $(x_0,
       x_1)$ as the result of $A$'s $\cookie{find}$ stage.
     \item When reinvoked in the $\cookie{guess}$ stage, return the challenge
       ciphertext $y$ as the result of $A'$'s $(i + 1)$-th query.
     \item Respond to the remaining $q_E - i - 1$ left-or-right queries
       $(x_0, x_1)$ with $E(x_1)$.
     \item Return the bit output by $A'$.
     \end{enumerate}
     This evidently simulates the environment of
     $\Expt{hyb-$i$-\id{atk}-$b$}{\mathcal{E}}(A')$; hence $A$ achieves the
     claimed advantage.  Thus,
     \[ \InSec{lor-\id{atk}}(\mathcal{E}; t, q_E, q_D) \le
        q_E \cdot \InSec{ftg-\id{atk}}(\mathcal{E}; t, q_E - 1, q_D). \]%
     
     Now we show that we can't obtain a better reduction.  Suppose that
     $\mathcal{E} = (E, D)$ is $(t, q_E, q_D, \epsilon)$-secure in the FTG
     sense.  We construct a \emph{$p$-leaky} version, $\mathcal{E}' = (E',
     D')$.  Let $\id{maybe}(p)$ denote a function which returns $1$ with
     probability $p$.
     \begin{program}
       Algorithm $E'_K(x)$: \+ \\
         \IF $\id{maybe}(p) = 1$ \THEN \RETURN $1 \cat x$; \\
         \RETURN $0 \cat E_K(x)$;
     \next
       Algorithm $D'_K(y')$: \+ \\
         \PARSE $y'$ \AS $1\colon b, y$; \\
         \IF $b = 1$ \THEN \RETURN $y$; \\
         \RETURN $D_K(y)$;
     \end{program}
     A simple simulation argument shows that this scheme is still secure,
     except for an additional term $p$, handling the case where the challenge
     ciphertext $y^* = 1 \cat x^*$.  It is easy to see that
     \[ \InSec{lor-\id{atk}}(\mathcal{E}'; t, q_E, 0) \ge q_E p, \]
     concluding the proof.
  \end{enumerate}
     
  The proofs that $\text{FTG-\id{atk}} \implies \text{SEM-\id{atk}}$ and
  $\text{SEM-\id{atk}} \implies \text{FTG-\id{atk}}$ are just as in the
  public-key case (page~\pageref{pf:pub-ind-eq-sem}), except for the presence
  of encryption oracles (which are passed on unmolested).  And that's all we
  need.
\end{proof}

\begin{exercise}
  Consider the following `ciphertext-or-random-string' security notion.
  \begin{program}
    Experiment $\Expt{cor-\id{atk}-$0$}{\mathcal{E}}(A)$: \+ \\
      $b' \gets A^{\id{rand}(E_K(\cdot)), D_1(\cdot)}$; \\
      \RETURN $b'$; \- \\[\smallskipamount]
    Function $\id{rand}(x)$: \+ \\
      $x' \getsr \{0, 1\}^{|x|}$; \\
      \RETURN $x'$;
  \next
    Experiment $\Expt{cor-\id{atk}-$1$}{\mathcal{E}}(A)$; \+ \\
      $K \getsr \keys\mathcal{E}$; \\
      $b' \gets A^{E_K(\cdot), D_1(\cdot)}$; \\
      \RETURN $b'$;
  \end{program}
  Relate this notion to the others we've already seen.
  \answer%
  It's not hard to see that $\text{COR} \implies \text{LOR}$; the proof is
  similar to $\text{ROR} \implies \text{LOR}$, and we have
  $\InSec{cor-\id{atk}}(\mathcal{E}; t, q_E, q_D) \le 2\cdot
  \InSec{lor-\id{atk}}(\mathcal{E}; t, q_E, q_D)$.  On the other hand,
  $\text{LOR} \not\implies \text{COR}$.  To see this, let $\mathcal{E} = (E,
  D)$ be an encryption scheme secure in the LOR-\id{atk} sense, and define
  $\mathcal{E}' = (E', D')$ by $E'_K(x) = 0^n \cat E_K(x)$ and $D'_K(y') =
  D_K(y)$ if $y' = 0^n \cat y$ for some $y$, or $\bot$ otherwise.  Because
  the fixed padding is independent of the plaintext,
  $\InSec{lor-\id{atk}}(\mathcal{E}'; t, q_E, q_D) \le
  \InSec{lor-\id{atk}}(\mathcal{E}; t, q_E, q_D)$.  But $\mathcal{E}'$ is not
  COR-CPA secure because an adversary can check for the fixed padding; hence
  $\InSec{cor-cpa}(\mathcal{E}'; t, q_E, q_D) \ge 1 - q_E 2^{-n}$.
\end{exercise}

\begin{exercise}
  Let $F\colon \{0, 1\}^k \times \{0, 1\}^l \to \{0, 1\}^l$ be a PRF, and let
  $g\colon \{0, 1\}^l \to \{0, 1\}^{2l}$ be a length-doubling PRG.  Recall
  from Exercise~\ref{ex:dbl-prg} the construction $g^(i)$, defined by
  \[ g^{(1)}(x) = g(x); \qquad
     g^{(i+1)}(x) = g_0(x) \cat g^{(i)}(g_1(x)). \]%
  We define an encryption scheme $\mathcal{E} = (E, D)$ as follows:
  \begin{program}
    Algorithm $E_K(x)$: \\
      $i \getsr \{0, 1\}^l$; \\
      $n \gets \bigl\lceil \frac{|x|}{L} \bigr\rceil - 1$; \\
      $s \gets F_K(i)$; \\
      $p \gets g^{(n)}(s)$; \\
      $y \gets i \cat (x \xor p)$; \\
      \RETURN $y$;
  \next
    Algorithm $D_K(y)$: \\
      \PARSE $y$ \AS $l\colon i, y'$; \\
      $n \gets \bigl\lceil \frac{|x|}{L} \bigr\rceil - 1$; \\
      $s \gets F_K(i)$; \\
      $p \gets g^{(n)}(s)$; \\
      $x \gets y' \xor p$; \\
      \RETURN $x$;
  \end{program}
  Prove that
  \[ \InSec{lor-cpa}(\mathcal{E}; t, q, \mu) \le
     2 \cdot \InSec{prf}(F; t, q) +
     2 q \mu \cdot \InSec{prg}(g; t) + q(q - 1), \]%
  where $\mu$ is the maximum value of $n$, as computed by $E_K(\cdot)$, for
  any encryption query.
  Hints:
  \begin{parenum}
  \item use a sequence of games, ending with one in which the `ciphertext'
    are random strings of the right length;
  \item attack the PRF first;
  \item use a hybrid argument to attack the PRG, as was used in the proof
    that $\text{FTG} \implies \text{LOR}$.
  \end{parenum}
  \answer%
  For each game~$\G{i}$, $S_i$~is the event that the adversary guesses
  correctly.  Game~$\G0$ is the original attack game (with the hidden bit~$b$
  selected uniformly).  Game~$\G1$ is the same, except that if, for any pair
  of ciphertexts, the $i$-values are equal, the game ends immediately: the
  standard collision bound shows that $|{\Pr[S_1]} - \Pr[S_0]| \le q(q -
  1)/2$.  In game~$\G2$, rather than using $F_K$ to compute the seeds~$s$, we
  just choose $s \in \{0, 1\}^l$ at random each time.  Note that the
  $i$-values are distinct; hence considering an adversary attacking $F$ as a
  PRF, which simulates either $\G1$ or $\G2$ depending on whether its oracle
  is an instance of~$F$ or a random function respectively, shows that
  $|{\Pr[S_2]} - \Pr[S_1]| \le \InSec{prf}(F; t, q)$.
  
  In game~$\G3$, rather than using the PRG~$g^{(n)}$, we generate the strings
  $p$ uniformly at random from $\{0, 1\}^{l(n+1)}$, and claim that
  $|{\Pr[S_3]} - \Pr[S_2]| \le q \mu \cdot \InSec{prg}(g; t)$ (proven below).
  Finally, in game~$\G4$, rather than computing the ciphertext as $i \cat (x
  \xor p)$, we just generate a random string $\{0, 1\}^{l(n+2)}$.  Since $i$
  and $p$ are uniform and random anyway, this doesn't affect the
  distribution; it does show that the result is independent of the
  adversary's ciphertext, however, so $\Pr[S_4] = \Pr[S_3] = \frac{1}{2}$.
  Tying all of this together, $(\Adv{lor-cpa}{\mathcal{E}}(A) + 1)/2 \le
  \frac{1}{2} + \InSec{prf}(F; t, q) + q\mu \cdot \InSec{prg}(g; t) + q(q -
  1)/2$.  Multiplying through by~2 and rearranging yields the required
  result.

  \def\H#1{\G[H]{#1}}%
  We finally turn to the claim made earlier.  In $\G2$, we use the PRG; in
  $\G3$ we don't.  We construct a number of hybrid games~$\H{i}$ for $0 \le i
  \le q$ in which encryption query~$j$ (for $0 \le j < q$) is handled as
  follows: if $0 \le j < i$ then the query is handled as in $\G3$; if $i \le
  j < q$ then the query is handed as in $\G2$.  Let $T_i$ be the event that
  the adversary wins in game $\H{i}$.  Clearly, $\H0 \equiv \G2$, and $\H{q}
  \equiv \G3$.  For each adjacent pair of hybrid games $\H{i}, \H{i+1}$ (for
  $0 \le i < q$), we can bound $|{\Pr[T_{i+1}} - \Pr[T_i]|$ by considering an
  adversary attacking~$g^{(n)}$ by running~$A$ and using its input as the XOR
  mask~$p$ for query~$i$, and following the rules of game~$\H{i}$ for the
  other queries: then if $y$~is random, it simulates $\H{i+1}$, whereas if
  $y$ is the output of $g^{(n)}$ then it simulates $\H{i}$.  Thus
  $|{\Pr[T_{i+1}} - \Pr[T_i]| \le \mu \cdot \InSec{prg}(g; t)$ (by the answer
  to \ref{ex:dbl-prg}), and $|{\Pr[S_3]} - \Pr[S_2]| = |{\Pr[T_{q-1}]} -
  \Pr[T_0]| \le q \mu \cdot \InSec{prg}(g; t)$ as claimed.
\end{exercise}

\xcalways\subsection{Block cipher modes}\x

\begin{slide}
  \head{Block cipher modes}

  Block ciphers (which we model as PRPs) are readily available components,
  and we have good tools for analysing their (heuristic) security.  It'd be
  good if we could use them to construct secure encryption schemes.
  
  We analyse three standard \emph{modes of operation}:
  \begin{description}
  \item[Electronic Code Book (ECB)] Each plaintext block is encrypted
    independently of the others, using the block cipher.
  \item[Counter (CTR)] Choose a random starting point $i$.  The plaintext
    blocks are XORed with the result of encrypting the counter values $i$,
    $i + 1$, \ldots
  \item[Ciphertext Block Chaining (CBC)] The first plaintext block is XORed
    with a random \emph{initialization vector} and encrypted using the block
    cipher; thereafter, each plaintext block are XORed with the previous
    ciphertext block and then encrypted with the block cipher.
  \end{description}
\end{slide}

\begin{slide}
  \head{General notation}
  
  We consider pseudorandom permutations $E\colon \{0, 1\}^k \times \{0, 1\}^l
  \to \{0, 1\}^l$ operating on $l$-bit blocks.  We write $E_K(\cdot)$ rather
  than $E(K, \cdot)$.
  
  For the sake of simplicity, we assume that plaintexts are a multiple of $l$
  bits in length.  We shall consider chosen-plaintext attacks, and we shall
  be quantifying our results in terms of:
  \begin{itemize}
  \item the running time $t$ of adversaries;
  \item the number $q$ of queries made to the encryption oracle; and
  \item the maximum size in bits $\mu$ of any individual encryption query.
  \end{itemize}
  
  We shall write `\FOREACH $l\colon z$ \FROM $x$ \DO \ldots' to denote
  iteration over each $l$-bit block $z$ of $x$ in turn.
  
  We use $\emptystring$ to denote the empty string.
\end{slide}

\begin{slide}
  \topic{ECB}
  \resetseq
  \head{Electronic Code Book (ECB), \seq: description}
  
  We define the scheme $\Xid{\mathcal{E}}{ECB}^E = (\Xid{E}{ECB}^E,
  \Xid{D}{ECB}^E))$ by setting $\keys\Xid{\mathcal{E}}{ECB}^E = \{0, 1\}^k$
  and
  \begin{program}
    Algorithm $\Xid{E}{ECB}^E_K(x)$: \+ \\
      $y \gets \emptystring$; \\
      \FOREACH $l\colon z$ \FROM $x$ \DO \\
      \quad $y \gets y \cat E_K(z)$; \\
      \RETURN $y$;
  \next
    Algorithm $\Xid{D}{ECB}^E_K(y)$: \+ \\
      $x \gets \emptystring$; \\
      \FOREACH $l\colon z$ \FROM $y$ \DO \\
      \quad $x \gets x \cat E_K^{-1}(z)$; \\
      \RETURN $x$;
  \end{program}
\end{slide}

\begin{slide}
  \head{Electronic Code Book (ECB), \seq: analysis}
  
  ECB fails to disguise equality of message blocks.  Hence, it is insecure in
  the left-or-right sense.
  \begin{program}
    Adversary $A^{E(\cdot, \cdot)}$: \+ \\
      $y \gets E(0^l \cat 1^l, 0^l \cat 0^l)$; \\
      \PARSE $y$ \AS $l\colon y_0, l\colon y_1$; \\
      \IF $y_0 = y_1$ \THEN \RETURN $1$; \\
      \ELSE \RETURN $0$;
  \end{program}
  Since $\Xid{\mathcal{E}}{ECB}^E$ always encrypts blocks independently, and
  the block cipher $E$ is deterministic, $A$ always succeeds.  Hence,
  \[ \InSec{lor-cpa}(\Xid{\mathcal{E}}{ECB}^E; t, 1, 2 l) = 1 \]
  for some small $t$ describing the running-time of the adversary $A$.
  
  According to our formal definitions, then, ECB mode is \emph{completely
  insecure}.
\end{slide}

\begin{slide}
  \topic{stateful counter mode}
  \resetseq
  \head{Counter (CTR), \seq: a stateful mode}
  
  We define two schemes.  Firstly, a stateful-sender scheme
  $\Xid{\mathcal{E}}{CTRS}^E = (\Xid{E}{CTRS}^E, \Xid{D}{CTRS}^E))$.  We set
  $\keys\Xid{\mathcal{E}}{ECB}^E = \{0, 1\}^k$, initialize $i \gets 0$, and
  define
  \begin{program}
    Algorithm $\Xid{E}{CTRS}^E_K(x)$: \+ \\
      $y \gets i$; \\
      \FOREACH $l\colon z$ \FROM $x$ \DO \\ \quad \= \+ \kill
        $y \gets y \cat (z \xor E_K(i))$; \\
        $i \gets i + 1$; \- \\
      \RETURN $y$;
  \next
    Algorithm $\Xid{D}{CTRS}^E_K(y)$: \+ \\
      \PARSE $y$ \AS $l\colon i, y$; \\
      $x \gets \emptystring$; \\
      \FOREACH $l\colon z$ \FROM $y$ \DO \\ \quad \= \+ \kill
        $x \gets x \cat (z \xor E_K(i))$; \\
        $i \gets i + 1$; \- \\
      \RETURN $x$;
  \end{program}
\end{slide}

\begin{slide}
  \head{Counter (CTR), \seq: analysis of the stateful version}
  
  We write $q' = q\mu/l$ for the total number of blocks queried by the
  adversary, and we restrict our attention to the case $n \le 2^l$.
  
  Firstly, suppose that, rather than a block cipher, we use a completely
  random function $R \in \Func{l}{l}$.  Then $E(0) \cat E(1) \cat \cdots$ is
  a string of uniformly distributed and independent bits.  Hence
  \[ \InSec{lor-cpa}(\Xid{\mathcal{E}}{CTRS}^{\Func{l}{l}}; t, q, \mu) = 0 \]
  for arbitrary $t$, and for $q \mu/l \le 2^l$.
  
  A simple reduction shows that, for a pseudorandom function $F$, we have
  \[ \InSec{ror-cpa}(\Xid{\mathcal{E}}{CTRS}^F; t, q, \mu) \le
     \InSec{prf}(F; t, q'), \]%
  and hence, for a pseudorandom permutation $E$,
  \[ \InSec{ror-cpa}(\Xid{\mathcal{E}}{CTRS}^E; t, q, \mu) \le
     \InSec{prp}(E; t, q') + \frac{q'(q' - 1)}{2^{l+1}}. \]%
\end{slide}

\begin{exercise}
  Fill in the gaps in the above proof.
  \answer%
  The reduction from the PRF distinguisher to the counter-with-PRF scheme
  works as follows.  Let $A$ attack $\Xid{\mathcal{E}}{CTRS}^F$ in the ROR
  sense; consider adversary $B^{F(\cdot)}$: \{ $b \gets
  A^{\Xid{E}{CTRS}^F(\cdot)}$; \RETURN $b$;~\}.  If $F(\cdot)$ is an instance
  of the PRF then $B$ encrypts messages chosen by $A$ faithfully; if
  $F(\cdot)$ is a random function then the ciphertexts $B$ returns consists
  of a counter followed by a random string, which is therefore distributed
  identically to a ciphertext of a \emph{random} plaintext.  Thus, $B$
  simulates the real-or-random game perfectly.  The result for a PRP follows
  because $\InSec{prf}(F; t, q) \le \InSec{prp}(F; t, q) + q(q - 1)
  2^{-L-1}$.
\end{exercise}

\begin{slide}
  \topic{randomized counter mode}
  \head{Counter (CTR), \seq: a randomized mode}
  
  The randomized scheme $\Xid{\mathcal{E}}{CTR$\$$}^E = (\Xid{E}{CTR$\$$}^E,
  \Xid{D}{CTR$\$$}^E))$ differs from the stateful scheme in the encryption
  algorithm only.  We simply choose the starting value for the counter at
  random, rather than remembering it.
  \begin{program}
    Algorithm $\Xid{E}{CTR$\$$}^E_K(x)$: \+ \\
      $i \getsr \{0, 1\}^l$; \\
      $y \gets i$; \\
      \FOREACH $l\colon z$ \FROM $x$ \DO \\ \quad \= \+ \kill
        $y \gets y \cat (z \xor E_K(i))$; \\
        $i \gets i + 1$; \- \\
      \RETURN $y$;
  \next
    Algorithm $\Xid{D}{CTR$\$$}^E_K(y)$: \+ \\
      \PARSE $y$ \AS $l\colon i, y$; \\
      $x \gets \emptystring$; \\
      \FOREACH $l\colon z$ \FROM $y$ \DO \\ \quad \= \+ \kill
        $x \gets x \cat (z \xor E_K(i))$; \\
        $i \gets i + 1$; \- \\
      \RETURN $x$;
  \end{program}
\end{slide}

\begin{slide}
  \head{Counter (CTR), \seq: analysis of the randomized version}

  The randomized mode remains secure so long as a counter is never repeated.
  This occurs with probability no greater than
  \[ \frac{q\mu(q - 1)}{2^{l+1}}. \]
  Hence, we have, for a pseudorandom function $F$,
  \[ \InSec{ror-cpa}(\Xid{\mathcal{E}}{CTR$\$$}^F; t, q, \mu) \le
     \InSec{prf}(F; t, q') + \frac{q\mu(q - 1)}{2^{l+1}}, \]%
  and, for a pseudorandom permutation $E$,
  \[ \InSec{ror-cpa}(\Xid{\mathcal{E}}{CTR$\$$}^E; t, q, \mu) \le
     \InSec{prp}(E; t, q') + \frac{q'(q' - 1 + l(q - 1))}{2^{l+1}}. \]%
\end{slide}

\begin{proof}[Proof of the collision bound]
  Suppose all of the queries are maximum length.  Then the probability that
  two randomly started counter sequences overlap is $\mu\cdot 2^{-l}$.
  Hence, an upper bound on the collision probability is given by
  \begin{eqnarray*}[rl]
    \Pr[\text{no collision}] &\le \frac{\mu}{2^l}(1 + 2 + \cdots + q - 1) \\
                             &= \frac{\mu}{2^l} \frac{q(q - 1)}{2} \\
                             &= \frac{q\mu(q - 1)}{2^{l+1}}
  \end{eqnarray*}
  as required.
\end{proof}

\begin{slide}
  \topic{CBC}
  \resetseq
  \head{Ciphertext Block Chaining (CBC), \seq: description}

  We define the scheme $\Xid{\mathcal{E}}{CBC}^E = (\Xid{E}{CBC}^E,
  \Xid{D}{CBC}^E))$ by setting $\keys\Xid{\mathcal{E}}{CBC}^E = \{0, 1\}^k$
  and
  \begin{program}
    Algorithm $\Xid{E}{CBC}^E_K(x)$: \+ \\
      $i \getsr \{0, 1\}^l$; \\
      $y \gets i$; \\
      \FOREACH $l\colon z$ \FROM $x$ \DO \\ \quad \= \+ \kill
        $i \gets E_K(z \xor i)$; \\
        $y \gets y \cat i$; \- \\
      \RETURN $y$;
  \next
    Algorithm $\Xid{D}{CBC}^E_K(y)$: \+ \\
      \PARSE $y$ \AS $l\colon i, y$; \\
      $x \gets \emptystring$; \\
      \FOREACH $l\colon z$ \FROM $y$ \DO \\ \quad \= \+ \kill
        $x \gets x \cat (i \xor E_K^{-1}(z))$; \\
        $i \gets z$; \- \\
      \RETURN $x$;
  \end{program}
\end{slide}

\begin{slide}
  \head{Ciphertext Block Chaining (CBC), \seq: analysis}

  As before, we set $q' = q\mu/l$ as the number of blocks queried by an
  adversary attacking the encryption scheme.

  As if by magic,\footnote{%
    The proof of this result is omitted.  The interested reader is directed
    towards \cite{Bellare:2000:CST}.} %
  we have the result
  \[ \InSec{ror-cpa}(\Xid{\mathcal{E}}{CBC}^E; t, q, \mu) \le
     \frac{q'(q' - 1)}{2^l}. \]%
\end{slide}

\begin{slide}
  \topic{requirement for random IVs in CBC mode}
  \head{Ciphertext Block Chaining (CBC), \seq: on randomness of IVs}
  
  The initialization vector used in CBC encryption must be \emph{a priori}
  unpredictable to the adversary.  Suppose that $P(i)$, given an IV for a
  ciphertext, can predict the IV which will be used with the next ciphertext
  with probability $\epsilon$.  Then we construct this adversary, attacking
  $\Xid{\mathcal{E}}{CBC}$ in the ROR-CPA sense:
  \begin{program}
    Adversary $A^{E(\cdot)}$: \+ \\
      $y \gets E(0^l)$; \PARSE $y$ \AS $l\colon i, z$; \\
      $j \gets P(y)$; $y' \gets E(j)$; \PARSE $y'$ \AS $l\colon i', z'$; \\
      \IF $i' = j \land y = y'$ \THEN \RETURN $1$; \\
      \ELSE \RETURN $0$;
  \end{program}
  The adversary succeeds when it guesses the IV correctly, \emph{except} when
  the random encryption oracle happens to choose the same plaintext as we
  wanted to encrypt anyway.  So, therefore,
  \[ \Adv{ror-cpa}{\Xid{\mathcal{E}}{CBC}^E} \ge \epsilon - 2^{-l}. \]
\end{slide}

\xcalways\subsection{Chosen-ciphertext security for symmetric encryption}\x

\begin{exercise}
  Show that CTR and CBC modes are not secure against adaptive
  chosen-ciphertext attacks.
  \answer%
  We use the FTG-CCA2 notion.  For CTR mode: \cookie{find}: \RETURN $(0, 1,
  \bot)$; \cookie{guess}: $y' \gets D(y \xor 0^L1)$; \RETURN $y' \xor 1$;
  For CBC mode: same find stage, $y' \gets D(y \xor 1)$; \RETURN $y' \xor 1$;
\end{exercise}
  
\begin{slide}
  \topic{integrity of ciphertexts}
  \head{Integrity of ciphertexts \cite{Bellare:2000:AER}}

  Informally, we say that an encryption scheme $\mathcal{E} = (E, D)$ has
  \emph{integrity of ciphertexts} (whose confusing short name is INT-CTXT) if
  it's hard for an adversary equipped with an encryption oracle to come with
  a new \emph{valid} ciphertext, i.e., one for which the decryption function
  $D_K$ does not return the symbol $\bot$.

  We shall see later that integrity of ciphertexts \emph{and}
  indistinguishability under chosen-plaintext attacks together imply
  chosen-ciphertext security.  This is intuitively clear, but it's worth
  proving anyway.
\end{slide}

\begin{slide}
  \head{Integrity of ciphertexts (cont.)}
  
  Consider the following game played by an adversary $A$:
  \begin{program}
    Experiment $\Expt{int-ctxt}{\mathcal{E}}(A)$: \+ \\
      $K \getsr \keys\mathcal{E}$; $\Xid{y}{list} \gets \emptyset$;
      $y \gets A^{\id{encrypt}(\cdot), D_K(\cdot)}$; \\
      \IF $y \notin \Xid{y}{list} \land D_K(y) \ne \bot$
      \THEN \RETURN $1$; \\
      \ELSE \RETURN $0$;
  \next
    Oracle $\id{encrypt}(x)$: \+ \\
      $y \gets E_K(x)$; \\
      $\Xid{y}{list} \gets \Xid{y}{list} \cup \{y\}$; \\
      \RETURN $y$;
  \end{program}
  We define $A$'s success probability in this game by
  \[ \Succ{int-ctxt}{\mathcal{E}}(A) =
     \Pr[\Expt{int-ctxt}{\mathcal{E}}(A) = 1] \]%
  and write that
  \[ \InSec{int-ctxt}(\mathcal{E}; t, q_E, q_D) =
     \max_A \Succ{int-ctxt}{\mathcal{E}}(A), \]%
  where the maximum is over all adversaries running in time $t$ and issuing
  $q_E$ encryption and $q_D$ decryption queries.
\end{slide}

\begin{slide}
  \topic{INT-CTXT and LOR-CPA imply LOR-CCA}
  \head{INT-CTXT and LOR-CPA together imply LOR-CCA}
  
  We now prove the claim made earlier.  Suppose that the adversary $A$
  attacks $\mathcal{E}$ in the LOR-CCA sense.  We consider these two
  adversaries, attacking the chosen-plaintext security and ciphertext
  integrity of $\mathcal{E}$ respectively.
  \begin{program}
    Adversary $B^{E(\cdot, \cdot)}$: \+ \\
      $b \gets A^{E(\cdot, \cdot), \Xid{D}{sim}(\cdot)}$; \\
      \RETURN $b$; \- \\[\smallskipamount]
    Oracle $\Xid{D}{sim}(y)$; \+ \\
      \RETURN $\bot$;
  \next
    Adversary $C^{E(\cdot), D(\cdot)}$: \+ \\
      $b \getsr \{0, 1\}$; $y^* \gets \bot$; \\
      $b' \gets A^{E(\id{lr}_b(\cdot, \cdot)), \Xid{D}{sim}(\cdot)}$; \\
      \RETURN $y^*$; \- \\[\smallskipamount]
    Function $\id{lr}_b(x_0, x_1)$: \+ \\
      \RETURN $x_b$; \- \\[\smallskipamount]
    Oracle $\Xid{D}{sim}(y)$: \+ \\
      $x \gets D(y)$; \\
      \IF $x \ne \bot$ \THEN $y^* \gets y$; \\
      \RETURN $x$;
  \end{program}
\end{slide}

\begin{slide}
  \head{INT-CTXT and LOR-CPA together imply LOR-CCA2 (cont.)}
  
  We analyse the advantage of $B$, attacking $\mathcal{E}$ in the LOR-CPA
  sense.  Obviously, $B$ is lying through its teeth in its simulation of
  $A$'s decryption oracle.  If in fact all of $A$'s decryption queries were
  for invalid ciphertexts, $B$ can't notice.  So let $V$ be the event that at
  least one of $A$'s ciphertexts was valid.  Then
  \[ \Adv{lor-cpa}{\mathcal{E}}(A) \ge
       \Adv{lor-cca}{\mathcal{E}}(A) - 2\Pr[V]. \]%
  To bound $\Pr[V]$, we consider adversary $C$, which simply records any of
  $A$'s decryption queries which returns a valid ciphertext.  Since $A$ is
  forbidden from passing any ciphertexts obtained from its encryption oracle
  to its decryption oracle, $C$'s returned ciphertext $y^*$ is not one it
  obtained from \emph{its} encryption oracle.  So
  \[ \Succ{int-ctxt}{\mathcal{E}}(A) = \Pr[V]. \]
  Concluding, then,
  \[ \InSec{lor-cca}(\mathcal{E}; t, q_E, q_D) \le
       \InSec{lor-cpa}(\mathcal{E}; t, q_E) +
       2 \cdot \InSec{int-ctxt}(\mathcal{E}; t, q_E, q_D). \]%
\end{slide}

\begin{slide}
  \topic{strong MACs provide INT-CTXT}
  \head{A strong MAC provides integrity of ciphertexts}

  That's a very nice result, but how do we achieve INT-CTXT?  Well, the
  game in the definition looks very much like the forgery games we played
  when we were thinking about MACs.
  
  Suppose that $\mathcal{E} = (E, D)$ is an encryption scheme secure in the
  LOR-CPA sense, and $\mathcal{M} = (T, V)$ is a strong MAC (in the SUF-CMA
  sense).  Then we can define $\Xid{\mathcal{E}}{auth}^{\mathcal{M}} =
  (\Xid{E}{auth}^{\mathcal{E}, \mathcal{M}}, \Xid{D}{auth}^{\mathcal{E},
    \mathcal{M}})$ by
  \[ \keys\Xid{\mathcal{E}}{auth}^{\mathcal{E}, \mathcal{M}} =
     \keys\mathcal{E} \times \keys\mathcal{M} \]%
  and
  \begin{program}
    Algorithm
    $\Xid{E}{auth}^{\mathcal{E}, \mathcal{M}}_{K_E, K_T}(x)$: \+ \\
      $y \gets E_{K_E}(x)$; \\
      $\tau \gets T_{K_T}(y)$; \\
      \RETURN $\tau \cat y$;
  \next
    Algorithm
    $\Xid{D}{auth}^{\mathcal{E}, \mathcal{M}}_{K_E, K_T}(y')$: \+ \\
      \PARSE $y'$ \AS $\tau, y$; \\
      \IF $V_{K_T}(y, \tau) = 0$ \THEN \RETURN $\bot$; \\
      \ELSE \RETURN $D_{K_E}(y)$;
  \end{program}
\end{slide}

\begin{slide}
  \head{A strong MAC provides integrity of ciphertexts (cont.)}

  The security proof for $\Xid{\mathcal{E}}{auth}^{\mathcal{E}, \mathcal{M}}$
  is left as a trivial exercise.  We end up with the result that
  \[ \InSec{int-ctxt}(\Xid{\mathcal{E}}{auth}^{\mathcal{E}, \mathcal{M}};
                     t, q_E, q_D) \le
    \InSec{suf-cma}(\mathcal{M}; t, q_E, q_D) \]%
  and hence
  \begin{eqnarray*}[Ll]
    \InSec{lor-cca}(\Xid{\mathcal{E}}{auth}^{\mathcal{E}, \mathcal{M}};
                     t, q_E, q_D) \\
    & \le \InSec{lor-cpa}(\mathcal{E}; t, q_E) +
          2 \cdot \InSec{suf-cma}(\mathcal{M}; t, q_E, q_D).
  \end{eqnarray*}
  A MAC, therefore, can help us to attain a strong notion of secrecy, even if
  no actual integrity appears to be required.  This is an important lesson.
\end{slide}

\begin{exercise}
  Prove the above result.
  \answer%
  Let $A$ attack INT-CTXT.  Construct adversary $B^{T(\cdot), V(\cdot)}$: \{
  $K \getsr \keys\mathcal{E}$; $(y, \tau) \gets A^{\id{encrypt}(\cdot),
  \id{decrypt}(\cdot)}$; \RETURN $(y, \tau)$;~\} Oracle $\id{encrypt}(x)$:
  \{ $y \gets E_K(x)$; $\tau \gets T(y)$; \RETURN $(y, \tau)$;~\} Oracle
  $\id{decrypt}(y, \tau)$: \{ \IF $V(y, \tau) = 1$ \THEN \RETURN $D_K(y)$;
  \ELSE \RETURN $\bot$;~\}.  The simulation of the INT-CTXT game is perfect.
\end{exercise}

\begin{slide}
  \topic{mixing encryption and MACs}
  \head{Notes on mixing encryption and MACs}

  To construct $\Xid{\mathcal{E}}{auth}^{\mathcal{E}, \mathcal{M}}$, we
  applied a MAC to the \emph{ciphertext}.  This isn't perhaps the most
  intuitive way to combine an encryption scheme with a MAC.

  There are three constructions which look plausible.
  \begin{description}
  \item[Encrypt-then-MAC:]
    %
    $y \gets E_{K_E}(x)$; $\tau \gets T_{K_T}(y)$; \RETURN $\tau \cat y$;
    \\
    Encrypt the plaintext, and MAC the ciphertext; used in IPsec and nCipher
    Impath; we've proven its generic security, using the notion of integrity
    of ciphertexts.
    %
  \item[MAC-then-encrypt:]
    %
    $\tau \gets T_{K_T}(x)$; $y \gets E_{K_E}(\tau \cat x)$; \RETURN $y$;
    \\
    MAC the plaintext, and encrypt both the plaintext and tag; used in SSL
    and TLS; not \emph{generically} secure against chosen-ciphertext attacks.
    %
  \item[Encrypt-and-MAC:]
    %
    $y \gets E_{K_E}(x)$; $\tau \gets T_{K_T}(x)$; \RETURN $\tau \cat y$;
    \\
    Separately MAC and encrypt the plaintext; used in SSH; \emph{never}
    secure against chosen-ciphertext, not generically secure against
    chosen-plaintext!
  \end{description}
\end{slide}

\begin{proof}
  We begin with a few words on our approach, before we embark on the proof
  proper.
  
  To demonstrate the generic insecurity of a scheme, we assume the existence
  of an encryption scheme and MAC (since if they don't exist, the result is
  vacuously true) and construct modified schemes whose individual security
  relates tightly to the originals, but the combined scheme is weak.
  
  We demonstrate \emph{universal} insecurity by showing an attack which works
  given \emph{any} component encryption and MAC schemes.
  
  We prove security relationships using the LOR-CPA notion because this is
  strongest, and bounds for other notions can be derived readily from the
  left-or-right analysis.  We prove insecurity using the FTG-CCA or FTG-CPA
  notions, because they are weakest and show the strength of our results
  best.
  
  We've dealt with the generic security of encrypt-then-MAC already.  We turn
  our attention first first to the generic insecurity of the MAC-then-encrypt
  scheme.

  Let $\mathcal{E} = (E, D)$ be a symmetric encryption scheme, and let
  $\mathcal{M} = (T, V)$ be a MAC.  We define the MAC-then-encrypt scheme
  $\Xid{\mathcal{E}}{MtE}^{\mathcal{E}, \mathcal{M}} =
  (\Xid{E}{MtE}^{\mathcal{E}, \mathcal{M}}, \Xid{D}{MtE}^{\mathcal{E},
    \mathcal{M}})$ as follows:
  \[ \keys\Xid{\mathcal{E}}{MtE}^{\mathcal{E}, \mathcal{M}} =
     \keys\mathcal{E} \times \keys\mathcal{M} \]%
  and
  \begin{program}
    Algorithm
    $\Xid{E}{MtE}^{\mathcal{E}, \mathcal{M}}_{K_E, K_T}(x)$: \+ \\
      $\tau \gets T_{K_T}(x)$; \\
      $\RETURN E_{K_E}(\tau \cat x)$;
  \next
    Algorithm
    $\Xid{D}{MtE}^{\mathcal{E}, \mathcal{M}}_{K_E, K_T}(y)$: \+ \\
      $x' \gets D_{K_E}(y)$; \\
      \PARSE $x'$ \AS $\tau, x$; \\
      \IF $V_{K_T}(x, \tau) = 0$ \THEN \RETURN $\bot$; \\
      \ELSE \RETURN $x$;
  \end{program}
  We construct a new encryption scheme $\mathcal{E}' = (E', D')$ in terms of
  $\mathcal{E}$, such that the combined scheme
  $\Xid{\mathcal{E}}{MtE}^{\mathcal{E}', \mathcal{M}}$ is insecure in the
  FTG-CCA sense.  Our modified encryption scheme has $\keys\mathcal{E}' =
  \keys\mathcal{E}$, and works as follows:
  \begin{program}
    Algorithm $E'_K(x)$: \+ \\
      \RETURN $0 \cat E_K(x)$;
  \next
    Algorithm $D'_K(y')$: \+ \\
      \PARSE $y'$ \AS $1\colon b, y$; \\
      \RETURN $D_K(y)$;
  \end{program}
  That is, the encryption scheme prepends a single bit to the ciphertext, and
  doesn't check its value during decryption.  Intuitively, this makes the
  scheme malleable: we can change the ciphertext by flipping the first bit,
  but the MAC tag remains valid because the plaintext is unaffected.
  
  Firstly, we prove that $\mathcal{E}'$ is LOR-CPA if $\mathcal{E}$ is.
  Suppose $A'$ attacks $\mathcal{E}'$ in the LOR-CPA sense: then
  \begin{program}
    Adversary $A^{E(\cdot, \cdot)}$: \+ \\
      \RETURN $A'^{0 \cat E(\cdot, \cdot)}$;
  \end{program}
  has the same advantage.
  
  Secondly, we show that the combined MAC-then-encrypt scheme
  $\Xid{\mathcal{E}}{MtE}^{\mathcal{E}', \mathcal{M}}$ is insecure in the
  FTG-CCA sense.  Consider this adversary:
  \begin{program}
    Adversary $B^{E(\cdot), D(\cdot)}(\cookie{find})$: \+ \\
      \RETURN $(0, 1, \bot)$;
  \next
    Adversary $B^{E(\cdot), D(\cdot)}(\cookie{guess}, y', s)$: \+ \\
      \PARSE $y'$ \AS $1\colon b, y$; \\
      \RETURN $D(1 \cat y)$;
  \end{program}
  The ciphertext $1 \cat y$ was never returned by the encryption oracle
  (because it always returns the first bit zero); but the plaintext of $1
  \cat y$ is the challenge plaintext.  Hence, $B$ wins always, and
  \[ \InSec{ftg-cca}(\Xid{\mathcal{E}}{MtE}^{\mathcal{E}', \mathcal{M}};
                     t, 0, 1) = 1, \]%
  where $t$ is the running time of the adversary $B$ above.
  
  We now address the separate encrypt-and-MAC scheme, which we define
  formally.  Let $\mathcal{E} = (E, D)$ be a symmetric encryption scheme, and
  let $\mathcal{M} = (T, V)$ be a MAC.  Then the the encrypt-and-MAC scheme
  $\Xid{\mathcal{E}}{E\&M}^{\mathcal{E}, \mathcal{M}} =
  (\Xid{E}{E\&M}^{\mathcal{E}, \mathcal{M}}, \Xid{D}{E\&M}^{\mathcal{E},
    \mathcal{M}})$ is defined by:
  \[ \keys\Xid{\mathcal{E}}{E\&M}^{\mathcal{E}, \mathcal{M}} =
     \keys\mathcal{E} \times \keys\mathcal{M} \]%
  and
  \begin{program}
    Algorithm
    $\Xid{E}{E\&M}^{\mathcal{E}, \mathcal{M}}_{K_E, K_T}(x)$: \+ \\
      $y \gets E_{K_E}(x)$; \\
      $\tau \gets T_{K_T}(x)$; \\
      $\RETURN \tau \cat y$;
  \next
    Algorithm
    $\Xid{D}{E\&M}^{\mathcal{E}, \mathcal{M}}_{K_E, K_T}(y')$: \+ \\
      \PARSE $y'$ \AS $\tau, y$; \\
      $x \gets D_{K_E}(y)$; \\
      \IF $V_{K_T}(x, \tau) = 0$ \THEN \RETURN $\bot$; \\
      \ELSE \RETURN $x$;
  \end{program}
  
  We first show that this scheme is \emph{universally} insecure against
  chosen-ciphertext attack.  Let $\mathcal{E}$ and $\mathcal{M}$ be an
  arbitrary symmetric encryption scheme and MAC, respectively.  The attack
  works because the MACs can be detached and used in chosen-ciphertext
  queries to test for equality of messages.
  \begin{program}
    Adversary $B^{E(\cdot), D(\cdot)}(\cookie{find})$: \+ \\
      \RETURN $(0, 1, \bot)$;
  \next
    Adversary $B^{E(\cdot), D(\cdot)}$(\cookie{guess}, y', s): \+ \\
      $y_1' \gets E(1)$; \\
      \PARSE $y'$ \AS $\tau, y$; \\
      \PARSE $y_1'$ \AS $\tau_1, y_1$; \\
      \IF $\tau = \tau_1 \lor D(\tau \cat y_1) \ne \bot$
      \THEN \RETURN $1$; \\
      \ELSE \RETURN $0$;
  \end{program}
  After receiving the challenge ciphertext, the adversary requests an
  additional encryption of the plaintext $1$.  If the tags are equal on the
  two ciphertexts then we announce that the hidden bit is $1$.  Otherwise, we
  attempt a decryption of the new ciphertext, using the tag from the
  challenge.  If it decrypts successfully, we announce that the bit is $1$;
  otherwise we claim it is zero.
  
  Certainly, this strategy is always correct when the hidden bit is indeed
  $1$.  However, there is a possibility that the MACs are equal or verify
  correctly even when the hidden bit is $0$.  To bound this probability, we
  construct the following simple adversary against the MAC:
  \begin{program}
    Adversary $B'^{T(\cdot), V(\cdot)}$: \+ \\
      $\tau \gets T(1)$; \\
      \RETURN $(0, \tau)$;
  \end{program}
  We see readily that
  \[ \InSec{ftg-cca}(\Xid{\mathcal{E}}{E\&M}^{\mathcal{E}, \mathcal{M}};
                     t, 1, 1) \ge
     1 - \InSec{suf-cma}(\mathcal{M}; t', 1, 0), \]%
  where $t$ and $t'$ are the running times of adversaries $B$ and $B'$
  respectively.
  
  Finally, we show that the encrypt-and-MAC scheme is generically insecure
  against chosen-plaintext attacks only.  There are two strategies we could
  use.  Since both offer useful insights into the properties of MACs, we
  present both here.
  \begin{itemize}
    
  \item \emph{Deterministic MACs.}  In the proof of the universal weakness of
    the encrypt-and-MAC scheme, we used the check on the MAC to decide on the
    equality of two plaintexts given the ciphertexts.  If the MAC is
    deterministic (e.g., a PRF) then we don't need a decryption query.

    Let $\mathcal{E} = (E, D)$ be a symmetric cipher, and let $\mathcal{M} =
    (T, V)$ be a deterministic MAC, e.g., a PRF, or HMAC.  Then consider this
    adversary:
    \begin{program}
      Adversary $B^{E(\cdot)}(\cookie{find})$: \+ \\
        \RETURN $(0, 1, \bot)$;
    \next
      Adversary $B^{E(\cdot)}(\cookie{guess}, y', s)$: \+ \\
        $y_1' \gets E(1)$; \\
        \PARSE $y'$ \AS $\tau, y$; \\
        \PARSE $y_1'$ \AS $\tau_1, y_1$; \\
        \IF $\tau = \tau_1$ \THEN \RETURN $1$; \\
        \ELSE \RETURN $0$;
    \end{program}
    Since the MAC is deterministic, the tag attached to a ciphertext $1$ is
    always the same.  We bound the probability that $T_K(0) = T_K(1)$ using
    the adversary $B'$ above, and conclude that
    \[ \InSec{ftg-cpa}(\Xid{\mathcal{E}}{E\&M}^{\mathcal{E}, \mathcal{M}};
                       t, 1) \ge
       1 - \InSec{suf-cma}(\mathcal{M}; t', 1, 0), \]%
    where $t$ and $t'$ are the running times of adversaries $B$ and $B'$
    respectively.
      
  \item \emph{Leaky MACs.}  A MAC doesn't have to conceal information about
    messages.  Suppose $\mathcal{M} = (T, V)$ is a secure MAC.  We define the
    leaky MAC $\mathcal{M}' = (T', V')$ by stating that $\keys\mathcal{M}' =
    \keys\mathcal{M}''$ and
    \begin{program}
      Algorithm $T'_K(x)$: \+ \\
        \PARSE $x$ \AS $1\colon x_0, z$; \\
        \RETURN $x_0 \cat T_K(x)$;
    \next
      Algorithm $V'_K(x, \tau')$: \+ \\
        \PARSE $\tau'$ \AS $1\colon \tau_0, \tau$; \\
        \PARSE $x$ \AS $1\colon x_0, z$; \\
        \IF $x_0 \ne \tau_0$ \THEN \RETURN $0$; \\
        \ELSE \RETURN $V_K(x, \tau)$;
    \end{program}
    We must first prove that $\mathcal{M}'$ remains secure.  To do this,
    consider an adversary $A'$ attacking $\mathcal{M}'$.  We construct $A$
    attacking $\mathcal{M}$ in the obvious way:
    \begin{program}
      Algorithm $A^{T(\cdot), V(\cdot)}$: \\
        $(x', \tau') \gets
          A'^{\Xid{T'}{sim}(\cdot), \Xid{V'}{sim}(\cdot)}$; \\
        \PARSE $\tau'$ \AS $1\colon \tau_0, \tau$; \\
        \RETURN $(x, \tau)$;
    \next
      Oracle $\Xid{T'}{sim}(x)$: \+ \\
        \PARSE $x$ \AS $1\colon x_0, z'$; \\
        \RETURN $x_0 \cat T(x)$; \- \\[\smallskipamount]
      Oracle $\Xid{V'}{sim}(x, \tau')$: \+ \\
        \PARSE $\tau'$ \AS $1\colon \tau_0, \tau$; \\
        \PARSE $x$ \AS $1\colon x_0, z$; \\
        \IF $x_0 \ne \tau_0$ \THEN \RETURN $0$; \\
        \ELSE \RETURN $V(x, \tau)$;
    \end{program}
    Here, $A$ simply simulates the environment expected by $A'$.  It is clear
    that $A$ succeeds whenever $A'$ returns a valid tag for a \emph{new}
    message.  However, suppose that $A'$ returns a new tag $\tau'$ for some
    old message $x$, for which the tag $\tau$ was returned by the tagging
    oracle.  Let $x_0$, $\tau_0$ and $\tau'_0$ be the first bits of $x$,
    $\tau$ and $\tau'$ respectively, and let $\tau^*$ be the remaining bits
    of $\tau'$.  If the pair $(x, \tau')$ is to be a valid
    $\mathcal{M}'$-forgery, we must have $x_0 = \tau_0 = \tau'_0$.  Hence,
    $\tau$ and $\tau'$ must differ in at least one other bit, and $(x,
    \tau^*)$ is a valid $\mathcal{M}$-forgery.  We conclude that
    \[ \InSec{suf-cma}(\mathcal{M}'; t, q_T, q_V) \le
       \InSec{suf-cma}(\mathcal{M}; t, q_T, q_V) \]%
    as required.

    Now we show that the combined encrypt-and-MAC scheme is weak in the
    FTG-CPA sense.  Consider this adversary attacking the scheme:
    \begin{program}
      Adversary $B^{E(\cdot), D(\cdot)}(\cookie{find})$: \+ \\
        \RETURN $(0, 1, \bot)$;
    \next
      Adversary $B^{E(\cdot), D(\cdot)}$(\cookie{guess}, y', s): \+ \\
        \PARSE $y'$ \AS $\tau, y$; \\
        \PARSE $\tau$ \AS $1\colon b, \tau^*$; \\
        \RETURN $b$;
    \end{program}
    The leaky MAC simply tells us the right answer.  So
    \[ \InSec{ftg-cpa}(\Xid{\mathcal{E}}{E\&M}^{\mathcal{E}, \mathcal{M}'};
                       t, 0) = 1, \]%
    where $t$ is the running time of adversary $B$ above.

  \end{itemize}

  This concludes the proof.
\end{proof}

%% TO DO: Include stuff about integrity-aware encryption modes some day.

\endinput

%%% Local Variables: 
%%% mode: latex
%%% TeX-master: "ips"
%%% End: