5 %%% Standard block cipher modes of operation
7 %%% (c) 2003 Mark Wooding
10 \newif\iffancystyle\fancystylefalse
12 \errorcontextlines=
\maxdimen
13 \showboxdepth=
\maxdimen
14 \showboxbreadth=
\maxdimen
18 [a4paper, article,
10pt, numbering, noherefloats, notitlepage
]
20 \usepackage[T1]{fontenc}
21 \usepackage[palatino, helvetica, courier, maths=cmr
]{mdwfonts
}
22 \usepackage[within = subsection, mdwmargin
]{mdwthm
}
25 \PassOptionsToPackage{dvips}{xy
}
27 \documentclass[a4paper]{llncs
}
31 \PassOptionsToPackage{show
}{slowbox
}
32 %\PassOptionsToPackage{hide}{slowbox}
33 \usepackage{mdwtab, mathenv, mdwmath, crypto
}
35 \usepackage{amssymb, amstext
}
36 \usepackage{url, multicol
}
37 \DeclareUrlCommand\email{\urlstyle{tt
}}
43 \title{New proofs for old modes
}
45 \author{Mark Wooding \\
\email{mdw@distorted.org.uk
}}
48 \institute{\email{mdw@distorted.org.uk
}}
52 \bibliographystyle{mdwalpha
}
53 \let\epsilon\varepsilon
54 \let\emptyset\varnothing
55 \let\le\leqslant\let\leq\le
56 \let\ge\geqslant\let\geq\ge
57 \numberwithin{table
}{section
}
58 \numberwithin{figure
}{section
}
60 \bibliographystyle{plain
}
61 \expandafter\let\csname claim*
\endcsname\claim
62 \expandafter\let\csname endclaim*
\endcsname\endclaim
65 %%\newcommand{\Nupto}[1]{\N_{<{#1}}}
66 \newcommand{\Nupto}[1]{\
{0,
1,
\ldots,
#1 -
1\
}}
68 \let\emptystring\lambda
69 \edef\Pr{\expandafter\noexpand\Pr\nolimits}
70 \newcommand{\bitsto}{\mathbin{..
}}
71 \newcommand{\shift}[1]{\lsl_{#1}}
72 \newcommand{\E}{{\mathcal{E
}}}
73 \newcommand{\M}{{\mathcal{M
}}}
77 \let\makelabel\textit%
78 \desclabelstyle\multilinelabel%
83 \def\fixme{\marginpar{FIXME
}}
84 \def\hex#1{\texttt{#1}_
{x
}}
86 \newslowboxenv{cgraph
}{\par$$
}{\begin{graph
}}{\end{graph
}}{$$
\par}
87 \newslowboxenv{vgraph
}
88 {\hfil$
\vcenter\bgroup\hbox\bgroup}
92 \newenvironment{vgraphs
}{\hbox to
\hsize\bgroup}{\hfil\egroup}
96 %%%--------------------------------------------------------------------------
101 We study the standard block cipher modes of operation: CBC, CFB, OFB, and
102 CBCMAC and analyse their security. We don't look at ECB other than briefly
103 to note its insecurity, and we have no new results on counter mode. Our
104 results improve over those previously published in that (a) our bounds are
105 better, (b) our proofs are shorter and easier, (c) the proofs correct
106 errors we discovered in previous work, or some combination of these. We
107 provide a new security notion for symmetric encryption which turns out to
108 be rather useful when analysing block cipher modes. Finally, we define a
109 new condition for initialization vectors, introducing the concept of a
110 `generalized counter', and proving that generalized counters suffice for
111 security in (full-width) CFB and OFB modes and that generalized counters
112 encrypted using the block cipher (with the same key) suffice for all the
113 encryption modes we study.
118 \columnsep=
2em
\columnseprule=
0pt
119 \tableofcontents[\begin{multicols
}{2}\raggedright][\end{multicols
}]
120 \listoffigures[\begin{multicols
}{2}\raggedright][\end{multicols
}]
121 \listoftables[\begin{multicols
}{2}\raggedright][\end{multicols
}]
125 %%%--------------------------------------------------------------------------
127 \section{Introduction
}
130 \subsection{Block cipher modes
}
132 Block ciphers -- keyed pseudorandom permutations -- are essential
133 cryptographic tools, widely used for bulk data encryption and to an
134 increasing extent for message authentication. Because the efficient block
135 ciphers we have operate on fixed and relatively small strings of bits --
64
136 or
128 bits at a time, one needs a `mode of operation' to explain how to
137 process longer messages.
139 A collection of encryption modes, named ECB, CBC, CFB and OFB, were defined
140 in
\cite{FIPS81
}. Of these, ECB -- simply divide the message into blocks and
141 process them independently with the block cipher -- is just insecure and not
142 to be recommended for anything much. We describe the other three, and
143 analyse their security using the standard quantitative provable-security
144 approach. All three require an `initialization vector' or `IV' which
145 diversifies the output making it hard to correlate ciphertexts with
146 plaintexts. We investigate which conditions on these IVs suffice for secure
149 We also examine the CBC-MAC message-authentication scheme, because it's
150 intimately related to the CBC encryption scheme and the same techniques we
151 used in the analysis of the latter apply to the former.
153 \subsection{Previous work
}
155 The first quantitative security proof for a block cipher mode is the analysis
156 of CBCMAC of
\cite{Bellare:
1994:SCB
}. Security proofs for the encryption
157 modes CBC and CTR appeared in
\cite{Bellare:
2000:CST
}, which also defines and
158 relates the standard security notions of symmetric encryption. The authors
159 of
\cite{Alkassar:
2001:OSS
} offer a proof of CFB mode, though we believe it
160 to be flawed in a number of respects.
162 \subsection{Our contribution
}
164 We introduce a new security notion for symmetric encryption, named
165 `result-or-garbage', or `ROG-CPA', which generalizes the `real-or-random'
166 notion of
\cite{Bellare:
2000:CST
} and the `random-string' notion of
167 \cite{Rogaway:
2001:OCB
}. Put simply, it states that an encryption scheme is
168 secure if an adversary has difficulty distinguishing true ciphertexts from
169 strings chosen by an algorithm which is given only the
\emph{length
} of the
170 adversary's plaintext. This turns out to be just the right tool for
171 analysing our encryption modes. We relate this notion to the standard
172 `left-or-right' notion and, thereby, all the others.
174 Our bound for CBC mode improves over the `tight' bound proven in
175 \cite{Bellare:
2000:CST
} by almost a factor of two. The difference comes
176 because they analyse the construction as if it were built from a PRF and add
177 in a `PRP-used-as-a-PRF' correction term: our analysis considers the effect
178 of a permutation directly. We prove that CBC mode is still secure if an
179 encrypted counter is used in place of a random string as the IV for each
180 message. Finally, we show that the `ciphertext stealing' technique is
183 For CFB, we first discuss the work of
\cite{Alkassar:
2001:OSS
}, who offer a
184 proof for both CFB mode and an optimized variant which enhances the
185 error-recovery properties of standard CFB. We believe that their proof is
186 defective in a number of ways. We then offer our own proof. Our bound is a
187 factor of two worse than theirs; however, we believe that fixing their proof
188 introduces this missing factor of two: that is, that our `poorer' bound
189 reflects the true security of CFB mode more accurately. We show that
190 full-width CFB is secure if the IV is any `generalized counter', and that
191 both full-width and truncated $t$-bit CFB are secure if the IV is an
192 encrypted counter. We also show that, unlike CBC mode, it is safe to `carry
193 over' the final shift-register value from the previous message as the IV for
196 OFB mode is in fact a simple modification to CFB mode, and we prove the
197 security of OFB by relating it to CFB.
199 Finally, for CBCMAC, we analyse it using
\emph{both
} pseudorandom functions
200 \emph{and
} pseudorandom permutations, showing that, in fact, using a block
201 cipher rather than a PRF reduces the security hardly at all. Also, we
202 improve on the (groundbreaking) work of
\cite{Bellare:
1994:SCB
} firstly by
203 improving the security bound by a factor of almost four, and secondly by
204 extending the message space from a space of fixed-length messages to
205 \emph{any
} prefix-free set of strings.
207 As a convenient guide, our security bounds are summarized in
208 table~
\ref{tab:summary
}.
212 \vbox to
\baselineskip{\vskip\baselineskip\vskip2pt\hbox{#1}\vss}}
213 \def\none{\multicolumn{1}{c|
}{---
}}
216 {| c | ?>
{\hack}c | c | >
{\displaystyle} Mc | >
{\displaystyle} Mc |
}
218 \multicolumn{1}{|c|
}{\lower{\bfseries Mode
}} &
219 \multicolumn{1}{c|
}{\lower{\bfseries Section
}} &
220 \multicolumn{1}{c|
}{\lower{\bfseries Notion
}} &
221 \multicolumn{2}{c|
}{\bfseries Security with
} \\
\hlx{v
[4]zc
{4-
5}v
}
223 \multicolumn{1}{c|
}{\bfseries $(t, q,
\epsilon)$-PRF
} &
224 \multicolumn{1}{c|
}{\bfseries $(t, q,
\epsilon)$-PRP
}
226 CBC &
\ref{sec:cbc
} & LOR-CPA &
228 2\epsilon +
\frac{q (q -
1)
}{2^
\ell - q
} \\
\hlx{vvhvv
}
229 CFB &
\ref{sec:cfb
} & LOR-CPA &
230 2 \epsilon +
\frac{q (q -
1)
}{2^
\ell} &
231 2 \epsilon +
\frac{q (q -
1)
}{2^
{\ell-
1}} \\
\hlx{vvhvv
}
232 OFB &
\ref{sec:ofb
} & LOR-CPA &
233 2 \epsilon +
\frac{q (q -
1)
}{2^
\ell} &
234 2 \epsilon +
\frac{q (q -
1)
}{2^
{\ell-
1}} \\
\hlx{vvhvv
}
235 CBCMAC &
\ref{sec:cbcmac
} & SUF-CMA &
236 \epsilon +
\frac{q (q -
1) +
2 q_V
}{2^
{\ell+
1}} &
238 \frac{q (q -
1)
}{2 \cdot (
2^
\ell - q)
} +
239 \frac{q_V
}{2^
\ell - q_T
} \\
\hlx{vvh
}
242 \caption[Summary of our results
]
243 {Summary of our results. In all cases, $q$ is the number of block
244 cipher applications used in the game.
}
248 \subsection{The rest of the paper
}
250 In section~
\ref{sec:prelim
} we define the various bits of notation and
251 terminology we'll need in the rest of the paper. The formal definitions are
252 given for our new `result-or-garbage' security notion, and for our
253 generalized counters. In section~
\ref{sec:cbc
} we study CBC mode, and
254 ciphertext stealing. In section~
\ref{sec:cfb
} we study CFB mode. In
255 section~
\ref{sec:ofb
} we study OFB mode. In section~
\ref{sec:cbcmac
} we
256 study the CBCMAC message authentication scheme.
258 %%%--------------------------------------------------------------------------
260 \section{Notation and definitions
}
263 \subsection{Bit strings
}
264 \label{sec:bitstrings
}
266 Most of our notation for bit strings is standard. The main thing to note is
267 that everything is zero-indexed.
270 \item We write $
\Bin = \
{0,
1\
}$ for the set of binary digits. Then $
\Bin^n$
271 is the set of $n$-bit strings, and $
\Bin^*$ is the set of all (finite) bit
273 \item If $x$ is a bit string then $|x|$ is the length of $x$. If $x
\in
274 \Bin^n$ then $|x| = n$.
275 \item If $x, y
\in \Bin^n$ are strings of bits of the same length then $x
276 \xor y
\in \Bin^n$ is their bitwise XOR.
277 \item If $x$ is a bit string and $i$ is an integer satisfying $
0 \le i < |x|$
278 then $x
[i
]$ is the $i$th bit of $x$. If $a$ and $b$ are integers
279 satisfying $
0 \le a
\le b
\le |x|$ then $x
[a
\bitsto b
]$ is the substring
280 of $x$ beginning with bit $a$ and ending just
\emph{before
} bit $b$. We
281 have $|x
[i
]| =
1$ and $|x
[a
\bitsto b
]| = b - a$; if $y = x
[a
\bitsto b
]$
282 then $y
[i
] = x
[a + i
]$.
283 \item If $x$ and $y$ are bit strings then $x y$ is the result of
284 concatenating $y$ to $x$. If $z = x y$ then $|z| = |x| + |y|$; $z
[i
] =
285 x
[i
]$ if $
0 \le i < |x|$ and $z
[i
] = y
[i - |x|
]$ if $|x|
\le i < |x| +
286 |y|$. Sometimes, for clarity (e.g., to distinguish from integer
287 multiplication) we write $x
\cat y$ instead of $x y$.
288 \item The empty string is denoted $
\emptystring$. We have $|
\emptystring| =
289 0$, and $x = x
\emptystring =
\emptystring x$ for all strings $x
291 \item If $x$ is a bit string and $n$ is a natural number then $x^n$ is the
292 result of concatenating $x$ to itself $n$ times. We have $x^
0 =
293 \emptystring$ and if $n >
0$ then $x^n = x^
{n-
1} \cat x = x
\cat x^
{n-
1}$.
294 \item If $x$ and $y$ are bit strings, $|x| =
\ell$, and $|y| = t$, then we
295 define $x
\shift{t
} y$ as:
296 \
[ x
\shift{t
} y = (x y)
[t
\bitsto t +
\ell] =
\begin{cases
}
297 x
[t
\bitsto \ell] \cat y & if $t <
\ell$, or \\
298 y
[t -
\ell \bitsto t
] & if $t
\ge \ell$.
300 Observe that, if $z = x
\shift{t
} y$ then $|z| = |x| =
\ell$ and
301 \
[ z
[i
] = (x y)
[i + t
] =
\begin{cases
}
302 x
[i + t
] & if $
0 \le i <
\ell - t$, or \\
303 y
[i + t -
\ell] & if $
\min(
0,
\ell - t)
\le i <
\ell$.
305 Obviously $x
\shift{0} \emptystring = x$, and if $|x| = |y| = t$ then $x
306 \shift{t
} y = y$. Finally, if $|y| = t$ and $|z| = t'$ then $(x
\shift{t
}
307 y)
\shift{t'
} z = x
\shift{t + t'
} (y z)$.
310 \subsection{Other notation
}
311 \label{sec:miscnotation
}
315 \item If $n$ is any natural number, then $
\Nupto{n
}$ is the set $\
{\, i
\in
316 \Z \mid 0 \le i < n \,\
} = \
{ 0,
1,
\ldots, n \
}$.
318 \item The symbol $
\bot$ (`bottom') is a value different from every bit
320 \item We write $
\Func{l
}{L
}$ as the set of all functions from $
\Bin^l$ to
321 $
\Bin^L$, and $
\Perm{l
}$ as the set of all permutations on $
\Bin^l$.
324 \subsection{Algorithm descriptions
}
325 \label{sec:algorithms
}
327 An
\emph{adversary
} is a probabilistic algorithm which attempts (possibly) to
328 `break' a cryptographic scheme. We will often provide adversaries with
329 oracles which compute values with secret data. The
\emph{running time
} of an
330 adversary conventionally includes the size of the adversary's description:
331 this is an attempt to `charge' the adversary for having large precomputed
334 Most of the notation used in the algorithm descriptions should be obvious.
335 We briefly note a few features which may be unfamiliar.
337 \item The notation $a
\gets x$ denotes the action of assigning the value $x$
339 \item We write oracles as superscripts, with dots marking where inputs to
340 the oracle go, e.g., $A^
{O(
\cdot)
}$.
341 \item The notation $a
\getsr X$, where $X$ is a finite set, denotes the
342 action of assigning to $a$ a random value $x
\in X$ according to the
343 uniform probability distribution on $X$; i.e., following $a
\getsr X$, we
344 have $
\Pr[a = x
] =
1/|X|$ for any $x
\in X$.
346 The notation is generally quite sloppy about types and scopes. We don't
347 think these informalities cause much confusion, and they greatly simplify the
348 presentation of the algorithms.
350 \subsection{Pseudorandom functions and permutations
}
351 \label{sec:prfs-and-prps
}
353 Our definitions of pseudorandom functions and permutations are standard. We
354 provide them for the sake of completeness.
356 \begin{definition
}[Pseudorandom function family
]
358 A
\emph{pseudorandom function family (PRF)
} $F = \
{F_K\
}_K$ is a collection
359 of functions $F_K
\colon \Bin^
\ell \to \Bin^L$ indexed by a
\emph{key
} $K
360 \in \keys F$. If $A$ is any adversary, we define $A$'s
\emph{advantage in
361 distinguishing $F$ from a random function
} to be
363 \Pr[K
\getsr \keys F: A^
{F_K(
\cdot)
} =
1] -
364 \Pr[R
\getsr \Func{\ell}{L
}: A^
{R(
\cdot)
} =
1]
366 where the probability is taken over all choices of keys, random functions,
367 and the internal coin-tosses of $A$. The
\emph{insecurity of $F$
} is given
369 \
[ \InSec{prf
}(F; t, q) =
\max_A \Adv{prf
}{F
}(A) \
]
370 where the maximum is taken over all adversaries which run in time~$t$ and
371 issue at most $q$ oracle queries. If $
\InSec{prf
}(F; t, q)
\le \epsilon$
372 then we say that $F$ is a $(t, q,
\epsilon)$-PRF.
375 \begin{definition
}[Pseudorandom permutation family
]
377 A
\emph{pseudorandom permutation family (PRP)
} $E = \
{E_K\
}_K$ is a
378 collection of permutations $E_K
\colon \Bin^
\ell \to \Bin^
\ell$ indexed by a
379 \emph{key
} $K
\in \keys E$. If $A$ is any adversary, we define $A$'s
380 \emph{advantage in distinguishing $E$ from a random permutation
} to be
382 \Pr[K
\getsr \keys E: A^
{E_K(
\cdot)
} =
1] -
383 \Pr[P
\getsr \Perm{\ell}: A^
{P(
\cdot)
} =
1]
385 where the probability is taken over all choices of keys, random
386 permutations, and the internal coin-tosses of $A$. Note that the adversary
387 is not allowed to query the inverse permutation $E^
{-
1}_K(
\cdot)$ or
388 $P^
{-
1}(
\cdot)$. The
\emph{insecurity of $E$
} is given by
389 \
[ \InSec{prp
}(E; t, q) =
\max_A \Adv{prf
}{E
}(A) \
]
390 where the maximum is taken over all adversaries which run in time~$t$ and
391 issue at most $q$ oracle queries. If $
\InSec{prp
}(E; t, q)
\le \epsilon$
392 then we say that $E$ is a $(t, q,
\epsilon)$-PRP.
395 The following result is standard; we shall require it for the security proofs
396 of CFB and OFB modes. The proof is given as an introduction to our general
400 \label{prop:prps-are-prfs
}
401 Suppose $E$ is a PRP over $
\Bin^
\ell$. Then
402 \
[ \InSec{prf
}(E; t, q)
403 \le \InSec{prp
}(E; t, q) +
\frac{q (q -
1)
}{2^
{\ell+
1}}.
408 \
[ \InSec{prf
}(
\Perm{\ell}; t, q)
\le \frac{q (q -
1)
}{2^
{\ell+
1}}, \
]
409 i.e., that a
\emph{perfect
} $
\ell$-bit random permutation is a PRF with the
410 stated bounds. The proposition follows immediately from this claim and the
413 We now prove the claim. Consider any adversary~$A$. Let $x_i$ be $A$'s
414 queries, and let $y_i$ be the responses, for $
0 \le i < q$. Assume,
415 without loss of generality, that the $x_i$ are distinct. Let $C_n$ be the
416 event in the random-function game $
\Expt{prf-$
0$
}{\Perm{\ell}}(A)$ that
417 $y_i = y_j$ for some $i$ and $j$ where $
0 \le i < j < n$. Then
419 \Pr[C_n
] \le \sum_{0\le i<n
} \frac{i
}{2^
\ell}
420 =
\frac{n (n -
1)
}{2^
{\ell+
1}}.
422 It's clear that the two games proceed identically if $C_q$ doesn't occur in
423 the random-function game. The claim follows.
426 \subsection{Symmetric encryption
}
429 We begin with a purely syntactic description of a symmetric encryption
430 scheme, and then define our two notions of security.
432 \begin{definition
}[Symmetric encryption
]
434 A
\emph{symmetric encryption scheme
} is a triple of algorithms $
\E = (G, E,
435 D)$, with three (implicitly) associated sets: a keyspace, a plaintext
436 space, and a ciphertext space.
438 \item $G$ is a probabilistic
\emph{key-generation algorithm
}. It is
439 invoked with no arguments, and returns a key $K$ which can be used with
440 the other two algorithms. We write $K
\gets G()$.
441 \item $E$ is a probabilistic
\emph{encryption algorithm
}. It is invoked
442 with a key $K$ and a
\emph{plaintext
} $x$ in the plaintext space, and it
443 returns a
\emph{ciphertext
} $y$ in the ciphertext space. We write $y
445 \item $D$ is a deterministic
\emph{decryption algorithm
}. It is invoked
446 with a key $K$ and a ciphertext $y$, and it returns either a plaintext
447 $x$ or the distinguished symbol $
\bot$. We write $x
\gets D_K(y)$.
449 For correctness, we require that whenever $y$ is a possible result of
450 computing $E_K(x)$, then $x = D_K(y)$.
453 Our primary notion of security is
\emph{left-or-right indistinguishability
454 under chosen-plaintext attack
} (LOR-CPA), since it offers the best reductions
455 to the other common notions. (We can't acheive security against chosen
456 ciphertext attack using any of our modes, so we don't even try.) See
457 \cite{Bellare:
2000:CST
} for a complete discussion of LOR-CPA, and how it
458 relates to other security notions for symmetric encryption.
460 \begin{definition
}[Left-or-right indistinguishability
]
462 Let $
\E = (G, E, D)$ be a symmetric encryption scheme. Define the function
463 $
\id{lr
}(b, x_0, x_1) = x_b$. Then for any adversary $A$, we define $A$'s
464 \emph{advantage against the LOR-CPA security of $
\E$
} as
465 \
[ \Adv{lor-cpa
}{\E}(A) =
466 \Pr[K
\gets G(): A^
{E_K(
\id{lr
}(
1,
\cdot,
\cdot))
} =
1] -
467 \Pr[K
\gets G(): A^
{E_K(
\id{lr
}(
0,
\cdot,
\cdot))
} =
1].
469 We define the
\emph{LOR-CPA insecurity of $
\E$
} to be
470 \
[ \InSec{lor-cpa
}(
\E; t, q_E,
\mu_E) =
471 \max_A \Adv{lor-cpa
}{\E}(A)
473 where the maximum is taken over all adversaries which run in time~$t$ and
474 issue at most $q_E$ encryption queries totalling at most $
\mu_E$ bits. If
475 $
\InSec{lor-cpa
}(
\E; t, q_E,
\mu_E)
\le \epsilon$ then we say that $
\E$ is
476 $(t, q_E,
\mu_E,
\epsilon)$-LOR-CPA.
479 Our second notion is named
\emph{result-or-garbage
} and abbreviated ROG-CPA.
480 It is related to the notion used by
\cite{Rogaway:
2001:OCB
}, though different
481 in important ways: for example, there are reductions both ways between
482 ROG-CPA and LOR-CPA (and hence the other standard notions of security for
483 symmetric encryption), whereas the notion of
\cite{Rogaway:
2001:OCB
} is
484 strictly stronger than LOR-CPA. Our idea is that an encryption scheme is
485 secure if ciphertexts of given plaintexts --
\emph{results
} -- hard to
486 distinguish from strings constructed independently of any plaintexts --
487 \emph{garbage
}. We formalize this notion in terms of a
488 \emph{garbage-emission algorithm
} $W$ which is given only the length of the
489 plaintext. The algorithm $W$ will usually be probabilistic, and may maintain
490 state. Unlike
\cite{Rogaway:
2001:OCB
}, we don't require that $W$'s output
491 `look random' in any way, just that it be chosen independently of the
492 adversary's plaintext selection.
494 \begin{definition
}[Result-or-garbage indistinguishability
]
496 Let $
\E = (G, E, D)$ be a symmetric encryption scheme, and let $W$ be a
497 possibly-stateful, possibly-probabilistic
\emph{garbage-emission
}
498 algorithm. Then for any adversary $A$, we define $A$'s
\emph{advantage
499 against the ROG-CPA-$W$ security of $
\E$
} as
500 \
[ \Adv{rog-cpa-$W$
}{\E}(A) =
501 \Pr[K
\gets G(): A^
{E_K(
\cdot)
} =
1] -
\Pr[A^
{W(|
\cdot|)
} =
1]. \
]
502 We define the
\emph{ROG-CPA insecurity of $
\E$
} to be
503 \
[ \InSec{lor-cpa
}(
\E; t, q_E,
\mu_E) =
504 \max_A \Adv{lor-cpa
}{\E}(A) \
]
505 where the maximum is taken over all adversaries which run in time~$t$ and
506 issue at most $q_E$ encryption queries totalling at most $
\mu_E$ bits. If
507 $
\InSec{rog-cpa-$W$
}(
\E; t, q_E,
\mu_E)
\le \epsilon$ for some $W$ then we
508 say that $
\E$ is $(t, q_E,
\mu_E,
\epsilon)$-ROG-CPA.
511 The following proposition relates our new notion to the existing known
515 \def\Wror{{W_
{\text{ROR
}}}}
516 \begin{proposition
}[ROG $
\Leftrightarrow$ LOR
]
517 \label{prop:rog-and-lor
}
518 Let $
\E$ be a symmetric encryption scheme. Then,
520 \item for all garbage-emission algorithms $W$,
521 \
[ \InSec{lor-cpa
}(
\E; t, q_E,
\mu_E)
523 \InSec{rog-cpa-$W$
}(
\E; t + t_E
\mu_E, q_E,
\mu_E)
526 \item there exists a garbage-emission algorithm $
\Wror$ for which
527 \
[ \InSec{rog-cpa-$
\Wror$
}(
\E; t, q_E,
\mu_E)
528 \le \InSec{lor-cpa
}(
\E; t + t_E
\mu_E, q_E,
\mu_E)
531 for some fairly small constant $t_E$.
534 Note the asymmetry between these two statements. ROG-CPA-$W$ implies
535 LOR-CPA for
\emph{any
} garbage emitter $W$, but LOR-CPA implies
536 ROG-CPA-$
\Wror$ for the specific emitter $
\Wror$ only.
538 \begin{proof
}[Proof of proposition
\ref{prop:rog-and-lor
}]
540 \item Let $W$ and $
\E$ be given, and let $A$ be an adversary attacking the
541 LOR-CPA security of $
\E$. Consider adversary $B$ attacking $
\E$'s
542 ROG-CPA-$W$ security.
544 Adversary $B^E(
\cdot)$: \+ \\
545 $b^*
\getsr \Bin$; \\
546 $b
\gets A^
{E(
\id{lr
}(b^*,
\cdot,
\cdot))
}$; \\
547 \IF $b = b^*$
\THEN \RETURN $
1$
\ELSE \RETURN $
0$;
549 Function $
\id{lr
}(b, x_0, x_1)$: \+ \\
550 \IF $b =
0$
\THEN \RETURN $x_0$
\ELSE \RETURN $x_1$;
552 If $E(
\cdot)$ is the `result' encryption oracle, then $B$ simulates the
553 left-or-right game for the benefit of $A$, and therefore returns $
1$ with
554 probability $(
\Adv{lor-cpa
}{\E}(A) +
1)/
2$. On the other hand, if
555 $E(
\cdot)$ returns `garbage' then the oracle responses are entirely
556 independent of $b^*$. This follows because $A$ is constrained to query
557 only on pairs of plaintexts with equal lengths, and the responses are
558 dependent only on these (common) lengths and any internal state and coin
559 tosses of $W$. So $b$ is independent of $b^*$ and $
\Pr[b = b^*
] =
560 \frac{1}{2}$. The result follows.
561 \item Let $
\E = (G, E, D)$ be given. Our garbage emitter simulates the
562 real-or-random game of
\cite{Bellare:
2000:CST
}. Let $K_W =
\bot$
563 initially: we define our emitter $
\Wror$ thus:
565 Garbage emitter $
\Wror(n)$: \+ \\
566 \IF $K_W =
\bot$
\THEN $K_W
\gets G()$; \\
567 $x
\getsr \Bin^n$; \\
568 \RETURN $E_
{K_W
}(x)$;
570 We now show that $
\InSec{rog-cpa-$
\Wror$
}(
\E; t, q_E,
\mu_E)
\le
571 \InSec{lor-cpa
}(
\E; t + t_E
\mu_E, q_E,
\mu_E)$ for our $
\Wror$. Let $A$
572 be an adversary attacking the ROG-CPA-$
\Wror$ security of $
\E$. Consider
573 adversary $B$ attacking $
\E$'s LOR-CPA security:
575 Adversary $B^
{E(
\cdot,
\cdot)
}$: \+ \\
576 $b
\gets A^
{\id{lorify
}(
\cdot)
}$; \\
579 Function $
\id{lorify
}(x)$: \+ \\
580 $x'
\getsr \Bin^
{|x|
}$; \\
583 The adversary simulates the ROG-CPA-$
\Wror$ games perfectly, since the
584 game has chosen the random $K_W$ for us already: the `left' game returns
585 only the results of encrypting random `garbage' plaintexts $x'$, while
586 the right game returns correct results of encrypting the given plaintexts
587 $x$. The result follows.
\qed
593 \subsection{Message authentication
}
596 Our definitions for message authentication are standard; little needs to be
597 said of them. As with symmetric encryption, we begin with a syntactic
598 definition, and then describe our notion of security.
600 \begin{definition
}[Message authentication code
]
602 A
\emph{message authentication code (MAC)
} is a triple of algorithms $
\M =
603 (G, T, V)$ with three (implicitly) associated sets: a keyspace, a message
604 space, and a tag space.
606 \item $G$ is a probabilistic
\emph{key-generation algorithm
}. It is
607 invoked with no arguments, and returns a key $K$ which can be used with
608 the other two algorithms. We write $K
\gets G()$.
609 \item $T$ is a probabilistic
\emph{tagging algorithm
}. It is invoked with
610 a key $K$ and a
\emph{message
} $x$ in the message space, and it returns a
611 \emph{tag
} $
\tau$ in the tag space. We write $
\tau \gets T_K(x)$.
612 \item $V$ is a deterministic
\emph{verification algorithm
}. It is invoked
613 with a key $K$, a message $x$ and a tag $
\tau$, and returns a bit $b
\in
614 \Bin$. We write $b
\gets V_K(x,
\tau)$.
616 For correctness, we require that whenever $
\tau$ is a possible result of
617 computing $T_K(x)$, then $V_K(x,
\tau) =
1$.
620 Our notion of security is the strong unforgeability of
621 \cite{Abdalla:
2001:DHIES,Bellare:
2000:AER
}.
623 \begin{definition
}[Strong unforgeability
]
624 Let $
\M = (G, T, V)$ be a message authentication code, and let $A$
625 be an adversary. We perform the following experiment.
627 Experiment $
\Expt{suf-cma
}{\M}(A)$: \+ \\
629 $
\Xid{T
}{list
} \gets \emptyset$; \\
630 $
\id{good
} \gets 0$; \\
631 $A^
{\id{tag
}(
\cdot),
\id{verify
}(
\cdot,
\cdot)
}$; \\
634 Oracle $
\id{tag
}(x)$: \+ \\
635 $
\tau \gets T_K(x)$; \\
636 $
\Xid{T
}{list
} \gets \Xid{T
}{list
} \cup \
{(x,
\tau)\
}$; \\
639 Oracle $
\id{verify
}(x,
\tau)$: \+ \\
640 $b
\gets V_K(x,
\tau)$; \\
641 \IF $b =
1 \land (x,
\tau)
\notin \Xid{T
}{list
}$
\THEN
642 $
\id{good
} \gets 1$; \\
645 That is, the adversary `wins' if it submits a query to its verification
646 oracle which is
\emph{new
} -- doesn't match any message/tag pair from the
647 tagging oracle -- and
\emph{valid
} -- the verification oracle returned
648 success. We define the adversary's
\emph{success probability
} as
649 \
[ \Succ{suf-cma
}{\M}(A) =
650 \Pr[\Expt{suf-cma
}{\M}(A) =
1]. \
]
651 We define the
\emph{SUF-CMA insecurity of $
\M$
} to be
652 \
[ \InSec{suf-cma
}(
\M; t, q_T,
\mu_T, q_V,
\mu_V) =
653 \max_A \Adv{suf-cma
}{\M}(A) \
]
654 where the maximum is taken over all adversaries which run in time~$t$,
655 issue at most $q_T$ tagging queries totalling at most $
\mu_T$ bits, and
656 issue at most $q_V$ verification queries totalling at most $
\mu_V$ bits.
657 If $
\InSec{suf-cma
}(
\M; t, q_T,
\mu_T, q_V,
\mu_V)
\le \epsilon$
658 then we say that $
\E$ is $(t, q_T,
\mu_T, q_V,
\mu_V)$-SUF-CMA.
661 \subsection{Initialization vectors and encryption modes
}
664 In order to reduce the number of definitions in this paper to a tractable
665 level, we will describe the basic modes independently of how initialization
666 vectors (IVs) are chosen, and then construct the actual encryption schemes by
667 applying various IV selection methods from the modes.
669 We consider the following IV selection methods.
671 \item[Random selection
] An IV is chosen uniformly at random just before
672 encrypting each message.
673 \item[Counter
] The IV for each message is a
\emph{generalized counter
} (see
674 discussion below, and definition~
\ref{def:genctr
}).
675 \item[Encrypted counter
] The IV for a message is the result of applying the
676 block cipher to a generalized counter, using the same key as for message
678 \item[Carry-over
] The IV for the first message is fixed; the IV for
679 subsequent messages is some function of the previous plaintexts or
680 ciphertexts (e.g., the last ciphertext block of the previous message).
682 Not all of these methods are secure for all of the modes we consider.
684 \begin{definition
}[Generalized counters
]
686 If $S$ is a finite set, then a
\emph{generalized counter in $S$
} is an
687 bijection $c
\colon \Nupto{|S|
} \leftrightarrow S$. For brevity, we shall
688 refer simply to `counters', leaving implicit the generalization.
691 \begin{remark
}[Examples of generalized counters
] \leavevmode
693 \item There is a `natural' binary representation of the natural numbers
694 $
\Nupto{2^
\ell}$ as $
\ell$-bit strings: for any $n
\in \Nupto{2^
\ell}$,
695 let $R(n)$ be the unique $r
\in \Bin^
\ell$ such that $
\smash{n =
696 \sum_{0\le i<
\ell} 2^i r
[i
]}$. Then $R(
\cdot)$ is a generalized counter
698 \item We can represent elements of the finite field $
\gf{2^
\ell}$ as
699 $
\ell$-bit strings. Let $p(x)
\in \gf{2}[x
]$ be a primitive polynomial
700 of degree $
\ell$; then represent $
\gf{2^
\ell}$ by $
\gf{2}[x
]/(p(x))$.
701 Now for any $a
\in \gf{2^
\ell}$, let $R(a)$ be the unique $r
\in
702 \Bin^
\ell$ such that $
\smash{a =
\sum_{0\le i<
\ell} x^i r
[i
]}$. Because
703 $p(x)$ is primitive, $x$ generates the multiplicative group
704 $
\gf{2^
\ell}^
{\,*
}$, so define $c(n) = R(x^n)$ for $
0 \le n <
2^
\ell -
1$
705 and $c(
2^
{\ell -
1}) =
0^
\ell$; then $c(
\cdot)$ is a generalized counter
706 in $
\Bin^
\ell$. This counter can be implemented efficiently in hardware
707 using a linear feedback shift register.
711 \begin{definition
}[Encryption modes
]
712 \label{def:enc-modes
}
714 A
\emph{block cipher encryption mode
} $m_P = (
\id{encrypt
},
\id{decrypt
})$
715 is a pair of deterministic oracle algorithms (and implicitly-defined
716 plaintext and ciphertext spaces) which satisfy the following conditions:
718 \item The algorithm $
\id{encrypt
}$ runs with oracle access to a permutation
719 $P
\colon \Bin^
\ell \leftrightarrow \Bin^
\ell$; on input a plaintext $x$
720 and an initialization vector $v
\in \Bin^
\ell$, it returns a ciphertext
721 $y$ and a
\emph{chaining value
} $v'
\in \Bin^
\ell$. We write $(v', y) =
722 \id{encrypt
}^
{P(
\cdot)
}(v, x)$.
723 \item The algorithm $
\id{decrypt
}$ runs with oracle access to a permutation
724 $P
\colon \Bin^
\ell \leftrightarrow \Bin^
\ell$ and its inverse
725 $P^
{-
1}(
\cdot)$; on input a ciphertext $y$ and an initialization vector
726 $v
\in \Bin^
\ell$, it returns a plaintext $x$. We write that $x =
727 \id{decrypt
}^
{P(
\cdot), P^
{-
1}(
\cdot)
}(v, y)$.
728 \item For all permutations $P
\colon \Bin^
\ell \leftrightarrow \Bin^
\ell$,
729 all plaintexts $x$ and all initialization vectors $v$, if $(v', y) =
730 \id{encrypt
}^
{P(
\cdot)
}(v, x)$ then $x =
\id{decrypt
}^
{P(
\cdot),
731 P^
{-
1}(
\cdot)
}(v, y)$.
733 Similarly, a
\emph{PRF encryption mode
} $m_F = (
\id{encrypt
},
734 \id{decrypt
})$ is a pair of deterministic oracle algorithms (and
735 implicitly-defined plaintext and ciphertext spaces) which satisfy the
736 following conditions:
738 \item The algorithm $
\id{encrypt
}$ runs with oracle access to a function
739 $F
\colon \Bin^
\ell \to \Bin^L$; on input a plaintext $x$ and an
740 initialization vector $v
\in \Bin^
\ell$, it returns a ciphertext $y$ and
741 a
\emph{chaining value
} $v'
\in \Bin^
\ell$. We write $(v', y) =
742 \id{encrypt
}^
{F(
\cdot)
}(v, x)$.
743 \item The algorithm $
\id{decrypt
}$ runs with oracle access to a function
744 $F
\colon \Bin^
\ell \to \Bin^L$; on input a ciphertext $y$ and an
745 initialization vector $v
\in \Bin^
\ell$, it returns a plaintext $x$. We
746 write that $(v', x) =
\id{decrypt
}^
{F(
\cdot)
}(v, y)$.
747 \item For all functions $F
\colon \Bin^
\ell \to \Bin^L$, all plaintexts $x$
748 and all initialization vectors $v$, if $(v', y) =
749 \id{encrypt
}^
{F(
\cdot)
}(v, x)$ then $x =
\id{decrypt
}^
{F(
\cdot)
}(v, y)$.
754 \begin{definition
}[Symmetric encryption schemes from modes
]
755 \label{def:enc-scheme
}
756 Let $F$ be a pseudorandom permutation on $
\Bin^
\ell$ (resp.\ a
757 pseudorandom function from $
\Bin^
\ell$ to $
\Bin^L$); let $m =
758 (
\id{encrypt
},
\id{decrypt
})$ be a block cipher (resp.\ PRF) encryption
759 mode. (To save on repetition, if $F$ is a PRF then define $F_K^
{-
1}(x) =
760 \bot$ for all keys $K$ and inputs $x$.) We define the following symmetric
761 encryption schemes according to how IVs are selected.
764 \def\Enc{\Xid{\E}{$m$
\what}^
{\super}}
765 \def\GG{\Xid{G
}{$m$
\what}^
{\super}}
766 \def\EE{\Xid{E
}{$m$
\what}^
{\super}}
767 \def\DD{\Xid{D
}{$m$
\what}^
{\super}}
771 \item Randomized selection: define $
\Enc = (
\GG,
\EE,
\DD)$, where
773 Algorithm $
\GG()$: \+ \\
774 $K
\getsr \keys F$; \\
777 Algorithm $
\EE(K, x)$: \+ \\
778 $v
\getsr \Bin^
\ell$; \\
779 $(v', x)
\gets \id{encrypt
}^
{F_K(
\cdot)
}(v, x)$; \\
782 Algorithm $
\DD(K, y')$; \+ \\
783 $(v, y)
\gets y'$; \\
784 $(v', x)
\gets {}$ \\
785 \qquad $
\id{decrypt
}^
{F_K(
\cdot), F^
{-
1}_K(
\cdot)
}(v, y)$; \\
791 \def\imsg{\Xid{i
}{msg
}}
792 \item Generalized counters: define $
\Enc = (
\GG,
\EE,
\DD)$, where $c$ is a
793 generalized counter in $
\Bin^
\ell$, and
795 Algorithm $
\GG()$: \+ \\
796 $K
\getsr \keys F$; \\
800 Algorithm $
\EE(K, x)$: \+ \\
801 $i
\gets c(
\imsg)$; \\
802 $(v', x)
\gets \id{encrypt
}^
{F_K(
\cdot)
}(i, x)$; \\
803 $
\imsg \gets \imsg +
1$; \\
806 Algorithm $
\DD(K, y')$; \+ \\
807 $(i, y)
\gets y'$; \\
808 $(v', x)
\gets {}$ \\
809 \qquad $
\id{decrypt
}^
{F_K(
\cdot), F^
{-
1}_K(
\cdot)
}(i, y)$; \\
815 \def\imsg{\Xid{i
}{msg
}}
816 \item Encrypted counters: if $L
\ge \ell$, then define $
\Enc = (
\GG,
\EE,
817 \DD)$, where $c$ is a generalized counter in $
\Bin^
\ell$, and
819 Algorithm $
\GG()$: \+ \\
820 $K
\getsr \keys F$; \\
824 Algorithm $
\EE(K, x)$: \+ \\
825 $i
\gets c(
\imsg)$; \\
826 $v
\gets F_K(i)
[0 \bitsto \ell]$; \\
827 $(v', x)
\gets \id{encrypt
}^
{F_K(
\cdot)
}(v, x)$; \\
828 $
\imsg \gets \imsg +
1$; \\
831 Algorithm $
\DD(K, y')$; \+ \\
832 $(i, y)
\gets y'$; \\
833 $v
\gets F_K(i)
[0 \bitsto \ell]$; \\
834 $(v', x)
\gets {}$ \\
835 \qquad $
\id{decrypt
}^
{F_K(
\cdot), F^
{-
1}_K(
\cdot)
}(v, y)$; \\
838 (We require $L
\ge \ell$ for this to be well-defined; otherwise the
839 encrypted counter value is too short.)
843 \def\vnext{\Xid{v
}{next
}}
844 \item Carry-over: define $
\Enc = (
\GG,
\EE,
\DD)$ where $V_0
\in \Bin^
\ell$
845 is the initialization vector for the first message, and
847 Algorithm $
\GG()$: \+ \\
848 $K
\getsr \keys F$; \\
849 $
\vnext \gets V_0$; \\
852 Algorithm $
\EE(K, x)$: \+ \\
854 $(v', x)
\gets \id{encrypt
}^
{F_K(
\cdot)
}(v, x)$; \\
855 $
\vnext \gets v'$; \\
858 Algorithm $
\DD(K, y')$; \+ \\
859 $(v, y)
\gets y'$; \\
860 $(v', x)
\gets {}$ \\
861 \qquad $
\id{decrypt
}^
{F_K(
\cdot), F^
{-
1}_K(
\cdot)
}(v, y)$; \\
866 Note that, while the encryption algorithms of the above schemes are either
867 randomized or stateful, the decryption algorithms are simple and
871 The following simple and standard result will be very useful in our proofs.
874 \label{prop:enc-info-to-real
}
877 \item Suppose that $
\E^P = (G^P, E^P, D^P)$ is one of the symmetric
878 encryption schemes of definition~
\ref{def:enc-scheme
}, constructed from a
879 pseudorandom permutation $P
\colon \Bin^
\ell \leftrightarrow \Bin^
\ell$.
880 If $q$ is an upper bound on the number of PRP applications required for
881 the encryption $q_E$ messages totalling $
\mu_E$ bits, then there is some
882 small constant $t'$ such that
883 \
[ \InSec{lor-cpa
}(
\E^P; t, q_E,
\mu_E)
\le
884 \InSec{lor-cpa
}(
\E^
{\Perm{\ell}}; t, q_E,
\mu_E) +
885 2 \cdot \InSec{prp
}(P; t + q t', q) .
887 \item Similarly, suppose that $
\E^F = (G^F, E^F, D^F)$ is one of the
888 symmetric encryption schemes of definition~
\ref{def:enc-scheme
},
889 constructed from a pseudorandom function $F
\colon \Bin^
\ell \to \Bin^L$.
890 If $q$ is an upper bound on the number of PRP applications required for
891 the encryption $q_E$ messages totalling $
\mu_E$ bits, then there is some
892 small constant $t'$ such that
893 \
[ \InSec{lor-cpa
}(
\E^F; t, q_E,
\mu_E)
\le
894 \InSec{lor-cpa
}(
\E^
{\Func{\ell}{L
}}; t, q_E,
\mu_E) +
895 2 \cdot \InSec{prf
}(F; t + q t', q) .
901 \item Let $A$ be an adversary attacking the LOR-CPA security of $
\E^P$,
902 which takes time $t$ and issues $q_E$ encryption queries totalling
903 $
\mu_E$ bits. We construct an adversary $B$ attacking the security of
904 the PRP $P$ as follows. $B$ selects a random $b^*
\inr \Bin$. It then
905 runs $A$, simulating the LOR-CPA game by using $b^*$ to decide whether to
906 encrypt the left or right plaintext, and using its oracle access to $P$
907 to do the encryption. Eventually, $A$ returns a bit $b$. If $b = b^*$,
908 $B$ returns $
1$ (indicating `pseudorandom'); otherwise it returns $
0$.
910 If $B$'s oracle is selected from the PRP $P$, then $B$ correctly
911 simulates the LOR-CPA game for $
\E^P$, and $B$ returns $
1$ with
912 probability precisely $(
\Adv{lor-cpa
}{\E^P
}(A) +
1)/
2$. Conversely, if
913 $B$'s oracle is a random permutation, then $B$ correctly simulates the
914 LOR-CPA game for $
\E^
{\Perm{\ell}}$, so $B$ returns $
1$ with probability
915 $(
\Adv{lor-cpa
}{\E^P
}(A) +
1)/
2$. Thus, we have
918 & = (
\Adv{lor-cpa
}{\E^P
}(A) +
1)/
2
919 - (
\Adv{lor-cpa
}{\E^
{\Perm{\ell}}}(A) +
1)/
2 \\
920 & = (
\Adv{lor-cpa
}{\E^P
}(A)
921 -
\Adv{lor-cpa
}{\E^
{\Perm{\ell}}}(A))/
2 .
923 Note that the extra work which $B$ does over $A$ -- initialization,
924 tidying up and encrypting messages -- is bounded by some small constant
925 $t_P$ multiplied by the number of oracle queries~$q$ made by~$B$, and the
926 required result follows by multiplying through by~$
2$ and rearranging.
927 \item The proof for this case is almost identical: merely substitute $F$
928 for $P$, `PRF' for `PRP' and $
\Func{\ell}{L
}$ for $
\Perm{\ell}$ in the
933 Of course, proving theorems about each of the above schemes individually will
934 be very tedious. We therefore define a `hybrid' scheme which switches
935 between the above selection methods. This isn't a practical encryption
936 scheme -- just a `trick' to reduce the number of complicated proofs we need
939 \begin{definition
}[Hybrid encryption modes
]
940 \label{def:enc-hybrid
}
941 \def\Enc{\Xid{\E}{$m$
\what}^
{\super}_
{\sub}}
942 \def\GG{\Xid{G
}{$m$
\what}^
{\super}_
{\sub}}
943 \def\EE{\Xid{E
}{$m$
\what}^
{\super}_
{\sub}}
944 \def\DD{\Xid{D
}{$m$
\what}^
{\super}_
{\sub}}
946 \def\super{F, V_0, c
}
947 \def\sub{n_L, n_C, n_E
}
948 \def\imsg{\Xid{i
}{msg
}}
949 \def\vnext{\Xid{v
}{next
}}
950 Let $n_L$, $n_C$ and $n_E$ be nonnegative integers, with $n_L + n_C + n_E
951 \le 2^
{\ell}$; let $F$ be a pseudorandom permutation on $
\Bin^
\ell$ (resp.\
952 a pseudorandom function from $
\Bin^
\ell$ to $
\Bin^L$); let $m =
953 (
\id{encrypt
},
\id{decrypt
})$ be a block cipher (resp.\ PRF) encryption
954 mode let $V_0
\in \Bin^
\ell$ be an initialization vector; and let $c
\colon
955 \Nupto{2^
\ell} \to \Bin^
\ell$ be a generalized counter. (Again, if $F$ is
956 a PRF, we set $F_K(x) =
\bot$ for all $K$ and $x$.) We define the scheme
957 $
\Enc = (
\GG,
\EE,
\DD)$ as follows.
959 Algorithm $
\GG()$: \+ \\
960 $K
\getsr \keys F$; \\
962 $
\vnext \gets V_0$; \\
965 Algorithm $
\DD(K, y')$; \+ \\
966 $(v, y)
\gets y'$; \\
967 $(v', x)
\gets \id{decrypt
}^
{F_K(
\cdot), F^
{-
1}_K(
\cdot)
}(v, y)$; \\
970 Algorithm $
\EE(K, x)$: \+ \\
971 \IF $
\imsg < n_L$
\THEN $v
\gets \vnext$; \\
972 \ELSE\IF $
\imsg < n_L + n_C$
\THEN $v
\gets c(
\imsg)$; \\
973 \ELSE\IF $
\imsg < n_L + n_C + n_E$
\THEN
974 $v
\gets F_K(c(
\imsg)
[0 \bitsto \ell])$; \\
975 \ELSE $v
\getsr \Bin^
\ell$; \\
976 $(v', x)
\gets \id{encrypt
}^
{F_K(
\cdot)
}(v, x)$; \\
977 $
\vnext \gets v'$; \\
978 $
\imsg \gets \imsg +
1$; \\
981 For this to be well-defined, we require that $L
\ge \ell$ or $n_E =
0$ --
982 otherwise the encrypted counter values are too short.
985 The following proposition relates the security of our artificial hybrid
986 scheme to that of the practical schemes defined in
987 definition~
\ref{def:enc-scheme
}.
990 \label{prop:enc-hybrid
}
991 Let $F$ be a pseudorandom permutation on $
\Bin^
\ell$ (resp.\ a pseudorandom
992 function from $
\Bin^
\ell$ to $
\Bin^L$); let $m$ be a block cipher (resp.\
993 PRF) encryption mode. Then:
995 \def\ii#1{\item $
\displaystyle#1$
}
996 \ii{\InSec{lor-cpa
}(
\Xid{E
}{$m\$$
}^F; t, q_E,
\mu_E)
\le
997 \InSec{lor-cpa
}(
\Xid{E
}{$m$H
}^
{F, V_0, c
}_
{0,
0,
0}; t, q_E,
\mu_E)
}
998 \ii{\InSec{lor-cpa
}(
\Xid{E
}{$m$C
}^
{F, c
}; t, q_E,
\mu_E)
\le
1000 (
\Xid{E
}{$m$H
}^
{F, V_0, c
}_
{q_E,
0,
0}; t, q_E,
\mu_E)
}
1001 \ii{\InSec{lor-cpa
}(
\Xid{E
}{$m$E
}^
{F, c
}; t, q_E,
\mu_E)
\le
1003 (
\Xid{E
}{$m$H
}^
{F, V_0, c
}_
{0, q_E,
0}; t, q_E,
\mu_E)
}
1004 \ii{\InSec{lor-cpa
}(
\Xid{E
}{$m$L
}^
{F, V_0
}; t, q_E,
\mu_E)
\le
1006 (
\Xid{E
}{$m$H
}^
{F, V_0, c
}_
{0,
0, q_E
}; t, q_E,
\mu_E)
}
1011 For
1, it suffices to observe that $
\Xid{E
}{$m\$$
}^F
\equiv
1012 \Xid{E
}{$m$H
}^
{F, V_0, c
}_
{0,
0,
0}$ for any $c$, $V_0$. For
2, note that
1013 $
\Xid{E
}{$m$C
}^
{F, c
}$ behaves identically to $
\Xid{E
}{$m$H
}^
{F, V_0,
1014 c
}_
{q_E,
0,
0}$ for any $c$, $V_0$ for the first $q_E$ encryption
1015 queries; but no adversary is permitted to exceed this limit, and hence no
1016 adversary can distinguish the two. Similarly, for
4, note that
1017 $
\Xid{E
}{$m$L
}^
{F, V_0
}$ behaves identically to $
\Xid{E
}{$m$H
}^
{F, V_0,
1018 c
}_
{0,
0, q_E
}$ for any $c$, $V_0$ for the first $q_E$ encryption
1021 The case of
3 is slightly more complicated: $
\Xid{E
}{$m$E
}^
{F, c
}$ behaves
1022 identically to $
\Xid{E
}{$m$H
}^
{F, V_0, c
}_
{0, q_E,
0}$ for the first $q_E$
1023 encryption queries
\emph{except
} that the latter returns different
1024 initialization vectors from its encryption oracle. However, since the
1025 counter $c$ is fixed public knowledge, it is trivial to construct a fully
1026 faithful replica of the $m$E game given the hybrid oracle, such that no
1027 adversary can distinguish the two.
1030 %%%--------------------------------------------------------------------------
1032 \section{Ciphertext block chaining (CBC) encryption
}
1035 \subsection{Description
}
1036 \label{sec:cbc-desc
}
1038 Suppose $E$ is an $
\ell$-bit pseudorandom permutation. CBC mode works as
1039 follows. Given a message $X$, we divide it into $
\ell$-bit blocks $x_0$,
1040 $x_1$, $
\ldots$, $x_
{n-
1}$. Choose an initialization vector $v
\in
1041 \Bin^
\ell$. Before passing each $x_i$ through $E$, we XOR it with the
1042 previous ciphertext, with $v$ standing in for the first block:
1044 y_0 = E_K(x_0
\xor v)
\qquad
1045 y_i = E_K(x_i
\xor y_
{i-
1} \
\text{(for $
1 \le i < n$)
}.
1047 The ciphertext is then the concatenation of $v$ and the $y_i$. Decryption is
1050 x_0 = E^
{-
1}_K(y_0)
\xor v
\qquad
1051 x_i = E^
{-
1}_K(y_i)
\xor y_
{i-
1} \
\text{(for $
1 \le i < n$)
}
1053 See figure~
\ref{fig:cbc
} for a diagram of CBC encryption.
1056 \begin{cgraph
}{cbc-mode
}
1057 []!
{0; <
0.85cm,
0cm>: <
0cm,
0.5cm>::
}
1058 *+=(
1,
0)+
[F
]{\mathstrut x_0
}="x"
1060 [ll
] *+=(
1,
0)+
[F
]{\mathstrut v
} :"xor"
1061 :
[dd
] *+
[F
]{E
}="e" :
[ddd
] *+=(
1,
0)+
[F
]{\mathstrut y_0
}="i"
1063 [rrruuuu
] *+=(
1,
0)+
[F
]{\mathstrut x_1
}="x"
1065 "e"
[d
] :`r
[ru
] `u "xor" "xor"
1066 :
[dd
] *+
[F
]{E
}="e" :
[ddd
]
1067 *+=(
1,
0)+
[F
]{\mathstrut y_1
}="i"
1069 [rrruuuu
] *+=(
1,
0)+
[F--
]{\mathstrut x_i
}="x"
1070 :@
{-->
}[dd
] *
{\xor}="xor"
1071 "e"
[d
] :@
{-->
}`r
[ru
] `u "xor" "xor"
1072 :@
{-->
}[dd
] *+
[F
]{E
}="e" :@
{-->
}[ddd
]
1073 *+=(
1,
0)+
[F--
]{\mathstrut y_i
}="i"
1074 "e"
[l
] {K
} :@
{-->
}"e"
1075 [rrruuuu
] *+=(
1,
0)+
[F
]{\mathstrut x_
{n-
1}}="x"
1077 "e"
[d
] :@
{-->
}`r
[ru
] `u "xor" "xor"
1078 :
[dd
] *+
[F
]{E
}="e" :
[ddd
]
1079 *+=(
1,
0)+
[F
]{\mathstrut y_
{n-
1}}="i"
1083 \caption{Encryption using CBC mode
}
1087 \begin{definition
}[CBC algorithms
]
1089 For any permutation $P
\colon \Bin^
\ell \to \Bin^
\ell$, any initialization
1090 vector $v
\in \Bin^
\ell$, any plaintext $x
\in \Bin^
{\ell\N}$ and any
1091 ciphertext $y
\in \Bin^*$, we define the encryption mode $
\id{CBC
} =
1092 (
\id{cbc-encrypt
},
\id{cbc-decrypt
})$ as follows:
1094 Algorithm $
\id{cbc-encrypt
}^
{P(
\cdot)
}(v, x)$: \+ \\
1095 $y
\gets \emptystring$; \\
1096 \FOR $i =
0$
\TO $|x|/
\ell$
\DO \\
\ind
1097 $x_i
\gets x
[\ell i
\bitsto \ell (i +
1)
]$; \\
1098 $y_i
\gets P(x_i
\xor v)$; \\
1100 $y
\gets y
\cat y_i$; \- \\
1103 Algorithm $
\id{cbc-decrypt
}^
{P(
\cdot), P^
{-
1}(
\cdot)
}(v, y)$: \+ \\
1104 \IF $|y|
\bmod \ell \ne 0$
\THEN \RETURN $
\bot$; \\
1105 $x
\gets \emptystring$; \\
1106 \FOR $
1 =
0$
\TO $|y|/
\ell$
\DO \\
\ind
1107 $y_i
\gets y
[\ell i
\bitsto \ell (i +
1)
]$; \\
1108 $x_i
\gets P^
{-
1}(y_i)
\xor v$; \\
1110 $x
\gets x
\cat x_i$; \- \\
1113 Now, let $c$ be a generalized counter in $
\Bin^
\ell$. We define the
1114 encryption schemes $
\Xid{E
}{CBC$\$$
}^P$, $
\Xid{E
}{CBCE
}^
{P, c
}$ and
1115 $
\Xid{E
}{CBCH
}^
{P, c,
\bot}_
{0,
0, n_E
}$, as described in
1116 definition~
\ref{def:enc-scheme
}.
1119 \subsection{Security of CBC mode
}
1121 We now present our main theorem on CBC mode.
1123 \begin{theorem
}[Security of hybrid CBC mode
]
1125 Let $P
\colon \keys P
\times \Bin^
\ell \to \Bin^
\ell$ be a pseudorandom
1126 permutation; let $V_0
\in \Bin^
\ell$ be an initialization vector; let $n_L
1127 \in \
{ 0,
1 \
}$; let $c$ be a generalized counter in $
\Bin^
\ell$; and
1128 let $n_C
\in \N$ be a nonnegative integer; and suppose that at most one of
1129 $n_L$ and $n_C$ is nonzero. Then, for any $t$, $q_E
\ge n$ and $
\mu_E$,
1131 (
\Xid{\E}{CBCH
}^
{P, c, V_0
}_
{n_L,
0, n_E
}; t, q_E,
\mu_E)
\le
1132 2 \cdot \InSec{prp
}(P; t + q t_P, q) +
\frac{q (q -
1)
}{2^
\ell - q
}
1134 where $q = n_L + n_E +
\mu_E/
\ell$ and $t_P$ is some small constant.
1137 The proof of this theorem we postpone until section~
\ref{sec:cbc-proof
}. As
1138 promised, the security of our randomized and stateful schemes follow as
1141 \begin{corollary
}[Security of practical CBC modes
]
1143 Let $P$ and $c$ be as in theorem~
\ref{thm:cbc
}. Then for any $t$, $q_E$
1144 and $
\mu_E$, and some small constant $t_P$,
1145 \begin{eqnarray*
}[rl
]
1146 \InSec{lor-cpa
}(
\Xid{\E}{CBC$\$$
}^P; t, q_E,
\mu_E)
1147 &
\le 2 \cdot \InSec{prp
}(P; t + q t_P, q) +
\frac{q (q -
1)
}{2^
\ell - q
}
1149 \InSec{lor-cpa
}(
\Xid{\E}{CBCE
}^
{P, c
}; t, q_E,
\mu_E)
1150 &
\le 2 \cdot \InSec{prp
}(P; t + q' t_P, q') +
1151 \frac{q' (q' -
1)
}{2^
\ell - q'
}
1154 \InSec{lor-cpa
}(
\Xid{\E}{CBCL
}^
{P, V_0
}; t,
1,
\mu_E)
1155 &
\le 2 \cdot \InSec{prp
}(P; t + q t_P, q) +
1156 \frac{q (q -
1)
}{2^
\ell - q
}
1158 where $q =
\mu_E/
\ell$, and $q' = q + q_E$.
1161 Follows from theorem~
\ref{thm:cbc
} and proposition~
\ref{prop:enc-hybrid
}.
1165 The insecurity of CBC mode over that inherent in the underlying PRP is
1166 essentially a birthday bound: note for $q
\le 2^
{\ell/
2}$, our denominator
1167 $
2^
\ell - q
\approx 2^
\ell$, and for larger $q$, the term $q (q -
1)/
2^
\ell
1168 >
1$ anyway, so all security is lost (according to the above result).
1169 Compared to
\cite[theorem~
17]{Bellare:
2000:CST
}, we gain the tiny extra
1170 term in the denominator, but lose the PRP-as-a-PRF term
1171 $q^
2/
2^
{\ell-
1}$.
\footnote{%
1172 In fact, they don't prove the stated bound of $q (
3 q -
2)/
2^
{\ell+
1}$
1173 but instead the larger $q (
2 q -
1)/
2^
\ell$. The error is in the
1174 application of their proposition~
8: the PRF-insecurity term is doubled,
1175 so the PRP-as-a-PRF term must be also.
} %
1178 \subsection{Ciphertext stealing
}
1180 Ciphertext stealing
\cite{Daemen:
1995:CHF,Schneier:
1996:ACP,RFC2040
} allows
1181 us to encrypt any message in $
\Bin^*$ without the need for padding. The
1182 trick is to fill in the `gap' at the end of the last block with the end bit
1183 of the previous ciphertext, and then to put the remaining short penultimate
1184 block at the end. Decryption proceeds by first decrypting the final block to
1185 recover the remainder of the penultimate one. See
1186 figure~
\ref{fig:cbc-steal
}.
1189 \begin{cgraph
}{cbc-steal-enc
}
1190 []!
{0; <
0.85cm,
0cm>: <
0cm,
0.5cm>::
}
1191 *+=(
1,
0)+
[F
]{\mathstrut x_0
}="x"
1193 [ll
] *+=(
1,
0)+
[F
]{\mathstrut v
} :"xor"
1194 :
[dd
] *+
[F
]{E
}="e" :
[ddddd
] *+=(
1,
0)+
[F
]{\mathstrut y_0
}="i"
1196 [rrruuuu
] *+=(
1,
0)+
[F
]{\mathstrut x_1
}="x"
1198 "e"
[d
] :`r
[ru
] `u "xor" "xor"
1199 :
[dd
] *+
[F
]{E
}="e" :
[ddddd
]
1200 *+=(
1,
0)+
[F
]{\mathstrut y_1
}="i"
1202 [rrruuuu
] *+=(
1,
0)+
[F--
]{\mathstrut x_i
}="x"
1203 :@
{-->
}[dd
] *
{\xor}="xor"
1204 "e"
[d
] :@
{-->
}`r
[ru
] `u "xor" "xor"
1205 :@
{-->
}[dd
] *+
[F
]{E
}="e" :@
{-->
}[ddddd
]
1206 *+=(
1,
0)+
[F--
]{\mathstrut y_i
}="i"
1207 "e"
[l
] {K
} :@
{-->
}"e"
1208 [rrruuuu
] *+=(
1,
0)+
[F
]{\mathstrut x_
{n-
2}}="x"
1210 "e"
[d
] :@
{-->
}`r
[ru
] `u "xor" "xor"
1213 [rrruuuu
] *+=(
1,
0)+
[F
]{\mathstrut x_
{n-
1} \cat 0^
{\ell-t
}}="x"
1215 "e"
[d
] :`r
[ru
] `u "xor" "xor"
1216 "e"
[dddddrrr
] *+=(
1,
0)+
[F
]{\mathstrut y_
{n-
1}[0 \bitsto t
]}="i"
1219 []!
{"x"; "e" **
{}, "x"+/
4pt/ ="p",
1220 "x"; "y" **
{}, "x"+/
4pt/ ="q",
1221 "y"; "x" **
{}, "y"+/
4pt/ ="r",
1222 "y"; "i" **
{}, "y"+/
4pt/ ="s",
1228 "i" **
\dir{-
}?>*
\dir{>
}}
1229 "xor" :
[dd
] *+
[F
]{E
}="e"
1231 "e"
[dddddlll
] *+=(
1,
0)+
[F
]{\mathstrut y_
{n-
2}}="i"
1234 []!
{"x"; "e" **
{}, "x"+/
4pt/ ="p",
1235 "x"; "y" **
{}, "x"+/
4pt/ ="q",
1236 "y"; "x" **
{}, "y"+/
4pt/ ="r",
1237 "y"; "i" **
{}, "y"+/
4pt/ ="s",
1238 "x"; "y" **
{} ?="c" ?(
0.5)/-
4pt/ ="cx" ?(
0.5)/
4pt/ ="cy",
1243 "c" *
[@
]\cir<
4pt>
{d^u
};
1247 "i" **
\dir{-
}?>*
\dir{>
}}
1250 \begin{cgraph
}{cbc-steal-dec
}
1251 []!
{0; <
0.85cm,
0cm>: <
0cm,
0.5cm>::
}
1252 *+=(
1,
0)+
[F
]{\mathstrut y_0
}="y"
1253 :
[ddddddd
] *+
[F
]{D
}="d"
[l
] {K
} :"d"
1254 [rrrdd
] *
{\xor} ="nx" "d"
[u
] :`r
[rd
] `d "nx" "nx"
1255 "d" :
[dd
] *
{\xor} ="xor"
[ll
] *+=(
1,
0)+
[F
]{\mathstrut v
} :"xor"
1256 :
[dd
] *+=(
1,
0)+
[F
]{\mathstrut x_0
} "nx"="xor"
1257 "y"
[rrr
] *+=(
1,
0)+
[F
]{\mathstrut y_1
}="y"
1258 :
[ddddddd
] *+
[F
]{D
}="d"
[l
] {K
} :"d"
1259 [rrrdd
] *
{\xor} ="nx" "d"
[u
] :@
{-->
}`r
[rd
] `d "nx" "nx"
1261 :
[dd
] *+=(
1,
0)+
[F
]{\mathstrut x_1
} "nx"="xor"
1262 "y"
[rrr
] *+=(
1,
0)+
[F--
]{\mathstrut y_i
}="y"
1263 :@
{-->
}[ddddddd
] *+
[F
]{D
}="d"
[l
] {K
} :"d"
1264 [rrrdd
] *
{\xor} ="nx" "d"
[u
] :@
{-->
}`r
[rd
] `d "nx" "nx"
1266 :
[dd
] *+=(
1,
0)+
[F--
]{\mathstrut x_i
} "nx"="xor"
1267 "y"
[rrr
] *+=(
1,
0)+
[F
]{\mathstrut y_
{n-
2}}="y"
1268 [dddddrrr
] *+
[F
]{D
}="d"
[r
] {K
} :"d"
1271 []!
{"x"; "y" **
{}, "x"+/
4pt/ ="p",
1272 "x"; "e" **
{}, "x"+/
4pt/ ="q",
1273 "e"; "x" **
{}, "e"+/
4pt/ ="r",
1274 "e"; "d" **
{}, "e"+/
4pt/ ="s",
1280 "d" **
\dir{-
}?>*
\dir{>
}}
1282 "z"
[llluu
] *
{\xor} ="x1"
1283 "z" :`l
[lu
] `u "x1" |*+
{\scriptstyle 0^t
\cat z
[t
\bitsto \ell]} "x1"
1284 "z" :
[dd
] *
{\xor} ="xor2"
1285 :
[dd
] *+
[F
]{\mathstrut x_
{n-
1}[0 \bitsto t
]}
1286 "y"
[rrr
] *+=(
1,
0)+
[F
]{\mathstrut y_
{n-
1} \cat 0^
{\ell-t
}}="y"
1289 []!
{"x"; "y" **
{}, "x"+/
4pt/ ="p",
1290 "x"; "e" **
{}, "x"+/
4pt/ ="q",
1291 "e"; "x" **
{}, "e"+/
4pt/ ="r",
1292 "e"; "x1" **
{}, "e"+/
4pt/ ="s",
1293 "x"; "e" **
{} ?="c" ?(
0.5)/-
4pt/ ="cx" ?(
0.5)/
4pt/ ="cy",
1298 "c" *
[@
]\cir<
4pt>
{d^u
};
1302 "x1" **
\dir{-
}?>*
\dir{>
}}
1303 "x1"
[d
] :`r
[rd
] `d "xor2" "xor2"
1304 "x1" :
[dd
] *+
[F
]{D
}="d"
[l
] {K
} :"d"
1306 :
[dd
] *+
[F
]{\mathstrut x_
{n-
2}}
1309 \caption{Encryption and decryption using CBC mode with ciphertext stealing
}
1310 \label{fig:cbc-steal
}
1313 Encrypting messages shorter than the block involves `IV stealing' -- using
1314 the IV instead of the ciphertext from the last full-length block -- which is
1315 a grotty hack but works fine if IVs are random; if the IVs are encrypted
1316 counters then there's nothing (modifiable) to steal from.
1318 We formally present a description of a randomized CBC stealing mode.
1320 \begin{definition
}[CBC mode with ciphertext stealing
]
1321 \label{def:cbc-steal
}
1322 Let $P
\colon \keys P
\times \Bin^
\ell \to \Bin^
\ell$ be a pseudorandom
1323 permutation. Let $c$ be a generalized counter on $
\Bin^
\ell$. We define
1324 the randomized symmetric encryption scheme
1325 $
\Xid{\E}{CBC$\$$-steal
}^P = (
\Xid{G
}{CBC$\$$-steal
}^P,
1326 \Xid{E
}{CBC$\$$-steal
}^P,
\Xid{D
}{CBC\$-steal
}^P)$ for messages in $
\Bin^*$
1329 Algorithm $
\Xid{G
}{CBC$\$$-steal
}^P()$: \+ \\
1330 $K
\getsr \keys P$; \\
1332 \- \\
[\medskipamount]
1333 Algorithm $
\Xid{E
}{CBC$\$$-steal
}^P(K, x)$: \+ \\
1334 $t
\gets |x|
\bmod \ell$; \\
1335 \IF $t
\ne 0$
\THEN $x
\gets x
\cat 0^
{\ell-t
}$; \\
1336 $v
\getsr \Bin^
\ell$; \\
1337 $y
\gets v
\cat \id{cbc-encrypt
}(K, v, x)$; \\
1338 \IF $t
\ne 0$
\THEN \\
\ind
1339 $b
\gets |y| -
2\ell$; \\
1340 $y
\gets $\=$y
[0 \bitsto b
] \cat
1341 y
[b +
\ell \bitsto |y|
] \cat {}$ \\
1342 \>$y
[b
\bitsto b + t
]$; \- \\
1345 Algorithm $
\Xid{D
}{CBC$\$$-steal
}^P(K, y)$: \+ \\
1346 \IF $|y| <
\ell$
\THEN \RETURN $
\bot$; \\
1347 $v
\gets y
[0 \bitsto \ell]$; \\
1348 $t = |y|
\bmod \ell$; \\
1349 \IF $t
\ne 0$
\THEN \\
\ind
1350 $b
\gets |y| - t -
\ell$; \\
1351 $z
\gets P^
{-
1}_K(y
[b
\bitsto b +
\ell])$; \\
1352 $y
\gets $\=$y
[0 \bitsto b
] \cat
1353 y
[b +
\ell \bitsto |y|
] \cat {}$ \\
1354 \>$z
[t
\bitsto \ell]$; \- \\
1355 $x
\gets \id{cbc-decrypt
}(K, v, y
[\ell \bitsto |y|
])$; \\
1356 \IF $t
\ne 0$
\THEN \\
\ind
1357 $x
\gets x
\cat z
[0 \bitsto t
] \xor y
[b
\bitsto b + t
]$; \- \\
1362 The security of ciphertext stealing follows directly from the definition and
1363 the security CBC mode.
1365 \begin{corollary
}[Security of CBC with ciphertext stealing
]
1366 \label{cor:cbc-steal
}
1367 Let $P
\colon \keys P
\times \Bin^
\ell \to \Bin^
\ell$ be a pseudorandom
1369 \begin{eqnarray*
}[rl
]
1370 \InSec{lor-cpa
}(
\Xid{\E}{CBC$\$$-steal
}; t, q_E,
\mu_E)
1371 &
\le \InSec{lor-cpa
}
1372 (
\Xid{\E}{CBC$\$$
}; t, q_E,
\mu_E + q_E (
\ell -
1)) \\
1373 &
\le 2 \cdot \InSec{prp
}(P; t + q t_P, q) +
1374 \frac{q (q -
1)
}{2^
\ell -
2^
{\ell/
2}}
1376 where $q =
\bigl\lfloor \bigl(
\mu_E + q_E (
\ell -
1)
\bigr)/
\ell
1377 \bigr\rfloor$ and $t_P$ is some small constant.
1381 From the definition, we see that the encryption algorithm
1382 $
\Xid{E
}{CBC-steal
}$ simply pads a plaintext, encrypts it as for standard
1383 CBC mode, and postprocesses the ciphertext. Hence, if $A$ is any adversary
1384 attacking $
\Xid{\E}{CBC-steal
}$, we can construct an adversary
1385 $A'$ which simply runs $A$ except that, on each query to the encryption
1386 oracle, it pads both plaintexts, queries its CBC oracle, postprocesses the
1387 ciphertext returned, and gives the result back to $A$. The fact that
1388 plaintexts can now be up to $
\ell -
1$ bits shorter than the next largest
1389 whole number of blocks means that $B$ submits no more than $
\mu_E + q_E
1390 (
\ell -
1)$ bits of plaintext to its oracle. The required result
1391 follows then directly from theorem~
\ref{thm:cbc
}.
1394 \subsection{Proof of theorem~
\ref{thm:cbc
}}
1395 \label{sec:cbc-proof
}
1397 The techniques and notation used in this proof will also be found in several
1398 of the others. We recommend that readers try to follow this one carefully.
1400 We begin considering CBC mode using a completely random permutation. To
1401 simplify notation slightly, we shall write $n = n_L + n_E$. Our main goal is
1402 to prove the claim that there exists a garbage-emitter $W$ such that
1405 (
\Xid{\E}{CBCH
}^
{\Perm{\ell}, c, V_0
}_
{n_L,
0, n_E
};
1407 \frac{q (q -
1)
}{2 \cdot (
2^
\ell - n)
}.
1409 From this, we can apply proposition~
\ref{prop:rog-and-lor
} to obtain
1412 (
\Xid{\E}{CBCH
}^
{\Perm{\ell}, c,
\bot}_
{0,
0, n
};
1414 \frac{q (q -
1)
}{2^
\ell - n
}.
1416 and, noting that there are precisely $q =
\mu_E/
\ell$ PRP-applications, we
1417 apply proposition~
\ref{prop:enc-info-to-real
} to obtain the required result.
1419 Our garbage-emitter $W$ is a bit complicated. It chooses random but
1420 \emph{distinct
} blocks for the `ciphertext'; for the IVs, it uses $V_0$ for
1421 the first message if $n_L =
1$, and otherwise it chooses random blocks
1422 distinct from each other and the `ciphertext' blocks for the next $n_E$
1423 messages, and just random blocks for subsequent ones. The algorithm $W$ is
1424 shown in figure~
\ref{fig:cbc-garbage
}.
1428 Initialization: \+ \\
1430 $
\id{gone
} \gets \emptyset$;
1431 \- \\
[\medskipamount]
1432 Function $
\id{fresh
}()$ \+ \\
1433 $x
\getsr \Bin^
\ell \setminus \id{gone
}$; \\
1434 $
\id{gone
} \gets \id{gone
} \cup \
{ x \
}$; \\
1437 Garbage emitter $W(m)$: \+ \\
1438 \IF $i
\ge 2^
\ell$
\THEN \ABORT; \\
1439 \IF $i < n_L$
\THEN $v
\gets V_0$; \\
1440 \ELSE \IF $i < n$
\THEN $v
\gets \id{fresh
}()$; \\
1442 \ELSE $v
\getsr \Bin^
\ell$; \\
1443 $y
\gets \emptystring$; \\
1444 \FOR $j =
0$
\TO $m/
\ell$; \\
\ind
1445 $y_j
\gets \id{fresh
}()$; \\
1446 $y
\gets y
\cat y_j$; \- \\
1450 \caption{Garbage emitter $W$ for CBC mode
}
1451 \label{fig:cbc-garbage
}
1454 Fortunately, it doesn't need to be efficient: the above simulations only need
1455 to be able to do the LOR game, not the ROG one. The unpleasant-sounding
1456 \ABORT\ only occurs after $
2^
\ell$ queries. If that happens we give up and
1457 say the adversary won anyway: the claim is trivially true by this point,
1458 since the adversary's maximum advantage is
1.
1460 Now we show that this lash-up is a good imitation of CBC encryption to
1461 someone who doesn't know the key. The intuition works like this: every time
1462 we query a random permutation at a new, fresh input value, we get a new,
1463 different, random output value; conversely, if we repeat an input, we get the
1464 same value out as last time. So, in the real `result' CBC game, if all the
1465 permutation inputs are distinct, it looks just like the garbage emitted by
1466 $W$. Unfortunately, that's not quite enough: the adversary can work out what
1467 the permutation inputs ought to be and spot when there ought to have been a
1468 collision but wasn't. So we'll show that, provided all the $P$-inputs --
1469 values which
\emph{would
} be input to the permutation if we're playing that
1470 game -- are distinct, the two games look identical.
1472 We need some notation to describe the values in the game. Let $c_i = c(i)$
1473 be the $i$th counter value, for $
0 \le i < n_E$, and let $v_i$ be the $i$th
1474 initialization vector, where $v_0 = V_0$ is as given if $n_L =
1$, $v_i =
1475 P(c_i - n_L)$ if $n_L
\le i < n$, and $v_i
\inr \Bin^
\ell$ if $n
\le i <
1476 q_E$. Let $q' =
\mu_E/
\ell = q - n$ be the total number of plaintext blocks
1477 in the adversary's queries, let $x_i$ be the $i$th plaintext block queried,
1478 let $y_i$ be the $i$th ciphertext block returned, let
1479 \
[ w_i =
\begin{cases
}
1480 v_j & if block $i$ is the first block of the $j$th query, and \\
1483 and let $z_i = x_i
\xor w_i$, all for $
0 \le i < q'$. This is summarized
1484 diagramatically in figure~
\ref{fig:cbc-proof-notation
}. The $P$-inputs are
1485 now precisely the $c_i$ and the $z_i$. We'll denote probabilities in the
1486 `result' game as $
\Pr_R[\cdot]$ and in the `garbage' game as $
\Pr_G[\cdot]$.
1490 \begin{vgraph
}{cbc-notation-a
}
1491 [] !
{<
1.33cm,
0cm>: <
0cm,
1cm>::
}
1492 {c_i
} :
[r
] *+
[F
]{E
}="e"
[u
] {K
} :"e" :
[r
] {v_i
}
1494 \begin{vgraph
}{cbc-notation-b
}
1495 [] !
{<
1.33cm,
0cm>: <
0cm,
1cm>::
}
1496 {x_i
} :
[r
] *
{\xor} ="xor" :
[r
] {z_i
}
1497 :
[r
] *+
[F
]{E
}="e"
[u
] {K
} :"e" :
[r
] {y_i
}
1498 "xor"
[u
] {w_i
} ="w" :"xor"
1499 "w"
[lu
] {v_j
} ="v" :"w"
1500 "w"
[ru
] {y_
{i-
1}} ="y" :"w"
1501 "v" :@
{.
}|-*+
\hbox{or
} "y"
1505 \caption{Notation for the proof of theorem~
\ref{thm:cbc
}.
}
1506 \label{fig:cbc-proof-notation
}
1509 Let $C_r$ be the event, in either game, that $z_i = z_j$ for some $
0 \le i <
1510 j < r$, or that $z_i = c_j$ for some $
0 \le i < r$ and some $
0 \le j < n_E$.
1511 We need to bound the probability that $C_
{q'
}$ occurs in both the `result'
1512 and `garbage' games. We'll do this inductively. By the definition,
1513 $
\Pr_R[C_0
] =
\Pr_G[C_0
] =
0$.
1515 Firstly, tweak the games so that all of the IVs corresponding to counters are
1516 chosen at the beginning, instead of as we go along. Obviously this doesn't
1517 make any difference to the adversary's view of the proceedings, but it makes
1518 our analysis easier.
1520 Let's assume that $C_r$ didn't happen; we want the probability that $C_
{r+
1}$
1521 did, which is obviously just the probability that $z_r$ collides with some
1522 $z_i$ for $
0 \le i < r$ or some $c_i$ for $
0 \le i < n$. At this point, the
1523 previous $z_i$ are fixed. So:
1526 \Pr[C_
{r+
1} |
\bar{C
}_r
]
1527 =
\sum_{z
\in \Bin^
\ell} \biggl(
1528 \sum_{0\le i<n
} \Pr[z = c_i
] +
1529 \sum_{0\le i<r
} \Pr[z = z_i
]
1530 \biggr)
\cdot \Pr[z_r = z
]
1532 Now note that $z_r = w_r
\xor x_r$. We've no idea how $x_r$ was chosen; but,
1533 one of the following cases holds.
1535 \item If $x_r$ is the first block of the first plaintext, i.e., $r =
0$, and
1536 $n_L =
1$, then $w_r = v_0$. However, in this case we know that $n_E =
0$
1537 by hypothesis. There are no $z_i$ which $z_r$ might collide with, so the
1538 probability of a collision is zero.
1539 \item If $x_r$ is the first block of plaintext $i$, and $
0 \le i < n$, then
1540 $w_r = v_i$, and was chosen at random from a set of $
2^
\ell - i
\le 2^
\ell
1541 - n
\le 2^
\ell - n - r$ possibilities, either by our random permutation or
1542 by $W$. We know $x_r$ is independent of $w_r$ because none of the previous
1543 $P$-inputs were equal to $c_i$, by our assumption of $
\bar{C
}_r$.
1544 \item If $x_r$ is the first block of plaintext $i$, and $n
\le i < q'$, then
1545 $w_r = v_i$, and was chosen at random from all $
2\ell$ possible $
\ell$-bit
1546 blocks. We know $x_r$ is independent of $w_r$ because we just chose $w_r$
1547 at random, after $x_r$ was chosen.
1548 \item Otherwise, $x_r$ is a subsequent block in some message, and $w_r =
1549 y_
{r-
1}$, and was chosen at random from a set of $
2^
\ell - n - r$
1550 possibilities, either by our random permutation or by $W$. We know $x_r$
1551 is independent of $w_r$ because $z_
{r-
1}$ is a new $P$-input, by our
1552 assumption of $
\bar{C
}_r$.
1554 So, except in case~
1, which isn't a problem anyway, $w_r$ is independent of
1555 $x_r$, and chosen uniformly at random from a set of at least $
2^
\ell - r - n$
1556 elements, in either game -- so we can already see that $
\Pr_R[C_i
] =
1557 \Pr_G[C_i
]$ for any $i
\ge 0$. Finally, the $z_i$ and $c_i$ are all
1558 distinct, so the $z_i
\xor x$ and $c_i
\xor x$ must all be distinct, for any
1560 \begin{eqnarray
}[rl
]
1561 \Pr[C_
{r+
1} |
\bar{C
}_r
]
1562 & =
\sum_{x
\in \Bin^
\ell} \biggl(
1563 \sum_{0\le i<n
} \Pr[w_r = x
\xor c_i
] +
1564 \sum_{0\le i<r
} \Pr[w_r = x
\xor z_i
]
1565 \biggr)
\cdot \Pr[x_r = x
] \\
1566 &
\le \sum_{x
\in \Bin^
\ell} \frac{r + n
}{2^
\ell - r - n
} \Pr[x_r = x
]
1567 =
\frac{r + n
}{2^
\ell - r - n
} \sum_{x
\in \Bin^
\ell} \Pr[x_r = x
] \\
1568 & =
\frac{r + n
}{2^
\ell - r - n
}.
1570 Now we're almost home. All the $c_i$ and $z_i$ are distinct; all the $v_i$
1571 and $y_i$ are random, assuming $C_
{q'
}$. We can bound $
\Pr[C_
{q'
}]$ thus:
1574 \le \sum_{0<i
\le q'
} \Pr[C_i |
\bar{C
}_
{i-
1}]
1575 \le \sum_{0\le i
\le q'
} \frac{i + n -
1}{2^
\ell - i - n +
1}
1577 Now, let $i' = i + n -
1$. Then
1580 \le \sum_{n-
1\le i'
\le q'+n-
1} \frac{i'
}{2^
\ell - i'
}
1581 \le \sum_{0\le i'<q
} \frac{i'
}{2^
\ell - q
}
1582 =
\frac{q (q -
1)
}{2 \cdot (
2^
\ell - q)
}
1585 Finally, let $R$ be the event that the adversary returned
1 at the end of the
1586 game -- indicating a guess of `result'. Then, noting as we have, that
1587 $
\Pr_R[C_
{q'
}] =
\Pr_G[C_
{q'
}]$, we get this:
1588 \begin{eqnarray
}[rl
]
1589 \Adv{rog-cpa-$W$
}{\Xid{\E}{CBCH
}^
{P, c, n
}}(A)
1590 & =
\Pr_R[R
] -
\Pr_G[R
] \\
1591 &
\begin{eqnalign
}[rLl
][b
]
1592 {} = & (
\Pr_R[R | C_
{q'
}] \Pr_R[C_
{q'
}] +
1593 \Pr_R[R |
\bar{C
}_
{q'
}] \Pr_R[\bar{C
}_
{q'
}]) -
{} \\
1594 & & (
\Pr_G[R | C_
{q'
}] \Pr_R[C_
{q'
}] +
1595 \Pr_G[R |
\bar{C
}_
{q'
}] \Pr_G[\bar{C
}_
{q'
}])
1597 & =
\Pr_R[R | C_
{q'
}] \Pr_R[C_
{q'
}] -
\Pr_G[R | C_
{q'
}] \Pr_G[C_
{q'
}] \\
1598 &
\le \Pr[C_
{q'
}] \le \frac{q (q -
1)
}{2 \cdot (
2^
\ell - q)
}
1603 %%%--------------------------------------------------------------------------
1605 \section{Ciphertext feedback (CFB) encryption
}
1608 \subsection{Description
}
1609 \label{sec:cfb-desc
}
1611 Suppose $F$ is an $
\ell$-bit-to-$L$-bit pseudorandom function, and let $t
\le
1612 L$. CFB mode works as follows. Given a message $X$, we divide it into
1613 $t$-bit blocks $x_0$, $x_1$, $
\ldots$, $x_
{n-
1}$. Choose an initialization
1614 vector $v
\in \Bin^
\ell$. We maintain a
\emph{shift register
} $s_i$, whose
1615 initial value is $v$. To encrypt a block $x_i$, we XOR it with the result of
1616 passing the shift register through the PRF, forming $y_i$, and then update
1617 the shift register by shifting in the ciphertext block $y_i$. That is,
1620 y_i = x_i
\xor F_K(s_i)
\qquad
1621 s_
{i+
1} = s_i
\shift{t
} y_i \
\text{(for $
0 \le i < n$)
}.
1623 Decryption follows from noting that $x_i = y_i
\xor F_K(s_i)$. See
1624 figure~
\ref{fig:cfb
} for a diagrammatic representation.
1626 Also, we observe that the final plaintext block needn't be $t$ bits long: we
1627 can pad it out to $t$ bits and truncate the result without affecting our
1631 \begin{cgraph
}{cfb-mode
}
1632 [] !
{<
0.425cm,
0cm>: <
0cm,
0.5cm>::
}
1633 *+=(
2,
0)+
[F
]{\mathstrut v
} ="v" :|<>(
0.35)@
{/
}_<>(
0.35)
{\ell}[rrrrr
]
1634 *+
[o
][F
]{\shift{t
}} ="shift"
1635 [ll
] :|-@
{/
}^-
{\ell}[dd
] *+
[F
]{E
} ="e"
[ll
] {K
} :"e"
1636 :|-@
{/
}^-
{t
}[dd
] *
{\xor} ="xor"
1637 [lll
] *+=(
2,
0)+
[F
]{\mathstrut x_0
} :|-@
{/
}_-
{t
} "xor"
1638 :|-@
{/
}^-
{t
}[ddd
] *+=(
2,
0)+
[F
]{\mathstrut y_0
}
1639 "xor"
[d
] :`r "shift" "shift"|-@
{/
}_-
{t
}
1640 :|-@
{/
}_-
{\ell}[rrrrrrr
] *+
[o
][F
]{\shift{t
}} ="shift"
1641 [ll
] :|-@
{/
}^-
{\ell}[dd
] *+
[F
]{E
} ="e"
[ll
] {K
} :"e"
1642 :|-@
{/
}^-
{t
}[dd
] *
{\xor} ="xor"
1643 [lll
] *+=(
2,
0)+
[F
]{\mathstrut x_1
} :|-@
{/
}_-
{t
} "xor"
1644 :|-@
{/
}^-
{t
}[ddd
] *+=(
2,
0)+
[F
]{\mathstrut y_1
}
1645 "xor"
[d
] :`r "shift" "shift"|-@
{/
}_-
{t
}
1646 :@
{-->
}|-@
{/
}_-
{\ell}[rrrrrrr
] *+
[o
][F
]{\shift{t
}} ="shift"
1647 [ll
] :@
{-->
}|-@
{/
}^-
{\ell}[dd
] *+
[F
]{E
} ="e"
[ll
] {K
} :"e"
1648 :@
{-->
}|-@
{/
}^-
{t
}[dd
] *
{\xor} ="xor"
1649 [lll
] *+=(
2,
0)+
[F--
]{\mathstrut x_i
} :@
{-->
}|-@
{/
}_-
{t
} "xor"
1650 :@
{-->
}|-@
{/
}^-
{t
}[ddd
] *+=(
2,
0)+
[F--
]{\mathstrut y_i
}
1651 "xor"
[d
] :@
{-->
} `r "shift" "shift"|-@
{/
}_-
{t
}
1652 [rrrrrdd
] *+
[F
]{E
} ="e"
1653 "shift" :@
{-->
}`r "e" |-@
{/
}_-
{\ell} "e"
1655 :|-@
{/
}^-
{t
}[dd
] *
{\xor} ="xor"
1656 [lll
] *+=(
2,
0)+
[F
]{\mathstrut x_
{n-
1}} :|-@
{/
}_-
{t
} "xor"
1657 :|-@
{/
}^-
{t
}[ddd
] *+=(
2,
0)+
[F
]{\mathstrut y_
{n-
1}}
1660 \caption{Encryption using CFB mode
}
1664 \begin{definition
}[CFB algorithms
]
1665 For any function $F
\colon \Bin^
\ell \to \Bin^t$, any initialization vector
1666 $v
\in \Bin^
\ell$, any plaintext $x
\in \Bin^*$ and any ciphertext $y
\in
1667 \Bin^*$, we define PRF encryption mode $
\id{CFB
} = (
\id{cfb-encrypt
},
1668 \id{cfb-decrypt
})$ as follows:
1670 Algorithm $
\id{cfb-encrypt
}(F, v, x)$: \+ \\
1673 $x
\gets x
\cat 0^
{t
\lceil L/t
\rceil - L
}$; \\
1674 $y
\gets \emptystring$; \\
1675 \FOR $i =
0$
\TO $(|x| - t')/t$
\DO \\
\ind
1676 $x_i
\gets x
[ti
\bitsto t(i +
1)
]$; \\
1677 $y_i
\gets x_i
\xor F(s)$; \\
1678 $s
\gets s
\shift{t
} y_i$; \\
1679 $y
\gets y
\cat y_i$; \- \\
1680 \RETURN $(s, y
[0 \bitsto L
])$;
1682 Algorithm $
\id{cfb-decrypt
}(F, v, y)$: \+ \\
1685 $y
\gets y
\cat 0^
{t
\lceil L/t
\rceil - L
}$; \\
1686 $x
\gets \emptystring$; \\
1687 \FOR $i =
0$
\TO $(|x| - t')/t$
\DO \\
\ind
1688 $y_i
\gets y
[ti
\bitsto t(i +
1)
]$; \\
1689 $x_i
\gets x_i
\xor F(s)$; \\
1690 $s
\gets s
\shift{t
} y_i$; \\
1691 $x
\gets x
\cat x_i$; \- \\
1692 \RETURN $x
[0 \bitsto L
]$;
1694 We now define the schemes $
\Xid{\E}{CFB$\$$
}^F$,
1695 $
\Xid{\E}{CFBC
}^
{F, c
}$, $
\Xid{\E}{CFBE
}^
{F, c
}$, and
1696 $
\Xid{\E}{CFBL
}^
{F, V_0
}$ according to
1697 definition~
\ref{def:enc-scheme
}; and we define the hybrid scheme
1698 $
\Xid{\E}{CFBH
}^
{F, V_0, c
}_
{n_L, n_C, n_E
}$ according to
1699 definition~
\ref{def:enc-hybrid
}.
1702 \subsection{Sliding strings
}
1704 Consider for a moment the mode CFBL, i.e., with carry-over of IV from one
1705 plaintext to the next, with $t <
\ell$. Then we find that some IVs are
1708 Pretend for a moment that we're an adversary playing the LOR-CPA game using
1709 an ideal random function $F
\inr \Func{\ell}{t
}$, and that the initial IV
1710 $V_0 =
0^
\ell$. We choose two distinct
8-bit plaintexts $l$ and $r$ as our
1711 first left-or-right query. With probability $
2^
{-t
}$, the result of
1712 encrypting that first query is $
0^t$. However, in this case, the IV for the
1713 \emph{next
} query is $V_0
\shift{t
} 0^t =
0^
\ell = V_0$. If this happens,
1714 we have only to submit the pair $(l, l)$ as our second query. If the
1715 ciphertext to this second query also comes back zero, we guess that we're
1716 dealing with a left oracle; otherwise we guess right. If we don't get lucky
1717 with our first query, we just guess randomly.
1721 Adversary $S^
{E(
\cdot,
\cdot)
}$: \+ \\
1722 $l
\gets 0^t$; $r
\gets 0^
{t -
1} 1$; \\
1723 $y
\gets E(l, r)$; \\
1724 \IF $y
[\ell \bitsto \ell + t
] =
0^t$
\THEN \\
\ind
1725 \IF $E(l, l) = y$
\THEN $b
\gets 0$
\ELSE $b
\gets 1$; \- \\
1727 $b
\getsr \
{0,
1\
}$; \- \\
1730 \caption{Adversary $S$ attacking $
\Xid{\E}{CFBL
}^
{\Func{\ell}{t
},
0^
\ell}$
}
1731 \label{fig:adv-sliding
}
1734 This attack is shown more formally as adversary~$S$ in
1735 figure~
\ref{fig:adv-sliding
}. Its resource usage is almost trivial --
1736 negligible computation and at most two encryption queries. However, its
1737 advantage is quite good:
1738 \
[ \Adv{LOR-CPA
}{\Xid{\E}{CFBL
}^
{\Func{\ell}{t
},
0^
\ell}}(S) =
1739 \frac{1}{2^t
} \biggl(
1 -
\frac{1}{2^t
} \biggr).
1742 This attack works because $V_0
[t
\bitsto \ell] = V_0
[0 \bitsto \ell - t
]$.
1743 There are similar attacks for other such relationships. The following
1744 definition characterizes these kinds of `bad' IVs.
1746 \begin{definition
}[Sliding strings
]
1748 We say that an $
\ell$-bit string $x$
\emph{$t$-slides
} if there exist
1749 integers $i$ and $j$ such that $
0 \le j < i <
\ell/t$ and $x
[i t
\bitsto
1750 \ell] = x
[j t
\bitsto \ell - (i - j) t
]$.
1753 For all $
\ell >
0$ and $t <
\ell$, the string $
0^
{\ell-
1} 1$ does not
1757 \subsection{Security of CFB mode
}
1759 %% I suspect David will want to put some negative results here, and complain
1760 %% about Alkassar et al.'s alleged proof. I'll press on with the positive
1763 %% The problems come when $t < \ell$. Then C-mode isn't necessarily secure
1764 %% (well, we get a similar bound with $t$ instead of $\ell$, which isn't very
1765 %% impressive). The L-mode needs careful selection of the initial IV.
1767 \begin{theorem
}[Security of CFB mode
]
1769 Let $F$ be a pseudorandom function from $
\Bin^
\ell$ to $
\Bin^t$; let $V_0
1770 \in \Bin^
\ell$ be a non-$t$-sliding string; let $c$ be a generalized
1771 counter in $
\Bin^
\ell$; and let $n_L$, $n_C$, $n_E$ and $q_E$ be
1772 nonnegative integers; and furthermore suppose that
1774 \item $n_L + n_C + n_E
\le q_E$,
1775 \item $n_L =
0$, or $n_C = n_E =
0$, or $
\ell \le t$ and $V_0
\ne c(i)$
1776 for any $n_L
\le i < n_L + n_C + n_E$, and
1777 \item either $n_C =
0$ or $
\ell \le t$.
1779 Then, for any $t_E$ and $
\mu_E$, and whenever
1781 \
[ \InSec{lor-cpa
}(
\Xid{\E}{CFBH
}^
{F, V_0, c
}_
{n_L, n_C, n_E
};
1782 t_E, q_E,
\mu_E)
\le
1783 2 \cdot \InSec{prf
}(F; t_E + q t_F, q) +
\frac{q (q -
1)
}{2^
\ell}
1785 where $q =
\bigl\lfloor \bigl(
\mu_E + q_E (t -
1)
\bigr)/t
\bigr\rfloor +
1786 n_E$, and $t_F$ is some small constant.
1789 The proof is a bit involved; we postpone it until
1790 section~
\ref{sec:cfb-proof
}.
1794 Let $F$, $c$ and $V_0$ be as in theorem~
\ref{thm:cfb
}. Then for any $t_E$,
1796 \begin{eqnarray*
}[rl
]
1797 \InSec{lor-cpa
}(
\Xid{\E}{CFB$\$$
}^F; t_E, q_E,
\mu_E)
1798 &
\le 2 \cdot \InSec{prf
}(F; t_E + q t_F, q) +
\frac{q (q -
1)
}{2^
\ell}
1800 \InSec{lor-cpa
}(
\Xid{\E}{CFBE
}^
{F, c
}; t_E, q_E,
\mu_E)
1801 &
\le 2 \cdot \InSec{prf
}(F; t_E + q' t_F, q') +
1802 \frac{q' (q' -
1)
}{2^
\ell}
1804 \InSec{lor-cpa
}(
\Xid{\E}{CFBL
}^
{F, V_0
}; t_E, q_E,
\mu_E)
1805 &
\le 2 \cdot \InSec{prf
}(F; t_E + q t_F, q) +
\frac{q (q -
1)
}{2^
\ell}
1807 \tabpause{and, if $
\ell \le t$,
}
1808 \InSec{lor-cpa
}(
\Xid{\E}{CFBC
}^
{F, c
}; t_E, q_E,
\mu_E)
1809 &
\le 2 \cdot \InSec{prf
}(F; t_E + q t_F, q) +
\frac{q (q -
1)
}{2^
\ell}
1811 where $q =
\bigl\lfloor \bigl(
\mu_E + q_E (t -
1)
\bigr)/t
\bigr\rfloor +
1812 n_E$, $q' = q + q_E$, and $t_F$ is some small constant.
1815 Follows from theorem~
\ref{thm:cfb
} and proposition~
\ref{prop:enc-hybrid
}.
1820 Let $P$ be a pseudorandom permutation on $
\Bin^
\ell$, and let $c$ and $V_0$
1821 be as in theorem~
\ref{thm:cfb
}. Then for any $t_E$, $q_E$ and $
\mu_E$,
1822 \begin{eqnarray*
}[rl
]
1823 \InSec{lor-cpa
}(
\Xid{\E}{CFB$\$$
}^P; t_E, q_E,
\mu_E)
1824 &
\le 2 \cdot \InSec{prp
}(P; t_E + q t_F, q) +
1825 \frac{q (q -
1)
}{2^
{\ell-
1}}
1827 \InSec{lor-cpa
}(
\Xid{\E}{CFBE
}^
{P, c
}; t_E, q_E,
\mu_E)
1828 &
\le 2 \cdot \InSec{prp
}(P; t_E + q' t_F, q') +
1829 \frac{q' (q' -
1)
}{2^
{\ell-
1}}
1831 \InSec{lor-cpa
}(
\Xid{\E}{CFBL
}^
{P, V_0
}; t_E, q_E,
\mu_E)
1832 &
\le 2 \cdot \InSec{prp
}(P; t_E + q t_F, q) +
1833 \frac{q (q -
1)
}{2^
{\ell-
1}}
1835 \tabpause{and, if $
\ell \le t$,
}
1836 \InSec{lor-cpa
}(
\Xid{\E}{CFBC
}^
{P, c
}; t_E, q_E,
\mu_E)
1837 &
\le 2 \cdot \InSec{prp
}(P; t_E + q t_F, q) +
1838 \frac{q (q -
1)
}{2^
{\ell-
1}}
1840 where $q =
\bigl\lfloor \bigl(
\mu_E + q_E (t -
1)
\bigr)/t
\bigr\rfloor +
1841 n_E$, $q' = q + q_E$, and $t_F$ is some small constant.
1844 Follows from corollary~
\ref{cor:cfb-prf
} and
1845 proposition~
\ref{prop:prps-are-prfs
}.
1848 \subsection{Proof of theorem~
\ref{thm:cfb
}}
1849 \label{sec:cfb-proof
}
1851 Our proof follows the same lines as for CBC mode: we show the ROG-CPA
1852 security of hybrid-CFB mode using an ideal random function, and then apply
1853 our earlier results to complete the proof. However, the ROG-CPA result will
1854 be useful later when we consider the security of OFB mode, so we shall be a
1855 little more formal about defining it.
1857 The garbage emitter is in some sense the `perfect' one: it emits a `correct'
1858 IV followed by a uniform random string of the correct length.
1860 \begin{definition
}[The $W_\$$ garbage emitter
]
1861 Let natural numbers $n_L$, $n_C$, and $V_0
\in \Bin^
\ell$ be given; then we
1862 define the garbage emitter $W_\$$ as follows.
1864 Initialization: \+ \\
1867 \- \\
[\medskipamount]
1868 Garbage emitter $W_\$(m)$: \+ \\
1869 \IF $i < n_L$
\THEN $v'
\gets v$; \\
1870 \ELSE \IF $n_L
\le i < n_L + n_C$
\THEN $v'
\gets c(i)$; \\
1871 \ELSE \IF $n_L + n_C
\le i$
\THEN $v'
\getsr \Bin^
\ell$; \\
1873 $m'
\gets t
\lfloor (m + t -
1)/t
\rfloor$; \\
1874 $y
\getsr \Bin^
{m'
}$; \\
1875 $v
\gets v'
\shift{m'
} y$; \\
1876 \RETURN $(v', y
[0 \bitsto m
])$
1880 We now show that CFB mode with a random function is hard to distinguish from
1882 \begin{lemma
}[Pseudorandomness of CFB mode
]
1884 Let $
\ell$, $t$, $n_L$, $n_C$, $n_E$, $q_E$, $c$, $V_0$, and $q$ be as in
1885 theorem~
\ref{thm:cfb
}. Then, for any $t_E$ and $
\mu_E$,
1886 \
[ \InSec{rog-cpa-$W_\$$
}
1887 (
\Xid{\E}{CFBH
}^
{\Func{\ell}{t
}, V_0, c
}_
{n_L, n_C, n_E
};
1889 \frac{q (q -
1)
}{2^
{\ell+
1}}.
1892 Theorem~
\ref{thm:cfb
} follows from this result by application of
1893 propositions
\ref{prop:rog-and-lor
} and~
\ref{prop:enc-info-to-real
}. It
1894 remains therefore for us to prove lemma~
\ref{lem:cfb-rog
}.
1896 To reduce the weight of notation, let us agree to suppress the adornments on
1897 $
\Adv{}{}$ and $
\InSec{}$ symbols. Also, let $m_L = n_L$; let $m_C$ = $n_L +
1898 n_C$; and let $m_E = n_L + n_C + n_E$. (Remember: the $m$s are
1899 cu
\textit{m
}ulative.)
1901 The truncation of ciphertext blocks makes matters complicated. Let us say
1902 that an adversary is
\emph{block-respecting
} if all of its plaintext queries
1903 are a multiple of $t$ bits in length; obviously all of the oracle responses
1904 for a block-respecting adversary are also a multiple of $t$ bits in length.
1906 Let $A'$ be a block-respecting adversary querying a total of $
\mu_E$ bits of
1907 plaintext queries; then
1908 \
[ \Adv{}{}(A')
\le \frac{q (q -
1)
}{2^
{\ell+
1}} \
]
1909 where $q =
\mu_E/t$.
1911 Lemma~
\ref{lem:cfb-rog
} follows from this claim: if $A$ is any adversary,
1912 then we construct a block-respecting adversary $A'$ by padding $A$'s
1913 plaintext queries and truncating the oracle responses; and if $A$ makes $q_E$
1914 queries totalling $
\mu_E$ bits, then the total bits queried by $A'$ is no
1915 more than $
\bigl\lfloor\bigl(
\mu_E + q_E (t -
1)
\bigr)
\bigr\rfloor$ bits.
1916 We now proceed to the proof of the above claim.
1918 Suppose, then, that we are given a block-respecting adversary $A$ which makes
1919 $q$ queries to its encryption oracle. Let $F(
\cdot)$ denote the application
1920 of the random function. We want to show that, provided all of the $F$-inputs
1921 are distinct, the $F$-outputs are uniformly random, and hence the CFB
1922 ciphertexts are uniformly random. As for the CBC case, life isn't that good
1923 to us: we have to deal with the case where the adversary can see that two
1924 $F$-inputs would have collided, and therefore that a garbage string couldn't
1925 have been generated by CFB encryption of his plaintext.
1927 Our notation will be similar to, yet slightly different from, that of
1928 section~
\ref{sec:cbc-proof
}.
1930 Let $q' = q - n_E$ be the number of $t$-bit plaintext blocks the adversary
1931 submits, and for $
0 \le i < q'$, let $x_i$ be the $i$th plaintext block
1932 queried, and let $y_i$ be the $i$th ciphertext block returned.
1934 For $m_L
\le i < m_E$, let $c_i = c(i)$ be the $i$th counter value. For $
0
1935 \le i < q_E$ let $v_i$ be the $i$th initialization vector, i.e.,
1936 \
[ v_i =
\begin{cases
}
1937 V_0 & if $i =
0$ and $n_L >
0$; \\
1938 v_
{i-
1} \shift{t
} Y_
{i-
1}
1939 & if $
1 \le i < m_L$ and $Y_
{i-
1}$ was the ciphertext
1940 from query $i -
1$; \\
1941 c_i & if $m_L
\le i < m_C$; \\
1942 F(c_i) & if the oracle is `result', and $m_C
\le i < m_E$;
1944 R_i & for some $R_i
\inr \Bin^
\ell$, otherwise.
1947 Note that the only difference in the $v_i$ between the `result' and `garbage'
1948 games occurs in the encrypted-counters phase. Furthermore, if no other
1949 $F$-input is equal to any $c_i$ for $m_C
\le i < m_E$ then the IVs are
1950 identically distributed.
1952 Now, for $
0 \le i < q'$, define
1953 \
[ z_i =
\begin{cases
}
1954 v_j & if block $i$ is the first block of the
1956 z_
{i-
1} \shift{t
} y_
{i-
1} & otherwise
1959 and let $w_i = x_i
\xor y_i$. In the `result' game, we have $w_i = F(z_i)$,
1960 of course. All of this notation is summarized diagrammatically in
1961 figure~
\ref{fig:cfb-proof-notation
}. The $F$-inputs are precisely the $z_i$
1962 and $c_i$ for $m_C
\le i < m_E$.
1964 We'll denote probabilities in the `result' game as $
\Pr_R[\cdot]$ and in the
1965 `garbage' game as $
\Pr_G[\cdot]$.
1969 \begin{vgraph
}{cfb-notation-a
}
1970 [] !
{<
1.333cm,
0cm>: <
0cm,
1cm>::
}
1971 {z_i
} ="z" :|-@
{/
}_-
{\ell}[r
] *+
[F
]{F
} ="F"
1972 :|-@
{/
}_-
{t
}[r
] {w_i
} ="w" :|-@
{/
}_-
{t
}[r
] *
{\xor} ="xor"
1973 "xor"
[u
] {x_i
} ="x" :|-@
{/
}^-
{t
}"xor" :|-@
{/
}^-
{t
}[d
] {y_i
} ="y"
1974 "z"
[lu
] {v_j
} ="v" :"z"
1975 "z"
[ru
] {z_
{i-
1} \shift{t
} y_
{i-
1}} ="y" :"z"
1976 "v" :@
{.
}|-*+
\hbox{or
} "y"
1980 \caption{Notation for the proof of lemma~
\ref{lem:cfb-rog
}.
}
1981 \label{fig:cfb-proof-notation
}
1984 Let $C_r$ be the event, in either game, that $z_i = z_j$ for some $
0 \le i <
1985 j < r$, or that $z_i = c_j$ for some $
0 \le i < r$ and some $m_C
\le j <
1988 Let's assume that $C_r$ didn't happen; we want the probability that $C_
{r+
1}$
1989 did, which is just the probability that $z_r$ collides with some $z_i$ where
1990 $
0 \le i < r$, or some $c_i$ for $m_C
\le i < m_E$. Observe that, under this
1991 assumption, all the $w_i$, and hence the $y_i$, are uniformly distributed,
1992 and that therefore the two games are indistinguishable.
1994 One of the following cases holds.
1996 \item If $r =
0$ and $m_L >
0$ then $z_r = V_0$. There is no other $z_i$ yet
1997 for $z_r$ to collide with, though it might collide with some encrypted
1998 counter $F(c_i)$, with probability $n_E/
2^
\ell$.
1999 \item If $z_r = c_i$ is the IV for some message $i$ where $m_L
\le i < m_C$,
2000 life is a bit complicated. It can't collide with $V_0$ or other $c_i$ by
2001 assumption; the encrypted counters and random IVs haven't been chosen yet;
2002 and either $n_C =
0$ (in which case there's nothing to do here anyway) or
2003 $
\ell \le t$, so there are no $z_i$ containing partial copies of $V_0$ to
2004 worry about. This leaves non-IV $z_i$: again, $
\ell \le t$, so $z_i =
2005 y_i
[t -
\ell \bitsto t
]$, which is random by our assumption of $
\bar{C
}_r$;
2006 hence a collision with one of these $z_i$ occurs with probability at most
2008 \item If $z_r$ is the IV for some message $i$ where $m_C
\le i < m_E$, then
2009 it can collide with previous $z_i$ or either previous or future $c_i$. We
2010 know, however, that no $F$-input has collided with $c_i$, so in the
2011 `result' game, $z_r = F(c_r)$ is uniformly distributed; in the `garbage'
2012 game, $W_\$$ generates $z_r$ at random anyway. It collides, therefore,
2013 with probability at most $(r + n_E)/
2^
\ell$.
2014 \item If $z_r$ is the IV for some message $i$ where $m_E
\le i < q'$ then
2015 $z_r$ was chosen uniformly at random. Hence it collides with probability
2016 at most $(r + n_E)/
2^
\ell$.
2017 \item Finally, either $z_r$ is not the IV for a message, or it is, but the
2018 message number $i < n_L$, so in either case, $z_r = z_
{r-
1} \shift{t
}
2019 y_
{r-
1}$. We have two subcases to consider.
2021 \item If $
1 \le r <
\ell/t$ (we dealt with the case $r =
0$ above) then
2022 some of $V_0$ remains in the shift register. If $z_r$ collides with some
2023 $z_i$, for $
0 \le i < r$, then we must have $z_r
[0 \bitsto \ell - t r
] =
2024 z_i
[0 \bitsto \ell - t r
]$; but $z_r
[0 \bitsto \ell - t r
] = V_0
[t r
2025 \bitsto \ell]$, and $z_i
[0 \bitsto \ell - t r
] = V_0
[t i
\bitsto \ell - t
2026 (r - i)
]$, i.e., we have found a $t$-sliding of $V_0$, which is
2027 impossible by hypothesis. Hence, $z_r$ cannot collide with any earlier
2028 $z_i$. Also by hypothesis, $n_C = n_E =
0$ if $
\ell > t$, so $z_r$
2029 cannot collide with any counters $c_i$.
2030 \item Suppose, then, that $r
\ge \ell/t$. For $
0 \le j <
\ell/t$, let $H_j
2031 =
\ell - t j$, $L_j =
\max(
0, H_j - t)$, and $N_j = H_j - L_j$. (Note
2032 that $
\sum_{0\le j<
\ell/t
} N_j =
\ell$.) Then $z_r
[L_j
\bitsto H_j
] =
2033 y_
{r-j-
1}[t - N_j
\bitsto t
]$; but the $y_i$ for $i < r$ are uniformly
2034 distributed. Thus, $z_r$ collides with some specific other value $z'$
2035 only with probability $
1/
2^
{\sum_j N_j
} =
1/
2^
\ell$. The overall
2036 collision probablity for $z_r$ is then at most $(r + n_E)/
2^
\ell$.
2039 In all these cases, it's clear that the collision probability is no more than
2042 The probability that there is a collision during the course of the game is
2043 $
\Pr[C_
{q'
}]$, which we can now bound thus:
2045 \Pr[C_q'
] \le \sum_{0<i
\le q'
} \Pr[C_i |
\bar{C
}_
{i-
1}]
2046 \le \sum_{0<i
\le q'
} \frac{i + n_E
}{2^
\ell}.
2048 If we set $i' = i + n_E$, then we get
2050 \Pr[C_q'
] \le \sum_{0\le i'
\le q
} \frac{i'
}{2^
\ell}
2051 =
\frac{q (q -
1)
}{2^
{\ell+
1}}.
2053 Finally, then, we can apply the same argument as we used at the end of
2054 section~
\ref{sec:cbc-proof
} to show that
2056 \Adv{}{}(A')
\le \frac{q (q -
1)
}{2^
{\ell+
1}}
2058 as claimed. This completes the proof.
2060 %%%--------------------------------------------------------------------------
2062 \section{OFB mode encryption
}
2065 \subsection{Description
}
2066 \label{sec:ofb-desc
}
2068 Suppose $F$ is an $
\ell$-bit-to-$L$-bit pseudorandom function, and let $t
\le
2069 L$. OFB mode works as follows. Given a message $X$, we divide it into
2070 $t$-bit blocks $x_0$, $x_1$, $
\ldots$, $x_
{n-
1}$. Choose an initialization
2071 vector $v
\in \Bin^
\ell$. We maintain a
\emph{shift register
} $s_i$, whose
2072 initial value is $v$. To encrypt a block $x_i$, we XOR it with the result
2073 $z_i$ of passing the shift register through the PRF, forming $y_i$, and then
2074 update the shift register by shifting in the PRF output $z_i$. That
2078 z_i = F_K(s_i)
\qquad
2079 y_i = x_i
\xor z_i
\qquad
2080 s_
{i+
1} = s_i
\shift{t
} z_i \
\text{(for $
0 \le i < n$)
}.
2082 Decryption is precisely the same operation.
2084 Also, we observe that the final plaintext block needn't be $t$ bits long: we
2085 can pad it out to $t$ bits and truncate the result without affecting our
2089 \begin{cgraph
}{ofb-mode
}
2090 [] !
{<
0.425cm,
0cm>: <
0cm,
0.5cm>::
}
2091 *+=(
2,
0)+
[F
]{\mathstrut v
} ="v" :|<>(
0.35)@
{/
}_<>(
0.35)
{\ell}[rrrrr
]
2092 *+
[o
][F
]{\shift{t
}} ="shift"
2093 [ll
] :|-@
{/
}^-
{\ell}[dd
] *+
[F
]{E
} ="e"
[ll
] {K
} :"e"
2094 :|-@
{/
}^-
{t
}[ddd
] *
{\xor} ="xor"
2095 [lll
] *+=(
2,
0)+
[F
]{\mathstrut x_0
} :|-@
{/
}_-
{t
} "xor"
2096 :|-@
{/
}^-
{t
}[dd
] *+=(
2,
0)+
[F
]{\mathstrut y_0
}
2097 "xor"
[u
] :`r "shift" "shift"|-@
{/
}_-
{t
}
2098 :|-@
{/
}_-
{\ell}[rrrrrrr
] *+
[o
][F
]{\shift{t
}} ="shift"
2099 [ll
] :|-@
{/
}^-
{\ell}[dd
] *+
[F
]{E
} ="e"
[ll
] {K
} :"e"
2100 :|-@
{/
}^-
{t
}[ddd
] *
{\xor} ="xor"
2101 [lll
] *+=(
2,
0)+
[F
]{\mathstrut x_1
} :|-@
{/
}_-
{t
} "xor"
2102 :|-@
{/
}^-
{t
}[dd
] *+=(
2,
0)+
[F
]{\mathstrut y_1
}
2103 "xor"
[u
] :`r "shift" "shift"|-@
{/
}_-
{t
}
2104 :@
{-->
}|-@
{/
}_-
{\ell}[rrrrrrr
] *+
[o
][F
]{\shift{t
}} ="shift"
2105 [ll
] :@
{-->
}|-@
{/
}^-
{\ell}[dd
] *+
[F
]{E
} ="e"
[ll
] {K
} :"e"
2106 :@
{-->
}|-@
{/
}^-
{t
}[ddd
] *
{\xor} ="xor"
2107 [lll
] *+=(
2,
0)+
[F--
]{\mathstrut x_i
} :@
{-->
}|-@
{/
}_-
{t
} "xor"
2108 :@
{-->
}|-@
{/
}^-
{t
}[dd
] *+=(
2,
0)+
[F--
]{\mathstrut y_i
}
2109 "xor"
[u
] :@
{-->
} `r "shift" "shift"|-@
{/
}_-
{t
}
2110 [rrrrrdd
] *+
[F
]{E
} ="e"
2111 "shift" :@
{-->
}`r "e" |-@
{/
}_-
{\ell} "e"
2113 :|-@
{/
}^-
{t
}[ddd
] *
{\xor} ="xor"
2114 [lll
] *+=(
2,
0)+
[F
]{\mathstrut x_
{n-
1}} :|-@
{/
}_-
{t
} "xor"
2115 :|-@
{/
}^-
{t
}[dd
] *+=(
2,
0)+
[F
]{\mathstrut y_
{n-
1}}
2118 \caption{Encryption using OFB mode
}
2122 \begin{definition
}[OFB algorithms
]
2123 For any function $F
\colon \Bin^
\ell \to \Bin^t$, any initialization vector
2124 $v
\in \Bin^
\ell$, any plaintext $x
\in \Bin^*$ and any ciphertext $y
\in
2125 \Bin^*$, we define PRF encryption mode $
\id{OFB
} = (
\id{ofb-encrypt
},
2126 \id{ofb-decrypt
})$ as follows:
2128 Algorithm $
\id{ofb-encrypt
}(F, v, x)$: \+ \\
2131 $x
\gets x
\cat 0^
{t
\lceil L/t
\rceil - L
}$; \\
2132 $y
\gets \emptystring$; \\
2133 \FOR $i =
0$
\TO $(|x| - t')/t$
\DO \\
\ind
2134 $x_i
\gets x
[ti
\bitsto t(i +
1)
]$; \\
2135 $z_i
\gets F(s)$; \\
2136 $y_i
\gets x_i
\xor z_i$; \\
2137 $s
\gets s
\shift{t
} z_i$; \\
2138 $y
\gets y
\cat y_i$; \- \\
2139 \RETURN $(s, y
[0 \bitsto L
])$;
2141 Algorithm $
\id{ofb-decrypt
}(F, v, y)$: \+ \\
2142 \RETURN $
\id{ofb-encrypt
}(F, v, y)$;
2144 We now define the schemes $
\Xid{\E}{OFB$\$$
}^F$, $
\Xid{\E}{OFBC
}^
{F, c
}$,
2145 $
\Xid{\E}{OFBE
}^
{F, c
}$, and $
\Xid{\E}{OFBL
}^
{F, V_0
}$ according to
2146 definition~
\ref{def:enc-scheme
}; and we define the hybrid scheme
2147 $
\Xid{\E}{OFBH
}^
{F, V_0, c
}_
{n_L, n_C, n_E
}$ according to
2148 definition~
\ref{def:enc-hybrid
}.
2151 \begin{remark
}[Similarity to CFB mode
]
2152 \label{rem:ofb-like-cfb
}
2153 OFB mode is strongly related to CFB mode: we can OFB encrypt a message $x$
2154 by
\emph{CFB-encrypting
} the all-zero string $
0^
{|x|
}$ with the same key
2155 and IV. That is, we could have written $
\id{ofb-encrypt
}$ and
2156 $
\id{ofb-decrypt
}$ like this:
2158 Algorithm $
\id{ofb-encrypt
}(F, v, x)$: \+ \\
2159 $(s, z)
\gets \id{cfb-encrypt
}(F, v,
0^
{|x|
})$; \\
2160 \RETURN $(s, x
\xor z)$;
2162 Algorithm $
\id{ofb-decrypt
}(F, v, y)$: \+ \\
2163 \RETURN $
\id{ofb-encrypt
}(F, v, y)$;
2165 We shall use this fact to prove the security of OFB mode in the next
2169 \subsection{Security of OFB mode
}
2171 \begin{theorem
}[Security of OFB mode
]
2173 Let $F$ be a pseudorandom function from $
\Bin^
\ell$ to $
\Bin^t$; let $V_0
2174 \in \Bin^
\ell$ be a non-$t$-sliding string; let $c$ be a generalized
2175 counter in $
\Bin^
\ell$; and let $n_L$, $n_C$, $n_E$ and $q_E$ be
2176 nonnegative integers; and furthermore suppose that
2178 \item $n_L + n_C + n_E
\le q_E$,
2179 \item $n_L =
0$, or $n_C = n_E =
0$, or $
\ell \le t$ and $V_0
\ne c(i)$
2180 for any $n_L
\le i < n_L + n_C + n_E$, and
2181 \item either $n_C =
0$ or $
\ell \le t$.
2183 Then, for any $t_E$ and $
\mu_E$, and whenever
2185 \
[ \InSec{lor-cpa
}(
\Xid{\E}{OFBH
}^
{F, V_0, c
}_
{n_L, n_C, n_E
};
2186 t_E, q_E,
\mu_E)
\le
2187 2 \cdot \InSec{prf
}(F; t_E + q t_F, q) +
\frac{q (q -
1)
}{2^
\ell}
2189 where $q =
\bigl\lfloor \bigl(
\mu_E + q_E (t -
1)
\bigr)/t
\bigr\rfloor +
2190 n_E$, and $t_F$ is some small constant.
2194 \
[ \InSec{rog-cpa-$W_\$$
}
2195 (
\Xid{\E}{OFBH
}^
{\Func{\ell}{t
}, V_0, c
}_
{n_L, n_C, n_E
};
2197 \frac{q (q -
1)
}{2^
{\ell+
1}}.
2199 This follows from lemma~
\ref{lem:cfb-rog
}, which makes the same statement
2200 about CFB mode, and the observation in remark~
\ref{rem:ofb-like-cfb
}.
2201 Suppose $A$ attempts to distinguish OFBH encryption from $W_\$$. We define
2202 the adversary $B$ which uses $A$ to attack CFBH encryption, as follows:
2204 Adversary $B^
{E(
\cdot)
}$: \+ \\
2205 \RETURN $A^
{\id{ofb
}(
\cdot)
}$; \-
2207 Function $
\id{ofb
}(x)$: \+ \\
2208 $(v, z)
\gets E(
0^
{|x|
})$; \\
2209 \RETURN $(v, x
\xor z)$;
2211 Now we apply proposition~
\ref{prop:rog-and-lor
}; the theorem follows.
2216 Let $F$, $c$ and $V_0$ be as in theorem~
\ref{thm:ofb
}. Then for any $t_E$,
2218 \begin{eqnarray*
}[rl
]
2219 \InSec{lor-cpa
}(
\Xid{\E}{OFB$\$$
}^F; t_E, q_E,
\mu_E)
2220 &
\le 2 \cdot \InSec{prf
}(F; t_E + q t_F, q) +
\frac{q (q -
1)
}{2^
\ell}
2222 \InSec{lor-cpa
}(
\Xid{\E}{OFBE
}^
{F, c
}; t_E, q_E,
\mu_E)
2223 &
\le 2 \cdot \InSec{prf
}(F; t_E + q' t_F, q') +
2224 \frac{q' (q' -
1)
}{2^
\ell}
2226 \InSec{lor-cpa
}(
\Xid{\E}{OFBL
}^
{F, V_0
}; t_E, q_E,
\mu_E)
2227 &
\le 2 \cdot \InSec{prf
}(F; t_E + q t_F, q) +
\frac{q (q -
1)
}{2^
\ell}
2229 \tabpause{and, if $
\ell \le t$,
}
2230 \InSec{lor-cpa
}(
\Xid{\E}{OFBC
}^
{F, c
}; t_E, q_E,
\mu_E)
2231 &
\le 2 \cdot \InSec{prf
}(F; t_E + q t_F, q) +
\frac{q (q -
1)
}{2^
\ell}
2233 where $q =
\bigl\lfloor \bigl(
\mu_E + q_E (t -
1)
\bigr)/t
\bigr\rfloor +
2234 n_E$, $q' = q + q_E$, and $t_F$ is some small constant.
2237 Follows from theorem~
\ref{thm:ofb
} and proposition~
\ref{prop:enc-hybrid
}.
2242 Let $P$ be a pseudorandom permutation on $
\Bin^
\ell$, and let $c$ and $V_0$
2243 be as in theorem~
\ref{thm:ofb
}. Then for any $t_E$, $q_E$ and $
\mu_E$,
2244 \begin{eqnarray*
}[rl
]
2245 \InSec{lor-cpa
}(
\Xid{\E}{OFB$\$$
}^P; t_E, q_E,
\mu_E)
2246 &
\le 2 \cdot \InSec{prp
}(P; t_E + q t_F, q) +
\frac{q (q -
1)
}{2^
\ell}
2248 \InSec{lor-cpa
}(
\Xid{\E}{OFBE
}^
{P, c
}; t_E, q_E,
\mu_E)
2249 &
\le 2 \cdot \InSec{prp
}(P; t_E + q' t_F, q') +
2250 \frac{q' (q' -
1)
}{2^
\ell}
2252 \InSec{lor-cpa
}(
\Xid{\E}{OFBL
}^
{P, V_0
}; t_E, q_E,
\mu_E)
2253 &
\le 2 \cdot \InSec{prp
}(P; t_E + q t_F, q) +
\frac{q (q -
1)
}{2^
\ell}
2255 \tabpause{and, if $
\ell \le t$,
}
2256 \InSec{lor-cpa
}(
\Xid{\E}{OFBC
}^
{P, c
}; t_E, q_E,
\mu_E)
2257 &
\le 2 \cdot \InSec{prp
}(P; t_E + q t_F, q) +
\frac{q (q -
1)
}{2^
\ell}
2259 where $q =
\bigl\lfloor \bigl(
\mu_E + q_E (t -
1)
\bigr)/t
\bigr\rfloor +
2260 n_E$, $q' = q + q_E$, and $t_F$ is some small constant.
2263 Follows from corollary~
\ref{cor:ofb-prf
} and
2264 proposition~
\ref{prop:prps-are-prfs
}.
2267 %%%--------------------------------------------------------------------------
2269 \section{CBCMAC mode message authentication
}
2275 \begin{cgraph
}{cbc-mac
}
2276 []!
{<
0.425cm,
0cm>: <
0cm,
0.75cm>::
}
2277 *+=(
2,
0)+
[F
]{\mathstrut x_0
}
2278 :`d
[dr
] [rrr
] *+
[F
]{E
} ="e"
[d
] {K
} :"e"
2279 :
[rrr
] *
{\xor} ="xor"
2280 [u
] *+=(
2,
0)+
[F
]{\mathstrut x_1
} :"xor"
2281 :
[rrr
] *+
[F
]{E
} ="e"
[d
] {K
} :"e"
2282 :@
{-->
}[rrr
] *
{\xor} ="xor"
2283 [u
] *+=(
2,
0)+
[F--
]{\mathstrut x_i
} :@
{-->
}"xor"
2284 :@
{-->
}[rrr
] *+
[F
]{E
} ="e"
[d
] {K
} :@
{-->
}"e"
2285 :@
{-->
}[rrr
] *
{\xor} ="xor"
2286 [u
] *+=(
2,
0)+
[F
]{\mathstrut x_
{n-
1}} :"xor"
2287 :
[rrr
] *+
[F
]{E
} ="e"
[d
] {K
} :"e"
2288 :
[rrr
] *+=(
2,
0)+
[F
]{\mathstrut \tau}
2291 \caption{Message authentication using CBCMAC mode
}
2296 Alas, it's been so long since I've picked this up that I've (a) forgotten how
2297 the proof for this mode went, and (b) lost my notes. You'll either have to
2298 wait, or I'll have to drop this bit.
2300 %%%--------------------------------------------------------------------------
2302 \section{Acknowledgements
}
2304 Thanks to Clive Jones for his suggestions on notation, and his help in
2305 structuring the proofs.
2307 %%%----- That's all, folks --------------------------------------------------
2309 \bibliography{mdw-crypto,cryptography2000,cryptography,rfc
}
2313 %%% Local Variables: