--- /dev/null
+%%% -*-latex-*-
+%%%
+%%% $Id$
+%%%
+%%% Standard block cipher modes of operation
+%%%
+%%% (c) 2003 Mark Wooding
+%%%
+
+\newif\iffancystyle\fancystylefalse
+\fancystyletrue
+\errorcontextlines=\maxdimen
+\showboxdepth=\maxdimen
+\showboxbreadth=\maxdimen
+
+\iffancystyle
+ \documentclass
+ [a4paper, article, 10pt, numbering, noherefloats, notitlepage]
+ {strayman}
+ \usepackage[T1]{fontenc}
+ \usepackage[palatino, helvetica, courier, maths=cmr]{mdwfonts}
+ \usepackage[within = subsection, mdwmargin]{mdwthm}
+ \usepackage{mdwlist}
+ \usepackage{sverb}
+ \PassOptionsToPackage{dvips}{xy}
+\else
+ \documentclass[a4paper]{llncs}
+ \usepackage{a4wide}
+\fi
+
+\PassOptionsToPackage{show}{slowbox}
+%\PassOptionsToPackage{hide}{slowbox}
+\usepackage{mdwtab, mathenv, mdwmath, crypto}
+\usepackage{slowbox}
+\usepackage{amssymb, amstext}
+\usepackage{url, multicol}
+\DeclareUrlCommand\email{\urlstyle{tt}}
+\ifslowboxshow
+ \usepackage[all]{xy}
+ \turnradius{4pt}
+\fi
+
+\title{New proofs for old modes}
+\iffancystyle
+ \author{Mark Wooding \\ \email{mdw@distorted.org.uk}}
+\else
+ \author{Mark Wooding}
+ \institute{\email{mdw@distorted.org.uk}}
+\fi
+
+\iffancystyle
+ \bibliographystyle{mdwalpha}
+ \let\epsilon\varepsilon
+ \let\emptyset\varnothing
+ \let\le\leqslant\let\leq\le
+ \let\ge\geqslant\let\geq\ge
+ \numberwithin{table}{section}
+ \numberwithin{figure}{section}
+\else
+ \bibliographystyle{plain}
+ \expandafter\let\csname claim*\endcsname\claim
+ \expandafter\let\csname endclaim*\endcsname\endclaim
+\fi
+
+%%\newcommand{\Nupto}[1]{\N_{<{#1}}}
+\newcommand{\Nupto}[1]{\{0, 1, \ldots, #1 - 1\}}
+\let\Bin\Sigma
+\let\emptystring\lambda
+\edef\Pr{\expandafter\noexpand\Pr\nolimits}
+\newcommand{\bitsto}{\mathbin{..}}
+\newcommand{\shift}[1]{\lsl_{#1}}
+\newcommand{\E}{{\mathcal{E}}}
+\newcommand{\M}{{\mathcal{M}}}
+\iffancystyle
+ \def\description{%
+ \basedescript{%
+ \let\makelabel\textit%
+ \desclabelstyle\multilinelabel%
+ \desclabelwidth{1in}%
+ }%
+ }
+\fi
+\def\fixme{\marginpar{FIXME}}
+
+\newslowboxenv{cgraph}{\par$$}{\begin{graph}}{\end{graph}}{$$\par}
+\newslowboxenv{vgraph}
+ {\hfil$\vcenter\bgroup\hbox\bgroup}
+ {\begin{graph}}
+ {\end{graph}}
+ {\egroup\egroup$}
+\newenvironment{vgraphs}{\hbox to\hsize\bgroup}{\hfil\egroup}
+
+\begin{document}
+
+%%%--------------------------------------------------------------------------
+
+\maketitle
+
+\begin{abstract}
+ We study the standard block cipher modes of operation: CBC, CFB, OFB, and
+ CBCMAC and analyse their security. We don't look at ECB other than briefly
+ to note its insecurity, and we have no new results on counter mode. Our
+ results improve over those previously published in that (a) our bounds are
+ better, (b) our proofs are shorter and easier, (c) the proofs correct
+ errors we discovered in previous work, or some combination of these. We
+ provide a new security notion for symmetric encryption which turns out to
+ be rather useful when analysing block cipher modes. Finally, we define a
+ new, condition for initialization vectors, introducing the concept of a
+ `generalized counter', and proving that generalized suffice for security in
+ (full-width) CFB and OFB modes and that generalized counters encrypted
+ using the block cipher (with the same key) suffice for all the encryption
+ modes we study.
+\end{abstract}
+
+\iffancystyle
+\newpage
+\columnsep=2em \columnseprule=0pt
+\tableofcontents[\begin{multicols}{2}\raggedright][\end{multicols}]
+\listoffigures[\begin{multicols}{2}\raggedright][\end{multicols}]
+\listoftables[\begin{multicols}{2}\raggedright][\end{multicols}]
+\newpage
+\fi
+
+%%%--------------------------------------------------------------------------
+
+\section{Introduction}
+\label{sec:intro}
+
+\subsection{Block cipher modes}
+
+Block ciphers -- keyed pseudorandom permutations -- are essential
+cryptographic tools, widely used for bulk data encryption and to an
+increasing extent for message authentication. Because the efficient block
+ciphers we have operate on fixed and relatively small strings of bits -- 64
+or 128 bits at a time, one needs a `mode of operation' to explain how to
+process longer messages.
+
+A collection of encryption modes, named ECB, CBC, CFB and OFB, were defined
+in \cite{FIPS81}. Of these, ECB -- simply divide the message into blocks and
+process them independently with the block cipher -- is just insecure and not
+to be recommended for anything much. We describe the other three, and
+analyse their security using the standard quantitative provable-security
+approach. All three require an `initialization vector' or `IV' which
+diversifies the output making it hard to correlate ciphertexts with
+plaintexts. We investigate which conditions on these IVs suffice for secure
+encryption.
+
+We also examine the CBC-MAC message-authentication scheme, because it's
+intimately related to the CBC encryption scheme and the same techniques we
+used in the analysis of the latter apply to the former.
+
+\subsection{Previous work}
+
+The first quantitative security proof for a block cipher mode is the analysis
+of CBCMAC of \cite{Bellare:1994:SCB}. Security proofs for the encryption
+modes CBC and CTR appeared in \cite{Bellare:2000:CST}, which also defines and
+relates the standard security notions of symmetric encryption. The authors
+of \cite{Alkassar:2001:OSS} offer a proof of CFB mode, though we believe it
+to be flawed in a number of respects.
+
+\subsection{Our contribution}
+
+We introduce a new security notion for symmetric encryption, named
+`result-or-garbage', or `ROG-CPA', which generalizes the `real-or-random'
+notion of \cite{Bellare:2000:CST} and the `random-string' notion of
+\cite{Rogaway:2001:OCB}. Put simply, it states that an encryption scheme is
+secure if an adversary has difficulty distinguishing true ciphertexts from
+strings chosen by an algorithm which is given only the \emph{length} of the
+adversary's plaintext. This turns out to be just the right tool for
+analysing our encryption modes. We relate this notion to the standard
+`left-or-right' notion and, thereby, all the others.
+
+Our bound for CBC mode improves over the `tight' bound proven in
+\cite{Bellare:2000:CST} by almost a factor of two. The difference comes
+because they analyse the construction as if it were built from a PRF and add
+in a `PRP-used-as-a-PRF' correction term: our analysis considers the effect
+of a permutation directly. We prove that CBC mode is still secure if an
+encrypted counter is used in place of a random string as the IV for each
+message. Finally, we show that the `ciphertext stealing' technique is
+secure.
+
+For CFB, we first discuss the work of \cite{Alkassar:2001:OSS}, who offer a
+proof for both CFB mode and an optimized variant which enhances the
+error-recovery properties of standard CFB. We believe that their proof is
+defective in a number of ways. We then offer our own proof. Our bound is a
+factor of two worse than theirs; however, we believe that fixing their proof
+introduces this missing factor of two: that is, that our `poorer' bound
+reflects the true security of CFB mode more accurately. We show that
+full-width CFB is secure if the IV is any `generalized counter', and that
+both full-width and truncated $t$-bit CFB are secure if the IV is an
+encrypted counter. We also show that, unlike CBC mode, it is safe to `carry
+over' the final shift-register value from the previous message as the IV for
+the next message.
+
+OFB mode is in fact a simple modification to CFB mode, and we prove the
+security of OFB by relating it to CFB.
+
+Finally, for CBCMAC, we analyse it using \emph{both} pseudorandom functions
+\emph{and} pseudorandom permutations, showing that, in fact, using a block
+cipher rather than a PRF reduces the security hardly at all. Also, we
+improve on the (groundbreaking) work of \cite{Bellare:1994:SCB} firstly by
+improving the security bound by a factor of almost four, and secondly by
+extending the message space from a space of fixed-length messages to
+\emph{any} prefix-free set of strings.
+
+As a convenient guide, our security bounds are summarized in
+table~\ref{tab:summary}.
+
+\begin{table}
+ \def\lower#1{%
+ \vbox to\baselineskip{\vskip\baselineskip\vskip2pt\hbox{#1}\vss}}
+ \def\none{\multicolumn{1}{c|}{---}}
+ \let\hack=\relax
+ \begin{tabular}[C]
+ {| c | ?>{\hack}c | c | >{\displaystyle} Mc | >{\displaystyle} Mc |}
+ \hlx{hv[4]}
+ \multicolumn{1}{|c|}{\lower{\bfseries Mode}} &
+ \multicolumn{1}{c|}{\lower{\bfseries Section}} &
+ \multicolumn{1}{c|}{\lower{\bfseries Notion}} &
+ \multicolumn{2}{c|}{\bfseries Security with} \\ \hlx{v[4]zc{4-5}v}
+ & & &
+ \multicolumn{1}{c|}{\bfseries $(t, q, \epsilon)$-PRF} &
+ \multicolumn{1}{c|}{\bfseries $(t, q, \epsilon)$-PRP}
+ \\ \hlx{vhvv}
+ CBC & \ref{sec:cbc} & LOR-CPA &
+ \none &
+ 2\epsilon + \frac{q (q - 1)}{2^\ell - q} \\ \hlx{vvhvv}
+ CFB & \ref{sec:cfb} & LOR-CPA &
+ 2 \epsilon + \frac{q (q - 1)}{2^\ell} &
+ 2 \epsilon + \frac{q (q - 1)}{2^{\ell-1}} \\ \hlx{vvhvv}
+ OFB & \ref{sec:ofb} & LOR-CPA &
+ 2 \epsilon + \frac{q (q - 1)}{2^\ell} &
+ 2 \epsilon + \frac{q (q - 1)}{2^{\ell-1}} \\ \hlx{vvhvv}
+ CBCMAC & \ref{sec:cbcmac} & SUF-CMA &
+ \epsilon + \frac{q (q - 1) + 2 q_V}{2^{\ell+1}} &
+ \epsilon +
+ \frac{q (q - 1)}{2 \cdot (2^\ell - q)} +
+ \frac{q_V}{2^\ell - q_T} \\ \hlx{vvh}
+ \end{tabular}
+
+ \caption[Summary of our results]
+ {Summary of our results. In all cases, $q$ is the number of block
+ cipher applications used in the game.}
+ \label{tab:summary}
+\end{table}
+
+\subsection{The rest of the paper}
+
+In section~\ref{sec:prelim} we define the various bits of notation and
+terminology we'll need in the rest of the paper. The formal definitions are
+given for our new `result-or-garbage' security notion, and for our
+generalized counters. In section~\ref{sec:cbc} we study CBC mode, and
+ciphertext stealing. In section~\ref{sec:cfb} we study CFB mode. In
+section~\ref{sec:ofb} we study OFB mode. In section~\ref{sec:cbcmac} we
+study the CBCMAC message authentication scheme.
+
+%%%--------------------------------------------------------------------------
+
+\section{Notation and definitions}
+\label{sec:prelim}
+
+\subsection{Bit strings}
+\label{sec:bitstrings}
+
+Most of our notation for bit strings is standard. The main thing to note is
+that everything is zero-indexed.
+
+\begin{itemize}
+\item We write $\Bin = \{0, 1\}$ for the set of binary digits. Then $\Bin^n$
+ is the set of $n$-bit strings, and $\Bin^*$ is the set of all (finite) bit
+ strings.
+\item If $x$ is a bit string then $|x|$ is the length of $x$. If $x \in
+ \Bin^n$ then $|x| = n$.
+\item If $x, y \in \Bin^n$ are strings of bits of the same length then $x
+ \xor y \in \Bin^n$ is their bitwise XOR.
+\item If $x$ is a bit string and $i$ is an integer satisfying $0 \le i < |x|$
+ then $x[i]$ is the $i$th bit of $x$. If $a$ and $b$ are integers
+ satisfying $0 \le a \le b \le |x|$ then $x[a \bitsto b]$ is the substring
+ of $x$ beginning with bit $a$ and ending just \emph{before} bit $b$. We
+ have $|x[i]| = 1$ and $|x[a \bitsto b]| = b - a$; if $y = x[a \bitsto b]$
+ then $y[i] = x[a + i]$.
+\item If $x$ and $y$ are bit strings then $x y$ is the result of
+ concatenating $y$ to $x$. If $z = x y$ then $|z| = |x| + |y|$; $z[i] =
+ x[i]$ if $0 \le i < |x|$ and $z[i] = y[i - |x|]$ if $|x| \le i < |x| +
+ |y|$. Sometimes, for clarity (e.g., to distinguish from integer
+ multiplication) we write $x \cat y$ instead of $x y$.
+\item The empty string is denoted $\emptystring$. We have $|\emptystring| =
+ 0$, and $x = x \emptystring = \emptystring x$ for all strings $x
+ \in \Bin^*$.
+\item If $x$ is a bit string and $n$ is a natural number then $x^n$ is the
+ result of concatenating $x$ to itself $n$ times. We have $x^0 =
+ \emptystring$ and if $n > 0$ then $x^n = x^{n-1} \cat x = x \cat x^{n-1}$.
+\item If $x$ and $y$ are bit strings, $|x| = \ell$, and $|y| = t$, then we
+ define $x \shift{t} y$ as:
+ \[ x \shift{t} y = (x y)[t \bitsto t + \ell] = \begin{cases}
+ x[t \bitsto \ell] \cat y & if $t < \ell$, or \\
+ y[t - \ell \bitsto t] & if $t \ge \ell$.
+ \end{cases} \]
+ Observe that, if $z = x \shift{t} y$ then $|z| = |x| = \ell$ and
+ \[ z[i] = (x y)[i + t] = \begin{cases}
+ x[i + t] & if $0 \le i < \ell - t$, or \\
+ y[i + t - \ell] & if $\min(0, \ell - t) \le i < \ell$.
+ \end{cases} \]
+ Obviously $x \shift{0} \emptystring = x$, and if $|x| = |y| = t$ then $x
+ \shift{t} y = y$. Finally, if $|y| = t$ and $|z| = t'$ then $(x \shift{t}
+ y) \shift{t'} z = x \shift{t + t'} (y z)$.
+\end{itemize}
+
+\subsection{Other notation}
+\label{sec:miscnotation}
+
+\begin{itemize}
+\iffalse
+\item If $n$ is any natural number, then $\Nupto{n}$ is the set $\{\, i \in
+ \Z \mid 0 \le i < n \,\} = \{ 0, 1, \ldots, n \}$.
+\fi
+\item The symbol $\bot$ (`bottom') is a value different from every bit
+ string.
+\item We write $\Func{l}{L}$ as the set of all functions from $\Bin^l$ to
+ $\Bin^L$, and $\Perm{l}$ as the set of all permutations on $\Bin^l$.
+\end{itemize}
+
+\subsection{Algorithm descriptions}
+\label{sec:algorithms}
+
+An \emph{adversary} is a probabilistic algorithm which attempts (possibly) to
+`break' a cryptographic scheme. We will often provide adversaries with
+oracles which compute values with secret data. The \emph{running time} of an
+adversary conventionally includes the size of the adversary's description:
+this is an attempt to `charge' the adversary for having large precomputed
+tables.
+
+Most of the notation used in the algorithm descriptions should be obvious.
+We briefly note a few features which may be unfamiliar.
+\begin{itemize}
+\item The notation $a \gets x$ denotes the action of assigning the value $x$
+ to the variable $a$.
+\item We write oracles as superscripts, with dots marking where inputs to
+ the oracle go, e.g., $A^{O(\cdot)}$.
+\item The notation $a \getsr X$, where $X$ is a finite set, denotes the
+ action of assigning to $a$ a random value $x \in X$ according to the
+ uniform probability distribution on $X$; i.e., following $a \getsr X$, we
+ have $\Pr[a = x] = 1/|X|$ for any $x \in X$.
+\end{itemize}
+The notation is generally quite sloppy about types and scopes. We don't
+think these informalities cause much confusion, and they greatly simplify the
+presentation of the algorithms.
+
+\subsection{Pseudorandom functions and permutations}
+\label{sec:prfs-and-prps}
+
+Our definitions of pseudorandom functions and permutations are standard. We
+provide them for the sake of completeness.
+
+\begin{definition}[Pseudorandom function family]
+ \label{def:prf}
+ A \emph{pseudorandom function family (PRF)} $F = \{F_K\}_K$ is a collection
+ of functions $F_K\colon \Bin^\ell \to \Bin^L$ indexed by a \emph{key} $K
+ \in \keys F$. If $A$ is any adversary, we define $A$'s \emph{advantage in
+ distinguishing $F$ from a random function} to be
+ \[ \Adv{prf}{F}(A) =
+ \Pr[K \getsr \keys F: A^{F_K(\cdot)} = 1] -
+ \Pr[R \getsr \Func{\ell}{L}: A^{R(\cdot)} = 1]
+ \]
+ where the probability is taken over all choices of keys, random functions,
+ and the internal coin-tosses of $A$. The \emph{insecurity of $F$} is given
+ by
+ \[ \InSec{prf}(F; t, q) = \max_A \Adv{prf}{F}(A) \]
+ where the maximum is taken over all adversaries which run in time~$t$ and
+ issue at most $q$ oracle queries. If $\InSec{prf}(F; t, q) \le \epsilon$
+ then we say that $F$ is a $(t, q, \epsilon)$-PRF.
+\end{definition}
+
+\begin{definition}[Pseudorandom permutation family]
+ \label{def:prp}
+ A \emph{pseudorandom permutation family (PRP)} $E = \{E_K\}_K$ is a
+ collection of permutations $E_K\colon \Bin^\ell \to \Bin^\ell$ indexed by a
+ \emph{key} $K \in \keys E$. If $A$ is any adversary, we define $A$'s
+ \emph{advantage in distinguishing $E$ from a random permutation} to be
+ \[ \Adv{prp}{F}(A) =
+ \Pr[K \getsr \keys E: A^{E_K(\cdot)} = 1] -
+ \Pr[P \getsr \Perm{\ell}: A^{P(\cdot)} = 1]
+ \]
+ where the probability is taken over all choices of keys, random
+ permutations, and the internal coin-tosses of $A$. Note that the adversary
+ is not allowed to query the inverse permutation $E^{-1}_K(\cdot)$ or
+ $P^{-1}(\cdot)$. The \emph{insecurity of $E$} is given by
+ \[ \InSec{prp}(E; t, q) = \max_A \Adv{prf}{E}(A) \]
+ where the maximum is taken over all adversaries which run in time~$t$ and
+ issue at most $q$ oracle queries. If $\InSec{prp}(E; t, q) \le \epsilon$
+ then we say that $E$ is a $(t, q, \epsilon)$-PRP.
+\end{definition}
+
+The following result is standard; we shall require it for the security proofs
+of CFB and OFB modes. The proof is given as an introduction to our general
+approach.
+
+\begin{proposition}
+ \label{prop:prps-are-prfs}
+ Suppose $E$ is a PRP over $\Bin^\ell$. Then
+ \[ \InSec{prf}(E; t, q)
+ \le \InSec{prp}(E; t, q) + \frac{q (q - 1)}{2^{\ell+1}}.
+ \]
+\end{proposition}
+\begin{proof}
+ We claim
+ \[ \InSec{prf}(\Perm{\ell}; t, q) \le \frac{q (q - 1)}{2^{\ell+1}}, \]
+ i.e., that a \emph{perfect} $\ell$-bit random permutation is a PRF with the
+ stated bounds. The proposition follows immediately from this claim and the
+ definition of a PRP.
+
+ We now prove the claim. Consider any adversary~$A$. Let $x_i$ be $A$'s
+ queries, and let $y_i$ be the responses, for $0 \le i < q$. Assume,
+ without loss of generality, that the $x_i$ are distinct. Let $C_n$ be the
+ event in the random-function game $\Expt{prf-$0$}{\Perm{\ell}}(A)$ that
+ $y_i = y_j$ for some $i$ and $j$ where $0 \le i < j < n$. Then
+ \begin{equation}
+ \Pr[C_n] \le \sum_{0\le i<n} \frac{i}{2^\ell}
+ = \frac{n (n - 1)}{2^{\ell+1}}.
+ \end{equation}
+ It's clear that the two games proceed identically if $C_q$ doesn't occur in
+ the random-function game. The claim follows.
+\end{proof}
+
+\subsection{Symmetric encryption}
+\label{sec:sym-enc}
+
+We begin with a purely syntactic description of a symmetric encryption
+scheme, and then define our two notions of security.
+
+\begin{definition}[Symmetric encryption]
+ \label{def:symm-enc}
+ A \emph{symmetric encryption scheme} is a triple of algorithms $\E = (G, E,
+ D)$, with three (implicitly) associated sets: a keyspace, a plaintext
+ space, and a ciphertext space.
+ \begin{itemize}
+ \item $G$ is a probabilistic \emph{key-generation algorithm}. It is
+ invoked with no arguments, and returns a key $K$ which can be used with
+ the other two algorithms. We write $K \gets G()$.
+ \item $E$ is a probabilistic \emph{encryption algorithm}. It is invoked
+ with a key $K$ and a \emph{plaintext} $x$ in the plaintext space, and it
+ returns a \emph{ciphertext} $y$ in the ciphertext space. We write $y
+ \gets E_K(x)$.
+ \item $D$ is a deterministic \emph{decryption algorithm}. It is invoked
+ with a key $K$ and a ciphertext $y$, and it returns either a plaintext
+ $x$ or the distinguished symbol $\bot$. We write $x \gets D_K(y)$.
+ \end{itemize}
+ For correctness, we require that whenever $y$ is a possible result of
+ computing $E_K(x)$, then $x = D_K(y)$.
+\end{definition}
+
+Our primary notion of security is \emph{left-or-right indistinguishability
+under chosen-plaintext attack} (LOR-CPA), since it offers the best reductions
+to the other common notions. (We can't acheive security against chosen
+ciphertext attack using any of our modes, so we don't even try.) See
+\cite{Bellare:2000:CST} for a complete discussion of LOR-CPA, and how it
+relates to other security notions for symmetric encryption.
+
+\begin{definition}[Left-or-right indistinguishability]
+ \label{def:lor-cpa}
+ Let $\E = (G, E, D)$ be a symmetric encryption scheme. Define the function
+ $\id{lr}(b, x_0, x_1) = x_b$. Then for any adversary $A$, we define $A$'s
+ \emph{advantage against the LOR-CPA security of $\E$} as
+ \[ \Adv{lor-cpa}{\E}(A) =
+ \Pr[K \gets G(): A^{E_K(\id{lr}(1, \cdot, \cdot))} = 1] -
+ \Pr[K \gets G(): A^{E_K(\id{lr}(0, \cdot, \cdot))} = 1].
+ \]
+ We define the \emph{LOR-CPA insecurity of $\E$} to be
+ \[ \InSec{lor-cpa}(\E; t, q_E, \mu_E) =
+ \max_A \Adv{lor-cpa}{\E}(A)
+ \]
+ where the maximum is taken over all adversaries which run in time~$t$ and
+ issue at most $q_E$ encryption queries totalling at most $\mu_E$ bits. If
+ $\InSec{lor-cpa}(\E; t, q_E, \mu_E) \le \epsilon$ then we say that $\E$ is
+ $(t, q_E, \mu_E, \epsilon)$-LOR-CPA.
+\end{definition}
+
+Our second notion is named \emph{result-or-garbage} and abbreviated ROG-CPA.
+It is related to the notion used by \cite{Rogaway:2001:OCB}, though different
+in important ways: for example, there are reductions both ways between
+ROG-CPA and LOR-CPA (and hence the other standard notions of security for
+symmetric encryption), whereas the notion of \cite{Rogaway:2001:OCB} is
+strictly stronger than LOR-CPA. Our idea is that an encryption scheme is
+secure if ciphertexts of given plaintexts -- \emph{results} -- hard to
+distinguish from strings constructed independently of any plaintexts --
+\emph{garbage}. We formalize this notion in terms of a
+\emph{garbage-emission algorithm} $W$ which is given only the length of the
+plaintext. The algorithm $W$ will usually be probabilistic, and may maintain
+state. Unlike \cite{Rogaway:2001:OCB}, we don't require that $W$'s output
+`look random' in any way, just that it be chosen independently of the
+adversary's plaintext selection.
+
+\begin{definition}[Result-or-garbage indistinguishability]
+ \label{def:rog-cpa}
+ Let $\E = (G, E, D)$ be a symmetric encryption scheme, and let $W$ be a
+ possibly-stateful, possibly-probabilistic \emph{garbage-emission}
+ algorithm. Then for any adversary $A$, we define $A$'s \emph{advantage
+ against the ROG-CPA-$W$ security of $\E$} as
+ \[ \Adv{rog-cpa-$W$}{\E}(A) =
+ \Pr[K \gets G(): A^{E_K(\cdot)} = 1] - \Pr[A^{W(|\cdot|)} = 1]. \]
+ We define the \emph{ROG-CPA insecurity of $\E$} to be
+ \[ \InSec{lor-cpa}(\E; t, q_E, \mu_E) =
+ \max_A \Adv{lor-cpa}{\E}(A) \]
+ where the maximum is taken over all adversaries which run in time~$t$ and
+ issue at most $q_E$ encryption queries totalling at most $\mu_E$ bits. If
+ $\InSec{rog-cpa-$W$}(\E; t, q_E, \mu_E) \le \epsilon$ for some $W$ then we
+ say that $\E$ is $(t, q_E, \mu_E, \epsilon)$-ROG-CPA.
+\end{definition}
+
+The following proposition relates our new notion to the existing known
+notions of security.
+
+\begin{proposition}[ROG $\Leftrightarrow$ LOR]
+ \label{prop:rog-and-lor}
+ Let $\E$ be a symmetric encryption scheme. Then,
+ \begin{enumerate}
+ \item for all garbage-emission algorithms $W$,
+ \[ \InSec{lor-cpa}(\E; t, q_E, \mu_E)
+ \le 2 \cdot
+ \InSec{rog-cpa-$W$}(\E; t + t_E \mu_E, q_E, \mu_E)
+ \]
+ and
+ \item there exists a garbage-emission algorithm $W$ for which
+ \[ \InSec{rog-cpa-$W$}(\E; t, q_E, \mu_E)
+ \le \InSec{lor-cpa}(\E; t + t_E \mu_E, q_E, \mu_E)
+ \]
+ \end{enumerate}
+ for some fairly small constant $t_E$.
+\end{proposition}
+\begin{proof}
+ \begin{enumerate}
+ \item Let $W$ and $\E$ be given, and let $A$ be an adversary attacking the
+ LOR-CPA security of $\E$. Consider adversary $B$ attacking $\E$'s
+ ROG-CPA-$W$ security.
+ \begin{program}
+ Adversary $B^E(\cdot)$: \+ \\
+ $b^* \getsr \Bin$; \\
+ $b \gets A^{E(\id{lr}(b^*, \cdot, \cdot))}$; \\
+ \IF $b = b^*$ \THEN \RETURN $1$ \ELSE \RETURN $0$;
+ \next
+ Function $\id{lr}(b, x_0, x_1)$: \+ \\
+ \IF $b = 0$ \THEN \RETURN $x_0$ \ELSE \RETURN $x_1$;
+ \end{program}
+ If $E(\cdot)$ is the `result' encryption oracle, then $B$ simulates the
+ left-or-right game for the benefit of $A$, and therefore returns $1$ with
+ probability $(\Adv{lor-cpa}{\E}(A) + 1)/2$. On the other hand, if
+ $E(\cdot)$ returns `garbage' then the oracle responses are entirely
+ independent of $b^*$. This follows because $A$ is constrained to query
+ only on pairs of plaintexts with equal lengths, and the responses are
+ dependent only on these (common) lengths and any internal state and coin
+ tosses of $W$. So $b$ is independent of $b^*$ and $\Pr[b = b^*] =
+ \frac{1}{2}$. The result follows.
+ \item Let $\E = (G, E, D)$ be given. Our garbage emitter simulates the
+ real-or-random game of \cite{Bellare:2000:CST}. Let $K_W = \bot$
+ initially: we define our emitter $W$ thus:
+ \begin{program}
+ Garbage emitter $W(n)$: \+ \\
+ \IF $K_W = \bot$ \THEN $K_W \gets G()$; \\
+ $x \getsr \Bin^n$; \\
+ \RETURN $E_K(x)$;
+ \end{program}
+ We now show that $\InSec{rog-cpa-$W$}(\E; t, q_E, \mu_E) \le
+ \InSec{lor-cpa}(\E; t + t_E \mu_E, q_E, \mu_E)$ for our $W$. Let $A$ be
+ an adversary attacking the ROG-CPA-$W$ security of $\E$. Consider
+ adversary $B$ attacking $\E$'s LOR-CPA security:
+ \begin{program}
+ Adversary $B^{E(\cdot, \cdot)}$: \+ \\
+ $b \gets A^{\id{lorify}(\cdot)}$; \\
+ \RETURN $b$;
+ \next
+ Function $\id{lorify}(x)$: \+ \\
+ $x' \getsr \Bin^{|x|}$; \\
+ \RETURN $E(x', x)$;
+ \end{program}
+ The adversary simulates the ROG-CPA-$W$ games perfectly for our chosen
+ $W$, since the game has chosen the random $K_W$ for us already: the
+ `left' game returns only the results of encrypting random `garbage'
+ plaintexts $x'$, while the right game returns correct results of
+ encrypting the given plaintexts $x$. The result follows.
+ \qed
+ \end{enumerate}
+\end{proof}
+
+
+
+\subsection{Message authentication}
+\label{sec:mac}
+
+Our definitions for message authentication are standard; little needs to be
+said of them. As with symmetric encryption, we begin with a syntactic
+definition, and then describe our notion of security.
+
+\begin{definition}[Message authentication code]
+ \label{def:mac}
+ A \emph{message authentication code (MAC)} is a triple of algorithms $\M =
+ (G, T, V)$ with three (implicitly) associated sets: a keyspace, a message
+ space, and a tag space.
+ \begin{itemize}
+ \item $G$ is a probabilistic \emph{key-generation algorithm}. It is
+ invoked with no arguments, and returns a key $K$ which can be used with
+ the other two algorithms. We write $K \gets G()$.
+ \item $T$ is a probabilistic \emph{tagging algorithm}. It is invoked with
+ a key $K$ and a \emph{message} $x$ in the message space, and it returns a
+ \emph{tag} $\tau$ in the tag space. We write $\tau \gets T_K(x)$.
+ \item $V$ is a deterministic \emph{verification algorithm}. It is invoked
+ with a key $K$, a message $x$ and a tag $\tau$, and returns a bit $b \in
+ \Bin$. We write $b \gets V_K(x, \tau)$.
+ \end{itemize}
+ For correctness, we require that whenever $\tau$ is a possible result of
+ computing $T_K(x)$, then $V_K(x, \tau) = 1$.
+\end{definition}
+
+Our notion of security is the strong unforgeability of
+\cite{Abdalla:2001:DHIES,Bellare:2000:AER}.
+
+\begin{definition}[Strong unforgeability]
+ Let $\M = (G, T, V)$ be a message authentication code, and let $A$
+ be an adversary. We perform the following experiment.
+ \begin{program}
+ Experiment $\Expt{suf-cma}{\M}(A)$: \+ \\
+ $K \gets G()$; \\
+ $\Xid{T}{list} \gets \emptyset$; \\
+ $\id{good} \gets 0$; \\
+ $A^{\id{tag}(\cdot), \id{verify}(\cdot, \cdot)}$; \\
+ \RETURN $\id{good}$;
+ \newline
+ Oracle $\id{tag}(x)$: \+ \\
+ $\tau \gets T_K(x)$; \\
+ $\Xid{T}{list} \gets \Xid{T}{list} \cup \{(x, \tau)\}$; \\
+ \RETURN $\tau$;
+ \next
+ Oracle $\id{verify}(x, \tau)$: \+ \\
+ $b \gets V_K(x, \tau)$; \\
+ \IF $b = 1 \land (x, \tau) \notin \Xid{T}{list}$ \THEN
+ $\id{good} \gets 1$; \\
+ \RETURN $b$;
+ \end{program}
+ That is, the adversary `wins' if it submits a query to its verification
+ oracle which is \emph{new} -- doesn't match any message/tag pair from the
+ tagging oracle -- and \emph{valid} -- the verification oracle returned
+ success. We define the adversary's \emph{success probability} as
+ \[ \Succ{suf-cma}{\M}(A) =
+ \Pr[\Expt{suf-cma}{\M}(A) = 1]. \]
+ We define the \emph{SUF-CMA insecurity of $\M$} to be
+ \[ \InSec{suf-cma}(\M; t, q_T, \mu_T, q_V, \mu_V) =
+ \max_A \Adv{suf-cma}{\M}(A) \]
+ where the maximum is taken over all adversaries which run in time~$t$,
+ issue at most $q_T$ tagging queries totalling at most $\mu_T$ bits, and
+ issue at most $q_V$ verification queries totalling at most $\mu_V$ bits.
+ If $\InSec{suf-cma}(\M; t, q_T, \mu_T, q_V, \mu_V) \le \epsilon$
+ then we say that $\E$ is $(t, q_T, \mu_T, q_V, \mu_V)$-SUF-CMA.
+\end{definition}
+
+\subsection{Initialization vectors and encryption modes}
+\label{sec:iv}
+
+In order to reduce the number of definitions in this paper to a tractable
+level, we will describe the basic modes independently of how initialization
+vectors (IVs) are chosen, and then construct the actual encryption schemes by
+applying various IV selection methods from the modes.
+
+We consider the following IV selection methods.
+\begin{description}
+\item[Random selection] An IV is chosen uniformly at random just before
+ encrypting each message.
+\item[Counter] The IV for each message is a \emph{generalized counter} (see
+ discussion below, and definition~\ref{def:genctr}).
+\item[Encrypted counter] The IV for a message is the result of applying the
+ block cipher to a generalized counter, using the same key as for message
+ encryption.
+\item[Carry-over] The IV for the first message is fixed; the IV for
+ subsequent messages is some function of the previous plaintexts or
+ ciphertexts (e.g., the last ciphertext block of the previous message).
+\end{description}
+Not all of these methods are secure for all of the modes we consider.
+
+\begin{definition}[Generalized counters]
+ \label{def:genctr}
+ If $S$ is a finite set, then a \emph{generalized counter in $S$} is an
+ bijection $c\colon \Nupto{|S|} \leftrightarrow S$. For brevity, we shall
+ refer simply to `counters', leaving implicit the generalization.
+\end{definition}
+
+\begin{remark}[Examples of generalized counters] \leavevmode
+ \begin{itemize}
+ \item There is a `natural' binary representation of the natural numbers
+ $\Nupto{2^\ell}$ as $\ell$-bit strings: for any $n \in \Nupto{2^\ell}$,
+ let $R(n)$ be the unique $r \in \Bin^\ell$ such that $\smash{n =
+ \sum_{0\le i<\ell} 2^i r[i]}$. Then $R(\cdot)$ is a generalized counter
+ in $\Bin^\ell$.
+ \item We can represent elements of the finite field $\gf{2^\ell}$ as
+ $\ell$-bit strings. Let $p(x) \in \gf{2}[x]$ be a primitive polynomial
+ of degree $\ell$; then represent $\gf{2^\ell}$ by $\gf{2}[x]/(p(x))$.
+ Now for any $a \in \gf{2^\ell}$, let $R(a)$ be the unique $r \in
+ \Bin^\ell$ such that $\smash{a = \sum_{0\le i<\ell} x^i r[i]}$. Because
+ $p(x)$ is primitive, $x$ generates the multiplicative group
+ $\gf{2^\ell}^{\,*}$, so define $c(n) = R(x^n)$ for $0 \le n < 2^\ell - 1$
+ and $c(2^{\ell - 1}) = 0^\ell$; then $c(\cdot)$ is a generalized counter
+ in $\Bin^\ell$. This counter can be implemented efficiently in hardware
+ using a linear feedback shift register.
+ \end{itemize}
+\end{remark}
+
+\begin{definition}[Encryption modes]
+ \label{def:enc-modes}
+
+ A \emph{block cipher encryption mode} $m_P = (\id{encrypt}, \id{decrypt})$
+ is a pair of deterministic oracle algorithms (and implicitly-defined
+ plaintext and ciphertext spaces) which satisfy the following conditions:
+ \begin{enumerate}
+ \item The algorithm $\id{encrypt}$ runs with oracle access to a permutation
+ $P\colon \Bin^\ell \leftrightarrow \Bin^\ell$; on input a plaintext $x$
+ and an initialization vector $v \in \Bin^\ell$, it returns a ciphertext
+ $y$ and a \emph{chaining value} $v' \in \Bin^\ell$. We write $(v', y) =
+ \id{encrypt}^{P(\cdot)}(v, x)$.
+ \item The algorithm $\id{decrypt}$ runs with oracle access to a permutation
+ $P\colon \Bin^\ell \leftrightarrow \Bin^\ell$ and its inverse
+ $P^{-1}(\cdot)$; on input a ciphertext $y$ and an initialization vector
+ $v \in \Bin^\ell$, it returns a plaintext $x$. We write that $x =
+ \id{decrypt}^{P(\cdot), P^{-1}(\cdot)}(v, y)$.
+ \item For all permutations $P\colon \Bin^\ell \leftrightarrow \Bin^\ell$,
+ all plaintexts $x$ and all initialization vectors $v$, if $(v', y) =
+ \id{encrypt}^{P(\cdot)}(v, x)$ then $x = \id{decrypt}^{P(\cdot),
+ P^{-1}(\cdot)}(v, y)$.
+ \item There exists an efficient algorithm which, given a ciphertext $y$ and
+ the initialization vector but \emph{not} access to $P$, computes the
+ chaining value $v'$ such that $(v', y) = \id{encrypt}^P(v, x)$.
+ \end{enumerate}
+ Similarly, a \emph{PRF encryption mode} $m_F = (\id{encrypt},
+ \id{decrypt})$ is a pair of deterministic oracle algorithms (and
+ implicitly-defined plaintext and ciphertext spaces) which satisfy the
+ following conditions:
+ \begin{enumerate}
+ \item The algorithm $\id{encrypt}$ runs with oracle access to a function
+ $F\colon \Bin^\ell \to \Bin^L$; on input a plaintext $x$ and an
+ initialization vector $v \in \Bin^\ell$, it returns a ciphertext $y$ and
+ a \emph{chaining value} $v' \in \Bin^\ell$. We write $(v', y) =
+ \id{encrypt}^{F(\cdot)}(v, x)$.
+ \item The algorithm $\id{decrypt}$ runs with oracle access to a function
+ $F\colon \Bin^\ell \to \Bin^L$; on input a ciphertext $y$ and an
+ initialization vector $v \in \Bin^\ell$, it returns a plaintext $x$. We
+ write that $(v', x) = \id{decrypt}^{F(\cdot)}(v, y)$.
+ \item For all functions $F\colon \Bin^\ell \to \Bin^L$, all plaintexts $x$
+ and all initialization vectors $v$, if $(v', y) =
+ \id{encrypt}^{F(\cdot)}(v, x)$ then $x = \id{decrypt}^{F(\cdot)}(v, y)$.
+ \item There exists an efficient algorithm which, given a ciphertext $y$ and
+ the initialization vector but \emph{not} access to $F$, computes the
+ chaining value $v'$ such that $(v', y) = \id{encrypt}^F(v, x)$.
+ \qed
+ \end{enumerate}
+\end{definition}
+
+\begin{definition}[Symmetric encryption schemes from modes]
+ \label{def:enc-scheme}
+ Let $F$ be a pseudorandom permutation on $\Bin^\ell$ (resp.\ a
+ pseudorandom function from $\Bin^\ell$ to $\Bin^L$); let $m =
+ (\id{encrypt}, \id{decrypt})$ be a block cipher (resp.\ PRF) encryption
+ mode. (To save on repetition, if $F$ is a PRF then define $F_K^{-1}(x) =
+ \bot$ for all keys $K$ and inputs $x$.) We define the following symmetric
+ encryption schemes according to how IVs are selected.
+
+ \begin{itemize}
+ \def\Enc{\Xid{\E}{$m$\what}^{\super}}
+ \def\GG{\Xid{G}{$m$\what}^{\super}}
+ \def\EE{\Xid{E}{$m$\what}^{\super}}
+ \def\DD{\Xid{D}{$m$\what}^{\super}}
+
+ \def\what{$\$$}
+ \def\super{F}
+ \item Randomized selection: define $\Enc = (\GG, \EE, \DD)$, where
+ \begin{program}
+ Algorithm $\GG()$: \+ \\
+ $K \getsr \keys F$; \\
+ \RETURN $K$;
+ \next
+ Algorithm $\EE(K, x)$: \+ \\
+ $v \getsr \Bin^\ell$; \\
+ $(v', x) \gets \id{encrypt}^{F_K(\cdot)}(v, x)$; \\
+ \RETURN $(v, y)$;
+ \next
+ Algorithm $\DD(K, y')$; \+ \\
+ $(v, y) \gets y'$; \\
+ $(v', x) \gets {}$ \\
+ \qquad $\id{decrypt}^{F_K(\cdot), F^{-1}_K(\cdot)}(v, y)$; \\
+ \RETURN $x$;
+ \end{program}
+
+ \def\what{C}
+ \def\super{F, c}
+ \def\imsg{\Xid{i}{msg}}
+ \item Generalized counters: define $\Enc = (\GG, \EE, \DD)$, where $c$ is a
+ generalized counter in $\Bin^\ell$, and
+ \begin{program}
+ Algorithm $\GG()$: \+ \\
+ $K \getsr \keys F$; \\
+ $\imsg \gets 0$; \\
+ \RETURN $K$;
+ \next
+ Algorithm $\EE(K, x)$: \+ \\
+ $i \gets c(\imsg)$; \\
+ $(v', x) \gets \id{encrypt}^{F_K(\cdot)}(i, x)$; \\
+ $\imsg \gets \imsg + 1$; \\
+ \RETURN $(i, y)$;
+ \next
+ Algorithm $\DD(K, y')$; \+ \\
+ $(i, y) \gets y'$; \\
+ $(v', x) \gets {}$ \\
+ \qquad $\id{decrypt}^{F_K(\cdot), F^{-1}_K(\cdot)}(i, y)$; \\
+ \RETURN $x$;
+ \end{program}
+
+ \def\what{E}
+ \def\super{F, c}
+ \def\imsg{\Xid{i}{msg}}
+ \item Encrypted counters: if $L \ge \ell$, then define $\Enc = (\GG, \EE,
+ \DD)$, where $c$ is a generalized counter in $\Bin^\ell$, and
+ \begin{program}
+ Algorithm $\GG()$: \+ \\
+ $K \getsr \keys F$; \\
+ $\imsg \gets 0$; \\
+ \RETURN $K$;
+ \next
+ Algorithm $\EE(K, x)$: \+ \\
+ $i \gets c(\imsg)$; \\
+ $v \gets F_K(i)[0 \bitsto \ell]$; \\
+ $(v', x) \gets \id{encrypt}^{F_K(\cdot)}(v, x)$; \\
+ $\imsg \gets \imsg + 1$; \\
+ \RETURN $(i, y)$;
+ \next
+ Algorithm $\DD(K, y')$; \+ \\
+ $(i, y) \gets y'$; \\
+ $v \gets F_K(i)[0 \bitsto \ell]$; \\
+ $(v', x) \gets {}$ \\
+ \qquad $\id{decrypt}^{F_K(\cdot), F^{-1}_K(\cdot)}(v, y)$; \\
+ \RETURN $x$;
+ \end{program}
+ (We require $L \ge \ell$ for this to be well-defined; otherwise the
+ encrypted counter value is too short.)
+
+ \def\what{L}
+ \def\super{F, V_0}
+ \def\vnext{\Xid{v}{next}}
+ \item Carry-over: define $\Enc = (\GG, \EE, \DD)$ where $V_0 \in \Bin^\ell$
+ is the initialization vector for the first message, and
+ \begin{program}
+ Algorithm $\GG()$: \+ \\
+ $K \getsr \keys F$; \\
+ $\vnext \gets V_0$; \\
+ \RETURN $K$;
+ \next
+ Algorithm $\EE(K, x)$: \+ \\
+ $v \gets \vnext$; \\
+ $(v', x) \gets \id{encrypt}^{F_K(\cdot)}(v, x)$; \\
+ $\vnext \gets v'$; \\
+ \RETURN $(v, y)$;
+ \next
+ Algorithm $\DD(K, y')$; \+ \\
+ $(v, y) \gets y'$; \\
+ $(v', x) \gets {}$ \\
+ \qquad $\id{decrypt}^{F_K(\cdot), F^{-1}_K(\cdot)}(v, y)$; \\
+ \RETURN $x$;
+ \end{program}
+ \end{itemize}
+
+ Note that, while the encryption algorithms of the above schemes are either
+ randomized or stateful, the decryption algorithms are simple and
+ deterministic.
+\end{definition}
+
+The following simple and standard result will be very useful in our proofs.
+
+\begin{proposition}
+ \label{prop:enc-info-to-real}
+ \leavevmode
+ \begin{enumerate}
+ \item Suppose that $\E^P = (G^P, E^P, D^P)$ is one of the symmetric
+ encryption schemes of definition~\ref{def:enc-scheme}, constructed from a
+ pseudorandom permutation $P\colon \Bin^\ell \leftrightarrow \Bin^\ell$.
+ If $q$ is an upper bound on the number of PRP applications required for
+ the encryption $q_E$ messages totalling $\mu_E$ bits, and $t'$ is some
+ small constant, then
+ \[ \InSec{lor-cpa}(\E^P; t, q_E, \mu_E) \le
+ \InSec{lor-cpa}(\E^{\Perm{\ell}}; t, q_E, \mu_E) +
+ 2 \cdot \InSec{prp}(P; t + q t', q) .
+ \]
+ \item Similarly, suppose that $\E^F = (G^F, E^F, D^F)$ is one of the
+ symmetric encryption schemes of definition~\ref{def:enc-scheme},
+ constructed from a pseudorandom function $F\colon \Bin^\ell \to \Bin^L$.
+ If $q$ is an upper bound on the number of PRP applications required for
+ the encryption $q_E$ messages totalling $\mu_E$ bits, and $t'$ is some
+ small constant, then
+ \[ \InSec{lor-cpa}(\E^F; t, q_E, \mu_E) \le
+ \InSec{lor-cpa}(\E^{\Func{\ell}{L}}; t, q_E, \mu_E) +
+ 2 \cdot \InSec{prf}(F; t + q t', q) .
+ \]
+ \end{enumerate}
+\end{proposition}
+\begin{proof}
+ \begin{enumerate}
+ \item Let $A$ be an adversary attacking the LOR-CPA security of $\E^P$,
+ which takes time $t$ and issues $q_E$ encryption queries totalling
+ $\mu_E$ bits. We construct an adversary $B$ attacking the security of
+ the PRP $P$ as follows. $B$ selects a random $b^* \inr \Bin$. It then
+ runs $A$, simulating the LOR-CPA game by using $b^*$ to decide whether to
+ encrypt the left or right plaintext, and using its oracle access to $P$
+ to do the encryption. Eventually, $A$ returns a bit $b$. If $b = b^*$,
+ $B$ returns $1$ (indicating `pseudorandom'); otherwise it returns $0$.
+
+ If $B$'s oracle is selected from the PRP $P$, then $B$ correctly
+ simulates the LOR-CPA game for $\E^P$, and $B$ returns $1$ with
+ probability precisely $(\Adv{lor-cpa}{\E^P}(A) + 1)/2$. Conversely, if
+ $B$'s oracle is a random permutation, then $B$ correctly simulates the
+ LOR-CPA game for $\E^{\Perm{\ell}}$, so $B$ returns $1$ with probability
+ $(\Adv{lor-cpa}{\E^P}(A) + 1)/2$. Thus, we have
+ \begin{eqnarray}[rl]
+ \Adv{prp}{P}(B)
+ & = (\Adv{lor-cpa}{\E^P}(A) + 1)/2
+ - (\Adv{lor-cpa}{\E^{\Perm{\ell}}}(A) + 1)/2 \\
+ & = (\Adv{lor-cpa}{\E^P}(A)
+ - \Adv{lor-cpa}{\E^{\Perm{\ell}}}(A))/2 .
+ \end{eqnarray}
+ Note that the extra work which $B$ does over $A$ -- initialization,
+ tidying up and encrypting messages -- is bounded by some small constant
+ $t_P$ multiplied by the number of oracle queries~$q$ made by~$B$, and the
+ required result follows by multiplying through by~$2$ and rearranging.
+ \item The proof for this case is almost identical: merely substitute $F$
+ for $P$, `PRF' for `PRP' and $\Func{\ell}{L}$ for $\Perm{\ell}$ in the
+ above. \qed
+ \end{enumerate}
+\end{proof}
+
+Of course, proving theorems about each of the above schemes individually will
+be very tedious. We therefore define a `hybrid' scheme which switches
+between the above selection methods. This isn't a practical encryption
+scheme -- just a `trick' to reduce the number of complicated proofs we need
+to give.
+
+\begin{definition}[Hybrid encryption modes]
+ \label{def:enc-hybrid}
+ \def\Enc{\Xid{\E}{$m$\what}^{\super}_{\sub}}
+ \def\GG{\Xid{G}{$m$\what}^{\super}_{\sub}}
+ \def\EE{\Xid{E}{$m$\what}^{\super}_{\sub}}
+ \def\DD{\Xid{D}{$m$\what}^{\super}_{\sub}}
+ \def\what{H}
+ \def\super{F, V_0, c}
+ \def\sub{n_L, n_C, n_E}
+ \def\imsg{\Xid{i}{msg}}
+ \def\vnext{\Xid{v}{next}}
+ Let $n_L$, $n_C$ and $n_E$ be nonnegative integers, with $n_L + n_C + n_E
+ \le 2^{\ell}$; let $F$ be a pseudorandom permutation on $\Bin^\ell$ (resp.\
+ a pseudorandom function from $\Bin^\ell$ to $\Bin^L$); let $m =
+ (\id{encrypt}, \id{decrypt})$ be a block cipher (resp.\ PRF) encryption
+ mode let $V_0 \in \Bin^\ell$ be an initialization vector; and let $c\colon
+ \Nupto{2^\ell} \to \Bin^\ell$ be a generalized counter. (Again, if $F$ is
+ a PRF, we set $F_K(x) = \bot$ for all $K$ and $x$.) We define the scheme
+ $\Enc = (\GG, \EE, \DD)$ as follows.
+ \begin{program}
+ Algorithm $\GG()$: \+ \\
+ $K \getsr \keys F$; \\
+ $\imsg \gets 0$; \\
+ $\vnext \gets V_0$; \\
+ \RETURN $K$;
+ \next
+ Algorithm $\DD(K, y')$; \+ \\
+ $(v, y) \gets y'$; \\
+ $(v', x) \gets \id{decrypt}^{F_K(\cdot), F^{-1}_K(\cdot)}(v, y)$; \\
+ \RETURN $x$;
+ \newline
+ Algorithm $\EE(K, x)$: \+ \\
+ \IF $\imsg < n_L$ \THEN $v \gets \vnext$; \\
+ \ELSE\IF $\imsg < n_L + n_C$ \THEN $v \gets c(\imsg)$; \\
+ \ELSE\IF $\imsg < n_L + n_C + n_E$ \THEN
+ $v \gets F_K(c(\imsg)[0 \bitsto \ell])$; \\
+ \ELSE $v \getsr \Bin^\ell$; \\
+ $(v', x) \gets \id{encrypt}^{F_K(\cdot)}(v, x)$; \\
+ $\vnext \gets v'$; \\
+ $\imsg \gets \imsg + 1$; \\
+ \RETURN $(v, y)$;
+ \end{program}
+ For this to be well-defined, we require that $L \ge \ell$ or $n_E = 0$ --
+ otherwise the encrypted counter values are too short.
+\end{definition}
+
+The following proposition relates the security of our artificial hybrid
+scheme to that of the practical schemes defined in
+definition~\ref{def:enc-scheme}.
+
+\begin{proposition}
+ \label{prop:enc-hybrid}
+ Let $F$ be a pseudorandom permutation on $\Bin^\ell$ (resp.\ a pseudorandom
+ function from $\Bin^\ell$ to $\Bin^L$); let $m$ be a block cipher (resp.\
+ PRF) encryption mode. Then:
+ \begin{enumerate}
+ \def\ii#1{\item $\displaystyle#1$}
+ \ii{\InSec{lor-cpa}(\Xid{E}{$m\$$}^F; t, q_E, \mu_E) \le
+ \InSec{lor-cpa}(\Xid{E}{$m$H}^{F, V_0, c}_{0, 0, 0}; t, q_E, \mu_E)}
+ \ii{\InSec{lor-cpa}(\Xid{E}{$m$C}^{F, c}; t, q_E, \mu_E) \le
+ \InSec{lor-cpa}
+ (\Xid{E}{$m$H}^{F, V_0, c}_{q_E, 0, 0}; t, q_E, \mu_E)}
+ \ii{\InSec{lor-cpa}(\Xid{E}{$m$E}^{F, c}; t, q_E, \mu_E) \le
+ \InSec{lor-cpa}
+ (\Xid{E}{$m$H}^{F, V_0, c}_{0, q_E, 0}; t, q_E, \mu_E)}
+ \ii{\InSec{lor-cpa}(\Xid{E}{$m$L}^{F, V_0}; t, q_E, \mu_E) \le
+ \InSec{lor-cpa}
+ (\Xid{E}{$m$H}^{F, V_0, c}_{0, 0, q_E}; t, q_E, \mu_E)}
+ \end{enumerate}
+\end{proposition}
+
+\begin{proof}
+ For 1, it suffices to note that $\Xid{E}{$m\$$}^F \equiv \Xid{E}{$m$H}^{c,
+ V_0}_{0, 0, 0}$ for any $c$, $V_0$. For the others, we observe that, while
+ the IVs returned in the ciphertexts differ, it's very easy to simulate
+ encryption for the practical schemes given an encryption oracle for the
+ hybrid scheme: for the counter and encrypted-counter schemes, the counter
+ function is public knowledge; for the carry-over scheme, the correct IV for
+ the first message is known, and the IV any subsequent messages can be
+ computed from the previous IV and ciphertext according to condition~4 in
+ definition~\ref{def:enc-scheme}.
+\end{proof}
+
+%%%--------------------------------------------------------------------------
+
+\section{Ciphertext block chaining (CBC) encryption}
+\label{sec:cbc}
+
+\subsection{Description}
+\label{sec:cbc-desc}
+
+Suppose $E$ is an $\ell$-bit pseudorandom permutation. CBC mode works as
+follows. Given a message $X$, we divide it into $\ell$-bit blocks $x_0$,
+$x_1$, $\ldots$, $x_{n-1}$. Choose an initialization vector $v \in
+\Bin^\ell$. Before passing each $x_i$ through $E$, we XOR it with the
+previous ciphertext, with $v$ standing in for the first block:
+\begin{equation}
+ y_0 = E_K(x_0 \xor v) \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 $v$ and the $y_i$. Decryption is
+simple:
+\begin{equation}
+ x_0 = E^{-1}_K(y_0) \xor v \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{cgraph}{cbc-mode}
+ []!{0; <0.85cm, 0cm>: <0cm, 0.5cm>::}
+ *+=(1, 0)+[F]{\mathstrut x_0}="x"
+ :[dd] *{\xor}="xor"
+ [ll] *+=(1, 0)+[F]{\mathstrut v} :"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{cgraph}
+
+ \caption{Encryption using CBC mode}
+ \label{fig:cbc}
+\end{figure}
+
+\begin{definition}[CBC algorithms]
+ \label{def:cbc}
+ For any permutation $P\colon \Bin^\ell \to \Bin^\ell$, any initialization
+ vector $v \in \Bin^\ell$, any plaintext $x \in \Bin^{\ell\N}$ and any
+ ciphertext $y \in \Bin^*$, we define the encryption mode $\id{CBC} =
+ (\id{cbc-encrypt}, \id{cbc-decrypt})$ as follows:
+ \begin{program}
+ Algorithm $\id{cbc-encrypt}^{P(\cdot)}(v, x)$: \+ \\
+ $y \gets \emptystring$; \\
+ \FOR $i = 0$ \TO $|x|/\ell$ \DO \\ \ind
+ $x_i \gets x[\ell i \bitsto \ell (i + 1)]$; \\
+ $y_i \gets P(x_i \xor v)$; \\
+ $v \gets y_i$; \\
+ $y \gets y \cat y_i$; \- \\
+ \RETURN $(v, y)$;
+ \next
+ Algorithm $\id{cbc-decrypt}^{P(\cdot), P^{-1}(\cdot)}(v, y)$: \+ \\
+ \IF $|y| \bmod \ell \ne 0$ \THEN \RETURN $\bot$; \\
+ $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}(y_i) \xor v$; \\
+ $v \gets y_i$; \\
+ $x \gets x \cat x_i$; \- \\
+ \RETURN $(v, x)$;
+ \end{program}
+ Now, let $c$ be a generalized counter in $\Bin^\ell$. We define the
+ encryption schemes $\Xid{E}{CBC$\$$}^P$, $\Xid{E}{CBCE}^P$ and
+ $\Xid{E}{CBCH}^{P, c, \bot}_{0, 0, n_E}$, as described in
+ definition~\ref{def:enc-scheme}.
+\end{definition}
+
+\subsection{Security of CBC mode}
+
+We now present our main theorem on CBC mode.
+
+\begin{theorem}[Security of hybrid CBC mode]
+ \label{thm:cbc}
+ Let $P\colon \keys P \times \Bin^\ell \to \Bin^\ell$ be a pseudorandom
+ permutation; let $v_0 \in \Bin^\ell$ be an initialization vector; let $n_L
+ \in \{\, 0, 1 \,\}$; let $c$ be a generalized counter in $\Bin^\ell$; and
+ let $n_C \in \N$ be a nonnegative integer; and suppose that at most one of
+ $n_L$ and $n_C$ is nonzero. Then, for any $t$, $q_E \ge n$ and $\mu_E$,
+ \[ \InSec{lor-cpa}
+ (\Xid{\E}{CBCH}^{P, c, v_0}_{n_L, 0, n_E}; t, q_E, \mu_E) \le
+ 2 \cdot \InSec{prp}(P; t + q t_P, q) + \frac{q (q - 1)}{2^\ell - q}
+ \]
+ where $q = n_L + n_E + \mu_E/\ell$ and $t_P$ is some small constant.
+\end{theorem}
+
+The proof of this theorem we postpone until section~\ref{sec:cbc-proof}. As
+promised, the security of our randomized and stateful schemes follow as
+simple corollaries.
+
+\begin{corollary}[Security of practical CBC modes]
+ \label{cor:cbc}
+ Let $P$ and $c$ be as in theorem~\ref{thm:cbc}. Then for any $t$, $q_E$
+ and $\mu_E$, and some small constant $t_P$,
+ \begin{eqnarray*}[rl]
+ \InSec{lor-cpa}(\Xid{\E}{CBC$\$$}^P; t, q_E, \mu_E)
+ & \le 2 \cdot \InSec{prp}(P; t + q t_P, q) + \frac{q (q - 1)}{2^\ell - q}
+ \\
+ \InSec{lor-cpa}(\Xid{\E}{CBCE}^{P, c}; t, q_E, \mu_E)
+ & \le 2 \cdot \InSec{prp}(P; t + q' t_P, q') +
+ \frac{q' (q' - 1)}{2^\ell - q'}
+ \\
+ \tabpause{and}
+ \InSec{lor-cpa}(\Xid{\E}{CBCL}^{P, v_0}; t, 1, \mu_E)
+ & \le 2 \cdot \InSec{prp}(P; t + q t_P, q) +
+ \frac{q (q - 1)}{2^\ell - q}
+ \end{eqnarray*}
+ where $q = \mu_E/\ell$, and $q' = q + q_E$.
+\end{corollary}
+\begin{proof}
+ Follows from theorem~\ref{thm:cbc} and proposition~\ref{prop:enc-hybrid}.
+\end{proof}
+
+\begin{remark}
+ The insecurity of CBC mode over that inherent in the underlying PRP is
+ essentially a birthday bound: note for $q \le 2^{\ell/2}$, our denominator
+ $2^\ell - q \approx 2^\ell$, and for larger $q$, the term $q (q - 1)/2^\ell
+ > 1$ anyway, so all security is lost (according to the above result).
+ Compared to \cite[theorem~17]{Bellare:2000:CST}, we gain the tiny extra
+ term in the denominator, but lose the PRP-as-a-PRF term $q^2
+ 2^{-\ell-1}$.\footnote{%
+ In fact, they don't prove the stated bound of $q (3 q - 2)/2^{\ell+1}$
+ but instead the larger $q (2 q - 1)/2^\ell$. The error is in the
+ application of their proposition~8: the PRF-insecurity term is doubled,
+ so the PRP-as-a-PRF term must be also.} %
+\end{remark}
+
+\subsection{Ciphertext stealing}
+
+Ciphertext stealing \cite{Daemen:1995:CHF,Schneier:1996:ACP,RFC2040} allows
+us to encrypt any message in $\Bin^*$ without the need for padding. The
+trick is to fill in the `gap' at the end of the last block with the end bit
+of the previous ciphertext, and then to put the remaining short penultimate
+block at the end. Decryption proceeds by first decrypting the final block to
+recover the remainder of the penultimate one. See
+figure~\ref{fig:cbc-steal}.
+
+\begin{figure}
+ \begin{cgraph}{cbc-steal-enc}
+ []!{0; <0.85cm, 0cm>: <0cm, 0.5cm>::}
+ *+=(1, 0)+[F]{\mathstrut x_0}="x"
+ :[dd] *{\xor}="xor"
+ [ll] *+=(1, 0)+[F]{\mathstrut v} :"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{cgraph}
+
+ \begin{cgraph}{cbc-steal-dec}
+ []!{0; <0.85cm, 0cm>: <0cm, 0.5cm>::}
+ *+=(1, 0)+[F]{\mathstrut y_0}="y"
+ :[ddddddd] *+[F]{D}="d" [l] {K} :"d"
+ [rrrdd] *{\xor} ="nx" "d" [u] :`r [rd] `d "nx" "nx"
+ "d" :[dd] *{\xor} ="xor" [ll] *+=(1, 0)+[F]{\mathstrut v} :"xor"
+ :[dd] *+=(1, 0)+[F]{\mathstrut x_0} "nx"="xor"
+ "y" [rrr] *+=(1, 0)+[F]{\mathstrut y_1}="y"
+ :[ddddddd] *+[F]{D}="d" [l] {K} :"d"
+ [rrrdd] *{\xor} ="nx" "d" [u] :@{-->}`r [rd] `d "nx" "nx"
+ "d" :"xor"
+ :[dd] *+=(1, 0)+[F]{\mathstrut x_1} "nx"="xor"
+ "y" [rrr] *+=(1, 0)+[F--]{\mathstrut y_i}="y"
+ :@{-->}[ddddddd] *+[F]{D}="d" [l] {K} :"d"
+ [rrrdd] *{\xor} ="nx" "d" [u] :@{-->}`r [rd] `d "nx" "nx"
+ "d" :"xor"
+ :[dd] *+=(1, 0)+[F--]{\mathstrut x_i} "nx"="xor"
+ "y" [rrr] *+=(1, 0)+[F]{\mathstrut y_{n-2}}="y"
+ [dddddrrr] *+[F]{D}="d" [r] {K} :"d"
+ "y" [dd] ="x"
+ "d" [uu] ="e"
+ []!{"x"; "y" **{}, "x"+/4pt/ ="p",
+ "x"; "e" **{}, "x"+/4pt/ ="q",
+ "e"; "x" **{}, "e"+/4pt/ ="r",
+ "e"; "d" **{}, "e"+/4pt/ ="s",
+ "y";
+ "p" **\dir{-};
+ "q" **\crv{"x"};
+ "r" **\dir{-};
+ "s" **\crv{"e"};
+ "d" **\dir{-}?>*\dir{>}}
+ "d" :[dd] {z} ="z"
+ "z" [llluu] *{\xor} ="x1"
+ "z" :`l [lu] `u "x1" |*+{\scriptstyle 0^t \cat z[t \bitsto \ell]} "x1"
+ "z" :[dd] *{\xor} ="xor2"
+ :[dd] *+[F]{\mathstrut x_{n-1}[0 \bitsto t]}
+ "y" [rrr] *+=(1, 0)+[F]{\mathstrut y_{n-1} \cat 0^{\ell-t}}="y"
+ [dd] ="x"
+ "d" [llluu] ="e"
+ []!{"x"; "y" **{}, "x"+/4pt/ ="p",
+ "x"; "e" **{}, "x"+/4pt/ ="q",
+ "e"; "x" **{}, "e"+/4pt/ ="r",
+ "e"; "x1" **{}, "e"+/4pt/ ="s",
+ "x"; "e" **{} ?="c" ?(0.5)/-4pt/ ="cx" ?(0.5)/4pt/ ="cy",
+ "y";
+ "p" **\dir{-};
+ "q" **\crv{"x"};
+ "cx" **\dir{-};
+ "c" *[@]\cir<4pt>{d^u};
+ "cy";
+ "r" **\dir{-};
+ "s" **\crv{"e"};
+ "x1" **\dir{-}?>*\dir{>}}
+ "x1" [d] :`r [rd] `d "xor2" "xor2"
+ "x1" :[dd] *+[F]{D}="d" [l] {K} :"d"
+ "d" :"xor"
+ :[dd] *+[F]{\mathstrut x_{n-2}}
+ \end{cgraph}
+
+ \caption{Encryption and decryption using CBC mode with ciphertext stealing}
+ \label{fig:cbc-steal}
+\end{figure}
+
+Encrypting messages shorter than the block involves `IV stealing', which is a
+grotty hack but works fine if IVs are random; if the IVs are encrypted
+counters then there's nothing (modifiable) to steal from.
+
+We formally present a description of a randomized CBC stealing mode.
+
+\begin{definition}[CBC mode with ciphertext stealing]
+ \label{def:cbc-steal}
+ Let $P\colon \keys P \times \Bin^\ell \to \Bin^\ell$ be a pseudorandom
+ permutation. Let $c$ be a generalized counter on $\Bin^\ell$. We define
+ the randomized symmetric encryption scheme
+ $\Xid{\E}{CBC$\$$-steal}^P = (\Xid{G}{CBC$\$$-steal}^P,
+ \Xid{E}{CBC$\$$-steal}^P, \Xid{D}{CBC\$-steal}^P)$ for messages in $\Bin^*$
+ as follows:
+ \begin{program}
+ Algorithm $\Xid{G}{CBC$\$$-steal}^P()$: \+ \\
+ $K \getsr \keys P$; \\
+ \RETURN $K$;
+ \- \\[\medskipamount]
+ Algorithm $\Xid{E}{CBC$\$$-steal}^P(K, x)$: \+ \\
+ $t \gets |x| \bmod \ell$; \\
+ \IF $t \ne 0$ \THEN $x \gets x \cat 0^{\ell-t}$; \\
+ $v \getsr \Bin^\ell$; \\
+ $y \gets v \cat \id{cbc-encrypt}(K, v, x)$; \\
+ \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)$: \+ \\
+ \IF $|y| < \ell$ \THEN \RETURN $\bot$; \\
+ $v \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 \id{cbc-decrypt}(K, v, y[\ell \bitsto |y|])$; \\
+ \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}
+
+The security of ciphertext stealing follows directly from the definition and
+the security CBC mode.
+
+\begin{corollary}[Security of CBC with ciphertext stealing]
+ \label{cor:cbc-steal}
+ Let $P\colon \keys P \times \Bin^\ell \to \Bin^\ell$ be a pseudorandom
+ permutation. Then
+ \begin{eqnarray*}[rl]
+ \InSec{lor-cpa}(\Xid{\E}{CBC$\$$-steal}; t, q_E, \mu_E)
+ & \le \InSec{lor-cpa}
+ (\Xid{\E}{CBC$\$$}; t, q_E, \mu_E + q_E (\ell - 1)) \\
+ & \le 2 \cdot \InSec{prp}(P; t + q t_P, q) +
+ \frac{q (q - 1)}{2^\ell - 2^{\ell/2}}
+ \end{eqnarray*}
+ where $q = \bigl\lfloor \bigl(\mu_E + q_E (\ell - 1)\bigr)/\ell
+ \bigr\rfloor$ and $t_P$ is some small constant.
+\end{corollary}
+
+\begin{proof}
+ From the definition, we see that the encryption algorithm
+ $\Xid{E}{CBC-steal}$ simply pads a plaintext, encrypts it as for standard
+ CBC mode, and postprocesses the ciphertext. Hence, if $A$ is any adversary
+ attacking $\Xid{\E}{CBC-steal}$, we can construct an adversary
+ $A'$ which simply runs $A$ except that, on each query to the encryption
+ oracle, it pads both plaintexts, queries its CBC oracle, postprocesses the
+ ciphertext returned, and gives the result back to $A$. The fact that
+ plaintexts can now be up to $\ell - 1$ bits shorter than the next largest
+ whole number of blocks means that $B$ submits no more than $\mu_E + q_E
+ (\ell - 1)$ bits of plaintext to its oracle. The required result
+ follows then directly from theorem~\ref{thm:cbc}.
+\end{proof}
+
+\subsection{Proof of theorem~\ref{thm:cbc}}
+\label{sec:cbc-proof}
+
+The techniques and notation used in this proof will also be found in several
+of the others. We recommend that readers try to follow this one carefully.
+
+We begin considering CBC mode using a completely random permutation. To
+simplify notation slightly, we shall write $n = n_L + n_E$. Our main goal is
+to prove the claim that there exists a garbage-emitter $W$ such that
+\[
+ \InSec{rog-cpa-$W$}
+ (\Xid{\E}{CBCH}^{\Perm{\ell}, c, v_0}_{n_L, 0, n_E};
+ t, q_E, \mu_E) \le
+ \frac{q (q - 1)}{2 \cdot (2^\ell - n)}.
+\]
+From this, we can apply proposition~\ref{prop:rog-and-lor} to obtain
+\[
+ \InSec{lor-cpa}
+ (\Xid{\E}{CBCH}^{\Perm{\ell}, c, \bot}_{0, 0, n};
+ t, q_E, \mu_E) \le
+ \frac{q (q - 1)}{2^\ell - n}.
+\]
+and, noting that there are precisely $q = \mu_E/\ell$ PRP-applications, we
+apply proposition~\ref{prop:enc-info-to-real} to obtain the required result.
+
+Our garbage-emitter $W$ is a bit complicated. It chooses random but
+\emph{distinct} blocks for the `ciphertext'; for the IVs, it uses $v_0$ for
+the first message if $n_L = 1$, and otherwise it chooses random blocks
+distinct from each other and the `ciphertext' blocks for the next $n_E$
+messages, and just random blocks for subsequent ones. The algorithm $W$ is
+shown in figure~\ref{fig:cbc-garbage}.
+
+\begin{figure}
+ \begin{program}
+ Initialization: \+ \\
+ $i \gets 0$; \\
+ $\id{gone} \gets \emptyset$;
+ \- \\[\medskipamount]
+ Function $\id{fresh}()$ \+ \\
+ $x \getsr \Bin^\ell \setminus \id{gone}$; \\
+ $\id{gone} \gets \id{gone} \cup \{ x \}$; \\
+ \RETURN $x$;
+ \next
+ Garbage emitter $W(m)$: \+ \\
+ \IF $i \ge 2^\ell$ \THEN \ABORT; \\
+ \IF $i < n_L$ \THEN $v \gets v_0$; \\
+ \ELSE \IF $i < n$ \THEN $v \gets \id{fresh}()$; \\
+ $i \gets i + 1$ \\
+ \ELSE $v \getsr \Bin^\ell$; \\
+ $y \gets \emptystring$; \\
+ \FOR $j = 0$ \TO $m/\ell$; \\ \ind
+ $y_j \gets \id{fresh}()$; \\
+ $y \gets y \cat y_j$; \- \\
+ \RETURN $(v, y)$;
+ \end{program}
+
+ \caption{Garbage emitter $W$ for CBC mode}
+ \label{fig:cbc-garbage}
+\end{figure}
+
+Fortunately, it doesn't need to be efficient: the above simulations only need
+to be able to do the LOR game, not the ROG one. The unpleasant-sounding
+\ABORT\ only occurs after $2^\ell$ queries. If that happens we give up and
+say the adversary won anyway: the claim is trivially true by this point,
+since the adversary's maximum advantage is 1.
+
+Now we show that this lash-up is a good imitation of CBC encryption to
+someone who doesn't know the key. The intuition works like this: every time
+we query a random permutation at a new, fresh input value, we get a new,
+different, random output value; conversely, if we repeat an input, we get the
+same value out as last time. So, in the real `result' CBC game, if all the
+permutation inputs are distinct, it looks just like the garbage emitted by
+$W$. Unfortunately, that's not quite enough: the adversary can work out what
+the permutation inputs ought to be and spot when there ought to have been a
+collision but wasn't. So we'll show that, provided all the $P$-inputs --
+values which \emph{would} be input to the permutation if we're playing that
+game -- are distinct, the two games look identical.
+
+We need some notation to describe the values in the game. Let $c_i = c(i)$
+be the $i$th counter value, for $0 \le i < n_E$, and let $v_i$ be the $i$th
+initialization vector, where $v_0$ is as given if $n_L = 1$, $v_i = P(c_i -
+n_L)$ if $n_L \le i < n$, and $v_i \inr \Bin^\ell$ if $n \le i < q_E$. Let
+$q' = \mu_E/\ell = q - n$ be the total number of plaintext blocks in the
+adversary's queries, let $x_i$ be the $i$th plaintext block queried, let
+$y_i$ be the $i$th ciphertext block returned, let
+\[ w_i = \begin{cases}
+ v_j & if block $i$ is the first block of the $j$th query, and \\
+ y_{i-1} & otherwise
+\end{cases} \]
+and let $z_i = x_i \xor w_i$, all for $0 \le i < q'$. This is summarized
+diagramatically in figure~\ref{fig:cbc-proof-notation}. The $P$-inputs are
+now precisely the $c_i$ and the $z_i$. We'll denote probabilities in the
+`result' game as $\Pr_R[\cdot]$ and in the `garbage' game as $\Pr_G[\cdot]$.
+
+\begin{figure}
+ \begin{vgraphs}
+ \begin{vgraph}{cbc-notation-a}
+ [] !{<1.33cm, 0cm>: <0cm, 1cm>::}
+ {c_i} :[r] *+[F]{E}="e" [u] {K} :"e" :[r] {v_i}
+ \end{vgraph}
+ \begin{vgraph}{cbc-notation-b}
+ [] !{<1.33cm, 0cm>: <0cm, 1cm>::}
+ {x_i} :[r] *{\xor} ="xor" :[r] {z_i}
+ :[r] *+[F]{E}="e" [u] {K} :"e" :[r] {y_i}
+ "xor" [u] {w_i} ="w" :"xor"
+ "w" [lu] {v_j} ="v" :"w"
+ "w" [ru] {y_{i-1}} ="y" :"w"
+ "v" :@{.}|-*+\hbox{or} "y"
+ \end{vgraph}
+ \end{vgraphs}
+
+ \caption{Notation for the proof of theorem~\ref{thm:cbc}.}
+ \label{fig:cbc-proof-notation}
+\end{figure}
+
+Let $C_r$ be the event, in either game, that $z_i = z_j$ for some $0 \le i <
+j < r$, or that $z_i = c_j$ for some $0 \le i < r$ and some $0 \le j < n_E$.
+We need to bound the probability that $C_{q'}$ occurs in both the `result'
+and `garbage' games. We'll do this inductively. By the definition,
+$\Pr_R[C_0] = \Pr_G[C_0] = 0$.
+
+Firstly, tweak the games so that all of the IVs corresponding to counters are
+chosen at the beginning, instead of as we go along. Obviously this doesn't
+make any difference to the adversary's view of the proceedings, but it makes
+our analysis easier.
+
+Let's assume that $C_r$ didn't happen; we want the probability that $C_{r+1}$
+did, which is obviously just the probability that $z_r$ collides with some
+$z_i$ for $0 \le i < r$ or some $c_i$ for $0 \le i < n$. At this point, the
+previous $z_i$ are fixed. So:
+\begin{equation}
+ \label{eq:cbc-coll}
+ \Pr[C_{r+1} | \bar{C}_r]
+ = \sum_{z \in \Bin^\ell} \biggl(
+ \sum_{0\le i<n} \Pr[z = c_i] +
+ \sum_{0\le i<r} \Pr[z = z_i]
+ \biggr) \cdot \Pr[z_r = z]
+\end{equation}
+Now note that $z_r = w_r \xor x_r$. We've no idea how $x_r$ was chosen; but,
+one of the following cases holds.
+\begin{enumerate}
+\item If $x_r$ is the first block of the first plaintext, i.e., $r = 0$, and
+ $n_L = 1$, then $w_r = v_0$. However, in this case we know that $n_E = 0$
+ by hypothesis. There are no $z_i$ which $z_r$ might collide with, so the
+ probability of a collision is zero.
+\item If $x_r$ is the first block of plaintext $i$, and $0 \le i < n$, then
+ $w_r = v_i$, and was chosen at random from a set of $2^\ell - i \le 2^\ell
+ - n \le 2^\ell - n - r$ possibilities, either by our random permutation or
+ by $W$. We know $x_r$ is independent of $w_r$ because none of the previous
+ $P$-inputs were equal to $c_i$, by our assumption of $\bar{C}_r$.
+\item If $x_r$ is the first block of plaintext $i$, and $n \le i < q'$, then
+ $w_r = v_i$, and was chosen at random from all $2\ell$ possible $\ell$-bit
+ blocks. We know $x_r$ is independent of $w_r$ because we just chose $w_r$
+ at random, after $x_r$ was chosen.
+\item Otherwise, $x_r$ is a subsequent block in some message, and $w_r =
+ y_{r-1}$, and was chosen at random from a set of $2^\ell - n - r$
+ possibilities, either by our random permutation or by $W$. We know $x_r$
+ is independent of $w_r$ because $z_{r-1}$ is a new $P$-input, by our
+ assumption of $\bar{C}_r$.
+\end{enumerate}
+So, except in case~1, which isn't a problem anyway, $w_r$ is independent of
+$x_r$, and chosen uniformly at random from a set of at least $2^\ell - r - n$
+elements, in either game -- so we can already see that $\Pr_R[C_i] =
+\Pr_G[C_i]$ for any $i \ge 0$. Finally, the $z_i$ and $c_i$ are all
+distinct, so the $z_i \xor x$ and $c_i \xor x$ must all be distinct, for any
+fixed $x$. So:
+\begin{eqnarray}[rl]
+ \Pr[C_{r+1} | \bar{C}_r]
+ & = \sum_{x \in \Bin^\ell} \biggl(
+ \sum_{0\le i<n} \Pr[w_r = x \xor c_i] +
+ \sum_{0\le i<r} \Pr[w_r = x \xor z_i]
+ \biggr) \cdot \Pr[x_r = x] \\
+ & \le \sum_{x \in \Bin^\ell} \frac{r + n}{2^\ell - r - n} \Pr[x_r = x]
+ = \frac{r + n}{2^\ell - r - n} \sum_{x \in \Bin^\ell} \Pr[x_r = x] \\
+ & = \frac{r + n}{2^\ell - r - n}.
+\end{eqnarray}
+Now we're almost home. All the $c_i$ and $z_i$ are distinct; all the $v_i$
+and $y_i$ are random, assuming $C_{q'}$. We can bound $\Pr[C_{q'}]$ thus:
+\begin{equation}
+ \Pr[C_{q'}]
+ \le \sum_{0<i\le q'} \Pr[C_i | \bar{C}_{i-1}]
+ \le \sum_{0\le i\le q'} \frac{i + n - 1}{2^\ell - i - n + 1}
+\end{equation}
+Now, let $i' = i + n - 1$. Then
+\begin{equation}
+ \Pr[C_{q'}]
+ \le \sum_{n-1\le i'\le q'+n-1} \frac{i'}{2^\ell - i'}
+ \le \sum_{0\le i'<q} \frac{i'}{2^\ell - q}
+ = \frac{q (q - 1)}{2 \cdot (2^\ell - q)}
+\end{equation}
+
+Finally, let $R$ be the event that the adversary returned 1 at the end of the
+game -- indicating a guess of `result'. Then, noting as we have, that
+$\Pr_R[C_{q'}] = \Pr_G[C_{q'}]$, we get this:
+\begin{eqnarray}[rl]
+ \Adv{rog-cpa-$W$}{\Xid{\E}{CBCH}^{P, c, n}}(A)
+ & = \Pr_R[R] - \Pr_G[R] \\
+ & \begin{eqnalign}[rLl][b]
+ {} = & (\Pr_R[R | C_{q'}] \Pr_R[C_{q'}] +
+ \Pr_R[R | \bar{C}_{q'}] \Pr_R[\bar{C}_{q'}]) - {} \\
+ & & (\Pr_G[R | C_{q'}] \Pr_R[C_{q'}] +
+ \Pr_G[R | \bar{C}_{q'}] \Pr_G[\bar{C}_{q'}])
+ \end{eqnalign} \\
+ & = \Pr_R[R | C_{q'}] \Pr_R[C_{q'}] - \Pr_G[R | C_{q'}] \Pr_G[C_{q'}] \\
+ & \le \Pr[C_{q'}] \le \frac{q (q - 1)}{2 \cdot (2^\ell - q)}
+\end{eqnarray}
+And we're done!
+\qed
+
+%%%--------------------------------------------------------------------------
+
+\section{Ciphertext feedback (CFB) encryption}
+\label{sec:cfb}
+
+\subsection{Description}
+\label{sec:cfb-desc}
+
+Suppose $F$ is an $\ell$-bit-to-$L$-bit pseudorandom function, and let $t \le
+L$. CFB mode works as follows. Given a message $X$, we divide it into
+$t$-bit blocks $x_0$, $x_1$, $\ldots$, $x_{n-1}$. Choose an initialization
+vector $v \in \Bin^\ell$. We maintain a \emph{shift register} $s_i$, whose
+initial value is $v$. To encrypt a block $x_i$, we XOR it with the result of
+passing the shift register through the PRF, forming $y_i$, and then update
+the shift register by shifting in the ciphertext block $y_i$. That is,
+\begin{equation}
+ s_0 = v \qquad
+ y_i = x_i \xor F_K(s_i) \qquad
+ s_{i+1} = s_i \shift{t} y_i \ \text{(for $0 \le i < n$)}.
+\end{equation}
+Decryption follows from noting that $x_i = y_i \xor F_K(s_i)$. See
+figure~\ref{fig:cfb} for a diagrammatic representation.
+
+Also, we observe that the final plaintext block needn't be $t$ bits long: we
+can pad it out to $t$ bits and truncate the result without affecting our
+ability to decrypt.
+
+\begin{figure}
+ \begin{cgraph}{cfb-mode}
+ [] !{<0.425cm, 0cm>: <0cm, 0.5cm>::}
+ *+=(2, 0)+[F]{\mathstrut v} ="v" :|<>(0.35)@{/}_<>(0.35){\ell}[rrrrr]
+ *+[o][F]{\shift{t}} ="shift"
+ [ll] :|-@{/}^-{\ell}[dd] *+[F]{E} ="e" [ll] {K} :"e"
+ :|-@{/}^-{t}[dd] *{\xor} ="xor"
+ [lll] *+=(2, 0)+[F]{\mathstrut x_0} :|-@{/}_-{t} "xor"
+ :|-@{/}^-{t}[ddd] *+=(2, 0)+[F]{\mathstrut y_0}
+ "xor" [d] :`r "shift" "shift"|-@{/}_-{t}
+ :|-@{/}_-{\ell}[rrrrrrr] *+[o][F]{\shift{t}} ="shift"
+ [ll] :|-@{/}^-{\ell}[dd] *+[F]{E} ="e" [ll] {K} :"e"
+ :|-@{/}^-{t}[dd] *{\xor} ="xor"
+ [lll] *+=(2, 0)+[F]{\mathstrut x_1} :|-@{/}_-{t} "xor"
+ :|-@{/}^-{t}[ddd] *+=(2, 0)+[F]{\mathstrut y_1}
+ "xor" [d] :`r "shift" "shift"|-@{/}_-{t}
+ :@{-->}|-@{/}_-{\ell}[rrrrrrr] *+[o][F]{\shift{t}} ="shift"
+ [ll] :@{-->}|-@{/}^-{\ell}[dd] *+[F]{E} ="e" [ll] {K} :"e"
+ :@{-->}|-@{/}^-{t}[dd] *{\xor} ="xor"
+ [lll] *+=(2, 0)+[F--]{\mathstrut x_i} :@{-->}|-@{/}_-{t} "xor"
+ :@{-->}|-@{/}^-{t}[ddd] *+=(2, 0)+[F--]{\mathstrut y_i}
+ "xor" [d] :@{-->} `r "shift" "shift"|-@{/}_-{t}
+ [rrrrrdd] *+[F]{E} ="e"
+ "shift" :@{-->}`r "e" |-@{/}_-{\ell} "e"
+ [ll] {K} :"e"
+ :|-@{/}^-{t}[dd] *{\xor} ="xor"
+ [lll] *+=(2, 0)+[F]{\mathstrut x_{n-1}} :|-@{/}_-{t} "xor"
+ :|-@{/}^-{t}[ddd] *+=(2, 0)+[F]{\mathstrut y_{n-1}}
+ \end{cgraph}
+
+ \caption{Encryption using CFB mode}
+ \label{fig:cfb}
+\end{figure}
+
+\begin{definition}[CFB algorithms]
+ For any function $F\colon \Bin^\ell \to \Bin^t$, any initialization vector
+ $v \in \Bin^\ell$, any plaintext $x \in \Bin^*$ and any ciphertext $y \in
+ \Bin^*$, we define PRF encryption mode $\id{CFB} = (\id{cfb-encrypt},
+ \id{cfb-decrypt})$ as follows:
+ \begin{program}
+ Algorithm $\id{cfb-encrypt}(F, v, x)$: \+ \\
+ $s \gets v$; \\
+ $L \gets |x|$; \\
+ $x \gets x \cat 0^{t\lceil L/t \rceil - L}$; \\
+ $y \gets \emptystring$; \\
+ \FOR $i = 0$ \TO $(|x| - t')/t$ \DO \\ \ind
+ $x_i \gets x[ti \bitsto t(i + 1)]$; \\
+ $y_i \gets x_i \xor F(s)$; \\
+ $s \gets s \shift{t} y_i$; \\
+ $y \gets y \cat y_i$; \- \\
+ \RETURN $(s, y[0 \bitsto L])$;
+ \next
+ Algorithm $\id{cfb-decrypt}(F, v, y)$: \+ \\
+ $s \gets v$; \\
+ $L \gets |y|$; \\
+ $y \gets y \cat 0^{t\lceil L/t \rceil - L}$; \\
+ $x \gets \emptystring$; \\
+ \FOR $i = 0$ \TO $(|x| - t')/t$ \DO \\ \ind
+ $y_i \gets y[ti \bitsto t(i + 1)]$; \\
+ $x_i \gets x_i \xor F(s)$; \\
+ $s \gets s \shift{t} y_i$; \\
+ $x \gets x \cat x_i$; \- \\
+ \RETURN $x[0 \bitsto L]$;
+ \end{program}
+ We now define the schemes $\Xid{\E}{CFB$\$$}^F$,
+ $\Xid{\E}{CFBC}^{F, c}$, $\Xid{\E}{CFBE}^{F, c}$, and
+ $\Xid{\E}{CFBL}^{F, V_0}$ according to
+ definition~\ref{def:enc-scheme}; and we define the hybrid scheme
+ $\Xid{\E}{CFBH}^{F, V_0, c}_{n_L, n_C, n_E}$ according to
+ definition~\ref{def:enc-hybrid}.
+\end{definition}
+
+\subsection{Security of CFB mode}
+
+%% I suspect David will want to put some negative results here, and complain
+%% about Alkassar et al.'s alleged proof. I'll press on with the positive
+%% stuff.
+%%
+%% The problems come when $t < \ell$. Then C-mode isn't necessarily secure
+%% (well, we get a similar bound with $t$ instead of $\ell$, which isn't very
+%% impressive). The L-mode needs careful selection of the initial IV.
+
+\begin{definition}[Sliding strings]
+ \label{def:slide}
+ We say that an $\ell$-bit string $x$ \emph{$t$-slides} if there exist
+ integers $i$ and $j$ such that $0 \le j < i < \ell/t$ and $x[i t \bitsto
+ \ell] = x[j t \bitsto \ell - (i - j) t]$.
+\end{definition}
+\begin{remark}
+ For all $\ell > 0$ and $t < \ell$, the string $0^{\ell-1} 1$ does not
+ $t$-slide.
+\end{remark}
+
+\begin{theorem}[Security of CFB mode]
+ \label{thm:cfb}
+ Let $F$ be a pseudorandom function from $\Bin^\ell$ to $\Bin^t$; let $V_0
+ \in \Bin^\ell$ be a non-$t$-sliding string; let $c$ be a generalized
+ counter in $\Bin^\ell$; and let $n_L$, $n_C$, $n_E$ and $q_E$ be
+ nonnegative integers; and furthermore suppose that
+ \begin{itemize}
+ \item $n_L + n_C + n_E \le q_E$,
+ \item $n_L = 0$, or $n_C = n_E = 0$, or $\ell \le t$ and $V_0 \ne c(i)$
+ for any $n_L \le i < n_L + n_C + n_E$, and
+ \item either $n_C = 0$ or $\ell \le t$.
+ \end{itemize}
+ Then, for any $t_E$ and $\mu_E$, and whenever
+ we have
+ \[ \InSec{lor-cpa}(\Xid{\E}{CFBH}^{F, V_0, c}_{n_L, n_C, n_E};
+ t_E, q_E, \mu_E) \le
+ 2 \cdot \InSec{prf}(F; t_E + q t_F, q) + \frac{q (q - 1)}{2^\ell}
+ \]
+ where $q = \bigl\lfloor \bigl(\mu_E + q_E (t - 1)\bigr)/t \bigr\rfloor +
+ n_E$, and $t_F$ is some small constant.
+\end{theorem}
+
+The proof is a bit involved; we postpone it until
+section~\ref{sec:cfb-proof}.
+
+\begin{corollary}
+ \label{cor:cfb-prf}
+ Let $F$, $c$ and $V_0$ be as in theorem~\ref{thm:cfb}. Then for any $t_E$,
+ $q_E$ and $\mu_E$,
+ \begin{eqnarray*}[rl]
+ \InSec{lor-cpa}(\Xid{\E}{CFB$\$$}^F; t_E, q_E, \mu_E)
+ & \le 2 \cdot \InSec{prf}(F; t_E + q t_F, q) + \frac{q (q - 1)}{2^\ell}
+ \\
+ \InSec{lor-cpa}(\Xid{\E}{CFBE}^{F, c}; t_E, q_E, \mu_E)
+ & \le 2 \cdot \InSec{prf}(F; t_E + q' t_F, q') +
+ \frac{q' (q' - 1)}{2^\ell}
+ \\
+ \InSec{lor-cpa}(\Xid{\E}{CFBL}^{F, V_0}; t_E, q_E, \mu_E)
+ & \le 2 \cdot \InSec{prf}(F; t_E + q t_F, q) + \frac{q (q - 1)}{2^\ell}
+ \\
+ \tabpause{and, if $\ell \le t$,}
+ \InSec{lor-cpa}(\Xid{\E}{CFBC}^{F, c}; t_E, q_E, \mu_E)
+ & \le 2 \cdot \InSec{prf}(F; t_E + q t_F, q) + \frac{q (q - 1)}{2^\ell}
+ \end{eqnarray*}
+ where $q = \bigl\lfloor \bigl(\mu_E + q_E (t - 1)\bigr)/t \bigr\rfloor +
+ n_E$, $q' = q + q_E$, and $t_F$ is some small constant.
+\end{corollary}
+\begin{proof}
+ Follows from theorem~\ref{thm:cfb} and proposition~\ref{prop:enc-hybrid}.
+\end{proof}
+
+\begin{corollary}
+ \label{cor:cfb-prp}
+ Let $P$ be a pseudorandom permutation on $\Bin^\ell$, and let $c$ and $V_0$
+ be as in theorem~\ref{thm:cfb}. Then for any $t_E$, $q_E$ and $\mu_E$,
+ \begin{eqnarray*}[rl]
+ \InSec{lor-cpa}(\Xid{\E}{CFB$\$$}^P; t_E, q_E, \mu_E)
+ & \le 2 \cdot \InSec{prp}(P; t_E + q t_F, q) + \frac{q (q - 1)}{2^\ell}
+ \\
+ \InSec{lor-cpa}(\Xid{\E}{CFBE}^{P, c}; t_E, q_E, \mu_E)
+ & \le 2 \cdot \InSec{prp}(P; t_E + q' t_F, q') +
+ \frac{q' (q' - 1)}{2^\ell}
+ \\
+ \InSec{lor-cpa}(\Xid{\E}{CFBL}^{P, V_0}; t_E, q_E, \mu_E)
+ & \le 2 \cdot \InSec{prp}(P; t_E + q t_F, q) + \frac{q (q - 1)}{2^\ell}
+ \\
+ \tabpause{and, if $\ell \le t$,}
+ \InSec{lor-cpa}(\Xid{\E}{CFBC}^{P, c}; t_E, q_E, \mu_E)
+ & \le 2 \cdot \InSec{prp}(P; t_E + q t_F, q) + \frac{q (q - 1)}{2^\ell}
+ \end{eqnarray*}
+ where $q = \bigl\lfloor \bigl(\mu_E + q_E (t - 1)\bigr)/t \bigr\rfloor +
+ n_E$, $q' = q + q_E$, and $t_F$ is some small constant.
+\end{corollary}
+\begin{proof}
+ Follows from corollary~\ref{cor:cfb-prf} and
+ proposition~\ref{prop:prps-are-prfs}.
+\end{proof}
+
+\subsection{Proof of theorem~\ref{thm:cfb}}
+\label{sec:cfb-proof}
+
+Our proof follows the same lines as for CBC mode: we show the ROG-CPA
+security of hybrid-CFB mode using an ideal random function, and then apply
+our earlier results to complete the proof. However, the ROG-CPA result will
+be useful later when we consider the security of OFB mode, so we shall be a
+little more formal about defining it.
+
+The garbage emitter is in some sense the `perfect' one: it emits a `correct'
+IV followed by a uniform random string of the correct length.
+
+\begin{definition}[The $W_\$$ garbage emitter]
+ Let natural numbers $n_L$, $n_C$, and $V_0 \in \Bin^\ell$ be given; then we
+ define the garbage emitter $W_\$$ as follows.
+ \begin{program}
+ Initialization: \+ \\
+ $i \gets 0$; \\
+ $v \gets V_0$;
+ \- \\[\medskipamount]
+ Garbage emitter $W_\$(m)$: \+ \\
+ \IF $i < n_L$ \THEN $v' \gets v$; \\
+ \ELSE \IF $n_L \le i < n_L + n_C$ \THEN $v' \gets c(i)$; \\
+ \ELSE \IF $n_L + n_C \le i$ \THEN $v' \getsr \Bin^\ell$; \\
+ $i \gets i + 1$; \\
+ $m' \gets t \lfloor (m + t - 1)/t\rfloor$; \\
+ $y \getsr \Bin^{m'}$; \\
+ $v \gets v' \shift{m'} y$; \\
+ \RETURN $(v', y[0 \bitsto m])$
+ \end{program}
+\end{definition}
+
+We now show that CFB mode with a random function is hard to distinguish from
+$W_\$$.
+\begin{lemma}[Pseudorandomness of CFB mode]
+ \label{lem:cfb-rog}
+ Let $\ell$, $t$, $n_L$, $n_C$, $n_E$, $q_E$, $c$, $V_0$, and $q$ be as in
+ theorem~\ref{thm:cfb}. Then, for any $t_E$ and $\mu_E$,
+ \[ \InSec{rog-cpa-$W_\$$}
+ (\Xid{\E}{CFBH}^{\Func{\ell}{t}, V_0, c}_{n_L, n_C, n_E};
+ t, q_E, \mu_E) \le
+ \frac{q (q - 1)}{2^{\ell+1}}.
+ \]
+\end{lemma}
+Theorem~\ref{thm:cfb} follows from this result by application of
+propositions \ref{prop:rog-and-lor} and~\ref{prop:enc-info-to-real}. It
+remains therefore for us to prove lemma~\ref{lem:cfb-rog}.
+
+To reduce the weight of notation, let us agree to suppress the adornments on
+$\Adv{}{}$ and $\InSec{}$ symbols. Also, let $m_L = n_L$; let $m_C$ = $n_L +
+n_C$; and let $m_E = n_L + n_C + n_E$. (Remember: the $m$s are
+cu\textit{m}ulative.)
+
+The truncation of ciphertext blocks makes matters complicated. Let us say
+that an adversary is \emph{block-respecting} if all of its plaintext queries
+are a multiple of $t$ bits in length; obviously all of the oracle responses
+for a block-respecting adversary are also a multiple of $t$ bits in length.
+\begin{claim*}
+ If $A'$ be a block-respecting adversary querying a total of $\mu_E$ bits of
+ plaintext queries; then
+ \[ \Adv{}{}(A') \le \frac{q (q - 1)}{2^{\ell+1}} \]
+ where $q = \mu_E/t$.
+\end{claim*}
+Lemma~\ref{lem:cfb-rog} follows from this claim: if $A$ is any adversary,
+then we construct a block-respecting adversary $A'$ by padding $A$'s
+plaintext queries and truncating the oracle responses; and if $A$ makes $q_E$
+queries totalling $\mu_E$ bits, then the total bits queried by $A'$ is no
+more than $\bigl\lfloor\bigl( \mu_E + q_E (t - 1) \bigr)\bigr\rfloor$ bits.
+We now proceed to the proof of the above claim.
+
+Suppose, then, that we are given a block-respecting adversary $A$ which makes
+$q$ queries to its encryption oracle. Let $F(\cdot)$ denote the application
+of the random function. We want to show that, provided all of the $F$-inputs
+are distinct, the $F$-outputs are uniformly random, and hence the CFB
+ciphertexts are uniformly random. As for the CBC case, life isn't that good
+to us: we have to deal with the case where the adversary can see that two
+$F$-inputs would have collided, and therefore that a garbage string couldn't
+have been generated by CFB encryption of his plaintext.
+
+Our notation will be similar to, yet slightly different from, that of
+section~\ref{sec:cbc-proof}.
+
+Let $q' = q - n_E$ be the number of $t$-bit plaintext blocks the adversary
+submits, and for $0 \le i < q'$, let $x_i$ be the $i$th plaintext block
+queried, and let $y_i$ be the $i$th ciphertext block returned.
+
+For $m_L \le i < m_E$, let $c_i = c(i)$ be the $i$th counter value. For $0
+\le i < q_E$ let $v_i$ be the $i$th initialization vector, i.e.,
+\[ v_i = \begin{cases}
+ V_0 & if $i = 0$ and $n_L > 0$; \\
+ v_{i-1} \shift{t} Y_{i-1}
+ & if $1 \le i < m_L$ and $Y_{i-1}$ was the ciphertext
+ from query $i - 1$; \\
+ c_i & if $m_L \le i < m_C$; \\
+ F(c_i) & if the oracle is `result', and $m_C \le i < m_E$;
+ or \\
+ R_i & for some $R_i \inr \Bin^\ell$, otherwise.
+ \end{cases}
+\]
+Note that the only difference in the $v_i$ between the `result' and `garbage'
+games occurs in the encrypted-counters phase. Furthermore, if no other
+$F$-input is equal to any $c_i$ for $m_C \le i < m_E$ then the IVs are
+identically distributed.
+
+Now, for $0 \le i < q'$, define
+\[ z_i = \begin{cases}
+ v_j & if block $i$ is the first block of the
+ $j$th query, or \\
+ z_{i-1} \shift{t} y_{i-1} & otherwise
+ \end{cases}
+\]
+and let $w_i = x_i \xor y_i$. In the `result' game, we have $w_i = F(z_i)$,
+of course. All of this notation is summarized diagrammatically in
+figure~\ref{fig:cfb-proof-notation}. The $F$-inputs are precisely the $z_i$
+and $c_i$ for $m_C \le i < m_E$.
+
+We'll denote probabilities in the `result' game as $\Pr_R[\cdot]$ and in the
+`garbage' game as $\Pr_G[\cdot]$.
+
+\begin{figure}
+ \begin{vgraphs}
+ \begin{vgraph}{cfb-notation-a}
+ [] !{<1.333cm, 0cm>: <0cm, 1cm>::}
+ {z_i} ="z" :|-@{/}_-{\ell}[r] *+[F]{F} ="F"
+ :|-@{/}_-{t}[r] {w_i} ="w" :|-@{/}_-{t}[r] *{\xor} ="xor"
+ "xor" [u] {x_i} ="x" :|-@{/}^-{t}"xor" :|-@{/}^-{t}[d] {y_i} ="y"
+ "z" [lu] {v_j} ="v" :"z"
+ "z" [ru] {z_{i-1} \shift{t} y_{i-1}} ="y" :"z"
+ "v" :@{.}|-*+\hbox{or} "y"
+ \end{vgraph}
+ \end{vgraphs}
+
+ \caption{Notation for the proof of lemma~\ref{lem:cfb-rog}.}
+ \label{fig:cfb-proof-notation}
+\end{figure}
+
+Let $C_r$ be the event, in either game, that $z_i = z_j$ for some $0 \le i <
+j < r$, or that $z_i = c_j$ for some $0 \le i < r$ and some $m_C \le j <
+m_E$.
+
+Let's assume that $C_r$ didn't happen; we want the probability that $C_{r+1}$
+did, which is just the probability that $z_r$ collides with some $z_i$ where
+$0 \le i < r$, or some $c_i$ for $m_C \le i < m_E$. Observe that, under this
+assumption, all the $w_i$, and hence the $y_i$, are uniformly distributed,
+and that therefore the two games are indistinguishable.
+
+One of the following cases holds.
+\begin{enumerate}
+\item If $r = 0$ and $m_L > 0$ then $z_r = V_0$. There is no other $z_i$ yet
+ for $z_r$ to collide with, though it might collide with some encrypted
+ counter $F(c_i)$, with probability $n_E/2^\ell$.
+\item If $z_r = c_i$ is the IV for some message $i$ where $m_L \le i < m_C$,
+ life is a bit complicated. It can't collide with $V_0$ or other $c_i$ by
+ assumption; the encrypted counters and random IVs haven't been chosen yet;
+ and either $n_C = 0$ (in which case there's nothing to do here anyway) or
+ $\ell \le t$, so there are no $z_i$ containing partial copies of $V_0$ to
+ worry about. This leaves non-IV $z_i$: again, $\ell \le t$, so $z_i =
+ y_i[t - \ell \bitsto t]$, which is random by our assumption of $\bar{C}_r$;
+ hence a collision with one of these $z_i$ occurs with probability at most
+ $r/2^\ell$.
+\item If $z_r$ is the IV for some message $i$ where $m_C \le i < m_E$, then
+ it can collide with previous $z_i$ or either previous or future $c_i$. We
+ know, however, that no $F$-input has collided with $c_i$, so in the
+ `result' game, $z_r = F(c_r)$ is uniformly distributed; in the `garbage'
+ game, $W_\$$ generates $z_r$ at random anyway. It collides, therefore,
+ with probability at most $(r + n_E)/2^\ell$.
+\item If $z_r$ is the IV for some message $i$ where $m_E \le i < q'$ then
+ $z_r$ was chosen uniformly at random. Hence it collides with probability
+ at most $(r + n_E)/2^\ell$.
+\item Finally, either $z_r$ is not the IV for a message, or it is, but the
+ message number $i < n_L$, so in either case, $z_r = z_{r-1} \shift{t}
+ y_{r-1}$. We have two subcases to consider.
+ \begin{enumerate}
+ \item If $1 \le r < \ell/t$ (we dealt with the case $r = 0$ above) then
+ some of $V_0$ remains in the shift register. If $z_r$ collides with some
+ $z_i$, for $0 \le i < r$, then we must have $z_r[0 \bitsto \ell - t r] =
+ z_i[0 \bitsto \ell - t r]$; but $z_r[0 \bitsto \ell - t r] = V_0[t r
+ \bitsto \ell]$, and $z_i[0 \bitsto \ell - t r] = V_0[t i \bitsto \ell - t
+ (r - i)]$, i.e., we have found a $t$-sliding of $V_0$, which is
+ impossible by hypothesis. Hence, $z_r$ cannot collide with any earlier
+ $z_i$. Also by hypothesis, $n_C = n_E = 0$ if $\ell > t$, so $z_r$
+ cannot collide with any counters $c_i$.
+ \item Suppose, then, that $r \ge \ell/t$. For $0 \le j < \ell/t$, let $H_j
+ = \ell - t j$, $L_j = \max(0, H_j - t)$, and $N_j = H_j - L_j$. (Note
+ that $\sum_{0\le j<\ell/t} N_j = \ell$.) Then $z_r[L_j \bitsto H_j] =
+ y_{r-j-1}[t - N_j \bitsto t]$; but the $y_i$ for $i < r$ are uniformly
+ distributed. Thus, $z_r$ collides with some specific other value $z'$
+ only with probability $1/2^{\sum_j N_j} = 1/2^\ell$. The overall
+ collision probablity for $z_r$ is then at most $(r + n_E)/2^\ell$.
+ \end{enumerate}
+\end{enumerate}
+In all these cases, it's clear that the collision probability is no more than
+$(r + n_E)/2^\ell$.
+
+The probability that there is a collision during the course of the game is
+$\Pr[C_{q'}]$, which we can now bound thus:
+\begin{equation}
+ \Pr[C_q'] \le \sum_{0<i\le q'} \Pr[C_i | \bar{C}_{i-1}]
+ \le \sum_{0<i\le q'} \frac{i + n_E}{2^\ell}.
+\end{equation}
+If we set $i' = i + n_E$, then we get
+\begin{equation}
+ \Pr[C_q'] \le \sum_{0\le i'\le q} \frac{i'}{2^\ell}
+ = \frac{q (q - 1)}{2^{\ell+1}}.
+\end{equation}
+Finally, then, we can apply the same argument as we used at the end of
+section~\ref{sec:cbc-proof} to show that
+\begin{equation}
+ \Adv{}{}(A') \le \frac{q (q - 1)}{2^{\ell+1}}
+\end{equation}
+as claimed. This completes the proof.
+
+%%%--------------------------------------------------------------------------
+
+\section{OFB mode encryption}
+\label{sec:ofb}
+
+\subsection{Description}
+\label{sec:ofb-desc}
+
+Suppose $F$ is an $\ell$-bit-to-$L$-bit pseudorandom function, and let $t \le
+L$. OFB mode works as follows. Given a message $X$, we divide it into
+$t$-bit blocks $x_0$, $x_1$, $\ldots$, $x_{n-1}$. Choose an initialization
+vector $v \in \Bin^\ell$. We maintain a \emph{shift register} $s_i$, whose
+initial value is $v$. To encrypt a block $x_i$, we XOR it with the result
+$z_i$ of passing the shift register through the PRF, forming $y_i$, and then
+update the shift register by shifting in the PRF output $z_i$. That
+is,
+\begin{equation}
+ s_0 = v \qquad
+ z_i = F_K(s_i) \qquad
+ y_i = x_i \xor z_i \qquad
+ s_{i+1} = s_i \shift{t} z_i \ \text{(for $0 \le i < n$)}.
+\end{equation}
+Decryption is precisely the same operation.
+
+Also, we observe that the final plaintext block needn't be $t$ bits long: we
+can pad it out to $t$ bits and truncate the result without affecting our
+ability to decrypt.
+
+\begin{figure}
+ \begin{cgraph}{ofb-mode}
+ [] !{<0.425cm, 0cm>: <0cm, 0.5cm>::}
+ *+=(2, 0)+[F]{\mathstrut v} ="v" :|<>(0.35)@{/}_<>(0.35){\ell}[rrrrr]
+ *+[o][F]{\shift{t}} ="shift"
+ [ll] :|-@{/}^-{\ell}[dd] *+[F]{E} ="e" [ll] {K} :"e"
+ :|-@{/}^-{t}[ddd] *{\xor} ="xor"
+ [lll] *+=(2, 0)+[F]{\mathstrut x_0} :|-@{/}_-{t} "xor"
+ :|-@{/}^-{t}[dd] *+=(2, 0)+[F]{\mathstrut y_0}
+ "xor" [u] :`r "shift" "shift"|-@{/}_-{t}
+ :|-@{/}_-{\ell}[rrrrrrr] *+[o][F]{\shift{t}} ="shift"
+ [ll] :|-@{/}^-{\ell}[dd] *+[F]{E} ="e" [ll] {K} :"e"
+ :|-@{/}^-{t}[ddd] *{\xor} ="xor"
+ [lll] *+=(2, 0)+[F]{\mathstrut x_1} :|-@{/}_-{t} "xor"
+ :|-@{/}^-{t}[dd] *+=(2, 0)+[F]{\mathstrut y_1}
+ "xor" [u] :`r "shift" "shift"|-@{/}_-{t}
+ :@{-->}|-@{/}_-{\ell}[rrrrrrr] *+[o][F]{\shift{t}} ="shift"
+ [ll] :@{-->}|-@{/}^-{\ell}[dd] *+[F]{E} ="e" [ll] {K} :"e"
+ :@{-->}|-@{/}^-{t}[ddd] *{\xor} ="xor"
+ [lll] *+=(2, 0)+[F--]{\mathstrut x_i} :@{-->}|-@{/}_-{t} "xor"
+ :@{-->}|-@{/}^-{t}[dd] *+=(2, 0)+[F--]{\mathstrut y_i}
+ "xor" [u] :@{-->} `r "shift" "shift"|-@{/}_-{t}
+ [rrrrrdd] *+[F]{E} ="e"
+ "shift" :@{-->}`r "e" |-@{/}_-{\ell} "e"
+ [ll] {K} :"e"
+ :|-@{/}^-{t}[ddd] *{\xor} ="xor"
+ [lll] *+=(2, 0)+[F]{\mathstrut x_{n-1}} :|-@{/}_-{t} "xor"
+ :|-@{/}^-{t}[dd] *+=(2, 0)+[F]{\mathstrut y_{n-1}}
+ \end{cgraph}
+
+ \caption{Encryption using OFB mode}
+ \label{fig:ofb}
+\end{figure}
+
+\begin{definition}[OFB algorithms]
+ For any function $F\colon \Bin^\ell \to \Bin^t$, any initialization vector
+ $v \in \Bin^\ell$, any plaintext $x \in \Bin^*$ and any ciphertext $y \in
+ \Bin^*$, we define PRF encryption mode $\id{OFB} = (\id{ofb-encrypt},
+ \id{ofb-decrypt})$ as follows:
+ \begin{program}
+ Algorithm $\id{ofb-encrypt}(F, v, x)$: \+ \\
+ $s \gets v$; \\
+ $L \gets |x|$; \\
+ $x \gets x \cat 0^{t\lceil L/t \rceil - L}$; \\
+ $y \gets \emptystring$; \\
+ \FOR $i = 0$ \TO $(|x| - t')/t$ \DO \\ \ind
+ $x_i \gets x[ti \bitsto t(i + 1)]$; \\
+ $z_i \gets F(s)$; \\
+ $y_i \gets x_i \xor z_i$; \\
+ $s \gets s \shift{t} z_i$; \\
+ $y \gets y \cat y_i$; \- \\
+ \RETURN $(s, y[0 \bitsto L])$;
+ \next
+ Algorithm $\id{ofb-decrypt}(F, v, y)$: \+ \\
+ \RETURN $\id{ofb-encrypt}(F, v, y)$;
+ \end{program}
+ We now define the schemes $\Xid{\E}{OFB$\$$}^F$, $\Xid{\E}{OFBC}^{F, c}$,
+ $\Xid{\E}{OFBE}^{F, c}$, and $\Xid{\E}{OFBL}^{F, V_0}$ according to
+ definition~\ref{def:enc-scheme}; and we define the hybrid scheme
+ $\Xid{\E}{OFBH}^{F, V_0, c}_{n_L, n_C, n_E}$ according to
+ definition~\ref{def:enc-hybrid}.
+\end{definition}
+
+\begin{remark}[Similarity to CFB mode]
+ \label{rem:ofb-like-cfb}
+ OFB mode is strongly related to CFB mode: we can OFB encrypt a message $x$
+ by \emph{CFB-encrypting} the all-zero string $0^{|x|}$ with the same key
+ and IV. That is, we could have written $\id{ofb-encrypt}$ and
+ $\id{ofb-decrypt}$ like this:
+ \begin{program}
+ Algorithm $\id{ofb-encrypt}(F, v, x)$: \+ \\
+ $(s, z) \gets \id{cfb-encrypt}(F, v, 0^{|x|})$; \\
+ \RETURN $(s, x \xor z)$;
+ \next
+ Algorithm $\id{ofb-decrypt}(F, v, y)$: \+ \\
+ \RETURN $\id{ofb-encrypt}(F, v, y)$;
+ \end{program}
+ We shall use this fact to prove the security of OFB mode in the next
+ section.
+\end{remark}
+
+\subsection{Security of OFB mode}
+
+\begin{theorem}[Security of OFB mode]
+ \label{thm:ofb}
+ Let $F$ be a pseudorandom function from $\Bin^\ell$ to $\Bin^t$; let $V_0
+ \in \Bin^\ell$ be a non-$t$-sliding string; let $c$ be a generalized
+ counter in $\Bin^\ell$; and let $n_L$, $n_C$, $n_E$ and $q_E$ be
+ nonnegative integers; and furthermore suppose that
+ \begin{itemize}
+ \item $n_L + n_C + n_E \le q_E$,
+ \item $n_L = 0$, or $n_C = n_E = 0$, or $\ell \le t$ and $V_0 \ne c(i)$
+ for any $n_L \le i < n_L + n_C + n_E$, and
+ \item either $n_C = 0$ or $\ell \le t$.
+ \end{itemize}
+ Then, for any $t_E$ and $\mu_E$, and whenever
+ we have
+ \[ \InSec{lor-cpa}(\Xid{\E}{OFBH}^{F, V_0, c}_{n_L, n_C, n_E};
+ t_E, q_E, \mu_E) \le
+ 2 \cdot \InSec{prf}(F; t_E + q t_F, q) + \frac{q (q - 1)}{2^\ell}
+ \]
+ where $q = \bigl\lfloor \bigl(\mu_E + q_E (t - 1)\bigr)/t \bigr\rfloor +
+ n_E$, and $t_F$ is some small constant.
+\end{theorem}
+\begin{proof}
+ We claim that
+ \[ \InSec{rog-cpa-$W_\$$}
+ (\Xid{\E}{OFBH}^{\Func{\ell}{t}, V_0, c}_{n_L, n_C, n_E};
+ t, q_E, \mu_E) \le
+ \frac{q (q - 1)}{2^{\ell+1}}.
+ \]
+ This follows from lemma~\ref{lem:cfb-rog}, which makes the same statement
+ about CFB mode, and the observation in remark~\ref{rem:ofb-like-cfb}.
+ Suppose $A$ attempts to distinguish OFBH encryption from $W_\$$. We define
+ the adversary $B$ which uses $A$ to attack CFBH encryption, as follows:
+ \begin{program}
+ Adversary $B^{E(\cdot)}$: \+ \\
+ \RETURN $A^{\id{ofb}(\cdot)}$; \-
+ \next
+ Function $\id{ofb}(x)$: \+ \\
+ $(v, z) \gets E(0^{|x|})$; \\
+ \RETURN $(v, x \xor z)$;
+ \end{program}
+ Now we apply proposition~\ref{prop:rog-and-lor}; the theorem follows.
+\end{proof}
+
+\begin{corollary}
+ \label{cor:ofb-prf}
+ Let $F$, $c$ and $V_0$ be as in theorem~\ref{thm:ofb}. Then for any $t_E$,
+ $q_E$ and $\mu_E$,
+ \begin{eqnarray*}[rl]
+ \InSec{lor-cpa}(\Xid{\E}{OFB$\$$}^F; t_E, q_E, \mu_E)
+ & \le 2 \cdot \InSec{prf}(F; t_E + q t_F, q) + \frac{q (q - 1)}{2^\ell}
+ \\
+ \InSec{lor-cpa}(\Xid{\E}{OFBE}^{F, c}; t_E, q_E, \mu_E)
+ & \le 2 \cdot \InSec{prf}(F; t_E + q' t_F, q') +
+ \frac{q' (q' - 1)}{2^\ell}
+ \\
+ \InSec{lor-cpa}(\Xid{\E}{OFBL}^{F, V_0}; t_E, q_E, \mu_E)
+ & \le 2 \cdot \InSec{prf}(F; t_E + q t_F, q) + \frac{q (q - 1)}{2^\ell}
+ \\
+ \tabpause{and, if $\ell \le t$,}
+ \InSec{lor-cpa}(\Xid{\E}{OFBC}^{F, c}; t_E, q_E, \mu_E)
+ & \le 2 \cdot \InSec{prf}(F; t_E + q t_F, q) + \frac{q (q - 1)}{2^\ell}
+ \end{eqnarray*}
+ where $q = \bigl\lfloor \bigl(\mu_E + q_E (t - 1)\bigr)/t \bigr\rfloor +
+ n_E$, $q' = q + q_E$, and $t_F$ is some small constant.
+\end{corollary}
+\begin{proof}
+ Follows from theorem~\ref{thm:ofb} and proposition~\ref{prop:enc-hybrid}.
+\end{proof}
+
+\begin{corollary}
+ \label{cor:ofb-prp}
+ Let $P$ be a pseudorandom permutation on $\Bin^\ell$, and let $c$ and $V_0$
+ be as in theorem~\ref{thm:ofb}. Then for any $t_E$, $q_E$ and $\mu_E$,
+ \begin{eqnarray*}[rl]
+ \InSec{lor-cpa}(\Xid{\E}{OFB$\$$}^P; t_E, q_E, \mu_E)
+ & \le 2 \cdot \InSec{prp}(P; t_E + q t_F, q) + \frac{q (q - 1)}{2^\ell}
+ \\
+ \InSec{lor-cpa}(\Xid{\E}{OFBE}^{P, c}; t_E, q_E, \mu_E)
+ & \le 2 \cdot \InSec{prp}(P; t_E + q' t_F, q') +
+ \frac{q' (q' - 1)}{2^\ell}
+ \\
+ \InSec{lor-cpa}(\Xid{\E}{OFBL}^{P, V_0}; t_E, q_E, \mu_E)
+ & \le 2 \cdot \InSec{prp}(P; t_E + q t_F, q) + \frac{q (q - 1)}{2^\ell}
+ \\
+ \tabpause{and, if $\ell \le t$,}
+ \InSec{lor-cpa}(\Xid{\E}{OFBC}^{P, c}; t_E, q_E, \mu_E)
+ & \le 2 \cdot \InSec{prp}(P; t_E + q t_F, q) + \frac{q (q - 1)}{2^\ell}
+ \end{eqnarray*}
+ where $q = \bigl\lfloor \bigl(\mu_E + q_E (t - 1)\bigr)/t \bigr\rfloor +
+ n_E$, $q' = q + q_E$, and $t_F$ is some small constant.
+\end{corollary}
+\begin{proof}
+ Follows from corollary~\ref{cor:ofb-prf} and
+ proposition~\ref{prop:prps-are-prfs}.
+\end{proof}
+
+%%%--------------------------------------------------------------------------
+
+\section{CBCMAC mode message authentication}
+\label{sec:cbcmac}
+
+
+
+\begin{figure}
+ \begin{cgraph}{cbc-mac}
+ []!{<0.425cm, 0cm>: <0cm, 0.75cm>::}
+ *+=(2, 0)+[F]{\mathstrut x_0}
+ :`d [dr] [rrr] *+[F]{E} ="e" [d] {K} :"e"
+ :[rrr] *{\xor} ="xor"
+ [u] *+=(2, 0)+[F]{\mathstrut x_1} :"xor"
+ :[rrr] *+[F]{E} ="e" [d] {K} :"e"
+ :@{-->}[rrr] *{\xor} ="xor"
+ [u] *+=(2, 0)+[F--]{\mathstrut x_i} :@{-->}"xor"
+ :@{-->}[rrr] *+[F]{E} ="e" [d] {K} :@{-->}"e"
+ :@{-->}[rrr] *{\xor} ="xor"
+ [u] *+=(2, 0)+[F]{\mathstrut x_{n-1}} :"xor"
+ :[rrr] *+[F]{E} ="e" [d] {K} :"e"
+ :[rrr] *+=(2, 0)+[F]{\mathstrut \tau}
+ \end{cgraph}
+
+ \caption{Message authentication using CBCMAC mode}
+ \label{fig:cbcmac}
+\end{figure}
+
+\fixme
+Alas, it's been so long since I've picked this up that I've (a) forgotten how
+the proof for this mode went, and (b) lost my notes. You'll either have to
+wait, or I'll have to drop this bit.
+
+%%%--------------------------------------------------------------------------
+
+\section{Ackonowledgements}
+
+Thanks to Clive Jones for his suggestions on notation, and his help in
+structuring the proofs.
+
+%%%----- That's all, folks --------------------------------------------------
+
+\bibliography{mdw-crypto,cryptography2000,cryptography,rfc}
+
+\end{document}
+
+%%% Local Variables:
+%%% mode: latex
+%%% TeX-master: t
+%%% End:
~mdw / doc / modes / commitdiff