From fb439f817e3b8e53a422217083ba28790dce4f3e Mon Sep 17 00:00:00 2001 From: Mark Wooding Date: Wed, 1 Mar 2006 13:10:38 +0000 Subject: [PATCH] Check stuff in. --- Makefile | 18 + modes.tex | 2259 +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ 2 files changed, 2277 insertions(+) create mode 100644 Makefile create mode 100644 modes.tex diff --git a/Makefile b/Makefile new file mode 100644 index 0000000..1d444b0 --- /dev/null +++ b/Makefile @@ -0,0 +1,18 @@ +all: modes.ps modes.pdf modes.dvi + +modes.dvi: modes.tex + latex modes.tex + bibtex modes.aux + latex modes.tex + latex modes.tex + +modes.ps: modes.dvi + dvips -o $@.new $< + mv $@.new $@ + +modes.pdf: modes.ps + gs -sDEVICE=pdfwrite -sOutputFile=$@.new -q -dBATCH -dNOPAUSE $< + mv $@.new $@ + +clean: + rm -f *.aux *.toc *.blg *.bbl *.dvi *.ps *.pdf *.lof *.lot *.log diff --git a/modes.tex b/modes.tex new file mode 100644 index 0000000..94e57b1 --- /dev/null +++ b/modes.tex @@ -0,0 +1,2259 @@ +%%% -*-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: <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: <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: <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: -- 2.11.0