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
}}
85 \newslowboxenv{cgraph
}{\par$$
}{\begin{graph
}}{\end{graph
}}{$$
\par}
86 \newslowboxenv{vgraph
}
87 {\hfil$
\vcenter\bgroup\hbox\bgroup}
91 \newenvironment{vgraphs
}{\hbox to
\hsize\bgroup}{\hfil\egroup}
95 %%%--------------------------------------------------------------------------
100 We study the standard block cipher modes of operation: CBC, CFB, OFB, and
101 CBCMAC and analyse their security. We don't look at ECB other than briefly
102 to note its insecurity, and we have no new results on counter mode. Our
103 results improve over those previously published in that (a) our bounds are
104 better, (b) our proofs are shorter and easier, (c) the proofs correct
105 errors we discovered in previous work, or some combination of these. We
106 provide a new security notion for symmetric encryption which turns out to
107 be rather useful when analysing block cipher modes. Finally, we define a
108 new, condition for initialization vectors, introducing the concept of a
109 `generalized counter', and proving that generalized suffice for security in
110 (full-width) CFB and OFB modes and that generalized counters encrypted
111 using the block cipher (with the same key) suffice for all the encryption
117 \columnsep=
2em
\columnseprule=
0pt
118 \tableofcontents[\begin{multicols
}{2}\raggedright][\end{multicols
}]
119 \listoffigures[\begin{multicols
}{2}\raggedright][\end{multicols
}]
120 \listoftables[\begin{multicols
}{2}\raggedright][\end{multicols
}]
124 %%%--------------------------------------------------------------------------
126 \section{Introduction
}
129 \subsection{Block cipher modes
}
131 Block ciphers -- keyed pseudorandom permutations -- are essential
132 cryptographic tools, widely used for bulk data encryption and to an
133 increasing extent for message authentication. Because the efficient block
134 ciphers we have operate on fixed and relatively small strings of bits --
64
135 or
128 bits at a time, one needs a `mode of operation' to explain how to
136 process longer messages.
138 A collection of encryption modes, named ECB, CBC, CFB and OFB, were defined
139 in
\cite{FIPS81
}. Of these, ECB -- simply divide the message into blocks and
140 process them independently with the block cipher -- is just insecure and not
141 to be recommended for anything much. We describe the other three, and
142 analyse their security using the standard quantitative provable-security
143 approach. All three require an `initialization vector' or `IV' which
144 diversifies the output making it hard to correlate ciphertexts with
145 plaintexts. We investigate which conditions on these IVs suffice for secure
148 We also examine the CBC-MAC message-authentication scheme, because it's
149 intimately related to the CBC encryption scheme and the same techniques we
150 used in the analysis of the latter apply to the former.
152 \subsection{Previous work
}
154 The first quantitative security proof for a block cipher mode is the analysis
155 of CBCMAC of
\cite{Bellare:
1994:SCB
}. Security proofs for the encryption
156 modes CBC and CTR appeared in
\cite{Bellare:
2000:CST
}, which also defines and
157 relates the standard security notions of symmetric encryption. The authors
158 of
\cite{Alkassar:
2001:OSS
} offer a proof of CFB mode, though we believe it
159 to be flawed in a number of respects.
161 \subsection{Our contribution
}
163 We introduce a new security notion for symmetric encryption, named
164 `result-or-garbage', or `ROG-CPA', which generalizes the `real-or-random'
165 notion of
\cite{Bellare:
2000:CST
} and the `random-string' notion of
166 \cite{Rogaway:
2001:OCB
}. Put simply, it states that an encryption scheme is
167 secure if an adversary has difficulty distinguishing true ciphertexts from
168 strings chosen by an algorithm which is given only the
\emph{length
} of the
169 adversary's plaintext. This turns out to be just the right tool for
170 analysing our encryption modes. We relate this notion to the standard
171 `left-or-right' notion and, thereby, all the others.
173 Our bound for CBC mode improves over the `tight' bound proven in
174 \cite{Bellare:
2000:CST
} by almost a factor of two. The difference comes
175 because they analyse the construction as if it were built from a PRF and add
176 in a `PRP-used-as-a-PRF' correction term: our analysis considers the effect
177 of a permutation directly. We prove that CBC mode is still secure if an
178 encrypted counter is used in place of a random string as the IV for each
179 message. Finally, we show that the `ciphertext stealing' technique is
182 For CFB, we first discuss the work of
\cite{Alkassar:
2001:OSS
}, who offer a
183 proof for both CFB mode and an optimized variant which enhances the
184 error-recovery properties of standard CFB. We believe that their proof is
185 defective in a number of ways. We then offer our own proof. Our bound is a
186 factor of two worse than theirs; however, we believe that fixing their proof
187 introduces this missing factor of two: that is, that our `poorer' bound
188 reflects the true security of CFB mode more accurately. We show that
189 full-width CFB is secure if the IV is any `generalized counter', and that
190 both full-width and truncated $t$-bit CFB are secure if the IV is an
191 encrypted counter. We also show that, unlike CBC mode, it is safe to `carry
192 over' the final shift-register value from the previous message as the IV for
195 OFB mode is in fact a simple modification to CFB mode, and we prove the
196 security of OFB by relating it to CFB.
198 Finally, for CBCMAC, we analyse it using
\emph{both
} pseudorandom functions
199 \emph{and
} pseudorandom permutations, showing that, in fact, using a block
200 cipher rather than a PRF reduces the security hardly at all. Also, we
201 improve on the (groundbreaking) work of
\cite{Bellare:
1994:SCB
} firstly by
202 improving the security bound by a factor of almost four, and secondly by
203 extending the message space from a space of fixed-length messages to
204 \emph{any
} prefix-free set of strings.
206 As a convenient guide, our security bounds are summarized in
207 table~
\ref{tab:summary
}.
211 \vbox to
\baselineskip{\vskip\baselineskip\vskip2pt\hbox{#1}\vss}}
212 \def\none{\multicolumn{1}{c|
}{---
}}
215 {| c | ?>
{\hack}c | c | >
{\displaystyle} Mc | >
{\displaystyle} Mc |
}
217 \multicolumn{1}{|c|
}{\lower{\bfseries Mode
}} &
218 \multicolumn{1}{c|
}{\lower{\bfseries Section
}} &
219 \multicolumn{1}{c|
}{\lower{\bfseries Notion
}} &
220 \multicolumn{2}{c|
}{\bfseries Security with
} \\
\hlx{v
[4]zc
{4-
5}v
}
222 \multicolumn{1}{c|
}{\bfseries $(t, q,
\epsilon)$-PRF
} &
223 \multicolumn{1}{c|
}{\bfseries $(t, q,
\epsilon)$-PRP
}
225 CBC &
\ref{sec:cbc
} & LOR-CPA &
227 2\epsilon +
\frac{q (q -
1)
}{2^
\ell - q
} \\
\hlx{vvhvv
}
228 CFB &
\ref{sec:cfb
} & LOR-CPA &
229 2 \epsilon +
\frac{q (q -
1)
}{2^
\ell} &
230 2 \epsilon +
\frac{q (q -
1)
}{2^
{\ell-
1}} \\
\hlx{vvhvv
}
231 OFB &
\ref{sec:ofb
} & LOR-CPA &
232 2 \epsilon +
\frac{q (q -
1)
}{2^
\ell} &
233 2 \epsilon +
\frac{q (q -
1)
}{2^
{\ell-
1}} \\
\hlx{vvhvv
}
234 CBCMAC &
\ref{sec:cbcmac
} & SUF-CMA &
235 \epsilon +
\frac{q (q -
1) +
2 q_V
}{2^
{\ell+
1}} &
237 \frac{q (q -
1)
}{2 \cdot (
2^
\ell - q)
} +
238 \frac{q_V
}{2^
\ell - q_T
} \\
\hlx{vvh
}
241 \caption[Summary of our results
]
242 {Summary of our results. In all cases, $q$ is the number of block
243 cipher applications used in the game.
}
247 \subsection{The rest of the paper
}
249 In section~
\ref{sec:prelim
} we define the various bits of notation and
250 terminology we'll need in the rest of the paper. The formal definitions are
251 given for our new `result-or-garbage' security notion, and for our
252 generalized counters. In section~
\ref{sec:cbc
} we study CBC mode, and
253 ciphertext stealing. In section~
\ref{sec:cfb
} we study CFB mode. In
254 section~
\ref{sec:ofb
} we study OFB mode. In section~
\ref{sec:cbcmac
} we
255 study the CBCMAC message authentication scheme.
257 %%%--------------------------------------------------------------------------
259 \section{Notation and definitions
}
262 \subsection{Bit strings
}
263 \label{sec:bitstrings
}
265 Most of our notation for bit strings is standard. The main thing to note is
266 that everything is zero-indexed.
269 \item We write $
\Bin = \
{0,
1\
}$ for the set of binary digits. Then $
\Bin^n$
270 is the set of $n$-bit strings, and $
\Bin^*$ is the set of all (finite) bit
272 \item If $x$ is a bit string then $|x|$ is the length of $x$. If $x
\in
273 \Bin^n$ then $|x| = n$.
274 \item If $x, y
\in \Bin^n$ are strings of bits of the same length then $x
275 \xor y
\in \Bin^n$ is their bitwise XOR.
276 \item If $x$ is a bit string and $i$ is an integer satisfying $
0 \le i < |x|$
277 then $x
[i
]$ is the $i$th bit of $x$. If $a$ and $b$ are integers
278 satisfying $
0 \le a
\le b
\le |x|$ then $x
[a
\bitsto b
]$ is the substring
279 of $x$ beginning with bit $a$ and ending just
\emph{before
} bit $b$. We
280 have $|x
[i
]| =
1$ and $|x
[a
\bitsto b
]| = b - a$; if $y = x
[a
\bitsto b
]$
281 then $y
[i
] = x
[a + i
]$.
282 \item If $x$ and $y$ are bit strings then $x y$ is the result of
283 concatenating $y$ to $x$. If $z = x y$ then $|z| = |x| + |y|$; $z
[i
] =
284 x
[i
]$ if $
0 \le i < |x|$ and $z
[i
] = y
[i - |x|
]$ if $|x|
\le i < |x| +
285 |y|$. Sometimes, for clarity (e.g., to distinguish from integer
286 multiplication) we write $x
\cat y$ instead of $x y$.
287 \item The empty string is denoted $
\emptystring$. We have $|
\emptystring| =
288 0$, and $x = x
\emptystring =
\emptystring x$ for all strings $x
290 \item If $x$ is a bit string and $n$ is a natural number then $x^n$ is the
291 result of concatenating $x$ to itself $n$ times. We have $x^
0 =
292 \emptystring$ and if $n >
0$ then $x^n = x^
{n-
1} \cat x = x
\cat x^
{n-
1}$.
293 \item If $x$ and $y$ are bit strings, $|x| =
\ell$, and $|y| = t$, then we
294 define $x
\shift{t
} y$ as:
295 \
[ x
\shift{t
} y = (x y)
[t
\bitsto t +
\ell] =
\begin{cases
}
296 x
[t
\bitsto \ell] \cat y & if $t <
\ell$, or \\
297 y
[t -
\ell \bitsto t
] & if $t
\ge \ell$.
299 Observe that, if $z = x
\shift{t
} y$ then $|z| = |x| =
\ell$ and
300 \
[ z
[i
] = (x y)
[i + t
] =
\begin{cases
}
301 x
[i + t
] & if $
0 \le i <
\ell - t$, or \\
302 y
[i + t -
\ell] & if $
\min(
0,
\ell - t)
\le i <
\ell$.
304 Obviously $x
\shift{0} \emptystring = x$, and if $|x| = |y| = t$ then $x
305 \shift{t
} y = y$. Finally, if $|y| = t$ and $|z| = t'$ then $(x
\shift{t
}
306 y)
\shift{t'
} z = x
\shift{t + t'
} (y z)$.
309 \subsection{Other notation
}
310 \label{sec:miscnotation
}
314 \item If $n$ is any natural number, then $
\Nupto{n
}$ is the set $\
{\, i
\in
315 \Z \mid 0 \le i < n \,\
} = \
{ 0,
1,
\ldots, n \
}$.
317 \item The symbol $
\bot$ (`bottom') is a value different from every bit
319 \item We write $
\Func{l
}{L
}$ as the set of all functions from $
\Bin^l$ to
320 $
\Bin^L$, and $
\Perm{l
}$ as the set of all permutations on $
\Bin^l$.
323 \subsection{Algorithm descriptions
}
324 \label{sec:algorithms
}
326 An
\emph{adversary
} is a probabilistic algorithm which attempts (possibly) to
327 `break' a cryptographic scheme. We will often provide adversaries with
328 oracles which compute values with secret data. The
\emph{running time
} of an
329 adversary conventionally includes the size of the adversary's description:
330 this is an attempt to `charge' the adversary for having large precomputed
333 Most of the notation used in the algorithm descriptions should be obvious.
334 We briefly note a few features which may be unfamiliar.
336 \item The notation $a
\gets x$ denotes the action of assigning the value $x$
338 \item We write oracles as superscripts, with dots marking where inputs to
339 the oracle go, e.g., $A^
{O(
\cdot)
}$.
340 \item The notation $a
\getsr X$, where $X$ is a finite set, denotes the
341 action of assigning to $a$ a random value $x
\in X$ according to the
342 uniform probability distribution on $X$; i.e., following $a
\getsr X$, we
343 have $
\Pr[a = x
] =
1/|X|$ for any $x
\in X$.
345 The notation is generally quite sloppy about types and scopes. We don't
346 think these informalities cause much confusion, and they greatly simplify the
347 presentation of the algorithms.
349 \subsection{Pseudorandom functions and permutations
}
350 \label{sec:prfs-and-prps
}
352 Our definitions of pseudorandom functions and permutations are standard. We
353 provide them for the sake of completeness.
355 \begin{definition
}[Pseudorandom function family
]
357 A
\emph{pseudorandom function family (PRF)
} $F = \
{F_K\
}_K$ is a collection
358 of functions $F_K
\colon \Bin^
\ell \to \Bin^L$ indexed by a
\emph{key
} $K
359 \in \keys F$. If $A$ is any adversary, we define $A$'s
\emph{advantage in
360 distinguishing $F$ from a random function
} to be
362 \Pr[K
\getsr \keys F: A^
{F_K(
\cdot)
} =
1] -
363 \Pr[R
\getsr \Func{\ell}{L
}: A^
{R(
\cdot)
} =
1]
365 where the probability is taken over all choices of keys, random functions,
366 and the internal coin-tosses of $A$. The
\emph{insecurity of $F$
} is given
368 \
[ \InSec{prf
}(F; t, q) =
\max_A \Adv{prf
}{F
}(A) \
]
369 where the maximum is taken over all adversaries which run in time~$t$ and
370 issue at most $q$ oracle queries. If $
\InSec{prf
}(F; t, q)
\le \epsilon$
371 then we say that $F$ is a $(t, q,
\epsilon)$-PRF.
374 \begin{definition
}[Pseudorandom permutation family
]
376 A
\emph{pseudorandom permutation family (PRP)
} $E = \
{E_K\
}_K$ is a
377 collection of permutations $E_K
\colon \Bin^
\ell \to \Bin^
\ell$ indexed by a
378 \emph{key
} $K
\in \keys E$. If $A$ is any adversary, we define $A$'s
379 \emph{advantage in distinguishing $E$ from a random permutation
} to be
381 \Pr[K
\getsr \keys E: A^
{E_K(
\cdot)
} =
1] -
382 \Pr[P
\getsr \Perm{\ell}: A^
{P(
\cdot)
} =
1]
384 where the probability is taken over all choices of keys, random
385 permutations, and the internal coin-tosses of $A$. Note that the adversary
386 is not allowed to query the inverse permutation $E^
{-
1}_K(
\cdot)$ or
387 $P^
{-
1}(
\cdot)$. The
\emph{insecurity of $E$
} is given by
388 \
[ \InSec{prp
}(E; t, q) =
\max_A \Adv{prf
}{E
}(A) \
]
389 where the maximum is taken over all adversaries which run in time~$t$ and
390 issue at most $q$ oracle queries. If $
\InSec{prp
}(E; t, q)
\le \epsilon$
391 then we say that $E$ is a $(t, q,
\epsilon)$-PRP.
394 The following result is standard; we shall require it for the security proofs
395 of CFB and OFB modes. The proof is given as an introduction to our general
399 \label{prop:prps-are-prfs
}
400 Suppose $E$ is a PRP over $
\Bin^
\ell$. Then
401 \
[ \InSec{prf
}(E; t, q)
402 \le \InSec{prp
}(E; t, q) +
\frac{q (q -
1)
}{2^
{\ell+
1}}.
407 \
[ \InSec{prf
}(
\Perm{\ell}; t, q)
\le \frac{q (q -
1)
}{2^
{\ell+
1}}, \
]
408 i.e., that a
\emph{perfect
} $
\ell$-bit random permutation is a PRF with the
409 stated bounds. The proposition follows immediately from this claim and the
412 We now prove the claim. Consider any adversary~$A$. Let $x_i$ be $A$'s
413 queries, and let $y_i$ be the responses, for $
0 \le i < q$. Assume,
414 without loss of generality, that the $x_i$ are distinct. Let $C_n$ be the
415 event in the random-function game $
\Expt{prf-$
0$
}{\Perm{\ell}}(A)$ that
416 $y_i = y_j$ for some $i$ and $j$ where $
0 \le i < j < n$. Then
418 \Pr[C_n
] \le \sum_{0\le i<n
} \frac{i
}{2^
\ell}
419 =
\frac{n (n -
1)
}{2^
{\ell+
1}}.
421 It's clear that the two games proceed identically if $C_q$ doesn't occur in
422 the random-function game. The claim follows.
425 \subsection{Symmetric encryption
}
428 We begin with a purely syntactic description of a symmetric encryption
429 scheme, and then define our two notions of security.
431 \begin{definition
}[Symmetric encryption
]
433 A
\emph{symmetric encryption scheme
} is a triple of algorithms $
\E = (G, E,
434 D)$, with three (implicitly) associated sets: a keyspace, a plaintext
435 space, and a ciphertext space.
437 \item $G$ is a probabilistic
\emph{key-generation algorithm
}. It is
438 invoked with no arguments, and returns a key $K$ which can be used with
439 the other two algorithms. We write $K
\gets G()$.
440 \item $E$ is a probabilistic
\emph{encryption algorithm
}. It is invoked
441 with a key $K$ and a
\emph{plaintext
} $x$ in the plaintext space, and it
442 returns a
\emph{ciphertext
} $y$ in the ciphertext space. We write $y
444 \item $D$ is a deterministic
\emph{decryption algorithm
}. It is invoked
445 with a key $K$ and a ciphertext $y$, and it returns either a plaintext
446 $x$ or the distinguished symbol $
\bot$. We write $x
\gets D_K(y)$.
448 For correctness, we require that whenever $y$ is a possible result of
449 computing $E_K(x)$, then $x = D_K(y)$.
452 Our primary notion of security is
\emph{left-or-right indistinguishability
453 under chosen-plaintext attack
} (LOR-CPA), since it offers the best reductions
454 to the other common notions. (We can't acheive security against chosen
455 ciphertext attack using any of our modes, so we don't even try.) See
456 \cite{Bellare:
2000:CST
} for a complete discussion of LOR-CPA, and how it
457 relates to other security notions for symmetric encryption.
459 \begin{definition
}[Left-or-right indistinguishability
]
461 Let $
\E = (G, E, D)$ be a symmetric encryption scheme. Define the function
462 $
\id{lr
}(b, x_0, x_1) = x_b$. Then for any adversary $A$, we define $A$'s
463 \emph{advantage against the LOR-CPA security of $
\E$
} as
464 \
[ \Adv{lor-cpa
}{\E}(A) =
465 \Pr[K
\gets G(): A^
{E_K(
\id{lr
}(
1,
\cdot,
\cdot))
} =
1] -
466 \Pr[K
\gets G(): A^
{E_K(
\id{lr
}(
0,
\cdot,
\cdot))
} =
1].
468 We define the
\emph{LOR-CPA insecurity of $
\E$
} to be
469 \
[ \InSec{lor-cpa
}(
\E; t, q_E,
\mu_E) =
470 \max_A \Adv{lor-cpa
}{\E}(A)
472 where the maximum is taken over all adversaries which run in time~$t$ and
473 issue at most $q_E$ encryption queries totalling at most $
\mu_E$ bits. If
474 $
\InSec{lor-cpa
}(
\E; t, q_E,
\mu_E)
\le \epsilon$ then we say that $
\E$ is
475 $(t, q_E,
\mu_E,
\epsilon)$-LOR-CPA.
478 Our second notion is named
\emph{result-or-garbage
} and abbreviated ROG-CPA.
479 It is related to the notion used by
\cite{Rogaway:
2001:OCB
}, though different
480 in important ways: for example, there are reductions both ways between
481 ROG-CPA and LOR-CPA (and hence the other standard notions of security for
482 symmetric encryption), whereas the notion of
\cite{Rogaway:
2001:OCB
} is
483 strictly stronger than LOR-CPA. Our idea is that an encryption scheme is
484 secure if ciphertexts of given plaintexts --
\emph{results
} -- hard to
485 distinguish from strings constructed independently of any plaintexts --
486 \emph{garbage
}. We formalize this notion in terms of a
487 \emph{garbage-emission algorithm
} $W$ which is given only the length of the
488 plaintext. The algorithm $W$ will usually be probabilistic, and may maintain
489 state. Unlike
\cite{Rogaway:
2001:OCB
}, we don't require that $W$'s output
490 `look random' in any way, just that it be chosen independently of the
491 adversary's plaintext selection.
493 \begin{definition
}[Result-or-garbage indistinguishability
]
495 Let $
\E = (G, E, D)$ be a symmetric encryption scheme, and let $W$ be a
496 possibly-stateful, possibly-probabilistic
\emph{garbage-emission
}
497 algorithm. Then for any adversary $A$, we define $A$'s
\emph{advantage
498 against the ROG-CPA-$W$ security of $
\E$
} as
499 \
[ \Adv{rog-cpa-$W$
}{\E}(A) =
500 \Pr[K
\gets G(): A^
{E_K(
\cdot)
} =
1] -
\Pr[A^
{W(|
\cdot|)
} =
1]. \
]
501 We define the
\emph{ROG-CPA insecurity of $
\E$
} to be
502 \
[ \InSec{lor-cpa
}(
\E; t, q_E,
\mu_E) =
503 \max_A \Adv{lor-cpa
}{\E}(A) \
]
504 where the maximum is taken over all adversaries which run in time~$t$ and
505 issue at most $q_E$ encryption queries totalling at most $
\mu_E$ bits. If
506 $
\InSec{rog-cpa-$W$
}(
\E; t, q_E,
\mu_E)
\le \epsilon$ for some $W$ then we
507 say that $
\E$ is $(t, q_E,
\mu_E,
\epsilon)$-ROG-CPA.
510 The following proposition relates our new notion to the existing known
513 \begin{proposition
}[ROG $
\Leftrightarrow$ LOR
]
514 \label{prop:rog-and-lor
}
515 Let $
\E$ be a symmetric encryption scheme. Then,
517 \item for all garbage-emission algorithms $W$,
518 \
[ \InSec{lor-cpa
}(
\E; t, q_E,
\mu_E)
520 \InSec{rog-cpa-$W$
}(
\E; t + t_E
\mu_E, q_E,
\mu_E)
523 \item there exists a garbage-emission algorithm $W$ for which
524 \
[ \InSec{rog-cpa-$W$
}(
\E; t, q_E,
\mu_E)
525 \le \InSec{lor-cpa
}(
\E; t + t_E
\mu_E, q_E,
\mu_E)
528 for some fairly small constant $t_E$.
532 \item Let $W$ and $
\E$ be given, and let $A$ be an adversary attacking the
533 LOR-CPA security of $
\E$. Consider adversary $B$ attacking $
\E$'s
534 ROG-CPA-$W$ security.
536 Adversary $B^E(
\cdot)$: \+ \\
537 $b^*
\getsr \Bin$; \\
538 $b
\gets A^
{E(
\id{lr
}(b^*,
\cdot,
\cdot))
}$; \\
539 \IF $b = b^*$
\THEN \RETURN $
1$
\ELSE \RETURN $
0$;
541 Function $
\id{lr
}(b, x_0, x_1)$: \+ \\
542 \IF $b =
0$
\THEN \RETURN $x_0$
\ELSE \RETURN $x_1$;
544 If $E(
\cdot)$ is the `result' encryption oracle, then $B$ simulates the
545 left-or-right game for the benefit of $A$, and therefore returns $
1$ with
546 probability $(
\Adv{lor-cpa
}{\E}(A) +
1)/
2$. On the other hand, if
547 $E(
\cdot)$ returns `garbage' then the oracle responses are entirely
548 independent of $b^*$. This follows because $A$ is constrained to query
549 only on pairs of plaintexts with equal lengths, and the responses are
550 dependent only on these (common) lengths and any internal state and coin
551 tosses of $W$. So $b$ is independent of $b^*$ and $
\Pr[b = b^*
] =
552 \frac{1}{2}$. The result follows.
553 \item Let $
\E = (G, E, D)$ be given. Our garbage emitter simulates the
554 real-or-random game of
\cite{Bellare:
2000:CST
}. Let $K_W =
\bot$
555 initially: we define our emitter $W$ thus:
557 Garbage emitter $W(n)$: \+ \\
558 \IF $K_W =
\bot$
\THEN $K_W
\gets G()$; \\
559 $x
\getsr \Bin^n$; \\
562 We now show that $
\InSec{rog-cpa-$W$
}(
\E; t, q_E,
\mu_E)
\le
563 \InSec{lor-cpa
}(
\E; t + t_E
\mu_E, q_E,
\mu_E)$ for our $W$. Let $A$ be
564 an adversary attacking the ROG-CPA-$W$ security of $
\E$. Consider
565 adversary $B$ attacking $
\E$'s LOR-CPA security:
567 Adversary $B^
{E(
\cdot,
\cdot)
}$: \+ \\
568 $b
\gets A^
{\id{lorify
}(
\cdot)
}$; \\
571 Function $
\id{lorify
}(x)$: \+ \\
572 $x'
\getsr \Bin^
{|x|
}$; \\
575 The adversary simulates the ROG-CPA-$W$ games perfectly for our chosen
576 $W$, since the game has chosen the random $K_W$ for us already: the
577 `left' game returns only the results of encrypting random `garbage'
578 plaintexts $x'$, while the right game returns correct results of
579 encrypting the given plaintexts $x$. The result follows.
586 \subsection{Message authentication
}
589 Our definitions for message authentication are standard; little needs to be
590 said of them. As with symmetric encryption, we begin with a syntactic
591 definition, and then describe our notion of security.
593 \begin{definition
}[Message authentication code
]
595 A
\emph{message authentication code (MAC)
} is a triple of algorithms $
\M =
596 (G, T, V)$ with three (implicitly) associated sets: a keyspace, a message
597 space, and a tag space.
599 \item $G$ is a probabilistic
\emph{key-generation algorithm
}. It is
600 invoked with no arguments, and returns a key $K$ which can be used with
601 the other two algorithms. We write $K
\gets G()$.
602 \item $T$ is a probabilistic
\emph{tagging algorithm
}. It is invoked with
603 a key $K$ and a
\emph{message
} $x$ in the message space, and it returns a
604 \emph{tag
} $
\tau$ in the tag space. We write $
\tau \gets T_K(x)$.
605 \item $V$ is a deterministic
\emph{verification algorithm
}. It is invoked
606 with a key $K$, a message $x$ and a tag $
\tau$, and returns a bit $b
\in
607 \Bin$. We write $b
\gets V_K(x,
\tau)$.
609 For correctness, we require that whenever $
\tau$ is a possible result of
610 computing $T_K(x)$, then $V_K(x,
\tau) =
1$.
613 Our notion of security is the strong unforgeability of
614 \cite{Abdalla:
2001:DHIES,Bellare:
2000:AER
}.
616 \begin{definition
}[Strong unforgeability
]
617 Let $
\M = (G, T, V)$ be a message authentication code, and let $A$
618 be an adversary. We perform the following experiment.
620 Experiment $
\Expt{suf-cma
}{\M}(A)$: \+ \\
622 $
\Xid{T
}{list
} \gets \emptyset$; \\
623 $
\id{good
} \gets 0$; \\
624 $A^
{\id{tag
}(
\cdot),
\id{verify
}(
\cdot,
\cdot)
}$; \\
627 Oracle $
\id{tag
}(x)$: \+ \\
628 $
\tau \gets T_K(x)$; \\
629 $
\Xid{T
}{list
} \gets \Xid{T
}{list
} \cup \
{(x,
\tau)\
}$; \\
632 Oracle $
\id{verify
}(x,
\tau)$: \+ \\
633 $b
\gets V_K(x,
\tau)$; \\
634 \IF $b =
1 \land (x,
\tau)
\notin \Xid{T
}{list
}$
\THEN
635 $
\id{good
} \gets 1$; \\
638 That is, the adversary `wins' if it submits a query to its verification
639 oracle which is
\emph{new
} -- doesn't match any message/tag pair from the
640 tagging oracle -- and
\emph{valid
} -- the verification oracle returned
641 success. We define the adversary's
\emph{success probability
} as
642 \
[ \Succ{suf-cma
}{\M}(A) =
643 \Pr[\Expt{suf-cma
}{\M}(A) =
1]. \
]
644 We define the
\emph{SUF-CMA insecurity of $
\M$
} to be
645 \
[ \InSec{suf-cma
}(
\M; t, q_T,
\mu_T, q_V,
\mu_V) =
646 \max_A \Adv{suf-cma
}{\M}(A) \
]
647 where the maximum is taken over all adversaries which run in time~$t$,
648 issue at most $q_T$ tagging queries totalling at most $
\mu_T$ bits, and
649 issue at most $q_V$ verification queries totalling at most $
\mu_V$ bits.
650 If $
\InSec{suf-cma
}(
\M; t, q_T,
\mu_T, q_V,
\mu_V)
\le \epsilon$
651 then we say that $
\E$ is $(t, q_T,
\mu_T, q_V,
\mu_V)$-SUF-CMA.
654 \subsection{Initialization vectors and encryption modes
}
657 In order to reduce the number of definitions in this paper to a tractable
658 level, we will describe the basic modes independently of how initialization
659 vectors (IVs) are chosen, and then construct the actual encryption schemes by
660 applying various IV selection methods from the modes.
662 We consider the following IV selection methods.
664 \item[Random selection
] An IV is chosen uniformly at random just before
665 encrypting each message.
666 \item[Counter
] The IV for each message is a
\emph{generalized counter
} (see
667 discussion below, and definition~
\ref{def:genctr
}).
668 \item[Encrypted counter
] The IV for a message is the result of applying the
669 block cipher to a generalized counter, using the same key as for message
671 \item[Carry-over
] The IV for the first message is fixed; the IV for
672 subsequent messages is some function of the previous plaintexts or
673 ciphertexts (e.g., the last ciphertext block of the previous message).
675 Not all of these methods are secure for all of the modes we consider.
677 \begin{definition
}[Generalized counters
]
679 If $S$ is a finite set, then a
\emph{generalized counter in $S$
} is an
680 bijection $c
\colon \Nupto{|S|
} \leftrightarrow S$. For brevity, we shall
681 refer simply to `counters', leaving implicit the generalization.
684 \begin{remark
}[Examples of generalized counters
] \leavevmode
686 \item There is a `natural' binary representation of the natural numbers
687 $
\Nupto{2^
\ell}$ as $
\ell$-bit strings: for any $n
\in \Nupto{2^
\ell}$,
688 let $R(n)$ be the unique $r
\in \Bin^
\ell$ such that $
\smash{n =
689 \sum_{0\le i<
\ell} 2^i r
[i
]}$. Then $R(
\cdot)$ is a generalized counter
691 \item We can represent elements of the finite field $
\gf{2^
\ell}$ as
692 $
\ell$-bit strings. Let $p(x)
\in \gf{2}[x
]$ be a primitive polynomial
693 of degree $
\ell$; then represent $
\gf{2^
\ell}$ by $
\gf{2}[x
]/(p(x))$.
694 Now for any $a
\in \gf{2^
\ell}$, let $R(a)$ be the unique $r
\in
695 \Bin^
\ell$ such that $
\smash{a =
\sum_{0\le i<
\ell} x^i r
[i
]}$. Because
696 $p(x)$ is primitive, $x$ generates the multiplicative group
697 $
\gf{2^
\ell}^
{\,*
}$, so define $c(n) = R(x^n)$ for $
0 \le n <
2^
\ell -
1$
698 and $c(
2^
{\ell -
1}) =
0^
\ell$; then $c(
\cdot)$ is a generalized counter
699 in $
\Bin^
\ell$. This counter can be implemented efficiently in hardware
700 using a linear feedback shift register.
704 \begin{definition
}[Encryption modes
]
705 \label{def:enc-modes
}
707 A
\emph{block cipher encryption mode
} $m_P = (
\id{encrypt
},
\id{decrypt
})$
708 is a pair of deterministic oracle algorithms (and implicitly-defined
709 plaintext and ciphertext spaces) which satisfy the following conditions:
711 \item The algorithm $
\id{encrypt
}$ runs with oracle access to a permutation
712 $P
\colon \Bin^
\ell \leftrightarrow \Bin^
\ell$; on input a plaintext $x$
713 and an initialization vector $v
\in \Bin^
\ell$, it returns a ciphertext
714 $y$ and a
\emph{chaining value
} $v'
\in \Bin^
\ell$. We write $(v', y) =
715 \id{encrypt
}^
{P(
\cdot)
}(v, x)$.
716 \item The algorithm $
\id{decrypt
}$ runs with oracle access to a permutation
717 $P
\colon \Bin^
\ell \leftrightarrow \Bin^
\ell$ and its inverse
718 $P^
{-
1}(
\cdot)$; on input a ciphertext $y$ and an initialization vector
719 $v
\in \Bin^
\ell$, it returns a plaintext $x$. We write that $x =
720 \id{decrypt
}^
{P(
\cdot), P^
{-
1}(
\cdot)
}(v, y)$.
721 \item For all permutations $P
\colon \Bin^
\ell \leftrightarrow \Bin^
\ell$,
722 all plaintexts $x$ and all initialization vectors $v$, if $(v', y) =
723 \id{encrypt
}^
{P(
\cdot)
}(v, x)$ then $x =
\id{decrypt
}^
{P(
\cdot),
724 P^
{-
1}(
\cdot)
}(v, y)$.
725 \item There exists an efficient algorithm which, given a ciphertext $y$ and
726 the initialization vector but
\emph{not
} access to $P$, computes the
727 chaining value $v'$ such that $(v', y) =
\id{encrypt
}^P(v, x)$.
729 Similarly, a
\emph{PRF encryption mode
} $m_F = (
\id{encrypt
},
730 \id{decrypt
})$ is a pair of deterministic oracle algorithms (and
731 implicitly-defined plaintext and ciphertext spaces) which satisfy the
732 following conditions:
734 \item The algorithm $
\id{encrypt
}$ runs with oracle access to a function
735 $F
\colon \Bin^
\ell \to \Bin^L$; on input a plaintext $x$ and an
736 initialization vector $v
\in \Bin^
\ell$, it returns a ciphertext $y$ and
737 a
\emph{chaining value
} $v'
\in \Bin^
\ell$. We write $(v', y) =
738 \id{encrypt
}^
{F(
\cdot)
}(v, x)$.
739 \item The algorithm $
\id{decrypt
}$ runs with oracle access to a function
740 $F
\colon \Bin^
\ell \to \Bin^L$; on input a ciphertext $y$ and an
741 initialization vector $v
\in \Bin^
\ell$, it returns a plaintext $x$. We
742 write that $(v', x) =
\id{decrypt
}^
{F(
\cdot)
}(v, y)$.
743 \item For all functions $F
\colon \Bin^
\ell \to \Bin^L$, all plaintexts $x$
744 and all initialization vectors $v$, if $(v', y) =
745 \id{encrypt
}^
{F(
\cdot)
}(v, x)$ then $x =
\id{decrypt
}^
{F(
\cdot)
}(v, y)$.
746 \item There exists an efficient algorithm which, given a ciphertext $y$ and
747 the initialization vector but
\emph{not
} access to $F$, computes the
748 chaining value $v'$ such that $(v', y) =
\id{encrypt
}^F(v, x)$.
753 \begin{definition
}[Symmetric encryption schemes from modes
]
754 \label{def:enc-scheme
}
755 Let $F$ be a pseudorandom permutation on $
\Bin^
\ell$ (resp.\ a
756 pseudorandom function from $
\Bin^
\ell$ to $
\Bin^L$); let $m =
757 (
\id{encrypt
},
\id{decrypt
})$ be a block cipher (resp.\ PRF) encryption
758 mode. (To save on repetition, if $F$ is a PRF then define $F_K^
{-
1}(x) =
759 \bot$ for all keys $K$ and inputs $x$.) We define the following symmetric
760 encryption schemes according to how IVs are selected.
763 \def\Enc{\Xid{\E}{$m$
\what}^
{\super}}
764 \def\GG{\Xid{G
}{$m$
\what}^
{\super}}
765 \def\EE{\Xid{E
}{$m$
\what}^
{\super}}
766 \def\DD{\Xid{D
}{$m$
\what}^
{\super}}
770 \item Randomized selection: define $
\Enc = (
\GG,
\EE,
\DD)$, where
772 Algorithm $
\GG()$: \+ \\
773 $K
\getsr \keys F$; \\
776 Algorithm $
\EE(K, x)$: \+ \\
777 $v
\getsr \Bin^
\ell$; \\
778 $(v', x)
\gets \id{encrypt
}^
{F_K(
\cdot)
}(v, x)$; \\
781 Algorithm $
\DD(K, y')$; \+ \\
782 $(v, y)
\gets y'$; \\
783 $(v', x)
\gets {}$ \\
784 \qquad $
\id{decrypt
}^
{F_K(
\cdot), F^
{-
1}_K(
\cdot)
}(v, y)$; \\
790 \def\imsg{\Xid{i
}{msg
}}
791 \item Generalized counters: define $
\Enc = (
\GG,
\EE,
\DD)$, where $c$ is a
792 generalized counter in $
\Bin^
\ell$, and
794 Algorithm $
\GG()$: \+ \\
795 $K
\getsr \keys F$; \\
799 Algorithm $
\EE(K, x)$: \+ \\
800 $i
\gets c(
\imsg)$; \\
801 $(v', x)
\gets \id{encrypt
}^
{F_K(
\cdot)
}(i, x)$; \\
802 $
\imsg \gets \imsg +
1$; \\
805 Algorithm $
\DD(K, y')$; \+ \\
806 $(i, y)
\gets y'$; \\
807 $(v', x)
\gets {}$ \\
808 \qquad $
\id{decrypt
}^
{F_K(
\cdot), F^
{-
1}_K(
\cdot)
}(i, y)$; \\
814 \def\imsg{\Xid{i
}{msg
}}
815 \item Encrypted counters: if $L
\ge \ell$, then define $
\Enc = (
\GG,
\EE,
816 \DD)$, where $c$ is a generalized counter in $
\Bin^
\ell$, and
818 Algorithm $
\GG()$: \+ \\
819 $K
\getsr \keys F$; \\
823 Algorithm $
\EE(K, x)$: \+ \\
824 $i
\gets c(
\imsg)$; \\
825 $v
\gets F_K(i)
[0 \bitsto \ell]$; \\
826 $(v', x)
\gets \id{encrypt
}^
{F_K(
\cdot)
}(v, x)$; \\
827 $
\imsg \gets \imsg +
1$; \\
830 Algorithm $
\DD(K, y')$; \+ \\
831 $(i, y)
\gets y'$; \\
832 $v
\gets F_K(i)
[0 \bitsto \ell]$; \\
833 $(v', x)
\gets {}$ \\
834 \qquad $
\id{decrypt
}^
{F_K(
\cdot), F^
{-
1}_K(
\cdot)
}(v, y)$; \\
837 (We require $L
\ge \ell$ for this to be well-defined; otherwise the
838 encrypted counter value is too short.)
842 \def\vnext{\Xid{v
}{next
}}
843 \item Carry-over: define $
\Enc = (
\GG,
\EE,
\DD)$ where $V_0
\in \Bin^
\ell$
844 is the initialization vector for the first message, and
846 Algorithm $
\GG()$: \+ \\
847 $K
\getsr \keys F$; \\
848 $
\vnext \gets V_0$; \\
851 Algorithm $
\EE(K, x)$: \+ \\
853 $(v', x)
\gets \id{encrypt
}^
{F_K(
\cdot)
}(v, x)$; \\
854 $
\vnext \gets v'$; \\
857 Algorithm $
\DD(K, y')$; \+ \\
858 $(v, y)
\gets y'$; \\
859 $(v', x)
\gets {}$ \\
860 \qquad $
\id{decrypt
}^
{F_K(
\cdot), F^
{-
1}_K(
\cdot)
}(v, y)$; \\
865 Note that, while the encryption algorithms of the above schemes are either
866 randomized or stateful, the decryption algorithms are simple and
870 The following simple and standard result will be very useful in our proofs.
873 \label{prop:enc-info-to-real
}
876 \item Suppose that $
\E^P = (G^P, E^P, D^P)$ is one of the symmetric
877 encryption schemes of definition~
\ref{def:enc-scheme
}, constructed from a
878 pseudorandom permutation $P
\colon \Bin^
\ell \leftrightarrow \Bin^
\ell$.
879 If $q$ is an upper bound on the number of PRP applications required for
880 the encryption $q_E$ messages totalling $
\mu_E$ bits, and $t'$ is some
882 \
[ \InSec{lor-cpa
}(
\E^P; t, q_E,
\mu_E)
\le
883 \InSec{lor-cpa
}(
\E^
{\Perm{\ell}}; t, q_E,
\mu_E) +
884 2 \cdot \InSec{prp
}(P; t + q t', q) .
886 \item Similarly, suppose that $
\E^F = (G^F, E^F, D^F)$ is one of the
887 symmetric encryption schemes of definition~
\ref{def:enc-scheme
},
888 constructed from a pseudorandom function $F
\colon \Bin^
\ell \to \Bin^L$.
889 If $q$ is an upper bound on the number of PRP applications required for
890 the encryption $q_E$ messages totalling $
\mu_E$ bits, and $t'$ is some
892 \
[ \InSec{lor-cpa
}(
\E^F; t, q_E,
\mu_E)
\le
893 \InSec{lor-cpa
}(
\E^
{\Func{\ell}{L
}}; t, q_E,
\mu_E) +
894 2 \cdot \InSec{prf
}(F; t + q t', q) .
900 \item Let $A$ be an adversary attacking the LOR-CPA security of $
\E^P$,
901 which takes time $t$ and issues $q_E$ encryption queries totalling
902 $
\mu_E$ bits. We construct an adversary $B$ attacking the security of
903 the PRP $P$ as follows. $B$ selects a random $b^*
\inr \Bin$. It then
904 runs $A$, simulating the LOR-CPA game by using $b^*$ to decide whether to
905 encrypt the left or right plaintext, and using its oracle access to $P$
906 to do the encryption. Eventually, $A$ returns a bit $b$. If $b = b^*$,
907 $B$ returns $
1$ (indicating `pseudorandom'); otherwise it returns $
0$.
909 If $B$'s oracle is selected from the PRP $P$, then $B$ correctly
910 simulates the LOR-CPA game for $
\E^P$, and $B$ returns $
1$ with
911 probability precisely $(
\Adv{lor-cpa
}{\E^P
}(A) +
1)/
2$. Conversely, if
912 $B$'s oracle is a random permutation, then $B$ correctly simulates the
913 LOR-CPA game for $
\E^
{\Perm{\ell}}$, so $B$ returns $
1$ with probability
914 $(
\Adv{lor-cpa
}{\E^P
}(A) +
1)/
2$. Thus, we have
917 & = (
\Adv{lor-cpa
}{\E^P
}(A) +
1)/
2
918 - (
\Adv{lor-cpa
}{\E^
{\Perm{\ell}}}(A) +
1)/
2 \\
919 & = (
\Adv{lor-cpa
}{\E^P
}(A)
920 -
\Adv{lor-cpa
}{\E^
{\Perm{\ell}}}(A))/
2 .
922 Note that the extra work which $B$ does over $A$ -- initialization,
923 tidying up and encrypting messages -- is bounded by some small constant
924 $t_P$ multiplied by the number of oracle queries~$q$ made by~$B$, and the
925 required result follows by multiplying through by~$
2$ and rearranging.
926 \item The proof for this case is almost identical: merely substitute $F$
927 for $P$, `PRF' for `PRP' and $
\Func{\ell}{L
}$ for $
\Perm{\ell}$ in the
932 Of course, proving theorems about each of the above schemes individually will
933 be very tedious. We therefore define a `hybrid' scheme which switches
934 between the above selection methods. This isn't a practical encryption
935 scheme -- just a `trick' to reduce the number of complicated proofs we need
938 \begin{definition
}[Hybrid encryption modes
]
939 \label{def:enc-hybrid
}
940 \def\Enc{\Xid{\E}{$m$
\what}^
{\super}_
{\sub}}
941 \def\GG{\Xid{G
}{$m$
\what}^
{\super}_
{\sub}}
942 \def\EE{\Xid{E
}{$m$
\what}^
{\super}_
{\sub}}
943 \def\DD{\Xid{D
}{$m$
\what}^
{\super}_
{\sub}}
945 \def\super{F, V_0, c
}
946 \def\sub{n_L, n_C, n_E
}
947 \def\imsg{\Xid{i
}{msg
}}
948 \def\vnext{\Xid{v
}{next
}}
949 Let $n_L$, $n_C$ and $n_E$ be nonnegative integers, with $n_L + n_C + n_E
950 \le 2^
{\ell}$; let $F$ be a pseudorandom permutation on $
\Bin^
\ell$ (resp.\
951 a pseudorandom function from $
\Bin^
\ell$ to $
\Bin^L$); let $m =
952 (
\id{encrypt
},
\id{decrypt
})$ be a block cipher (resp.\ PRF) encryption
953 mode let $V_0
\in \Bin^
\ell$ be an initialization vector; and let $c
\colon
954 \Nupto{2^
\ell} \to \Bin^
\ell$ be a generalized counter. (Again, if $F$ is
955 a PRF, we set $F_K(x) =
\bot$ for all $K$ and $x$.) We define the scheme
956 $
\Enc = (
\GG,
\EE,
\DD)$ as follows.
958 Algorithm $
\GG()$: \+ \\
959 $K
\getsr \keys F$; \\
961 $
\vnext \gets V_0$; \\
964 Algorithm $
\DD(K, y')$; \+ \\
965 $(v, y)
\gets y'$; \\
966 $(v', x)
\gets \id{decrypt
}^
{F_K(
\cdot), F^
{-
1}_K(
\cdot)
}(v, y)$; \\
969 Algorithm $
\EE(K, x)$: \+ \\
970 \IF $
\imsg < n_L$
\THEN $v
\gets \vnext$; \\
971 \ELSE\IF $
\imsg < n_L + n_C$
\THEN $v
\gets c(
\imsg)$; \\
972 \ELSE\IF $
\imsg < n_L + n_C + n_E$
\THEN
973 $v
\gets F_K(c(
\imsg)
[0 \bitsto \ell])$; \\
974 \ELSE $v
\getsr \Bin^
\ell$; \\
975 $(v', x)
\gets \id{encrypt
}^
{F_K(
\cdot)
}(v, x)$; \\
976 $
\vnext \gets v'$; \\
977 $
\imsg \gets \imsg +
1$; \\
980 For this to be well-defined, we require that $L
\ge \ell$ or $n_E =
0$ --
981 otherwise the encrypted counter values are too short.
984 The following proposition relates the security of our artificial hybrid
985 scheme to that of the practical schemes defined in
986 definition~
\ref{def:enc-scheme
}.
989 \label{prop:enc-hybrid
}
990 Let $F$ be a pseudorandom permutation on $
\Bin^
\ell$ (resp.\ a pseudorandom
991 function from $
\Bin^
\ell$ to $
\Bin^L$); let $m$ be a block cipher (resp.\
992 PRF) encryption mode. Then:
994 \def\ii#1{\item $
\displaystyle#1$
}
995 \ii{\InSec{lor-cpa
}(
\Xid{E
}{$m\$$
}^F; t, q_E,
\mu_E)
\le
996 \InSec{lor-cpa
}(
\Xid{E
}{$m$H
}^
{F, V_0, c
}_
{0,
0,
0}; t, q_E,
\mu_E)
}
997 \ii{\InSec{lor-cpa
}(
\Xid{E
}{$m$C
}^
{F, c
}; t, q_E,
\mu_E)
\le
999 (
\Xid{E
}{$m$H
}^
{F, V_0, c
}_
{q_E,
0,
0}; t, q_E,
\mu_E)
}
1000 \ii{\InSec{lor-cpa
}(
\Xid{E
}{$m$E
}^
{F, c
}; t, q_E,
\mu_E)
\le
1002 (
\Xid{E
}{$m$H
}^
{F, V_0, c
}_
{0, q_E,
0}; t, q_E,
\mu_E)
}
1003 \ii{\InSec{lor-cpa
}(
\Xid{E
}{$m$L
}^
{F, V_0
}; t, q_E,
\mu_E)
\le
1005 (
\Xid{E
}{$m$H
}^
{F, V_0, c
}_
{0,
0, q_E
}; t, q_E,
\mu_E)
}
1010 For
1, it suffices to note that $
\Xid{E
}{$m\$$
}^F
\equiv \Xid{E
}{$m$H
}^
{c,
1011 V_0
}_
{0,
0,
0}$ for any $c$, $V_0$. For the others, we observe that, while
1012 the IVs returned in the ciphertexts differ, it's very easy to simulate
1013 encryption for the practical schemes given an encryption oracle for the
1014 hybrid scheme: for the counter and encrypted-counter schemes, the counter
1015 function is public knowledge; for the carry-over scheme, the correct IV for
1016 the first message is known, and the IV any subsequent messages can be
1017 computed from the previous IV and ciphertext according to condition~
4 in
1018 definition~
\ref{def:enc-scheme
}.
1021 %%%--------------------------------------------------------------------------
1023 \section{Ciphertext block chaining (CBC) encryption
}
1026 \subsection{Description
}
1027 \label{sec:cbc-desc
}
1029 Suppose $E$ is an $
\ell$-bit pseudorandom permutation. CBC mode works as
1030 follows. Given a message $X$, we divide it into $
\ell$-bit blocks $x_0$,
1031 $x_1$, $
\ldots$, $x_
{n-
1}$. Choose an initialization vector $v
\in
1032 \Bin^
\ell$. Before passing each $x_i$ through $E$, we XOR it with the
1033 previous ciphertext, with $v$ standing in for the first block:
1035 y_0 = E_K(x_0
\xor v)
\qquad
1036 y_i = E_K(x_i
\xor y_
{i-
1} \
\text{(for $
1 \le i < n$)
}.
1038 The ciphertext is then the concatenation of $v$ and the $y_i$. Decryption is
1041 x_0 = E^
{-
1}_K(y_0)
\xor v
\qquad
1042 x_i = E^
{-
1}_K(y_i)
\xor y_
{i-
1} \
\text{(for $
1 \le i < n$)
}
1044 See figure~
\ref{fig:cbc
} for a diagram of CBC encryption.
1047 \begin{cgraph
}{cbc-mode
}
1048 []!
{0; <
0.85cm,
0cm>: <
0cm,
0.5cm>::
}
1049 *+=(
1,
0)+
[F
]{\mathstrut x_0
}="x"
1051 [ll
] *+=(
1,
0)+
[F
]{\mathstrut v
} :"xor"
1052 :
[dd
] *+
[F
]{E
}="e" :
[ddd
] *+=(
1,
0)+
[F
]{\mathstrut y_0
}="i"
1054 [rrruuuu
] *+=(
1,
0)+
[F
]{\mathstrut x_1
}="x"
1056 "e"
[d
] :`r
[ru
] `u "xor" "xor"
1057 :
[dd
] *+
[F
]{E
}="e" :
[ddd
]
1058 *+=(
1,
0)+
[F
]{\mathstrut y_1
}="i"
1060 [rrruuuu
] *+=(
1,
0)+
[F--
]{\mathstrut x_i
}="x"
1061 :@
{-->
}[dd
] *
{\xor}="xor"
1062 "e"
[d
] :@
{-->
}`r
[ru
] `u "xor" "xor"
1063 :@
{-->
}[dd
] *+
[F
]{E
}="e" :@
{-->
}[ddd
]
1064 *+=(
1,
0)+
[F--
]{\mathstrut y_i
}="i"
1065 "e"
[l
] {K
} :@
{-->
}"e"
1066 [rrruuuu
] *+=(
1,
0)+
[F
]{\mathstrut x_
{n-
1}}="x"
1068 "e"
[d
] :@
{-->
}`r
[ru
] `u "xor" "xor"
1069 :
[dd
] *+
[F
]{E
}="e" :
[ddd
]
1070 *+=(
1,
0)+
[F
]{\mathstrut y_
{n-
1}}="i"
1074 \caption{Encryption using CBC mode
}
1078 \begin{definition
}[CBC algorithms
]
1080 For any permutation $P
\colon \Bin^
\ell \to \Bin^
\ell$, any initialization
1081 vector $v
\in \Bin^
\ell$, any plaintext $x
\in \Bin^
{\ell\N}$ and any
1082 ciphertext $y
\in \Bin^*$, we define the encryption mode $
\id{CBC
} =
1083 (
\id{cbc-encrypt
},
\id{cbc-decrypt
})$ as follows:
1085 Algorithm $
\id{cbc-encrypt
}^
{P(
\cdot)
}(v, x)$: \+ \\
1086 $y
\gets \emptystring$; \\
1087 \FOR $i =
0$
\TO $|x|/
\ell$
\DO \\
\ind
1088 $x_i
\gets x
[\ell i
\bitsto \ell (i +
1)
]$; \\
1089 $y_i
\gets P(x_i
\xor v)$; \\
1091 $y
\gets y
\cat y_i$; \- \\
1094 Algorithm $
\id{cbc-decrypt
}^
{P(
\cdot), P^
{-
1}(
\cdot)
}(v, y)$: \+ \\
1095 \IF $|y|
\bmod \ell \ne 0$
\THEN \RETURN $
\bot$; \\
1096 $x
\gets \emptystring$; \\
1097 \FOR $
1 =
0$
\TO $|y|/
\ell$
\DO \\
\ind
1098 $y_i
\gets y
[\ell i
\bitsto \ell (i +
1)
]$; \\
1099 $x_i
\gets P^
{-
1}(y_i)
\xor v$; \\
1101 $x
\gets x
\cat x_i$; \- \\
1104 Now, let $c$ be a generalized counter in $
\Bin^
\ell$. We define the
1105 encryption schemes $
\Xid{E
}{CBC$\$$
}^P$, $
\Xid{E
}{CBCE
}^P$ and
1106 $
\Xid{E
}{CBCH
}^
{P, c,
\bot}_
{0,
0, n_E
}$, as described in
1107 definition~
\ref{def:enc-scheme
}.
1110 \subsection{Security of CBC mode
}
1112 We now present our main theorem on CBC mode.
1114 \begin{theorem
}[Security of hybrid CBC mode
]
1116 Let $P
\colon \keys P
\times \Bin^
\ell \to \Bin^
\ell$ be a pseudorandom
1117 permutation; let $v_0
\in \Bin^
\ell$ be an initialization vector; let $n_L
1118 \in \
{\,
0,
1 \,\
}$; let $c$ be a generalized counter in $
\Bin^
\ell$; and
1119 let $n_C
\in \N$ be a nonnegative integer; and suppose that at most one of
1120 $n_L$ and $n_C$ is nonzero. Then, for any $t$, $q_E
\ge n$ and $
\mu_E$,
1122 (
\Xid{\E}{CBCH
}^
{P, c, v_0
}_
{n_L,
0, n_E
}; t, q_E,
\mu_E)
\le
1123 2 \cdot \InSec{prp
}(P; t + q t_P, q) +
\frac{q (q -
1)
}{2^
\ell - q
}
1125 where $q = n_L + n_E +
\mu_E/
\ell$ and $t_P$ is some small constant.
1128 The proof of this theorem we postpone until section~
\ref{sec:cbc-proof
}. As
1129 promised, the security of our randomized and stateful schemes follow as
1132 \begin{corollary
}[Security of practical CBC modes
]
1134 Let $P$ and $c$ be as in theorem~
\ref{thm:cbc
}. Then for any $t$, $q_E$
1135 and $
\mu_E$, and some small constant $t_P$,
1136 \begin{eqnarray*
}[rl
]
1137 \InSec{lor-cpa
}(
\Xid{\E}{CBC$\$$
}^P; t, q_E,
\mu_E)
1138 &
\le 2 \cdot \InSec{prp
}(P; t + q t_P, q) +
\frac{q (q -
1)
}{2^
\ell - q
}
1140 \InSec{lor-cpa
}(
\Xid{\E}{CBCE
}^
{P, c
}; t, q_E,
\mu_E)
1141 &
\le 2 \cdot \InSec{prp
}(P; t + q' t_P, q') +
1142 \frac{q' (q' -
1)
}{2^
\ell - q'
}
1145 \InSec{lor-cpa
}(
\Xid{\E}{CBCL
}^
{P, v_0
}; t,
1,
\mu_E)
1146 &
\le 2 \cdot \InSec{prp
}(P; t + q t_P, q) +
1147 \frac{q (q -
1)
}{2^
\ell - q
}
1149 where $q =
\mu_E/
\ell$, and $q' = q + q_E$.
1152 Follows from theorem~
\ref{thm:cbc
} and proposition~
\ref{prop:enc-hybrid
}.
1156 The insecurity of CBC mode over that inherent in the underlying PRP is
1157 essentially a birthday bound: note for $q
\le 2^
{\ell/
2}$, our denominator
1158 $
2^
\ell - q
\approx 2^
\ell$, and for larger $q$, the term $q (q -
1)/
2^
\ell
1159 >
1$ anyway, so all security is lost (according to the above result).
1160 Compared to
\cite[theorem~
17]{Bellare:
2000:CST
}, we gain the tiny extra
1161 term in the denominator, but lose the PRP-as-a-PRF term $q^
2
1162 2^
{-
\ell-
1}$.
\footnote{%
1163 In fact, they don't prove the stated bound of $q (
3 q -
2)/
2^
{\ell+
1}$
1164 but instead the larger $q (
2 q -
1)/
2^
\ell$. The error is in the
1165 application of their proposition~
8: the PRF-insecurity term is doubled,
1166 so the PRP-as-a-PRF term must be also.
} %
1169 \subsection{Ciphertext stealing
}
1171 Ciphertext stealing
\cite{Daemen:
1995:CHF,Schneier:
1996:ACP,RFC2040
} allows
1172 us to encrypt any message in $
\Bin^*$ without the need for padding. The
1173 trick is to fill in the `gap' at the end of the last block with the end bit
1174 of the previous ciphertext, and then to put the remaining short penultimate
1175 block at the end. Decryption proceeds by first decrypting the final block to
1176 recover the remainder of the penultimate one. See
1177 figure~
\ref{fig:cbc-steal
}.
1180 \begin{cgraph
}{cbc-steal-enc
}
1181 []!
{0; <
0.85cm,
0cm>: <
0cm,
0.5cm>::
}
1182 *+=(
1,
0)+
[F
]{\mathstrut x_0
}="x"
1184 [ll
] *+=(
1,
0)+
[F
]{\mathstrut v
} :"xor"
1185 :
[dd
] *+
[F
]{E
}="e" :
[ddddd
] *+=(
1,
0)+
[F
]{\mathstrut y_0
}="i"
1187 [rrruuuu
] *+=(
1,
0)+
[F
]{\mathstrut x_1
}="x"
1189 "e"
[d
] :`r
[ru
] `u "xor" "xor"
1190 :
[dd
] *+
[F
]{E
}="e" :
[ddddd
]
1191 *+=(
1,
0)+
[F
]{\mathstrut y_1
}="i"
1193 [rrruuuu
] *+=(
1,
0)+
[F--
]{\mathstrut x_i
}="x"
1194 :@
{-->
}[dd
] *
{\xor}="xor"
1195 "e"
[d
] :@
{-->
}`r
[ru
] `u "xor" "xor"
1196 :@
{-->
}[dd
] *+
[F
]{E
}="e" :@
{-->
}[ddddd
]
1197 *+=(
1,
0)+
[F--
]{\mathstrut y_i
}="i"
1198 "e"
[l
] {K
} :@
{-->
}"e"
1199 [rrruuuu
] *+=(
1,
0)+
[F
]{\mathstrut x_
{n-
2}}="x"
1201 "e"
[d
] :@
{-->
}`r
[ru
] `u "xor" "xor"
1204 [rrruuuu
] *+=(
1,
0)+
[F
]{\mathstrut x_
{n-
1} \cat 0^
{\ell-t
}}="x"
1206 "e"
[d
] :`r
[ru
] `u "xor" "xor"
1207 "e"
[dddddrrr
] *+=(
1,
0)+
[F
]{\mathstrut y_
{n-
1}[0 \bitsto t
]}="i"
1210 []!
{"x"; "e" **
{}, "x"+/
4pt/ ="p",
1211 "x"; "y" **
{}, "x"+/
4pt/ ="q",
1212 "y"; "x" **
{}, "y"+/
4pt/ ="r",
1213 "y"; "i" **
{}, "y"+/
4pt/ ="s",
1219 "i" **
\dir{-
}?>*
\dir{>
}}
1220 "xor" :
[dd
] *+
[F
]{E
}="e"
1222 "e"
[dddddlll
] *+=(
1,
0)+
[F
]{\mathstrut y_
{n-
2}}="i"
1225 []!
{"x"; "e" **
{}, "x"+/
4pt/ ="p",
1226 "x"; "y" **
{}, "x"+/
4pt/ ="q",
1227 "y"; "x" **
{}, "y"+/
4pt/ ="r",
1228 "y"; "i" **
{}, "y"+/
4pt/ ="s",
1229 "x"; "y" **
{} ?="c" ?(
0.5)/-
4pt/ ="cx" ?(
0.5)/
4pt/ ="cy",
1234 "c" *
[@
]\cir<
4pt>
{d^u
};
1238 "i" **
\dir{-
}?>*
\dir{>
}}
1241 \begin{cgraph
}{cbc-steal-dec
}
1242 []!
{0; <
0.85cm,
0cm>: <
0cm,
0.5cm>::
}
1243 *+=(
1,
0)+
[F
]{\mathstrut y_0
}="y"
1244 :
[ddddddd
] *+
[F
]{D
}="d"
[l
] {K
} :"d"
1245 [rrrdd
] *
{\xor} ="nx" "d"
[u
] :`r
[rd
] `d "nx" "nx"
1246 "d" :
[dd
] *
{\xor} ="xor"
[ll
] *+=(
1,
0)+
[F
]{\mathstrut v
} :"xor"
1247 :
[dd
] *+=(
1,
0)+
[F
]{\mathstrut x_0
} "nx"="xor"
1248 "y"
[rrr
] *+=(
1,
0)+
[F
]{\mathstrut y_1
}="y"
1249 :
[ddddddd
] *+
[F
]{D
}="d"
[l
] {K
} :"d"
1250 [rrrdd
] *
{\xor} ="nx" "d"
[u
] :@
{-->
}`r
[rd
] `d "nx" "nx"
1252 :
[dd
] *+=(
1,
0)+
[F
]{\mathstrut x_1
} "nx"="xor"
1253 "y"
[rrr
] *+=(
1,
0)+
[F--
]{\mathstrut y_i
}="y"
1254 :@
{-->
}[ddddddd
] *+
[F
]{D
}="d"
[l
] {K
} :"d"
1255 [rrrdd
] *
{\xor} ="nx" "d"
[u
] :@
{-->
}`r
[rd
] `d "nx" "nx"
1257 :
[dd
] *+=(
1,
0)+
[F--
]{\mathstrut x_i
} "nx"="xor"
1258 "y"
[rrr
] *+=(
1,
0)+
[F
]{\mathstrut y_
{n-
2}}="y"
1259 [dddddrrr
] *+
[F
]{D
}="d"
[r
] {K
} :"d"
1262 []!
{"x"; "y" **
{}, "x"+/
4pt/ ="p",
1263 "x"; "e" **
{}, "x"+/
4pt/ ="q",
1264 "e"; "x" **
{}, "e"+/
4pt/ ="r",
1265 "e"; "d" **
{}, "e"+/
4pt/ ="s",
1271 "d" **
\dir{-
}?>*
\dir{>
}}
1273 "z"
[llluu
] *
{\xor} ="x1"
1274 "z" :`l
[lu
] `u "x1" |*+
{\scriptstyle 0^t
\cat z
[t
\bitsto \ell]} "x1"
1275 "z" :
[dd
] *
{\xor} ="xor2"
1276 :
[dd
] *+
[F
]{\mathstrut x_
{n-
1}[0 \bitsto t
]}
1277 "y"
[rrr
] *+=(
1,
0)+
[F
]{\mathstrut y_
{n-
1} \cat 0^
{\ell-t
}}="y"
1280 []!
{"x"; "y" **
{}, "x"+/
4pt/ ="p",
1281 "x"; "e" **
{}, "x"+/
4pt/ ="q",
1282 "e"; "x" **
{}, "e"+/
4pt/ ="r",
1283 "e"; "x1" **
{}, "e"+/
4pt/ ="s",
1284 "x"; "e" **
{} ?="c" ?(
0.5)/-
4pt/ ="cx" ?(
0.5)/
4pt/ ="cy",
1289 "c" *
[@
]\cir<
4pt>
{d^u
};
1293 "x1" **
\dir{-
}?>*
\dir{>
}}
1294 "x1"
[d
] :`r
[rd
] `d "xor2" "xor2"
1295 "x1" :
[dd
] *+
[F
]{D
}="d"
[l
] {K
} :"d"
1297 :
[dd
] *+
[F
]{\mathstrut x_
{n-
2}}
1300 \caption{Encryption and decryption using CBC mode with ciphertext stealing
}
1301 \label{fig:cbc-steal
}
1304 Encrypting messages shorter than the block involves `IV stealing', which is a
1305 grotty hack but works fine if IVs are random; if the IVs are encrypted
1306 counters then there's nothing (modifiable) to steal from.
1308 We formally present a description of a randomized CBC stealing mode.
1310 \begin{definition
}[CBC mode with ciphertext stealing
]
1311 \label{def:cbc-steal
}
1312 Let $P
\colon \keys P
\times \Bin^
\ell \to \Bin^
\ell$ be a pseudorandom
1313 permutation. Let $c$ be a generalized counter on $
\Bin^
\ell$. We define
1314 the randomized symmetric encryption scheme
1315 $
\Xid{\E}{CBC$\$$-steal
}^P = (
\Xid{G
}{CBC$\$$-steal
}^P,
1316 \Xid{E
}{CBC$\$$-steal
}^P,
\Xid{D
}{CBC\$-steal
}^P)$ for messages in $
\Bin^*$
1319 Algorithm $
\Xid{G
}{CBC$\$$-steal
}^P()$: \+ \\
1320 $K
\getsr \keys P$; \\
1322 \- \\
[\medskipamount]
1323 Algorithm $
\Xid{E
}{CBC$\$$-steal
}^P(K, x)$: \+ \\
1324 $t
\gets |x|
\bmod \ell$; \\
1325 \IF $t
\ne 0$
\THEN $x
\gets x
\cat 0^
{\ell-t
}$; \\
1326 $v
\getsr \Bin^
\ell$; \\
1327 $y
\gets v
\cat \id{cbc-encrypt
}(K, v, x)$; \\
1328 \IF $t
\ne 0$
\THEN \\
\ind
1329 $b
\gets |y| -
2\ell$; \\
1330 $y
\gets $\=$y
[0 \bitsto b
] \cat
1331 y
[b +
\ell \bitsto |y|
] \cat {}$ \\
1332 \>$y
[b
\bitsto b + t
]$; \- \\
1335 Algorithm $
\Xid{D
}{CBC$\$$-steal
}^P(K, y)$: \+ \\
1336 \IF $|y| <
\ell$
\THEN \RETURN $
\bot$; \\
1337 $v
\gets y
[0 \bitsto \ell]$; \\
1338 $t = |y|
\bmod \ell$; \\
1339 \IF $t
\ne 0$
\THEN \\
\ind
1340 $b
\gets |y| - t -
\ell$; \\
1341 $z
\gets P^
{-
1}_K(y
[b
\bitsto b +
\ell])$; \\
1342 $y
\gets $\=$y
[0 \bitsto b
] \cat
1343 y
[b +
\ell \bitsto |y|
] \cat {}$ \\
1344 \>$z
[t
\bitsto \ell]$; \- \\
1345 $x
\gets \id{cbc-decrypt
}(K, v, y
[\ell \bitsto |y|
])$; \\
1346 \IF $t
\ne 0$
\THEN \\
\ind
1347 $x
\gets x
\cat z
[0 \bitsto t
] \xor y
[b
\bitsto b + t
]$; \- \\
1352 The security of ciphertext stealing follows directly from the definition and
1353 the security CBC mode.
1355 \begin{corollary
}[Security of CBC with ciphertext stealing
]
1356 \label{cor:cbc-steal
}
1357 Let $P
\colon \keys P
\times \Bin^
\ell \to \Bin^
\ell$ be a pseudorandom
1359 \begin{eqnarray*
}[rl
]
1360 \InSec{lor-cpa
}(
\Xid{\E}{CBC$\$$-steal
}; t, q_E,
\mu_E)
1361 &
\le \InSec{lor-cpa
}
1362 (
\Xid{\E}{CBC$\$$
}; t, q_E,
\mu_E + q_E (
\ell -
1)) \\
1363 &
\le 2 \cdot \InSec{prp
}(P; t + q t_P, q) +
1364 \frac{q (q -
1)
}{2^
\ell -
2^
{\ell/
2}}
1366 where $q =
\bigl\lfloor \bigl(
\mu_E + q_E (
\ell -
1)
\bigr)/
\ell
1367 \bigr\rfloor$ and $t_P$ is some small constant.
1371 From the definition, we see that the encryption algorithm
1372 $
\Xid{E
}{CBC-steal
}$ simply pads a plaintext, encrypts it as for standard
1373 CBC mode, and postprocesses the ciphertext. Hence, if $A$ is any adversary
1374 attacking $
\Xid{\E}{CBC-steal
}$, we can construct an adversary
1375 $A'$ which simply runs $A$ except that, on each query to the encryption
1376 oracle, it pads both plaintexts, queries its CBC oracle, postprocesses the
1377 ciphertext returned, and gives the result back to $A$. The fact that
1378 plaintexts can now be up to $
\ell -
1$ bits shorter than the next largest
1379 whole number of blocks means that $B$ submits no more than $
\mu_E + q_E
1380 (
\ell -
1)$ bits of plaintext to its oracle. The required result
1381 follows then directly from theorem~
\ref{thm:cbc
}.
1384 \subsection{Proof of theorem~
\ref{thm:cbc
}}
1385 \label{sec:cbc-proof
}
1387 The techniques and notation used in this proof will also be found in several
1388 of the others. We recommend that readers try to follow this one carefully.
1390 We begin considering CBC mode using a completely random permutation. To
1391 simplify notation slightly, we shall write $n = n_L + n_E$. Our main goal is
1392 to prove the claim that there exists a garbage-emitter $W$ such that
1395 (
\Xid{\E}{CBCH
}^
{\Perm{\ell}, c, v_0
}_
{n_L,
0, n_E
};
1397 \frac{q (q -
1)
}{2 \cdot (
2^
\ell - n)
}.
1399 From this, we can apply proposition~
\ref{prop:rog-and-lor
} to obtain
1402 (
\Xid{\E}{CBCH
}^
{\Perm{\ell}, c,
\bot}_
{0,
0, n
};
1404 \frac{q (q -
1)
}{2^
\ell - n
}.
1406 and, noting that there are precisely $q =
\mu_E/
\ell$ PRP-applications, we
1407 apply proposition~
\ref{prop:enc-info-to-real
} to obtain the required result.
1409 Our garbage-emitter $W$ is a bit complicated. It chooses random but
1410 \emph{distinct
} blocks for the `ciphertext'; for the IVs, it uses $v_0$ for
1411 the first message if $n_L =
1$, and otherwise it chooses random blocks
1412 distinct from each other and the `ciphertext' blocks for the next $n_E$
1413 messages, and just random blocks for subsequent ones. The algorithm $W$ is
1414 shown in figure~
\ref{fig:cbc-garbage
}.
1418 Initialization: \+ \\
1420 $
\id{gone
} \gets \emptyset$;
1421 \- \\
[\medskipamount]
1422 Function $
\id{fresh
}()$ \+ \\
1423 $x
\getsr \Bin^
\ell \setminus \id{gone
}$; \\
1424 $
\id{gone
} \gets \id{gone
} \cup \
{ x \
}$; \\
1427 Garbage emitter $W(m)$: \+ \\
1428 \IF $i
\ge 2^
\ell$
\THEN \ABORT; \\
1429 \IF $i < n_L$
\THEN $v
\gets v_0$; \\
1430 \ELSE \IF $i < n$
\THEN $v
\gets \id{fresh
}()$; \\
1432 \ELSE $v
\getsr \Bin^
\ell$; \\
1433 $y
\gets \emptystring$; \\
1434 \FOR $j =
0$
\TO $m/
\ell$; \\
\ind
1435 $y_j
\gets \id{fresh
}()$; \\
1436 $y
\gets y
\cat y_j$; \- \\
1440 \caption{Garbage emitter $W$ for CBC mode
}
1441 \label{fig:cbc-garbage
}
1444 Fortunately, it doesn't need to be efficient: the above simulations only need
1445 to be able to do the LOR game, not the ROG one. The unpleasant-sounding
1446 \ABORT\ only occurs after $
2^
\ell$ queries. If that happens we give up and
1447 say the adversary won anyway: the claim is trivially true by this point,
1448 since the adversary's maximum advantage is
1.
1450 Now we show that this lash-up is a good imitation of CBC encryption to
1451 someone who doesn't know the key. The intuition works like this: every time
1452 we query a random permutation at a new, fresh input value, we get a new,
1453 different, random output value; conversely, if we repeat an input, we get the
1454 same value out as last time. So, in the real `result' CBC game, if all the
1455 permutation inputs are distinct, it looks just like the garbage emitted by
1456 $W$. Unfortunately, that's not quite enough: the adversary can work out what
1457 the permutation inputs ought to be and spot when there ought to have been a
1458 collision but wasn't. So we'll show that, provided all the $P$-inputs --
1459 values which
\emph{would
} be input to the permutation if we're playing that
1460 game -- are distinct, the two games look identical.
1462 We need some notation to describe the values in the game. Let $c_i = c(i)$
1463 be the $i$th counter value, for $
0 \le i < n_E$, and let $v_i$ be the $i$th
1464 initialization vector, where $v_0$ is as given if $n_L =
1$, $v_i = P(c_i -
1465 n_L)$ if $n_L
\le i < n$, and $v_i
\inr \Bin^
\ell$ if $n
\le i < q_E$. Let
1466 $q' =
\mu_E/
\ell = q - n$ be the total number of plaintext blocks in the
1467 adversary's queries, let $x_i$ be the $i$th plaintext block queried, let
1468 $y_i$ be the $i$th ciphertext block returned, let
1469 \
[ w_i =
\begin{cases
}
1470 v_j & if block $i$ is the first block of the $j$th query, and \\
1473 and let $z_i = x_i
\xor w_i$, all for $
0 \le i < q'$. This is summarized
1474 diagramatically in figure~
\ref{fig:cbc-proof-notation
}. The $P$-inputs are
1475 now precisely the $c_i$ and the $z_i$. We'll denote probabilities in the
1476 `result' game as $
\Pr_R[\cdot]$ and in the `garbage' game as $
\Pr_G[\cdot]$.
1480 \begin{vgraph
}{cbc-notation-a
}
1481 [] !
{<
1.33cm,
0cm>: <
0cm,
1cm>::
}
1482 {c_i
} :
[r
] *+
[F
]{E
}="e"
[u
] {K
} :"e" :
[r
] {v_i
}
1484 \begin{vgraph
}{cbc-notation-b
}
1485 [] !
{<
1.33cm,
0cm>: <
0cm,
1cm>::
}
1486 {x_i
} :
[r
] *
{\xor} ="xor" :
[r
] {z_i
}
1487 :
[r
] *+
[F
]{E
}="e"
[u
] {K
} :"e" :
[r
] {y_i
}
1488 "xor"
[u
] {w_i
} ="w" :"xor"
1489 "w"
[lu
] {v_j
} ="v" :"w"
1490 "w"
[ru
] {y_
{i-
1}} ="y" :"w"
1491 "v" :@
{.
}|-*+
\hbox{or
} "y"
1495 \caption{Notation for the proof of theorem~
\ref{thm:cbc
}.
}
1496 \label{fig:cbc-proof-notation
}
1499 Let $C_r$ be the event, in either game, that $z_i = z_j$ for some $
0 \le i <
1500 j < r$, or that $z_i = c_j$ for some $
0 \le i < r$ and some $
0 \le j < n_E$.
1501 We need to bound the probability that $C_
{q'
}$ occurs in both the `result'
1502 and `garbage' games. We'll do this inductively. By the definition,
1503 $
\Pr_R[C_0
] =
\Pr_G[C_0
] =
0$.
1505 Firstly, tweak the games so that all of the IVs corresponding to counters are
1506 chosen at the beginning, instead of as we go along. Obviously this doesn't
1507 make any difference to the adversary's view of the proceedings, but it makes
1508 our analysis easier.
1510 Let's assume that $C_r$ didn't happen; we want the probability that $C_
{r+
1}$
1511 did, which is obviously just the probability that $z_r$ collides with some
1512 $z_i$ for $
0 \le i < r$ or some $c_i$ for $
0 \le i < n$. At this point, the
1513 previous $z_i$ are fixed. So:
1516 \Pr[C_
{r+
1} |
\bar{C
}_r
]
1517 =
\sum_{z
\in \Bin^
\ell} \biggl(
1518 \sum_{0\le i<n
} \Pr[z = c_i
] +
1519 \sum_{0\le i<r
} \Pr[z = z_i
]
1520 \biggr)
\cdot \Pr[z_r = z
]
1522 Now note that $z_r = w_r
\xor x_r$. We've no idea how $x_r$ was chosen; but,
1523 one of the following cases holds.
1525 \item If $x_r$ is the first block of the first plaintext, i.e., $r =
0$, and
1526 $n_L =
1$, then $w_r = v_0$. However, in this case we know that $n_E =
0$
1527 by hypothesis. There are no $z_i$ which $z_r$ might collide with, so the
1528 probability of a collision is zero.
1529 \item If $x_r$ is the first block of plaintext $i$, and $
0 \le i < n$, then
1530 $w_r = v_i$, and was chosen at random from a set of $
2^
\ell - i
\le 2^
\ell
1531 - n
\le 2^
\ell - n - r$ possibilities, either by our random permutation or
1532 by $W$. We know $x_r$ is independent of $w_r$ because none of the previous
1533 $P$-inputs were equal to $c_i$, by our assumption of $
\bar{C
}_r$.
1534 \item If $x_r$ is the first block of plaintext $i$, and $n
\le i < q'$, then
1535 $w_r = v_i$, and was chosen at random from all $
2\ell$ possible $
\ell$-bit
1536 blocks. We know $x_r$ is independent of $w_r$ because we just chose $w_r$
1537 at random, after $x_r$ was chosen.
1538 \item Otherwise, $x_r$ is a subsequent block in some message, and $w_r =
1539 y_
{r-
1}$, and was chosen at random from a set of $
2^
\ell - n - r$
1540 possibilities, either by our random permutation or by $W$. We know $x_r$
1541 is independent of $w_r$ because $z_
{r-
1}$ is a new $P$-input, by our
1542 assumption of $
\bar{C
}_r$.
1544 So, except in case~
1, which isn't a problem anyway, $w_r$ is independent of
1545 $x_r$, and chosen uniformly at random from a set of at least $
2^
\ell - r - n$
1546 elements, in either game -- so we can already see that $
\Pr_R[C_i
] =
1547 \Pr_G[C_i
]$ for any $i
\ge 0$. Finally, the $z_i$ and $c_i$ are all
1548 distinct, so the $z_i
\xor x$ and $c_i
\xor x$ must all be distinct, for any
1550 \begin{eqnarray
}[rl
]
1551 \Pr[C_
{r+
1} |
\bar{C
}_r
]
1552 & =
\sum_{x
\in \Bin^
\ell} \biggl(
1553 \sum_{0\le i<n
} \Pr[w_r = x
\xor c_i
] +
1554 \sum_{0\le i<r
} \Pr[w_r = x
\xor z_i
]
1555 \biggr)
\cdot \Pr[x_r = x
] \\
1556 &
\le \sum_{x
\in \Bin^
\ell} \frac{r + n
}{2^
\ell - r - n
} \Pr[x_r = x
]
1557 =
\frac{r + n
}{2^
\ell - r - n
} \sum_{x
\in \Bin^
\ell} \Pr[x_r = x
] \\
1558 & =
\frac{r + n
}{2^
\ell - r - n
}.
1560 Now we're almost home. All the $c_i$ and $z_i$ are distinct; all the $v_i$
1561 and $y_i$ are random, assuming $C_
{q'
}$. We can bound $
\Pr[C_
{q'
}]$ thus:
1564 \le \sum_{0<i
\le q'
} \Pr[C_i |
\bar{C
}_
{i-
1}]
1565 \le \sum_{0\le i
\le q'
} \frac{i + n -
1}{2^
\ell - i - n +
1}
1567 Now, let $i' = i + n -
1$. Then
1570 \le \sum_{n-
1\le i'
\le q'+n-
1} \frac{i'
}{2^
\ell - i'
}
1571 \le \sum_{0\le i'<q
} \frac{i'
}{2^
\ell - q
}
1572 =
\frac{q (q -
1)
}{2 \cdot (
2^
\ell - q)
}
1575 Finally, let $R$ be the event that the adversary returned
1 at the end of the
1576 game -- indicating a guess of `result'. Then, noting as we have, that
1577 $
\Pr_R[C_
{q'
}] =
\Pr_G[C_
{q'
}]$, we get this:
1578 \begin{eqnarray
}[rl
]
1579 \Adv{rog-cpa-$W$
}{\Xid{\E}{CBCH
}^
{P, c, n
}}(A)
1580 & =
\Pr_R[R
] -
\Pr_G[R
] \\
1581 &
\begin{eqnalign
}[rLl
][b
]
1582 {} = & (
\Pr_R[R | C_
{q'
}] \Pr_R[C_
{q'
}] +
1583 \Pr_R[R |
\bar{C
}_
{q'
}] \Pr_R[\bar{C
}_
{q'
}]) -
{} \\
1584 & & (
\Pr_G[R | C_
{q'
}] \Pr_R[C_
{q'
}] +
1585 \Pr_G[R |
\bar{C
}_
{q'
}] \Pr_G[\bar{C
}_
{q'
}])
1587 & =
\Pr_R[R | C_
{q'
}] \Pr_R[C_
{q'
}] -
\Pr_G[R | C_
{q'
}] \Pr_G[C_
{q'
}] \\
1588 &
\le \Pr[C_
{q'
}] \le \frac{q (q -
1)
}{2 \cdot (
2^
\ell - q)
}
1593 %%%--------------------------------------------------------------------------
1595 \section{Ciphertext feedback (CFB) encryption
}
1598 \subsection{Description
}
1599 \label{sec:cfb-desc
}
1601 Suppose $F$ is an $
\ell$-bit-to-$L$-bit pseudorandom function, and let $t
\le
1602 L$. CFB mode works as follows. Given a message $X$, we divide it into
1603 $t$-bit blocks $x_0$, $x_1$, $
\ldots$, $x_
{n-
1}$. Choose an initialization
1604 vector $v
\in \Bin^
\ell$. We maintain a
\emph{shift register
} $s_i$, whose
1605 initial value is $v$. To encrypt a block $x_i$, we XOR it with the result of
1606 passing the shift register through the PRF, forming $y_i$, and then update
1607 the shift register by shifting in the ciphertext block $y_i$. That is,
1610 y_i = x_i
\xor F_K(s_i)
\qquad
1611 s_
{i+
1} = s_i
\shift{t
} y_i \
\text{(for $
0 \le i < n$)
}.
1613 Decryption follows from noting that $x_i = y_i
\xor F_K(s_i)$. See
1614 figure~
\ref{fig:cfb
} for a diagrammatic representation.
1616 Also, we observe that the final plaintext block needn't be $t$ bits long: we
1617 can pad it out to $t$ bits and truncate the result without affecting our
1621 \begin{cgraph
}{cfb-mode
}
1622 [] !
{<
0.425cm,
0cm>: <
0cm,
0.5cm>::
}
1623 *+=(
2,
0)+
[F
]{\mathstrut v
} ="v" :|<>(
0.35)@
{/
}_<>(
0.35)
{\ell}[rrrrr
]
1624 *+
[o
][F
]{\shift{t
}} ="shift"
1625 [ll
] :|-@
{/
}^-
{\ell}[dd
] *+
[F
]{E
} ="e"
[ll
] {K
} :"e"
1626 :|-@
{/
}^-
{t
}[dd
] *
{\xor} ="xor"
1627 [lll
] *+=(
2,
0)+
[F
]{\mathstrut x_0
} :|-@
{/
}_-
{t
} "xor"
1628 :|-@
{/
}^-
{t
}[ddd
] *+=(
2,
0)+
[F
]{\mathstrut y_0
}
1629 "xor"
[d
] :`r "shift" "shift"|-@
{/
}_-
{t
}
1630 :|-@
{/
}_-
{\ell}[rrrrrrr
] *+
[o
][F
]{\shift{t
}} ="shift"
1631 [ll
] :|-@
{/
}^-
{\ell}[dd
] *+
[F
]{E
} ="e"
[ll
] {K
} :"e"
1632 :|-@
{/
}^-
{t
}[dd
] *
{\xor} ="xor"
1633 [lll
] *+=(
2,
0)+
[F
]{\mathstrut x_1
} :|-@
{/
}_-
{t
} "xor"
1634 :|-@
{/
}^-
{t
}[ddd
] *+=(
2,
0)+
[F
]{\mathstrut y_1
}
1635 "xor"
[d
] :`r "shift" "shift"|-@
{/
}_-
{t
}
1636 :@
{-->
}|-@
{/
}_-
{\ell}[rrrrrrr
] *+
[o
][F
]{\shift{t
}} ="shift"
1637 [ll
] :@
{-->
}|-@
{/
}^-
{\ell}[dd
] *+
[F
]{E
} ="e"
[ll
] {K
} :"e"
1638 :@
{-->
}|-@
{/
}^-
{t
}[dd
] *
{\xor} ="xor"
1639 [lll
] *+=(
2,
0)+
[F--
]{\mathstrut x_i
} :@
{-->
}|-@
{/
}_-
{t
} "xor"
1640 :@
{-->
}|-@
{/
}^-
{t
}[ddd
] *+=(
2,
0)+
[F--
]{\mathstrut y_i
}
1641 "xor"
[d
] :@
{-->
} `r "shift" "shift"|-@
{/
}_-
{t
}
1642 [rrrrrdd
] *+
[F
]{E
} ="e"
1643 "shift" :@
{-->
}`r "e" |-@
{/
}_-
{\ell} "e"
1645 :|-@
{/
}^-
{t
}[dd
] *
{\xor} ="xor"
1646 [lll
] *+=(
2,
0)+
[F
]{\mathstrut x_
{n-
1}} :|-@
{/
}_-
{t
} "xor"
1647 :|-@
{/
}^-
{t
}[ddd
] *+=(
2,
0)+
[F
]{\mathstrut y_
{n-
1}}
1650 \caption{Encryption using CFB mode
}
1654 \begin{definition
}[CFB algorithms
]
1655 For any function $F
\colon \Bin^
\ell \to \Bin^t$, any initialization vector
1656 $v
\in \Bin^
\ell$, any plaintext $x
\in \Bin^*$ and any ciphertext $y
\in
1657 \Bin^*$, we define PRF encryption mode $
\id{CFB
} = (
\id{cfb-encrypt
},
1658 \id{cfb-decrypt
})$ as follows:
1660 Algorithm $
\id{cfb-encrypt
}(F, v, x)$: \+ \\
1663 $x
\gets x
\cat 0^
{t
\lceil L/t
\rceil - L
}$; \\
1664 $y
\gets \emptystring$; \\
1665 \FOR $i =
0$
\TO $(|x| - t')/t$
\DO \\
\ind
1666 $x_i
\gets x
[ti
\bitsto t(i +
1)
]$; \\
1667 $y_i
\gets x_i
\xor F(s)$; \\
1668 $s
\gets s
\shift{t
} y_i$; \\
1669 $y
\gets y
\cat y_i$; \- \\
1670 \RETURN $(s, y
[0 \bitsto L
])$;
1672 Algorithm $
\id{cfb-decrypt
}(F, v, y)$: \+ \\
1675 $y
\gets y
\cat 0^
{t
\lceil L/t
\rceil - L
}$; \\
1676 $x
\gets \emptystring$; \\
1677 \FOR $i =
0$
\TO $(|x| - t')/t$
\DO \\
\ind
1678 $y_i
\gets y
[ti
\bitsto t(i +
1)
]$; \\
1679 $x_i
\gets x_i
\xor F(s)$; \\
1680 $s
\gets s
\shift{t
} y_i$; \\
1681 $x
\gets x
\cat x_i$; \- \\
1682 \RETURN $x
[0 \bitsto L
]$;
1684 We now define the schemes $
\Xid{\E}{CFB$\$$
}^F$,
1685 $
\Xid{\E}{CFBC
}^
{F, c
}$, $
\Xid{\E}{CFBE
}^
{F, c
}$, and
1686 $
\Xid{\E}{CFBL
}^
{F, V_0
}$ according to
1687 definition~
\ref{def:enc-scheme
}; and we define the hybrid scheme
1688 $
\Xid{\E}{CFBH
}^
{F, V_0, c
}_
{n_L, n_C, n_E
}$ according to
1689 definition~
\ref{def:enc-hybrid
}.
1692 \subsection{Security of CFB mode
}
1694 %% I suspect David will want to put some negative results here, and complain
1695 %% about Alkassar et al.'s alleged proof. I'll press on with the positive
1698 %% The problems come when $t < \ell$. Then C-mode isn't necessarily secure
1699 %% (well, we get a similar bound with $t$ instead of $\ell$, which isn't very
1700 %% impressive). The L-mode needs careful selection of the initial IV.
1702 \begin{definition
}[Sliding strings
]
1704 We say that an $
\ell$-bit string $x$
\emph{$t$-slides
} if there exist
1705 integers $i$ and $j$ such that $
0 \le j < i <
\ell/t$ and $x
[i t
\bitsto
1706 \ell] = x
[j t
\bitsto \ell - (i - j) t
]$.
1709 For all $
\ell >
0$ and $t <
\ell$, the string $
0^
{\ell-
1} 1$ does not
1713 \begin{theorem
}[Security of CFB mode
]
1715 Let $F$ be a pseudorandom function from $
\Bin^
\ell$ to $
\Bin^t$; let $V_0
1716 \in \Bin^
\ell$ be a non-$t$-sliding string; let $c$ be a generalized
1717 counter in $
\Bin^
\ell$; and let $n_L$, $n_C$, $n_E$ and $q_E$ be
1718 nonnegative integers; and furthermore suppose that
1720 \item $n_L + n_C + n_E
\le q_E$,
1721 \item $n_L =
0$, or $n_C = n_E =
0$, or $
\ell \le t$ and $V_0
\ne c(i)$
1722 for any $n_L
\le i < n_L + n_C + n_E$, and
1723 \item either $n_C =
0$ or $
\ell \le t$.
1725 Then, for any $t_E$ and $
\mu_E$, and whenever
1727 \
[ \InSec{lor-cpa
}(
\Xid{\E}{CFBH
}^
{F, V_0, c
}_
{n_L, n_C, n_E
};
1728 t_E, q_E,
\mu_E)
\le
1729 2 \cdot \InSec{prf
}(F; t_E + q t_F, q) +
\frac{q (q -
1)
}{2^
\ell}
1731 where $q =
\bigl\lfloor \bigl(
\mu_E + q_E (t -
1)
\bigr)/t
\bigr\rfloor +
1732 n_E$, and $t_F$ is some small constant.
1735 The proof is a bit involved; we postpone it until
1736 section~
\ref{sec:cfb-proof
}.
1740 Let $F$, $c$ and $V_0$ be as in theorem~
\ref{thm:cfb
}. Then for any $t_E$,
1742 \begin{eqnarray*
}[rl
]
1743 \InSec{lor-cpa
}(
\Xid{\E}{CFB$\$$
}^F; t_E, q_E,
\mu_E)
1744 &
\le 2 \cdot \InSec{prf
}(F; t_E + q t_F, q) +
\frac{q (q -
1)
}{2^
\ell}
1746 \InSec{lor-cpa
}(
\Xid{\E}{CFBE
}^
{F, c
}; t_E, q_E,
\mu_E)
1747 &
\le 2 \cdot \InSec{prf
}(F; t_E + q' t_F, q') +
1748 \frac{q' (q' -
1)
}{2^
\ell}
1750 \InSec{lor-cpa
}(
\Xid{\E}{CFBL
}^
{F, V_0
}; t_E, q_E,
\mu_E)
1751 &
\le 2 \cdot \InSec{prf
}(F; t_E + q t_F, q) +
\frac{q (q -
1)
}{2^
\ell}
1753 \tabpause{and, if $
\ell \le t$,
}
1754 \InSec{lor-cpa
}(
\Xid{\E}{CFBC
}^
{F, c
}; t_E, q_E,
\mu_E)
1755 &
\le 2 \cdot \InSec{prf
}(F; t_E + q t_F, q) +
\frac{q (q -
1)
}{2^
\ell}
1757 where $q =
\bigl\lfloor \bigl(
\mu_E + q_E (t -
1)
\bigr)/t
\bigr\rfloor +
1758 n_E$, $q' = q + q_E$, and $t_F$ is some small constant.
1761 Follows from theorem~
\ref{thm:cfb
} and proposition~
\ref{prop:enc-hybrid
}.
1766 Let $P$ be a pseudorandom permutation on $
\Bin^
\ell$, and let $c$ and $V_0$
1767 be as in theorem~
\ref{thm:cfb
}. Then for any $t_E$, $q_E$ and $
\mu_E$,
1768 \begin{eqnarray*
}[rl
]
1769 \InSec{lor-cpa
}(
\Xid{\E}{CFB$\$$
}^P; t_E, q_E,
\mu_E)
1770 &
\le 2 \cdot \InSec{prp
}(P; t_E + q t_F, q) +
\frac{q (q -
1)
}{2^
\ell}
1772 \InSec{lor-cpa
}(
\Xid{\E}{CFBE
}^
{P, c
}; t_E, q_E,
\mu_E)
1773 &
\le 2 \cdot \InSec{prp
}(P; t_E + q' t_F, q') +
1774 \frac{q' (q' -
1)
}{2^
\ell}
1776 \InSec{lor-cpa
}(
\Xid{\E}{CFBL
}^
{P, V_0
}; t_E, q_E,
\mu_E)
1777 &
\le 2 \cdot \InSec{prp
}(P; t_E + q t_F, q) +
\frac{q (q -
1)
}{2^
\ell}
1779 \tabpause{and, if $
\ell \le t$,
}
1780 \InSec{lor-cpa
}(
\Xid{\E}{CFBC
}^
{P, c
}; t_E, q_E,
\mu_E)
1781 &
\le 2 \cdot \InSec{prp
}(P; t_E + q t_F, q) +
\frac{q (q -
1)
}{2^
\ell}
1783 where $q =
\bigl\lfloor \bigl(
\mu_E + q_E (t -
1)
\bigr)/t
\bigr\rfloor +
1784 n_E$, $q' = q + q_E$, and $t_F$ is some small constant.
1787 Follows from corollary~
\ref{cor:cfb-prf
} and
1788 proposition~
\ref{prop:prps-are-prfs
}.
1791 \subsection{Proof of theorem~
\ref{thm:cfb
}}
1792 \label{sec:cfb-proof
}
1794 Our proof follows the same lines as for CBC mode: we show the ROG-CPA
1795 security of hybrid-CFB mode using an ideal random function, and then apply
1796 our earlier results to complete the proof. However, the ROG-CPA result will
1797 be useful later when we consider the security of OFB mode, so we shall be a
1798 little more formal about defining it.
1800 The garbage emitter is in some sense the `perfect' one: it emits a `correct'
1801 IV followed by a uniform random string of the correct length.
1803 \begin{definition
}[The $W_\$$ garbage emitter
]
1804 Let natural numbers $n_L$, $n_C$, and $V_0
\in \Bin^
\ell$ be given; then we
1805 define the garbage emitter $W_\$$ as follows.
1807 Initialization: \+ \\
1810 \- \\
[\medskipamount]
1811 Garbage emitter $W_\$(m)$: \+ \\
1812 \IF $i < n_L$
\THEN $v'
\gets v$; \\
1813 \ELSE \IF $n_L
\le i < n_L + n_C$
\THEN $v'
\gets c(i)$; \\
1814 \ELSE \IF $n_L + n_C
\le i$
\THEN $v'
\getsr \Bin^
\ell$; \\
1816 $m'
\gets t
\lfloor (m + t -
1)/t
\rfloor$; \\
1817 $y
\getsr \Bin^
{m'
}$; \\
1818 $v
\gets v'
\shift{m'
} y$; \\
1819 \RETURN $(v', y
[0 \bitsto m
])$
1823 We now show that CFB mode with a random function is hard to distinguish from
1825 \begin{lemma
}[Pseudorandomness of CFB mode
]
1827 Let $
\ell$, $t$, $n_L$, $n_C$, $n_E$, $q_E$, $c$, $V_0$, and $q$ be as in
1828 theorem~
\ref{thm:cfb
}. Then, for any $t_E$ and $
\mu_E$,
1829 \
[ \InSec{rog-cpa-$W_\$$
}
1830 (
\Xid{\E}{CFBH
}^
{\Func{\ell}{t
}, V_0, c
}_
{n_L, n_C, n_E
};
1832 \frac{q (q -
1)
}{2^
{\ell+
1}}.
1835 Theorem~
\ref{thm:cfb
} follows from this result by application of
1836 propositions
\ref{prop:rog-and-lor
} and~
\ref{prop:enc-info-to-real
}. It
1837 remains therefore for us to prove lemma~
\ref{lem:cfb-rog
}.
1839 To reduce the weight of notation, let us agree to suppress the adornments on
1840 $
\Adv{}{}$ and $
\InSec{}$ symbols. Also, let $m_L = n_L$; let $m_C$ = $n_L +
1841 n_C$; and let $m_E = n_L + n_C + n_E$. (Remember: the $m$s are
1842 cu
\textit{m
}ulative.)
1844 The truncation of ciphertext blocks makes matters complicated. Let us say
1845 that an adversary is
\emph{block-respecting
} if all of its plaintext queries
1846 are a multiple of $t$ bits in length; obviously all of the oracle responses
1847 for a block-respecting adversary are also a multiple of $t$ bits in length.
1849 If $A'$ be a block-respecting adversary querying a total of $
\mu_E$ bits of
1850 plaintext queries; then
1851 \
[ \Adv{}{}(A')
\le \frac{q (q -
1)
}{2^
{\ell+
1}} \
]
1852 where $q =
\mu_E/t$.
1854 Lemma~
\ref{lem:cfb-rog
} follows from this claim: if $A$ is any adversary,
1855 then we construct a block-respecting adversary $A'$ by padding $A$'s
1856 plaintext queries and truncating the oracle responses; and if $A$ makes $q_E$
1857 queries totalling $
\mu_E$ bits, then the total bits queried by $A'$ is no
1858 more than $
\bigl\lfloor\bigl(
\mu_E + q_E (t -
1)
\bigr)
\bigr\rfloor$ bits.
1859 We now proceed to the proof of the above claim.
1861 Suppose, then, that we are given a block-respecting adversary $A$ which makes
1862 $q$ queries to its encryption oracle. Let $F(
\cdot)$ denote the application
1863 of the random function. We want to show that, provided all of the $F$-inputs
1864 are distinct, the $F$-outputs are uniformly random, and hence the CFB
1865 ciphertexts are uniformly random. As for the CBC case, life isn't that good
1866 to us: we have to deal with the case where the adversary can see that two
1867 $F$-inputs would have collided, and therefore that a garbage string couldn't
1868 have been generated by CFB encryption of his plaintext.
1870 Our notation will be similar to, yet slightly different from, that of
1871 section~
\ref{sec:cbc-proof
}.
1873 Let $q' = q - n_E$ be the number of $t$-bit plaintext blocks the adversary
1874 submits, and for $
0 \le i < q'$, let $x_i$ be the $i$th plaintext block
1875 queried, and let $y_i$ be the $i$th ciphertext block returned.
1877 For $m_L
\le i < m_E$, let $c_i = c(i)$ be the $i$th counter value. For $
0
1878 \le i < q_E$ let $v_i$ be the $i$th initialization vector, i.e.,
1879 \
[ v_i =
\begin{cases
}
1880 V_0 & if $i =
0$ and $n_L >
0$; \\
1881 v_
{i-
1} \shift{t
} Y_
{i-
1}
1882 & if $
1 \le i < m_L$ and $Y_
{i-
1}$ was the ciphertext
1883 from query $i -
1$; \\
1884 c_i & if $m_L
\le i < m_C$; \\
1885 F(c_i) & if the oracle is `result', and $m_C
\le i < m_E$;
1887 R_i & for some $R_i
\inr \Bin^
\ell$, otherwise.
1890 Note that the only difference in the $v_i$ between the `result' and `garbage'
1891 games occurs in the encrypted-counters phase. Furthermore, if no other
1892 $F$-input is equal to any $c_i$ for $m_C
\le i < m_E$ then the IVs are
1893 identically distributed.
1895 Now, for $
0 \le i < q'$, define
1896 \
[ z_i =
\begin{cases
}
1897 v_j & if block $i$ is the first block of the
1899 z_
{i-
1} \shift{t
} y_
{i-
1} & otherwise
1902 and let $w_i = x_i
\xor y_i$. In the `result' game, we have $w_i = F(z_i)$,
1903 of course. All of this notation is summarized diagrammatically in
1904 figure~
\ref{fig:cfb-proof-notation
}. The $F$-inputs are precisely the $z_i$
1905 and $c_i$ for $m_C
\le i < m_E$.
1907 We'll denote probabilities in the `result' game as $
\Pr_R[\cdot]$ and in the
1908 `garbage' game as $
\Pr_G[\cdot]$.
1912 \begin{vgraph
}{cfb-notation-a
}
1913 [] !
{<
1.333cm,
0cm>: <
0cm,
1cm>::
}
1914 {z_i
} ="z" :|-@
{/
}_-
{\ell}[r
] *+
[F
]{F
} ="F"
1915 :|-@
{/
}_-
{t
}[r
] {w_i
} ="w" :|-@
{/
}_-
{t
}[r
] *
{\xor} ="xor"
1916 "xor"
[u
] {x_i
} ="x" :|-@
{/
}^-
{t
}"xor" :|-@
{/
}^-
{t
}[d
] {y_i
} ="y"
1917 "z"
[lu
] {v_j
} ="v" :"z"
1918 "z"
[ru
] {z_
{i-
1} \shift{t
} y_
{i-
1}} ="y" :"z"
1919 "v" :@
{.
}|-*+
\hbox{or
} "y"
1923 \caption{Notation for the proof of lemma~
\ref{lem:cfb-rog
}.
}
1924 \label{fig:cfb-proof-notation
}
1927 Let $C_r$ be the event, in either game, that $z_i = z_j$ for some $
0 \le i <
1928 j < r$, or that $z_i = c_j$ for some $
0 \le i < r$ and some $m_C
\le j <
1931 Let's assume that $C_r$ didn't happen; we want the probability that $C_
{r+
1}$
1932 did, which is just the probability that $z_r$ collides with some $z_i$ where
1933 $
0 \le i < r$, or some $c_i$ for $m_C
\le i < m_E$. Observe that, under this
1934 assumption, all the $w_i$, and hence the $y_i$, are uniformly distributed,
1935 and that therefore the two games are indistinguishable.
1937 One of the following cases holds.
1939 \item If $r =
0$ and $m_L >
0$ then $z_r = V_0$. There is no other $z_i$ yet
1940 for $z_r$ to collide with, though it might collide with some encrypted
1941 counter $F(c_i)$, with probability $n_E/
2^
\ell$.
1942 \item If $z_r = c_i$ is the IV for some message $i$ where $m_L
\le i < m_C$,
1943 life is a bit complicated. It can't collide with $V_0$ or other $c_i$ by
1944 assumption; the encrypted counters and random IVs haven't been chosen yet;
1945 and either $n_C =
0$ (in which case there's nothing to do here anyway) or
1946 $
\ell \le t$, so there are no $z_i$ containing partial copies of $V_0$ to
1947 worry about. This leaves non-IV $z_i$: again, $
\ell \le t$, so $z_i =
1948 y_i
[t -
\ell \bitsto t
]$, which is random by our assumption of $
\bar{C
}_r$;
1949 hence a collision with one of these $z_i$ occurs with probability at most
1951 \item If $z_r$ is the IV for some message $i$ where $m_C
\le i < m_E$, then
1952 it can collide with previous $z_i$ or either previous or future $c_i$. We
1953 know, however, that no $F$-input has collided with $c_i$, so in the
1954 `result' game, $z_r = F(c_r)$ is uniformly distributed; in the `garbage'
1955 game, $W_\$$ generates $z_r$ at random anyway. It collides, therefore,
1956 with probability at most $(r + n_E)/
2^
\ell$.
1957 \item If $z_r$ is the IV for some message $i$ where $m_E
\le i < q'$ then
1958 $z_r$ was chosen uniformly at random. Hence it collides with probability
1959 at most $(r + n_E)/
2^
\ell$.
1960 \item Finally, either $z_r$ is not the IV for a message, or it is, but the
1961 message number $i < n_L$, so in either case, $z_r = z_
{r-
1} \shift{t
}
1962 y_
{r-
1}$. We have two subcases to consider.
1964 \item If $
1 \le r <
\ell/t$ (we dealt with the case $r =
0$ above) then
1965 some of $V_0$ remains in the shift register. If $z_r$ collides with some
1966 $z_i$, for $
0 \le i < r$, then we must have $z_r
[0 \bitsto \ell - t r
] =
1967 z_i
[0 \bitsto \ell - t r
]$; but $z_r
[0 \bitsto \ell - t r
] = V_0
[t r
1968 \bitsto \ell]$, and $z_i
[0 \bitsto \ell - t r
] = V_0
[t i
\bitsto \ell - t
1969 (r - i)
]$, i.e., we have found a $t$-sliding of $V_0$, which is
1970 impossible by hypothesis. Hence, $z_r$ cannot collide with any earlier
1971 $z_i$. Also by hypothesis, $n_C = n_E =
0$ if $
\ell > t$, so $z_r$
1972 cannot collide with any counters $c_i$.
1973 \item Suppose, then, that $r
\ge \ell/t$. For $
0 \le j <
\ell/t$, let $H_j
1974 =
\ell - t j$, $L_j =
\max(
0, H_j - t)$, and $N_j = H_j - L_j$. (Note
1975 that $
\sum_{0\le j<
\ell/t
} N_j =
\ell$.) Then $z_r
[L_j
\bitsto H_j
] =
1976 y_
{r-j-
1}[t - N_j
\bitsto t
]$; but the $y_i$ for $i < r$ are uniformly
1977 distributed. Thus, $z_r$ collides with some specific other value $z'$
1978 only with probability $
1/
2^
{\sum_j N_j
} =
1/
2^
\ell$. The overall
1979 collision probablity for $z_r$ is then at most $(r + n_E)/
2^
\ell$.
1982 In all these cases, it's clear that the collision probability is no more than
1985 The probability that there is a collision during the course of the game is
1986 $
\Pr[C_
{q'
}]$, which we can now bound thus:
1988 \Pr[C_q'
] \le \sum_{0<i
\le q'
} \Pr[C_i |
\bar{C
}_
{i-
1}]
1989 \le \sum_{0<i
\le q'
} \frac{i + n_E
}{2^
\ell}.
1991 If we set $i' = i + n_E$, then we get
1993 \Pr[C_q'
] \le \sum_{0\le i'
\le q
} \frac{i'
}{2^
\ell}
1994 =
\frac{q (q -
1)
}{2^
{\ell+
1}}.
1996 Finally, then, we can apply the same argument as we used at the end of
1997 section~
\ref{sec:cbc-proof
} to show that
1999 \Adv{}{}(A')
\le \frac{q (q -
1)
}{2^
{\ell+
1}}
2001 as claimed. This completes the proof.
2003 %%%--------------------------------------------------------------------------
2005 \section{OFB mode encryption
}
2008 \subsection{Description
}
2009 \label{sec:ofb-desc
}
2011 Suppose $F$ is an $
\ell$-bit-to-$L$-bit pseudorandom function, and let $t
\le
2012 L$. OFB mode works as follows. Given a message $X$, we divide it into
2013 $t$-bit blocks $x_0$, $x_1$, $
\ldots$, $x_
{n-
1}$. Choose an initialization
2014 vector $v
\in \Bin^
\ell$. We maintain a
\emph{shift register
} $s_i$, whose
2015 initial value is $v$. To encrypt a block $x_i$, we XOR it with the result
2016 $z_i$ of passing the shift register through the PRF, forming $y_i$, and then
2017 update the shift register by shifting in the PRF output $z_i$. That
2021 z_i = F_K(s_i)
\qquad
2022 y_i = x_i
\xor z_i
\qquad
2023 s_
{i+
1} = s_i
\shift{t
} z_i \
\text{(for $
0 \le i < n$)
}.
2025 Decryption is precisely the same operation.
2027 Also, we observe that the final plaintext block needn't be $t$ bits long: we
2028 can pad it out to $t$ bits and truncate the result without affecting our
2032 \begin{cgraph
}{ofb-mode
}
2033 [] !
{<
0.425cm,
0cm>: <
0cm,
0.5cm>::
}
2034 *+=(
2,
0)+
[F
]{\mathstrut v
} ="v" :|<>(
0.35)@
{/
}_<>(
0.35)
{\ell}[rrrrr
]
2035 *+
[o
][F
]{\shift{t
}} ="shift"
2036 [ll
] :|-@
{/
}^-
{\ell}[dd
] *+
[F
]{E
} ="e"
[ll
] {K
} :"e"
2037 :|-@
{/
}^-
{t
}[ddd
] *
{\xor} ="xor"
2038 [lll
] *+=(
2,
0)+
[F
]{\mathstrut x_0
} :|-@
{/
}_-
{t
} "xor"
2039 :|-@
{/
}^-
{t
}[dd
] *+=(
2,
0)+
[F
]{\mathstrut y_0
}
2040 "xor"
[u
] :`r "shift" "shift"|-@
{/
}_-
{t
}
2041 :|-@
{/
}_-
{\ell}[rrrrrrr
] *+
[o
][F
]{\shift{t
}} ="shift"
2042 [ll
] :|-@
{/
}^-
{\ell}[dd
] *+
[F
]{E
} ="e"
[ll
] {K
} :"e"
2043 :|-@
{/
}^-
{t
}[ddd
] *
{\xor} ="xor"
2044 [lll
] *+=(
2,
0)+
[F
]{\mathstrut x_1
} :|-@
{/
}_-
{t
} "xor"
2045 :|-@
{/
}^-
{t
}[dd
] *+=(
2,
0)+
[F
]{\mathstrut y_1
}
2046 "xor"
[u
] :`r "shift" "shift"|-@
{/
}_-
{t
}
2047 :@
{-->
}|-@
{/
}_-
{\ell}[rrrrrrr
] *+
[o
][F
]{\shift{t
}} ="shift"
2048 [ll
] :@
{-->
}|-@
{/
}^-
{\ell}[dd
] *+
[F
]{E
} ="e"
[ll
] {K
} :"e"
2049 :@
{-->
}|-@
{/
}^-
{t
}[ddd
] *
{\xor} ="xor"
2050 [lll
] *+=(
2,
0)+
[F--
]{\mathstrut x_i
} :@
{-->
}|-@
{/
}_-
{t
} "xor"
2051 :@
{-->
}|-@
{/
}^-
{t
}[dd
] *+=(
2,
0)+
[F--
]{\mathstrut y_i
}
2052 "xor"
[u
] :@
{-->
} `r "shift" "shift"|-@
{/
}_-
{t
}
2053 [rrrrrdd
] *+
[F
]{E
} ="e"
2054 "shift" :@
{-->
}`r "e" |-@
{/
}_-
{\ell} "e"
2056 :|-@
{/
}^-
{t
}[ddd
] *
{\xor} ="xor"
2057 [lll
] *+=(
2,
0)+
[F
]{\mathstrut x_
{n-
1}} :|-@
{/
}_-
{t
} "xor"
2058 :|-@
{/
}^-
{t
}[dd
] *+=(
2,
0)+
[F
]{\mathstrut y_
{n-
1}}
2061 \caption{Encryption using OFB mode
}
2065 \begin{definition
}[OFB algorithms
]
2066 For any function $F
\colon \Bin^
\ell \to \Bin^t$, any initialization vector
2067 $v
\in \Bin^
\ell$, any plaintext $x
\in \Bin^*$ and any ciphertext $y
\in
2068 \Bin^*$, we define PRF encryption mode $
\id{OFB
} = (
\id{ofb-encrypt
},
2069 \id{ofb-decrypt
})$ as follows:
2071 Algorithm $
\id{ofb-encrypt
}(F, v, x)$: \+ \\
2074 $x
\gets x
\cat 0^
{t
\lceil L/t
\rceil - L
}$; \\
2075 $y
\gets \emptystring$; \\
2076 \FOR $i =
0$
\TO $(|x| - t')/t$
\DO \\
\ind
2077 $x_i
\gets x
[ti
\bitsto t(i +
1)
]$; \\
2078 $z_i
\gets F(s)$; \\
2079 $y_i
\gets x_i
\xor z_i$; \\
2080 $s
\gets s
\shift{t
} z_i$; \\
2081 $y
\gets y
\cat y_i$; \- \\
2082 \RETURN $(s, y
[0 \bitsto L
])$;
2084 Algorithm $
\id{ofb-decrypt
}(F, v, y)$: \+ \\
2085 \RETURN $
\id{ofb-encrypt
}(F, v, y)$;
2087 We now define the schemes $
\Xid{\E}{OFB$\$$
}^F$, $
\Xid{\E}{OFBC
}^
{F, c
}$,
2088 $
\Xid{\E}{OFBE
}^
{F, c
}$, and $
\Xid{\E}{OFBL
}^
{F, V_0
}$ according to
2089 definition~
\ref{def:enc-scheme
}; and we define the hybrid scheme
2090 $
\Xid{\E}{OFBH
}^
{F, V_0, c
}_
{n_L, n_C, n_E
}$ according to
2091 definition~
\ref{def:enc-hybrid
}.
2094 \begin{remark
}[Similarity to CFB mode
]
2095 \label{rem:ofb-like-cfb
}
2096 OFB mode is strongly related to CFB mode: we can OFB encrypt a message $x$
2097 by
\emph{CFB-encrypting
} the all-zero string $
0^
{|x|
}$ with the same key
2098 and IV. That is, we could have written $
\id{ofb-encrypt
}$ and
2099 $
\id{ofb-decrypt
}$ like this:
2101 Algorithm $
\id{ofb-encrypt
}(F, v, x)$: \+ \\
2102 $(s, z)
\gets \id{cfb-encrypt
}(F, v,
0^
{|x|
})$; \\
2103 \RETURN $(s, x
\xor z)$;
2105 Algorithm $
\id{ofb-decrypt
}(F, v, y)$: \+ \\
2106 \RETURN $
\id{ofb-encrypt
}(F, v, y)$;
2108 We shall use this fact to prove the security of OFB mode in the next
2112 \subsection{Security of OFB mode
}
2114 \begin{theorem
}[Security of OFB mode
]
2116 Let $F$ be a pseudorandom function from $
\Bin^
\ell$ to $
\Bin^t$; let $V_0
2117 \in \Bin^
\ell$ be a non-$t$-sliding string; let $c$ be a generalized
2118 counter in $
\Bin^
\ell$; and let $n_L$, $n_C$, $n_E$ and $q_E$ be
2119 nonnegative integers; and furthermore suppose that
2121 \item $n_L + n_C + n_E
\le q_E$,
2122 \item $n_L =
0$, or $n_C = n_E =
0$, or $
\ell \le t$ and $V_0
\ne c(i)$
2123 for any $n_L
\le i < n_L + n_C + n_E$, and
2124 \item either $n_C =
0$ or $
\ell \le t$.
2126 Then, for any $t_E$ and $
\mu_E$, and whenever
2128 \
[ \InSec{lor-cpa
}(
\Xid{\E}{OFBH
}^
{F, V_0, c
}_
{n_L, n_C, n_E
};
2129 t_E, q_E,
\mu_E)
\le
2130 2 \cdot \InSec{prf
}(F; t_E + q t_F, q) +
\frac{q (q -
1)
}{2^
\ell}
2132 where $q =
\bigl\lfloor \bigl(
\mu_E + q_E (t -
1)
\bigr)/t
\bigr\rfloor +
2133 n_E$, and $t_F$ is some small constant.
2137 \
[ \InSec{rog-cpa-$W_\$$
}
2138 (
\Xid{\E}{OFBH
}^
{\Func{\ell}{t
}, V_0, c
}_
{n_L, n_C, n_E
};
2140 \frac{q (q -
1)
}{2^
{\ell+
1}}.
2142 This follows from lemma~
\ref{lem:cfb-rog
}, which makes the same statement
2143 about CFB mode, and the observation in remark~
\ref{rem:ofb-like-cfb
}.
2144 Suppose $A$ attempts to distinguish OFBH encryption from $W_\$$. We define
2145 the adversary $B$ which uses $A$ to attack CFBH encryption, as follows:
2147 Adversary $B^
{E(
\cdot)
}$: \+ \\
2148 \RETURN $A^
{\id{ofb
}(
\cdot)
}$; \-
2150 Function $
\id{ofb
}(x)$: \+ \\
2151 $(v, z)
\gets E(
0^
{|x|
})$; \\
2152 \RETURN $(v, x
\xor z)$;
2154 Now we apply proposition~
\ref{prop:rog-and-lor
}; the theorem follows.
2159 Let $F$, $c$ and $V_0$ be as in theorem~
\ref{thm:ofb
}. Then for any $t_E$,
2161 \begin{eqnarray*
}[rl
]
2162 \InSec{lor-cpa
}(
\Xid{\E}{OFB$\$$
}^F; t_E, q_E,
\mu_E)
2163 &
\le 2 \cdot \InSec{prf
}(F; t_E + q t_F, q) +
\frac{q (q -
1)
}{2^
\ell}
2165 \InSec{lor-cpa
}(
\Xid{\E}{OFBE
}^
{F, c
}; t_E, q_E,
\mu_E)
2166 &
\le 2 \cdot \InSec{prf
}(F; t_E + q' t_F, q') +
2167 \frac{q' (q' -
1)
}{2^
\ell}
2169 \InSec{lor-cpa
}(
\Xid{\E}{OFBL
}^
{F, V_0
}; t_E, q_E,
\mu_E)
2170 &
\le 2 \cdot \InSec{prf
}(F; t_E + q t_F, q) +
\frac{q (q -
1)
}{2^
\ell}
2172 \tabpause{and, if $
\ell \le t$,
}
2173 \InSec{lor-cpa
}(
\Xid{\E}{OFBC
}^
{F, c
}; t_E, q_E,
\mu_E)
2174 &
\le 2 \cdot \InSec{prf
}(F; t_E + q t_F, q) +
\frac{q (q -
1)
}{2^
\ell}
2176 where $q =
\bigl\lfloor \bigl(
\mu_E + q_E (t -
1)
\bigr)/t
\bigr\rfloor +
2177 n_E$, $q' = q + q_E$, and $t_F$ is some small constant.
2180 Follows from theorem~
\ref{thm:ofb
} and proposition~
\ref{prop:enc-hybrid
}.
2185 Let $P$ be a pseudorandom permutation on $
\Bin^
\ell$, and let $c$ and $V_0$
2186 be as in theorem~
\ref{thm:ofb
}. Then for any $t_E$, $q_E$ and $
\mu_E$,
2187 \begin{eqnarray*
}[rl
]
2188 \InSec{lor-cpa
}(
\Xid{\E}{OFB$\$$
}^P; t_E, q_E,
\mu_E)
2189 &
\le 2 \cdot \InSec{prp
}(P; t_E + q t_F, q) +
\frac{q (q -
1)
}{2^
\ell}
2191 \InSec{lor-cpa
}(
\Xid{\E}{OFBE
}^
{P, c
}; t_E, q_E,
\mu_E)
2192 &
\le 2 \cdot \InSec{prp
}(P; t_E + q' t_F, q') +
2193 \frac{q' (q' -
1)
}{2^
\ell}
2195 \InSec{lor-cpa
}(
\Xid{\E}{OFBL
}^
{P, V_0
}; t_E, q_E,
\mu_E)
2196 &
\le 2 \cdot \InSec{prp
}(P; t_E + q t_F, q) +
\frac{q (q -
1)
}{2^
\ell}
2198 \tabpause{and, if $
\ell \le t$,
}
2199 \InSec{lor-cpa
}(
\Xid{\E}{OFBC
}^
{P, c
}; t_E, q_E,
\mu_E)
2200 &
\le 2 \cdot \InSec{prp
}(P; t_E + q t_F, q) +
\frac{q (q -
1)
}{2^
\ell}
2202 where $q =
\bigl\lfloor \bigl(
\mu_E + q_E (t -
1)
\bigr)/t
\bigr\rfloor +
2203 n_E$, $q' = q + q_E$, and $t_F$ is some small constant.
2206 Follows from corollary~
\ref{cor:ofb-prf
} and
2207 proposition~
\ref{prop:prps-are-prfs
}.
2210 %%%--------------------------------------------------------------------------
2212 \section{CBCMAC mode message authentication
}
2218 \begin{cgraph
}{cbc-mac
}
2219 []!
{<
0.425cm,
0cm>: <
0cm,
0.75cm>::
}
2220 *+=(
2,
0)+
[F
]{\mathstrut x_0
}
2221 :`d
[dr
] [rrr
] *+
[F
]{E
} ="e"
[d
] {K
} :"e"
2222 :
[rrr
] *
{\xor} ="xor"
2223 [u
] *+=(
2,
0)+
[F
]{\mathstrut x_1
} :"xor"
2224 :
[rrr
] *+
[F
]{E
} ="e"
[d
] {K
} :"e"
2225 :@
{-->
}[rrr
] *
{\xor} ="xor"
2226 [u
] *+=(
2,
0)+
[F--
]{\mathstrut x_i
} :@
{-->
}"xor"
2227 :@
{-->
}[rrr
] *+
[F
]{E
} ="e"
[d
] {K
} :@
{-->
}"e"
2228 :@
{-->
}[rrr
] *
{\xor} ="xor"
2229 [u
] *+=(
2,
0)+
[F
]{\mathstrut x_
{n-
1}} :"xor"
2230 :
[rrr
] *+
[F
]{E
} ="e"
[d
] {K
} :"e"
2231 :
[rrr
] *+=(
2,
0)+
[F
]{\mathstrut \tau}
2234 \caption{Message authentication using CBCMAC mode
}
2239 Alas, it's been so long since I've picked this up that I've (a) forgotten how
2240 the proof for this mode went, and (b) lost my notes. You'll either have to
2241 wait, or I'll have to drop this bit.
2243 %%%--------------------------------------------------------------------------
2245 \section{Ackonowledgements
}
2247 Thanks to Clive Jones for his suggestions on notation, and his help in
2248 structuring the proofs.
2250 %%%----- That's all, folks --------------------------------------------------
2252 \bibliography{mdw-crypto,cryptography2000,cryptography,rfc
}
2256 %%% Local Variables: