+\section{CBC mode encryption}
+\label{sec:cbc}
+
+Our implementation of the Wrestlers Protocol uses Blowfish
+\cite{Schneier:1994:BEA} in CBC mode. However, rather than pad plaintext
+messages to a block boundary, with the ciphertext expansion that entails, we
+use a technique called \emph{ciphertext stealing}
+\cite[section 9.3]{Schneier:1996:ACP}.
+
+\subsection{Standard CBC mode}
+
+Suppose $E$ is an $\ell$-bit pseudorandom permutation. Normal CBC mode works
+as follows. Given a message $X$, we divide it into blocks $x_0, x_1, \ldots,
+x_{n-1}$. Choose a random \emph{initialization vector} $I \inr \Bin^\ell$.
+Before passing each $x_i$ through $E$, we XOR it with the previous
+ciphertext, with $I$ standing in for the first block:
+\begin{equation}
+ y_0 = E_K(x_0 \xor I) \qquad
+ y_i = E_K(x_i \xor y_{i-1} \ \text{(for $1 \le i < n$)}.
+\end{equation}
+The ciphertext is then the concatenation of $I$ and the $y_i$. Decryption is
+simple:
+\begin{equation}
+ x_0 = E^{-1}_K(y_0) \xor I \qquad
+ x_i = E^{-1}_K(y_i) \xor y_{i-1} \ \text{(for $1 \le i < n$)}
+\end{equation}
+See figure~\ref{fig:cbc} for a diagram of CBC encryption.
+
+\begin{figure}
+ \[ \begin{graph}
+ []!{0; <0.85cm, 0cm>: <0cm, 0.5cm>::}
+ *+=(1, 0)+[F]{\mathstrut x_0}="x"
+ :[dd] *{\xor}="xor"
+ [ll] *+=(1, 0)+[F]{I} :"xor"
+ :[dd] *+[F]{E}="e" :[ddd] *+=(1, 0)+[F]{\mathstrut y_0}="i"
+ "e" [l] {K} :"e"
+ [rrruuuu] *+=(1, 0)+[F]{\mathstrut x_1}="x"
+ :[dd] *{\xor}="xor"
+ "e" [d] :`r [ru] `u "xor" "xor"
+ :[dd] *+[F]{E}="e" :[ddd]
+ *+=(1, 0)+[F]{\mathstrut y_1}="i"
+ "e" [l] {K} :"e"
+ [rrruuuu] *+=(1, 0)+[F--]{\mathstrut x_i}="x"
+ :@{-->}[dd] *{\xor}="xor"
+ "e" [d] :@{-->}`r [ru] `u "xor" "xor"
+ :@{-->}[dd] *+[F]{E}="e" :@{-->}[ddd]
+ *+=(1, 0)+[F--]{\mathstrut y_i}="i"
+ "e" [l] {K} :@{-->}"e"
+ [rrruuuu] *+=(1, 0)+[F]{\mathstrut x_{n-1}}="x"
+ :[dd] *{\xor}="xor"
+ "e" [d] :@{-->}`r [ru] `u "xor" "xor"
+ :[dd] *+[F]{E}="e" :[ddd]
+ *+=(1, 0)+[F]{\mathstrut y_{n-1}}="i"
+ "e" [l] {K} :"e"
+ \end{graph} \]
+
+ \caption{Encryption using CBC mode}
+ \label{fig:cbc}
+\end{figure}
+
+\begin{definition}[CBC mode]
+ \label{def:cbc}
+ Let $P\colon \keys P \times \Bin^\ell to \Bin^\ell$ be a pseudorandom
+ permutation. We define the symmetric encryption scheme
+ $\Xid{\mathcal{E}}{CBC}^P = (\Xid{E}{CBC}^P, \Xid{D}{CBC}^P)$ for messages
+ in $\Bin^{\ell\Z}$ by setting $\keys \Xid{\mathcal{E}}{CBC} = \keys P$ and
+ defining the encryption and decryption algorithms as follows:
+ \begin{program}
+ Algorithm $\Xid{E}{CBC}^P_K(x)$: \+ \\
+ $I \getsr \Bin^\ell$; \\
+ $y \gets I$; \\
+ \FOR $i = 0$ \TO $|x|/\ell$ \DO \\ \ind
+ $x_i \gets x[\ell i \bitsto \ell (i + 1)]$; \\
+ $y_i \gets P_K(x_i \xor I)$; \\
+ $I \gets y_i$; \\
+ $y \gets y \cat y_i$; \- \\
+ \RETURN $y$;
+ \next
+ Algorithm $\Xid{D}{CBC}^P_K(y)$: \+ \\
+ $I \gets y[0 \bitsto \ell]$; \\
+ $x \gets \emptystring$; \\
+ \FOR $1 = 0$ \TO $|y|/\ell$ \DO \\ \ind
+ $y_i \gets y[\ell i \bitsto \ell (i + 1)]$; \\
+ $x_i \gets P^{-1}_K(y_i) \xor I$; \\
+ $I \gets y_i$; \\
+ $x \gets x \cat x_i$; \- \\
+ \RETURN $x$;
+ \end{program}
+\end{definition}
+
+\begin{theorem}[Security of standard CBC mode]
+ \label{thm:cbc}
+ Let $P\colon \keys P \times \Bin^\ell \to \Bin^\ell$ be a pseudorandom
+ permutation. Then,
+ \begin{equation}
+ \InSec{lor-cpa}(\Xid{\mathcal{E}}{CBC}; t, q_E + \mu_E) \le
+ 2 \cdot \InSec{prp}(P; t + q t_P, q) +
+ \frac{q (q - 1)}{2^\ell - 2^{\ell/2}}
+ \end{equation}
+ where $q = \mu_E/\ell$ and $t_P$ is some small constant.
+\end{theorem}
+
+\begin{note}
+ Our security bound is slightly better than that of \cite[theorem
+ 17]{Bellare:2000:CST}. Their theorem statement contains a term $3 \cdot q
+ (q - 1) 2^{-\ell-1}$. Our result lowers the factor from 3 to just over 2.
+ Our proof is also much shorter and considerably more comprehensible.
+\end{note}
+
+The proof of this theorem is given in section~\ref{sec:cbc-proof}
+
+\subsection{Ciphertext stealing}
+
+Ciphertext stealing allows us to encrypt any message in $\Bin^*$ and make the
+ciphertext exactly $\ell$ bits longer than the plaintext. See
+figure~\ref{fig:cbc-steal} for a diagram.
+
+\begin{figure}
+ \[ \begin{graph}
+ []!{0; <0.85cm, 0cm>: <0cm, 0.5cm>::}
+ *+=(1, 0)+[F]{\mathstrut x_0}="x"
+ :[dd] *{\xor}="xor"
+ [ll] *+=(1, 0)+[F]{I} :"xor"
+ :[dd] *+[F]{E}="e" :[ddddd] *+=(1, 0)+[F]{\mathstrut y_0}="i"
+ "e" [l] {K} :"e"
+ [rrruuuu] *+=(1, 0)+[F]{\mathstrut x_1}="x"
+ :[dd] *{\xor}="xor"
+ "e" [d] :`r [ru] `u "xor" "xor"
+ :[dd] *+[F]{E}="e" :[ddddd]
+ *+=(1, 0)+[F]{\mathstrut y_1}="i"
+ "e" [l] {K} :"e"
+ [rrruuuu] *+=(1, 0)+[F--]{\mathstrut x_i}="x"
+ :@{-->}[dd] *{\xor}="xor"
+ "e" [d] :@{-->}`r [ru] `u "xor" "xor"
+ :@{-->}[dd] *+[F]{E}="e" :@{-->}[ddddd]
+ *+=(1, 0)+[F--]{\mathstrut y_i}="i"
+ "e" [l] {K} :@{-->}"e"
+ [rrruuuu] *+=(1, 0)+[F]{\mathstrut x_{n-2}}="x"
+ :[dd] *{\xor}="xor"
+ "e" [d] :@{-->}`r [ru] `u "xor" "xor"
+ :[dd] *+[F]{E}="e"
+ "e" [l] {K} :"e"
+ [rrruuuu] *+=(1, 0)+[F]{\mathstrut x_{n-1} \cat 0^{\ell-t}}="x"
+ :[dd] *{\xor}="xor"
+ "e" [d] :`r [ru] `u "xor" "xor"
+ "e" [dddddrrr] *+=(1, 0)+[F]{\mathstrut y_{n-1}[0 \bitsto t]}="i"
+ "e" [dd] ="x"
+ "i" [uu] ="y"
+ []!{"x"; "e" **{}, "x"+/4pt/ ="p",
+ "x"; "y" **{}, "x"+/4pt/ ="q",
+ "y"; "x" **{}, "y"+/4pt/ ="r",
+ "y"; "i" **{}, "y"+/4pt/ ="s",
+ "e";
+ "p" **\dir{-};
+ "q" **\crv{"x"};
+ "r" **\dir{-};
+ "s" **\crv{"y"};
+ "i" **\dir{-}?>*\dir{>}}
+ "xor" :[dd] *+[F]{E}="e"
+ "e" [l] {K} :"e"
+ "e" [dddddlll] *+=(1, 0)+[F]{\mathstrut y_{n-2}}="i"
+ "e" [dd] ="x"
+ "i" [uu] ="y"
+ []!{"x"; "e" **{}, "x"+/4pt/ ="p",
+ "x"; "y" **{}, "x"+/4pt/ ="q",
+ "y"; "x" **{}, "y"+/4pt/ ="r",
+ "y"; "i" **{}, "y"+/4pt/ ="s",
+ "x"; "y" **{} ?="c" ?(0.5)/-4pt/ ="cx" ?(0.5)/4pt/ ="cy",
+ "e";
+ "p" **\dir{-};
+ "q" **\crv{"x"};
+ "cx" **\dir{-};
+ "c" *[@]\cir<4pt>{d^u};
+ "cy";
+ "r" **\dir{-};
+ "s" **\crv{"y"};
+ "i" **\dir{-}?>*\dir{>}}
+ \end{graph} \]
+
+ \caption{Encryption using CBC mode with ciphertext stealing}
+ \label{fig:cbc-steal}
+\end{figure}
+
+\begin{definition}[CBC stealing]
+ \label{def:cbc-steal}
+ Let $P\colon \keys P \times \Bin^\ell \to \Bin^\ell$ be a pseudorandom
+ permutation. We define the symmetric encryption scheme
+ $\Xid{\mathcal{E}}{CBC-steal}^P = (\Xid{G}{CBC}^P, \Xid{E}{CBC-steal}^P,
+ \Xid{D}{CBC-steal}^P)$ for messages in $\Bin^{\ell\Z}$ by setting $\keys
+ \Xid{\mathcal{E}}{CBC-steal} = \keys P$ and defining the encryption and
+ decryption algorithms as follows:
+ \begin{program}
+ Algorithm $\Xid{E}{CBC-steal}^P_K(x)$: \+ \\
+ $I \getsr \Bin^\ell$; \\
+ $y \gets I$; \\
+ $t = |x| \bmod \ell$; \\
+ \IF $t \ne 0$ \THEN $x \gets x \cat 0^{\ell-t}$; \\
+ \FOR $i = 0$ \TO $|x|/\ell$ \DO \\ \ind
+ $x_i \gets x[\ell i \bitsto \ell (i + 1)]$; \\
+ $y_i \gets P_K(x_i \xor I)$; \\
+ $I \gets y_i$; \\
+ $y \gets y \cat y_i$; \- \\
+ \IF $t \ne 0$ \THEN \\ \ind
+ $b \gets |y| - 2\ell$; \\
+ $y \gets $\=$y[0 \bitsto b] \cat
+ y[b + \ell \bitsto |y|] \cat {}$ \\
+ \>$y[b \bitsto b + t]$; \- \\
+ \RETURN $y$;
+ \next
+ Algorithm $\Xid{D}{CBC-steal}^P_K(y)$: \+ \\
+ $I \gets y[0 \bitsto \ell]$; \\
+ $t = |y| \bmod \ell$; \\
+ \IF $t \ne 0$ \THEN \\ \ind
+ $b \gets |y| - t - \ell$; \\
+ $z \gets P^{-1}_K(y[b \bitsto b + \ell])$; \\
+ $y \gets $\=$y[0 \bitsto b] \cat
+ y[b + \ell \bitsto |y|] \cat {}$ \\
+ \>$z[t \bitsto \ell]$; \- \\
+ $x \gets \emptystring$; \\
+ \FOR $1 = 0$ \TO $|y|/\ell$ \DO \\ \ind
+ $y_i \gets y[\ell i \bitsto \ell (i + 1)]$; \\
+ $x_i \gets P^{-1}_K(y_i) \xor I$; \\
+ $I \gets y_i$; \\
+ $x \gets x \cat x_i$; \- \\
+ \IF $t \ne 0$ \THEN \\ \ind
+ $x \gets x \cat z[0 \bitsto t] \xor y[b \bitsto b + t]$; \- \\
+ \RETURN $x$;
+ \end{program}
+\end{definition}
+
+\begin{theorem}[Security of CBC with ciphertext stealing]
+ \label{thm:cbc-steal}
+ Let $P\colon \keys P \times \Bin^\ell \to \Bin^\ell$ be a pseudorandom
+ permutation. Then
+ \begin{equation}
+ \InSec{lor-cpa}(\Xid{\mathcal{E}}{CBC-steal}; t, q_E, \mu_E) \le
+ 2 \cdot \InSec{prp}(P; t + q t_P, q) +
+ \frac{q (q - 1)}{2^\ell - 2^{\ell/2}}
+ \end{equation}
+ where $q = \mu_E/\ell$ and $t_P$ is some small constant.
+\end{theorem}
+
+\begin{proof}
+ This is an easy reducibility argument. Let $A$ be an adversary attacking
+ $\Xid{\mathcal{E}}{CBC-steal}^P$. We construct an adversary which attacks
+ $\Xid{\mathcal{E}}{CBC}^P$:
+ \begin{program}
+ Adversary $A'^{E(\cdot)}$: \+ \\
+ $b \gets A^{\Xid{E}{steal}(\cdot)}$; \\
+ \RETURN $b$;
+ \- \\[\medskipamount]
+ Oracle $\Xid{E}{steal}(x_0, x_1)$: \+ \\
+ \IF $|x_0| \ne |x_1|$ \THEN \ABORT; \\
+ \RETURN $\id{steal}(|x_0|, E(\id{pad}(x_0), \id{pad}(x_1)))$;
+ \next
+ Function $\id{pad}(x)$: \+ \\
+ $t \gets |x| \bmod \ell$; \\
+ \RETURN $x \cat 0^{\ell-t}$;
+ \- \\[\medskipamount]
+ Function $\id{steal}(l, y)$: \+ \\
+ $t \gets l \bmod \ell$; \\
+ \IF $t \ne 0$ \THEN \\ \ind
+ $b \gets |y| - 2\ell$; \\
+ $y \gets $\=$y[0 \bitsto b] \cat
+ y[b + \ell \bitsto |y|] \cat y[b \bitsto b + t]$; \- \\
+ \RETURN $y$;
+ \end{program}
+ Comparing this to definition~\ref{def:cbc-steal} shows that $A'$ simlates
+ the LOR-CPA game for $\Xid{\mathcal{E}}{CBC-steal}$ perfectly. The theorem
+ follows.
+\end{proof}
+
+\subsection{Proof of theorem~\ref{thm:cbc}}
+\label{sec:cbc-proof}
+
+Consider an adversary $A$ attacking CBC encryption using an ideal random
+permutation $P(\cdot)$. Pick some point in the attack game when we're just
+about to encrypt the $n$th plaintext block. For each $i \in \Nupto{n}$,
+let $x_i$ be the $i$th block of plaintext we've processed; let $y_i$ be the
+corresponding ciphertext; and let $z_i = P^{-1}(y_i)$, i.e., $z_i = x_i \xor
+I$ for the first block of a message, and $z_i = x_i \xor y_{i-1}$ for the
+subsequent blocks.
+
+Say that `something went wrong' if any $z_i = z_j$ for $i \ne j$. This is
+indeed a disaster, because it means that $y_i = y_j$ , so he can detect it,
+and $x_i \xor y_{i-1} = x_j \xor y_{j-1}$, so he can compute an XOR
+difference between two plaintext blocks from the ciphertext and thus
+(possibly) reveal whether he's getting his left or right plaintexts
+encrypted. The alternative, `everything is fine', is much better. If all
+the $z_i$ are distinct, then because $y_i = P(z_i)$, the $y_i$ are all
+generated by $P(\cdot)$ on inputs it's never seen before, so they're all
+random subject to the requirement that they be distinct. If everything is
+fine, then, the adversary has no better way of deciding whether he has a left
+oracle or a right oracle than tossing a coin, and his advantage is therefore
+zero. Thus, we must bound the probability that something went wrong.
+
+Assume that, at our point in the game so far, everything is fine. But we're
+just about to encrypt $x^* = x_n$. There are two cases:
+\begin{itemize}
+\item If $x_n$ is the first block in a new message, we've just invented a new
+ random IV $I \in \Bin^\ell$ which is unknown to $A$, and $z_n = x_n \xor
+ I$. Let $y^* = I$.
+\item If $x_n$ is \emph{not} the first block, then $z_n = x_n \xor y_{n-1}$,
+ but the adversary doesn't yet know $y_{n-1}$, except that because $P$ is a
+ permutation and all the $z_i$ are distinct, $y_{n-1} \ne y_i$ for any $0
+ \le i < n - 1$. Let $y^* = y_{n-1}$.
+\end{itemize}
+Either way, the adversary's choice of $x^*$ is independent of $y^*$. Let
+$z^* = x^* \xor y^*$. We want to know the probability that something goes
+wrong at this point, i.e., that $z^* = z_i$ for some $0 \le i < n$. Let's
+call this event $C_n$. Note first that, in the first case, there are
+$2^\ell$ possible values for $y^*$ and in the second there are $2^\ell - n +
+1$ possibilities for $y^*$. Then
+\begin{eqnarray}[rl]
+ \Pr[C_n]
+ & = \sum_{x \in \Bin^\ell} \Pr[C_n \mid x^* = x] \Pr[x^* = x] \\
+ & = \sum_{x \in \Bin^\ell}
+ \Pr[x^* = x] \sum_{0\le i<n} \Pr[y^* = z_i \xor x] \\
+ & \le \sum_{0\le i<n} \frac{1}{2^\ell - n}
+ \sum_{x \in \Bin^\ell} \Pr[x^* = x] \\
+ & = \frac{n}{2^\ell - n}
+\end{eqnarray}
+
+Having bounded the probability that something went wrong for any particular
+block, we can proceed to bound the probability of something going wrong in
+the course of the entire game. Let's suppose that $q = \mu_E/\ell \le
+2^{\ell/2}$; for if not, $q (q - 1) > 2^\ell$ and the theorem is trivially
+true, since no adversary can achieve advantage greater than one.
+
+Let's give the name $W_i$ to the probability that something went wrong after
+encrypting $i$ blocks. We therefore want to bound $W_q$ from above.
+Armed with the knowledge that $q \le 2^{\ell/2}$, we have
+\begin{eqnarray}[rl]
+ W_q &\le \sum_{0\le i<q} \Pr[C_i]
+ \le \sum_{0\le i<q} \frac{i}{2^\ell - i} \\
+ &\le \frac{1}{2^\ell - 2^{\ell/2}} \sum_{0\le i<q} i \\
+ &= \frac{q (q - 1)}{2 \cdot (2^\ell - 2^{\ell/2})}
+\end{eqnarray}
+Working through the definition of LOR-CPA security, we can see that $A$'s
+(and hence any adversary's) advantage against the ideal system is at most $2
+W_q$.
+
+By using an adversary attacking CBC encryption as a statistical test in an
+attempt to distinguish $P_K(\cdot)$ from a pseudorandom permutation, we see
+that
+\begin{equation}
+ \InSec{prp}(P; t + q t_P, q) \ge
+ \frac{1}{2} \cdot
+ \InSec{lor-cpa}(\Xid{\mathcal{E}}{CBC}; t, q_E, \mu_E) -
+ \frac{q (q - 1)}{2 \cdot (2^\ell - 2^{\ell/2})}
+\end{equation}
+where $t_P$ expresses the overhead of doing the XORs and other care and
+feeding of the CBC adversary; whence
+\begin{equation}
+ \InSec{lor-cpa}(\Xid{\mathcal{E}}{CBC}; t, q_E, \mu_E) \le
+ 2 \cdot \InSec{prp}(P; t, q) + \frac{q (q - 1)}{2^\ell - 2^{\ell/2}}
+\end{equation}
+as required.
+\qed