}
\fi
\def\fixme{\marginpar{FIXME}}
+\def\hex#1{\texttt{#1}_{x}}
\newslowboxenv{cgraph}{\par$$}{\begin{graph}}{\end{graph}}{$$\par}
\newslowboxenv{vgraph}
errors we discovered in previous work, or some combination of these. We
provide a new security notion for symmetric encryption which turns out to
be rather useful when analysing block cipher modes. Finally, we define a
- new, condition for initialization vectors, introducing the concept of a
- `generalized counter', and proving that generalized suffice for security in
- (full-width) CFB and OFB modes and that generalized counters encrypted
- using the block cipher (with the same key) suffice for all the encryption
- modes we study.
+ new condition for initialization vectors, introducing the concept of a
+ `generalized counter', and proving that generalized counters suffice for
+ security in (full-width) CFB and OFB modes and that generalized counters
+ encrypted using the block cipher (with the same key) suffice for all the
+ encryption modes we study.
\end{abstract}
\iffancystyle
The following proposition relates our new notion to the existing known
notions of security.
+\begingroup
+\def\Wror{{W_{\text{ROR}}}}
\begin{proposition}[ROG $\Leftrightarrow$ LOR]
\label{prop:rog-and-lor}
Let $\E$ be a symmetric encryption scheme. Then,
\InSec{rog-cpa-$W$}(\E; t + t_E \mu_E, q_E, \mu_E)
\]
and
- \item there exists a garbage-emission algorithm $W$ for which
- \[ \InSec{rog-cpa-$W$}(\E; t, q_E, \mu_E)
+ \item there exists a garbage-emission algorithm $\Wror$ for which
+ \[ \InSec{rog-cpa-$\Wror$}(\E; t, q_E, \mu_E)
\le \InSec{lor-cpa}(\E; t + t_E \mu_E, q_E, \mu_E)
\]
\end{enumerate}
for some fairly small constant $t_E$.
\end{proposition}
-\begin{proof}
+\begin{remark}
+ Note the asymmetry between these two statements. ROG-CPA-$W$ implies
+ LOR-CPA for \emph{any} garbage emitter $W$, but LOR-CPA implies
+ ROG-CPA-$\Wror$ for the specific emitter $\Wror$ only.
+\end{remark}
+\begin{proof}[Proof of proposition \ref{prop:rog-and-lor}]
\begin{enumerate}
\item Let $W$ and $\E$ be given, and let $A$ be an adversary attacking the
LOR-CPA security of $\E$. Consider adversary $B$ attacking $\E$'s
\frac{1}{2}$. The result follows.
\item Let $\E = (G, E, D)$ be given. Our garbage emitter simulates the
real-or-random game of \cite{Bellare:2000:CST}. Let $K_W = \bot$
- initially: we define our emitter $W$ thus:
+ initially: we define our emitter $\Wror$ thus:
\begin{program}
- Garbage emitter $W(n)$: \+ \\
+ Garbage emitter $\Wror(n)$: \+ \\
\IF $K_W = \bot$ \THEN $K_W \gets G()$; \\
$x \getsr \Bin^n$; \\
- \RETURN $E_K(x)$;
+ \RETURN $E_{K_W}(x)$;
\end{program}
- We now show that $\InSec{rog-cpa-$W$}(\E; t, q_E, \mu_E) \le
- \InSec{lor-cpa}(\E; t + t_E \mu_E, q_E, \mu_E)$ for our $W$. Let $A$ be
- an adversary attacking the ROG-CPA-$W$ security of $\E$. Consider
+ We now show that $\InSec{rog-cpa-$\Wror$}(\E; t, q_E, \mu_E) \le
+ \InSec{lor-cpa}(\E; t + t_E \mu_E, q_E, \mu_E)$ for our $\Wror$. Let $A$
+ be an adversary attacking the ROG-CPA-$\Wror$ security of $\E$. Consider
adversary $B$ attacking $\E$'s LOR-CPA security:
\begin{program}
Adversary $B^{E(\cdot, \cdot)}$: \+ \\
$x' \getsr \Bin^{|x|}$; \\
\RETURN $E(x', x)$;
\end{program}
- The adversary simulates the ROG-CPA-$W$ games perfectly for our chosen
- $W$, since the game has chosen the random $K_W$ for us already: the
- `left' game returns only the results of encrypting random `garbage'
- plaintexts $x'$, while the right game returns correct results of
- encrypting the given plaintexts $x$. The result follows.
- \qed
+ The adversary simulates the ROG-CPA-$\Wror$ games perfectly, since the
+ game has chosen the random $K_W$ for us already: the `left' game returns
+ only the results of encrypting random `garbage' plaintexts $x'$, while
+ the right game returns correct results of encrypting the given plaintexts
+ $x$. The result follows. \qed
\end{enumerate}
\end{proof}
-
+\endgroup
\subsection{Message authentication}
all plaintexts $x$ and all initialization vectors $v$, if $(v', y) =
\id{encrypt}^{P(\cdot)}(v, x)$ then $x = \id{decrypt}^{P(\cdot),
P^{-1}(\cdot)}(v, y)$.
- \item There exists an efficient algorithm which, given a ciphertext $y$ and
- the initialization vector but \emph{not} access to $P$, computes the
- chaining value $v'$ such that $(v', y) = \id{encrypt}^P(v, x)$.
\end{enumerate}
Similarly, a \emph{PRF encryption mode} $m_F = (\id{encrypt},
\id{decrypt})$ is a pair of deterministic oracle algorithms (and
\item For all functions $F\colon \Bin^\ell \to \Bin^L$, all plaintexts $x$
and all initialization vectors $v$, if $(v', y) =
\id{encrypt}^{F(\cdot)}(v, x)$ then $x = \id{decrypt}^{F(\cdot)}(v, y)$.
- \item There exists an efficient algorithm which, given a ciphertext $y$ and
- the initialization vector but \emph{not} access to $F$, computes the
- chaining value $v'$ such that $(v', y) = \id{encrypt}^F(v, x)$.
- \qed
+ \qed
\end{enumerate}
\end{definition}
encryption schemes of definition~\ref{def:enc-scheme}, constructed from a
pseudorandom permutation $P\colon \Bin^\ell \leftrightarrow \Bin^\ell$.
If $q$ is an upper bound on the number of PRP applications required for
- the encryption $q_E$ messages totalling $\mu_E$ bits, and $t'$ is some
- small constant, then
+ the encryption $q_E$ messages totalling $\mu_E$ bits, then there is some
+ small constant $t'$ such that
\[ \InSec{lor-cpa}(\E^P; t, q_E, \mu_E) \le
\InSec{lor-cpa}(\E^{\Perm{\ell}}; t, q_E, \mu_E) +
2 \cdot \InSec{prp}(P; t + q t', q) .
symmetric encryption schemes of definition~\ref{def:enc-scheme},
constructed from a pseudorandom function $F\colon \Bin^\ell \to \Bin^L$.
If $q$ is an upper bound on the number of PRP applications required for
- the encryption $q_E$ messages totalling $\mu_E$ bits, and $t'$ is some
- small constant, then
+ the encryption $q_E$ messages totalling $\mu_E$ bits, then there is some
+ small constant $t'$ such that
\[ \InSec{lor-cpa}(\E^F; t, q_E, \mu_E) \le
\InSec{lor-cpa}(\E^{\Func{\ell}{L}}; t, q_E, \mu_E) +
2 \cdot \InSec{prf}(F; t + q t', q) .
\end{proposition}
\begin{proof}
- For 1, it suffices to note that $\Xid{E}{$m\$$}^F \equiv \Xid{E}{$m$H}^{c,
- V_0}_{0, 0, 0}$ for any $c$, $V_0$. For the others, we observe that, while
- the IVs returned in the ciphertexts differ, it's very easy to simulate
- encryption for the practical schemes given an encryption oracle for the
- hybrid scheme: for the counter and encrypted-counter schemes, the counter
- function is public knowledge; for the carry-over scheme, the correct IV for
- the first message is known, and the IV any subsequent messages can be
- computed from the previous IV and ciphertext according to condition~4 in
- definition~\ref{def:enc-scheme}.
+ For 1, it suffices to observe that $\Xid{E}{$m\$$}^F \equiv
+ \Xid{E}{$m$H}^{F, V_0, c}_{0, 0, 0}$ for any $c$, $V_0$. For 2, note that
+ $\Xid{E}{$m$C}^{F, c}$ behaves identically to $\Xid{E}{$m$H}^{F, V_0,
+ c}_{q_E, 0, 0}$ for any $c$, $V_0$ for the first $q_E$ encryption
+ queries; but no adversary is permitted to exceed this limit, and hence no
+ adversary can distinguish the two. Similarly, for 4, note that
+ $\Xid{E}{$m$L}^{F, V_0}$ behaves identically to $\Xid{E}{$m$H}^{F, V_0,
+ c}_{0, 0, q_E}$ for any $c$, $V_0$ for the first $q_E$ encryption
+ queries.
+
+ The case of 3 is slightly more complicated: $\Xid{E}{$m$E}^{F, c}$ behaves
+ identically to $\Xid{E}{$m$H}^{F, V_0, c}_{0, q_E, 0}$ for the first $q_E$
+ encryption queries \emph{except} that the latter returns different
+ initialization vectors from its encryption oracle. However, since the
+ counter $c$ is fixed public knowledge, it is trivial to construct a fully
+ faithful replica of the $m$E game given the hybrid oracle, such that no
+ adversary can distinguish the two.
\end{proof}
%%%--------------------------------------------------------------------------
\RETURN $(v, x)$;
\end{program}
Now, let $c$ be a generalized counter in $\Bin^\ell$. We define the
- encryption schemes $\Xid{E}{CBC$\$$}^P$, $\Xid{E}{CBCE}^P$ and
+ encryption schemes $\Xid{E}{CBC$\$$}^P$, $\Xid{E}{CBCE}^{P, c}$ and
$\Xid{E}{CBCH}^{P, c, \bot}_{0, 0, n_E}$, as described in
definition~\ref{def:enc-scheme}.
\end{definition}
\begin{theorem}[Security of hybrid CBC mode]
\label{thm:cbc}
Let $P\colon \keys P \times \Bin^\ell \to \Bin^\ell$ be a pseudorandom
- permutation; let $v_0 \in \Bin^\ell$ be an initialization vector; let $n_L
- \in \{\, 0, 1 \,\}$; let $c$ be a generalized counter in $\Bin^\ell$; and
+ permutation; let $V_0 \in \Bin^\ell$ be an initialization vector; let $n_L
+ \in \{ 0, 1 \}$; let $c$ be a generalized counter in $\Bin^\ell$; and
let $n_C \in \N$ be a nonnegative integer; and suppose that at most one of
$n_L$ and $n_C$ is nonzero. Then, for any $t$, $q_E \ge n$ and $\mu_E$,
\[ \InSec{lor-cpa}
- (\Xid{\E}{CBCH}^{P, c, v_0}_{n_L, 0, n_E}; t, q_E, \mu_E) \le
+ (\Xid{\E}{CBCH}^{P, c, V_0}_{n_L, 0, n_E}; t, q_E, \mu_E) \le
2 \cdot \InSec{prp}(P; t + q t_P, q) + \frac{q (q - 1)}{2^\ell - q}
\]
where $q = n_L + n_E + \mu_E/\ell$ and $t_P$ is some small constant.
\frac{q' (q' - 1)}{2^\ell - q'}
\\
\tabpause{and}
- \InSec{lor-cpa}(\Xid{\E}{CBCL}^{P, v_0}; t, 1, \mu_E)
+ \InSec{lor-cpa}(\Xid{\E}{CBCL}^{P, V_0}; t, 1, \mu_E)
& \le 2 \cdot \InSec{prp}(P; t + q t_P, q) +
\frac{q (q - 1)}{2^\ell - q}
\end{eqnarray*}
$2^\ell - q \approx 2^\ell$, and for larger $q$, the term $q (q - 1)/2^\ell
> 1$ anyway, so all security is lost (according to the above result).
Compared to \cite[theorem~17]{Bellare:2000:CST}, we gain the tiny extra
- term in the denominator, but lose the PRP-as-a-PRF term $q^2
- 2^{-\ell-1}$.\footnote{%
+ term in the denominator, but lose the PRP-as-a-PRF term
+ $q^2/2^{\ell-1}$.\footnote{%
In fact, they don't prove the stated bound of $q (3 q - 2)/2^{\ell+1}$
but instead the larger $q (2 q - 1)/2^\ell$. The error is in the
application of their proposition~8: the PRF-insecurity term is doubled,
\label{fig:cbc-steal}
\end{figure}
-Encrypting messages shorter than the block involves `IV stealing', which is a
-grotty hack but works fine if IVs are random; if the IVs are encrypted
+Encrypting messages shorter than the block involves `IV stealing' -- using
+the IV instead of the ciphertext from the last full-length block -- which is
+a grotty hack but works fine if IVs are random; if the IVs are encrypted
counters then there's nothing (modifiable) to steal from.
We formally present a description of a randomized CBC stealing mode.
to prove the claim that there exists a garbage-emitter $W$ such that
\[
\InSec{rog-cpa-$W$}
- (\Xid{\E}{CBCH}^{\Perm{\ell}, c, v_0}_{n_L, 0, n_E};
+ (\Xid{\E}{CBCH}^{\Perm{\ell}, c, V_0}_{n_L, 0, n_E};
t, q_E, \mu_E) \le
\frac{q (q - 1)}{2 \cdot (2^\ell - n)}.
\]
apply proposition~\ref{prop:enc-info-to-real} to obtain the required result.
Our garbage-emitter $W$ is a bit complicated. It chooses random but
-\emph{distinct} blocks for the `ciphertext'; for the IVs, it uses $v_0$ for
+\emph{distinct} blocks for the `ciphertext'; for the IVs, it uses $V_0$ for
the first message if $n_L = 1$, and otherwise it chooses random blocks
distinct from each other and the `ciphertext' blocks for the next $n_E$
messages, and just random blocks for subsequent ones. The algorithm $W$ is
\next
Garbage emitter $W(m)$: \+ \\
\IF $i \ge 2^\ell$ \THEN \ABORT; \\
- \IF $i < n_L$ \THEN $v \gets v_0$; \\
+ \IF $i < n_L$ \THEN $v \gets V_0$; \\
\ELSE \IF $i < n$ \THEN $v \gets \id{fresh}()$; \\
$i \gets i + 1$ \\
\ELSE $v \getsr \Bin^\ell$; \\
We need some notation to describe the values in the game. Let $c_i = c(i)$
be the $i$th counter value, for $0 \le i < n_E$, and let $v_i$ be the $i$th
-initialization vector, where $v_0$ is as given if $n_L = 1$, $v_i = P(c_i -
-n_L)$ if $n_L \le i < n$, and $v_i \inr \Bin^\ell$ if $n \le i < q_E$. Let
-$q' = \mu_E/\ell = q - n$ be the total number of plaintext blocks in the
-adversary's queries, let $x_i$ be the $i$th plaintext block queried, let
-$y_i$ be the $i$th ciphertext block returned, let
+initialization vector, where $v_0 = V_0$ is as given if $n_L = 1$, $v_i =
+P(c_i - n_L)$ if $n_L \le i < n$, and $v_i \inr \Bin^\ell$ if $n \le i <
+q_E$. Let $q' = \mu_E/\ell = q - n$ be the total number of plaintext blocks
+in the adversary's queries, let $x_i$ be the $i$th plaintext block queried,
+let $y_i$ be the $i$th ciphertext block returned, let
\[ w_i = \begin{cases}
v_j & if block $i$ is the first block of the $j$th query, and \\
y_{i-1} & otherwise
definition~\ref{def:enc-hybrid}.
\end{definition}
-\subsection{Security of CFB mode}
+\subsection{Sliding strings}
-%% I suspect David will want to put some negative results here, and complain
-%% about Alkassar et al.'s alleged proof. I'll press on with the positive
-%% stuff.
-%%
-%% The problems come when $t < \ell$. Then C-mode isn't necessarily secure
-%% (well, we get a similar bound with $t$ instead of $\ell$, which isn't very
-%% impressive). The L-mode needs careful selection of the initial IV.
+Consider for a moment the mode CFBL, i.e., with carry-over of IV from one
+plaintext to the next, with $t < \ell$. Then we find that some IVs are
+weak.
+
+Pretend for a moment that we're an adversary playing the LOR-CPA game using
+an ideal random function $F \inr \Func{\ell}{t}$, and that the initial IV
+$V_0 = 0^\ell$. We choose two distinct 8-bit plaintexts $l$ and $r$ as our
+first left-or-right query. With probability $2^{-t}$, the result of
+encrypting that first query is $0^t$. However, in this case, the IV for the
+\emph{next} query is $V_0 \shift{t} 0^t = 0^\ell = V_0$. If this happens,
+we have only to submit the pair $(l, l)$ as our second query. If the
+ciphertext to this second query also comes back zero, we guess that we're
+dealing with a left oracle; otherwise we guess right. If we don't get lucky
+with our first query, we just guess randomly.
+
+\begin{figure}
+ \begin{program}
+ Adversary $S^{E(\cdot, \cdot)}$: \+ \\
+ $l \gets 0^t$; $r \gets 0^{t - 1} 1$; \\
+ $y \gets E(l, r)$; \\
+ \IF $y[\ell \bitsto \ell + t] = 0^t$ \THEN \\ \ind
+ \IF $E(l, l) = y$ \THEN $b \gets 0$ \ELSE $b \gets 1$; \- \\
+ \ELSE \\ \ind
+ $b \getsr \{0, 1\}$; \- \\
+ \RETURN $b$;
+ \end{program}
+ \caption{Adversary $S$ attacking $\Xid{\E}{CFBL}^{\Func{\ell}{t}, 0^\ell}$}
+ \label{fig:adv-sliding}
+\end{figure}
+
+This attack is shown more formally as adversary~$S$ in
+figure~\ref{fig:adv-sliding}. Its resource usage is almost trivial --
+negligible computation and at most two encryption queries. However, its
+advantage is quite good:
+\[ \Adv{LOR-CPA}{\Xid{\E}{CFBL}^{\Func{\ell}{t}, 0^\ell}}(S) =
+ \frac{1}{2^t} \biggl( 1 - \frac{1}{2^t} \biggr).
+\]
+
+This attack works because $V_0[t \bitsto \ell] = V_0[0 \bitsto \ell - t]$.
+There are similar attacks for other such relationships. The following
+definition characterizes these kinds of `bad' IVs.
\begin{definition}[Sliding strings]
\label{def:slide}
$t$-slide.
\end{remark}
+%% Thinking about the probability that a random l-bit string t-slides...
+%%
+%%
+
+\subsection{Security of CFB mode}
+
+%% I suspect David will want to put some negative results here, and complain
+%% about Alkassar et al.'s alleged proof. I'll press on with the positive
+%% stuff.
+%%
+%% The problems come when $t < \ell$. Then C-mode isn't necessarily secure
+%% (well, we get a similar bound with $t$ instead of $\ell$, which isn't very
+%% impressive). The L-mode needs careful selection of the initial IV.
+
\begin{theorem}[Security of CFB mode]
\label{thm:cfb}
Let $F$ be a pseudorandom function from $\Bin^\ell$ to $\Bin^t$; let $V_0
be as in theorem~\ref{thm:cfb}. Then for any $t_E$, $q_E$ and $\mu_E$,
\begin{eqnarray*}[rl]
\InSec{lor-cpa}(\Xid{\E}{CFB$\$$}^P; t_E, q_E, \mu_E)
- & \le 2 \cdot \InSec{prp}(P; t_E + q t_F, q) + \frac{q (q - 1)}{2^\ell}
+ & \le 2 \cdot \InSec{prp}(P; t_E + q t_F, q) +
+ \frac{q (q - 1)}{2^{\ell-1}}
\\
\InSec{lor-cpa}(\Xid{\E}{CFBE}^{P, c}; t_E, q_E, \mu_E)
& \le 2 \cdot \InSec{prp}(P; t_E + q' t_F, q') +
- \frac{q' (q' - 1)}{2^\ell}
+ \frac{q' (q' - 1)}{2^{\ell-1}}
\\
\InSec{lor-cpa}(\Xid{\E}{CFBL}^{P, V_0}; t_E, q_E, \mu_E)
- & \le 2 \cdot \InSec{prp}(P; t_E + q t_F, q) + \frac{q (q - 1)}{2^\ell}
+ & \le 2 \cdot \InSec{prp}(P; t_E + q t_F, q) +
+ \frac{q (q - 1)}{2^{\ell-1}}
\\
\tabpause{and, if $\ell \le t$,}
\InSec{lor-cpa}(\Xid{\E}{CFBC}^{P, c}; t_E, q_E, \mu_E)
- & \le 2 \cdot \InSec{prp}(P; t_E + q t_F, q) + \frac{q (q - 1)}{2^\ell}
+ & \le 2 \cdot \InSec{prp}(P; t_E + q t_F, q) +
+ \frac{q (q - 1)}{2^{\ell-1}}
\end{eqnarray*}
where $q = \bigl\lfloor \bigl(\mu_E + q_E (t - 1)\bigr)/t \bigr\rfloor +
n_E$, $q' = q + q_E$, and $t_F$ is some small constant.
are a multiple of $t$ bits in length; obviously all of the oracle responses
for a block-respecting adversary are also a multiple of $t$ bits in length.
\begin{claim*}
- If $A'$ be a block-respecting adversary querying a total of $\mu_E$ bits of
+ Let $A'$ be a block-respecting adversary querying a total of $\mu_E$ bits of
plaintext queries; then
\[ \Adv{}{}(A') \le \frac{q (q - 1)}{2^{\ell+1}} \]
where $q = \mu_E/t$.
\label{fig:cbcmac}
\end{figure}
-\fixme
+\leavevmode\fixme
Alas, it's been so long since I've picked this up that I've (a) forgotten how
the proof for this mode went, and (b) lost my notes. You'll either have to
wait, or I'll have to drop this bit.
%%%--------------------------------------------------------------------------
-\section{Ackonowledgements}
+\section{Acknowledgements}
-Thanks to Clive Jones for his suggestions on notation, and his help in
-structuring the proofs.
+Thanks are due to David Wagner for pointing me at \cite{Alkassar:2001:OSS}
+and warning me of the dangers of sliding IVs in CFB mode. Thanks also to
+Clive Jones for his suggestions on notation, and his help in structuring the
+proofs.
%%%----- That's all, folks --------------------------------------------------
~mdw / doc / modes / blobdiff