Check stuff in.

[doc/modes] / modes.tex

%%% -*-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: